УМК ОС. Учебнометодический комплекс дисциплины Операционные сиcтемы по кредитной технологии обучения для студентов специальности
 Скачать 2.3 Mb.
|
|
Тема лекций №7: Алгоритмы замещения страниц План 1. Алгоритмы замещения страниц. 2. Распределение памяти. 7.1 Алгоритмы замещения страниц Идеальный алгоритм заключается в том, что бы выгружать ту страницу, которая будет запрошена позже всех. Но этот алгоритм не осуществим, т.к. нельзя знать какую страницу, когда запросят. Можно лишь набрать статистику использования. 7.1.1 Алгоритм NRU (NotRecentlyUsed - не использовавшаяся в последнее время страница) Используются биты обращения (R-Referenced) и изменения (M-Modified) в таблице страниц. При обращении бит R выставляется в 1, через некоторое время ОС не переведет его в 0. M переводится в 0, только после записи на диск. Благодаря этим битам можно получить 4-ре класса страниц: не было обращений и изменений (R=0, M=0) не было обращений, было изменение (R=0, M=1) было обращение, не было изменений (R=1, M=0) было обращений и изменений (R=1, M=1) 7.1.2 Алгоритм FIFO (первая прибыла - первая выгружена) Недостаток заключается в том, что наиболее часто запрашиваемая страница может быть выгружена. 7.1.3 Алгоритм "вторая попытка" Подобен FIFO, но если R=1, то страница переводится в конец очереди, если R=0, то страница выгружается.  Алгоритм "вторая попытка" В таком алгоритме часто используемая страница никогда не покинет память. Но в этом алгоритме приходится часто перемещать страницы по списку. 7.1.4 Алгоритм "часы" Чтобы избежать перемещения страниц по списку, можно использовать указатель, который перемещается по списку.  Алгоритм "часы" 7.1.5 Алгоритм LRU (LeastRecentlyUsed - использовавшаяся реже всего) Первый метод: Чтобы реализовать этот алгоритм, можно поддерживать список, в котором выстраивать страницы по количеству использования. Эта реализация очень дорога. Второй метод: В таблице страниц добавляется запись - счетчик обращений к странице. Чем меньше значение счетчика, тем реже она использовалась. 7.1.6 Алгоритм "рабочий набор" Замещение страниц по запросу - когда страницы загружаются по требованию, а не заранее, т.е. процесс прерывается и ждет загрузки страницы. Буксование - когда каждую следующую страницу приходится процессу загружать в память. Чтобы не происходило частых прерываний, желательно чтобы часто запрашиваемые страницы загружались заранее, а остальные подгружались по необходимости. Рабочий набор - множество страниц (к), которое процесс использовал до момента времени (t). Т.е. можно записать функцию w(k,t).  Зависимость рабочего набора w(k,t) от количества запрошенных страниц Т.е. рабочий набор выходит в насыщение, значение w(k,t) в режиме насыщения может служить для рабочего набора, который необходимо загружать до запуска процесса. Алгоритм заключается в том, чтобы определить рабочий набор, найти и выгрузить страницу, которая не входит в рабочий набор. Этот алгоритм можно реализовать, записывая, при каждом обращении к памяти, номер страницы в специальный сдвигающийся регистр, затем удалялись бы дублирующие страницы. Но это дорого. В принципе можно использовать множество страниц, к которым обращался процесс за последние t секунд. Текущее виртуальное время (Tv) - время работы процессора, которое реально использовал процесс. Время последнего использования (Told) - текущее время при R=1, т.е. все страницы проверяются на R=1, и если да то текущее время записывается в это поле. Теперь можно вычислить возраст страницы (не обновления) Tv-Told, и сравнить с t, если больше, то страница не входит в рабочий набор, и страницу можно выгружать. Получается три варианта: если R=1, то текущее время запоминается в поле время последнего использования если R=0 и возраст > t, то страница удаляется если R=0 и возраст =< t, то эта страница входит в рабочий набор 7.1.7 Алгоритм WSClock Алгоритм основан на алгоритме "часы", но использует рабочий набор. Используются битов R и M, а также время последнего использования.  Работа алгоритма WSClock Это достаточно реальный алгоритм, который используется на практике. 7.2 Распределение памяти 7.2.1 Политика распределения памяти Алгоритмы замещения бывают: локальные глобальные  Пример глобального и локального алгоритма В целом глобальный алгоритм работает лучше. Можно поровну распределять страничные блоки между процессами. Такой подход справедлив, но не эффективен, т.к. процессы разные. Можно распределять страничные блоки между процессами, в зависимости от размеров процесса Размер процесса динамически меняется, поэтому определить размер динамически сложно. Частота страничных прерываний - может служить показателем потребности процесса в страницах. Чем больше частота, тем больше памяти необходимо процессу.  Зависимость частоты страничных прерываний от размеров памяти предоставленной процессу Если частота стала ниже линии В, то памяти процессу предоставлено слишком много. Если частота стала выше линии А, то памяти процессу предоставлено слишком мало. Если всем процессам не хватает памяти (происходит пробуксовка), то производится выгрузка какого то процесса на диск. 7.2.2 Размеры страниц Есть два крайних случая: Маленькие страницы - улучшает распределение памяти, но увеличивает таблицу и частые переключения уменьшают производительность. Большие страницы - наоборот. 7.2.3 Совместно используемые страницы Отдельные пространства команд и данных  Пример разделения пространства команд и данных Совместно используемые страницы Два процесса могут содержать в таблицах страниц указатели на общие страницы. В случае разделения пространств команд и данных это легко реализуется. Эти данные используются в режиме чтения. В UNIX, когда создается дочерний процесс, у родительского и дочернего процесса общее пространство данных, и только если один из процессов попытается изменить данные, происходит прерывание и создание копии этой страницы, если записи не происходит, то оба процесса продолжают работать с общей памятью. Это приводит к экономии памяти. 7.2.4 Политика очистки страниц Лучше всегда держать в запасе свободные блоки, освобождая их заранее, чем при нехватке памяти, искать и освобождать их. Страничный демон - программа, периодически проверяющая состояние памяти, если занято много блоков, то производит выборочную выгрузку страниц. 7.3 Особенности реализации в UNIX В UNIX системах последовательность запуска процессов, следующая: процесс 0 - это свопер процесс 1 - это init процесс 2 - это страничный демон Страничный демон просыпается каждые 250мс, и проверяет количество свободных страничных блоков, если их меньше 1/4 памяти, то он начинает выгружать страницы на диск. Он использует модифицированный алгоритм часов, и он является глобальным (т.е. он не различает, какому процессу принадлежит страница). Каждые несколько секунд свопер проверяет, есть ли на диске готовые процессы для загрузки в память для выполнения. При этом сам код программы в своп-файле не сохраняется, а подкачивается непосредственно из файла программы. В LUNIX системе нет предварительной загрузки страниц и концепции рабочего набора. Тексты программ и отображаемые файлы подгружаются прямо из файлов расположенных на диске. Все остальное выгружается в раздел свопинга или файлы свопинга (их может быть от 0 до 8). Алгоритм выгрузки страниц основан на страничном демоне (kswapd), он активизируется раз в секунда и проверяет достаточно ли свободных страниц. Демон может быть активизирован и принудительно, при не хватке памяти. Демон состоит из трех процедур: В первой используется алгоритм часов, она ищет редко используемые страницы страничного кэша и буферного кэша файловой системы. Вторая процедура ищет совместно редко используемые страницы. Третья ищет редко используемые страницы одиночных пользователей. Сначала сканируются страницы у того процесса, у которого их больше всего. В LINUX есть еще один демон - bdflush. Он регулярно просыпается и проверяет, не превысило ли определенное значение количество измененных страниц, если да то он начинает их принудительно сохранять на диск. 7.4 Особенности реализации в Windows В Windows системах сегментация (следующая лекция) не поддерживается. Поэтому каждому процессу выделяется виртуальное адресное пространство в 4 Гбайт (ограничение 32 разрядов). Нижние 2 Гбайт доступны для процесса, а верхние 2 Гбайт отображаются на память ядра. В Advanced server и Datacenter server процесс может использовать до 3 Гбайт. Страницы имеют фиксированный размер (на процессорах Pentium 4 Кбайт, на Itanium 8 или 16 Кбайт) и подгружаются по требованию.  Конфигурация виртуального адресного пространства Windows Белым цветом выделены области приватных данных процесса. Затемнены области, совместно используемые всеми процессами. Области в 64 Кбайт в начале и в конце, используются для защиты виртуального адресного пространства процесса, при попытке чтения или записи в эти области будет вызвано прерывание. Системные данные содержат указатели и таймеры, доступные на чтение другим процессам. Отображение верхней части на память ядра, позволяет при переключении потока в режим ядра не менять карту памяти. У страниц есть три состояния: свободное - не используется фиксированное - данные отображены в странице зарезервированное - зарезервировано, но не занято данными (при создании потока) Файлы свопинга может быть до 16, разделов свопинга нет. В файлах свопинга хранятся только изменяемые страницы. Опережающая подкачка в Windows не используется. В Windows используется понятие рабочий набор. Страничный демон в Windows состоит из : менеджера балансового множества - проверяет, достаточно ли свободных страниц. менеджера рабочих наборов - который исследует рабочие наборы и освобождает страницы. Также в Windows есть следующие демоны: свопер-демон демон записи отображенных страниц - запись в отображенные файлы демон записи модифицированных страниц Тема лекций №:8 Сегментация памяти План 1. Основные понятия сегментации. 2. Реализации сегментации. 8.1 Основные понятия сегментации Рассмотрим пример, когда программа использует одно адресное пространство.  программа использует одно адресное пространство Недостатки такой системы: Один участок может полностью заполниться, но при этом останутся свободные участки. Можно конечно перемещать участки, но это очень сложно. Эти проблемы можно решить, если дать каждому участку независимое адресное пространство, называемое сегментом. Рассмотрим то же пример с использованием сегментов:  Сегментированная память Каждый сегмент может расти или уменьшаться независимо от других. Сегмент - это логический объект. В этом случае адрес имеет две части: номер сегмента адрес в сегменте Преимущества сегментации: Сегменты не мешают друг другу. Начальный адрес процедуры всегда начинается с (n,0). Что упрощает программирование. Облегчает совместное использование процедур и данных. Раздельная защита каждого сегмента (чтение, запись). 8.2 Реализация сегментации Если страницы имеют фиксированный размер, то сегменты нет. У сегментов так же, как и у страниц, существует проблема фрагментации. Т.к. памяти часто не хватает, стали использовать страничную организацию сегментов. При которой в памяти может находиться только часть сегмента. 8.2.1 Сегментация с использованием страниц: MULTICS В одной из первых, где была применена страничная сегментация, была система MULTICS. Каждая программа обеспечивалась до 2^18 сегментов (более 250 000), каждый из которых мог быть до 65 536 (36-разрядных) слов длиной. Таблица сегментов - хранит дескриптор для каждого сегмента. У каждой программы своя таблица. Т.к. записей в таблице более 250 000, она сама разбита на страницы. Сама таблица является отдельным сегментом.  Сегмент с таблицей дескрипторов указывающих на таблицы страниц для каждого сегмента Нормальный размер страницы равен 1024 словам. Если сегмент меньше 1024, то он либо не разбит на страницы, либо разбит на страницы по 64 слова.  Дескриптор сегмента Когда происходит обращение к памяти, выполняется следующий алгоритм: По номеру сегмента находится дескриптор сегмента. Проверяется, находиться ли таблица страницы в памяти. Если в памяти, определяется ее расположение. Если нет, вызывается сегментное прерывание. Проверяется, находиться ли страница в памяти. Если в памяти, определяется ее расположение в памяти. Если нет в памяти, вызывается страничное прерывание. К адресу начала страницы прибавляется смещение, в результате получаем адрес нужного слова в оперативной памяти. Происходит запись или чтение.  Преобразование адреса в системе MULTICS Так как такой алгоритм будет работать достаточно медленно. Аппаратура системы MULTICS содержит высокоскоростной буфер быстрого преобразования адреса (TLB) размером в 16 слов. Адреса 16 наиболее часто использующихся страниц хранятся в буфере. 8.2.2 Сегментация с использованием страниц: Intel Pentium Каждая программа обеспечивается до 16К сегментов, каждый из которых может быть до 1 млдр 36-разрядных слов длиной. Основа виртуальной памяти системы Pentium состоит из двух таблиц: Локальная таблица дескрипторов LDT (Local Descriptor Table) - есть у каждой программы, и описывает сегменты программы. Глобальная таблица дескрипторов GDT (Global Descriptor Table) - одна для всех программ, и описывает системные сегменты (включая саму ОС). Каждый селектор (указывает на дескриптор) представляет собой 16-разрядный номер.  Селектор в системе Pentium 13 битов определяют номер записи в таблице дескрипторов, поэтому эти таблицы ограничены, каждая содержит 8К (2^13) сегментных дескрипторов. 1 бит указывает тип используемой таблицы дескрипторов LDT или GDT.  Уровни привилегированности в системе Pentium Уровни привилегированности запрещают выполняемому коду обратиться к более низкому уровню. С учетом максимального размера сегмента - 4 Гбайта - каждая задача, при чисто сегментной организации виртуальной памяти, работает в виртуальном адресном пространстве в 64 Тбайта (4 Гбайта * 16К, где 16К=8К*2 т.к. LDT и GDT).  Дескриптор программного (не данных) сегмента в системе Pentium (всего 8 байт (64 бита)). База (Base) - базовый адрес сегмента (32-бита), разделен на три части из-за совместимости с i286, в котором это поле имеет только 24 бита. Размер (Limit) - размер сегмента (20 бит), разнесен на две части. Если размер сегмента указан в страницах, он может достигать 2^32 байтов (2^20 * 4Кбайт (2^12) (размер страницы в Pentium)). Алгоритм получение физического адреса: Селектор загружается в регистр (для сегмента команд в CS, для сегмента данных в DS). Определяется глобальный или локальный сегмент (LDT или GDT). Дескриптор извлекается из LDT или GDT, и сохраняется в микропрограммных регистрах. Если дескриптор в памяти и смещение не выходит за пределы сегмента, программа может продолжить работу, если нет, происходит прерывание. Система Pentium прибавляет базовый адрес к смещению, и получает линейный адрес, - если страничная организация памяти не используется, то он является физическим адресом (адрес получен), - если страничная организация памяти используется, то он является виртуальным адресом. В случае, если используется страничная организация памяти, линейный адрес переводится в физический с помощью таблицы страниц.  Преобразование пары (селектора, смещение) в физический адрес При 32-разрядном (2^32=4Гбайт) адресе и 4Кбатной странице, сегмент может содержать 1 млн страниц (4Гбайт/4Кбайта). Поэтому используется двухуровневое отображение (создана таблица (страничный каталог) содержащая список из 1024 таблиц страниц), благодаря чему можно снизить количество записей в таблице страниц до 1024. В этом случае сегмент в 4 Мбайта (1024 записи по 4 Кбайта страницы), будет иметь страничный каталог только с одной записью (и 1024 в таблице страниц), вместо 1 млн в одной таблице.  Отображение линейного адреса на физический адрес В системе Pentium также есть буфер быстрого преобразования адреса (TLB), в котором хранятся наиболее часто используемые комбинации Каталог-Страница на физический адрес страничного блока. Только если комбинация в TLB отсутствует, выполняется это алгоритм. 8.3 Особенности реализации в UNIX В LUNIX системе на 32-разрядной машине каждый процесс получает 3Гбайта виртуального пространства для себя, и 1Гбайт для страничных таблиц и других данных ядра. На компьютерах Pentium, используется двухуровневые таблицы страниц, и размер страниц фиксирован 4Кбайта На компьютерах Alpha, используется трехуровневые таблицы страниц, и размер страниц фиксирован 8Кбайт Для каждой программы выделяется 3 сегмента: Код программы (только для чтения) Данные Стек |