При порождении процессов создается иерархическая (древовидная) структура процессов, в которой родительский процесс может порождать несколько («дочерних») процессов-потомков, но у каждого процесса-потомка только один процесс-родитель.
Диспетчеризация и синхронизация процессов [1 c. 30 – 39, 104–110; 2 разд. 3.4]
Диспетчеризация (= планирование) – распределение времени процессора.
Для параллельно выполняемых взаимодействующих или решающих единую задачу программ (процессов или потоков) необходима синхронизация, т. е. согласование их действий по времени.
В частности, синхронизация нужна для проблемы взаимного исключения, когда каждому из процессов, обращающихся к разделяемому ими (т. е. совместно используемому) ресурсу, требуется монопольный доступ – исключение одновременного с ним доступа всех остальных процессов к этому ресурсу.
Когда процесс обращается к разделяемому ресурсу (например, данным), говорят, что этот процесс находится в критическом участке (критической области). Когда процессы используют общий ресурс, и один из процессов находится в своем критическом участке, необходимо исключить вхождение остальных процессов в критические участки.
Для синхронизации n процессов Э. Дейкстра предложил семафор – снабженную очередью целочисленную защищенную переменную, значение которой можно читать и изменять только специальными операциями: P, V и инициализация:
Инициализация_семафора (Семафор, Начальное_значение);
Двоичный семафор принимает значения 0 и 1, считающий семафор – целочисленные значения ≥ 0 для управления идентичными экземплярами одного ресурса. Счетчик семафора равен числу свободных экземпляров ресурса. В очереди у семафора процессы ожидают освобождения ресурса – выполнения V-операций.
Критические участки взаимного исключения по семафору S в каждом из синхронизируемых процессов обрамляются операциями P(S) и V(S) (можно трактовать операцию P как сигнал "получить ресурс", а V – сигнал "возвратить ресурс”):
P(S);
Критический участок;
V(S);
Если несколько процессов выполнят операцию P(S) – получение ресурса, это разрешат первому из них, а остальные будут ждать освобождения ресурса V(S) в очереди на этом семафоре.
Операции P(S) и V(S) должны выполняться в режиме атомарного доступа (без прерываний) и поэтому реализуются в ядре ОС.
Например, в ОС Windows XP двоичный семафор реализован в виде пользовательского объекта типа Critical Section для синхронизации потоков одного процесса. Объекты ядра типа mutex (двоичный семафор) и semaphore (со счетчиком) позволяют синхронизировать потоки одного или разных процессов, но требуют затрат времени для переключения в режим ядра и обратно.
Кроме того, в Windows XP для синхронизации потоков одного процесса в пользовательском режиме используют Interlocked-функции, изменяющие значения переменных в режиме атомарного доступа. Для синхронизации потоков одного или разных процессов можно также использовать любые объекты ядра, которые могут находиться в свободном или занятом состоянии (signaled / nonsignaled state) – типа event (событие), process, job (задание), file и другие.