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

275
// Описание: главная программа
// Входные параметры: список имён файлов для обработки
// Выходные параметры: нет
//
int main(int argc, char *argv[ ])
{
int i, pid, status;
// для всех файлов, перечисленных в командной строке for (i = 1; i< argc; i++)
{
// запускаем дочерний процесс pid = fork();
if (pid == 0)
{
// если выполняется дочерний процесс
// вызов функции счёта количества пробелов в файле printf( "(PID: %d), File %s, spaces = %d\n", getpid(), argv[i], processFile( argv[i]));
// выход из процесса exit();
}
// если выполняется родительский процесс else printf( "processFile started (pid = %d)\n", pid);
}
// ожидание окончания выполнения всех запущенных процессов if (pid != 0) while (wait(&status )>0);
return;
}
Из этого текста видно, что в этом случае все вычисления принимают статус процессов, а не тредов.
В заключение можно заметить, что очень трудно сравнивать API. При их раз- работке создатели, как правило, стараются реализовать полный набор основных функций, используя которые можно решать различные задачи, хотя, порой, и раз- личными способами. Один набор будет хорош для одного набора задач, другой –
для иного набора задач. Тем более что фактически у нас сейчас существенно огра- ниченное множество API. Причина в том, что доминируют наиболее распростра- нённые ОС, на распространение которых в большей степени оказали влияние не достоинства или недостатки этих ОС и их API, а правильная маркетинговая поли- тика фирм, их создавших.

276

277
Операционные системы имеют в своем составе различные средства синхрони- зации. Знание этих средств и их правильное использование позволяет создавать программы, которые при своей работе осуществляют корректный обмен информа- цией, а также исключают возможность возникновения тупиковых ситуаций.
В настоящем разделе рассматриваются основные понятия и проблемы, харак- терные для параллельных процессов. Описываются основные механизмы синхро- низации, даётся их сравнительный анализ, приводятся примеры характерных про- грамм, использующих данные механизмы.
Независимые и взаимодействующие
вычислительные процессы
Основной особенностью мультипрограммных операционных систем является то, что в их среде параллельно развивается несколько (последовательных) вычис- лительных процессов. С точки зрения внешнего наблюдателя эти последователь- ные вычислительные процессы, выполняются одновременно, мы будем использо- вать термин «параллельно». При этом под параллельными понимаются не только процессы, одновременно развивающиеся на различных процессорах, каналах и устройствах ввода/вывода, но и те последовательные процессы, которые разделяют центральный процессор и хотя бы частично перекрываются во времени. Любая мультипрограммная операционная система вместе с параллельно выполняющими- ся в ней задачами пользователей может быть логически описана как совокупность последовательных процессов, которые, с одной стороны, состязаются за использо- вание ресурсов, переходя из одного состояния в другое, а с другой – действуют почти независимо друг от друга, но образуют систему вследствие установления всевозможного рода связей между ними (путем пересылки сообщений и синхрони- зирующих сигналов).
Итак, параллельными мы будем называть такие последовательные вычисли- тельные процессы, которые одновременно находятся в каком-либо активном со- стоянии. Два параллельных процесса могут быть независимыми (independing proc- esses) либо взаимодействующими (cooperating processes).

278
Независимыми являются процессы, множества переменных которых не пере- секаются. Под переменными в этом случае понимают файлы данных, а также об- ласти оперативной памяти, сопоставленные определённым в программе и проме- жуточным переменным. Независимые процессы не влияют на результаты работы друг друга, так как не могут изменить значения переменных другого независимого процесса. Они могут только явиться причиной задержек исполнения других про- цессов, так как вынуждены разделять ресурсы системы.
Взаимодействующие процессы совместно используют некоторые (общие) пе- ременные, и выполнение одного процесса может повлиять на выполнение другого.
Как мы уже говорили, при выполнении вычислительные процессы разделяют ресурсы системы. Подчеркнём, что при рассмотрении вопросов синхронизации вычислительных процессов из числа разделяемых ими ресурсов исключаются: цен- тральный процессор и программы, реализующие эти процессы; то есть с логиче- ской точки зрения каждому процессу соответствуют свои процессор и программа,
хотя в реальных системах обычно несколько процессов разделяют один процессор и одну или несколько программ. Многие ресурсы вычислительной системы могут совместно использоваться несколькими процессами, но в каждый момент времени к разделяемому ресурсу может иметь доступ только один процесс. Ресурсы, кото- рые не допускают одновременного использования несколькими процессами, назы- ваются критическими.
Если нескольким вычислительным процессам необходимо пользоваться кри- тическим ресурсом в режиме разделения, им следует синхронизировать свои дей- ствия таким образом, чтобы ресурс всегда находился в распоряжении не более чем одного из процессов. Если один процесс пользуется в данный момент критическим ресурсом, то все остальные процессы, которым нужен этот ресурс, должны полу- чить отказ и ждать, пока он не освободится. Если в операционной системе не пре- дусмотрена защита от одновременного доступа процессов к критическим ресурсам,
в ней могут возникать ошибки, которые трудно обнаружить и исправить. Основной причиной возникновения этих ошибок является то, что процессы в мультипро- граммных операционных системах развиваются с различными скоростями, а отно-

279
сительные скорости развития каждого из взаимодействующих процессов неизвест- ны и не подвластны ни одному из них. Более того, на их скорости могут влиять решения планировщиков, касающиеся других процессов, с которыми ни одна из этих программ не взаимодействует. Кроме того, содержание одного процесса и скорость его исполнения обычно неизвестны другому процессу. Поэтому влияние,
которое оказывают друг на друга взаимодействующие процессы, не всегда пред- сказуемо и воспроизводимо.
Взаимодействовать могут либо конкурирующие процессы, либо процессы, со- вместно выполняющие общую работу. Конкурирующие процессы, на первый взгляд, действуют относительно независимо, но они имеют доступ к общим пере- менным.
Процессы, выполняющие общую совместную работу таким образом, что ре- зультаты вычислений одного процесса в явном виде передаются другому, то есть их работа построена именно на обмене данными, называются сотрудничающими.
Взаимодействие сотрудничающих процессов удобно всего рассматривать в схеме
«производитель – потребитель» (producer – consumer) или, как часто говорят – «по- ставщик – потребитель».
Рис.6.1. Пример конкурирующих процессов
В качестве первого примера рассмотрим работу двух процессов Р1 и Р2 с об- щей переменной X. Пусть оба процесса асинхронно, независимо один от другого,
изменяют (например, увеличивают) значение переменной X, считывая её значение

280
в локальную область памяти R
i
1
, при этом каждый процесс выполняет некоторые последовательности операций во времени (рис. 6.1).
Здесь мы рассмотрим не все операторы каждого из процессов, а только те, в которых осуществляется работа с общей переменной X. Каждому из операторов мы присвоили некоторый условный номер.
Поскольку при мультипрограммировании процессы могут иметь различные скорости исполнения, то может иметь место любая последовательность выполне- ния операций во времени. Если сначала будут выполнены все операции процесса
Р1, а уже потом – все операции процесса Р2 (или, наоборот, сначала операции 4-6,
а затем – операции 1-3), то в итоге переменная Х получит значение, равное Х+2
(рис. 6.2).
Рис.6.2. Первый вариант развития событий при выполнении процессов
Рис.6.3. Второй вариант развития событий при выполнении процессов
Однако, если в промежуток времени между выполнением операций 1 и 3 будет выполнена хотя бы одна из операций 4-6 (рис. 6.3), то значение переменной Х по- сле выполнения всех операций будет не (Х+2), а (Х+1).
Понятно, что это очень серьезная (и, к сожалению, неисправимая, так как её
нельзя проконтролировать) ошибка. Например, если бы процессы Р1 и P2 осущест-
1
Ri – имя переменной для процесса с номером i.

281
вляли продажу билетов и переменная Х фиксировала количество уже проданных,
то в результате некорректного взаимодействия было бы продано несколько билетов на одно и то же место.
В качестве второго примера рассмотрим ситуацию, которая ещё совсем недав- но была достаточно актуальной для первых персональных компьютеров. Пусть на
ПК с простейшей однопрограммной операционной системой (типа MS-DOS) уста- новлена некоторая резидентная программа с условным названием TIME, которая по нажатию на комбинацию клавиш (например, Ctrl+T) воспроизводит на экране дисплея время. Допустим, что значения переменных, указывающих час, минуты и секунды, равны 18:20:59, причём вывод на дисплей осуществляется справа налево
(то есть в порядке: секунды, минуты, часы). Пусть сразу же после передачи про- граммой TIME на дисплей информации «59 секунд» генерируется прерывание от таймера и значение времени обновляется: 18:21:00.
После этого программа TIME, прерванная таймером, продолжит своё выпол- нение, и на дисплей будут выданы значения: минуты = 21, часы = 18. В итоге на экране мы увидим: 18:21:59.
Рассмотрим теперь несколько иной случай развития событий обновления зна- чений времени по сигналу таймера. Если программа ведения системных часов по- сле вычислений количества секунд 59+1 = 60 и замены его на 00 прерывается от нажатия клавиш Ctrl+T, то есть программа не успевает осуществить пересчёт ко- личества минут, то время, индицируемое на дисплее, станет равным 18:20:00. И в этом случае мы получим неверное значение времени.
Наконец, в качестве третьего примера приведем пару процессов, которые из- меняют различные поля записей служащих какого-либо предприятия [37]. Пусть процесс АДРЕС изменяет домашний адрес служащего, а процесс СТАТУС – его должность и зарплату. Пусть каждый процесс копирует всю запись СЛУЖАЩИЙ в свою рабочую область. Предположим, что каждый процесс должен обработать не- которую запись ИВАНОВ. Предположим также, что после того, как процесс АД-
РЕС скопировал запись ИВАНОВ в свою рабочую область, но до того, как он запи- сал скорректированную запись обратно, процесс СТАТУС скопировал первона-

282
чальную запись ИВАНОВ в свою рабочую область. Изменения, выполненные тем из процессов, который первым запишет скорректированную запись назад в файл
СЛУЖАЩИЕ, будут утеряны и, возможно, никто не будет знать об этом.
Чтобы предотвратить некорректное исполнение конкурирующих процессов вследствие нерегламентированного доступа к разделяемым переменным, необхо- димо ввести механизм взаимного исключения, который не позволит двум процес- сам одновременно обращаться к разделяемым переменным.
Кроме реализации в операционной системе средств, организующих взаимное исключение и тем самым регулирующих доступ процессов к критическим ресур- сам, в ней должны быть предусмотрены средства, синхронизирующие работу взаимодействующих процессов. Другими словами, процессы должны обращаться к неким средствам не только ради синхронизации с целью взаимного исключения, но и чтобы обмениваться данными.
Допустим, что «поставщика – это процесс, который отправляет порции ин- формации (сообщения) другому процессу, имя которого «потребитель». Например,
процесс пользователя, порождающий строки для вывода, может выступать как
«поставщик», а процесс, который выводит эти строки на печать, – как «потреби- тель». Один из методов, применяемых при реализации передачи сообщений, со- стоит в том, что заводится пул
1
свободных буферов, каждый из которых может со- держать одно сообщение (длина сообщения может быть произвольной, но ограни- ченной).
В этом случае между процессами «поставщик» и «потребитель» будем иметь очередь заполненных буферов, содержащих сообщения. Когда «поставщик» хочет послать очередное сообщение, он добавляет в конец этой очереди ещё один буфер.
«Потребитель», чтобы получить сообщение, забирает из очереди буфер, который стоит в её начале. Такое решение, хотя и кажется тривиальным, требует, чтобы
«поставщик» и «потребитель» синхронизировали свои действия. Например, они должны следить за количеством свободных и заполненных буферов. «Поставщик»
может передавать сообщения только до тех пор, пока имеются свободные буферы.
1
Пул – pool – это совокупность однородных, динамически распределяемых объектов, например, блоков памяти оди- наковой длины.

283
Аналогично, «потребитель» может получать сообщения только если очередь не пуста. Ясно, что для учёта заполненных и свободных буферов нужны разделяемые переменные, поэтому для сотрудничающих процессов, как и для конкурирующих,
тоже возникает необходимость во взаимном исключении.
Таким образом, до окончания обращения одной задачи к общим переменным следует исключить возможность обращения к ним другой задачи. Эта ситуация и называется взаимным исключением. Другими словами, при организации различно- го рода взаимодействующих процессов приходится организовывать взаимное ис- ключение и решать проблему корректного доступа к общим переменным (критиче- ским ресурсам). Те места в программах, в которых происходит обращение к крити- ческим ресурсам, называются критическими секциями или критическими интерва- лами (Critical Section – CS). Решение этой проблемы заключается в организации та- кого доступа к критическому ресурсу» когда только одному процессу разрешается входить в критическую секцию. Данная задача только на первый взгляд кажется простой, ибо критическая секция, вообще говоря, не является последовательностью операторов программы, а является процессом, то есть последовательностью дейст- вий, которые выполняются этими операторами. Другими словами, несколько про- цессов, которые выполняются по одной и той же программе, могут выполнять кри- тические интервалы, базирующиеся на одной и той же последовательности опера- торов программы.
Когда какой-либо процесс находится в своём критическом интервале, другие процессы могут, конечно, продолжать своё исполнение, но без входа в их критиче- ские секции. Взаимное исключение необходимо только в том случае, когда процес- сы обращаются к разделяемым, общим данным. Если же они выполняют операции,
которые не приводят к конфликтным ситуациям, они должны иметь возможность работать параллельно. Когда процесс выходит из своего критического интервала,
то одному из остальных процессов, ожидающих входа в свои критические секции,
должно быть разрешено продолжить работу (если в этот момент действительно есть процесс в состоянии ожидания входа в свой критический интервал).