Алгоритм предварительного распределения ресурсов

Алгоритм предварительного распределения ресурсов в соответствии с первым стратегическим принципом Хавендера требует, чтобы процесс сразу же запрашивал все ресурсы, которые ему понадобятся. Система в ответ на эти запросы должна представлять ресурсы по принципу «все или ничего», т.е. если набор ресурсов, необходимый процессу, имеется, то система предоставляет процессу все эти ресурсы сразу же, так что он может продолжить свою работу. Если в данный момент времени полного набора ресурсов нет, то этому процессу придется ждать, пока они не освободятся.

3.4.3.3.3. Алгоритм распределения ресурсов с освобождением
при отказе

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

3.4.3.3.3. Алгоритм распределения с линейным упорядочением
по типам ресурсов

Алгоритм распределения ресурсов в этом случае предусматривает предварительное присвоение всем ресурсам вычислительной системы уникальных номеров.

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

3.4.3.3. Алгоритмы обхода тупиков

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

Алгоритм регулируемого распределения основан на представлении распределения ресурсов, запросов и процессов в виде ориентированного графа (орграфа) называемого графом распределения ресурсов (ГРР).

Правило Хабермана: Если граф распределения ресурсов имеет циклы, то такое распределение ресурсов по процессам может привести к образованию тупиковой ситуации.

Это правило позволяет построить следующий алгоритм распределения ресурсов:

· при поступлении очередного запроса проверить наличие свободного ресурса;

· если свободный ресурс отсутствует, то отказ, процесс блокировать, иначе сделать предварительное распределение и скорректировать ГРР;

· проверить ГРР на наличие циклов;

· если в ГРР имеются циклы, то отменить предварительное распределение, восстановить ГРР, сформировать отказ и блокировать процесс, иначе закрепить ресурс за процессом.

Алгоритм Хабермана позволяет обойти тупики, однако он сложен в реализации из-за необходимости работы с графом распределения ресурсов.

Контрольные вопросы к теме 3

1. Описать организацию управления в ОС.

2. Перечислить дисциплины обслуживания.

3. Перечислить режимы обслуживания.

4. Описать средства управления задачами на уровне внешнего планирования.

5. Дать определения понятия «контекст процесса».

6. Пояснить понятия «нить» и «процесс».

7. Назвать состав алгоритмов внутреннего планирования.

8. Охарактеризовать алгоритмы управления количеством процессов в рабочей смеси.

9. Охарактеризовать алгоритмы выбора очередности обработки.

10. Охарактеризовать алгоритмы выбора величины кванта

11. Дать определение понятий: параллельные процессы, критический ресурс, критический участок.

12. Что такое "примитивы взаимоисключения"?

13. Каковы механизмы реализации примитивов взаимоисключения?

14. Описать алгоритмы предотвращения тупиков.

15. Описать алгоритмы обхода тупиков.

Тема 4. Управление памятью в операционных системах

4.1. Понятие об организации и управлении физической памятью

В операционных системах различают два вида памяти: основная (первичная) и внешняя (вторичная).

Основная память (main storage) – оперативная память центрального процессора или ее часть, представляющее собой единое пространство памяти.

Внешняя память (external storage) – память, данные в которой доступны центральному процессору посредством операций ввода-вывода.

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

Кроме основной и внешней памяти в современных ЭВМ существует дополнительная быстродействующая память, называемая кэш-памятью.

Все три вида памяти образуют иерархию памяти вычислительной машины (рис.4.1).

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

Основная память представляет собой один из самых дорогостоящих ресурсов. Главной задачей при разработке ОС считается оптимальное использование основной памяти на основе рациональной организации и управления.

Под организацией памяти понимается то, каким образом представляется основная память.

Под управлением памятью понимается то, как используется основная память.

В ОС применяются следующие виды представления основной памяти:

- фиксированными блоками равного размера;

- фиксированными разделами неодинакового размера;

- динамическими разделами, размеры которых изменяются в ходе работы вычислительной системы.

Использование основной памяти может осуществляться следующими способами:

- размещение в памяти единовременно только одной программы пользователей;

- размещение в памяти одновременно нескольких программ пользователей;

- размещение программ пользователей в конкретном заранее заданном разделе основной памяти;

- размещение каждой программы пользователя в одном непрерывном (односвязном) пространстве основной памяти;

- размещение программы пользователя в несмежных областях оперативной памяти.

В операционных системах может применяться любая комбинация перечисленных видов представления и способов использования основной памяти ЭВМ.

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

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

- когда следует поместить новую программу в память;

- в какое место основной памяти будет размещаться очередная программа;

- как разместить очередную программу в памяти (с минимизацией потерь памяти или с максимизацией скорости размещения);

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

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

Стратегии управления памятью делятся на следующие категории: стратегии выборки; стратегии размещения; стратегии замещения.

В свою очередь стратегии выборки разделяют на две подкатегории: стратегии выборки по запросу (по требованию); стратегии упреждающей выборки.

Стратегии выборки ставят своей целью определить, когда следует “втолкнуть” очередную программу (или блок программы) или данные в основную память.

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

Стратегии замещения ставят своей целью определить, какой блок программы или данных следует вывести (“вытолкнуть”) из основной памяти, чтобы освободить место для размещения вновь поступающих программ или данных.

При реализации стратегий размещения операционные системы часто учитывают требования связного распределения памяти для программ и данных.

Связное распределение памяти – такое распределение основной памяти ЭВМ, при котором каждая программ занимает один непрерывный (связный) блок ячеек памяти.

Несвязное распределение памяти – такое распределение основной памяти ЭВМ, при котором программа пользователя разбивается на ряд блоков (сегментов, страниц), которые могут размещаться в основной памяти в участках, не обязательно соседствующих друг с другом (в несмежных участках). В этом случае обеспечивается более эффективное использование пространства основной памяти.

Эффективность той или иной стратегии размещения можно оценить с помощью коэффициента использования памяти h

(4.1)

где V_п – объем памяти, занимаемый программами пользователя; V_оп – полный объем основной памяти; V_ос – объем памяти, занимаемый операционной системой; V_{о –} объем памяти, доступный для распределения.

4.2. Методы связного распределения основной памяти
(без использования дискового пространства)

4.2.1. Связное распределение памяти для одного пользователя

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

Вся основная часть ЭВМ, не занятая программами операционной системы, выделяется программе единственного на данном отрезке времени пользователя (рис.4.2).

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

Коэффициент использования памяти вычисляется по формуле

h_с1=V_п/V_o, (4.2)

где V_п – размер программы пользователя; V_о – объем доступной для распределения основной памяти ЭВМ.

Функциями ОС являются: выделение программе необходимого пространства памяти; защита памяти; освобождение памяти.

Функция выделения памяти сводится к предоставлению программе всей доступной памяти ЭВМ.

Защита памяти в однопрограммных системах заключается в установке защиты областей памяти, занятых операционной системой, от воздействия программ пользователя. Эта функция реализуется при помощи одного регистра границы, встроенного в центральный процессор. Регистр границы содержит либо старший адрес команды, относящийся к операционной системе, либо младший адрес доступной программе основной памяти (адрес начала программы). Если программа пользователя пытается войти в область операционной системы, то вырабатывается прерывание по защите памяти, и программа аварийно завершается.

4.2.2. Связное распределение памяти при мультипрограммной
обработке

При мультипрограммной обработке в памяти компьютера размещается сразу несколько заданий. Распределение памяти между заданиями в этом случае может быть выполнено следующими способами: распределение фиксированными разделами; распределение переменными разделами; распределение со свопингом.

Распределение фиксированными разделами имеет две модификации:

а) с загрузкой программ в абсолютных адресах;

б) с загрузкой перемещаемых модулей.

При загрузке перемещаемых модулей вся оперативная память машины разбивается на некоторое количество разделов фиксированного размера (рис.4.3). Размеры разделов могут не совпадать. В каждом разделе может быть размещено только одно задание.

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

В случае загрузки перемещаемых модулей раздел, в котором будет размещено задание, либо автоматически определяется операционной системой в соответствии с реализованной в нем стратегией выбора раздела («первый подходящий», «самый подходящий», «самый неподходящий»), либо указывается операционной системе специальными командами языка управления заданиями.

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

Коэффициенты использования памяти при распределении с фиксированными разделами вычисляется по формулам:

, (4.3)

где h_{cMi –} коэффициент использования памяти i-го раздела; V_oi – размер i-го раздела; V_пi – длина программы, помещенной в i-ый раздел; N_ф – количество разделов; V_o – общий объем оперативной памяти, доступной для распределения.

Основным недостатком распределения памяти фиксированными разделами является неэффективное использование ресурсов вычислительной системы из-за возможного появления длинных очередей заданий, ожидающих освобождения конкретного раздела в то время, как остальные разделы пусты (рис.4.3).

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

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

Фрагментация памяти – появление в памяти вычислительной машины чередования занятых и незанятых (свободных) участков оперативной памяти.

Уровень фрагментации памяти можно оценить коэффициентом фрагментации K_ф, вычисляемый по формуле

,

где V_дi – размер i-ой “дыры”, т.е. i-го участка свободной памяти, ограниченного программами пользователей; N_Д – количество “дыр”, т.е. участков свободной памяти, лежащих между программами пользователей; V_o – объем оперативной памяти, доступной для распределения.

Фрагментация памяти представляет собой нарушение односвязности пространства свободной памяти ЭВМ, что приводит к снижению эффективности использования памяти.

Распределение памяти переменными разделами предназначено для повышения эффективности использования оперативной памяти ЭВМ. Суть способа распределения памяти переменными разделами состоит в том, что заданиям, когда они поступают, выделяется такой объем памяти, который им требуется, т.е. размер раздела оперативной памяти, выделяемой каждому заданию, в точности соответствует размеру этого задания. Поэтому “перерасхода” памяти, как это происходит при распределении фиксированными разделами, в данном способе не наблюдается.

Имеется две модификации способа распределения переменными разделами: распределение переменными неперемещаемыми разделами; распределение переменными перемещаемыми разделами.

При распределении памяти переменными неперемещаемыми разделами (динамическими разделами) операционная система создает две таблицы: таблицу учета распределенных областей памяти и таблицу учета свободных областей памяти (“дыр”).

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

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

При распределении памяти переменными перемещаемыми разделами операционная система осуществляет действия, называемые уплотнением памяти, состоящими в перемещении всех занятых участков к одному или другому краю основной памяти (рис.4.5в). Благодаря этому вместо большого количества небольших “дыр”, образующихся при использовании распределения переменными неперемещаемыми разделами, формируется единый (связный) участок свободной памяти. Этот процесс называют также дефрагментацией памяти.

Дефрагментация памяти, применяемая при распределении перемещаемыми разделами, имеет свои недостатки:

- требуются дополнительные затраты времени;

- во время уплотнения памяти система должна прекращать (приостанавливать) все другие работы, что зачастую может оказаться неприемлемым;

- необходимость перемещения заданий в памяти требует хранения значительного объема информации, связанной с размещением программ в памяти, что увеличивает требования к памяти со стороны ОС;

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

Распределение памяти со свопингом (от англ. swapping – подкачка) характеризуется тем, что в отличие от рассмотренных ранее способов распределения программы пользователей не остаются в основной памяти до момента их завершения. Вся память целиком на короткий период выделяется одному заданию, затем в некоторый момент времени это задание выводится (выталкивается, т.е. осуществляется “откачка”), а очередное задание вводится (вталкивается, т.е. осуществляется “подкачка”). В обычном случае каждое задание, еще до своего завершения, будет много раз перекачиваться из внешней памяти в основную и обратно. Для обеспечения свопинга во внешней памяти ОС создает один или несколько файлов подкачки, где хранятся образы оперативной памяти находящихся в работе заданий пользователей. Способ распределения памяти со свопингом применяется в простейших ОС, работающих в режиме разделения времени.

4.2.3. Стратегии размещения информации в памяти

Стратегии размещения информации в памяти предназначены для того, чтобы определить, в какое место основной памяти следует помещать поступающие программы и данные при распределении памяти неперемещаемыми разделами. Наиболее часто применяются следующие стратегии:

- размещение с выбором первого подходящего (стратегия “первый подходящий”):

- размещение с выбором наиболее подходящего (стратегия “самый подходящий”);

- алгоритм с выбором наименее подходящего (стратегия “самый неподходящий”).

Стратегия “первый подходящий ” состоит в выполнении следующих шагов:

- упорядочить таблицу свободных областей в порядке возрастания адресов;

- поместить информацию в первый встретившийся участок основной памяти размером не менее требуемого.

Стратегия “самый подходящий ” реализует следующую последовательность действий:

- упорядочить таблицу свободных областей в порядке возрастания размеров свободных областей:

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

Стратегия “самый неподходящий” выполняет следующие действия:

- упорядочить таблицу свободных областей в порядке убывания размеров областей;

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

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

4.3. Организация виртуальной памяти (с использованием дискового
пространства)

4.3.1. Основные концепции виртуальной памяти

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

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

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

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

