Билеты (Graur) (1114774), страница 17
Текст из файла (страница 17)
В той или иной системемогут допускаться как сообщения фиксированной длины, так и переменной. Впоследнем случае в заголовке сообщения, помимо отправителя и получателя,должна указываться длина сообщения. Выбор того или иного варианта зависит отцелей, которые преследует система обмена сообщениями, и от предполагаемойархитектуры ВС. Так, если предполагается возможность передачи большихобъемов данных, то сообщения с переменной длиной будут более гибкимрешением и позволят сократить накладные расходы на большое количествокоротких сообщений, где значительную часть занимает сам заголовок. С другойстороны, если обмен происходит между процессами на одной машине,немаловажную роль играет эффективность.
Здесь, возможно, было бы уместноограничить длину сообщения, с тем, чтобы использовать для их передачисистемные буфера с быстрым доступом.В заключение отметим еще раз, что механизм обмена сообщениями являетсямощным и гибким средством синхронизации, пригодным для использования как наоднопроцессорных системах и системах с общей памятью, так и в распределенныхВС. Однако, по сравнению с семафорами и мониторами, он, как правило, являетсяменее быстрым.БИЛЕТ 27Классические задачи синхронизации процессов.«Обедающие философы»Рассмотрим одну из классических задач, демонстрирующих проблему разделениядоступа к критическим ресурсам – «задачу об обедающих философах» [2]. Даннаязадача иллюстрирует ситуацию, когда процессы конкурируют за правоисключительного доступа к ограниченному числу ресурсов.
Пять философовсобираются за круглым столом, перед каждым из них стоит блюдо со спагетти, имежду каждыми двумя соседями лежит вилка. Каждый из философов некотороевремя размышляет, затем берет две вилки (одну в правую руку, другую в левую) иест спагетти, затем кладет вилки обратно на стол и опять размышляет и так далее.Каждый из них ведет себя независимо от других, однако вилок запасено ровностолько, сколько философов, хотя для еды каждому из них нужно две. Такимобразом, философы должны совместно использовать имеющиеся у них вилки(ресурсы).
Задача состоит в том, чтобы найти алгоритм, который позволитфилософам организовать доступ к вилкам таким образом, чтобы каждый имелвозможность насытиться, и никто не умер с голоду.Рассмотрим простейшее решение, использующее семафоры. Когда один изфилософов хочет есть, он берет вилку слева от себя, если она в наличии, а затем вилку справа от себя. Закончив есть, он возвращает обе вилки на свои места.Данный алгоритм может быть представлен следующим способом:#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() описывает поведение философа по захвату вилки: онждет, пока указанная вилка не освободится, и забирает ее.На первый взгляд, все просто, однако, данное решение может привести ктупиковой ситуации.
Что произойдет, если все философы захотят есть в одно и тоже время? Каждый из них получит доступ к своей левой вилке и будет находитьсяв состоянии ожидания второй вилки до бесконечности.Другим решением может быть алгоритм, который обеспечивает доступ квилкам только четырем из пяти философов. Тогда всегда среди четырех философовпо крайней мере один будет иметь доступ к двум вилкам.
Данное решение не имееттупиковой ситуации. Алгоритм решения может быть представлен следующимобразом:# define N 5# define LEFT (i-1)%N# define# define# define# define/* номер легого соседа для i-огофилософа */RIGHT (i+1)%N /* номер правого соседа для i-огофилософа*/THINKING 0/* философ думает */HUNGRY 1/* философ голоден */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]); /* блокируемся, если вилок нет */}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]);}}БИЛЕТ 28Задача «читателей и писателей»Другой классической задачей синхронизации доступа к ресурсам являетсязадача «читателей и писателей» [2], иллюстрирующая широко распространеннуюмодель совместного доступа к данным.
Представьте себе ситуацию, например, всистеме резервирования билетов, когда множество конкурирующих процессовхотят читать и обновлять одни и те же данные. Несколько процессов могут читатьданные одновременно, но когда один процесс начинает записывать данные(обновлять базу данных проданных билетов), ни один другой процесс не должениметь доступ к данным, даже для чтения. Возникает вопрос, как спланироватьработу такой системы? Одно из решений представлено ниже: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);/* отдать эксклюзивный доступ */}В этом примере, первый процесс, обратившийся к базе данных по чтению,осуществляет операцию down() над семафором db, тем самым блокируяэксклюзивный доступ к базе, который нужен для записи.
Число процессов,осуществляющих чтение в данный момент, определяется переменной rc (обратитевнимание! Так как переменная rc является разделяемым ресурсом – ее изменяютвсе процессы, обращающиеся к базе данных по чтению – то доступ к нейохраняется семафором mutex). Когда читающий процесс заканчивает свою работу,он уменьшает значение rc на единицу.
Если он является последним читателем, онтакже совершает операцию up над семафором db, тем самым разрешаязаблокированному писателю, если таковой имелся, получить эксклюзивный доступк базе для записи.Надо заметить, что приведенный алгоритм дает преимущество при доступе к базеданных процессам-читателям, так как процесс, ожидающий доступа по записи,будет ждать до тех пор, пока все читающие процессы не окончат работу, и если вэто время появляется новый читающий процесс, он тоже беспрепятственнополучит доступ. Это может привести к неприятной ситуации в том случае, если вфазе, когда ресурс доступен по чтению, и имеется ожидающий процесс-писатель,будут появляться новые и новые читающие процессы. К примеру, представим себе,что новый читающий процесс появляется каждую секунду и чтение длится всреднем 2 секунды.
Количество читающих процессов в этом случае будетприблизительно константным, и процесс-писатель никогда не получит доступ кданным.Чтобы этого избежать, можно модифицировать алгоритм таким образом, чтобы вслучае, если имеется хотя бы один ожидающий процесс-писатель, новые процессычитатели не получали доступа к ресурсу, а ожидали, когда процесс-писательобновит данные. В этой ситуации процесс-писатель должен будет ожидатьокончания работы с ресурсом только тех читателей, которые получили доступраньше, чем он его запросил. Однако, обратная сторона данного решения в том, чтооно несколько снижает производительность процессов-читателей, так каквынуждает их ждать в тот момент, когда ресурс не занят в эксклюзивном режиме.БИЛЕТ 29 Сигналы.
Примеры программирования.Сигналы.Сигналы представляют собой средство уведомления процесса о наступлениинекоторого события в системе. Инициатором посылки сигнала может выступатькак другой процесс, так и сама ОС. Сигналы, посылаемые ОС, уведомляют онаступлении некоторых строго предопределенных ситуаций (как, например,завершение порожденного процесса, прерывание процесса нажатием комбинацииCtrl-C, попытка выполнить недопустимую машинную инструкцию, попытканедопустимой записи в канал и т.п.), при этом каждой такой ситуации сопоставленсвой сигнал.
Кроме того, зарезервирован один или несколько номеров сигналов,семантика которых определяется пользовательскими процессами по своемуусмотрению (например, процессы могут посылать друг другу сигналы с цельюсинхронизации).Количество различных сигналов в современных версиях UNIX около 30, каждый изних имеет уникальное имя и номер. Описания представлены в файле <signal.h>.В таблице приведено несколько примеров сигналов:ЧисловоеКонстанта Значение сигналазначение2SIGINTПрерывание выполнения по нажатию Ctrl-C3SIGQUITАварийное завершение работы9SIGKILLУничтожение процесса14SIGALRM Прерывание от программного таймера18SIGCHLD Завершился процесс-потомокСигналы являются механизмом асинхронного взаимодействия, т.е. момент приходасигнала процессу заранее неизвестен. Однако процесс может предвидетьвозможность получения того или иного сигнала и установить определеннуюреакцию на его приход.
В этом плане сигналы можно рассматривать какпрограммный аналог аппаратных прерываний.При получении сигнала процессом возможны три варианта реакции на полученныйсигнал:- Процесс реагирует на сигнал стандартным образом, установленным поумолчанию (для большинства сигналов действие по умолчанию – этозавершение процесса).- Процесс может установить специальную обработку сигнала, в этомслучае по приходу сигнала вызывается функция-обработчик,определенная процессом (при этом говорят, что сигнал перехватывается)- Процесс может проигнорировать сигнал.Для каждого сигнала процесс может устанавливать свой вариант реакции,например, некоторые сигналы он может игнорировать, некоторые перехватывать, ана остальные установить реакцию по умолчанию.
При этом в процессе своейработы процесс может изменять вариант реакции на тот или иной сигнал. Однако,необходимо отметить, что некоторые сигналы невозможно ни перехватить, ниигнорировать. Они используются ядром ОС для управления работой процессов(например, SIGKILL, SIGSTOP).Если в процесс одновременно доставляется несколько различных сигналов, топорядок их обработки не определен. Если же обработки ждут несколькоэкземпляров одного и того же сигнала, то ответ на вопрос, сколько экземпляровбудет доставлено в процесс – все или один – зависит от конкретной реализации ОС.Отдельного рассмотрения заслуживает ситуация, когда сигнал приходит в моментвыполнения системного вызова. Обработка такой ситуации в разных версиях UNIXреализована по-разному, например, обработка сигнала может быть отложена дозавершения системного вызова; либо системный вызов автоматическиперезапускается после его прерывания сигналом; либо системный вызов вернет –1,а в переменной errno будет установлено значение EINTRДля отправки сигнала существует системный вызов kill():#include <sys/types.h>#INCLUDE <SIGNAL.H>INT KILL (PID_T PID, INT SIG)Первым параметром вызова служит идентификатор процесса, которому посылаетсясигнал (в частности, процесс может послать сигнал самому себе).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
