§ 4.1.Общиепринципыорганизациипамяти
Оперативнаяпамять (ОП) - один из важнейших ресурсов ОС, без которого не-
возможна работа на персональном компьютере. Поэтому изучение механизмов исполь-
зования памяти различными задачами и самой операционной системой по значимости
аналогично изучению механизмов многопоточности, событий, прерываний и т.п. С по-
явлением первых поколений ЭВМ в них было введено понятие оперативнойпамяти,
которую часто называют физическойпамятью. Оперативная память представляет со-
бой упорядоченное множество ячеек, и все они пронумерованы, то есть к каждой из них
можно обратиться, указав ее порядковый номер (адрес). Количество ячеек физической
памяти ограничено и фиксировано. Центральный процессор извлекает из ОП команды и
данные и помещает в нее результаты вычислений. Одновременно с этим, с точки зрения
программиста, ОП - область, с которой можно работать с помощью некоторого набора
логических имен (переменных), которые могут быть символьными или числовыми. Сле-
дует отметить, что множество переменных неупорядочено, хотя отдельные элементы и
могут располагаться в некотором порядке, например, элементы массива. Имена пере-
менных и входных точек программных модулей составляют пространство имен.
Операционная система должна связать каждое указанное пользователем имя с фи-
зической ячейкой памяти, то есть осуществить отображение пространства имен на физи-
ческую память компьютера. В общем случае это отображение осуществляется в два эта-
па, представленных на рис.4.1 [2]: сначала системой программирования, а затем
операционной системой, управляющей соответствующими аппаратными средствами. В
|
|
современных ОС переход с первого этапа на второй осуществляется через промежуточ-
ный виртуальный или логический адрес. При этом можно сказать, что множество всех
допустимых значений виртуального адреса для некоторой программы определяет ее
виртуальноеадресноепространство или виртуальнуюпамять. Виртуальное адрес-
ное пространство зависит прежде всего от архитектуры процессора и от системы про-
граммирования и практически не зависит от объема реальной физической памяти, уста-
новленной в персональном компьютере.
Любая система программирования осуществляет трансляцию и компоновку про-
граммы, используя библиотечные программные модули. В результате работы системы
программирования полученные виртуальные адреса могут иметь как двоичную форму,
так и символьно-двоичную, то есть некоторые программные модули и их переменные
получают какие-то числовые значения, а другие, адреса для которых в данный момент
не могут быть определены, имеют по-прежнему символьную форму и их окончательная
привязка к физическим ячейкам будет осуществлена на этапе загрузки программы в па-
мять перед ее непосредственным выполнением.
Одним из частных случаев отображения пространства имен на физическую память
[2] является тождественностьвиртуальногоадресногопространствафизической
памяти. При этом нет необходимости осуществлять второе отображение. В данном
случае говорят, что система программирования генерирует абсолютнуюдвоичнуюпро-
грамму; в этой программе все двоичные адреса таковы, что программа может испол-
|
|
няться только в том случае, если ее виртуальные адреса будут точно соответствовать
физическим. Часть программных модулей любой операционной системы обязательно
должны быть абсолютными двоичными программами. Эти программы размещаются по
фиксированным адресам и с их помощью далее можно реализовывать размещение ос-
тальных программных модулей, подготовленных системой программирования, на раз-
личных свободных физических адресах.
Рис.4.1. Связь переменной с физической памятью
Если рассматривать общую схему двухэтапного отображения адресов, то с пози-
ции соотношения объемов упомянутых адресных пространств можно отметить наличие
следующих трех ситуаций [2]:
• объем виртуального адресного пространства программы VVменьше объема физиче-
ской памяти Vp;
• V = Vp;
• V > Vp.
Первая ситуация, при которой VV < Vp, в настоящее время практически не встре-
чается, но тем не менее это реальное соотношение. Скажем, не так давно 16-разрядные
мини-ЭВМ имели систему команд, в которых пользователи-программисты могли адре-
совать до 216=64K адресов (обычно в качестве адресуемой единицы выступала ячейка
памяти размером 1 байт). А физически старшие модели этих мини-ЭВМ могли иметь
объем оперативной памяти в несколько мегабайт. Обращение к памяти столь большого
объема осуществлялось с помощью специальных регистров, содержимое которых скла-
дывалось с адресом операнда (или команды), извлекаемым и/или определяемым из поля
операнда (или из указателя команды). Соответствующие значения в эти специальные
|
|
регистры, выступающие как базовое смещение в памяти, заносила операционная систе-
ма. Для одной задачи в регистр заносилось одно значение, а для второй (третьей, четвер-
той и т. д.) задачи, размещаемой одновременно с первой, но в другой области памяти,
заносилось, соответственно, другое значение. Вся физическаяпамять,такимобразом,
разбиваласьнаразделыобъемомпо 64Кбайт, и на каждый такой раздел осуществля-
лось отображение своего виртуального адресного пространства.
Ситуация, когда VV = Vp, еще совсем недавно (80-90-е годы XX века) встречалась
достаточно часто, особенно характерна она была для недорогих вычислительных ком-
плексов. Для этого случая имелось большое количество способов распределения опера-
тивной памяти.
Наконец, в настоящее время наиболее вероятной является ситуация VV > Vp. Реа-
лизовано несколько способов распределения памяти для этого случая, отличающихся
как сложностью, так и эффективностью. Все эти способы можно разделить на две боль-
шие группы - непрерывные и разрывные [2, 5]. В первом случае каждая задача размеща-
ется в одной непрерывной области памяти, во втором разбивается на несколько не свя-
занных между собой областей. Рассмотрим наиболее известные способы распределения
памяти.
§ 4.2.Способыраспределенияпамяти
4.2.1. Простое непрерывное распределение памяти
Это самое простое решение, согласно которому вся память условно может быть
разделена на три участка:
• область, занимаемая операционной системой;
• область, в которой размещается исполняемая задача;
• свободная область памяти.
Изначально являясь самой первой схемой, она продолжает и сегодня быть доста-
точно распространенной в элементарных системах. При простом непрерывном распре-
делении предполагается, что ОС не поддерживает мультипрограммирование, поэтому не
возникает проблемы распределения памяти между несколькими задачами. Программные
модули, необходимые для всех программ, располагаются в области самой ОС, а вся ос-
тавшаяся память может быть предоставлена задаче. Эта область памяти является непре-
рывной, что облегчает работу системы программирования.
Для того, чтобы выделить наибольший объем памяти для задач, ОС строится таким
образом, что постоянно в оперативной памяти располагается только самая нужная ее
часть. Эту часть стали называть ядромоперационнойсистемы. Остальные модули ОС
являются диск-резидентными, то есть загружаются в оперативную память только по не-
обходимости, и после своего выполнения вновь выгружаются.
Такая схема распределения памяти влечет за собой двавидапотерьвычисли-
тельныхресурсов [2]: потеря процессорного времени, потому что центральный процес-
сор простаивает, пока задача ожидает завершения операций ввода/вывода, и потеря са-
мой оперативной памяти, потому что далеко не каждая программа использует всю
память, а режим работы в этом случае однопрограммный. Однако это очень недорогая
реализация, которая позволяет отказаться от многих дополнительных функций операци-
онной системы. В частности, от такой сложной проблемы, как защита памяти.
Классическимпримеромдляданногослучаяявляетсяраспределениепамятив
ОС DOS. Как известно, MS-DOS - это однопрограммная ОС. В ней, конечно, можно ор-
ганизовать запуск резидентных или TSR-задач, но в целом она предназначена для вы-
полнения только одного вычислительного процесса.
В IBM PC изначально использовался 16-разрядный микропроцессор i8086/88, ко-
торый за счет введения сегментного способа адресации позволял адресовать память объ-
емом до 1 Мбайт. В последующих ПК (IBM PC AT, AT386 и др.) поддерживалась со-
вместимость с первыми, поэтому при работе с MS-DOS прежде всего рассматривают
первый мегабайт. Таким образом, вся память в соответствии с архитектурой IBM PC ус-
ловно может быть разбита на три части [ОС].
В самыхмладшихадресахпамяти (первые 1024 ячейки) размещается таблица
векторов прерываний. Это связано с аппаратной реализацией процессора i8086/88, на
котором был реализован ПК. В последующих процессорах (начиная с i80286) адрес таб-
лицы прерываний определяется через содержимое соответствующего регистра, но для
обеспечения полной совместимости с первым процессором при включении или аппарат-
ном сбросе в этот регистр заносятся нули. Следует отметить, что в случае использования
современных микропроцессоров i80x86 векторы прерываний можно разместить и в дру-
гой области.
Втораячастьпамяти отводится для размещения программных модулей самой
MS-DOS и программ пользователя. Эта область памяти называется Conventional Memory
(основная, стандартная память). В младших адресах основной памяти размещается то,
что можно назвать ядром ОС - системные переменные, основные программные модули,
блоки данных для буферизации операций ввода/вывода. Для управления устройствами,
драйверы которых не входят в базовую подсистему ввода/вывода, загружаются так на-
зываемые загружаемые (или инсталлируемые) драйверы, перечень которых определя-
ется в специальном конфигурационном файле CONFIG.SYS. В случае использования ПК
с объемом ОП более 1 Мбайта и наличия в памяти драйвера HIMEM.SYS возможно раз-
мещение данных за пределами первого мегабайта. Эта область памяти получила назва-
ние HMA (high memory area- область высокой памяти)
Наконец, третьячастьадресногопространства отведена для постоянных запо-
минающих устройств и функционирования некоторых устройств ввода/вывода. Эта об-
ласть памяти получила название UMA (upper memory areas - область верхней памяти).
Для того чтобы предоставлять больше памяти программам пользователя, в MS-
DOS применено то же решение, что и во многих других простейших ОС - командный
процессор COMMAND.СОМ сделан состоящим из двух частей. Первая часть является
резидентной, она размещается в области ядра. Вторая часть - транзитивная; она разме-
щается в области старших адресов раздела памяти, выделяемой для программ пользова-
теля. Если программа пользователя перекрывает собой область, в которой была распо-
ложена транзитивная часть командного процессора, то последний при необходимости
восстанавливает ее в памяти после выполнения программы, так как далее управление
возвращается резидентной части COMMAND.СОМ.
4.2.2. Распределение памяти с перекрытием (оверлейные структуры)
Если есть необходимость создать программу, логическое (и виртуальное) адресное
пространство которой должно быть больше, чем свободная область памяти, или даже
больше, чем весь возможный объем оперативной памяти, то используется распределение
с перекрытием. Этот способ распределения предполагает, что вся программа может быть
разбита на части - сегменты. Каждая оверлейная программа имеет одну главнуючасть
(main) и несколькосегментов (segment), причем в памяти машины одновременно могут
находиться только ее главная часть и один или несколько не перекрывающихся сегмен-
тов.
Пока в оперативной памяти располагаются выполняющиеся сегменты, остальные
находятся во внешней памяти. После того как текущий (выполняющийся) сегмент за-
вершит свое выполнение, возможны два варианта. Либо он сам (если данный сегмент не
нужно сохранить во внешней памяти в его текущем состоянии) обращается к ОС с ука-
занием, какой сегмент должен быть загружен в память следующим. Либо он возвращает
управление главному сегменту задачи (в модуль main), и уже тот обращается к ОС с
указанием, какой сегмент сохранить (если это нужно), а какой сегмент загрузить в опе-
ративную память, и вновь отдает управление одному из сегментов, располагающихся в
памяти. Простейшие схемы сегментирования предполагают, что в памяти в каждый кон-
кретный момент времени может располагаться только один сегмент (вместе с модулем
main). Более сложные схемы, используемые в больших вычислительных системах, по-
зволяют располагать сразу по несколько сегментов. В некоторых вычислительных ком-
плексах могли существовать отдельно сегменты кода и сегменты данных. Сегменты ко-
да, как правило, не претерпевают изменений в процессе своего исполнения, поэтому при
загрузке нового сегмента кода на место отработавшего последний можно не сохранять
во внешней памяти, в отличие от сегментов данных, которые необходимо сохранять в
любом случае.
Первоначально программисты сами должны были включать в тексты своих про-
грамм соответствующие обращения (вызовы) к ОС и тщательно планировать, какие сег-
менты могут находиться в оперативной памяти одновременно, чтобы их адресные про-
странства не пересекались. В более современных системах программирования вызовы
стали вставляться компиляторами в код программы автоматически, если в том возникает
необходимость.
4.2.3. Распределение памяти разделами
Для организации мультипрограммного режима необходимо обеспечить одновре-
менное расположение в оперативной памяти нескольких задач (целиком или их частя-
ми). Самая простая схема распределения памяти между несколькими задачами предпо-
лагает, что память, незанятая ядром ОС, может быть разбитананесколько
непрерывныхчастей (зон, разделов). Разделы характеризуются именем, типом, грани-
цами (как правило, указываются начало раздела и его длина). Разбиение памяти на не-
сколько непрерывныхразделов может быть фиксированным (статическим), либо ди-
намическим. Рассмотрим вышесказанное более подробно.
Разбиение всего объема оперативной памяти на несколько разделов может осуще-
ствляться единовременно (то есть в процессе генерации варианта ОС, который потом и
эксплуатируется) или по мере необходимости. Пример разбиения памяти на разделы с
фиксированными границами приведен на рис.4.2.
Рис.4.2. Распределение памяти разделами с фиксированными границами
В каждом разделе на данный момент времени может располагаться по одной про-
грамме (задаче). В этом случае по отношению к каждому разделу можно применить все
те методы разработки программ, которые используются для однопрограммных систем.
Возможно использование оверлейных структур, что позволяет создавать более сложные
программы и в то же время поддерживать идеологию мультипрограммирования. Первые
многозадачные ОС, а в более поздний период - недорогие вычислительные системы
строились по подобной схеме, так как она является несложной и обеспечивает возмож-
ность параллельного выполнения программ. Иногда в одном разделе размещалось по
несколько небольших программ, которые постоянно в нем и находились. Такие про-
граммы назывались ОЗУ-резидентными.
При небольшом объеме памяти и, следовательно, небольшом количестве разделов
увеличить количество параллельно выполняемых приложений (особенно когда эти при-
ложения интерактивны и во время своей работы фактически не используют процессор-
ное время, а в основном ожидают операций ввода/вывода) можно за счет идеологии сво-
пинга (swapping). При свопинге задача может быть целиком выгружена на магнитный
диск (перемещена во внешнюю память), а на ее место загружается либо более привиле-
гированная, либо просто готовая к выполнению другая задача, находившаяся на диске в
приостановленном состоянии.
Основнымнедостатком такого способа распределения памяти является наличие
достаточно большого объема неиспользуемой памяти, которая может быть в каждом из
разделов. Поскольку разделов несколько, то и неиспользуемых областей получается не-
сколько, поэтому такие потери стали называть фрагментациейпамяти. В отдельных
разделах потери памяти могли быть достаточно значительными, но использовать фраг-
менты свободной памяти при таком способе распределения практически невозможно.
Чтобы избавиться от фрагментации, можно размещать в оперативной памяти зада-
чи плотно (динамически), одну за другой, выделяя ровно столько памяти, сколько зада-
ча требует.
Одной из первых ОС, реализовавшей такой способ распределения памяти, была ОС
MVT (multiprogramming with a variable number of tasks) - мультипрограммирование с пе-
ременным числом задач. Эта ОС была одной из самых распространенных при эксплуа-
тировании больших ЭВМ класса IBM 360/370. В этой системе специальныйпланиров-
щик (диспетчер памяти) ведет список адресов свободной оперативной памяти. При
появлении новой задачи диспетчер памяти просматривает этот список и выделяет для
задачи раздел, объем которого либо равен необходимому, либо чуть больше, если па-
мять выделяется не ячейками, а некими дискретными единицами. При этом модифици-
руется список свободной памяти. При освобождении раздела диспетчер памяти пытается
объединить освобождающийся раздел с одним из свободных участков, если таковой яв-
ляется смежным.
При этом список свободных участков может быть упорядочен либо по адресам,
либо по объему. Выделение памяти под новый раздел может осуществляться одним из
трех методов [2]:
• первый подходящий участок;
• самый подходящий участок;
• самый неподходящий участок.
В первомслучае список свободных областей упорядочивается по адресам (напри-
мер, по их возрастанию). Диспетчер памяти просматривает этот список и выделяет зада-
че раздел в той области, которая первой подойдет по объему. В этом случае, если подоб-
ный фрагмент имеется, то в среднем необходимо просмотреть половину списка. При
освобождении раздела также необходимо просмотреть половину списка. Таким образом,
«первыйподходящий»методприводитктому,чтопамятьдлянебольшихзадач
преимущественнобудетвыделятьсявобластимладшихадресови,следовательно,
этобудетувеличиватьвероятностьтого,чтовобластистаршихадресовбудут
образовыватьсяфрагментыдостаточнобольшогообъема.
Метод «самыйподходящий» предполагает, что список свободных областей упо-
рядочен по возрастанию объема этих фрагментов. В этом случае при просмотре списка
для нового раздела будет использован фрагмент свободной памяти, объем которой наи-
более точно соответствует требуемому. Требуемый раздел будет определяться по-
прежнему в результате просмотра в среднем половины списка. В результате оставшийся
фрагмент оказывается настолько малым, что в нем уже вряд ли удастся разместить ка-
кой-либо еще раздел и при этом этот фрагмент попадет в самое начало списка. Поэтому
в целом такую дисциплину нельзяназватьэффективной.
Как ни странно, самымэффективнымметодом является последний, по которому
для нового раздела выделяется «самыйнеподходящий » фрагмент свободной памяти.
Для этой дисциплины список свободных областей упорядочивается по убыванию объе-
ма свободного фрагмента. Очевидно, что если есть такой фрагмент памяти, то он сразу
же и будет найден, и поскольку этот фрагмент является самым большим, то, скорее все-
го, после выделения из него раздела памяти для задачи оставшаяся область памяти еще
сможет быть использована в дальнейшем.
Очевидно, что при любом из вышеуказанных методов, из-за того, что задачи появ-
ляются и завершаются в произвольные моменты времени и при этом они имеют разные
объемы, в памяти всегда будет наблюдаться сильная фрагментация. При этом возможны
ситуации, когда из-за сильной фрагментации памяти диспетчер задач не сможет образо-
вать новый раздел, хотя суммарный объем свободных областей будет больше, чем необ-
ходимо для задачи. В этой ситуации необходимо организовать так называемое уплот-
нениепамяти(дефрагментацию). Для уплотнения все вычисления
приостанавливаются, и диспетчер памяти корректирует свои списки, перемещая разделы
в начало памяти (или, наоборот, в область старших адресов). Недостаткомэтогоре-
шенияявляетсяпотерявременинадефрагментацию и, что самое главное, невоз-
можность при этом выполнять сами вычислительные процессы.
Следует отметить, что данный способ распределения памяти применялся доста-
точно длительное время, так как в нем для задач выделяется непрерывное адресное про-
странство, что существенно упрощает создание систем программирования и их работу.
В современных ОС на смену различным непрерывнымспособам распределения
памяти пришли разрывныеспособы. Идея заключается в предложении размещать задачу
не в одной непрерывной области памяти, а в нескольких областях. Это требует для своей
реализации соответствующей аппаратной поддержки - нужно иметь относительную ад-
ресацию. Если указывать адрес начала текущего фрагмента программы и величину сме-
щения относительно этого начального адреса, то можно указать необходимую нам пе-
ременную или команду. Таким образом,виртуальныйадресможнопредставить
состоящимиздвухполей. Первое поле будет указывать часть программы (с которой
сейчас осуществляется работа) для определения местоположения этой части в памяти, а
второе поле виртуального адреса позволит найти нужную нам ячейку относительно най-
денного адреса. Программист может либо самостоятельно разбивать программу на
фрагменты, либо автоматизировать эту задачу и возложить ее на систему программиро-
вания. Рассмотрим наиболее распространенные разрывные способы распределения па-
мяти.
4.2.4. Сегментное распределение памяти
Для реализации этого способа программу необходимо разбивать на части и уже
каждой части в отдельности выделять физическую память. Естественным механизмом
разбиения программы на части является разбиение ее на логическиеэлементы -сег-
менты. В принципе каждый программный модуль может быть воспринят как отдельный
сегмент, и тогда вся программа будет представлять собой множество сегментов. Каждый
сегмент размещается в памяти как до определенной степени самостоятельная единица.
Логически обращение к элементам программы в этом случае будет представляться как
указание имени сегмента и смещения относительно начала этого сегмента. Физически
имя (или порядковый номер) сегмента будет соответствовать некоторому адресу, с кото-
рого этот сегмент начинается при его размещении в памяти, и смещение должно при-
бавляться к этому базовому адресу.
Преобразование имени сегмента в его порядковый номер осуществляет система
программирования, а операционнаясистема размещает сегменты в физической памя-
ти и для каждого сегмента получает информацию о его начале. Таким образом, вирту-
альныйадресдляданногоспособасостоитиздвухполей -номерсегментаисмеще-
ниеотносительноначаласегмента. Каждый сегмент, размещаемый в памяти, имеет
соответствующую информационную структуру, часто называемую дескрипторомсег-
мента. Именно операционная система строит для каждого исполняемого процесса соот-
ветствующую таблицу дескрипторов сегментов и при размещении каждого из сегментов
в оперативной или внешней памяти в дескрипторе отмечает его текущее местоположе-
ние. Если сегмент задачи в данный момент находится в оперативной памяти, то об этом
делается пометка в дескрипторе. Как правило, для этого используется «битприсутст-
вия » (present bit). Вэтомслучаевполе «адрес»диспетчерпамятизаписываетадрес
физическойпамяти, с которого сегмент начинается, а вполе «длинасегмента» (limit)
указываетсяколичествоадресуемыхячеекпамяти. Это поле используется не только
для того, чтобы размещать сегменты без наложения один на другой, но и для того, чтобы
проконтролировать, не обращается ли код исполняющейся задачи за пределы текущего
сегмента. В случае превышения длины сегмента вследствие ошибок программирования
мы можем говорить о нарушении адресации и с помощью введения специальных аппа-
ратных средств генерировать сигналы прерывания, которые позволят обнаруживать по-
добные ошибки. Если битприсутствия в дескрипторе указывает, что сейчас этот сег-
мент находится не в оперативной, а во внешней памяти (например, на жестком диске), то
названные поля адреса и длины используются для указания адреса сегмента в координа-
тах внешней памяти.
Помимо информации о местоположении сегмента, в дескрипторе сегмента, как
правило, содержатся данные о его типе (сегмент кода или сегмент данных), правах дос-
тупа к этому сегменту (можно или нельзя его модифицировать, предоставлять другой
задаче), отметка об обращениях к данному сегменту (информация о том, как часто этот
сегмент используется), на основании которых можно принять решение о предоставлении
места, занимаемого текущим сегментом, другому сегменту.
При передаче управления следующей задаче ОС должна занести в соответствую-
щий регистр адрес таблицы дескрипторов сегментов для этой задачи. Сама таблицаде-
скрипторовсегментов, в свою очередь, также представляет собой сегмент данных, ко-
торый обрабатывается диспетчером памяти операционной системы.
При таком подходе появляется возможность размещать в оперативной памяти не
все сегменты задачи, а только те, с которыми в настоящий момент происходит работа.
Если требуемого сегмента в оперативной памяти нет, то возникает прерывание и управ-
ление передается через диспетчер памяти программе загрузки сегмента. Пока происхо-
дит поиск сегмента во внешней памяти и загрузка его в оперативную, диспетчер памяти
определяет подходящее для сегмента место. Возможно, что свободного места нет, и то-
гда принимается решение о выгрузке какого-нибудь сегмента и его перемещение во
внешнюю память. Если при этом еще остается время, то процессор передается другой
готовой к выполнению задаче. После загрузки необходимого сегмента процессор вновь
передается задаче, вызвавшей прерывание из-за отсутствия сегмента. Всякий раз при
считывании сегмента в оперативную память в таблице дескрипторов сегментов необхо-
димо установить адрес начала сегмента и признак присутствия сегмента.
Припоискесвободногоместа обычно используются правила «первого подходя-
щего» и «самого неподходящего». Если свободного фрагмента в памяти достаточного
объема нет, но тем не менее сумма свободных фрагментов превышает требования по
памяти для нового сегмента, может быть применена процедура дефрагментации памяти.
В идеальном случае размер сегмента должен быть достаточно малым, чтобы его
можно было разместить в случайно освобождающихся фрагментах оперативной памяти,
но и достаточно большим, чтобы содержать логически законченную часть программы с
тем, чтобы минимизировать межсегментные обращения.
Длярешенияпроблемызамещения (определения того сегмента, который должен
быть либо перемещен во внешнюю память, либо просто замещен новым) используются
следующие правила [2]:
• FIFO (first in - first out, что означает: «первый пришедший первым и выбывает»);
• LRU (least recently used, что означает «последний из недавно использованных» или,
иначе говоря, «дольше всего неиспользуемый»);
• LFU (least frequently used, что означает: «используемый реже всех остальных»);
• random (случайный) выбор сегмента.
Первая и последняя дисциплины являются самыми простыми в реализации, но они
не учитывают, насколько часто используется тот или иной сегмент и, следовательно,
диспетчер памяти может выгрузить или расформировать тот сегмент, к которому в са-
мом ближайшем будущем будет обращение.
Алгоритм FIFO ассоциирует с каждым сегментом время, когда он был помещен в
память. Для замещения выбирается наиболее старый сегмент. Учет времени необязате-
лен, когда все сегменты в памяти связаны в FIFO-очередь и каждый помещаемый в па-
мять сегмент добавляется в хвост этой очереди. Алгоритм учитывает только время на-
хождения сегмента в памяти, но не учитывает фактическое использование сегментов.
Например, первые загруженные сегменты программы могут содержать переменные, ис-
пользуемые на протяжении работы всей программы. Это приводит к немедленному воз-
вращению к только что замещенному сегменту.
Для реализации дисциплин LRU и LFU необходимо, чтобы процессор имел допол-
нительные аппаратные средства. В принципе достаточно, чтобы при обращении к деск-
риптору сегмента для получения физического адреса, с которого сегмент начинает рас-
полагаться в памяти, соответствующий бит обращения менял свое значение (скажем, с
нулевого, которое установила ОС, в единичное). Тогда диспетчер памяти может время
от времени просматривать таблицы дескрипторов исполняющихся задач и собирать для
соответствующей обработки статистическую информацию об обращениях к сегментам.
В результате можно составить список, упорядоченный либо по длительности не исполь-
зования (для дисциплины LRU), либо по частоте использования (для дисциплины LFU).
Важнейшейпроблемой, которая возникает при организации мультипрограммного
режима, является защитапамяти. Для того чтобы выполняющиеся приложения не
смогли испортить саму ОС и другие вычислительные процессы, необходимо, чтобы дос-
туп к таблицам сегментов с целью их модификации был обеспечен только для кода са-
мой ОС. Для этого код ОС должен выполняться в некотором привилегированном режи-
ме, из которого можно осуществлять манипуляции с дескрипторами сегментов, тогда
как выход за пределы сегмента в обычной прикладной программе должен вызывать пре-
рывание по защите памяти. Каждая прикладная задача должна иметь возможность об-
ращаться только к своим собственным сегментам.
Остановимся на основных недостатках сегментного способа распределения памя-
ти. Во-первых, по сравнению с непрерывными способами, произошло увеличениевре-
мениназагрузкупрограммыиеесегментов. Для получения доступа к искомой ячейке
памяти необходимо сначала найти и прочитать дескриптор сегмента, а уже потом, ис-
пользуя данные из него, вычислить и конечный физический адрес сегмента. Для того
чтобы уменьшить эти потери, используется кэширование, т.е расположение дескрипто-
ров выполняемых задач в кэш-памяти микропроцессора.
Вторым недостатком является наличиефрагментациипамяти, хотя и сущест-
венно меньшей, чем при непрерывном распределении.
Кроме этого, имеются потерипамятиипроцессорноговременинаразмещениеи
обработкудескрипторныхтаблиц, так как на каждую задачу необходимо иметь свою
таблицу дескрипторов сегментов, а при определении физических адресов необходимо
выполнять операции сложения. Уменьшение этих недостатков реализовано в странич-
ном способе распределения памяти, который будет рассмотрен далее.
Примером использования сегментного способа организации виртуальной памяти
является операционная система для ПК OS/2 ver.1, созданная для процессора i80286. В
этой ОС в полной мере использованы аппаратные средства микропроцессора, который
специально проектировался для поддержки сегментного способа распределения памяти.
OS/2 v.1 поддерживала распределение памяти, при котором выделялись сегменты
программы и сегменты данных. Система позволяла работать как с именованными, так и
неименованными сегментами. Имена разделяемых сегментов данных имели ту же фор-
му, что и имена файлов. Процессы получали доступ к именованным разделяемым сег-
ментам, используя их имена в специальных системных вызовах. OS/2 v.1 допускала раз-
деление программных сегментов приложений и подсистем, а также глобальных
сегментов данных подсистем. Сегменты, которые активно не использовались, могли вы-
гружаться на жесткий диск. Система восстанавливала их, когда в этом возникала необ-
ходимость. Вообще, вся концепция системы OS/2 была построена на понятии разделения
памяти: процессы почти всегда разделяют сегменты с другими процессами. В этом со-
стояло ее существенное отличие от систем типа UNIX, которые обычно разделяют толь-
ко реентерабельные программные модули между процессами.
4.2.5. Страничное распределение памяти
В этом способе все фрагменты (части) задачи имеют одинаковый размер и длину,
кратную степени двойки. Вследствие этого, операции сложения можно заменить опера-
циями слияния, что существенно уменьшает вычислительную нагрузку. Одинаковые
части задачи называют страницами и говорят, что память разбивается на физические
страницы, а программа - на виртуальные страницы. Часть виртуальных страниц задачи
может размещаться в оперативной памяти, а часть - во внешней. Обычно место во внеш-
ней памяти, в качестве которой в абсолютном большинстве случаев выступают жесткие
диски, называют файломподкачки или страничнымфайлом (paging file). Иногда этот