- •Основы построения операционных систем
- •Введение
- •1. Основные аспекты операционных систем
- •1.1. Программные системы
- •1.2. Ресурсы вычислительных систем
- •1.3. Функции операционных систем
- •1.3.1. Упрощение доступа к компьютеру
- •1.3.2. Повышение эффективности использования ресурсов
- •1.4. Классификация операционных систем
- •2. Управление файлами
- •2.1. Файлы
- •2.1.1. Имя файла
- •2.1.2. Типы файлов
- •2.1.3. Атрибуты файла
- •2.2. Функции системы управления файлами
- •2.3. Способы организации файлов
- •2.3.1. Последовательное размещение
- •2.3.2. Размещение с помощью сцепленных блоков
- •2.3.3. Организация файлов на основе таблиц размещения
- •2.3.4. Размещение с использованием таблицы индексов
- •2.3.5. Индексно-последовательное размещение
- •2.3.6. Библиотечная структура данных
- •2.4. Методы доступа к содержимому файлов
- •2.4.1. Последовательный доступ
- •2.4.2. Прямой доступ
- •2.4.3. Другие методы доступа
- •2.5. Способы организации файловой структуры
- •2.6. Манипулирование файловой структурой
- •3. Управление памятью
- •3.1. Простое непрерывное распределение
- •3.2. Распределение с несколькими непрерывными разделами
- •3.2.1. Мультипрограммирование и разбиение на разделы
- •3.2.2. Разделы с фиксированными границами
- •3.2.3. Разделы с подвижными границами
- •3.2.4. Своппинг
- •3.3. Организация виртуальной памяти
- •3.3.1. Основные концепции виртуальной памяти
- •3.3.2. Страничная организация памяти
- •3.3.3. Сегментная организация памяти
- •3.3.4. Сегментно-страничная организация памяти
- •3.4. Управление виртуальной памятью
- •3.4.1. Алгоритмы выталкивания страниц
- •3.4.2. Подкачка страниц по запросу
- •3.4.3. Подкачка страниц с опережением
- •3.4.4. Освобождение страниц
- •3.4.5. Размер страниц
- •4. Управление процессами
- •4.1. Концепции процесса
- •4.1.1. Понятие последовательного процесса
- •4.1.2. Состояния процесса
- •4.1.3. Блок управления процессом
- •4.1.4. Планирование процессов
- •4.1.5. Обработка прерываний
- •4.2. Синхронизация параллельных процессов
- •4.2.1. Параллельная обработка
- •4.2.2. Взаимное исключение
- •4.2.3. Алгоритм Деккера
- •4.2.4. Аппаратная реализация взаимного исключения
- •4.2.5. Семафоры
- •4.2.6. Мониторы
- •4.2.7. Передача сообщений
- •4.3. Тупиковые ситуации
- •4.3.1. Условия возникновения дедлоков
- •4.3.2. Основные направления исследований по проблеме тупиков
- •4.3.3. Предотвращение тупиков
- •4.3.4. Обход дедлоков
- •4.3.5. Алгоритм банкира
- •4.3.6. Распознавание дедлоков
- •4.3.7. Восстановление после тупиков
- •5. Управление процессором
- •5.1. Диспетчеризация процессов
- •5.2. Приоритеты
- •5.3. Алгоритмы диспетчеризации с одной очередью
- •5.3.1. Алгоритм fcfs (первый пришедший обслуживается первым)
- •5.3.2. Алгоритм spn (кратчайший процесс - следующий)
- •5.3.3. Алгоритм srt (по наименьшему остающемуся времени)
- •5.3.4. Алгоритм hrrn (по наибольшему относительному времени ответа)
- •5.3.5. Алгоритм циклической диспетчеризации rr
- •5.3.6. Сравнение алгоритмов диспетчеризации с одной очередью
- •5.4. Многоуровневые очереди с обратными связями
- •6. Управление устройствами
- •6.1. Общая организация ввода-вывода
- •6.2. Методы управления периферийными устройствами
- •6.3. Действия по вводу-выводу
- •6.3.1. Буферизация : прочитать и записать
- •6.3.2. Блокирование : получить и поместить
- •6.3.3. Подготовка : открыть и закрыть
- •6.4. Управление магнитными дисками
- •6.4.1. Физическая структура магнитного диска
- •6.4.2. Физическая структура формата данных дискеты
- •6.4.3. Логическая структура магнитного диска
- •6.4.4. Планирование работы с магнитными дисками
- •Заключение
- •Список используемых источников
- •Оглавление
3.3.2. Страничная организация памяти
Страничная виртуальная память состоит из блоков фиксированного размера, или страниц, которые служат единицами измерения объема памяти. Виртуальный адрес в страничной системе - это упорядоченная пара (p,d), где p - номер страницы в виртуальной памяти, а d - смещение в рамках страницы p, где размещается адресуемый элемент (рис.3.11). Для удобства в компьютерах с двоичной адресацией размер страницы обычно кратен степени двойки. Виртуальным адресом является одно число, в котором старшие биты определяют p, а младшие - d.
Рис. 3.11. Формат виртуального адреса в системе
со страничной организацией памяти
Физическая память также разделена на блоки того же размера, называемые страничными кадрами или фреймами. Страничные кадры начинаются с адресов первичной памяти, кратных фиксированному размеру страницы.
Поступающая страница может быть помещена в любой свободный страничный кадр. Отображение страниц в страничные кадры описывается таблицей отображения страниц. В этой таблице для каждой страницы имеется элемент, состоящий из двух полей. Первое из них содержит признак, указывающий, находится страница в оперативной памяти или на внешнем устройстве. Если страница находится в оперативной памяти, то второе поле (старшие биты адреса) задает номер соответствующей физической страницы. Если страницы нет в оперативной памяти, то второе поле содержит информацию, необходимую для определения ее положения во внешней памяти. Для каждого процесса имеется одна таблица отображения страниц, которая используется для преобразования адресов виртуальной памяти программы в соответствующие адреса реальной памяти. Процесс динамического преобразования адресов представлен на рис.3.12.
Выполняющийся процесс делает ссылку по виртуальному адресу v=(p,d). Прежде, чем процесс начнет выполняться, операционная система загружает адрес первичной памяти для таблицы отображения страниц в регистр начального адреса этой таблицы. Этот базовый адрес b таблицы прибавляется к номеру страницы p, образуя адрес первичной памяти b+p элемента таблицы для страницы p, к которой идет обращение. Затем операционная система проверяет признак в этом элементе. Если страницы нет в оперативной памяти, то говорят, что страница отсутствует. Тогда аппаратура генерирует прерывание, по которому вызывается программа подкачки страниц. Это управляющая программа, в функции которой входит, во-первых, считывание необходимой страницы в оперативную память и, во-вторых, переключение процессора с данного процесса на другой, который не находится в состоянии ожидания. Каждый раз при считывании страницы в элементе таблицы отображения страниц устанавливаются признак и адрес страничного кадра. Если же страница уже находится в оперативной памяти, то второе поле элемента определяет адрес страничного кадра f, в который загружена страница p. Затем к значению f приформировывается (путем конкатенации) смещение d, так что образуется реальный адрес r.
Рис. 3.12. Динамическое преобразование адреса страницы
Такой подход называется способом прямого отображения, потому что таблица отображения страниц содержит отдельную строку для каждой страницы виртуальной памяти данного процесса. Если процесс имеет в виртуальной памяти n страниц, то таблица при прямом отображении для этого процесса содержит последовательные строки для страницы 0, страницы 1, ..., страницы n-1.
Как преобразуемый виртуальный адрес, так и базовый адрес таблицы отображения страниц хранятся в высокоскоростных регистрах управляющего процессора, так что операции с их участием можно выполнять очень быстро внутри командного цикла. Однако таблица прямого отображения страниц, которая может быть довольно большой, обычно находится в первичной памяти. Следовательно, для обращения к этой таблице требуется один полный цикл выборки из первичной памяти. Поскольку время выборки из первичной памяти составляет, как правило, наибольшую долю цикла выполнения команды и поскольку нам требуется еще один цикл обращения к первичной памяти для выборки соответствующей строки таблицы, это означает, что использование метода прямого отображения для преобразования адресов страниц может вызвать снижение скорости вычислительной машины при выполнении программ почти вдвое. Это, естественно, недопустимо. Поэтому необходимы более высокоскоростные способы преобразования адресов. В то же время это не означает, что способ прямого отображения совершенно неприемлем. Некоторые операционные системы с успехом его реализуют, размещая целиком всю таблицу в сверхвысокоскоростной кэш-памяти.
При страничной организации памяти процесс во время своего исполнения одновременно обращается к определенному числу страниц, называемому рабочим множеством. Если рабочие множества нескольких процессов существенно меньше, чем общий размер процессов, то оперативная память может содержать существенно больше процессов, чем при нестраничном распределении, что увеличивает коэффициент мультипрограммирования.
Однако если для каждого процесса выделяется мало страничных кадров, то большинство страниц в оперативной памяти будут необходимыми в каждый момент времени, и почти каждое обращение к отсутствующей странице будет приводить к вытеснению одной из них, которая в свою очередь сама вскоре потребуется. Возникающее при этом явление носит название пробуксовка - состояние, при котором система тратит большую часть своего времени на обработку ситуации отсутствия страниц. Доля же полезных вычислений при этом значительно уменьшается.
Другой недостаток страничной организации связан с тем, что процессам произвольной длины отводится целое число страниц фиксированного размера. В результате часть страницы оказывается незаполненной, т.е. имеет место внутренняя фрагментация памяти. В среднем на каждый процесс незаполненность составляет половину страницы. Увеличение размера страницы с целью снижения внутренней фрагментации будет приводить к снижению коэффициента мультипрограммирования. С другой стороны, маленькие страницы требуют больше памяти под таблицы отображения страниц, при этом увеличивается вероятность отсутствия требуемой страницы.