Алгоритмы замещения процессов

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

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

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

- оптимальный алгоритм;

- алгоритм дольше всех неиспользовавшегося (least recently used – LRU);

- алгоритм "первым вошел – первым вышел" (first in first out – FIFO);

- часовой алгоритм.

Оптимальный алгоритм выбирает для замещения ту страницу, обращение к которой будет через наибольший промежуток времени по сравнению с остальными. Алгоритм приводит к минимальному количеству прерываний из-за отсутствия страницы. Реализовать такой алгоритм невозможно, поскольку требуется знать все будущие события системы. Данный алгоритм используется для

Алгоритм дольше всех неиспользовавшегося (least recently used – LRU) замещает в памяти ту страницу, обращений к которой не было дольше всех. Согласно принципу локализации, ожидается, что эта страница не будет использоваться в ближайшем будущем. Каждая страница должна быть помечена во время последнего обращения к странице. Этот алгоритм сложный в реализации, так как требует больших накладных расходов, однако недалек от оптимального.

Алгоритм "первым вошел – первым вышел" (first in first out FIFO) рассматривает кадры страниц процесса как циклический буфер, страницы удаляются из него циклически. Для реализации алгоритма требуется лишь указатель, циклически проходящий по кадрам страниц процесса. Это одна из простейших стратегий размещения в реализации. Замещается страница, находящаяся в основной памяти дольше других, однако, замещенные страницы могут понадобиться вскоре снова.

Часовой алгоритм использует для каждого кадра дополнительный бит – бит использования. Когда страница впервые загружается в кадр, бит использования устанавливается в 1. При последующих обращениях к странице, бит устанавливается в 1. При работе алгоритма замещения множество кадров, являющихся кандидатами на замещение, рассматривается как циклический буфер, с которым связан указатель. При замещении страницы указатель перемещается к следующему кадру в буфере. Когда наступает время замещения страницы, ОС сканирует буфер для поиска кадра, бит использования которого равен 0; если в процессе поиска встречается кадр с битом использования, равным 1, он сбрасывается в 0. Если все кадры имеют бит использования, равный 1, указатель совершает полный круг и возвращается к начальному положению, заменяя страницу в этом кадре.

 

Исходные условия для задач

 

Задачи по распределению оперативной памяти

Память содержит N свободных участков, расположенных в порядке возрастания адресов оперативной памяти. Их размеры соответственно равны

V₁, V_2, …, V_N.

Загружается процессы, для которых необходимы объемы оперативной памяти, равные соответственно W₁ и W₂.

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

- первый подходящий участок;

- самый подходящий участок;

- самый неподходящий участок.

В случае отсутствия необходимого участка осуществить уплотнение памяти и оценить размер свободного участка после загрузки процесса.

 

Задачи по использованию алгоритмов замещения

Предполагается, что процесс состоит из N страниц, последовательность вызова которых задана:

S₁, S_2, …, S_N.

Оперативная память представлена K кадрами, которые в начальном состоянии свободны.

Необходимо оценить количество прерываний для оптимального алгоритма,дольше всех неиспользовавшегося, "первым вошел – первым вышел" и часового алгоритмов.

Примеры решения

Пример задачи по распределению оперативной памяти

Количество свободных участков равно N=10. Их размеры в порядке возрастания адресов соответственно равны:

5 40 20 15 35 10 25 30 45 50.

Последовательно загружаются процессы, для которых необходимы объемы памяти соответственно равнs W₁ = 28 и W₂ = 70.

При использовании алгоритма «первый подходящий участок» процесс загружается во второй участок, при этом объем второго свободного участка будет равен 40-28=12.

При использовании алгоритма «самый подходящий участок» процесс загружается в восьмой участок, при этом объем восьмого свободного участка будет равен 30-28=2.

При использовании алгоритма «самый неподходящий участок» процесс загружается в десятый участок, при этом объем десятого свободного участка будет равен 50-28=22.

При загрузке второго процесса подходящий свободный участок отсутствует, поэтому осуществляется уплотнение памяти, в результате которого будет получен участок объемом 275, а после загрузки второго процесса будем иметь один свободный участок объемом 275-70=205.

Пример задачи по использованию алгоритмов замещения

Количество страниц процесса равно N=5, количество кадров оперативной памяти равно K=3.

Последовательность обращения к страницам следующая:

2 3 2 1 5 2 4 5 3 2 5 2.

Результаты решения задачи имеют вид:

 

Обращение к страницам

Оптимальный алгоритм

F

F

F

Алгоритм дольше всех неиспользо-вавшегося

F

F

F

F

Алгоритм «первым во- шел - первым вышел»

F

F

F

F

F

F

Часовой алгоритм

2^*

2^*

2^*

2^*

5^*

5^*

5^*

5^*

3^*

3^*

3^*

3^*

3^*

3^*

3^*

2^*

2^*

2^*

2^*

2^*

1^*

4^*

4^*

5^*

5^*

F

F

F

F

F

 

Для данной задачи количество прераваний следующее:

- оптимальный алгоритм - 3;

- долше всех неиспользовавшегося - 4;

- «первый вошел – первым вышел» - 6;

- часовой алгоритм - 5.

 

Варианты задач

 

Варианты задач распределения оперативной памяти

Вариант

W1

W2

V1

V2

V3

V4

V5

V6

V7

V8

V9

V10

Варианты задач алгоритмов замещения

Вариант

N

K

S1

S2

S3

S4

S5

S6

