Учебный курс Операционные среды, системы и оболочки

Юрий Дмитриевич

организация памяти
3. Управление виртуальной памятью
4. Алгоритм распределения страничных рамок

памятью, основанный на том, что все процессы, участвующие в мультипрограммной

обработке, хранятся во внешней памяти.
Процесс, которому выделен CPU, временно перемещается в основную память (swap in/roll in). В случае прерывания работы процесса он перемещается обратно во внешнюю память (swap out/roll out).
Свопинг используют при приоритетном планировании CPU. С целью освобождения памяти для высокоприоритетных процессов, низкоприоритетные процессы перемещаются во внешнюю память.
Основное применение свопинг находит в системах разделения времени.

времени на загрузку или выгрузку процессов (используются модифицированные варианты свопинга).
Методы

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

программы ограничивается размером ОЗУ. При смежном размещении для загрузки программы,

размеры которых превышают размеры ОЗУ, используют метод оверлейных сегментов (overlay segments)
Оверлейную структуру программы и последовательность загрузки оверлейных сегментов планирует программист.
В процессе выполнения программы все ее адреса не должны быть меньше числа а. В противном случае возможна запись результата работы программы поверх ОС и уничтожение некоторых ее частей. Защиту ОС можно осуществить с помощью регистра границы.
Все адреса, генерируемые CPU, сравниваются с содержимым регистра границы. Если генерируется адрес меньше числа а, работа программы прерывается.

адресного пространства на ряд разделов фиксированного размера (в каждом разделе

размещается один процесс).

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

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

.

имеются две причины фрагментации:
размер загруженного процесса меньше размера, занимаемого

разделом (внутренняя фрагментация),
размер процесса в очереди больше размера свободного раздела, и этот раздел остается свободным (внешняя фрагментация).

Для защиты памяти при мультипрограммировании с фиксированным количеством разделов необходимы два регистра:
- регистр верхней границы (наименьший адрес),
- регистр нижней границы (наибольший адрес).
Прежде чем программа в разделе N начнет выполняться, ее граничные адреса загружаются в соответствующие регистры. В процессе работы программы все формируемые ею адреса контролируются на удовлетворение неравенства а < Адр. < б.
При выходе любого адреса программы за отведенные ей границы работа программы прерывается.

памяти на разделы и использование загрузочных модулей в перемещаемых адресах,

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

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

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

предполагают наличие входной очереди/очередей к разделам основной памяти.

Алгоритмы выбора ОС

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

несмежного размещения процессов в основной памяти.
Достоинство - позволяет свести к

минимуму общую фрагментацию за счет полного устранения внешней фрагментации и минимизации внутренней фрагментации.

Базовый метод.
Адресное пространство основной и внешней памяти разбивают на блоки фиксированного размера, называемые страничные рамки (frames).
Логическое адресное пространство программы разбивается на блоки фиксированного размера, называемые страницами (pages).
Размеры страничных рамок и страниц совпадают.
Процесс загружается в память постранично, причем каждая страница помещается в любую свободную страничную рамку основной памяти.

частей:
н — номер страницы (page number)
с — смещение в

пределах страницы (offset).
Номер страницы может использоваться как индекс для таблицы страниц (page table).
Таблица страниц содержит начальные адреса всех страничных рамок, в которых размещена программа.
Физический адрес определяется путем сложения начального адреса страничной рамки и смещения с.
Страничная организация памяти полностью исключает внешнюю фрагментацию. Внутренняя фрагментация не превышает величины page size-QElem, где page size — размер страничной рамки, a QElem — минимальный адресуемый элемент основной памяти.

заменяют операцией конкатенации.

Для того чтобы операция конкатенации была возможна, необходимо,

чтобы базовые адреса страничных рамок располагались только в старших разрядах (2n+1), а следующие — только в младших разрядах (2°, 21, 22).

Каждая операционная система поддерживает свой собственный метод работы с таблицей страниц.

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

адреса в физические осуществляется для каждого адреса, генерируемого процессором, поэтому

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

в таблице страниц, т. е. ни в одном из ассоциативных

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

памяти мультипрограммную смесь, необходимую для мультипрограммирования.
Виртуальная память — это

технология, которая позволяет выполнять процесс, который может только частично располагаться в основной памяти (виртуальная память позволяет выполнять программы, размеры которых превышают размеры физического адресного пространства).
Перемещение страниц по запросу (demand paging). Виртуальная память реализуется на базе страничной организации памяти, совмещенной со свопингом страниц.
Свопингу подвергаются только те страницы, которые необходимы процессору. Перемещение страниц по запросу означает:
программа может выполняться CPU, когда часть страниц находится в основной памяти, а часть — во внешней;
в процессе выполнения новая страница не перемещается в основную память до тех пор, пока в ней не возникла необходимость.

основной памятью каждая строка таблицы страниц дополняется битом местонахождения страницы

(valid/invalid bit).

В том случае, если процессор пытается использовать страницу, помеченную значением invalid, возникает событие, называемое страничная недостаточность (paging fault).
Страничная недостаточность вызывает прерывание выполнения программы и передачу управления операционной системе.

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

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

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

выполнение процесса даже в том случае, когда ни одна страница

этого процесса не загружена в основную память.

Вторичная память, используемая при обмене страниц по запросу, — это высокоскоростное дисковое устройство, называемое оборудованием свопинга (swap device), а часть используемого дискового пространства — пространство свопинга (swap space).

ОС может обнаружить, что все страничные рамки основной памяти заняты

и, следовательно, невозможно загрузить требуемую страницу.
Возможны следующие режимы:
приостановка прерванного процесса,
уменьшение на единицу количества процессов мультипрограммной смеси для освобождения всех ею занимаемых страничных рамок,
использование метода замещения страниц.
Метод замещения страниц состоит в том, что в основной памяти выбирается наименее важная/используемая страница, называется страница-жертва (victim page), которая временно перемещается в пространство свопинга, а на ее место загружается страница, вызываемая страничной недостаточностью.

по следующему алгоритму:
определяется местонахождение страницы путем анализа бита местонахождения;
если значение

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

пространство свопинга;
требуемая страница перемещается в освободившуюся страничную рамку.

Для учета факта

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

Для практического использования метода обмена страниц по запросу необходимы два алгоритма:
алгоритм распределения страничных рамок (frame allocation algorithm);
алгоритм замещения страниц (page replacement algorithm).

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

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

FIFO (first in first out).
Алгоритм ассоциирует с каждой страницей время, когда эта страница была помещена в память. Для замещения выбирается наиболее старая страница.
Учет времени необязателен, когда все страницы в памяти связаны в FIFO-очередь, а каждая помещаемая в память страница добавляется в хвост очереди.
Алгоритм учитывает только время нахождения страницы в памяти, но не учитывает используемость страницы.

количества замещенных страниц к количеству ссылок.
Алгоритм строится по следующему

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

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

выбирает для замещения ту страницу, на которую не было ссылки

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

Два подхода при внедрении алгоритма:
подход на основе логических часов (счетчика) — ассоциируют с каждой строкой таблицы поле «время использования», а в CPU добавляются логические часы.
подход на основе стека номеров страниц — стек номеров страниц хранит номера страниц, упорядоченных в соответствии с историей их использования, на «вершине» стека располагается только что использованная страница, а на «дне» дольше всех не используемая страница.