Вариант решения домашнего задания №1 - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Вариант решения домашнего задания №1 - страница №1/1

Вариант решения домашнего задания №1.

Задача 1.
а) Плотность битов вдоль внешней дорожки определяется по формуле:

.
Емкость дорожки = 300 Кб = 307 200 байт = 2 457 600 бит.

Обозначим через x долю межсекторных промежутков дорожки.

Полезная длина внешней дорожки = .

Обычно диаметр внешней дорожки диска составляет 3.5 дюйма. Следовательно,

Полезная длина внешней дорожки = дюйма.

Таким образом, плотность битов вдоль внешней дорожки = . Требуется найти минимальное значение x (), при котором плотность была бы больше 300 000 бит/дюйм, т.е. удовлетворяющее неравенству:



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

В таком случае, поскольку диаметр внутренней дорожки обычно равен 1.5 дюймам, плотность битов вдоль внутренней дорожки = .

б) Пусть N – количество дорожек поверхности диска.

Нужно определить максимальное и среднее время получения блока.

В обоих случаях нужно определить время передачи блока данных (время движения головок над секторами блока). По условию блок состоит из 16 секторов, т.е. блоку головок требуется пройти дугу, состоящую из 16 секторов и 15 межсекторных промежутков. Всего на дорожке 1200 секторов и столько же межсекторных промежутков. Поскольку межсекторные промежутки составляют 26% дорожки, то их общая длина равна . Таким образом, длина дуги = . Так как время одного оборота диска составляет , то время передачи блока данных = .

Максимальное время получения блока = максимальное время движения головок +

+ максимальная задержка вращения + время передачи блока

В худшем случае потребуется двигать блок головок от одного крайнего цилиндра к другому, т.е. пройти N-1 цилиндр, т.е. максимальное время движения головок = =1+0.005*(N-1) мс. Максимальная задержка вращения = времени одного оборота диска, т.е. 8.333 мс. Таким образом,

Максимальное время получения блока = 1+0.005*(N-1)+8.333+0.109 = 9.437+0.005*N мс.

Среднее время получения блока = среднее время движения головок +

+ средняя задержка вращения + время передачи блока.

Среднее количество цилиндров, которое требуется пройти блоку головок = N/3. Средняя задержка вращения = время одного оборота/2 = 4.1665 мс

Среднее время получения блока = 1+0.005*N/3 + 4.1665 + 0.109 = 5.2755+0.0016(6)*N.

Требуется подобрать N так, чтобы выполнялось неравенство



, т.е.

, или , т.е. количество дорожек равно 4 503 дорожки.
Задача 2.
Среднее время получения блока при движении головок на n цилиндров = 1+0.005*n + +4.1665+0.109 = 0.005*n + 5.2755 мс.

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

1. 0 мс – 2 000 цилиндр;

2. 3 мс – 100 цилиндр;

3. 5 мс – 500 цилиндр;

4. 6 мс – 300 цилиндр;

5. 10 мс – 3 500 цилиндр.

Алгоритм FIFO.

Момент завершения обработки запроса 1 (2 000 цилиндр) = 0.005*(2000-1000)+5.2755 =

= 10.2755 мс.

Время обработки запроса 1 = 10.2755 – 0 = 10.2755 мс.

Момент завершения обработки запроса 2 (100 цилиндр) = 10.2755+0.005*(2000 –

- 100) +5.2755 = 25.051 мс.

Время обработки запроса 2 = 25.051 – 3 = 22.051 мс.

Момент завершения обработки запроса 3 (500 цилиндр) = 22.051+0.005*(500 –

- 100) +5.2755 = 32.3265 мс.

Время обработки запроса 3 = 32.3265 – 5 = 27.3265 мс.

Момент завершения обработки запроса 4 (300 цилиндр) = 32.3265+0.005*(500 –

- 300) +5.2755 = 38.602 мс.

Время обработки запроса 4 = 38.602 – 6 = 32.602 мс.

Момент завершения обработки запроса 5 (3 500 цилиндр) = 38.602+0.005*(3500 –

- 300) +5.2755 = 59.8775 мс.

Время обработки запроса 5 = 59.8775 – 10 = 49.8775 мс.


Среднее время обработки запроса = =

= 28.4265 мс.



Алгоритм «лифта».

Момент завершения обработки запроса 1 (2000 цилиндр) = 0.005*(2000-1000)+5.2755 =

= 10.2755 мс.

Время обработки запроса 1 = 10.2755 – 0 = 10.2755 мс.

К этому моменту поступили уже все запросы. Сначала блок головок двигается в сторону увеличения номера цилиндра.

Момент завершения обработки запроса 5 (3 500 цилиндр) = 10.2755+0.005*(3500-

-2000)+5.2755 = 23.051 мс.

Время обработки запроса 5 = 23.051 – 10 = 13.051 мс.

Теперь блок головок может двигаться в сторону уменьшения номера цилиндра.

Момент завершения обработки запроса 3 (500 цилиндр) = 23.051+0.005*(3500-

-500)+5.2755 = 43.3265 мс.

Время обработки запроса 3 = 43.3265 – 5 = 38.3265 мс.

Момент завершения обработки запроса 4 (300 цилиндр) = 43.3265 +0.005*(500-

-300)+5.2755 = 49.602 мс.

Время обработки запроса 4 = 49.602 – 6 = 43.602 мс.

Момент завершения обработки запроса 2 (100 цилиндр) = 49.602 +0.005*(300-

-100)+5.2755 = 55.8775 мс.

Время обработки запроса 2 = 55.8775 – 3 = 52.8775 мс.

Среднее время обработки запроса = =

= 31.6265 мс.


Задача 3.
а) По условию блок состоит из 16 секторов.

Размер 1 блока = байт.

Количество кортежей в одном блоке = кортеж.

Здесь [..] ( ) – операция округления в меньшую (большую) сторону.

Количество блоков для хранения отношения (B) = блоков.

Пусть M – количество буферов оперативной памяти, которые выделяются для проведения сортировки отношения.

Количество списков, сформированных на фазе 1 алгоритма сортировки = .

На фазе 2 алгоритма сортировки главный принцип – количество списков фазы 1 должно быть не больше, чем число буферов оперативной памяти – 1 (буфер вывода), т.е.



. Решая это неравенство, получим, что минимальное число буферов оперативной памяти для проведения сортировки отношения с помощью алгоритма двухфазной сортировки слиянием M=314 буферов.

Размер оперативной памяти = 314*Размер блока =314*4096 = 1 286 144 байт = 1 256 Кб.

б) На фазе 1 алгоритма будет создано списков (312 списков длиной по 314 блоков, 1 список длиной 72 блока).

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

Среднее время получения блока данных = 1+0.005*(4503/3) +4.1665+0.109 =

= 12.7805 мс.



Количество операций ввода/вывода = 4*В = 4*98 040 =392 160 операций ввода/вывода.

Время выполнения алгоритма = 392 160*12.7805 = 5 012 000.88 мс = 5 012 с = 83.5 мин.


izumzum.ru