Имя материала: Информационные системы и технологии в экономике

Автор: Т.П. Барановская

4.6. управление ресурсами вычислительных систем

 

4.6.1.   ОДНОПРОЦЕССОРНЫЕ СИСТЕМЫ ОПЕРАТИВНОЙ ОБРАБОТКИ

 

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

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

Алгоритм RR. Простейшее правило планирования работ, обес-

печивающее выполнение указанного требования, задается алго-

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

RR (Round-Robin).

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

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

Заявки на выполнение работ поступают в очередь (рис. Работы, стоящие в очереди      получают квант процессорного

 

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

Применяются модификации алгоритма различающиеся по

величине квантов времени, предоставляемых заявкам из разных

очередей. Возможно планирование на основе постоянной вели-

чины кванта или с использованием квантов переменной длитель-

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

Одна из таких модификаций — алгоритм планирования ЕВ с уче-

том приоритетов работ. поступающие в систему, раз-

деляются в зависимости от приоритетов 1    п на и потоков /) ..../„.

Приоритеты задач т.е. поступление в систему за-

явки более высокого приоритета не прерывает процесс обработ-

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

более приоритетные заявки будут назначены в первую очередь.

Работы с высшим приоритетом поступают в очередь а рабо-

ты с низким приоритетом — в очередь Работам, выбираемым

на обслуживание из разных       выделяются кванты време-

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

заявкам из очереди От_і,т = 2.п.

Приоритеты работам могут назначаться исходя из трудоем-

кости последних. Если трудоемкости работ известны хотя бы

приближенно, то работам с большой трудоемкостью присваива-

ются низкие приоритеты и они сразу же поступают в

соответствующего в которых получают большие

кванты времени. В результате этого трудоемкие работы не будут

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

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

завышен, то после окончания    для нее кванта време-

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

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

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

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

где [х]

 

