Задачи по основным разделам операционных систем

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Для решения задач по курсам

«Системное программное обеспечение» «Операционные системы»

для студентов специальностей

8.091501 «Компьютерные системы и сети»,

7.091506 “Специализированные компьютерные системы”

всех форм обучения

ЗАДАЧИ ПО ОСНОВНЫМ РАЗДЕЛАМ ОПЕРАЦИОННЫХ СИСТЕМ

 

 

 

Методические указания для решения задач по курсам «Системное программное обеспечение» и «Операционные системы» для студентов специальностей 8.091501 «Компьютерные системы и сети», 7.091506 “Специализированные компьютерные системы” всех форм обучения. Задачи по основным разделам операционных систем / Сост. Вершина А.И., Семерюк Т.Н. – Запорожье: ЗНТУ, 2009. – с.

 

 

Составители: Вершина А.И., доцент, к.т.н.

Семерюк Т.Н., ассистент

 

Ответственный

за выпуск: Вершина А.И., доцент, к.т.н.

Утвержден на заседании

кафедры компьютерных систем и сетей

Протокол № от..2009г.

СОДЕРЖАНИЕ

1.1 1.2 1.3 1.4 2.1 2.2 2.3 2.4 3.1 3.1.1 3.1.2 3.2 3.2.1 3.2.2 3.3 3.3.1 3.3.2 3.4 3.4.1 3.4.2 4.1 4.2 4.3 4.4 5.1 5.2 5.3 5.4

СОДЕРЖАНИЕ………………………………………………. ВВЕДЕНИЕ…………………………………………………… Управление заданиями………………………...…… Теоретическая часть…………………………………………. Исходные условия для задач………………………………… Пример решения……………………………………………… Варианты задач……………………………………………….. Управление процессами……………………………...……… Теоретическая часть………………………………………….. Исходные условия для задач ………………………………... Пример решения………………………………………...……. Варианты задач……………………………………………….. УПРАВЛЕНИЕ ПАМЯТЬЮ…………………………...……. Теоретическая часть………………………………………….. Распределение оперативной памяти…………………...…… Алгоритмы замещения процессов………………………...… Исходные условия для задач………………………………… Задачи по распределению оперативной памяти……………. Задачи по использованию алгоритмов замещения………… Примеры решения……………………………………………. Пример задачи по распределению оперативной памяти….. Пример задачи по использованию алгоритмов замещения.. Варианты задач……………………………………………… Варианты задач распределения оперативной памяти…….. Варианты задач алгоритмов замещения…………………… УПРАВЛЕНИЕ ФАЙЛАМИ……………………………….. Теоретическая часть………………………………………… Исходные условия для задач……………………………….. Пример решения……………………………………………... Варианты задач………………………………………………. УПРАВЛЕНИЕ ВВОДОМ-ВЫВОДОМ……………………. Теоретическая часть…………………………………………. Исходные условия для задач………………………………… Пример решения……………………………………………... Варианты задач………………………………………………. ПЕРЕЧЕНЬ ТЕМ ДЛЯ ПРОВЕРКИ ЗНАНИЙ…………….. ЛИТЕРАТУРА………………………………………………..

 

 

ВВЕДЕНИЕ

Методические указания предназначены для решения задач по дисциплине «Операционные системы», являющейся составной частью «Системного программного обеспечения». Рассмотрены основные вопросы: подсистем управления заданиями, памяти, файлами и ввода-вывода. Приведены примеры решения задач и представлены задачи для самостоятельной работы.

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

1 Управление заданиями

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

При выполнении заданий в условиях мультизадачности различают переключательную, невытесняющую и вытесняющую много­задачность.

Переключение программ имеет очень большое значение. Пользователи DOS осуществляли такое переключение "вручную", работая с резидентными программами. В этом случае выполнение текущей программы приоста­навливается и на экране появляется резидентная программа. Это позволяет пользователю приступить к работе с другой программой, не завершая текущей, и затем вновь вернуться к прерванной программе.

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

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

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

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

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

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

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

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

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

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

- для однозадачного режима;

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

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

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

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

 

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

 

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

 

Однозадачный режим

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

Второй процесс

Пр1

Вв 1

Пр1

Вв1

Пр2

Вв2

Вв2

Пр2

 

Общее время выполнения задач равно 16 квантов времени. Задачи выполняются одна за другой. Процессор загружен на 50%. Количество переключений равно 1.

 

Невытесняющая многозадачность

Пр1	Вв1	Пр1		Вв1
	Пр2	Вв2	Вв2	Пр2

 

Общее время выполнения задач составляет 10 квантов времени. Процессор загружен на 60%. Количество переключений равно 3.

Вытесняющая многозадачность

Пр1		Пр1	В/в1	В/в1		Пр1		Пр1	Вв1	Вв1
	Пр2		Пр2		Вв2	Вв2	Вв2	Вв2	Пр2		Пр2

Общее время выполнения задач составляет 12 квантов времени. Процессор загружен на 67%. Количество переключений равно 11.

 

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

Вариант	N	E	T	P1	P2	P3
				1,2	1,2	-
				1,2	1,3	-
				1,2	1,4	-
				1,3	1.2	-
				1,3	1,3	-
				1,3	1,4	-
				1,4	1,2	-
				1,4	1,3	-
				1,4	1,4	-
				1,2	1,2	1,2
				1,2	1,2	1,3
				1,2	1,2	1,4
				1,2	1,3	1,2
				1,2	1,3	1,3
				1,2	1,3	1,4
				1,2	1,4	1,2
				1,2	1,4	1,3
				1,2	1,4	1,4
				1,3	1,2	1,2
				1,3	1,2	1,3
				1,3	1,2	1,4
				1,3	1,3	1,2
				1,3	1,3	1,3
				1,3	1,3	1,4
				1,3	1,4	1,2

Управление процессами

 

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

 

Все многозадачные операционные системы используют кон­цепцию процесса. Задачей операционной системы является определение схемы чередования процессов и вы­деления им ресурсов.

В простейшем случае процесс любой мо­мент времени может быть в одном из двух состояний: выполняющийся или не выпол­няющийся.

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

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

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

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

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

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

Каждый приостановленный процесс обычно блокирован в ожидании какого-то определенного собы­тия, и если это событие происходит, процесс перестает быть блокированным и можно продолжить его выполнение.

Все выше сказанное приводит к следующим состояниям процесса:

• новый (Н):

• выполняющийся (В);

• готовый (Г):

• блокированный (Б):

• блокированный/приостановленный (Б/П):

• готовый/приостановленный (Г/П)

• завершающийся (З).

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

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

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

 

Определить какие из перечисленных переходов между состояниями процессов являются допустимыми:

 

Н-Г	Б-В	В-З	В-Г/П	Б/П-Г/П	З-Г	Б/П-В	Б/П-Б	Б-В	Г/П-Н

 

Допустимыми переходами являются 1, 3, 5, 8, а переходы 2, 4, 6, 7, 9 и 10 – невозможны.

 

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

Вариант задачи	Варианты переходов между состояниями
	Н-В	Н-Г	Н-Б	В-Г	В-Б/П	В-Г/П	Г-Б	Г-Б/П	Г-Г/П	Б-Б/П
	Б-Г/П	Б-З	Б/П-Г/П	Б/П-З	Б/П-Н	Г/П-З	Г/П-Н	Г/П-В	З-Н	З-В
	З-Г	Н-В	Н-Г	В-Г	В-Б/П	Г-Б	Г-Б/П	Б-Б/П	Б-Г/П	Б/П-Г/П
	Б/П-З	Г/П-З	Г/П-Н	З-Н	З-В	Н-В	В-Г	Г-Б	Б-Б/П	Б/П-Г/П
	Г/П-З	Н-В	Н-Г	Н-Б	Н-Б/П	В-Г	В-Б/П	В-Г/П	В-З	Г-Б
	Г-Б/П	Г-Г/П	Г-З	Г-Н	Б-Б/П	Б-Г/П	Б-З	Б-Н	Б-В	Б/П-Г/П
	Б/П-З	Б/П-Н	Б/П-В	Б/П-Г	З-Н	З-В	З-Г	З-Б	З-Б/П	Н-В
	Н-Г	Н-Б	Н-Б/П	Н-Г/П	Н-З	В-Г	В-Б	В-Б/П	В-Г/П	В/З
	Н-В	Н-Г	Н-Б	Н-Б/П	Н-Г/П	Н-З	В-Г	В-Б	В-Б/П	В-Г/П
	В-З	В-Н	Г-Б	Г-Б/П	Г-Г/П	Г-З	Г-Н	Г-В	Б-Б/П	Б-Г/П
	Б-З	Б-Н	Б-В	Б-Г	Б/П-Г/П	Б/П-З	Б/П-Н	Б/П-В	Б/П-Г	Б/П-Б
	Г/П-З	Г/П-Н	Г/П-В	Г/П-Г	Г/П-Б	Г/П-Б/П	З-Н	З-В	З-Г	З-Б
	З-Б/П	З-Г/П	Н-В	Н-Г	Н-Б	В-Г/П	Г-Б	Г-Б/П	Г-Г/П	Б-Б/П
	Б-Г/П	Б-З	Б/П-Г/П	Б/П-З	Б/П-Н	Г-Б	Г-Б/П	Б-Б/П	Б-Г/П	Б/П-Г/П
	З-Г	Н-В	Н-Г	В-Г	В-Б/П	Б-Г/П	Б-З	Б/П-Г/П	Б/П-З	Б/П-Н
	Б/П-З	Г/П-З	Г/П-Н	З-Н	З-В	В-Г	В-Б/П	В-Г/П	В-З	Г-Б
	Г/П-З	Н-В	Н-Г	Н-Б	Н-Б/П	Б-Г/П	Б-З	Б-Н	Б-В	Б/П-Г/П
	Н-Г	Н-Б	Н-Б/П	Н-Г/П	Н-З	Г-З	Г-Н	Г-В	Б-Б/П	Б-Г/П
	Н-В	Н-Г	Н-Б	Н-Б/П	Н-Г/П	Б/П-З	Б/П-Н	Б/П-В	Б/П-Г	Б/П-Б
	Б/П-З	Б/П-Н	Б/П-В	Б/П-Г	Б/П-Б	В-З	В-Н	Г-Б	Г-Б/П	Г-Г/П
	Н-В	Н-Г	Н-Б	Б-Г/П	Б-З	Б/П-Г/П	Г/П-З	Г/П-Б	Г/П-Б/П	З-Н
	Б-Г	Б/П-Г/П	Б/П-З	Н-В	Н-Г	Н-Б	Г/П-Б	Г/П-Б/П	З-Н	Г/П-В
	Г/П-Г	Г/П-Б	Г/П-Б/П	З-Н	З-В	В-З	В-Н	Г-Б	Г-Б/П	З-Б/П
	Б/П-В	Б/П-Г	Б/П-Б	В-З	В-Н	Н-В	Н-Г	Н-Б	Н-Б/П	Н-Г/П
	Б/П-Г/П	Б/П-З	Б/П-Н	Г/П-З	Г/П-Н	В-Г/П	Г-Б	Г-Б/П	Г-Г/П	Б-Б/П

 

УПРАВЛЕНИЕ ПАМЯТЬЮ

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

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

 

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

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

Количество свободных участков равно 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 Гб

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

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

 

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

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

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

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

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