Дисциплины диспетчеризации

Известно большое количество дисциплин диспетчеризации, то есть правил форми­рования очереди готовых к выполнению задач, в соответствии с которыми форми­руется эта очередь (список). Иногда их называют дисциплинами обслуживания, опуская тот факт, что речь идет о распределении процессорного времени. Одни дисциплины диспетчеризации дают наилучшие результаты для одной стратегии обслуживания, в то время как для другой стратегии они могут быть вовсе непри­емлемыми. Известно большое количество дисциплин диспетчеризации. Мы же, несмотря на статус этой книги, рассмотрим далеко не все, а только те, которые признаны наиболее эффективными и до сих пор имеют применение.

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

В концепции приоритетов имеем следующие варианты:

- приоритет, присвоенный задаче, является величиной постоянной;

- приоритет изменяется в течение времени решения задачи {динамический прио­ритет).

56__________________________________________ Глава 2, Управление задачами

Рис. 2.1. Дисциплины диспетчеризации

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

Рассмотрим некоторые основные (наиболее часто используемые) дисциплины диспетчеризации.

Самой простой в реализации является дисциплина FCFS (First Come First Served — первым пришел, первым обслужен), согласно которой задачи обслуживаются «в по­рядке очереди», то есть в порядке их появления. Те задачи, которые были заблоки-

Планирование и диспетчеризация процессов и задач__________________________ 57

рованы в процессе работы (попали в какое-либо из состояний ожидания, напри­мер из-за операций ввода-вывода), после перехода в состояние готовности вновь ставятся в эту очередь готовности. При этом возможны два варианта. Первый (са­мый простой) — это ставить разблокированную задачу в конец очереди готовых к выполнению задач. Этот вариант применяется чаще всего. Второй вариант за­ключается в том, что диспетчер помещает разблокированную задачу перед теми задачами, которые еще не выполнялись. Другими словами, в этом случае образу­ется две очереди (рис. 2.2): одна очередь образуется из новых задач, а вторая оче­редь — из ранее выполнявшихся, но попавших в состояние ожидания. Такой под­ход позволяет реализовать стратегию обслуживания «по возможности заканчивать вычисления в порядке их появления». Эта дисциплина обслуживания не требует внешнего вмешательства в ход вычислений, при ней не происходит перераспреде­ления процессорного времени. Про нее можно сказать, что она относится к не вы­тесняющим дисциплинам¹.

Очередь новых задач Рис. 2.2. Дисциплина диспетчеризации FCFS

К достоинствам этой дисциплины прежде всего можно отнести простоту реализа­ции и малые расходы системных ресурсов на формирование очереди задач.

Однако эта дисциплина приводит к тому, что при увеличении загрузки вычисли­тельной системы растет и среднее время ожидания обслуживания, причем короткие задания (требующие небольших затрат машинного времени) вынуждены ожидать

¹ Существующие дисциплины диспетчеризации процессов могут быть разбиты на два класса: вытес­няющие (preemptive) и не вытесняющие (non-preemptive). В первых пакетных операционных систе­мах часто реализовывали параллельное выполнение заданий без принудительного перераспределе­ния процессора между задачами. В большинстве современных ОС для мощных вычислительных систем, а также в ОС для персональных компьютеров, ориентированных на высокопроизводитель­ное выполнение приложений (Windows 9x/NT/2000/XP, Linux, OS/2), реализованы вытесняющие дисциплины диспетчеризации (вытесняющая многозадачность).

58__________________________________________ Глава 2. Управление задачами

столько же, сколько трудоемкие задания. Избежать этого недостатка позволяют дис­циплины SJN и SRT. Правило FCFS применяется и в более сложных дисциплинах диспетчеризации. Например, в приоритетных дисциплинах диспетчеризации, если имеется несколько задач с одинаковым приоритетом, которые стоят в очереди гото­вых к выполнению задач, то попадают они в эту очередь с учетом времени.

