4.6. УПРАВЛЕНИЕ РЕСУРСАМИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

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

В системах обработки данных в качестве основного критерия эффективности используется среднее время обслуживания заявок. При оперативной обработке вычислительных задач невозможно проводить одновременно и их сортировку. Задачи с различной длительностью решения поступают на процессор в случайном по­рядке. В связи с этим невозможно использовать режим SPT (Shortest-Processing-Task-first), назначающий задачи на решение в порядке убывания времени их решения. В реальных системах оперативной обработки априорная информация о времени ре­шения задач, как правило, отсутствует. Чтобы воспользоваться принципами планирования на основе алгоритма SPT, в систему вводятся средства, которые выявляют короткие и длинные рабо­ты непосредственно в ходе вычислительного процесса.

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

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

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

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

 

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

Применяются модификации алгоритма РВ, различающиеся по величине квантов времени, предоставляемых заявкам из разных очередей. Возможно планирование на основе постоянной вели­чины кванта или с использованием квантов переменной длитель­ности, которая возрастает по мере увеличения номера очереди. Одна из таких модификаций — алгоритм планирования ЕВ с уче­том приоритетов работ. поступающие в систему, раз­деляются в зависимости от приоритетов 1  п на и потоков /)..../„.

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

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

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

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

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

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

 

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

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

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

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

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

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

 

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

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

Рассмотрим систему с п идентичными процессорами, с помо­щью которой необходимо решить Ь независимых задач; каждая задача решается одним процессором в течение времени ?,, і = 1 ,..., Ь. Требуется найти алгоритм, который для каждого данного пакета (набора) задач строил бы расписание решения задач на процессорах системы, обеспечивающее минимально возможное время решения. При этом достигается максимально возможная производительность системы.         в двухпроцессорной си­

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

Очевидно, что наилучший в смысле минимизации общего вре­мени решения задач вариант в, для которого время Т решения пакета задач совпадает с соответствующим оптимальным значе­нием '/ = То = 0 и в данном случае равно величине 0 = max {max //, (1/") ЪЦ}.

Величина в является нижней границей для оптимального зна­чения 7о. Действительно, длина Тлюбого расписания не может быть меньше ни max // — максимального из времен решения за­дач пакета, ни величины                определяющей длину расписа­ния в том случае, когда до момента завершения решения после­дней из задач пакета ни один процессор не простаивает, т.е. все процессоры имеют 100 %-ную загруженность.

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

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

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

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

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

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

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

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

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

Пусть: L = п + 1 и tj= п, i - 1, п + 1.

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

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

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

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

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

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

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

Го — длина оптимального расписания.

Очевидно, что

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

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

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

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

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

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

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

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

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

нию с системами с общей памятью.                        послед­

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

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

5-1909

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

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

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

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

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

м

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

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

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

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

где = АТ(х — суммарная интенсивность обслуживания заявок ТУ-про- цессорной системой.

 

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

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

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

 

(4.1)

(4.2)

 

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

R = A/^l = NA/N|Л = Np.

Суммарная загрузка Я в отношении ТУ-канальной системы массового обслуживания определяет среднее число каналов, ко­торые заняты обслуживанием заявок. Для стационарного режи­ма Я<К С учетом формулы (4.3) выражения (4.1) и (4.2) можно представить в виде

(4.4)

 

где р = л/(лг)ц — загрузка процессора Л^-процессорной системы.

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

Распределение числа заявок в системе носит унимодальный характер, причем с увеличением загрузки максимальное значение Р_п сдвигается в сторону больших N. Распределение (4.4) содер­жит всю информацию, необходимую для определения характери­стик МПС. Средняя длина очереди заявок, ожидающих обслужи­вания в      системе, находится исходя из форму­лы (4.4) как математическое ожидание случайной величины і = п-Ы > 0, равной числу заявок в очереди:

(4.6)

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

 

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

т = І + Я

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

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

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

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

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

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

 

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

В МПС с индивидуальной памятью множество программ об­служивания и связанных с ними данных Р = {Р\,...,Рм} разделяет­ся на подмножества Ор..-, Одг, = {Р_а,---, Рт} £Р{г = 1,..., Щ, размещаемые в памяти соответствующих процессоров Прь...,Прлг. В результате этого каждый из процессоров ориентируется на об­служивание заявок определенных типов, а именно тех, программы обслуживания которых размещены в памяти процессора. Режим работы МПС, при котором каждый из процессоров обслуживает заявки определенных типов и не может обслуживать заявки дру­гих типов, называется режимом разделения функций.

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

Для этой модели характеристики обслуживания заявок каж­дого типа могут быть вычислены в предположении, что входя­щие потоки — пуассоновские при произвольном распределении длительностей обслуживания и различных дисциплинах обслужи­вания заявок. В частности, при экспоненциальном распределе­нии длительности обслуживания и дисциплине FIFO среднее вре­мя ожидания заявок в системе с номером / = 1,...,ЛГи загрузкой рi = \ / Ц/ < 1 равно:

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

u_t = W_i+e_i=[l/(\~p_im,                                        (4.11)

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

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

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

N

W = ]T(A,MW,.                                                        _(4]2)

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

В случае, когда каждый из процессоров обслуживает точно часть суммарного потока заявок и средняя длительность обслуживания одинакова для всех процессоров и равна 9. В та­ком случае Х\ = ...— Xдт = Л / п и р1 = ...= рдт = р. При равномер­ном распределении нагрузки из выражений (4.12) и (4.10), а так­же (4.13) и (4.11) следует, что средние времена ожидания и пре­бывания заявок равны соответственно: