Задание 22 · Многопроцессорные системы
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — сколько процессов шло в 21-ю миллисекунду — решалась на восьми процессах, посчитанных руками, и каждая подтема добавляла к расписанию новый вопрос. Пролистай решение: в подписи каждого шага — подтема, откуда приём.
- Подтема 1. Процесс ждёт всех, от кого зависит: начинается, когда закончился последний из них. Цепочка 2 → 5 → 7 → 8 даёт итог 14 мс.
- Подтемы 1 и 2. Расписание: начало — наибольшее окончание поставщиков, окончание — начало плюс время. В Excel это ВПР и МАКС.
- Подтема 3. В n-й мс идут процессы с началом меньше n и окончанием не меньше n: на 7-й мс — 3, 4 и 5. Так же в задаче темы на 21-й мс — 3 процесса.
- Подтема 4. Сетка по миллисекундам: сумма столбца — сколько процессов идёт одновременно, пик — самый длинный отрезок с наибольшей суммой.
Расписание строится один раз, а вопросы к нему — разные. Подтема 5 разрешает сдвигать процессы позже, а дополнительный урок добавляет задержки и ограниченное число процессоров.
Карта темы
Каждая подтема дала одну формулу или правило, и любое решение собирается из них. Сверху — путь от таблицы к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Расписаниеначало — МАКС окончаний поставщиков
- Сдвигиможно ли запускать позже
- ОтветСЧЁТЕСЛИМН, МАКС или сетка
1Процессы и расписание
- началосамое позднее окончание поставщиков
- окончаниеначало + время
- итогнаибольшее окончание всех процессов
2Расписание в Excel
=ЕСНД(ВПР(C2;окончание поставщика; нет поставщика — 0$A$1:$H1; 8; 0); 0) =МАКС(E2:F2)начало процесса- «Текст по столбцам»разложить «1;2» на числа
3Сколько процессов
- n-я мсначало < n и окончание ≥ n
СЧЁТЕСЛИМНоба условия сразу
4Параллельность
- сетка1, если процесс идёт в эту мс
- сумма столбцасколько процессов идёт одновременно
5Сдвиги процессов
- позднее началосчитают с конца, от итога
- запаспозднее начало минус раннее
6Задержки и ограниченные ресурсыдополнительный урок
- задержкаприбавить к самому позднему окончанию
- мало процессоровпроцесс готов и есть свободное место
Как решать
Любое задание 22 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
После протягивания открой несколько формул — первой строки, из середины, процесса с тремя поставщиками — и проверь, что каждая ищет своих поставщиков в строках выше.
Частые ошибки
Пять ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- сложены окончания
- начало — сумма окончаний поставщиков → начало — их максимум. Спроси себя: поставщики идут одновременно или по очереди?подтема 1
- ответ по последнему ID
- общее время взято из последней строки →
=МАКС(H2:H…). Спроси себя: точно ли последний процесс кончается последним?подтема 1 - поставщик-текст
- ВПР не находит «1;2» → «Текст по столбцам» — ID станут числами. Спроси себя: поставщик записан числом или текстом?подтема 2
- граница миллисекунды
- для n-й мс: начало ≤ n → начало < n и окончание ≥ n. Спроси себя: идёт ли процесс с 6 до 8 в 6-й мс?подтема 3
- сдвиги не учтены
- ответ из раннего расписания, хотя сдвигать можно → поздние начала и запас. Спроси себя: сказано ли «в самое раннее допустимое время»?подтема 5
Итог
Тема пройдена: задача темы решена от восьми процессов до ответа 3. Вот что взять с собой.
- ПорядокТаблица, расписание, сдвиги, вопрос, проверка.
- РасписаниеНачало — МАКС окончаний поставщиков.
- Миллисекундаn-я мс: начало < n, окончание ≥ n.
- ПараллельностьСетка: сумма столбца и самый длинный пик.
- Задача темыНа 21-й мс шло 3 процесса.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Процесс ждёт процессы, которые кончаются в 4 и в 6 мс, и работает 3 мс. Когда он начнётся и закончится?
ОтветСкрыть ответ
Начнётся в 6 — когда закончится последний из поставщиков, — и закончится в 9.
Процесс идёт с 6 до 8. В какие миллисекунды он выполняется?
ОтветСкрыть ответ
В 7-ю и 8-ю: n-я мс — промежуток от n − 1 до n.
Почему общее время — МАКС окончаний, а не окончание последнего по номеру процесса?
ОтветСкрыть ответ
Процессы идут параллельно, и последний по номеру может закончиться раньше других.
Как найти самый длинный отрезок, на котором шло больше всего процессов?
ОтветСкрыть ответ
Построить сетку по миллисекундам, сложить столбцы и найти самую длинную серию с наибольшей суммой.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Общее время по файлу 22-6
По файлу 22-6.xlsx определите минимальное время (в мс), через которое завершится выполнение всей совокупности процессов.
Введите число.
Подсказка
Расписание через ВПР; ответ — наибольшее окончание.
Решение
73.
Формулы в Excel
C: Данные → Текст по столбцам, разделитель «;» → C:EF2: =ЕСНД(ВПР(C2;$A$1:$J1;10;0);0) — на F2:H…I2: =МАКС(F2:H2) — началоJ2: =I2+B2 — окончание; всё протянуть внизОтвет: =МАКС(J2:J31)Ответ: 73
Десять процессов по файлу 22-4
По файлу 22-4.xlsx определите минимальное время (в мс), через которое завершится выполнение 10 процессов.
Введите число.
Подсказка
Десятое по возрастанию окончание.
Решение
11.
Формулы в Excel
C: Данные → Текст по столбцам, разделитель «;» → C:EF2: =ЕСНД(ВПР(C2;$A$1:$J1;10;0);0) — на F2:H…I2: =МАКС(F2:H2) — началоJ2: =I2+B2 — окончание; всё протянуть внизОтвет: =НАИМЕНЬШИЙ(J2:J21;10)Ответ: 11
Пик параллельности по файлу 22-3
По файлу 22-3.xlsx определите длительность (в мс) самого длинного отрезка времени, на котором выполнялось наибольшее количество процессов одновременно.
Введите число.
Подсказка
Сетка миллисекунд, строка сумм и счётчик подряд.
Решение
3: наибольшее число одновременно идущих процессов — 5, подряд они идут 3 мс.
Формулы в Excel
C: Данные → Текст по столбцам, разделитель «;» → C:EF2: =ЕСНД(ВПР(C2;$A$1:$J1;10;0);0) — на F2:H…I2: =МАКС(F2:H2) — началоJ2: =I2+B2 — окончание; всё протянуть внизL1, M1, …: номера мс 1, 2, 3, …L2: =ЕСЛИ(И(L$1>$I2;L$1<=$J2);1;0) — на сеткустрока 18: суммы столбцов, строка 19 — счётчикОтвет: МАКС счётчика при k = МАКС(строки сумм)Ответ: 3
Не раньше 20 мс по файлу 22-5
По файлу 22-5.xlsx: процесс может начаться в любой момент после завершения всех процессов, от которых он зависит. Определите наибольшее количество процессов, которые могут начать выполнение не раньше чем через 20 мс после запуска первого процесса, если все процессы должны завершиться за минимально возможное время.
Введите число.
Подсказка
Поздние начала — с конца; считай те, что не меньше 20.
Решение
13.
Формулы в Excel
C: Данные → Текст по столбцам, разделитель «;» → C:EF2: =ЕСНД(ВПР(C2;$A$1:$J1;10;0);0) — на F2:H…I2: =МАКС(F2:H2) — началоJ2: =I2+B2 — окончание; всё протянуть внизK: позднее окончание — МИН поздних начал тех, кто ждёт; у кого никто — =МАКС(J2:J19)L2: =K2-B2 — позднее началоОтвет: =СЧЁТЕСЛИ(L2:L19;">=20")Ответ: 13
45-я миллисекунда по файлу 22-1
По файлу 22-1.xlsx определите, сколько процессов выполнялось в течение 45-й миллисекунды, при условии, что все независимые друг от друга процессы могут выполняться параллельно. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.
Введите число.
Подсказка
Начало < 45, окончание ≥ 45.
Решение
4 — четыре процесса с началом меньше 45 и окончанием не меньше 45.
Формулы в Excel
C: Данные → Текст по столбцам, разделитель «;» → C:EF2: =ЕСНД(ВПР(C2;$A$1:$J1;10;0);0) — на F2:H…I2: =МАКС(F2:H2) — началоJ2: =I2+B2 — окончание; всё протянуть внизОтвет: =СЧЁТЕСЛИМН(I2:I19;"<45";J2:J19;">=45")Ответ: 4