Задание №22: Многопроцессорные системы и параллельные процессы
Основные типы и прототипы задания №22:
Параллельные и зависимые процессы
Критический путь в диаграмме Ганта
Многопоточное выполнение
Условие задания
(Г. Шапошников) В файле 22-96.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Типовой пример организации данных в файле:
Будем считать, что процессы выполняются одновременно, в случае если есть хотя бы один момент времени, когда оба процесса выполнялись. Найдите количество процессов, которые могли выполняться одновременно с процессом номер 13 (не обязательно все одновременно).
Пояснение к примеру: допустим нам нужно определить количество процессов, которые могли выполняться одновременно с процессом 2. Процессы 1 и 3 не подходят, т.к. процесс 2 можно запустить только после выполнения процесса 1, а процесс 3 только после выполнения процесса 2. Процесс 4 подходит в случае, если процесс 1 был запущен в самом начале, сразу после него был запущен процесс 2 (через 4 мс после начала работы программы) и процесс 4 также был запущен сразу после начала работы программы (тогда с 4 по 7 мс процессы 2 и 4 выполнялись совместно).
Процесс 5 подходит, в случае, если запустить процесс 4 в самом начале, и сразу после него (через 7 мс после начала работы программы) запустить процесс 5. Процесс 1 же можно запустить через 3 мс после начала работы программы (тогда закончится он к 7 мс). И сразу после него запустить процесс 2. Тогда с 7 мс по 10 мс процесс 2 и 5 будут выполняться совместно.
Таким образом, одновременно с процессом 2 могут выполняться процессы 4 и 5. Ответ: 2.
Типовой пример организации данных в файле:
Будем считать, что процессы выполняются одновременно, в случае если есть хотя бы один момент времени, когда оба процесса выполнялись. Найдите количество процессов, которые могли выполняться одновременно с процессом номер 13 (не обязательно все одновременно). Пояснение к примеру: допустим нам нужно определить количество процессов, которые могли выполняться одновременно с процессом 2. Процессы 1 и 3 не подходят, т.к. процесс 2 можно запустить только после выполнения процесса 1, а процесс 3 только после выполнения процесса 2. Процесс 4 подходит в случае, если процесс 1 был запущен в самом начале, сразу после него был запущен процесс 2 (через 4 мс после начала работы программы) и процесс 4 также был запущен сразу после начала работы программы (тогда с 4 по 7 мс процессы 2 и 4 выполнялись совместно).
Процесс 5 подходит, в случае, если запустить процесс 4 в самом начале, и сразу после него (через 7 мс после начала работы программы) запустить процесс 5. Процесс 1 же можно запустить через 3 мс после начала работы программы (тогда закончится он к 7 мс). И сразу после него запустить процесс 2. Тогда с 7 мс по 10 мс процесс 2 и 5 будут выполняться совместно.
Таким образом, одновременно с процессом 2 могут выполняться процессы 4 и 5. Ответ: 2.
Ответ:
5