<<

В.Е. Карпов К.А. Коньков. Основы операционных систем. 2005

Книга представляет собой систематизированный учебный курс по теории операционных систем. В ней рассмотрены фундаментальные принципы построения и особенности проектирования современных ОС. Теоретический материал дополнен разнообразными практическими примерами. Рекомендовано для студентов высших учебных заведений, обучающихся по специальностям в области информационных технологий.

<< | >>

О проекте

Предисловие

Об авторах

Часть I. Обзор

Лекция 1. Введение

Что такое операционная система

Что такое ОС

Операционная система как виртуальная машина

Операционная система как менеджер ресурсов

Операционная система как защитник пользователей и программ

Операционная система как постоянно функционирующее ядро

Краткая история эволюции вычислительных систем

Первый период (1945-1955 гг.). Ламповые машины. Операционных систем нет

Второй период (1955 г.-начало 1960-х гг.). Компьютеры на основе транзисторов. Пакетные операционные системы

Третий период (начало 1960-х - 1980г.). Компьютеры на основе интегральных микросхем. Первые многозадачные ОС

Четвертый период (с 1980 г. по настоящее время) Персональные компьютеры. Классические, сетевые и распределенные системы

Основные понятия, концепции ОС

Системные вызовы

Прерывания

Исключительные ситуации

Процессы, нити

Архитектурные особенности ОС

Монолитное ядро

Многоуровневые системы (Layered Systems)

Виртуальные машины

Микроядерная архитектура

Смешанные системы

Классификация ОС

Реализация многозадачности

Многопроцессорная обработка

Системы реального времени

Заключение

Приложение 1. Некоторые сведения об архитектуре компьютера

Взаимодействие с периферийными устройствами

Часть II. Процессы и их поддержка в операционной системе

Лекция 2. Процессы

Понятие процесса

Состояния процесса

Операции над процессами и связанные с ними понятия Набор операций

Process Control Block и контекст процесса

Одноразовые операции

Многоразовые операции

Переключение контекста

Заключение

Лекция 3. Планирование процессов

Уровни планирования

Критерии планирования и требования к алгоритмам

Параметры планирования

Вытесняющее и невытесняющее планирование

Алгоритмы планирования

First-Come, First-Served (FCFS)

Round Robin (RR)

Shortest-Job-First (SJF)

Гарантированное планирование

Приоритетное планирование

Многоуровневые очереди (Multilevel Queue)

Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)

Заключение

Лекция 4. Кооперация процессов и основные аспекты ее логической организации

Взаимодействующие процессы

Категории средств обмена информацией

Логическая организация механизма передачи информации

Как устанавливается связь?

Информационная валентность процессов и средств связи

Особенности передачи информации с помощью линий связи

Буферизация

Поток ввода/вывода и сообщения

Надежность средств связи

Как завершается связь?

Нити исполнения

Заключение

Лекция 5. Алгоритмы синхронизации

Interleaving, race condition и взаимоисключения

Критическая секция

Программные алгоритмы организации взаимодействия процессов Требования, предъявляемые к алгоритмам

Запрет прерываний

Переменная-замок

Строгое чередование

Флаги готовности

Алгоритм Петерсона

Алгоритм булочной (Bakery algorithm)

Аппаратная поддержка взаимоисключений

Команда Test-and-Set (проверить и присвоить 1)

Команда Swap (обменять значения)

Заключение

Лекция 6. Механизмы синхронизации

Семафоры

Концепция семафоров

Решение проблемы producer-consumerс помощью семафоров

Мониторы

Сообщения

Эквивалентность семафоров, мониторов и сообщений

Реализация мониторов и передачи сообщений с помощью семафоров

Реализация семафоров и передачи сообщений с помощью мониторов

Реализация семафоров и мониторов с помощью очередей сообщений

Заключение

Лекция 7. Тупики

Введение

Условия возникновения тупиков

Основные направления борьбы с тупиками

Игнорирование проблемы тупиков

Способы предотвращения тупиков

Способы предотвращения тупиков путем тщательного распределения ресурсов. Алгоритм банкира

Предотвращение тупиков за счет нарушения условий возникновения тупиков

Нарушение условия взаимоисключения

Нарушение условия ожидания дополнительных ресурсов

Нарушение принципа отсутствия перераспределения

Нарушение условия кругового ожидания

Обнаружение тупиков

Восстановление после тупиков

Заключение

Часть III. Управление памятью

Лекция 8. Организация памяти компьютера. Простейшие схемы управления памятью

Введение

Физическая организация памяти компьютера

Локальность

Логическая память

Связывание адресов

Функции системы управления памятью

Простейшие схемы управления памятью

Схема с фиксированными разделами

Один процесс в памяти

Оверлейная структура

Динамическое распределение. Свопинг

Схема с переменными разделами

Страничная память

Сегментная и сегментно-страничная организация памяти

Заключение

Лекция 9. Виртуальная память. Архитектурные средства поддержки виртуальной памяти

Понятие виртуальной памяти

Архитектурные средства поддержки виртуальной памяти

Страничная виртуальная память

Сегментно-страничная организации виртуальной памяти

Структура таблицы страниц

Ассоциативная память

Инвертированная таблица страниц

Размер страницы

Заключение

Лекция 10. Аппаратно-независимый уровень управления виртуальной памятью

Исключительные ситуации при работе с памятью

Стратегии управления страничной памятью

Алгоритмы замещения страниц

Алгоритм FIFO. Выталкивание первой пришедшей страницы

Аномалия Билэди (Belady)

Оптимальный алгоритм (ОРТ)

Выталкивание дольше всего не использовавшейся страницы. Алгоритм LRU

Выталкивание редко используемой страницы. Алгоритм NFU

Другие алгоритмы

Управление количеством страниц, выделенным процессу. Модель рабочего множества

Трешинг ( Thrashing)

Модель рабочего множества

Страничные демоны

Программная поддержка сегментной модели памяти процесса

Отдельные аспекты функционирования менеджера памяти

Заключение

Часть IV. Файловые системы

Лекция 11. Файлы с точки зрения пользователя

Введение

Общие сведения о файлах Имена файлов

Типы файлов

Атрибуты файлов

Организация файлов и доступ к ним

Последовательный файл

Файл прямого доступа

Другие формы организации файлов

Операции над файлами

Директории. Логическая структура файлового архива

Разделы диска. Организация доступа к архиву файлов

Операции над директориями

Защита файлов

Контроль доступа к файлам

Списки прав доступа

Заключение

Лекция 12. Реализация файловой системы

Общая структура файловой системы

Управление внешней памятью

Методы выделения дискового пространства

Выделение непрерывной последовательностью блоков

Связный список

Таблица отображения файлов

Индексные узлы

Управление свободным и занятым дисковым пространством

Учет при помощи организации битового вектора

Учет при помощи организации связного списка

Размер блока

Структура файловой системы на диске

Реализация директорий

Примеры реализации директорий в некоторых ОС Директории в ОС МБ-ООБ

Директории в ОС Unix

Поиск в директории

Линейный поиск

Хеш-таблица

Другие методы поиска

Монтирование файловых систем

Связывание файлов

Кооперация процессов при работе с файлами

Примеры разрешения коллизий и тупиковых ситуаций

Надежность файловой системы

Целостность файловой системы

Порядок выполнения операций

Журнализация

Проверка целостности файловой системы при помощи утилит

Управление «плохими» блоками

Производительность файловой системы

Кэширование

Оптимальное размещение информации на диске

Реализация некоторых операций над файлами

Системные вызовы, работающие с символическим именем файла

Связывание файла

Удаление файла

Системные вызовы, работающие с файловым дескриптором

Функции ввода-вывода из файла

Современные архитектуры файловых систем

Заключение

Часть V. Ввод-вывод

Лекция 13. Система управления вводом-выводом

Физические принципы организации ввода-вывода

Общие сведения об архитектуре компьютера

Структура контроллера устройства

Опрос устройств и прерывания. Исключительные ситуации и системные вызовы

Прямой доступ к памяти (Direct Memory Access - DMA)

Логические принципы организации ввода-вывода

Структура системы ввода-вывода

Систематизация внешних устройств и интерфейс между базовой подсистемой ввода-вывода и драйверами

Функции базовой подсистемы ввода-вывода

Блокирующиеся, неблокирующиеся и асинхронные системные вызовы

Буферизация и кэширование

Спулинг и захват устройств

Обработка прерываний и ошибок

Планирование запросов

Алгоритмы планирования запросов к жесткому диску

Строение жесткого диска и параметры планирования

Алгоритм First Come First Served (FCFS)

Алгоритм Short Seek Time First (SSTF)

Алгоритмы сканирования (SCAN, C-SCAN, LOOK, C-LOOK)

Заключение

Часть VI. Сети и сетевые операционные системы

