Определите количество процессов, которые завершатся до старта процесса 118. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1. Например, для приведённой таблицы до старта процесса 3 завершатся 3 процесса (это процессы 1, 2 и 4).

Решение:

Для определения, какие процессы завершатся до старта процесса 118, необходимо рассчитать время завершения каждого процесса. Время начала каждого процесса — самое раннее возможное. Процесс может начаться, как только завершатся все зависящие от него процессы.

Дана следующая таблица:

Рассчитаем время начала и завершения каждого процесса:

• Процесс 1:
  • Зависимости: 0 (независимый).
  • Время начала: 1 мс (самое раннее допустимое).
  • Время выполнения: 3 мс.
  • Время завершения: 1 + 3 = 4 мс.
• Процесс 4:
  • Зависимости: 0 (независимый).
  • Время начала: 1 мс (самое раннее допустимое).
  • Время выполнения: 5 мс.
  • Время завершения: 1 + 5 = 6 мс.
• Процесс 2:
  • Зависимости: 1.
  • Время начала: Завершение процесса 1 (4 мс).
  • Время выполнения: 4 мс.
  • Время завершения: 4 + 4 = 8 мс.
• Процесс 5:
  • Зависимости: 1, 4.
  • Время начала: Максимум из времени завершения процессов 1 (4 мс) и 4 (6 мс) = 6 мс.
  • Время выполнения: 8 мс.
  • Время завершения: 6 + 8 = 14 мс.
• Процесс 3:
  • Зависимости: 2, 4.
  • Время начала: Максимум из времени завершения процессов 2 (8 мс) и 4 (6 мс) = 8 мс.
  • Время выполнения: 5 мс.
  • Время завершения: 8 + 5 = 13 мс.

Процесс 118 является конечным. Все процессы, завершившиеся до 118 мс, учитываются.

Время завершения процессов:

• Процесс 1: 4 мс
• Процесс 2: 8 мс
• Процесс 3: 13 мс
• Процесс 4: 6 мс
• Процесс 5: 14 мс

Все эти процессы завершаются до 118 мс.

Ответ: 5 процессов.