Файл: А. В. Гордеев А. Ю. Молчанов системное программное обеспечение электронный вариант книги издательства Питер СанктПетербург Челябинск юургу каф. Автоматика и управление 2002 2 Предисловие Настоящий учебник.pdf

56
некотором заранее установленном порядке без учета их относительной важности и времени обслуживания. При реализации приоритетных дисциплин обслуживания отдельным задачам предоставляется преимущественное право попасть в состояние исполнения. Перечень дисциплин обслуживания и их классификация приведены на рис. 2.1.
Дисциплины диспетчеризации
Бесприори-
Приоритетные

57
Запомним о приоритетах следующее:
♦ приоритет, присвоенный задаче, может являться величиной постоянной;
♦ приоритет задачи может изменяться в процессе её решения.
Диспетчеризация с динамическими приоритетами требует дополнительных расходов на вычисление значений приоритетов исполняющихся задач, поэтому во многих ОС реального времени используются методы диспетчеризации на основе статических (постоянных) приоритетов. Хотя надо заметить, что динамические приоритеты позволяют реализовать гарантии обслуживания задач.
Рассмотрим кратко некоторые основные (наиболее часто используемые) дис- циплины диспетчеризации.
Самой простой в реализации является дисциплина FCFS (first come – first served), согласно которой задачи обслуживаются «в порядке очерёди», то есть в порядке их появления. Те задачи, которые были заблокированы в процессе работы
(попали в какое-либо из состояний ожидания, например, из-за операций вво- да/вывода), после перехода в состояние готовности ставятся в эту очередь готовно- сти перед теми задачами, которые ещё не выполнялись. Другими словами, образу- ются две очерёди (рис. 2.2): одна очередь образуется из новых задач, а вторая оче- редь – из ранее выполнявшихся, но попавших в состояние ожидание. Такой подход позволяет реализовать стратегию обслуживания «по возможности заканчивать вы- числения в порядке их появления». Эта дисциплина обслуживания не требует внешнего вмешательства в ход вычислений, при ней не происходит перераспреде- ление процессорного времени. Существующие дисциплины диспетчеризации про- цессов могут быть разбиты на два класса – вытесняющие (preemptive) и не вытес- няющие (non-preemptive). В первых пакетных ОС часто реализовывали параллель- ное выполнение заданий без принудительного перераспределения процессора меж- ду задачами. В большинстве современных ОС для мощных вычислительных сис- тем, а также и в ОС для ПК, ориентированных на высокопроизводительное выпол- нение приложений (Windows NT, OS/2, Unix), реализована вытесняющая многоза- дачность. Можно сказать, что рассмотренная дисциплина относится к не вытес- няющим.

58
Рис. 2.2. Дисциплина диспетчеризации FCFS
К достоинствам этой дисциплины, прежде всего, можно отнести простоту реа- лизации и малые расходы системных ресурсов на формирование очерёди задач.
Однако эта дисциплина приводит к тому, что при увеличении загрузки вычис- лительной системы растет и среднее время ожидания обслуживания, причем ко- роткие задания (требующие небольших затрат машинного времени) вынуждены ожидать столько же, сколько и трудоёмкие задания. Избежать этого недостатка по- зволяют дисциплины SJN и SRT.
Дисциплина обслуживания SJN (shortest job next, что означает: следующим бу- дет выполняться кратчайшее задание) требует, чтобы для каждого задания была из- вестна оценка в потребностях машинного времени. Необходимость сообщать ОС
характеристики задач, в которых описывались бы потребности в ресурсах вычис- лительной системы, привела к тому, что были разработаны соответствующие язы- ковые средства. В частности, язык JCL (job control language, язык управления зада- ниями) был одним из наиболее известных. Пользователи вынуждены были указы- вать предполагаемое время выполнения, и для того, чтобы они не злоупотребляли возможностью указать заведомо меньшее время выполнения (с целью получить ре- зультаты раньше других), ввели подсчет реальных потребностей. Диспетчер задач сравнивал заказанное время и время выполнения и в случае превышения указанной
Процессор
Блокирование
Выполненные задачи
Очередь задач, вновь готовых к исполнению
Очередь новых задач