Лекция 14. Сети и сетевые операционные системы

Для чего компьютеры объединяют в сети

Сетевые и распределенные операционные системы

Взаимодействие удаленных процессов как основа работы вычислительных сетей

Основные вопросы логической организации передачи информации между удаленными процессами

Понятие протокола

Многоуровневая модель построения сетевых вычислительных систем

Проблемы адресации в сети

Одноуровневые адреса

Двухуровневые адреса

Удаленная адресация и разрешение адресов

Локальная адресация. Понятие порта

Полные адреса. Понятие сокета (socket)

Проблемы маршрутизации в сетях

Связь с установлением логического соединения и передача данных с помощью сообщений

Синхронизация удаленных процессов

Заключение

Часть VII. Проблемы безопасности операционных систем

Лекция 15. Основные понятия информационной безопасности

Введение

Угрозы безопасности

Формализация подхода к обеспечению информационной безопасности

Криптография как одна из базовых технологий безопасности ОС

Шифрование с использованием алгоритма RSA

Теорема Эйлера

Заключение

Лекция 16. Защитные механизмы операционных систем

Идентификация и аутентификация

Пароли, уязвимость паролей

Шифрование пароля

Авторизация. Разграничение доступа к объектам ОС

Домены безопасности

Матрица доступа

Список прав доступа. Access control list

Мандаты возможностей. Capability list

Другие способы контроля доступа

Смена домена

Недопустимость повторного использования объектов

Выявление вторжений. Аудит системы защиты

Анализ некоторых популярных ОС с точки зрения их защищенности

NetWare, IntranetWare

Windows NT/2000/XP

Заключение

Семинары

Семинары 1-2. Введение в курс практических заня- тий. Знакомство с операционной системой UNIX

Введение в курс практических занятий

Краткая история операционной системы UNIX, ее структура

Системные вызовы и библиотека libe

Понятия login и password

Вход в систему и смена пароля

Упрощенное понятие об устройстве файловой системы в UNIX. Полные и относительные имена файлов

Понятие о текущей директории. Команда pwd. Относительные имена файлов

Домашняя директория пользователя и ее определение

Команда man - универсальный справочник

Команды cd - для смены текущей директории и Is - для просмотра состава директории

Путешествие по структуре файловой системы

Команда cat и создание файла. Перенаправление ввода и вывода

Создание файла с помощью команды cat

Шаблоны имен файлов

История редактирования файлов - ed, vi

Система Midnight Commander - me. Встроенный тс редактор и редактор joe

Пользователь и группа. Команды chown и chgrp. Права доступа к файлу

Команда 1в с опциями -а1. Использование команд сИтос) и итавк

Маска создания файлов текущего процесса

Команда umask

Системные вызовы деипс! и де!д1с1

Компиляция программ на языке С в 1Ш1Х и запуск их на счет

Написание, компиляция и запуск программы с использованием системных вызовов getuid() и getgidQ

Семинары 3-4. Процессы в операционной системе UNIX

Понятие процесса в UNIX. Его контекст

Идентификация процесса

Состояния процесса. Краткая диаграмма состояний

Иерархия процессов

Системные вызовы getppid() и getpid()

Написание программы с использованием getpid() и getppid()

Создание процесса в UNIX. Системный вызов fork()

Системный вызов для порождения нового процесса

Прогон программы с fork() с одинаковой работой родителя и ребенка

Системный вызов fork() (продолжение)

Написание, компиляция и запуск программы с использованием вызова fork() с разным поведением процессов ребенка и родителя

Завершение процесса. Функция exit()

Параметры функции main() в языке С. Переменные среды и аргументы командной строки

Написание, компиляция и запуск программы, распечатывающей аргументы командной строки и параметры среды

Изменение пользовательского контекста процесса. Семейство функций для системного вызова ехес()

Функции изменения пользовательского контекста процесса

Прогон программы с использованием системного вызова ехес ()

Написание, компиляция и запуск программы для изменения пользовательского контекста в порожденном процессе

Семинар 5. Организация взаимодействия процессов через pipe и FIFO в UNIX

Понятие о потоке ввода-вывода

Понятие о работе с файлами через системные вызовы и стандартную библиотеку ввода-вывода для языка С

Файловый дескриптор

Открытие файла. Системный вызов ореп()

Системные вызовы read(), write(), close()

Системный вызов close

Прогон программы для записи информации в файл

Написание, компиляция и запуск программы для чтения информации из файла

