Примитивы взаимодействия процессов

Вводится понятия двух примитивов.

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

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

Применение примитивов

Основное преимущество - это отсутствие активного ожидания..

Проблема заключается в следующем, если спулер пуст, то wakeup срабатывает в пустую.

Проблема переполненного буфера (проблема производителя и потребителя)

Рассмотрим два процесса, которые совместно используют буфер ограниченного размера, один процесс пишет в буфер, другой считывает данные.

Чтобы первый процесс не писал, когда буфер полный, а второй не считывал, когда он пуст, вводится переменная countдля подсчета количества элементов в буфере.

Проблема переполненного буфера

В этой ситуации оба процесса могут попасть в состояние ожидания, если пропадет сигнал активации.

Алгоритм такой ситуации:

1. Процесс В, считал count=0 (заблокироваться он еще не успел)

2. Планировщик передал управление процессу А

3. Процесс А, выполнил все вплоть до wakeup, пытаясь разблокировать процесс В (но он не заблокирован, wakeup срабатывает впустую)

4. Планировщик передал управление процессу В

5. И он заблокировался, и больше сигнала на разблокировку не получит

6. Процесс А в конце концов заполнит буфер и заблокируется, но сигнала на разблокировку не получит.

Семафоры

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

Были предложены две операции down и up (аналоги sleep и wakeup).

Прежде чем заблокировать процесс, down проверяет семафор, если он равен нулю, то он блокирует процесс, если нет, то процесс снова становится активным, и уменьшает семафор на единицу.

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

down уменьшает значение семафора на 1 или блокирует процесс, если семафор =0.

down и up выполняются как элементарное действие, т.е. процесс не может быть блокирован во время выполнения этих операций. Значит, у операционной системы должен быть запрет на все прерывания, и перевод процесса в режим ожидания.

Решение проблемы переполненного буфера с помощью семафора

Применим три семафора:

full - подсчет заполненных сегментов (в начале = 0)

empty - подсчет пустых сегментов (в начале = количеству сегментов)

mutex - для исключения одновременного доступа к буферу двух процессов. (в начале = 1)

Мьютекс упрощенная версия семафора, он управляет доступом к ресурсу. Показывает, блокирован или нет ресурс.

Решение проблемы переполненного буфера с помощью семафора

Применение семафоров для устройств ввода/вывода

Для устройств ввода/вывода семафор выставляется равный нулю. После запуска управляющего процесса выполняется down, и т.к. семафор равен нулю, процесс блокируется. Когда нужно активизировать процесс управления, выполняется up.

Лекция 9. Планирование процессов

Литература

o Современные операционные системы, Э. Таненбаум, 2002, СПб, Питер, 1040 стр., (в djvu 10.1Мбайт) подробнее>>

o Сетевые операционные системы Н. А. Олифер, В. Г. Олифер (в zip архиве 1.1Мбайт)

o Сетевые операционные системы Н. А. Олифер, В. Г. Олифер, 2001, СПб, Питер, 544 стр., (в djvu 6.3Мбайт)подробнее>>

4.1 Основные понятия планирования процессов

Планирование - обеспечение поочередного доступа процессов к одному процессору.

Планировщик - отвечающая за это часть операционной системы.

Алгоритм планирования - используемый алгоритм для планирования.

Ситуации, когда необходимо планирование:

1. Когда создается процесс

2. Когда процесс завершает работу

3. Когда процесс блокируется на операции ввода/вывода, семафоре, и т.д.

4. При прерывании ввода/вывода.

Алгоритм планирования без переключений (неприоритетный) - не требует прерывание по аппаратному таймеру, процесс останавливается только когда блокируется или завершает работу.

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

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

Основные три системы:

1. Системы пакетной обработки - могут использовать неприоритетный и приоритетный алгоритм (например: для расчетных программ).

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

3. Системы реального времени - могут использовать неприоритетный и приоритетный алгоритм (например: система управления автомобилем).

Задачи алгоритмов планирования:

1. Для всех систем
Справедливость - каждому процессу справедливую долю процессорного времени
Контроль над выполнением принятой политики
Баланс - поддержка занятости всех частей системы (например: чтобы были заняты процессор и устройства ввода/вывода)

2. Системы пакетной обработки
Пропускная способность - количество задач в час
Оборотное время - минимизация времени на ожидание обслуживания и обработку задач.
Использование процесса - чтобы процессор всегда был занят.

3. Интерактивные системы
Время отклика - быстрая реакция на запросы
Соразмерность - выполнение ожиданий пользователя (например: пользователь не готов к долгой загрузке системы)

4. Системы реального времени
Окончание работы к сроку - предотвращение потери данных
Предсказуемость - предотвращение деградации качества в мультимедийных системах (например: потерь качества звука должно быть меньше чем видео)

Планирование в системах пакетной обработки

4.2.1"Первый пришел - первым обслужен" (FIFO - First In Fist Out)

Процессы ставятся в очередь по мере поступления.

Преимущества:

o Простата

o Справедливость (как в очереди покупателей, кто последний пришел, тот оказался в конце очереди)

Недостатки:

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

4.2.2 "Кратчайшая задача - первая"

Нижняя очередь выстроена с учетом этого алгоритма

Преимущества:

o Уменьшение оборотного времени

o Справедливость (как в очереди покупателей, кто без сдачи проходит в перед)

Недостатки:

o Длинный процесс занявший процессор, не пустит более новые краткие процессы, которые пришли позже.