Адреса, на которые делает ссылки выполняющийся процесс, называются виртуальными адресами. Адреса, которые реально существуют в первичной памяти, называются реальными (физическими) адресами.

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

Несмотря на то, что процессы обращаются только к виртуальным адресам, в действительности они должны работать с реальной памятью. Для установления соответствия между виртуальными и реальными адресами разработаны механизмы динамического преобразования адресов ДПА (или DAT – от англ.Dynamics Adress Transformation), обеспечивающие преобразование виртуальных адресов в реальные во время выполнения процесса. Все подобные системы обладают общим свойством – смежные адреса виртуального адресного пространства процесса не обязательно будут смежными в реальной памяти. Это свойство называют “искусственной смежностью”. Тем самым пользователь освобождается от необходимости рассматривать физическую память с ее уникальными характеристиками.

Виртуальная память строится, как правило, по двухуровневой схеме.

Первый уровень – это реальная память, в которой находятся выполняемые процессы и в которой должны размещаться данные, к которым обращаются эти процессы.

Второй уровень – это внешняя память большой емкости, например, накопители на магнитных дисках, способные хранить программы и данные, которые не могут все сразу уместиться в реальной памяти из-за ограниченности ее объема. Память второго уровня называют вторичной или внешней.

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

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

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

4.3.2. Схема прямого отображения адресов

Адреса в системе поблочного отображения являются двухкомпонентными (двумерными). Чтобы обратиться к конкретному элементу данных, программа указывает блок, в котором расположен этот элемент, и смещение элемента относительно начала блока. Виртуальный адрес n указывает при помощи упорядоченной пары (b, d), где b- номер блока, в котором размещается соответствующий элемент данных, а d – смещение относительно начального адреса этого блока.

Преобразование адреса виртуальной памяти n=(b, d) в адрес реальной памяти r осуществляется следующим образом (рис.4.6).

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

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

4.3.3. Отображения адресов при страничной организации
виртуальной памяти

Виртуальный адрес при чисто страничной организации памяти – это упорядоченная пара (p, d), где p – номер страницы в виртуальной памяти, а d – смещение в рамках страницы p. Процесс может выполняться, если его текущая страница находится в первичной памяти. Страницы переписываются из внешней памяти в первичную и размещаются в ней в блоках, называемых страничными кадрами и имеющих точно такой же размер, как у поступающих страниц. Страничные кадры начинаются в реальной памяти с адресов, кратных фиксированному размеру страниц. Поступающая страница может быть помещена в любой свободный страничный кадр.

Для обеспечения работы механизма отображения страниц формируется таблица отображения страниц, каждая строка которой содержит информацию об отображаемой странице виртуальной памяти; r – признак наличия страницы в первичной памяти (r=0 – страницы в первичной памяти нет; 1 – страница находится в первичной памяти); S – адрес страницы во внешней памяти (при r=0); p’ – номер страничного кадра в первичной памяти, где размещена виртуальная страница с номером p.

4.3.4. Отображения адресов при сегментной организации
виртуальной памяти

Виртуальный адрес при сегментной организации виртуальной памяти – это упорядоченная пара n=(s, d), где s – номер сегмента виртуальной памяти, а d – смещение в рамках этого сегмента. Процесс может выполняться только в том случае, если его текущий сегмент находится в первичной памяти, Сегменты передаются из внешней памяти в первичную целиком. Все ячейки, относящиеся к сегменту, занимают смежные адреса первичной памяти. Для размещения поступающих из внешней памяти сегментов в свободные участки первичной памяти применяются те же стратегии размещения, как и при распределении переменными неперемещаемыми разделами – “первый подходящий”, “самый подходящий”, “самый неподходящий”. Динамическое преобразование виртуальных адресов в реальные адреса осуществляется в соответствии со схемой прямого отображения.

4.3.4. Отображения адресов при странично-сегментной организации
виртуальной памяти

Системы со странично-сегментной организацией обладают достоинствами обоих способов реализации виртуальной памяти. Сегменты обычно содержат целое число страниц, причем не обязательно, чтобы все страницы сегмента находились в первичной памяти одновременно, а смежные страницы виртуальной памяти не обязательно должны оказаться смежными в первичной памяти. В системе со странично-сегментной организацией применяется трехкомпонентная (трехмерная) адресация. Виртуальный адрес n здесь определяется как упорядоченная тройка n=(s, p, d), где s – номер сегмента, p – номер страницы, а d – смещение в рамках страницы, где находится нужный элемент.

Операционная система для каждого процесса формирует, во-первых, одну таблицу сегментов процесса, и, во-вторых, таблицы страниц сегментов (по одной на каждый сегмент процесса).

Таблица сегментов процесса содержит в своих строках информацию о количестве страниц в сегменте и о начальных адресах s’ размещения таблиц страниц сегментов в первичной памяти ЭВМ.

Каждая страница таблиц сегмента содержит в своих строках информацию о начальном адресе p’ размещения в первичной памяти страничного кадра для данной страницы виртуальной памяти.

Динамическое преобразование виртуальных адресов в системах со странично-сегментной организацией отличается от преобразования по схеме наличием еще одного уровня вычисления адреса (см.рис.4.7) и появлением таблиц страниц для каждого сегмента процесса.

4.4. Управление виртуальной памятью

4.4.1. Стратегии управления виртуальной памятью

Стратегии управления виртуальной памятью, так же, как и стратегии управления физической памятью, разделяются на три категории: стратегии вталкивания, стратегии размещения и стратегии выталкивания.

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

Целью стратегий размещения является определить, в какое место первичной памяти помещать поступающую страницу или сегмент.

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

Большинство стратегий управления виртуальной памятью базируется на концепции локальности.

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

Свойство локальности проявляется как во времени, так и в пространстве.

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

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

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

4.4.2. Стратегии вталкивания (подкачки)

Для управления вталкиванием применяются следующие стратегии:

- вталкивание (подкачка) по запросу (по требованию);

- вталкивание (подкачка) с упреждением (опережением).

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

К положительным сторонам относятся:

- гарантировано, что в первичную память будут переписываться только те страницы (сегменты), которые необходимы для работы процесса;

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

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

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

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

4.4.3. Стратегии размещения

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

Для систем с сегментной организацией виртуальной памяти применяются такие же стратегии размещения, какие используются в системах распределения памяти переменными разделами (см. п.4.2), а именно: размещение с выбором первого подходящего свободного участка; размещение с выбором самого подходящего свободного участка; размещение с выбором наименее подходящего свободного участка.

4.4.4. Стратегии выталкивания

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

- выталкивание случайных страниц или сегментов;

- выталкивание первой пришедшей страницы или сегмента (FIFO);

- выталкивание дольше всего не использовавшихся страниц или сегментов (LRU – Least Recently Used);

- выталкивание наименее часто использовавшихся страниц или сегментов (LFU – Least Frequently Used);

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

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

Стратегия выталкивания первой пришедшей страницы или сегмента (FIFO-стратегия) реализует принцип «первый пришел – первый ушел». В этом случае в момент поступления каждой страницы (сегмента) в первичную память ей (ему) присваивается метка времени. Когда появляется необходимость удалить из первичной памяти какую-либо страницу (сегмент), выбирается та страница (сегмент), у которой метка времени имеет наименьшее значение.

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

Стратегия выталкивания реже всего используемых страниц или сегментов (LFU-стратегия) является одной из наиболее близких к рассмотренной выше LRU-стратегии. В соответствии с LFU-стратегией из первичной памяти выталкиваются наименее часто (наименее интенсивно) использовавшиеся к данному времени страницы или сегменты. Здесь контролируется интенсивность использования страниц (сегментов). Для этого каждой странице (сегменту) назначается счетчик, значение которого увеличивается на единицу при каждом обращении к данной странице (сегменту). LFU-стратегия, будучи интуитивно оправданной, имеет те же недостатки, что и стратегия LRU: во-первых, велика вероятность того, что из первичной памяти будут удалены страницы или сегменты, которые потребуются процессам при следующем обращении к памяти и, во-вторых, ее реализация может быть сопряжена со значительными затратами на организацию контроля интенсивности использования страниц или сегментов.

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

Поскольку желательно заменять те страницы (сегменты), которые в период нахождения в основной памяти не изменялись, реализация NRU-стратегии предусматривает введение двух аппаратных бит-признаков на страницу (сегмент):

- бит-признак b₀ обращения к странице (сегменту);

- бит-признак b₁ модификации страницы (сегмента).

Первоначально все b₀ и b₁ устанавливаются в 0. При обращении к странице (сегменту) соответствующий бит-признак b₀ устанавливается в 1. В случае изменения содержимого страницы (сегмента) соответствующий бит-признак b₁ устанавливается в 1. NRU-стратегия предусматривает существование четырех групп страниц (сегментов), показанных в табл. 4.5.

