Конспект лекций для студентов специальности 5В070200 Автоматизация и управление Алматы 2015

29 
бесприоритетном обслуживании выбор задач производится в некотором 
заранее установленном порядке без учета их относительной важности и 
времени обслуживания. При реализации приоритетных дисциплин 
обслуживания отдельным задачам предоставляется преимущественное право 
попасть в состояние исполнения. В концепции приоритетов имеются 
следующие варианты: приоритет, присвоенный задаче, является величиной 
постоянной; приоритет изменяется в течение времени решения задачи 
(динамический приоритет). 
Диспетчеризация 
с 
динамическими 
приоритетами 
требует 
дополнительных 
расходов 
на 
вычисление 
значений 
приоритетов 
исполняющихся задач, поэтому во многих ОС реального времени 
используются методы диспетчеризации на основе абсолютных приоритетов. 
Это позволяет сократить время реакции системы на очередное событие, 
однако требует детального анализа всей системы для правильного присвоения 
соответствующих приоритетов всем исполняющимся задачам, чтобы 
гарантировать обслуживание. Перечень дисциплин обслуживания и их 
классификация приведен на рисунке А.6. Рассмотрим основные наиболее 
часто используемые дисциплины диспетчеризации.
Самой простой в реализации является дисциплина FCFS (First Come First 
Served – первый пришел, первым обслужен), согласно которой задачи 
обслуживаются «в порядке очереди», т.е. в порядке их появления (рисунок 
А.7). Те задачи, которые были заблокированы в процессе работы (попали в 
состояние ожидания, например из-за операций ввода-вывода) после перехода 
в состояние готовности вновь ставятся в эту очередь готовности. При этом 
возможны два варианта:
1)
ставить разблокированную задачу в конец очереди готовых к 
выполнению задач (самый простой, применяется чаще всего);
2)
диспетчер помещает разблокированную задачу перед теми 
задачами, которые еще не выполнялись – т.е. образуется две очереди: одна из 
новых задач, а другая – из ранее выполнявшихся задач, попавших в состояние 
ожидания. 
Дисциплина не требует внешнего вмешательства в ход вычислений, при 
ней не происходит перераспределения процессорного времени. Она относится 
к не вытесняющим дисциплинам. Достоинства: простота реализации и малые 
расходы системных ресурсов на формирование очереди задач. Недостаток: 
при увеличении загрузки вычислительной системы растет среднее время 
ожидания обслуживания, причем короткие задания вынуждены ожидать 
столько же, сколько и трудоемкие. Избежать этого недостатка позволяют 
дисциплины SJN и SRT.
Дисциплина обслуживания SJN (Shortest Job Next – следующим 
выполняется самое короткое задание) требует, чтобы для каждого задания 
была известна оценка в потребностях машинного времени. Она предполагает, 
что имеется только одна очередь заданий, готовых к выполнению. Задания, 
которые были заблокированы в процессе своего исполнения, вновь попадают 

