УПРАВЛЕНИЕ ПРОЦЕССАМИ
Параллельность
В литературе по операционным системам предлагается много определений процесса, от формального определения в терминах множества состояний выполнения до неформального понятия процесса как отдельного исполнения программы. Возможно, для нас наиболее полезным является определение, предложенное Шоу, который определяет последовательный процесс как “работу, производимую последовательным процессором при выполнении программы с ее данными”. Например, последовательным процессом является компиляция исходной программы на однопроцессорной ЭВМ. Если для компиляции трех исходных программ используется повторно входимый компилятор, обрабатывающий их по очереди, то каждая из компиляций - это отдельный процесс, хотя исполняется только одна копия программы компилятора.
Последовательные процессы, исполнение которых хотя бы частично перекрывается по времени, являются параллельными. Два параллельных процесса могут быть независимыми либо взаимодействующими. Независимыми являются процессы, которые работают на независимых множествах переменных. На результат исполнения такого процесса не влияет работа независимого от него процесса, так как последний никак не может изменить значения переменных первого. Взаимодействующие процессы совместно используют переменные, и выполнение одного влияет на результат другого. “Переменные” в этом контексте требуют более широкой интерпретации; к ним могут относиться файлы данных, а также ячейки оперативной памяти, сопоставленные переменным программы на исходном языке.
Взаимодействовать могут либо конкурирующие процессы, либо процессы, совместно выполняющие общую работу. Примером процессов первого типа в операционной системе является программа обработки отсутствия страницы и супервизор ввода/вывода. Каждая из них добавляет запрос на чтение с конкретного диска а список запросов на ввод/вывод. Примером процессов второго типа является пара программ производитель - потребитель. Такой парой в операционной системе является программа, собирающая информацию об использовании ресурсов, и программа подготовки счетов. Производителем и потребителем могут быть конечно и процессы пользователя. Производитель может подавать запросы, поступающие с автоматических банковских терминалов, а потребитель - производить их обработку. Производитель записывает данные, которые примерно с такой же скоростью считываются потребителем. Чтобы сгладить разницу в скоростях, производитель и потребитель совместно используют буфер, который содержит записанные производителем, но еще не прочитанные потребителем записи.
Влияние, которое оказывают друг на друга взаимодействующие программы, не всегда предсказуемо и воспроизводимо. Это происходит из-за того, что относительные скорости исполнения двух параллельных процессов не подвластны ни одному из них. Более того, на их скорости могут влиять решения планировщика, касающиеся других процессов, с которыми ни одна из этих программ не взаимодействует. Кроме того, скорость одного процесса обычно неизвестна другому. Могут произойти все типы ошибок, зависящих от времени. Так как часто невозможно в точности воспроизвести условия, которые были в момент возникновения ошибки, то исправить ее чрезвычайно трудно. Еще хуже то, что могут существовать на первый взгляд правильные операции, которые фактически работают неверно.
Рассмотрим влияние временной зависимости на каждый из двух типов взаимодействующих процессов. Пусть процессы ПООС (программа обработки отсутствия страницы) и СВВ (супервизор ввода/вывода) добавляют запросы к диску в конец очереди. Эта очередь показана на рис. 2.1 (а). Она имеет указатели как на начало, так и на конец, что позволяет легко удалять и добавлять запросы. Соответствующие части программ ПООС и СВВ приведены на рис. 2.2. Если обращения к ПООС и СВВ и скорости их исполнения таковы, что их работа с указателем на конец списка не перекрывается по времени, то обе вставки будут выполнены правильно. Однако, даже перекрываясь по времени, они все же могут выполняться корректно. Теперь предположим, что после того, как процесс ПООС выполнил первый оператор присваивания, но перед тем, как он продолжит свою работу, процесс СВВ выполняет два оператора присваивания. В результате, как показано на рис. 2.1(6), в очередь будет поставлен запрос запвв, а не нетстр, а указатель конец будет указывать на нетстр вместо запвв. Приведенный пример демонстрирует влияние скорости исполнения, поскольку результат исполнения процессов определяется тем, кто первым успеет установить указатели конец.ссылка и конец.
Можно потребовать, чтобы процессы операционной системы, такие как ПООС и СВВ, были написаны так, чтобы они не прерывали друг друга. Хотя такой подход осуществим для одной пары процессов, неразумно применять его ко всей операционной системе, так как в этом случае высокоприоритетные управляющие программы зачастую должны были бы ждать завершения управляющих программ низкого приоритета и производительность операционной системы заметно бы снизилась. Кроме того, влияние скорости исполнения существенно не только для операционной системы, но и для процессов пользователя.
В качестве второго примера приведем пару процессов, которые изменяют различные поля записей списка служащих данного предприятия. Процесс АДРЕС изменяет адрес, а ЗРПЛ - зарплату, копируя всю запись в свои рабочие области. Пусть каждый процесс должен обработать запись Кейлингерт. Предположим, что после того, как процесс АДРЕС скопировал запись Кейлингерт в свою рабочую область, но до того, как он записал скорректированную запись обратно, процесс ЗРПЛ скопировал первоначальную запись Кейлингерт в свою рабочую область. Изменения, выполненные тем из процессов, который первым запишет скорректированную запись назад в Кейлингерт, будут утеряны, и, возможно, никто не будет знать об этом.
И на управление очередью, и на изменение записи из-за нерегламентированного доступа к разделяемым переменным - указателям в первом примере и записям служащих во втором - влияет скорость исполнения процессов. Чтобы предотвратить некорректное исполнение конкурирующих процессов, н еобходимо ввести такое понятие, как взаимное исключение, которое не позволит двум процессам одновременно обращаться к разделяемым переменным.
Совершенно другая задача возникает в упомянутом ранее примере “производитель - потребитель”. Во-первых, существует опасность, что потребитель попытается читать из пустого буфера. Если буфер считается пустым только потому, что все записи, сделанные производителем, уже прочитаны, то потребитель может прочесть запись второй раз. Если буфep действительно пуст, то операция чтения не выполнится, и, возможно, нужно будет закончить работу потребителя. Вo-вторых, существует опасность, что производитель попытается писать в полный буфер. Если буфер считается полым только потому, что производитель записал больше записей, чем потребитель смог прочесть, то в этом случае будут затираться непрочитанные записи и потребитель получит от производителя меньше информации, чем надо. Если буфер действительно полон, то операция записи не выполнится и, возможно, работу производителя нужно будет закончить.
Трудности, связанные с парой производитель - потребитель. состоят не в том, что оба процесса могут одновременно обращаться к буферу (поскольку они не обращаются к одной и той же записи буфера), а в том, что их обращения производятся асинхронно, что порождает возможность локальных изменений скоростей производства и потребления. В этом случае необходимы средства синхронизации процессов.
Хотя для синхронизации достаточно обмениваться сигналами, часто процессам нужно обмениваться более информативными данными. Так, компилятор, используемый интерактивно, должен вести диалог с каждым пользовательским процессом. Часто один процесс передает другому в качестве сообщения запросы на операции ввода/вывода. Почтовую службу в операционной системе UNIX и в других интерактивных системах можно рассматривать как форму обмена данными между процессами. Для перечисленных действий необходимы средства связи между процессами.
Введение средств для взаимного исключения, синхронизации и связи предоставляет взаимодействующим параллельным процессам возможность получать правильные результаты независимо от скоростей их исполнения. Если эти средства ввести в язык программирования, то многие из упомянутых ошибок можно зафиксировать на этапе компиляции. К таким языкам, предназначенным для программирования параллельных процессов, относятся Concurrent, Pascal, Modula и CSP/k.
Средством взаимодействия процессов могут служить прерывания, и они часто используются для этого, особенно при управлении вводом/выводом. Однако во многих ситуациях вовсе не обязательно, чтобы один процесс прерывал исполнение другого. Вместо этого обычно используются разделяемые переменные, особенно в управляющих программах операционной системы.
