Инвертированные. Альтернатива постоянно растущим уровням иерархии страничной адресации называется инвертированными таблицами страниц. В данной конструкции имеется одна запись для каждого страничного блока в реальной памяти, а не одна запись на каждую страницу в виртуальном адресном пространстве. Например, при использовании 64-разрядных виртуальных адресов, страниц размером 4 Кбайт и оперативной памяти размером 4 Гбайт инвертированные таблицы требовали только 1 048 576 записей. В каждой записи отслеживается, что именно находится в страничном блоке (процесс, виртуальная страница).

+: инвертированные таблицы страниц экономят значительное количество пространства, по крайней мере в том случае, когда виртуальное адресное пространство намного объемнее физической памяти.

-: преобразование виртуальных адресов в физические становится сложнее. Когда процесс n обращается к виртуальной странице p, аппаратура уже не может найти физическую страницу, используя p в качестве индекса внутри таблицы страниц. Вместо этого она должна провести поиск записи (n, p) по всей инвертированной таблице страниц. Поиск должен быть проведен при каждом обращении к памяти, а не только при ошибках отсутствия страницы.

Решение этой дилеммы состоит в использовании TLB. Если в этом буфере можно будет хранить информацию обо всех интенсивно используемых страницах, преобразование может происходить быстро. Но при отсутствии нужной записи в TLB программа должна просмотреть инвертированную таблицу страниц. Одним из приемлемых способов осуществления этого поиска является ведение хэш-таблицы, созданной на основе виртуальных адресов. Все находящиеся на данный момент в памяти виртуальные страницы, имеющие одинаковые хэш-значения, связываются в одну цепочку. Если у хэш-таблицы столько же строк, сколько физических страниц у машины, средняя цепочка будет длиной всего лишь в одну запись, позволяя существенно ускорить отображение. Как только будет найден номер страничного блока, в TLB будет введена новая пара значений (виртуального, физического).

8. Дайте определение процессу и опишите блок управления процессом.

Процесс — абстракция, описывающая выполняющуюся программу; просто экземпляр выполняемой программы, включая текущие значения счетчика команд, регистров и переменных. Концептуально у каждого процесса есть свой, виртуальный, центральный процессор. Процессы поддерживают возможность осуществления (псевдо) параллельных операций даже при наличии всего одного центрального процессора. Они превращают один центральный процессор в несколько виртуальных. Без абстракции процессов современные вычисления просто не могут существовать. При запуске системы запускается множество процессов. Для эффективного функционирования ПК необходим способ обеспечения параллельной работы и управления ею.

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

Для реализации модели процессов операционная система ведет таблицу (состоящую из массива структур), называемую таблицей процессов, в которой каждая запись соответствует какому-нибудь процессу. (Ряд авторов называют эти записи блоками управления процессом.) Эти записи содержат важную информацию о состоянии процесса, включая счетчик команд, указатель стека, распределение памяти, состояние открытых им файлов, его учетную и планировочную информацию и все остальное, касающееся процесса, что должно быть сохранено, когда процесс переключается из состояния выполнения в состояние готовности или блокировки, чтобы позже он мог возобновить выполнение, как будто никогда не останавливался.

Для того чтобы операционная система могла управлять процессами, на каждый процесс заводится специальная информационная структура, содержащая определенную важную информацию о процессе, и называемая дескриптором процесса (PCB). В общем случае дескриптор процесса содержит следующую информацию:

• идентификатор процесса;

• тип (или класс) процесса, который определяет для супервизора некоторые правила предоставления ресурсов;

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

• переменную состояния, которая определяет, в каком состоянии находится процесс (готов к работе, в состоянии выполнения, ожидание устройства ввода/вывода и т.д.);

• защищенную область памяти (или адрес такой зоны), в которой хранятся текущие значения регистров процессора, если процесс прерывается, не закончив работы. Эта информация называется контекстом задачи (процесса);

• информацию о ресурсах, которыми процесс владеет и/или имеет право пользоваться (указатели на открытые файлы, информация о незавершенных операциях ввода/вывода и т. п.);

• место (или его адрес) для организации общения с другими процессами;

• параметры времени запуска (момент времени, когда процесс должен активизироваться, и периодичность этой процедуры).

9. Опишите механизмы создания и уничтожения процессов Создание процесса

