Кафедра математического обеспечения компьютерных систем

 

 

Н.Ф. Трубина, О.И. Розновец

 

«Операционные системы»

Конспект лекций

 

 

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

направление подготовки - прикладная математика

 

 

 

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

 

Авторы:       

Н.Ф. Трубина, старший преподаватель кафедры математического обеспечения компьютерных систем,

О.И.Розновец, канд. физ.-мат. наук, ассистент кафедры математического обеспечения компьютерных систем

 

 

Рецензенты:

Т.И.Петрушина, кандидат физико-математических наук, заведующая кафедрой математического обеспечения компьютерных систем ОНУ им. И.И.Мечникова;

Ю.Н.Крапивный, кандидат физико-математических наук, доцент кафедры математического обеспечения компьютерных систем ОНУ им. И.И.Мечникова.

 

 

Дисциплина «Операционные системы» ориентирована на изучение концептуального базиса и методов управления ресурсами компьютера. Изучаются варианты реализации многозадачной и многопоточной обработки, организация виртуальной памяти, средства синхронизации, средства файловой системы, логическая и физическая реализация файловых систем и систем управления вводом-выводом.

Настоящее пособие призвано помочь в организации самостоятельной работы студентов, изучающих дисциплину «Операционные системы».

 

Рекомендовано к изданию Учёным советом Института математики, экономики и механики ОНУ им. И. И. Мечникова.

Протокол № 1 от 9 октября 2009 года

                              

Оглавление

 

ВВЕДЕНИЕ.. 10

1 Понятие операционной системы... 11

Контрольные вопросы.. 13

2 Организация компьютерной системы... 14

2.1  Архитектура компьютера с общей шиной. 14

2.2  Структура памяти. 16

2.3  Структура ввода-вывода. 18

Контрольные вопросы.. 20

3 Классификация Операционных Систем... 21

Контрольные вопросы.. 24

4 Функциональные компоненты операционной системы 25

4.1  Управление процессами. 25

4.2  Управление памятью.. 26

4.3  Управление файлами и внешними устройствами. 26

4.4  Безопасность и защита данных. 28

4.5  Интерфейс прикладного программирования. 29

4.6  Пользовательский интерфейс. 30

Контрольные вопросы.. 30

5 СТРУКТУРА операционной системы... 31

5.1  Монолитные системы.. 31

5.2  Многоуровневые системы.. 32

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

5.4  Экзоядро. 37

5.5  Модель клиент-сервер. 37

Контрольные вопросы.. 39

6 Процессы и потоки.. 40

6.1  Концепция процесса. 40

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

6.3  Реализация процессов. 42

6.4  Потоки. 44

6.5  Операции над процессами. 48

6.5.1  Создание процессов. 48

6.5.2  Завершение процессов. 52

Контрольные вопросы.. 53

7 ПЛАНИРОВАНИЕ ПРОЦЕССОРА.. 54

7.1  Планирование процессов. Очереди. 54

7.2  Планировщики. 55

7.3  Моменты перепланировки. Вытеснение. 57

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

7.5  Диспетчеризация. 59

7.6  Критерии планирования процессора. 59

7.7  Стратегии планирования процессора. 60

7.7.1  Планирование в порядке поступления. 60

7.7.2  Стратегия SJF. 61

7.7.3  Приоритетное планирование. 63

7.7.4  Карусельная стратегия планирования. 66

7.7.5  Очереди с обратной связью.. 67

7.7.6  Гарантированное планирование. 68

7.7.7  Лотерейное планирование. 69

7.7.8  Планирование в системах реального времени. 69

7.8  Планирование потоков. 71

7.9  Оценка алгоритмов планирования. 72

7.9.1  Детерминированное моделирование. 73

7.9.2  Моделирование очередей. 74

7.9.3  Имитация. 75

Контрольные вопросы.. 76

8 Взаимодействие процессов.. 77

8.1  Разделяемая память. Проблема производителя и потребителя. 78

8.2  Взаимодействие путем передачи сообщений. 79

8.2.1  Буферизация. 81

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

8.2.3 Вызов удаленных процедур (RPC). 83

Контрольные вопросы.. 84

9 Синхронизация процессов.. 85

9.1  Взаимное исключение и критические участки. 86

9.2  Синхронизация с помощью элементарных приемов нижнего уровня. 87

9.2.1  Запрещение прерываний. 87

9.2.2  Переменные блокировки. 87

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

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

9.2.5  Операция проверки и установки. 90

9.3  Семафоры.. 92

9.3.1  Использование семафоров. 92

