 |
Нити с переменными приоритетами
|
|
|
|
Изначально процессу присваивается базовый приоритет.
Базовый приоритет процесса может меняться ОС, следовательно, могут измениться базовые приоритеты составляющих его нитей.
Нить получает значение приоритета из диапазона базового приоритета.
Приоритет нити может отклоняться от своего базового приоритета, и это может быть не связано с изменением базового приоритета процесса (см. диапазон значений динамического приоритета нитей).
• Поддерживается группа очередей (для нитей с переменными приоритетами) – по одной для каждого приоритета. Система просматривает очереди, начиная с самой приоритетной.
• На выполнение выбирается нить с наивысшим приоритетом. Ей выделяется квант времени. Если во время выполнения в очереди появляется нить с более высоким приоритетом, то текущая нить вытесняется. Вытесненная нить становится в очередь готовых впереди тех, что имеют тот же приоритет.
• Если нить исчерпала квант – ее приоритет понижается на единицу и она перемещается в соответствующую очередь
• Повышается значение приоритета – при выходе из состояния ожидания окончания ввода-вывода
Планирование свопинга в ОС Unix
При принятии нового процесса на обработку необходимо освободить ресурсы. Какой - то процесс скидывается в область своппинга.
Область свопинга - специально выделенное системой пространство внешней памяти
P_TIME – счетчик, находящийся в контексте процесса. Суммирует время нахождения процесса в состоянии мультипрограммной обработки или в области свопинга. При переходе из одного состояния в другое счетчик обнуляется. Для загрузки процесса в память из области свопинга выбирается процесс с максимальным значением P_TIME. Если для загрузки этого процесса нет свободного пространства оперативной памяти, то система ищет среди процессов в оперативной памяти процесс, ожидающий ввода/вывода (сравнительно медленных операций, процессы у которых приоритет выше значения P_ZERO) и имеющий максимальное значение P_TIME (т.е. тот, который находился в оперативной памяти дольше всех). Если такого процесса нет, то выбирается просто процесс с максимальным значением P_TIME.
|
|
|
Лекция 12. Управление оперативной памятью
Основные задачи:
1.Контроль состояния каждой единицы памяти (система должна отслеживать, какая единица свободна/распределена, обеспечение аппаратурой компьютера и ОС - таблицы).
2.Стратегия распределения памяти (выбор правил, по которым принимаются решения, кому, когда и сколько памяти должно быть выделено).
3.Выделение памяти (принятие решения: выбор конкретной области, которая должна быть выделена).
4.Стратегия освобождения памяти (процесс освобождает, ОС “забирает” окончательно или временно. Здесь же выбор стратегии).
Рассмотрим стратегии управления по следующему плану
1.Основные концепции.
2.Необходимые аппаратные средства.
3.Основные алгоритмы.
4.Достоинства, недостатки.
1.Одиночное непрерывное распределение.
Необходимые аппаратные средства:
•Регистр границ + режим ОС / режим пользователя.
•Если ЦП в режиме пользователя попытается обратиться в область ОС, то возникает прерывание.
Алгоритмы: очевидны.
Достоинства: простота.
Недостатки:
1.Часть памяти не используется.
2.Процессом/заданием память занимается все время выполнения.
3.Ограничение на размеры задания.
2.Распределение разделами.
Необходимые аппаратные средства:
1.Два регистра границ.
Недостатки:
а. перегрузка регистра границ при каждой смене контекста;
|
|
|
б. сложности при использовании каналов/процессоров ввода/вывода.
2.Ключи защиты (PSW).
Алгоритмы: Модель статического определения разделов
А. Сортировка входной очереди процессов по отдельным очередям к разделам. Процесс размещается в разделе минимального размера, достаточного для размещения данного процесса. В случае отсутствия процессов в каких-то под очередях – неэффективность использования памяти.
Алгоритмы: Модель статического определения разделов
Б. Одна входная очередь процессов.
1. Освобождение раздела, поиск (в начале очереди) первого процесса, который может разместиться в разделе. Проблема: большие разделы маленькие процессы.
2. Освобождение раздела, поиск процесса максимального размера, не превосходящего размер раздела.
Проблема: дискриминация “маленьких” процессов.
- Оптимизация варианта 2. Каждый процесс имеет счетчик дискриминации. Если значение счетчика процесса ³ K, то обход его в очереди невозможен.
Достоинства:
1.Простое средство организации мультипрограммирования.
2.Простые средства аппаратной поддержки.
3.Простые алгоритмы.
Недостатки:
1.Фрагментация.
2.Ограничение размерами физической памяти.
3.Весь процесс размещается в памяти – возможно неэффективное использование.
3.Распределение перемещаемыми разделами.
Необходимые аппаратные средства:
1.Регистры границ + регистр базы
2.Ключи + регистр базы
Алгоритмы: Аналогично предыдущему
Достоинства:
1.Ликвидация фрагментации
Недостатки:
1.Ограничение размером физической памяти
2.Затраты на перекомпоновку
4.Страничное распределение.
Основные концепции:
Таблица страниц – отображение номеров виртуальных страниц на номера физических.
Проблемы:
1. Размер таблицы страниц (количество 4кб страниц при 32-х разрядной адресации – 1000000. Любой процесс имеет собственную таблицу страниц).
2. Скорость отображения.
Необходимые аппаратные средства:
1.Полностью аппаратная таблица страниц (стоимость, полная перегрузка при смене контекстов, скорость преобразования).
2.Регистр начала таблицы страниц в памяти (простота, управление смены контекстов, медленное преобразование).
|
|
|
3.Гибридные решения.
Алгоритмы и организация данных:
Размеры таблицы страниц – иерархическая организация таблицы страниц.
Модельная структура записи таблицы страниц
α – присутствие/отсутствие
β – защита (чтение, чтение/запись, выполнение)
γ – изменения
δ – обращение (чтение, запись, выполнение)
ε – блокировка кэширование
TBL (Translation Lookaside Buffer) – буфер быстрого преобразования адресов.
Суть: для разрешения коммуникаций, связанных со скоростью и т.д. необходимо гибридное решение. Имеется аппаратный буфер (т.н. буфер ассоциативной памяти) относительно небольшого размера, кот используется в качестве КЭШа таблицы страниц. Структура этого буфера:
N виртуальных страниц
N соответствующих физических страниц
Если попадаем – автоматическая замена поля физической страницы виртуальной, иначе – прерывание, по которому управление передается ОС и она уже сама обновляется.
Проблема: стратегии по преобразованию строчки в TLB => организация алгоритмов выбора.
Другая проблема – объем таблицы страниц.
Иерархия организации таблицы страниц.
1) Многоуровневая:
индексация по внешней таблице страниц
смещение по этой странице
2) 
hash-таблицы, которые
•Обычно используются для адресации
•Используется больше 32 разрядов.
3)
3) инвертированные таблицы страниц
Проблема – поиск по таблице
Использование хэширования
Замещение страниц
Проблема загрузки «новой» страницы в память. Необходимо выбрать страницу для удаления из памяти (с учетом ее модификации и пр.)
Существуют разные алгоритмы:
-
Алгоритм NRU
(Not Recently Used – не использовавшийся в последнее время), который использует биты статуса страницы в записях таблицы страниц
1.При запуске процесса M и R для всех страниц процесса обнуляются
2.По таймеру происходит обнуление всех битов R
3.При возникновении страничного прерывания ОС делит все страниц на классы:
•Класс 0:
•Класс 1:
•Класс 2:
•Класс 3:
4.Случайная выборка страницы для удаления в непустом классе с минимальным номером
|
|
|
Стратегия: лучше выгрузить измененную страницу, к которой не было обращений как минимум в течение 1 «тика» таймера, чем часто используемую страницу
- Алгоритм FIFO
«Первым прибыл – первым удален» - простейший вариант FIFO. (проблемы «справедливости»)
Модификация алгоритма (алгоритм вторая попытка):
1.Выбирается самая «старая страница». Если R=0, то она заменяется
2.Если R=1, то R – обнуляется, обновляется время загрузки страницы в память (т.е. переносится в конец очереди). На п.1
- Алгоритм «Часы»
1.Если R=0, то выгрузка страницы и стрелка на позицию вправо.
2.Если R=1, то R-обнуляется, стрелка на позицию вправо и на П.1.
-
Алгоритм LRU
(Least Recently Used – «менее недавно» - наиболее давно используемая страница)
5. Алгоритм NFU
(Not Frequently Used – редко использовавшаяся страница )
Программная модификация LRU.
Для каждой физической страницы i – программный счетчик Counti
0. Изначально Counti– обнуляется для всех i.
1.По таймеру Counti = Counti + Ri
Выбор страницы с минимальным значением {Counti}
Недостаток – «помнит» всю активность по использованию страниц
6. Модификация NFU
– алгоритм старения
Модификация:
1.Значение счетчика сдвигается на 1 разряд вправо.
2.Значение R добавляется в крайний левый разряд счетчика.
4. Сегментная организация памяти.
Основные концепции:
•Виртуальное адресное пространство представляется в виде совокупности сегментов
•Каждый сегмент имеет свою виртуальную адресацию (от 0 до N-1)
•Виртуальный адрес: <номер_сегмента, смещение>
Необходимые аппаратные средства:
5. Сегментно-страничная организация памяти.
Необходимые аппаратные средства:
Упрощенная модель Intel.
Необходимые аппаратные средства:
Достоинства\недостатки как у страничной, + достоинства сегментной и сегментно-страничной.
Оглавление.
Лекция 1. Операционные системы. 2
Экскурс в историю. 3
Основы архитектуры вычислительных систем. 5
Лекция 2. Системы программирования. 10
Основы компьютерной архитектуры. 14
Центральный процессор 17
Лекция 3.Внешние запоминающие устройства. 22
Аппаратная поддержка ОС и систем программирования. 26
Регистровые окна 28
Виртуальная память 30
Лекция 4.Операционная система. Общие характеристики и свойства. 32
Структура ОС. 34
Процессы в ОС UNIX. 38
Лекция 5. Взаимодействие процессов: синхронизация, тупики 44
Средства синхронизации 46
Классические задачи синхронизации процессов 48
Лекция 6.Основы взаимодействия сети. 53
Многомашинные и многопроцессорные ассоциации. 54
|
|
|
Компьютерные сети 57
Лекция 7. Файловые системы 62
Лекция 8. ОС UNIX. Файловая система. 71
Управление внешними устройствами. 77
Лекция 9. Программное управление внешними устройствами 79
OC Unix: Работа с внешними устройствами 84
Лекция 10. Система межпроцессного взаимодействия IPC 88
Лекция 11. Планирование 104
Алгоритмы, основанные на приоритетах 106
Планирование в ОС UNIX 109
Планирование в Windows NT. 110
Планирование свопинга в ОС Unix 111
Лекция 12. Управление оперативной памятью 112
|
|
|
