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

• Введение
• 1. Теоретические основы планирования и диспетчеризации
• 1.1 Дисциплины обслуживания
• 1.3 Оценки эффективности планирования
• 2. Планирование верхнего уровня управления заданиями
• 2.1 Исходные данные
• 2.2 Сравнительный анализ дисциплин FIFO и SJF
• 2.3 Выводы
• 3. Диспетчеризация
• 3.1 Задание
• 3.2 Бесприоритетная ДО — смешанный алгоритм
• 3.3 Приоритетная ДО — относительный приоритет
• Заключение
• Список литературы
• Приложение

Цель работы:

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

Вследствие этого ставятся следующие задачи:

изучение теоретических данных об основах планирования и диспетчеризации;

построение временных диаграмм для исследования работы алгоритмов дисциплин FIFO и SJF;

выявление сходств и различий между работой алгоритмов;

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

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

1. Теоретические основы планирования и диспетчеризации

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

Современные ОС имеют целое множество функций:

Основные функции:

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

· Загрузка программ в оперативную память и их выполнение.

· Стандартизованный доступ к периферийным устройствам (устройства ввода-вывода).

· Управление оперативной памятью (распределение между процессами, организация виртуальной памяти).

· Управление доступом к данным на энергонезависимых носителях (таких как жёсткий диск, оптические диски и др.), организованным в той или иной файловой системе.

· Обеспечение пользовательского интерфейса.

· Сохранение информации об ошибках системы.

Дополнительные функции:

· Параллельное или псевдопараллельное выполнение задач (многозадачность).

· Эффективное распределение ресурсов вычислительной системы между процессами.

· Разграничение доступа различных процессов к ресурсам.

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

· Взаимодействие между процессами: обмен данными, взаимная синхронизация.

· Защита самой системы, а также пользовательских данных и программ от действий пользователей (злонамеренных или по незнанию) или приложений.

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

Центральная часть ОС — ядро, управляющее выполнением процессов, ресурсами вычислительной системы и предоставляющая процессам координированный доступ к этим ресурсам. Любая операционная система позволяет обрабатывать поступающую информацию в мультипрограммном режиме, т. е. в систему может поступить несколько заданий и если она обладает достаточными ресурсами памяти, то эти задания могут быть выполнены либо все одновременно, либо в какой-то последовательности. Примитивные многозадачные среды обеспечивают чистое «разделение ресурсов», когда за каждой задачей закрепляется определённый участок памяти, и задача активизируется в строго определённые интервалы времени. Более развитые многозадачные системы проводят распределение ресурсов динамически, когда задача стартует в памяти или покидает память в зависимости от её приоритета и от стратегии системы. В последних ресурсы распределяет служба управления, которая содержит 2 составляющие: планировщик заданий и планировщик задач. Планировщик заданий выбирает, какие задания и в какой последовательности должны поступать на обработку. Он должен обеспечивать определённую дисциплину выбора заданий на обработку. Для принятия такого решения могут учитываться такие характеристики заданий, как приоритет, необходимые ресурсы и т. п. Планировщик заданий не только выделяет необходимые ресурсы для поступающего на обработку задания, но и освобождает ресурсы после выполнения задания. Также планировщик задач занимается распределением ресурсов процессора между процессами. Он должен решить, какому из созданных процессов предоставить процессор, в какой момент и на сколько, во временном отношении.

1.1 Дисциплины обслуживания

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

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

Более развёрнутая классификация имеет следующий вид:

Бесприоритетные ДО:

1. FIFO — «первым пришел — первым выбран на обслуживание» .

Время обслуживания заявки равно ее трудоемкости.

2. LIFO — «последним пришел — первым выбран на обслуживание» .

Время обработки самой последней задачи аналогично FIFO.

3. RAND — случайный выбор заявки из очереди.

планирование диспетчеризация дисциплина обслуживание

4. RR — «круговорот». Отличается от FIFO лишь временем обслуживания: каждая заявка получает определенный квант времени (одинаковый для всех).

Приоритетные ДО:

1. PRT — выбор заявок на обслуживание по приоритету. Более приоритетной заявке соответствует меньшее число.

2. SJF — выбор заявки на обслуживание с минимальной трудоемкостью.

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

1.2 Оценки эффективности планирования

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

t = t_З — t_П, где

t — время обращения задания, t_З — время завершения задания, t_П — время поступления задания.

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

Более универсальной оценкой, позволяющей сравнивать между собой задания любой длины, является взвешенное время обращения

W = (t_З — t_П) / T, где

W — взвешенное время обращения,

T — действительное время выполнения задания.

Для случая M заданий можно провести оценку по среднему взвешенному времени обращения

W_СР — средневзвешенное время обращения,

W_i — взвешенное время обращения i — го задания,

M — количество заданий.

2. Планирование верхнего уровня управления заданиями

2.1 Исходные данные

