Способ управления памятью компьютерной системы

Настоящее изобретение относится к системам и способам управления компьютерными системами и может быть использовано в операционных системах, планировщиках, менеджерах памяти.

Известен способ страничного представления в компьютерной системе. В этом способе каждый work-stealing дек представлен в виде двухсвязного списка узлов фиксированного размера. Узлы динамически выделяются и освобождаются из общего пула узлов, доступного множеству процессоров. Когда процессор израсходовал свои локальные ресурсы памяти (дек), он перехватывает их у другого процессора, у которого эти ресурсы есть (Патент США US 7779222, опубликовано 17.08.2010 г.).

Основными недостатками способа являются дополнительные временные расходы при работе со списками и потери памяти по двум адресам на каждый узел списка для хранения указателей на другие узлы. Этот способ предназначен для представления стеков и очередей в виде связного списка массивов (узлов) и зависит от выбора размера узла, что приводит к многооперационости.

Известны способы оптимального управления двумя последовательными, циклическими деками, для которых построены и проанализированы математические модели процесса работы. Деки расположены в разделенной общей памяти, где каждому деку выделен свой отдельный участок памяти. В способах сравнивается время работы системы, общая память которой разделена поровну между деками, и системы, где память разделена оптимально, в зависимости от вероятностных характеристик операций с деками (Источники: Барковский Е.А. Математические модели и методы оптимального управления Work-stealing деками в общей памяти // Стохастическая оптимизация в информатике, Т. 11, №1, 2015 г.; Sokolov A. Barkovsky Е. The Mathematical Model and The Problem of Optimal Partitioning of Shared Memory for Work-Stealing Deques // International Conference on Parallel Computing Technologies, 2015 г.; Соколов A.B., Барковский Е.А. Вероятностная модель для задачи оптимального управления Work-stealing деками // Всероссийский Симпозиум по прикладной и промышленной математике, 2015 г.; Вероятностная модель для задачи оптимального управления work-stealing деками при различных стратегиях перехвата работы // Вероятностные методы в дискретной математике, 2016 г.).

Однако для использования данных способов на практике надо проводить предварительные статистические исследования для оценки вероятностей операций с деками в исследуемых приложениях, что усложняет процесс и делает его трудоемким.

Наиболее близким является способ управления work-stealing деками в компьютерной системе, имеющей интегральные схемы для одновременного выполнения нескольких процессов и общую память, хранящую деки с информацией, требуемой для выполнения задач системы с последовательным циклическим представлением структуры данных. В этом способе у каждого потока есть свой дек, который представлен в виде циклического массива, а общая память заранее разделена и для ее управления используется стандартный метод динамического распределения памяти. Когда поток пытается добавить новое значение в циклический массив своего дека, а он переполнен, содержимое дека копируется в циклический массив большего размера и система настраивается для работы с ним (Патент США US 7363438, опубликовано 22.04.2008 г.).

Данный способ описан для одного дека и не учитывает параметры других деков. Недостатком способа также является то, что при переполнении дека стандартный механизм работы с динамической памятью выделяет новый больший массив и элементы дека копируются туда, а старый массив возвращается в список свободной памяти, что требует дополнительных затрат времени и может приводить к уменьшению среднего времени работы компьютерной системы до переполнения.

В основу изобретения положена задача создания универсального способа управления памятью компьютерной системы, направленного на повышение эффективности использования памяти компьютерной системы.

Техническим результатом изобретения является увеличение среднего времени работы компьютера до переполнения доступной памяти компьютерной системы.

Заявляемый технический результат достигается тем, что в способе управления памятью компьютерной системы, включающей интегральные схемы для одновременного выполнения нескольких процессов и общую память, хранящую work-stealing деки с последовательным представлением структуры данных, согласно изобретению общая память циклична и не разделена между деками, количество которых два и более и они последовательно двигаются в одном направлении, друг за другом, через равные промежутки единиц памяти, при этом новые деки начинают расти из середины свободного пространства памяти.

Заявляемый способ управления памятью компьютерной системы применим:

- ко всем типам процессорных устройств, которые могут быть частью системы как симметричного, так и асимметричного мультипроцессирования и количество которых больше или равно двум;

- ко всем типам памяти любого размера, которые делятся между двумя или большим количеством процессорных устройств и имеют фиксированный размер одной ячейки памяти;

- ко всем типам данных, которые хранятся в общей памяти в буферах вида «work-stealing» деков, обрабатываются процессорными устройствами и имеют фиксированный размер одной структурной единицы, который равен целому числу ячеек памяти (при делении размера общей памяти на размер одной структурной единицы остатка нет);

- ко всем механизмам, срабатывающим после переполнения общей памяти; ко всем стратегиям «work-stealing», в которых осуществляется перехват целого количества структурных единиц.

Способ управления памятью компьютерной системы осуществляется следующим образом.

Общая память циклична и представляется в виде круга. В одну или несколько ячеек памяти записывается одна структурная единица данных, которая будет обработана процессорным устройством. Следующая структурная единица данных, которая будет обработана этим же процессорным устройством, записывается вплотную к предыдущей. Таким образом в общей памяти, для процессорного устройства возникает последовательность элементов - буфер, у которой определяют голову - первый элемент последовательности и хвост - последний элемент последовательности. Этот буфер работает по принципу «work-stealing» дека, т.е. включение элементов осуществляется в головной конец дека и только процессорным устройством - хозяином дека. Включенный элемент становится первым элементом дека - головой. Исключение осуществляется из двух концов дека: если исключение производит процессорное устройство - хозяин дека, то из головного конца, в таком случае головой дека становится следующий в последовательности элемент; если исключение производит другое процессорное устройство, то из хвостового конца дека, в таком случае хвостом дека становится предыдущий в последовательности элемент. Структурная единица данных для другого процессорного устройства записывается в середину свободного пространства памяти.

Свободный участок памяти, в котором будет расти новый дек, выбирается согласно используемому в системе механизму: случайным образом; наибольший размер; наименьший размер и т.д. Когда требуется разместить в пустой памяти несколько структурных единиц данных, предназначенных разным процессорным устройствам, то их размещают через равные или примерно равные промежутки памяти. Впоследствии элементы данных для процессорных устройств записывается в свои деки таким образом, что голова одного дека направлена в сторону хвоста другого. Так, в процессе работы компьютерной системы в общей памяти образуются «work-stealing» деки, двигающиеся друг за другом, по кругу.

Изобретение иллюстрируется фигурами.

На фиг. 1 показано начало работы компьютерной системы, имеющей n процессорных устройств и, как следствие, n work-stealing деков. В деках уже имеется по одному элементу. Представленный вариант является идеальным случаем начала работы системы: каждый дек начинает расти через равные промежутки памяти, расстояние а между двумя деками одинаково.

На фиг. 2 представлен вариант появления work-stealing дека. В системе имеется три процессорных устройства, в двух из которых уже хранится некоторое количество элементов. Вариант разбит на этапы: I - исходное состояние системы; II - выбор места для записи элемента, предназначенного для третьего процессорного устройства (здесь выбран наибольший участок памяти между двумя уже существующими деками); III - запись этого элемента и, как следствие, появление третьего дека.

На фиг. 3 показан вариант работы компьютерной системы, реализующий заявляемое изобретение. Компьютерная система содержит два процессора, которые делят общую память на 8 ячеек. Данными, которые обрабатывают процессоры, являются указатели на задачи. Размер указателя совпадает с размером ячейки памяти. Стратегия перехвата элемента - один элемент.

В табл. 1 представлены результаты имитационного моделирования. Время работы компьютерной системы, реализованной по предлагаемому способу, сравнивается со временем работы компьютерной системы, где память заранее разделена между деками: первому деку выделено s=50 единиц памяти; второму - m-s=50 единиц. Общий размер памяти m=100 единиц. Стратегия work-stealing - перехват одного элемента.

В табл. 2 представлены результаты имитационного моделирования. Входные данные те же, что и в табл. 1, однако отражена стратегия work-stealing перехвата половины элементов.

Пример (фиг. 3). Компьютерная система содержит два процессора, которые делят общую память на 8 ячеек. Данные, которые обрабатывают процессоры, являются указатели на задачи. Размер указателя совпадает с размером ячейки памяти. Стратегия перехвата элемента - один элемент.

Процесс работы компьютерной системы состоит из следующих шагов:

1. Исходное состояние системы, общая память представлена в виде круга, т.е. зациклена.

2. Первый процессор добавляет указатель на задачу, которую он должен выполнить. Для процессора создается буфер задач, представленный в виде «work-stealing» дека.

3. Второй процессор добавляет указатель на задачу, которую он должен выполнить. Этот указатель помещается в середину свободного пространства памяти и создается второй «work-stealing» дек.

4. Первый и второй процессоры одновременно помещают указатели на свои задачи в свои деки. В каждом деке находится по два элемента и теперь можно различить и голову - первый элемент и хвост - последний элемент дека.

5. Первый процессор добавляет указатель на задачу. Он помещается в начало дека и, соответственно, становится первым элементом дека или его головой. В это же время второй процессор начинает выполнять выделенную ему задачу. Он удаляет указатель на задачу из своего дека, т.е. он удаляет первый элемент дека. После этого в деке остается только один элемент.

6. Первый и второй процессор одновременно начинают выполнять свои задачи и удаляют указатели на них из своих деков. Дек второго процессора становится пустым.

7. В дек второго процессора не произошло включений, и он перехватывает указатель на задачу из дека первого процессора. Т.к. используемая стратегия «work-stealing» - один элемент, то перехватывается только один указатель, а именно последний элемент дека первого процессора, т.е. его хвост. Этот элемент теперь принадлежит второму процессору. Он перезаписывается в новую ячейку памяти, которая расположена в середине свободного пространства памяти и становится первым элементом нового дека.

8. Первый и второй процессоры одновременно помещают указатели на свои задачи в свои деки.

9. Первый процессор начинает выполнять задачу. Он исключает элемент из головы своего дека. Головой дека становится оставшийся элемент.

10. Второй процессор добавляет указатель на задачу, которую он должен выполнить. Он помещается в начало дека и, соответственно, становится первым элементом дека или его головой.

11. Первый и второй процессоры одновременно помещают указатели на свои задачи в свои деки. Между головой второго дека и хвостом первого не остается свободных ячеек памяти.

12. Второй процессор добавляет указатель на задачу, но в его деке нет свободного места. Происходит переполнение дека второго процессора и указатель теряется. Работа системы прекращается.

Для дальнейшего анализа предлагаемого способа была построена имитационная модель работы двух work-stealing деков в общей памяти размером m единиц. Элементы дека имеют размер в одну единицу памяти. Вся работа системы была разбита на операции, выполняемые за одну единицу времени с заданными вероятностями выполнения: включение в первый дек р₁, включение во второй дек р₂, параллельное включение в оба дека р₁₂, исключение из первого дека q₁, исключение из второго дека q₂, параллельное исключение из двух деков q₁₂, включение в первый дек и параллельное исключение из второго pq₂₁, включение во второй дек и параллельное исключение из первого pq₂, отсутствие операций, изменяющих размер деков r. С помощью генератора псевдослучайных чисел определялось, какая операция произошла в тот или иной момент времени. Модель работает до тех пор, пока один из деков не переполнится. Данная модель проверялась на задаче комбинаторной оптимизации - о рюкзаке, и задаче перемножения матриц.

Исходными данными являются оценки вероятностей (по частоте) работы системы при решении задачи перемножения матриц и задачи о рюкзаке. Эти вероятности были получены в результате работы экспериментального планировщика work-stealing деков (Кучумов Р.И. Реализация и анализ work-stealing планировщика задач // Стохастическая оптимизация в информатике, Т. 12, №1, 2016 г). Анализируя представленные результаты, можно сделать вывод, что система, построенная на основе предлагаемого способа, работает дольше. Так, при стратегии перехвата одного элемента (табл. 1) для задачи перемножения матрицы, разница во времени работы системы составляет 324, то есть система работает, в среднем, на 324 операций дольше, если деки расположены в общей памяти друг за другом по кругу. А для задачи о рюкзаке - уже на 1736 операций дольше. Аналогичные результаты получены и для стратегии перехвата половины элементов (табл. 2).

Примеры и варианты заявляемого способа могут быть реализованы как электронными аппаратными средствами, так и программными средствами или их сочетанием. Конкретная реализация способа зависит от особенностей и ограничений той или иной компьютерной системы.

Таким образом, применение заявленного способа управления памятью компьютерной системы позволяет увеличить среднее время работы до переполнения. Еще одним преимуществом способа является его универсальность, т.е. изобретение не зависит от типа и размера памяти, вида и архитектуры процессоров, типа данных, которые записываются в work-stealing деки. На базе этого способа можно реализовать операционные системы, планировщики, менеджеры памяти и другие системные программы.