30 
в конец очереди готовых к выполнению наравне с вновь поступающими. Это 
приводило к тому, что те задания, которым требовалось немного времени для 
завершения, вынуждены были ожидать процессор наравне с длительными 
работами. 
Дисциплина обслуживания SRT (Shortest Remaining Time – следующим 
выполняется задание, которому осталось меньше всего времени выполняться 
на компьютере) была предложена для устранения этого недостатка. 
Все три дисциплины обслуживания могут использоваться для пакетных 
режимов обработки, когда пользователю не нужно ждать реакции системы – 
он просто сдает свое задание и через несколько часов получает результаты 
вычислений. Для интерактивных вычислений необходимо обеспечить 
приемлемое 
время 
реакции 
системы. 
Если 
система 
является 
мультитерминальной, желательно, чтобы она обеспечивала еще и равенство в 
обслуживании. Для систем разделения времени основной является система 
обслуживания, согласно которой главным является равенство обслуживания 
при приемлемом времени обслуживания (этой стратегии соответствуют Unix-
системы). Если же система однопользовательская с возможностью 
мультипрограммной обработки, то желательно, чтобы программы, с которыми 
непосредственно работает пользователь, имели лучшее время реакции, 
нежели фоновые задания. При этом желательно, чтобы некоторые 
приложения, выполняясь без непосредственного участия пользователя 
(например, получение электронной почты с использованием модема и 
коммутирующих линий для передачи данных), гарантированно получали 
необходимую им долю процессорного времени.
Для решения перечисленных проблем используется дисциплина 
обслуживания, называемая карусельной (Round Robin, RR), и приоритетные 
методы обслуживания. Дисциплина RR (рисунок А.8) предполагает, что 
каждая задача получает процессорное время порциями (квантами времени q – 
time slice). После окончания кванта времени q задача снимается с процессора, 
и он передается следующей задаче. Снятая задача ставится в конец очереди 
задач, готовых к выполнению. Это - одна из самых распространенных 
дисциплин. 
Для оптимальной работы системы необходимо правильно выбрать 
закон, по которому кванты времени выделяются задачам. Величина кванта 
времени выбирается как компромисс между приемлемым временем реакции 
системы на запросы пользователей и накладными расходами на частую смену 
контекста задач. В некоторых ОС есть возможность указывать в явном виде q 
или диапазон возможных значений, тогда система будет стараться выбирать 
оптимальное значение сама. Дисциплина карусельной диспетчеризации более 
подходит для случая, когда все задачи имеют одинаковые права на 
использование ресурсов центрального процессора. Однако одни задачи всегда 
нужно решать в первую очередь, тогда как остальные могут подождать. Это 
реализуется за счет того, что одной задаче присваивается один приоритет, а 
другой задаче – другой. Задачи в очереди будут располагаться в соответствии 

31 
с их приоритетами. Формирует очередь диспетчер задач. Процессор в первую 
очередь предоставляется задаче с более высоким приоритетом, и только если 
ее потребности удовлетворены или она попала в состояние ожидания, 
диспетчер может предоставить его следующей задаче. Основная идея 
карусельной дисциплины обслуживания и механизм приоритетов по-разному 
используются в различных дисциплинах обслуживания. 
Бывают ситуации, когда ОС не поддерживает в явном виде дисциплину 
RR. Например, в некоторых системах реального времени используется 
диспетчер задач, работающий по принципу абсолютных приоритетов 
(процессор предоставляется задаче с максимальным приоритетом, а при 
равенстве приоритетов он действует по принципу очередности). Т.о. 
причиной снятия задачи с выполнения может быть только появление задачи с 
более высоким приоритетом. В своей простейшей реализации дисциплина RR 
предполагает, что все задачи имеют одинаковый приоритет. Если же 
необходимо ввести механизм приоритетного обслуживания, то это делается за 
счет организации нескольких очередей. Процессорное время предоставляется 
дисциплинам, которые стоят в самой привилегированной очереди. Если она 
пустая, то диспетчер задач начинает посматривать остальные очереди. 
Именно по такому алгоритму действует диспетчер задач в ОС OS/2, Windows 
9x, Windows NT/2000/XP и многих других. Отличия заключаются в 
количестве очередей и правилах перемещения задач из одной очереди в 
другую.
Известные дисциплины диспетчеризации могут применять или не 
применять еще одно правило, касающееся перераспределения процессорного 
времени между выполняющимися задачами. 
Диспетчеризация без 
перераспределения процессорного времени, т.е. невытесняющая (non-
preemptive multitasking) или кооперативная многозадачность – это такой 
способ диспетчеризации задач, при котором активная задача выполняется до 
тех пор, пока она сама «по собственной инициативе» не отдаст управление 
диспетчеру задач для того, чтобы он выбрал из очереди другой, готовый к 
выполнению поток или процесс. Это – дисциплины FCFS, SJN, SRT.
Есть дисциплины, в которых процессор может быть принудительно 
отобран у текущей задачи. Такие дисциплины называются вытесняющими, 
поскольку 
одна 
задача 
вытесняется 
другой. 
Диспетчеризация 
с 
перераспределением процессорного времени между задачами, т.е. 

жүктеу/скачать 0,92 Mb.

Достарыңызбен бөлісу: