Распределение памяти между задачами

Задачи управления памятью. Распределение памяти

Главная задача любой ВС – выполнять программы. Чтобы процессор мог выполнять программу, ее коды и данные, с которыми программа работает, должны (по крайней мере, частично) находиться в оперативной (главной, основной) памяти ЭВМ. В реальной ВС используется не одно запоминающее устройство, а целый ряд устройств, обладающих различными характеристиками.

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

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

Т. е. программа помещается в некоторое виртуальное адресное пространство. Начальным адресом программы при этом обычно назначается нулевой адрес.

Со времен ЭВМ фон — Неймана основная память в компьютере организована как линейное (одномерное) адресное пространство, состоящее из последовательности машинных слов (позднее − байтов).

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

В одних ОС виртуальное адресное пространство подобно физической памяти и представляется в виде непрерывной линейной последовательности виртуальных адресов. Такую структуру адресов называют плоской (flat).

В большинстве современных ОС виртуальное адресное пространство структурировано. Т. е. оно делится на части, называемые сегментами, при этом виртуальный адрес представляется парой чисел (n, m), где n – номер сегмента, а m – смещение ячейки внутри сегмента.

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

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

Решение задач отображения виртуальных адресов на общую физическую память ВС может быть выполнено двумя способами.

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

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

Динамическое преобразование адресов позволяет перемещать программу в течение всего периода выполнения программы.

Существующие алгоритмы распределения памяти разделяют на два основных класса:

1. Алгоритмы, не использующие для решения задач распределения памяти HDD.

2. Алгоритмы, в которых используется перемещение отдельных сегментов процессов между ОП и HDD.

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

К алгоритмам второго класса относятся алгоритмы, предусматривающие размещение части кодов программ в оперативной памяти (активный процесс), а части кодов – на жестком диске (приостановленные процессы).

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

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

Вопросы для самопроверки по теме 4.1

1. Какие основные задачи решает ОС в процессе управления памятью?

2. Какие алгоритмы распределения памяти используются в ОС?

3. В чем заключается отличие метода распределения памяти с фиксированными разделами от метода распределения памяти динамическими разделами?

4. Чем отличается загрузка процессов при свопинге от загрузки процессов при страничной организации памяти?

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

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

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.

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

Общая задача распределения памяти и стратегии ее решения

ТЕМА 3. УПРАВЛЕНИЕ ПАМЯТЬЮ

Лекция 10. Страничная организация памяти.

План занятия:

1. Откачка и подкачка.

2. Смежное распределение памяти.

3. Общая задача распределения памяти и стратегии ее решения.

5. Страничная организация.

6. Реализация таблицы страниц.

7. Оценка среднего времени доступа к памяти с использованием TLB.

8. Защита памяти.

9. Структура таблицы страниц.

10. Хешированные таблицы страниц.

11. Инвертированные таблицы страниц.

12. Разделяемые страницы

Откачка и подкачка

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

Откачка и подкачка (swapping) –это действия операционной системы по откачке (записи)образа неактивного процесса на диск или подкачке (считыванию)активного процесса в основную память. Необходимость выполнения подобных действий вызвана нехваткой основной памяти.

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

Популярная разновидность стратегии откачки и подкачки – roll out / roll in: откачка и подкачка на базе приоритетов; более приоритетные процессы исполняются, менее приоритетные – откачиваются на диск.

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

В распространенных ОС – UNIX, Linux, Windows и др. – реализованы различные стратегии откачки и подкачки.

Схема откачки и подкачки изображена на рис. 1.

Рис. 1.Схема откачки и подкачки.

Смежное распределение памяти

Наиболее простая и распространенная стратегия распределения памятисмежное распределение памятираспределение памяти для пользовательских процессов в одной смежной области памяти. Основная память разбивается на две смежных части (partitions), которые «растут» навстречу друг другу: резидентная часть ОС и вектор прерываний – по меньшим адресам. Для пользовательских процессов память распределяется в одном и том же смежном участке памяти. Для каждого процесса регистр перемещения указывает на начало выделенной ему области памяти, регистр границы содержит длину диапазона логических адресов. Каждый логический адрес должен быть меньше содержимого регистра границы. Физический адрес вычисляется аппаратно как сумма логического адреса и значения регистра перемещения. Схема адресации с аппаратной поддержкой регистров перемещения и границы изображена на рис.2.

Рис. 2.Адресация с аппаратной поддержкой регистров перемещения и границы.

