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

Задание № 1.

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

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

Состояние готовности это состояние, при котором у процесса имеются все необходимые ресурсы для выполнения на процессоре кроме самого процессора.

В состоянии выполнения (исполнения) происходит непосредственное выполнение команд, относящихся к данному процессу, т. е. процессу предоставляется процессор как основной ресурс системы.

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

- бездействие;

- готовность;

- выполнение;

- ожидание окончания вывода.

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

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

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

1. FCFS (first come – first served – первым пришёл - первым обслужился) – прежде процессор получает та задача, которая раньше перешла в состояние готовности. Данная дисциплина проста в реализации, равноправна по отношению, как к “длинным ”, так и к “коротким” процессам, а среднее время пребывания в очереди готовности весьма значительное.

2. SJN (shortest job next – следующий с кратчайшим заданием) – прежде процессор получает та задача, которая имеет минимальное заказное время обслуживания. Данная дисциплина требует, чтобы для каждой задачи была известна оценка потребности в машинном времени, значение которой задаётся как параметр задачи. Такая дисциплина более сложна в реализации по сравнению с FCFS, она дискриминационна по отношению к “длинным процессам”, среднее время пребывания в очереди готовности меньше чем для FCFS. SJN имеет существенный недостаток. Задачи, которые были временно заблокированы (например, ожидали завершения ввода/вывода), в результате попадут в конец очереди готовности, даже если для их выполнения требуется небольшое процессорное время.

3. SRT (shortest remaining time) – прежде процессор получает та задача, которая имеет меньше всего времени для своего завершения. Это время определяется как разность между заказанным временем обслуживания и тем процессорным временем, которая задача уже получила. SRT свободна от недостатка, характерного для SJN. SRT сложна в реализации и дискриминационна по отношению к “длинным” процессам.

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

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

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

6. Дисциплины на основе динамических приоритетов задач. Для каждой задачи задаётся начальное значение приоритета, которое затем изменяется во времени. Таким образом, приоритет задачи есть функция времени. Конкретный вид таких функций может быть разный, но общая их направленность состоит в том, что, чем дольше задача находится в очереди готовности, тем выше становится её приоритет. Это позволяет гарантировать обслуживание как коротких, так и длинных процессов.

Цель задания: написать и отладить программу, моделирующую работу диспетчера операционной системы.

Задаваемые исходные данные по каждому варианту:

- число параллельно выполняемых задач, данное значение должно задаваться произвольно, т. е. не быть константой;

- данные по каждой задаче:

момент активизации задачи (процесса), т. е. момент перехода задачи из состояния бездействия в состояние готовности.

время выполнения её на процессоре.

Особенности дополнительных исходных данных по различным вариантам:

Для вариантов 2 и 3 необходимо также задать по каждой задаче значение ожидаемого заказного времени обслуживания.

Для варианта 4 необходимо задать значение интервала мультиплексирования.

Для варианта 5 необходимо задавать абсолютные приоритеты задач по каждой задаче.

Для вариантов с 6-го по 12 необходимо задавать значения начальных приоритетов задач и соответствующих коэффициентов, имеющихся в формулах изменения приоритетов. Кроме того, для этих вариантов необходимо задать значение интервала пересчёта приоритетов задач, находящихся в очереди готовности.

Требования к программе.

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

Варианты заданий

1. Диспетчер на основе дисциплины FCFS.

2. Диспетчер на основе дисциплины SJN.

3. Диспетчер на основе дисциплины SRT.

4. Диспетчер на основе дисциплины RR. Дополнительно задаётся значение интервала мультиплексирования.

5. Диспетчер на основе дисциплины с абсолютными приоритетами задач. Для каждой задачи задаётся значение приоритета.

6. Диспетчер на основе дисциплины с динамическими приоритетами, изменяющимися по формуле Pri=Pr0i+ai*t., где Pr0i – начальное значение приоритета i-ой задачи, ai – задаваемый коэффициент i-ой задачи, i =1..n, n – число задач.

7. Диспетчер на основе дисциплины с динамическими приоритетами, изменяющимися по формуле Pri=Pr0i + ai*exp(t).

8. Диспетчер на основе дисциплины с динамическими приоритетами, изменяющимися по формуле Pri=Pr0i+ai*log(t).

9. Диспетчер на основе дисциплины с динамическими приоритетами, изменяющимися по формуле Pri=Pr0i+ai*t*t.

10. Диспетчер на основе дисциплины с динамическими приоритетами, изменяющимися по формуле Pri=Pr0i+ai*sqrt(t).

11. Диспетчер на основе дисциплины с динамическими приоритетами, изменяющимися по формуле Pri=Pr0i+ai*t*t*t.

12. Диспетчер на основе дисциплины с динамическими приоритетами, изменяющимися по формуле Pri=Pr0i+ki., где ki – случайное число.

13. Диспетчер на основе дисциплины LCFS (last come – first served – последним пришёл - первым обслужился). Данная дисциплина является вытесняющей и характерна для обработки прерываний.

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

Поиск по сайту: