Александр Кручинин - Операционные системы

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

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

Литература по операционным системам содержит множество интересных проблем, которые широко обсуждались и анализировались с применением различных методов синхронизации. Часть из них описана в работе [14].

2.4 Планирование

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

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

Основные ситуации, когда необходимо применять планирование:

• при создание нового процесса, необходимо решить, какой процесс запустить: родительский или дочерний;

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

• при блокировании процесса на операции ввода-вывода, семафоре или по-другому, необходимо выбрать и запустить другой процесс;

Рисунок 14 – Периоды использования процессора, чередующиеся с ожиданием ввода-вывода: процесс, ограниченный возможностями процессора (а); процесс, ограниченный возможностями устройств ввода-вывода (б)

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

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

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

В различных средах используются различные алгоритмы планирования. Выделяют 3 типичных среды [14]:

• системы пакетной обработки данных;

• интерактивные системы;

• системы реального времени.

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

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

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

Основные задачи алгоритмов планирования: а) для всех систем;

1) справедливость – предоставление каждому процессу справедливой доли процессорного времени;

2) принудительное применение политики – контроль за выполнением принятой политики (т.е., к примеру, предоставление процессам контроля безопасности процессора по первому требованию);

3) баланс – поддержка занятости всех частей системы (т.е. важно, чтобы работало больше устройств, чем один процесс только производил вычисления); б) для систем пакетной обработки данных; 1) пропускная способность – максимальное количество задач в час;

2) оборотное время – минимизация времени, затрачиваемого на ожидание обслуживания и обработку задачи;

3) использование процессора – поддержка постоянной занятости процессора; в) для интерактивных систем;

1) время отклика – быстрая реакция на запросы;

2) соразмерность – выполнение пожеланий пользователя; г) для систем реального времени;

1) окончание работы к сроку – предотвращение потери данных;

2) предсказуемость – предотвращение деградации качества в мультимедийных системах.

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

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

1 «Первым пришёл – первым ушёл»

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

2 Алгоритм «Кратчайшая задача – первая»

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

3 Алгоритм «Наименьшее оставшееся время выполнения»

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

4 Алгоритм трехуровневого планирования

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

Рисунок 15 – Трехуровневое планирование

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

Конец ознакомительного фрагмента.