Дисциплины диспетчеризации
Известно большое количество правил (дисциплин диспетчеризации), в соответствии с которыми формируется список (очередь) готовых к выполнению задач. Различают два больших класса дисциплин обслуживания – бесприоритетные и приоритетные. При бесприоритетном обслуживании выбор задачи производится в некотором, заранее установленном порядке без учета их относительной важности и времени обслуживания. При реализации приоритетных дисциплин обслуживания отдельным задачам предоставляется преимущественное право попасть в состояние исполнения. Перечень дисциплин обслуживания и их классификация приведены на рис. 1.1.
При использовании приоритетов возможны два варианта:
1) приоритет, присвоенный задаче, может являться величиной постоянной;
2) приоритет задачи может изменяться в процессе ее решения.
Диспетчеризация с динамическими приоритетами требует дополнительных расходов на вычисление значений приоритетов исполняющихся задач, поэтому во многих ОС реального времени используются методы диспетчеризации на основе статических (постоянных) приоритетов. Хотя надо заметить, что динамические приоритеты позволяют реализовать гарантии обслуживания задач.
Существующие дисциплины диспетчеризации процессов могут быть разбиты на два класса – вытесняющие (preemptive) и не вытесняющие (non-preemptive). Диспетчеризация без перераспределения процессорного времени, т.е. невытесняющая многозадачность (non-preemptive multitasking) – это такой способ диспетчеризации процессов, при котором активный процесс выполняется до тех пор, пока он сам, «по собственной инициативе», не отдаст управление Диспетчеру задач. Диспетчер задач – программа, обслуживающая очередь задач на использование центрального процессора.
Диспетчеризация перераспределением процессорного времени между задачами, то есть вытесняющая многозадачность (preemptive multitasking) – это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается диспетчером задач, а не самой активной задачей. При вытесняющей многозадачности механизм диспетчеризации задач целиком сосредоточен в операционной системе, и программист может писать свое приложение, не заботясь о том, как оно будет выполняться параллельно с другими задачами. В большинстве современных ОС для мощных вычислительных систем, а также и в ОС для ПК, ориентированных на высокопроизводительное выполнение приложений (Windows NT, OS/2, Unix), реализована вытесняющая многозадачность.
Рассмотрим, как организована вытесняющая многозадачность в ОС Windows NT. Жизненный цикл задачи начинается в тот момент, когда программа создает новую задачу. Менеджер процессов выделяет память для задачи и обращается к ядру. После инициализации задача проходит через следующие состояния:
• Готовность. При поиске задачи на выполнение диспетчер просматривает только задачи, находящиеся в состоянии готовности, у которых есть все для выполнения, но не хватает только процессора.
• Первоочередная готовность (standby). Для каждого процессора системы выбирается одна задача, которая будет выполняться следующей (самая первая в очереди). Когда условия позволяют, происходит переключение на контекст этой задачи.
• Выполнение. Как только происходит переключение контекстов, задача переходит в состояние выполнения и находится в нем до тех пор, пока либо ядро не вытеснит ее, из-за того что появилась более приоритетная задача или закончился квант времени, выделенный этой задаче, либо задача завершится вообще, либо она по собственной инициативе перейдет в состояние ожидания.
• Ожидание. Задача может входить в состояние ожидания несколькими способами: задача по своей инициативе ожидает некоторый объект, для того чтобы синхронизировать свое выполнение; операционная система (например, подсистема ввода-вывода) может ожидать в интересах задачи; подсистема окружения может непосредственно заставить задачу приостановить себя. Когда ожидание задачи подойдет к концу, она возвращается в состояние готовности.
• Переходное состояние. Задача входит в переходное состояние, если она готова к выполнению, но ресурсы, которые ей нужны, заняты. Например, страница, содержащая стек задачи, может быть выгружена из оперативной памяти на диск. При освобождении ресурсов задача переходит в состояние готовности.
• Завершение. Когда выполнение задачи закончилось, она входит в состояние завершения. Находясь в этом состоянии, задача может быть либо удалена, либо не удалена. Это зависит от алгоритма работы менеджера объектов, в соответствии с которым он и решает, когда удалять объект.
Рассмотрим кратко некоторые основные (наиболее часто используемые) дисциплины диспетчеризации.
Самой простой в реализации является дисциплина FCFS (first come – first served), согласно которой задачи обслуживаются «в порядке очереди», то есть в порядке их появления. Те задачи, которые были заблокированы в процессе работы (попали в какое-либо из состояний ожидания, например, из-за операций ввода/вывода), после перехода в состояние готовности ставятся в эту очередь готовности перед теми задачами, которые еще не выполнялись. Другими словами, образуются две очереди (рис. 1.2): одна очередь образуется из новых задач, а вторая очередь – из ранее выполнявшихся, но попавших в состояние ожидание. Такой подход позволяет реализовать такую стратегию обслуживания, как «по возможности заканчивать вычисления в порядке их появления». Эта дисциплина обслуживания не требует внешнего вмешательства в ход вычислений, при ней не происходит перераспределение процессорного времени.
К достоинствам этой дисциплины, прежде всего, можно отнести простоту реализации и малые расходы системных ресурсов на формирование очереди задач.
Однако эта дисциплина приводит к тому, что при увеличении загрузки вычислительной системы растет и среднее время ожидания обслуживания, причем короткие задания (требующие небольших затрат машинного времени) вынуждены ожидать столько же, сколько и трудоемкие задания. Избежать этого недостатка позволяют дисциплины SJN и SRT.
Дисциплина обслуживания SJN (shortest job next, что означает: следующим будет выполняться кратчайшее задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Необходимость сообщать ОС характеристики задач, в которых описывались бы потребности в ресурсах вычислительной системы, привела к тому, что были разработаны соответствующие языковые средства. В частности, язык JCL (job control language, язык управления заданиями) был одним из наиболее известных. Пользователи вынуждены были указывать предполагаемое время выполнения и для того, чтобы они не злоупотребляли возможностью указать заведомо меньшее время выполнения (с целью получить результаты раньше других), ввели подсчет реальных потребностей. Диспетчер задач сравнивал заказанное время и время выполнения и в случае превышения указанной оценки в данном ресурсе ставил данное задание не в начало, а в конец очереди. Дисциплина обслуживания SJN предполагает, что имеется только одна очередь заданий, готовых к выполнению. И задания, которые в процессе своего исполнения были временно заблокированы (например, ожидали завершения операций ввода/вывода), вновь попадают в конец очереди готовых к выполнению наравне с вновь поступающими. Это приводит к тому, что задания, которым требуется очень немного времени для своего завершения, вынуждены ожидать процессор наравне с длительными работами, что не всегда хорошо.
Для устранения этого недостатка и была предложена дисциплина SRT (shortest remaining time, следующее задание требует меньше всего времени для своего завершения).
Все эти три дисциплины обслуживания могут использоваться для пакетных режимов обработки, когда пользователь не вынужден ожидать реакции системы, а просто сдает свое задание и через несколько часов получает свои результаты вычислений. Для интерактивных же вычислений желательно прежде всего обеспечить приемлемое время реакции системы и равенство в обслуживании, если система является мультитерминальной. Если же это однопользовательская система, но с возможностью мультипрограммной обработки, то желательно, чтобы те программы, с которыми мы сейчас непосредственно работаем, имели лучшее время реакции, нежели наши фоновые задания. При этом мы можем пожелать, чтобы некоторые приложения, которые выполняются без нашего непосредственного участия (например, программа получения электронной почты, использующая модем и коммутируемые линии для передачи данных), тем не менее гарантированно получали необходимую им долю процессорного времени. Для решения подобных проблем используется дисциплина обслуживания, называемая RR (round robin – круговая, карусельная), и приоритетные методы обслуживания.
Дисциплина обслуживания RR предполагает, что каждая задача получает процессорное время порциями (говорят: квантами времени, q). После окончания кванта времени q задача снимается с процессора, и он передается следующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполнению. Эта дисциплина обслуживания иллюстрируется рис. 1.3. Для оптимальной работы системы необходимо правильно выбрать закон, по которому кванты времени выделяются задачам. Величина кванта времени q выбирается как компромисс между приемлемым временем реакции системы на запросы пользователей (с тем, чтобы их простейшие запросы не вызывали длительного ожидания) и накладными расходами на частую смену контекста задач.
Дисциплина диспетчеризации RR – это одна из самых распространенных дисциплин. В своей простейшей реализации дисциплина карусельной диспетчеризации предполагает, что все задачи имеют одинаковый приоритет. Если же необходимо ввести механизм приоритетного обслуживания, то это, как правило, делается за счет организации нескольких очередей. Процессорное время будет предоставляться в первую очередь тем задачам, которые стоят в самой привилегированной очереди. Если она пустая, то диспетчер задач начнет просматривать остальные очереди. Именно по такому алгоритму действует диспетчер задач в операционных системах OS/2 и Windows NT.
Дисциплины обслуживания FCFS, SJN, SRT относятся к невытесняющим. Дисциплина RR и многие другие, построенные на ее основе, относятся к вытесняющим.
Статьи к прочтению:
11. LINUX. Распределение ресурсов системы | Технострим
Похожие статьи:
При выполнении программ, реализующих какие-либо задачи контроля и управления (что характерно, прежде всего, для систем реального времени), может…
Источник
Дисциплины диспетчеризации
Стратегии планирования (диспетчеризации)
Планирование процессов и диспетчеризация задач
Стратегия планирования определяет, какие процессы планируются на выполнение, чтобы достичь поставленной цели. Существует много стратегий, можно назвать некоторые из них:
a) по возможности заканчивать вычислительные процессы в том же самом
порядке, в котором они были начаты;
b) отдавать предпочтение более коротким процессам;
c) предоставлять всем процессам пользователей одинаковые услуги, в том
числе и одинаковое время ожидания.
Когда говорят о стратегии обслуживания, всегда имеют в виду понятие процесса, поскольку процесс может состоять из нескольких задач.
Известно большое количество правил (дисциплин) диспетчеризации, в соответствии с которыми формируется список (очередь) готовых к выполнению задач. Различают два больших класса таких дисциплин – бесприоритетные и приоритетные. При реализации приоритетных дисциплин отдельным задачам предоставляется преимущественное право попасть в состояние исполнения.
Рассмотрим кратко некоторые наиболее часто используемые дисциплины диспетчеризации.
Самой простой в реализации является дисциплина FCFS (first come – first served), согласно которой задачи обслуживаются в порядке очереди, т.е. в порядке их появления. Те задачи, которые были заблокированы в процессе работы, после перехода в состояние готовности ставятся в эту очередь перед теми задачами, которые еще не выполнялись, т.е. образуется две очереди – одна из новых задач, а вторая очередь – из ранее выполнявшихся, но попавших в состояние ожидания. Такой подход позволяет реализовать стратегию обслуживания «по возможности заканчивать вычислительные процессы в порядке их появления».
Рис.1. Дисциплина FCFS
К достоинствам этой дисциплины можно отнести простоту реализации и малые расходы системных ресурсов на формирование очереди задач.
Но она приводит к тому, что при увеличении загрузки вычислительной системы растет и среднее время ожидания обслуживания, причем короткие задания вынуждены ожидать столько же, сколько и трудоемкие задания. Избежать этого недостатка позволяют дисциплины SJN и SRT.
Дисциплина обслуживания SJN (shortest job next – следующим будет выполняться кратчайшее задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Для этого были разработаны специальные языковые средства, например, язык JCL (job control language – язык управления заданиями). Пользователи должны были указывать предполагаемое время выполнения, а чтобы они не ловчили, ввели подсчет реальных потребностей. Если обнаруживался обман, то задание ставилось в конец очереди или оплата шла по более высоким тарифам.
Дисциплина обслуживания SJN предполагает, что имеется только одна очередь заданий, готовых к выполнению. И задания, которые в процессе своего выполнения были временно заблокированы, вновь попадают в конец очереди. Это приводит к тому, что задания, которым требуется очень немного времени для завершения, ожидают процессор наравне с длительными работами.
Для устранения этого недостатка была предложена дисциплина SRT (shortest remaining time) – следующее задание требует меньше всего времени для своего завершения.
Все эти три дисциплины могут использоваться для пакетных режимов обработки, когда пользователь сдает свое задание, не ожидает реакции системы, а ему нужен только результат вычислений. Для интерактивных вычислений желательно обеспечить приемлемое время реакции системы и равенство в обслуживании, если система является мультитерминальной. Для однопользовательских систем с возможностью мультипрограммной обработки желательно, чтобы программы, с которыми работают непосредственно, имели лучшее время реакции, чем фоновые задания. Для решения подобных проблем используется дисциплина обслуживания RR(round robin – круговая, карусельная) и приоритетные методы обслуживания.
Дисциплина RR предполагает, что каждая задача получает процессорное время порциями (квантами времени q). После окончания кванта времени q задача снимается с процессора, и он передается следующей задаче. Снятая задача ставится в конец очереди задач, готовых к исполнению. Для оптимальной работы системы необходимо правильно выбрать закон, по которому кванты времени выделяются задачам.
Величина кванта времени q выбирается как компромисс между приемлемым временем реакции системы на запросы пользователей и накладными расходами на частую смену контекста задачи (надо запоминать много информации для прерываний).
Дисциплина RR – это одна из самых распространенных дисциплин диспетчеризации. В своей простейшей реализации на предполагает, что все задачи имеют одинаковый приоритет. Для введения приоритетного обслуживания вводят несколько очередей. Процессорное время будет предоставляться в первую очередь тем задачам, которые стоят в самой привилегированной очереди. Если она пустая, то диспетчер задач начнет просматривать остальные очереди. По такому алгоритму действует диспетчер задач в Windows NT.
Рис.2. Дисциплина RR
Диспетчеризация без перераспределения процессорного времени, т.е. не вытесняющая многозадачность – это такой способ диспетчеризации процессов, при котором активный процесс выполняется до тех пор, пока он сам не отдаст управление диспетчеру задач. Дисциплины FCFS, SJN, SRT относятся к не вытесняющим.
Диспетчеризация с перераспределением процессорного времени между задачами, т.е. вытесняющая многозадачность – это такой способ, при котором решение о переключении с одного процесса на другой принимается диспетчером задач, а не самой активной задачей. Дисциплина RR относится к вытесняющим.
Для сравнения алгоритмов диспетчеризации обычно используют следующие критерии:
a) использование (загрузка) CPU – центрального процессора;
b) пропускная способность CPU – количество процессов, выполняющихся в
c) время оборота – интервал от момента появления процесса во входной
очереди до момента его завершения;
d) время ожидания – суммарное время нахождения в очереди готовых
e) время отклика – время, прошедшее от момента попадания во входнуюъ
очередь до момента первого обращения к терминалу. Является важным для
Правильное планирование сильно влияет на производительность всей системы.
Источник