S7

S8

S9

S10

S11

S12

S13

S14

S15

 

УПРАВЛЕНИЕ ФАЙЛАМИ

Теоретическая часть

 

Все современные ОС имеют в своем составе системы управления файлами.

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

Информация на магнитных дисках размещается и передается бло­ками, которые называют секторами, расположенными на концентрических дорожках поверхности диска. Каждая дорожка обра­зуется при вращении магнитного диска под зафиксированной в некотором положении головкой чтения/записи.

Каждой головке соответствует своя поверхность диска.

Группы дорожек (треков) одного радиуса, расположенных на поверхностях маг­нитных дисков называются цилиндрами.

Размер сектора устанавливается контроллером или драйвером. Обычно его размер равен 512 байт.

Обмен информацией между ОЗУ и дисками физически осуществ­ляется только секторами

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

Разбиение на кластеры взамен одиночных секторов уменьшает фрагмента­цию файлов и ускоряет доступ к ним. Однако слишком большой размер кластера ведет к неэффективному использова­нию области данных, особенно в случае большого количества маленьких файлов. Поэтому в современных файловых системах размеры кластеров ограничи­ваются (обычно — от 512 байт до 4 Кбайт). Их максимальное количество определяется количеством бит, выделяемых для задания номера кластера. Так, например, для файловой системы FAT количество кластеров равно 2¹⁶, а для FAT32 – 2³².

Исходные условия для задач

 

Задан объем жесткого диска V, размер сектора равен 512 байт, для номера кластера выделяется R разрядов (16 или 32), размер может быть ограничен и равен K, это оказывает ограничение на размер логического диска и максимальный размер файла.

Необходимо:

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

- оценить потери на кластеризацию P при количестве файлов, равном F;

- оценить максимальный размер L логического диска при ограниченном размере кластера.

 

Пример решения

Заданы:

- объем жесткого диска V =200 Мбайт;

- количество разрядов для указания номера кластера R =16;

- размер кластера ограничен K =1024 байт;

- количество записанных файлов F =100.

Решение

1) Оценим предварительно возможный размер кластера без ограничений

k =200*1024*1024/2¹⁶=3200 байт,

учитывая размер сектора 512 байт, оценим количество секторов

s =3200/512= 6.25,

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

K = 512*7=3584 байта.

2) Средние потери P на кластеризацию равны половине кластера на один файл и при количестве файлов равном 100 равны

P =3584*100=358 400 байт.

3) При ограничении размера кластера, то есть равном K =1024 и количестве, равном 2¹⁶=65535 получим максимально возможный размер логического диска

L = 65535*1024=67107840, то есть примерно 67 Мбайт.

Варианты задач

Вариант	V	R	K	F
	100 Мб
	200 Мб
	300 Мб
	400 Мб
	500 Мб
	600 Мб
	700 Мб
	800 Мб
	900 Мб
	1 Гб
	2 Гб
	3 Гб
	4 Гб
	5 Гб
	10 Гб
	20 Гб
	30 Гб
	40 Гб
	50 Гб
	100 Гб
	150 Гб
	200 Гб
	250 Гб
	300 Гб
	350 Гб

УПРАВЛЕНИЕ ВВОДОМ-ВЫВОДОМ

Теоретическая часть

 

Имеется два основных режима ввода/вывода: режим обмена с опро­сом готовности и режим обмена с прерываниями.

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

Режим обмена с прерываниями является режимом асинхронного управления. После выдачи команды ввода/вывода осуществляется переход на выполнение другой программы. А появление сигнала готовности трактуется как запрос на прерывание от устройства ввода/вывода. Драйверы, работающие в режиме прерываний, представляют собой сложный комп­лекс программных модулей и могут иметь несколько секций: секцию запуска, одну или несколько секций продолжения и секцию завершения.

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

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

Главная их задача — создать видимость параллельного разделения устройства ввода/вывода с последовательным доступом, которое фактически должно использоваться только монопольно и может быть закрепленным. Вычислительному процессу предоставляется не реальное, а виртуальное устройство. Потоки информации сначала направляются в специальный файл на магнитном диске, который называют спул-файлом. Затем в соответствии с принятой дисциплиной обслуживания и приоритетами приложений процесс работает со спул-файлом.

Исходные условия для задач

В ОС запускаются N задач.

Каждая задача представлена процессом, представленным E этапов выполнения.

Время выполнения каждого этапа составляет T единиц (квантов времени).

Каждый этап представляет либо работу процессора, либо и операцию ввода-вывода.

Ввод-вывод (В/в) выполняется независимо от работы процессора (Пр) с использованием спул-файла. Время, затраченное процессом на ввод-вывод с использованием спул-файла незначительно а вывод результатов осуществляется последовательно из спул-файла по мере его заполнения информации процессом.

Необходимо оценить общее время выполнения заданий:

- невытесняющей многозадачности;

- вытесняющей многозадачности.

Оценить загрузку процессора.

Решение выполнять, используя циклограммы работы.

Пример решения

Для двух задач (N =2), каждая из которых представлена четырьмя этапами работы (E =4), время выполнения каждого этапа составляет два кванта (T =2). Работа процессора для первой задачи выполняется во время первого и третьего этапов (P ₁=1,3), а для второй задачи во время первого и четвертого этапов (P ₂=1,4).

 

Первый процесс
Пр1	Вв 1	Пр1	Вв1

 

Второй процесс
Пр2	Вв2	Вв2	Пр2