Диспетчер задач для бесприоритетной ДО – смешанный алгоритм. Курсовая работа по дисциплине СПО

  • ID: 04322 
  • 23 страницы

Содержание:


Диспетчер задач для бесприоритетной ДО – смешанный алгоритм. Курсо…

1.Введение в предметную область

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

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

Понятие диспетчеризации

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

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

Дисциплины диспетчеризации (ДД) – правила в соответствии с которым из очереди выбирается соответствующее требование и предоставляется ресурс.

Требования к ДД:

– ДД должны обеспечивать высокий показатель эффективности, при этом время ожидания должно быть равномерно

– Необходимо, чтобы ДД была минимальна по трудоёмкости

Классификация дисциплин обслуживания приведена на рис.3.

Рисунок 2 - Классификация дисциплин обслуживания

Общая характеристика ДО

Бесприоритетные ДО: выбирают заявки без учёта их важности, а по принципу последовательности поступления.

2. Исходные данные

2.1 Задание

Вычислительная система располагает оперативной памятью (ОП) V и внешним обьемом памяти Н (НМД). ОП память выделяется перемещаемым разделами, которые исключают влияние фрагментации. Реализуется режим мультипрограммирования: если одновременно выполняется несколько задач, то процессорное время распределяется между ними равномерно. В систему поступает поток из М заданий, очередное задание поступает через время ti, для простоты каждое задание состоит из одной задачи и требует обьем ОП - vi, обьем внешней памяти hi, процессорное время. Каждое задание использует свою внешнюю память только для ввода данных в течение времени q*hi, после чего начинается счет. Однако закрепленные за каждым заданием носители освобождаются только после завершения задания. Предположим, возможно параллельное использование внешней памяти заданиями без задержки друг друга. Если бы задания выполнялись по одному, то на каждое задание было бы затрачено время Тi = q*hi + ti. Вновь поступившие задания помещаются в очередь. Для выбора заданий из очереди на выполнение используются два алгоритма:

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

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

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

2.2. Таблица последовательностей.

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

Таблица 1 – Исходные данные

Таблица 2 - Таблица последовательностей

3. Временные диаграммы использования FIFO и SJF. Таблицы результатов.

ДО FIFO:

Рисунок 3 -Мультипрограммирование с учетом требований к памяти и НМЛ (ДО - FIFO).

ДО SJF:

Рисунок 4 - Мультипрограммирование с учетом требований к памяти и НМЛ (ДО - SJF).

Таблица 3- Мультипрограммирование с учетом требований к памяти и НМЛ (FIFIO)

Таблица 4 - Мультипрограммирование с учетом требований к памяти и НМЛ (SJF)

….

Таблица 5 - Сводка результатов (ДО - FIFO):

Максимальный коэффициент мультипрограммирования равен 4, на участках: 14 – 119 (задания: 3,4,7,8 ) и 139 – 219 (задания: 1,2,3,7).

Таблица 6 - Сводка результатов (ДО - SJF):

Максимальный коэффициент мультипрограммирования равен 4, на участках: 14 – 119 (задания: 3,4,7,8) и 139 – 219 (задания: 1,2,3,7).

4. Выводы по разделу №1.

Сравнивая полученные результаты, можно сделать следующие выводы:

1. Оба алгоритма показали коэффициент мультипрограммирования 4.

2. Применение принципа FIFO снижает длительность времени ожидания для каждого задания.

3. Планирование по принципу SJF обеспечивает уменьшение среднего времени обращения, но отдает явное предпочтение коротким заданиям.

В данном конкретном примере ДО SJF выглядела несколько предпочтительнее, для заданного набора задач. Показатели среднего взвешенного времени обращения ДО SJF оказались лучше, чем ДО FIFO.

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

5. Диспетчер. Раздел № 2.

5.1. Задание.

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

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

5.2. Исходные данные.

ДО - следующие:

- бесприоритетные ДО (БП) – FB- обратная связь;

- приоритетные ДО (П) - адаптивное обслуживание;

Участок, на котором коэффициент мультипрограммирования максимален (Kmax = 4 )

6. Диспетчеризация заданий.

6.1 Общие положения.

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

6.2. Диспетчер задач для бесприоритетной ДО – смешанный алгоритм.

Смешанный алгоритм обслуживания - это совмещение (RR+FB).

На рисунке 5 представлена схема алгоритма обслуживания с учетом ДО (RR и FB)

Рисунок 5 - Схема циклической ДО (FB)

Рисунок 6 - Диаграмма циклической ДО (FB)

6.3 Диспетчер задач для приоритетной ДО – адаптивное обслуживание.

В этом случае решения об абсолютном или относительном приоритетах принимаются в зависимости от обстановки. Для решения этого вопроса взвешивается - "что стоит" прерывание.

Рисунок 7 - Схема алгоритма - адаптивное обслуживание.

Присвоение приоритетов задачам осуществлено пользователем :

Рисунок 8 - Диаграмма адаптивного обслуживания.

7. Программная реализация

#include

#include

#include

#include

#define OS 9

#define TEXT 0

#define FRAPH 11

#define ERROR 12

8. Заключение

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

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

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

Используемая литература

1. Коршикова Л.А. «Лекции по дисциплине СПО»

2. Методическое пособие по СПО «Планирование верхнего уровня управления заданиями».

3. Мэдник С., Донован Дж. Операционные системы. – М.: Мир, 1978, 792 с.