Разработка операционных систем

РАЗМЕЩАЕТСя ОДИН ПРОЦЕСС.

Наиболее простой и наименее эффективный режим MFT соответствует

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

соответствующего раздела.

В этом случае, если соответствующий раздел занят, то процесс остается

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

свободны.

Уменьшить фрагментацию при мультипрограммировании с фиксированными

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

Такой модуль может быть загружен в любой свободный раздел после

соответствующей настройки.

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

имеются две причины фрагментации. Первая — размер загруженного процесса

меньше размера, занимаемого разделом (внутренняя фрагментация), вторая —

размер процесса в очереди больше размера свободного раздела, и этот раздел

остается свободным (внешняя фрагментация).

Для защиты памяти при мультипрограммировании с фиксированным

разделами необходимы два регистра. Первый — регистр верхней границы

(наименьший адрес), второй — регистр нижней границы (наибольший адрес).

Прежде чем программа в разделе N начнет выполняться, ее граничные

адреса загружаются в соответствующие регистры. В процессе работы программы

все формируемые ею адреса контролируются на удовлетворение неравенства

а < Адр. < б

При выходе любого адреса программы за отведенные ей границы, работа

программы прерывается.

3.2.3. Мультипрограммирование с переменными разделами.

(multiprogramming with a

variable number of tasks (MVT).

МЕТОД MULTIPROGRAMMING WITH A VARIABLE NUMBER OF TASKS ПРЕДПОЛАГАЕТ

РАЗДЕЛЕНИЕ ПАМяТИ НА РАЗДЕЛЫ И ИСПОЛЬЗОВАНИЕ ЗАГРУЗОчНЫХ МОДУЛЕЙ В

ПЕРЕМЕЩАЕМЫХ АДРЕСАХ, ОДНАКО, ГРАНИЦЫ РАЗДЕЛОВ НЕ ФИКСИРУЮТСя.

| | | | | |0|ОС |

|90 Кб | | | | |а|Раздел 1 |

|П5 |П4 |П3 |П2 |П1 | |Раздел 2 |

| | | | | | |Раздел 3 |

| | | | | | |Раздел 4 |

| | | | | | |80 Кб |

Как следует из рисунка, в начальной фазе отсутствует фрагментация,

связанная с тем, что размер очередного процесса меньше размера, занимаемого

этим процессом раздела. На этой фазе причиной фрагментации является

несоответствие размера очередного процесса и оставшегося участка памяти. По

мере завершения работы программы освобождаются отдельные разделы. В том

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

разделы объединяются.

| | | |0|ОС |

| | |90 Кб |а|Раздел 1 |

|П7 |П6 |П5 | |100 Кб |

| | | | | |

| | | | |Раздел 4 |

| | | | | |

За счет объединения или слияния смежных разделов образуются большие

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

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

фрагментации, что и для метода MFT.

3.2.4. Мультипрограммирование с переменными разделами и уплотнением памяти.

ЯСНО, чТО МЕТОД MULTIPROGRAMMING WITH A VARIABLE NUMBER OF TASKS

ПОРОЖДАЕТ В ПАМяТИ МНОЖЕСТВО МАЛЫХ ФРАГМЕНТОВ, КАЖДЫЙ ИЗ КОТОРЫХ МОЖЕТ БЫТЬ

НЕДОСТАТОчЕН ДЛя РАЗМЕЩЕНИя ОчЕРЕДНОГО ПРОЦЕССА, ОДНАКО СУММАРНЫЙ РАЗМЕР

ФРАГМЕНТОВ ПРЕВЫШАЕТ РАЗМЕР ЭТОГО ПРОЦЕССА.

Уплотнением памяти называется перемещение всех занятых разделов по

адресному пространству памяти. Таким образом, чтобы свободный фрагмент

занимал одну связную область.

На практике реализация уплотнения памяти сопряжена с усложнением

операционной системы и обладает следующими недостатками:

1. в тех случаях, когда мультипрограммная смесь неоднородна по отношению к

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

расходует ресурс процессорное время и компенсирует экономию ресурса

памяти.

1. во время уплотнения все прикладные программы переводятся в состояние

“ожидание”, что приводит к невозможности выполнения программ в реальном

масштабе времени.

3.2.5. Основные стратегии заполнения

свободного раздела.

РАССМОТРЕННЫЕ МЕТОДЫ МУЛЬТИПРОГРАММИРОВАНИя ПРЕДПОЛАГАЮТ НАЛИчИЕ

ВХОДНОЙ ОчЕРЕДИ/ОчЕРЕДЕЙ К РАЗДЕЛАМ ОСНОВНОЙ ПАМяТИ.

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

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

Алгоритм выбора может использовать одну из следующих трех стратегий:

1. стратегия наиболее подходящего (best fit strategy) выбирает процесс,

которому в освободившемся разделе наиболее тесно (выигрыш в памяти).

1. стратегия первого подходящего (first fit strategy) выбирает первый

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

1. стратегия наименее подходящего (last fit strategy) выбирает процесс,

которому в освободившемся разделе наиболее свободно (в этом случае

остающийся фрагмент часто достаточен для размещения еще одного процесса).

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

СТРАНИчНАя ОРГАНИЗАЦИя ПАМяТИ (PAGING) ОТНОСИТСя К МЕТОДАМ НЕСМЕЖНОГО

РАЗМЕЩЕНИя ПРОЦЕССОВ В ОСНОВНОЙ ПАМяТИ.

Основное достоинство страничной организации памяти заключается в том,

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

устранения внешней фрагментации и минимизации внутренней фрагментации.

3.3.1. Базовый метод.

АДРЕСНОЕ ПРОСТРАНСТВО ОСНОВНОЙ И ВНЕШНЕЙ ПАМяТИ РАЗБИВАЮТ НА БЛОКИ

ФИКСИРОВАННОГО РАЗМЕРА, НАЗЫВАЕМЫЕ СТРАНИчНЫЕ РАМКИ (FRAMES). ЛОГИчЕСКОЕ

АДРЕСНОЕ ПРОСТРАНСТВО ПРОГРАММЫ ТАКЖЕ РАЗБИВАЕТСя НА БЛОКИ ФИКСИРОВАННОГО

РАЗМЕРА, НАЗЫВАЕМЫХ СТРАНИЦАМИ (PAGES). РАЗМЕРЫ СТРАНИчНЫХ РАМОК И СТРАНИЦ

СОВПАДАЮТ. ПРОЦЕСС ЗАГРУЖАЕТСя В ПАМяТЬ ПОСТРАНИчНО, ПРИчЕМ КАЖДАя СТРАНИЦА

ПОМЕЩАЕТСя В ЛЮБУЮ СВОБОДНУЮ СТРАНИчНУЮ РАМКУ ОСНОВНОЙ ПАМяТИ.

Каждый адрес, генерируемый процессором, состоит из двух частей: П -

номер страницы (page number) и Д - смещение в пределах страницы (off set).

Номер страницы может использоваться как индекс для таблицы страниц (page

table).

Таблица страниц содержит начальные адреса f всех страничных рамок, в

которых размещена программа. Физический адрес определяется путем сложения

начального адреса страничной рамки f и смещения Д.

| | |Вторичная | |Таблица | |Основная |

| | |память | |страниц | |память |

| | | | |программы | | |

| | | | |А | | |

| | |стр. 0 | |1 | |стр. 0 |

| |программа |стр. 1 | |3 | | |

| |А |стр. 2 | |4 | |стр. 1 |

| | |стр. 3 | | |7 | |стр. 2 |

| | | | | | | |

| | | | | | | |

| | | | | | |стр. 3 | |

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

исключает внешнюю фрагментацию. Внутренняя фрагментация не превышает

величины page_size-Q_Elem, где page_size — размер страничной рамки, а

Q_Elem — минимальный адресуемый элемент основной памяти.

Для ускорения вычисления физического адреса операцию суммирования

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

|старшие разряды |младшие разряды | |

| |2n+|2n | |f |

| |1 | | | |

| | | |

| |2n-| |2n |Д |

| |1 | | | |

На рисунке заштрихованы незаполненные нулевые разряды. Для того чтобы

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

страничных рамок располагались только в старших разрядах (2n+1), а

следующие — только младших разрядов (20, 21, 22).

Например, при n=9 базовые адреса страничных рамок — это следующий

ряд: 512, 1024, 1536. Следовательно, размер страничной рамки равен 512

байт.

В современных операционных системах типичный размер страницы

составляет 2 Кб или 4 Кб.

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

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

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

указатель на таблицу страниц хранится в PCB соответствующего процесса.

3.3.2. Аппаратная поддержка страничной

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

ПРЕОБРАЗОВАНИЕ ЛОГИчЕСКОГО АДРЕСА В ФИЗИчЕСКИЕ ОСУЩЕСТВЛяЕТСя ДЛя

КАЖДОГО АДРЕСА, ГЕНЕРИРУЕМОГО ПРОЦЕССОРОМ, ПОЭТОМУ чАСТО ДЛя УСКОРЕНИя

ЭТОГО ПРОЦЕССА ПРИМЕНяЮТСя АППАРАТНЫЕ МЕТОДЫ. НА РИСУНКЕ ПРИВЕДЕНА СХЕМА,

ИЛЛЮСТРИРУЮЩАя МЕТОД, ИСПОЛЬЗУЮЩИЙ АССОЦИАТИВНЫЕ РЕГИСТРЫ (ASSOCIATIVE

REGISTERS).

Каждый ассоциативный регистр кроме операций чтения - записи может

обрабатывать операцию сравнения кода, поступающего на его вход с частью

кода, хранимого в регистре. Матрица ассоциативных регистров хранит часть

таблицы страниц. Номер страницы П подается одновременно на входы всех

ассоциативных регистров, которые параллельно выполняют операцию сравнения.

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

страничной рамки f того регистра, в котором про-

изошло совпадение кода.

В том случае, если требуемый номер страницы находится в таблице

страниц, то есть ни в одном из ассоциативных регистров не произошло

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

номер страничной рамки, а найденная строка таблицы страниц переписывается в

один из ассоциативных регистров.

Защита страничной памяти основана на контроле уровня доступа к каждой

странице, возможны следующие уровни доступа:

1. только чтение

1. и чтение и запись

1. только выполнение

В этом случае каждая страница снабжается трехбитным кодом уровня

доступа. При трансформации логического адреса в физический сравнивается

значение кода разрешенного уровня доступа с фактически требуемым. При их

несовпадении работа программы прерывается.

3.4. Сегментная организация памяти.

СТРАНИчНАя ОРГАНИЗАЦИя ПАМяТИ ПРЕДПОЛАГАЕТ, чТО РАЗДЕЛЕНИЕ ПРОГРАММЫ

НА СТРАНИЦЫ ОСУЩЕСТВЛяЕТ ОПЕРАЦИОННАя СИСТЕМА И ЭТО НЕВИДИМО ДЛя

ПРИКЛАДНОГО ПРОГРАММИСТА. БОЛЬШИНСТВО ТЕХНОЛОГИЙ ПРОГРАММИРОВАНИя ТАКЖЕ

ПРЕДПОЛАГАЕТ РАЗДЕЛЕНИЕ ПРОГРАММЫ НА МНОЖЕСТВО ЛОГИчЕСКИХ чАСТЕЙ —

ПОДПРОГРАММЫ, ПРОЦЕДУРЫ, МОДУЛИ И ТАК ДАЛЕЕ.

Сегментная организация памяти представляет собой метод несмежного

размещения, при котором программа разбивается на части (сегменты) на этапе

программирования. Отдельный сегмент хранит отдельную логическую часть

программы: программный модуль или структуру данных (массив), стек, таблица

и так далее.

3.4.1. Базовый метод сегментной организации памяти.

ОБЫчНО СЕГМЕНТЫ ФОРМИРУЮТСя КОМПИЛяТОРОМ, А НА ЭТАПЕ ЗАГРУЗКИ ИМ

ПРИСВАИВАЮТСя ИДЕНТИФИЦИРУЮЩИЕ НОМЕРА. ТАКИМ ОБРАЗОМ, ЛОГИчЕСКИЙ АДРЕС ПРИ

СЕГМЕНТНОЙ ОРГАНИЗАЦИИ ПАМяТИ СОСТОИТ ИЗ ДВУХ чАСТЕЙ: S И D, ГДЕ S — НОМЕР

СЕГМЕНТА, А D — СМЕЩЕНИЕ В ПРЕДЕЛАХ СЕГМЕНТА.

Трансформация логического адреса в физический осуществляется с

помощью таблицы сегментов (segment table).

Количество строк таблицы сегментов равно количеству сегментов

программы: S, limit, base. Limit — размер сегмента, base — начальный адрес

сегмента в памяти.

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

сегментов. С помощью таблицы сегментов определяется его начальный адрес

base в основной памяти. Значение limit используется для защиты памяти.

Смещение d должно удовлетворять неравенству 0

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

определяется как сумма начального адреса base и смещения d. В том случае,

если таблица сегментов имеет значительные размеры, она располагается в

основной памяти, а её начальный адрес и длина хранятся в специальных

регистрах STBR (segment table base register), STLR (segment table length

register). Для ускорения трансформации логического адреса в физический

операция суммирования часто заменяется операцией конкатенации (для этого

необходимо, чтобы начальные адреса сегментов были кратны некоторому числу

2n).Таблица сегментов (или её часть) располагается в ассоциативной памяти.

Защита сегментной памяти основана на контроле уровня доступа к

каждому сегменту. Например, сегменты, содержащие только код, могут быть

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

содержащие данные, помечают как доступные для чтения и записи.

3.4.2. Разделение сегмента между НЕСКОЛЬКИМИ процессами.

ПОСКОЛЬКУ СЕГМЕНТ яВЛяЕТСя ЛОГИчЕСКИ ЗАВЕРШЕННЫМ ПРОГРАММНЫМ МОДУЛЕМ,

ОН МОЖЕТ ИСПОЛЬЗОВАТЬСя РАЗЛИчНЫМИ ПРОЦЕССАМИ. СЕГМЕНТ НАЗЫВАЕТСя

РАЗДЕЛяЕМЫМ, КОГДА ЕГО НАчАЛЬНЫЙ АДРЕС И РАЗМЕР УКАЗАНЫ В ДВУХ И БОЛЕЕ

ТАБЛИЦАХ СЕГМЕНТОВ. НАПРИМЕР, ДВА ПРОЦЕССА МОГУТ ИСПОЛЬЗОВАТЬ ПОДПРОГРАММУ

SQRT, КОТОРАя ХРАНИТСя В ВИДЕ ОДНОЙ ФИЗИчЕСКОЙ КОПИИ.

На рисунке приведен пример, иллюстрирующий использование разделяемого

текстового редактора.

| |таблица | | | |

| |сегментов | | |основная |

| |процесса 1 | | |память |

| |limit|base | | | |

| |25286|43062| |43062 | |

| |4425 |68348| |68348 |редактор |

| | | | | |данные |

| | | |72773 |1 |

| |таблица | | | |

| |сегментов | | | |

| |процесса 2 | |90003 | |

| |limit|base | | |данные |

| |25286|43062| |98553 |2 |

| |8550 |90003| | | |

| | | | | | |

3.4.3. Фрагментация.

ПРОГРАММА ВО ВХОДНОЙ ОчЕРЕДИ ЗАГРУЖАЕТСя В ПАМяТЬ ПОСЕГМЕНТНО В ЛЮБЫЕ

СВОБОДНЫЕ РАЗДЕЛЫ ОСНОВНОЙ ПАМяТИ. ПРИ ЭТОМ, КАК ПРАВИЛО, ИСПОЛЬЗУЮТСя

СТРАТЕГИИ BEST FIT И FIRST FIT. СЕГМЕНТНОЙ ОРГАНИЗАЦИИ ПАМяТИ ПРИСУЩИ КАК

ВНУТРЕННяя, ТАК И ВНЕШНяя ФРАГМЕНТАЦИИ. ВНУТРЕННяя ФРАГМЕНТАЦИя ОБРАЗУЕТСя

ВСЛЕДСТВИЕ ТОГО, чТО РАЗМЕР ЗАГРУЖАЕМОГО СЕГМЕНТА МЕНЬШЕ РАЗМЕРА ИМЕЮЩЕГОСя

СВОБОДНОГО РАЗДЕЛА, А ВНЕШНяя ВСЛЕДСТВИЕ ТОГО, чТО ОТСУТСТВУЕТ УчАСТОК

ПАМяТИ ПОДХОДяЩЕГО РАЗМЕРА. ВНЕШНяя ФРАГМЕНТАЦИя ОЗНАчАЕТ, чТО чАСТЬ

ПРОЦЕССА ОСТАЕТСя НЕЗАГРУЖЕННОЙ, И ЕГО ВЫПОЛНЕНИЕ В КАКОЙ–ТО МОМЕНТ ВРЕМЕНИ

ДОЛЖНО БЫТЬ ПРИОСТАНОВЛЕНО.

Очень часто сегментация комбинируется со страничированием. Это

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

страничной организации и естественное расчленение программы по сегментам.

Сегментация и страничирование используется об операционных системах

OS/2 для управления компьютерами.

4. Управление виртуальной памятью.

ВСЕ МЕТОДЫ УПРАВЛЕНИя ПАМяТЬЮ ИМЕЮТ ОДНУ И ТУ ЖЕ ЦЕЛЬ — ХРАНИТЬ В

ПАМяТИ МУЛЬТИПРОГРАММНУЮ СМЕСЬ, НЕОБХОДИМУЮ ДЛя МУЛЬТИПРОГРАММИРОВАНИя.

РАССМОТРЕННЫЕ РАНЕЕ МЕТОДЫ ПРЕДПОЛАГАЛИ, чТО ВСя ПРОГРАММА ПЕРЕД

ВЫПОЛНЕНИЕМ ДОЛЖНА БЫТЬ РАЗМЕЩЕНА В ОСНОВНОЙ ПАМяТИ. ВИРТУАЛЬНАя ПАМяТЬ —

ЭТО ТЕХНОЛОГИя, КОТОРАя ПОЗВОЛяЕТ ВЫПОЛНяТЬ ПРОЦЕСС, КОТОРЫЙ МОЖЕТ ТОЛЬКО

чАСТИчНО РАСПОЛАГАТЬСя В ОСНОВНОЙ ПАМяТИ. ТАКИМ ОБРАЗОМ, ВИРТУАЛЬНАя ПАМяТЬ

ПОЗВОЛяЕТ ВЫПОЛНяТЬ ПРОГРАММЫ, РАЗМЕРЫ КОТОРЫХ ПРЕВЫШАЮТ РАЗМЕРЫ

ФИЗИчЕСКОГО АДРЕСНОГО ПРОСТРАНСТВА.

4.1. Страничирование по запросу (demand paging).

ВИРТУАЛЬНАя ПАМяТЬ чАЩЕ ВСЕГО РЕАЛИЗУЕТСя НА БАЗЕ СТРАНИчНОЙ

ОРГАНИЗАЦИИ ПАМяТИ, СОВМЕЩЕННОЙ СО СВОППИНГОМ СТРАНИЦ.

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

процессору. Таким образом, страничирование по запросу означает

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

основной памяти, а часть — во внешней.

1. в процессе выполнения новая страница не перемещается в основную память

до тех пор, пока в ней не возникла необходимость.

| |логичес| |таблица | | |физическа| |вторичная| |

| |кая | | | | |я | | | |

| |память | |страниц | | |память | |память | |

| | | |4 |v|0 | | | | |

| | | | |i|1 | | | | |

| | | |6 |v|2 | | | | |

| | | | |i|3 | | | | |

| | | | |i|4 |A | | | |

| | | |8 |v|5 | | | | |

| | | | |i|6 |C | | | |

Страницы: 1, 2, 3, 4, 5