59
оценки в данном ресурсе ставил данное задание не в начало, а в конец очерёди. ещё
в некоторых ОС в таких случаях использовалась система штрафов, при которой в случае превышения заказанного машинного времени оплата вычислительных ре- сурсов осуществлялась уже по другим расценкам.
Дисциплина обслуживания SJN предполагает, что имеется только одна оче- редь заданий, готовых к выполнению. И задания, которые в процессе своего ис- полнения были временно заблокированы (например, ожидали завершения опера- ций ввода/вывода), вновь попадают в конец очерёди готовых к выполнению нарав- не с вновь поступающими. Это приводит к тому, что задания, которым требуется очень немного времени для своего завершения, вынуждены ожидать процессор на- равне с длительными работами, что не всегда хорошо.
Для устранения этого недостатка и была предложена дисциплина SRT (shortest remaining time, следующее задание требует меньше всего времени для своего за- вершения).
Все эти три дисциплины обслуживания могут использоваться для пакетных режимов обработки, когда пользователь не вынужден ожидать реакции системы, а просто сдает свое задание и через несколько часов получает свои результаты вы- числений. Для интерактивных же вычислений желательно прежде всего обеспечить приемлемое время реакции системы и равенство в обслуживании, если система яв- ляется мультитерминальной. Если же это однопользовательская система, но с воз- можностью мультипрограммной обработки, то желательно, чтобы те программы, с которыми мы сейчас непосредственно работаем, имели лучшее время реакции, не- жели наши фоновые задания. При этом мы можем пожелать, чтобы некоторые приложения, выполняясь без нашего непосредственного участия (например, про- грамма получения электронной почты, использующая модем и коммутируемые ли- нии для передачи данных), тем не менее, гарантированно получали необходимую им долю процессорного времени. Для решения подобных проблем используется дисциплина обслуживания, называемая RR (round robin, круговая, карусельная), и приоритетные методы обслуживания.

60
Дисциплина обслуживания RR предполагает, что каждая задача получает про- цессорное время порциями (говорят: квантами времени
1
, q). После окончания кванта времени q задача снимается с процессора и он передаётся следующей зада- че. Снятая задача ставится в конец очерёди задач, готовых к выполнению. Эта дис- циплина обслуживания иллюстрируется рис. 2.3. Для оптимальной работы системы необходимо правильно выбрать закон, по которому кванты времени выделяются задачам.
Рис. 2.3. Карусельная дисциплина диспетчеризации (round robin)
Величина кванта времени q выбирается как компромисс между приемлемым временем реакции системы на запросы пользователей (с тем, чтобы их простейшие запросы не вызывали длительного ожидания) и накладными расходами на частую смену контекста задач. Очевидно, что при прерываниях ОС вынуждена сохранить достаточно большой объём информации о текущем (прерываемом) процессе, по- ставить дескриптор снятой задачи в очередь, загрузить контекст задачи, которая теперь будет выполняться (её дескриптор был первым в очерёди готовых к испол- нению). Если величина q велика, то при увеличении очерёди готовых к выполне- нию задач реакция системы станет плохой. Если же величина мала, то относитель- ная доля накладных расходов на переключения между исполняющимися задачами станет большой и это ухудшит производительность системы. В некоторых ОС есть возможность указывать в явном виде величину q либо диапазон её возможных зна- чений, поскольку система будет стараться выбирать оптимальное значение сама.
1
Time slice – квант времени.
Процессор
Выполненные задачи
Очередь готовых к исполнению задач
Новые задачи

61
Например, в OS/2 в файле CONFIG.SYS есть возможность с помощью опера- тора TIMESLICE указать минимальное и максимальное значение для кванта q. Так,
например, строка TIMESLICE=32,256 указывает, что минимальное значение q рав- но 32 миллисекундам, а максимальное – 256. Если некоторая задача (тред) была прервана, поскольку выделенный ей квант времени q израсходован, то следующий выделенный ему интервал будет увеличен на время, равное одному периоду тай- мера (около 32 мс), и так до тех пор, пока квант времени не станет равным мак- симальному значению, указанному в операторе TIMESLICE. Этот метод позволяет
OS/2 уменьшить накладные расходы на переключение задач в том случае, если не- сколько задач параллельно выполняют длительные вычисления.
Дисциплина диспетчеризации RR – это одна из самых распространенных дис- циплин. Однако бывают ситуации, когда ОС не поддерживает в явном виде дис- циплину карусельной диспетчеризации. Например, в некоторых ОС реального вре- мени используется диспетчер задач, работающий по принципам абсолютных при- оритетов (процессор предоставляется задаче с максимальным приоритетом, а при равенстве приоритетов он действует по принципу очерёдности) [21]. Другими сло- вами, снять задачу с выполнения может только появление задачи с более высоким приоритетом. Поэтому если нужно организовать обслуживание задач таким обра- зом, чтобы все они получали процессорное время равномерно и равноправно, то системный оператор может сам организовать эту дисциплину. Для этого достаточ- но всем пользовательским задачам присвоить одинаковые приоритеты и создать одну высокоприоритетную задачу, которая не должна ничего делать, но которая,
тем не менее, будет по таймеру (через указанные интервалы времени) планиро- ваться на выполнение. Эта задача снимет с выполнения текущее приложение, оно будет поставлено в конец очерёди, и поскольку этой высокоприоритетной задаче на самом деле ничего делать не надо, то она тут же освободит процессор и из оче- рёди готовности будет взята следующая задача.
В своей простейшей реализации дисциплина карусельной диспетчеризации предполагает, что все задачи имеют одинаковый приоритет. Если же необходимо ввести механизм приоритетного обслуживания, то это, как правило, делается за

62
счёт организации нескольких очерёдей. Процессорное время будет предоставлять- ся в первую очередь тем задачам, которые стоят в самой привилегированной оче- рёди. Если она пустая, то диспетчер задач начнет просматривать остальные очерё- ди. Именно по такому алгоритму действует диспетчер задач в операционных систе- мах OS/2 и Windows NT.
Вытесняющие и не вытесняющие алгоритмы диспетчеризации
Диспетчеризация без перераспределения процессорного времени, то есть не
вытесняющая многозадачность (non-preemptive multitasking) – это такой способ диспетчеризации процессов, при котором активный процесс выполняется до тех пор, пока он сам, что называется «по собственной инициативе», не отдаст управ- ление диспетчеру задач для выбора из очерёди другого, готового к выполнению процесса или треда. Дисциплины обслуживания FCFS, SJN, SRT относятся к не вытесняющим.
Диспетчеризация с перераспределением процессорного времени между зада- чами, то есть вытесняющая многозадачность (preemptive multitasking) – это такой способ, при котором решение о переключении процессора с выполнения одного процесса на выполнение другого процесса принимается диспетчером задач, а не самой активной задачей. При вытесняющей многозадачности механизм диспет- черизации задач целиком сосредоточен в операционной системе, и программист может писать свое приложение, не заботясь о том, как оно будет выполняться па- раллельно с другими задачами. При этом операционная система выполняет сле- дующие функции: определяет момент снятия с выполнения текущей задачи, сохра- няет её контекст в дескрипторе задачи, выбирает из очерёди готовых задач сле- дующую и запускает её на выполнение, предварительно загрузив её контекст. Дис- циплина RR и многие другие, построенные на её основе, относятся к вытес- няющим.
При не вытесняющей многозадачности механизм распределения процессорно- го времени распределен между системой и прикладными программами. Приклад- ная программа, получив управление от операционной системы, сама определяет момент завершения своей очередной итерации и передаёт управление супервизору

