Однопроцессорное ядро
В предыдущих главах для определения параллельной работы использовались операторы со и декларации 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 Программирование с разделяемыми переменными