Задание 22. Многопоточные вычисления

Задание 22 демонстрационного варианта ЕГЭ-2027 (ФИПИ).

Файл к заданию: demo_22.ods – скачайте его и повторяйте шаги разбора в LibreOffice.

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

Определите максимальное количество процессов, которые параллельно выполняются на 7-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.

Типовой пример организации данных в файле:

Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.

1. Вся задача сводится к двум числам на процесс – когда он начинается и когда заканчивается.
2. Правило начала: независимый процесс стартует на 1-й мс; зависимый – на следующей миллисекунде после того, как закончится последняя из задач, от которых он зависит. То есть начало = максимум концов зависимостей + 1.
3. Правило конца: конец = начало + время выполнения - 1. Минус один – потому что нумерация миллисекунд идёт с 1 и сама первая миллисекунда уже рабочая: процесс длиной 3 мс, начатый на 1-й, заканчивается на 3-й, а не на 4-й.
4. Проверим правило на типовом примере из условия.

Процесс 3 получил начало 8 и конец 9 – ровно то, что написано в условии. Это и есть проверка, что таблица построена верно: если ваши числа здесь разошлись с этими, дальше идти незачем.

5. Главная ловушка файла: строки в нём не отсортированы по зависимостям. В demo_22.ods процесс 1 (первая строка данных) зависит от процессов 3 и 25, а те лежат ниже. Поэтому считать сверху вниз по одной строке нельзя – формула обязана смотреть сразу на весь столбец концов, а порядок вычислений Calc разберёт сам.
6. Вопрос «сколько процессов работает на 7-й мс» – это подсчёт строк, у которых начало не больше 7, а конец не меньше 7. Считать руками двадцать пять строк не нужно, для этого есть СУММПРОИЗВ.

Откройте demo_22.ods – лист «Лист 1», данные в строках 2-26.

Разбейте список зависимостей. В столбце C зависимости записаны одной строкой: 3;25, 8;6;15. Искать по такой строке неудобно, поэтому разложим её по ячейкам. Выделите C2:C26, откройте Данные → Текст по столбцам, в «Параметрах разделителя» отметьте точку с запятой и нажмите OK. Список 8;6;15 ляжет в C, D и E тремя числами, а 3;25 – в C и D, и E останется пустой. Если в списке встречаются пробелы (2; 4), отметьте ещё «Пробел» и «Объединять разделители».

В F1 напишите «Начало», в G1 – «Конец». Формулы для строки 2:

F2: =МАКС(ЕСЛИОШИБКА(ВПР(C2;$A$2:$G$26;7;0);0);ЕСЛИОШИБКА(ВПР(D2;$A$2:$G$26;7;0);0);ЕСЛИОШИБКА(ВПР(E2;$A$2:$G$26;7;0);0))+1
G2: =F2+B2-1

Как читать формулу начала. Она состоит из трёх одинаковых кусков – по одному на каждую зависимость в C, D, E:

• ВПР(C2;$A$2:$G$26;7;0) берёт ID из C2, находит его строку в столбце A и возвращает 7-й столбец диапазона – это G, конец того процесса. Для процесса 1 в C2 стоит 3, и ВПР отдаёт конец процесса 3 – 9. Второй кусок ищет D2 = 25 и отдаёт 5.
• ЕСЛИОШИБКА(…;0) нужна для пустых ячеек и нулей. В E2 пусто, у независимого процесса в C стоит 0 – такого ID в столбце A нет, и ВПР выдаёт ошибку #Н/Д. ЕСЛИОШИБКА заменяет её нулём, и этот кусок ни на что не влияет.
• МАКС(…)+1 выбирает самый поздний конец из трёх и сдвигает на следующую миллисекунду: у процесса 1 МАКС(9;5;0)+1 = 10. У независимого процесса все три куска дают 0, и начало выходит 1 – отдельная проверка не нужна.

Знаки $ в $A$2:$G$26 держат диапазон на месте при протягивании: каждая строка ищет по всей таблице, поэтому порядок строк в файле не мешает.

Формула начала смотрит на столбец концов, а конец считается из начала – формально это ссылка по кругу, и Calc умеет разобрать её сам. Если вместо чисел в столбце появилось Ошибка:522, включите итеративные вычисления: Сервис → Параметры → LibreOffice Calc → Вычисления → «Итеративные ссылки», шагов 100. Больше эта настройка ни для чего не нужна.

В свободную ячейку (например I2) – формулу ответа:

I2: =СУММПРОИЗВ((F2:F26<=7)*(G2:G26>=7))

(F2:F26<=7) даёт столбец из ИСТИНА/ЛОЖЬ «начался не позже 7-й мс», второй множитель – «ещё не закончился на 7-й». Произведение двух логических значений – это 1 только там, где верны оба, СУММПРОИЗВ их складывает. Ответ: 8.

Таблица начал и концов строится одинаково, меняется только формула ответа.

• Нет $ в диапазоне ВПР. При протягивании диапазон уезжает вниз, верхние процессы из него выпадают, ЕСЛИОШИБКА молча заменяет промах нулём – ответ неверный, а ошибок на экране нет.
• Не тот номер столбца в ВПР. Он должен указывать на «Конец», считая от первого столбца диапазона. Промах на один – и вместо конца зависимости берётся её начало.
• Нет ЕСЛИОШИБКА. Пустая ячейка и 0 дают #Н/Д, и ошибка расползается по всем зависимым процессам.
• Конец без -1. Первая миллисекунда процесса – уже рабочая: длиной 3 мс, начатый на 1-й, он кончается на 3-й.
• Строгие границы. «Выполняется на k-й мс» – это начало <=k и конец >=k, обе включительно.