p = [og2(LnILq+l)l

целая часть X;

длина программы в байтах;

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

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

 

4.6.2.  МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ ПРИ ОБРАБОТКЕ ПАКЕТОВ ЗАДАЧ С ПРЕРЫВАНИЯМИ

 

Рассмотрим систему с п идентичными процессорами, с помо-

щью которой необходимо решить L независимых задач; каждая

задача решается одним процессором в течение времени ?,, = 1

,... , L. Требуется найти алгоритм, который для каждого данного

пакета (набора) задач строил бы расписание решения задач на

процессорах системы, обеспечивающее минимально возможное

время решения. При этом достигается максимально возможная

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

стеме и при наборе задач с временем их       3; 3; 2; 2; 2 воз-

можны различные варианты назначения задач на решение. Приведем некоторые из них (рис. 4.19).

Очевидно, что наилучший в смысле минимизации общего времени решения задач вариант в, для которого время Т решения пакета задач совпадает с соответствующим оптимальным значе-ниєм Т = То = 0 и в данном случае равно величине 8 = max {max tt, (1/л)

Величина является нижней границей для оптимального зна-

чения Действительно, длина Т любого расписания не может

быть меньше ни max — максимального из времен решения за-

дач пакета, ни величины определяющей длину расписа-

ния в том случае, когда до момента завершения решения после-

дней из задач пакета ни один процессор не простаивает, т.е. все

процессоры имеют 100 \%-ную загруженность.

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

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

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

прерываниями.

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

Примем: и = 2, L - 4, время решения задач: 5; 4; 3; 2. Тогда 0 = max {5, 1/2 • (5 + 4 + 3 + 2)} = 7; а расписание, полученное в соответствии с алгоритмом Макнотона, имеет вид, показанный на рис. 4.20.

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

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

 

Подпись:

 

5 10

5          10 Г

Рис. 4.20. Оптимальное расписание

 

15

15

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

Пусть: L = п + 1иґ,-= п, і-,п + 1.

Тогда: 8 = max {п ,/п (п + 1)и} = п + 1, а расписание, получаемое в соответствии с алгоритмом Макнотона, имеет вид, показанный на рис. 4.21.

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

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

 

4.6.3.  МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ ПРИ ОБРАБОТКЕ ПАКЕТОВ НЕЗАВИСИМЫХ ЗАДАЧ БЕЗ ПРЕРЫВАНИЙ

 

Рассмотрим систему, содержащую п идентичных процессоров, , на которой необходимо решить без прерываний набор из L независимых задач с временами решения i = 1,... , L. Получение расписания с минимальным временем решения и в этом случае является NP-трудной задачей. Один из наиболее эффективных и нетрудоемких алгоритмов организации таких

LPT (Longest-Processing Task first — самая длинная задача решается первой), являющийся частным случаем алгоритма критического пути для независимых задач. Суть этого алгоритма заключается в назначении задач в порядке убывания времени решения на освобождающиеся процессоры. Сотрудником фирмы BellLaboratories, США, Грэхемом в 1967 г. был получен следующий результат: при использовании алгоритма LPT для распределения любого пакета П = {Z,} независимых задач без прерываний в системе с п идентичными процессорами справедливо:

Г<(4/3~]/Зп)Г0,

где   Т — время решения пакета П при распределении задач алгоритмом LPT;

Приведенная оценка является наилучшей.

ТЬ  — длина оптимального расписания. Очевидно, что

4.6.4. ПРОИЗВОДИТЕЛЬНОСТЬ МУЛЬТИПРОЦЕССОРНЫХ СИСТЕМ С ОБЩЕЙ И ИНДИВИДУАЛЬНОЙ ПАМЯТЬЮ

 

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

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

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

Наиболее существен в структурной организации МПС способ связи между процессорами и памятью системы. В этом аспекте МПС разделяются на МПС с памятью общей (полнодоступной) и индивидуальной (раздельной).

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

Структура МПС с общей памятью наиболее универсальна: любая информация, хранимая в памяти системы, в равной степени доступна любому процессору и каналу ввода-вывода. цательное свойство МПС с общей памятью — большие затраты оборудования в коммутаторах (эти затраты пропорциональны произведению числа устройств, подключенных к памяти, и числа модулей памяти).

В МПС с индивидуальной памятью каждый из процессоров

обращается в основном к своему модулю памяти. Для обмена

данными между подсистемами "процессор — модуль памяти" в

процессорах предусмотрены блоки обмена, обеспечивающие пе-

редачу сегментов информации между общей памятью и модулем

памяти. При этом блок обмена может работать как селекторный

канал: операция обмена инициируется процессором, и передача

данных выполняется с параллельной работой последнего. Прин-

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

в интенсивно используемом канале "процессор — модуль памя-

ти", вследствие чего увеличивается номинальное быстродействие

процессоров и        затраты оборудования по сравне-

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

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

 

5-1909

МПС С ОБЩЕЙ ПАМЯТЬЮ

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

В модели МПС с обшей памятью процесс обслуживания заявок в режиме разделения нагрузки можно рассматривать как процесс функционирования одной многоканальной системы массового обслуживания (рис. 4.22) с интенсивностью входящего потока заданий X, общей очередью О, заявки из которой выбираются в порядке поступления их в систему, и средней длительностью обслуживания заявки каждым из процессоров Прі,..., Прдг, равной 6. Заявка, поступающая в систему, содержащую N процессоров, при наличии хотя бы одного свободного процессора немедленно принимается последним на обслуживание. Если все процессоры заняты обслуживанием ранее поступивших заявок, поступающая заявка размещается в очереди.

Определим характеристики МПС на основе модели, показанной на рис. 4.22.

Пусть в МПС поступает М потоков с интенсивностями Х,...,Хм. Обслуживание заявок сводится к выполнению соответствующих программ, средние трудоемкости которых равны ©1,...7©М операций в расчете на один прогон программы. Примем, что обслуживание заявок выполняется на основе дисциплины FIFO. В таком случае можно считать, что система обслуживает однородный поток заявок, поступающих с интенсивностью

м

Для обслуживания любой заявки из суммарного потока требуется в среднем

м

0 = £(VA)©i 1=1

процессорных операции.

Примем, что заявка, поступившая на обслуживание, захватывает процессор до полного завершения обслуживания. В таком случае средняя длительность обслуживания заявки процессором с быстродействием В равна 9 = 0 IB, а интенсивность обслуживания заявок одним процессором =1/9.

Параметры системы Л, N и 9 = 0 IB должны отвечать условию существования стационарного режима, при котором в очереди пребывает конечное число заявок и, следовательно, конечны времена ожидания и пребывания заявок. На каждый из процессоров поступает N-я доля заявок, и поэтому отдельный процессор обслуживает поток с интенсивностью       . Загрузка процессора

 

где ц.£ =Ці — суммарная интенсивность обслуживания заявок TV-процессорной системой.

Стационарный режим существует, если р < 1. Следовательно, параметры МПС должны отвечать соотношению Х01 (NB) < 1.

Характеристики системы можно получить в явной аналитической форме, если принять предположение о том, что входящий поток заявок — пуассоновский и длительность обслуживания распределена по экспоненциальному закону со средним 9.

В теории массового обслуживания доказывается, что при указанных предположениях вероятность пребывания в системе N — 0,1,2,... заявок, обслуживаемых процессорами и стоящих в очереди

Подпись:

 

где

 

(4.1)

 

(4.2)

есть вероятность того, что в системе нет ни одной заявки, т.е. все N процессоров простаивают; R — суммарная загрузка TV-канальной системы:

Подпись:
Суммарная загрузка R в отношении TV-канальной системы массового обслуживания определяет среднее число каналов, которые заняты обслуживанием заявок. Для стационарного режима R

Подпись:

 

(4.4)

Подпись:

 

(4.5)

где p = A/(N)y. — загрузка процессора N-процессорной системы.

Характер изменения вероятностей Рп при изменении суммар-

ной загрузки            системы представлен    рис. 4.23.

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

сдвигается в сторону больших N. Распределение (4.4) содер-

жит всю информацию, необходимую для определения характери-

стик    Средняя длина очереди заявок, ожидающих обслужи-

вания в         системе, находится исходя из форму-

лы (4.4) как математическое ожидание случайной величины

i = n-N > 0, равной числу заявок в очереди:

Подпись:

 

(4.6)

где Ро определяется из формулы (4.5).

 

Среднее число заявок, пребывающих в системе:

 

 

(4.7)

где  / — среднее число заявок, находящихся в очереди, определяемое выражением (4.6);

R  — суммарная загрузка МПС, определяемая выражением (4.3).

или с использованием формулы (4.3)

 

Для систем без потерь заявок среднее время ожидания W и среднее время пребывания и заявок в системе равны соответственно W - 1 /Л и и - ml К. Подставляя в эти соотношения выражения (4.6) и (4.7), получим:

Одна из важных характеристик системы — вероятность ненулевого ожидания заявок Pr (W > 0), т.е. вероятность того, что в момент поступления очередной заявки все N процессоров заняты обслуживанием. Эта вероятность равна:

Из сравнения формул (4.8) и (4.9) вытекает следующее выражение для среднего времени ожидания заявок:

В свою очередь, вероятность нулевого ожидания заявок, т.е. вероятность того, что в момент поступления заявки хотя бы один процессор свободен, равна: .Р,.( W - 0) ч 1 - Pr(W> 0). 134

МПС С ИНДИВИДУАЛЬНОЙ ПАМЯТЬЮ

 

В МПС с индивидуальной памятью множество программ обслуживания и связанных с ними данных Р = {Р,...,Рм} разделяется на подмножества Op..., QN, Q, = {Ра,---> Рсо} £ P(i = 1,---, N), размещаемые в памяти соответствующих процессоров Прі,...,Прдг. В результате этого каждый из процессоров ориентируется на обслуживание заявок определенных типов, а именно тех, программы обслуживания которых размещены в памяти процессора. Режим работы МПС, при котором каждый из процессоров обслуживает заявки определенных типов и не может обслуживать заявки других типов, называется режимом разделения функций.

Рассмотрим модель МПС с индивидуальной памятью. В наиболее простом случае процессоры обмениваются информацией с общей памятью. Количество информации, передаваемой при обменах, может быть столь незначительно, что допустимо пренебречь влиянием процессов обмена на процесс обслуживания заявок. В таком случае можно считать, что процессоры функционируют независимо и работу jV-процессорной системы в режиме разделения функций можно рассматривать как процесс функционирования N одноканальных систем массового обслуживания (рис. 4.24). Каждая из систем массового обслуживания состоит из потока заявок, поступающих с интенсивностью Я/, очереди О/ и процессора

 

Поток заданий ^

Для этой модели характеристики обслуживания заявок каждого типа могут быть вычислены в предположении, что входящие потоки — пуассоновские при произвольном распределении длительностей обслуживания и различных дисциплинах обслуживания заявок. В частности, при экспоненциальном распределении длительности обслуживания и дисциплине FIFO среднее время ожидания заявок в системе с номером і = 1,...,jVh загрузкой Pi = X/ / )і/ < 1 равно:

 

 

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

щ =Wi+9i=U/(~pi)ei

(4.10) (4.11)

среднее число заявок в очереди = = /(1 - и среднее число заявок в системе     =      =    / (1 pi).

МПС как единый объект обслуживает суммарный поток заявок, поступающий на вход системы с интенсивностью

Подпись:
Заявка из суммарного потока с вероятностью X, / Л будет ожидать обслуживания в среднем единиц времени. С учетом этого среднее время ожидания заявки из суммарного потока определяется выражением:

N

(4.12)

Аналогично определяется среднее время пребывания заявки системе:

в

Подпись:

(4.13)

В случае, когда каждый из процессоров обслуживает точно часть суммарного потока заявок и средняя длительность обслуживания одинакова для всех процессоров и равна 9. В таком случае Х = ...— Xn = Л / п и pi = ...= рдг = р. При равномер-

ном распределении нагрузки из выражений (4.12) и (4.10), а так-

же (4.13) и    следует, что средние времена ожидания и пре-

бывания заявок равны соответственно:

W = [pi{-pm

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 |