Виды организации взаимосвязи процессов

Подчиненный процесс – процесс, зависящий от процесса-родителя.

Независимый процесс – дочерний процесс, выполняемый независимо от процесса-родителя

Сопроцесс (coprocess, coroutine) – процесс, равноправно взаимодействующий с другими такими же процессами;

1. Потоки (threads) и многопоточное выполнение программ (multi-threading)

Поток (thread) – это запускаемый из некоторого процесса особого рода параллельный процесс, выполняемый в том же адресном пространстве, что и процесс-родитель.

Многопоточность имеет большие преимущества:

· Увеличение скорости (по сравнению с использованием обычных процессов

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

· Экономия. Благодаря многопоточности, достигается значительная экономия памяти, по причинам, объясненным выше.

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

1. Стратегии и критерии диспетчеризации процессов

Решения по диспетчеризации могут быть приняты в случаях, если процесс:

1)Переключается из состояния выполнения в состояние ожидания.

2)Переключается из состояния выполнения в состояние готовности к выполнению.

3)Переключается из состояния ожидания в состояние готовности.

4)Завершается.

Диспетчеризация типов 1 и 4 обозначается термином диспетчеризация без прерывания процесса (nonpreemptive).

Диспетчеризация типов 2 и 3 обозначается термином диспетчеризация с прерыванием процесса (preemptive).

Диспетчер процессора - компонента ОС, предоставляющая процессор тому процессу, который был выбран планировщиком.

Диспетчер выполняет последовательность действий:

-Переключает контекст

-Переключает процессор в пользовательский режим

-Выполняет переход по соответствующему адресу в пользовательскую программу для ее рестарта.

Скрытая активность (латентность) диспетчера (dispatch latency) - время, требуемое для диспетчера, чтобы остановить один процесс и стартовать другой. Разумеется, система должна стремиться минимизировать это время, однако набор критериев диспетчеризации более сложен.

Критерии диспетчеризации:

1)Использование процессора (CPU utilization) - поддержание его в режиме занятости максимально возможный период времени. Критерий оптимизации: максимизация данного показателя.

2)Пропускная способность системы (throughput) - (среднее) число процессов, завершающих свое выполнение за единицу времени. Критерий оптимизации: максимизация.

3)Время обработки процесса (turnaround time) - время, необходимое для исполнения какого-либо процесса. Критерий оптимизации: минимизация.

4)Время ожидания (waiting time) -время, которое процесс ждет в очереди процессов, готовых к выполнению. Критерий оптимизации: минимизация.

5)Время ответа (response time) - время, требуемое от момента первого запроса до первого ответа. Критерий оптимизации: минимизация.

Стратегии:

Стратегия First-Come-First-Served (обслуживание в порядке поступления) - наиболее простая стратегия диспетчеризации, при которой ресурсы процессора предоставляются процессам в порядке их поступления (ввода) в систему.

Стратегия Shortest Job First (SJF, обслуживание самого короткого задания первым) - стратегия диспетчеризации процессора, при которой процессор предоставляется в первую очередь наиболее короткому процессу из имеющихся в системе.

Возможны две схемы применения данной стратегии:

1)Без прерывания процессов - пока процессу предоставляется процесс, он не может быть прерван, пока не истечет его квант времени.

2)С прерыванием процессов - если приходит новый процесс, время активности которого меньше, чем оставшееся время активного процесса, - прервать активный процесс. Эта схема известна под названием Shortest-Remaining-Time-First (SRTF).

Нетрудно видеть, что стратегия SJF оптимальна, в том смысле, что она обеспечивает минимальное среднее время ожидания для заданного набора процессов.

1. Методы синхронизации процессов

Синхронизация процессов – актуальная задача, исследование которой началось с работ Э. Дейкстры в 1960-х гг. Совместный доступ процессов к общим данным (race condition) может привести к нарушению их целостности, поэтому необходима их синхронизация.

Методы синхронизации процессов:

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

Алгоритм булочной – еще один подход к решению проблемы критических секций. Использует присвоение уникального номера в очереди (приоритета) каждому процессу.

Общий семафор (по Э. Дейкстре) – синхронизирующий примитив: целая переменная, над которой определены семафорные операции wait и signal. Приведено решение проблемы критических секций с помощью семафоров. Семафор реализуется в виде структуры из двух полей:

- счетчик

- ссылка

на список ждущих процессов. Для реализации операций над семафором достаточно двух примитивов:

block – блокировка текущего процесса,

wakeup(P) – разблокировка процесса P.

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

Используются две разновидности семафоров:

-общие (с целым значением) Общий семафор может быть реализован с помощью двоичных семафоров.

- двоичные (значениями могут быть только 0 и 1).

Критические области – высокоуровневая конструкция для синхронизации, основанная на описаниях разделяемых ресурсов (shared) и конструкции region, обеспечивающей взаимное исключение критических секций более удобным и надежным способом, чем семафоры.

Монитор (по Ч. Хоару) – высокоуровневая конструкция для синхронизации: многовходовый модуль, содержащий описание общих данных и операций над ними в виде процедур. Обеспечивается взаимное исключение исполнения мониторных операций. Монитор может также содержать условные переменные, для которых определены операции wait и signal для организации дополнительных очередей процессов. Рассмотрено решение задачи "обедающие философы" с использованием монитора. Описана реализация монитора и условных переменных с помощью семафоров.

В системе Solaris для синхронизации используются адаптивные мьютексы, блокировщики читателей-писателей, условные переменные и "вертушки" (turnstiles), позволяющие сочетать применение адаптивных мьютексов и блокировщиков читателей-писателей.

В системе Windows 2000 для синхронизации используются вертящиеся замки (spinlocks) и объекты-диспетчеры, генерирующие события (аналогичные условным переменным).

1. Тупики (deadlocks), методы предотвращения и обнаружения тупиков

Тупик (deadlock) – множество заблокированных процессов, каждый из которых владеет некоторым ресурсом и ожидает ресурса, которым владеет какой-либо другой процесс из этого множества.

Тупик может возникнуть, если одновременно выполняются следующие четыре условия:

1. взаимное исключение: только один процесс в каждый момент времени может получить доступ к ресурсу;

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

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

4. циклическое ожидание: существует множество {P0, P1, … Pn},такое, что P0 ожидает ресурса, которым обладает P1; P1 ожидает ресурса, которым обладает P2 … Pn ожидает ресурса, которым обладает P0.

• Если граф распределения ресурсов не содержит циклов, то в системе тупиков нет;
• Если граф распределения ресурсов содержит цикл, то возможно два случая:

· Если ресурсов каждого вида имеется только по одному экземпляру, то имеет место тупик;

· Если ресурсов по несколько экземпляров, то тупик возможен.