Тема 4.6. Эффективность программ

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

Возможности увеличения быстродействия.

Методы распределения ресурсов в вычислительных системах

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

Пер­вым важнейшим показателем, характеризующим вычислитель­ные системы (ВС), является их производительность. При форму­лировании любой задачи необходимо сопоставлять произво­дительность доступной ВС с необходимыми затратами времени для решения данной задачи или допустимой длительностью ожидания результатов (длительностью отклика). Существенный ограничивающий фактор — длительность, в течение которой ЭВМ можно представить для решения данной задачи, или то реальное время, в пределах которого целесообразно получить результаты для их использования. Поэтому для всех типов систем актуальной является проблема распределения ограни­ченной производительности ВС для решения функциональных задач и применения методов эффективной организации вы­числительного процесса (см. этап 2 на рис. 1.3) [7, 13, 24].

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

Разнообразие видов памяти, значительно различающихся по быстродействию и стоимости хранения единицы информации, привело к применению в ВС многоуровневых систем памяти. Каждый последующий уровень памяти характеризуется сниже­нием быстродействия и увеличением возможного объема храни­мых данных. Задача состоит в определении объемов памяти каж­дого уровня, обеспечивающих хранение заданного объема ин­формации при минимальном времени обращения к любым дан­ным и ограниченной стоимости всей памяти. Характеристики памяти непосредственно влияют на производительность ВС, и их приходится анализировать совместно. В общем случае в реаль­ном времени производительность ВС — более критичный пара­метр, чем объем памяти. Методы и средства распределения вычислительных ресурсов и организации вычислительного процесса можно классифицировать по степени неопределенности априор­ной информации об основных динамических характеристиках поступления сообщений и их обслуживания.

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

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

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

Рис. 3.2

 

 

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

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

При анализе обслуживания в большинстве практических слу­чаев можно удовлетвориться основными характеристиками слу­чайных величин — их первыми двумя моментами. При этом зна­чение средней длительности обслуживания Г, заявки i-го типа или интенсивности обслуживания ц, == Tг^\ важны не своими аб­солютными величинами, а в сопоставлении с интенсивностью то­го же потока и относительно длительностей обслуживания заявок других типов. Программы второго типа характеризуются средне-квадратическим отклонением длительностей обслуживания, со­измеримым или меньшим среднего значения. Это означает, что коэффициент вариации v-i == д/ Di/Ti ^ 1, где D, — дисперсия дли­тельности обслуживания.

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

Третий тип программ (рис. 3.3, в). Вследствие большого ко­личества неконтролируемых факторов иногда невозможно клас­сифицировать длительности реализации заявок различных типов по некоторым априорным признакам вызываемых программ. Ина­

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

Оперативная память. Общее распределение опера­тивной памяти ВС на зоны различного функционального назна­чения представлено укрупненно на рис 3.2. В зависимости от назначения зон их объем при анализе может выражаться в различных единицах. Однако при совместном распределении всех ресурсов оперативной памяти приходится приводить все характеристики к количеству слов или байтов.

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

             ______общее число ячеек буферной зоны памяти______

число ячеек для запоминания одного сообщения или заявки

Во всех реальных системах объем буферной памяти ограни­чен 1 < r < оо. При достаточно большом объеме буферной па­мяти это ограничение не является определяющим для обработки заявок и качество обслуживания полностью зависит от длитель­ности ожидания. Тогда можно полагать г = оо и качество об­служивания заявок оценивается использованием производитель­ности ВС. В большинстве ВС реального времени объем буфер­ной памяти ограничен количеством сообщений г w 50...100. При большом объеме буферных накопителей возможно столь длитель­ное хранение сообщений или заявок, что их обработка может терять смысл либо из-за поступления более свежей информации того же типа, либо вследствие практически полной потери цен­ности долго ожидающих сообщений.

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

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

Методы распределения ресурсов ВС. Применение тех или иных методов распределения ресурсов зависит в первую очередь от динамических характеристик использования ВС и от степени связи функционирования ВС с реальным временем [2, 7, 13].

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

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

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

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

Распределение производительности вычислительных систем методами теории расписаний. В ряде ВС состав решаемых за­дач и длительность их решения можно считать достаточно известными и не зависящими от случайных факторов. Это поз­воляет рассматривать распределение ресурсов ВС как строго детерминированную задачу, которую можно сформулировать в понятиях теории расписаний и решать методами этой теории при следующих предположениях [13], когда:

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

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

из-за отсутствия прореживания потока заявок при неограни­ченной буферной памяти в однопроцессорной ЭВМ ограничена суммарная загрузка: р < 1;

одна ЭВМ может одновременно решать только одну задачу и не допускается прерывание до полного завершения реализации заявки на задачу.

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

Бесприоритетные дисциплины. При отсутствии априорной информации о характеристиках заявок и их обслужи­вании нет причин для предпочтения каким-либо из них. Порядок обслуживания в этом случае может быть случайным или учиты­вать последовательность поступления заявок. Простейшими ва­риантами являются обслуживание по принципу «первым при­шел—первым обслужен» (s=l) или «последний пришел— первый обслужен». Практически наиболее целесообразно приме­нять обслуживание в порядке поступления заявок, поэтому ниже эта дисциплина используется как основная бесприоритетная, с которой сопоставляются характеристики других дисциплин.

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

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

Приоритетные дисциплины. Если характеристики обслуживания заявок различны (в зависимости от их типа или источника), то появляется возможность предпочтения при об­служивании некоторых из них. Наиболее четко особенности приоритетного обслуживания проявляются при анализе дис­циплин с относительными (s = 2) и с абсолютными (s = 3) приоритетами. Эти дисциплины в наибольшей степени различают­ся по использованию априорных сведений о характеристиках обслуживания обрабатываемой и поступивших заявок. Такими данными являются средняя длительность обслуживания заявки соответствующего типа и штраф за ожидание в очереди.

