Пример 1
В таблице приведены сведения о вычислительных процессах, которые могут выполняться параллельно. Процесс может начаться только после завершения всех процессов, от которых он зависит; 0 означает, что зависимостей нет.
Определите минимальное время (в мс), через которое завершится выполнение всех процессов, если количество одновременно выполняемых процессов не ограничено.
Показать решение и ответ
1. Для каждого процесса считаем момент окончания: самое позднее окончание его зависимостей плюс его собственное время.
2. Процесс 1: 0 + 4 = 4. Процесс 2: 0 + 3 = 3.
3. Процесс 3 ждёт 1: 4 + 5 = 9. Процесс 4 ждёт 1 и 2: max(4, 3) + 2 = 6.
4. Процесс 5 ждёт 3: 9 + 6 = 15. Процесс 6 ждёт 4: 6 + 4 = 10.
5. Процесс 7 ждёт 5 и 6: max(15, 10) + 3 = 18.
6. Все процессы закончатся через 18 мс.
В файле с экзамена процессов десятки — там то же самое делают формулой в таблице: окончание = МАКС(окончаний зависимостей) + время.
Ответ: 18
