Часть I. Общие сведения 5

Глава 1. Введение 5

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

1.1.1 Структура вычислительной системы 5

1.1.2 Что такое ОС 6

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

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

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

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

1.4.2  Слоеные системы (Layered systems) 15

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

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

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

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

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

Глава 2. Процессы 20

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

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

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

2.3.1. Набор операций 23

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

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

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

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

Глава 3. Планирование процессов 29

3.1. Уровни планирования 29

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

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

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

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

3.5.1. First-Come, First-Served (FCFS) 33

3.5.2. Round Robin (RR) 34

3.5.3. Shortest-Job-First (SJF) 35

3.5.4. Гарантированное планирование 37

3.5.5. Приоритетное планирование 38

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

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

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

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

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

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

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

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

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

4.3.3.1 Буферизация 46

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

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

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

4.4. Потоки исполнения 49

Глава 5. Алгоритмы синхронизации 54

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

5.2. Критическая секция 56

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

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

5.3.2. Запрет прерываний 60

5.3.3. Переменная-замок 60

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

5.3.5. Флаги готовности 61

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

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

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

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

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

Глава 6. Механизмы синхронизации 66

6.1. Семафоры 66

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

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

6.2. Мониторы 68

6.3. Сообщения 70

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

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

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

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

Глава 7. Тупики 74

7.1  Введение 74

7.2 Концепция ресурса 75

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

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

7.5  Алгоритм страуса 76

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

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

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

7.7.2        Восстановление через откат назад 79

7.7.3  Восстановление через ликвидацию одного из процессов 79

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

7.8.1 Алгоритм банкира. 80

7.8.2  Недостатки алгоритма банкира 81

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

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

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

7.9.3 Нарушение принципа неперераспределяемости. 82

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

7.10  Родственные проблемы 83

7.10.1 Двухфазная локализация 83

7.10.2 Тупики не ресурсного типа 83

7.10.3 Голод (starvation) 83

7.11 Заключение. 83