Курс_ИОиТПР_Комолов_АВ (1006469), страница 5

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

Текст из файла (страница 5)

отдельных процессоров

(i=1-L)

l TL

.

. Tc=max Tl

. 1 l L

.

L

Tc

Эта задача может быть решена методом полного перебора вариантов

n

загрузки системы  2

Алгоритм решения этой задачи:

Среднее время загрузки процессов: Тср= (1/L)*(ΣТl)

ТсТср

min ТсТср  Идеальной схемой загрузки системы является любая схема, позволяющая достичь: min Тс=Тср ,  наша задача сводится, чтобы максимально равномерно загрузить процессы, т.е. это задача выравнивания загрузки всех процессов

Чтобы это доказать, надо рассмотреть сумму отклонений Т от Тср

((Тl-Тср)), которая будет = 0:

l

Σ (Тl-Тср)= Σ Тl - L Tср = Σ Тl -Σ Тl = 0

l l l l

Тогда алгоритм будет следующий:

1) вытянуть все работы в одну линию по возрастанию их длительности

r

I II N -1 N

Тср

τv

И рассмотреть Тср (отсечь). В зависимости от того, что больше I или II, мы отправим на 1-й процесс, либо r самых коротких работ, либо (r-1) работу.

τv – длительность перенумерованных работ (v = 1-N)

τr - I+II

r r

- Тср+Στv = II; Тср-Στv = I;

v=1 v=1

Если I>II, то r-работ на 1-й процессор.

2) Загрузка 2-го процессора по схеме шага 1

Предварительный план загрузки ПΙ системы получается в результате (L-1) шагов.

Характеристики ПI: max I

- время занятости наиболее загруженного процессора max Tl=Tl = Tc

1 l  L

min

- время занятости наименее загруженного процессора min Tl= Tl

1 l  L

L) наиболее и наименее загруженные процессоры

min

Tl

max

Tl

Тср

Попытаемся улучшить эти характеристики , путем перераспределения работ

max I I

между этими 2-мя процессорами (это надо, т.к. Tl = Tc , а Tc надо уменьшить) по предыдущей схеме  ПII. ПII всегда лучше ПI с т.зр. показателя Тс

Далее можно с ПII либо перейти к ПIII, либо оценка точности ПII.

δ =(maxTl-Tср)/Тср

Если δ - удовлетворительная, то не надо искать ПIII.

В результате мы получаем приемлемый по точности план загрузки

0

процессора П

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

Пример задачи о мультипроцессоре. Требуется построить оптимальный план загрузки системы (minТс)

L=4

N=7

Решение:

Тср=423; НОД τj = 3

1. Рассматриваем суммы величин τ:

τ 1+τ2=114<Тср 6

τ1+τ2+τ3=174< Тср Tср -Στj =24

………………………. J=1

 на 1-й процессор идут

Т1=339 первые шесть работ

1. списка

Στj=339<Tср 7

J=1 Στj-Tср=66

J=1

7

Στj=489>Tср

J=1

1. Повторяем предыдущий шаг для оставшихся работ. На второй процессор идут работы 1-7 Т2=384 и т.д. На 3-й процессор идут работы 11-14 Т3=474, на 4-й процессор идут работы 15-17 Т4=435

2. П1: (предварительный план загрузки)

54,60,60,72,75,78 90,90,96,108 111,120,120,123 135,150,150

l=1 Т1=399 l=2 Т2=384 l=3 Т3=474 l= 4 Т4=435

1. Для плана оцениваем

max Тl=Т3=474 min Тl = T2=384

l l

Т3-Т2=90

Встает задача уравнения загрузки 3-го и 2-го процессора

2

3 45

90

Если будет: 90,90,96,108 111,120,120,123

L=2 Т2=384 l=3 T3=474 ,

То загрузка идеально выравнивается

1. П2:

54,60,60,72,75,78 90,108,111,120 90,96,120,123 135,150,150

l=1 T1=399 l=2 T2=429 l=3 T3=429 l=4 T4=435

max Тl=Т4=435 min Тl = T2=399 T4-T1=36

δ = (435-423)/423=12/423 3%

1. Если работа 60,72, с 1-го передать в обмен на 150 с 4-го, то будет новый план.

П3:

54,60,75,78,150 90,108,111,120 90,96,120,123 60,72,135,150

l=1 T1=417 l=2 T2=429 l=3 T3=429 T4=417

max Tl=T2=T3 = 429 min Tl=T1, T4=417

min-max=12

δ=6/423=1.5%

VII) Τl: 417 429

Т.к.ΗΟДτj, то ряд: 417,420,423,426,429 содержит точный план.

Это позволяет утверждать: для того, чтобы найти точное решение задачи достаточно решить уравнение вида:

Στjyj=B,

В - любое из чисел ряда

Yj – принимает значение 0/1.

Для этого можно рассмотреть таблицу вида:

m-min и max кол-во отрезков τj, которое может образовывать В.

Все, что попадёт в строку №3, будет оптимальным решением. Если это строка будет пустой, то значит оптимальной будет соседняя строка.

Чтобы посмотреть эту таблицу для нашей задачи, надо рассмотреть 20 тыс. вариантов, т.е. мы в области резко растущей трудоёмкости.

Если бы мы это сделали, то получили бы решение:

( 60,72,90,90,111)

(120,120,108,75)

(150,54,123,96) max Тl = Тср = 423

(150,78,135,60)

( 60,75,78,90,120)

(150,54,111,108) max Тl =Тср = 423

(135,72,120,96)

(150,60,123,90)

Есть еще несколько идеальных решений.

Планирование работ с возрастающей длительностью.

Истощение инструментального ресурса приводит к возрастанию длительности работы.

Постановка задачи: Дана система однопроцессорная, с помощью которой должна быть выполнены N работ, которые характеризуются своими

номинальными длительностями (τj; j=1-N), т.е. если бы эта работа попала на первое место в очереди, то она была бы выполнена за это время τj

Если некоторая работа начинается в момент времени t>0, то её номинальная длительность увеличивается , то её номинальная длительность увеличивает

(t)

ся на некоторую величину τj

0 0 (t)

τj τm τm t

0 t>0 1 m  N

Требуется найти такой порядок выполнения работ, который обеспечил Тсmin

Предположим:

1. Закономерности возрастания длительности для всех работ одинаковы

0

(τj)

2) этот рост линейно зависит от t

τj

k

t

Решение:

Рассмотрим на оси времени 2 соседние по номерам работы: τv-1 τv

t v-1 tv-1 tv t

0 (tv-1)

О тсюда следует: tv=tv-1+τv+τv, v=2,3,…,N

Э то разностное уравнение можно решить непосредственной подстановкой tv, для v=2,3,…,N.

0 0

 t1=τ1, tv=τv+(1+k)tv-1 или

v-1 s 0

t v=Σ(1+k)τv-s и

s=0

n-1 s o

Tc=Σ(1+k)τn-s

S=0 s

Чем дальше работа от конца, тем больше весовой коэффициент (1+к)

 оптимальный порядок: на первое место попадут самые короткие по номиналу работы.

Выводы:

1. Теория расписаний предлагает разные подходы к исследованию проблем организационного характера.

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

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

10

Характеристики

Список файлов лекций