- •Челябинск
- •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
Файловые системыVfaTиFat32
Одной из важнейших характеристик исходной FATбыло использование имён файлов формата «8.3», в котором 8 символов отводится на указание имени файла и 3 символа – для расширения имени. К стандартнойFAT(имеется в виду прежде всего реализацияFAT16) добавились ещё две разновидности, используемые в широко распространенных операционных системахMicrosoft(конкретно – вWindows95 иWindowsNT):VFAT(виртуальнаяFAT) и FAT32, используемая в одной из редакций ОСWindows95 иWindows98. Ныне эта файловая система (FAT32) поддерживается и такими ОС, какWindowsMillenniumEdition, и всеми ОС семействаWindows2000. Имеются реализации систем управления файлами для FAT32,WindowsNTи ОСLinux.
Файловая система VFAT впервые появилась в WindowsforWorkgroups3.11 и была предназначена для выполнения файлового ввода/вывода в защищённом режиме (см. раздел «Реальный и защищенный режимы работы процессора», глава 3). С выходомWindows95 в VFAT добавилась поддержка длинных имён файлов (longfilename,LFN). Тем не менее, VFAT сохраняет совместимость с исходным вариантомFAT; это означает, что наряду с длинными именами в ней поддерживаются имена формата «8.3», а также существует специальный механизм для преобразования имен «8.3» в длинные имена, и наоборот. Именно файловая система VFAT поддерживается исходными версиямиWindows95,WindowsNT4. При работе с VFAT крайне важно использовать файловые утилиты, поддерживающие VFAT вообще и длинные имена в частности. Дело в том, что более ранние файловые утилитыDOSзапросто модифицируют то, что кажется им исходной структуройFAT. Это может привести к потере или порче длинных имен из таблицыFAT, поддерживаемой VFAT (или FAT32). Следовательно, для томов VFAT необходимо пользоваться файловыми утилитами, которые понимают и сохраняют файловую структуру VFAT.
В исходной версии Windows95 основной файловой системой была 32–разрядная VFAT. VFAT может использовать 32-разрядные драйверы защищённого режима или 16-разрядные драйверы реального режима. При этом элементыFATостаются 12- или 16-разрядными, поэтому на диске используется та же структура данных, что и в предыдущих реализацияхFAT.VFATобрабатывает все обращения к жёсткому диску и использует 32-разрядный код для всех файловых операций с дисковыми томами.
Основными недостатками файловых систем FATи VFAT являются большие потери на кластеризацию при больших размерах логического диска и ограничения на сам размер логического диска. Это привело к разработке новой реализации файловой системы с использованием той же идеи использования таблицыFAT. Поэтому вMicrosoftWindows95OEMServiceRelease2 (эта версияWindows95 часто называетсяWindows95OSR2) на смену системе VFAT пришла файловая система FAT32. FAT32 является полностью самостоятельной 32-разрядной файловой системой и содержит многочисленные усовершенствования и дополнения по сравнению с предыдущими реализациямиFAT.
Принципиальное отличие заключается в том, что FAT32 намного эффективнее расходует дисковое пространство. Прежде всего, система FAT32 использует кластеры меньшего размера по сравнению с предыдущими версиями, которые ограничивались 65 535 кластерами на том (соответственно, с увеличением размера диска приходилось увеличивать и размер кластеров). Следовательно, даже для дисков размером до 8 Гбайт FAT32 может использовать 4-килобайтные кластеры. В результате по сравнению с дисками FAT16 экономится значительное дисковое пространство (в среднем 10-15 %) [53].
FAT32 также может перемещать корневой каталог и использовать резервную копию FATвместо стандартной. Расширенная загрузочная запись FAT32 позволяет создавать копии критических структур данных; это повышает устойчивость дисков FAT32 к нарушениям структурыFATпо сравнению с предыдущими версиями. Корневой каталог в FAT32 представлен в виде обычной цепочки кластеров. Следовательно, корневой каталог может находиться в произвольном месте диска, что снимает действовавшее ранее ограничение на размер корневого каталога (512 элементов).Windows95OSR2 иWindows98 могут работать и с разделами VFAT, созданнымиWindowsNT. То, что говорилось ранее об использовании файловых утилитVFATс томамиVFAT, относится и кFAT32. Поскольку прежние утилитыFAT(для FAT32 в эту категорию входят обе файловые системы,FATи VFAT) могут повредить или уничтожить важную служебную информацию, для томов FAT32 нельзя пользоваться никакими файловыми утилитами, кроме утилит FAT32.
Кроме повышения ёмкости FATдо величины в 4 Тбайт, файловая система FAT32 вносит ряд необходимых усовершенствований в структуру корневого каталога. Предыдущие реализации требовали, чтобы вся информация корневого каталогаFATнаходилась в одном дисковом кластере. При этом корневой каталог мог содержать не более 512 файлов. Необходимость представлять длинные имена и обеспечить совместимость с прежними версиямиFATпривела разработчиков компанииMicrosoftк компромиссному решению: для представления длинного имени они стали использовать элементы каталога, в том числе и корневого. Рассмотрим способ представления в VFAT длинного имени файла (рис. 4.9).
Первые одиннадцать байтов элемента каталога DOSиспользуются для хранения имени файла. Каждое такое имя разделяется на две части: в первых восьми байтах хранятся символы собственно имени, а в последних трех – символы так называемого расширения, с помощью которого реализуются механизмы предопределенных типов. Были введены соответствующие системные соглашения, и файлы определенного типа необходимо (желательно) именовать с оговоренным расширением. Например, исполняемые файлы с расширением СОМ определяют исполняемую двоичную программу с простейшей односегментной структурой1. Более сложные программы имеют расширение ЕХЕ. Определенны расширения для большого количества типов файлов, и эти расширения используются для ассоциированного запуска обрабатывающих файлы программ.
Рис.4.9. Элементы каталогов дляFAT,VFATи FAT32
Если имя файла состоит менее чем из восьми символов, то в элементе каталога оно дополняется символами пробела, чтобы полностью заполнить все восемь байтов соответствующего поля. Аналогично и расширение может содержать от нуля до трех символов. Остальные (незаполненные) позиции в элементе каталога, определяющем расширение имени файла, заполняются символами пробела. Поскольку при работе с именем файла учитываются все одиннадцать свободных мест, то необходимость в отображении точки, которая обычно вводится между именем файла и его расширением, отпадает. В элементе каталога она просто подразумевается.
В двенадцатом байте элемента каталога хранятся атрибуты файла.Шесть из восьми указанных разрядов используютсяDOS1. К атрибутам DOSотносятся следующие:
атрибут «архивный» (А – archive). Показывает, что файл был открыт программой таким образом, чтобы у неё была возможность изменить содержимое этого файла.DOSустанавливает этот разряд атрибута в состояниеON(включено) при открытии файла. Программы резервного копирования нередко устанавливают его вOFF(выключено) при выполнении резервного копирования файла. Если применяется подобная методика, то в следующую создаваемую по порядку резервную копию будут добавлены только файлы с данным разрядом, установленным в состояниеON;
атрибут каталога (D–directory). Показывает, что данный элемент каталога указывает на подкаталог, а не на файл;
атрибут тома (V – volume). Применяется только к одному элементу каталога в корневом каталоге. В нём, собственно, и хранится имя дискового тома. Этот атрибут также применяется в случае длинных имён файлов, о чём можно будет узнать из следующего раздела;
атрибут «системный» (S–system). Показывает, что файл является частью операционной системы или специально отмечен подобным образом прикладной программой, что иногда делается в качестве составной части метода защиты от копирования;
атрибут «скрытый» (Н – hidden). Сюда относятся, в частности, файлы с установленным в состояниеONатрибутом «системный» (S), которые не отображаются в обычном списке, выводимом по командеDIR;
атрибут «только для чтения» (R–readonly). Показывает, что данный файл не подлежит изменению. Разумеется, поскольку это лишь разряд байта, хранящегося на диске, то любая программа может изменить этот разряд, после чегоDOSсвободно разрешила бы изменение данного файла. Этот атрибут в основном используется для примитивной защиты от пользовательских ошибок, то есть он позволяет избежать неумышленного удаления или изменения ключевых файлов.
Следует отметить, что наличие файла, помеченного одним или более из указанных выше атрибутов, может иметь вполне определенный смысл. Например, большинство файлов, отмечаемых в качестве системных, отмечаются также признаками скрытых файлов и «только для чтения».
На дисках FAT12 илиFAT16 следующие за именем десять байтов не используются. Обыкновенно они заполняются нулями и считаются резервными значениями. А на диске с файловой системойFAT32 эти 10 байт содержат самую разную информацию о файле. При этом байт, отмеченный как «зарезервировано дляNT», представляет собой, как подразумевает его название, поле, не используемое вDOSилиWindows9x, но применяемое вWindowsNT.
Из соображений совместимости поля, которые встречаются в элементах каталога для коротких имен формата FAT12 и FAT16, находятся на тех же местах и в элементах каталога для коротких имен формата FAT32. Остальные поля, которые встречаются только в элементах каталога для коротких имен формата FAT32, соответствуют зарезервированной области длиной в десять байт в элементах каталога для коротких имен форматов FAT12 и FAT16.
Как видно из рис.4.9, для длинного имени файла используется несколько элементов каталога. Таким образом, появление длинных имён фактически привело к дальнейшему уменьшению количества файлов, которые могут находиться в корневом каталоге. Поскольку длинное имя может содержать до 256 символов, всего один файл с полным длинным именем занимает до 25 элементов FAT,(1 для имени 8.3 и ещё 24 для самого длинного имени). Количество элементов корневого каталогаVFATуменьшается до 21. Очевидно, что это не самое изящное решение, поэтому компанияMicrosoftсоветует избегать длинных имен в корневых каталогахFATпри отсутствии FAT32, у которой количество элементов каталога соответственно просто увеличено. Помните и о том, что длина полной файловой спецификации, включающей путь и имя файла (длинное или в формате 8.3), тоже ограничивается 260 символами. FAT32 успешно справляется с проблемой длинных имён в корневом каталоге, но проблема с ограничением длины полной файловой спецификации остаётся. По этой причинеMicrosoftрекомендует ограничивать длинные имена 75–80 символами, чтобы оставить достаточно места для пути (180–185 символов).