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

1.

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

2.

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

3.

4. Очереди

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

5. Очередь

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

6.

При прохождении через компьютер процесс
мигрирует между различными очередями под
управлением программы, которая называется
планировщик (scheduler).
Операционная система, обеспечивающая режим
мультипрограммирования, обычно включает два
планировщика — долгосрочный и краткосрочный.
Например, в OS/360 долговременный планировщик
назывался планировщиком заданий, а краткосрочный
— супервизором задач.
На уровень долгосрочного планирования выносятся
редкие системные действия, требующие больших
затрат
системных
ресурсов,
на
уровень
краткосрочного планирования — частые и более
короткие процессы.

7.

Основное различие между долгосрочным и
краткосрочным планировщиками заключается в
частоте
запуска,
например,
краткосрочный
планировщик может запускаться каждые 100 мс,
долгосрочный — 1 раз за несколько минут.
Долгосрочный планировщик решает, какой из
процессов, находящихся во входной очереди, должен
быть переведен в очередь готовых процессов в случае
освобождения ресурсов памяти.
Долгосрочный планировщик выбирает процесс из
входной очереди с целью создания неоднородной
мультипрограммной смеси. Это означает, что в
очереди готовых процессов должны находиться в
разной пропорции как процессы, ориентированные на
ввод-вывод, так и процессы, ориентированные на
преимущественную работу с CPU

8.

На уровне долгосрочного планирования объектом
является не отдельный процесс, а некоторое
объединение процессов по функциональному
назначению,
которое
называется
работой
(приложением).
Каждая работа рассматривается как независимая
от других работ деятельность, связанная с
использованием одной или многих программ и
характеризующаяся
конечностью
и
определенностью. По мере порождения новых
работ создается собственная виртуальная машина
для их выполнения. Например, в ОС Windows 95 для
каждого 32-разрядного приложения реализуется
своя виртуальная машина. Распределение машин
производится
однократно
в
отличие
от
краткосрочного планирования, где процессор
процессу может выделяться многократно

9.

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

10.

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

11. Взаимодействие процессов

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

12.

Буфер имеет фиксированные размеры и, следовательно,
процессы могут находиться в состоянии ожидания, когда:
• буфер заполнен — ожидает процесс-производитель;
• буфер пуст — ожидает процесс-потребитель.
Буфер может предоставляться и поддерживаться самой
ОС, например, с помощью средств межпроцессной
коммуникации,
либо
должен
быть
организован
прикладным программистом. При этом оба процесса
используют общий участок памяти.
Взаимодействие заключается в передаче данных между
процессами или совместном использовании некоторых
ресурсов и обычно реализуется с помощью таких
механизмов, как т р а н с по рте ры, о че ре д и, с и г на - л ы ,
семафоры.

13. Транспортеры (каналы)

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

14. Очереди

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

15. Очереди

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

16. Очереди

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

17. Сигналы

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

18. Сигналы

Характер выполняемых действий при
возникновении сигнала:
обработка системной ошибки при
появлении сигнала,
блокирование сигнала,
передача управления подпрограмме.

19. Лекция 7

Продолжение

20. Семафоры

Являются механизмами передачи сообщений
от одного потока к другому о наступлении
некоторого события. Различают семафоры
системные и оперативной памяти.

21. Семафоры

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

22. Семафоры

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

23. Семафоры

В операционных системах OS/2 и Microsoft Windows существует
специальный механизм для взаимодействия процессов в
реальном масштабе времени. Этот механизм называется DDE
(Dynamic Data Exchange — динамический обмен данными). Он
стандартизирует процесс обмена командами, сообщениями и
объектами для обработки между задачами. Наиболее
распространенным процессом, для которого используется DDE,
является печать.
Другим интерфейсом для обмена данными является OLE (Object
Linking and Embedding — связывание и встраивание объектов).
Этот интерфейс позволяет хранить объекты, созданные одной
программой, в объектах, созданных другой программой, а также
редактировать (печатать) их без нарушения целостности
информации и связей.

24. Семафоры

Одним из наиболее простых, удобных и интуитивных
интерфейсов межпрограммного взаимодействия
является буфер обмена — clipboard. Буфер обмена
может содержать в себе один информационный
объект — фрагмент текста, рисунок и т. д. С помощью
системного вызова процесс может получить копию
информации, содержащейся в буфере обмена, или
сам поместить объект в буфер, при этом старое
содержимое буфера теряется. Таким образом,
программы получают простой, но эффективный
способ обмена информацией в процессе своей
работы.

