Однопроцессорное ядро

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

SO;

СО     PI:   S1;   //   ...   //   Pn:   Sn;   ос

Sn+1;

Pi — это имена процессов, si обозначают списки операторов и необязательные декларации локальных переменных процесса pi.

Для реализации приведенного фрагмента программы необходимы три механизма:

•    создания процессов и их запуска на выполнение;

•    остановки (и уничтожения) процесса;

•    определения момента завершения оператора со.

Примитив — это процедура, реализованная ядром так, что она выполняется как неделимое действие. Процессы создаются и уничтожаются с помощью двух примитивов ядра: fork и quit.

214                                               Часть 1. Программирование с разделяемыми переменными

Когда процесс запускает примитив fork, создается еще один процесс, готовый к запуску. Аргументы примитива fork передают адрес первой выполнимой инструкции нового процес­са и любые другие данные, необходимые для определения его начального состояния, напри­мер, параметры процесса. Новый процесс называется сыновним, а процесс, выполняющий примитив fork, —родительским. Вызывая примитив quit, процесс прекращает свое сущест­вование. У примитива quit аргументов нет.

Третий примитив ядра, join, используется для ожидания завершения процессов и, сле­довательно, для определения момента завершения оператора со. В частности, когда роди­тельский процесс выполняет примитив join, он ждет завершения сыновнего процесса, ко­торый до этого был порожден операцией fork. Аргументом операции join является имя сы­новнего процесса. (Примитив join используется и без аргументов— тогда процесс ждет завершения любого из сыновних процессов и, возможно, возвращает его идентификатор.)

Итак, для реализации указанного выше фрагмента можно использовать три описанных примитива fork, j oin и quit.
Каждый сыновний процесс Pi выполняет следующий код:

Si;   quit О;

Главный процесс выполняет такой код. SO; for   [i  =  1  to n]       #  создать  сыновние процессы

fork(Pi) ; for   [i  =  1  to n]       #  ожидать  завершения  каждого из них

join(Pi); Sn+1 ;

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

Во втором цикле for приведенная программа ждет выхода из сыновнего процесса 1, за­тем выхода из процесса 2 и т.д. При использовании примитива join без параметров ожидается завершение всех n сыновних процессов в произвольном порядке. Если сыновние процессы бы­ли объявлены с помощью декларации process и, следовательно, должны выполняться в фоно­вом режиме, то главный процесс создаст их таким же образом, но не будет ждать выхода из них.

Теперь представим однопроцессорное ядро, реализующее операции fork, join и quit. Также опишем, как планировать процессы, чтобы каждый процесс периодически получал возможность выполняться, т.е. представим диспетчер со стратегией планирования, справед­ливой в слабом смысле (см. определение в разделе 2.8).

Любое ядро содержит структуры данных, которые представляют процессы и три базовых типа процедур: обработчики прерываний, сами примитивы и диспетчер. Ядро может вклю­чать и другие структуры данных или функции — например, дескрипторы файлов и процедуры доступа к файлам. Сосредоточимся, однако, на той части ядра, которая реализует процессы.

Есть два основных способа организовать ядро:

•    в виде монолитного модуля, в котором каждый примитив ядра выполняется недели­мым образом;

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

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



В ядре каждый процесс представлен дескриптором процесса. Когда процесс простаивает, его дескриптор хранит состояние процесса, или контекст, — всю информацию, необходимую для выполнения процесса. Состояние (контекст) включает адрес следующей инструкции, ко­торую должен выполнять процесс, и содержимое регистров процессора.

Глава б Реализация                                                                                                                       215

Ядро начинает выполняться, когда происходит прерывание. Прерывания можно разде­лить на две широкие категории: внешние прерывания от периферийных устройств и внут­ренние прерывания, или ловушки, которые возбуждаются выполняемым процессом. Когда происходит прерывание, процессор автоматически сохраняет необходимую информацию о состоянии процесса, чтобы прерываемый процесс можно было продолжить. Затем процес­сор входит в обработчик прерывания; обычно каждый тип прерываний имеет свой обработчик.

Для запуска примитива ядра процесс вызывает внутреннее прерывание, выполняя ма­шинную инструкцию, которая называется вызовом супервизора (supervisor call — SVC) или ло­вушкой (trap). В инструкции SVC процесс передает аргумент, который задает вызываемый примитив; остальные аргументы передаются в регистрах. Обработчик прерывания SVC сна­чала сохраняет состояние выполняемого процесса, затем вызывает соответствующий прими­тив, реализованный в виде процедуры ядра. Примитив, завершаясь, вызывает процедуру dispatcher (процессорный диспетчер). Процедура dispatcher выбирает процесс для вы­полнения и загружает его состояние. Состояние процесса называется контекстом, поэтому последнее действие процедуры dispatcher носит название переключение контекста.

