Требования к отчету по л.р. № 1

Отчет должен содержать:

1. Сформулированную студентом постановку задачи.

2. Структуру разрабатываемой программы (на уровне модулей) с указанием их входных и выходных данных.

3. Алгоритмы работы модулей (в виде схемы алгоритма или с использованием диаграмм Шнейдерманна или на формализованном ограниченном естественном языке).

4. Описание алгоритма диспетчеризации, реализуемого в ходе данной работы.

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

6. Протокол работы Вашей "системы" в соответствии с разрабо­танным тестовым примером.

7. Письменные ответы на контрольные вопросы к л.р. № 1

4.1.8. Контрольные вопросы к л.р. № 1

I группа.

1 .Сформулируйте определение состояния процесса. 2. Охарактер­изуйте причины изменения состояний процессов в ВС. З. Что является причиной изменения состояний процессов в разработанной Вами "системе"?

II группа.

1. Перечислите операции диспетчеризации, реализуемые при выполнении л. р. № 1. 2. Составьте диаграмму переходов процессов из одного состояния в другое. 3. Каким образом инициируется выполне­ние каждой из реализованных в Вашей "системе" операции диспетче­ризации?

III. группа.

1. Приведите краткое описание команд взаимодействия с разработанной Вами "системой". 2. Каждой "управляющей" команде поставьте в соответствие операции планирования и диспетчеризации, выполнение которых вызывает данная команда 3. Перечислите ситуации в работе Вашей "системе", которые приводят к выполнению опе­рации "Выделение_ресурса".

4.2. Лабораторная работа № 2.
"Изучение дисциплин диспетчеризации процессов
в многопрограммных ОС".

Цель работы.

Освоение и программная реализация дисциплин распределения ресурсов, используемых в многопрограммных ОС.

Содержание работы.

При выполнении лабораторной работы № 2 необходимо осуществить развитие дисциплины диспетчеризации, реализованной в ходе выпол­нения лабораторной работы № 1. Развитие дисциплины диспетчеризации должно осуществляться по следующим направлениям:

1. Изменение при переводе процесса в состояние готовность. Формирование соответствующего списка должно осуществляться в соответствии с перечисленными выше условиями (см. 4.1.3.); однако место в списке готовых процессов, определяемое ранее по принципу HPF=FCFS, при выполнении лабораторной работы № 2 должно определя­ться с учетом объема ОП, необходимой для выполнения машинной программы, - чем "короче" программа, тем ближе к началу списка должен располагаться соответствующий дескриптор (при сохранении принципа HPF), т.е. речь идет о реализации комплексного правила HPF=SMN=FCFS.

2. Реализация принципа циклической диспетчеризации.

3. В ходе лабораторной работы № 2 дополнительно к операциям диспетчеризации процессов Выбор, Запрос_ресурса, Выделение_ресурса и операции планирования процессов – Завершение (реализуемых при выполнении лабораторной работы № 1) необходимо осуществить программную имитаций операции диспетчеризации процессов Истечение_кванта.

4.2.1. Краткое описание схемы одноочередной круговой (цикли­ческой)
диспетчеризации.

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

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

а) упрощенный фрагмент диспетчеризации с FCFS (FIFO) без квантования времени ЦП.

Запуск Выбор Завершение

Истечение кванта

б) упрощенный фрагмент схемы диспетчеризации с FCFS (FIFO)с квантованием времени ЦП.

Рис. 4. Одноочередная реализация диспетчеризации для операций
Запуск, Выбор, Истечение_кванта

На рис. 4 представлена схема формирования очереди готовых процессов при выполнении операций планирования Запуск и операции диспетчеризации Истечение_кванта. Заметим, что операция Выбор производит выделение кванта времени ЦП, процессу, дескриптор которого находится в начале очереди готовых процессов, формируемой по принципу FCFS. Алгоритм, иллюстрируемый данной схемой, прост для реализации; необходимо отметить, что в рассмотренной схеме в наиболее благоприятных условиях находятся процессы, которым требуется меньшее время для использования ресурсов (включая ЦП).

4.2.2. Краткое описание алгоритма многоочередной диспетчеризации для операции Истечение_кванта.

Рассмотренная выше дисциплина является одноочередной. Ее усовершенствованием является модификация данной схемы, связанная с введением многоочередной схемы диспетчеризации.

На рис.5 представлена схема многоочередной диспетчеризации.

Очередь1

Конец … начало

Запуск Выбор Завершение

 

Очередь2

Конец … начало

 

Очередь3

Конец … начало

 

:

:

Очередь1

Конец … начало

 

:

:

Очередь n-1

Конец … начало

 

Очередь n

Конец … начало

 

 

Истечение_кванта

 

 

Рис.5. Многоочередная реализация диспетчеризации для операций Истечение_кванта.

Для представленной схемы организуются n очередей. После выполнения операции планирования для какого-либо процесса его дескриптор помещается в Очередь 1. В принципе, в качестве первой очереди может использоваться списковая структура, формирование которой осуществляется не обязательно в соответствии с правилом FCFS. В очереди с номерами от 2 до n поступают дескрипторы активных процессов, отношении которых произведена операция Истече­ние_кванта. Поступление и извлечение дескрипторов процессов в/из очередей осуществляется следующим образом.

При выполнении операции Выбор процесс, дескриптор которого расположен в начале i-той очереди (1<=i<=n), будет помещен в состояние выполнение только в том случае, если все очереди от первой до (i-1)-ой – пустые. Выполнение выбранного процесса будет осуществляться в течение кванта времени (если, конечно, не произойдет операция диспетчеризации Запрос_ресурса, Завершение или какая-либо другая операция планирования процессов в отношении данного выполняемого процесса). После истечения кванта времени, вследст­вие выполнения операции диспетчеризации Истечение_кванта времени ЦП произойдет перевод процесса из состояния выполнение в состоя­ние готовность и его дескриптор поступает в конец очереди с номером i+1.

Последующая за этим операция Выбор переведет в состояние выполнение тот процесс, дескриптор которого стоит в начале очереди с самым младшим номером. Таким процессом может оказаться процесс, дескриптор которого стоял следующим в очереди i или в очереди i+1 (при условии, что после выбора процесса из очереди i последняя оказалась пустой). Дескриптор процесса, переводимого из пассивного состояния в активное (с помощью операции Запуск), поступает в первую очередь (i=1). Если это имеет место быть, после окончания кванта времени ЦП, выделенного для выполнения процесса из очереди i, будет осуществлен запуск процесса, дескриптор которого помещен в очередь номер 1.

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