Таблица 4.5 – Группы страниц (сегментов)

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

Контрольные вопросы к теме 4

1. Описать иерархию организации памяти.

2. Перечислить и охарактеризовать методы связного распределения памяти. Где они применяются.

3. Охарактеризовать стратегии размещения при связном распределении памяти.

4. Что такое виртуальная память? Каковы свойства различных видов организации виртуальной памяти?

5. Описать способы вычисления адреса при страничной, сегментной и странично-сегментной организации виртуальной памяти.

6. Перечислить и охарактеризовать стратегии управления виртуальной памятью.

7. Сформулируйте и поясните принцип локальности.

8. Перечислить и охарактеризовать стратегии вталкивания, размещения и выталкивания.

Тема 5. Управление файлами и вводом-выводом в ОС

5.1.Методы организации данных в операционных системах

Данные – это информация, представленная в виде, пригодном для обработки автоматическими средствами при возможном участии человека.

Любые данные, подлежащие обработке, находятся на том или ином носителе.

Носитель данных – это материальный объект, предназначенный для хранения данных.

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

Источник данных – функциональное устройство, являющееся источником передаваемых данных.

Источник информации – часть коммуникационной системы, которая порождает сообщение.

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

В первом случае понятие структуры данных есть не что иное, как представление пользователя о данных вне связи с методами хранения данных.

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

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

Организация данных – это представление данных и управление данными в соответствии с определенными соглашениями.

Одна и та же структура данных может отображаться в среду хранения несколькими способами, каждый из которых будет соответствовать определенной структуре хранения. Каждая структура хранения материализуется в среде хранения в виде одного или нескольких наборов данных.

Набор данных – идентифицированная совокупность физических записей, организованная одним из установленных в системе обработки данных способов и представляющая файлы или части файлов в среде хранения.

Файл – идентифицированная совокупность экземпляров полностью описанного в конкретной программе типа данных, находящихся вне программы во внешней памяти и доступных программе посредством специальных операций.

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

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

Последовательный доступ к порции данных – доступ к порции данных, при котором операции чтения или запись порции данных, к которым осуществляется доступ, проводится после чтения или записи всех порций, расположенных до этой порции в соответствии с порядком, фиксированным для определенной совокупности порций данных.

Различают физически последовательные и логически последовательные наборы данных.

Физически последовательные наборы данных предполагают размещение составляющих в памяти сплошным массивом.

Логически последовательные наборы данных могут не иметь в памяти представления в виде сплошного массива.

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

Древовидная организация данных основана на представлении структуры данных в виде деревьев, причем каждый узел дерева является частью структуры (рис.5.2).

Методы представления древовидных структур в памяти ЭВМ могут быть разделены на две группы:

- методы физически последовательного размещения данных;

- методы логически последовательного размещения данных.

Рис.5.2.Древовидная организация данных

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

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

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

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

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

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

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

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

Основными недостатками метода прямой адресации являются:

- необходимость использования порций данных одинаковой длины;

- перед созданием набора данных необходимо выполнить подготовительные действия по разметке отведенного для него участка на носителе данных;

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

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

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

Логической единицей любого набора данных является запись.

Запись – совокупность данных, которая используется средствами системы как единое целое.

Записи могут быть фиксированной, переменной или неопределенной длины.

Запись фиксированной длины – это логическая запись, длина которой задана вне этой записи.

Запись переменной длины – логическая запись, длина которой определяется значением одного из ее полей.

Запись неопределенной длины – логическая запись, в которой отсутствует специализированное поле для описания ее длины, а длина определяется в момент обработки этой записи.

5.2. Методы доступа к данным

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

Метод прямого управления доступом к данным основан на наличии непосредственной связи между центральным процессором и внешним запоминающим устройством (см. рис. 5.6а).

На центральный процессор возлагается обязанность непосредственно управления работой устройства, что предполагает наличие в составе команд процессора специальных команд по управлению работой этого устройства (инициирование ВЗУ, проверка готовности к работе, остановка ВЗУ, запись/чтение данных и т.п.)

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

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

Независимо от принятого в системе метода управления доступ, к данным в программах пользователя может осуществляться разными методами. Наиболее распространенными в настоящее время являются два доступа к данным уз программ пользователя: доступ к данным на низком уровне; доступ к данным на высоком уровне.

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

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

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

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

Поиск по сайту: