В компьютерной системе необходимо выполнить некоторое количество вычислительных процессов, которые могут выполняться параллельно или последовательно. Для запуска некоторых процессов необходимы данные, которые получаются как результаты выполнения одного или двух других процессов — поставщиков данных. Если зависимый процесс получает данные от одного или нескольких других процессов (поставщиков данных), то выполнение зависимого процесса не может начаться раньше завершения всех процессов-поставщиков. Количество одновременно выполняемых процессов может быть любым. Длительность процесса не зависит от других параллельно выполняемых процессов.
В таблице представлены идентификатор (ID) каждого процесса, его длительность, для зависимых процессов — ID поставщиков данных. Для независимых процессов в качестве ID поставщиков данных
Выполните задания, используя данные из файла ниже:
Отсортируем данные в таблице так, чтобы все независимые процессы оказались в начале таблицы и любой процесс был расположен после всех процессов, от которых он зависит. Также в таблицу добавим столбец «Время окончания процесса» и запишем туда длительности независимых процессов.
| A | B | C | D | |
|---|---|---|---|---|
| 1 | ID | Время выполнения | ID | Время окончания процесса |
| 2 | 1 | 97 | 0 | 97 |
| 3 | 2 | 149 | 0 | 149 |
| 4 | 3 | 44 | 1;2 | |
| 5 | 4 | 80 | 3 | |
| 6 | 5 | 26 | 3 | |
| 7 | 6 | 47 | 5 | |
| 8 | 7 | 74 | 4;6 | |
| 9 | 8 | 82 | 0 | 82 |
| 10 | 9 | 137 | 0 | 137 |
| 11 | 10 | 90 | 8;9 | |
| 12 | 11 | 48 | 10 | |
| 13 | 12 | 84 | 10 | |
| 14 | 13 | 17 | 11 |
Далее рассчитаем время выполнения оставшихся процессов:
f(3) = 44 + max(f(1), f(2)) = 44 + 149 = 193;
f(4) = 80 + f(3) = 80 + 193 = 273;
f(5) = 26 + f(3) = 26 + 193 = 219;
f(6) = 47 + f(5) = 47 + 219 = 266;
f(7) = 74 + max(f(4), f(6)) = 74 + 273 = 347;
f(10) = 90 + max(f(8), f(9)) = 90 + 137 = 227;
f(11) = 48 + f(10) = 48 + 227 = 275;
f(12) = 84 + f(10) = 84 + 227 = 311;
f(13) = 17 + f(11) = 17 + 275 = 292.
| A | B | C | D | |
|---|---|---|---|---|
| 1 | ID | Время выполнения процесса B (мс) | ID | Время окончания процесса |
| 2 | 1 | 97 | 0 | 97 |
| 3 | 2 | 149 | 0 | 149 |
| 4 | 3 | 44 | 1;2 | 193 |
| 5 | 4 | 80 | 3 | 273 |
| 6 | 5 | 26 | 3 | 219 |
| 7 | 6 | 47 | 5 | 266 |
| 8 | 7 | 74 | 4;6 | 347 |
| 9 | 8 | 82 | 0 | 82 |
| 10 | 9 | 137 | 0 | 137 |
| 11 | 10 | 90 | 8;9 | 227 |
| 12 | 11 | 48 | 10 | 275 |
| 13 | 12 | 84 | 10 | 311 |
| 14 | 13 | 17 | 11 | 292 |
Построим диаграмму выполнения каждого процесса.
Заметим, что процессы 1,2, 8 и 9 можно начинать с любого времени. Максимальный отрезок, в течение которого возможно одновременное выполнение четырёх процессов, получиться, если сдвинуть начала процесса 8.
Построим диаграмму выполнения каждого процесса и рассмотрим когда могут выполняться одновременно 4 процесса.
Максимальная длительность отрезка времени (в мс), в течение которого возможно одновременное выполнение четырёх процессов, при условии, что в эту четвёрку не входит процесс с ID = 2, начинается с 194 мс и проходит до 266 мс. Всего:
266 − 194 + 1 = 73 мс.
Ответ: 73.