Понятие о pipe. Системный вызов pipe()

Прогон программы для pipe в одном процессе

Организация связи через pipe между процессом- родителем и процессом-потомком. Наследование файловых дескрипторов при вызовах fork() и ехес()

Прогон программы для организации однонаправленной связи между родственными процессами через pipe

Написание, компиляция и запуск программы для организации двунаправленной связи между родственными процессами через pipe

Особенности поведения вызовов read() и writeQ для pip’a

Системные вызовы read и write (продолжение) Особенности поведения при работе с pipe, FIFO и socket

Особенности поведения вызова ореп() при открытии FIFO

Прогон программы с FIFO в родственных процессах

Написание, компиляция и запуск программы с FIFO в неродственных процессах

Неработающий пример для связи процессов на различных компьютерах

Семинары 6-7. Средства System VIPC. Организация работы с разделяемой памятью в UNIX. Понятие нитей исполнения (thread)

Преимущества и недостатки потокового обмена данными

Понятие о System V IPC

Пространство имен. Адресация в System V IPC. Функция ftok()

Дескрипторы System V IPC

Разделяемая память в UNIX. Системные вызовы shmget(), shmat(), shmdt()

Системный вызов shmget()

Системный вызов вЬтаЦ)

Прогон программ с использованием разделяемой памяти

Команды ipcs и ipcrm

Использование системного вызова shmctl() для освобождения ресурса

Разделяемая память и системные вызовы fork(), ехес() и функция exit()

Самостоятельное написание, компиляция и запуск программы для организации связи двух процессов через разделяемую память

Понятие о нити исполнения (thread) в UNIX. Идентификатор нити исполнения. Функция pthread_self()

Функция для завершения нити исполнения

Функция pthreadJoin()

Прогон программы с использованием двух нитей исполнения

Написание, компиляция и прогон программы с использованием трех нитей исполнения

Необходимость синхронизации процессов и нитей исполнения, использующих общую память

Семинар 8. Семафоры в UNIX как средство синхронизации процессов

Семафоры в UNIX. Отличие операций над UNIX-семафорами от классических операций

Создание массива семафоров или доступ к уже существующему. Системный вызов semget()

Выполнение операций над семафорами. Системный вызов semop()

Системный вызов semop()

Описание системного вызова

Прогон примера с использованием семафора

Изменение предыдущего примера

Удаление набора семафоров из системы с помо- щью команды ipcrm или системного вызова semctl()

Системный вызов semctl()

Написание, компиляция и прогон программы с организацией взаимоисключения с помощью семафоров для двух процессов, взаимодействующих через разделяемую память

Написание, компиляция и прогон программы с организацией взаимной очередности с помощью семафоров для двух процессов, взаимодействующих через pipe

Понятие о POSIX-семафорах

Семинар 9. Очереди сообщений в UNIX

Сообщения как средства связи и средства синхронизации процессов

Очереди сообщений в UNIX как составная часть System VIPC

Создание очереди сообщений или доступ к уже существующей. Системный вызов msgget()

Системный вызов msgget()

Реализация примитивов send и receive. Системные вызовы msgsnd() и msgrcv()

Системный вызов msgsndO

Удаление очереди сообщений из системы с помощью команды ¡рсгт или системного вызова твдсЫО

Прогон примера с однонаправленной передачей текстовой информации

Модификация предыдущего примера для передачи числовой информации

Написание, компиляция и прогон программ для осуществления двусторонней связи через одну очередь сообщений

Понятие мультиплексирования. Мультиплексирование сообщений. Модель взаимодействия процессов клиент — сер- вер. Неравноправность клиента и сервера

Написание, компиляция и прогон программ клиента и сервера

Использование очередей сообщений для синхронизации работы процессов

Семинары 10-11. Организация файловой системы в UNIX. Работа с файлами и директориями. Понятие о memory mapped файлах

Введение

Разделы носителя информации (partitions) в UNIX

Логическая структура файловой системы и типы файлов в UNIX

Организация файла на диске в UNIX на примере файловой системы s5fs. Понятие индексного узла (inode)

Организация директорий (каталогов) в UNIX

Понятие суперблока

Операции над файлами и директориями

Системные вызовы и команды для выполнения операций над файлами и директориями

Системный вызов creat()

Операция чтения атрибутов файла. Системные вызовы stat (),

Системные вызовы для чтения атрибутов файла

Системный вызов lseek()

Практическое применение команд и системных вызовов для операций над файлами

