1 Управление памятью Системное и прикладное программное обеспечение Малышенко Владислав Викторович

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

3 Основное управление памятью Системы управления памятью можно разделить на два класса: Перемещающие процессы между оперативной памятью и диском во время их выполнения (то есть осуществляющие подкачку процессов целиком (swapping) или использующие страничную подкачку (paging)); Не перемещающие процессы между оперативной памятью и диском во время их выполнения.

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

5 Основное управление памятью Программное обеспечение растет еще быстрее, чем память; поэтому вполне возможно, что потребность в рациональном и эффективном управлении памятью будет существовать всегда. В 80-е годы многие университеты использовали системы разделения времени для работы десятков (более-менее довольных) пользователей на машинах VAX с объемом памяти 4 Мбайт. Сейчас компания Microsoft рекомендует для индивидуальной работы в системе Windows 2000 устанавливать на компьютер, по меньшей мере, 64 Мбайт оперативной памяти. Дальнейшее развитие в сторону мультимедийных систем накладывает еще большие требования на память. Таким образом, весьма вероятно, что качество управления этой частью компьютера будет актуальным по крайней мере в течение следующего десятилетия.

6 Однозадачная система без подкачки на диск Самая простая из возможных схем управления памятью заключается в том, что в каждый конкретный момент времени работает только одна программа, при этом память разделяется между программами и операционной системой. Три варианта такой схемы: Операционная система может находиться в нижней части памяти, то есть в ОЗУ (оперативное запоминающее устройство, RAM (Random Access Memory - память с произвольным доступом)) ; Операционная система может располагаться в самой верхней части памяти - в ПЗУ (постоянное запоминающее устройство, ROM (Read-Only Memory - память только для чтения)); Третий способ: драйверы устройств могут находиться наверху в ПЗУ, а остальная часть системы - в ОЗУ, расположенной ниже.

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

8 Первая модель раньше применялась на мэйнфреймах и мини- компьютерах, но в настоящее время практически не употребляется. Вторая схема сейчас используется на некоторых карманных компьютерах и встроенных системах. Третья модель устанавливалась на ранних персональных компьютерах (например, работающих с MS-DOS), при этом часть системы в ПЗУ носила название BIOS (Basic Input Output System - базовая система ввода-вывода). Когда система организована таким образом, в каждый конкретный момент времени может работать только один процесс. Как только пользователь набирает команду, операционная система копирует запрашиваемую программу с диска в память и выполняет ее, а после окончания процесса выводит на экран символ приглашения и ждет новой команды. Получив команду, она загружает новую программу в память, записывая ее поверх предыдущей.

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

10 Многозадачность с фиксированными разделами (2)

11 Моделирование многозадачности При использовании многозадачности повышается эффективность загрузки центрального процессора. Грубо говоря, если средний процесс выполняет вычисления только 20 % от того времени, которое он находится в памяти, то при присутствии в памяти одновременно пяти процессов центральный процессор должен быть занят все время. Более совершенная модель рассматривает эксплуатацию центрального процессора с точки зрения теории вероятности. Предположим, что процесс проводит часть р своего времени в ожидании завершения операции ввода-вывода. Если в памяти находится одновременно n процессов, вероятность того, что все n процессов ждут ввод-вывод, равна р n. Тогда степень загрузки центрального процессора будет выражаться формулой: Степень загрузки центрального процессора = 1 - р n.

12 Моделирование многозадачности

13 Моделирование многозадачности (пример) Предположим, что компьютер имеет 32 Мбайт памяти, 16 Мбайт отдано операционной системе, а каждая программа пользователя занимает по 4 Мбайт. При таких заданных размерах одновременно можно загрузить в память четыре пользовательские программы. При 80 % времени на ожидание ввода-вывода в среднем мы получим загруженность процессора равной 1-0,84, или около 60 %. Добавление еще 16 Мбайт памяти позволит системе повысить степень многозадачности от четырех до восьми и таким образом повысить степень загрузки процессора до 83 %. Другими словами, дополнительные 16 Мбайт увеличат производительность на 38 %. Еще 16 Мбайт могли бы повысить загрузку процессора с 83 до 93 %, таким образом, увеличив производительность всего лишь на 12 %. С помощью этой модели владелец компьютера может решить, что первые 16 Мбайт оперативной это хорошее вложение капитала, а вторые - нет.

