СИСТЕМА УПРАВЛЕНИя ПРОЦЕССАМИ ОБЕСПЕчИВАЕТ ПРОХОЖДЕНИЕ ПРОЦЕССА чЕРЕЗ КОМПЬЮТЕР. В ЗАВИСИМОСТИ ОТ СОСТОяНИя ПРОЦЕССА ЕМУ ДОЛЖЕН БЫТЬ ПРЕДОСТАВИТЬ ТОТ ИЛИ ИНОЙ РЕСУРС. НАПРИМЕР, НОВЫЙ ПРОЦЕСС НЕОБХОДИМО РАЗМЕСТИТЬ В ОСНОВНОЙ ПАМяТИ, СЛЕДОВАТЕЛЬНО, ЕМУ НЕОБХОДИМО ВЫДЕЛИТЬ чАСТЬ АДРЕСНОГО ПРОСТРАНСТВА. ПРОЦЕССУ В СОСТОяНИИ ГОТОВЫЙ ДОЛЖНО БЫТЬ ПРЕДОСТАВЛЕНО ПРОЦЕССОРНОЕ ВРЕМя. ВЫПОЛНяЕМЫЙ ПРОЦЕСС МОЖЕТ ПОТРЕБОВАТЬ ОБОРУДОВАНИЕ ВВОДА - ВЫВОДА И ДОСТУП К ФАЙЛУ.
Распределение процессов между имеющимися ресурсами носит название планирование процессов. Одним из методом планирования процессов, ориентированных на эффективную загрузку ресурсов, является метод очередей ресурсов. Новые процессы находятся во входной очереди, часто называемой очередью работ - заданий (job queue).
Входная очередь располагается во внешней памяти, во входной очереди процессы ожидают освобождения ресурса — адресного пространства основной памяти.
Готовые к выполнению процессы располагаются в основной памяти и связаны очередью готовых процессов или ready queue. Процессы в этой очереди ожидают освобождения ресурса процессорное время.
Процесс в состоянии ожидания завершения операции ввода - вывода находится в одной из очередей к оборудованию ввода - вывода, которая носит название devices queue.
При прохождении через компьютер процесс мигрирует между различными очередями под управлением программы, которая называется планировщик. (scheduler) Операционная система, обеспечивающая режим мультипрограммирования, обычно включает два планировщика — долгосрочный (long term scheduler) и краткосрочный (short term scheduler/CPU scheduler).
Основное отличие между долгосрочным и краткосрочным планировщиками заключается в частоте запуска, например: краткосрочный планировщик может запускаться каждые 100 мс, долгосрочный — один раз за несколько минут.
Долгосрочный планировщик решает, какой из процессов, находящихся во входной очереди, должен быть переведен в очередь готовых процессов в случае освобождения ресурсов памяти.
Долгосрочный планировщик выбирает процесс из входной очереди с целью создания неоднородной мультипрограммной смеси. Это означает, что в очереди готовых процессов должны находиться в разной пропорции как процессы, ориентированные на ввод - вывод, так и процессы, ориентированные на преимущественную работу с CPU.
Краткосрочный планировщик решает, какой из процессов, находящихся в очереди готовых процессов, должен быть передан на выполнение в CPU. В некоторых операционных системах долгосрочный планировщик может отсутствовать. Например, в системах разделения времени (time sharing system), каждый новый процесс сразу же помещается в основную память.
1.3. Взаимодействие процессов.
Пользовательский уровень.
СОВМЕСТНО ВЫПОЛНяЕМЫЕ ПРОЦЕССЫ МОГУТ БЫТЬ ЛИБО НЕЗАВИСИМЫМИ (INDEPENDED PROCESSES), ЛИБО ВЗАИМОДЕЙСТВУЮЩИМИ (COOPERATING PROCESSES). ВЗАИМОДЕЙСТВИЕ ПРОЦЕССОВ чАСТО ПОНИМАЕТСя В СМЫСЛЕ ВЗАИМНОГО ОБМЕНА ДАННЫМИ чЕРЕЗ ОБЩИЙ БУФЕР ДАННЫХ.
Взаимодействие процессов удобно рассматривать в схеме производитель - потребитель (produces - consumer). Например, программа вывода на печать производит последовательность символов, которые потребляются драйвером принтера или компилятор производит ассемблерный текст, который затем потребляется ассемблером.
Для того чтобы процесс - производитель и процесс - потребитель могли заполнять совместно необходимый буфер, заполняемый процессом - производителем и потребляемым процессом - потребителем.
Буфер имеет фиксированные размеры, и, следовательно процессы могут находиться в состоянии ожидания, когда:
1. буфер заполнен; ожидает процесс - производитель
2. буфер пуст; ожидает процесс - потребитель
Буфер может предоставляться и поддерживаться самой ОС, например с помощью средств коммуникации процессов (IPC — Inter Process Communication), либо организовать прикладным программистом. При этом оба процесса используют общий участок памяти, например процесс - производитель и процесс - потребитель могут использовать следующие переменные: Var n; type item=...; Var buffer:array[0..n-1] of item; in, out:0..n-1; где n - количество адресуемых элементов буфера, Item - имя типа элементов буфера, in, out - указатели, характеризующие заполнение буфера.
Буфер представлен в виде циклически связанного массива адресуемых элементов с двумя указателями - in, out. Указатель in содержит номер первого свободного элемента буфера, а out - первого занятого элемента буфера. | | | | | | | | | | | | | | | | | | |0 |1 |2 |3 |4 |5 | | | | |n-| | | | | | | | | | | | | | | |1 | | | | | | | | | | | | | | | | | | |
1. Пуст. in=out. Очевидно, что буфер пуст в том случае, если выполняется это условие. 1. Буфер будет полностью заполнен, если выполняется условие (in+1) mod n = out
Процесс - производитель должен выполнять процедуру записи в буфер типа
Repeat
... продуцируется очередной элемент в Next p ... while (in+1) mod n = out do no_op; buffer (in):=next p; in:=(in+1) mod n; until false где Next p - локальная переменная процесса - производителя, в которой хранится очередной продуцируемый элемент no_op - пустой оператор Процесс - потребитель должен выполнять процедуру чтения из буфера типа Repeat while in = out do no_op; next p := buffer (out); out:=(out+1) mod n;
... потребляется очередной элемент из Next
... until false
2. Планирование процессора.
КРАТКОСРОчНЫЙ ПЛАНИРОВЩИК ВЫБИРАЕТ ПРОЦЕССЫ ИЗ ОчЕРЕДИ ГОТОВЫХ ПРОЦЕССОВ И ПЕРЕДАЕТ ИХ НА ВЫПОЛНЕНИЕ В CPU. СУЩЕСТВУЮТ РАЗЛИчНЫЕ АЛГОРИТМЫ ИЛИ СТРАТЕГИИ РЕШЕНИя ЭТОЙ ЗАДАчИ, ОТЛИчАЮЩИЕСя ОТНОШЕНИЕМ К КРИТЕРИяМ ПЛАНИРОВАНИя.
2.1. Критерии планирования процессора.
ИСПОЛЬЗУЮТСя СЛЕДУЮЩИЕ КРИТЕРИИ, ПОЗВОЛяЮЩИЕ СРАВНИВАТЬ АЛГОРИТМЫ КРАТКОСРОчНЫХ ПЛАНИРОВЩИКОВ: 1. утилизация CPU (использование) CPU utilization. Утилизация CPU теоретически может находиться пределах от 0 до 100%. В реальных системах утилизация CPU колеблется в пределах 40% для легко загруженного CPU, 90% для тяжело загруженного CPU. 1. пропускная способность CPU throughput. Пропускная способность CPU может измеряться количеством процессов, которые выполняются в единицу времени. 1. время оборота (turnaround time) для некоторых процессов важным критерием является полное время выполнения, то есть интервал от момента появления процесса во входной очереди до момента его завершения. Это время названо временем оборота и включает время ожидания во входной очереди, время ожидания в очереди готовых процессов, время ожидания в очередях к оборудованию, время выполнения в процессоре и время ввода - вывода. 1. время ожидания (waiting time). Под временем ожидания понимается суммарное время нахождения процесса в очереди готовых процессов. 1. время отклика (response time) для сугубо интерактивных программ важным показателем является время отклика или время, прошедшее от момента попадания процесса во входную очередь до момента первого обращения к терминалу.
Очевидно, что простейшая стратегия краткосрочного планировщика должна быть направлена на максимизацию средних значений загруженности и пропускной способности, времени ожидания и времени отклика.
В ряде случаев используются сложные критерии, например, так называемый минимаксный критерий, то есть вместо простого критерия минимум среднего времени отклика используется следующий — минимум максимального времени отклика.
2.2. Стратегии планирования процессора.
2.2.1.ПЕРВЫЙ ПРИШЕЛ - ПЕРВЫЙ ОБСЛУЖИВАЕТСя FIFO. FIRST COME -
FIRST SERVED (FCFS).
НА РИСУНКЕ СХЕМАТИчЕСКИ ПОКАЗАНО, КАКИМ ОБРАЗОМ ОПЕРАЦИОННАя СИСТЕМА ИСПОЛЬЗУЕТ PROCESS CONTROL BLOCK ДЛя ПЕРЕКЛЮчЕНИя ПРОЦЕССОРА С ОДНОГО ПРОЦЕССА НА ДРУГОЙ.
FCFS является наиболее простой стратегией планирования процессов и заключается в том, что процессор передается тому процессу, который раньше всех других его запросил.
Когда процесс попадает в очередь готовых процессов, process control block присоединяется к хвосту очереди.
Среднее время ожидания для стратегии FCFS часто весьма велико и зависит от порядка поступления процессов в очередь готовых процессов. Пример № 1
Пусть три процесса попадают в очередь одновременно в момент 0 и имеют следующие значения времени последующего обслуживания в CPU. вариант 1: П1(24 мс) П2(3 мс) П3(3 мс) вариант 2: П2(3 мс) П3(3 мс) П1(24 мс)
На рисунке приведены диаграммы Ганга очереди готовых процессов вариант 1: |П1 |П2 |П3 |WT=17 мс | |WT1=0 мс |WT2=24 мс |WT3=27 мс | |
вариант 2: |П2 |П3 |П1 |WT=3 мс | |WT2=0 мс |WT3=3 мс |WT1=6 мс | |
Стратегии FCFS присущ так называемый “эффект конвоя”. В том случае, когда в компьютере имеется один большой процесс и несколько малых, то все процессы собираются в начале очереди готовых процессов, а затем в очереди к оборудованию. Таким образом, “эффект конвоя” приводит к снижению загруженности как процессора, так и периферийного оборудования.
2.2.2. Стратегия - наиболее короткая работа! SJF.
SJF — SHORTEST JOB FIRST. ОДНИМ ИЗ МЕТОДОВ БОРЬБЫ С “ЭФФЕКТОМ КОНВОя” яВЛяЕТСя СТРАТЕГИя, ПОЗВОЛяЮЩАя ПРОЦЕССУ ИЗ ОчЕРЕДИ ВЫПОЛНяТЬСя ПЕРВЫМ. Пример № 2
Пусть четыре процесса одновременно попадают в очередь готовых процессов и имеют следующие значения времени последующего обслуживания П1(6 мс) П2(8 мс) П3(7 мс) П4(3 мс) |П4 |П1 |П3 |П2 |WT=7 мс | |WT4=0 мс |WT1=3 мс |WT3=9 мс |WT2=16 мс | |
На рисунке приведена диаграмма Ганга, построенная в соответствии со стратегией SJF.
Легко посчитать, что при использовании FCFS - стратегии среднее время ожидания для тех же процессов равно 10.25 мс, таким образом стратегия SJF снижает время ожидания очереди. Наибольшая трудность в практической реализации SJF заключается в невозможности заранее определить величину времени последующего обслуживания.
Поэтому стратегия SJF часто применяется в долгосрочных планировщиках, обслуживающих пакетный режим. В этом случае вместо величины времени последующего обслуживания используется допустимое максимальное время выполнения задания, которое программист должен специфицировать перед отправкой задания в пакет.
2.2.3. Приоритетное планирование.
ОПИСАННЫЕ РАНЕЕ СТРАТЕГИИ МОГУТ РАССМАТРИВАТЬСя КАК чАСТНЫЕ СЛУчАИ СТРАТЕГИИ ПРИОРИТЕТНОГО ПЛАНИРОВАНИя. ЭТА СТРАТЕГИя ПРЕДПОЛАГАЕТ, чТО КАЖДОМУ ПРОЦЕССУ ПРИПИСЫВАЕТСя ПРИОРИТЕТ, ОПРЕДЕЛяЮЩИЙ ОчЕРЕДНОСТЬ ПРЕДОСТАВЛЕНИя ЕМУ CPU. НАПРИМЕР, СТРАТЕГИя FCFS ПРЕДПОЛАГАЕТ, чТО ВСЕ ПРОЦЕССЫ ПРЕДПОЛАГАЕТ, чТО ВСЕ ПРОЦЕССЫ ИМЕЮТ ОДИНАКОВЫЕ ПРИОРИТЕТЫ, А СТРАТЕГИя SJF ПРЕДПОЛАГАЕТ, чТО ПРИОРИТЕТ ЕСТЬ ВЕЛИчИНА, ОБРАТНАя ВРЕМЕНИ ПОСЛЕДУЮЩЕГО ОБСЛУЖИВАНИя.
Страницы: 1, 2, 3, 4
