Вопросы

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

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

 

Чтобы определить оптимальный размер страницы для данной системы, необходимо учитывать ряд соображений:

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

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

· Ввод-вывод более эффективен при больших размерах страниц.

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

 

 

1. Оцените с точки зрения принципа оптимальности следующие

нетрадиционные алгоритмы выталкивания страниц применительно к мультипрограммной системе с виртуальной памятью:

· “Глобальный LIFO”- выталкивается страница, самой последей поступившая в память;

· “Локальный LIFO”- выталкивается самая последняя по времени поступления страница, вызванная процессом, который запросил новую страницу;

· “Утомленная страница” - выталкивается страница, подвергшаяся наиболее интенсивным обращениям в системе;

· “Истрепанная страница”- выталкивается страница., подвергшаяся наиболее интенсивным модификациям в системе.

2. Одна из сложностей реализации стратегии управления памятью по

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

3. Перечислите несколько причин, по которым на некоторые страницы

должен действовать запрет на выталкивание из ОП.

4. Предположим, что блок управления памятью принимает решение о том,

какую страницу следует вытолкнуть исключительно на основе анализа

битов-признаков обращения и модификации страницы. Приведите

несколько примеров некорректных решений..

5. Почему в общем случае целесообразнее выталкивать немодифицированную

страницу, а не страницу, подвергшуюся модификации?

6. Для каждой из приведенных ниже пар стратегий выталкивания страниц

укажите последовательность обращений, при которой обе стратегии выбрали бы для выталкивания одну и ту же страницу:

· LRU, NUR;

· LRU, LFU;

· LRU, FIFO

· NUR, FIFO

7. Отмечалось, что стратегию FIFO достаточно просто реализовать, но

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

8. Приведите аргументы за и против страницы малых размеров (страницы

больших размеров).

9. Объясните как влияет стиль программирования на скоростные

характеристики системы со страничной организацией. Рассмотрите

следующие подходы:

· модульность;

· минимальное использование операторов goto.

10. Приведите сходства и различия между страничной и сегментной

оргаизацией памяти.

11.Укажите общие и отличительные признаки систем с чисто сегментной и

комбинированной странично-сегментной организацией.памяти.

12.Каким образом эволюционировали виды организации памяти.

13.Рассмотрите иерархическую организацию памяти.


 

Дополнительный материал

 

СВОПИНГ В ОС UNIX

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

 

1. Управление пространством на устройстве выгрузки

 

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

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

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

 

алгоритм malloc /* алгоритм выделения пространства с ис-   пользованием карты памяти */   входная информация: (1) адрес /* указывает на тип ис-   пользуемой карты */   (2) требуемое число единиц ресурса   выходная информация: адрес - в случае успешного завершения   0 - в противном случае   {   для (каждой строки карты)   {   если (требуемое число единиц ресурса располагается в   строке карты)   {   если (требуемое число == числу единиц в строке)   удалить строку из карты;   в противном случае   отрегулировать стартовый адрес в строке;   вернуть (первоначальный адрес строки);   }   }   вернуть (0);   }

. Алгоритм выделения пространства с помощью карт памяти

Освобождая ресурсы, ядро ищет для них соответствующее место в карте по адресу. При этом возможны три случая:

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

2. Освободившиеся ресурсы частично закрывают пробел в карте памяти. Если они имеют адрес, смежный с адресом ресурсов из строки, непосредственно предшествующей или непосредственно следующей за данной (но не с адресами из обеих строк), ядро переустанавливает значение адреса и числа ресурсов в соответствующей строке с учетом вновь освободившихся ресурсов. Число строк в карте памяти остается неизменным.

3. Освободившиеся ресурсы частично закрывают пробел в карте памяти, но их адреса не соприкасаются с адресами каких-либо других ресурсов карты. Ядро создает новую строку и вставляет ее в соответствующее место в карте.

 

 

В традиционной реализации системы UNIX используется одно устройство выгрузки, однако в последних редакциях версии V допускается уже наличие множества устройств выгрузки. Ядро выбирает устройство выгрузки по схеме "кольцевого списка" при условии, что на устройстве имеется достаточный объем непрерывного адресного пространства. Администраторы могут динамически создавать и удалять из системы устройства выгрузки. Если устройство выгрузки удаляется из системы, ядро не выгружает данные на него; если же данные подкачиваются с удаляемого устройства, сначала оно опорожняется и только после освобождения принадлежащего устройству пространства устройство может быть удалено из системы.

2. Выгрузка процессов

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

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

2. Произведено обращение к системной функции brk, увеличивающей размер процесса.

3. Размер процесса увеличился в результате естественного увеличения стека процесса.

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

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

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

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

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

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