Реферат: ЧАСТЬ I Операционные
Содержание
Предисловие…… .:… 13
От издательства… 16
Часть I.Операционные системы и среды
Глава 1. Основные понятия… .22
Понятие операционной среды… 22
Понятия вычислительного процесса и ресурса… 24
Диаграмма состояний процесса… 28
Реализация понятия последовательного процесса в ОС… 31
Процессы и треды… '. 33
Прерывания… 37
Основные виды ресурсов… 44
Классификация операционных систем… 48
Контрольные вопросы и задачи… 49
Вопросы для проверки… 49
Глава 2.Управление задачами и памятью в операционных системах.. 51
Планирование и диспетчеризация процессов и задач… 53
Стратегии планирования… 53
Дисциплины диспетчеризации… 54
Качество диспетчеризации и гарантии обслуживания… 60
Диспетчеризация задач с использованием динамических приоритетов.… 62
Память и отображения, виртуальное адресное пространство… 67
Простое непрерывное распределение и распределение с перекрытием
(оверлейные структуры)… 70
Распределение статическими и динамическими разделами… 72
Разделы с фиксированными границами… 73
Разделы с подвижными границами… ;… 75
Сегментная, страничная и сегментно-страничная организация памяти..... 76
Сегментный способ организации виртуальной памяти… 77
Страничный способ организации виртуальной памяти… .82
Сегментно-страничный способ организации виртуальной памяти… 86
Распределение оперативной памяти в современных ОС для ПК… 88
Распределение оперативной памяти в MS-DOS… 89
Распределение оперативной памяти в Microsoft Windows 95/98 ....;… 92
Распределение оперативной памяти в Microsoft Windows NT… 95
Контрольные вопросы и задачи… 99
Вопросы для проверки… 99
Глава 3.Особенности архитектуры микропроцессоров 180x86… 100
Реальный и защищенный режимы работы процессора… 100
Новые системные регистры микропроцессоров i80x86… 102
Адресация в 32-разрядных микропроцессорах i80x86 при работе
в защищенном режиме… 104
Поддержка сегментного способа организации виртуальной памяти… 104
Поддержка страничного способа организации виртуальной памяти..... 108
Режим виртуальных машин для исполнения приложений
реального режима… 111
Защита адресного пространства задач… 112
Уровни привилегий для защиты адресного пространства задач… 113
Механизм шлюзов для передачи управления на сегменты кода
с другими уровнями привилегий… 115
Система прерываний 32-разрядных микропроцессоров i80x86…:… 119
Работа системы прерываний в реальном режиме работы процессора... 119
Работа системы прерываний в защищенном режиме работы процессора.. 123
Контрольные вопросы и задачи… 127
Вопросы для проверки… 127
Глава 4.Управление вводом/выводом и файловые системы… 129
Основные понятия и концепции организации ввода/вывода в ОС… 130
Режимы управления вводом/выводом… 133
Закрепление устройств, общие устройства ввода/вывода…. 135
Основные системные таблицы ввода/вывода… 136
Синхронный и асинхронный ввод/вывод… 140
Кэширование операций ввода/вывода при работе с накопителями
на магнитных дисках… 142
Функции файловой системы ОС и иерархия данных… 146
Структура магнитного диска (разбиение дисков на разделы)… 147
Файловая система FAT… 156
Таблица размещения файлов… 156
Структура загрузочной записи DOS… 160
Файловые системы VFAT и FAT32… 162
Файловая система HPFS… 167
Файловая система NTFS (New Technology File System)… 178
Основные возможности файловой системы NTFS… 178
Структура тома с файловой системой NTFS… 180
Возможности файловой системы NTFS по ограничению доступа
к файлам и каталогам… 185
Основные отличия FAT и NTFS… 187
Контрольные вопросы и задачи… 188
Вопросы для проверки… 188
Задания… 189
Глава 5.Архитектура операционных систем и интерфейсы
прикладного программирования… 191
Основные принципы построения операционных систем… 191
Принцип модульности… 191
Принцип функциональной избирательности… 192
Принцип генерируемое™ ОС.… 192
Принцип функциональной избыточности… 193
Принцип виртуализации… 193
Принцип независимости программ от внешних устройств… 195
Принцип совместимости… :… 195
Принцип открытой и наращиваемой ОС… 196
Принцип мобильности (переносимости)… 197
Принцип обеспечения безопасности вычислений… 197
Микроядерные операционные системы… 199
Монолитные операционные системы… 201
Требования, предъявляемые к ОС реального времени.… 202
Мультипрограммность и многозадачность… 203
Приоритеты задач (потоков)… 203
Наследование приоритетов… 204
Синхронизация процессов и задач… 204
Предсказуемость… 205
Принципы построения интерфейсов операционных систем… 205
Интерфейс прикладного программирования… 207
Реализация функций API на уровне ОС… 208
Реализация функций API на уровне системы программирования… 209
Реализация функций API с помощью внешних библиотек… 211
Платформенно-независимый интерфейс POSIX… 213
Пример программирования в различных API ОС…. 216
Текст программы для Windows (WinAPI)… 216
Текст программы для Linux (POSIX API)… 218
Контрольные вопросы и задачи… 219
Вопросы для проверки… 219
Глава 6.Проектирование параллельных взаимодействующих
вычислительных процессов… 221
Независимые и взаимодействующие вычислительные процессы…. 221
Средства синхронизации и связи при проектировании
взаимодействующих вычислительных процессов… .227
Использование блокировки памяти при синхронизации параллельных
процессов… 227
Синхронизация процессов посредством операции
«ПРОВЕРКА И УСТАНОВКА»… 233
Семафорные примитивы Дейкстры… 236
Использование семафоров при проектировании взаимодействующих
вычислительных процессов….… 242
Мониторы Хоара… 250
Почтовые ящики… 253
Конвейеры и очереди сообщений… 255
Конвейеры (программные каналы)… 255
Очереди сообщений… 257
Примеры создания параллельных взаимодействующих
вычислительных процессов… 258
Пример создания многозадачного приложения с помощью системы
программирования Borland Delphi… 259
Пример создания комплекса параллельных взаимодействующих программ, выступающих как самостоятельные
вычислительные процессы… 262
Контрольные вопросы и задачи… 267
Вопросы для проверки… 267
Глава 7.Проблема тупиков и методы борьбы с ними… 269
Понятие тупиковой ситуации при выполнении параллельных
вычислительных процессов… 269
Примеры тупиковых ситуаций и причины их возникновения… 271
Пример тупика на ресурсах типа CR… 271
Пример тупика на ресурсах типа CR и SR… 273
Пример тупика на ресурсах типа SR… 274
Формальные модели для изучения проблемы тупиковых ситуаций… 276
Сети Петри… 276
Вычислительные схемы… 281
Модель пространства состояний системы… 283
Методы борьбы с тупиками… 287
Предотвращение тупиков… 287
Обход тупиков… 288
Обнаружение тупика… 291
Контрольные вопросы и задачи… 300
Вопросы для проверки… 300
Глава 8.Современные операционные системы… 301
Семейство операционных систем UNIX… 301
Общая характеристика семейства операционных систем UNIX,
особенности архитектуры семейства ОС UNIX… 301
Основные понятия системы UNIX… 303
Функционирование системы UNIX… 308
Файловая система… 311
Межпроцессные коммуникации в UNIX… 316
Операционная система Linux… 323
Семейство операционных систем OS/2 Warp компании IBM…. 325
Особенности архитектуры и основные возможности OS/2 Warp… 328
Особенности интерфейса OS/2 Warp… 331
Серверная операционная система OS/2 Warp 4.5… 332
Сетевая ОС реального времени QNX… 334
Архитектура системы QNX… 335
Основные механизмы QNX для организации
распределенных вычислений… 339
Контрольные вопросы и задачи… 344
Вопросы для проверки… 344
Часть II.Трансляторы, формальные языки и грамматики
Глава 9.Формальные языки и грамматики… 347
Языки и цепочки символов. Способы задания языков… 347
Цепочки символов. Операции над цепочками символов… 347
Понятие языка. Формальное определение языка… 348
Способы задания языков… 349
Синтаксис и семантика языка… 350
Особенности языков программирования… 351
Определение грамматики. Форма Бэкуса—Наура… 353
Понятие о грамматике языка… 353
Формальное определение грамматики. Форма Бэкуса—Наура… 354
Принцип рекурсии в правилах грамматики… 356
Другие способы задания грамматик… 357
Классификация языков и грамматик… 360
Классификация грамматик. Четыре типа грамматик по Хомскому… 361
Классификация языков… 363
Примеры классификации языков и грамматик… 365
Цепочки вывода. Сентенциальная форма… 367
Вывод. Цепочки вывода… 367
Сентенциальная форма грамматики. Язык, заданный грамматикой… 369
Левосторонний и правосторонний выводы… 370
Дерево вывода. Методы построения дерева вывода… 370
Проблемы однозначности и эквивалентности грамматик… 372
Однозначные и неоднозначные грамматики… 372
Эквивалентность и преобразование грамматик… 373
Правила, задающие неоднозначность в грамматиках… 376
Распознаватели. Задача разбора… 376
Общая схема распознавателя… 376
Виды распознавателей… 378
Классификация распознавателей по типам языков… 380
Задача разбора (постановка задачи)… 382
Контрольные вопросы и задачи… 383
Вопросы… 383
Задачи…. 384
Глава 10.Регулярные языки… 387
Регулярные языки и грамматики… 387
Леволинейные и праволинейные грамматики. Автоматные грамматики... 387 Алгоритм преобразования регулярной грамматики к автоматному виду... 388 Пример преобразования регулярной грамматики к автоматному виду... 390
Конечные автоматы… 391
Определение конечного автомата… ... 391
Детерминированные и недетерминированные конечные автоматы… 392
Преобразование конечного автомата к детерминированному виду… 393
Минимизация конечных автоматов… 395
Регулярные множества и регулярные выражения… 397
Определение регулярного множества… •. 397
Регулярные выражения. Свойства регулярных выражений… 398
Уравнения с регулярными коэффициентами… 399
Способы задания регулярных языков… 403
Три способа задания регулярных языков… 403
Связь регулярных выражений и регулярных грамматик… 404
Связь регулярных выражений и конечных автоматов… 407
Связь регулярных грамматик и конечных автоматов… 408
Пример построения конечного автомата на основе
заданной грамматики… 410
Свойства регулярных языков… 413
Свойства регулярных языков… 413
Лемма о разрастании для регулярных языков… 414
Контрольные вопросы и задачи… 415
Вопросы… 415
Задачи… 416
Глава 11.Контекстно-свободные языки… 418
Распознаватели КС-языков. Автоматы с магазинной памятью… 418
Определение МП-автомата… 418
Эквивалентность языков МП-автоматов и КС-грамматик… 420
Детерминированные МП-автоматы… 423
Свойства КС-языков… 423
Свойства произвольных КС-языков… 423
Свойства детерминированных КС-языков… 424
Лемма о разрастании КС-языков… 425
Преобразование КС-грамматик. Приведенные грамматики..… 426
Преобразование грамматик. Цель преобразования… 426
Приведенные грамматики… 427
Удаление недостижимых символов…… 427
Удаление бесплодных символов… 427
Устранение Х-правил… 429
Устранение цепных правил… 431
КС-грамматики в нормальной форме… 433
Грамматики в нормальной форме Хомского… 433
Устранение левой рекурсии. Грамматики в нормальной форме Грейбах.. 437
Распознаватели КС-языков с возвратом… 441
Принципы работы распознавателей с возвратом… 441
Нисходящий распознаватель с возвратом…,... 443
Распознаватель на основе алгоритма «сдвиг-свертка»… 449
Табличные распознаватели для КС-языков… 455
Общие принципы работы табличных распознавателей… 455
Алгоритм Кока—Янгера—Касами… 456
Алгоритм Эрли (основные принципы)… 457
Принципы построения распознавателей КС-языков без возвратов… 458
Контрольные вопросы и задачи.… 460
Вопросы… 460
Задачи… 461
Глава 12.Классы КС-языков и грамматик..… 463
Нисходящие распознаватели КС-языков без возвратов… 463
Левосторонний разбор по методу рекурсивного спуска… 463
Определение ЩК)-грамматики… 471
Принципы построения распознавателей для Щ!<)-грамматик… 474
Алгоритм разбора для Щ1)-грамматик… 475
Восходящие распознаватели КС-языков без возвратов… 486
Определение ЬН(К)-грамматики… 486
Принципы построения распознавателей для 1В(К)-грамматик… 489
Грамматики предшествования (основные принципы)… 497
Грамматики простого предшествования… 498
Грамматики операторного предшествования… 508
Соотношение классов КС-языков и КС-грамматик… 519
Особенности восходящих и нисходящих распознавателей… 519
Отношения между классами КС-грамматик… 521
Отношения между классами КС-языков… 524
Контрольные вопросы и задачи… 525
Вопросы…. 525
Задачи…. 527
Глава 13.Основные принципы построения трансляторов… 529
Трансляторы, компиляторы и интерпретаторы — общая схема работы… 529
Определение транслятора, компилятора, интерпретатора… 529
Этапы трансляции. Общая схема работы транслятора… 535
Понятие прохода. Многопроходные и однопроходные компиляторы… 538
Интерпретаторы. Особенности построения интерпретаторов… 540
Трансляторы с языка ассемблера («ассемблеры»)… 542
Таблицы идентификаторов. Организация таблиц идентификаторов… 548
Назначение и особенности построения таблиц идентификаторов… 548
Простейшие методы построения таблиц идентификаторов… 550
Построение таблиц идентификаторов по методу бинарного дерева… 551
Хэш-функции и хэш-адресация…. 554
Комбинированные способы построения таблиц идентификаторов… 563
Лексические анализаторы (сканеры). Принципы построения сканеров… 564
Назначение лексического анализатора… 564
Принципы построения лексических анализаторов… 568
Построение лексических анализаторов… 570
Автоматизация построения лексических анализаторов
(программа LEX)… 576
Синтаксические анализаторы. Синтаксически управляемый перевод… 577
Основные принципы работы синтаксического анализатора… 577
Дерево разбора. Преобразование дерева разбора в дерево операций... 579 Автоматизация построения синтаксических анализаторов
(программа YACC)… 582
Контрольные вопросы и задачи… 583
Вопросы… 583
Задачи… 585
Глава 14.Генерация и оптимизация кода… 588
Семантический анализ и подготовка к генерации кода… 588
Назначение семантического анализа… 588
Этапы семантического анализа… 589
Идентификация лексических единиц языков программирования… 594
Распределение памяти. Принципы распределения памяти… 597
Дисплей памяти процедуры (функции). Стековая организация
дисплея памяти… 603
Память для типов данных (RTTI-информация)… 610
Генерация кода. Методы генерации кода… 612
Общие принципы генерации кода.
Синтаксически управляемый перевод… 612
Способы внутреннего представления программ… 615
Обратная польская запись операций… 619
Схемы СУ-перевода… 622
Оптимизация кода. Основные методы оптимизации… 630
Общие принципы оптимизации кода… 630
Оптимизация линейных участков программы… 634
Другие методы оптимизации программ… 641
Машинно-зависимые методы оптимизации… 648
Контрольные вопросы и задачи… 650
Вопросы… 650
Задачи… 652
Глава 15.Современные системы программирования… 655
Понятие и структура системы программирования… 655
История возникновения систем программирования… 655
Структура современной системы программирования… 658
Принципы функционирования систем программирования… 660
Функции текстовых редакторов в системах программирования… 660
Компилятор как составная часть системы программирования… 661
Компоновщик. Назначение и функции компоновщика… 662
Загрузчики и отладчики. Функции загрузчика… 663
Библиотеки подпрограмм как составная часть
систем программирования..................................................
Дополнительные возможности систем программирования… 668
Лексический анализ «на лету». Система подсказок и справок… .668
Разработка программ в архитектуре «клиент—сервер»… 669
Разработка программ в трехуровневой архитектуре.
Серверы приложений… g7Q
Примеры современных систем программирования… 672
Системы программирования компании Borland/Inprise… 672
Системы программирования фирмы Microsoft… 677
Системы программирования под ОС Linux и UNIX… .682
Разработка программного обеспечения для сети Интернет… 687
Контрольные вопросы и задачи… 696
Вопросы ...................................................
Задачи ' ' • •… '..'.'. '.'•'. '.'. '.'. '.'.'. '.'.'.'.'.'. 698
Приложение А.Тексты программы параллельных
взаимодействующих задач 700
Приложение Б.Тексты программ комплекса параллельных
взаимодействующих приложений!… 709
Список литературы… 719
Алфавитный указатель… 725
Предисловие
Настоящий учебник предназначается в первую очередь студентам технических вузов, хотя может быть востребован и обычными подготовленными пользователями, желающими углубить свои познания в области системного программного обеспечения.
Согласно Государственному образовательному стандарту, по которому ведется обучение студентов, поступивших в вузы до 2000 г., в рамках дисциплины «Системное программное обеспечение», относящейся к обязательным специальным дисциплинам учебного плана по направлению «Информатика и вычислительная техника», студент должен изучить следующие обязательные разделы: «… назначение, функции и структура операционной системы (ОС); понятие процесса; управление процессами, способы диспетчеризации процессов; понятие ресурса, виды ресурсов, управление ресурсами; управление памятью; устройства, виды устройств, драйверы устройств, устройства в MS-DOS; файловая система на диске, структура логического диска в MS-DOS; синхронизация процессов, семафоры, сообщения, использование семафоров для решения задач взаимоисключения и синхронизации; тупики, способы борьбы с тупиками; загрузка и настройка ОС, файлы конфигурирования MS-DOS, основные команды MS-DOS; обзор современных ОС; трансляторы; формальные языки и грамматики, типы грамматик; вывод цепочек; конечный и магазинный автоматы, распознаватели и преобразователи, построение автомата по заданной грамматике; структура компиляторов и интерпретаторов, лексический, синтаксический и семантический анализаторы, генератор кода; распределение памяти, виды переменных; статическое и динамическое связывание; загрузчики; функции загрузчика; настраивающий и динамический загрузчики; подключение библиотек».
В новой редакции Государственного образовательного стандарта, который вступил в силу в 2000 г. и относится к поколению студентов, поступивших в вузы осенью 2000 г. и позже, несколько изменено основное содержание этой дисциплины. В частности, в стандарте записано, что в рамках дисциплины «Системное программное обеспечение» должны изучаться следующие обязательные разделы: «… пользовательский интерфейс операционной среды; управление задачами; управление памятью; управление вводом/выводом; управление файлами; пример современной операционной системы; программирование в операционной среде; ассемблеры; мобильность программного обеспечения; макроязыки; трансляторы;
формальные языки и грамматики, типы грамматик; вывод цепочек; конечный и магазинный автоматы, распознаватели и преобразователи, построение автомата по заданной грамматике; структура компиляторов и интерпретаторов, лексический, синтаксический и семантический анализаторы, генератор кода; распределение памяти, виды переменных; статическое и динамическое связывание; загрузчики; функции загрузчика; настраивающий и динамический загрузчики; подключение библиотек».
Таким образом, мы можем констатировать, что в основном в дисциплине «Системное программное обеспечение» должно уделяться внимание операционным системам, средам и системам программирования. Именно в таком ключе в основном и строится настоящий учебник, поскольку предполагается, что его читателями, прежде всего, будут студенты, обучающиеся по специальностям, относящимся к направлению «Информатика и вычислительная техника». Учебный материал, ставший основой для настоящего учебника, уже в течение нескольких лет изучается студентами специальности 22.01.00 в Санкт-Петербургском государств^н-ном университете аэрокосмического приборостроения. Другими словами, по существу, в основу учебника лег расширенный конспект лекций по дисциплине «Системное программное обеспечение». Эта дисциплина изучается в течение двух семестров. В первом семестре рассматриваются операционные системы (принципы их построения и функционирования, вопросы создания параллельных взаимодействующих задач, выполняющихся в мультизадачных операционных системах), а во втором — формальные грамматики, трансляторы и системы программирования. Поэтому книга разбита на две крупные части. Эти две части связаны между собой не потому, что так построен план изучения дисциплины. Материал, рассматриваемый в каждой из частей учебника, тесно связан с вопросами, изучаемыми в другой ее части. Таким образом, детальное изучение материала любой части книги требует по крайней мере знакомства с основными понятиями всего учебника. Так, например, изучение структуры и технических аспектов работы компиляторов невозможно без знания принципов распределения памяти, которые относятся к вопросам построения операционных систем. Именно поэтому эти два крупных раздела объединены авторами в одну книгу и совместно представляются вниманию читателей.
Помимо общетеоретических вопросов в учебнике рассмотрены и отдельные практические вопросы, описаны конкретные реализации различных системных программ.
В первой части учебника, прежде всего, излагаются основные понятия ОС, принципы их построения и функционирования. В последние годы практически повсеместно ПК работают под управлением современных 32-битовых ОС, использующих аппаратные возможности микропроцессоров для создания и организации эффективных и защищенных вычислений. Мы посчитали необходимым рассмотреть в первой части учебника эти вопросы.
Наиболее популярными ОС являются системы Windows 95/98, Windows NT 4.0, начинается переход к Windows ME и семейству ОС Windows 2000 компании Microsoft. По этим ОС имеется огромное количество самых разнообразных публикаций, в том числе и учебных материалов, объем которых порой очень велик. В то же время по остальным ОС публикаций существенно меньше. Поэтому
в первой части настоящего учебного пособия мы в качестве примеров операционных систем и сред кратко рассматриваем такие ОС, как OS/2 Warp, UNIX и Linux, QNX. Естественно, что отдельные вопросы иллюстрируются и на примере популярных ОС Windows 95/98 и Windows NT 4.0.
Во второй части учебника рассматриваются как общие вопросы, связанные с по-строением трансляторов, так и методы их практической реализации от примитивных распознавателей текста до законченных систем программирования. Практическая реализация компиляторов и интерпретаторов рассматривается с точки зрения современных широко распространенных языков программирования высокого уровня, таких как Pascal, С и C++.
Кратко рассматриваются также практические вопросы построения прикладных программ на основе архитектуры «клиент—сервер» и трехзвенной архитектуры, ориентированной на работу с серверами баз данных и серверами приложений. Эти вопросы затрагиваются не с точки зрения технологии их реализации (такие сведения можно найти в появившейся сейчас специализированной литературе) в той или иной ОС, а со стороны методов разработки соответствующих прикладных программ с помощью той или иной системы программирования. Для более детального знакомства с конкретными реализациями читатели могут воспользоваться приводимыми авторами ссылками на литературные источники или на соответствующие технические публикации в глобальной сети Интернет. Таким образом, данный учебник должен быть полезен не только тем, кто хочет детально изучить системное программное обеспечение, но и тем, кто собирается сам разработать отдельные компоненты, в том числе отдельные системные утилиты, распознаватели и интерпретаторы команд, компоновщик или транслятор с некоторого языка, создать комплекс параллельно исполняющихся взаимодействующих программ. В учебнике рассматриваются вопросы, которые полезно знать в любом случае, если разработчик прикладной программы имеет дело с некоторым входным языком (которым может быть далеко не только язык программирования, но и любой другой язык команд, в том числе заданный пользователем или определенный в некоторой прикладной области). Примеры систем программирования, которые рассматриваются в этом учебнике, предназначены для работы в среде перечисленных выше операционных систем. Фрагменты программ, приведенные в книге, написаны на языках программирования высокого уровня Pascal и С.
В этом коротком предисловии мы, как авторы этой книги, хотим еще высказать самые теплые слова благодарности своим родным и близким за их долгое терпение, доброжелательность и сердечную заботу в течение всего времени подборки материалов, написания книга и ее «бесконечного» улучшения, благодаря которым только и мог появиться на свет этот труд, вынужденно оторвавший нас на некоторое время от домашних забот и хлопот. Хочется поблагодарить и Горде-ева В. А. за конструктивную критику и помощь в подготовке отдельных программ. Авторы признательны также сотрудникам издательства «Питер» Васильеву А. В. и Ваулиной Е. Ю. за их терпеливое и внимательное отношение в процессе подготовки текста книги, его обработки и корректуры. Наше взаимное уважение и сотрудничество позволили довести учебный материал книги «до ума», хотя это и не всегда удавалось сделать в заранее оговоренные сроки.
От издательства
Ваши замечания, предложения, вопросы отправляйте по адресу электронной почты comp@piter.com (издательство «Питер», компьютерная редакция). Мы будем рады узнать ваше мнение!
Подробную информацию о наших книгах вы найдете на Web-сайте издательства www.piter.com.
А
ЧАСТЬ I Операционные