Scientific publications

This paper analyzes the problem of optimal control of two work-stealing deques in two-level memory (for example, registers—random access memory), where probabilities of parallel operations with deques are known. The classic sequential cyclic method for representing a deque in memory is considered. In the case of the deque overflowing in fast memory or emptying the FIFO-part or LIFO-part the necessary exchanges between fast and slow memory and shifts of elements in fast memory occur for relocation to the optimal state, which to be found. The task is to find the optimal partition of the total fast memory for deques and to determine the optimal state of each deque in each partition after the memory reallocation, i.e., to find the optimal number of elements, taken from both sides of the deque, to leave in the fast memory if the deque is filled or emptied. Optimality criteria for memory sharing is to maximize the sum of the mean operating times of each deque before the memory is redistributed and to maximize the lowest mean operating time of each deque before the memory is redistributed. The mathematical model in the form of an absorbing Markov chain are constructed. Simulation modeling, based on the proposed mathematical model, was carried out. The results of numerical experiments are presented.