Чтобы обеспечить неделимое выполнение примитивов, обработчик прерывания в начале своей работы должен запретить дальнейшие прерывания, а диспетчер в конце — разрешить их. Когда возникает прерывание, все остальные прерывания автоматически запрещаются ап­паратной частью; в качестве побочного эффекта нагрузки состояния процесса ядро вновь разрешает прерывания. (В некоторых машинах прерывания разделены на несколько уровней, или классов.


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

На рис. 6.1 показаны компоненты ядра и поток управления внутри него. Поток идет в од­ном направлении, от обработчиков прерываний через примитивы к процедуре dispatcher и затем обратно к активному процессу. Следовательно, возвращений из вызовов внутри ядра не происходит, поскольку вместо возврата к тому процессу, который выполнялся при входе в ядро, оно часто начинает выполнение другого процесса.



Тип processType — это тип структуры (записи), описывающий поля в дескрипторе процес­са. Родительский процесс просит ядро создать сыновний процесс, вызывая примитив fork, который выделяет и инициализирует пустой дескриптор. Когда процедура ядра dispatcher планирует процессы, она ищет дескриптор процесса, имеющий право выполнения. Процедуры fork и dispatcher можно реализовать путем поиска в массиве дескрипторов процессов при условии, что каждая запись содержит поле, указывающее, занят ли данный элемент массива. Однако обычно используются два списка: список свободных (пустых дескрипторов) и список го­товых к работе (там содержатся дескрипторы процессов, ожидающих своей очереди на выпол­нение). Родительские процессы, ожидающие завершения работы сыновних процессов, запоми­наются в дополнительном списке ожидания. Наконец, ядро содержит переменную executing, значением которой является индекс дескриптора процесса, выполняемого в данный момент.

Предполагается, что при инициализации ядра, которая происходит при "загрузке" про­цессора, создается один процесс и переменная executing указывает на его дескриптор. Все остальные дескрипторы помещаются в список свободных. Таким образом, в начале выполне­ния списки готовых и ожидающих процессов пусты.

216                                               Часть 1 Программирование с разделяемыми переменными

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


Примитив join проверяет, произошел ли уже выход из сыновнего процесса, и, если нет, блокирует выполняющийся (родительский) процесс. Примитив quit запоминает, что про­изошел выход из процесса, помещает дескриптор выполняемого процесса в список свободных, запускает родительский процесс, если он ждет, и присваивает переменной executing значение нуль, чтобы указать процедуре dispatcher, что процесс больше не будет выполняться.

Процедура dispatcher, вызываемая в конце примитива, проверяет значение перемен­ной executing. Если это значение не равно нулю, то текущий процесс должен продолжить работу. Иначе процедура dispatcher удаляет первый дескриптор из списка готовых к вы­полнению и присваивает переменной executing значение, указывающее на этот процесс. Затем процедура dispatcher загружает состояние этого процесса. Здесь предполагается, что список готовых к выполнению процессов является очередью с обработкой типа "первым пришел — первым ушел" (FIFO).

Осталось обеспечить справедливость выполнения процесса. Если бы выполняемые про­цессы всегда завершались за конечное время, то описанная реализация ядра обеспечивала бы справедливость, поскольку список готовых к выполнению процессов имеет очередность FIFO. Но если есть процесс, ожидающий выполнения некоторого условия, которое в данный момент ложно, он заблокируется навсегда, если только его не заставить освободить процес­сор. (Процесс также зацикливается навсегда, если в результате ошибки программирования содержит бесконечный цикл.) Для того чтобы процесс периодически освобождал управление процессором, можно использовать интервальный таймер, если, конечно, он реализован ап-паратно. Тогда в сочетании с очередностью FIFO обработки списка готовых процессов каж­дый процесс периодически будет получать возможность выполнения, т.е. стратегия планиро­вания будет справедливой в слабом смысле.

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


Такой таймер используется в ядре следующим образом. Вначале, перед загрузкой состояния следующего выполняемого процесса, процедура dispatcher инициализирует таймер. Затем, когда возникает прерыва­ние таймера, обработчик этого прерывания помещает дескриптор процесса, на который ука­зывает переменная executing, в конец списка готовых к выполнению процессов, присваи­вает переменной executing значение 0 и вызывает процедуру dispatcher. В результате образуется круговая очередность выполнения процессов.

Собрав вместе все описанные выше части, получим схему однопроцессорного ядра (листинг 6.1). Предполагается, что побочный результат запуска интервального таймера в про­цедуре dispatcher состоит в запрете всех прерываний, которые могут возникнуть в резуль­тате достижения таймером нулевого значения во время выполнения ядра. При таком необхо­димом дополнительном условии выбранный для выполнения процесс не будет прерван не­медленно и не потеряет управления процессором

Листинг 6.1. Схема однопроцессорного ядр]