Общая задача распределения памяти и стратегии ее решения

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

Возникает общая задача распределения памяти: Имеется список свободных областей памяти и список занятых областей разного размера. Разработать и реализовать оптимальный (по некоторому критерию)алгоритм выделения свободного смежного участка памяти длины n(слов или байтов).

Для решения данной задачи применяются следующие стратегии: метод первого подходящего (first-fit), метод наиболее подходящего (best-fit)и метод наименее подходящего (worst-fit).Рассмотрим каждую из них подробнее.

Метод первого подходящего: Выбирается первый по списку свободный участок подходящего размера (не меньшего, чем n ). На первый взгляд, данная стратегия оптимальна, но далее мы увидим, что это не всегда так.

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

Метод наименее подходящего: Выбирается из списка подходящая область наибольшегоразмера. Почему наибольшего? Чтобы избежать фрагментации (проблема фрагментации подробно рассмотрена далее в данной лекции).

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

Читайте также  Ультразвуковая стиральная машинка

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

Фрагментация– это дробление памяти на мелкие не смежные свободные области маленького размера. Фрагментация возникает после выполнения системой большого числа запросов на память, таких, что размеры подходящих свободных участков памяти оказываются немного больше, чем требуемые. Например, если имеется 100 смежных свободных областей памяти по 1000 слов, то после выполнения 100 запросов на память по999 слов каждый в списке свободной памяти останутся 1000 областей по одному слову.

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

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

При компактировке памяти и анализе свободных областей может быть выявлена проблема зависшей задачи: какая-либо задача может «застрять» в памяти, так как выполняет ввод-вывод в свою область памяти (по этой причине откачать ее невозможно). Решение данной проблемы: ввод-вывод должен выполняться только в специальные буфера, выделяемой для этой цели операционной системой.

Страничная организация

Страничная организация (paging) –стратегия управления памятью, при которой:

· логическая память делится на страницы– смежные области одинаковой длины, обычно – степень 2 (например, 512 слов);

· физическая память, соответственно, делится на фреймытакого же размера;

· распределение логической памяти происходит с точностью до страницы;

· физическая память процесса может не быть непрерывной;

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

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

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

При страничной организации логический адрес обрабатывается системой особым образом – как структура (p, d):его старшие разряды обозначают номер страницы, младшие – смещение внутри страницы. Номер страницы (p)трактуется как индекс в таблице страниц, соответствующий элемент которой содержит базовый адрес начала страницы в физической памяти. Смещение внутри страницы (d)добавляется к ее базовому адресу. В результате формируется физический адрес, передаваемый в устройство управления памятью.

Архитектура трансляции адресов при страничной организации изображена на рис. 3.

Рис. 3.Архитектура трансляции адресов при страничной организации.

На рис.4 приведен пример страничной организации, который демонстрирует, что, в отличие от непрерывной логической памяти процесса, соответствующие фреймы страниц в основной памяти могут быть расположены не смежно: логической странице 0 соответствует фрейм 1, странице 1 – фрейм 4, странице 2 – фрейм 3, странице 3 – фрейм 7.

Рис. 4.Пример страничной организации.

На рис.5 приведен другой возможный пример страничной организации: логическая и физическая память разбита на блоки по 4 страницы подряд; в таблице страниц хранится не номер страницы, а номер блока страниц. Например, в элементе 0 таблицы страниц хранится номер блока 5, по которому адрес начала блока вычисляется домножением содержимого элемента таблицы страниц на размер блока, равный 4 (результат – 20).

Рис. 5.Пример страничной организации блоками по 4 страницы.

Использования списка свободных фреймов иллюстрируется на рис. 6.

Рис.6.Список свободных фреймов.

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

Способы управления памятью.

Простое непрерывное распределение и распределение с перекрытием (оверлейные структуры)

Простое непрерывное распределение – это самая простая схема, согласно которой вся память может быть условно разделена на три части:

область, занимаемая операционной системой;

область, в которой размещается исполняемая задача;

незанятая ничем (свободная) область памяти.

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

Чтобы для задач отвести как можно больший объем памяти, ОС строится таким образом, что постоянно в оперативной памяти располагается только самая нужная ее часть. Эту часть принято называть ядром. Остальные модули ОС могут быть обычными диск-резидентными, т.е. загружаться в оперативную память только по необходимости, и после своего выполнения вновь освобождать память.

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