Дисциплина обслуживания SJN( Shortest Job Next — следующим выполняется са­мое короткое задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Необходимость сообщать операционной сис­теме характеристики задач с описанием потребностей в ресурсах вычислительной системы привела к тому, что были разработаны соответствующие языковые сред­ства. В частности, ныне уже забытый язык]СL (Job Control Language — язык уп­равления заданиями) был одним из наиболее известных. Пользователи вынужде­ны были указывать предполагаемое время выполнения задачи и для того, чтобы они не злоупотребляли возможностью указать заведомо меньшее время выполне­ния (с целью возможности получить результаты раньше других), ввели подсчет реальных потребностей. Диспетчер задач сравнивал заказанное время и время вы­полнения и в случае превышения указанной оценки потребности в данном ресур­се ставил данное задание не в начало, а в конец очереди. Еще в некоторых операци­онных системах в таких случаях использовалась система штрафов, при которой в случае превышения заказанного машинного времени оплата вычислительных ре­сурсов осуществлялась уже по другим расценкам.

Дисциплина обслуживания SJN предполагает, что имеется только одна очередь заданий, готовых к выполнению. Задания, которые в процессе своего исполнения были временно заблокированы (например, ожидали завершения операций ввода-вывода), вновь попадали в конец очереди готовых к выполнению наравне с вновь поступающими. Это приводило к тому, что задания, которым требовалось очень немного времени для своего завершения, вынуждены были ожидать процессор наравне с длительными работами, что не всегда хорошо.

Для устранения этого недостатка и была предложена дисциплина SRT (Shortest Remaining Time) — следующим будет выполняться задание, которому осталось меньше всего выполняться на процессоре.

Все эти три дисциплины обслуживания могут использоваться для пакетных ре­жимов обработки, когда пользователю не нужно ждать реакции системы — он про­сто сдает свое задание и через несколько часов получает результаты вычислений. Для интерактивных же вычислений желательно прежде всего обеспечить прием­лемое время реакции системы. Если же система является мультитерминальной, то помимо малого времени реакции системы на запрос пользователя желательно, чтобы она обеспечивала и равенство в обслуживании. Можно сказать, что страте­гия обслуживания, согласно которой главным является равенство обслуживания при приемлемом времени обслуживания, является главной для систем разделе­ния времени. Кстати, UNIX-системы реализуют дисциплины обслуживания, со­ответствующие именно этой стратегии.

Если же это однопользовательская система, но с возможностью мультипрограмм-. ной обработки, то желательно, чтобы те программы, с которыми непосредственно

Планирование и диспетчеризация процессов и задач__________________________ 59

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

Для решения перечисленных проблем используется дисциплина обслуживания, называемая карусельной (Round Robin, RR), и приоритетные методы обслужи­вания.

Дисциплина обслуживания RR предполагает, что каждая задача получает процес­сорное время порциями или, как говорят, квантами времени (time slice) q. После окончания кванта времени q задача снимается с процессора, и он передается сле­дующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполне­нию. Эту дисциплину обслуживания иллюстрирует рис. 2.3. Для оптимальной ра­боты системы необходимо правильно выбрать закон, по которому кванты времени выделяются задачам.

Рис. 2.3. Карусельная дисциплина диспетчеризации

Величина кванта времени q выбирается как компромисс между приемлемым време­нем реакции системы на запросы пользователей (с тем, чтобы их простейшие запро­сы не вызывали длительного ожидания) и накладными расходами на частую смену контекста задач. Очевидно, что при прерываниях операционная система вынуждена выполнять большой объем работы, связанной со сменой контекста. Она должна со­хранить достаточно большой объем информации о текущем (прерываемом) процес­се, поставить дескриптор снятой задачи в очередь, занести в рабочие регистры про­цессора соответствующие значения для той задачи, которая теперь будет выполняться (ее дескриптор расположен первым в очереди готовых к исполнению задач). Если величина q велика, то при увеличении очереди готовых к выполнению задач реак­ция системы станет медленной. Если же величина q мала, то относительная доля

60__________________________________________ Глава 2. Управление задачами

накладных расходов на переключения контекста между исполняющимися задачами увеличится, и это ухудшит производительность системы.