Вычислительная система располагает оперативной памятью (ОП) V и внешним объемом памяти Н (НМД). ОП память выделяется перемещаемым разделами, которые исключают влияние фрагментации. Реализуется режим мультипрограммирования: если одновременно выполняется несколько задач, то процессорное время распределяется между ними равномерно. В систему поступает поток из М заданий, очередное задание поступает через время t_i, для простоты каждое задание состоит из одной задачи и требует объем ОП — v_i, объем внешней памяти h_i, процессорное время. Каждое задание использует свою внешнюю память только для ввода данных в течение времени q*h_i, после чего начинается счет.

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

Т_i = q*h_i + t_i.

Вновь поступившие задания помещаются в очередь. Для выбора заданий из очереди на выполнение используются два алгоритма:

1) среди заданий в очереди, для которых достаточно свободных ресурсов, выбирается задание, поступившее первым (правило FIFO);

2) среди заданий в очереди, для которых достаточно свободных ресурсов, выбирается задание с наименьшим t_i (правило SJF).

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

где — время завершения задания, — время поступления задания в систему.

Таблица 1. Последовательность заданий и их параметры

Значение используемых параметров: V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) t_i=k_i.

2.2 Сравнительный анализ дисциплин FIFO и SJF

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

Дисциплина FIFO

Таблица 2. Трассировка планирования по алгоритму FIFO

Сведём полученные данные в таблицу 3 и рассчитаем средневзвешенное время обращения для каждого задания.

Средневзвешенное время обращения рассчитывается:

,

- время поступления задания;

- время завершения задания.

Ниже приведены расчёты взвешенного времени обращения для каждой задачи и средневзвешенного времени обращения для дисциплины FIFO в целом:

Максимальный коэффициент мультипрограммирования равен 3. Такой коэффициент был получен на участках 75 — 213 (Задания 2,8,9) и 243−330 (Задания 3,4,5); Средневзвешенное время обращения ;

Таблица 3. Сводная таблица для алгоритма FIFO

Приведём график работы дисциплины обслуживания FIFO:

Рис. 1. График исполнения задач на процессоре для ДО FIFO

Дисциплина SJF

Таблица 4. Трассировка планирования по алгоритму SJF

Средневзвешенное время обращения рассчитывается:

,

- время поступления задания;

- время завершения задания;

Данные расчёты аналогичны расчётам для дисциплины FIFO, поэтому я не вижу смысла их здесь приводить.

Максимальный коэффициент мультипрограммирования K равен 3. Такой коэффициент был получен на участке 199−234 (3, 4,7).

Таблица 5. Сводная таблица для алгоритма SJF

Приведём график работы дисциплины обслуживания SJF:

Рис. 2. График исполнения задач на процессоре для ДО SJF

2.3 Выводы

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

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

3. Диспетчеризация

3.1 Задание

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

Диспетчер использует метод разделения времени в сочетании с приоритетами. ДО — следующие:

бесприоритетные ДО (БП) — смешанный алгоритм;

приоритетные ДО (П) — относительный приоритет;

Интервал наибольшей протяженности, соответствующий максимальному коэффициенту мультипрограммирования К_max=3, 75 — 213 (Задания 2,8,9). Задания, развивающиеся на процессоре на этом интервале, перечислены в таблице:

Таблица 6. Задания на процессоре

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

3.2 Бесприоритетная ДО — смешанный алгоритм

На рисунке представлена схема смешанного алгоритма обслуживания

Рис. 3. Схема смешанного алгоритма обслуживания

Суть данного алгоритма заключается в том, что каждая заявка проходит в i-ой очереди несколько кругов и только потом переходит в очередь i+1. Этот алгоритм является производным алгоритма с обратной связью и смешанного алгоритма.

Блок-схема алгоритма работы диспетчера представлена на рисунке.

n_replay — параметр диспетчера, задающий количество квантов работы задачи перед ее переходом в следующую очередь.

rep — счетчик, связанный с каждой задачей, индицирующий количество квантов ее исполнения в текущей очереди.

i — номер текущей очереди.

t — текущее значение времени

?t — квант времени, предоставляемый задаче

Рис. 4. Блок-схема смешанного алгоритма обслуживания

Рис. 5. Результат работы программы диспетчера с относительным приоритетом

3.3 Приоритетная ДО — относительный приоритет

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

Рис. 6. Схема алгоритма обслуживания с относительным приоритетом

Если поступило несколько заявок одного приоритета, то в очереди они обслуживаются по принципу FIFO.

Чем меньше значение приоритета, тем раньше выполняется задача.

Блок-схема алгоритма работы диспетчера представлена на рисунке.

i — номер текущей очереди.

t — текущее значение времени

?t — квант времени, предоставляемый задаче

Рис. 7. Блок-схема алгоритма обслуживания с относительным приоритетом

Рис. 8. Результат работы программы диспетчера с относительным приоритетом

Заключение

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

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

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

