Многопроцессорные системы, Ким 22 (1 тип задач)

Построение математических моделей для решения практических задач. Архитектура современных компьютеров. Многопроцессорные системы Ким 22

(повышенный уровень, 7 мин)

Болгова Н.А.

Нужно знать :

• процессы в современных компьютерах могут выполняться параллельно , если являются независимыми
• выражение « процесс В зависит от процесса А» означает, что выполнение процесса В не может начаться раньше , чем выполнение процесса А

Уровень сложности 1 Поиск времени завершения процессов

Задача 1

Шаг 1. Выполним сортировку диапазона С2:С13 по возрастанию

Шаг 2. Переместим таблицу на строку ниже и добавим в строку 2 нулевой процесс

Шаг 3. Разделим параллельные процессы по отдельным столбцам: ДАННЫЕ – Текст по столбцам – разделители …..

Результат:

Шаг 5 . Вычислим общее время выполнения процессов Для независимых процессов (С2:С6) время выполнения не меняется

Шаг 5 . Вычислим общее время выполнения процессов Для независимых процессов (С2:С6) время выполнения не меняется

Шаг 5 . Вычислим общее время выполнения процессов Для последовательных процессов (С7:С12) время =

Шаг 5 . Вычислим общее время выполнения процессов Для последовательных «сдвоенных» процессов (С13:С14) время =

Шаг 6 . Вычислим минимальное время = время завершения последнего процесса (это функция МАКС)

Задание 2

процесс B зависит от процесса A, если для выполнения процесса B требуется, чтобы был выполнен хотя бы 50% от количества процессов А. Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.

• Разделим параллельные процессы по столбцам (Данные – текст по столбцам – с разделителем «;»)
• Добавим нулевой процесс

• Разделим параллельные процессы по столбцам (Данные – текст по столбцам – с разделителем «;»
• Добавим нулевой процесс

процессы

время выполнения каждого процесса

3. Вычислим общее время выполнения (Н2)

= B3+МАКС(F3:H3)

4. Вычислим время выполнения каждого процесса

=ВПР(C3;$A:$I;9;0)

Примечание:

в диапазоне таблицы А:Н замораживаем столбцы (добавим «$»)

5. Копируем формулу для t2, t3 и далее для диапазона F4:H14

Примечание: время окончания изменит значения

Условие: для выполнения процесса B требуется, чтобы был выполнен хотя бы 50% от количества процессов А . Процесс 3 начнется после выполнения процессов длительностью 4 и 3 м/сек, т.е. после 3 м/сек

6 . исправим формулу для I5: =B5+ МАКС(F5:H5 )+ G5

Аналогично для ячеек I9, I10

7. Найдем минимальное время завершения всех процессов: =МАКС(I2:I14 )

Ответ: 16

Задание 3

При составлении таблицы была потеряна информация о том, после какого процесса А начался процесс В с ID = 12. Однако известно, что вся совокупности процессов завершилась за минимальное время 25 мс. Определите ID процесса, после которого начался процесс с ID = 12. В ответе укажите только число.

Выполним пункт 1- пункт 5 (задача 2)

вся совокупности процессов завершилась за минимальное время 25 мс.

6. Очевидно, значение ID 12 = 25 7. Время выполнения процесса А (ячейка С14) = общее время (25) – время выполнения процесса В (19 м/сек): = G14 – B14 ,получаем 6 м/сек

8. Необходимо найти ID, общее время выполнения которого равно 6 м/сек – это ID 5

Задание 4

• Определим общее время выполнения каждого процесса
• ( п. 1- п. 6 (задача 2))

Примечание:

1)Процессы, зависимые от ID16 выделены цветом

2) Максимальное время выполнения = 134 (выделено цветом)

Введем произвольное значение в ячейку В18, например 10. В результате получаем макс = 131, не подходящий к условию задачи.

Таким образом подбираем значения в ячейке В18, пока не получим макс = 134

Ответ: 26