В некоторых операционных системах есть возможность указывать в явном виде величину кванта времени или диапазон возможных значений, тогда система будет стараться выбирать оптимальное значение сама. Например, в операционной сис­теме OS/2 в файле CONFIG.SYS есть возможность с помощью оператора TIMESLICE указать минимальное и максимальное значения для кванта q. Так, например, стро­ка TIMESLICE=32,256 указывает, что минимальное значение равно 32 мс, а макси­мальное — 256. Если некоторая задача прервана, поскольку израсходован выде­ленный ей квант времени q, то следующий выделенный ей интервал будет увеличен на время, равное одному периоду таймера (около 32 мс), и так до тех пор, пока квант времени не станет равным максимальному значению, указанному в операто­ре TIMESLICE. Этот метод позволяет OS/2 уменьшить накладные расходы на пе­реключение задач в том случае, если несколько задач параллельно выполняют длительные вычисления. Следует заметить, что диспетчеризация задач в этой опе­рационной системе реализована, пожалуй, наилучшим образом с точки зрения ре­акции системы и эффективности использования процессорного времени.

Дисциплина карусельной диспетчеризации более всего подходит для случая, когда все задачи имеют одинаковые права на использование ресурсов центрального про­цессора. Однако как мы знаем, равенства в жизни гораздо меньше, чем неравенства. Одни задачи всегда нужно решать в первую очередь, тогда как остальные могут по­дождать. Это можно реализовать за счет того, что одной задаче мы (или диспетчер задач) присваиваем один приоритет, а другой задаче — другой. Задачи в очереди будут располагаться в соответствии с их приоритетами. Формирует очередь диспетчер за­дач. Процессор в первую очередь будет предоставляться задаче с самым высоким приоритетом, и только если ее потребности в процессоре удовлетворены или она попала в состояние ожидания некоторого события, диспетчер может предоставить его следующей задаче. Многие дисциплины диспетчеризации по-разному исполь­зуют основную идею карусельной диспетчеризации и механизм приоритетов.

Дисциплина диспетчеризации RR — это одна из самых распространенных дисцип­лин. Однако бывают ситуации, когда операционная система не поддерживает в яв­ном виде дисциплину карусельной диспетчеризации. Например, в некоторых опе­рационных системах реального времени используется диспетчер задач, работающий по принципу абсолютных приоритетов (процессор предоставляется задаче с мак­симальным приоритетом, а при равенстве приоритетов он действует по принципу очередности) [7, 11]. Другими словами, причиной снятия задачи с выполнения может быть только появление задачи с более высоким приоритетом. Поэтому если нужно организовать обслуживание задач таким образом, чтобы все они получали процессорное время равномерно и равноправно, то системный оператор может сам организовать эту дисциплину. Для этого достаточно всем пользовательским зада­чам присвоить одинаковые приоритеты и создать одну высокоприоритетную зада­чу, которая не должна ничего делать, но которая, тем не менее, будет по таймеру (через указанные интервалы времени) планироваться на выполнение. Благодаря высокому приоритету этой задачи текущее приложение будет сниматься с выпол­нения и ставиться в конец очереди, а поскольку этой высокоприоритетной задаче

Планирование и диспетчеризация процессов и задач__________________________ 61

на самом деле ничего делать не надо, то она тут же освободит процессор, и из оче­реди готовности будет взята следующая задача.

В своей простейшей реализации дисциплина карусельной диспетчеризации пред­полагает, что все задачи имеют одинаковый приоритет. Если же необходимо ввес­ти механизм приоритетного обслуживания, то это, как правило, делается за счет организации нескольких очередей. Процессорное время предоставляется в первую очередь тем задачам, которые стоят в самой привилегированной очереди. Если она пустая, то диспетчер задач начинает просматривать остальные очереди. Именно по такому алгоритму действует диспетчер задач в операционных системах OS/2, Windows 9x, Windows NT/2000/XP и многих других. Отличия в основном заклю­чаются в количестве очередей и в правилах, касающихся перемещения задач из одной очереди в другую.

Известные дисциплины диспетчеризации (мы здесь рассмотрели только основ­ные) могут применять или не применять еще одно правило, касающееся перерас­пределения процессора между выполняющимися задачами.

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