9.3.2  Реализация семафоров. 93

9.3.3  Тупики и зависания. 94

9.4  Классические проблемы синхронизации. 94

9.4.1  Проблема ограниченного буфера. 94

9.4.2  Проблема читателей и писателей. 95

9.4.3  Задача об обедающих философах. 96

9.5  Двоичные семафоры.. 98

9.6  Сигналы.. 98

Контрольные вопросы.. 99

10 ТУПИКОВЫЕ СИТУАЦИИ.. 100

10.1 Необходимые условия возникновения тупиков. 100

10.2 Граф выделения и закрепления ресурсов. 100

10.3 Методы решения проблемы тупиков. 103

10.3.1 Предотвращение тупиков. 103

10.3.2 Обход тупиков. 105

10.3.3 Простейший алгоритм обхода тупика. 106

10.3.4 Алгоритм банкира. 107

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

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

Контрольные вопросы.. 111

11 УПРАВЛЕНИЕ ПАМЯТЬЮ.... 112

11.1 Функции операционной системы по управлению памятью.. 112

11.2 Типы адресов. 113

11.3 Физическое и логическое адресное пространство. 113

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

11.5 Динамическая загрузка. 116

11.6 Динамическое связывание. 116

11.7 Перекрытие программ в памяти. 117

11.8 Свопинг. 118

11.9 Смежное размещение процессов. 120

11.9.1 Простое непрерывное распределение. 120

11.9.2 Распределение с несколькими непрерывными разделами. 121

11.10  Фрагментация. 122

11.11  Страничная организация памяти. 123

11.12  Сегментная организация памяти. 125

11.13  Сегментация в сочетании со страничной памятью.. 127

Контрольные вопросы.. 128

12 УПРАВЛЕНИЕ ВИРТУАЛЬНОЙ ПАМЯТЬЮ.... 129

12.1 Подкачка страниц. 129

12.2 Алгоритмы вытеснения страниц. 130

12.2.1 Случайный выбор (Random). 130

12.2.2 «Первым пришел ¾ первым ушел» (FIFO). 130

12.2.3 Вытеснение по давности использования (LRU). 131

12.2.4 Вытеснение редко используемых страниц (LFU). 131

12.2.5 Оптимальный алгоритм (OPT). 132

12.3 Аномалии в алгоритмах страничной реализации. 132

12.3.1 «Толкотня» в памяти. 132

12.3.2 Аномалия Биледи. 133

12.4 Эффективность и применимость виртуальной памяти. 134

Контрольные вопросы.. 134

13 ИНТЕРФЕЙС ФАЙЛОВОЙ СИСТЕМЫ... 135

13.1 Понятие файла. Атрибуты файла и операции с файлами. 135

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

13.3 Типы файлов. 137

13.4 Структура файлов. 138

13.5 Методы доступа. 139

13.5.1 Последовательный метод доступа. 139

13.5.2 Прямой метод доступа. 140

13.5.3 Другие методы доступа. 141

13.6 Каталоги. 141

13.7 Логическая структура каталога. 142

13.7.1 Одноуровневая структура каталога. 143

13.7.2 Двухуровневая структура каталога. 143

13.7.3 Древовидная структура каталога. 144

13.7.4 Организация каталога в виде графа без циклов. 146

13.7.5 Организация каталога в виде произвольного (простого) графа. 148

13.8 Проблемы защиты файлов. 149

13.8.1 Типы доступа. 150

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

13.8.3 Другие подходы к защите. 151

Контрольные вопросы.. 152

14 Некоторые аспекты Реализации файловой системы 153

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

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

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

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

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

14.2.4 Индексные узлы.. 157

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

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

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

14.3.3 Размер блока. 159

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

Контрольные вопросы.. 161

Литература.. 162

 

ВВЕДЕНИЕ

Учебная дисциплина «Операционные системы» принадлежит к циклу подготовки бакалавров по направлению «Прикладная математика».

Данная дисциплина «Операционные системы» ориентирована на изучение концептуального базиса и методов управления ресурсами компьютера. Целью курса является изучение основных методов, которые используются при управлении ресурсами в разных операционных системах.  Изучаются варианты реализации многозадачной и многопоточной обработки, организация виртуальной памяти, средства синхронизации, средства файловой системы, логическая и физическая реализация файловых систем и систем управления вводом-выводом.

Знание основ организации операционных систем и принципов их функционирования позволяет использовать компьютеры более эффективно. Глубокое изучение операционных систем позволяет применить эти знания, прежде всего, при создании программного обеспечения.

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