Будь умным!

У вас вопросы?
У нас ответы:) SamZan.net

Системное программное обеспечение раздел Организация вычислительных процессов Для студентов IIIIV ку

Работа добавлена на сайт samzan.net:


Планирование верхнего уровня управления заданиями
(Планирование заданий с учетом требований
к памяти и внешним устройствам)

Методические указания к лабораторной работе по курсу
«Системное программное обеспечение»
раздел «Организация вычислительных процессов»

Для студентов III-IV курсов факультета автоматики и вычислительной техники
(специальность 2201) всех форм обучения

Цель работы

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

Общие сведения о планировании заданий

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

Можно выделить следующие компоненты этой службы:

–планировщик заданий,

–планировщик задач (планировщик процессов).

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

Объектами работы планировщика заданий являются задания, а планировщик задач управляет процессами.

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

Планировщик задач выступает в роли «микропланировщика», распределяющего процессор между процессами.

В случае мультипрограммирования планировщик заданий выбирает несколько заданий из множества всех представленных и вводит их в систему. Для каждого задания формируется таблица задания JCB (Job Control Block). Пример таблицы задания приведен на рис. 1.

Идентификатор задания –

Количество шагов –

1

приоритет –

объем памяти –

число внешних устройств –

предполагаемое время выполнения –

признаки выполнения задачи –

2

.

.

N

признаки выполнения задачи –

Рис. 1. Таблица задания.

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

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

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

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

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

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

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

d0. 2. .

В настоящей лабораторной работе рассматриваются 4 дисциплины обслуживания:

. Линейная дисциплина обслуживания FIFO (First In –First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь первой.

. Линейная дисциплина обслуживания LIFO (Last In –First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь последней.

. Дисциплина обслуживания с фиксированным приоритетом SJF (Short Job First). Из очереди заявок на обслуживание выбирается заявка с минимальным временем обслуживания.

. Дисциплина обслуживания с фиксированным приоритетом PRT (PRioriTy). Из очереди заявок на обслуживание выбирается заявка с максимальным приоритетом.

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

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

t = tЗ – tП, где

t – время обращения задания,

tЗ – время завершения задания,

tП – время поступления задания.

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

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

W = (tЗ – tП) / T, где

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

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

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

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

Wi – взвешенное время обращения i -го задания,

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

Пример построения временной диаграммы мультипрограммной работы ЭВМ (дисциплина обслуживания FIFO)

Примем, что в нашем распоряжении имеются 9 Kb оперативной памяти и 5 внешних устройств. Характеристики заданий приведены в таблице 1.

Таблица 1. Характеристики заданий.

Номер задания

Время поступления

Необходимое процессорное время

Требования
к ОП

Требования
к ВУ

1

2

3

4

Время ввода каждого задания определим по формуле:

tввода = q × N , где

q – время работы одного внешнего устройства (q=5 ед.времени), N – число внешних устройств.

Таким образом, если бы задания выполнялись по одному, то на каждое задание было бы затрачено время

T = tввода + tпроц. , где

T – время выполнения задания,

tпроц. – процессорное время, затраченное для выполнения задания.

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

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

Временная диаграмма мультипрограммной работы ЭВМ при приведенных выше исходных данных изображена на рис.3

Рис. 3. Временная диаграмма мультипрограммной работы ЭВМ
(Дисциплина обслуживания FIFO).

Процесс построения временной диаграммы рассмотрен в таблице 2.

Таблица 2. Описание построения временной диаграммы.

Время

Событие

t = 0

Поступило задание 1. Т.к. свободных ресурсов (ОП и ВУ) заданию хватает, оно назначается на выполнение. (Начинается ввод).

t = 5

Ввод завершен и все процессорное время отдается для выполнения задания 1.

t = 7

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

t = 12

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

t = 20

Поступило задание 4. Т.к. свободных ресурсов заданию хватает, оно назначается на выполнение. Первые 5 ед. времени процессорное время заданию 4 не требуется и его полностью получает задание 1.

t = 25

Завершился ввод задания 4. С этого момента времени процессор необходим обоим заданиям. Процессор начинает работать в мультипрограммном режиме. Каждое из заданий получает 10 ед. процессорного времени. В сумме процессорного времени затрачено 20 ед.

t = 45

Завершено выполнение задания 1. Ресурсы, занятые им, освобождены. Теперь свободных ресурсов достаточно для назначения на выполнение задания 2 или 3 (но не одновременно). В действие вступает дисциплина обслуживания FIFO. На выполнение назначается задание 2 –оно поступило первым (задание 3 остается в очереди).

t = 50

Те 5 ед. времени, в течение которых выполнялся ввод задания 2, все процессорное время (5 ед.) получило задание 4. Вновь процессор начинает работать в мультипрограммном режиме. 10 ед. процессорного времени распределяются между заданиями 4 и 2.

t = 60

Выполнение задания 4 завершено, но освободившихся ресурсов недостаточно для назначения на выполнение задания 3. Задание 3 остается в очереди.

t = 65

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

t = 85

Завершилось выполнение задания 3.

Каким образом можно проверить правильность построения временной диаграммы?

Для этого необходимо определить по временной диаграмме, сколько времени работал процессор. Это временные интервалы с t=5 до t=65 и с t=75 до t=85. В интервале с t=65 до t=75 процессор простаивал. Таким образом, процессор работал в течение 70 ед. времени.

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

Tпроцессора = 30+10+10+20=70 ед.

Значения равны, следовательно, диаграмма построена верно.

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

  1.  W1 = (tЗ – tП) / T = (tЗ – tП) / (tввода + tпроц) = (tЗ – tП) / (q × N + tпроц) = (45 –) / (5 × 1 + 40) =
    = 1.00
  2.  W2 = (65 –) / (5 × 1 + 15) = 2.90
  3.  W3 = (82 –) / (5 × 2 + 10) = 3.65
  4.  W4 = (60 –) / (5 × 1 + 35) = 1.00

Т.о. Wср = (W1 + W2 + W3 + W4) / 4 = 2.14.

Описание модели, планировщик заданий

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

– ввод параметра потока заданий;

– ввод параметров системы;

– назначение задания на выполнение и выделение заданию необходимых ресурсов (при условии, что свободных ресурсов достаточно для выполнения задания);

– отслеживание выполняющихся заданий в дискретные моменты времени (через каждый квант модельного времени);

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

– отсчет времени ввода и выполнения задания;

– печать состояния заданий через каждый квант модельного времени.

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

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

После завершения моделирования программа переключается в режим диалога с пользователем и осуществляет вывод на экран результатов моделирования. Работа в этом режиме происходит только с журналом полученных результатов, т.е. при изменении параметров просмотра (View -> Diagram, View -> Process и т.д.) повторного моделирования не происходит, а изменяются лишь параметры просмотра содержимого журнала.

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

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

Рис. 4.  Блок-схема программной модели планировщика заданий.

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

В ЭВМ (работа которой промоделирована в настоящей лабораторной работе) имеется память объемом 16К и 10 внешних устройств, реализуется режим мультипрограммирования: если одновременно выполняется несколько задач, а процессорное время распределяется между ними равномерно. В ЭВМ поступает поток (или пакет) из заданий. Поступившие задания, которым не хватает свободных ресурсов, помещаются в очередь. Для выборки заданий из очереди (среди заданий, для которых достаточно свободных ресурсов) используются дисциплины обслуживания FIFO, LIFO, SJF, PRT. Задание состоит из одной задачи. Для формирования последовательности заданий используется набор из 10 типов задач, характеристики которых приведены в таблице 3. Каждое задание включает одну из этих 10 задач. В одном потоке заданий могут встречаться задания, содержащие одинаковые задачи. Для выполнения каждого задания требуется определенный объем оперативной памяти, несколько внешних устройств, процессорное время.

Если бы задания выполнялись по одному, то на каждое задание было бы затрачено время

T = tвода + tпроцессора, где

T – время выполнения задания,

tввода – время ввода задания,

tпроцессора – процессорное время, необходимое для выполнения задания.

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

tввода = q × N, где

N – число внешних устройств, используемых заданием,

q – время работы одного внешнего устройства (q = 5 ед. модельного времени).

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

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

Таблица 3. Характеристики задач.

Номер задачи

Процессорное время,
ед. модельного времени

70

40

Требования к ОП, К

6

6

1

Требования к ВУ, шт.

2

Приоритет

2

Таблица 4. Варианты заданий.

Номер
варианта

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

1

FIFO, SJF

2

LIFO, PRT

3

LIFO, SJF

4

FIFO, PRT

Порядок выполнения лабораторной работы

Первая часть лабораторной работы

Лабораторная работа состоит из двух частей. В первой части лабораторной работы исследуются модели дисциплин обслуживания для существующего входного потока (входной поток задан заранее и сохранен в файле test.dat). Цель первой части работы –знакомство с интерфейсом программы и ознакомление с различными дисциплинами обслуживания. Параметры заданий и системы подобраны таким образом, что позволяют наглядно увидеть различия между дисциплинами обслуживания.

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

  •  multivis.exe – исполняемый файл программы;
  •  help.htm – файл помощи;
  •  Лабораторная работа №1 –СПО.rtf –электронная версия описания лабораторной работы;
  •  test.dat, 1task.dat, 2task.dat, many.dat –заранее сформированные наборы заданий для модели, исследование которых проводится в первой части лабораторной работы.
  1.  Порядок выполнения первой части.
  2.  Запустить программу MultiVis.exe.
  3.  Выбрать пункт Load… в меню File (рис. 5).

Рис. 5. Общий вид программы

  1.  Выбрать имя файла test.dat и нажать Open.

Рис. 6. Диалог ввода заданий.

  1.  В появившемся диалоговом окне «Ввод заданий» (Рис. 6) выбрать дисциплину обслуживания в соответствии с заданным вариантом (см. табл. 4). В примере, приведенном  на рис. 6 выбрана дисциплина обслуживания PRT.

Рис. 7. Моделирования в режиме временной диаграммы.

  1.  Нажать «Старт». При этом диалоговое окно закроется, и программа перейдет в режим моделирования. По умолчанию, будет представлена работа схемы в виде временной диаграммы.

Описание режима временной диаграммы (рис. 7). В нижней части экрана представлена временная ось, отображающая время моделирования. Поскольку используется событийное моделирование, то все времена, указанные на оси, соответствуют некоторым событиям. Эти события отмечаются на экране вертикальными пунктирными линиями. Горизонтальными линиями отображаются состояния заданий в системе. Задание может находиться в 3-х состояниях: ожидание (у системы недостаточно ресурсов для выполнения задания), загрузка (задание выполняет работу с внешними устройствами для загрузки) и выполнение (развитие задания на процессоре).

  1.  За ходом моделирования можно следить в двух режимах: в режиме временной диаграммы (меню View->Diagram) и в режиме просмотра текущего состояния заданий (меню View->Process). Во втором режиме возможно изменение скорости моделирования (пункты Increase и Decrease меню View, либо клавиши ‘+’ и ‘–‘). Для повтора моделирования в этом режиме можно выбрать View->Replay.

Рис. 8. Моделирования в режиме просмотра текущего состояния заданий.

  1.  В режиме Process (рис. 8) отображается следующая информация: текущее время моделирования, состояние задания, количество свободных ресурсов, оставшееся время выполнения (для каждого из заданий), схематично отображаются сами задания, при этом белым маркером показывается текущее место выполнения задания. В нижней части окна представлено занятие ресурсов заданиями, т.е. наглядно изображается какую часть оперативной памяти или внешних устройств занимает каждое из заданий. На примере: задание № 2 заняло всю оперативную память и все имеющиеся внешние устройства.
  2.  Для оценки эффективности работы вычислительной системы вычисляется средне взвешенное время выполнения заданий. Для получения значений взвешенного времени выполнения, времени поступления, начала и окончания работы заданий нужно воспользоваться пунктом Statistics меню View (рис. 9).

Рис. 9. Окно статистики.

  1.  Для возврата к диалоговому окну «Ввод заданий» можно воспользоваться пунктом меню File->Edit… 
  2.  Рекомендуется просмотреть и проанализировать результаты (аналогично рассуждениям представленным в табл. 2) моделирования для всех имеющихся дисциплин обслуживания.
  3.  Провести аналогичные исследования и ознакомиться в результатами моделирования наборов заданий для модели, содержащимися в файлах 1task.dat, 2task.dat и many.dat.
  4.  Ответьте на вопросы: Какой коэффициент мультипрограммирования достигается в моделируемой ситуации и почему? Как называется данный режим работы системы?

Вторая часть лабораторной работы

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

Параметры исследования:

  •  количество ОЗУ –изменяемый параметр –принимает следующие значения: 8, 10, 12, 14, 16;
  •  количество ВУ –постоянный параметр –выбирается из диапазона 8-10 единиц в начале работы либо самостоятельно, либо преподавателем; в процессе исследования
    не изменяется.
  •  количество заданий в наборе –постоянный параметр –наборы заданий формируется в начале выполнения второй части лабораторной работы и не изменяются в процессе исследований; количество заданий –-7 шт.
  1.  Порядок выполнения второй части работы.
  2.  Запустить программу MultiVis.exe
  3.  Выбрать пункт New… в меню File.
  4.  Задать необходимое количество Оперативной памяти и Дисковой памяти.
  5.  Ввести параметры заданий (клавиша «Добавить»). Имеется возможность редактирования данных (клавиша «Редактировать…») Примерный вид диалога приводится на рис. 10.

Рис. 10. Диалог редактирования задания.

  1.  После ввода необходимых заданий рекомендуется сохранить исходные данные модели, выбрав клавишу «Сохранить…».
  2.  Сформировать пакет коротких заданий (количество коротких заданий больше, чем длинных). Промоделировать полученный пакет, изменяя объем доступной оперативной памяти (8, 10, 12, 14, 16). Моделирование оценивается средневзвешенным временем выполнения заданий и максимальным коэффициентом мультипрограммирования. Полученный результаты заносятся в таблицу (рекомендуется использовать MS Excel), примерный вид таблицы приведен ниже (табл. 5).
  3.  Сформировать пакет длинных заданий и провести аналогичные исследования.
  4.  Провести эксперимент для двух потоков заданий (поток длинных и поток коротких заданий).

Содержание отчета

  1.  Цель работы.
  2.  Исходные данные.
  3.  Таблицы с результатами моделирования при изменении объема ОП.

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

Количество
ОП

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

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

Короткие

Длинные

Короткие

Длинные

пакет

поток

пакет

поток

пакет

поток

пакет

поток

Отчет должен содержать 2 таблицы: в одну заносятся результаты средневзвешенного времени выполнения заданий, в другую –максимальные значения коэффициента мультипрограммирования (для каждого варианта моделирования).

  1.  Графики зависимости средневзвешенного времени выполнения пакета (потока) работ от количества ОП.
  2.  Графики зависимости коэффициента мультипрограммирования от количества ОП.
  3.  Сравнительный анализ временных диаграмм по среднему взвешенному времени обращения и коэффициенту мультипрограммирования.
  4.  Составить алгоритм выбора планировщиком дисциплины обслуживания в зависимости от параметров поступивших в систему заданий (поток или пакет, короткие или длинные задания).

Контрольные вопросы

  1.  Определите понятия: задание, шаг задания, задача, процесс.
  2.  Каковы функции планировщика заданий?
  3.  Приведите примеры дисциплин обслуживания.
  4.  Приведите классификацию дисциплин обслуживания.
  5.  Какие существуют критерии планирования?
  6.  Какие существуют оценки эффективности планирования?
  7.  Заполните таблицу задания JCB для одного из заданий, использованных в лабораторной работе.

Список рекомендуемой литературы

  1.  Донован Дж. Системное программирование. –М.: Мир, 1975. –с.
  2.  Липаев В.В. Проектирование программных средств. Учебное пособие для ВУЗов. –М.: ВШ, 1990 –, илл.
  3.  Системное программное обеспечение /А.В.Гордеев, А.Ю.Молчанов. –Спб.: Питер, 2001. –с. илл.
  4.  Сетевые операционные системы/ В.Г.Олифер, И.А.Олифер. –Спб.: Питер, 2001. –с., илл.
  5.  Кейлингерт П. Элементы операционных систем –М.: Мир, 1985. –с., илл.

Содержание

Цель работы 1

Общие сведения о планировании заданий 1

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

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

Пример построения временной диаграммы мультипрограммной
работы ЭВМ (дисциплина обслуживания FIFO) 3

Описание модели, планировщик заданий 5

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

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

Порядок выполнения лабораторной работы 7

Первая часть лабораторной работы 7

Вторая часть лабораторной работы 11

Содержание отчета 12

Контрольные вопросы 12

Список рекомендуемой литературы 12

Содержание 13




1. Социальное поведение нормальных клеток и антисоциальное поведение опухолевых клеток
2.  Введение 2 Безрботица- причины формы уровни 3
3. Название отряда- ТормозаДевиз отряда- Тормозим мы все подряд два вожатых и Название отряда
4. модуль ПМ.01 Организация и управление торговосбытовой деятельностью Разработала
5. а ~ выстлан однослойным призматическим эпителием
6. Вексельное обращение
7. Воспитание детей в игре
8. История государства и права Беларуси Предметом изучения истории государства и права Республики Беларусь
9. кадры на ТВ сюжеты
10. 1Характеристика пищевого продукта6 1
11. Учет налоговых платежей
12. Лекция 12 Лексикология
13. Философия А.С. Хомякова
14. По их мнению число даты рождения и число имени должны совпадать
15. ДАТЧИКИ-РЕЛЕ КОНТРОЛЯ ПЛАМЕНИ ОПТИЧЕСКИЕ
16. Вычисление массы молекулы фтора и молярных масс эквивалентов окислителя и восстановителя
17. На тему- Психология беременных женщин
18. по теме расчет себестоимости оказания юридических услуг
19. Контрольная работа- Организация бухгалтерского дела на предприяти
20. Потребители туристских услуг; Агенты по продвижению туристских услуг; Поставщики туристских услуг

Материалы собраны группой SamZan и находятся в свободном доступе