Опишите механизмы диспетчеризации процессов.
В однопроцессорных системах потоки конкурируют за ресурсы процессора. В этом случае они выполняются фактически квазипараллельно и поэтому взаимно влияют друг на друга, порождая проблему эффективного планирования. Механизмы планирования потоков вместе с системой приоритетов устанавливают правила и условия переключения потоков.
Планирование — это работа по определению того, в какой момент необходимо прервать выполнение активного текущего потока и какому потоку предоставить возможность выполняться. Системная программа, выбирающая один из готовых для исполнения потоков, называется планировщиком. Диспетчеризация заключается в реализации найденного в результате планирования решения, то есть переключении процессора с одного потока на другой. Механизм диспетчеризации непосредственно влияет на минимальное время реакции управляющей системы на внешние события.
Чтобы создать алгоритм планирования, нужно иметь некое представление о том, с чем должен справиться толковый алгоритм. Некоторые задачи зависят от среды окружения (пакетная, интерактивная или реального времени), но есть и такие задачи, которые желательно выполнить в любом случае.
Все системы:
• равнодоступность — предоставление каждому процессу справедливой доли времени центрального процессора;
• принуждение к определенной политике — наблюдение за выполнением установленной политики;
• баланс — поддержка загруженности всех составных частей системы.
Пакетные системы (FIFO, сначала самое короткое задание, приоритет наименьшему времени выполнения):
• производительность — выполнение максимального количества заданий в час;
• оборотное время — минимизация времени между представлением задачи и ее завершением;
• использование центрального процессора — поддержка постоянной загруженности процессора.
Интерактивные системы (циклическое планирование, приоритетное, использование нескольких очередей, выбор следующего самого короткого процесса, гарантированное, лотерейное и справедливое планирование):
• время отклика — быстрый ответ на запросы;
• пропорциональность — оправдание пользовательских надежд.
Системы реального времени (жесткие и гибкие системы):
• соблюдение предельных сроков — предотвращение потери данных;
• предсказуемость — предотвращение ухудшения качества в мультимедийных системах.
Дайте определение свопинг. Опишите механизм управления свободной памятью при свопинге (битовые матрицы)
На практике суммарный объем оперативной памяти, необходимый для размещения всех процессов, зачастую значительно превышает имеющийся объем ОЗУ.
С годами для преодоления перегрузки памяти были выработаны два основных подхода. Самый простой из них, свопинг, заключается в размещении в памяти всего процесса целиком, его запуске на некоторое время, а затем сбросе на диск. Бездействующие процессы большую часть времени хранятся на диске и в нерабочем состоянии не занимают пространство оперативной памяти (хотя некоторые из них периодически активизируются, чтобы проделать свою работу, после чего опять приостанавливаются).
|
|
Изменения в выделении памяти по мере появления процессов в памяти и выгрузки их из нее (неиспользованные области памяти заштрихованы) |
|
Изначально в памяти присутствует только процесс A. Затем создаются или появляются в памяти путем свопинга с диска процессы B и C. На рис. г процесс A за счет свопинга выгружается на диск. Затем появляется процесс D и выгружается из памяти процесс B. И наконец, снова появляется в памяти процесс A. Поскольку теперь процесс A находится в другом месте, содержащиеся в нем адреса должны быть перестроены либо программным путем, при загрузке в процессе свопинга, либо (скорее всего) аппаратным путем в процессе выполнения программы. Когда в результате свопинга в памяти создаются несколько свободных областей, их можно объединить в одну большую за счет перемещения при первой же возможности всех процессов в нижние адреса. Эта технология известна как уплотнение памяти.
Если память распределяется в динамическом режиме, то управлять этим должна операционная система. В общих чертах, существуют два способа отслеживания использования памяти: битовые матрицы и списки свободного пространства.
Если память распределяется в динамическом режиме, то управлять этим должна операционная система. В общих чертах, существуют два способа отслеживания использования памяти: битовые матрицы и списки свободного пространства.
При использовании битовых матриц память делится на единичные блоки размером от нескольких слов до нескольких килобайт. С каждым единичным блоком соотносится один бит в битовой матрице, который содержит 0, если единичный блок свободен, и 1, если он занят (или наоборот).
Важным вопросом является размер единичного блока памяти. Чем меньше блок, тем больше битовая матрица. Но даже с таким небольшим единичным блоком памяти, размер которого равен 4 байта, для 32 бит памяти понадобится 1 бит матрицы. Память, состоящая из 32n бит, будет использовать n бит матрицы, таким образом, битовая матрица займет лишь 1/32 памяти. Если выбран более объемный единичный блок памяти, битовая матрица будет меньше, но тогда в последнем блоке процесса, если он не будет в точности кратен размеру единичного блока, будет впустую теряться довольно существенный объем памяти.
+: простой способ отслеживания слов памяти в фиксированном объеме памяти, поскольку ее размер зависит только от размера памяти и размера единичного блока памяти.
-: поиск в битовой матрице последовательности заданной длины — довольно медленная операция (поскольку последовательность может пересекать границы слов в матрице).