ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.01.2025
Просмотров: 7042
Скачиваний: 3
СОДЕРЖАНИЕ
1.2.1 Ос как виртуальная машина
1.2.2 Ос как система управления ресурсами
1.3 Интерфейс прикладного программирования
1.4 Структура операционных систем
1.4.2 Многоуровневая структура ос
1.4.4 Микроядерная архитектура (модель клиент-сервер)
1.4.5 Обобщение сравнения моделей
2.2.3 Преимущества использования потоков
2.2.4 Реализация потоков в пространстве пользователя, ядра и смешанное
2.2.5 Особенности реализации Windows
3.1 Взаимодействие между процессами
3.1.1 Передача информации от одного процесса другому
3.1.4 Взаимное исключение с активным ожиданием
3.1.5 Примитивы взаимодействия процессов
4.1 Основные понятия планирования процессов
4.2 Планирование в системах пакетной обработки
4.3.2 Приоритетное планирование
4.3.3 Методы разделения процессов на группы
4.4 Планирование в системах реального времени
4.4.1 Планирование однородных процессов
4.4.2 Общее планирование реального времени
5.1 Взаимоблокировка процессов
5.2 Моделирование взаимоблокировок
5.3 Методы борьбы с взаимоблокировками
5.3.1 Пренебрежением проблемой в целом (страусовый алгоритм)
5.3.2 Обнаружение и устранение взаимоблокировок
5.3.3 Динамическое избежание взаимоблокировок
5.3.4 Предотвращение четырех условий, необходимых для взаимоблокировок
6.2 Методы без использования внешней памяти
6.2.1 Однозадачная система без подкачки на диск
6.2.2 Распределение памяти с фиксированными разделами.
6.2.3 Распределение памяти динамическими разделами
6.3 Методы с использованием внешней памяти (свопинг и виртуальная память)
7.1 Алгоритмы замещения страниц
7.2.1 Политика распределения памяти
7.2.3 Совместно используемые страницы
7.2.4 Политика очистки страниц
7.3 Особенности реализации в unix
7.4 Особенности реализации в Windows
8.1 Основные понятия сегментации
8.2.1 Сегментация с использованием страниц: multics
8.2.2 Сегментация с использованием страниц: Intel Pentium
8.3 Особенности реализации в unix
9.1 Принципы аппаратуры ввода-вывода
9.1.3 Отображаемый на адресное пространство памяти ввод-вывод
9.1.4 Прямой доступ к памяти (dma - Direct Memory Access)
9.2 Принципы программного обеспечения ввода-вывода
9.2.1 Задачи программного обеспечения ввода-вывода
9.2.3 Управляемый прерываниями ввод-вывод
9.2.4 Ввод-вывод с использованием dma
9.3 Программные уровни и функции ввода-вывода
9.3.3 Независимое от устройств программное обеспечение ввода-вывода
9.3.4 Программное обеспечение ввода-вывода пространства пользователя
9.3.5 Обобщение уровней и функций ввода-вывода
10.1.2 Raid (Redundant Array of Independent Disk - массив независимых дисков с избыточностью)
10.1.3.1 Компакт-диски с возможностью записи cd-r
10.1.3.2 Многократно перезаписываемые компакт-диски cd-rw
10.1.3.3 Универсальный цифровой диск dvd (Digital Versatile Disk)
10.2 Форматирование дисков (программная часть)
10.2.1 Низкоуровневое форматирование
10.2.3 Высокоуровневое форматирование
10.3 Алгоритмы планирования перемещения головок
10.3.1 Алгоритм "первый пришел - первым обслужен" fcfs (First Come, First Served)
10.3.3 Алгоритмы сканирования (scan, c-scan, look, c-look)
10.5 Стабильное запоминающее устройство
10.6.1 Аппаратная часть таймеров
10.6.2 Программное обеспечение таймеров
11.1.7 Файлы, отображаемые на адресное пространство памяти
12.2.3 Связные списки при помощи таблиц в памяти
12.3.1 Реализация длинных имен файлов
12.3.2 Ускорение поиска файлов
12.3.2.1 Использование хэш-таблицы для ускорения поиска файла.
12.3.2.2 Использование кэширования результатов поиска файлов для ускорения поиска файла.
12.4 Совместно используемые файлы
12.5 Организация дискового пространства
12.6 Надежность файловой системы
12.6.2 Непротиворечивость файловой системы
12.7 Производительность файловой системы
13.1.2 Рок-ридж расширения для unix
13.1.3 Joliet расширения для Windows
13.2 Файловая система ms-dos (fat-12,16,32)
13.2.4 Расширение Windows 98 для fat-32
14.1.2 Блокировка данных файла
14.1.3 Создание и работа с файлом
14.4 Сравнительная таблица некоторых современных файловых систем
14.4.1 Архитектура файловой системы nfs
4.4 Планирование в системах реального времени
Системы реального времени делятся на:
жесткие (жесткие сроки для каждой задачи) - управление движением
гибкие (нарушение временного графика не желательны, но допустимы) - управление видео и аудио
Внешние события, на которые система должна реагировать, делятся:
периодические - потоковое видео и аудио
непериодические (непредсказуемые) - сигнал о пожаре
Что бы систему реального времени можно было планировать, нужно чтобы выполнялось условие:
m - число периодических событий
i - номер события
P(i) - период поступления события
T(i) - время, которое уходит на обработку события
Т.е. перегруженная система реального времени является не планируемой.
4.4.1 Планирование однородных процессов
В качестве однородных процессов можно рассмотреть видео сервер с несколькими видео потоками (несколько пользователей смотрят фильм).
Т.к. все процессы важны, можно использовать циклическое планирование.
Но так как количество пользователей и размеры кадров могут меняться, для реальных систем он не подходит.
4.4.2 Общее планирование реального времени
Используется модель, когда каждый процесс борется за процессор со своим заданием и графиком его выполнения.
Планировщик должен знать:
частоту, с которой должен работать каждый процесс
объем работ, который ему предстоит выполнить
ближайший срок выполнения очередной порции задания
Рассмотрим пример из трех процессов.
Процесс А запускается каждые 30мс, обработка кадра 10мс
Процесс В частота 25 кадров, т.е. каждые 40мс, обработка кадра 15мс
Процесс С частота 20 кадров, т.е. каждые 50мс, обработка кадра 5мс
Три периодических процесса
Проверяем, можно ли планировать эти процессы.
10/30+15/40+5/50=0.808<1
Условие выполняется, планировать можно.
Будем планировать эти процессы статическим (приоритет заранее назначается каждому процессу) и динамическим методами.
4.4.3 Статический алгоритм планирования RMS (Rate Monotonic Scheduling)
Процессы должны удовлетворять условиям:
Процесс должен быть завершен за время его периода
Один процесс не должен зависеть от другого
Каждому процессу требуется одинаковое процессорное время на каждом интервале
У непериодических процессов нет жестких сроков
Прерывание процесса происходит мгновенно
Приоритет в этом алгоритме пропорционален частоте.
Процессу А он равен 33 (частота кадров)
Процессу В он равен 25
Процессу С он равен 20
Процессы выполняются по приоритету.
Статический алгоритм планирования RMS (Rate Monotonic Scheduling)
4.4.4 Динамический алгоритм планирования EDF (Earliest Deadline First)
Наибольший приоритет выставляется процессу, у которого осталось наименьшее время выполнения.
При больших загрузках системы EDF имеет преимущества.
Рассмотрим пример, когда процессу А требуется для обработки кадра - 15мс.
Проверяем, можно ли планировать эти процессы.
15/30+15/40+5/50=0.975<1
Загрузка системы 97.5%
Динамический алгоритм планирования EDF (Earliest Deadline First)
Алгоритм планирования RMS терпит неудачу.
Лекция 5
Взаимоблокировка процессов.
5.1 Взаимоблокировка процессов
Взаимоблокировка процессов может происходить, когда несколько процессов борются за один ресурс.
Ресурсы бывают выгружаемые и невыгружаемые, аппаратные и программные.
Выгружаемый ресурс - этот ресурс безболезненно можно забрать у процесса (например: память).
Невыгружаемый ресурс - этот ресурс нельзя забрать у процесса без потери данных (например: принтер).
Проблема взаимоблокировок процессов возникает при борьбе за невыгружаемый ресурсы.
Условия необходимые для взаимоблокировки:
Условие взаимного исключения - в какой-то момент времени, ресурс занят только одним процессом или свободен.
Условие удержания и ожидания - процесс, удерживающий ресурс может запрашивать новые ресурсы.
Условие отсутствия принудительной выгрузки ресурса.
Условие циклического ожидания - должна существовать круговая последовательность из процессов, каждый, из которого ждет доступа к ресурсу, удерживаемому следующим членом последовательности.
5.2 Моделирование взаимоблокировок
Моделирование тупиков с помощью графов.
Условные обозначения
На такой модели очень хорошо проверить возникает ли взаимоблокировка. Если есть цикл, значит, есть и взаимоблокировка.
Рассмотрим простой пример:
три процесса A, B, C
три ресурса R, S, T
Последовательное выполнение процессов, взаимоблокировка не возникает
Рассмотрим циклический алгоритм:
три процесса A, B, C
три ресурса R, S, T
Возникает взаимоблокировка
Рассмотрим тот же самый случай, но допустим, что система, зная о предстоящей взаимоблокировке, заблокирует процесс B.
Взаимоблокировка не возникает.
5.3 Методы борьбы с взаимоблокировками
Четыре стратегии избегания взаимоблокировок:
Пренебрежением проблемой в целом (вдруг пронесет).
Обнаружение и устранение (взаимоблокировка происходит, но оперативно ликвидируется).
Динамическое избежание тупиков.
Предотвращение четырех условий, необходимых для взаимоблокировок.
5.3.1 Пренебрежением проблемой в целом (страусовый алгоритм)
Если вероятность взаимоблокировки очень мала, то ею легче пренебречь, т.к. код исключения может очень усложнить ОС и привести к большим ошибкам. Также многие взаимоблокировки тяжело обнаружить.
Этот алгоритм используется как в UNIX, так и в Windows.
Поэтому (и не только) на серверах часто устанавливают автоматическую перезагрузку (раз в сутки, как правило ночью), если возникнет взаимоблокировка, то после перезагрузки ее не будет.
5.3.2 Обнаружение и устранение взаимоблокировок
Система не пытается предотвратить взаимоблокировку, а пытается обнаружить ее и устранить.
Обнаружение взаимоблокировки при наличии одного ресурса каждого типа
Под одним ресурсом каждого типа, подразумевается один принтер, один сканер и один плоттер и т.д.
Рассмотрим систему из 7-ми процессов и 6-ти ресурсов.
Обнаружение взаимоблокировки при наличии одного ресурса каждого типа
Визуально хорошо видна взаимоблокировка, но нам нужно чтобы ОС сама определяла взаимоблокировку.
Для этого нужен алгоритм.
Рассмотрим один из алгоритмов.
Для каждого узла N в графе выполняется пять шагов.
Задаются начальные условия: L-пустой список, все ребра не маркированы.
Текущий узел добавляем вконец списка L и проверяем количество появления узла в списке. Если он встречается два раза, значит цикл и взаимоблокировка.
Для заданного узла смотрим, выходит ли из него хотя бы одно немаркированное ребро. Если да, то переходим к шагу 4, если нет, то переходим к шагу 5.
Выбираем новое немаркированное исходящее ребро и маркируем его. И переходим по нему к новому узлу и возвращаемся к шагу 3.
Зашли в тупик. Удаляем последний узел из списка и возвращаемся к предыдущему узлу. Возвращаемся к шагу 3. Если это первоначальный узел, значит, циклов нет, и алгоритм завершается.
Алгоритм обнаружения взаимоблокировок
Для нашего случая тупик обнаруживается в списке L=[B,T,E,V,G,U,D,T]
Обнаружение взаимоблокировки при наличии нескольких ресурсов каждого типа
Рассмотрим систему.
m - число классов ресурсов (например: принтеры это один класс)
n - количество процессов
P(n) - процессы
E - вектор существующих ресурсов
E(i) - количество ресурсов класса i
A - вектор доступных (свободных) ресурсов
A(i) - количество доступных ресурсов класса i
С - матрица текущего распределения (какому процессу, какие ресурсы принадлежат)
R - матрица запросов (какой процесс, какой ресурс запросил)
C(ij) - количество экземпляров ресурса j, которое занимает процесс P(i).
R(ij) - количество экземпляров ресурса j, которое хочет получить процесс P(i).
Общее количество ресурсов равно сумме занятых и свободных ресурсов
Рассмотрим алгоритм поиска тупиков.
Алгоритм поиска тупиков при наличии нескольких ресурсов каждого типа
Если остаются не маркированные процессы, значит, есть тупик.
Рассмотрим работу алгоритма на реальном примере.
Используем алгоритм:
Третий процесс может получить желаемые ресурсы, т.к. R (2 1 0 0) = A (2 1 0 0)
Третий процесс освобождает ресурсы. Прибавляем их к A. А = (2 1 0 0) + (0 1 2 0) =(2 2 2 0). Маркируем процесс.
Может выполняться процесс 2. По окончании А=(4 2 2 1).
Теперь может работать первый процесс.
Тупиков не обнаружено.
Если рассмотреть пример, когда второму процессу требуются ресурсы (1 0 3 0), то два процесса окажутся в тупике.