А есть дисциплины диспетчеризации, в которых ничто не может отобрать у задачи процессор, пока она сама его не освободит. Освобождение процессора в этом слу­чае, как правило, связано с тем, что задача попадает в состояние ожидания некото­рого события.

Итак, диспетчеризация без перераспределения процессорного времени, то есть не вытесняющая (non-preemptive multitasking), или кооперативная, многозадачность (cooperative multitasking), — это такой способ диспетчеризации задач, при кото­ром активная задача выполняется до тех пор, пока она сама, что называется «по собственной инициативе», не отдаст управление диспетчеру задач для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс или поток. Дисцип­лины обслуживания FCFS, SJN, SRT относятся к не вытесняющим.

Диспетчеризация с перераспределением процессорного времени между задачами, то есть вытесняющая многозадачность (preemptive multitasking), — это такой спо­соб, при котором решение о переключении процессора с выполнения одной задачи на выполнение другой принимается диспетчером задач, а не самой активной зада­чей. При вытесняющей многозадачности механизм диспетчеризации задач цели­ком сосредоточен в операционной системе, и программист может писать свое при­ложение, не заботясь о том, как оно будет выполняться параллельно с другими задачами (процессами и потоками). При этом операционная система выполняет следующие функции: определяет момент снятия с выполнения текущей задачи, сохраняет ее контекст в дескрипторе задачи, выбирает из очереди готовых задач следующую и запускает ее на выполнение, загружая ее контекст. Дисциплина RR и многие другие, построенные на ее основе, относятся к вытесняющим.

62 Глава 2. Управление задачами

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

Для пользователей это означает, что управление системой может теряться на не­который произвольный период времени, который определяется процессом выпол­нения приложения (а не системой, старающейся всегда обеспечить приемлемое время реакции на запросы пользователей) [27]. Если приложение тратит слишком много времени на выполнение какой-либо работы (например, на форматирование диска), пользователь не может переключиться с этой на другую задачу (например, на текстовый или графический редактор, в то время как форматирование продол­жалось бы в фоновом режиме). Эта ситуация нежелательна, так как пользователи обычно не хотят долго ждать, когда машина завершит свою задачу.

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

Например, в ныне уже забытой операционной среде Windows 3.x нативные 16-раз­рядные приложения этой системы разделяли между собой процессорное время именно таким образом. И именно программисты должны были обеспечивать «дру­жественное» отношение своей программы к другим выполняемым одновременно с ней программам, достаточно часто отдавая управление ядру системы. Крайним проявлением «недружественности» приложения является его зависание, приво­дящее к общему краху системы — прекращению всех вычислений. В системах с вы­тесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный механизм диспетчеризации, во-первых, обеспечивает все задачи про­цессорным временем, во-вторых, дает возможность иметь надежные механизмы мониторинга вычислений и, в-третьих, позволяет снять зависшую задачу с выпол­нения.

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

Качество диспетчеризации и гарантии обслуживания__________________________ 63

данного фиксированного набора задач образом [27, 44, 46]. Так как разработчик сам определяет в программе момент времени передачи управления, то при этом исключаются нерациональные прерывания программ в «неудобные» для них мо­менты времени. Кроме того, легко разрешаются проблемы совместного использо­вания данных: задача во время каждой итерации использует их монопольно и уве­рена, что на протяжении этого периода никто другой их не изменит. Примером эффективного применения не вытесняющей многозадачности является сетевая операционная система Novell NetWare, в которой в значительной степени благо­даря этому достигнута высокая скорость выполнения файловых операций. Менее удачным оказалось использование не вытесняющей многозадачности в операци­онной среде Windows 3.x. К счастью, на сегодня эта операционная система уже нигде не применяется, ее с успехом заменила сначала Windows 95, а затем и Win­dows 98. Правда, следует заметить, что при выполнении в этих операционных систе­мах старых 16-разрядных приложений, разработанных в свое время для операци­онной среды Win 16 API, создается виртуальная машина, работающая по принципам не вытесняющей многозадачности.