Тема OS27асу. Стратегия подкачки страниц Стратегии управления виртуальной памятью · стратегии выборки; · стратегии размещения; · стратегии замещения. Стратегии выталкивания страниц Принцип оптимальности Выталкивание случайной страницы Выталкивание первой пришедшей страницы (FIFO) Аномалия FIFO Выталкивание дольше всего не использовавшейся страницы (LRU) Выталкивание реже всего используемой страницы (LFU) Выталкивание не использовавшейся в последнее время страницы (NUR) Локальность Рабочие множества Подкачка страниц по запросу Подкачка страниц с упреждением Освобождение страниц Размер страниц Поведение программ при подкачке страниц   Ранее были рассмотрены различные практически реализованные способы организации виртуальной памяти, а именно: ·         страничная организация, ·         сегментная организация, ·         комбинированная странично-сегментная организация.   Мы обсуждали аппаратные и программные механизмы реализации виртуальной памяти. В настоящей главе мы рассмотрим стратегии управления системами виртуальной памяти, а также поведение этих систем при управлении в соответствии с этими стратегиями.   9.2 Стратегии управления виртуальной памятью В главе, посвященной реальной памяти, рассматривались стратегии управления вталкиванием (выборкой), размещением и выталкиванием (замещением) информации. Здесь мы рассмотрим их заново применительно к системам виртуальной памяти. Стратегии вталкивания. Их цель - определить, в какой момент следует переписать страницу или сегмент из вторичной памяти в первичную. Вталкивание по запросу (по требованию) предполагает, что система ждет ссылки на страницу или сегмент от выполняющего процесса и только после появления ссылки начинает переписывать данную страницу или сегмент в первичную память. Вталкивание с упреждением (опережением) предполагает, что система пытается заблаговременно определить, к каким страницам или сегментам будет обращаться процесс. Если вероятность обращения высока и в первичной памяти имеется свободное место, то соответствующие страницы или сегменты будут переписываться в основную память еще до того, как к ним будет явно производиться обращение. Стратегии размещения. Их цель — определить, в какое место первичной памяти помещать поступающую страницу или сегмент. В системах со страничной организацией решение о размещении принимается достаточно тривиально, поскольку поступающая страница может быть помещена в любой свободный страничный кадр. Системы с сегментной организацией требуют стратегий размещения, аналогичных тем, которые мы обсуждали применительно к системам мультипрограммирования с переменными разделами. Стратегии выталкивания. Их цель — решить, какую страницу или сегмент следует удалить из первичной памяти, чтобы освободить место для помещения поступающей страницы или сегмента, если первичная память полностью занята.   9.3 Стратегии выталкивания страниц В системах со страничной организацией все страничные кадры бывают, как правило, заняты. В этом случае программы управления памятью, входящие в операционную систему, должны решать, какую страницу следует удалить из первичной памяти, чтобы освободить место для поступающей страницы. Мы рассмотрим следующие стратегии выталкивания страниц. ·         Принцип оптимальности. ·         Выталкивание случайной страницы. ·         Первой выталкивается первая пришедшая страница (FIFO). ·         Первой выталкивается дольше всего не использовавшаяся страница (LRU). ·         Первой выталкивается наименее часто использовавшаяся страница (LFU). ·         Первой выталкивается не использовавшаяся в последнее время страница (NUR). ·         Рабочее множество.   9.3.1 Принцип оптимальности Принцип оптимальности (De70) говорит о том, что для обеспечения оптимальных скоростных характеристик и эффективного использования ресурсов следует заменять ту страницу, к которой в дальнейшем не будет новых обращений в течение наиболее длительного времени. Можно, конечно, продемонстрировать, что подобная стратегия действительно оптимальна, однако реализовать ее, естественно, нельзя, поскольку мы не умеем предсказывать будущее. В связи с этим для обеспечения высоких скоростных характеристик и эффективного использования ресурсов мы попытаемся наиболее близко подойти к принципу оптимальности, применяя различные методы выталкивания страниц, приближающиеся к оптимальному.   9.3.2 Выталкивание случайной страницы Если нам нужно иметь стратегию выталкивания страниц, которая характеризовалась бы малыми издержками и не являлась бы дискриминационной по отношению к каким-либо конкретным пользователям, то можно пойти по очень простому пути - выбирать случайную страницу. В этом случае все страницы, находящиеся в основной памяти, могут быть выбраны для выталкивания с равной вероятностью, в том числе даже следующая страница, к которой будет производиться обращение (и которую, естественно, удалять из памяти наиболее нецелесообразно). Поскольку подобная стратегия по сути как бы рассчитана на «слепое» везение и похожа на подход «пан или пропал», в реальных системах она применяется редко.   9.3.3 Выталкивание первой пришедшей страницы (FIFO) При выталкивании страниц по принципу FIFO мы присваиваем каждой странице в момент поступления в основную память временную метку. Когда появляется необходимость удалять из основной памяти какую-нибудь страницу, мы выбираем ту, которая находилась в памяти дольше других. Интуитивный аргумент в пользу подобной стратегии кажется весьма весомым, а именно: у данной страницы уже были возможности «использовать свой шанс», и пора дать подобные возможности и другой странице. К сожалению, стратегия FIFO с достаточно большой вероятностью будет приводить к замещению активно используемых страниц, поскольку тот факт, что страница находится в основной памяти в течение длительного времени, вполне может означать, что она постоянно в работе. Например, для крупных систем разделения времени стандартна ситуация, когда многие пользователи во время ввода и отработки своих программ совместно используют одну копию текстового редактора. Если в подобной системе выталкивать страницы по принципу FIFO, это может привести к удалению из памяти какой-либо интенсивно используемой страницы редактора. А это будет безусловно нецелесообразно, поскольку ее почти немедленно придется снова переписывать в основную память.   9.3 3.1. Аномалия FIFO На первый взгляд кажется очевидным, что с увеличением количества страничных кадров, выделяемых процессу, этот процесс будет выполняться с меньшим количеством прерываний по отсутствию нужной страницы в памяти. Рис. 9.1 Аномалия FIFO.   Однако, как установили Билейди, Нельсон и Шедлер (Ве69b), в стратегии FIFO определенные последовательности обращений к страницам приводят в действительности к увеличению количества прерываний по отсутствию страницы при увеличении количества страничных кадров, выделяемых процессу. Это явление носит название «аномалии FIFO». Рассмотрим рис. 9.1. Самый левый столбец — это последовательность страниц, к которым обращается процесс. Первая таблица рисунка показывает, как для этой последовательности обращений страницы будут вталкиваться и выталкиваться при реализации стратегии FIFO и выделении данному процессу трех страничных кадров. Вторая таблица показывает, каким образом этот процесс будет работать при тех же самых обстоятельствах, при выделении ему четырех страничных кадров. Слева от каждой таблицы мы отмечаем, будет ли соответствующее новое обращение к странице вызывать прерывание по отсутствию страницы или нет. В действительности оказывается, что при выполнении процесса с четырьмя страничными кадрами количество прерываний по отсутствию страницы на одно больше, чем в случае трех страничных кадров, — факт, явно противоречащий интуиции. Аномалию FIFO следует, по-видимому, считать скорее курьезом, чем фактором, требующим серьезного к себе отношения. Быть может, истинное значение этого явления для студента, изучающего операционные системы, состоит в том, что оно служит дополнительным указанием на исключительную сложность операционных систем как объектов, где интуитивный подход иногда неприемлем.   9.3.4 Выталкивание дольше всего не использовавшейся страницы (LRU) Эта стратегия предусматривает, что для выталкивания следует выбирать ту страницу, которая не использовалась дольше других. Здесь мы исходим из эвристического правила, говорящего о том, что недавнее прошлое — хороший ориентир для прогнозирования ближайшего будущего. Стратегия LRU требует, чтобы при каждом обращении к странице ее временная метка обновлялась. Это может быть сопряжено с существенными издержками, и поэтому стратегия LRU, хотя она и кажется весьма привлекательной, в современных системах реализуется редко. Чаще применяются близкие к LRU стратегии, для которых характерны меньшие издержки. Разработчики операционных систем должны всегда с большой осторожностью применять эвристические правила и рассуждения. Например, при реализации стратегии LRU может быть так, что страница, к которой дольше всего не было обращений, в действительности станет следующей используемой страницей, если программа к этому моменту очередной раз пройдет большой цикл, охватывающий несколько страниц. Таким образом, выталкивая страницу, к которой дольше всего не было обращений, мы можем оказаться вынужденными почти немедленно возвращать ее обратно.   9.3.5 Выталкивание реже всего используемой страницы (LFU) Одной из близких к LRU стратегий является стратегия, согласно которой выталкивается наименее часто (наименее интенсивно) использовавшаяся страница (LFU). Здесь мы контролируем интенсивность использования каждой страницы. Выталкивается та страница, которая наименее интенсивно используется или обращения к которой наименее часты. Подобный подход опять-таки кажется интуитивно оправданным, однако в то же время велика вероятность того, что удаляемая страница будет выбрана нерационально. Например, наименее интенсивно используемой может оказаться та страница, которую только что переписали в основную память и к которой успели обратиться только один раз, в то время как к другим страницам могли уже обращаться более одного раза. Теперь работающий по принципу LFU механизм вытолкнет эту страницу, а она скорее всего сразу же будет использоваться. Таким образом, практически любой метод выталкивания страниц, по-видимому, не исключает опасности принятия нерациональных решений. Это действительно так просто потому, что мы не можем достаточно точно прогнозировать будущее. В связи с этим необходима такая стратегия выталкивания страниц, которая обеспечивала бы принятие рациональных решений в большинстве случаев и в то же время не требовала больших накладных расходов.   9.3.6 Выталкивание не использовавшейся в последнее время страницы (NUR) Один из распространенных алгоритмов, близких к стратегии LRU и характеризующихся малыми издержками, — это алгоритм выталкивания страницы, не использовавшейся в последнее время (NUR); к страницам, которые в последнее время не использовались, вряд ли будут обращения и в ближайшем будущем, так что их можно заменять на вновь поступающие страницы. Поскольку желательно заменять ту страницу, которая в период нахождения в основной памяти не изменялась, реализация стратегии NUR предусматривает введение двух аппаратных битов-признаков на страницу. Это а) бит-признак обращения = 0, если к странице не было обращений; = 1, если к странице были обращения; б) бит-признак модификации = 0, если страница не изменялась; = 1, если страница изменялась. Бит-признак модификации часто называют также «признаком записи» в страницу. Стратегия NUR реализуется следующим образом. Первоначально биты-признаки обращения и модификации для всех страниц устанавливаются в 0, При обращении к какой-либо странице ее бит-признак обращения устанавливается в 1, а в случае изменения содержимого страницы устанавливается в 1 ее бит-признак модификации. Когда нужно выбрать страницу для выталкивания, прежде всего мы пытаемся найти такую страницу, к которой не было обращений (поскольку мы стремимся приблизиться к алгоритму LRU). В противном случае у нас не будет другого выхода, как вытолкнуть страницу, к которой были обращения. Если к странице обращения были, мы проверяем, подверглась ли она изменению или нет. Если нет, мы заменяем ее из тех соображений, что это связано с меньшими затратами, чем в случае замены модифицированной страницы, которую необходимо будет физически переписывать во внешнюю память. В противном случае нам придется заменять модифицированную страницу. В многоабонентских системах основная память, естественно, работает активно, так что рано или поздно у большинства страниц бит-признак обращения будет установлен в 1, и мы не сможем отличать те страницы, которые вытолкнуть наиболее целесообразно. Один из широко распространенных способов решения этой проблемы заключается в том, что все биты-признаки обращений периодически сбрасываются в 0, с тем чтобы механизм вталкивания оказался в исходном состоянии, а затем снова разрешается установка этих битов-признаков в 1 обычным образом при обращениях. Правда, в этом случае существует опасность того, что могут быть вытолкнуты даже активные страницы, однако только в течение короткого периода после сброса битов-признаков, поскольку почти немедленно биты-признаки обращений для этих страниц будут снова установлены в 1. Описанный выше алгоритм NUR предусматривает существование четырех групп страниц: Группа 1 Обращений не было Модификаций не было Группа 2 Обращений не было Модификация была Группа 3 Обращения были Модификаций не было Группа 4 Обращения были Модификация была Страницы групп о меньшими номерами следует выталкивать в первую очередь, а с большими — в последнюю. Отметим, что группа 2 обозначает на первый взгляд нереальную ситуацию, она включает страницы, к которым как бы не было обращений, но они оказались модифицированными. В действительности это просто результат того, что биты-признаки обращения (но не биты-признаки модификации) периодически сбрасываются, т. е. подобная ситуация вполне возможна.   9.4 Локальность Большинство стратегий управления памятью базируется на концепции локальности, суть которой заключается в том, что распределение запросов процессов на обращение к памяти имеет, как правило, неравномерный характер с высокой степенью локальной концентрации. Свойство локальности проявляется как во времени, так и в пространстве. Временная локальность — это концентрация во времени. Если, например, в 15 ч наблюдается солнечная погода, то можно с достаточно высокой вероятностью считать (но, естественно, без всяких гарантий), что было солнечно в 14 ч 30 мин и будет солнечно в 15 ч 30 мин. Пространственная локальность означает, что соседние объекты будут, как правило, характеризоваться одинаковыми свойствами. Если опять-таки взять в качестве примера погоду, то в случае, когда в одном городе солнечно, можно с достаточно высокой вероятностью (но без всяких гарантий) считать, что и в близлежащих городах солнечно. Свойство локальности наблюдается также и в работе операционных систем, в частности при управлении памятью. Свойство это скорее эмпирическое (наблюдаемое), чем теоретически обоснованное. Локальность никак нельзя гарантировать, однако ее вероятность зачастую весьма велика. Например, в системах со страничной организацией мы наблюдаем, что процессы обычно «оказывают предпочтение» определенным подмножествам своих страниц и что эти страницы обычно размещаются по соседству друг с другом в виртуальном адресном пространстве процесса. Это не значит, что процесс не будет иметь ссылок на какую-либо новую страницу — если бы это было так, то процессы вообще не могли бы даже начать выполнение. Это просто означает, что процесс будет, как правило, сосредоточивать свои обращения в течение некоторого временного интервала на некотором конкретном подмножестве своих страниц. Фактически свойство локальности для вычислительных систем довольно легко объяснимо, если учесть, каким образом пишутся программы и организуются данные. В частности,   1. Временная локальность, означающая, что к ячейкам памяти, к которым недавно производилось обращение, с большой вероятностью будет обращение в ближайшем будущем, обусловливается наличием следующих факторов: а) программных циклов, б) подпрограмм, в) стеков, г) переменных, используемых в качестве счетчиков и для накопления итоговых сумм. 2. Пространственная локальность, означающая, что обращения к памяти, как правило, концентрируются таким образом, что в случае обращения к некоторой ячейке памяти с большой вероятностью можно ожидать обращения к близлежащим ячейкам, обусловливается наличием следующих факторов: а) организацией данных в виде массивов, б) последовательным выполнением кода программы» в) тенденцией программистов размещать описания взаимосвязанных переменных поблизости друг от друга. Рис. 9.2 Картина распределения обращений к памяти, свидетельствующая о существовании явления локальности (перепечатывается с разрешения корпорации IBM из IBM Systems Journal. © 1971).   По-видимому, самым важным следствием локализации обращений к памяти является то, что программа может эффективно работать, когда в памяти находится подмножество, включающее наиболее «популярные» ее страницы. На основе изучения свойства локальности Деннинг сформулировал свою теорию рабочего множества программ (De68, De68a). Эту теорию мы рассмотрим в следующем разделе. 'Было проведено много исследований, иллюстрирующих явление локальности. Так, на рис. 9.2 в графическом виде показано распределение обращений процесса к различным страницам памяти (На72). Здесь штрихами показано, к каким областям памяти производились обращения в течение последовательных временных интервалов. Из рисунка ясно видно, что в течение определенных периодов работы процесс обращается преимущественно лишь к некоторому подмножеству своих страниц. Рис. 9.3 Зависимость частоты прерываний от объема выделяемой первичной памяти: (а) процесс с равновероятными обращениями к страницам, (б) процесс с Локализованными обращениями.   Рис. 9.3 также подтверждает существование явления локальности. Здесь изображено, каким образом частота прерываний по отсутствию нужной страницы для процесса зависит от объема первичной памяти, выделяемой для размещения его страниц. Прямая линия показывает, как выглядела бы эта зависимость в случае, если бы процессы обращались к памяти по случайному закону, с равномерным распределением ссылок на различные свои страницы. Кривая линия показывает, как в действительности ведут себя большинство процессов во время работы. Если количество страничных кадров, выделяемых процессу, уменьшается, то существует некоторый интервал, в котором это не очень заметно сказывается на увеличении частоты прерываний по отсутствию нужной страницы. Однако, начиная с определенного момента при дальнейшем уменьшении количества выделяемых страничных кадров частота прерываний резко возрастает. При этом замечено, что, до тех пор, пока в первичной памяти остается подмножество наиболее интенсивно используемых страниц процесса, частота прерываний меняется мало. Но, как только какие-либо страницы этого подмножества из памяти удаляются, интенсивность подкачки резко возрастает, поскольку процесс постоянно обращается и вновь вызывает эти страницы в первичную память. Все это подтверждает предложенную Деннингом концепцию рабочего множества, которая рассматривается в следующем разделе. (Отметим, что приведенные рассуждения распространяются также по существу и на размещение рабочих множеств в кэш-памяти.)   9.5 Рабочие множества Деннинг (De68) предложил оценивать интенсивность подкачки страниц для программы согласно концепции, которую он назвал теорией поведения программы с рабочим множеством. Если говорить неформально, то рабочее множество — это подмножество страниц, к которым процесс активно обращается. Деннинг утверждал, что для обеспечения эффективного выполнения программы необходимо, чтобы ее рабочее множество находилось в первичной Рис. 9.4 Одно из определений рабочего множества страниц процесса.   памяти. В противном случае может возникнуть режим чрезмерно интенсивной подкачки страниц, так называемое пробуксовывание, или трешинг (De68b), поскольку программа будет многократно подкачивать одни и те же страницы из внешней памяти. Стратегия управления памятью в соответствии с рабочим множеством стремится к тому, чтобы рабочее множество программы было в первичной памяти. Решение о том, следует ли добавить новый процесс к набору активных процессов (т. е. об увеличении степени мультипрограммирования), должно базироваться на том, имеется ли в основной памяти достаточно свободного места, чтобы разместить рабочее множество страниц этого процесса. Подобное решение, особенно в случае впервые инициируемых процессов, зачастую принимается эвристически, поскольку система не может заранее знать, каким окажется рабочее множество данного процесса. Рис. 9.5 Размер рабочего множества как функция размера окна.   Рабочее множество страниц процесса W(t, w) в момент времени t есть набор страниц, к которым этот процесс обращается в течение интервала времени процесса от t—w до t (см. рис. 9.4). Время процесса — это время, в течение которого процесс имеет в своем распоряжении центральный процессор. Переменная w называется размером окна рабочего множества, причем выбор величины этого окна играет решающую роль с точки зрения эффективности стратегии управления памятью по рабочему множеству. На рис. 9.5 показано, как растет размер рабочего множества с увеличением размера окна w. Эта кривая следует из математического определения рабочего множества и не является результатом обработки эмпирически наблюдаемых размеров рабочих множеств. Реальное рабочее множество процесса — это множество страниц, которые должны находиться в первичной памяти, чтобы процесс мог эффективно выполняться. Во время работы процесса его рабочие множества динамически меняются. Иногда к текущему рабочему множеству добавляются или из него удаляются некоторые страницы. Иногда происходят резкие изменения, например, когда процесс переходит к этапу, требующему совершенно нового рабочего множества. Таким образом, любые предположения относительно размера и содержимого начального рабочего множества процесса не обязательно будут справедливыми для последующих рабочих множеств данного процесса. В связи с этим существенно усложняется задача реализации четкой стратегии управления памятью по рабочим множествам. На рис. 9.6 показано, как мог бы использовать первичную память процесс при управлении памятью по рабочим множествам. Вначале, поскольку процесс запрашивает страницы своего рабочего множества не все сразу, а по одной, он постепенно получает достаточный объем памяти для размещения текущего рабочего множества. Затем на какой-то период времени этот объем памяти стабилизируется, поскольку процесс интенсивно обращается к страницам Рис. 9.6 Выделение основной памяти при управлении памятью на основе рабочих множеств.   своего первого рабочего множества. Со временем процесс перейдет на следующее рабочее множество, что показывает кривая линия от первого ко второму рабочему множеству. Вначале эта кривая поднимается выше уровня первого рабочего набора, поскольку для процесса по его запросам быстро производится подкачка страниц нового рабочего множества. При этом система не может сразу определить, то ли процесс просто расширяет свое рабочее множество, то ли он переходит на новое. После того как процесс начнет стабильно обращаться к страницам своего следующего рабочего множества, система видит, что в течение выбранного окна происходит обращение к меньшему количеству страниц, чем ранее, и сокращает объем памяти, выделяемой процессу, до числа страниц этого второго рабочего множества. Каждый раз, когда осуществляется переход с одного рабочего множества на другое, кривая линия поднимается, а затем спадает, показывая, каким образом система адаптируется к подобному переходу. Рис. 9.6 иллюстрирует одну из серьезных трудностей, связанных с выбором стратегии управления памятью на основе рабочих множеств; проблема состоит в том, что рабочие множества меняются во времени, причем следующее рабочее множество процесса может существенно отличаться от предыдущего. Стратегия управления памятью должна обязательно учитывать этот факт, чтобы избегать перегрузок первичной памяти и возникающего вследствие этого трешинга.   9.6 Подкачка страниц по запросу Традиционно считается, что наиболее рационально загружать в основную память страницы, необходимые для работы процесса, по его запросу. Не следует переписывать из внешней памяти в основную ни одной страницы до тех пор, пока к ней явно не обратится выполняющийся процесс, В пользу такой стратегии можно привести несколько аргументов: ·         Теория вычислимости, в частности проблема останова (Mi67, Не77), говорит о том, что путь, который выберет программа при своем выполнении, точно предсказать невозможно. Поэтому любая попытка заранее загрузить страницы в память в предвидении того, что они потребуются в работе, может оказаться неудачной — будут загружены не те страницы. ·         Подкачка страниц по запросу гарантирует, что в основную память будут переписываться только те страницы, которые фактически необходимы для работы процессов. ·         Накладные расходы на то, чтобы определить, какие страницы следует передавать в основную память, минимальны. Стратегии вталкивания с упреждением могут потребовать значительных дополнительных затрат процессорного времени.   Подкачка страниц по запросу, как показывает рис. 9.7, имеет свои проблемы. Процесс должен накапливать в памяти, требуемые ему страницы по одной. При появлении ссылки на каждую новую страницу процессу приходится ждать, когда эта страница будет передана в основную память. В зависимости от того, сколько страниц данного процесса уже находятся в основной памяти, эти периоды ожидания будут обходиться все более дорого, поскольку ожидающие процессы будут занимать все больший объем памяти. Рис. 9.7 иллюстрирует понятие произведения «пространство— время», которое часто применяется в операционных системах для оценки использования памяти процессом. Произведение «пространство—время» соответствует площади «под кривой» на этом рисунке. Оно является комплексным показателем, отражающим как объем, так и время использования памяти процессом. Уменьшение произведения «пространство—время» за счет периодов ожидания процессом нужных ему страниц является важнейшей целью всех стратегий управления памятью. Рис. 9.7 Произведение «пространство-время» при подкачке страниц по запросу.   9.6 Подкачка страниц с упреждением Главный критерий эффективности управления ресурсами можно сформулировать следующим образом: интенсивность использования каждого ресурса должна определяться относительной ценностью этого ресурса. Так, в настоящее время стоимость аппаратуры резко снижается, и поэтому значительно снижается относительная ценность машинного времени по сравнению с временем, затрачиваемым человеком. Сейчас разработчики операционных систем активно ищут пути уменьшения количества времени, в течение которого пользователям приходится ждать получения результатов от компьютера. Одним из весьма перспективных в этом смысле является метод подкачки страниц с упреждением (с опережением). При упреждающей подкачке операционная система пытается заблаговременно предсказать, какие страницы потребуются процессу, а затем, когда в основной памяти появляется свободное место, загружает в нее эти страницы. Пока процесс работает со своими текущими страницами, система запрашивает новые страницы, которые будут уже готовы к использованию, когда процесс к ним обратится. Если решения о выборе страниц для подкачки принимаются правильно, то удается значительно сократить общее время выполнения данного процесса. Метод подкачки страниц с упреждением характеризуется следующими преимуществами: ·         Если в большинстве случаев удается принимать правильные решения о выборе страниц для подкачки, то время выполнения процесса значительно уменьшается. Поэтому имеет смысл пытаться создавать механизмы упреждающей подкачки, даже если от них нельзя ожидать абсолютной точности. ·         Во многих случаях вполне можно находить правильные решения. Если такое принятие решений удается реализовать при относительно малых затратах, то выполнение данного процесса можно значительно ускорить, не замедляя при этом работы других активных процессов. ·         Поскольку аппаратура вычислительных машин все более дешевеет, последствия неоптимальных решений становятся менее серьезны. Сейчас мы можем позволить себе приобрести дополнительную основную память, обеспечивающую накопление дополнительных страниц, которые механизм упреждающей подкачки будет передавать в основную память.   9.8 Освобождение страниц При управлении памятью по рабочему множеству программы говорят нам, какие страницы они хотят использовать, явно обращаясь к этим страницам. Страницы, которые больше не нужны, должны каким-то образом выводиться из рабочих множеств. Существует обычно период времени, в течение которого ненужные страницы все еще остаются в основной памяти. Когда выясняется, что некоторая страница больше не понадобится, пользователь может по собственной инициативе выдать сигнал об удалении страницы из памяти (отказаться от страницы) с освобождением соответствующего страничного кадра. Благодаря этому будет исключен период задержки, неизбежный в случае, если предоставить системе возможность естественным порядком вывести эту страницу из рабочего множества процесса. Подобное «добровольное освобождение» страниц может исключить непроизводительное использование памяти и ускорить выполнение программ. Однако большинство пользователей современных вычислительных машин даже не знают, что такое страница, поэтому их вообще нельзя просить принимать решения на системном уровне. Включение команд освобождения страниц в прикладные программы пользователя может значительно замедлить их разработку. Можно надеяться, что реально эта проблема будет решена при помощи компиляторов и операционных систем, которые будут автоматически обнаруживать ситуации, требующие освобождения, страниц, причем, делать это гораздо быстрее, чем позволяют стратегии с использованием рабочих, множеств страниц.   9.9 Размер страниц В системах со страничной организацией реальная память обычно разбивается на страничные кадры фиксированного размера. Какой величины следует выбирать размер этих страничных кадров? Какой величины следует выбирать размер страницы? Должны ли все страницы в системе иметь одинаковый размер либо следует использовать страницы нескольких различных размеров? Если используются различные размеры страниц, то должны ли большие размеры страниц быть целыми кратными меньших размеров? Для ответа на эти вопросы требуется тщательный анализ и всестороннее понимание возможностей аппаратных и программных средств и области применения конкретной системы. Здесь не может быть универсальных ответов. Не существует никакой особой необходимости в том, чтобы все вычислительные системы имели одинаковый или единственный размер страниц. Некоторые соображения, которые необходимо учитывать при выборе того или иного размера страницы, приведены ниже. ·         Чем меньше размер страницы, тем большее количество страниц и страничных кадров будет в системе и тем больше будут таблицы страниц. Для систем, в которых таблицы страниц занимают первичную память, это указывает на необходимость увеличенных размеров страниц. Такое неэффективное использование памяти из-за чрезмерно больших таблиц называется табличной фрагментацией. Здесь мы отметим, что подобный аргумент в настоящее время не столь актуален, поскольку выпускается недорогая память очень большой емкости. ·         При крупных размерах страниц в первичную память при подкачке попадают большие объемы информации, которая, вообще говоря, может и не понадобиться. Это указывает на необходимость уменьшения размеров страниц. ·         Поскольку обмены данными с дисковой памятью занимают относительно много времени, мы хотим свести к минимуму число обменов, которые будут производиться для программы во время ее выполнения. Это указывает, по-видимому, на необходимость увеличения размеров страниц. ·         Программы, как правило, проявляют свойство локальности обращений, причем размеры подобных локальных участков невелики. Таким образом, уменьшение размера страницы должно способствовать тому, что у программы образуется более компактный набор страниц, т. е. страницы рабочего множества» размещаемые в реальной памяти, будут содержать более интенсивно используемые объекты. ·         Поскольку блоки процедур и данных редко представляют целое число страниц, в системах со страничной организацией наблюдается внутренняя фрагментация, иллюстрируемая рис. 9.8. Сегмент длины s с равной вероятностью может иметь свою последнюю страницу почти полную или почти пустую, и, таким образом, в среднем потери из-за внутренней фрагментации составляют половину страницы (при том ограничительном условии, что страница не может содержать части более чем одного сегмента). Чем меньше размер страницы, тем меньше потери из-за внутренней фрагментации. Рис. 9.8 Внутренняя фрагментация в системе со страничной организацией.   Фирма Модель Размер страницы Единицы измерения Honeywell Multics 1024 36-битовое слово IBM 360/67 1024 32-битовое слово IBM 370/168 1024 или 512 32-битовое слово DEC PDP- 10 PDP-20 512 36-битовое слово DEC YAX 11/780 128 32-битовое слово Рис. 9.9 Некоторые стандартные размеры страниц.   Большинство приводящихся в литературе данных (De80), как теоретических, так и эмпирических, указывает на то, что необходимы страницы малых размеров. На рис. 9.9 приведены размеры страниц нескольких популярных компьютеров. Отметим, что для одной из недавно разработанных машин, VAX 11/780, выбран размер страницы 128 слов.   9.10 Поведение программ при подкачке страниц Страничная организация — весьма эффективная концепция, так что она будет, по-видимому, по-прежнему находить применение в вычислительных системах в течение следующих нескольких десятилетий. Было проведено много исследований, анализирующих поведение процессов со страничной организацией памяти (Ве66, Со68, На72, Sp72, О174, Sa75, Ва76, Ро77, Sp77, Fr78, De80). B данном разделе мы приведем некоторые качественные результаты этих исследований. Рис. 9.10   На рис. 9.10 показан график зависимости процента страниц, к которым обращается типичный процесс, от времени, причем с начала выполнения этого процесса. Первоначальный резкий скачок вверх свидетельствует о том, что сразу после начала выполнения процесс обращается к значительной части своих страниц. Со временем наклон кривой уменьшается и она асимптотически приближается к уровню 100%. Безусловно, некоторые процессы используют все 100% своих страниц, однако приведенный качественный график отражает тот факт, что многие процессы могут в течение длительного времени выполняться, не обращаясь ко всем своим страницам. Это часто бывает, например, в случае, когда к определенным подпрограммам обработки ошибок приходится прибегать лишь изредка. На рис. 9.11 показано, к каким последствиям приводит изменение размера страницы при сохранении постоянного объема первичной памяти. Из графика видно, что для работающего процесса число прерываний по отсутствию нужной страницы увеличивается с увеличением размера страницы. Это происходит потому, что с увеличением размера страницы в первичную память фиксированного размера попадает большее число процедур и данных, к Рис. 9.11 Рис. 9.12   которым не будет обращений. Тем самым уменьшается доля, занимаемая процедурами и данными, к которым будут производиться обращения, в общем ограниченном объеме памяти процессора. А поскольку последовательность обращений процесса к элементам памяти по сути не зависит от объема выделяемой ему первичной памяти, во время выполнения процесса будет возникать большее количество прерываний, вызывающих передачу страниц с требуемыми процедурами и данными в первичную память. На рис. 9.12 показано, каким образом меняется среднее время между прерываниями по отсутствию нужной страницы в памяти при увеличении числа страничных кадров, выделяемых процессу. Кривая монотонно растет — чем больше страничных кадров имеет процесс, тем больше интервал между прерываниями по отсутствию нужных страниц. Однако на кривой есть точка перегиба, после которой наклон резко уменьшается. Эта точка соответствует моменту, когда в первичной памяти оказывается все рабочее множество страниц процесса. Первоначально величина интервала между прерываниями растет очень быстро, поскольку растет часть рабочего множества, которая оказывается в первичной памяти. После того как выделенный объем первичной памяти оказывается достаточным для размещения всего рабочего множества, кривая делает перегиб, указывая на то, что выделение дополнительных страничных кадров не приведет к существенному увеличению интервала между прерываниями. Ключевой момент здесь состоит в том, чтобы все рабочее множество попало в первичную память. Рис. 9.13   На рис. 9.13 показано, какой процент команд данной страницы выполняется до того, как управление будет передано другой странице. В одном проведенном эксперименте максимум указанной кривой пришелся на точку, соответствующую примерно 200 командам страницы размером 1024 слов. Подобные результаты говорят, по-видимому, о том, что необходимо уменьшать размеры страниц. В общем качественные оценки и рассуждения, приведенные в этом разделе, свидетельствуют о правомерности концепции рабочего множества и о необходимости уменьшения размеров страниц. По мере развития архитектуры компьютеров эти результаты придется пересматривать.   Заключение Стратегии управления виртуальной памятью разделяются на три категории. Стратегии вталкивания ставят своей целью определить, в какой момент следует переписывать очередную страницу или сегмент в основную память. В случае вталкиваний по запросу это делается при появлении явной ссылки; при упреждающем вталкивании это делается заблаговременно, когда с достаточно высокой вероятностью можно считать, что к данной странице или сегменту вскоре будет обращение. Стратегии размещения ставят своей целью определить, в какое место первичной памяти помещать поступающую страницу или сегмент. Стратегии выталкивания определяют, какую страницу или сегмент следует заменить, чтобы освободить место для поступающей страницы или сегмента, когда первичная память полностью занята. В данной главе обсуждались следующие стратегии выталкивания страниц: ·         Принцип оптимальности — выталкивается страница, которая наиболее долго не будет использоваться в дальнейшем. ·         Случайный принцип — равновероятно выталкивается любая страница. ·         FIFO — выталкивается страница, которая находилась в памяти дольше других. ·         LRU — выталкивается страница, которая дольше всего не использовалась. ·         LFU — выталкивается страница, которая использовалась реже других. ·         NUR — недорогая и эффективная стратегия, приближающаяся к LRU, — выталкивается страница, не используемая в последнее время. ·         Рабочее множество — выталкивается страница, которая не входит в подмножество наиболее активно используемых страниц процесса.   Аномалия FIFO — это явление, суть которого заключается в том, что иногда увеличение количества страничных кадров, выделяемых процессу, приводит к увеличению частоты прерываний по отсутствию нужных страниц для этого процесса. Локальность — это свойство выполняющихся процессов, состоящее в том, что процессы, как правило, более активно обращаются к некоторому подмножеству своих страниц в течение некоторого временного интервала выполнения. Временная локальность означает, что процесс, обращающийся к некоторой странице, с большой вероятностью вскоре снова обратится к этой же странице. Пространственная локальность означает, что процесс, обращающийся к некоторой странице, с большой вероятностью вскоре обратится к соседним страницам своего виртуального адресного пространства. Свойство локальности вполне объяснимо, если учесть, что программы пишутся с использованием циклов, подпрограмм, стеков, счетчиков, переменных для накопления итоговых сумм, массивов, что код программы обычно выполняется последовательно и что у программистов принято размещать описания взаимосвязанных элементов поблизости друг от друга. Деннинг разработал концепцию рабочих множеств, объясняющую поведение программы на основе понятия локальности. Стратегии управления памятью с использованием рабочих множеств ставят своей целью размещать страницы рабочего множества, т. е. страницы, к которым производились обращения в самое последнее время, в основной памяти, с тем чтобы процесс мог быстро выполняться. Новые процессы можно инициировать только в случае, если в основной памяти имеется свободное место для размещения их рабочих множеств. Деннинг определил рабочее множество W (t, w) в момент времени t как множество страниц, к которым процесс обращается в интервале процессорного времени от t—w до t. Если делается попытка выполнять процессы, не имеющие достаточного места в памяти для размещения рабочих множеств, то часто возникает явление пробуксовки, или трешинга; оно заключается в том, что производится непрерывное выталкивание страниц с последующим немедленным вталкиванием их обратно. Подкачка страниц по запросу традиционно считается наиболее рациональной стратегией управления памятью, поскольку. ·         теория вычислимости говорит о том, что полностью эффективные механизмы упреждающей подкачки реализовать нельзя, так как мы не можем точно предсказывать будущее; ·         в основную память вводятся только те страницы, которые фактически необходимы для работы процесса, и ·         издержки на выборку страниц минимальны.   В то же время подкачка страниц по запросу приводит к неэффективному использованию первичной памяти, поскольку процессам приходится ждать, пока не поступит каждая нужная страница. Сторонники подкачки страниц с упреждением, напротив, утверждают, что в большинстве случаев удается принимать правильные решения по выбору страниц и что процессы будут выполняться гораздо быстрее, когда нужные им страницы будут уже находиться в первичной памяти. Некоторые системы предусматривают возможность добровольного освобождения страниц, т. е. выполняющийся процесс в явном виде сообщает системе, что какая-то конкретная страница ему больше не понадобится. Такой подход помогает освобождать первичную память от ненужных страниц. Чтобы определить оптимальный размер страницы для данной системы, необходимо учитывать ряд соображений. ·         Малый размер страницы приводит к увеличению таблиц страниц и, как следствие, к табличной фрагментации. ·         Большой размер страницы приводит к тому, что в первичную память будут переписываться команды и данные, к которым не будет обращений. ·         Ввод-вывод более эффективен при больших размерах страниц. ·         Свойство локальности распространяется, как правило, на небольшие участки. ·         При малых размерах страниц потери памяти на внутреннюю фрагментацию уменьшаются.   В целом большинство разработчиков придерживается мнения, что все эти факторы, свидетельствуют о необходимости выбора небольших размеров страниц. Было проведено много экспериментов для исследования поведения программ в вычислительных системах со страничной организацией, причем получены интересные результаты. ·         Когда процесс начинает выполнение, он обычно быстро обращается к большому проценту своих страниц. ·         Количество прерываний по отсутствию нужной страницы для выполняющегося процесса увеличивается с увеличением размера страницы, если предположить, что объем первичной памяти, выделенной этому процессу, остается постоянным. ·         Интервал между прерываниями по отсутствию нужной страницы для работающего процесса растет с увеличением количества выделяемых ему страничных кадров. После того как процессу выделено количество страничных кадров, достаточное для размещения его рабочего множества, скорость увеличения этого периода уменьшается. ·         Число команд, выполняемых на странице до передачи управления другой странице, как правило, невелико.   Терминология аномалия FIFO (FIFO Anomaly) внутренняя фрагментация (internal fragmentation) выталкивание страниц по принципу FIFO («первой заменяется первая пришедшая страница») (first-in-first-out (FIFO) page replacement) выталкивание страниц по принципу LFU («первой заменяется наименее часто используемая страница») (least-frequently-used (LFU) page replacement) выталкивание страниц по принципу LRU («первой заменяется дольше всего не использовавшаяся страница») (least-recently-used (LRU) page replacement) выталкивание страниц по принципу NUR («первой заменяется не использовавшаяся в последнее время страница») (not-used-recently (NUR) page replacement) выталкивание страниц рабочего множества (working set page replacement) выталкивание страниц по случайному принципу (random page replacement) добровольное освобождение страницы, отказ от страницы (voluntary page release) локальность (locality) локальность временная (temporal locality) локальность пространственная (spatial locality) оптимальное выталкивание страниц (optimal page replacement) подкачка страниц по запросу (по требованию) (demand paging) подкачка страниц с упреждением (anticipatory paging) принцип оптимальности (Principle of Optimality) пробуксовка, трешинг (thrashing) произведение «пространство—время» (space-time product) рабочее множество страниц (working set of pages) размер окна рабочего множества (working set window size) стратегия вталкивания (fetch strategy) стратегия выталкивания (page replacement strategy) стратегия управления памятью на основе рабочих множеств (working set storage management policy) табличная фрагментация (table fragmentation) теория поведения программ с рабочим множеством (working set theory of program behavior)   Упражнения 9.1Обсудите цели каждой из следующих стратегий управления памятью применительно к системам виртуальной памяти со страничной организацией: а) стратегия вталкивания, б) стратегия размещения, в) стратегия выталкивания. 9.2Объясните, почему управление памятью в чисто сегментных системах весьма похоже на управление памятью в системах мультипрограммирования с переменными разделами. 9.3Приведите несколько причин, по которым подкачка страниц по запросу в течение многих лет считалась наиболее рациональной стратегией вталкивания страниц. 9.4В одной конкретной вычислительной системе с комбинированной странично-сегментной виртуальной памятью предусматривается уровень мультипрограммирования, выражаемый показателем 10 (одновременно могут выполняться 10 программ). Страницы команд (реентерабельный код) отделены от страниц данных (допускающих модификацию). Вы исследовали эту систему в работе и сделали следующие наблюдения: (1) большинство процедурных сегментов содержат по много страниц и (2) большинство сегментов данных используют только незначительную часть страницы. Ваш помощник предложил в качестве одного из способов повышения эффективности использования памяти объединять несколько сегментов данных каждого пользователя в одной индивидуальной странице. Прокомментируйте это предложение с учетом следующих факторов: а) использование памяти, б) эффективность выполнения программ, в) бесконечное откладывание, г) защита, д) разделение ресурсов. 9.5В настоящее время среди специалистов наблюдается большой интерес к упреждающей подкачке страниц и к упреждающему распределению ресурсов вообще. Какую полезную информацию может предоставить механизму упреждающей подкачки страниц каждый из следующих объектов? а) программа пользователя, б) языковый транслятор, в) операционная система, г) журнал с данными о прошлых прогонах программы. 9.6Известно, что в общем случае мы не можем предсказать путь выполнения произвольной программы. А если бы мы могли, то мы оказались бы в состоянии решить проблему останова, которая, как известно, неразрешима. Объясните, каким образом это обстоятельство влияет на эффективность механизмов упреждающего распределения ресурсов. 9.7Предположим, что блок управления памятью при принятии решения о выталкивании страницы должен выбрать одну из двух страниц. Предположим, что одна из этих страниц разделяется несколькими процессами, а другая используется только одним процессом. Должен ли блок управления вытолкнуть эту монопольно используемую страницу? Объясните. 9.8Обсудите каждый из следующих нетрадиционных алгоритмов выталкивания страниц применительно к мультипрограммной системе с виртуальной памятью, обслуживающей пользователей как в пакетном, так и в диалоговом режимах: а) «Глобальный LIFO» — выталкивается страница, самой последней поступившая в физическую память. б) «Локальный LIFO» — выталкивается самая последняя по времени поступления страница, вызванная процессом, который запросил поступающую новую страницу. в) «Утомленная страница» — выталкивается страница, подвергавшаяся наиболее интенсивным обращениям в системе. (Рассмотрите как глобальный, так и локальный варианты этого алгоритма.) г) «Истрепанная страница» — выталкивается страница, подвергавшаяся наиболее интенсивным модификациям в системе. (Рассмотрите как глобальный, так и локальный варианты этого алгоритма.) 9.9Некоторые типы процессов хорошо работают при одних стратегиях выталкивания страниц и плохо при других. Обсудите возможность реализации блока управления памятью, который динамически определял бы тип процесса, а затем выбирал бы и использовал соответствующую стратегию выталкивания страниц памяти для этого процесса. 9.10Предположим, что блок управления памятью принимает решение о том, какую страницу следует вытолкнуть, исключительно на основе анализа битов-признаков обращения и модификации для каждого страничного кадра. Приведите несколько примеров некорректных решений, которые мог бы принять такой блок управления. 9.11Перечислите несколько причин, по которым на некоторые страницы должен действовать запрет на выталкивание из первичной памяти. 9.12Почему в общем случае более целесообразно выталкивать немодифицированную страницу, а не страницу, подвергавшуюся модификации? При каких обстоятельствах может оказаться более целесообразным выталкивать модифицированную страницу? 9.13Для каждой из приведенных ниже пар стратегий выталкивания укажите последовательность обращений к страницам, при которой обе стратегии выбрали бы для выталкивания (1) одну и ту же страницу и (2) разные страницы: а) LRU, NUR, б) LRU, LFU, в) LRU, FIFO, г) NUR, LFU, д) LFU, FIFO, е) NUR, FIFO. 9.14Оптимальная стратегия подкачки страниц (ОРТ) практически неосуществима, поскольку невозможно предсказать будущее. Существуют, однако, обстоятельства, при которых эту стратегию реализовать можно. Что это за обстоятельства? 9.15Затраты на перепись модифицированной страницы во внешнюю память, с тем чтобы можно было освободить место для новой страницы, настолько велики, что этого по возможности следует избегать. Предположим, что блок управления памятью выбирает для замещения модифицированную страницу. Эту страницу необходимо записать во внешнюю память, чтобы в ее освободившийся страничный кадр можно было поместить новую страницу. Поэтому блок управления планирует произвести выталкивание указанной страницы и заносит ее в список страниц, ожидающих выталкивания. Таким образом, страница будет оставаться в первичной памяти в течение некоторого времени, прежде чем будет вытолкнута во внешнюю память. Предположим теперь, что именно в это время указанную страницу запросит выполняющийся процесс. Как должен отреагировать блок управления памятью на запрос? При ответе не упускайте из виду возможность бесконечного откладывания и необходимость гарантировать приемлемые времена реакции для интерактивных пользователей. 9.16Стратегию замещения FIFO относительно просто реализовать, причем с малыми издержками. Однако эта стратегия вполне может выбрать для замены и активно используемую страницу. Предложите простую модификацию стратегии FIFO, которая также характеризовалась бы легкостью реализации, малыми издержками и в то же время не позволяла заменять интенсивно используемую страницу. 9.17Приведите пример аномалии FIFO, отличающийся от указанного в тексте. 9.18Разработайте экспериментальную программу для демонстрации явления локальности в системе со страничной организацией. 9.19Программист, который пишет программы, принимая специальные меры для обеспечения высокой степени локальности, может ожидать заметного повышения эффективности работы своих программ. Перечислите несколько принципов, которые может использовать программист для улучшения локальности. В частности, какие средства языков высокого уровня следует применять более широко? Применения каких средств следует избегать? 9.20Предположим, что вы подключились к каналу ввода-вывода и наблюдаете активное движение страниц. Означает ли это, что имеет место трешинг? Объясните. 9.21Почему глобальная стратегия выталкивания страниц может оказаться более подверженной трешингу, чем локальная? 9.22Обсудите взаимосвязи между предоставлением каждому процессу большего числа страничных кадров, чем ему реально требуется (чтобы предотвратить трешинг), и получающейся фрагментацией первичной памяти. 9.23Предложите несколько эвристических правил, которые мог бы использовать блок управления памятью, чтобы определять, не произошла ли перегрузка первичной памяти. 9.24Рабочее множество страниц процесса может иметь несколько определений. Обсудите достоинства каждой из приведенных ниже схем выбора страниц, составляющих рабочее множество процесса: а) те страницы, к которым процесс обращался в течение последних w секунд календарного времени; б) те страницы, к которым процесс обращался в течение последних w секунд виртуального времени (т. е. времени, в течение которого этот процесс фактически имел в своем распоряжении центральный процессор); в) последние k различных страниц, к которым обращался процесс; г) те страницы, к которым процесс делал свои последние r обращений за командами или данными; д) те страницы, к которым процесс обращался в течение последних w секунд виртуального времени с частотой, превышающей f раз в виртуальную секунду. 9.25Приведите пример ситуации, при которой стратегия выталкивания страниц по рабочему множеству будет приводить к замене а) наиболее удачной страницы, б) наименее удачной страницы. 9.26Одна из сложностей реализации стратегии управления памятью по рабочим множествам заключается в том, что, когда процесс запрашивает новую страницу, трудно определить, переходит ли этот процесс к новому рабочему множеству или просто расширяет свое текущее рабочее множество. В первом случае блоку управления памятью лучше принять решение о замене одной из страниц этого процесса, а во втором — о добавлении еще одной страницы к уже выделенным страницам процесса. Как может блок управления решить, с какой ситуацией он столкнулся? 9.27Сам факт, что некоторая страница является членом рабочего множества процесса, не обязательно означает, что к ней производятся частые обращения. Аналогично к страницам рабочего множества процесса не обязательно производятся обращения с одной и той же частотой. Предложите модификацию стратегии подкачки по рабочим множествам, которая в случае необходимости замены страницы рабочего множества обеспечивала бы выбор этой страницы согласно одному из прочих алгоритмов, например FIFO, LRU, LFU, NUR и т. д. Сравните эту новую стратегию с чистым принципом рабочих множеств. 9.28Предположим, что все процессы, работающие в мультипрограммной системе, разместили свои рабочие множества в первичной памяти. При изменении картины локальности (распределения обращений) рабочие множества могут возрасти и первичная память может оказаться перегруженной, что приводит к трешингу. Обсудите относительные достоинства указанных ниже стратегий, направленных на предотвращение этого неприятного явления: а) Никогда не инициировать новый процесс, если реальная память уже загружена на 80% и более. б) Никогда не инициировать новый процесс, если реальная память уже загружена на 97% и более. в) При инициировании нового процесса назначать для его рабочего множества максимальный размер, за пределы которого нельзя будет выходить. 9.29Критическим фактором с точки зрения обеспечения высоких скоростных характеристик является организация взаимодействия между различными компонентами операционной системы. Обсудите проблемы взаимодействия между блоком управления памятью и модулем инициирования задач в мультипрограммной схеме с виртуальной памятью. В частности, рассмотрите случай, когда блок управления памятью реализует метод управления памятью по рабочим множествам. 9.30Рассмотрите приведенный ниже эксперимент и объясните наблюдаемые результаты. Программа выполняется на машине со страничной организацией памяти, причем начинает работу со своей первой процедурной страницы. Во время выполнения программы необходимые страницы подкачиваются по запросу в имеющиеся страничные кадры, число которых значительно больше числа страниц программы. Однако вне компьютера имеется специальное наборное устройство, при помощи которого оператор ЭВМ может задавать максимальное количество страничных кадров, предоставляемых программе для использования. Первоначально это наборное устройство устанавливается на два кадра и программа выполняется с начала до конца. Затем устройство устанавливается на три кадра и программа снова выполняется с начала до конца. Этот процесс повторяется до тех пор, пока на наборном устройстве не будет установлено полное количество имеющихся страничных кадров реальной памяти, и программа выполняется последний раз. При каждом прогоне фиксируется время выполнения программы. Наблюдаемые результаты: При изменении числа кадров с двух до трех и затем до четырех времена выполнения программы резко уменьшаются. При переходе от четырех к пяти и затем к шести времена выполнения каждый раз также сокращаются, однако менее резко. После того как на наборном устройстве устанавливается семь кадров и более, времена выполнения программы остаются практически постоянными. 9.31Разработчик операционной системы предложил так называемую PD-стратегию управления памятью, реализующую следующий алгоритм. Каждому активному процессу выделяются ровно два страничных кадра. В этих кадрах размещается самая последняя по времени обращения процедурная страница, Р-страница, и самая последняя по времени обращения страница данных, D-страница. Когда происходит прерывание по отсутствию страницы и если нужная страница процедурная, она заменяет Р-страницу, а если это страница данных, она заменяет D-страницу. Разработчик говорит, что главное достоинство такого алгоритма заключается в том, что он до предела упрощает все аспекты управления памятью и благодаря этому характеризуется очень малыми накладными расходами. а) Каким образом PD-алгоритм сказывается на реализации стратегий (1) вталкивания, (2) размещения и (3) выталкивания при управлении памятью. б) При каких обстоятельствах PD-алгоритм фактически обеспечивает лучшие результаты, чем управление памятью по рабочим множествам? в) При каких обстоятельствах PD-алгоритм дает неблагоприятные результаты. 9.32Опишите, каким образом коллективное использование кода и данных затрагивает перечисленные ниже стратегии и явления: а) стратегию вталкивания, б) стратегию размещения, в) стратегию выталкивания, г) «локальную локальность» (т. е. локальность в рамках одного процесса), д) «глобальную локальность» (т. е. локальность для всех процессов), е) трешинг, ж) назначение платы за использование ресурсов, з) фрагментацию (I) внутреннюю, (II) внешнюю, (III) блочную. 9.33Приведите в сводном виде аргументы за и против (1) страницы малых размеров и (2) страницы больших размеров. 9.34 Система Multics первоначально разрабатывалась с ориентацией на использование страниц двух размеров — 64 слова и 1024 слова (в конце концов от такого подхода разработчики отказались). а) Какие факторы, по вашему мнению, послужили предпосылками для принятия такого конструкторского решения? б) Каким образом подобный подход с использованием страниц двух размеров сказался на стратегиях управления памятью? 9.35Обсудите, каким образом в системах виртуальной памяти могут использоваться следующие аппаратные средства: а) механизмы динамического преобразования адресов, б) ассоциативная память, в) кэш-память, г) бит-признак обращения к странице, д) бит-признак модификации страницы, е) бит-признак «страница в процессе передачи» (означающий, что в настоящее время страница передается в конкретный страничный кадр). 9.36Обсудите вопрос о том, каким образом стиль программирования влияет на скоростные характеристики системы со страничной организацией. При этом рассмотрите следующие подходы и проблемы: а) нисходящее программирование, б) минимальное использование операторов перехода GOTO, в) модульность, г) рекурсия, д) итерация. 9.37Если в системе со страничной организацией программы тщательно продуманы и построены таким образом, что распределение обращений характеризуется высокой степенью локальности, т. е. концентрируется на малых группах страниц, то можно получить весьма внушительный выигрыш в скоростных характеристиках. Однако, поскольку в настоящее время большинство программ пишутся на языках высокого уровня, программист, как правило, просто не располагает достаточной информацией, чтобы способствовать генерации эффективных программ. Поскольку путь, который выберет программа при своем выполнении, предсказать нельзя, трудно точно установить, какие части кода будут использоваться наиболее интенсивно. Один из способов, предположительно улучшающих построение программ, называется динамическим реструктурированием программ. Здесь операционная система контролирует рабочие характеристики программы и перестраивает структуру ее кода и данных таким образом, чтобы наиболее активные элементы размещались совместно на одних и тех же страницах. а) Какие рабочие характеристики крупной программы следует контролировать, чтобы обеспечить эффективное динамическое реструктурирование программы? б) Каким образом механизм динамического реструктурирования программ должен использовать полученную информацию для принятия эффективных решений по перестройке структуры? 9.38Назначение платы за использование ресурсов является сложной проблемой. Применительно к мультипрограммной системе со страничной организацией виртуальной памяти рассмотрите каждый из следующих вопросов: а) Следует ли предъявлять процессу более крупный счет за то, что при его выполнении возникает чрезмерное число прерываний по отсутствию нужной страницы? б) Следует ли предъявлять процессу более крупный счет за то, что он имеет большое рабочее множество страниц? в) Следует ли предоставлять процессу скидки в случае, если он страдает от ухудшения обслуживания, вызванного трешингом? г) Следует ли в счет для процесса включать определенную долю накладных расходов операционной системы, связанных с управлением виртуальной памятью?   Литература (Ah71) Aho A. V., Denning P. J., Ullman J. D., "Principles of Optimal Page Replacement", JACM, Vol. 18, No, 1, January 1971, pp. 80—93. (Ba76) Baer J., Sager G. R., "Dynamic Improvement of Locality in Virtual Memory Systems", IEEE Trans, on Soft. Eng., Vol. SE-1, March 1976, pp. 54—62. (Ba70) Batson A. P., Ju S., Wood D., "Measurements of Segment Size", CACM, Vol. 13, No. 3, March 1970, pp. 155—159. (Ва77) Batson A. P., Bondage R. G., "Segment Sizes and Lifetimes in ALGOL 60 Programs", CACM, Vol. 20, January 1977, pp. 36—44. (Be66) Belady L. A., "A Study of Replacement Algorithms for Virtual Storage Computers", IBM Systems Journal, Vol. 5, No. 2, 1966, pp. 78—101. (Be69) Belady L. A., Kuehner C. J., "Dynamic Space Sharing in Computer Systems", CACM, Vol. 12, No. 5, May 1969, pp. 282—288. (Be69b) Belady L. A., Nelson R. A., Shedler G. S., "An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Environment", CACM, Vol. 12, No. 6, June 1969, pp. 349—353. (Вr68) Brawn В., Gustavson F. G., "Program Behavior in a Paging Environment", AFIPS Conf. Proc., Vol. 33, 1968 FJCC, pp. 1019—1032. (Вr75) Bryant P., "Predicting Working Set Sizes", IBM Journal of R&D, Vol. 19, No. 3, May 1975, pp. 221—229. (Ch73) Chamberlin D. D., S. H. Fuller, b. Liu, "An Analysis of Page Allocation Strategies for Virtual Memory Systems", IBM Journal of R&D, Vol. 17, 1973, pp. 404—412. (Ch76) Chu W. W., Opderbeck H., "Program Behavior and the Page-Fault-Frequency Replacement Algorithm", Computer, November 1976, pp. 29—38. (Со73) Coffman E. G., Jr., Denning P. J., Operating Systems Theory, Englewood Cliffs, N. J.: Prentice-Hall, 1973. (Со68) Coffman E. G., Jr., Varian L. C., "Further Experimental Data on the Behavior of Programs in a Paging Environment", CACM, Vol. 11, No. 7, July 1968, pp. 471—474. (De68) Denning P. J., "The Working Set Model for Program Behavior". CACM, Vol. 11, No. 5, May 1968, pp. 323—333. (De68a) Denning P. J., Resource Allocation in Multiprocess Computer Systems, Ph. D. Thesis, Report MAC-TR-50 M. I. T. Project MAC, May 1968. (De68b) Denning P. J., "Thrashing: Its Causes and Prevention" AFIPS Соя/. Proc., Vol. 33, 1968 FJCC, pp. 915—922. (De70) Denning P. J., "Virtual Memory", ACM Computing Surveys, Vol. 2, No. 3, September 1970, pp. 153—189. (De72) Denning P. J., Schwartz S, C., "Properties of the Working Set Model", CACM, Vol. 15, No. 2, March 1972, pp. 191—198. (De72a) Denning P. J., "On Modeling Program Behavior", AFIPS Соя/. Proc., Vol. 40, 1972 SJCC, pp. 937—944. (De75) Denning P. J., Graham G. S., "Multiprogrammed Memory Management", Proc. IEEE, Vol. 63, June 1975, pp. 924—939. (De75a) Denning P. J., К- С. Kahn, "A Study of Program Locality and Lifetime Functions", Proc. 5th ACM Symp Operating Systems Principles, November 1975, pp. 207—216. (De78) Denning P. J., "Optimal Multiprogrammed Memory Management", В сб.   К. М. Chandy, R. Yeh (ред.), Current Trends In Programming, Methodology, Vol. Ill, Englewood Cliffs, N. J.: Prentice-Hall, 1978, pp. 298—322. (De80) Denning P. J., "Working Sets Past and Present", IEEE Trans, on Soft. Eng., Vol. SE-6, No. 1, January 1980, pp. 64—84. (Ea77) Easton M. C., Bennett В. Т., "Transient-Free Working Set Statistics", CACM, Vol. 20, No. 2, February 1977, pp. 93—99. (Fe74) Ferrari D., "Improving Locality by Critical Working Sets", CACM, Vol. 17, No. 11, November 1974, pp. 614—620. (Fe75) Ferrari D., "Tailoring Programs to Models of Program Behavior", IBM Journal of R&D, Vol. 19, No. 3, May 1975, pp. 244—251. (Fe76) Ferrari D., "The Improvement of Program Behavior", IEEE Computer, Vol. 9, No. 11, November 1976, pp. 39—47. (Fo74) Fogel M., "The VMOS Paging Algorithm", Operating Systems Review, Vol. 8, 1974, pp. 8—16. (Fr78) Franklin M. A., Graham G. S., Gupta R. P., "Anomalies with Variable Partition Paging Algorithms", CACM, Vol. 21, No. 3, March 1978, pp. 232—236. (Gu78) Gupta R. K., Franklin M. A., "Working Set and Page Fault Frequency Replacement Algorithms: A Performance Comparison", IEEE Trans, on Computers, Vol. C-27, August 1978, pp. 706—712. (Ha71) Hatfield D., Gerald J., "Program Restructuring for Virtual Memory", IBM Systems Journal, Vol. 10, 1971, pp. 168—192. (Ha72) Hatfield D., "Experiments on Page Size, Program Access Patterns, and Virtual Memory Performance", IBM Journal of R&D, Vol. 16, No. 1, January 1972, pp. 58 — 62. (He77) Hennie F., Introduction to Computability, Reading, Mass.: Addison- Wesley, 1977. (Ma76) Madison A. W., Batson A. P., "Characteristics of Program Localities", CACM, Vol. 19, No. 5, May 1976, pp. 285—294. (Ma70) Mattson R. L., Gecsei J., Slutz D. R., Traiger I. L., "Evaluation Techniques for Storage Hierarchies", IBM Systems Journal, Vol. 9, No. 2, 1970, pp. 78—117. (Mi67) Minsky M. L., Computation: Finite and Infinite Machines, Englewood Cliffs, N.J.: Prentice-Hall, 1967. (Mo72) Morris J. В., "Demand Paging through the Use of Working Sets on the Maniac II", CACM, Vol. 15, No. 10, October 1972, pp. 867—872. (O174) Oliver N. A., "Experimental Data on Page Replacement Algorithms", Proc. API PS, 1974 NCC 43, Montvale, N. J.: AFIPS Press, 1974, pp. 179—184 (Op74) Operdeck H., Chu W. W., "Performance of the Page Fault Frequency Algorithm in a Multiprogramming Environment". Proc. IFIP Congress, 1974, pp. 235—241. (Po81) Pohn A. V., Smay T. A., "Computer Memory Systems", IEEE Computer Magazine, October 1981, pp. 93—110. (Pr76) Prieve B. G., Fabry R. S., "VMIN — An Optimal Variable Space Page Replacement Algorithm", CACM, Vol. 19, No. 5, May 1976, pp. 295— 297. (Po77) Potier D., "Analysis of Demand Paging Policies with Swapped Working Sets", Proc. 6th ACM Symposium on Operating Systems Principles, November 1977, pp. 125—131. (Ro73) Rodriguez-Rosell J., Dupuy J. P., "The Design, Implementation, and Evaluation of a Working Set Dispatcher", CACM, Vol. 16, No. 4, April '1973, pp 247—253. (Sa75) Sadeh E., "An Analysis of the Performance of the Page Fault Frequency (PFF) Replacement Algorithm", Proc. 5th ACM Symposium on Operating Systems Principles, November 1975, pp. 6—13. (S174) Slutz D. R., Traiger I. L., "A Note on the Calculation of Average Working Set Size", CACM, Vol. 17, No. 10, October 1974, pp. 563—565. (Sm76) Smith A. J., "A Modified Working Set Paging Algorithm", IEEE Trans, on Computers, Vol. C-25, No. 9, September 1976. pp. 907—914 (Sm78) Smith A. J., "Sequential Program Prefetching in Memory Hierarchies" Computer, Vol. 11. No 12, December 1978, pp. 7—21. (Sn78) Snyder R., "On a Priori Program Restructuring for Virtual Memorv Systems , Proc. 2nd Intl. Colloq. on Operating Systems,, Ш1А, October 19/8. (Sp72) Spirn J. R., Denning P. J., "Experiments with Program locality" AFIPS Cont. Proc., Vol. 41, 1972 FJCC, pp. 611-621. (Sp77) Spirn J. R., Program. Behavior: Models and Measurement, Elsevier/North-Holland, 1977. (Tr76) Trivedi K. S., "Prepaging and Applications to Array Algorithms", IEEB Trans, on Computers, Vol. C-25, September 1976, pp. 915—921. (Vo81) Vogt P. D., "Virtual Memory Extension for an Existing Minicomputer", Computer Design, July 1981, pp. 151—156. (We69) Weizer N., Openheimer G., "Virtual Memory Management in a Paging Environment", AFIPS Conf. Proc., Vol. 34, 1969 SJCC, pp. 234. (Wi73) Wilkes M. V., "The Dynamics of Paging", Computer Journal, Vol. 16» February 1973, pp. 4—9.