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

Министерство образования Российской Федерации

Кубанский государственный технологический университет

Кафедра вычислительной техники и АСУ

АРХИТЕКТУРА ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И СЕТЕЙ ЭВМ

Методические указания к лабораторным работам

для студентов всех форм обучения специальности 220400 - «Программное обеспечение вычислительной техники и автоматизированных систем»

Ошибка! Ошибка связи.

Млин…

Краснодар

УДК 681.32

Составитель: профессор каф. ВТ и АСУ В. И. Лойко

Архитектура вычислительных систем и сетей ЭВМ. Методические указания к лабораторным работам для студентов всех форм обучения специальности 220400 - Программное обеспечение вычислительной техники и автоматизированных систем / Кубан. гос. технол. ун-т., Сост.
В.И. Лойко, Краснодар, 1998, 70 с.

Составлены в соответствии с рабочей программой курса “ Архитектура вычислительных систем и сетей ЭВМ ” для студентов специальности 220400.

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

Табл. 7. Ил. 35. Библиогр.: 15 назв.

Рецензенты: зав. каф. КТ и ИБ проф. В.С. Симанков (КубГТУ),

зав. каф. ВТ и АСУ проф. В.И. Ключко (КубГТУ).

Организационно-методические указания

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

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

3. Студенты готовятся к выполнению очередной работы заблаговременно.

4. Студенты обязаны изучить технику безопасности при работе на лабораторных установках до 1000 В.

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

6. Неподготовленные студенты к выполнению лабораторной работы не допускаются.

7. Студенты, не сдавшие отчет во время занятия, сдают его в назначенное преподавателем время.

8. Студент, не выполнивший лабораторную работу, выполняет ее в согласованное с преподавателем время.

9. Каждая лабораторная работа выполняется студентами самостоятельно. Все студенты предъявляют индивидуальные отчеты. Допускается предъявление отчета в виде электронного документа.

10. Проверка знаний студентов производится преподавателем во время лабораторного занятия и при сдаче отчета.

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

Лабораторная работа №1

Управление ресурсами однопроцессорных систем оперативной обработки

Цель и порядок работы

Цель работы - моделирование вычислительной однопроцессорной системы оперативной обработки.

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

- ознакомиться с описанием лабораторной работы;

- выполнить задание раздела 3;

- ответить на контрольные вопросы теста;

- оформить отчет согласно указаниям раздела 4.

- представить результаты работы преподавателю.

Общие сведения

Алгоритм SPT

В системах оперативной обработки в качестве основного критерия эффективности используется средне время обслуживания заявок. Нетрудно видеть, что в случае, когда времена решения задач априори известны, минимальное среднее время ответа дает алгоритм SPT (Shortest-processing-task-first), назначающий задачи на решение в порядке убывания времени решения t_i, т.е. t₁£t₂£...£t_L . При этом время

_{i i-1}

ответа u_i для задачи z_i есть u_i= St_j, где St_j- время

^{j=1 j=1}

ожидания, t_i- собственно время решения и среднее время

ответа есть

.

Покажем, что u* действительно минимальное значение среднего времени обслуживания. Для того чтобы показать, что u* действительно минимально среди u для всех перестановок, достаточно показать, что применение к произвольной перестановке (a₁,...,a_L) любой парной транспозиции, меняющей местами элементы a_k и a_l, где ta_l£ ta_k и l>k, может лишь уменьшить исходное значение u, соответствующее перестановке (a₁,...,a_L), где a_i - номер задачи, назначаемой на решение i-й по порядку, i=I,L. Действительно, пусть задачи с номерами a_k и a_l поменялись местами. Тогда для полученной перестановки среднее время обслуживания равно

Нетрудно видеть, что

, а потому

,

так как l>k, а ta_l£ ta_k. Следовательно, перемещение вперед задачи с меньшим временем решения приводит к уменьшению среднего времени обслуживания. В перестановке (1, ... ,L) при условии, что t₁£...£t_L, нельзя сделать ни одной такой улучшающей транспозиции, а потому u* есть минимальное среднее время обслуживания и алгоритм SPT дает оптимальное решение рассматриваемой задачи.

Алгоритм RR

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

Простейшее правило планирования работ, обеспечивающее выполнение указанного требования, задается алгоритмом циклического обслуживания, или, иначе, алгоритмом RR (Round–Robin). Работа алгоритма иллюстрируется рисунком.

Заявки на выполнение работ поступают с интенсивностью l в очередь O, откуда они выбираются и исполняются процессором Пр. Для обслуживания отдельной заявки отводится постоянный квант времени q, достаточный для выполнения нескольких тысяч операций. Если работа была выполнена за время q, она покидает систему. В противном случае она вновь поступает в конец очереди и ожидает предоставления ей очередного кванта процессорного времени.

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

p_k=s^k-1(1-s), k=1,2,...

