Ответы 190 страниц (1184228), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

· Теория вычислимости, в частности проблема останова (Mi67, Не77), говорит о том, что путь, который выберет программа при своем выполнении, точно предсказать невозможно. Поэтому любая попытка заранее загрузить страницы в память в предвидении того, что они потребуются в работе, может оказаться неудачной — будут загружены не те страницы.

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

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

Подкачка страниц по запросу, как показывает рис. 9.7, имеет свои проблемы. Процесс должен накапливать в памяти, требуемые ему страницы по одной. При появлении ссылки на каждую новую страницу процессу приходится ждать, когда эта страница будет передана в основную память. В зависимости от того, сколько страниц данного процесса уже находятся в основной памяти, эти периоды ожидания будут обходиться все более дорого, поскольку ожидающие процессы будут занимать все больший объем памяти. Рис. 9.7 иллюстрирует понятие произведения «пространство— время», которое часто применяется в операционных системах для оценки использования памяти процессом. Произведение «пространство—время» соответствует площади «под кривой» на этом рисунке. Оно является комплексным показателем, отражающим как объем, так и время использования памяти процессом. Уменьшение произведения «пространство—время» за счет периодов ожидания процессом нужных ему страниц является важнейшей целью всех стратегий управления памятью.

9.6 Подкачка страниц с упреждением

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

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

Метод подкачки страниц с упреждением характеризуется следующими преимуществами:

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

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

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

9.8 Освобождение страниц

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

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

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

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

9.9 Размер страниц

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

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

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

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

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

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

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

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

Большинство приводящихся в литературе данных (De80), как теоретических, так и эмпирических, указывает на то, что необходимы страницы малых размеров.

Ассоциативаня память

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

1924021

9448304

3336167

Для получения номера телефона второго абонента следует обратиться: load (2) и получить в регистре ответа R = 9448304. Такой вид памяти, при котором необходимая информация определяется номером строки памяти, называется адресной. Другой вид оперативной памяти – ассоциативной можно рассматривать также как двумерную таблицу, но у каждой строки которой есть дополнительное поле, поле ключа. Например:

Ключ Содержимое

Иванов 1924021

Петров 9448304

Сидоров 3336167

После обращение к ассоциативной памяти с запросом : load (Петров) для данного примера получим ответ: R = 9448304. Здесь задание координаты строки памяти производится не по адресу, а по ключу. Но при состоянии ассоциативной памяти:

Ключ Содержимое

1 1924021

2 9448304

3 3336167

можно получить номер телефона из второй строки запросом: load (2). Таким образом на ассоциативной памяти можно моделировать работу адресной. Ассоциативная память имеет очевидное преимущества перед адресной, однако, у нее есть большой недостаток - ее аппаратная реализация невозможна для памяти большого объема.

ВОПРОС: Предложите схему реализации модели ассоциативной памяти при помощи адресной.

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

Назначение и структура кэш-памяти.

Cache - это способ совместного функционирования двух типов запоминающих устройств, отличающихся временем доступа и стоимостью хранения данных, который позволяет уменьшить среднее время доступа к данным и экономить более дорогую быстродействующую память за счет динамического копирования в "быстрое" ЗУ (Кэш-память) наиболее часто используемой информации из "медленного" ЗУ.

Кэш - очень быстрая память сравнительно небольшого объема (обычно на статических микросхемах SRAM), логически располагающаяся между ЦП и оперативной памятью.

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

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

Алгоритм поиска и алгоритм замещения данных в кэше непосредственно зависят от того, каким образом основная память отображается на кэш-память. Существует три основных типа организации кэш-памяти, которые определяются принципом размещения строк в кэше.

Концепция кэш-памяти возникла раньше чем архитектура IBM/360, и сегодня кэш-память имеется практически в любом классе компьютеров, а в некоторых компьютерах - во множественном числе.

Все термины, которые были определены раньше могут быть использованы и для кэш-памяти, хотя слово "строка" (line) часто употребляется вместо слова "блок" (block).

Кэш-строка представляет собой полный набор данных, которым обмениваются кэш и основная память. В кэш-строке адрес двойного слова для 32-битной шины данных задается адресными битами А3-А2. Кэш-строка обычно является либо целиком действительной, либо целиком недействительной; она не может быть действительной частично. Если даже процессору нужно прочитать только один байт, то все равно все 16 байт соответствующей кэш-строки должны находиться в кэш-памяти SRAM; в противном случае происходит кэш-промах. Кэш-строка - это собственно кэш-память; кэш-директория используется только для управления ею. Кэш-строка обычно содержит большее число данных, чем можно передать за один цикл шины. По этой причины в большинстве кэш-контроллеров реализован пакетный режим, при котором предварительное задание адресных последовательностей обеспечивает более быструю передачу данных через шину. Это очень просто реализовать для заполнения кэш-строки и для обратной записи кэш-строк, поскольку в этих режимах всегда используется непрерывная и последовательно расположенная информация.

Полностью ассоциативная кэш-память.

Если некоторая строка основной памяти может располагаться на любом месте кэш-памяти, то такой кэш называется полностью ассоциативным (fully associative). Для того чтобы в дальнейшем можно было найти нужные данные в кэше, они помещаются туда вместе со своим адресом, то есть тем адресом, который данные имеют в оперативной памяти. При каждом запросе к оперативной памяти выполняется поиск в кэше, причем критерием поиска выступает адрес оперативной памяти из запроса. Каждый тег одновременно сравнивается с этим адресом (ассоциативный поиск - сравнение выполняется не последовательно с каждой записью кэша, а параллельно со всеми его записями, так как простой перебор приводит к недопустимо большим временным затратам). Если тег совпадает с адресом, то обеспечивается доступ к блоку памяти, связанному с этим тегом.

Такая организация позволяет достичь максимально возможного процента попаданий, однако скорость поиска снизится весьма значительно.

Дополнение

Память, адресуемая по содержанию

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

Характеристики

Список файлов ответов (шпаргалок)