Файл: А. В. Гордеев А. Ю. Молчанов системное программное обеспечение электронный вариант книги издательства Питер СанктПетербург Челябинск юургу каф. Автоматика и управление 2002 2 Предисловие Настоящий учебник.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.01.2024
Просмотров: 1011
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Разделы с фиксированными границами
Разбиение всего объёма оперативной памяти на несколько разделов может осуществляться единовременно (то есть в процессе генерации варианта ОС, кото- рый потом и эксплуатируется) или по мере необходимости оператором системы.
Однако и во втором случае при выполнении разбиения памяти на разделы вычис- лительная система более ни для каких целей в этот момент не используется.
1
Partition, region – раздел.
83
Пример разбиения памяти на несколько разделов приведен на рис. 2.6.
Рис. 2.6. Распределение памяти разделами с фиксированными границами
В каждом разделе в каждый момент времени может располагаться по одной программе (задаче). В этом случае по отношению к каждому разделу можно при- менить все те методы создания программ, которые используются для однопро- граммных систем. Возможно использование оверлейных структур, что позволяет создавать большие сложные программы и в то же время поддерживать коэффици- ент мультипрограммирования
1
(под коэффициентом мультипрограммирования (
µ)
понимают количество параллельно выполняемых программ) на должном уровне.
Первые мультипрограммные ОС строились по этой схеме. Использовалась эта схе- ма и много лет спустя при создании недорогих вычислительных систем, ибо она является несложной и обеспечивает возможность параллельного выполнения про- грамм. Иногда в некотором разделе размещалось по несколько небольших про- грамм, которые постоянно в нем и находились. Такие программы назывались ОЗУ–
резидентными (или просто – резидентными). Они же используются и в современ-
1
Обычно на практике для загрузки центрального процессора до уровня 90 % необходимо, чтобы коэффициент муль- типрограммирования был не менее 4-5. А для того, чтобы наиболее полно использовать и остальные ресурсы систе- мы, желательно иметь
µ на уровне 10-15.
Ядро операционной системы
Транзитная область ОС
Задача А
Неиспользуемая область
Задача В
Неиспользуемая область
Задача С
Неиспользуемая область
Раздел №0
Раздел №1
Раздел №2
Раздел №3
84
ных встроенных системах; правда, для них характерно, что все программы являют- ся резидентными и внешняя память во время работы вычислительного оборудова- ния не используется.
При небольшом объёме памяти и, следовательно, небольшом количестве раз- делов увеличить количество параллельно выполняемых приложений (особенно ко- гда эти приложения интерактивны и во время своей работы они фактически не ис- пользуют процессорное время, а в основном ожидают операций ввода/вывода)
можно за счёт своппинга (swapping). При своппинге задача может быть целиком выгружена на магнитный диск (перемещена во внешнюю память), а на её место за- гружается либо более привилегированная, либо просто готовая к выполнению дру- гая задача, находившаяся на диске в приостановленном состоянии. При своппинге из основной памяти во внешнюю (и обратно) перемещается вся программа, а не её
отдельная часть.
Серьезная проблема, которая возникает при организации мультипрограммного режима работы вычислительной системы, – это защита как самой ОС от ошибок и преднамеренного вмешательства задач в её работу, так и самих задач друг от друга.
В самом деле, программа может обращаться к любым ячейкам в пределах сво- его виртуального адресного пространства. Если система отображения памяти не содержит ошибок и в самой программе их тоже нет, то возникать ошибок при вы- полнении программы не должно. Однако в случае ошибок адресации, что не так уж и редко случается, исполняющаяся программа может начать «обработку» чужих данных или кодов с непредсказуемыми последствиями. Одной из простейших, но достаточно сильных мер является введение регистров защиты памяти. В эти реги- стры ОС заносит граничные значения области памяти раздела текущей исполняю- щейся задачи. При нарушении адресации возникает прерывание и управление пе- редаётся супервизору ОС. Обращения к ОС за необходимыми сервисами осущест- вляются не напрямую, а через команды программных прерываний, что обеспечива- ет передачу управления только в предопределенные входные точки кода ОС, и в системном режиме работы процессора, при котором регистры защиты памяти иг-
85
норируются. Таким образом, выполнение функции защиты требует введения спе- циальных аппаратных механизмов, используемых операционной системой.
Основным недостатком такого способа распределения памяти является нали- чие порой достаточно большого объёма неиспользуемой памяти (см. рис. 2.6). Не- используемая память может быть в каждом из разделов. Поскольку разделов не- сколько, то и неиспользуемых областей получается несколько, поэтому такие поте- ри стали называть фрагментацией памяти. В отдельных разделах потери памяти могут быть очень значительными, однако использовать фрагменты свободной па- мяти при таком способе распределения не представляется возможным. Желание разработчиков сократить столь значительные потери привело их к следующим двум решениям:
♦ выделять раздел ровно такого объёма, который нужен под текущую задачу;
♦ размещать задачу не в одной непрерывной области памяти, а в нескольких областях.
Второе решение реализовалось в нескольких способах организации виртуаль- ной памяти. Мы их обсудим в следующем разделе, а сейчас кратко рассмотрим первое решение.
Разделы с подвижными границами
Чтобы избавиться от фрагментации, можно попробовать размещать в опера- тивной памяти задачи плотно, одну за другой, выделяя ровно столько памяти,
сколько задача требует. Одной из первых ОС, реализовавшей такой способ распре- деления памяти, была OS MVT
1
. Специальный планировщик (диспетчер памяти)
ведет список адресов свободной оперативной памяти. При появлении новой задачи диспетчер памяти просматривает этот список и выделяет для задачи раздел, объём которого либо равен необходимому, либо чуть больше, если память выделяется не ячейками, а некими дискретными единицами. При этом модифицируется список свободной памяти. При освобождении раздела диспетчер памяти пытается объеди- нить освобождающийся раздел с одним из свободных участков, если таковой явля- ется смежным.
86
При этом список свободных участков может быть упорядочен либо по адре- сам, либо по объёму. Выделение памяти под новый раздел может осуществляться одним из трех способов:
♦ первый подходящий участок;
♦ самый подходящий участок;
♦ самый неподходящий участок.
В первом случае список свободных областей упорядочивается по адресам (на- пример, по возрастанию адресов). Диспетчер памяти просматривает этот список и выделяет задаче раздел в той области, которая первой подойдет по объёму. В этом случае, если такой фрагмент имеется, то в среднем необходимо просмотреть поло- вину списка. При освобождении раздела также необходимо просмотреть половину списка. Правило «первый подходящий» приводит к тому, что память для неболь- ших задач преимущественно будет выделяться в области младших адресов и, сле- довательно, это будет увеличивать вероятность того, что в области старших адре- сов будут образовываться фрагменты достаточно большого объёма.
Способ «самый подходящий» предполагает, что список свободных областей упорядочен по возрастанию объёма этих фрагментов. В этом случае при просмотре списка для нового раздела будет использован фрагмент свободной памяти, объём которой наиболее точно соответствует требуемому. Требуемый раздел будет опре- деляться по-прежнему в результате просмотра в среднем половины списка. Однако оставшийся фрагмент оказывается настолько малым, что в нём уже вряд ли удастся разместить какой-либо ещё раздел и при этом этот фрагмент попадет в самое нача- ло списка. Поэтому в целом такую дисциплину нельзя назвать эффективной.
Как ни странно, самым эффективным правилом является последнее, по кото- рому для нового раздела выделяется «самый неподходящий» фрагмент свободной памяти. Для этой дисциплины список свободных областей упорядочивается по убыванию объёма свободного фрагмента. Очевидно, что если есть такой фрагмент памяти, то он сразу же и будет найден, и поскольку этот фрагмент является самым
1
MVT (multiprogramming with a variable number of tasks) – мультипрограммирование с переменным числом задач.
Эта ОС была одной из самых распространённых при эксплуатировании больших ЭВМ класса IBM 360 (370).
87
большим, то, скорее всего, после выделения из него раздела памяти для задачи ос- тавшаяся область памяти ещё сможет быть использована в дальнейшем.
Однако очевидно, что при любой дисциплине обслуживания, по которой рабо- тает диспетчер памяти, из-за того, что задачи появляются и завершаются в произ- вольные моменты времени и при этом они имеют разные объёмы, то в памяти все- гда будет наблюдаться сильная фрагментация. При этом возможны ситуации, когда из-за сильной фрагментации памяти диспетчер задач не сможет образовать новый раздел, хотя суммарный объём свободных областей будет больше, чем необходимо для задачи. В этой ситуации возможно организовать так называемое «уплотнение
памяти». Для уплотнения памяти все вычисления приостанавливаются, и диспет- чер памяти корректирует свои списки, перемещая разделы в начало памяти (или,
наоборот, в область старших адресов). При определении физических адресов зада- чи будут участвовать новые значения базовых регистров, с помощью которых и осуществляется преобразование виртуальных адресов в физические. Недостатком этого решения является потеря времени на уплотнение и, что самое главное, не- возможность при этом выполнять сами вычислительные процессы.
Данный способ распределения памяти, тем не менее, применялся достаточно длительное время в нескольких операционных системах, поскольку в нем для задач выделяется непрерывное адресное пространство, а это упрощает создание систем программирования и их работу.
Сегментная, страничная и сегментно-
страничная организация памяти
Методы распределения памяти, при которых задаче уже может не предостав- ляться сплошная (непрерывная) область памяти, называют разрывными. Идея вы- делять память задаче не одной сплошной областью, а фрагментами требует для своей реализации соответствующей аппаратной поддержки – нужно иметь относи- тельную адресацию. Если указывать адрес начала текущего фрагмента программы и величину смещения относительно этого начального адреса, то можно указать не- обходимую нам переменную или команду. Таким образом, виртуальный адрес
88
можно представить состоящим из двух полей. Первое поле будет указывать часть программы (с которой сейчас осуществляется работа) для определения местополо- жения этой части в памяти, а второе поле виртуального адреса позволит найти нужную нам ячейку относительно найденного адреса. Программист может либо самостоятельно разбивать программу на фрагменты, либо автоматизировать эту за- дачу и возложить её на систему программирования.
Сегментный способ организации виртуальной памяти
Первым среди разрывных методов распределения памяти был сегментный.
Для этого метода программу необходимо разбивать на части и уже каждой такой части выделять физическую память. Естественным способом разбиения программы на части является разбиение её на логические элементы – так называемые сегмен- ты. В принципе каждый программный модуль (или их совокупность, если мы того пожелаем) может быть воспринят как отдельный сегмент, и вся программа тогда будет представлять собой множество сегментов. Каждый сегмент размещается в памяти как до определенной степени самостоятельная единица. Логически обра- щение к элементам программы в этом случае будет представляться как указание имени сегмента и смещения относительно начала этого сегмента. Физически имя
(или порядковый номер) сегмента будет соответствовать некоторому адресу, с ко- торого этот сегмент начинается при его размещении в памяти, и смещение должно прибавляться к этому базовому адресу.
Преобразование имени сегмента в его порядковый номер осуществит система программирования, а операционная система будет размещать сегменты в память и для каждого сегмента получит информацию о его начале. Таким образом, вирту- альный адрес для этого способа будет состоять из двух полей – номер сегмента и смещение относительно начала сегмента. Соответствующая иллюстрация приведе- на на рис.2.7. На этом рисунке изображен случай обращения к ячейке, виртуальный адрес которой равен сегменту с номером 11 и смещением от начала этого сегмента,
равным 612. Как мы видим, операционная система разместила данный сегмент в памяти, начиная с ячейки с номером 19 700.
89
Каждый сегмент, размещаемый в памяти, имеет соответствующую информа- ционную структуру, часто называемую дескриптором сегмента. Именно операци- онная система строит для каждого исполняемого процесса соответствующую таб- лицу дескрипторов сегментов и при размещении каждого из сегментов в оператив- ной или внешней памяти в дескрипторе отмечает его текущее местоположение.
Рис. 2.7. Сегментный способ организации виртуальной памяти
Если сегмент задачи в данный момент находится в оперативной памяти, то об этом делается пометка в дескрипторе. Как правило, для этого используется «бит
присутствия» (present). В этом случае в поле «адрес» диспетчер памяти за- писывает адрес физической памяти, с которого сегмент начинается, а в поле «дли- на сегмента» (limit) указывается количество адресуемых ячеек памяти. Это поле используется не только для того, чтобы размещать сегменты без наложения один на другой, но и для того, чтобы проконтролировать, не обращается ли код испол- няющейся задачи за пределы текущего сегмента. В случае превышения длины сег- мента вследствие ошибок программирования мы можем говорить о нарушении ад- ресации и с помощью введения специальных аппаратных средств генерировать сигналы прерывания, которые позволят фиксировать (обнаруживать) такого рода ошибки.
Регистр таблицы
сегментов (таблицы
дескрипторов сегментов)
31 500
11
612
+
Сегмент №11
19 700
23 312
Виртуальный адрес
S(Segment) D(Destination)
Таблица дескрипторов текущей задачи
Адрес начала
сегмента
Длина
сегмента
Права
доступа
1
19 700
1 300
R-X
+
90
Если бит present в дескрипторе указывает, что сейчас этот сегмент находится не в оперативной, а во внешней памяти (например, на винчестере), то названные поля адреса и длины используются для указания адреса сегмента в координатах внешней памяти. Помимо информации о местоположении сегмента, в дескрипторе сегмента, как правило, содержатся данные о его типе (сегмент кода или сегмент данных), правах доступа к этому сегменту (можно или нельзя его модифицировать,
предоставлять другой задаче), отметка об обращениях к данному сегменту (инфор- мация о том, как часто или как давно/недавно этот сегмент используется или не ис- пользуется, на основании которой можно принять решение о том, чтобы предоста- вить место, занимаемое текущим сегментом, другому сегменту).
При передаче управления следующей задаче ОС должна занести в соответст- вующий регистр адрес таблицы дескрипторов сегментов этой задачи. Сама табли-
ца дескрипторов сегментов, в свою очередь, также представляет собой сегмент данных, который обрабатывается диспетчером памяти операционной системы.
При таком подходе появляется возможность размещать в оперативной памяти не все сегменты задачи, а только те, с которыми в настоящий момент происходит работа. С одной стороны, становится возможным, чтобы общий объём виртуально- го адресного пространства задачи превосходил объём физической памяти компью- тера, на котором эта задача будет выполняться. С другой стороны, даже если по- требности в памяти не превосходят имеющуюся физическую память, появляется возможность размещать в памяти как можно больше задач. А увеличение коэффи-
циента мультипрограммирования
µ, как мы знаем, позволяет увеличить загрузку системы и более эффективно использовать ресурсы вычислительной системы. Оче- видно, однако, что увеличивать количество задач можно только до определенного предела, ибо если в памяти не будет хватать места для часто используемых сегмен- тов, то производительность системы резко упадет. Ведь сегмент, который сейчас находится вне оперативной памяти, для участия в вычислениях должен быть пере- мещен в оперативную память. При этом если в памяти есть свободное пространст- во, то необходимо всего лишь найти его во внешней памяти и загрузить в опера- тивную память. А если свободного места сейчас нет, то необходимо будет принять
91
решение – на место какого из ныне присутствующих сегментов будет загружаться требуемый.
Итак, если требуемого сегмента в оперативной памяти нет, то возникает пре- рывание и управление передаётся через диспетчер памяти программе загрузки сег- мента. Пока происходит поиск сегмента во внешней памяти и загрузка его в опера- тивную, диспетчер памяти определяет подходящее для сегмента место. Возможно,
что свободного места нет, и тогда принимается решение о выгрузке какого-нибудь сегмента и его перемещение во внешнюю память. Если при этом ещё остается вре- мя, то процессор передаётся другой готовой к выполнению задаче. После загрузки необходимого сегмента процессор вновь передаётся задаче, вызвавшей прерывание из-за отсутствия сегмента. Всякий раз при считывании сегмента в оперативную память в таблице дескрипторов сегментов необходимо установить адрес начала сегмента и признак присутствия сегмента.
При поиске свободного места используется одна из вышеперечисленных дис- циплин работы диспетчера памяти (применяются правила «первого подходящего»
и «самого неподходящего» фрагментов). Если свободного фрагмента памяти дос- таточного объёма сейчас нет, но тем не менее сумма этих свободных фрагментов превышает требования по памяти для нового сегмента, то в принципе может быть применено «уплотнение памяти», о котором мы уже говорили в подразделе «Раз- делы с фиксированными границами» при рассмотрении динамического способа разбиения памяти на разделы.
В идеальном случае размер сегмента должен быть достаточно малым, чтобы его можно было разместить в случайно освобождающихся фрагментах оператив- ной памяти, но достаточно большим, чтобы содержать логически законченную часть программы с тем, чтобы минимизировать межсегментные обращения.
Для решения проблемы замещения (определения того сегмента, который дол- жен быть либо перемещен во внешнюю память, либо просто замещен новым) ис- пользуются следующие дисциплины
1
:
1
Их называют «дисциплинами замещения».
92
♦ правило FIFO (first in – first out, что означает: «первый пришедший первым и выбывает»);
♦ правило LRU (least recently used, что означает «последний из недавно ис- пользованных» или, иначе говоря, «дольше всего неиспользуемый»);
♦ правило LFU (least frequently used, что означает: «используемый реже всех остальных»);
♦ случайный (random) выбор сегмента.
Первая и последняя дисциплины являются самыми простыми в реализации, но они не учитывают, насколько часто используется тот или иной сегмент и, следова- тельно, диспетчер памяти может выгрузить или расформировать тот сегмент, к ко- торому в самом ближайшем будущем будет обращение. Безусловно, достоверной информации о том, какой из сегментов потребуется в ближайшем будущем, в об- щем случае иметь нельзя, но вероятность ошибки для этих дисциплин многократно выше, чем у второй и третьей дисциплины, которые учитывают информацию об использовании сегментов.
Алгоритм FIFO ассоциирует с каждым сегментом время, когда он был поме- щён в память. Для замещения выбирается наиболее старый сегмент. Учет времени необязателен, когда все сегменты в памяти связаны в FIFO-очередь и каждый по- мещаемый в память сегмент добавляется в хвост этой очерёди. Алгоритм учитыва- ет только время нахождения сегмента в памяти, но не учитывает фактическое ис- пользование сегментов. Например, первые загруженные сегменты программы мо- гут содержать переменные, используемые на протяжении работы всей программы.
Это приводит к немедленному возвращению к только что замещенному сегменту.
Для реализации дисциплин LRU и LFU необходимо, чтобы процессор имел дополнительные аппаратные средства. Минимальные требования – достаточно,
чтобы при обращении к дескриптору сегмента для получения физического адреса,
с которого сегмент начинает располагаться в памяти, соответствующий бит обра- щения менял свое значение (скажем, с нулевого, которое установила ОС, в единич- ное). Тогда диспетчер памяти может время от времени просматривать таблицы де- скрипторов исполняющихся задач и собирать для соответствующей обработки ста-
Разбиение всего объёма оперативной памяти на несколько разделов может осуществляться единовременно (то есть в процессе генерации варианта ОС, кото- рый потом и эксплуатируется) или по мере необходимости оператором системы.
Однако и во втором случае при выполнении разбиения памяти на разделы вычис- лительная система более ни для каких целей в этот момент не используется.
1
Partition, region – раздел.
83
Пример разбиения памяти на несколько разделов приведен на рис. 2.6.
Рис. 2.6. Распределение памяти разделами с фиксированными границами
В каждом разделе в каждый момент времени может располагаться по одной программе (задаче). В этом случае по отношению к каждому разделу можно при- менить все те методы создания программ, которые используются для однопро- граммных систем. Возможно использование оверлейных структур, что позволяет создавать большие сложные программы и в то же время поддерживать коэффици- ент мультипрограммирования
1
(под коэффициентом мультипрограммирования (
µ)
понимают количество параллельно выполняемых программ) на должном уровне.
Первые мультипрограммные ОС строились по этой схеме. Использовалась эта схе- ма и много лет спустя при создании недорогих вычислительных систем, ибо она является несложной и обеспечивает возможность параллельного выполнения про- грамм. Иногда в некотором разделе размещалось по несколько небольших про- грамм, которые постоянно в нем и находились. Такие программы назывались ОЗУ–
резидентными (или просто – резидентными). Они же используются и в современ-
1
Обычно на практике для загрузки центрального процессора до уровня 90 % необходимо, чтобы коэффициент муль- типрограммирования был не менее 4-5. А для того, чтобы наиболее полно использовать и остальные ресурсы систе- мы, желательно иметь
µ на уровне 10-15.
Ядро операционной системы
Транзитная область ОС
Задача А
Неиспользуемая область
Задача В
Неиспользуемая область
Задача С
Неиспользуемая область
Раздел №0
Раздел №1
Раздел №2
Раздел №3
84
ных встроенных системах; правда, для них характерно, что все программы являют- ся резидентными и внешняя память во время работы вычислительного оборудова- ния не используется.
При небольшом объёме памяти и, следовательно, небольшом количестве раз- делов увеличить количество параллельно выполняемых приложений (особенно ко- гда эти приложения интерактивны и во время своей работы они фактически не ис- пользуют процессорное время, а в основном ожидают операций ввода/вывода)
можно за счёт своппинга (swapping). При своппинге задача может быть целиком выгружена на магнитный диск (перемещена во внешнюю память), а на её место за- гружается либо более привилегированная, либо просто готовая к выполнению дру- гая задача, находившаяся на диске в приостановленном состоянии. При своппинге из основной памяти во внешнюю (и обратно) перемещается вся программа, а не её
отдельная часть.
Серьезная проблема, которая возникает при организации мультипрограммного режима работы вычислительной системы, – это защита как самой ОС от ошибок и преднамеренного вмешательства задач в её работу, так и самих задач друг от друга.
В самом деле, программа может обращаться к любым ячейкам в пределах сво- его виртуального адресного пространства. Если система отображения памяти не содержит ошибок и в самой программе их тоже нет, то возникать ошибок при вы- полнении программы не должно. Однако в случае ошибок адресации, что не так уж и редко случается, исполняющаяся программа может начать «обработку» чужих данных или кодов с непредсказуемыми последствиями. Одной из простейших, но достаточно сильных мер является введение регистров защиты памяти. В эти реги- стры ОС заносит граничные значения области памяти раздела текущей исполняю- щейся задачи. При нарушении адресации возникает прерывание и управление пе- редаётся супервизору ОС. Обращения к ОС за необходимыми сервисами осущест- вляются не напрямую, а через команды программных прерываний, что обеспечива- ет передачу управления только в предопределенные входные точки кода ОС, и в системном режиме работы процессора, при котором регистры защиты памяти иг-
85
норируются. Таким образом, выполнение функции защиты требует введения спе- циальных аппаратных механизмов, используемых операционной системой.
Основным недостатком такого способа распределения памяти является нали- чие порой достаточно большого объёма неиспользуемой памяти (см. рис. 2.6). Не- используемая память может быть в каждом из разделов. Поскольку разделов не- сколько, то и неиспользуемых областей получается несколько, поэтому такие поте- ри стали называть фрагментацией памяти. В отдельных разделах потери памяти могут быть очень значительными, однако использовать фрагменты свободной па- мяти при таком способе распределения не представляется возможным. Желание разработчиков сократить столь значительные потери привело их к следующим двум решениям:
♦ выделять раздел ровно такого объёма, который нужен под текущую задачу;
♦ размещать задачу не в одной непрерывной области памяти, а в нескольких областях.
Второе решение реализовалось в нескольких способах организации виртуаль- ной памяти. Мы их обсудим в следующем разделе, а сейчас кратко рассмотрим первое решение.
Разделы с подвижными границами
Чтобы избавиться от фрагментации, можно попробовать размещать в опера- тивной памяти задачи плотно, одну за другой, выделяя ровно столько памяти,
сколько задача требует. Одной из первых ОС, реализовавшей такой способ распре- деления памяти, была OS MVT
1
. Специальный планировщик (диспетчер памяти)
ведет список адресов свободной оперативной памяти. При появлении новой задачи диспетчер памяти просматривает этот список и выделяет для задачи раздел, объём которого либо равен необходимому, либо чуть больше, если память выделяется не ячейками, а некими дискретными единицами. При этом модифицируется список свободной памяти. При освобождении раздела диспетчер памяти пытается объеди- нить освобождающийся раздел с одним из свободных участков, если таковой явля- ется смежным.
86
При этом список свободных участков может быть упорядочен либо по адре- сам, либо по объёму. Выделение памяти под новый раздел может осуществляться одним из трех способов:
♦ первый подходящий участок;
♦ самый подходящий участок;
♦ самый неподходящий участок.
В первом случае список свободных областей упорядочивается по адресам (на- пример, по возрастанию адресов). Диспетчер памяти просматривает этот список и выделяет задаче раздел в той области, которая первой подойдет по объёму. В этом случае, если такой фрагмент имеется, то в среднем необходимо просмотреть поло- вину списка. При освобождении раздела также необходимо просмотреть половину списка. Правило «первый подходящий» приводит к тому, что память для неболь- ших задач преимущественно будет выделяться в области младших адресов и, сле- довательно, это будет увеличивать вероятность того, что в области старших адре- сов будут образовываться фрагменты достаточно большого объёма.
Способ «самый подходящий» предполагает, что список свободных областей упорядочен по возрастанию объёма этих фрагментов. В этом случае при просмотре списка для нового раздела будет использован фрагмент свободной памяти, объём которой наиболее точно соответствует требуемому. Требуемый раздел будет опре- деляться по-прежнему в результате просмотра в среднем половины списка. Однако оставшийся фрагмент оказывается настолько малым, что в нём уже вряд ли удастся разместить какой-либо ещё раздел и при этом этот фрагмент попадет в самое нача- ло списка. Поэтому в целом такую дисциплину нельзя назвать эффективной.
Как ни странно, самым эффективным правилом является последнее, по кото- рому для нового раздела выделяется «самый неподходящий» фрагмент свободной памяти. Для этой дисциплины список свободных областей упорядочивается по убыванию объёма свободного фрагмента. Очевидно, что если есть такой фрагмент памяти, то он сразу же и будет найден, и поскольку этот фрагмент является самым
1
MVT (multiprogramming with a variable number of tasks) – мультипрограммирование с переменным числом задач.
Эта ОС была одной из самых распространённых при эксплуатировании больших ЭВМ класса IBM 360 (370).
87
большим, то, скорее всего, после выделения из него раздела памяти для задачи ос- тавшаяся область памяти ещё сможет быть использована в дальнейшем.
Однако очевидно, что при любой дисциплине обслуживания, по которой рабо- тает диспетчер памяти, из-за того, что задачи появляются и завершаются в произ- вольные моменты времени и при этом они имеют разные объёмы, то в памяти все- гда будет наблюдаться сильная фрагментация. При этом возможны ситуации, когда из-за сильной фрагментации памяти диспетчер задач не сможет образовать новый раздел, хотя суммарный объём свободных областей будет больше, чем необходимо для задачи. В этой ситуации возможно организовать так называемое «уплотнение
памяти». Для уплотнения памяти все вычисления приостанавливаются, и диспет- чер памяти корректирует свои списки, перемещая разделы в начало памяти (или,
наоборот, в область старших адресов). При определении физических адресов зада- чи будут участвовать новые значения базовых регистров, с помощью которых и осуществляется преобразование виртуальных адресов в физические. Недостатком этого решения является потеря времени на уплотнение и, что самое главное, не- возможность при этом выполнять сами вычислительные процессы.
Данный способ распределения памяти, тем не менее, применялся достаточно длительное время в нескольких операционных системах, поскольку в нем для задач выделяется непрерывное адресное пространство, а это упрощает создание систем программирования и их работу.
Сегментная, страничная и сегментно-
страничная организация памяти
Методы распределения памяти, при которых задаче уже может не предостав- ляться сплошная (непрерывная) область памяти, называют разрывными. Идея вы- делять память задаче не одной сплошной областью, а фрагментами требует для своей реализации соответствующей аппаратной поддержки – нужно иметь относи- тельную адресацию. Если указывать адрес начала текущего фрагмента программы и величину смещения относительно этого начального адреса, то можно указать не- обходимую нам переменную или команду. Таким образом, виртуальный адрес
88
можно представить состоящим из двух полей. Первое поле будет указывать часть программы (с которой сейчас осуществляется работа) для определения местополо- жения этой части в памяти, а второе поле виртуального адреса позволит найти нужную нам ячейку относительно найденного адреса. Программист может либо самостоятельно разбивать программу на фрагменты, либо автоматизировать эту за- дачу и возложить её на систему программирования.
Сегментный способ организации виртуальной памяти
Первым среди разрывных методов распределения памяти был сегментный.
Для этого метода программу необходимо разбивать на части и уже каждой такой части выделять физическую память. Естественным способом разбиения программы на части является разбиение её на логические элементы – так называемые сегмен- ты. В принципе каждый программный модуль (или их совокупность, если мы того пожелаем) может быть воспринят как отдельный сегмент, и вся программа тогда будет представлять собой множество сегментов. Каждый сегмент размещается в памяти как до определенной степени самостоятельная единица. Логически обра- щение к элементам программы в этом случае будет представляться как указание имени сегмента и смещения относительно начала этого сегмента. Физически имя
(или порядковый номер) сегмента будет соответствовать некоторому адресу, с ко- торого этот сегмент начинается при его размещении в памяти, и смещение должно прибавляться к этому базовому адресу.
Преобразование имени сегмента в его порядковый номер осуществит система программирования, а операционная система будет размещать сегменты в память и для каждого сегмента получит информацию о его начале. Таким образом, вирту- альный адрес для этого способа будет состоять из двух полей – номер сегмента и смещение относительно начала сегмента. Соответствующая иллюстрация приведе- на на рис.2.7. На этом рисунке изображен случай обращения к ячейке, виртуальный адрес которой равен сегменту с номером 11 и смещением от начала этого сегмента,
равным 612. Как мы видим, операционная система разместила данный сегмент в памяти, начиная с ячейки с номером 19 700.
89
Каждый сегмент, размещаемый в памяти, имеет соответствующую информа- ционную структуру, часто называемую дескриптором сегмента. Именно операци- онная система строит для каждого исполняемого процесса соответствующую таб- лицу дескрипторов сегментов и при размещении каждого из сегментов в оператив- ной или внешней памяти в дескрипторе отмечает его текущее местоположение.
Рис. 2.7. Сегментный способ организации виртуальной памяти
Если сегмент задачи в данный момент находится в оперативной памяти, то об этом делается пометка в дескрипторе. Как правило, для этого используется «бит
присутствия» (present). В этом случае в поле «адрес» диспетчер памяти за- писывает адрес физической памяти, с которого сегмент начинается, а в поле «дли- на сегмента» (limit) указывается количество адресуемых ячеек памяти. Это поле используется не только для того, чтобы размещать сегменты без наложения один на другой, но и для того, чтобы проконтролировать, не обращается ли код испол- няющейся задачи за пределы текущего сегмента. В случае превышения длины сег- мента вследствие ошибок программирования мы можем говорить о нарушении ад- ресации и с помощью введения специальных аппаратных средств генерировать сигналы прерывания, которые позволят фиксировать (обнаруживать) такого рода ошибки.
Регистр таблицы
сегментов (таблицы
дескрипторов сегментов)
31 500
11
612
+
Сегмент №11
19 700
23 312
Виртуальный адрес
S(Segment) D(Destination)
Таблица дескрипторов текущей задачи
Адрес начала
сегмента
Длина
сегмента
Права
доступа
1
19 700
1 300
R-X
+
90
Если бит present в дескрипторе указывает, что сейчас этот сегмент находится не в оперативной, а во внешней памяти (например, на винчестере), то названные поля адреса и длины используются для указания адреса сегмента в координатах внешней памяти. Помимо информации о местоположении сегмента, в дескрипторе сегмента, как правило, содержатся данные о его типе (сегмент кода или сегмент данных), правах доступа к этому сегменту (можно или нельзя его модифицировать,
предоставлять другой задаче), отметка об обращениях к данному сегменту (инфор- мация о том, как часто или как давно/недавно этот сегмент используется или не ис- пользуется, на основании которой можно принять решение о том, чтобы предоста- вить место, занимаемое текущим сегментом, другому сегменту).
При передаче управления следующей задаче ОС должна занести в соответст- вующий регистр адрес таблицы дескрипторов сегментов этой задачи. Сама табли-
ца дескрипторов сегментов, в свою очередь, также представляет собой сегмент данных, который обрабатывается диспетчером памяти операционной системы.
При таком подходе появляется возможность размещать в оперативной памяти не все сегменты задачи, а только те, с которыми в настоящий момент происходит работа. С одной стороны, становится возможным, чтобы общий объём виртуально- го адресного пространства задачи превосходил объём физической памяти компью- тера, на котором эта задача будет выполняться. С другой стороны, даже если по- требности в памяти не превосходят имеющуюся физическую память, появляется возможность размещать в памяти как можно больше задач. А увеличение коэффи-
циента мультипрограммирования
µ, как мы знаем, позволяет увеличить загрузку системы и более эффективно использовать ресурсы вычислительной системы. Оче- видно, однако, что увеличивать количество задач можно только до определенного предела, ибо если в памяти не будет хватать места для часто используемых сегмен- тов, то производительность системы резко упадет. Ведь сегмент, который сейчас находится вне оперативной памяти, для участия в вычислениях должен быть пере- мещен в оперативную память. При этом если в памяти есть свободное пространст- во, то необходимо всего лишь найти его во внешней памяти и загрузить в опера- тивную память. А если свободного места сейчас нет, то необходимо будет принять
91
решение – на место какого из ныне присутствующих сегментов будет загружаться требуемый.
Итак, если требуемого сегмента в оперативной памяти нет, то возникает пре- рывание и управление передаётся через диспетчер памяти программе загрузки сег- мента. Пока происходит поиск сегмента во внешней памяти и загрузка его в опера- тивную, диспетчер памяти определяет подходящее для сегмента место. Возможно,
что свободного места нет, и тогда принимается решение о выгрузке какого-нибудь сегмента и его перемещение во внешнюю память. Если при этом ещё остается вре- мя, то процессор передаётся другой готовой к выполнению задаче. После загрузки необходимого сегмента процессор вновь передаётся задаче, вызвавшей прерывание из-за отсутствия сегмента. Всякий раз при считывании сегмента в оперативную память в таблице дескрипторов сегментов необходимо установить адрес начала сегмента и признак присутствия сегмента.
При поиске свободного места используется одна из вышеперечисленных дис- циплин работы диспетчера памяти (применяются правила «первого подходящего»
и «самого неподходящего» фрагментов). Если свободного фрагмента памяти дос- таточного объёма сейчас нет, но тем не менее сумма этих свободных фрагментов превышает требования по памяти для нового сегмента, то в принципе может быть применено «уплотнение памяти», о котором мы уже говорили в подразделе «Раз- делы с фиксированными границами» при рассмотрении динамического способа разбиения памяти на разделы.
В идеальном случае размер сегмента должен быть достаточно малым, чтобы его можно было разместить в случайно освобождающихся фрагментах оператив- ной памяти, но достаточно большим, чтобы содержать логически законченную часть программы с тем, чтобы минимизировать межсегментные обращения.
Для решения проблемы замещения (определения того сегмента, который дол- жен быть либо перемещен во внешнюю память, либо просто замещен новым) ис- пользуются следующие дисциплины
1
:
1
Их называют «дисциплинами замещения».
92
♦ правило FIFO (first in – first out, что означает: «первый пришедший первым и выбывает»);
♦ правило LRU (least recently used, что означает «последний из недавно ис- пользованных» или, иначе говоря, «дольше всего неиспользуемый»);
♦ правило LFU (least frequently used, что означает: «используемый реже всех остальных»);
♦ случайный (random) выбор сегмента.
Первая и последняя дисциплины являются самыми простыми в реализации, но они не учитывают, насколько часто используется тот или иной сегмент и, следова- тельно, диспетчер памяти может выгрузить или расформировать тот сегмент, к ко- торому в самом ближайшем будущем будет обращение. Безусловно, достоверной информации о том, какой из сегментов потребуется в ближайшем будущем, в об- щем случае иметь нельзя, но вероятность ошибки для этих дисциплин многократно выше, чем у второй и третьей дисциплины, которые учитывают информацию об использовании сегментов.
Алгоритм FIFO ассоциирует с каждым сегментом время, когда он был поме- щён в память. Для замещения выбирается наиболее старый сегмент. Учет времени необязателен, когда все сегменты в памяти связаны в FIFO-очередь и каждый по- мещаемый в память сегмент добавляется в хвост этой очерёди. Алгоритм учитыва- ет только время нахождения сегмента в памяти, но не учитывает фактическое ис- пользование сегментов. Например, первые загруженные сегменты программы мо- гут содержать переменные, используемые на протяжении работы всей программы.
Это приводит к немедленному возвращению к только что замещенному сегменту.
Для реализации дисциплин LRU и LFU необходимо, чтобы процессор имел дополнительные аппаратные средства. Минимальные требования – достаточно,
чтобы при обращении к дескриптору сегмента для получения физического адреса,
с которого сегмент начинает располагаться в памяти, соответствующий бит обра- щения менял свое значение (скажем, с нулевого, которое установила ОС, в единич- ное). Тогда диспетчер памяти может время от времени просматривать таблицы де- скрипторов исполняющихся задач и собирать для соответствующей обработки ста-