Планирование вычислительных процессов и стратегии планирования (обслуживания).

Стратегия планирования определяет, какие процессы мы планируем на выполнение, для того чтобы достичь поставленной цели. Известно большое количество различных стратегий выбора процесса, которому необходимо представить процессор. Среди них: по возможности заканчивать вычисления в том же самом порядке, в каком они были начаты; отдавать предпочтение более коротким вычислительным задачам; предоставлять всем пользователям одинаковые услуги, в том числе и время ожидания.

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

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

1. бесприоритетные. При бесприоритетном обслуживании выбор задач происходит в заранее установленном порядке без учета важности и времени обслуживания. Бывают линейные и циклические. Линейные бывают: в порядке очереди и случайного выбора процесса. Циклические делятся на: циклический алгоритм и многоприоритетный циклический алгоритм (относится к приоритетным дисциплинам с фиксированным приоритетом).

2. приоритетные. При реализации приоритетного обслуживания отдельным задачам предоставляется преимущественное право попасть в очередь выполнения. Бывают: с фиксированным и динамическим приоритетом. К фиксированным относят: с относительным и абсолютным приоритетом, с адаптивным обслуживанием (одновременно относится к динамическому приоритету). К динамическому приоритету относятся: дисциплины, у которых приоритет зависит от времени ожидания; дисциплины, у которых приоритет зависит от времени обслуживания.

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

Дисциплины:

· First Come First Served (FCFS) – согласно которой задачи обслуживаются в порядке очереди. Те задачи, которые были заблокированы в процессе работы, после перехода в состояние готовности вновь ставятся в очередь готовности. При этом возможны 2 варианта: ставить разблокированную задачу в конец очереди готовых к выполнению задач, этот вариант применяется чаще всего; диспетчер задач помещает разблокированную задачу перед теми, которые ещё не выполнялись, в этом случае образуется 2 очереди: очередь новых задач и ранее выполнявшихся, но попавших в состояние ожидания. Такой подход позволяет реализовать концепцию обслуживания «по возможности заканчивать вычисления в порядке их появления». Эта дисциплина не требует внешнего вмешательства в ход вычислений, при ней не происходит перераспределения процессорного времени. Она не относится к вытесняющим дисциплинам. Основным достоинством является простота реализации и малые расходы системных ресурсов на формирование очереди задач, но дисциплина приводит к тому, что при увеличении загрузки ВС растет и среднее время обслуживания, причем короткие задания вынуждены ждать столько же, сколько и трудоемкие. Избежать этого недостатка позволяют дисциплины SJN, SRT. Правила FCFS применяются и в более сложных дисциплинах диспетчеризации, например, в приоритетных дисциплинах, если имеется несколько задач с одинаковым приоритетом, которые стоят в очереди готовых задач, то они попадают в эту очередь с учетом времени.

· SJN (Shortest Job Next) – следующей выполняется самая короткая задача. Дисциплина требует, чтобы для каждого задания была известна оценка в потребностях режимного времени. Необходимость сообщать ОС характеристики задач с описанием потребностей ресурсов вычислительной системы привела к тому, что были разработаны языковые средства – JCL. Пользователи вынуждены были указывать предполагаемое время выполнения задач. Чтобы они не злоупотребляли возможностью указывать заведомо меньшее время выполнения, ввели подсчет реальных потребностей. Диспетчер задач сравнивал заказанное время и время выполнения, и в случае превышения оценки потребности ставил данное задание не в начало, а в конец очереди. Еще в некоторых ОС использовалась система штрафов. Дисциплина обслуживания предполагает, что имеется только одна очередь заданий, готовых к выполнению, задания, которые в процессе выполнения были временно заблокированы, вновь попадали в конец очереди наравне с поступающими. Это приводило к тому, что задания, которым требовалось очень немного времени для завершения, были вынуждены ждать процессор наравне с длительными работами. Для устранения этого недостатка была предложена другая дисциплина.

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

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

Если же это однопользовательская система, но с возможностью мультипрограммной обработки, то желательно, чтобы те программы, с которыми непосредственно работает пользователь, имели лучшее время реакции, нежели фоновые задания, при этом желательно, чтобы приложение, выполняясь без пользователя, тем не менее, гарантированно получали необходимую долю процессорного времени. Для решения перечисленных проблем используется карусельная дисциплина (RR – Round Robin) и приоритетные методы обслуживания. Дисциплина RR предполагает, что каждая задача получает процессорное время порциями или квантами времени. После окончания кванта времени q задача снимается с процессора, и он передается следующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполнению. Для оптимальной работы системы необходимо правильно выбрать закон, по которому кванты времени выделяются задаче. Величина кванта q выбирается как компромисс между приемлемым временем реакции на запрос пользователя и накладными расходами на частую смену контекста задач. Если величина q велика, то при увеличении очереди реакция системы станет медленной. Если q мала, то относительная доля накладных расходов на переключение контекста между задачами увеличиться, и это ухудшит производительность системы. В некоторых Ос есть возможность указывать величину кванта времени или диапазон. Дисциплина карусельной диспетчеризации больше всего подходит для случая, когда все задачи имеют одинаковые права на использование ресурсов ЦП, однако зачастую одни задачи нужно решать в первую очередь, тогда как остальные могут подождать. Это можно реализовать присваиванием приоритетов. Задачи в очереди будут располагаться в соответствии с приоритетом. Формирует очередь Диспетчер задач. Многие дисциплины диспетчеризации используют основную идею карусельной и механизм приоритетов. Дисциплина RR одна из самых распространенных, но бывают ситуации, когда ОС не поддерживает в явном виде карусельную дисциплину, например, в некоторых ОС реального времени. В таких системах используется Диспетчер задач, основанный на абсолютных приоритетах. Другими словами, причиной снятия задачи с выполнения может быть только появление задачи с более высоким приоритетом.

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

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

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

1. определяет момент снятия с выполнения текущей задачи

2. сохраняет её контекст в дескрипторе задач

3. выбирает из очереди готовых задач следующую

4. запускает её на выполнение, загружая её контекст.

Дисциплина RR и многие другие, построенные на её основе, относятся к вытесняющим.