Метод распределения памяти с перекрытием – оверлейные структуры (overlay – перекрытие, расположение поверх чего-то) – предполагает, что вся программа может быть разбита на части – сегменты. Каждая оверлейная программа имеет одну главную часть (main) и несколько сегментов (segment), причем в памяти компьютера одновременно могут находиться одна главная ее часть и один или несколько не перекрывающихся сегментов. Пока в оперативной памяти располагаются выполняющиеся сегменты, остальные находятся во внешней памяти. После того, как текущий (выполняющийся) сегмент завершит свое выполнение, возможны два варианта. Либо он сам (если данный сегмент не нужно сохранять в памяти в его текущем состоянии) обращается к ОС с указанием, какой сегмент дожжен быть загружен в память следующим. Либо он возвращает управление главному сегменту задачи (в модель main), и уже тот обращается к ОС с указанием, какой сегмент сохранить, а какой сегмент загрузить в оперативную память, и вновь отдает управление одному из сегментов, располагающихся в памяти. Простейшие схемы сегментирования предполагают, что в памяти в каждый конкретный момент времени может располагаться только один сегмент (вместе с модулем main). Более сложные схемы, используемые в больших вычислительных системах, позволяют располагать по несколько сегментов.

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

Распределение со статическими и динамическими разделами.

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

Исходные данные.

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

Полный объем доступной памяти ЭВМ предполагается равным 56000 байт; ОС занимает первые 10000 байт. Память, не занятая ОС, состоит из 4-х разделов. Раздел 1 начинается с адреса 10000 сразу за ОС и имеет длину 18000 байт. Раздел 2-3 – по 10000 байт каждый. Раздел 4 – 8000 байт.

В простой схеме распределения с разделением фиксированного размера каждое входящее задание загружается в наименьший подходящий по объему раздел. Если размер раздела превосходит размер задания, то оставшееся внутри раздела память не используется. Система, имея вначале пустыми все 4-е раздела, первым делом загрузит задание 1 в раздел 2. Затем задание 2 будет загружено в единственно достаточно большой для него раздел 1. Задание 3 и 4 загружаются в разделы 3 и 4. После этого все разделы оказываются занятыми, поэтому больше заданий загрузить нельзя.

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

По окончании задания 2 в раздел 1 загрузится задание 5.

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

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

Читайте также  Как проверить проводку мультиметром на авто?

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

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

выделять раздел ровно такого объема, который нужен под текущую задачу;

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

Простое непрерывное распределение и распределение с перекрытием (оверлейные структуры)

Организация и распределение памяти

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

1. Помещение в память только одной программы пользователя или нескольких программ одновременно.

2. Выделение программам одинакового или различного числа ячеек памяти.

3. Статическое разбиение памяти или динамическое планирование.

4. Размещение программы в непрерывном блоке или разбивание её на отдельные блоки с размещением их в «дырах».

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

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

2. Выбор места памяти для размещения очередной программы – размещение программы как можно более плотное с экономией памяти или как можно быстрое с экономией времени.

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

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

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

Самой простой схемой является простое непрерывное распределение (т.н. связное распределение), при котором вся память условно разделяется на три части:

· область, занимаемая операционной системой;

· область, в которой размещается исполняемая задача;

· незанятая (свободная) область памяти.

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

Вариантов простого непрерывного распределения памяти существовало очень много (примером может являться ОС MS-DOS).

В случае, если необходимо создать программу, логическое (и виртуальное) адресное пространство которой должно быть больше, чем весь возможный объём ОП, используется распределение с перекрытием (т.н. оверлейные структуры). При этом методе распределения предполагается, что вся программа может быть разбита на части – сегменты. Каждая оверлейная программа имеет одну главную часть и несколько сегментов, причём в памяти компьютера одновременно могут находиться только главная часть и один или несколько не перекрывающихся сегментов. После того, как текущий сегмент закончит своё выполнение, возможны два варианта:

· Этот сегмент сам обращается к ОС с указанием, какой сегмент нужно загрузить следующим.

· Он возвращает управление главному сегменту задачи (модуль main), и уже тот обращается к ОС с указанием, какой сегмент нужно сохранить, а какой загрузить в ОП, и снова отдаёт управление одному из сегментов, находящихся в памяти.

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

Распределение статическими и динамическими разделами при мультипрограммном режиме

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

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

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

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

Основным недостатком такого способа распределения является возникновение фрагментации памяти. В каждом из разделов может оставаться неиспользованная память, которая в сумме даёт весьма ощутимые потери. Но использовать эти свободные части при таком способе распределения не представляется возможным.

