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

Когда говорят о диспетчеризации, то всегда в явном или неявном виде имеют в виду понятие задачи (потока). Если ОС не поддерживает механизм тредов, то можно заменять понятие задачи на понятие процесса. Так как эти термины часто используются именно в таком смысле, мы вынуждены будем использовать тер­мин «процесс» как синоним термина «задача».

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

Запомним о приоритетах следующее:

¨ приоритет, присвоенный задаче, может являться величиной постоянной;

¨ приоритет задачи может изменяться в процессе её решения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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