Файл: Новосибирский государственный технический университет факультет автоматики и вычислительной техники кафедра вычислительной техники.docx

• 
  Линейная дисциплина обслуживания FIFO (First In – First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь первой.
  
• 
  Линейная дисциплина обслуживания LIFO (Last In – First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь последней.
  
• 
  Линейная дисциплина обслуживания RAND (Randomize). Случайный выбор заявки из очереди.
  
• 
  Циклическая дисциплина обслуживания RR (Round Rotation). Отличается от FIFO лишь временем обслуживания. Каждая заявка получает определённый квант времени (одинаковый для всех) .
  
• 
  Дисциплина обслуживания с фиксированным приоритетом SJF (Short Job First). Из очереди заявок на обслуживание выбирается заявка с минимальным временем обслуживания.
  
• 
  Дисциплина обслуживания с фиксированным приоритетом PRT (PRioriTy). Из очереди заявок на обслуживание выбирается заявка с максимальным приоритетом.
  

В настоящей работе рассматриваются 2 дисциплины обслуживания:

• 
  линейная дисциплина обслуживания FIFO (First In – First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь первой.
  
• 
  дисциплина обслуживания с фиксированным приоритетом SJF (Short Job First). Из очереди заявок на обслуживание выбирается заявка с минимальным временем обслуживания.
  

2. 
   Раздел 1
   

2.1. Задание.

Вычислительная система располагает оперативной памятью (ОП) V и внешним обьемом памяти Н (НМД). ОП память выделяется переме­щаемым разделами, которые исключают влияние фрагментации. Реали­зуется режим мультипрограммирования: если одновременно выполня­ется несколько задач, то процессорное время распределяется между ними равномерно. В систему поступает поток из М заданий, очеред­ное задание поступает через время t_i, для простоты каждое задание состоит из одной задачи и требует обьем ОП - v_i, обьем внешней памяти h_i, процессорное время. Каждое задание использует свою внешнюю память только для ввода данных в течение времени q*h_i , после чего начинается счет. Однако закрепленные за каждым зада­нием носители освобождаются только после завершения задания. Предположим, возможно параллельное использование внешней памяти заданиями без задержки друг друга. Если бы задания выполнялись по одному, то на каждое задание было бы затрачено время Т_i = q*h_i + t_i. Вновь поступившие задания помещаются в очередь. Для выбора заданий из очереди на выполнение используются два алгоритма:

---

1. 
   среди заданий в очереди, для которых достаточно свободных ре­сурсов, выбирается задание, поступившее первым (правило FIFO);
   
2. 
   среди заданий в очереди, для которых достаточно свободных ре­сурсов, выбирается задание с наименьшим t_i(правило SJF).
   

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

2.2. Исходные данные

Средневзвешенное время обращения:



где,

- время завершения задания,

- время поступления задания в систему,

M - количество заданий в потоке, который поступает в систему,

— время, потраченное на ввод и работу задания,

количество ОП, необходимое задаче,

количество ВП, необходимое задаче,

,

— время загрузки задания в систему,

— процессорное время, приходящееся на каждую задачу, с учётом коэффициента мультипрограммирования,

— время, которое задание провело на процессоре.

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

X_i = [7 * X_i-1 + 417] mod 1000;

K_i

---

= [X_i / 7] mod 10, i=1M, Xo = N, где

[c] - целая часть числа с,

y mod z - остаток от деления y на z,

Значение используемых параметров: V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) t_i=k_i .

Таблица 1. Набор задач для нормировки вариантов.

K	0	1	2	3	4	5	6	7	8	9
v	6	3	2	4	3	5	7	9	4	1
h	2	4	3	1	2	0	4	1	6	3
τ	60	90	20	10	60	30	70	30	40	20

Таблица последовательностей.
Используя индивидуальный расстановочный код: X0=N=819, были рассчитаны K_i номера

задач:

X0=N=819

X1=[7*819+417] mod 1000=150

K1=[150/7] mod 10=1

X2=[7*150+417] mod 1000=467

K2=[467/7] mod 10=7

X3=[7*467+417] mod 1000=686

K3=[686/7] mod 10=8

X4=[7*686+417] mod 1000=473

K4=[473/7] mod 10=8

X5=[7*473+417] mod 1000=728

K5=[728/7] mod 10=4

X6=[7*728+417] mod 1000=513

K6=[513/7] mod 10=3

X7=[7*513+417] mod 1000=8

K7=[8/7] mod 10=1

X8=[7*8+417] mod 1000=473

K8=[473/7] mod 10=8

X9=[7*473+417] mod 1000=728

K9=[728/7] mod 10=4

X10=[7*728+417] mod 1000=513

K10=[513/7] mod 10=3
Произведем расчёт .Для этого воспользуемся формулой где, -объём внешней памяти и q=5.

---

На основе полученных результатов и таблицы 1 (Набор задач для нормировки вариантов) составим таблицу 2.
Таблица 2. Характеристики заданий.

№	Xi	Ki	vi	hi	τ i	ti	tзагрузки	tпоступ.
1	150	1	3	4	90	1	20	1
2	467	7	9	1	30	7	5	8
3	686	8	4	6	40	8	30	16
4	473	8	4	6	40	8	30	24
5	728	4	3	2	60	4	10	28
6	513	3	4	1	10	3	5	31
7	8	1	3	4	90	1	20	32
8	473	8	4	6	40	8	30	40
9	728	4	3	2	60	4	10	44
10	513	3	4	1	10	3	5	47

---

---