Специальные функции для работы с содержимым директорий

Функция opendir()

Функция readdir()

Написание, прогон и компиляция программы, анализирующей содержимое директории

Понятие о файлах, отображаемых в память (memory mapped файлах). Системные вызовы mmap(), munmap()

Системный вызов mmap()

Системный вызов munmap

Анализ, компиляция и прогон программы для создания memory mapped файла и записи его содержимого

Изменение предыдущей программы для чтения из файла, используя его отображение в память

Семинары 12-13. Организация ввода-вывода в 1Ш1Х. Файлы устройств. Аппарат прерываний. Сигналы в 1Ш1Х

Понятие виртуальной файловой системы

Операции над файловыми системами. Монтирование файловых систем

Команда umount

Блочные, символьные устройства. Понятие драйвера. Блочные, символьные драйверы, драйверы низкого уровня. Файловый интерфейс

Аппаратные прерывания (interrupt), исключения (exception), программные прерывания (trap, software interrupt). Их обработка

Понятие сигнала. Способы возникновения сигналов и виды их обработки

Понятия группыпроцессов, сеанса, лидера группы, лидера сеанса, управляющего терминала сеанса. Системные вызовы де!рдгр(), Бе1рдгр(), де!рд1с1(), ве1рд1с1(), де1в1с1(), ве181с1()

Системный вызов kîll() и команда kill()

Системный вызов kill()

Изучение получения сигнала SIGHUP процессами при завершении лидера сеанса

Системный вызов signal(). Установка собственного обработчика сигнала

Прогон программы, игнорирующей сигнал SIGINT

Модификация предыдущей программы для игнорирования сигналов SIGINT и SIGQUIT

Прогон программы с пользовательской обработкой сигнала SIGINT

Модификация предыдущей программы для пользовательской обработки сигналов SIGINT и SIGQUIT

Восстановление предыдущей реакции на сигнал

Сигналы SIGUSR1 HSIGUSR2. Использование сигналов для синхронизации процессов

Завершение порожденного процесса. Системный вызов waitpid(). Сигнал SIGCHLD

Системные вызовы wait() и waitpid()

Прогон программы для иллюстрации обработки сигнала SIGCHLD

Возникновение сигнала SIGPIPE при попытке записи в pipe или FIFO, который никто не собирается читать

Понятие о надежности сигналов. POSIX-функции для работы с сигналами

Семинары 14-15. Семейство протоколов TCP/IP. Сокеты (sockets) в UNIX и основы работы с ними

Краткая история семейства протоколов TCP/IP

Общие сведения об архитектуре семейства протоколов TCP/IP

Уровень сетевого интерфейса

Уровень Internet. Протоколы IP, ICMP, ARP, RARP. Internet-адреса

Транспортный уровень. Протоколы TCP и UDP. TCP- и UDP-сокеты. Адресные пространства портов. Понятие encapsulation

Уровень приложений/процессов

Использование модели клиент-сервер для взаимодействия удаленных процессов

Организация связи между удаленными процессами с помощью датаграмм

Сетевой порядок байт. Функции htons(), htonlQ, ntohsQ, ntohlQ

Функции преобразования IP-адресов inet_ntoa(), inet_aton()

Функция Ьгего()

Создание сокета. Системный вызов socket()

Адреса сокетов. Настройка адреса сокета. Системный вызов bind()

Системные вызовы sendto() и recvfrom()

Определение IP-адресов для вычислительного комплекса

Пример программы UDP-клиента

Пример программы UDP-сервера

Организация связи между процессами с помощью установки логического соединения

Установление логического соединения. Системный вызов connect()

Пример программы ТСР-клиента

Как происходит установление виртуального соединения

Системный вызов listen()

Системный вызов listen()

Системный вызов accept()

Пример простого ТСР-сервера

Создание программы с параллельной обработкой запросов клиентов

Применение интерфейса сетевых вызовов для других семейств протоколов. UNIX Domain протоколы. Файлы типа «сокет»

Создание потоковых клиента и сервера для стека UNIX Domain протоколов

Помощь с написанием учебных работ

Книги и учебники по дисциплине Windows:

- Windows - Архитектура компьютера - Интернет - Информатика - Компьютер - Компьютерные и телекоммуникационные системы - Программирование - Социальные сети -

- Английский язык - Астрология - Астрономия - Биология - Военная литература - Журналистика - Компьютерная инженерия - Педагогика - Право - Психология - Социология -