Н.В. Вдовикина, А.В. Казунин, И.В. Машечкин, А.Н. Техехин - Системное программное обеспечение - взаимодействие процессов, страница 6

Что произойдет, если все философызахотят есть в одно и то же время? Каждый из них получит доступ ксвоей левой вилке и будет находиться в состоянии ожидания второйвилки до бесконечности.Другим решением может быть алгоритм, который обеспечиваетдоступ к вилкам только четырем из пяти философов. Тогда всегдасреди четырех философов по крайней мере один будет иметь доступк двум вилкам.

Данное решение не имеет тупиковой ситуации.Алгоритм решения может быть представлен следующим образом:26# define N 5/* количество философов */# define LEFT (i-1)%N/* номер легого соседа для i-огофилософа */# define RIGHT (i+1)%N/* номер правого соседа для iого философа*/# define THINKING 0/* философ думает */# define HUNGRY 1/* философ голоден */# define EATING 2/* философ ест */typedef int semaphore;/* тип данных «семафор» */int state[N];/* массив состояний философов */semaphore mutex=1;/* семафор для критической секции */semaphore s[N];/* по одному семафору на философа */void philosopher (int i)/* i : номер философа от 0 до N-1 */{while (TRUE)/* бесконечный цикл */{think();/* философ думает */take_forks(i);/*философ берет обеили блокируется */eat();/* философ ест */put_forks(i);/* философвилки */вилкиосвобожаетобе}}void take_forks(int i)/* i : номер философа от 0 до N-1 */{down(&mutex);/* вход в критическую секцию */state[i] = HUNGRY;/*записываем, что i-ыйголоден */философtest(i);/* попытка взять обе вилки */up(&mutex);/* выход из критической секции */down(&s[i]);/* блокируемся, если вилок нет */27}void put_forks(i)/* i : номер философа от 0 до N-1 */{down(&mutex);/* вход в критическую секцию */state[i] = THINKING;/* философ закончил есть */test(LEFT);/* проверить может ли левый сосед сейчас есть */test(RIGHT);/* проверить может ли правый сосед сейчас есть*/up(&mutex);/* выход из критической секции */}void test(i)/* i : номер философа от 0 до N-1 */{if (state[i] == HUNGRY && state[LEFT] != EATING &&state[RIGHT] != EATING){state[i] = EATING;up (&s[i]);}}3.2.2 Задача «читателей и писателей»Другой классической задачей синхронизации доступа кресурсам является задача «читателей и писателей» [2],иллюстрирующая широко распространенную модель совместногодоступа к данным.

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

Возникает вопрос, какспланировать работу такой системы? Одно из решений представленониже:28typedef int semaphore;/* тип данных «семафор» */semaphore mutex = 1;/* контроль за доступом к «rc»(разделямый ресурс) */semaphore db = 1;/* контроль за доступом к базеданных */int rc = 0;/* кол-во процессов читающих илипишущих */void reader (void){while (TRUE)/* бесконечный цикл */{down(&mutex);/*получитьэксклюзивныйдоступ к «rc»*/rc = rc + 1;больше *//*if (rc == 1) down(&db);ещеоднимчитателем/*еслиэтопервыйчитатель,нужнозаблокироватьэксклюзивный доступ кбазе */up(&mutex);/*освободить ресурс rc */read_data_base();/* доступ к данным */down(&mutex);/*получитьэксклюзивныйдоступ к «rc»*/rc = rc - 1:/* теперьменьше */if (rc == 0) up(&db);однимчитателем/*еслиэтобылпоследнийчитатель,разблокироватьэксклюзивный доступ кбазе данных */up(&mutex);/*освободитьресурс rc */use_data_read();/* некритическая секция */}}void writer (void){29разделяемыйwhile(TRUE)/* бесконечный цикл */{think_up_data();/* некритическая секция */down(&db);/*получитьэксклюзивныйдоступ к данным*/write_data_base();/* записать данные */up(&db);/*отдатьдоступ */эксклюзивный}}В этом примере, первый процесс, обратившийся к базе данныхпо чтению, осуществляет операцию down() над семафором db, темсамым блокируя эксклюзивный доступ к базе, который нужен длязаписи.

Число процессов, осуществляющих чтение в данныймомент, определяется переменной rc (обратите внимание! Так какпеременная rc является разделяемым ресурсом – ее изменяют всепроцессы, обращающиеся к базе данных по чтению – то доступ кней охраняется семафором mutex). Когда читающий процессзаканчивает свою работу, он уменьшает значение rc на единицу.Если он является последним читателем, он также совершаетоперацию up над семафором db, тем самым разрешаязаблокированному писателю, если таковой имелся, получитьэксклюзивный доступ к базе для записи.Надо заметить, что приведенный алгоритм дает преимуществопри доступе к базе данных процессам-читателям, так как процесс,ожидающий доступа по записи, будет ждать до тех пор, пока всечитающие процессы не окончат работу, и если в это времяпоявляется новый читающий процесс, он тоже беспрепятственнополучит доступ.

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

Однако,обратная сторона данного решения в том, что оно несколькоснижает производительность процессов-читателей, так каквынуждает их ждать в тот момент, когда ресурс не занят вэксклюзивном режиме.3.2.3 Задача о «спящем парикмахере»Еще одна классическая задача на синхронизацию процессов –это так называемая «задача о спящем парикмахере» [2]. Рассмотримпарикмахерскую, в которой работает один парикмахер, имеется однокресло для стрижки и несколько кресел в приемной для посетителей,ожидающих своей очереди. Если в парикмахерской нет посетителей,парикмахер засыпает прямо на своем рабочем месте. Появившийсяпосетитель должен его разбудить, в результате чего парикмахерприступает к работе.

Если в процессе стрижки появляются новыепосетители, они должны либо подождать своей очереди, либопокинуть парикмахерскую, если в приемной нет свободного кресладля ожидания. Задача состоит в том, чтобы корректнозапрограммировать поведение парикмахера и посетителей.Одно из возможных решений этой задачи представлено ниже.Процедура barber() описывает поведение парикмахера (онавключает в себя бесконечный цикл – ожидание клиентов и стрижку).Процедура customer() описывает поведение посетителя. Несмотряна кажущуюся простоту задачи, понадобится целых 3 семафора:customers – подсчитывает количество посетителей, ожидающих вочереди, barbers – обозначает количество свободных парикмахеров(в случае одного парикмахера его значения либо 0, либо 1) и mutex –используется для синхронизации доступа к разделяемой переменнойwaiting.

Переменная waiting, как и семафор customers, содержитколичество посетителей, ожидающих в очереди, она используется впрограмме для того, чтобы иметь возможность проверить, имеетсяли свободное кресло для ожидания, и при этом не заблокироватьпроцесс, если кресла не окажется. Заметим, что как и в предыдущемпримере, эта переменная является разделяемым ресурсом, и доступ кней охраняется семафором mutex. Это необходимо, так как дляобычной переменной, в отличие от семафора, чтение и последующееизменение не являются неделимой операцией.#define CHAIRS 5typedef int semaphore;/* тип данных «семафор» */31semaphore customers = 0;/*посетители,ожидающие в очереди */semaphore barbers = 0;/*парикмахеры,ожидающие посетителей */semaphore mutex = 1;/* контроль за доступомпеременной waiting */кint waiting = 0;void barber(){while (true) {down(customers);/* если customers == 0,т.е.посетителейнет,тозаблокируемся до появления посетителя*/down(mutex);/*получаемwaiting */доступwaiting = wating – 1;/*уменьшаеможидающих клиентов */up(barbers);/*парикмахерработе */up(mutex);/*освобождаемwaiting */cut_hair();ккол-воготовкресурс/* процесс стрижки */}void customer(){down(mutex);/* получаем доступ к waiting */if (waiting < CHAIRS)/*естьместоожидания */для{waiting = waiting + 1; /* увеличиваем колво ожидающих клиентов */up(customers);up(mutex);/*еслипарикмахерспит, это его разбудит *//* освобождаемwaiting */ресурсdown(barbers); /* если парикмахер занят,переходимвсостояниеожидания, иначе – занимаемпарикмахера*/get_haircut();32/* процесс стрижки */}else{up(mutex);/* нет свободного кресладляожидания–придетсяуйти */}}33ЧАСТЬ II.

РЕАЛИЗАЦИЯ ПРОЦЕССОВ.В этой части пособия мы подробно рассмотрим практическоеприменение понятия процесса в ОС, а также реализацию механизмауправления процессами на примере ОС UNIX.4 Реализация процессов в ОС UNIX4.1 Понятие процесса в UNIX.Выше уже говорилось, что в каждой конкретной ОСсуществует свое системно-ориентированное определение понятияпроцесса. В ОС UNIX процесс можно определить, с одной стороны,как единицу управления и потребления ресурсов, с другой стороны –как объект, зарегистрированный в таблице процессов ядра UNIX.Каждому процессу в UNIX сопоставлено некое уникальное целоечисло, называемое идентификатором процесса – PID.

Это числонаходится в диапазоне от нуля до некоторого предельного номера,характеризующегомаксимальновозможноеколичествоодновременно существующих процессов в данной ОС. Некоторыезначения идентификаторов являются зарезервированными иназначаются специальным процессам ОС, например, процесс сPID=0 ассоциируется с работой ядра ОС, а процесс с PID=1 – этопроцесс init, работа которого будет подробно рассмотрена ниже.4.1.1 Контекст процесса.С точки зрения организации данных ядра ОС, идентификаторпроцесса фактически представляет собой номер записи в таблицепроцессов, соответствующей данному процессу. Содержимое записитаблицы процессов позволяет получить доступ к контекступроцесса (а именно, часть информации, составляющей контекстпроцесса, хранится непосредственно в таблице процессов, а наструктуры данных, содержащие оставшуюся часть контекста, взаписи таблицы процессов имеются прямые или косвенные ссылки).Таблица процессов поддерживается ядром UNIX и находится вадресном пространстве ядра.С точки зрения логической структуры контекст процесса вUNIX состоит из:- пользовательской составляющей или тела процесса(иногда используется термин «пользовательскийконтекст»)- аппаратной составляющей (иногда используетсятермин «аппаратный контекст»)34- системной составляющей ОС UNIX (иногданазываемой«системным контекстом» или«контекстом системного уровня»)Иногда при рассмотрении контекста процесса два последнихкомпонента объединяют, в этом случае используется терминобщесистемная составляющая контекста.Рассмотрим подробнее каждую из составляющих контекстапроцесса.таблица процессовконтекст процессаPIDсистемныйконтекстаппаратныйконтексттелопроцессасегменткодасегментданныхСтатическиеданныеадресноепр-воядраадресноепр-вопроцессаРазделяемаяпамятьСтекРис.