1. Л. А. Коршикова. Операционные системы как системы управления вычислительными ресурсами: Учеб. пособие. — Новосибирск: Изд-во НГТУ, 2001. — 63 с.

2. 1. Коршикова Л. А. «Основы операционных систем»: учеб. Пособие / - Новосибирск: изд-во НГТУ, 2008. — 356 с.

3. Многозадачная операционная система. Моделирование функций. Методические указания к лабораторной работе по дисциплине СПО.681 М735 № 1538, НГТУ, 1997 г.

Приложение

Листинг программы, используемой в пункте 3:

struct Task // Структура, определяющая задачу

{

int pr; // приоритет

int num; // номер

Task *next; // следующая задача

Task (int num, int pr=-1): pr (pr), num (num), next (NULL) {}

};

class Queue // класс очереди

{

Task *first, *last;

public:

int cnt;

Queue (): first (NULL), last (NULL), cnt (0) {}

Enqueue (int num, int pr=-1) // включение

{

if (! first) first = last = new Task (num, pr);

else

{last->next = new Task (num, pr); last = last->next; }

cnt++;

}

Enqueue (Task *t) // включение

{

if (! first) first = last = t;

else

{last->next = t; last = last->next; }

cnt++;

}

Task* Dequeue () // исключение

{

if (first)

{

Task *t = first;

first = first->next;

cnt—;

return t;

}

}

int Empty () // пусто?

{

return! cnt;

}

};

class Dispather // базовый класс диспетчера

{

protected:

double kvant; // квант CPU, выделяемый задаче

int n_tasks; // количество задач

int sv_kvant; // квант SV

Queue Q [10]; // массив очередей

public:

Dispather (double kvant, int sv_kvant);

virtual Add (int n, int prt) = 0; // длбавить задачу

virtual Do (double t, double T) = 0; // выполнять

};

Dispather: Dispather (double kvant, int sv_kvant)

: kvant (kvant), n_tasks (0), sv_kvant (sv_kvant)

{

}

class DispatherNoPrt: public Dispather // класс диспетчера со смешанным алгоритмом

{

int n_replay; // количество повторений

public:

DispatherNoPrt (double kvant, int sv_kvant, int n_replay)

: Dispather (kvant, sv_kvant), n_replay (n_replay) {}

Add (int n, int prt=-1);

Do (double t, double T);

};

DispatherNoPrt: Add (int n, int prt)

{

Q. Enqueue (n); n_tasks++;

}

DispatherNoPrt: Do (double t, double T)

{

int cur_q = 0;

Task* cur_t;

double tmAbs = t;

for (double tm=t; tm<=T;)

{

for (int rep=0; rep

{

for (int i=0; i<=T; i++)

{

cur_t = Q [cur_q]. Dequeue ();

cout<<" SV «<<' '<<» Time = «<

tmAbs += sv_kvant;

cout<<" Task #" <num<<' '<<" Time = «<

if (rep == n_replay-1) Q [cur_q+1]. Enqueue (cur_t);

else Q [cur_q]. Enqueue (cur_t);

tm+=kvant;

tmAbs += kvant;

}

}

cur_q++;

}

}

class DispatherPrt: public Dispather // класс диспетчера с относительным приоритетом

{

public:

DispatherPrt (double kvant, int sv_kvant)

: Dispather (kvant, sv_kvant) {}

Add (int n, int pr);

Do (double t, double T);

};

DispatherPrt: Add (int n, int pr)

{

Q [pr]. Enqueue (n, pr);

n_tasks++;

}

DispatherPrt: Do (double t, double T)

{

int cur_q = 0;

Task* cur_t;

double tm=t;

double tmAbs = t;

for (int j=0; j<10; j++)

{

if (! Q [cur_q]. Empty ())

{

for (double tml=0;

tm<=T && tml<= (double) (T-t) / (double) n_tasks* (double) Q [cur_q]. cnt; tml+=kvant)

{

cur_t = Q [cur_q]. Dequeue ();

cout<<" SV «<<' '<<» Time = «<

tmAbs += sv_kvant;

cout<<" Task #" <num<<' '<<" Time = «<

Q [cur_q]. Enqueue (cur_t);

tm+=kvant;

tmAbs+=kvant;

}

}

cur_q++;

}

}

#include

#include

#include «disp. h»

void main ()

{

cout<<" 1 — FIFO" <

cout<<" 2 — SJF" <

int c;

cin>>c;

double kv, sv;

cout<<" Enter CPU kvant: «;

cin>>kv;

cout<<" Enter SV kvant: «;

cin>>sv;

Dispather *d;

if (c == 1)

d = new DispatherNoPrt (kv, sv,

2);

if (c == 2)

d = new DispatherPrt (kv, sv);

d->Add (2,2);

d->Add (3,3);

d->Add (4,1);

d->Add (5,4);

d->Add (8,2);

d->Do (0, 42);

cin>>c;

delete d;

}