Контрольная работа по «Операционные системы ЭВМ»

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

Windows NT поддерживает 32 уровня приоритетов, разделенных на два класса - класс  реального времени и класс  переменных приоритетов. Нити реального  времени, приоритеты которых находятся  в диапазоне от 16 до 31, являются  более приоритетными процессами  и используются для выполнения  задач, критичных ко времени.

Каждый раз, когда необходимо выбрать нить для выполнения, диспетчер прежде всего просматривает очередь готовых нитей реального времени и обращается к другим нитям, только когда очередь нитей реального времени пуста. Большинство нитей в системе попадают в класс нитей с переменными приоритетами, диапазон приоритетов которых от 0 до 15. Этот класс имеет название "переменные приоритеты" потому, что диспетчер настраивает систему, выбирая (понижая или повышая) приоритеты нитей этого класса.

Алгоритм планирования нитей в Windows NT объединяет в себе обе базовых концепции - квантование и приоритеты. Как и во всех других алгоритмах, основанных на квантовании, каждой нити назначается квант, в течение которого она может выполняться. Нить освобождает процессор, если:  блокируется, уходя в состояние ожидания; завершается; исчерпан квант; в очереди готовых появляется более приоритетная нить.

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

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

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

3. Физическая организация и адрес файла

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

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

 

Рис. 2. Физическая организация файла: а - непрерывное размещение; б - связанный список блоков; в - связанный список индексов; г - перечень номеров блоков

Популярным способом, используемым, например, в файловой системе FAT операционной системы MS-DOS, является использование связанного списка индексов. С каждым блоком связывается некоторый элемент - индекс. Индексы располагаются в отдельной области диска (в MS-DOS это таблица FAT). Если некоторый блок распределен некоторому файлу, то индекс этого блока содержит номер следующего блока данного файла. При такой физической организации сохраняются все достоинства предыдущего способа, но снимаются оба отмеченных недостатка: во-первых, для доступа к произвольному месту файла достаточно прочитать только блок индексов, отсчитать нужное количество блоков файла по цепочке и определить номер нужного блока; во-вторых, данные файла занимают блок целиком, а значит, имеют объем, равный степени двойки.

В заключение рассмотрим задание физического расположения файла путем простого перечисления номеров блоков, занимаемых этим файлом. ОС UNIX использует вариант данного способа, позволяющий обеспечить фиксированную длину адреса, независимо от размера файла. Для хранения адреса файла выделено 13 полей. Если размер файла меньше или равен 10 блокам, то номера этих блоков непосредственно перечислены в первых десяти полях адреса. Если размер файла больше 10 блоков, то следующее 11-е поле содержит адрес блока, в котором могут быть расположены еще 128 номеров следующих блоков файла. Если файл больше, чем 10+128 блоков, то используется 12-е поле, в котором находится номер блока, содержащего 128 номеров блоков, которые содержат по 128 номеров блоков данного файла. И, наконец, если файл больше 10+128+128/128, то используется последнее 13-е поле для тройной косвенной адресации, что позволяет задать адрес файла, имеющего размер максимум 10+ 128 + 128/128 + 128/128/128.

4. Переведите числа из одной системы счисления в другую: 22710→X8, 48610→X16, 32116→X10, 10011012→X10, A4E16→X10, 11000.11→X2

Решение:

1. 22710→X8

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

227	8
16	28	8
67	24	3
64	4
3

В результате, построив число из остатков деления (справа налево), получим число 3438

2. 48610→X16

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

486	16
48	30	16
6	16	1
	14

 

В результате получились остатки 6, 14 и 1. Десятичное число 14 соответствует шестнадцатеричному числу E. Поэтому получилось число 1E616

3. 32116→X10

При переводе числа из шестнадцатеричной СС в десятичную, нужно пронумеровать число справа налево:

 2  1  0

32116 , а затем записать в виде: 32116=3·162+2·161+1·160, где 16 – основание СС, показатели степени – номер позиции. Вычислим:

32116=3·162+2·161+1·160=3·256+2·16+1=768+32+1=80110

4. 10011012→X10

Аналогично предыдущему примеру осуществляется перевод числа из двоичной СС в десятичную СС. Сначала пронумеруем число справа налево и запишем его в виде суммы:

6  5  4  3  2  1  0

10011012=1·26+0·25+0·24+1·23+1·22+0·21+1·20=64+0+0+8+4+1=7710

5. A4E16→X10

Аналогично предыдущему примеру осуществляется перевод числа из шестнадцатеричной СС в десятичную СС, но шестнадцатеричное число A соответствует десятичному числу 10, а E=14, поэтому пронумеруем это число и запишем в следующем виде:

2   1 0

A4E16=A·162+4·161+E·160=10·162+4·161+14·160=10·256+4·16+14=2560+64+14=263810

6. 11000.11→X2

Чтобы перевести число из десятичной СС в двоичную СС, нужно последовательно делить целую часть данного числа на 2 до получения целого остатка, меньше, чем 2:

 

11000	2
10	5500	2
10	4	2750	2
10	15	2	1375	2
0	14	7	12	687	2
	10	6	17	6	343	2
	10	15	16	8	2	171	2
	0	14	15	8	14	16	85	2
		10	14	7	14	11	8	42	2
		10	1	6	3	10	5	4	21	2
		0		1	2	1	4	2	2	10	2
					1		1	2	1	10	5	2
								0		0	4	2	2
											1	2	1
												0

 

 

 

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

 

 

 

		0,11
	×
		2
0		0,22
	×
		2
0		0,44
	×
		2
0		0,88
	×
		2
1		0,76
	×
		2
1		0,52
	×
		2
1		0,04
	×
		2
0		0,08
	×
		2
0		0,16
	×
		2
0		0,32
	×
		2
0		0,64
	×
		2
		0,28