14 Анализ производительности многозадачных систем

15 Анализ производительности многозадачных систем (2) Описанную выше модель также можно применить для анализа систем пакетной обработки. Например, рассмотрим компьютерный центр, в котором среднее время ожидания ввода- вывода задачами равно 80 %. Однажды утром подаются на выполнение 4 задания. Первая задача, поступившая в 10 утра, требует 4 мин работы процессора. Тогда при 80 % времени ожидания ввода-вывода за каждую минуту своего нахождения в памяти задача использует только 12с времени процессора, даже если нет никаких других параллельных заданий, также желающих занять процессор. Остальные 48с процесс проводит в ожидании ввода-вывода. Таким образом, задача должна находиться в памяти по крайней мере 20 мин для того, чтобы процессор сделал работу, требующую на самом деле всего 4 мин, и это все при отсутствии конкуренции на право использования процессора.

16 Анализ производительности многозадачных систем (3) Что же происходит дальше? С 10:00 до 10:10 утра в памяти находится целиком первая задача и выполняется половина работы (10 мин работы процессора). Когда в 10:10 поступает второе задание, загрузка процессора увеличивается с 0,20 до 0,36 вследствие более высокой степени многозадачности. Однако при циклическом планировании каждое задание получает для себя половину времени процессора, поэтому за каждую минуту нахождения в памяти выполняется часть задачи, требующая 0,18 мин работы процессора. Заметим, что добавление второй задачи обходится первой задаче всего в 10 % ее производительности. Время использования процессора за минуту реального времени уменьшилось с 0,20 мин до 0,18 мин. В 10:15 утра поступает третье задание. В этот момент для первой задачи процессор отработал 2,9 мин, для второй - 0,9 мин. Степень многозадачности теперь равна 3, каждое задание получает для себя 0,16 мин работы процессора за минуту реального времени. Тогда с 10:15 до 10:20 утра для каждого из трех заданий процессор работает по 0,8 мин. В 10:20 утра поступает четвертая задача.

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

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

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

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

21 Подкачка (2)

22 Подкачка (3). Работа системы свопинга. На начальной стадии в памяти находится только процесс А. Затем создаются или загружаются с диска процессы В и С. Процесс А выгружается на диск. Затем появляется процесс D, а процесс В завершается. Наконец, процесс А снова возвращается в память. Основная разница между фиксированными разделами и непостоянными разделами заключается в том, что во втором случае количество, размещение и размер разделов изменяются динамически по мере поступления и завершения процессов. Гибкость схемы, в которой нет ограничений, связанных с определенным количеством разделов, и каждый из разделов может быть очень большим или совсем маленьким, улучшает использование памяти, но, кроме того, усложняет операции размещения процессов и освобождения памяти, а также отслеживание происходящих изменений.

23 Подкачка (4) Когда в результате подкачки процессов с диска в памяти появляется множество неиспользованных фрагментов, их можно объединить в один большой участок, передвинув все процессы в сторону младших адресов настолько, насколько это возможно. Такая операция называется уплотнением или сжатием памяти. Обычно ее не выполняют, потому что на нее уходит много времени работы процессора. Например, на машине с 256 Мбайт оперативной памяти, которая может копировать 4 байта за 40 нс, уплотнение всей памяти займет около 2,7 с. Еще один момент, на который стоит обратить внимание: сколько памяти должно быть предоставлено процессу, когда он создается или скачивается с диска? Если процесс имеет фиксированный никогда не изменяющийся размер, размещение происходит просто: операционная система предоставляет точно необходимое количество памяти, ни больше, ни меньше, чем нужно. Однако если область данных процесса может расти, например, в результате динамического распределения памяти из кучи, как происходит во многих языках программирования, проблема предоставления памяти возникает каждый раз, когда процесс пытается увеличиться.

24 Подкачка (5)

25 Управление памятью Если память выделяется динамически, этим процессом должна управлять операционная система. Существует два способа учета использования памяти: битовые массивы, иногда называемые битовыми картами; списки свободных участков.

26 Управление памятью с помощью битовых массивов (2) При работе с битовым массивом память разделяется на единичные блоки размещения размером от нескольких слов до нескольких килобайт. Размер единичного блока представляет собой важный вопрос стадии разработки системы. Чем меньше единичный блок, тем больше потребуется битовый массив. Однако даже при маленьком единичном блоке, равном четырем байтам, для 32 битов памяти потребуется 1 бит в карте. Тогда память размером в 32n будет использовать n битов в карте, таким образом, битовая карта займет всего лишь 1/33 часть памяти. Битовый массив предоставляет простой способ отслеживания слов в памяти фиксированного объема, потому что размер битовой карты зависит только от размеров памяти и единичного блока. Основная проблема, возникающая при этой схеме, заключается в том, что при решении переместить k-блочный процесс в память модуль управления памяти должен найти в битовой карте серию из k следующих друг за другом нулевых битов.

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

28 Управление памятью с помощью связных списков (2) Другой способ отслеживания состояния памяти предоставляет поддержка связных списков занятых и свободных фрагментов памяти, где сегментом является или процесс, или участок между двумя процессами. Память, представлена в виде связного списка сегментов. Каждая запись в списке указывает, является ли область памяти свободной (Н, от hole - дыра) или занятой процессом (Р, process); адрес, с которого начинается эта область; ее длину; содержит указатель на следующую запись.

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

30 Управление памятью с помощью связных списков (2) a) корректировка списка требует замены Р на Н. b) в две записи соединяются в одну, а список становится на запись короче. c) объединяются три записи, а из списка удаляются два пункта. Такая структура упрощает поиск предыдущей записи и оценку возможности соединения.

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

32 Управление памятью с помощью связных списков (3) Если процессы и свободные участки хранятся в списке, отсортированном по адресам, существует несколько алгоритмов для предоставления памяти процессу, создаваемому заново (или для существующих процессов, скачиваемых с диска). Допустим, менеджер памяти знает, сколько памяти нужно предоставить. Алгоритмы поиска свободного участка памяти: «первого подходящего участка» «следующий подходящий участок» «самый подходящий участок»

33 Управление памятью с помощью связных списков (3) Простейший алгоритм представляет собой выбор первого подходящего участка. Менеджер памяти просматривает список областей до тех пор, пока не находит достаточно большой свободный участок. Затем этот участок делится на две части: одна отдается процессу, а другая остается неиспользуемой. Так происходит всегда, кроме статистически нереального случая точного соответствия свободного участка и процесса. Это быстрый алгоритм, потому что поиск уменьшен настолько, насколько возможно.

34 Управление памятью с помощью связных списков (3) Алгоритм «следующий подходящий участок» действует с минимальными отличиями от правила «первый подходящий». Он работает так же, как и первый алгоритм, но всякий раз, когда находит соответствующий свободный фрагмент, он запоминает его адрес. И когда алгоритм в следующий раз вызывается для поиска, он стартует с того самого места, где остановился в прошлый раз вместо того, чтобы каждый раз начинать поиск с начала списка, как это делает алгоритм «первый подходящий».

35 Управление памятью с помощью связных списков (3) Алгоритм называется «самый подходящий участок». Он выполняет поиск по всему списку и выбирает наименьший по размеру подходящий свободный фрагмент. Вместо того чтобы делить большую незанятую область, которая может понадобиться позже, этот алгоритм пытается найти участок, близко подходящий к действительно необходимым размерам. Пример работы алгоритмов «первый подходящий» и «самый подходящий». Если необходим блок размером 2, правило «первый подходящий» предоставит область по адресу 5, а схема «самый подходящий» разместит процесс в свободном фрагменте по адресу 18.

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

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

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

39 Страничная организация памяти (2)

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

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

42 Страничная организация памяти (5)

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

44 Страничная организация памяти (7) Что происходит, если программа пытается воспользоваться неотображаемой страницей, например, с помощью инструкции MOV REG которая обращается к байту 12 на виртуальной странице 8 (начинающейся с адреса 32768)? 1. Диспетчер памяти замечает, что страница не отображается, и инициирует прерывание центрального процессора, передающее управление операционной системе. Такое прерывание называется ошибкой из-за отсутствия страницы или страничным прерыванием (page fault). 2. Операционная система выбирает малоиспользуемый страничный блок и записывает его содержимое на диск. 3. Затем она считывает с диска страницу, на которую произошла ссылка, в только что освободившийся блок, изменяет карту отображения и запускает заново прерванную команду.

45 Таблица страниц

46 Таблица страниц (2) Виртуальный адрес делится на номер виртуальной страницы (старшие биты) и сдвиг (младшие биты). Например, при 16- разрядных адресах и размере страницы 4 Кбайт старшие 4 бита могут указывать одну из 16 виртуальных страниц, а нижние 12 бит могут определять байт смещения (от 0 до 4095) внутри выбранной страницы. Однако разбиение страницы на 3,5 или какое-нибудь другое число битов также возможно. Разные части подразумевают различные размеры страниц. Номер виртуальной страницы используется как индекс в таблице страниц для поиска записи этой страницы. По записи в таблице страниц находится номер физического блока страницы (если это имеет место). Данный номер присоединяется к старшим разрядам числа смещения, замещая номер виртуальной страницы и тем самым формируя физический адрес, который может быть послан в память.

47 Таблица страниц (3) Несмотря на столь простое описание, существует две важные проблемы, которые необходимо решить: 1. Таблица страниц может быть слишком большой; 2. Отображение должно быть быстрым.

48 Таблица страниц (4) Первый пункт следует из того факта, что современные компьютеры используют по крайней мере 32-разрядные виртуальные адреса. При размере страницы, скажем, 4 Кбайт, 32-разрядное адресное пространство будет состоять из одного миллиона страниц. При одном миллионе страниц в виртуальном адресном пространстве таблица страниц должна состоять из одного миллиона записей. Второй пункт - это вывод из того факта, что преобразование виртуальных адресов в физические должно быть выполнено для каждого обращения к ячейке памяти. Типичная команда процессора включает в себя слово-команду и часто также операнд памяти. В результате необходимо сделать 1,2 или иногда больше обращений к таблице страниц за команду.

49 Таблица страниц (5) Потребность в огромном, но при этом быстром страничном отображении накладывает существенные ограничения на способы построения компьютеров. Хотя проблема наиболее серьезно встает для старших моделей семейства, она также появляется и для младших моделей, когда стоимость и соотношение цена/производительность имеют критическое значение. Простейшее конструкторское решение заключается в поддержании таблицы страниц, состоящей из массива быстрых аппаратных регистров с одной записью для каждой виртуальной страницы, индексированного по номерам виртуальных страниц. Недостатком является его потенциально высокая стоимость. Необходимость загрузки полной таблицы в регистры при каждом контекстном переключении наносит ущерб производительности. Другая крайность заключается в том, что таблица страниц целиком располагается в оперативной памяти. Тогда все необходимое оборудование состоит из одного-единственного регистра, указывающего на начало таблицы страниц. Такая схема позволяет изменять карту памяти при контекстном переключении путем перезагрузки только одного регистра.

50 Многоуровневые таблицы страниц

51 Многоуровневые таблицы страниц (2) Чтобы обойти проблему необходимости постоянного хранения в памяти огромных таблиц страниц, многие компьютеры используют многоуровневую таблицу страниц. Простой пример представлен 32-разрядный виртуальный адрес, который разделен на 10-разрядное поле РТ1, 10-разрядное поле РТ2 и 12-разрядное поле Offset (смещение). Так как под смещение отведено 12 бит, страницы имеют размер 4 Кбайт, и их всего 220. Секрет метода многоуровневой таблицы страниц заключается в том, чтобы избегать постоянного содержания в памяти всех таблиц страниц. В частности, те части, которые не нужны в данный момент, не должны храниться в памяти. Предположим, например, что процессу нужно 12 Мбайт, младшие 4 Мбайт памяти для текста программы, следующие 4 Мбайт для данных и старшие 4 Мбайт для стека. Между верхом данных и низом стека образуется гигантский свободный участок, который не используется.

52 Структура элемента таблицы страниц Номер страничного блока Бит присутствия Бит изменения Бит Обращения Бит блокировки КЭШа

53 Структура элемента таблицы страниц (2) Наиболее важным полем является Номер страничного блока. Прежде всего, задачей отображения страниц является определение этой величины. За этим полем следует бит Присутствия/отсутствия. Если этот бит равен 1, запись имеет силу и может использоваться. Если он равен 0, виртуальная страница, которой соответствует эта запись, в данный момент отсутствует в памяти. Обращение к записи в таблице страниц, у которой этому биту присвоено нулевое значение, приводит к страничному прерыванию.

54 Структура элемента таблицы страниц (2) Биты Защиты говорят о том, какие разрешены виды доступа к этой странице. В простейшей форме это поле содержит один бит, равный 1 для чтения/записи и равный 0 только для чтения. Биты Изменения и Обращения отслеживают использование страницы. Когда страница записывается, аппаратура автоматически устанавливает бит Изменение.. Этот бит учитывается, когда операционная система решает освободить страничный блок. Если страница в нем была изменена (то есть она «грязная»), то ее новая версия должна быть переписана на диск. Если она не была модифицирована (то есть страница «чистая»), ее можно просто удалить из памяти, так как все еще действительна копия на диске. Этот бит иногда называют грязным битом, так как он отражает состояние страницы.

55 Структура элемента таблицы страниц (2) Бит Обращения устанавливается всякий раз, когда происходит обращение к странице для чтения или записи. Его значение помогает операционной системе при выборе страницы для удаления из памяти, когда случается ошибка из-за отсутствия страницы. Последний бит позволяет запретить кэширование страницы. Это свойство важно для страниц, отображающихся не на память, а на регистры устройств. Если операционная система находится в цикле ожидания ответа от некоторого устройства ввода-вывода, которому была только что дана команда, существенно, чтобы аппаратура продолжала получать слово из устройства.

56 Буферы быстрого преобразования адреса (TLB) Небольшое аппаратное устройство, служащие для отображения виртуальных адресов в физические без прохода по таблице страниц. Это устройство, называемое буфером быстрого преобразования адреса (TLB - Translation Lookaside Buffer) или иногда ассоциативной памятью. Оно обычно находится внутри диспетчера памяти и состоит из нескольких записей. В этом примере их восемь, но фактически записей редко бывает больше 64. Каждая запись содержит информацию об одной странице, а именно: номер виртуальной страницы, бит, устанавливаемый при изменении страницы, код защиты и номер физического страничного блока.

57 Буферы быстрого преобразования адреса (TLB) (2)

58 Программное управление буфером TLB Многие современные RISC-компьютеры, включая машины SPARC, MIPS, Alpha и HP PA, выполняют почти все страничное управление программно. На этих машинах записи буферы TLB явно загружаются операционной системой. Когда происходит неудачный поиск в буфере TLB, диспетчер памяти вместо того, чтобы переходить к таблице страниц для поиска и выбора необходимой страницы, формирует ошибку буфера TLB и передает проблему в руки операционной системы. Система должна найти страницу, удалить запись из буфера TLB, ввести новую запись и перезапустить прерванную инструкцию. Если буфер TLB имеет небольшой размер (скажем, 64 записи) для понижения частоты неудачных пропусков, программное управление буфером, оказывается, является приемлемо результативным. Главная выгода здесь заключается в намного более простом устройстве диспетчера памяти.

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

60 Инвертированные таблицы страниц (2) Традиционные таблицы страниц, тип которых мы описывали до сих пор, требуют по одной записи на каждую виртуальную страницу. Если адресное пространство состоит из 2 32 байт с размером страницы 4096 байт, тогда в таблице страниц должно быть больше миллиона записей. При этом таблица страниц будет занимать минимум 4 Мбайт. Однако поскольку 64-разрядные компьютеры встречаются все чаще, ситуация радикально меняется. Если теперь адресное пространство увеличилось до 2 52 байт с размером страницы 4 Кбайт, нам требуется таблица страниц с 252 записями. Если каждая запись равна 8 байтам, таблица займет больше 30 Тбайт. Выделение 30 Тбайт только для таблицы страниц нереально сейчас и не будет реальным когда-либо в будущем. Следовательно, для 64-разрядного страничного виртуального пространства необходимо другое решение.

