В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов — поставщиков данных. Все независимые процессы (не имеющие поставщиков данных) запускаются в начальный момент времени. Если зависимый процесс получает данные от одного или нескольких других процессов (поставщиков данных), то выполнение зависимого процесса начинается сразу же после завершения последнего из процессов-поставщиков. Количество одновременно выполняемых процессов может быть любым, длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице представлены идентификатор (ID) каждого процесса, его длительность и ID поставщиков данных для зависимых процессов.
Определите суммарную длительность всех промежутков времени, в течение которых выполнялось ровно
Выполните задания, используя данные из файла ниже:
Отсортируем данные в таблице так, чтобы все независимые процессы оказались в начале таблицы и любой процесс был расположен после всех процессов, от которых он зависит. Также в таблицу добавим столбец «Время окончания процесса» и запишем туда длительности независимых процессов.
| A | B | C | D | |
|---|---|---|---|---|
| 1 | ID | Время выполнения | ID | Время окончания процесса |
| 2 | 1 | 4 | 0 | 4 |
| 3 | 2 | 2 | 0 | 2 |
| 4 | 9 | 7 | 0 | 7 |
| 5 | 10 | 9 | 0 | 9 |
| 6 | 4 | 7 | 3 | |
| 7 | 5 | 6 | 3 | |
| 8 | 6 | 2 | 5 | |
| 9 | 8 | 2 | 6 | |
| 10 | 11 | 6 | 9 | |
| 11 | 12 | 6 | 10 | |
| 12 | 3 | 5 | 1;2 | |
| 13 | 7 | 5 | 4;6 |
Далее рассчитаем время выполнения оставшихся процессов:
f(4) = 7 + f(3) = 7 + 9 = 16;
f(5) = 6 + f(3) = 6 + 9 = 15;
f(6) = 2 + f(5) = 2 + 15 = 17;
f(8) = 2 + f(6) = 2 + 17 = 19;
f(11) = 6 + f(9) = 6 + 7 = 13;
f(12) = 6 + f(10) = 6 + 9 = 15;
f(3) = 5 + max(f(1), f(2)) = 5 + 4 = 9;
f(7) = 5 + max(f(4), f(6)) = 5 + 17 = 22.
| A | B | C | D | |
|---|---|---|---|---|
| 1 | ID | Время выполнения | ID | Время окончания процесса |
| 2 | 1 | 4 | 0 | 4 |
| 3 | 2 | 2 | 0 | 2 |
| 4 | 9 | 7 | 0 | 7 |
| 5 | 10 | 9 | 0 | 9 |
| 6 | 4 | 7 | 3 | 16 |
| 7 | 5 | 6 | 3 | 15 |
| 8 | 6 | 2 | 5 | 17 |
| 9 | 8 | 2 | 6 | 19 |
| 10 | 11 | 6 | 9 | 13 |
| 11 | 12 | 6 | 10 | 15 |
| 12 | 3 | 5 | 1;2 | 9 |
| 13 | 7 | 5 | 4;6 | 22 |
Построим диаграмму выполнения каждого процесса и рассмотрим когда могут выполняться одновременно
Максимальная продолжительность отрезка времени
Ответ: 6.