63
ОС с помощью соответствующего системного вызова. При этом естественно, что диспетчер задач, так же как и в случае вытесняющей мультизадачности, формирует очерёди задач и выбирает в соответствии с некоторым алгоритмом (например, с учётом порядка поступления задач или их приоритетов) следующую задачу на вы- полнение. Такой механизм создает некоторые проблемы, как для пользователей,
так и для разработчиков.
Для пользователей это означает, что управление системой может теряться на некоторый произвольный период времени, который определяется процессом вы- полнения приложения (а не системой, старающейся всегда обеспечить приемлемое время реакции на запросы пользователей) [54]. Если приложение тратит слишком много времени на выполнение какой-либо работы (например, на форматирование диска), пользователь не может переключиться с этой задачи на другую задачу (на- пример, на текстовый или графический редактор, в то время как форматирование продолжалось бы в фоновом режиме). Эта ситуация нежелательна, так как пользо- ватели обычно не хотят долго ждать, когда машина завершит свою задачу.
Поэтому разработчики приложений для не вытесняющей операционной среды,
возлагая на себя функции диспетчера задач, должны создавать приложения так,
чтобы они выполняли свои задачи небольшими частями. Так, упомянутая выше программа форматирования может отформатировать одну дорожку дискеты и вер- нуть управление системе. После выполнения других задач система возвратит управление программе форматирования, чтобы та отформатировала следующую дорожку. Подобный метод разделения времени между задачами работает, но он существенно затрудняет разработку программ и предъявляет повышенные тре- бования к квалификации программиста.
Например, в ныне уже забытой операционной среде Windows 3.х нативные приложения этой системы разделяли между собой процессорное время именно та- ким образом. И программисты сами должны были обеспечивать «дружественное»
отношение своей программы к другим выполняемым одновременно с ней про- граммам, достаточно часто отдавая управление ядру системы. Крайним про- явлением «не дружественности» приложения является его зависание, которое при-

64
водит к общему краху системы. В системах с вытесняющей многозадачностью та- кие ситуации, как правило, исключены, так как центральный механизм диспетче- ризации, во–первых, обеспечивает все задачи процессорным временем, а во–вто- рых, дает возможность иметь надёжные механизмы для мониторинга вычислений и позволяет снять зависшую задачу с выполнения.
Однако распределение функций диспетчеризации между системой и прило- жениями не всегда является недостатком, а при определенных условиях может быть и преимуществом, потому что дает возможность разработчику приложений самому проектировать алгоритм распределения процессорного времени, наиболее подходящий для данного фиксированного набора задач [54]. Так как разработчик сам определяет в программе момент времени отдачи управления, то при этом ис- ключаются нерациональные прерывания программ в «неудобные» для них момен- ты времени. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждой итерации использует их монопольно и уверена,
что на протяжении этого периода никто другой не изменит эти данные. Примером эффективного использования не вытесняющей многозадачности является сетевая операционная система Novell NetWare, в которой в значительной степени благода- ря этому достигнута высокая скорость выполнения файловых операций. Менее удачным оказалось использование не вытесняющей многозадачности в операцион- ной среде Windows 3.х.
Качество диспетчеризации и гарантии обслуживания
Одна из проблем, которая возникает при выборе подходящей дисциплины об- служивания, – это гарантия обслуживания. Дело в том, что при некоторых дис- циплинах, например при использовании дисциплины абсолютных приоритетов,
низкоприоритетные процессы оказываются обделенными многими ресурсами и,
прежде всего, процессорным временем. Возникает реальная дискриминация низ- коприоритетных задач, и ряд таких процессов, имеющих к тому же большие по- требности в ресурсах, могут очень длительное время откладываться или, в конце концов, вообще могут быть не выполнены. Известны случаи, когда вследствие вы- сокой загрузки вычислительной системы отдельные процессы так и не были вы-