61 Инвертированные таблицы страниц (2,5) Одним из таких решений является инвертированная таблица страниц. В этой модели таблица содержит по одной записи на страничный блок в реальной памяти, а не на страницу в виртуальном адресном пространстве. Например, при 64-разрядных виртуальных адресах, размере страниц 4 Кбайт и 256 Мбайт оперативной памяти инвертированная таблица страниц потребует всего лишь записей. Каждая запись отслеживает, что (процесс, виртуальная страница) расположено в данном страничном блоке.

62 Инвертированные таблицы страниц (3) Хотя инвертированные таблицы страниц экономят значительное количество места, по крайней мере, когда виртуальное адресное пространство намного больше, чем физическая память, они имеют серьезный недостаток: перевод виртуального адреса в физический становится намного сложнее. Когда процесс n обращается к виртуальной странице р, аппаратное обеспечение не может больше найти физическую страницу, используя номер р в качестве индекса в таблице страниц. Вместо этого оно должно производить поиск записи (n, р) во всей инвертированной таблице страниц. Более того, этот поиск должен выполняться при каждом обращении к памяти, а не только при страничном прерывании. Операция поиска в таблице размером 64 К при каждой ссылке к памяти вовсе не увеличит скорость вашей машины. Выйти из этого затруднительного положения можно, используя буфер быстрого преобразования адреса (TLB). Если буфер TLB может содержать все часто используемые страницы, трансляция адреса будет происходить так же быстро, как и с обычными таблицами страниц. Но при неудачном поиске в буфере TLB поиск в инвертированной таблице страниц должен выполняться программно. Один из возможных способов усовершенствовать его - поддерживать хэш-таблицу виртуальных адресов. Все виртуальные страницы, находящиеся в данный момент в памяти и имеющие одинаковое значение хэш-функции, сцепляются друг с другом. Если хэш-таблица состоит из такого же количества ячеек, сколько в машине физических страниц, средняя цепочка будет длиной только в одну запись, что значительно увеличит скорость отображения адресов. Как только найден номер страничного блока, новая пара (виртуальная, физическая) помещается в буфер TLB. Инвертированные таблицы страниц в настоящее время используются на некоторых рабочих станциях компаний IBM и Hewlett-Packard и будут встречаться все чаще, так как 64-разрядные машины получают все более широкое распространение.

63 Алгоритмы замещения страниц Когда происходит страничное прерывание, операционная система должна выбрать страницу для удаления из памяти, чтобы освободить место для страницы, которую нужно перенести в память. Если удаляемая страница была изменена за время своего присутствия в памяти, ее необходимо переписать на диск, чтобы обновить копию, хранящуюся там. Однако если страница не была модифицирована (например, она содержит текст программы), копия на диске уже является самой новой и ее не надо переписывать. Тогда страница, которую нужно прочитать, просто считывается поверх выгружаемой страницы. Хотя в принципе можно при каждом страничном прерывании выбирать случайную страницу для удаления из памяти, производительность системы заметно повышается, когда предпочтение отдается редко используемой странице. Если выгружается страница, обращения к которой происходят часто, велика вероятность, что вскоре опять потребуется ее возврат в память, что даст в результате дополнительные издержки. Теме разработки алгоритмов замены страницы было посвящено много работ, как теоретических, так и экспериментальных. Следует отметить, что проблема «страничного обмена» также встает и в других областях конструирования компьютеров. Например, у большинства компьютеров есть один или несколько кэшей, состоящих из используемых в последнее время 32-байтовых или 64-байтовых блоков памяти. Когда кэш заполнен, необходимо выбрать некоторые блоки для удаления. Эта проблема практически аналогична замещению страниц лишь с одной разницей, заключающейся в меньшем масштабе времени (операция должна быть выполнена за несколько наносекунд, а не миллисекунд, как для замены страниц). Причиной для более короткого промежутка времени является то, что неудачный поиск блока в кэше обрабатывается из основной памяти, в которой не тратится время на поиск нужного цилиндра диска и нет задержки из-за его вращения. Второй пример встречается на web-серверах. Сервер может хранить определенное количество часто используемых web-страниц в своей кэш-памяти. Однако когда кэш-память заполняется целиком и происходит обращение к новой странице, должно приниматься решение о том, какую из страниц выгружать. Здесь применимы те же рассуждения, что и для страниц в виртуальной памяти, с той разницей, что web-страницы никогда не изменяются в кэше, поэтому для них всегда есть свежая копия на диске. В системе виртуальной памяти страницы в оперативной памяти могут быть «чистыми» или «грязными».

