© К. Поляков, 2022
Тема: Построение математических моделей для решения практических задач. Архитектура современных компьютеров. Многопроцессорные системы
Что проверяется:Умение анализировать алгоритм, содержащий ветвление и цикл
3.1.1. Программная и аппаратная организация компьютеров и компьютерных систем. Виды программного обеспечения.1.3.2. Оценивать скорость передачи и обработки информации.Что нужно знать:
-
процессы в современных компьютерах могут выполняться параллельно, если являются независимыми
-
выражение «процесс В зависит от процесса А» означает, что выполнение процесса В не может начаться раньше, чем выполнение процесса А
Пример задания:P-00 (демо-2022). В файле
22-0.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно. Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.Типовой пример организации данных в файле:
ID процесса B
|
Время выполнения процесса B (мс)
|
ID процесса(ов) A
|
1
|
4
|
0
|
2
|
3
|
0
|
3
|
1
|
1; 2
|
4
|
7
|
3
|
В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 – через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть, через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть, через 5 мс. Он длится 7 мс, так что минимальное время завершения всех процессов равно 5 + 7 = 12 мс.
Решение (электронные таблицы): -
таблица имеет вид:
ID процесса B
|
Время выполнения процесса B (мс)
|
ID процесса (ов) A
|
1
|
4
|
0
|
2
|
3
|
0
|
3
|
1
|
1; 2
|
4
|
7
|
3
|
5
|
6
|
3
|
6
|
3
|
5
|
7
|
1
|
4; 6
|
8
|
2
|
7
|
9
|
7
|
0
|
10
|
8
|
0
|
11
|
6
|
9
|
12
|
6
|
10
|
-
отсортируем данные в таблице так, чтобы:
– все независимые процессы оказались в начале таблицы– любой процесс был расположен ПОСЛЕ всех процессов, от которых он зависит
ID процесса B
|
Время выполнения процесса B (мс)
|
ID процесса (ов) A
|
1
|
4
|
0
|
2
|
3
|
0
|
9
|
7
|
0
|
10
|
8
|
0
|
3
|
1
|
1; 2
|
4
|
7
|
3
|
5
|
6
|
3
|
6
|
3
|
5
|
7
|
1
|
4; 6
|
8
|
2
|
7
|
11
|
6
|
9
|
12
|
6
|
10
|
-
добавляем еще один столбец: время окончания процесса; для всех независимых процессов записываем в соответствующие ячейки время окончания, равное длительности процесса:
ID процесса B
|
Время выполнения процесса B (мс)
|
ID процесса (ов) A
|
Время окончания T, мс
|
1
|
4
|
0
|
4
|
2
|
3
|
0
|
3
|
9
|
7
|
0
|
7
|
10
|
8
|
0
|
8
|
3
|
1
|
1; 2
|
|
4
|
7
|
3
|
|
5
|
6
|
3
|
|
6
|
3
|
5
|
|
7
|
1
|
4; 6
|
|
8
|
2
|
7
|
|
11
|
6
|
9
|
|
12
|
6
|
10
|
|
-
для остальных процессов определяем время окончания как сумму длительности этого процесса и максимального времени окончания процессов, от которых зависит данный процесс (здесь T(x) обозначает время окончания процесса с идентификатором x):
T(3) = 1 + max( T(1), T(2) ) = 1 + 4 = 5T(4) = 7 + T(3) = 7 + 5 = 12T(5) = 6 + T(3) = 6 + 5 = 11T(6) = 3 + T(5) = 3 + 11 = 14T(7) = 1 + max( T(4), T(6) ) = 1 + 14 = 15T(8) = 2 + T(7) = 2 + 15 = 17T(11) = 6 + T(9) = 6 + 7 = 13T(12) = 6 + T(10) = 6 + 8 = 14
ID процесса B
|
Время выполнения процесса B (мс)
|
ID процесса (ов) A
|
Время окончания T, мс
|
1
|
4
|
0
|
4
|
2
|
3
|
0
|
3
|
9
|
7
|
0
|
7
|
10
|
8
|
0
|
8
|
3
|
1
|
1; 2
|
5
|
4
|
7
|
3
|
12
|
5
|
6
|
3
|
11
|
6
|
3
|
5
|
14
|
7
|
1
|
4; 6
|
15
|
8
|
2
|
7
|
17
|
11
|
6
|
9
|
13
|
12
|
6
|
10
|
14
|
-
время завершения совокупности всех процессов равно времени завершения последнего из них, поэтому нужно выбрать максимальное значение в последнем столбце
-
Ответ: 17.
Решение (электронные таблицы, функция ВПР, Информатик БУ): -
Для начала отсортируем таблицу по столбцу C (ID процесса (ов) A). Это нужно для того, чтобы отдельно рассмотреть независимые процессы (те, у которых в столбце C находится значение 0); вместо этого можно было бы использовать функцию ЕСЛИ, но в этом случае формула была бы немного сложнее;
-
Теперь необходимо расцепить процессы в ячейках столбца C, в которых находится более одного процесса; в данном примере это можно было бы сделать вручную, но ручной способ не подойдет для больших таблиц. Для этого выделяем нужные ячейки столбца C, переходим в меню «Данные», и нажимаем кнопку «Текст по столбцам»:
В появившемся окне выбираем формат данных «с разделителями», нажимаем кнопку «Далее», и указываем символы, которые разделяют процессы в ячейках. В нашем случае это точка с запятой и пробел. Нажимаем кнопку «Готово».После этого один из процессов останется в столбце C, а второй отправится в столбец D (если процессов больше, чем 2, номера оставшихся размещаются в столбцах E, F и далее).
-
Посчитаем в столбце E полное время выполнения каждого процесса (время самого процесса + время процессов, связанных с ним). Сначала отдельно рассмотрим независимые процессы. Для этого в ячейке E2 пишем формулу =B2, и копируем её для всех независимых процессов.
-
Теперь рассмотрим процессы B, которые зависят только от одного процесса. Для этого возьмем время выполнения самого процесса B, и прибавим к нему полное время выполнения процесса A (ID процесса A находится в столбце C, а полное время выполнения – в столбце E). Для поиска времени выполнения процесса A воспользуемся функцией ВПР. В ячейку E6 запишем формулу:
=B6+ВПР(C6;A:E;5;0)и скопируем её для всех процессов B, у которых указан только один процесс A.
-
Далее рассмотрим процессы B, которые зависят уже от двух процессов. Так как процессы в столбцах C и D могут выполняться параллельно, будем брать максимальное значение среди времени их выполнения, и прибавлять к этому значению время выполнения самого процесса B. Для этого в ячейку E12 запишем формулу:
=B12+МАКС(ВПР(C12;A:E;5;0);ВПР(D12;A:E;5;0))и копируем её для всех процессов B, у которых указано два процесса A.
-
Так мы получили столбец E, в ячейках которого указано полное время выполнения каждого процесса B. Так как процессы могут выполняться параллельно, нам остаётся найти максимальное значение в ячейках столбца E. Для этого в любую пустую ячейку пишем формулу: =МАКС(A:A) и получаем ответ: 17.
-
Ответ: 17.
Решение (электронная таблица, С. Кох): -
сортируем таблицу по первому столбцу (ID процесса B) и добавляем первой строкой (в электронной таблице – в строку 2) фиктивный процесс в которую записываем процесс с ID = 0, время выполнения 0 и время окончания процесса 0:
-
расцепляем процессы в ячейках столбца C с помощью функции «Текст по столбцам» (см. выше в решении Информатика БУ):
-
В первом свободном столбце в 3-й строке пишем формулу, которая учитывает максимальное количество процессов, которое встречается в этой задаче (например, здесь в E3 пишем формулу =МАКС(ВПР(C3;A:E;5);ВПР(D3;A:E;5))+B3)
и растягиваем эту формулу на весь столбец. В этом случае все пустые ячейки Excel считает равными 0 и обращается к 0 процессу, время завершения которого 0.
-
находим максимум в последнем столбце:
-
Ответ: 17.
Решение (диаграмма Ганта, А. Кожевникова): -
Решение удобно выполнять в Excel, построив диаграмму Ганта, которая показывает зависимость процессов. Построение диаграммы состоит в закрашивании ячеек таблицы Excel разным цветом, длина (количество закрашиваемых ячеек) процесса соответствует времени его выполнения.
-
Построим диаграмму Ганта для таблицы, приведённой в задании:
ID процесса B
|
Время выполнения процесса B (мс)
|
ID процесса (ов) A
|
1
|
4
|
0
|
2
|
3
|
0
|
3
|
1
|
1; 2
|
4
|
7
|
3
|
5
|
6
|
3
|
6
|
3
|
5
|
7
|
1
|
4; 6
|
8
|
2
|
7
|
9
|
7
|
0
|
10
|
8
|
0
|
11
|
6
|
9
|
12
|
6
|
10
|
-
Сначала отобразим на диаграмме процесс 1 и 2. Оба процесса начинаются независимо друг от друга. Поэтому строим оба процесса с самого начала.
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-
процесс 3 длительностью 1 начинается только после окончания процессов 1 и 2:
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
1
|
3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-
Процессы 4 и 5 начинаются после выполнения процесса 3:
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
1
|
3
|
4
|
|
|
|
|
|
2
|
|
|
5
|
|
|
|
|
|
|
-
Процесс 6 начинается после выполнения процесса 5. Процесс 7 начинается после завершения процессов 4 и 6. Процесс 8 начинается после завершения процесса 7.
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
1
|
3
|
4
|
|
|
7
|
8
|
|
2
|
|
|
5
|
6
|
|
|
|
|
-
Процессы 9 и 10 начинаются сразу в момент 0, так как независимы от других процессов. Процесс 11 начинается после завершения процесса 9, а процесс 12 процесс сразу после завершения процесса 10.
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
1
|
3
|
4
|
|
|
7
|
8
|
|
2
|
|
|
5
|
6
|
|
|
|
|
9
|
11
|
|
|
|
|
|
10
|
12
|
|
|
|
-
Позже всех – через 17 мс – заканчивается процесс 8. Это и есть минимальное время завершения всей совокупности процессов.
-
Ответ: 17.