Существуют четыре основных события, приводящих к созданию процессов.

1. Инициализация системы. При запуске операционной системы создаются, как правило, несколько процессов. Некоторые из них представляют собой высокоприоритетные процессы, то есть процессы, взаимодействующие с пользователями и выполняющие для них определенную работу. Остальные являются фоновыми процессами, не связанными с конкретными пользователями, но выполняющими ряд специфических функций.

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

3. Запрос пользователя на создание нового процесса. Пользователи могут одновременно открыть несколько окон, в каждом из которых запущен какой-нибудь процесс.

4. Инициация пакетного задания. Применимо только к системам пакетной обработки данных. Когда ОС решает, что у нее достаточно ресурсов для запуска еще одного задания, она создает новый процесс и запускает новое задание из имеющейся у нее очереди входящих заданий.

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

Удаление процесса

Рано или поздно новые процессы будут завершены, обычно в силу следующих обстоятельств:

1. обычного выхода (добровольно);

2. выхода при возникновении ошибки (добровольно);

3. возникновения фатальной ошибки (принудительно), например, неверная инструкцию, ссылку на несуществующий адрес памяти или деление на нуль;

4. уничтожения другим процессом (принудительно).

1. Опишите основные состояния процессов и возможные переходы между ними. Дайте определение переключению контекста.

Несмотря на самостоятельность каждого процесса, наличие собственного счетчика команд и внутреннего состояния, процессам зачастую необходимо взаимодействовать с другими. Три состояния процесса:

Переключение контекста – переключение ЦП с одной программы, процесса, потока на другое. Переключение контекста может быть описано несколько более подробно как kernel (т. е. ядро операционной системы), выполняющее следующие действия в отношении процессов (включая потоки) на CPU: (1) приостановка прогрессии одного процесса и сохранение состояния CPU (т. е. контекста) для этого процесса где-то в памяти, (2) извлекая контекст следующего процесса из памяти и восстанавливая его в регистрах CPU и (3) возвращаясь в место, указанное счетчиком программы (т. е. возвращаясь к строке кода, в которой процесс был прерван), чтобы возобновить процесс.

При переключении контекста происходит сохранение и восстановление: регистрового контекста РОН, контекста с плавающей точкой, состояния управляющих регистров, сегментных и ММХ.

11. Опишите механизмы диспетчеризации процессов.

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

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

Чтобы создать алгоритм планирования, нужно иметь некое представление о том, с чем должен справиться толковый алгоритм. Некоторые задачи зависят от среды окружения (пакетная, интерактивная или реального времени), но есть и такие задачи, которые желательно выполнить в любом случае.

Все системы:

• равнодоступность — предоставление каждому процессу справедливой доли времени центрального процессора;

• принуждение к определенной политике — наблюдение за выполнением установленной политики;

• баланс — поддержка загруженности всех составных частей системы.

Пакетные системы (FIFO, сначала самое короткое задание, приоритет наименьшему времени выполнения):

• производительность — выполнение максимального количества заданий в час;

• оборотное время — минимизация времени между представлением задачи и ее завершением;

• использование центрального процессора — поддержка постоянной загруженности процессора.

Интерактивные системы (циклическое планирование, приоритетное, использование нескольких очередей, выбор следующего самого короткого процесса, гарантированное, лотерейное и справедливое планирование):

• время отклика — быстрый ответ на запросы;

• пропорциональность — оправдание пользовательских надежд.

Системы реального времени (жесткие и гибкие системы):

• соблюдение предельных сроков — предотвращение потери данных;

• предсказуемость — предотвращение ухудшения качества в мультимедийных системах.

12. Дайте определение свопинг. Опишите механизм управления свободной памятью при свопинге (битовые матрицы)

На практике суммарный объем оперативной памяти, необходимый для размещения всех процессов, зачастую значительно превышает имеющийся объем ОЗУ.

С годами для преодоления перегрузки памяти были выработаны два основных подхода. Самый простой из них, свопинг, заключается в размещении в памяти всего процесса целиком, его запуске на некоторое время, а затем сбросе на диск. Бездействующие процессы большую часть времени хранятся на диске и в нерабочем состоянии не занимают пространство оперативной памяти (хотя некоторые из них периодически активизируются, чтобы проделать свою работу, после чего опять приостанавливаются).