64 Алгоритмы замещения страниц (2) Оптимальный алгоритм Алгоритм NRU – не использовавшаяся в последнее время страница Алгоритм FIFO – первым прибыл – первым обслужен Алгоритм «вторая попытка» Алгоритм «часы» Алгоритм LRU – страница, не использовавшаяся дольше всего Программное моделирование алгоритма LRU Алгоритм «рабочий набор» Алгоритм WSClock

65 Алгоритмы замещения страниц (3)

66 Сегментация

67 Сегментация. Таблицы компилятора. 1. Исходный текст. 2. Символьная таблица, содержащая имена и атрибуты переменных. 3. Таблица констант. 4. Дерево грамматического разбора, содержащее синтаксический анализ программы. 5. Стек, используемый для процедурных вызовов внутри компилятора.

68 Таблицы компилятора. Виртуальное адресное пространство. Таблица кодировки символов Исходный текст Таблица констант Дерево синтаксического анализа Стек вызовов

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

70 Сегментация. Таблицы компилятора.

71 Сегментация. Преимущества. Сегмент - это логический объект. Сегмент может иметь в составе процедуру, массив, стек или набор скалярных переменных. Каждая процедура занимает отдельный сегмент, компоновка отдельно скомпилированных процедур происходит намного проще. Таблица кодировки символов Исходный текст Таблица констант Дерево синтаксического анализа Стек вызовов П1 процедурапроцедура П2 П3 П1 П2 П3

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

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

74 Сравнения страничной и сегментной организации памяти

75 Реализация. Отличия. страницы имеют фиксированный размер, сегменты не имеют фиксированного размера.

76 Реализация

77 Pentium Пример реализации

78 Сегментация с использованием страниц: Intel Pentium Виртуальная память на компьютере Pentium использует сегментную и страничную организацию. Система Pentium поддерживает 16К независимых сегментов, каждый до 1 млрд 32-разрядных слов. Основа виртуальной памяти системы Pentium состоит их двух таблиц: локальной таблицы дескрипторов LDT (Local Descriptor Table); глобальной таблицы дескрипторов GDT (Global Descriptor Table).

79 Сегментация с использованием страниц: Intel Pentium У каждой программы есть своя собственная таблица LDT, глобальная таблица дескрипторов одна. Таблица LDT описывает сегменты, локальные для каждой программы, включая ее код, данные, стек и т.д. Таблица GDT несет информацию о системных сегментах, включая саму операционную систему.

80 Доступ к сегменту Операционная система Pentium сначала загружает селектор для сегмента в один из шести сегментных регистров машины. регистр CS содержит селектор для сегмента кода команд, регистр DS хранит селектор для сегмента данных. Каждый селектор представляет собой 16-разрядный номер. Один из битов селектора несет информацию о том, является ли данный сегмент локальным или глобальным. Тринадцать битов определяют номер записи в таблице дескрипторов. 2 бита относятся к проблемам защиты и будут описаны позже. Дескриптор 0 является запрещенным.

81 Селектор в системе Pentium

82 Дескриптор программного сегмента в системе Pentium.

83 Преобразование пары (селектор, смещение) в физический адрес

84 Отображение линейного адреса на физический адрес

85 Защита в системе Pentium