Условие:
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс В зависит от процесса А, если для выполнения процесса В необходимы результаты выполнения процесса A. В этом случае процессы А и В могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы - время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
| ID процесса B | Время выполнения процесса В (MC) | ID процесса (ов) A |
|---|---|---|
| 101 | 14 | 0 |
| 102 | 3 | 0 |
| 103 | 1 | 101;102 |
| 104 | 11 | 102 |
| 105 | 13 | 103 |
| 106 | 5 | 103 |
| 107 | 3 | 106 |
| 108 | 1 | 105;107 |
| 109 | 2 | 108 |
| 110 | 8 | 0 |
| 111 | 16 | 110 |
| 112 | 8 | 110 |
| 113 | 14 | 112 |
Решение:
Для решения задачи о максимальной продолжительности отрезка времени, в течение которого возможно одновременное выполнение максимальн...
Сначала мы создадим граф зависимостей, где каждый процесс будет представлять собой узел, а зависимости между процессами — направленные ребра. - Процессы 101 и 102 независимы (время 14 и 3 мс соответственно). - Процесс 103 зависит от 101 и 102 (время 1 мс). - Процесс 104 зависит от 102 (время 11 мс). - Процесс 105 зависит от 103 (время 13 мс). - Процесс 106 зависит от 103 (время 5 мс). - Процесс 107 зависит от 106 (время 3 мс). - Процесс 108 зависит от 105 и 107 (время 1 мс). - Процесс 109 зависит от 108 (время 2 мс). - Процесс 110 независим (время 8 мс). - Процесс 111 зависит от 110 (время 16 мс). - Процесс 112 зависит от 110 (время 8 мс). - Процесс 113 зависит от 112 (время 14 мс). Теперь мы можем определить время выполнения каждого процесса, учитывая их зависимости. 1. Процессы 101 и 102 могут выполняться одновременно: - Время 0-14 мс: процесс 101 - Время 0-3 мс: процесс 102 2. Процесс 103 может начаться только после завершения 101 и 102: - Время 14-15 мс: процесс 103 (зависит от 101 и 102) 3. Процесс 104 может начаться после завершения 102: - Время 3-14 мс: процесс 104 (зависит от 102) 4. Процессы 105 и 106 могут начаться только после завершения 103: - Время 15-16 мс: процесс 105 - Время 15-16 мс: процесс 106 5. Процесс 107 зависит от 106: - Время 16-19 мс: процесс 107 6. Процесс 108 зависит от 105 и 107: - Время 19-20 мс: процесс 108 7. Процесс 109 зависит от 108: - Время 20-22 мс: процесс 109 8. Процесс 110 независим: - Время 0-8 мс: процесс 110 9. Процессы 111 и 112 зависят от 110: - Время 8-24 мс: процесс 111 - Время 8-16 мс: процесс 112 10. Процесс 113 зависит от 112: - Время 16-30 мс: процесс 113 Теперь мы можем определить, в какие моменты времени выполняется максимальное количество процессов: - Время 0-3 мс: 2 процесса (101, 102) - Время 3-8 мс: 2 процесса (104, 102) - Время 8-14 мс: 3 процесса (110, 111, 112) - Время 14-15 мс: 3 процесса (101, 102, 103) - Время 15-19 мс: 4 процесса (105, 106, 101, 102) - Время 19-20 мс: 3 процесса (108, 110, 111) - Время 20-22 мс: 2 процесса (109, 110) - Время 22-30 мс: 2 процесса (113, 110) Максимальное количество одновременно выполняемых процессов равно 4, и это происходит в интервале времени с 15 до 19 мс. Таким образом, максимальная продолжительность отрезка времени, в течение которого возможно одновременное выполнение максимального количества процессов, составляет: