Метод представления трех work-stealing деков в двухуровневой памяти

Е. А. Аксенова^a, Е. А. Барковский, А. В. Соколов<sup>a

a</sup> Институт прикладных математических исследований Карельского научного центра Российской академии наук (185910 Петрозаводск, ул. Пушкинская, д. 11)

Аннотация: Эффективность работы распределенных систем во многом зависит от равномерной загруженности потоков, что обеспечивается за счет различных стратегий балансировки задач между ними. Одним из методов децентрализованной динамической стратегии балансировки, где каждый поток участвует в распределении задач, является «work-stealing». Принцип метода в том, что поток не имеющий задач перехватывает («steal») их у других потоков. В основе процесса лежит специальная структура данных, work-stealing дек, в котором находятся указатели на задачи. При работе с деками возникает проблема их эффективного расположения в памяти. В двухуровневой памяти дек можно расположить разделив его на концы и середину: в быстрой памяти (первый уровень) находятся вершина и основание дека; в медленной памяти (второй уровень) — середина. Таким образом, система может быстро обращаться к концам дека, где элементы активно добавляются и удаляются. В статье анализируется новый метод представления трех work-stealing деков в двухуровневой памяти, где концы деков находятся в отдельных участках памяти. Для него строится имитационная модель на основе метода Монте-Карло, с помощью которой исследуются задачи оптимального разделения памяти. В качестве критерия оптимальности используется максимальное среднее время работы системы до перераспределения памяти.

Ключевые слова: двухуровневая память, метод Монте-Карло, структуры данных, work-stealing деки.

УДК: 004.942

Поступила в редакцию: 21.07.2025