Основы операционных систем Лекция 8 - 20.03.081 Лекция 8. Простейшие схемы управления памятью Введение Связывание адресов Простейшие схемы управления памятью. - презентация

1 Основы операционных систем Лекция Лекция 8. Простейшие схемы управления памятью Введение Связывание адресов Простейшие схемы управления памятью

2 Основы операционных систем Лекция Введение (1) В следующих нескольких лекциях обсуждается идеология построения системы управления памятью в современных ОС Система виртуальной памяти обеспечивает поддержку и защиту больших виртуальных сегментированных адресных пространств процессов Тщательное проектирование аппаратно-зависимых и аппаратно-независимых компонентов менеджера памяти дает возможность организовать их производительную работу

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

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

5 Основы операционных систем Лекция Введение (4) Адрес состоит из двух компонентов: номер сегмента и смещение внутри сегмента Оказалось удобным размещать в разных сегментах данные разных типов (код программы, данные, стек) Можно контролировать характер работы с конкретным сегментом, приписав ему атрибуты, например, права доступа или допустимые типы операций В большинстве современных ОС поддерживается сегментная организация памяти В некоторых архитектурах сегментация поддерживается оборудованием

6 Основы операционных систем Лекция Введение (5) физическуюлогическую Вторая идея состоит в разделении памяти на физическую и логическую Адреса, к которым обращается процесс, отделяются от адресов, реально существующих в оперативной памяти логическим виртуальным физическим Адрес, сгенерированный программой, обычно называют логическим (в системах с виртуальной памятью он обычно называется виртуальным) адресом, тогда как адрес, который видит устройство памяти, обычно называется физическим адресом Задача ОС (и/или аппаратуры): в какой-то момент времени осуществить связывание (или отображение) логического адресного пространства с физическим

7 Основы операционных систем Лекция Введение (6) локальности И, наконец, идея локальности Свойство локальности присуще природе Пространственная локальность - соседние объекты характеризуются похожими свойствами Временная локальность - если в 15:00 была хорошая погода, то, вероятно, что и в 14:30 и в 15:30 также наблюдалась хорошая погода Свойство локальности (скорее, эмпирическое) присуще и работе ОС

8 Основы операционных систем Лекция Введение (7) Свойство локальности объяснимо, если учесть, что обычно в течение какого-то отрезка времени ограниченный фрагмент кода работает с ограниченным набором данных иерархию памяти Позволяет организовать иерархию памяти: быстрая память используется для хранения минимума необходимых данных; оставшиеся данные размещаются на устройствах с более медленным доступом и подкачиваются в быструю память по мере необходимости вторичная память, ВП Типичный пример иерархии: регистры, кэш, ОП, внешняя память (вторичная память, ВП)

9 Основы операционных систем Лекция Введение (8) ОП - это массив слов или байт; каждое слово имеет свой адрес Использование ВП в качестве расширения ОП дает дополнительные преимущества Во-первых, основная память слишком мала, чтобы содержать все необходимые программы и данные постоянно изменчивоеvolatile Во-вторых, основная память есть изменчивое (volatile) устройство, которое теряет свое содержимое при отключении питания ВП может хранить большие объемы данных постоянно

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

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

12 Основы операционных систем Лекция Введение (11) На этой лекции будут рассмотрены простейшие схемы управления памятью Затем будет описана доминирующая на сегодня схема виртуальной памяти, ее аппаратная и программная поддержка

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

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

15 Основы операционных систем Лекция Связывание адресов (3) Обычно программа проходит нескольких шагов: текст на языке программирования, объектный модуль, загрузочный модуль, бинарный образ в памяти В каждом конкретном случае адреса могут быть представлены различными способами Адреса в исходных текстах обычно символические Компилятор связывает символические адреса с перемещаемыми адресами Компоновщик связывают перемещаемые адреса с виртуальными адресами Каждое связывание - отображение одного адресного пространства в другое

16 Основы операционных систем Лекция Связывание адресов (4) Привязка инструкций и данных к памяти в принципе может быть сделана на следующих шагах: Этап компиляцииCompile time Этап компиляции (Compile time) Если на стадии компиляции известно точное место размещения процесса в памяти, то генерируются абсолютные адреса Если стартовый адрес программы меняется, необходимо перекомпилировать код В качестве примера можно привести программы MS- DOS, которые связываются с физическими адресами на стадии компиляции

17 Основы операционных систем Лекция Связывание адресов (5) Этап загрузки (Load time) Если на стадии компиляции не известно, где процесс будет размещен в памяти, компилятор генерирует перемещаемый код В этом случае окончательное связывание откладывается до момента загрузки Если стартовый адрес меняется, нужно всего лишь перезагрузить код с учетом измененной величины

18 Основы операционных систем Лекция Связывание адресов (6) Этап выполнения (Execution time) Если процесс может быть перемещен во время выполнения из одного сегмента памяти в другой, связывание откладывается до времени выполнения Здесь желательно специализированное оборудование, например регистры перемещения Их значение прибавляется к каждому адресу, сгенерированному процессом Например, в MS-DOS использовалось четыре таких (сегментных) регистра

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

20 Основы операционных систем Лекция Простейшие схемы управления памятью (2) «Простой свопинг» Каждый процесс располагается в ОП целиком Иногда образ некоторого процесса целиком сбрасывается из ОП в ВП и заменяется в ОП образом некоторого другого процесса Схемы такого рода имеют не только историческую ценность встроенных (embedded) В настоящее время они применяются в учебных и научно-исследовательских модельных ОС, а также в ОС для встроенных (embedded) компьютеров

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

