Александр Кручинин - Операционные системы
Все описанные примитивы не подходят для реализации обмена информации между компьютерами в распределенной системе с несколькими процессорами. Для этого используется передача сообщений. Этот метод межпроцессного взаимодействия использует два примитива: 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 – Трехуровневое планирование
Как только задание попало в систему, для него будет создан соответствующий процесс, который вступает в борьбу за доступ к процессору. В ситуации, когда процессов слишком много, работает второй уровень планирования (планировщик памяти), который определяет, какие процессы будут находиться в памяти, а какие можно выгрузить на диск. Естественно это не должно происходить слишком часто, т.к. дисковые операции сравнительно медленные. Количество процессов, одновременно находящихся в памяти, называется степенью многозадачности.
Конец ознакомительного фрагмента.
Текст предоставлен ООО «ЛитРес».
Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.
Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.
