Вычисление максимальной и минимальной трудоёмкости

⇐ ПредыдущаяСтр 2 из 3Следующая ⇒

Минимально и максимально возможное значения трудоемкости на момент окончания выполнения оператора обозначим соответственно через и . Для начальной вершины имеем и . Тогда для остальных вершин с номерами

, (2.3.1)

, (2.3.2)

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

Для конечной вершины графа вычисляются значения

, (2.3.3)

, (2.3.4)

характеризующие минимальную и максимальную трудоемкость алгоритма.

Расчёты выглядят следующим образом:

min = k₁+k₂+k₈+k₉+k₁₀ =

max = 10(k₁+k₂+5(k₅+k₆+k₇)+k₉+k₁₀) =

Определение рабочей нагрузки

Описание рабочей нагрузки можно выразить ввиде таблицы:

M	1 (13)	2 (№8)	3 (16)		4(№12)		5 (№3)
	2.4	1.6	0.8	1.4		0.8
Пр.	оп	оп	бп	ап		бп
Q	3000	8000	6000	3000		3000
Q	20	20	30	15		20

Таб.2.4.1. Описание рабочей нагрузки.

Где:

M - Задачи, решаемые системой

- Интенсивность поступления задач

Q - Трудоёмкость задачи

Q - Количество обращений удалённых пользователей

Для полного описания рабочей нагрузки, необходимо определить:

1) Интенсивность поступления:

L = (2.4.1)

L =

2) Доля задач класса m в общей смеси:

p_m = l_m/L, (2.4.2)

p_{1 =}

p_{2 =}

p_{3 =}

p_{4 =}

p₅=

3) Трудоемкость процессорных операций:

Q = (2.4.3)

Q =

4) Среднее число обращений к файлу F_k:

D_k = (2.4.4)

Номер задачи	Трудоёмкость процессорных операций, млн. оп.	Среднее число обращений к файлам										Количество обращений удаленных пользователей (ВСТ ЛВС)
Номер задачи	Трудоёмкость процессорных операций, млн. оп.	FI	F2	F3	F4	F5	F6	F7	F8	F9	F10
13	3000	-	50	50	-	-	80	-	100	-	-	20
8	8000	-	120	60	-	80	-	-	30	-	180	20
16	6000	-	150	200	60	40	-	50	-	120	-	30
12	3000	15	40	-	-	80	-	20	-	100	-	15
3	3000	-	-	100	-	150	-	-	-	-	40	20

Таб.2.4.2. Среднее число обращений к файлу F_k

5) Общее число обращений к файлам:

D = (2.4.5)

Для задачи №13 D = 280

Для задачи №8 D = 308

Для задачи №16 D = 620

Для задачи №12 D = 255

Для задачи №3 D = 290

6) Средняя длина блока записей файлов:

l _{ср бл} = ( )/D (2.4.6)

Параметры файлов	F1	F2	F3	F4	F5	F6	F7	F8	F9	F1O
Длина файла, Мбайт	370	250	360	280	320	375	280	350	140	350
Средняя длина блока записей, Кбайт	40	30	75	40	40	50	40	75	25	20

7) Среднее число обращений этих источников к задаче:

Q = (2.4.7)

Q ,в данном случае, определено для каждой задачи и указано в таблице 2.4.2.

8) Среднее количество прерываний центрального процессора определяется с учетом того, что любая операция обращения к файлу F_k или к удаленному пользователю вызывает прерывание центрального процессора:

H_ЦПр= D + Q + 1 (2.4.8)

Для задачи №13 H_ЦПр= 280+20+1= 301

Для задачи №8 H_ЦПр= 308+20+1= 329

Для задачи №16 H_ЦПр=620+30+1= 351

Для задачи №12 H_ЦПр=255+15+1= 271

Для задачи №3 H_ЦПр=290+20+1= 311

9) Средняя трудоемкость (количество операций) непрерывного счета на процессоре:

Q₀ = Q / H_ЦПр. (2.4.9)

Для задачи №13Q₀ = 3000/301 = 9.97

Для задачи №8Q₀ = 8000/329 = 24.32

Для задачи №16Q₀ = 6000/351 = 17.09

Для задачи №12Q₀ = 3000/271 = 11.07

Для задачи №3Q₀ = 3000/311 = 9.65

Расчёт быстродействия процессора

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

28 с

По этому, для вычисления минимально необходимого быстродействия процессора, воспользуемся формулой:

(2.5.1)

Где:

Подставив имеющиеся данные получим:

B ˃16490, B = 17000

Теперь найдём приоритетность каждой задачи (в секундах) по формуле:

(2.5.2)

_{1 = 0.18}

_{2 = 0.47}

_{3 = 0.35}

4_{= 0.18}

_{5 = 0.18}

Исходя из имеющихся данных, можем вычислить (нагрузку) по формуле:

(2.5.3)

Таким образом:

𝜚₁= 0.18 · 2.4 = 0.432

𝜚₂= 0.47 · 1.6 = 0.752

𝜚₃= 0.35 · 0.8 = 0.28

𝜚₄= 0.18 · 1.4 = 0.252

𝜚₅= 0.18 · 0.8 = 0.144

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

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

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

(2.5.4)

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