Лабораторная работа №4 по дисциплине «Операционные Системы»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО

ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Лабораторная работа №4

По дисциплине «Операционные Системы»

Управление процессами. Семафорные операции.

Факультет: АВТ

Группа: АМ-511

Студент:

Преподаватель:

Новосибирск, 2008г.

Цель работы:

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

Сравнение семафоров в UNIX и WINDOWS NT

В отличие от общепринятого понятия – семафор, который может быть либо открыт, разрешая движение, либо закрыт, запрещая его, семафоры в операционной системе Microsoft Windows NT действуют более сложным образом.

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

С каждым семафором связывается счетчик, начальное и максимальные значения которого задаются при создании семафора. Значение этого счетчика уменьшается, когда задача вызывает для семафора функцию WaitForSingleObject или WaitForMultipleObject, и увеличивается при вызове другой, специально предназначенной для этого функции ReleaseSemaphore.

Если значение счетчика семафора равно нулю, он находится в неотмеченном состоянии. Если же это значение больше нуля, семафор переходит в отмеченное состояние.

Пусть, например, приложение создало семафор, указав для него максимальное значение счетчика, равное трем. Пусть начальное значение этого счетчика также будет равно трем.

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

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

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

Семафор в Unix состоит из следующих элементов.

1.  Значение семафора.

2.  Идентификатор последнего из процессов, работавших с семафором.

3.  Количество процессов, ожидающих увеличения значения семафора.

4.  Количество процессов, ожидающих момента, когда значение семафора станет равным 0.

Для создания набора семафоров и получения доступа к ним используется системная функция semget, для выполнения различных управляющих операций над набором – функция semctl, для работы со значениями семафоров – функция semop.

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

Синтаксис вызова системной функции semop:

oldval = semop(id, oplist, count), где id – дескриптор, возвращаемый функцией semget, oplist – указатель на список операций, count – размер списка. Возвращаемое функцией значение oldval является прежним значением семафора, над которым производилась операция.

Каждый элемент списка операций имеет следующий формат:

-  номер семафора, идентифицирующий элемент массива семафоров, над которым выполняется операция;

-  код операции;

-  флаги.

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

Ядро меняет значение семафора в зависимости от кода операции. Если код операции имеет положительное значение, ядро увеличивает значение семафора и выводит из состояния приостанова все процессы, ожидающие наступления этого события. Если код операции равен 0, ядро проверяет значение семафора: если оно равно 0, ядро переходит к выполнению других операций; в противном случае ядро увеличивает число приостановленных процессов, ожидающих, когда значение семафора станет нулевым, и «засыпает». Если код операции имеет отрицательное значение и если его абсолютное значение не превышает значение семафора, ядро прибавляет код операции к значению семафора. Если результат равен 0, ядро выводит из состояния приостанова все процессы, ожидающие обнуления значения семафора. Если результат меньше абсолютного значения кода операции, ядро приостанавливает процесс до тех пор, пока значение семафора не увеличится.

Выполнение лабораторной работы:

Исходные данные:

на процессоре одновременно развивается 6 задач интенсивность обращения к ресурсам – 40%

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

Рис. 1 Временная диаграмма, полученная в результате моделирования

Анализируя временную диаграмму, составим таблицу:

Процесс	print	tty	winch	flop	Scs	Sблок	Scpu. факт
0	-	35	-	15	50	0	51,98
1	14	-	72	-	86	35	45,13
2	44	-	40	-	84	0	35,30
3	-	-	-	104	104	12	32,55
4	54	-	-	24	78	27	72,53
5	47	61	-	-	108	0	66,43

где:

·  print, tty, winch, flop – время нахождения на каждом из перечисленных ресурсов (если несколько раз процесс обращается к одному и тому же ресурсу, то время суммируется);

·  Scs – суммарное время нахождения процесса на всех ресурсах;

·  Sблок – суммарное время блокирования процесса;

·  Scpu. факт – суммарное время (фактическое) пользования процессором (исполнение кодовых инструкций);

·  Sоч-на-вып – общее время нахождения процесса в очереди на выполнение;

Пример расчета для процесса № 0:

1)  Scs = tty + flop = 35 + 15 = 50

2)  Sблок = 0

3)  Scpu. факт = 51,98

При переходе на уровень диспетчеризации необходимо рассчитывать время работы диспетчера: , где ki – коэффициент мультипрограммирования i-го интервала, - время диспетчера, затраченное на 1 процесс на i-ом интервале.

Переход на уровень диспетчеризации приведен в приложении.

Вывод:

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

Семафоры – целочисленные объекты, для которых определены две элементарные операции – P и V. Операция P заключается в уменьшении значения семафора, операция V – в увеличении этого значения.

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

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

2. Исходные данные:

Размер кванта времени: 8

Объем оперативной памяти: 10

Шесть процессов.

3. Результаты исследований работы процессов по дисциплине FIFO

№	Время	Загрузка	Операция	Процесс	Действие
1	26	50	P	12	Процесс 12 занял принтер
2	61	50	V	12	Процесс 12 освободил дисковод
3	113	51	P	12	Процесс 12 занял винчестер
4	151	45	V	12	Процесс 12 освободил винчестер
5	204	46	P	14	Процесс 14 занял винчестер
6	212	46	P	15	Процесс 15 занял дисковод
7	254	44	V	14	Процесс 14 освободил винчестер
8	255	44	V	15	Процесс 15 освободил дисковод
9	290	42	P	14	Процесс 14 занял дисковод
10	295	42	P	15	Процесс 15 занял винчестер
11	319	43	P	13	13 ожидает Дисковод
12	340	44	P	11	11 ожидает дисковод
13	354	44	V	14,13	14 освободил дисковод, 13 получил дисковод
14	355	44	V	15	15 освободил винчестер
15	361	44	P	10	10 ожидает дисковод
16	372	44	P	14	14 занял винчестер
17	403	44	V	13,11	13 освободил дисковод, 11 получил дисковод
18	426	44	P	13	13 ожидает винчестер
19	439	44	V	14,13	14 освободил винчестер, 13 получил винчестер
20	455	44	V	11,10	11 освободил дисководб 10 получил дисковод

5.  Результаты исследований работы процессов по дисциплине LFU

№	Время	Загрузка
1	26	50
2	50	61
3	113	51
4	152	49
5	206	47
6	252	44
7	253	43
8	275	44
9	296	43
10	297	43
11	312	44
12	325	45
13	333	45
14	345	46
15	358	46
16	387	48
17	407	48
18	426	48
19	441	48
20	453	48
21	454	48
22	483	47
23	512	49
24	515	49
25	539	50
26	551	49
27	582	50
28	597	49
29	635	48
30	647	49
31	747	49
32	762	49
33	811	49
34	812	49
35	859	49
36	901	49
37	957	50
38	988	50
39	1023	49
40	1073	49
41	1120	49

5. Временные диаграммы загрузки процессора для двух дисциплин

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

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

7. Выводы

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

Момент времени холостого хода для ДО FIFO – 2560.

Момент времени холостого хода для ДО LFU – 2610.

Из этих данных можно сделать вывод о том, что ДО LFU наиболее эффективна, т. к. она обслуживает процессы быстрее FIFO, однако это преимущество проявляется далеко не всегда. Как видно из графика, средняя величина загрузки процессора на время выполнения для этой дисциплины больше, чем для других и равна 48%.