- •Челябинск
- •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
Пример создания комплекса параллельных взаимодействующих программ, выступающих как самостоятельные вычислительные процессы
Теперь рассмотрим более сложную задачу: пусть параллельно выполняющиеся задачи имеют статус полноценного вычислительного процесса, а не потока и, кроме этого, организуем обращение к соответствующим системным механизмам непосредственно на уровне API. Схема взаимодействия программ для этого примера изображена на рис. 6.7.
Рис. 6.7.Схема № 2 взаимодействия параллельно выполняющихся вычислительных процессов
На этом рисунке программа с именем А в точке 1 порождает сразу четыре параллельно выполняющихся задачи (вычислительных процесса): В, С, I и J. Процессы В и С завершаются и должны запустить, в свою очередь, два параллельных процессаDи Е. В точке 2, в которой происходит синхронизация задач В и С, процессы D и Е должны быть запущены той из задач В или С, которая закончит свое выполнение раньше, но только после момента окончания второй. Далее, в точке 3 необходимо запустить программыGи Н. Запускает их первая завершившая свою работу программа (D, Е или I), но дождавшись завершения остальных программ. Точка 4 синхронизирует выполнение процессовF,G, Н иJ, при этом программу К запускает последний из завершившихся процессов.
Для решения поставленной задачи будем использовать соответствующие механизмы, описанные нами выше (применительно к OS/2), а именно конвейер (pipe) и семафоры. В нашей задаче через конвейер передается переменная типа
ParentInfo:
struct ParentInfo
{
char ParentName [15];
char LaunchTime [12];
int Number;
}
Parentlnfo– хранит имя программы-предка;LaunchTIme– содержит время запуска текущей программы программой-предком (время, когда программа-предок выполнила функциюDosExecPgm);переменная Numberуказывает, для какого числа программ предназначена переменная ParentInfo.
Читать из конвейера мы можем при помощи функции DorRead, но при этом уничтожается запись в конвейере, и мы обязаны перезаписывать данные в конвейер для других программ. Каждая программа читает данные из конвейера и затем уменьшает значениеNumber. Программа, установившая значение 1, является последней программой, прочитавшей данные из конвейера; она посылает сигнал предку о завершении инициализации необходимых ресурсов. Программа пишет в конвейер данные только в том случае, если именно она будет запускать следующие программы.
Для чтения и записи в конвейер необходимы переменные WriteHandleиReadHandle, указывающие на описатели записи и чтения в конвейер. Необходимо, чтобы значения этих переменных, полученных в процессе А, были известны остальным процессам для совместного использования. Для этого значения этих переменных мы можем передать процессам-потомкам в качестве строк аргументов.
При попытке считывания информации из пустого конвейера процесс переводится в состояние ожидания. После записи информации в конвейер другим процессом ожидающий процесс считывает поступившую информацию и продолжает свою работу.
Поскольку программы, которые мы сейчас рассматриваем, созданы для операционной системы OS/2, приведём краткое описание использованных механизмов, которые имеют отличия от вышеописанных общих принципов и схем.
Функция создания семафора:
DosCreateEventSem (“\\SEM\\PIPESEM”, &PipeSem, 1, 0);
где "\\SEM\\PIPESEM"– имя семафора,PipeSem– идентификатор семафора,1– параметр совместного использования семафора (DC_SEM_SHARED),0– зарезервированный системный параметр.
Функция открытия семафора:
DosOpenEventSem ("\\SEM\\PIPESEM", &PipeSem);
где ''\\SEM\\PIPESEM"– имя семафора,PipeSem– идентификатор семафора.
Функция установки семафора:
DosPostEventSem (PipeSem);
где PipeSem– идентификатор семафора.
Функция сброса семафора:
DosResetEventSem (PipeSem, &NPost);
где PipeSem– идентификатор семафора,NPost– количество обращений к установке семафора с момента последнего сброса.
Функция ожидания установки семафора:
DosPostEventSem (PipeSem, -1):
где PipeSem– идентификатор семафора,-1– ожидание семафора до его установки (положительное значение – это задержка в миллисекундах).
Для синхронизации процессов и обработки критических участков программ необходимы семафоры, к которым имеют доступ все работающие программы. Программа-потомок может унаследовать семафор от программы-предка, которая создала или открыла необходимый семафор. Но это произойдет только тогда, когда программа-предок дождётся момента открытия семафора в программе-потомке. Это обеспечивается за счёт дополнительных семафоров ExitSem1, ExitSem2, ExitSem3. Когда последняя программа-потомок прочитывает данные из конвейера (работа с конвейером) и обнаруживает, что она последней прошла участок открытия уже созданных семафоров, она устанавливает необходимый семафор, принадлежащий программе-предку. Программа-предок, ожидающая установки семафора, завершает свою работу.
Для управления запуском и завершением программ также используются соответствующие функции.
DosExecPgm (FailFile, sizeof( FailFile), 1, Argument, 0, ResCode, "progr_b.exe")– функция запуска программы-потомка, где
FailFile– буфер для помещения имени объекта, из-за которого возникла ошибка запуска программы,sizeof( FailFile)– размер буфера;
1означает, что процесс-потомок следует выполнять асинхронно с процессом-предком,Argument– строки аргументов программы,0– строки среды,ResCode– результирующие коды запуска программы,"progr_b.exe"– имя запускаемой (планируемой на выполнение) программы;
DosExit– функция завершения процесса (и всех его подпроцессов);
DosSetPriority– установка приоритета программы (и всех его подпроцессов).
Каждую программу в соответствии с заданием создаём как независимую, то есть имеющую своё локальное адресное пространство. Благодаря этому переменные в текстах программ, имеющие одинаковые имена (см. листинги в приложении Б), фактически являются разными переменными. Программа с именем А является начальной, стартовой. Именно она создаёт те системные объекты, которыми потом пользуются её потомки для своей синхронизации. Имена системных объектов они получают в наследство при своём порождении.
Для совместного использования вычислительными процессами одного файла необходимо правильно его открыть в программе А. После корректного открытия или создания файла к нему могут обращаться все программы, имеющие идентификатор открытого файла. Значение этого идентификатора передается запускающимся процессам в строке аргументов, сопровождающих вызов.
В соответствии с заданием каждая программа записывает в файл время своего запуска, имя процесса-предка и время завершения своей работы. Поскольку файл используется всеми программами и запись производится в строгой последовательности, часть программы, которая обеспечивает запись в файл, должна быть признана нами как критический участок программы (критический интервал). Алгоритм обработки этого участка описан ниже. Если не пытаться регулировать доступ процессов к файлу, может возникнуть беспорядочная запись в файл. При регулировании записи каждый процесс производит сразу все три записи в файл.
Опишем теперь алгоритм обработки критических участков программ – записи в файл и работы с конвейером.
Критический участок – работа с конвейером.
Приведем фрагмент программы, обеспечивающий чтение из конвейера.
1: do { DosWaitEventSem (PipeSem, -1);
2: rc=DosResetEventSem (PipeSem, &NPost);
3: } while (rc!=0);
4: DosRead(ReadHandle,(PVOID)&OldInform,sizeof(Oldlnform),
BytesReaden);
5: DosPostEventSem(PipeSem);
Программа А создает семафор PipeSem, который затем используют все программы для прохождения критической части программы, связанной с чтением и записью в конвейер.
В строке 1 программа ожидает установки семафора PipeSem; после того как этот семафор будет установлен, программа переходит к строке 2. Переменнаяrcвозвращает код ошибки при попытке сбросить семафор в строке 2. Это сделано со следующей целью: если после завершения строки1будет выполняться другая программа и она успеет сбросить семафор, то когда программа вновь продолжит своё выполнение, она обнаружит в строке 2, что семафор уже сброшен иrcне будет равно нулю; затем цикл повторится. Так будет продолжаться до тех пор, покаrcне станет равно нулю, то есть текущая программа первой сбросила семафор. Тогда в строке 4 программа считывает из конвейера данные и сигнализирует об освобождении ресурса в строке 5.
Для записи в конвейер используется аналогичный алгоритм.
Критический участок –запись в файл.
Здесь использован такой же алгоритм, как и при работе с конвейером, но задействован специально созданный для этого семафор FileSem. Теперь рассмотрим алгоритмы, решающие задачи синхронизации в каждой из точек нашей схемы (см. рис. 6.7). Начнем с прохождения точки 2. Приведём фрагмент исходного текста программы (см. приложение Б).
1: rc=DosPostEventSem(Point1Sem) :
2: if (rc==0)
3: { DosWrite(WriteHandle, (PVOID)&NewInform, sizeof(NewInform), &BytesWr1tten);
4: DosCreateEventSem("\\SEM32\\EXITSEM2", &ExitSem2, DC_SEM_SHARED, 0);
5: DosExecPgm(FailFileb, sizeof(FailFileb), 1, Argument, 0, &ResCodeb, "progr_d.exe");
6: DosExecPgm(FaiIFileb, sizeof(FailFileb), 1, Argument, 0, &ResCodeb, "progr_e.exe");
7: DosExecPgm(FailFileb, sizeof(FailFileb), 1, Argument, 0, &ResCodeb, "progr_f.exe");
8: DosWaitEventSem(ExitSem2, -1);
9: DosCloseEventSem(ExitSem2); }
В точке 2 программы D, Е, иFдолжны быть запущены процессом, который первым завершит свою работу. Для определения последовательности завершения работы программ (В или С) нами используется семафорPoint1Sem. В строке 1 производится установка данного семафора. Если значениеrcне равно нулю, значит, семафор уже установлен, то есть текущая программа не первой завершила свою работу. Еслиrcравно нулю, то текущая программа закончила работу первой и осуществляется переход к строке 3. В строке 3 осуществляется запись в конвейер. Строка 4 – создание семафора ожидания. Этот семафор используется для ожидания открытия семафоров в программах-потомках. Ожидание открытия семафоров происходит в строке 8, затем семафор закрывается. В строках 5–7 осуществляется запуск программ D, Е, F.
Теперь приведём алгоритм прохождения точки 3. Фрагмент исходного текста программы изображен ниже.
1: rc=DosPostEventSem(Point2Sem);
2: if (гс==0)
3: { do{ DosQueryEventSem(Point2Sem, &BytesWritten);
4: }while (BytesWritten<=2);
5: DosWrite(WriteHandle, (PVOID)&NewInform, sizeof(NewInform),
&BytesWritten);
6: DosCreateEventSem("\\SEM32\\EXITSEM3", &ExitSem3,
DC_SEM_SHARED, 0);
7: DosExecPgm(FailFileb, sizeof(FailFileb), Argument, 0, &ResCodeb,
"progr_g.exe");
8: DosExecPgm(FailFileb, sizeof(FailFileb), Argument, 0, &ResCodeb,
"progr_h.exe");
9: DosWaitEventSem(ExitSem3, -1);
В точке 3 программы Gи Н запускаются той программой, которая первой завершает свою работу, но только после того, как работу завершат остальные программы. Для определения последовательности завершения работы программ (I,Dили Е) используется семафорPoint2Sem. В строке 1 производится установка данного семафора. Если значениеrcне равно нулю, значит, семафор уже установлен, то есть текущая программа не первой завершила свою работу. Еслиrcравно нулю, то текущая программа закончила работу первой и осуществляется переход к строке 3. В этой строке подсчитывается количество обращений к данному семафору. Цикл повторяется до тех пор, пока количество обращений не станет равно 3, то есть когда все остальные программы завершили свою работу. После этого в строке 5 осуществляется запись в конвейер. Строка 6 – создание семафора ожидания. Этот семафор используется для ожидания открытия семафоров в программах-потомках. Ожидание открытия семафоров происходит в строке 9. В строках 7 и 8 осуществляется запуск программGи Н соответственно.
Наконец, приведём ещё алгоритм прохождения точки 4. Фрагмент исходного текста программы, реализующей эту задачу, приведён ниже.
1: do { DosWaitEventSem(Point1Sem, -1);
2: rc=DosResetEventSem(Point1Sem, &BytesReaden);
3: } while (rc!=0);
4: DosPostEventSem(Point3Sem);
5: DosQueryEventSem(Point3Sem, &BytesWritten);
6: DosPostEventSem(Point1Sem);
7: if (BytesWritten==4)
8: { DosWrite(WriteHandle, (PVOID)&NewInform, sizeof(NewInform),
&BytesWritten);
9: DosCreateEventSem("\\SEM32\\EXITSEM4", &ExTtSem4,
DC_SEM_SHARED, 0);
10: DosExecPgm(FailFileb, sizeof(FailFileb), 1, Argument, 0, &ResCodeb,
"progr_k.exe"):
11: DosWaitEventSem(ExitSem4, -1);
Итак, в точке 4 программа К запускается задачей, которая последней завершила свою работу. Для определения последовательности завершения работы программ (J,G, Н илиF) используется семафорPoint3Sem. Каждая программа должна обратиться к данному семафору, установить его и проверить количество обращений к нему. Но при выполнении этих двух операций другие программы могут также установить семафор, и значение обращений к семафору в текущей программе окажется неверным. Для доступа к семафоруPoint3Semиспользуется семафорPoint1Sem. В строке 1 программа ожидает установки семафораPoint1Sem, который сигнализирует о доступности неразделяемого ресурсаPoint3Sem. В строке 2 семафор сбрасывается, но если другие программы успели сбросить семафор, то об этом сообщит значениеrc. Если текущей программе удалось завладеть ресурсом, то есть значениеrcравно нулю, то дальше в строках 4, 5 производится установка семафораPoint3Sem и подсчёт количества обращений. Строка 6 сигнализирует о завершении работы критической части программы установкой семафораPoint1Sem. Затем, как и в предыдущих алгоритмах, программа записывает информацию в транспортёр (строка 8), создает семафор ожидания открытия семафоров в программах-потомках (строка 9), запускает программу К (строка 10) и ожидает открытия семафоров в программе К (строка 11).
Тексты четырех программ (А, В, Dи G), действующих по рассмотренным алгоритмам, приведены в приложении Б. Остальные программы аналогичны им и отличаются только использованием других имён.