- •Челябинск
- •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
Контрольные вопросы и задачи Вопросы для проверки
1 Какие последовательные вычислительные процессы мы называем параллельными и почему? Какие параллельные процессы называются независимыми, а какие – взаимодействующими?
2 Изложите алгоритм Деккера, позволяющий разрешить проблему взаимного исключения путём использования одной только блокировки памяти.
3 Объясните команду «проверка и установка».
4 Расскажите о семафорах Дейкстры. Чем обеспечивается взаимное исключение при выполнении Р- и V-примитивов?
5 Изложите, как могут быть реализованы семафорные примитивы для мультипроцессорной системы.
6 Что такое мьютекс (mutex)?
7 Изложите алгоритм решения задачи «поставщик – потребитель» при использовании семафоров Дейкстры.
8 Изложите алгоритм решения задачи «читатели – писатели» при использовании семафоров Дейкстры.
9 Что такое «монитор Хоара»? Приведите пример такого монитора.
10 Что представляют собой «почтовые ящики»?
11 Что представляют собой «конвейеры» (программные каналы)?
12 Что представляют собой «очереди сообщений»? Чем отличаются очереди сообщений от почтовых ящиков?
Глава 7 Проблема тупиков и методы борьбы с ними
Рассмотрим одну из самых серьезных и трудно разрешимых проблем, возникающих при организации мультипрограммирования – проблему тупиков и основные подходы при борьбе с ними. В настоящей главе приводятся некоторые модели параллельных вычислительных процессов, позволяющие проводить анализ последних в аспекте корректного решения указанных проблем.
Понятие тупиковой ситуации при выполнении параллельных вычислительных процессов
При организации параллельного выполнения нескольких процессов одной из главных функций операционной системы является решение сложной задачи корректного распределения ресурсов между выполняющимися процессами и обеспечение последних средствами взаимной синхронизации и обмена данными.
При параллельном исполнении процессов могут возникать ситуации, при которых два или более процесса всё время находятся в заблокированном состоянии. Самым простым является случай, когда каждый из двух процессов ожидает ресурс, занятый другим процессом. Из-за такого ожидания ни один из процессов не может продолжить исполнение и освободить в конечном итоге ресурс, необходимый другому процессу. Эта тупиковая ситуация называется дедлоком1,тупиком или клинчем. Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, если он ждёт события, которое никогда не произойдёт. Тупики чаще всего возникают из-за конкуренции несвязанных параллельных процессов за ресурсы вычислительной системы, но иногда к тупикам приводят и ошибки программирования.
При рассмотрении проблемы тупиков целесообразно понятие ресурсов системы обобщить и разделить их все на два класса – повторно используемые (или системные) ресурсы (типа RRилиSR–reusableresourceилиsystemresource) и потребляемые (или расходуемые) ресурсы (типаCR–consumableresource).
Повторно используемый ресурс (SR) есть конечное множество идентичных единиц со следующими свойствами [92]:
число единиц ресурса постоянно;
каждая единица ресурса или доступна, или распределена одному и только одному процессу (разделение либо отсутствует, либо не принимается во внимание, так как не оказывает влияния на распределение ресурсов, а значит, и на возникновение тупиковой ситуации);
процесс может освободить единицу ресурса (сделать её доступной), только если он ранее получил эту единицу, то есть никакой процесс не может оказывать какое-либо влияние ни на один ресурс, если он ему не принадлежит.
Данное определение выделяет существенные для изучения проблемы тупика свойства обычных системных ресурсов, к которым мы относим такие компоненты аппаратуры, как основная память, вспомогательная (внешняя) память, периферийные устройства и, возможно, процессоры, а также программное и информационное обеспечение, такое как файлы данных, таблицы и «разрешение войти в критическую секцию».
Расходуемый ресурс (CR) отличается от ресурса типа SR в нескольких важных отношениях [37]:
число доступных единиц некоторого ресурса типа CR изменяется по мере того, как приобретаются (расходуются) и освобождаются (производятся) отдельные их элементы выполняющимися процессами, и такое число единиц ресурса является потенциально неограниченным; процесс «производитель» увеличивает число единиц ресурса, освобождая одну или более единиц, которые он «создал»;
процесс «потребитель» уменьшает число единиц ресурса, сначала запрашивая и затем приобретая (потребляя) одну или более единиц. Единицы ресурса, которые приобретены, в общем случае не возвращаются ресурсу, а потребляются (расходуются). Эти свойства потребляемых ресурсов присущи многим синхронизирующим сигналам, сообщениям и данным, порождаемым как аппаратурой, так и программным обеспечением, и могут рассматриваться как ресурсы типа CR при изучении тупиков. В их число входят: прерывания от таймера и устройств ввода/вывода; сигналы синхронизации процессов; сообщения, содержащие запросы на различные виды обслуживания или данные, а также соответствующие ответы.
Для исследования параллельных процессов и, в частности, проблемы тупиков было разработано несколько моделей. Одной из них является модель повторно используемых ресурсов Холта [92]. Согласно этой модели система представляется как набор (множество) процессов и набор ресурсов, причём каждый из ресурсов состоит из фиксированного числа единиц. Любой процесс может изменять состояние системы с помощью запроса, получения или освобождения единицы ресурса.
В графической форме процессы и ресурсы представляются квадратами и кружками соответственно. Каждый кружок содержит некоторое количество маркеров (фишек) в соответствии с существующим количеством единиц этого ресурса. Дуга, указывающая из «процесса» на «ресурс», означает запрос одной единицы этого ресурса. Дуга, указывающая из «ресурса» на «процесс», представляет выделение ресурса процессу. Поскольку каждая единица любого ресурса типа SRможет быть выделена одновременно не более чем одному процессу, то число дуг, исходящих из ресурса к различным процессам, не может превышать общего числа единиц этого ресурса. Такая модель называетсяграфом повторно используемых ресурсов.
Одно из состояний примера системы из двух процессов с ресурсами типа SR представлено на рис. 7.1.
Пусть процесс Р1 запрашивает две единицы ресурса R1 и одну единицу ресурсаR2. Процессу Р2 принадлежат две единицы ресурса R1 и ему нужна одна единица R2. Предположим, что процесс Р1 получил бы теперь запрошенную им единицу R2. Если принято правило, по которому процесс должен получить все запрошенные им ресурсы, прежде чем освободить хотя бы один из них, то удовлетворение запроса Р1 приведет к тупиковой ситуации: Р1 не сможет продолжиться до тех пор, пока Р2 не освободит единицу ресурса R1, а процесс Р2 не сможет продолжиться до тех пор, пока Р1 не освободит единицу R2. Причиной этого дедлока являются неупорядоченные попытки процессов войти в критический интервал, связанный с выделением соответствующей единицы ресурса.
Рис. 7.1.Пример модели Холта для системы из двух процессов