Файл: А. В. Гордеев А. Ю. Молчанов системное программное обеспечение электронный вариант книги издательства Питер СанктПетербург Челябинск юургу каф. Автоматика и управление 2002 2 Предисловие Настоящий учебник.pdf

341
осуществляется переход к строке 3. В строке 3 осуществляется запись в конвейер.
Строка 4 – создание семафора ожидания. Этот семафор используется для ожидания открытия семафоров в программах-потомках. Ожидание открытия семафоров про- исходит в строке 8, затем семафор закрывается. В строках 5–7 осуществляется за- пуск программ D, Е, F.
Теперь приведём алгоритм прохождения точки 3. Фрагмент исходного текста программы изображен ниже.
1: rc=DosPostEventSem(Point2Sem);
2: if (гс==0)
3: { do{ DosQueryEventSem(Point2Sem, &BytesWritten);
4: }while (BytesWritten<=2);
5: DosWrite(WriteHandle, (PVOID)&NewInform, sizeof(NewInform),
&BytesWritten);
6: DosCreateEventSem("\\SEM32\\EXITSEM3", &ExitSem3,
DC_SEM_SHARED, 0);
7: DosExecPgm(FailFileb, sizeof(FailFileb), Argument, 0, &ResCodeb,
"progr_g.exe");
8: DosExecPgm(FailFileb, sizeof(FailFileb), Argument, 0, &ResCodeb,
"progr_h.exe");
9: DosWaitEventSem(ExitSem3, -1);
В точке 3 программы G и Н запускаются той программой, которая первой за- вершает свою работу, но только после того, как работу завершат остальные про- граммы. Для определения последовательности завершения работы программ (I, D
или Е) используется семафор Point2Sem. В строке 1 производится установка дан- ного семафора. Если значение rc не равно нулю, значит, семафор уже установлен,
то есть текущая программа не первой завершила свою работу. Если rc равно нулю,
то текущая программа закончила работу первой и осуществляется переход к строке
3. В этой строке подсчитывается количество обращений к данному семафору. Цикл повторяется до тех пор, пока количество обращений не станет равно 3, то есть ко- гда все остальные программы завершили свою работу. После этого в строке 5 осу-

342
ществляется запись в конвейер. Строка 6 – создание семафора ожидания. Этот се- мафор используется для ожидания открытия семафоров в программах-потомках.
Ожидание открытия семафоров происходит в строке 9. В строках 7 и 8 осуществ- ляется запуск программ G и Н соответственно.
Наконец, приведём ещё алгоритм прохождения точки 4. Фрагмент исходного текста программы, реализующей эту задачу, приведён ниже.
1: do { DosWaitEventSem(Point1Sem, -1);
2: rc=DosResetEventSem(Point1Sem, &BytesReaden);
3: } while (rc!=0);
4: DosPostEventSem(Point3Sem);
5: DosQueryEventSem(Point3Sem, &BytesWritten);
6: DosPostEventSem(Point1Sem);
7: if (BytesWritten==4)
8: { DosWrite(WriteHandle, (PVOID)&NewInform, sizeof(NewInform),
&BytesWritten);
9: DosCreateEventSem("\\SEM32\\EXITSEM4", &ExTtSem4,
DC_SEM_SHARED, 0);
10: DosExecPgm(FailFileb, sizeof(FailFileb), 1, Argument, 0, &ResCodeb,
"progr_k.exe"):
11: DosWaitEventSem(ExitSem4, -1);
Итак, в точке 4 программа К запускается задачей, которая последней заверши- ла свою работу. Для определения последовательности завершения работы про- грамм (J, G, Н или F) используется семафор Point3Sem. Каждая программа должна обратиться к данному семафору, установить его и проверить количество обраще- ний к нему. Но при выполнении этих двух операций другие программы могут так- же установить семафор, и значение обращений к семафору в текущей программе окажется неверным. Для доступа к семафору Point3Sem используется семафор
Point1Sem. В строке 1 программа ожидает установки семафора Point1Sem, кото- рый сигнализирует о доступности неразделяемого ресурса Point3Sem. В строке 2
семафор сбрасывается, но если другие программы успели сбросить семафор, то об

343
этом сообщит значение rc. Если текущей программе удалось завладеть ресурсом,
то есть значение rc равно нулю, то дальше в строках 4, 5 производится установка семафора Point3Sem и подсчёт количества обращений. Строка 6 сигнализирует о завершении работы критической части программы установкой семафора
Point1Sem. Затем, как и в предыдущих алгоритмах, программа записывает инфор- мацию в транспортёр (строка 8), создает семафор ожидания открытия семафоров в программах-потомках (строка 9), запускает программу К (строка 10) и ожидает от- крытия семафоров в программе К (строка 11).
Тексты четырех программ (А, В, D и G), действующих по рассмотренным ал- горитмам, приведены в приложении Б. Остальные программы аналогичны им и от- личаются только использованием других имён.

344 11 Что представляют собой «конвейеры» (программные каналы)?
12 Что представляют собой «очереди сообщений»? Чем отличаются очереди сообщений от почтовых ящиков?
ГЛАВА 7 Проблема тупиков и методы борьбы с ними
Рассмотрим одну из самых серьезных и трудно разрешимых проблем, возни- кающих при организации мультипрограммирования – проблему тупиков и основ- ные подходы при борьбе с ними. В настоящей главе приводятся некоторые модели параллельных вычислительных процессов, позволяющие проводить анализ по- следних в аспекте корректного решения указанных проблем.
Понятие тупиковой ситуации при
выполнении параллельных вычислительных
процессов
При организации параллельного выполнения нескольких процессов одной из главных функций операционной системы является решение сложной задачи кор- ректного распределения ресурсов между выполняющимися процессами и обес- печение последних средствами взаимной синхронизации и обмена данными.
При параллельном исполнении процессов могут возникать ситуации, при ко- торых два или более процесса всё время находятся в заблокированном состоянии.
Самым простым является случай, когда каждый из двух процессов ожидает ресурс,
занятый другим процессом. Из-за такого ожидания ни один из процессов не может продолжить исполнение и освободить в конечном итоге ресурс, необходимый дру- гому процессу. Эта тупиковая ситуация называется дедлоком
1
, тупиком или клин- чем. Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ждёт события, которое никогда не произойдёт. Тупики чаще всего возникают из-за конкуренции несвязанных параллельных процессов за ресурсы вычислительной системы, но иногда к тупикам приводят и ошибки программиро- вания.

345
При рассмотрении проблемы тупиков целесообразно понятие ресурсов систе- мы обобщить и разделить их все на два класса – повторно используемые (или сис- темные) ресурсы (типа RR или SR – reusable resource или system resource) и по- требляемые (или расходуемые) ресурсы (типа CR – consumable resource).
Повторно используемый ресурс (SR) есть конечное множество идентичных единиц со следующими свойствами [92]:
♦ число единиц ресурса постоянно;
♦ каждая единица ресурса или доступна, или распределена одному и только одному процессу (разделение либо отсутствует, либо не принимается во внимание,
так как не оказывает влияния на распределение ресурсов, а значит, и на возникно- вение тупиковой ситуации);
♦ процесс может освободить единицу ресурса (сделать её доступной), только если он ранее получил эту единицу, то есть никакой процесс не может оказывать какое-либо влияние ни на один ресурс, если он ему не принадлежит.
Данное определение выделяет существенные для изучения проблемы тупика свойства обычных системных ресурсов, к которым мы относим такие компоненты аппаратуры, как основная память, вспомогательная (внешняя) память, периферий- ные устройства и, возможно, процессоры, а также программное и информационное обеспечение, такое как файлы данных, таблицы и «разрешение войти в критиче- скую секцию».
Расходуемый ресурс (CR) отличается от ресурса типа SR в нескольких важных отношениях [37]:
♦ число доступных единиц некоторого ресурса типа CR изменяется по мере того, как приобретаются (расходуются) и освобождаются (производятся) от- дельные их элементы выполняющимися процессами, и такое число единиц ресурса является потенциально неограниченным; процесс «производитель» увеличивает число единиц ресурса, освобождая одну или более единиц, которые он «создал»;
♦ процесс «потребитель» уменьшает число единиц ресурса, сначала запраши- вая и затем приобретая (потребляя) одну или более единиц. Единицы ресурса, ко-
1
Dead lock – смертельное объятие

346
торые приобретены, в общем случае не возвращаются ресурсу, а потребляются
(расходуются). Эти свойства потребляемых ресурсов присущи многим синхрони- зирующим сигналам, сообщениям и данным, порождаемым как аппаратурой, так и программным обеспечением, и могут рассматриваться как ресурсы типа CR при изучении тупиков. В их число входят: прерывания от таймера и устройств вво- да/вывода; сигналы синхронизации процессов; сообщения, содержащие запросы на различные виды обслуживания или данные, а также соответствующие ответы.
Для исследования параллельных процессов и, в частности, проблемы тупиков было разработано несколько моделей. Одной из них является модель повторно ис- пользуемых ресурсов Холта [92]. Согласно этой модели система представляется как набор (множество) процессов и набор ресурсов, причём каждый из ресурсов состоит из фиксированного числа единиц. Любой процесс может изменять состоя- ние системы с помощью запроса, получения или освобождения единицы ресурса.
В графической форме процессы и ресурсы представляются квадратами и кружками соответственно. Каждый кружок содержит некоторое количество марке- ров (фишек) в соответствии с существующим количеством единиц этого ресурса.
Дуга, указывающая из «процесса» на «ресурс», означает запрос одной единицы этого ресурса. Дуга, указывающая из «ресурса» на «процесс», представляет выде- ление ресурса процессу. Поскольку каждая единица любого ресурса типа SR может быть выделена одновременно не более чем одному процессу, то число дуг, исхо- дящих из ресурса к различным процессам, не может превышать общего числа еди- ниц этого ресурса. Такая модель называется графом повторно используемых ресур-
сов.
Одно из состояний примера системы из двух процессов с ресурсами типа SR
представлено на рис. 7.1.
Пусть процесс Р1 запрашивает две единицы ресурса R1 и одну единицу ресур- са R2. Процессу Р2 принадлежат две единицы ресурса R1 и ему нужна одна едини- ца R2. Предположим, что процесс Р1 получил бы теперь запрошенную им единицу
R2. Если принято правило, по которому процесс должен получить все запрошен- ные им ресурсы, прежде чем освободить хотя бы один из них, то удовлетворение

347
запроса Р1 приведет к тупиковой ситуации: Р1 не сможет продолжиться до тех пор,
пока Р2 не освободит единицу ресурса R1, а процесс Р2 не сможет продолжиться до тех пор, пока Р1 не освободит единицу R2. Причиной этого дедлока являются неупорядоченные попытки процессов войти в критический интервал, связанный с выделением соответствующей единицы ресурса.
Рис. 7.1. Пример модели Холта для системы из двух процессов
Примеры тупиковых ситуаций и причины их
возникновения
Для понимания основных причин возникновения тупиков рассмотрим не- сколько простых характерных примеров.
Пример тупика на ресурсах типа CR
Пусть имеются три процесса ПР1, ПР2 и ПРЗ, которые вырабатывают соответ- ственно сообщения Ml, M2 и МЗ. Эти сообщения представляют собой ресурсы ти- па CR. Пусть процесс ПР1 является «потребителем» сообщения МЗ, процесс ПР2
получает сообщение Ml, а ПРЗ – сообщение М2 от процесса ПР2, то есть каждый из процессов является и «поставщиком» и «потребителем» одновременно, и вместе они образуют «кольцевую» систему (рис. 7.2) передачи сообщений через почтовые ящики (ПЯ). Если связь с помощью этих сообщений со стороны каждого процесса устанавливается в порядке, изображенном в листинге 7.1, то никаких трудностей

348
не возникает. Однако перестановка этих двух процедур в каждом из процессов
(листинг 7.2) вызывает тупик:
Рис. 7.2. Кольцевая схема взаимодействия процессов
Листинг 7.1. Вариант без тупиковой ситуации
ПР1: . . .
ПОСЛАТЬ СООБЩЕНИЕ (ПР2, M1, ПЯ2);
ЖДАТЬ СООБЩЕНИЕ (ПР3, М3, ПЯ1);
ПР2: . . .
ПОСЛАТЬ СООБЩЕНИЕ (ПРЗ, М2, ПЯ3);
ЖДАТЬ СООБЩЕНИЕ (ПР1, M1, ПЯ2);
ПРЗ: . . .
ПОСЛАТЬ СООБЩЕНИЕ (ПР1, МЗ, ПЯ1);
ЖДАТЬ СООБЩЕНИЕ (ПР2, М2, ПЯ3);
Листинг 7.2. Вариант с тупиковой ситуацией
ПР1: . . .
ЖДАТЬ СООБЩЕНИЕ (ПР3, М3, ПЯ1);
ПОСЛАТЬ СООБЩЕНИЕ (ПР2, M1, ПЯ2);

349
ПР2: . . .
ЖДАТЬ СООБЩЕНИЕ (ПР1, M1, ПЯ2);
ПОСЛАТЬ СООБЩЕНИЕ (ПРЗ, М2, ПЯЗ);
ПРЗ: . . .
ЖДАТЬ СООБЩЕНИЕ (ПР2, М2, ПЯЗ);
ПОСЛАТЬ СООБЩЕНИЕ (ПР1, МЗ, ПЯ1);
В самом деле, во втором варианте ни один из процессов не сможет послать со- общения до тех пор, пока сам его не получит, а этого события никогда не произой- дет, поскольку ни один процесс не может этого сделать.
Пример тупика на ресурсах типа CR и SR
Пусть некоторый процесс ПР1 должен обменяться сообщениями с процессом
ПР2 и каждый из них запрашивает некоторый ресурс R, причем ПР1 требует три единицы этого ресурса для своей работы, а ПР2 – две единицы и только на время обработки сообщения. Всего же имеются только четыре единицы ресурса R. Запрос ресурса можно реализовать через соответствующий монитор с процедурами RE-
QUEST(R, N) – запрос N единиц ресурса R и RELEASE(R, N) – освобождение, воз- врат N единиц ресурса R. Обмен сообщениями будем осуществлять через почто- вый ящик MB. Фрагменты программ ПР1 и ПР2 приведены в листинге. 7.3.
Листинг 7.3. Пример тупика на CR- и SR-pecypcax
ПР1: REQUEST (R, 3);
SEND_MESSAGE (ПР2, сообщение, MB);
WAIT ANSWER (ответ, MB);
RELEASE (R, 3);