КУРС ВВЕДЕНИЕ В ОПЕРАЦИОННЫЕ СИСТЕМЫ СОВМЕСТНО С КОМПАНИЕЙ INTEL

КУРС ВВЕДЕНИЕ В ОПЕРАЦИОННЫЕ СИСТЕМЫ (СОВМЕСТНО С КОМПАНИЕЙ INTEL)

Глава 1. Введение

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

Что такое операционная система.

Структура вычислительной системы

Во вторую очередь это программное обеспечение. Все программное обеспечение принято делить на две части: прикладное и системное. К прикладному… Рис. 1.1. Слои программного обеспечения компьютерной системы.

Что такое ОС

Операционная система как виртуальная машина Архитектура большинства компьютеров на уровне машинных команд очень неудобна… Операционная система как менеджер ресурсов

Краткая история эволюции вычислительных систем

Первый период (1945-1955). Ламповые машины. Операционные систем отсутствовали. Мы начнем исследование развития компьютерных комплексов с появления… Первые шаги по созданию электронных вычислительных машин были предприняты в конце второй мировой войны. В середине…

Основные понятия, концепции ОС.

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

Системные вызовы

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

Прерывания

Исключительные ситуации

Файлы Файлы предназначены для хранения информации на внешних носителях, то есть,… Главная задача файловой системы (file system) скрыть особенности ввода-вывода и дать программисту простую абстрактную…

Архитектурные особенности ОС.

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

Монолитное ядро

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

Слоеные системы (Layered systems)

Рис. 1.2 Структура слоеной системы THE. Слоеные системы хорошо реализуются. При использовании операций нижнего слоя не нужно знать, как они реализованы, нужно…

Виртуальные машины

Рис. 1.3 Вариант виртуальной машины. Первой реальной системой такого рода была система CP/CMS или VM/370, как ее называют сейчас, для семейства машин…

Микроядерная архитектура.

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

Смешанные системы

Примером смешанного подхода может служить возможность запуска операционной системы с монолитным ядром под управлением микроядра. Так устроены 4.4BSD… Наиболее тесно элементы микроядерной архитектуры и элементы монолитного ядра… Таким образом, Windows NT можно с полным правом назвать гибридной операционной системой.

Классификация ОС

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

Реализация многозадачности

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

• многозадачные (Unix, OS/2, Windows).
• однозадачные (например, MS-DOS) и

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

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

Поддержка многопользовательского режима.

По числу одновременно работающих пользователей ОС можно разделить на:

• однопользовательские (MS-DOS, Windows 3.x);
• многопользовательские (Windows NT, Unix).

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

Многопроцессорная обработка

Многопроцессорные системы состоят из двух или более центральных процессоров, осуществляющих параллельное выполнение команд. Поддержка мультипроцессирования является важным свойством ОС и приводит к усложнению всех алгоритмов управления ресурсами. Многопроцессорная обработка реализована в таких ОС, как Linux, Solaris, Windows NT и в ряде других.

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

Системы реального времени.

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

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

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

Приведенная классификация ОС не является исчерпывающей. Более подробно особенности применения современных ОС рассмотрены в [30].

Резюме

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

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

Часть II. Процессы и их поддержка в операционной системе.

Глава 2. Процессы

— Гусар, Вы любите детей?
— Нет. Но сам процесс!..
Из известного анекдота

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

Понятие процесса

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

Состояния процесса

Как видим, каждый процесс может находиться как минимум в двух состояниях: процесс исполняется и процесс не исполняется. Диаграмма состояний процесса… Рис 2.1. Простейшая диаграмма состояний процесса.

Операции над процессами и связанные с ними понятия

Набор операций

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

Process Control Block и контекст процесса

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

Одноразовые операции

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

Рис 2.4 Упрощенный генеалогический лес процессов. Стрелочка означает отношение родитель-ребенок.

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

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

После наделения процесса-ребенка ресурсами необходимо занести в его адресное пространство программный код, значения данных, установить программный счетчик. Здесь также возможны два решения. В первом случае процесс-ребенок становится дубликатом процесса-родителя по регистровому и пользовательскому контекстам, при этом должен существовать способ определения кто для кого из процессов-двойников является родителем. Во втором случае процесс-ребенок загружается новой программой из какого-либо файла. Операционная система UNIX разрешает порождение процесса только первым способом; для запуска новой программы необходимо сначала создать копию процесса-родителя, а затем процесс-ребенок должен заменить свой пользовательский контекст с помощью специального системного вызова. Операционные системы VAX/VMS и WINDOWS NT допускают только второе решение.

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

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

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

Следует заметить, что в ряде операционных систем (например, в VAX/VMS) гибель процесса-родителя приводит к завершению работы всех его детей. В других операционных системах (например, в UNIX) процессы-дети продолжают свое существование и после окончания работы процесса-родителя. При этом возникает необходимость изменения информации в PCB процессов-детей о породившем их процессе для того, чтобы генеалогический лес процессов оставался целостным. Рассмотрим следующий пример. Пусть процесс с номером 2515 был порожден процессом с номером 2001 и после завершения его работы остается в вычислительной системе неограниченно долго. Тогда, не исключено, что номер 2001 будет использован операционной системой повторно для совсем другого процесса. Если не изменить информацию о процессе-родителе для процесса 2515, то генеалогический лес процессов окажется некорректным — процесс 2515 будет считать своим родителем новый процесс 2001, а процесс 2001 будет открещиваться от нежданного потомка. Как правило, осиротевшие процессы усыновляются одним из системных процессов, который порождается при старте операционной системы, и функционирует все время, пока она работает.

Многоразовые операции

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

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

Запуск процесса.Из числа процессов, находящихся в состоянии готовность, операционная система выбирает один процесс для последующего исполнения. Критерии и алгоритмы такого выбора будут подробно рассмотрены в главе 3 – Планирование процессов. Для избранного процесса операционная система обеспечивает наличие в оперативной памяти информации, необходимой для его дальнейшего выполнения. То, как она это делает, будет в деталях описано в части 3 – Управление Памятью. Далее состояние процесса изменяется на исполнение, восстанавливаются значения регистров для данного процесса, и управление передается команде, на которую указывает счетчик команд процесса. Все данные, необходимые для этого восстановления контекста, извлекаются из PCB процесса, над которым совершается операция.

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

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

Разблокирование процесса. После возникновения в системе какого-либо события, операционной системе нужно точно определить какое именно событие произошло. Затем операционная система проверяет: находился ли некоторый процесс в состоянии ожидание для данного события и, если находился, переводит его в состояние готовность, выполняя необходимые действия, связанные с наступлением события (инициализация операции ввода-вывода для очередного ожидающего процесса и т. п.). Эта операция, как и операция блокирование, будет детальнее описана в части V — “Управление вводом-выводом”.

Переключение контекста

  Рис 2.5 Выполнение операции разблокирования процесса. Использование термина… Давайте для примера упрощенно рассмотрим, как в реальности может проистекать операция разблокирования процесса,…

Резюме

