Лекции по "Системному программированию"

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

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

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

Большинство систем виртуальная памяти используют страничную организацию памяти (paging). Все программно формируемые адреса называются виртуальными адресами и формируют виртуальное адресное пространство. Если ОС не использует виртуальное адресное пространство, то виртуальный адрес подается непосредственно на адресную шину. В противном случае виртуальный адрес передается диспетчеру памяти, который преобразует виртуальный адрес в физический и уже его подает на шину. Допустим, рассматриваемая система может формировать 16-разрядные адреса от 0 до 64к - это виртуальное адресное пространство. Так же система имеет основную память объемом 32к. Виртуальное адресное пространство разделено на блоки памяти, называемые страницами (page). Физическая память разделена на блоки точно такого же размера и эти блоки называются страничными кадрами (page frame).

В фактическом  аппаратном обеспечении страницы, присутствующие в оперативной памяти, отслеживаются с помощью бита присутствия/отсутствия. В случае инструкции mov ax, 16k произойдет обращение к неотображаемой странице. В этом случае диспетчер памяти инициирует прерывание ЦП, передающее управление ОС. Такое прерывание называется страничным прерыванием (page fault). ОС блокирует вызвавший прерывание процесс, выбирает малоиспользуемый страничный блок и записывает его на диск. Далее соответствующая страница записывается в освободившийся страничный кадр, и устанавливается бит присутствия, после чего управление передается либо прерванному процессу либо планировщику. 16-разрядный адрес состоит из 4-битного номера страницы и 12-битного смещения (4к). Номер страницы используется в качестве индекса в таблице страниц, которая выдает номер страничного кадра, соответствующего виртуальной странице.

 

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

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

В нашей системе 32к виртуального адресного пространства и 16к основной памяти.

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

- таблица  может быть слишком большой.  При размере страницы 4к, для  32-разрядного адресного пространства, каждая таблица страниц будет  содержать 2^20 записей, при том,  что каждый процесс нуждается  в своей собственной таблице  страниц;

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

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

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

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

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

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

30. Структура элемента таблицы  страниц. 

Наиболее  распространенный размер - 32 бита. В  зависимости от системы, точная структура  может изменяться, но основная информация в основном совпадает.

 

 

 

 

Бит присутствия: 1 - страницы присутствует в памяти. 0 - страница отсутсвует в памяти, при обращении возникает страничная ошибка.

Биты защиты: в простейшей схеме 1 бит. 0 - только чтение. 1 - чтение/запись. В сложных схемах используются 3 бита, по одному для каждой операции (чтение, запись, выполнение).

Бит изменения: устанавливается в 1 при изменении  страницы. Учитывается при решении  ОС освободить страничный кадр. Если бит установлен в 1 - страница должна быть перезаписана на диск.

Бит обращения - устанавливается при каждом обращении  к данной странице. Сбрасывается через  определенные промежутки времени. Используется при выборе страниц на удаление из памяти.

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

В записи не содержится адреса места на диске  для страницы, выгруженной из памяти. Эта информация хранится в служебных таблицах ОС.

31. Буфер быстрого преобразования  адреса.

Буферы быстрого преобразования адреса. Ассоциативная  память

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

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

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

Традиционные  таблицы страниц требуют по одной  записи для каждой виртуальной страницы. Для 32-разрядного виртуального адресного  пространства и страницы размером в 4к таблицы страниц займет 4Мб. Для 64-разрядного адресного пространства таблица займет порядка 15Тб. Чтобы  решить эту проблему используются инвертированные  таблицы страниц. В такой модели таблица содержит по одной записи на каждый страничный блок. Тогда для 64-разрядного виртуального адресного  пространства при 256Мб оперативной  памяти с размером страничного блока 4к, таблица страниц займет 4б*64к (менее 1Мб). Хотя инвертированные таблицы  экономят много места, усложняется  процесс перевода виртуального адреса в физический. Когда процесс N обращается к виртуальной странице P, аппаратное обеспечение не сможет найти физическую страницу используя только номер P в качестве индекса. Вместо этого поиск должен производиться по паре (N,P) во всей инвертированной таблице. Кроме того поиск должен выполняться при каждом обращении к памяти. Ускорить процесс можно с помощью ассоциативной памяти. Буфер TLB может содержать все часто используемые страницы. В этом случае поиск будет проходить так же быстро, как и с обычными таблицами. Однако, при неудачном поиске придется программно искать пару во всей инвертированной таблице. Усовершенствовать такой поиск можно с помощью хэш-таблицы виртуальных страниц. Все виртуальные страницы, которые находятся в данный момент в памяти и имеют одинаковое значение хэш-функции, сцепляются друг с другом.

33. Алгоритмы замещения страниц.  Оптимальный алгоритм. Алгоритм  NRU.

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

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

 

 

Оптимальный алгоритм

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

NRU (Not Recently Used) алгоритм (не использовавшаяся в последнее время страница)

В табличной  записи для каждой страницы присутствуют 2 бита:

- бит R (бит обращения) устанавливается в единицу при каждом обращении к странице. Возможен сброс этого бита, например каждые n тиков таймера, чтобы отличить страницы, к которым давно не было обращения;

- бит M (бит модификации) устанавливается в единицу при изменении страницы. Сигнализирует о том, что при удалении надо страницу записать на диск.

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

34. Алгоритмы замещения страниц.  FIFO. Вторая попытка. Алгоритм LRU.

FIFO алгоритм

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

Алгоритм "вторая попытка"

Является  модификацией алгоритма FIFO. При страничном прерывании, у первой страницы в списке изучается бит R. Если он равен единице, страница помещается в конец списка, а бит R сбрасывается, и проверяется следующая страница. Данный алгоритм ищет в списке страницу, к которой не было обращений за последние n тиков таймера. Если происходили ссылки на все страницы, алгоритм превращается в обычный FIFO.

35. Алгоритмы замещения страниц.  Часы. Алгоритм LRU.

Алгоритм "часы"

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

 

Алгоритм  LRU (Last Recently Used), страница, не использовавшаяся больше всего

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

Для первого  метода требуется оснащение компьютера специальным N-разрядным счетчиком, который автоматически возрастает после каждой команды. Кроме этого, каждая запись в таблице страниц должна иметь поле для хранения значения этого счетчика. После каждого обращения к памяти, значение счетчика запоминается в записи в таблице в соответствующей странице, к которой произошло обращение. Если возникает страничное прерывание, менеджер памяти проверяет значение счетчиков во всей таблице и ищет наименьшее. Эта страница и является неиспользуемой дольше всего.

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

 

 

36. 37. Сегментация памяти. Сегментация в ядрах Intel Pentium.

Сегментация

Описанная выше виртуальная память представляет собой  одномерное пространство, то есть виртуальные  адреса идут по порядку от 0 до некоторого максимума. В этом адресном пространстве могут одновременно располагаться  различные наборы данных, например CODE, DATA, STACK. В случае использования виртуальных адресов программа не видит разницы между разными наборами данных и может, например, попытаться поменять данные из набора CODE.

В таких обстоятельствах  удобно было бы иметь несколько отдельных  виртуальных адресных пространств. Самым простым решением  является обеспечение компьютера так называемыми  сегментами. Каждый сегмент может  иметь разную длину, свои атрибуты защиты и начинаться с любого адреса. Для  адресации внутри сегмента вместо 32-разрядного виртуального адреса используется пара значений: номер сегмента и смещение внутри сегмента (sg:offs). Поскольку сегменты независимы друг от друга, они самостоятельно могут изменять размер. Сегмент является логическим объектом, что должно учитываться программистом при написании программы (например, сегмент не должен одновременно содержать данные и код). При наличии различных атрибутов защиты и отсутствии криворукости у разработчика можно избежать попыток несанкционированного доступа к разным типам данных.