- •Челябинск
- •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
Модель пространства состояний системы
Приведём еще одну формальную модель (она подробно рассмотрена в работе [92]). Эта модель очень проста, однако она позволяет сформулировать, что нам нужно делать, чтобы не попасть в тупиковое состояние.
Пусть состояние операционной системы будет сводиться к состоянию различных ресурсов в системе (свободны они или кому-то распределены). Состояние системы изменяется процессами, когда они запрашивают, приобретают или освобождают ресурсы; это будут единственно возможные действия (точнее, мы принимаем во внимание только такие действия). Если процесс не блокирован в данном состоянии, он может изменить это состояние на новое. Однако, так как в общем случае невозможно знать заранее, какой путь может избрать произвольный процесс в своей программе (это неразрешимая проблема!), то новое состояние может быть любым из конечного числа возможных. Следовательно, процессы нами будут трактоваться как недетерминированные объекты. Введённые ограничения на известные понятия приводят нас к следующим формальным определениям:
Система есть пара <,>, где
– множество состояний системы {S1,S2,S3, ... ,Sn};
– множество процессов {P1, Р2, Р3, ... , Рk}.
Процесс Рi есть частичная функция, отображающая состояние системы в непустые подмножества её же состояний. Это обозначается так:
Pi:{}
Если Piопределён на состоянииS, то область значений Рi , обозначается какPi(S). Если SkPi(Se), то мы говорим, чтоPiможет изменить состояниеSeв состояние Skпосредством операции, и используем обозначение Se Sk .
Наконец, запись SeSwобозначает, что
Se =Swили
Se Swдля некоторогоiили
Se Skдля некоторогоiи Sk, и Sk Sw.
Другими словами, система может быть переведена посредством п0 операций с помощьют 0 различных процессов из состояния Seв состояниеSw.
Мы говорим, что процесс заблокирован в данном состоянии, если он не может изменить состояние, то есть в этом состоянии процесс не может ни затребовать, ни получать, ни освобождать ресурсы. Поэтому справедливо будет записать следующее:
Процесс Piзаблокирован в состоянии Se, если не существует ни одного состояния Sk, такого что Se Sk(Pi(Se) =).
Далее, мы говорим, что процесс находится в тупике в данном состоянии Se, если он заблокирован в состоянии Seи если вне зависимости от того, какие операции (изменения состояний) произойдут в будущем, процесс остается заблокированным. Поэтому дадим еще одно определение:
Процесс Piнаходится в тупике в состоянии Se, если для всех состояний Sk, таких что Se Sk, процесс Pi блокирован в Sk.
Приведём пример. Определим систему <,>:
={S1,S2,S3,S4};= {P1, Р2};
P1(S1) = {S2, S3}; P2(Sl) = {S3};
Pl(S2) = ; P2(S2) = {S1, S4};
Pl(S3) = {S4}; P2(S3) = ;
P1(S4) = {S3}; P2(S4) = .
Некоторые возможные последовательности изменений для этой системы таковы:
S1 S3; S2 S4; S1 S4.
Последовательность S1 S4может быть реализована, например, следующим образом: S1 S2; S2 S4 или же S1 S3; S3 S4.
Заметим, что процесс Р2находится в тупике как в состоянииS3, так и в состоянииS4; для последнего случая S2 S4или S2 S1и процессP1не становится заблокированным ни вS4, ни вS1.
Диаграмма переходов этой системы изображена на рис. 7.9.
Рис. 7.9.Пример системы <,> на 4 состояния
Состояние Sназывается тупиковым, если существует процесс Рi, находящийся в тупике в состоянии S.
Теперь мы можем сказать, что тупик предотвращается, по определению, при введении такого ограничения на систему, чтобы каждое её возможное состояние не было тупиковым состоянием.
Введем еще одно определение.
Состояние Siестьбезопасное состояние,если для всехSk, таких что
Si Sk,Skне является тупиковым состоянием.
Рассмотрим ещё один пример системы <,>.Граф её состояний приведен на рис. 7.10. Здесь состоянияS2иS3являются безопасными; из них система никогда не сможет попасть в тупиковое состояние. Состояния S1иS4могут привести как к безопасным состояниям, так и к опасному состояниюS5. СостояниеS6иS7является тупиковым.
Рис. 7.10.Пример системы <,> с безопасными, опасными и тупиковым
состояниями
Наконец, в качестве ещё одной простейшей системы вида <,> приведём пример тупика с SR-ресурсами, уже рассмотренный нами в этой главе ранее. Определим следующим образом состояния процессовP1и Р2, которые используют ресурсы R1и R2.
Таблица 7.1.Состояния процессов Р1и Р2
Состояния для процесса Р1
|
Состояния для процесса Р2
| ||
0
|
Не содержит никаких ресурсов |
0
|
Не содержит никаких ресурсов
|
1
|
Запросил ресурс R2, не держит никаких ресурсов
|
1
|
Запросил ресурс R1, не держит никаких ресурсов
|
2
|
Держит ресурс R2
|
2
|
Держит ресурс R1
|
3
|
Запросил ресурс R1, держит ресурс R2
|
3
|
Запросил ресурс R2, держит ресурс R1
|
4
|
Держит ресурсы R1 и R2
|
4
|
Держит ресурсы R1 и R2
|
5
|
Держит ресурс R2 после освобождения ресурса R1 |
5
|
Держит ресурс R2 после освобождения ресурса R1
|
Пусть состояние системы Sijозначает, что процессP1находится в состоянииSi, а процесс Р2– в состоянии Sj. Возможные изменения в пространстве состояний этой системы изображены на рис.7.11. «Вертикальными» стрелками показаны возможные переходы из одного состояния в другое для процессаP1, а «горизонтальными» – для процесса Р2. В данной системе имеются три опасных состояния. Попав в любое из них, мы неминуемо перейдем в тупиковое состояние.
Рис. 7.11.Пример системы
Теперь, когда мы знаем понятия надежного, опасного и безопасного состояний, можно рассмотреть и методы борьбы с тупиками.