- •Челябинск
- •2002 Предисловие
- •От издательства
- •Часть 1 Операционные системы и среды
- •Глава 1 Основные понятия Понятие операционной среды
- •Понятия вычислительного процесса и ресурса
- •Диаграмма состояний процесса
- •Реализация понятия последовательного процесса в ос
- •Процессы и треды
- •Прерывания
- •Основные виды ресурсов
- •Классификация операционных систем
- •Контрольные вопросы и задачи Вопросы для проверки
- •Глава 2 Управление задачами и памятью в операционных системах
- •Планирование и диспетчеризация процессов и задач Стратегии планирования
- •Дисциплины диспетчеризации
- •Вытесняющие и не вытесняющие алгоритмы диспетчеризации
- •Качество диспетчеризации и гарантии обслуживания
- •Диспетчеризация задач с использованием динамических приоритетов
- •Память и отображения, виртуальное адресное пространство
- •Простое непрерывное распределение и распределение с перекрытием (оверлейные структуры)
- •Распределение статическими и динамическими разделами
- •Разделы с фиксированными границами
- •Разделы с подвижными границами
- •Сегментная, страничная и сегментно-страничная организация памяти
- •Сегментный способ организации виртуальной памяти
- •Страничный способ организации виртуальной памяти
- •Сегментно-страничный способ организации виртуальной памяти
- •Распределение оперативной памяти в современных ос для пк
- •Распределение оперативной памяти вMs-dos
- •Распределение оперативной памяти вMicrosoftWindows95/98
- •Распределение оперативной памяти вMicrosoftWindowsNt
- •Контрольные вопросы и задачи Вопросы для проверки
- •Глава 3 Особенности архитектуры микропроцессоровi80x86
- •Реальный и защищённый режимы работы процессора
- •Новые системные регистры микропроцессоров i80x86
- •Адресация в 32-разрядных микропроцессорахi80х86 при работе в защищённом режиме Поддержка сегментного способа организации виртуальной памяти
- •Поддержка страничного способа организации виртуальной памяти
- •Режим виртуальных машин для исполнения приложений реального режима
- •Защита адресного пространства задач
- •Уровни привилегий для защиты адресного пространства задач
- •Механизм шлюзов для передачи управления на сегменты кода с другими уровнями привилегий
- •Система прерываний 32-разрядных микропроцессоровi80x86
- •Работа системы прерываний в реальном режиме работы процессора
- •Работа системы прерываний в защищённом режиме работы процессора
- •Обработка прерываний в контексте текущей задачи
- •Обработка прерываний с переключением на новую задачу
- •Контрольные вопросы и задачи Вопросы для проверки
- •Глава 4 Управление вводом/выводом и файловые системы
- •Основные понятия и концепции организации ввода/вывода в ос
- •Режимы управления вводом/выводом
- •Закрепление устройств, общие устройства ввода/вывода
- •Основные системные таблицы ввода/вывода
- •Синхронный и асинхронный ввод/вывод
- •Кэширование операций ввода/вывода при работе с накопителями на магнитных дисках
- •Функции файловой системы ос и иерархия данных
- •Структура магнитного диска (разбиение дисков на разделы)
- •Файловая системаFat
- •Структура загрузочной записиDos
- •Файловые системыVfaTиFat32
- •Файловая система hpfs
- •Файловая система ntfs (New Technology File System)
- •Основные возможности файловой системы ntfs
- •Структура тома с файловой системой ntfs
- •Возможности файловой системыNtfSпо ограничению доступа к файлам и каталогам
- •Основные отличияFaTи ntfs
- •Контрольные вопросы и задачи Вопросы для проверки
- •Задания
- •Глава 5 Архитектура операционных систем и интерфейсы прикладного
- •Принцип функциональной избирательности
- •Принцип генерируемости ос
- •Принцип функциональной избыточности
- •Принцип виртуализации
- •Принцип независимости программ от внешних устройств
- •Принцип совместимости
- •Принцип открытой и наращиваемой ос
- •Принцип мобильности (переносимости)
- •Принцип обеспечения безопасности вычислений
- •Микроядерные операционные системы
- •Монолитные операционные системы
- •Требования, предъявляемые к ос реального времени
- •Мультипрограммность и многозадачность
- •Приоритеты задач (потоков)
- •Наследование приоритетов
- •Синхронизация процессов и задач
- •Предсказуемость
- •Принципы построения интерфейсов операционных систем
- •Интерфейс прикладного программирования
- •Реализация функцийApIна уровне ос
- •Реализация функцийApIна уровне системы программирования
- •Реализация функцийApIс помощью внешних библиотек
- •Платформенно-независимый интерфейс posix
- •Пример программирования в различныхApiос
- •Текст программы дляWindows(WinApi)
- •Текст программы дляLinux(posixapi)
- •Контрольные вопросы и задачи Вопросы для проверки
- •Глава 6 Проектирование параллельных взаимодействующих вычислительных процессов
- •Независимые и взаимодействующие вычислительные процессы
- •Средства синхронизации и связи при проектировании взаимодействующих вычислительных процессов
- •Использование блокировки памяти при синхронизации параллельных процессов
- •Возможные проблемы при организации взаимного исключения посредством использования только блокировки памяти
- •Алгоритм Деккера
- •Синхронизация процессов посредством операции «проверка и установка»
- •Семафорные примитивы Дейкстры
- •Мьютексы
- •Использование семафоров при проектировании взаимодействующих вычислительных процессов
- •Задача «поставщик – потребитель»
- •Пример простейшей синхронизации взаимодействующих процессов
- •Решение задачи «читатели – писатели»
- •Мониторы Хоара
- •Почтовые ящики
- •Конвейеры и очереди сообщений Конвейеры (программные каналы)
- •Очереди сообщений
- •Примеры создания параллельных взаимодействующих вычислительных процессов
- •Пример создания многозадачного приложения с помощью системы программированияBorlandDelphi
- •Пример создания комплекса параллельных взаимодействующих программ, выступающих как самостоятельные вычислительные процессы
- •Контрольные вопросы и задачи Вопросы для проверки
- •Глава 7 Проблема тупиков и методы борьбы с ними
- •Понятие тупиковой ситуации при выполнении параллельных вычислительных процессов
- •Примеры тупиковых ситуаций и причины их возникновения
- •Пример тупика на ресурсах типаCr
- •Пример тупика на ресурсах типаCRиSr
- •Пример тупика на ресурсах типаSr
- •1: P(s2); 5: p(s1);
- •Формальные модели для изучения проблемы тупиковых ситуаций
- •Сети Петри
- •Вычислительные схемы
- •Модель пространства состояний системы
- •Методы борьбы с тупиками
- •Предотвращение тупиков
- •Обход тупиков
- •Обнаружение тупика
- •Обнаружение тупика посредством редукции графа повторно используемых ресурсов
- •Методы обнаружения тупика по наличию замкнутой цепочки запросов
- •Алгоритм обнаружения тупика по наличию замкнутой цепочки запросов
- •Контрольные вопросы и задачи Вопросы для проверки
- •Глава 8 Современные операционные системы
- •Семейство операционных системUnix Общая характеристика семейства операционных систем unix, особенности архитектуры семейства осunix
- •Основные понятия системыUnix
- •Виртуальная машина
- •Пользователь
- •Интерфейс пользователя
- •Привилегированный пользователь
- •Команды и командный интерпретатор
- •Процессы
- •Функционирование системыUnix
- •Выполнение процессов
- •Подсистема ввода/вывода
- •Перенаправление ввода/вывода
- •Файловая система
- •Структура файловой системы
- •Защита файлов
- •Межпроцессные коммуникации вUnix
- •Сигналы
- •Семафоры
- •Программные каналы
- •Очереди сообщений
- •Разделяемая память
- •Вызовы удаленных процедур (rpc)
- •Операционная системаLinux
- •Семейство операционных систем os/2WarpкомпанииIbm
- •Особенности архитектуры и основные возможности os/2Warp
- •Особенности интерфейса os/2Warp
- •Серверная операционная система os/2Warp4.5
- •Сетевая ос реального времениQnx
- •Архитектура системыQnx
- •Основные механизмы qnx для организации распредёленных вычислений
- •Контрольные вопросы и задачи Вопросы для проверки
- •Приложение а Тексты программы параллельных взаимодействующих задач
- •Приложение б Тексты программ комплекса параллельных взаимодействующих приложений
- •Текст программы а
- •Текст программы в
- •Текст программы d
- •Текст программы g
- •Список литературы
- •Часть 1 6
- •Глава 5 Архитектура операционных систем и интерфейсы прикладного 240
- •Глава 6 Проектирование параллельных взаимодействующих вычислительных 279
- •Глава 7 Проблема тупиков и методы 348
- •Глава 8 Современные операционные 391
Обнаружение тупика
Чтобы распознать тупиковое состояние, необходимо для каждого процесса определить, сможет ли он когда-либо снова развиваться, то есть изменять свои состояния. Так как нас интересует возможность развития процесса, а не сам процесс смены состояния, то достаточно рассмотреть только самые благоприятные изменения состояния.
Очевидно, что незаблокированный процесс (он только что получил ресурс и поэтому не заблокирован) через некоторое время освобождает все свои ресурсы и затем благополучно завершается. Освобождение ранее занятых ресурсов может «разбудить» некоторые ранее заблокированные процессы, которые, в свою очередь, развиваясь, смогут освободить другие ранее занятые ресурсы. Это может продолжаться до тех пор, пока либо не останется незаблокированных процессов, либо какое-то количество процессов всё же останется заблокированными. В последнем случае (если существуют заблокированные процессы при завершении указанной последовательности действий) начальное состояние Sявляется состоянием тупика, а оставшиеся процессы находятся в тупике в состоянии S. В противном случае S не есть состояние тупика.
Обнаружение тупика посредством редукции графа повторно используемых ресурсов
Наиболее благоприятные условия для незаблокированного процесса Рiмогут быть представленыредукцией(сокращением) графа повторно используемых ресурсов (см. первый раздел данной главы, описание модели Холта). Редукция графа может быть описана следующим образом:
Граф повторно используемых ресурсов сокращается процессом Рр который не является ни заблокированной, ни изолированной вершиной, с помощью удаления всех ребер, входящих в вершину Рiи выходящих из Рi. Эта процедура является эквивалентной приобретению процессом Рiнеких ресурсов, на которые он ранее выдавал запросы, а затем освобождению всех его ресурсов. ТогдаPiстановится изолированной вершиной.
Граф повторно используемых ресурсов несокращаем (не редуцируется), если он не может быть сокращен ни одним процессом.
Граф ресурсов типа RSявляется полностью сокращаемым, если существует последовательность сокращений, которая удаляет все дуги графа.
Приведем лемму, которая позволяет предложить алгоритмы обнаружения тупика.
Лемма.Для ресурсов типаSRпорядок сокращений несуществен; все последовательности ведут к одному и тому же несокращаемому графу.
Доказательство.Допустим, что лемма неверна. Тогда должно существовать некоторое состояние S, которое сокращается до некоторого несокращаемого состояния S1с помощью последовательности seq1и до несокращаемого состоянияS2– с помощью последовательностиseq2так, чтоS1S2(то есть все процессы в состоянияхS1иS2или заблокированы, или изолированы).
Если сделать такое предположение, то мы приходим к противоречию, которое устраняется только при условии, что S1=S2. Действительно, предположим, что последовательность seq1состоит из упорядоченного списка процессов (P1,P2, ... ,Pk). Тогда последовательность seq1должна содержать процесс Р, который не содержится в последовательностиseq2. В противном случаеS1=S2 , потому что редукция графа только удаляет дуги, уже существующие в состоянии S, а если последовательности seq1иseq2содержат одно и то же множество процессов (пусть и в различном порядке), то должно быть удалено одно и то же множество дуг. И доказательство по индукции покажет, что РРi(i= 1,2,...,k) приводит к указанному нами противоречию.
Р P1, так как вершина S может быть редуцирована процессомP1, а состояниеS2должно, следовательно, также содержать процессP1.
Пусть Р Pi, (i = 1, 2, ... , j). Однако, поскольку после редукции процессамиPi(i= 1, 2, ... , j) возможно ещё сокращение графа процессомPj+1, это же самое должно быть справедливо и для последовательностиseq2независимо от порядка следования процессов. То же самое множество рёбер графа удаляется с помощью процессаPi . Таким образом, РPj+1
Следовательно, Р Pi для i = 1, 2, ...,kи Р не может существовать, а это противоречит нашему предположению, чтоS1S2. Следовательно,S1=S2.
Теорема о тупике.СостояниеSесть состояние тупика тогда и только тогда, когда граф повторно используемых ресурсов в состоянии S не является полностью сокращаемым.
Доказательство.
а) Предположим, что состояние S есть состояние тупика и процесс Piнаходится в тупике в S. Тогда для всехSj, таких что S Sj процесс Рiзаблокирован в Sj(по определению). Так как сокращения графа идентичны для серии операций процессов, то конечное несокращаемое состояние в последовательности сокращений должно оставить процессPiблокированным. Следовательно, граф не является полностью сокращаемым.
б) Предположим, что S не является полностью сокращаемым. Тогда существует процесс Pi, который остаётся заблокированным при всех возможных последовательностях операций редукции в соответствие с леммой. Так как любая последовательность операций редукции графа повторно используемых ресурсов, оканчивающаяся несокращаемым состоянием, гарантирует, что все ресурсы типаSR, которые могут когда-либо стать доступными, в действительности освобождены, то процессPiнавсегда заблокирован и, следовательно, находится в тупике.
Следствие 1. Процесс Рiне находится в тупике тогда и только тогда, когда серия сокращений приводит к состоянию, в котором Рi, не заблокирован.
Следствие 2.Если S есть состояние тупика (по ресурсам типа SR), то по крайней мере два процесса находятся в тупике в S.
Из теоремы о тупике непосредственно следует и алгоритм обнаружения тупиков. Нужно просто попытаться сократить граф по возможности эффективным способом; если граф полностью не сокращается, то начальное состояние было состоянием тупика для тех процессов, вершины которых остались в несокращенном графе. Рассмотренная нами лемма позволяет удобным образом упорядочивать сокращения.
Граф повторно используемых ресурсов может быть представлен или матрицами, или списками. В обоих случаях экономия памяти может быть достигнута использованием взвешенных ориентированных мультиграфов (слиянием определённых дуг получения или дуг запроса между конкретным ресурсом и данным процессом в одну дугу с соответствующим весом, определяющим количество единиц ресурса).
Рассмотрим вариант с матричным представлением. Поскольку граф двудольный, он представляется двумя матрицами размером nm. Одна матрица –матрица распределенияD= ||dij||, в которой элемент dijотражает количество единицRjресурса, распределенного процессу Рiто естьdij= |(Rj, Р;)|, где (Rj,Pi) – это дуга между вершинами RjиPi, ведущая из Rjв Рi. Вторая матрица –матрица запросовN = ||nij||, гдеnij= |(Рi,Rj)|.
В случае использования связанных списков для отображения той же структуры можно построить две группы списков. Ресурсы, распределенные некоторому процессу Pi, связаны сPiуказателями:
Pi(Rx,dx)(Ry,dy)...(Rz,dz), гдеRj– вершина, представляющая ресурс, иdj– вес дуги, то естьdj= |(Rj,Pi)|.
Подобным образом и ресурсы, запрошенные процессом Рi, связаны вместе.
Аналогичные списки создаются и для ресурсов (списки распределенных и запрошенных ресурсов).
Ri(Pu, nu) (Pv, nv)... (Pw, nw), где nj = |(Pj, Rj)|.
Для обоих представлений удобно также иметь одномерный массив доступных единиц ресурсов (r1,r2, ...,rm), гдеriуказывает число доступных (нераспределённых единиц ресурсаRi, то естьri= |Ri| –|(Ri,Pk)|.
Простой метод прямого обнаружения тупика заключается в просмотре по порядку списка (или матрицы) запросов, причём, где возможно, производятся сокращения дуг графа до тех пор, пока нельзя будет сделать более ни одного сокращения. При этом самая плохая ситуация возникает, когда процессы упорядочены в некоторой последовательности P1, Р2, ... , Рn, а единственно возможным порядком сокращений является обратная последовательность, то есть Рn,Pn-1, ...,P2, Р1, а также в случае, когда процесс запрашивает всеmресурсов. Тогда число проверок процессов равно
n+ (n-1) + ... + 1=n(n+1)/2,
причём каждая проверка требует испытания m ресурсов. Таким образом, время выполнения такого алгоритма в наихудшем случае пропорционально mn2.
Более эффективный алгоритм может быть получен за счёт хранения некоторой дополнительной информации о запросах. Для каждой вершины процесса Рiопределяется так называемый счётчикожиданийwi, отображающий количество ресурсов (не число единиц ресурса), которые в какое-то время вызывают блокировку процесса. Кроме этого, можно сохранять для каждого ресурса запросы, упорядоченные по размеру (числу единиц ресурса). Тогда следующий алгоритм сокращений, записанный на псевдокоде, имеет максимальное время выполнения, пропорциональное mn.
For all P L do
Begin for all Rj |(Rj, P)| > 0 do
Begin rj := rj + |(Rj, P)|;
For all Pi 0 < |(Pi, Rj)| <= rj do
Begin wi := wi – 1;
If wi = 0 then L := L {Pi}
End
End
End
Deadlock := Not (L = {P1, P2, ... , Pn});
Здесь L– это текущий список процессов, которые могут выполнять редукцию графа. Можно сказать, чтоL := {Рiwi = 0}. Программа выбирает процесс Р из списка L, процесс Р сокращает граф, увеличивая число доступных единицrj всех ресурсовRj, распределенных процессу Р, обновляет счётчик ожиданияwiкаждого процесса Рiкоторый сможет удовлетворить свой запрос на частный ресурс Rj, и добавляет Рiк L, если счётчик ожидания становится нулевым.