processType  processDescriptor[maxProcs];

int executing =0;         # индекс выполняемого процесса

объявления переменных для списков свободных, готовых к работе и ожидающих процессов;

SVC_Handler:   {         # вход с запрещенными прерываниями сохранить состояние выполняемого процесса (с индексом executing) ; определить, какой примитив был вызван, и запустить его;

}



В ядре (см. листинг 6.1) игнорируются такие возможные особые ситуации, как пустой список свободных дескрипторов при вызове примитива fork. В данной реализации также предполагается, что всегда есть хотя бы один готовый к работе процесс. На практике ядро всегда имеет один процесс-"бездельник", который запускается, когда другой работы нет; как это сделать, показано в следующем разделе Не учтено еще несколько моментов, возникаю­щих на практике, — например, обработка прерываний ввода-вывода, управление устройства­ми, доступ к файлам и управление памятью.

6.2.


Многопроцессорное ядро

Мультипроцессор с разделяемой памятью содержит несколько процессоров и память, доступную каждому из них. Расширить однопроцессорное ядро для работы на мультипроцес­сорных машинах относительно нетрудно. Вот наиболее важные изменения:

218                                               Часть 1. Программирование с разделяемыми переменными

•    процедуры и структуры данных ядра должны храниться в разделяемой памяти;

•    доступ к структурам данных должен осуществляться со взаимным исключением, когда необходимо избегать взаимного влияния;

•    процедуру dispatcher следует преобразовать для использования с несколькими про­цессорами.

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

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

Когда процессор прерывается, он входит в ядро и запрещает дальнейшие прерывания для данного процессора. Вследствие этого выполнение в ядре становится неделимым на данном процессоре, но остальные процессоры, тем не менее, могут одновременно выполняться в ядре.

Чтобы предотвратить взаимное влияние процессоров, можно сделать критической секци­ей все ядро, но это плохо по двум причинам. Во-первых, нет необходимости запрещать неко­торые безопасные параллельные операции, поскольку критичен только доступ к таким разде­ляемым ресурсам, как списки дескрипторов свободных и готовых к работе процессов. Во-вторых, если все ядро заключить в критическую секцию, она будет слишком длинной, что '• снижает производительность и увеличивает число конфликтов в памяти из-за переменных, реализующих протокол критической секции.


Следующий принцип позволяет получить на много более удачный вариант решения.

(6.1) Принцип блокировки мультипроцессора. Делайте критические секции короткими, за щищая каждую критическую структуру данных отдельно. Для каждой структуры дан ных используйте отдельные критические секции с отдельными переменными для про­токолов входа и выхода.

В нашем ядре критическими данными являются списки дескрипторов свободных, готовых к работ! и ожидающих процессов. Для защиты доступа к ним можно использовать любой из протоколе! критической секции, описанных выше в книге. Для конкретного мультипроцессора выбор дела­ется на основе доступных машинных инструкций. Например, если есть инструкция "извлеч! и сложить", можно использовать простой и справедливый алгоритм билета (см. листинг 3.9).

Предполагается, что ловушки обрабатываются тем же процессором, в котором они возни­кают, и каждый процессор имеет свой собственный интервальный таймер, поэтому обработ­чики прерываний от ловушек и от таймера остаются почти такими же, как и для однопроцес­сорного ядра. У них есть только два отличия: переменная executing теперь должна быть массивом с отдельным элементом для каждого из процессоров, а процедура Timer_Handler должна блокировать и освобождать список готовых к выполнению процессов.

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

Наибольшие изменения касаются процедуры dispatcher. До этого в нашем распоряже­нии был один процессор, и предполагалось, что всегда есть процесс для выполнения на нем, Теперь процессов может быть меньше, чем процессоров, поэтому некоторые процессоры могут простаивать. Когда создается новый процесс (или запускается после прерывания ввода-вывода), он должен быть привязан к незанятому процессору, если такой есть. Это можно сде­лать одним из трех способов:



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

