7.3: Додавання алгоритму

Last updated

Oct 27, 2022
Save as PDF
- 7.2: Початок роботи
- 7.4: Вибір списку пріоритетів

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

До цих пір ми створювали графіки шляхом вгадування і перевірки, який працює досить добре для невеликих графіків, але не буде добре працювати з десятками або сотнями завдань. Щоб створити більш процедурний підхід, ми могли б почати з якось створення списку пріоритетів. Після того, як у нас є список пріоритетів, ми можемо почати планування, використовуючи цей список та алгоритм обробки списку.

Список пріоритетів

Список пріоритетів - це перелік завдань, що даються в тому порядку, в якому ми хочемо, щоб вони були виконані.

Алгоритм обробки списків перетворює список пріоритетів у розклад.

Алгоритм обробки списків

На диграфі або списку пріоритетів обведіть всі завдання, які готові, тобто всі обов'язкові завдання виконані.
Призначте кожному доступному процесору, по порядку, перше готове завдання. Позначте завдання як виконується, можливо, проставивши один рядок через завдання.
Рухайтеся вперед у часі, поки завдання не буде виконано. Позначте завдання як виконане, можливо, перекреслюючи завдання. Якщо якісь нові завдання стануть готовими, позначте їх як такі.
Повторюйте до тих пір, поки всі завдання не будуть заплановані.

Приклад 2

Використовуючи наш диграф зверху, заплануйте його, використовуючи список пріоритетів нижче:

$\mathrm{T}_{1}, \mathrm{T}_{3}, \mathrm{T}_{4}, \mathrm{T}_{5}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}$

Рішення

Час 0: Позначте готові завдання

Список пріоритетів: $({\mathrm{T}_{1}}), (\mathrm{T}_{3}), (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}$

Перше завдання ми призначаємо, $\mathrm{T}_{1}$ на перший процесор $\mathrm{P}_{1}$ , а друге готове завдання $\mathrm{T}_{3}$ , на другий процесор. Роблячи ці завдання, ми відзначаємо ці завдання як виконувані:

Список пріоритетів: $\cancel{(\mathrm{T}_{1})}, \cancel{(\mathrm{T}_{3})}, (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}$

Заплануйте до тут:

$clipboard_e77fb190a3f596755cb0ed99767471a80.png$

Перестрибуємо до часу, коли чергове завдання завершиться, яке на час 2.

Час 2: Обидва процесори завершують свої завдання. Ми відзначаємо ці завдання як завершені. Коли завдання 1 завершено, Завдання 2 стає готовим:

Список пріоритетів: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}$

Призначаємо наступне готове завдання в списку, $\mathrm{T}_{4}$ до $\mathrm{P}_{1}$ , і $\mathrm{T}_{5}$ до $\mathrm{P}_{2}$ .

Список пріоритетів: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \cancel{(\mathrm{T}_{4})}, \cancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}$

$clipboard_ed931c39742cb3d6bfcc67592f093b557.png$

Час 3: Процесор 1 завершено $\mathrm{T}_{4}$ . Завершення не $\mathrm{T}_{4}$ робить жодних інших завдань готовими (зверніть увагу, що всі інші вимагають, $\mathrm{T}_{2}$ щоб вони були виконані першими).

Список пріоритетів: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \cancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}$

Так як наступні три завдання ще не готові, призначаємо наступне готове завдання, $\mathrm{T}_{2}$ щоб $\mathrm{P}_{1}$

Список пріоритетів: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \cancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}$

$clipboard_e5f8d7915ae037b71ff7e5fa3c51f66de.png$

Час 3.5: Процесор 1 завершено $\mathrm{T}_{2}$ . Завершити $\mathrm{T}_{2}$ причини $\mathrm{T}_{6}$ і $\mathrm{T}_{7}$ стати готовим. Доручаємо $\mathrm{T}_{6}$ до $\mathrm{P}_{1}$ .

Список пріоритетів: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \cancel{(\mathrm{T}_{6})}, (\mathrm{T}_{7}), \mathrm{T}_{8}, \xcancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}$

$clipboard_e5d65817f8fa5dc929322c44dbfb1f85a.png$

Час 4: Обидва процесори завершують свої завдання. Доопрацювання $\mathrm{T}_{5}$ $\mathrm{T}_{8}$ дозволяє стати готовим. Призначаємо $\mathrm{T}_{7}$ до $\mathrm{P}_{1}$ і $\mathrm{T}_{8}$ до $\mathrm{P}_{2}$ .

Список пріоритетів: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \xcancel{(\mathrm{T}_{6})}, \cancel{(\mathrm{T}_{7})}, \cancel{(\mathrm{T}_{8})}, \xcancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}$

$clipboard_e00d40539291882f1466b3b9ba4fc17fc.png$

Час 4.5: Обидва процесори завершують свої завдання. $\mathrm{T}_{9}$ стає готовим, і покладається на $\mathrm{P}_{1}$ . Немає готового завдання $\mathrm{P}_{2}$ для роботи, так що $\mathrm{P}_{2}$ холостий хід.

Список пріоритетів: $\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \xcancel{(\mathrm{T}_{6})}, \xcancel{(\mathrm{T}_{7})}, \xcancel{(\mathrm{T}_{8})}, \xcancel{(\mathrm{T}_{2})}, \cancel{(\mathrm{T}_{9})}$

$clipboard_e7bc0f4b15e2eb217727706f983d188af.png$

Коли останнє завдання виконано, ми маємо завершений графік, час закінчення 5,5 днів.

Спробуйте зараз 1

Використовуючи диграф нижче, створіть розклад, використовуючи список пріоритетів:

$\mathrm{T}_{1}, \mathrm{T}_{2}, \mathrm{T}_{3}, \mathrm{T}_{4}, \mathrm{T}_{5}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{9}$

$sc3.svg$

Відповідь

Час 0: Завдання 1, 4 та 7 готові. Призначити завдання 1 і 4

Час 9: Завдання 4 завершено. Готово тільки завдання 7; призначити завдання 7

Час 10: Завдання 1 завершено. Завдання 2 тепер готове. Призначити завдання 2

Час 17: Завдання 2 завершено. Нічого не готово. Процесор 1 холостий

Час 22: Завдання 7 виконано. Завдання 5 і 8 готові. Призначте завдання 5 і 8

Час 26: Завдання 8 виконано. Завдання 9 готове. Призначити завдання 9

Час 27: Завдання 5 виконано. Завдання 3 і 6 готові. Призначити завдання 3

Час 31: Завдання 3 виконано. Призначити завдання 6

Час 35: Все зроблено. Час закінчення - 35 для цього графіка.

$clipboard_eeee2de77e15748630b6197c99fed34fc.png$

Важливо відзначити, що сам алгоритм обробки списків не впливає на отриманий графік — графік повністю визначається списком пріоритетів, за яким слідує. Обробка списку, хоча це можна зробити вручну, може так само легко бути виконана комп'ютером. Цікавою частиною планування є те, як вибрати список пріоритетів, який створить найкращий графік.