Разработка операционных систем

| | | | |i|7 | | | | |

| | | | | |8 |F | | | |

| | | | | | | | | | |

| | | | | | | | | | |

| | | | | |15 | | | | |

Для учёта распределения страниц между внешней и основной памятью

каждая строка таблицы страниц дополняется битом местонахождения страницы.

Valid/invalid bit.

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

помеченную значением invalid, возникает событие, называемое страничная

недостаточность (paging fault).

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

передачу управления операционной системе. Реакция операционной системы на

страничную недостаточность заключается в том, что необходимая страница

загружается в основную память.

На рисунке показаны основные этапы обработки события «страничная

недостаточность».

| |

| |

| |

|свободна|

|я рамка |

| |

| |

| |

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

физический, проверяет значение бита местонахождения необходимой

страницы*.

1. если значение бита invalid, то процесс прерывается и управление

передается операционной системе для обработки события страничная

недостаточность.

1. разыскивается необходимая страница во вторичной памяти и свободная

страничная рамка в основной**.

1. требуемая страница загружается в выбранную страничную рамку.

1. после завершения операции загрузки редактируется соответствующая строка

таблицы страниц, в которую вносится базовый адрес и valid значение бита

местонахождения.

1. управление передается прерванному процессу

4.2. Замещение страниц.

В ПРОЦЕССЕ ОБРАБОТКИ СТРАНИчНОЙ НЕДОСТАТОчНОСТИ ОПЕРАЦИОННАя СИСТЕМА

МОЖЕТ ОБНАРУЖИТЬ, чТО ВСЕ СТРАНИчНЫЕ РАМКИ ОСНОВНОЙ ПАМяТИ ЗАНяТЫ, И,

СЛЕДОВАТЕЛЬНО, НЕВОЗМОЖНО ЗАГРУЗИТЬ ТРЕБУЕМУЮ СТРАНИЦУ. В ЭТОМ СЛУчАЕ

ВОЗМОЖНЫ СЛЕДУЮЩИЕ РЕЖИМЫ: ПРИОСТАНОВКА ПРЕРВАННОГО ПРОЦЕССА, УМЕНЬШЕНИЕ НА

ЕДИНИЦУ КОЛИчЕСТВА ПРОЦЕССОВ МУЛЬТИПРОГРАММНОЙ СМЕСИ ДЛя ОСВОБОЖДЕНИя ВСЕХ

ЕЮ ЗАНИМАЕМЫХ СТРАНИчНЫХ РАМОК, ИСПОЛЬЗОВАНИЕ МЕТОДА ЗАМЕЩЕНИя СТРАНИЦ.

Метод замещения страниц означает, что в основной памяти выбирается

наименее важная/используемая страница, называется страница — жертва (victim

page), которая временно перемещается в swap space, а на её место

загружается страница, вызываемая страничной недостаточностью.

Обработка страничной недостаточности с учетом замещения

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

1. определяется местонахождение страницы путем анализа бита местонахождения

2. если значение бита invalid, то разыскивается свободная страничная рамка.

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

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

замещения, который выбирает страницу — жертву.

3. страница — жертва перемещается в swap space и редактируется таблица

страниц.

3. требуемая страница загружается на место страницы — жертвы и

соответствующим образом редактируется таблица страниц.

Управление передается прерванному процессу. Приведенный алгоритм

замещения требует двухстраничных перемещений.

1. страница - жертва перемещается в swap space.

1. требуемая страница перемещается в освободившуюся страничную рамку.

Страницу - жертву можно не копировать в swap space в том случае, если

за время, прошедшее от последнего перемещения её содержимое не

модифицировалось. В этом случае время замещения уменьшается примерно вдвое.

Для учета факта модификации страницы в таблицу страниц вводится

дополнительный бит, который меняет своё значение на противоположное в том

случае, если содержимое страницы изменилось.

Для практического использования метода страничирования по запросу

необходимо разработать два алгоритма.

1. алгоритм распределения страничных рамок (from allocation algorithm).

1. алгоритм замещения страниц (page replacement algorithm).

Алгоритм распределения страничных рамок решает, сколько страничных

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

смеси.

Алгоритм замещения страниц решает, какую из страниц выбрать в

качестве жертвы.

4.2.1. FIFO.

НАИБОЛЕЕ ПРОСТЫМ АЛГОРИТМОМ ЗАМЕЩЕНИя СТРАНИЦ яВЛяЕТСя АЛГОРИТМ FIFO.

ЭТОТ АЛГОРИТМ АССОЦИИРУЕТ С КАЖДОЙ СТРАНИЦЕЙ ВРЕМя, КОГДА ЭТА СТРАНИЦА БЫЛА

ПОМЕЩЕНА В ПАМяТЬ. ДЛя ЗАМЕЩЕНИя ВЫБИРАЕТСя НАИБОЛЕЕ СТАРАя СТРАНИЦА.

| | | | | | | | | | | | | | | | | | | | | | | | | | | |

Учет времени необязателен, когда все страницы в памяти связаны в FIFO-

очередь, а каждая помещаемая в память страница добавляется в хвост очереди.

Алгоритм учитывает только время нахождения страницы в памяти, но не

учитывает используемость страницы. Например, первые страницы программы

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

программы. Это приводит к немедленному возвращению к только что замещенной

странице.

4.2.2. Оптимальный алгоритм.

ЭТОТ АЛГОРИТМ ИМЕЕТ НАИЛУчШЕЕ СООТНОШЕНИЕ КОЛИчЕСТВА ЗАМЕЩЕННЫХ

СТРАНИЦ К КОЛИчЕСТВУ ССЫЛОК. АЛГОРИТМ СТРОИТСя ПО СЛЕДУЮЩЕМУ ПРИНЦИПУ:

ЗАМЕЩАЕТСя ТА СТРАНИЦА, НА КОТОРУЮ НЕТ ССЫЛКИ НА ПРОТяЖЕНИИ НАИБОЛЕЕ

ДЛИТЕЛЬНОГО ПЕРИОДА ВРЕМЕНИ. ДЛя РЕАЛИЗАЦИИ ЭТОГО АЛГОРИТМА НЕОБХОДИМО

КАЖДЫЙ РАЗ СКАНИРОВАТЬ ВЕСЬ ПОТОК ССЫЛОК, ПОЭТОМУ ОН НЕРЕАЛИЗУЕМ НА

ПРАКТИКЕ И ИСПОЛЬЗУЕТСя ДЛя ОЦЕНКИ РЕАЛЬНО РАБОТАЮЩИХ АЛГОРИТМОВ.

4.2.3. LRU — алгоритм (least recently used).

АЛГОРИТМ ВЫБИРАЕТ ДЛя ЗАМЕЩЕНИя ТУ СТРАНИЦУ, НА КОТОРУЮ НЕ БЫЛО

ССЫЛКИ НА ПРОТяЖЕНИИ НАИБОЛЕЕ ДЛИННОГО ПЕРИОДА ВРЕМЕНИ. LEAST RECENTLY USED

АССОЦИИРУЕТ С КАЖДОЙ СТРАНИЦЕЙ ВРЕМя ПОСЛЕДНЕГО ИСПОЛЬЗОВАНИя ЭТОЙ

СТРАНИЦЫ. ДЛя ЗАМЕЩЕНИя ВЫБИРАЕТСя ТА СТРАНИЦА, КОТОРАя ДОЛЬШЕ ВСЕХ НЕ

ИСПОЛЬЗОВАЛАСЬ. ЭТОТ АЛГОРИТМ НАИБОЛЕЕ чАСТО ИСПОЛЬЗУЕТСя В СИСТЕМАХ

СТРАНИчИРОВАНИя ПО ЗАПРОСУ. ОБЫчНО ПРИМЕНяЕТСя ДВА ПОДХОДА ПРИ ВНЕДРЕНИИ

ЭТОГО АЛГОРИТМА.

1. подход на основе логических часов (счетчика)

1. подход на основе стека номеров страниц

1. ассоциируют с каждой строкой таблицы поле “время использования” а в CPU

добавляются логические часы. Логические часы увеличивают своё значение

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

страницу, значение регистра логических часов копируется в поле “время

использования”. Заменяется страница с наименьшим значением в отмеченном

поле путем сканирования всей таблицы страниц. Сканирование отсутствует

при использовании подхода на основе стека.

1. стек номеров страниц хранит номера страниц, упорядоченных в соответствии

с историей их использования, на вершине стека располагается только что

использованная страница, а на дне least recently used страница. Как

только осуществляется ссылка на страницу, она перемещается на вершину

стека, а номера всех страниц сдвигаются вниз.

5. ОБЩИЕ СВЕДЕНИЯ

Теперь, после ознакомления с теорией операционных систем, рассмотрим

вкратце каждую из выше перечисленных*. Все эти операционные системы

работают в многозадачном однопользовательском режиме работы (UNIX также

поддерживает и многопользовательский режим); поддерживают иерархическую

файловую систему, межпроцессное взаимодействие, встроенные средства отладки

программ, стандартизируют программный интерфейс для многих внешних

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

5.1. УПРАВЛЕНИЕ ПАМЯТЬЮ.

Все рассматриваемые операционные системы обеспечивают выделение

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

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

Операционная система OS/2 использует страничную модель памяти, то есть

программа получает память порциями по 4 кб; подкачка также осуществляется

порциями по 4 кб. Программа не может управлять процессом подкачки.

Важной особенностью OS/2 является возможность создания специальных

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

межпроцессного взаимодействия (см. гл. межпроцессное взаимодействие).

Microsoft Windows использует сегментированную модель память.

Исторически сложилось так, что ОС (а, точнее, программная оболочка)

Microsoft Windows до разработки процессора 80386 работала в реальном режиме

(’real mode’) и защищенном режиме 80286-го процессора (’standart mode’). В

реальном режиме механизм подкачки не использовался; при наличии 286-го

процессора ОС позволяла выгружать на диск только MS-DOS-освские программы.

С появлением процессора 80386 и использованием его защищенного режима,

возможности использования виртуальной памяти резко расширились: появилась

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

системных вызовов, программа пользователя может управлять многими нюансами

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

перемещением объектов в памяти.

5.2. ФАЙЛОВАЯ СИСТЕМА.

Все системы поддерживают следующие элементы иерархических файловых

систем: обычные файлы, каталоги, специальные байт-ориентированные и блок-

ориентированные файлы. Файл является массивом байтов (блоков фиксированной

длины). Каталоги обеспечивают связь между именами файлов и собственно

файлами. Каждый элемент каталога содержит имя файла и ссылку на конкретный

файл. Для именования файлов используются корневой и текущий каталоги. Имя

файла состоит из последовательности компонентов - локальных имен,

разделенных символами '\' (В операционной системе UNIX - '/').

ОС UNIX характеризуется единственной однородной файловой системой на

один или несколько компьютеров. В Microsoft Windows и OS/2 файловые системы

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

алфавита).

Операционная система OS/2, кроме того, поддерживает свою файловую

систему - HPFS (High Performance File System - высокопроизводительная

файловая система), характеризующаяся хранением имен файлов и каталогов в

виде B-дерева.

Внешние устройства (такие как терминал, принтер) так же часто

представляются как файлы для упрощения работы с ними.

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

на смену и получение имени текущего каталога; создание, открытие, закрытие,

удаление, переименование и получение информации о файле или каталоге,

позиционирование в них.

Все рассматриваемые операционные системы поддерживают операции

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

многозадачной среде.

5.3. УПРАВЛЕНИЕ ПРОЦЕССАМИ.

Единицей управления и потребления ресурсов в многозадачной системе

является процесс. В частности, ввод-вывод выполняется синхронно, и процесс

приостанавливается до его завершения. Если требуется продолжить выполнение

процесса параллельно с инициированным им вводом-выводом, нужно

предварительно породить другой процесс для реализации ввода-вывода.

Microsoft Windows, OS/2 и UNIX предоставляют сходные системные вызовы для

обслуживания и управления процессами ('сессия' в OS/2): порождение,

уничтожение.

OS/2 предоставляет гораздо более широкий спектр системных вызовов для

управления процессами. В OS/2 существуют три вида процессов: нити (цепи или

треды), 'настоящие' процессы и экранные группы. Экранные группы - наиболее

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

виртуальную консоль, адресное пространство, открытые файлы, очереди и

каналы (см. ниже). Внутри экранной группы могут находится один или более

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

и свое адресное пространство. Нити - самый простой класс процессов, они

имеют только свое собственное адресное пространство, а все остальные

ресурсы наследуют от породившего их 'настоящего' процесса.

В операционной системе OS/2 планировщик задач может выделять

'настоящим' процессам кванты времени по двум алгоритмам: динамического и

абсолютного приоритетов. Алгоритм динамического приоритета выражается:

система подсчитывает интенсивность операций ввода-вывода, использования

процессорного времени, и по ним определяет количество квантов времени,

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

распределяет кванты времени согласно числовым значениям, заданным при

старте процесса. Процесс может изменять свой приоритет в небольших пределах

с помощью системной функции.

В Microsoft Windows планировщика задач распределяет кванты

процессорного времени аналогично алгоритму абсолютных приоритетов в

операционной системе OS/2. Программа никак не может повлиять на количество

предоставляемого ей процессорного времени.

В операционной системе UNIX алгоритм работы планировщика задач зависит

от реализации.

5.4. МЕЖПРОЦЕССНОЕ ВЗАИМОДЕЙСТВИЕ.

Операционные системы используют разные термины для определения

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

Единственным видом межпроцессного взаимодействия в ОС UNIX является

сигнальный механизм. Посредством сигналов передается информация о

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

исключительных ситуациях или завершении порожденного процесса. Сигнал

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

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

сигнал, определенный в системе, процесс должен иметь реакцию - действие,

которое он выполняет при получении сигнала.

Операционная система OS/2 предоставляет три типа межпроцессного

взаимодействия: каналы, очереди и семафоры.

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

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

между процессами. Только два процесса могут читать или писать в канал -

сервер и клиент.

Очередь - это упорядоченный список из 32-битных значений,

интерпретируемых процессом по контексту (это может быть целое, указатель на

общую область памяти или просто флаг). Любой процесс может прочесть

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

Семафор - это объект, имеющий два устойчивых состояния (рабочее и

нерабочее) и используемый для синхронизации исполнения процессов.

Существует несколько видов семафоров: семафор событий, взаимного

исключения, взаимного ожидания и именованный.

Когда семафор событий находится в нерабочем состоянии, операционная

система блокирует исполнение всех процессов, которые запрашивают состояние

семафора.

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

обращении к разделяемым ресурсам. Операционная система блокирует доступ к

разделяемому ресурсу до тех пор, пока соответствующий семафор не будет

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

значение семафора в рабочее состояние, показывая тем самым, что ресурс

занят.

Семафор взаимного ожидания представляет собой пакет из семафоров

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

процесс до тех пор, пока один или все семафоры внутри именованного семафора

не окажутся в состоянии 'свободен'(в зависимости от потребности процесса).

Реакция на именованный семафор зависит от процессов, совместно

использующих его.

В операционных системах OS/2 и Microsoft Windows существует

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

времени. Этот механизм называется DDE (Dynamic Data Exchange - динамический

обмен данными). Он стандартизирует процесс обмена командами, сообщениями и

объектами для обработки между задачами. Наиболее распространенные действия,

для которых используются DDE - печать.

Другим интерфейсом для обмена данными является OLE (Object Linking and

Embedding - объектное связывание со встраиванием). Этот интерфейс позволяет

хранить объекты, созданные одной программой, в объектах, созданных другой

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

информации и связей.

Одним из наиболее простых, удобных и интуитивных интерфейсов

межпрограммного взаимодействия является буфер обмена - Clipboard. Буфер

обмена может содержать в себе один информационный объект - кусок текста,

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

информации, содержащейся в буфере обмена или сам поместить объект в буфер,

при этом старое содержимое буфера теряется. Таким образом программы

получают простой, но эффективный способ обмена информацией в процессе своей

работы.

Операционная система UNIX не предоставляет этого способа обмена

информацией, Microsoft Windows же позволяет задачам обмениваться

информацией таким образом, даже в DOS-сессиях.

5.5. ГРАФИЧЕСКИЙ ИНТЕРФЕЙС ПОЛЬЗОВАТЕЛЯ.

Графический интерфейс пользователя изначально был несвойственен

Страницы: 1, 2, 3, 4, 5