2. формируется диспетчер памяти,

3. формируются значения некоторых структур данных (наборы буферов блоков,

буфера индексных дескрипторов) и ряд других.

4. По окончании этих действий происходит инициализация процесса с номером "0".

для этого невозможно использовать методы порождения процессов, изложенные выше, т.е. с использованием функций fork() и exec().

При инициализации этого процесса резервируется память под его контекст и формируется нулевая запись в таблице процессов.

Основными отличиями нулевого процесса являются следующие моменты

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

2. Он существует в течениеe всего времени работы системы (чисто системный процесс) и считается, что он активен, когда работает ядро ОС.

Далее ядро копирует "0" процесс и создает "1" процесс.

Сначала процесс "1" представляет собой полную копию процесса "0" , т.е. у него нет области кода. Потом происходит увеличение его размера. Во вновь созданную кодовую область копируется программа, реализующая системный вызов exec() , необходимый для выполнения программы /etc/init.

На этом завершается подготовка первых двух процессов.

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

Второй – это уже подобие реального процесса.

Далее ОС переходит к выполнению программ диспетчера.

Диспетчер наделен обычными функциями и на первом этапе он запускает exec() , который заменит команды процесса "1" кодом, содержащимся в файле /etc/init. Получившийся процесс, называемый init, призван настраивать структуры процессов системы.

Далее он подключает интерпретатор команд к системной консоли. Так возникает однопользовательский режим, так как консоль регистрируется с корневыми привилегиями и доступ по каким-либо другим линиям связи невозможен.

При выходе из однопользовательского режима init создает многопользовательскую среду.

С этой целью init организует процесс getty для каждого активного канала связи, т.е. каждого терминала. Это программа ожидает входа кого-либо по каналу связи.

Далее, используя системный вызов exec(), getty передает управление программе login, проверяющей пароль.

Во время работы ОС процесс init ожидает завершения одного из порожденных им процессов, после чего он активизируется и создает новую программу getty для соответствующего терминала.

Таким образом процесс init поддерживает многопользовательскую структуру во время функционирования системы.

Лекция 5. Взаимодействие процессов: синхронизация, тупики

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

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

Необходимо уметь решать две важнейшие задачи:

1. Распределение ресурсов между процессами.

2. Организация защиты адресного пространства и других ресурсов, выделенных определенному процессу, от неконтролируемого доступа со стороны других процессов.

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

Рассмотрим ситуацию, изображенную на Рис. 1:

Рис. 1 Конкуренция процессов за ресурс.

В этом случае символ, считанный процессом А, был потерян, а символ, считанный процессом В, был выведен дважды. Результат выполнения процессов здесь зависит от того, в какой момент осуществляется переключение процессов, и от того, какой конкретно процесс будет выбран для выполнения следующим. Такие ситуации называются гонками (race conditions) между процессами, а процессы – конкурирующими. Единственный способ избежать гонок при использовании разделяемых ресурсов – контролировать доступ к любым разделяемым ресурсам в системе. При этом необходимо организовать взаимное исключение – т.е. такой способ работы с разделяемым ресурсом, при котором постулируется, что в тот момент, когда один из процессов работает с разделяемым ресурсом, все остальные процессы не могут иметь к нему доступ.

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

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

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

Е сть два процесса А и В, каждому из которых в некоторый момент требуется иметь доступ к двум ресурсам R₁ и R₂. Процесс А получил доступ к ресурсу R_1, и следовательно, никакой другой процесс не может иметь к нему доступ, пока процесс А не закончит с ним работать. Одновременно процесс В завладел ресурсом R₂. В этой ситуации каждый из процессов ожидает освобождения недостающего ресурса, но оба ресурса никогда не будут освобождены, и процессы никогда не смогут выполнить необходимые действия.

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

Рассмотри классические методы (средства) синхронизации

Средства синхронизации

Семафоры Дейкстры

Семафоры были предложены как механизм синхронизации доступа к разделяемым ресурсам западноевропейским ученым Дейкстрой (Дийкстра - и такой вариант его имени встречается в литературе), человеком известным в теории программирования (Кстати, именно его учения легли в основу разработок алгоритмов маршрутизации сетей). В литературе эти семафоры часто называют семафорами Дейкстры. Он предложил использовать некий формализм, суть которого заключается в том, что есть некоторая целочисленная переменная S, которая называется семафором. Над семафором определены две операции: P(S), V(S).

• действие P(S) таково: если значение семафора равно нулю, то процесс, выполняющий обращение к P(S) будет приостановлен до тех пор, пока какой-нибудь другой процесс не изменит значение семафора, если же значение семафора отлично от 0, то значение семафора будет уменьшено на единицу.

• V(S) увеличивает значение семафора на единицу;

Считается, что операции P(S) и V(S) неделимы. Это означает, что выполнение этих операций не может прерваться до их завершения. Эти операции состоят как бы из трех команд: чтение переменной S, сравнение с 0 и то или иное действие над S. Так вот эти три команды, три действия неделимы. Никакое событие не может приостановить выполнение этой цепочки действий и передать управление другому процессу. (Прослеживается некоторая аналогия с механизмом прерываний, т. е. если при выполнении команды произошло прерывание, то команда выполнятся до конца, затем происходит обработка прерывания с последующим возвратом в эту же точку программы). Две операции с семафором - как бы две цельные машинные команды. Эти команды должны входить в систему команд или же ОС должна уметь эмулирвать их.

Частным случаем продекларированного семафора является двоичный семафор, максимальное значение которого равно единичке. Если S=1, то это означает, что ни один из процессов (связанных с этим семафором) не находится в критическом участке. При S=0 один из процессов находится в критическом участке {вот-вот попадет в очередь}, а другой нормально функционирует. При S=-1 один из процессов находится в критическом участке, а другой заблокирован и находится в очереди.

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

Использование двоичного семафора для организации взаимного исключения проиллюстрировано на рисунке.

Семафоры – это низкоуровневые средства синхронизации, для корректной практической реализации которых необходимо наличие специальных, атомарных семафорных машинных команд.

Мониторы

Идея монитора была впервые сформулирована в 1974 г. Хоаром. В отличие от других средств, монитор представляет собой языковую конструкцию, т. е. Некоторое средство, предоставляемое языком программирования и поддерживаемое компилятором. Монитор представляет собой совокупность процедур и структур данных, объединенных в программный модуль специального типа. Постулируются три основных свойства монитора:

1. структуры данных, входящие в монитор, могут быть доступны только для процедур, входящих в этот монитор (таким образом, монитор представляет собой некоторый аналог объекта в объектно-ориентированных языках и реализует инкапсуляцию данных);

2. процесс «входит» в монитор путем вызова одной из его процедур;

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

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

Обмен сообщениями

Средство, решающее проблему синхронизации

• для однопроцессорных систем и систем с общей памятью,

• для распределенных систем (когда каждый процессор имеет доступ только к своей памяти)

Основная функциональность метода обеспечивается двумя примитивами (являющимися, как и семафоры, в отличие от мониторов, системными вызовами, а не конструкциями языка) :

send (destination, message)

receive (message)

•Синхронизация

- Операции посылки/приема сообщения могут быть блокирующими и не блокирующими.

• Адресация

-Прямая (ID процесса)

-Косвенная (почтовый ящик, или очередь сообщений)

• Длина сообщения

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

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