Конспект лекций по курсу опд. Ф. 11. Операционные системы

1 Введение 6

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

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

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

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

1.5 Некоторые сведения об архитектуре компьютера. 17

2 Лекция 1: Процессы 18

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

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

2.3 Операции над процессами и связанные с ними понятия 21

2.4 Заключение 26

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

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

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

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

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

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

3.6 Заключение 40

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

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

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

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

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

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

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

4.6.1 Буферизация 43

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

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

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

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

4.9 Заключение 49

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

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

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

6 Программные алгоритмы организации взаимодействия процессов 53

6.1 Требования, предъявляемые к алгоритмам 53

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

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

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

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

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

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

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

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

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

6.11 Заключение 58

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

7.1 Семафоры 59

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

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

7.2 Мониторы 60

7.3 Сообщения 62

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

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

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

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

7.8 Заключение 65

8 Лекция 7: Тупики 65

8.1 Введение 65

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

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

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

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

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

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

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

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

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

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

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

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

8.10 Заключение 73

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

9.1 Введение 73

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

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

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

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

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

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

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

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

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

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

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

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

9.7 Заключение 83

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

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

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

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

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

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

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

10.7 Функционирование менеджера памяти при наличии ассоциативной памяти. 88

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

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

10.10 Заключение 89

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

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

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

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

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

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

11.6 Оптимальный алгоритм (OPT) 93

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

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

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

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

11.11 Трешинг (Thrashing) 95

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

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

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

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

11.16 Заключение 99

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

12.1 Введение 99

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

12.2.1 Имена файлов 101

12.2.2 Типы файлов 101

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

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

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

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

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

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

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

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

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

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

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

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

12.9 Заключение 108

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

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

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

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

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

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

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

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

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

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

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

13.2.9 Размер блока 113

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

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

13.4 Примеры реализации директорий в некоторых ОС 115

13.4.1 Директории в ОС MS-DOS 115

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

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

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

13.5.2 Хеш-таблица 116

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

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

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

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

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

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

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

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

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

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

13.9.5 Управление "плохими" блоками 122

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

13.10.1 Кэширование 122

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

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

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

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

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

13.13 Заключение 126

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

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

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

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

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

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

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

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

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

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

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

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

14.2.3 Spooling и захват устройств 139

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

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

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

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

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

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

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

14.4 Заключение 143

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15.16 Заключение 159

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

16.1 Введение 160

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

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

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

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

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

16.5 Заключение 167

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

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

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

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

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

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

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

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

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

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

17.5 Смена домена 173

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

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

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

17.8.1 MS-DOS 175

17.8.2 NetWare, IntranetWare 175

17.8.3 OS/2 175

17.8.4 Unix 176

17.8.5 Windows NT/2000/XP 177

17.9 Заключение 178