со средним

Таким образом, если известны средняя трудоемкость работ Q и длительность q кванта, то среднее количество квантов, с одной стороны, равно Q/q, а с другой – полученному выше выражению, то есть

, откуда .

Определим среднее время ответа для работы J, требующей ровно t единиц времени обработки. Пусть m – наименьшее целое, при котором m_q³t (т.е. m – число квантов, достаточное для обслуживания заявки). Рассмотрим состояние системы на момент поступления работы J. При поступлении работы J в системе в среднем находится W₁ других работ. Значение N₁ определяется как среднее число заявок в системе с бесприоритетным обслуживанием, на вход которой заявки поступают с интенсивностью

L=l+ls+ls²+¼+lsⁿ+¼=l/(1-s)

(с учетом интенсивности поступления заявок на дообслуживание в последующих тактах) и обслуживаются по экспоненциальному закону со средним q. Для определения W₁ требуется найти распределение вероятностей {pk} того, что в очереди будет ровно k заявок. Тогда

W₁= S kp_k.

Для определения p_k составим систему дифференциальных уравнений Колмогорова с помощью графа переходов (m=1/q)

Здесь S_i – состояние системы с i заявками в очереди (одна из них обслуживается). Тогда система уравнений имеет вид

p`_i =Lp_i-1 - mp_i - Lp_i + mp_i+1,

или

æ

í p`_i =Lp_i-1 - (m+L)p_i + mp_i+1, i=1,2,...

