Оптимальное управление двумя work-stealing деками в общей памяти при различных стратегиях перехвата работы

В параллельных балансировщиках задач, работающих по стратегии work-stealing, каждый процессор имеет свой дек (deque) задач. Один конец дека используется только владельцем для добавления и извлечения задач, а другой — для перехвата другими процессорами. Целью работы является построение и анализ математических моделей процесса работы с двумя циклическими деками, расположенными в общей памяти. Параметрами этих моделей являются вероятности операций на каждом шаге дискретного времени (возможно как последовательное, так и параллельное выполнение операций). Модели строятся в виде случайных блужданий по целочисленной решетке на плоскости. На основе вышеупомянутых моделей решены задачи оптимального разделения памяти при некоторых стратегиях перехвата элементов. В качестве критерия оптимальности рассматривается максимальное среднее время до переполнения памяти. Проведены статистические исследования по оценке вероятностей операций работы с деками для нескольких типов задач, выполняемых в реализованном балансировщике. Для полученных вероятностей операций работы с деками проведены численные эксперименты по анализу разработанных моделей