Дисциплина с относительными приорите­тами (s = 2) характеризуется тем, что заявки упорядочи­ваются и обслуживаются в зависимости от средней длитель­ности обслуживания и штрафа за ожидание в очереди. Основ­ным показателем, используемым для распределения типов заявок по приоритетным уровням, является отношение а./Г; штрафа за единицу времени ожидания (а;) в очереди к средней длитель­ности обслуживания (Г,) заявок данного типа. При этой дисцип­лине дисперсия и другие характеристики длительностей обслу­живания на эффективность дисциплины не влияют и обслужива­ние любой заявки не прерывается.

Дисциплина с абсолютными приоритетами (s == 3) характеризуется прерыванием обслуживания любой заявки при появлении заявки более высокого приоритета с по­следующим продолжением прерванного обслуживания после за­вершения обслуживания заявки высшего приоритета. Распре­деление типов заявок по приоритетным уровням, так же как и в предыдущем случае, является априорным в соответствии со значениями отношения о./Г,. Однако в этом случае на эффек­тивность дисциплины, оказывает влияние дисперсия длительно­стей обслуживания.

 

Критерии и эффективность распределения производительности в вычислительных системах

Критерии эффективности распределения ресурсов в ВС. Ре­альные ограничения на производительность и другие характе­ристики ВС приводят к ожиданию результатов или к неполному

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

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

ерациональности применения дисциплин с абсолютными приорите­тами.

Распределение памяти в вычислительных системах

Принципы распределения буферной памяти для приема и вы­дачи сообщений. Для исключения связи во времени процессов приема сообщений и их обработки применяются буферные на­копители, объем которых ограничен. При выдаче сообщений внешним абонентам буферные накопители используются для вре­менного хранения сообщений, необходимого из-за несинхронной подготовки сообщений и освобождения каналов связи. Эффек­тивность использования ограниченных буферных накопителей прежде всего зависит от их структурного построения и распре­деления имеющейся памяти на зоны (см. этап 2 на рис. 1.3). Кроме того, на эффективность существенно влияют дисциплины заполнения памяти заявками-сообщениями и их передачи из на­копителей на обработку [13, 17].

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

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

 

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

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

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

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

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

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

Принципы распределе­ния многоуровневой па­мяти. Использование ие­

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

Затраты на организацию обмена данными между запоминаю­щими устройствами различных уровней приводят к снижению производительности ВС на 20...50 % по сравнению с производи­тельностью процессора, использующего память только верхних иерархических уровней (оперативную и сверхоперативную). Это определило широкое использование оптимизации распределения памяти на основе показателей производительность — стоимость. 'Для решения этой задачи проводится анализ [2, 7, 17]: распре­деления памяти по уровням иерархии; динамики вызова и заме­щения массивов данных (страниц) в оперативной памяти; эф­фективности взаимодействия в двухуровневой (в основном вра­щающейся) памяти.

Распределение памяти по иерархическим уровням. Одна из задач использования многоуровневой памяти состоит в опти­мальном выборе объемов памяти различных типов. Для этого среднее время обращения сводится к минимуму при заданной ограниченной стоимости ВС или минимизируется стоимость си­стемы при заданном среднем времени обращения за информаци­ей. Предполагается, что устройства памяти образуют иерархи­ческую систему, компоненты которой известны и различаются временем выборки и стоимостью единицы хранения, а также объемом одного блока [13]. Для оптимизации необходимо за­дать объем памяти, используемой для хранения программ и дан­

ных каждой задачи, а также их «активность» или частоту вызо­ва на решение.

Дисциплины замещения страниц при многоуровневой памяти. Использование многоуровневой памяти предполагает, что на выс­шем уровне памяти может размещаться некоторая ограниченная часть программ с используемыми ими массивами данных. Про­граммы, размещенные во внешней памяти, перед исполнением должны быть переписаны в оперативную память, что приводит к дополнительным затратам времени. Требующаяся программа переписывается из внешней памяти и «вытесняет» из оперативной памяти какую-либо из находящихся в ней. Возникает задача выбора дисциплины замещения программ и обмена с внешней памятью, позволяющей сократить затраты, обусловленные огра­ниченным объемом оперативной памяти [13, 21].

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

Основной характеристикой процесса обмена является вероят­ность смены страницы, т. е. вероятность такого события, когда

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

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

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

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

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

В тех случаях, когда программы независимы и одинакового объема, отсутствуют ограничения на использование оперативной памяти и каждая программа вызывается регулярно с заданным темпом, доказано, что в оперативной памяти следует замещать программу, к которой следующее обращение произойдет через максимальный интервал времени. В простейшем случае предпола­гается, что все заявки случайны, программы независимы и имеют равную длину. Количество программ, находящихся в оперативной памяти, определяется ее объемом и характеризуется количеством одинаковых участков от, достаточных для размещения каждой программы. Общее количество программ п~>т и программы, не помещающиеся в оперативной памяти, размещаются во внешней памяти. При появлении заявки на программу, отсутствующую в оперативной памяти, определяется программа, подлежащая удалению, и фиксируется обмен с внешней памятью. В этом случае оптимальной (ОПТ на рис. 3.13) является дисциплина, при которой программы с наибольшей вероятностью вызова постоянно разме­щены в оперативной памяти, и выделен единственный участок. оперативной памяти, в который записываются по мере вызова все остальные программы. Таким образом, для обмена целесооб­разно использовать только один участок оперативной памяти, а все остальные участки могут быть, в принципе, заменены постоянной полнодоступной памятью с неизменными программами.

Содержание