Реализация взаимодействия процессов

Классические задачи синхронизации процессов

«Обедающие философы»

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

Рассмотрим простейшее решение, использующее семафоры. Когда один из философов хочет есть, он берет вилку слева от себя, если она в наличии, а затем - вилку справа от себя. Закончив есть, он возвращает обе вилки на свои места. Данный алгоритм может быть представлен следующим способом:

#define N 5 /* число философов*/

void philosopher (int i) /* i – номер философа от 0 до 4*/

{

while (TRUE)

{

think(); /*философ думает*/

take_fork(i); /*берет левую вилку*/

take_fork((i+1)%N); /*берет правую вилку*/

eat(); /*ест*/

put_fork(i); /*кладет обратно левую вилку*/

put_fork((i+1)%N); /* кладет обратно правую вилку */

}

}

Функция take_fork() описывает поведение философа по захвату вилки: он ждет, пока указанная вилка не освободится, и забирает ее.

На первый взгляд, все просто, однако, данное решение может привести к тупиковой ситуации. Что произойдет, если все философы захотят есть в одно и то же время? Каждый из них получит доступ к своей левой вилке и будет находиться в состоянии ожидания второй вилки до бесконечности. Другим решением может быть алгоритм, который обеспечивает доступ к вилкам только четырем из пяти философов. Тогда всегда среди четырех философов по крайней мере один будет иметь доступ к двум вилкам. Данное решение не имеет тупиковой ситуации. Здесь определяется количество философов, далее идут макросы для определения номеров левой, правой вилки и три состояния философов: философ думает, философ голоден и философ ест. Определяется тип данных semaphore и массив состояний каждого из философов – массив state. Далее определяется один семафор для реализации критической секции и по одному семафору на каждого философа – это массив семафоров s. Вот, обратите внимание, они выделены цветом, и далее операции с этими семафорами тоже будут выделены цветом. Основная функция – это философы. Философ думает затем, когда он проголодается, он вызывает функцию take_forks(), затем происходит еда, и вызывается функция put_forks(). В функции take_forks() в первую очередь идет вход в критическую секцию одного конкретного философа. Критическая секция охраняется семафором mutex. В момент входа в критическую секцию семафор mutex охраняет массив состояний философа. Идет изменение состояния на голоден, и вызывается функция test(). Затем производится выход из критической секции: поднятие семафора mutex и опускание семафора конкретного философа. В функции test() происходит проверка: что делает левый сосед, и что делает правый сосед. Если состояние голоден и левый сосед не ест и правый сосед не ест, т.е. вилки свободны, то состояние философа меняется на состояние поедания и поднимается семафор этого философа. Итак опускание семафора происходит в take_forks(), а поднятие в test(). Т.е. если семафор не был поднят в test() (не выполнилось условие, что оба соседа не едят), то в момент down() на семафоре в функции take_forks() философ будет заблокирован и будет ожидать, пока один из соседей не освободит его состояние, что происходит в функции put_forks(). Здесь тоже самое: опускается семафор для хранения критической секции, которая охраняет массив состояний. Состояние изменяется на «думающий» и производится тест на левого и правого соседа. В этот момент, когда посылается тест для обоих соседей, если один из этих соседей был ранее заблокирован из-за того, что его вилка была занята нашим философом, то в этот момент он разблокируется и сможет взять вилку. Обращаю ваше внимание на то, что семафор mutex необходим для охраны массива состояний философов. Т.е. здесь массив состояний философов является разделяемым ресурсом, потому что эти состояния проверяются как самим философом так и его левым и правым соседом (функция test()). Поэтому необходимо охранять их, потому что если доступ к ним будет осуществляться со стороны двух или более процессов одновременно, то один из процессов может проверить это состояние, в то время как другой процесс будет его изменять. Чтобы такого не происходило необходимо сделать этот ресурс критическим и охранять его семафором, что и делает семафор mutex. Массив семафоров s используется для того, чтобы блокировать философов, которые не могут в данный момент взять вилку и разблокирование философов происходит в тот момент, когда сосед вилки освобождает. Т.е. это решение уже более сложное, однако, оно позволяет избежать тупиковых ситуаций, но не гарантирует отсутствие дискриминации, т.е. здесь возможно ситуация, что поскольку в момент когда разблокируется один из соседей всегда возможна ситуация, что вилку захватит другой сосед, соответственно второй сосед может остаться без вилок.

Алгоритм решения может быть представлен следующим образом:

# 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]={0,0,0,0,0}; /* массив состояний философов */

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]); /* блокируемся, если вилок нет */

}

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]);}

}

Задача «читателей и писателей»

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

typedef 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)

{

while(TRUE) /* бесконечный цикл */

{

think_up_data(); /* некритическая секция */

down(db); /* получить эксклюзивный доступ к данным*/

write_data_base(); /* записать данные */

up(db); /* отдать эксклюзивный доступ */

}

}

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

Задача о «спящем парикмахере»

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

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

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

#define CHAIRS 5

typedef int semaphore; /* тип данных «семафор» */

semaphore 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(); /* процесс стрижки */

}

else

{

up(mutex); /* нет свободного кресла для ожидания – придется уйти */

}

}

Проблемы, связанные с организацией взаимодействия процессов:

Первая – именование процессов отправителей и получателей или именование некоторого объекта, через который осуществляется взаимодействие. Эта проблема решается по-разному в зависимости от конкретного механизма взаимодействия.

Так в системах, обеспечивающих взаимодействие процессов, функционирующих на различных компьютерах в сети используется адресация, принятая в конкретной сети ЭВМ (например, аппарат сокетов, MPI).

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

При взаимодействии родственных процессов проблема именования решается за счет наследования потомками некоторых свойств одного из прародителей. Например, в случае неименованных каналов процесс-родитель для организации взаимодействия создает канал. Этот канал наследуется сыновними процессами, тем самым создается возможность организации симметричного (ибо все процессы изначально равноправны) взаимодействия родственных процессов. Другой пример, это взаимодействие процессов по схеме главный-подчиненный (или трассировка). Данный тип взаимодействия ассиметричный, так как изначально один из взаимодействующих процессов получает статус и права «главного», второй - «подчиненного». Главный – это родительский процесс, подчиненный – сыновний. Соответственно именование жестко привязано к связке отец-сын (идентификаторы сына и отца всегда доступны и однозначно определены).

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

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

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

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

Комплексное решение проблемы синхронизации зависит от свойств используемых средств взаимодействия процессов. В некоторых случаях операционная система обеспечивает некоторые уровни синхронизации (например передача сигналов, использование каналов). В некоторых участие операционной системы в синхронизации минимально (например, разделяемая память IPC).

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