22 Основы операционных систем Лекция Простейшие схемы управления памятью (4) Схема с фиксированными разделами Каждый раздел может иметь свою очередь или может существовать глобальная очередь для всех разделов Эта схема была реализована в IBM OS/360 (MFT) и в DEC RSX-11 Подсистема управления памятью оценивает размер программы Выбирает подходящий раздел, производит загрузку программы и настройку адресов

23 Основы операционных систем Лекция Простейшие схемы управления памятью (5) Схема с фиксированными разделами В какой раздел помещать программу? Распространены три стратегии: Стратегия первого подходящего (First fit) Используется первый подходящий по размеру раздел Стратегия наиболее подходящего (Best fit) Используется раздел, в котором остается меньше всего свободного места Стратегия наименее подходящего (Worst fit) Используется раздел, в котором остается больше всего свободного места

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

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

26 Основы операционных систем Лекция Простейшие схемы управления памятью (8) Схема с фиксированными разделами: Один процесс в памяти Частный случай схемы с фиксированными разделами используется в работе менеджера памяти однозадачной ОС В памяти размещается один пользовательский процесс Остается определить, где располагается пользовательская программа по отношению к ОС - сверху, снизу или посередине ROM (read- only-memory) При этом часть ОС может располагаться в ROM (read- only-memory) (например, BIOS, драйверы устройств)

27 Основы операционных систем Лекция Простейшие схемы управления памятью (9) Схема с фиксированными разделами: Один процесс в памяти Главный фактор, влияющий на это решение - расположение вектора прерываний, который обычно локализован в нижней части памяти, поэтому ОС также размещают в нижней Примером такой организации может служить ОС MS- DOS Чтобы пользовательская программа не портила код ОС, требуется защита ОС, которая может быть организована при помощи одного граничного регистра, содержащего адрес границы ОС

28 Основы операционных систем Лекция Простейшие схемы управления памятью (10) Схема с фиксированными разделами: Оверлейная структура оверлеем (overlay) Поскольку размер логического адресного пространства процесса может быть больше размера выделенного ему раздела (или больше чем размер самого большого раздела), иногда используется техника, называемая оверлеем (overlay) или организация структуры с перекрытием Основная идея - держать в памяти только те команды и данные программы, которые нужны в данный момент Потребность появляется, если логическое адресное пространство системы мало, например 1 мегабайт (MS-DOS) или даже всего 64 килобайта (PDP-11), а программа относительно велика

29 Основы операционных систем Лекция Простейшие схемы управления памятью (11) Схема с фиксированными разделами: Оверлейная структура Коды ветвей оверлейной структуры программы находятся на диске как абсолютные образы памяти и считываются драйвером оверлеев при необходимости Для конструирования оверлеев необходимы специальные алгоритмы перемещения и связывания Для описания оверлейной структуры обычно используется специальный несложный язык (overlay description language) Совокупность файлов исполняемой программы дополняется файлом, описывающим дерево вызовов внутри программы Для примера текст этого файла может выглядеть так: A-(B,C); C-(D,E) Синтаксис подобного файла может распознаваться загрузчиком Привязка к памяти происходит в момент очередной загрузки одной из ветвей программы

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

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

32 Основы операционных систем Лекция Простейшие схемы управления памятью (14) Свопинг Имея дело с пакетными системами, можно обходиться фиксированными разделами и не использовать ничего более сложного В системах с разделением времени возможна ситуация, когда память не в состоянии содержать все пользовательские процессы свопингуswapping Приходится прибегать к свопингу (swapping) - перемещению процессов из главной памяти на диск и обратно целиком пейджингомpaging Частичная выгрузка процессов на диск связана с пейджингом (paging) будет рассмотрена в следующих лекциях

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

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

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

36 Основы операционных систем Лекция Простейшие схемы управления памятью (18) Мультипрограммирование с переменными разделами По истечении некоторого времени память представляет собой набор занятых и свободных участков Смежные свободные участки могут быть объединены в один Типовой цикл работы менеджера: анализ запроса на выделение свободного участка (раздела); выборка его среди имеющихся в соответствие с одной из стратегий загрузка процесса в выбранный раздел внесение изменений в таблицы свободных и занятых областей Аналогично после завершения процесса Связывание адресов может быть на этапах загрузки и выполнения

37 Основы операционных систем Лекция Простейшие схемы управления памятью (19) Мультипрограммирование с переменными разделами Этот метод более гибок по сравнению с методом фиксированных разделов Но ему присуща внешняя фрагментация из-за наличия большого числа участков свободной памяти Проблемы фрагментации могут быть различными В худшем случае можно иметь участок свободной (потерянной) памяти между каждыми двумя процессами Если все эти куски объединить в один блок, разместилось бы больше процессов first-fitbest-fit Выбор между first-fit и best-fit слабо влияет на уровень фрагментации

38 Основы операционных систем Лекция Простейшие схемы управления памятью (20) Мультипрограммирование с переменными разделами В зависимости от суммарного размера памяти и среднего размера процесса эта проблема может быть большей или меньшей nn/2 1/3 Статистический анализ показывает, что при наличии n блоков пропадает n/2 блоков, то есть 1/3 памяти! 50% Это известное правило 50% Два соседних свободных участка в отличие от двух соседних процессов могут быть объединены в один

39 Основы операционных систем Лекция Простейшие схемы управления памятью (21) Мультипрограммирование с переменными разделами Одно из решений проблемы внешней фрагментации - разрешить адресному пространству процесса не быть непрерывным, что разрешает выделять процессу память в любых доступных местах paging Один из способов реализации такого решения - это paging, используемый во многих современных ОС (будет рассмотрен в следующих лекциях) сжатие Другим способом борьбы с внешней фрагментацией является сжатие, то есть перемещение всех занятых (свободных) участков в сторону возрастания (убывания) адресов так, чтобы вся свободная память образовала непрерывную область

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

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