25.

Стратегии планирования
процессора

26.

4.1 Основные понятия планирования процессов
Планирование - обеспечение поочередного доступа
процессов к одному процессору.
Планировщик - отвечающая за это часть
операционной системы.
Алгоритм планирования - используемый алгоритм
для планирования.
Ситуации, когда необходимо планирование:
•Когда создается процесс
•Когда процесс завершает работу
•Когда процесс блокируется на операции
ввода/вывода, семафоре, и т.д.
•При прерывании ввода/вывода.

27.

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

28.

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

29.

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

30.

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

31.

Планирование в системах пакетной обработки
1.1 "Первый пришел - первым обслужен" (FIFO - First
In Fist Out)
Процессы ставятся в очередь по мере поступления.
Преимущества:
Простота, Справедливость.
Недостатки:
Процесс, ограниченный возможностями процессора
может затормозить более быстрые процессы,
ограниченные устройствами ввода/вывода.

32.

1.2 "Кратчайшая задача - первая"SJF — Shortest Job
First
Преимущества:
Уменьшение оборотного времени
Справедливость (как в очереди покупателей, кто без
сдачи проходит в перед)
Недостатки:
Длинный процесс занявший процессор, не пустит
более новые краткие процессы, которые пришли
позже.

33.

1.3 Наименьшее оставшееся время выполнение
Аналог предыдущего, но если приходит новый
процесс, его полное время выполнения сравнивается с
оставшимся временем выполнения текущего
процесса.

34.

2 Планирование в интерактивных системах
2.1 Циклическое планирование«Карусельная» стратегия планирования RRRound Robin
Самый простой алгоритм планирования и часто используемый.
Каждому процессу предоставляется квант времени процессора. Когда квант
заканчивается процесс переводится планировщиком в конец очереди. При
блокировке процессор выпадает из очереди.
Преимущества: Простота, Справедливость
Недостатки: Если частые переключения (квант - 4мс, а время переключения
равно 1мс), то происходит уменьшение производительности.
Если редкие переключения (квант - 100мс, а время переключения равно
1мс), то происходит увеличение времени ответа на запрос.
При очень малых значениях временного кванта Round Robin стратегию
называют разделением процессора — processor sharing.

35.

2.2 Приоритетное планирование
Каждому процессу присваивается приоритет, и
управление передается процессу с самым высоким
приоритетом.
Приоритет может быть динамический и статический.
Т.е. процессы, ограниченные вводом/вывода, будут
иметь приоритет над процессами ограниченными
процессором.
Часто процессы объединяют по приоритетам в группы,
и используют приоритетное планирование среди
групп, но внутри группы используют циклическое
планирование.

36.

• Обычно приоритет — это целое положительное число, находящееся в
некотором диапазоне, например, от 0 до 7 или от 0 до 1024. Будем
считать, что чем меньше значение числа, тем выше приоритет
процесса. Приоритеты назначаются, исходя из совокупности
внутренних и внешних по отношению к операционной системе
факторов. Внутренние факторы:
требования к памяти;
количество открытых файлов;
отношение среднего времени ввода-вывода к среднему времени
использования ресурсов CPU и т. д.
• Внешние факторы:
важность процесса;
тип и величина файлов, используемых для оплаты;
отделение, выполняющее работы, и т. д.
Внутренние факторы могут использоваться для автоматического
назначения приоритетов самой операционной системой, а внешние —
для принудительного, с помощью оператора.
Главный недостаток приоритетного планирования заключается в
возможности блокирования на неопределенно долгое время
низкоприоритетных процессов.

37.

Так же существуют:
Гарантированное планирование,
Лотерейное планирование,
Справедливое планирование,
Планирование в системах реального времени,
Планирование однородных процессов…
Важно отметить, что для разных назначений уже
разработаны свои алгоритмы планирования
процессов. Они отличаются друг от друга в
зависимости от того, в какой среде они будут
использоваться, на каком устройстве. Задача
разработчика в такой ситуации подобрать
максимально подходящий процесс для его задачи, и,
возможно, доработать его под свою специфику.