Для сокращения потерь были предложены варианты:

· выделять раздел ровно такого объёма, который нужен под текущую задачу;

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

Разделы с подвижными границами. Чтобы избавиться от фрагментации, можно попробовать размещать в ОП задачи плотно, одну за другой, выделяя каждой столько памяти, сколько для неё требуется (Первая ОС, реализовавшая этот способ – OS MVT – «мультипрограммирование с переменным числом задач», ОС для больших ЭВМ класса IBM 360). Специальный планировщик (диспетчер памяти) ведет список адресов свободной ОП. При появлении новой задачи он просматривает этот список и выделяет для задачи раздел, объём которого равен необходимому или чуть больше, если память выделяется не ячейками, а некими дискретными единицами. При этом список свободной памяти модифицируется. При освобождении раздела диспетчер пытается объединить смежные свободные участки памяти.

Список свободных участков может быть упорядочен либо по адресам, либо по объёму. Выделение памяти под новый раздел может осуществляться одним из трёх способов:

· первый подходящий участок;

· самый подходящий участок;

· самый неподходящий участок;

В первом случае список упорядочивается по адресам. Правило «первый подходящий» приводит к тому, что память для небольших задач будет преимущественно выделяться в области младших адресов и, следовательно, повысится вероятность того, что в области старших адресов будут образовываться фрагменты достаточно большого объёма. При таком способе диспетчеру приходится просматривать в среднем половину списка.

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

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

Очевидно, что в силу того, что задачи имеют разные объёмы и появляются и завершаются в произвольные моменты времени, при любой дисциплине обслуживания всегда будет наблюдаться сильная фрагментация памяти. Возможно, что новый раздел нельзя будет образовать, несмотря на то, что суммарный объём свободной памяти окажется превосходящим тот, который необходим для задачи. В такой ситуации возможно организовать т.н. «уплотнение памяти», при котором приостанавливаются все вычисления и диспетчер памяти перемещает свободные разделы в тот или иной конец памяти с соответствующей корректировкой списков. Тогда при определении физических адресов задачи будут участвовать уже новые значения базовых регистров. Недостатками данного решения являются потери времени на уплотнение и приостановка всех процессов. В системах реального времени такой способ непригоден.

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

Читайте также  Датчик скрытой проводки своими руками

Распределение памяти фиксированными разделами.

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

Рис. 8.6. Распределение памяти фиксированными разделами.

В этом случае подсистема управления памятью выполняет задачи:

¨ сравнения размера поступившей на выполнение программы с размерами свободных разделов памяти;

¨ выбора подходящего раздела;

¨ загрузка программы и настройка адресов.

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

Другой способ – распределение памяти разделами переменной величины. При таком способе распределения в начале работы ЭВМ вся ОП свободна. Каждой поступающей на выполнение задаче выделяется необходимый ей объем ОЗУ. Если достаточный объем памяти отсутствует, задача не принимается на выполнение и стоит в очереди. После завершения задачи память освобождается, и на это место может быть загружена другая задача.

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

Рис. 8.7. Распределения памяти динамическими разделами

В начальный момент времени t0 в ОП загружена только ОС. К моменту времени t1 ОП разделена между ОС и 5 программами (задачами), имеется также свободная область. К моменту времени t2 задача П2 уже завершена и покидает ОП, а на ее место может быть подгружена задача На освободившееся место загружается задача П6, поступившая в момент времени t3. Выбором раздела для вновь поступившей задачи занимается ОС. Осуществляется выбор раздела по правилам: «первый попавшийся раздел достаточного размера», «раздел, имеющий наименьший достаточный размер», «раздел, имеющий наибольший достаточный размер».

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

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

¨ анализ запроса (при поступлении новой задачи);

¨ просмотр таблицы свободных областей (с целью выбора раздела для размещения вновь поступившей задачи);

¨ загрузка задачи в выделенный ей раздел;

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

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

Статьи к прочтению:

  • Распределение памяти подвижными разделами
  • Распределение памяти при выполнении программ

Когда фиксировать прибыль в сделке (А. Пурнов)

Похожие статьи:

Простейший способ управления оперативной памятью состоит в том, что память разбивается на несколько областей фиксированной величины, называемых…

Разбиение всего объема оперативной памяти на несколько разделов может осуществляться единовременно (в процессе генерации ОС). Пример разбиения памяти на…

Операционные системы

  • Современные операционные системы, Э. Таненбаум, 2002, СПб, Питер, 1040 стр., (в djvu 10.1Мбайт) подробнее>>
  • Сетевые операционные системы Н. А. Олифер, В. Г. Олифер (в zip архиве 1.1Мбайт)
  • Сетевые операционные системы Н. А. Олифер, В. Г. Олифер, 2001, СПб, Питер, 544 стр., (в djvu 6.3Мбайт) подробнее>>

6.1 Основные понятия

Менеджер памяти — часть операционной системы, отвечающая за управление памятью.

Основные методы распределения памяти:

Без использования внешней памяти (например: HDD)

С использованием внешней памяти

6.2 Методы без использования внешней памяти

6.2.1 Однозадачная система без подкачки на диск

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

Схемы разделения памяти:

Схемы разделения памяти

Третий вариант используется в MS-DOS. Та часть, которая находится в ПЗУ, часто называется BIOS.

6.2.2 Распределение памяти с фиксированными разделами.

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

Системы могут иметь:

общую очередь ко всем разделам

к каждому разделу отдельную очередь

Распределение памяти с фиксированными разделами

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

Алгоритмы планирования в случае одной очереди:

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

Также может быть смешанная система.

6.2.3 Распределение памяти динамическими разделами

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

Распределение памяти динамическими разделами.

Перемещаемые разделы

Это один из методов борьбы с фрагментацией. Но на него уходит много времени.

Рост разделов

Иногда процессу может понадобиться больше памяти, чем предполагалось изначально.

Настройка адресов и защита памяти

В предыдущих примерах мы можем увидеть две основные проблемы.

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

Защита адресного пространства каждой программы

Решение обоих проблем заключается в оснащении машины специальными аппаратными регистрами.

Базовый (указывает начало адресного пространства программы)

Предельный (указывает конец адресного пространства программы)

6.3 Методы с использованием внешней памяти (свопинг и виртуальная память)

Так как памяти, как правило, не хватает. Для выполнения процессов часто приходится использовать диск.

Основные способы использования диска:

Свопинг (подкачка) — процесс целиком загружается в память для работы

Виртуальная память — процесс может быть частично загружен в память для работы

6.3.1 Свопинг (подкачка)

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

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

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

Свопер — планировщик, управляющий перемещением данных между памятью и диском.

Этот метод был основным для UNIX до версии 3BSD.

Управление памятью с помощью битовых массивов

Вся память разбивается на блоки (например, по 32бита), массив содержит 1 или 0 (занят или незанят).

Чтобы процессу в 32Кбита занять память, нужно набрать последовательность из 1000 свободных блоков.

Такой алгоритм займет много времени.

битовые массивы и списки

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

Этот способ отслеживает списки занятых (между процессами) и свободных (процессы) фрагментов памяти.

Запись в списке указывает на:

занят (P) или незанят (H) фрагмент

адрес начала фрагмента

Четыре комбинации соседей для завершения процесса X

Алгоритмы выделения блока памяти:

первый подходящий участок.

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

самый подходящий участок (медленнее, но лучше использует память).

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

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

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

Программа при этом общается с виртуальной памятью, а не с физической.

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

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

Страницы — это части, на которые разбивается пространство виртуальных адресов.

Страничные блоки — единицы физической памяти.

Страницы всегда имеют фиксированный размер. Передача данных между ОЗУ и диском всегда происходит в страницах.

Х — обозначает не отображаемую страницу в физической памяти.

Страничное прерывание — происходит, если процесс обратился к странице, которая не загружена в ОЗУ (т.е. Х). Процессор передается другому процессу, и параллельно страница загружается в память.

Таблица страниц — используется для хранения соответствия адресов виртуальной страницы и страничного блока.

Таблица может быть размещена:

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

Типичная запись в таблице страниц

Присутствие/отсутствие — загружена или незагружена в память

Защита — виды доступа, например, чтение/запись.

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

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

Информация о адресе страницы когда она хранится на диске, в таблице не размещается.

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

Страничная организация памяти используется, и в UNIX, и в Windows.

Хранение страничной памяти на диске

Статическая область свопинга

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

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

Этот механизм наиболее простой.

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

Динамическая область свопинга

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

Этот механизм сложнее, так как процессы не привязаны к какому-то пространству на диске, и нужно хранить информацию (карту диска) о местоположении на диске каждой страницы.