Понятие процесса характеризует некоторую совокупность набора исполняющихся команд, ассоциированных с ним ресурсов и текущего момента его выполнения, находящуюся под управлением операционной системы. В любой момент времени процесс полностью описывается своим контекстом, состоящим из регистровой, системной и пользовательской частей. В операционной системе процессы представляются определенной структурой данных — PCB, отражающей содержание регистрового и системного контекстов. Процессы могут находиться в пяти основных состояниях: рождение, готовность, исполнение, ожидание, закончил исполнение. Из состояния в состояние процесс переводится операционной системой в результате выполнения над ним операций. Операционная система может выполнять над процессами следующие операции: создание процесса, завершение процесса, приостановка процесса, запуск процесса, блокирование процесса, разблокирование процесса, изменение приоритета процесса. Между выполнением операций содержимое PCB не изменяется. Деятельность мультипрограммной операционной системы состоит из цепочек перечисленных операций, выполняемых над различными процессами, и сопровождается процедурами сохранения/восстановления работоспособности процессов, т. е. переключением контекста. Переключение контекста не имеет отношения к полезной работе, выполняемой процессами, и время, затраченное на него, уменьшает полезное время работы процессора.

Глава 3. Планирование процессов

“Я планов наших люблю громадьё…”
В. В. Маяковский

“Чем тщательнее мы планируем свою деятельность,
тем меньше времени остается на ее осуществление.”
Из анналов Госплана

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

Уровни планирования

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

Критерии планирования и требования к алгоритмам

§ Справедливость: гарантировать каждому заданию или процессу определенную часть времени использования процессора в компьютерной системе, стараясь… § Эффективность: постараться занять процессор на все 100% рабочего времени,… § Сокращение полного времени выполнения (turnaround time): обеспечить минимальное время между стартом процесса или…

Параметры планирования

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

Вытесняющее и невытесняющее планирование

1. Когда процесс переводится из состояния исполнение в состояние завершение. 2. Когда процесс переводится из состояния исполнение в состояние ожидание. 3. Когда процесс переводится из состояния исполнение в состояние готовность (например, после прерывания от таймера). …

Алгоритмы планирования

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

First-Come, First-Served (FCFS)

Надо отметить, что аббревиатура FCFS используется для этого алгоритма планирования вместо стандартной аббревиатуры FIFO для механизмов подобного… Такой алгоритм выбора процесса осуществляет невытесняющее планирование.… Таблица 3.1.

Round Robin (RR)

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

Shortest-Job-First (SJF)

SJF алгоритм краткосрочного планирования может быть как вытесняющим, так и невытесняющим. При невытесняющем SJF планировании процессор… Рассмотрим пример работы невытесняющего алгоритма SJF. Пусть в состоянии… Таблица 3.4.

Гарантированное планирование

то i - й пользователь несправедливо обделен процессорным временем. Если же

Приоритетное планирование

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

Многоуровневые очереди (Multilevel Queue)

Рис. 3.5. Несколько очередей планирования.

Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)

Для простоты рассмотрим ситуацию, когда процессы в состоянии готовность организованы в 4 очереди, как на рисунке 3.6. Планирование процессов между… Рис. 3.6.Схема миграции процессов в многоуровневых очередях планирования с… Родившийся процесс поступает в очередь 0. При выборе на исполнение он получает в свое распоряжение квант времени…

Резюме

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

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

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

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

Глава 4. Кооперация процессов и основные аспекты ее логической организации

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

Взаимодействующие процессы

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

Категории средств обмена информацией

Логическая организация механизма передачи информации

4.3.1. Как устанавливается связь? Могу ли я использовать средство связи непосредственно для обмена информацией… К этому же вопросу тесно примыкает вопрос о способе адресации при использовании средства связи. Если я передаю…

Информационная валентность процессов и средств связи

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

Особенности передачи информации с помощью линий связи

Буферизация

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

Надежность средств связи

Мы будем называть способ коммуникации надежным, если при обмене данными выполняются следующие четыре условия: Не происходит потери информации.… Очевидно, что передача данных через разделяемую память является надежным… Каким образом в вычислительных системах пытаются бороться с ненадежностью коммуникаций? Давайте рассмотрим возможные…

Нити исполнения

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

Резюме

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

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

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

Глава 5. Алгоритмы синхронизации

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

Interleaving, race condition и взаимоисключения

Неделимые операции могут иметь некоторые внутренние невидимые действия (взять батон хлеба в левую руку, взять нож в правую руку, собственно… Пусть имеется две активности P: a b c Q: d e… где a, b, c, d, e, fатомарные операции. При последовательном выполнении активностей мы получаем следующую…

PQ: a b c d e f

а b c d e f a b d c e f a b d e c f a b d e f c a d b c e f ...... d e f a b c То есть атомарные операции активностей могут чередоваться всевозможными… Что мы получим в результате их псевдопараллельного выполнения, если переменные x и y являются общими для активностей?…

Критическая секция

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

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

Требования, предъявляемые к алгоритмам

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

Запрет прерываний

while (some condition) { запретить все прерывания critical section

Переменная-замок

shared int lock = 0; while (some condition) { while(lock); lock = 1;

Critical section

lock = 0;

Remainder section

К сожалению, внимательное изучение показывает, что такое решение, не удовлетворяет условию взаимоисключения, так как действие while(lock); lock = 1;…

Строгое чередование

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

shared int turn = 0;

while (some condition) {

while(turn != i);

Critical section

turn = 1-i;

Remainder section

}

Легко видеть, что взаимоисключение гарантируется, процессы входят в критическую секцию строго по очереди: P₀, P₁, P₀, P₁, P₀, ... Но наш алгоритм не удовлетворяет условию прогресса. Например, если значение turn равно 1и процесс P₀ готов войти в критический участок, он не может сделать этого, даже если процесс P₁находится в remainder section.

Флаги готовности

shared int ready[2] = {0, 0}; Когда i-й процесс готов войти в критическую секцию, он присваивает элементу… while (some condition) {

Critical section

ready[i] = 0;

Remainder section

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

Алгоритм Петерсона

shared int ready[2] = {0, 0}; shared int turn; while (some condition) { ready[i] = 1; turn =1- i; while(ready[1-i] && turn == 1-i);

Critical section

ready[i] = 0;

Remainder section

При исполнении пролога критической секции процесс Pi заявляет о своей готовности выполнить критический участок и одновременно предлагает другому… Давайте докажем, что все пять наших требований к алгоритму действительно… Удовлетворение требований 1 и 2 очевидно.

Алгоритм булочной (Bakery algorithm)

shared enum {false, true} choosing[n]; shared int number[n]; Изначально элементы этих массивов инициируются значениями false и… (a,b) < (c,d), если a < c или если a == c и b < d

Critical section

number[i] = 0;

Remainder section

}

Доказательство того, что этот алгоритм удовлетворяет условиям 1 – 5, проделайте самостоятельно в качестве упражнения.

Аппаратная поддержка взаимоисключений

Многие вычислительные системы помимо этого имеют специальные команды процессора, которые позволяют проверить и изменить значение машинного слова или…

Команда Test-and-Set (Проверить и присвоить 1)

int Test_and_Set (int *target){ int tmp = *target; *target = 1; return tmp; }

Critical section

lock = 0;

Remainder section

}

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

Команда Swap (Обменять значения)

void Swap (int *a, int *b){ int tmp = *a; *a = *b; *b = tmp; }

Critical section

lock = 0;

Remainder section

}

Резюме

Последовательное выполнение некоторых действий, направленных на достижение определенной цели, называется активностью. Активности состоят из атомарных операций, выполняемых неразрывно, как единичное целое. При исполнении нескольких активностей в псевдопараллельном режиме атомарные операции различных активностей могут перемешиваться между собой с соблюдением порядка следования внутри активностей. Это явление получило название interleaving (чередование). Если результаты выполнения нескольких активностей не зависят от варианта чередования, то этот набор активностей называется детерминированным. В противном случае он носит название недетерминированного. Существует достаточное условие Бернстайна для определения детерминированности набора активностей, но оно накладывает очень жесткие ограничения на набор, требуя практически не взаимодействующих активностей. Про недетерминированный набор активностей говорят, что он имеет race condition (условие гонки, состязания). Устранение race condition возможно при ограничении допустимых вариантов чередований атомарных операций с помощью синхронизации поведения активностей. Участки активностей, выполнение которых может привести к race condition, называют критическими участками. Необходимым условием для устранения race condition является организация взаимоисключения на критических участках: внутри соответствующих критических участков не может одновременно находиться более одной активности.

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

Применение специальных команд процессора, выполняющих ряд действий как атомарную операцию, - Test-And-Set, Swap – позволяет существенно упростить алгоритмы, удовлетворяющие оставшимся условиям.

Глава 6. Механизмы синхронизации

Рассмотренные в конце предыдущей главы алгоритмы хотя и являются корректными, но достаточно громоздки и не обладают элегантностью. Более того, процедура ожидания входа в критический участок включает в себя достаточно длительное вращение процесса в пустом цикле, вхолостую пожирая драгоценное время процессора. Существуют и другие серьезные недостатки у алгоритмов, построенных средствами обычных языков программирования. Допустим, что в вычислительной системе находятся два взаимодействующих процесса: один из них — H — с высоким приоритетом, другой —L — с низким приоритетом. Пусть планировщик устроен так, что процесс с высоким приоритетом вытесняет низкоприоритетный процесс всякий раз, когда он готов к исполнению, и занимает процессор на все время своего CPU burst (если не появится процесс с еще большим приоритетом). Тогда в случае, когда процесс L находится в своей критической секции, а процессH, получив процессор, подошел ко входу в критическую область, мы получаем тупиковую ситуацию. Процесс Hне может войти в критическую область, находясь в цикле, а процессL не получает управления, чтобы покинуть критический участок.

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

Семафоры

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

Концепция семафоров

Эта запись означает следующее: при выполнении операции P над семафором S сначала проверяется его значение. Если оно больше 0, то из S вычитается1.… Подобные переменные-семафоры могут быть с успехом применены для решения…

Решение проблемы producer-consumer с помощью семафоров

Если буфер забит, то производитель должен ждать, пока в нем появится место, чтобы положить туда новую порцию информации. Если буфер пуст, то… Semaphore mutex = 1; Semaphore empty = N, где N – емкость буфера; Semaphore… Producer:

Мониторы

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

Сообщения

send(P, message)—послать сообщение message процессу P; receive(Q, message) — получить сообщение message от процесса Q. В случае непрямой адресации мы будем обозначать их так: send(A, message) — послать сообщение message в почтовый ящикA; receive(A, message) — получить сообщение message из…

Эквивалентность семафоров, мониторов и сообщений

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

Реализация мониторов и передачи сообщений с помощью семафоров

Для выполнения операции wait над условной переменной компилятор будет генерировать вызов функции wait, которая выполняет операцию V для семафора… Semaphore mutex = 1; void monitor_enter(){

Реализация семафоров и передачи сообщений с помощью мониторов

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

Реализация семафоров и мониторов с помощью очередей сообщений

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

Резюме

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

 

Глава 7. Тупики

Введение

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

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

Рис. 7.1. Пример тупиковой ситуации.

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

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

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

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

Концепция ресурса

Как устройства, так и данные могут являться ресурсами. Некоторые виды ресурсов допускают разделение между процессами, то есть… Последовательность событий, требуемых для использования ресурса такова: запросить (request) ресурс, …

Условия возникновения тупиков

1. Условие взаимоисключения (Mutual exclusion). Каждый ресурс выделен в точности одному процессу или доступен. Процессы требуют предоставления им… 2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают за собой… 3. Условие неперераспределяемости (No preemtion). Ресурс, данный ранее, не может быть принудительно забран у процесса.…

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

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

Основные направления борьбы с тупиками:

1. Игнорировать данную проблему
2. Обнаружение тупиков
3. Восстановление после тупиков
4. Предотвращение тупиков за счет тщательного выделения ресурсов или нарушения одного из условий возникновения тупиков.

Алгоритм страуса

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

Обнаружение тупиков

Рассмотрим модельную ситуацию: Процесс A удерживает ресурс R и ожидает ресурс S. Процесс B претендует на ресурс T. Процесс C претендует на… Вопрос состоит в том, является ли данная ситуация тупиковой, и если да, то…

Восстановление после тупиков

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

Восстановление при помощи перераспределения ресурсов

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

Восстановление через откат назад

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

Восстановление через ликвидацию одного из процессов

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

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

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

Предотвращение тупиков и алгоритм банкира.

определенных правил. Наиболее известен среди алгоритмов такого рода - алгоритм банкира, предложенный Дейкстрой. Он, как бы имитирует действия… Предположим, что у системы в наличии n устройств, например лент. Суть… Рассмотрим пример надежного состояния для системы с тремя пользователями и 12-ю устройствами, где 10 устройств…

Недостатки алгоритма банкира

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

Предотвращение тупиков за счет нарушения условий возникновения тупиков.

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

Нарушение условия взаимоисключения

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

Hарушение условия ожидания дополнительных ресурсов

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

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

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

Нарушение условия кругового ожидания

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

Родственные проблемы

Двухфазная локализация

Если в первой фазе некоторые записи, которые ему нужны, уже локализованы, процесс освобождает все, что он локализовал и пытается повторить первую…

Тупики не ресурсного типа

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

Голод (starvation)

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

Заключение.

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

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

Считается, что в будущих системах тупики станут более критичным фактором, так как системы будущего:

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

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

Более подробно данная тема рассмотрена в [9,12,22 и др.]

Часть III. Управление памятью.

Глава 8. Введение. Простейшие схемы управления памятью.

Введение.

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

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

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

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

И, наконец, идея локальности. Свойство локальности присуще природе. Пространственная локальность - соседние объекты характеризуются похожими свойствами (если в данной местности хорошая погода, то вероятнее всего, что в близкой окрестности также хорошая погода). Временная локальность - если в 15:00 была хорошая погода, то, вероятно, что и в 14:30 и в 15:30 также наблюдалась хорошая погода. Свойство локальности (скорее эмпирическое) присуще и работе ОС. Фактически свойство локальности объяснимо, если учесть, как пишутся программы и организованы данные, то есть обычно в течение какого-то отрезка времени ограниченный фрагмент кода работает с ограниченным набором данных. Понимание данной особенности позволяет организовать иерархию памяти, используя быструю дорогостоящую память для хранения минимума необходимой информации, размещая оставшуюся часть данных на устройствах с более медленным доступом и подкачивая их в быструю память по мере необходимости. Типичный пример иерархии: регистры процессора, кэш процессора, главная память, внешняя память на магнитных дисках (вторичная память).

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

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

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

• Механизм управления памятью или идеологию построения системы управления.
• Архитектурные особенности используемой системы.
• Структуры данных в ОС, используемые для управления памятью.
• Алгоритмы, используемые для управления памятью.

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

Связывание адресов.

Как уже упоминалось в разделе 8.1, адреса, с которыми имеет дело менеджер памяти, бывают логические (виртуальные для систем с виртуальной памятью) и… Пользовательская программа не видит реальных физических адресов, а имеет дело…  

Простейшие схемы управления памятью.

Схема с фиксированными разделами.

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

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

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

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

Эта схема была реализована в IBM OS/360 (MFT) и в DEC RSX-11.

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

В какой раздел помещать программу? Распространены три стратегии:

· Стратегия первого подходящего (First fit). Задание помещается в первый подходящий по размеру раздел.

· Стратегия наиболее подходящего (Best fit). Задание помещается в тот раздел, где ему наиболее тесно.

· Стратегия наименее подходящего (Worst fit). При помещении в самый большой раздел в нем остается достаточно места для возможного размещения еще одного процесса.

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

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

Очевидный недостаток этой схемы число одновременно выполняемых процессов ограничено числом разделов.

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

8.3.1.1 Один процесс в памяти

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

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

8.3.1.2 Оверлейная структура

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

Потребность в таком способе загрузки появляется, если логическое адресное пространство системы мало, например 1 мегабайт (MS-DOS) или даже всего 64 килобайта (PDP-11), а программа относительно велика. На современных 32-разрядных системах, где виртуальное адресное пространство измеряется гигабайтами, проблемы с нехваткой памяти решаются другими способами (см. раздел Виртуальная память).

Рис 8.3 . Организация структуры с перекрытием. Можно поочередно загружать в память ветви A-B, A-C-D и A-C-E программы.

Коды ветвей оверлейной структуры программы находятся на диске как абсолютные образы памяти и считываются драйвером оверлеев при необходимости. Для конструирования оверлеев необходимы специальные алгоритмы перемещения и связывания. Для описания оверлейной структуры обычно используется специальный несложный язык (overlay description language). Совокупность файлов исполняемой программы дополняется файлом (обычно с расширением .odl), описывающим дерево вызовов внутри программы. Например, для примера, приведенного на рис. 8.3 , текст этого файла может выглядеть так:

A-(B,C)

C-(D,E)

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

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

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

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

Свопинг

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

Мультипрограммирование с переменными разделами.

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

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

Рис. 8.4 Динамика распределения памяти между процессами. Серым цветом показана неиспользуемая память.

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

Этот метод более гибок по сравнению с методом фиксированных разделов

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

В зависимости от суммарного размера памяти и среднего размера процесса эта проблема может быть большей или меньшей. Статистический анализ показывает, что при наличии n блоков пропадает n/2 блоков, то есть 1/3 памяти! Это известное 50% правило (два соседних свободных участка в отличие от двух соседних процессов могут быть объединены в один).

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

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

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

Резюме

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

Проблема размещения больших программ. Понятие виртуальной памяти.

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

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

Итак, мы имеем большое (для 32-разрядных архитектур это обычно 2**32 = 4 Гб) виртуальное адресное пространство и физическое пространство существенно… Таким образом, важный компонент менеджера виртуальной памяти система или…

Страничная память

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

Сегментная и сегментно-страничная организации памяти

С точки зрения пользователя процесс представляется обычно не как линейный массив байтов, а как набор сегментов переменного размера (данные, код,… Программисты, пишущие на языках низкого уровня должны иметь представление о… Каждый сегмент - линейная последовательность адресов от 0 до максимума. Различные сегменты могут иметь различные…

Таблица страниц

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

Итак, виртуальный адрес состоит из виртуального номера страницы (high-order bits) и смещения (low-order bits). Номер виртуальной страницы используется как индекс в таблице страниц для нахождения записи (entry) о виртуальной странице. Из этой записи в таблице страниц находится номер кадра (page frame number), затем прибавляется смещение и формируется физический адрес. Помимо этого запись в таблице страниц содержит информацию об атрибутах страницы, в частности биты защиты.

Основную проблему для эффективной реализации таблицы страниц создают большие размеры виртуальных адресных пространств современных компьютеров, которые обычно определяются разрядностью архитектуры процессора. Самыми распространенными на сегодняшний день являются 32-разрядные процессоры, позволяющие создавать виртуальные адресные пространства такого размером 4 Гб (для 64-разрядных компьютеров эта величина равна 2**64б).

Подсчитаем примерный размер таблицы страниц. В 32-битном адресном пространстве при размере страницы 4К (Intel) получаем 1М страниц, а в 64-битном и того более. Т.о. таблица должна иметь 1М строк (entry), причем запись в строке состоит из нескольких байт. Заметим, что каждый процесс, нуждается в своей таблице страниц (а в случае сегментно-страничной схемы по одной на каждый сегмент). Итак, в этом случае таблица страниц может быть слишком большой.

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

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

Рассмотрим модельный пример (см. рис. 9.4). Предположим, что 32-разрядный адрес делится на 10-разрядное поле Рtr1, 10-разрядное поле Рtr2 и 12-разрядное смещение Offset. 12 разрядов смещения позволяют локализовать байт внутри страницы размером 4К (2**12), а всего имеем 2**20 страниц. Как видно из рис. 9.4 1024 строки в таблице верхнего уровня при помощи поля Ptr1 ссылаются на 1024 таблицы второго уровня, каждая из которых содержит также 1024 строки. При помощи поля Ptr2 каждая строка таблицы второго уровня указывает на конкретную страницу. Смысл такой организации в том, чтобы избежать поддержки всех таблиц второго уровня (а их 1024) в памяти постоянно. Рассмотрим пример с круглыми цифрами. Допустим, что процессу нужны 12М памяти: 4М в нижней части памяти для кода, 4М в нижней части для данных и 4М в верхней части памяти для стека. Между дном стека и верхом данных гигантское пространство размером 4Gb-12Mb, которое не используется. Для этого случая необходимы лишь 1 таблица верхнего уровня и 3 таблицы второго уровня.

Рис. 9.4 Пример двухуровневой таблицы страниц.

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

Рассмотрим одну из записей таблицы страниц. Ее размер колеблется от системы к системе, но 32 бита - наиболее общий случай. Самое важное поле - номер кадра. Цель страничного отображения - локализовать эту величину. Далее бит присутствия. Далее биты защиты (например, 0 - read/write, 1 - read only ...) Есть еще биты модификации (если на нее писали) и биты ссылки, которые помогают выделить мало используемые страницы, биты разрешающие кэширование. Заметим, что адреса страниц на диске не являются частью таблицы страниц.

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

Количество уровней в таблице страниц зависит от конкретных особенностей архитектуры. Можно привести примеры реализации одноуровневого (DEC PDP-11), двухуровневого (Intel, DEC VAX), трехуровневого (Sun SPARC, DEC Alpha) paging'а, а также paging'а с задаваемым количеством уровней (Motorola). Функционирование RISC процессора MIPS R2000 осуществляется вообще без таблицы страниц. Здесь поиск нужной страницы, если эта страница отсутствует в ассоциативной памяти, должна взять на себя ОС (так называемый zero level paging).

Ассоциативная память.

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

Иерархия памяти

Рассмотренная нами схема трехуровневой памяти (ассоциативная, основная, вторичная) является частным случаем многоуровневой памяти. Например, как… . Рис. 9.5 Иерархия памяти компьютера

Размер страницы

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

Глава 10. Аппаратно-независимый уровень управления виртуальной памятью

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

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

Исключительные ситуации при работе с памятью.

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

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

Стратегия выборки (fetch policy) - в какой момент следует переписать страницу из вторичной памяти в первичную. Выборка бывает по запросу и с… Существует модификация алгоритма выборки, которая применяет еще и опережающее… Стратегия размещения (placement policy) - определить в какое место первичной памяти поместить поступающую страницу. В…

Алгоритмы замещения страниц

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

FIFO алгоритм. Выталкивание первой пришедшей страницы.

Аномалия Belady

Три кадра (9 faults) оказываются лучше чем 4 кадра (10 faults) для 012301401234 цепочки чередования страниц при выборе стратегии FIFO. Рис. 10.1 Аномалия Belady. (a) FIFO с тремя страничными кадрами. (b) FIFO с четырьмя страничными кадрами.

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

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

Выталкивание дольше всего не использовавшейся страницы. LRU (The Least Recently Used) Algorithm .

Ключевое отличие между FIFO и оптимальным алгоритмом в том, что один смотрит назад, а другой вперед. Если использовать прошлое, для аппроксимации… LRU часто используется и считается хорошим. Основная проблема - реализация. … Необходимо иметь связанный список всех страниц в памяти, в начале которого будут часто используемые страницы.

Выталкивание редко используемой страницы. NFU (Not Frequently Used) алгоритм.

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

Другие алгоритмы

Например, алгоритм Second-Chance - модификации FIFO, которая позволяет избежать потери часто используемых страниц - анализ бита r (reference) для… В компьютере Макинтош использован алгоритм NRU(Not Recently-Used), где… Имеется также и много других алгоритмов замещения. Объем этого курса не позволяет рассмотреть их подробно. Подробное…

Thrashing. Свойство локальности. Модель рабочего множества.

Хотя теоретически возможно уменьшить число кадров процесса до минимума, существует какое-то число активно используемых страниц, без которого процесс… Рис. 10.2 Частота page fault'ов

Концепция локальности

Модель локальности состоит в том, что когда процесс выполняется, он двигается от одной локальности к другой. Локальность - набор страниц, которые… Если процессу выделять меньше кадров, чем ему нужно для поддержки его…

Модель рабочего множества (Working Set)

В некотором смысле предложенный Деннингом подход является практически реализуемой аппроксимацией оптимального алгоритма (см. также [28]. Принцип… Наиболее важное свойство рабочего множества - его размер. ОС выделяет каждому… Решение о размещении процессов в памяти должно, следовательно, базироваться на размере его рабочего множества. Для…

Демоны пейджинга

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

Аппаратно-независимая модель памяти процесса.

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

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

Имеется также несколько описательных структур на уровне страниц. Так для управления физической памятью поддерживается несколько списков страниц:… Введение подобной обобщенной модели организации виртуальной памяти и… Загрузка исполняемого файла (системный вызов exec) осуществляется обычно через отображение (mapping) его частей (кода,…

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

В ряде случаев поддержка страничной системы приводит к необходимости разрешить некоторым страницам быть локализованными в памяти. Факт наличия виртуальной памяти не означает, что ввод-вывод отсутствует. Они… Одно из решений данной проблемы - вводить данные в невытесняемый буфер в пространстве ядра. А затем копировать их в…

Заключение

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

Часть IV. Файловые системы

Глава 11. Файлы с точки зрения пользователя

Введение

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

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

Основная идея использования внешней памяти состоит в следующем. ОС делит ее на блоки фиксированного размера, например, 4096 байт. С точки зрения пользователя каждый файл состоит из набора индивидуальных элементов, называемых записями (например, характеристика какого-нибудь объекта). Каждый файл хранится в виде определенной последовательности блоков (не обязательно смежных); каждый блок хранит целое число записей. В некоторых ОС (MS-DOS) адреса блоков, содержащих данные файла, могут быть организованы в связный список и вынесены в отдельную таблицу в памяти. В других ОС (Unix), адреса блоков данных файла хранятся в отдельном блоке внешней памяти (так называемом индексе или индексном узле). Этот прием называется индексацией и является наиболее распространенным для приложений, требующих произвольного доступа к записям файлов. Индекс файла состоит из списка элементов, каждый из которых содержит номер блока в файле и указание о местоположении данного блока. В современных ОС файлы обычно представляют собой неструктурированную последовательность байтов (длина записи равна 1) и считывание очередного байта осуществляется с так называемой текущей позиции, которая характеризуется смещением от начала файла. Зная размер блока, легко вычислить номер блока, содержащего текущую позицию. Адрес же нужного блока диска можно затем извлечь из индекса файла. Базовой операцией, выполняемой по отношению к файлу, является чтение блока с диска и перенос его в буфер, находящийся в основной памяти.

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

Понятие «файловая система» включает [30]:

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

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

Перечислим основные функции файловой системы:

1. Идентификация файлов. Связывание имени файла с выделенным ему пространством внешней памяти.
2. Распределение внешней памяти между файлами. Для работы с конкретным файлом не требуется иметь информацию о местоположении этого файла на внешнем носителе информации. Например, для того, чтобы загрузить документ в редактор с жесткого диска нам не требуется знать на какой стороне какого магнитного диска и на каком цилиндре и в каком секторе находится требуемый документ.
3. Обеспечение надежности и отказоустойчивости. Стоимость информации может во много раз превышать стоимость компьютера.
4. Обеспечение защиты от НСД.
5. Обеспечение совместного доступа к файлам, не требуя от пользователя специальных усилий по обеспечению синхронизации доступа.
6. Обеспечение высокой производительности.

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

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

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

Имена файлов

Многие ОС поддерживают имена из двух частей (имя+расширение), например progr.c(файл, содержащий текст программы на языке Си) или autoexec.bat (файл,… Обычно ОС накладывают некоторые ограничения, как на используемые в имени…

Структура файлов

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

Типы и атрибуты файлов

К типам файлов, поддерживаемых современными ОС, относят регулярные (обычные) файлы и директории. Обычные (регулярные) файлы содержат… Напомним, что хотя внутри подсистемы управления файлами обычный файл… Далее, главным образом, речь пойдет об обычных файлах.

Доступ к файлам

Ранние ОС давали только один способ доступа – последовательный(модель ленты). Записи считывались в порядке поступления. Текущая позиция считывания… Последовательный доступ базируется на модели ленты и работает как на… Не все системы поддерживают оба (последовательный и прямой) метода доступа. Последовательный доступ легко эмулировать…

Операции над файлами.

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

• Create. Создание файла, не содержащего данных. Смысл данного вызова - объявить, что файл существует и присвоить ему ряд атрибутов.
• Delete. Удаление файла и освобождение занятого им дискового пространства.
• Open. Перед использованием файла процесс должен его открыть. Цель данного системного вызова разрешить системе проанализировать атрибуты файла и проверить права доступа к файлу, а также считать в оперативную память список адресов блоков файла для быстрого доступа к его данным.
• Close. Если работа с файлом завершена, его атрибуты и адреса блоков на диске больше не нужны. В этом случае файл нужно закрыть, чтобы освободить место во внутренних таблицах файловой системы.
• Seek. Дает возможность специфицировать место внутри файла, откуда будет производиться считывание (или запись) данных, то есть задать текущую позицию.
• Read. Чтение данных из файла. Обычно это происходит с текущей позиции. Пользователь должен задать объем считываемых данных и предоставить буфер для них.
• Write. Запись данных в файл с текущей позиции. Если текущая позиция находится в конце файла, его размер увеличивается, в противном случае запись осуществляется на место имеющихся данных, которые, таким образом, теряются.
• Get attributes. Предоставляет процессам нужные им сведения об атрибутах файла. В качестве примера можно привести, утилиту make, которая использует информацию о времени последней модификации файлов.
• Set attributes. Дает возможность пользователю установить некоторые атрибуты. Наиболее очевидный пример - установка режима доступа к файлу.
• Rename. Возможность переименования файла создает дополнительные удобства для пользователя. Данная операция может быть смоделирована копированием данного файла в файл с новым именем и последующим его удалением.

Существует два способа выполнить последовательность действий над файлами [30]:

В первом случае для каждой операции выполняются как универсальные, так и уникальные действия (схема stateless). Например, последовательность операций может быть такой: open, read1, close, … open, read2, close, … open, read3, close.

Альтернативный способ, это когда универсальные действия выполняются в начале и в конце последовательности операций, а для каждой промежуточной операции выполняются только уникальные действия. В этом случае последовательность вышеприведенных операций будет выглядеть так: open, read1, … read2, … read3, close.

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

Директории. Логическая структура файлового архива.

Каждый каталог содержит список каталогов и/или файлов, содержащихся в данном каталоге. Каталоги имеют один и тот же внутренний формат, где каждому… Рис. 11.3 Директории. (а) Атрибуты внутри записи в директории. (б) Атрибуты в другой структуре

Операции над директориями

Так же, как и в случае файлов, система обязана обеспечить пользователя набором операций, необходимых для работы с директориями, реализованных через системные вызовы. Несмотря на то, что директории, это файлы, логика работы с ними отличается от логики работы с обычными файлами и определяется природой этих объектов, предназначенных поддерживать структуру файлового архива. Совокупность системных вызовов для управления директориями зависит от особенностей конкретной ОС. Рассмотрим в качестве примера некоторые системные вызовы ОС Unix.

• Create. Создание директории. Вновь созданная директория включает записи с именами '.' и '..', однако считается пустой.
• Delete. Удаление директории. Удалена может быть только пустая директория.
• Opendir. Открытие директории для последующего чтения. Например, чтобы перечислить файлы, входящие в директорию, процесс должен открыть директорию и считать имена всех файлов, которые она включает.
• Closedir. Закрытие директории после ее чтения для освобождения места во внутренних системных таблицах.
• Readdir. Данный системный вызов возвращает содержимое текущей записи в открытой директории. Вообще говоря, для этих целей может быть использован системный вызов Read, но в этом случае от программиста потребуется знание внутренней структуры директории. Readdir возвращает содержимое записи в стандартном формате, независимо от используемой структуры директорий.
• Rename. Имена директорий можно менять, также как и имена файлов.
• Link. Связывание - это техника, которая позволяет информации о файле появляться более чем в одной директории. Данный системный вызов связывает существующий файл с абсолютным именем директории, используя их в качестве параметров. При помощи вызова Link можно связать файл сразу с несколькими директориями.
• Unlink. Удаление записи о файле из директории. Если удаляемый файл присутствует только в одной директории, то он вообще удаляется из файловой системы, в противном случае система ограничивается только удалением специфицируемой записи.

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

Защита файлов.

Общие проблемы безопасности ОС рассмотрены в гл. 15-16. Информация в компьютерной системе должна быть защищена как от физического разрушения (reliability), так и от несанкционированного доступа (protection).

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

Контроль доступа к файлам

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

Списки прав доступа

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

Резюме

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

Глава 12. Реализация файловой системы

Интерфейс файловой системы.

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

Общая структура файловой системы

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

Структура файловой системы на диске.

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

Методы выделения дискового пространства

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

Управление свободным и занятым дисковым пространством.

Учет при помощи организации битового вектора. Часто список свободных блоков диска реализован в виде битового вектора (bit… Главное преимущество этого подхода - он относительно прост и эффективен при нахождении первого свободного блока, или n…

Размер блока

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

Структура файловой системы на диске

Рис. 12.6 Примерная структура файловой системы на диске. В начале раздела находится суперблок, содержащий общее описание файловой системы, например: Тип файловой системы…

Реализация директорий

Для доступа к файлу ОС использует путь (pathname), сообщенный пользователем. Запись в директории связывает имя файла или имя поддиректории с блоками… Отдельная проблема способ хранения атрибутов файла. Иногда их хранят… Рассмотрим несколько конкретных примеров.

Примеры реализация директорий в некоторых ОС

Директории в ОС CP/M

В ОС CP/M только одна директория.

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

Директории в ОС MS-DOS

В ОС MS-DOS типовая запись в директории имеет вид:

Рис. 12.7 Вариант записи в директории MS-DOS

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

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

Директории в ОС Unix

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

Рис. 12.8 Вариант записи в директории Unix

Поиск в директории

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

Монтирование файловых систем.

Функция mount (монтировать) связывает файловую систему из указанного раздела на диске с существующей иерархией файловых систем, а функция umount… Процедура монтирования состоит в следующем. Пользователь (в Unix это… mount(special pathname,directory pathname,options);

Связывание файлов.

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

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

Рис. 12.11 Структура файловой системы с возможностью связывания файла с новым именем.

Ядро позволяет пользователю связывать каталоги, упрощая написание программ, требующих пересечения дерева файловой системы. Часто имеет смысл хранить под разными именами одну и ту же команду (выполняемый файл). Например, выполняемый файл традиционного текстового редактора ОС UNIX vi обычно может вызываться под именами ex, edit, vi, view и vedit файловой системы. Соединение между директорией и разделяемым файлом называется связью или ссылкой (link). Дерево файловой системы превращается в циклический граф.

Это удобно, но создает ряд дополнительных проблем.

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

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

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

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

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

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

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

Кооперация процессов при работе с файлами.

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

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

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

Рассмотрим в качестве примера образование потенциального тупика при образовании связи (link) при совместном доступе к файлу [1].

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

процесс A: link("a/b/c/d","e/f/g");

процесс B: link("e/f","a/b/c/d/ee");

могут зайти в тупик. Предположим, что процесс A обнаружил индекс файла "a/b/c/d" в тот самый момент, когда процесс B обнаружил индекс файла "e/f". Фраза "в тот же самый момент" означает, что система достигла состояния, при котором каждый процесс получил искомый индекс. Когда же теперь процесс A попытается получить индекс файла "e/f", он приостановит свое выполнение до тех пор, пока индекс файла "f" не освободится. В то же время процесс B пытается получить индекс каталога "a/b/c/d" и приостанавливается в ожидании освобождения индекса файла "d". Процесс A будет удерживать заблокированным индекс, нужный процессу B, а процесс B, в свою очередь, будет удерживать заблокированным индекс, нужный процессу A.

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

Поводов для нежелательной конкуренциимежду процессами много, особенно при удалении имен каталогов. Предположим, что один процесс пытается найти данные файла по его полному символическому имени, последовательно проходя компонент за компонентом, а другой процесс удаляет каталог, имя которого входит в путь поиска. Допустим, процесс A делает разбор имени "a/ b/c/d" и приостанавливается во время получения индексного узла для файла "c". Он может приостановиться при попытке заблокировать индексный узел или при попытке обратиться к дисковому блоку, где этот индексный узел хранится. Если процессу B нужно удалить связь для каталога с именем "c", он может приостановиться по той же самой причине, что и процесс A. Пусть ядро впоследствии решит возобновить процесс B раньше процесса A. Прежде чем процесс A продолжит свое выполнение, процесс B завершится, удалив связь каталога "c" и его содержимое по этой связи. Позднее, процесс A попытается обратиться к несуществующему индексному узлу, который уже был удален. Алгоритм поиска файла, проверяющий в первую очередь неравенство значения счетчика связей нулю, должен сообщить об ошибке.

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

Надежность файловой системы.

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

Целостность файловой системы.

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

Управление плохими блоками.

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

Производительность файловой системы

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

Реализация некоторых операций над файлами.

В предыдущей главе перечислены основные операции над файлами. В данном разделе будет описан порядок работы некоторых системных вызовов для работы с файловой системой, следуя главным образом [1], с учетом совокупности введенных в данной главе понятий.

Системные вызовы, работающие с символическим именем файла.

Это функции создания и открытия файла. Например, в ОС Unix fd = creat(pathname,modes); fd = open(pathname,flags,modes);

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

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

Современные архитектуры файловых систем

На верхнем уровне, на котором располагается так называемый диспетчер файловых систем (например, в Windows 95 этот компонент называется installable… Рис. 12.13 Архитектура современной файловой системы

Резюме

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

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

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

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

Часть V. Ввод-вывод

Глава 13. Система управления вводом-выводом

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

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

Рассмотрение того, что именно делает процессор при обработке информации, как он решает задачу и какой алгоритм выполняет, не входит в задачи нашего курса. Это скорее относится к курсу “Алгоритмы и структуры данных”, с которого обычно начинается изучение информатики. Как операционная система управляет обработкой информации, мы разобрали в части II, в деталях описав два состояния процессов – исполнение (а что его описывать то?) и готовность (очереди планирования и т.д.), а также правила, по которым осуществляется перевод процессов из одного состояния в другое (алгоритмы планирования процессов).

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

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

Физические принципы организации ввода-вывода.

Общие сведения об архитектуре компьютера.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. После выполнения действий 1 и 2 на шину управления выставляются сигналы, соответствующие операции записи и работе с устройствами ввода-вывода (переключение адресных пространств!), что приведет к передаче необходимой информации в требуемый порт.

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

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

§ Устройства ввода-вывода подключаются к системе через порты.

§ Могут существовать два адресных пространства: пространство памяти и пространство ввода-вывода.

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

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

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

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

Структура контроллера устройства.

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

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

1. Процессор в цикле читает информацию из порта регистра состояний и проверяет значение бита занятости. Если бит занятости установлен, то это… 2. Процессор записывает код команды вывода в порт регистр управления. 3. Процессор записывает данные в порт регистра входных данных.

Логические принципы организации ввода-вывода.

Структура системы ввода-вывода.

§ Скорость обмена информацией может варьироваться в диапазоне от нескольких байт в секунду (клавиатура) до нескольких гигабайт в секунду (сетевые… § Некоторые устройства могут быть использованы параллельно несколькими… § Устройства могут запоминать выведенную информацию для ее последующего ввода или не обладать этой функцией.…

Систематизация внешних устройств и интерфейс между базовой подсистемой ввода-вывода и драйверами.

§ символьные (клавиатура, модем, терминал и т.п.); § блочные (магнитные и оптические диски и ленты, и т.д.); § сетевые (сетевые карты);

Функции базовой подсистемы ввода-вывода.

Блокирующиеся, не блокирующиеся и асинхронные системные вызовы.

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

Буферизация и кэширование.

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

Spooling и захват устройств.

Рассмотрим в качестве внешнего устройства принтер. Хотя принтер не может печатать информацию, поступающую одновременно от нескольких процессов,… В некоторых операционных системах вместо использования spooling’а для… Обеспечение spooling’а и механизма захвата устройств является прерогативой базовой подсистемы ввода-вывода.

Обработка прерываний и ошибок.

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

Планирование запросов.

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

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

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

Строение жесткого диска и параметры планирования.

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

Алгоритм First Come First Served (FCFS)

63->23->67->55->14->31->7->84->10 и всего головки переместятся на 329 цилиндров. Неэффективность алгоритма…

Алгоритм Short Seek Time First (SSTF).

63->67->55->31->23->14->10->7->84 и всего головки переместятся на 141 цилиндр. Заметим, что наш алгоритм похож… Точный алгоритм SJF являлся оптимальным для заданного набора процессов с заданными временами CPU burst. Легко видеть,…

Алгоритмы сканирования (SCAN, C-SCAN, LOOK, C-LOOK)

63->55->31->23->14->10->7->0->67->84 и всего головки переместятся на 147 цилиндров. Если мы знаем, что обслужили последний попутный запрос в направлении движения головок, то мы можем не доходить до края…

Резюме.

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

Часть VII. Проблемы безопасности операционных систем.

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

Юджин Х. Спаффоpд

Глава 15. Основные понятия информационной безопасности.

Введение

В октябре 1988 г. в США произошло событие, названное специалистами крупнейшим нарушением безопасности амеpиканских компьютеpных систем из когда-либо случавшихся. 23-летний студент выпускного куpса Коpнеллского унивеpситета Робеpт Таппан Моppис запустил в компьютеpной сети ARPANET пpогpамму; пpедставлявшую собой pедко встpечающуюся pазновидность компьютеpных виpусов - сетевых чеpвей. В pезультате атаки был полностью или частично заблокиpован pяд общенациональных компьютеpных сетей, в частности Internet, CSnet, NSFnet, BITnet, ARPANET и несекpетная военная сеть Milnet. В итоге виpус поpазил более 6200 компьютеpных систем по всей Амеpике, включая системы многих кpупнейших унивеpситетов, институтов, пpавительственных лабоpатоpий, частных фиpм, военных баз, клиник, агентства NASA. Общий ущеpб от этой атаки оценивается специалистами минимум в 100 миллионов доллаpов. Р. Моppис был исключен из унивеpситета с пpавом повтоpного поступления чеpез год, и пpиговоpен судом к штpафу в 270 тыс.долл. и тpем месяцам тюpемного заключения.

Важность решения проблемы информационной безопасности в настоящее время общепризнанна, свидетельством чему служат громкие процессы о нарушении целостности систем. Убытки ведущих компаний США в связи с нарушениями безопасности информации в период с 1997 по 1999 годы составили $360'720'555. Причем только 31% опрошенных компаний смог определить количественно размер потерь. Проблема обеспечения безопасности носит комплексный характер, для ее решения необходимо сочетание законодательных, организационных и программно-технических мер.

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

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

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

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

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

Введем еще несколько понятий (см. также [30]).

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

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

Доступность (availability) гарантия того, что авторизованные пользователи всегда получат доступ к данным.

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

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

Классификация угроз

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

Общей классификации угроз не существует. Имеет смысл различать неумышленные и умышленные угрозы.

Неумышленные угрозы связаны с:

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

Умышленные угрозы, в отличие от случайных, преследуют цель нанесения ущерба пользователям ОС и, в свою очередь, подразделяются на активные и пассивные. Пассивная угроза - несанкционированный доступ к информации без изменения состояния системы, активная - несанкционированное изменение системы. Можно выделить следующие типы угроз [30] :

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

Типизация угроз не слишком строгая.

А.Таненбаум [12] приводит свой список наиболее успешных атак на ОС:

• Попытки чтения страниц памяти, дисков и лент, которые сохранили информацию предыдыдущего пользователя.
• Попытки выполнения нелегальных системных вызовов, или системных вызовов с нелегальными параметрами
• Внедрение программы, которая выводит на экран слово login . Многие легальные пользователи, видя такое, начинают пытаться входить в систему, и их попытки могут протоколироваться (вариант Троянского коня).
• Попытки торпедировать программу проверки входа в систему путем многократного нажатия клавиш del, break, rubout, cancel и.т.д. В некоторых системах проверочная программа погибает, и вход в систему становится возможным.
• Подкуп персонала. Hапример, малооплачиваемого секретаря.
• Использование закладных элементов (дыр), специально оставленных дизайнерами системы.
• И т.д.

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

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

Формализация подхода к обеспечению информационной безопасности. Классы безопасности

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

• оранжевая (по цвету обложки) книга МО США [2]
• гармонизированные критерии европейских стран [3]
• руководящие документы Гостехкомиссии при Президенте РФ [17-21]
• рекомендации X.800 по защите распределенных систем [7]
• федеральный закон Об информации, информатизации и защите информации.
• и др.

Основополагающие документы открыли путь к ранжированию информационных систем по степени надежности. Так, в Оранжевой книге определяется четыре уровня безопасности - D , С , В и А. По мере перехода от уровня D до А к надежности систем предъявляются все более жесткие требования. Уровни С и В подразделяются на классы (C1, С2, В1, В2, ВЗ). Чтобы система в результате процедуры сертификации могла быть отнесена к некоторому классу, ее политика безопасности и гарантированность должны удовлетворять оговоренным требованиям.

В качестве примера рассмотрим требования класса C2, которому удовлетворяют некоторые популярные ОС (Windows NT, отдельные реализации Unix и др.):

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

Политика безопасности

В дальнейшем мы будем оперировать понятиями субъект и объект безопасности. Субъект безопасности - активная, а объект - пассивная системные… Формируя политику безопасности необходимо учитывать несколько базовых… Можно добавить еще ряд, например [30]: Принцип комплексного подхода, баланс надежности защиты всех уровней …

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

Шифрование процесс изменения цифрового сообщения из открытого текста (plaintext) в шифротекст (ciphertext) таким образом, чтобы его могли прочитать… В алгоритмах шифрования предусматривается наличие секретного ключа и принято… В методе шифрования с секретнымили симметричнымключом имеется один ключ, который используется как для шифрования, так…

Лекция 16. Защитные механизмы операционных систем.

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

Идентификация и аутентификация

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

Пароли, уязвимость паролей

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

Шифрование пароля

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

Авторизация. Разграничение доступа к объектам ОС

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

Домены безопасности

Рис. 16.1 Специфицирование прав доступа к ресурсам. Связь процессов с доменами может быть статической и динамической. Организация динамической связи сложнее.

Матрица доступа

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

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

Список прав доступа. Access control list.

Список прав доступа может быть дополнен дефолтным набором прав. Пример Unix. Все субъекты разделены на три группы, для членов каждой группы…

Capability list

Примерами систем такого рода являются Hydra, Cambridge CAP System. Иногда применяется комбинированный способ. Например, в том же Unix на этапе… Существуют другие общие методы, используемые для смены домена в ОС, в которой идентификаторы пользователей…

Недопустимость повторного использование объектов

Аудит, учет использования системы защиты

· вход или выход из системы; · операции с файлами (открыть, закрыть, переименовать, удалить); · обращение к удаленной системе;

Анализ некоторых популярных ОС с точки зрения их защищенности.

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

MS-DOS

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

NetWare, IntranetWare

16.4.3 OS/2 OS/2 работает в защищенном режиме (protected-mode) процессора i80x86. … Считается, что такие операционные системы, как MS-DOS, MacOS, Windows, OS/2, имеют уровень защищенности D (по…

Unix

Рост популярности Unix и все большая осведомленность о проблемах безопасности привели к осознанию необходимости достичь приемлемого уровня безопасности ОС, сохранив при этом мобильность, гибкость и открытость программных продуктов. В Unix есть несколько уязвимых с точки зрения безопасности мест, хорошо известным искушенным пользователям, вытекающими из самой природы Unix и открывающими двери для нападения. (см., например, раздел Типичные объекты атаки хакеров в книге [23]). Однако, хорошее системное администрирование может ограничить эту уязвимость.

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

Обычно, говоря о защищенности Unix, рассматривают защищенность автоматизированных систем, одним из компонентов которых является Unix сервер. Безопасность такой системы увязывается с защитой глобальных и локальных сетей, безопасностью удаленных сервисов типа telnet и rlogin/rsh и аутентификацией в сетевой конфигурации, безопасностью X Windows приложений. Hа системном уровне важно наличие средств идентификации и аудита.

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

Все пользователи, которым разрешена работа в системе, учитываются в файле пользователей /etc/passwd. Группы пользователей учитываются в файле /etc/group. Каждому пользователю назначается целочисленный идентификатор и пароль.

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

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

По отношению к конкретному файлу все пользователи делятся на три категории:

· владелец файла

· члены группы владельца

· прочие пользователи

Для каждой из этих категорий режим доступа определяет права на операции с файлом, а именно:

· Право на чтение

· Право на запись

· Право на выполнение (для каталогов - право на поиск)

Стандартная команда ls -l выдает список файлов с правами доступа к ним, например:

rwxr-x--- ... filename

Здесь символы rwx означают наличие прав на чтение, запись и исполнение соответственно, а символ - - отсутствие такого права.

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

Наличие всего трех видов субъектов доступа: владелец, группа, все остальные - затрудняет задание прав с точностью до пользователя, особенно в случае больших конфигураций. В популярной разновидности Unix - Solaris имеется возможность использовать списки управления доступом (ACL), позволяющие с помощью команды setfacl индивидуально устанавливать права доступа отдельных пользователей или групп.

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

В Unix имеются инструменты системного аудита - хронологическая запись событий, имеющих отношение к безопасности. К таким событиям обычно относят: обращения программ к отдельным серверам; события, связанные с входом/выходом в систему и другие. Обычно регистрационные действия выполняются специализированным syslog-демоном, который проводит запись событий в регистрационный журнал в соответствии с текущей конфигурацией. Syslog-демон стартует в процессе загрузки системы.

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

16.4.5 Windows NT/2000.

С момента выхода версии 3.1 осенью 1993 года в Windows NT гарантировалось соответствие уровню безопасности C2. В настоящее время (точнее в 1999) сертифицирована версия NT 4 с Service Pack 6a с использованием файловой системы NTFS в автономной и сетевой конфигурации. Следует помнить, что этот уровень безопасности не подразумевает защиту информации, передаваемой по сети, и не гарантирует защищенности от физического доступа. Компоненты защиты NT частично встроены в ядро, а частично реализуются подсистемой защиты. Подсистема защиты регистрирует правила контроля доступа и контролирует учетную информацию.

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

Microsoft Windows NT - относительно новая ОС, которая была спроектирована для поддержки разнообразных защитных механизмов от минимальных до C2. Дефолтный уровень называется минимальным, но он легко может быть доведен системным администратором до желаемого уровня. Утилита C2config.exe помогает администратору сделать нужные установки. ...

Система защиты ОС Windows NT состоит из следующих компонентов:

· Процедуры регистрации (Logon Processes), которые обрабатывают запросы пользователей на вход в систему. Они включают в себя начальную интерактивную процедуру, которая отображает начальный диалог с пользователем на экране и удаленные процедуры входа, которые позволяют удаленным пользователям получить доступ с рабочей станции сети к серверным процессам Windows NT.

· Подсистемы локальной авторизации (Local Security Authority, LSA), которая гарантирует, что пользователь имеет разрешение на доступ в систему.

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

· Менеджера учета (Security Account Manager, SAM), который управляет базой данных учета пользователей. Эта база данных содержит информацию обо всех пользователях и группах пользователей. SAM предоставляет услуги по легализации пользователей, которые используются в LSA.

· Диспетчера доступа (Security Reference Monitor, SRM), который проверяет, имеет ли пользователь право на доступ к объекту и на выполнение тех действий, которые он пытается совершить с объектом. Эта компонента проводит в жизнь легализацию доступа и политику аудита, определяемые LSA. Она предоставляет услуги для программ супервизорного и пользовательского режимов для того, чтобы гарантировать, что пользователи и процессы, осуществляющие попытки доступа к объекту, имеют необходимые права. Эта компонента также порождает аудитные сообщения, когда это необходимо.

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

Резюме

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

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

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

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

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