Глава б. Реализация                                                                                                                 219

•    заставить процессор, выполняющий fork, искать свободный процессор и назначать ему новый процесс;

•    использовать отдельный процесс-диспетчер, который выполняется на отдельном про­цессоре и постоянно пытается назначать свободным процессорам готовые к работе процессы.

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

Когда диспетчер определяет, что список готовых к работе процессов пуст, он присваивает переменной executing [ i ] значение, указывающее на дескриптор бездействующего процесса, и загружает его состояние. Код бездействующего процесса показан в листинге 6.2. По существу, процесс idle — "сам себе диспетчер". Сначала, пока в списке готовых к работе процессов нет элементов, он зацикливается, затем удаляет из списка дескриптор процесса и начинает выпол­нение этого процесса. Чтобы не было конфликтов в памяти, процесс Idle не должен непре­рывно просматривать или блокировать и разблокировать список готовых к работе процессов, поэтому используем протокол "проверить-проверить-установить", аналогичный по структуре приведенному в листинге ЗА. Поскольку список готовых к работе процессов может стать пус­тым после того, как процесс idle захватит его блокировку, необходима повторная проверка.

Листинг 6.2. Код бездействующего процесса

process  Idle   {

while   (executing [i]   == бездействующий процесс)   { while   (список готовых пуст)   Задержка; заблокировать список готовых; i f   (список готовых не пуст)   { удалить дескриптор из начала списка готовых; установить executingti]   нанего; }

снять блокировку со списка готовых; }



запустить интервальный таймер на процессоре  i;

загрузить состояние executing [i] ;   #  с разрешенными прерываниями }___________________________________________________________________________

Осталось обеспечить справедливость планирования. Вновь используем таймеры, чтобы заставить процессы, выполняемые вне ядра, освобождать процессоры. Предполагаем, что каждый процессор имеет свой таймер, который используется так же, как и в однопроцессор­ном ядре. Но одних таймеров недостаточно, поскольку теперь процессы могут быть приоста­новлены в ядре в ожидании доступа к разделяемым структурам данных ядра. Таким образом, нужно использовать справедливое решение для задачи критической секции, например, алго­ритм разрыва узлов, алгоритм билета или алгоритм поликлиники (глава 3). Если вместо этого использовать протокол "проверить-установить", появится возможность "зависания" процессов. Однако это маловероятно, поскольку критические секции в ядре являются очень короткими.

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

Листинг 6.3. Схема*ядра"для мультипроцессора с разделяемой памятью

processType processDescriptor[maxProcs];

int executing[maxProcs];  # по одному элементу для процессора





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


Таким образом, список готовых к работе процес­сов может стать " узким местом" программы. Если число уровней приоритетов фиксировано, то эффективное решение — использовать по одной очереди на каждый уровень приоритета и по одной блокировке на каждую очередь. При таком представлении вставка процесса в спи­сок готовых к работе требует только вставки в конец соответствующей очереди. Но если чис­ло уровней приоритета изменяется динамически, то чаще всего используют единый список готовых к работе процессов.

В ядре (см. листинг 6.3) также предполагается, что процесс может выполняться на любом процессоре, поэтому диспетчер всегда выбирает первый готовый к выполнению процесс. В некоторых мультипроцессорах такие процессы, как драйверы устройств или файловые сер­веры, могут работать только на специальном процессоре, к которому присоединены перифе­рийные устройства. В этой ситуации для такого процессора создается отдельный список гото­вых к работе процессов и, возможно, собственный диспетчер. (Ситуация значительно услож­няется, если на специализированном процессоре могут выполняться и обычные процессы, поскольку их тоже нужно планировать.)

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

Независимо от того, однородно или нет время доступа к памяти, процессоры обычно имеют кэш-память и буферы трансляции адресов виртуальной памяти. В этой ситуации про­цесс должен планироваться на тот процессор, на котором он выполнялся последний раз (предполагается, что часть состояния процесса находится в кэш-памяти и буферах трансля­ции процессора). Кроме того, если два процесса разделяют данные, находящиеся в кэш­памяти, гораздо эффективнее выполнять эти процессы по очереди на одном процессоре, чем на разных. Это называется совместным планированием. Здесь также предполагается наличие отдельного списка готовых к работе процессов у каждого процессора, что в свою очередь при­водит к необходимости балансировки нагрузки. Дополнительная информация по этим во­просам дана в ссылках и упражнениях в конце главы.

222                                               Часть 1 Программирование с разделяемыми переменными


Содержание раздела

---

---