№12 Обход тупиков. Алгоритм банкира.
Алгоритм банкира – ресурсы процессу можно выдавать только в том случае, если состояние системы останется надежным.
Надежное состояние – ОС гарантирует всем процессам завершение в конечное время. Введем следующие обозначения:
M(i) – максимальная потребность i-го процесса в ресурсе; L(i) – текущая величина ресурса, выделенного i-му процессу; С(i) – текущая потребность в ресурсе, C(i)=M(i)-L(i);
Т – суммарный ресурс, имеющийся в системе; а – остаточный ресурс, а=Т- L(i);
Пусть в некоторый момент времени в системе существуют три процесса.
T=12
|
L(i) |
M(i) |
C(i) |
Решение примера |
|
|
|||
|
|
|
|
|
Process |
1 |
4 |
3 |
|
|
||||
1 |
|
|||
|
|
|
|
|
|
|
|
|
|
Process |
4 |
6 |
2 |
|
2 |
|
|||
|
|
|
|
|
|
|
|
|
|
Process |
5 |
8 |
3 |
|
3 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
a |
|
2 |
|
|
|
|
|
|
№13 Прерывания ОС и BIOS. Обработка прерываний.
Прерывание - это событие, при котором меняется последовательность команд, выполняемых процессором.
Что происходит после прерывания?
Управление передается ОС
ОС запоминает состояние прерванного процесса (например в PCB)
Передача управления соответствующей программе обработчику прерывания
Типы прерываний.
SVC прерывание (super visor call instruction) - программа вызывает супервизор – ОС, то есть требует системную услугу.
то есть SVC – механизм не позволяет получать программе пользователя системные ресурсы без контроля со стороны ОС (механизм доступа, паролей и так далее)
I/O прерывание: инициатор – устройство ввода-вывода (изменение его состояния)
Внешнее прерывание (оператор, другой процессор)
Прерывание по рестарту (при сигнале рестарт процессору)
Прерывание по ошибке программы Прерывание по ошибке ЭВМ
Обработчики прерываний.
Для каждого типа прерывания существует свой IH (interrupt handler) = обработчик прерываний. Система передает управление IH способом
PSW (program status word) - слово состояния программы – управляет порядком выполнения команд и содержит информацию о процессе.
PWS бывает: текущее(current), новое(new), старое(old).
Новое PSW = содержит адрес по которому резидентно размещается IH. При прерывании текущее PSW становится старым, а новое PWS становится текущим. После
выполнения IH управление будет передано либо прерванному процессу (OLD PSW), либо более приоритетному из очереди (перехват ЦП).
№14. Организация оперативной памяти. Однопрограммные системы. Оверлеи.
Организация памяти это способ представления и использования основной памяти Способы организации основной памяти (DRAM)
•Однопрограммные системы
•Мультипрограммные системы с фиксированными разделами с трансляцией и загрузкой в абсолютных адресах
•Мультипрограммные системы с фиксированными разделами с трансляцией и загрузкой перемещаемых модулей
•Мультипрограммные системы с переменными разделами
•Системы со свопингом (SWAP)
Однопрограммные системы |
|
Free |
|
Rg (bottom) |
|
User task |
User task |
Rg (top) |
|
ОС |
|
Защита области памяти процесса
Free |
User |
(overlay) |
User |
(resident) |
ОС |
User (ovl 1) |
User (ovl 2) |
User (ovl N) |
User |
|
|
(resident) |
|
|
Однозадачные OS могут работать только с одной (в данный момент времени) программой, т.е. выполняют функцию предоставления пользователю виртуальной машины. Пример - MS-DOS.
Оверлеи представляют собой части программы, которые совместно используют общую область памяти. В один и тот же момент времени резидентно размещаться в памяти может та или иная часть программы, необходимая для выполнения заданной функции. В процессе выполнения эти части программы могут замещать друг друга.
Оверлеи полезны только в программах DOS реального режима. Поскольку для программ Windows памятью управляет сама Windows, а для программ защищенного режима - администратор этапа выполнения (RTM.EXE), эти средства включают в себя полный механизм обслуживания оверлеев, и в программах Windows и программах защищенного режима необходимость использования оверлеев отпадает.
Оверлеи могут значительно сократить объем памяти, необходимый для выполнения программы. Фактически, так как в любой момент времени в памяти резидентно размещаются только части программы, с помощью оверлеев вы можете выполнять программы, значительно превосходящие по объему доступную память.
№15. Организация оперативной памяти. Мультипрограммные системы.
Организация памяти это способ представления и использования основной памяти Способы организации основной памяти (DRAM)
•Однопрограммные системы
•Мультипрограммные системы с фиксированными разделами с трансляцией и загрузкой в абсолютных адресах
•Мультипрограммные системы с фиксированными разделами с трансляцией и загрузкой перемещаемых модулей
•Мультипрограммные системы с переменными разделами
•Системы со свопингом (SWAP)
Мультипрограммные системы.
Многозада́чность (англ. multitasking) — свойство операционной системы или среды программирования обеспечивать возможность параллельной (или псевдопараллельной) обработки нескольких процессов. Истинная многозадачность операционной системы возможна только в распределенных вычислительных системах.
Схема с фиксированными разделами.
Трансляция и загрузка в абсолютных адресах (раздельные очереди процессов)
|
|
Раздел 3 |
|
|
|
1 |
|
|
|
Раздел 2 |
|
3 |
2 |
1 |
|
|
|
Раздел 1 |
|
|
2 |
1 |
|
|
|
ОС |
ОС |
Плюсы: простота организации работы, высокая скорость загрузки Минусы: число одновременно загруженных процессов ограничено и не зависит от занимаемой ими памяти; переход в свободный раздел невозможен.
Трансляция и загрузка перемещаемых модулей (общая очередь процессов)
Раздел 3
Раздел 2
Раздел 1
ОС
Плюс: простое управление очередью. |
Процесс 1 |
|
|
|
|
Минус: сложный загрузчик. |
|
|
Схема с переменными разделами
Стратегии выбора разделов:
ОС
•first fit - первый подходящий по размеру
•best fit - наиболее подходящий по размеру
•worst fit - наименее подходящий по размеру Плюс: эффективное использование памяти
Минус: необходимость периодической дефрагментации.
Процесс 1 |
|
Процесс 1 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
Процесс 2
Процесс 3
|
|
|
|
|
ОС |
|
ОС |
|
ОС |
|
|
|
|
|
№16 Основные функции системы управления памятью.
Основные функции системы управления памятью (Memory Manager)
•отображение адресного пространства процесса на конкретные области физической памяти (размещение);
•распределение памяти между конкурирующими процессами (выборка);
•контроль доступа к адресным пространствам процессов;
•выгрузка процессов (целиком или частично) во внешнюю память, когда в оперативной памяти недостаточно места (замещение);
•учет свободной и занятой памяти.
№17 Организация оперативной памяти. Основные способы.
Организация памяти это способ представления и использования основной памяти Способы организации основной памяти (DRAM)
•Однопрограммные системы
•Мультипрограммные системы с фиксированными разделами с трансляцией и загрузкой в абсолютных адресах
•Мультипрограммные системы с фиксированными разделами с трансляцией и загрузкой перемещаемых модулей
•Мультипрограммные системы с переменными разделами
•Системы со свопингом (SWAP)
№18 Организация оперативной памяти. Системы со свопингом.
Организация памяти это способ представления и использования основной памяти Способы организации основной памяти (DRAM)
Свопинг Один из механизмов реализации виртуальной памяти, при котором отдельные запущенные процессы
(обычно неактивные) перемещаются из ОЗУ на жёсткий диск, освобождая ОЗУ для загрузки других процессов. Основное отличие этого механизма от страничного заключается в том, что процессы перемещаются между ОЗУ и жестким диском целиком, поэтому иногда некоторые процессы могут полностью отсутствовать в ОЗУ. При наступлении условий активизации процесса он возвращается диспетчером памяти в ОЗУ. Существуют различные алгоритмы выбора процессов на загрузку и выгрузку, а также различные способы выделения оперативной и дисковой памяти загружаемому процессу.
Мультипрограммные системы с фиксированными разделами и переменными разделами требуют, чтобы задание оставалось в памяти до момента завершения. При свопинге задание можно «вталкивать» до завершения во внешнюю память.
Основная идея – держать в памяти только те инструкции программы, которые нужны в данный момент.
№19. Виды памяти вычислительных систем.
|
|
Registers |
|
L1 |
|
Instruction |
|
|
CPU |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Cash |
|
L2 |
|
Data |
|
Store |
|
|
|
|
|
|
|
|
buffer |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
DRAM
On other |
UMA |
Memory
nodes
NUMA
Flash
|
|
Flash |
|
Flash |
Disk |
|
HDD |
|
ZIP |
|
|
Network |
|
….. |
|
|
|
Различают два основных вида памяти — внутреннюю и внешнюю.
В состав внутренней памяти входят оперативная память, кэш-память и специальная память.
Внешняя память (ВЗУ) предназначена для длительного хранения программ и данных, и целостность её содержимого не зависит от того, включен или выключен компьютер. В отличие от оперативной памяти, внешняя память не имеет прямой связи с процессором.
В состав внешней памяти компьютера входят: накопители на жёстких магнитных дисках; накопители на гибких магнитных дисках; накопители на компакт-дисках; накопители на магнитной ленте (стримеры);
накопители на магнитно-оптических дисках;
№20 Виртуальная память, назначение, основные проблемы. Методы организации.
Виртуальная память – организация памяти, которая позволяет процессу адресовать пространство памяти намного большее, чем имеется в системе.
Основная проблема
Процесс работает с виртуальными адресами V, а процессор с реальными R. Необходимо уметь быстро преобразовывать V в R.
1.Преобразование каждого адреса V в реальный R. Совершенно нереальный механизм. Таблица преобразований займет всю память и вытеснит процесс. Если ее попытаться хранить во внешней памяти, то скорость работы процесса очень существенно снизится.
2.Преобразование блока виртуальных адресов V в блок реальных адресов R.
Реальный механизм. Таблица преобразований компактна и может храниться в КЭШ. Требует двухкомпонентного адреса
V(S,d)
Где S – номер блока, а d смещение от начала блока
Методы организации виртуальной памяти:
1)СТРАНИЧНАЯ – все блоки одинаковые по размеру
2)СЕГМЕНТНАЯ – все блоки разные по размеру
3)СЕГМЕНТНО-СТРАНИЧНАЯ – все сегменты разные по размеру, но состоят из целого числа одинаковых блоков
№21 Задачи менеджера виртуальной памяти.
Менеджер виртуальной памяти (далее просто «менеджер памяти») — часть операционной системы, благодаря которой можно адресовать память большую, чем объем физической памяти (ОЗУ).
Основные задачи:
1)Подкачка – когда и какую страницу из ВМ перевести в ОЗУ По запросу Достоинства:
-самый дешевый вариант (низкие накладные расходы)
-исключает ненужные подкачки
Недостатки:
- простой процесса в ожидании нужного набора страниц
С упреждением Достоинства:
-при правильном предсказании увеличение производительности
-при «большом» ОЗУ снижается урон от промаха
Недостатки:
-любит ОЗУ
-некоторое увеличение накладных расходов
2)Выталкивание - какую страницу можно «убрать» из ОЗУ 1. Принцип оптимальности.
Надо выталкивать ту страницу, к которой дольше всего не будет обращений. Как это можно определить? Никак!
Стратегия не реализуется.
2. Выталкивание случайной страницы.
Достоинство: быстрое решение с маленькими накладными расходами. Недостатки: может возрасти частота прерываний (выталкиваем нужную страницу). Используется крайне редко.
3)Размещение – куда поместить загружаемую в ОЗУ страницу Куда разместить страницу?
Если есть свободное место в ОЗУ, то используем его.
Если все занято, то решаем задачу замещения или выталкивания.
№22 Страничная организация виртуальной памяти.
Вбольшинстве современных операционных систем виртуальная память организуется с помощью страничной адресации. Оперативная память делится на страницы: области памяти фиксированной длины (например, 4096 байт), которые являются минимальной единицей выделяемой памяти (то есть даже запрос на 1 байт от приложения приведёт к выделению ему страницы памяти). Процесс обращается к памяти с помощью адреса виртуальной памяти, который содержит в себе номер страницы и смещение внутри страницы. Операционная система преобразует виртуальный адрес в физический, при необходимости подгружая страницу с жёсткого диска в оперативную память. При запросе на выделение памяти операционная система может «сбросить» на жёсткий диск страницы, к которым давно не было обращений. Критические данные (например, код запущенных и работающих программ, код и память ядра системы) обычно находятся в оперативной памяти (исключения существуют, однако они не касаются той части, которая отвечает за использование файла подкачки).
Всемействе операционных систем Microsoft Windows место для хранения страниц на жёстких дисках должно быть выделено заранее. Пользователь может положиться на автоматический механизм или самостоятельно указать размер области виртуальной памяти на каждом из разделов диска. На указанных разделах операционной системой создаётся файл pagefile.sys требуемого размера, который и хранит «сброшенные» из оперативной памяти страницы.
№23 Сегментная организация виртуальной памяти.
Механизм организации виртуальной памяти, при котором виртуальное пространство делится на части произвольного размера — сегменты. Этот механизм позволяет, к примеру, разбить данные процесса на логические блоки.[1] Для каждого сегмента, как и для страницы, могут быть назначены права доступа к нему пользователя и его процессов. При загрузке процесса часть сегментов помещается в оперативную память (при этом для каждого из этих сегментов операционная система подыскивает подходящий участок свободной памяти), а часть сегментов размещается в дисковой памяти. Сегменты одной программы могут занимать в оперативной памяти несмежные участки. Во время загрузки система создает таблицу сегментов процесса (аналогичную таблице страниц), в которой для каждого сегмента указывается начальный физический адрес сегмента в оперативной памяти, размер сегмента, правила доступа, признак модификации, признак обращения к данному сегменту за последний интервал времени и некоторая другая информация. Если виртуальные адресные пространства нескольких процессов включают один и тот же сегмент, то в таблицах сегментов этих процессов делаются ссылки на один и тот же участок оперативной памяти, в который данный сегмент загружается в единственном экземпляре. Система с сегментной организацией функционирует аналогично системе со страничной организацией: время от времени происходят прерывания, связанные с отсутствием нужных сегментов в памяти, при необходимости освобождения памяти некоторые сегменты выгружаются, при каждом обращении к оперативной памяти выполняется преобразование виртуального адреса в физический. Кроме того, при обращении к памяти проверяется, разрешен ли доступ требуемого типа к данному сегменту.
Виртуальный адрес при сегментной организации памяти может быть представлен парой (g, s), где g — номер сегмента, а s — смещение в сегменте. Физический адрес получается путем сложения начального физического адреса сегмента, найденного в таблице сегментов по номеру g, и смещения s. Недостатком данного метода распределения памяти является фрагментация на уровне сегментов и более медленное по сравнению со страничной организацией преобразование адреса.