Лекция 1. Введение в сетевые ОС (стр. 3 )

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

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

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

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

Лекция 4. Управление памятью в ОС

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

· отслеживание свободной и занятой памяти;

· выделение памяти процессам, освобождение памяти по завершении процессов, а также динамическое её перераспределение во время работы;

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

· организация преобразования адресов (совместно с АО ИВС). На большинстве современных платформ внутри ОС и приложений используются виртуальные адреса– условные адреса, присваиваемые переменным и командам программы транслятором. Совокупность виртуальных адресов процесса называется виртуальным адресным пространством (ВАП). Тем не менее для фактического считывания содержимого ячейки памяти на шину адреса должен быть выставлен физический адрес – линейный номер ячейки физической памяти при сквозной нумерации от начала ОЗУ. Задачей ОС является отображение индивидуальных ВАП всех одновременно выполняющихся процессов на общую физическую память;

· защита памяти (совместно с АО ИВС) процессов друг от друга.

Способы выполнения перечисленных функций зависят в основном от структуры ВАП. Можно выделить несколько стандартных подходов к его организации: линейное (плоское) ВАП, страничная и многоуровневая страничная организация ВАП, ВАП на основе сегментации, сегментно-страничная организация ВАП.

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

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

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

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

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

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

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

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

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

Рис. 4.1. Распределение памяти с фиксированными разделами:
с раздельными очередями (а), общей очередью (б)

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

При очевидном преимуществе – простоте реализации - данный метод имеет существенный недостаток – жесткость. С одной стороны, уровень мультипрограммности заранее ограничен числом разделов, с другой – невозможно выполнить процессы, которые не помещаются ни в один из разделов, но для которых было бы достаточно памяти нескольких разделов. Такой способ применялся в ранних мультипрограммных ОС (например, OS/360 от IBM), хотя он находит применение и на данном этапе в системах реального времени. Детерминированность вычислительного процесса систем реального времени компенсирует недостаточную гибкость данного способа управления памятью.

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

Функциями ОС, предназначенными для реализации данного метода управления памятью, являются:

· ведение таблиц свободных и занятых областей;

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

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

· корректирока таблица свободных и занятых областей после завершения процесса.

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

Рис. 4.2. Учёт использования памяти: с помощью битового массива (а);
с помощью связного списка (б)

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

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

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

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

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

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

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

5. Алгоритм «быстрый подходящий» поддерживает отдельные списки для некоторых наиболее часто запрашиваемых размеров. Например, могла бы существовать таблица, в которой первая запись указывает на начало списка свободных фрагментов размером 4 Кбайт, вторая – 8 Кбайт, третья – 12 Кбайт и т. д. Данный алгоритм находит фрагмент требуемого размера чрезвычайно быстро, но операция поиска соседей является такой же трудоемкой.

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

Лекция 5. Организация виртуальной памяти в ОС

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

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

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

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

2. Сегментная ВП предусматривает перемещение данных сегментами – частями ВАП произвольного размера, полученных с учетом смыслового значения данных.

3. Сегментно-страничная ВП использует двухуровневое деление: ВАП делится на сегменты, а затем сегменты – на страницы. Единицей перемещения данных здесь является страница.

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

Рис. 5.1. Страничное распределение памяти

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

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

Рис. 5.2. Преобразование виртуального адреса в физический
при одноуровневой страничной адресации

Страничные прерывания

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

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

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

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

· алгоритм «не использовавшая в последнее время» - применяет два статусных флага – флаг модификации и флаг обращений. При запуске процесса эти флаги для всех его страниц сбрасываются. Периодически (по таймеру) флаг обращений очищается, чтобы отличать страницы, к которым давно не происходило обращений, от часто востребованных. Когда возникает страничное прерывание, ОС проверяет все страницы и делит их на 4 категории на основании текущих значений флагов: класс 0 (не было обращений и изменений), класс 1 (не было обращений, страница изменена), класс 2 (было обращение, страница не изменена), класс 3 (произошли и обращение, и изменение). С помощью случайного поиска удаляется страница в непустом классе с наименьшим номером. Подразумевается, что лучше выгрузить измененную страницу, к которой не было обращений, по крайней мере, в течение одного тика системных часов, чем стереть часто используемую страницу. Алгоритм легок для понимания, умеренно сложен в реализации и дает производительность, которая не оптимальна, но может вполне оказаться достаточной;

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

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

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

· алгоритм «не использовавшаяся дольше всего» отличается от «не использовавшаяся в последнее время» тем, что ведется подсчет количества периодов, в течение которых не было обращения к странице, и удаляет ту, у которой это значение максимальное. Алгоритм теоретически реализуем, однако не является оптимальным в плане вычислительных затрат. Кроме того, в записи элемента таблицы страниц необходимо наличие поля, достаточного для хранения значения счетчика;

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

· алгоритм «WSClock» представляет собой совмещение подходов «часов» и «рабочего набора» (с временем старения). Перемещение осуществляется по кругу. Если флаг обращения установлен, то он сбрасывается в нуль, и происходит переход на следующую по кругу запись. Когда он сброшен, то анализируются дополнительные условия: если возраст страницы больше чем некоторое значение «рабочего набора», а страница – чистая, то на ее место загружается новая страница; если же страница «грязная», то ее нельзя немедленно стереть, так как на диске нет последней копии. Чтобы избежать переключения процессов на сохранение страницы на диск, ее запись включается в график планирования, но на данный момент «стрелка» передвигается на следующую страницу в списке. Несмотря на то что «грязная» страница может быть старше, чистая находится ближе в ряду страниц, которые можно использовать немедленно. После обхода стрелки по кругу возможны два варианта: запланированы (как минимум одна) операции записи на диск, ни одной операции записи не запланировано. В первом случае стрелка продолжает движение, отыскивая чистую страницу. Поскольку запланирована одна или больше операций записи, то со временем какая-нибудь из них будет выполнена, и соответствующая страница будет помечена как чистая. Во втором случае все страницы находятся в рабочем наборе, поэтому за недостатком дополнительной информации проще всего предъявить права на любую чистую страницу и использовать ее.

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

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

1) таблица страниц может быть слишком большой (адресное пространство 32 бита – более миллиона страниц, причем для каждого приложения своя таблица);

2) отображение должно быть быстрым (так как происходит при каждом обращении к ячейке памяти, и не должно замедлять работу).

Организация многоуровневых таблиц страниц

Чтобы обойти проблему постоянного хранения в памяти огромных таблиц страниц, часто используются многоуровневые таблицы. Все ВАП процесса делится на разделы, а разделы – на страницы (рис. 5.3).

Рис. 5.3. Адресация при многоуровневой организации ВАП

Все страницы имеют одинаковый размер, а разделы содержат одинаковое количество страниц. Если размер и количество страниц в разделе выбрать равными степеням двойки (2k, 2n соответственно), то принадлежность виртуального адреса к разделу и странице, а также смещение внутри страницы можно определить очень просто: младшие k двоичных разрядов дают смещение, следующие n разрядов дают номер виртуальной страницы, а оставшиеся старшие разряды содержат номер раздела. Для каждого раздела строится собственная таблица страниц, причем количество элементов таблицы и их размер подбираются такими, чтобы объем таблицы был равен объему страницы. Например, в Pentium при размере страницы 4 Кбайта длина элемента таблицы составляет 4 байта и количество записей в таблице страниц – 1024. Каждая таблица страниц описывается элементом в таблице разделов, называемой также каталогом страниц. Страница, содержащая таблицу разделов, никогда не выгружается из памяти, а таблицы страниц могут при необходимости выгружаться на диск (это экономит память, но приводит к дополнительным затратам времени при получении физического адреса).

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