Автор работы: Пользователь скрыл имя, 30 Ноября 2011 в 20:54, реферат
С 1965 по 1969 год компания Bell Labs совместно с компанией General Electric и группой исследователей из Масачусетского технологического института участвовала в проекте ОС Multics. Целью проекта было создание многопользовательской интерактивной операционной системы, обеспечивающей большое число пользователей удобными и мощными средствами доступа к вычислительным ресурсам. В этом курсе мы не ставим задачу познакомить слушателей с ОС Multics. Это могло бы быть темой отдельного большого курса. Однако отметим хотя бы некоторые идеи, которые содержались в проекте MAC (так назывался проект ОС Multics).
Во-первых, эта система основывалась на принципах многоуровневой защиты. Виртуальная память имела сегментно-страничную организацию, разделялись сегменты данных и сегменты программного кода, и с каждым сегментом связывался уровень доступа (по выполнению для сегментов команд и уровень чтения и записи для сегментов данных). Для того, чтобы какая-либо программа могла вызвать программу или обратиться к данным, располагающимся в некотором сегменте, требовалось, чтобы уровень выполнения этой программы (точнее, сегмента, в котором эта программа содержалась, был не ниже уровня доступа соответствующего сегмента). Такая организация позволяла практически полностью и с полной защитой содержать операционную систему в системных сегментах любого пользовательского виртуального адресного пространства.
Проект операционной системы Multics: неудача с положительными последствиями 2
Возникновение и первая редакция ОС UNIX 3
Исследовательский UNIX 5
Первый перенос ОС UNIX 5
Седьмая редакция 6
Возникновение группы университета г. Беркли (BSD) 7
UNIX System III и первые коммерческие версии системы 8
AT&T System V Release 2 и Release 3 9
Пользователь 9
Интерфейс пользователя 10
Привилегированный пользователь 10
Ядро ОС UNIX 11
Общая организация традиционного ядра ОС UNIX 12
Основные функции 13
Принципы взаимодействия с ядром 14
Принципы обработки прерываний 15
Файловая система 16
Структура файловой системы 16
Монтируемые файловые системы 18
Защита файлов 18
Драйверы устройств 19
Внешний и внутренний интерфейсы устройств 20
Сетевая файловая система (NFS) 21
Основные функции и компоненты ядра ОС UNIX 22
Управление памятью 22
Виртуальная память 23
Перспективные ОС, поддерживающие среду ОС UNIX 28
Понятие микроядра 29
Микроядро Mach университета Карнеги-Меллон 31
Микроядро Chorus компании Chorus Systems 33
Примеры микроядерных реализаций ОС UNIX 33
OSF-1 компании Open Software Foundation 33
MiX компании Chorus Systems 33
Hurd Free Software Foundation 34
Для полноты изложения, но не вдаваясь в детали, заметим, что существуют две другие схемы организации виртуальной памяти: сегментная и сегментно-страничная. При сегментной организации виртуальный адрес по-прежнему состоит из двух полей - номера сегмента и смещения внутри сегмента. Отличие от страничной организации состоит в том, что сегменты виртуальной памяти могут быть разного размера. В элементе таблицы сегментов помимо физического адреса начала сегмента (если виртуальный сегмент содержится в основной памяти) содержится длина сегмента. Если размер смещения в виртуальном адресе выходит за пределы размера сегмента, возникает прерывание. Понятно, что компьютер с сегментной организацией виртуальной памяти можно использовать как компьютер со страничной организацией, если использовать сегменты одного размера.
При сегментно-страничной организации виртуальной памяти происходит двухуровневая трансляция виртуального адреса в физический. В этом случае виртуальный адрес состоит из трех полей: номера сегмента виртуальной памяти, номера страницы внутри сегмента и смещения внутри страницы. Соответственно, используются две таблицы отображения - таблица сегментов, связывающая номер сегмента с таблицей страниц, и отдельная таблица страниц для каждого сегмента.
Сегментно-страничная
организация виртуальной памяти
позволяла совместно
В дальнейшем рассмотрении мы ограничимся проблемами управления страничной виртуальной памяти. С небольшими коррективами все обсуждаемые ниже методы и алгоритмы относятся и к сегментной, и сегментно-страничной организациям.
Как же достигается
возможность наличия
Наиболее ответственным действием описанного процесса является выделение страницы основной памяти для удовлетворения требования доступа к отсутствующей в основной памяти виртуальной странице. Напомним, что мы рассматриваем ситуацию, когда размер каждой виртуальной памяти может существенно превосходить размер основной памяти. Это означает, что при выделении страницы основной памяти с большой вероятностью не удастся найти свободную (не приписанную к какой-либо виртуальной памяти) страницу. В этом случае операционная система должна в соответствии с заложенными в нее критериями (совокупность этих критериев принято называть "политикой замещения", а основанный на них алгоритм замещения - "алгоритмом подкачки") найти некоторую занятую страницу основной памяти, переместить в случае надобности ее содержимое во внешнюю память, должным образом модифицировать соответствующий элемент соответствующей таблицы страниц и после этого продолжить процесс удовлетворения доступа к странице.
Существует большое количество разнообразных алгоритмов подкачки. Объем этого курса не позволяет рассмотреть их подробно. Соответствующий материал можно найти в изданных на русском языке книгах по операционным системам Цикритзиса и Бернстайна, Дейтела и Краковяка. Однако, чтобы вернуться к описанию конкретных методов управления виртуальной памятью, применяемых в ОС UNIX, мы все же приведем некоторую краткую классификацию алгоритмов подкачки.
Во-первых, алгоритмы подкачки делятся на глобальные и локальные. При использовании глобальных алгоритмов операционная система при потребности замещения ищет страницу основной памяти среди всех страниц, независимо от их принадлежности к какой-либо виртуальной памяти. Локальные алгоритмы предполагают, что если возникает требование доступа к отсутствующей в основной памяти странице виртуальной памяти ВП1, то страница для замещения будет искаться только среди страниц основной памяти, приписанных к той же виртуальной памяти ВП1.
Наиболее распространенными традиционными алгоритмами (как в глобальном, так в локальном вариантах) являются алгоритмы FIFO (First In First Out) и LRU (Least Recently Used). При использовании алгоритма FIFO для замещения выбирается страница, которая дольше всего остается приписанной к виртуальной памяти. Алгоритм LRU предполагает, что замещать следует ту страницу, к которой дольше всего не происходили обращения. Хотя интуитивно кажется, что критерий алгоритма LRU является более правильным, известны ситуации, в которых алгоритм FIFO работает лучше (и, кроме того, он гораздо более дешево реализуется).
Заметим еще, что при использовании глобальных алгоритмов, вне зависимости от конкретного применяемого алгоритма, возможны и теоретически неизбежны критические ситуации, которые называются по-английски thrashing (несмотря на множество попыток, хорошего русского эквивалента так и не удалось придумать). Рассмотрим простой пример. Пусть на компьютере в мультипрограммном режиме выполняются два процесса - П1 в виртуальной памяти ВП1 и П2 в виртуальной памяти ВП2, причем суммарный размер ВП1 и ВП2 больше размеров основной памяти. Предположим, что в момент времени t1 в процессе П1 возникает требование виртуальной страницы ВС1. Операционная система обрабатывает соответствующее прерывание и выбирает для замещения страницу основной памяти С2, приписанную к виртуальной странице ВС2 виртуальной памяти ВП2 (т.е. в элементе таблицы страниц, соответствующем ВС2, проставляется флаг отсутствия страницы). Для полной обработки требования доступа к ВС1 в общем случае потребуется два обмена с внешней памятью (первый, чтобы записать текущее содержимое С2, второй - чтобы прочитать копию ВС1). Поскольку операционная система поддерживает мультипрограммный режим работы, то во время выполнения обменов доступ к процессору получит процесс П2, и он, вполне вероятно, может потребовать доступа к своей виртуальной странице ВС2 (которую у него только что отняли). Опять будет обрабатываться прерывание, и ОС может заменить некоторую страницу основной памяти С3, которая приписана к виртуальной странице ВС3 в ВП1. Когда закончатся обмены, связанные с обработкой требования доступа к ВС1, возобновится процесс П1, и он, вполне вероятно, потребует доступа к своей виртуальной странице ВС3 (которую у него только что отобрали). И так далее. Общий эффект состоит в том, что непрерывно работает операционная система, выполняя бесчисленные и бессмысленные обмены с внешней памятью, а пользовательские процессы П1 и П2 практически не продвигаются.
Понятно, что при использовании локальных алгоритмов ситуация thrashing, затрагивающая несколько процессов, невозможна. Однако в принципе возможна аналогичная ситуация внутри одной виртуальной памяти: ОС может каждый раз замещать ту страницу, к которой процесс обратится в следующий момент времени.
Единственным алгоритмом, теоретически гарантирующим отсутствие thrashing, является так называемый "оптимальный алгоритм Биледи" (по имени придумавшего его венгерского математика). Алгоритм заключается в том, что для замещения следует выбирать страницу, к которой в будущем наиболее долго не будет обращений. Понятно, что в динамической среде операционной системы точное знание будущего невозможно, и в этом контексте алгоритм Биледи представляет только теоретический интерес (хотя он с успехом применяется практически, например, в компиляторах для планирования использования регистров).
В 1968 году американский исследователь Питер Деннинг сформулировал принцип локальности ссылок (называемый принципом Деннинга) и выдвинул идею алгоритма подкачки, основанного на понятии рабочего набора. В некотором смысле предложенный им подход является практически реализуемой аппроксимацией оптимального алгоритма Биледи. Принцип локальности ссылок (недоказуемый, но подтверждаемый на практике) состоит в том, что если в период времени (T-t, T) программа обращалась к страницам (С1, С2, ..., Сn), то при надлежащем выборе t с большой вероятностью эта программа будет обращаться к тем же страницам в период времени (T, T+t). Другими словами, принцип локальности утверждает, что если не слишком далеко заглядывать в будущее, то можно хорошо его прогнозировать исходя из прошлого. Набор страниц (С1, С2, ..., Сn) называется рабочим набором программы (или, правильнее, соответствующего процесса) в момент времени T. Понятно, что с течением времени рабочий набор процесса может изменяться (как по составу страниц, так и по их числу). Идея алгоритма подкачки Деннинга (иногда называемого алгоритмом рабочих наборов) состоит в том, что операционная система в каждый момент времени должна обеспечивать наличие в основной памяти текущих рабочих наборов всех процессов, которым разрешена конкуренция за доступ к процессору. Мы не будем вдаваться в технические детали алгоритма, а лишь заметим следующее. Во-первых, полная реализация алгоритма Деннинга практически гарантирует отсутствие thrashing. Во-вторых, алгоритм реализуем (известна, по меньшей мере, одна его полная реализация, которая однако потребовала специальной аппаратной поддержки). В-третьих, полная реализация алгоритма Деннинга вызывает очень большие накладные расходы.
Поэтому на практике
применяются облегченные
Микроядро - это минимальная стержневая часть операционной системы, служащая основой модульных и переносимых расширений. По-видимому, большинство операционных систем следующего поколения будут обладать микроядрами. Однако имеется масса разных мнений по поводу того, как следует организовывать службы операционной системы по отношению к микроядру: как проектировать драйверы устройств, чтобы добиться наибольшей эффективности, но сохранить функции драйверов максимально независимыми от аппаратуры; следует ли выполнять операции, не относящиеся к ядру, в пространстве ядра или в пространстве пользователя; стоит ли сохранять программы имеющихся подсистем (например, UNIX) или лучше отбросить все и начать с нуля.
В широкий обиход
понятие микроядра ввела
Следующей микроядерной операционной системой была Windows NT компании Microsoft, в которой ключевым преимуществом использования микроядра должна была стать не только модульность, но и переносимость. (Заметим, что отсутствует единодушное мнение по поводу того, следует ли на самом деле относить NT к микроядерным ОС.) ОС NT была построена таким образом, чтобы ее можно было применять в одно- и мультипроцессорных системах, основанных на процессорах Intel, Mips и Alpha (и тех, которые придут вслед за ними). Поскольку в среде NT должны были выполняться программы, написанные для DOS, Windows, OS/2 и систем, совместимых со стандартами Posix, компания Microsoft использовала присущую микроядерному подходу модульность для создания общей структуры NT, не повторяющей ни одну из существующих операционных систем. Каждая операционная система эмулируется в виде отдельного модуля или подсистемы.
Позднее микроядерные архитектуры операционных систем были объявлены компаниями Novell/USL, Open Software Foundation (OSF), IBM, Apple и другими. Одним из основных конкурентов NT в области микроядерных ОС является Mach 3.0, система, созданная в университете Карнеги-Меллон, которую как IBM, так и OSF взялись довести до коммерческого вида. (Компания Next в качестве основы для NextStep пока использует Mach 2.5, но тоже внимательно присматривается к Mach 3.0.) Другим конкурентом является микроядро Chorus 3.0 компании Chorus Systems, выбранное USL в качестве основы новых реализаций ОС UNIX. Некоторое микроядро будет использоваться в SpringOS фирмы Sun, объектно-ориентированном преемнике ОС Solaris (если, конечно, Sun доведет работу над SpringOS до конца). Очевидна тенденция к переходу от монолитных к микроядерным системам (хотя, как мы отмечали в предыдущем разделе, этот процесс не является прямолинейным: компания IBM сделала шаг назад и отказалась от перехода к микроядерной технологии). Кстати, это совсем не новость для компаний QNX Software Systems и Unisys, которые уже в течение нескольких лет выпускают пользующиеся успехом микроядерные операционные системы. ОС QNX пользуется спросом на рынке систем реального времени, а CTOS фирмы Unisys популярна в области банковского дела. В обеих системах успешно использована модульность, присущая микроядерным ОС.