следующую запись. Узлы списка на рис. 4.5, в, для которых требовались три слова и один бит (Р/Н), больше не нужны.

Еще один алгоритм распределения называется быстрым подходящий , он поддерживает отдельные списки для некоторых из наиболее часто запрашиваемых размеров. Например, могла бы существовать таблица с п записями, в которой первая запись указьшает на начало списка свободных фрагментов размером 4 Кбайт, вторая запись является указателем на список незанятых областей размером 8 Кбайт, третья - 12 Кбайт и т. д. Свободный фрагмент размером, скажем, 21 байт мог бы располагаться или в списке областей 20 Кбайт или в специальном списке участков дополнительных размеров. Согласно правилу быстрый подходящий поиск фрагмента требуемого размера происходит чрезвычайно быстро. Но этот алгоритм имеет тот же недостаток, что и прочие схемы, которые сортируют свободные области по размеру, а именно: если процесс завершается или выгружается на диск, поиск его соседей с целью узнать, возможно ли их объединение, является затратной операцией. А если не производить слияния областей, память очень скоро окажется разбитой на офомное число маленьких свободных фрагментов, в которые не поместится ни один процесс.

4.3. Виртуальная память

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

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

Разработанный метод известен как виртуальная память [34]. Основная идея виртуальной памяти исходит из того, что совместный размер профаммы, данных и стека может превысить количество доступной физической памяти. Операционная система хранит части профаммы, использующиеся в настоящий момент, в оперативной памяти, остальные - на диске. Например, программа размером 16 Мбайт сможет работать на машине с 4 Мбайт памяти, если тщательно продумать, какие 4 Мбайт должны находиться в памяти в каждый момент времени. При этом части программы, находящиеся на диске, будут меняться местами с частями в памяти по мере необходимости.

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

4.3.1. Страничная организация памяти

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

MOVE REG.1000

она делает это для того, чтобы скопировать содержимое памяти по адресу 1000 в регистр REG (или наоборот, в зависимости от компьютера). Адреса могут формироваться с использованием индексации, базовых регистров, сегментных регистров и другими путями.

Блок процессора

Центральный процессор передает виртуальный адрес диспетчеру памяти

Центральный процессор

Память

Контроллер диска

Шина

Диспетчер памяти посылает физический адрес в память

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

Эти программно формируемые адреса, называемые виртуальными адресами, образуют виртуальное адресное пространство. На компьютерах без виртуальной памяти виртуальные адреса подаются непосредственно на шину памяти и при чтении или записи читается или записывается слово в физической памяти с тем же самым адресом. При применении виртуальной памяти виртуальные адреса не передаются напрямую шиной памяти. Вместо этого они направляются диспетчеру памяти (MMU - Memory Management Unit), который отображает виртуальные адреса на физические адреса, что продемонстрировано на рис. 4.7.

Очень простой пример того, как работает такого рода отображение, приведен на рис. 4.8. Мы рассматриваем компьютер, который может формировать 16-разрядные адреса, от О до 64 К. Это виртуальные адреса. Однако у этого компьютера есть только 32 Кбайт физической памяти, поэтому, хотя программы размером 64 Кбайт могут быть написаны, их нельзя целиком загрузить в память и запустить на выполнение. Полная копия образа памяти программы размером до 64 Кбайт должна присутствовать на диске, но в таком виде, чтобы ее можно было по мере надобности переносить в память по частям.

Пространство виртуальных адресов разделено на единичные блоки, называемые страницами. Соответствующие единицы в физической памяти называются страничными блоками (page frame). Страницы и их блоки имеют всегда одинаковый размер. В этом примере они равны 4 Кбайт, но в реальных системах использовались размеры от 512 байт до 64 Кбайт. Имея 64 Кбайт виртуального адресного пространства и 32 Кбайт физической памяти, мы получаем 16 виртуальных страниц и 8 страничных блоков. Передача данных между ОЗУ и диском всегда происходит в терминах страниц.

Когда программа пытается получить доступ к адресу О, например, с помощью команды

MOVE REG.О

виртуальный адрес О передается диспетчеру памяти (MMU). Диспетчер памяти видит, что этот виртуальный адрес попадает на страницу О (от О до 4095), а та отображается на страничный блок 2 (адреса от 8192 до 12287). Диспетчер переводит виртуальный адрес О в физический адрес 8192 и выставляет последний на щину. Память ничего не знает о диспетчере памяти и видит просто запрос на чтение или запись слова по адресу 8192 и выполняет запрос. Таким образом, диспетчер памяти эффективно отображает все виртуальные адреса между О и 4095 на физические адреса от 8192 до 12287. Точно так же инструкция

MOVE REG.8192

преобразуется в команду MOVE REG.24576

поскольку виртуальный адрес 8192 находится на виртуальной странице 2, а эта страница отображается на физический страничный блок 6 (физические адреса от 24576 до 28671). В качестве третьего примера рассмотрим виртуальный адрес 20500, который адресует 20-й байт от начала виртуальной страницы 5 (виртуальные адреса от 20480 до 24575) и отображается на физический адрес 12288 + + 20 = 12308.

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