Алгоритмы диспетчеризации

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

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

- вытесняющие и невытесняющие дисциплины алгоритмов диспетчеризации;

- диспетчеризация на основе времени готовности к обслуживанию;

- диспетчеризация на основе приоритетов;

- диспетчеризация с квантованием;

- диспетчеризация с учетом хода выполнения процесса.

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

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

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

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

1. Диспетчеризация по принципу очереди: первым пришел – первым обслужен;

2. Диспетчеризация по принципу стека: последним пришел – первым обслужен;

3. Круговая диспетчеризация: последовательное выполнение процессов вне зависимости от их времени начала готовности к выполнению.

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

При организации приоритетного распределения времени выполнения процессов, диспетчеризацию можно разделить по типу применяемых приоритетов:

1. Статические – вычислительные процессы имеют фиксированное значение приоритета. Как правило, распределение приоритетов проводится на этапе проектирования системы;

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

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

В ряде операционных систем в процесс распределения ресурса между потребителями вводится понятия кванта.

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

Алгоритмы диспетчеризации с квантованием можно разделить на два вида:

1. Алгоритмы с равными квантами – каждому процессу в равной степени предоставляются одинаковые интервалы исполнения;

2. Алгоритмы с разной величиной квантов – процессам выделяются кванты различной длины в зависимости от условий, приоритетности и иных характеристик процесса.

В данной работе для занятий с преподавателем и самостоятельных тренингов студентов будут задаваться разные величины квантов. Для первых один квант будет составлять 1,5 часа, а для вторых – 15 минут.

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

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

Вывод

В качестве решения предлагается совместить 3 вышеописанных способа составления расписания.

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