è p`₀ = -Lp₀ + mp₁.

Кроме того, требуется соблюдение условия нормировки

.

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

Lp_i-1 - (m+L)p_i + mp_i+1=0, i=1,2,...

- Lp₀ + mp₁=0,

p_{0 +} p_{1 +} ... + p_i + ... =1.

Из второго уравнения выразим p₁ через p₀ :

p₁ = L/m* p₀ ;

подставим это значение в первое уравнение с i=1. Тогда

Делаем индуктивное предположение: . Тогда из k-го уравнения получаем

откуда , что подтверждает индуктивное предположение. Поэтому в соответствии с условием нормировки имеем

,

где

.

На основании полученного выражения или p_k имеем

.

С учетом допущения об экспоненциальности распределения кванта q время дообслуживания работы J, не зависит от этого момента и в среднем равно q. Таким образом, работа будет ожидать W_1q единиц времени до получения первого кванта. За время W_1q и первый квант выполнения работы J в систему поступит l новых работ. Кроме того, sW₁ работ из их общего числа W₁ вернутся обратно в очередь на довыполнение. Поэтому в следующем цикле работа J застанет в системе W₂ работ:
W₂ = lW₁q + lq + sW₁.

Подставляя в последнее выражение ранее полученное значение W₁, получаем

В общем случае аналогично получаем

W_i = l W_i-1q + lq + s W_i-1 = r/(1-r).

Среднее время ожидания для работы J, время выполнения которой составляет m квантов, равно

w_m = q = mqr/(1-r) .

Здесь среднее время ожидания w_m определяется как время, необходимое для обслуживания всех W_i работ, стоящих впереди работы J в каждом из m циклов обслуживания. Среднее время ответа для работы J

Um = w_m +mq = mq/(1-r),

где r = lq/(1-s) = lq/(q/Q) = lQ – загрузка системы. Из выражения для времени ожидания w_m видно, что время ожидания обслуживания возрастает с увеличением трудоемкости t=mq задачи. В то же время при обслуживании задач в порядке поступления без прерываний среднее время ожидания w не зависит от трудоемкости и составляет

,

где , – средняя трудоемкость.

Сравним w и w_m:

.

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

Алгоритм FB

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

Заявки на выполнение работ поступают в очередь O₁. Работы, стоящие в очереди O₁, получают квант процессорного времени q. Если за это время работа была выполнена, то она покидает систему. В противном случае заявка на работу переносится в очередь O₂, откуда она может быть занесена в очереди O₃,O₄,...,O_n. Очереди обслуживаются в следующем порядке. Если имеется хотя бы одна заявка в очереди O₁, то эта заявка непременно обслуживается. Заявки из очереди O₂ обслуживаются при условии, что нет заявок в очереди O₁. Аналогично заявки из очереди O_m обслуживаются только в том случае, если все очереди O₁,..., O_m-1 пусты. Заявка, достигшая последней очереди O_n, остается в ней до полного завершения работы.

Применяются модификации алгоритма FB, различающиеся по величине квантов времени, предоставляемых заявкам из разных очередей. Возможно планирование на основе постоянной величины кванта или с использованием квантов переменной длительности, которая возрастает по мере увеличения номера очереди. Одна из таких модификаций – алгоритм планирования FB с учетом приоритетов работ. Работы, поступающие в систему, разделяются в зависимости от приоритетов I, ... , n на n потоков l₁, ... , l_n. Приоритеты задач относительны, т.е. поступление в систему заявки более высокого приоритета не прерывает процесс обработки менее приоритетных заявок, но при освобождении ресурса более приоритетные заявки будут назначены в первую очередь. Работы с высшим приоритетом поступают в очередь O₁, а работы с низким приоритетом – в очередь O_n. Работам, выбираемым на обслуживание из разных очередей, выделяются кванты времени различной длительности, причем заявкам из очереди O_m выделяется больший по продолжительности квант времени, чем заявкам из очереди O_m-1, m=2,n.

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

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

Например, операционная система для малых ЭВМ ОСРВ обеспечивает две процедуры разделения времени – циклическое планирование и вытеснение на диск. Процедура циклического планирования через заданный интервал времени циклически перемещает указатель задач в таблице задач системы STD (System Task Directory) и объявляет значимое событие, в результате обработки которого происходит перепланирование задач. Планировщик выбирает для выполнения первую задачу из STD. Обычно интервал времени циклического планирования устанавливается равным 0.1с.

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

– задача должна быть установлена как вытесняемая;

– на диске есть более приоритетная задача, для которой нет места в основной памяти;

– задача не имеет незавершенных запросов ввода-вывода (кроме запроса ввода с терминала).

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

Приоритетность программ для систем со свопингом может назначаться в соответствии с алгоритмом Корбато. Здесь априорно принимается следующее предположение: программы с большей длиной – более трудоемкие.

Исходя из этого предположения приоритеты программам присваиваются на основе формулы

,

где [x] – целая часть X; L_n – длина программы в байтах;

L_q – число байтов, передаваемых между оперативной и внешней памятью за время q, равное минимальной длительности кванта.

Отношение определяет число квантов времени, необходимых для загрузки программы в оперативную память и для вывода ее из оперативной памяти. Работа с приоритетом r заносится в очередь O_p. Очередям с номерами p=1, ... , n выделяются кванты времени длительности

q_p=2^p-1q,

где q – квант времени, выделяемый для работ из очереди O₁ .

Таким образом, очередям O₁,O₂, O₃, O₄,... соответствуют кванты времени q,2q,4q,8q,... Увеличение кванта времени на выполнение работ с большой трудоемкостью способствует сокращению числа прерываний работы процессора и числа пересылок программ между оперативной и внешней памятью.

Вопросы

1.Что используется в системах оперативной обработки в качестве критерия эффективности?

n среднее время обслуживания заявок;

n вероятность прихода заявки;

n число пришедших заявок.

2.Как назначаются задачи на решение в алгоритме SPT?

n в порядке убывания времени решения;

n в порядке не убывания времени решения;

n в порядке прихода.

3.К чему приводит перемещение вперед задачи с меньшим временем решения в алгоритме SPT?

n уменьшению среднего времени обслуживания;

n увеличению среднего времени обслуживания;

n ни к чему не приводит.

4.Что такое алгоритм RR(round-robin)?

n алгоритм нахождения минимального среднего времени ответа заявки;

n алгоритм нахождения вероятности прихода заявки;

n алгоритм циклического обслуживания.

5. Для обслуживания конкретной заявки по алгоритму RR отводится постоянный квант времени. Если работа выполняется за этот квант, то она

n переходит в следующую очередь;

n поступает в конец очереди;

n покидает систему.

6. Зависит ли среднее время ожидания задачи от трудоемкости при обслуживании задач в порядке поступления без прерываний?

n да;

n нет;

n частичная зависимость.

7. С увеличением трудоемкости задачи в алгоритме RR время ожидания обслуживания

n возрастает;

n остается неизменным;

n убывает.

8.Что такое алгоритм FB(foreground-background)?

n алгоритм циклического планирования;

n алгоритм многоуровневого циклического планирования;

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

9. В алгоритме FB при поступлении в систему заявок более высокого приоритета процесс обработки менее приоритетных заявок

n прерывается;

n продолжается;

n прерывается и обращается к следующей заявке.

10. Свопинг это

n процесс завершения работы системы;

n процесс перемещения задач во внешнюю память;

n процесс циклического замещения программ.

Задание

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

2. Смоделировать реализацию алгоритма SPT через алгоритм RR.

3. Построить характеристику I и II системы:

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

– степень загрузки процессора - вероятность занятого состояния.

Входными данными являются :

– вероятность прихода заявки (R);

– длительность решения задачи (L).

Вариант	Задание
	R=40; L=5; LK<3
	R=50; L=6; LK<3
	R=60; L=7; LK<4
	R=70; L=8; LK<4
	R=40; L=7; LK<4
	R=60; L=6; LK<3
	R=50; L=5; LK<3
	R=70; L=9; LK<5
	R=80; L=7; LK<4
	R=60; L=4; LK<3
	R=50; L=7; LK<4
	R=70; L=7; LK<4

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

5.1. Титульный лист

5.2. Наименование и цель работы

5.3. Отчет по заданию

5.4. Выводы по работе

Лабораторная работа №2

Разработка и исследование планировщиков

Цель и порядок работы

Цель работы : Разработать и провести сравнительный анализ работы планировщиков с алгоритмами Макнотона и LPT.

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

- ознакомиться с описанием лабораторной работы;

- выполнить задание раздела 3;

- ответить на контрольные вопросы теста;

- оформить отчет согласно указаниям раздела 4.

- представить результаты работы преподавателю.

Общие сведения

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

Алгоритм Макнотона

Рассмотрим систему с n идентичными процессорами, на которой необходимо решить L независимых задач; каждая задача решается одним процессором в течение времени

t i, i = 1 ,..., L. Требуется найти алгоритм, который для каждого данного пакета (набора) строил бы расписание решения задач на процессорах системы, обеспечивающее минимально возможное время решения. При этом достигается максимально возможная производительность системы. Например, в случае 2-процессорной системы и набора задач с временами (3,3,2,2,2) возможны различные варианты назначения задач на решение. Приведем некоторые из них:

a)

б)

T = T0 = θ

с)

Очевидно, что наилучший в смысле минимизации общего времени решения задач - вариант c, для которого время Т решения пакета задач совпадает с соответствующим оптимальным значением Т0и в данном случае равно величине

q = max { max ti , 1/n *å ti }

Величина q является нижней границей для оптимального значения Т0. Действительно, длина Т любого расписания не может быть меньше ни max ti - максимального из времен решения задач пакета П, ни величины (1/n *å ti ) , дающей длину расписания в том случае, когда до момента завершения решения последней из задач пакета ни один процессор не простаивает, т.е. все процессоры имеют 100% загруженности.

В общем случае даже при n = 2 задача поиска оптимального значения Т при условии решения задач, является NP-трудной, т.е. все известные алгоритмы ее решения имеют трудоемкость, экспоненциально зависящую от L. Однако, если допустить возможность прерывания решения задач пакета до завершения их обслуживания, то могут быть предложены полиномиально-трудоемкие алгоритмы, приводящие к расписанию оптимальной длины Т0. При этом считается, что после прерывания решение задачи может быть возобновлено с точки прерывания на любом процессоре, не обязательно на том, на котором она первоначально решалась. Число прерываний должно быть по возможности меньшим, так как с каждым актом прерывания связаны потери машинного времени на загрузку-выгрузку задач из оперативной памяти.

Рассмотрим предложенный Макнотоном в 1959 г. алгоритм построения оптимального по длине расписания с не более чем n-1 прерываниями.

Алгоритм Макнотона заключается в предварительном упорядочении задач по убыванию времени решения и назначении задач последовательно по порядку номеров одну за другой на процессоры системы справа налево от уровня q.

Пример

n=2,L=4, времена решения задач:(5,4,3,2). Тогда

q = max {5 , 1/2 *(5+4+3+2) } =7.

И расписание, полученное в соответствии с алгоритмом Макнотона,

имеет следующий вид:

В данном случае число прерываний равно единице.

Покажем, что n-1 (максимальное число прерываний для расписания, полученного в соответствии с алгоритмом Макнотона) является достижимой границей числа прерываний.

Для доказательства этого построим такой пример пакета задач, для которого алгоритм Макнотона дает расписание с числом прерываний n-1.

Пусть L=n+1 и ti = n, i= 1, n+1.

Тогда q = max { n , 1/n * (n+1)*n = n+1, а расписание, получаемое в соответствии с алгоритмом Макнотона, имеет вид:

T=n+1=q

Число прерываний в этом случае, как видно, равно n-1,что и требовалось показать. Покажем теперь, что любое оптимальное расписание для этого пакета задач также имеет не менее n-1 прерываний. Очевидно, что в любом оптимальном расписании ни один процессор не простаивает на интервале [0,n+1]. Предположим, что существует некоторое оптимальное расписание с числом прерываний, меньшим n-1. Тогда по крайней мере 2 процессора (предположим для определенности Pk и Pl ) обслуживают заявки без прерываний. Очевидно эти процессоры обслуживают некоторые задачи Zik и Zil в интервале [0,n] без прерываний (если решение этих задач начинается позже момента времени t=0, значит до этого момента на этих процессорах решались некоторые другие задачи, решение которых прерывается в моменты начала решения задач Zik и Zil ). Найдутся моменты времени t, t`, такие, что n £ t < t` £ n+1, и в интервале [ t , t` ] хотя бы один процессор простаивает, а потому рассматриваемое решение не может быть оптимальным.

Так как мы пришли к противоречию, делаем вывод о том, что предположение о числе прерываний, меньшем n-1 , в оптимальном расписании ложно.