Операционные системы (архив ИПМ специалисты, бакалавры 2001г — 2021г, Богомолов)
- Современные операционные системы, Э. Таненбаум, 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.
Хранение страничной памяти на диске
Статическая область свопинга
После запуска процесса он занимает определенную память, на диске сразу ему выделяется такое же пространство. Поэтому файл подкачки должен быть не меньше памяти. А в случае нехватки памяти даже больше. Как только процесс завершится, он освободит память и место на диске.
На диске всегда есть дубликат страницы, которая находится в памяти.
Этот механизм наиболее простой.
Статический и динамический методы организации свопинга.
Динамическая область свопинга
Предполагается не выделять страницам место на диске, а выделять только при выгрузке страницы, и как только страница вернется в память освобождать место на диске.
Этот механизм сложнее, так как процессы не привязаны к какому-то пространству на диске, и нужно хранить информацию (карту диска) о местоположении на диске каждой страницы.
Источник
Страничная организация памяти
Презентацию к данной лекции Вы можете скачать здесь.
Введение
Страничная организация памяти ( paging ) – наиболее распространенная стратегия управления памятью , используемая практически во всех операционных системах. В данной лекции рассматриваются общие проблемы управления памятью , принципы страничной организации и ее различные формы.
Откачка и подкачка
Пользовательский процесс может находиться в различных состояниях во время обработки системой. В частности, процесс может быть некоторое время неактивным, если, например, он исполняется в режиме разделения времени, и пользователь за терминалом обдумывает следующую команду или редактирует исходный код своей программы. В подобных случаях процесс может быть откачан операционной системой на диск , в связи с тем, что занимаемая им память оказывается необходимой в данный момент для другого, активного, процесса .
Откачка и подкачка (swapping) – это действия операционной системы по откачке (записи) образа неактивного процесса на диск или подкачке (считыванию) активного процесса в основную память . Необходимость выполнения подобных действий вызвана нехваткой основной памяти.
Файл откачки (backing store) — область дисковой памяти, используемая операционной системой для хранения образов откачанных процессов. Файл откачки организуется максимально эффективно: обеспечивается прямой доступ ко всем образам процессов в памяти (например, через таблицу по номеру процесса).
Популярная разновидность стратегии откачки и подкачки – roll out / roll in: откачка и подкачка на базе приоритетов; более приоритетные процессы исполняются, менее приоритетные – откачиваются на диск .
Наибольшие временные затраты на откачку – это затраты на передачу данных: полный образ процесса может занимать большую область памяти. Общее время откачки пропорционально размеру откачиваемых данных.
В распространенных ОС – UNIX , Linux, Windows и др. – реализованы различные стратегии откачки и подкачки.
Схема откачки и подкачки изображена на рис. 16.1.
Смежное распределение памяти
Наиболее простая и распространенная стратегия распределения памяти – смежное распределение памяти – распределение памяти для пользовательских процессов в одной смежной области памяти. Основная память разбивается на две смежных части ( partitions ), которые «растут» навстречу друг другу: резидентная часть ОС и вектор прерываний – по меньшим адресам. Для пользовательских процессов память распределяется в одном и том же смежном участке памяти. Для каждого процесса регистр перемещения указывает на начало выделенной ему области памяти, регистр границы содержит длину диапазона логических адресов . Каждый логический адрес должен быть меньше содержимого регистра границы. Физический адрес вычисляется аппаратно как сумма логического адреса и значения регистра перемещения. Схема адресации с аппаратной поддержкой регистров перемещения и границы изображена на рис. 16.2.
Общая задача распределения памяти и стратегии ее решения
В общем случае, в операционных системах может использоваться смежное распределение памяти в нескольких смежных областях. Свободная область – это смежный блок свободной памяти. Свободные области могут быть произвольно разбросаны по памяти. При загрузке процесса ему предоставляется память из любой свободной смежной области, которая достаточно велика для его размещения. При этом операционная система хранит список свободных областей памяти и список занятых областей памяти. Все эти области могут быть произвольно расположены в памяти и иметь различную длину.
Возникает общая задача распределения памяти: Имеется список свободных областей памяти и список занятых областей разного размера. Разработать и реализовать оптимальный ( по некоторому критерию) алгоритм выделения свободного смежного участка памяти длины n (слов или байтов).
Для решения данной задачи применяются следующие стратегии: метод первого подходящего (first-fit), метод наиболее подходящего (best-fit) и метод наименее подходящего (worst-fit).Рассмотрим каждую из них подробнее.
Метод первого подходящего:Выбирается первый по списку свободный участок подходящего размера (не меньшего, чем n ). На первый взгляд, данная стратегия оптимальна, но далее мы увидим, что это не всегда так.
Метод наиболее подходящего:Выбирается из списка наиболее подходящий свободный участок (минимального размера, не меньшего, чем n ). В отличие от предыдущего метода, требует просмотра всего списка, если список не упорядочен по размеру областей. Применение метода приводит к образованию оставшейся части самого маленького размера.
Метод наименее подходящего: Выбирается из списка подходящая область наибольшего размера. Почему наибольшего? Чтобы избежать фрагментации (проблема фрагментации подробно рассмотрена далее в данной лекции).
Применение первой и второй стратегий лучше со следующих точек зрения: скорость выполнения и минимальность объема использованной памяти. Однако их применение может создать фрагментацию.
Фрагментация
Фрагментация – это дробление памяти на мелкие не смежные свободные области маленького размера. Фрагментация возникает после выполнения системой большого числа запросов на память , таких, что размеры подходящих свободных участков памяти оказываются немного больше, чем требуемые. Например, если имеется 100 смежных свободных областей памяти по 1000 слов, то после выполнения 100 запросов на память по 999 слов каждый в списке свободной памяти останутся 1000 областей по одному слову.
Фрагментация бывает внутренняя и внешняя. При внешней фрагментации имеется достаточно большая область свободной памяти, но она не является непрерывной. Внутренняя фрагментация может возникнуть вследствие применения системой специфической стратегии выделения памяти, при которой фактически в ответ на запрос память выделяется несколько большего размера, чем требуется, — например, с точностью до страницы (листа ), размер которого – степень двойки. Страничная организация памяти подробно рассматривается далее в данной лекции.
Внешняя фрагментация может быть уменьшена или ликвидирована путем применения компактировки (compaction) – сдвига или перемешивания памяти с целью объединения всех не смежных свободных областей в один непрерывный блок. Компактировка может выполняться либо простым сдвигом всех свободных областей памяти, либо путем перестановки занятых областей, с выбором на каждом шаге подходящей свободной области методом наиболее подходящего. Компактировка возможна, только если связывание адресов и перемещение (см. лекцию 15) происходит динамически. Компактировка выполняется во время исполнения программы.
При компактировке памяти и анализе свободных областей может быть выявлена проблема зависшей задачи: какая-либо задача может «застрять» в памяти, так как выполняет ввод-вывод в свою область памяти ( по этой причине откачать ее невозможно). Решение данной проблемы: ввод-вывод должен выполняться только в специальные буфера, выделяемой для этой цели операционной системой.
Источник
