Построение математических моделей для решения практических задач. Многопроцессорные системы (диаграмма Ганта)
(Ким 22, 7 мин)
Болгова Н.А.
Учитель информатики
МБОУ СОШ с.Тербуны
Нужно знать :
- процессы в современных компьютерах могут выполняться параллельно , если являются независимыми
- выражение « процесс В зависит от процесса А» означает, что выполнение процесса В не может начаться раньше , чем выполнение процесса А
Параллельно – независимые последовательные - зависимые
1
2
3
1
2
3
Задача 1
график Ганта (формулы)
Шаг 1. Разделим параллельные процессы: ДАННЫЕ – Текст по столбцам – разделители ….. Шаг 2. Добавим время выполнения каждого процесса (t1,t2), начало процесса (t0) и окончание процесса (tn)
Шаг 3 . Вычислим общее время выполнения процессов = B2 + МАКС( (E2 : F2)- нарастить
Шаг 4 . Вычислим время выполнения каждого процесса =ВПР(C2; A : H ; 8 ; 0) (нарастить)
Шаг 5 . Аналогично, время выполнения зависимых процессов =ВПР(D2;$A:$H;8;0)
Шаг 6 . Начало выполнения процессов =H2-B2+1 (+ 1, выполнение начинается с первой секунды )
Шаг 7. Создаем временнУю таблицу ( J - номер процесса, K1:AH1 - время в м/секунды
Шаг 8. в ячейку К2 вводим формулу =ЕСЛИ(И($G2 K$1 ; K$1 (начало
Если в данную м/секунду процесс выполняется, поставим в ячейку 1, иначе - пробел
Пояснение формулы:
Заморозка столбца (начало процесса $G2)
Заморозка столбца (окончание процесса $Н2)
Заморозка строки 1 ( K$1)
Для исключения потери данных
при копировании вправо - вниз
Условное форматирование
Из таблицы видим, что последний процесс завершился на 17 м/сек
Ответ: 17
45.( Д. Статный ) В файле 22-45.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. ……
- Определите максимальное количество процессов, которые выполнялись параллельно , при условии, что все независимые друг от друга процессы стартовали одновременно, а зависимые процессы стартовали одновременно с завершением всех процессов, от которых они зависят.
2 способ ( ручное построение-визуальный способ )
шаг 1.Обозначим время (м/сек)
шаг 2. Отметим независимые процессы (объединение ячеек)
шаг 3. Отметим зависимые процессы
Процесс 2 выполняется после завершения процесса 1 и длится 3 м/сек
шаг 4. Аналогично отмечаем все процессы
Примечание:
1) зависимый процесс можно отмечать в любой строке диаграммы;
2) Для удобства лучше использовать разные цвета
3) Процессы можно перемещать (рис – 6 и 8)
максимальное количество процессов, которые выполнялись параллельно
6
6
Ответ: 6
№ 46
В файле 22-46.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно.
Определите наибольшее количество процессов, выполнявшихся параллельно . В ответе укажите сумму этого количества и времени, прошедшего с момента начала вычислений до их завершения.
1 способ (формулы)
Определите наибольшее количество процессов, выполнявшихся параллельно . В ответе укажите сумму этого количества и времени, прошедшего с момента начала вычислений до их завершения.
кол-во = 6
время = 18
Ответ: 24
2 способ (визуальный способ)
наибольшее количество процессов, выполнявшихся параллельно . В ответе укажите сумму этого количества и времени, прошедшего с момента начала вычислений до их завершения
кол-во = 6
Общее время = 18
Сумма 18 + 6 = 24
Ответ: 24
№ 47
- ( А. Куканова ) В файле 22-46.xls содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно.
- Вычислительное устройство имеет 4 вычислительных ядра . Каждый из параллельных процессов выполняется на отдельном ядре. Из готовых к выполнению процессов в первую очередь запускаются процессы с наименьшими ID .
- Определите минимальное время, через которое завершится выполнение всей совокупности процессов.
1 способ (визуальный способ)
4 ядра
Ответ: 22
2 способ (формулы)
- Дополним I-столбец время задержки процесса
- Столбец H (окончание процесса) изменим формулу: было =B2+МАКС(E2:F2), Новая формула : = B2+МАКС(E2:F2)+ I2
- Добавим сумму всех процессов Sпроц = СУММ(I2:I16)
Анализ процессов: процесс 14 независимый, сделаем для него задержку на 3 м/с
!
Нужно следить, чтобы сумма в каждой м/с не превышала 4 (т.е. 4 процесса за одну м/с по количеству разрядов)
На шестой м/с видим, что выполняется одновременно 5 процессов, следовательно можно сместить либо процесс № 1, либо № 6.
Таким образом, изменяя время начала процесса (столбец I), нужно получить выполнение только 4х процессов одновременно в каждую м/с
Изменяя время начала процесса (столбец I), получаем 4х процесса в м/с.
Важно сделать время минимальным
Ответ: 22
Литература
- КИМ ЕГЭ 2025
- Сайт К.Ю.Полякова, задание 22 + файлы к заданиям [ https://kpolyakov.spb.ru/school/ege.htm ]