Среднее время ожидания в расписании Round Robin

Question

Время ожидания определяется как время, которое каждый процесс должен ждать, прежде чем он получит свой интервал времени.В алгоритмах планирования, таких как «Зарезервированное задание первым и первым обслужено», мы можем легко найти это время ожидания, когда просто ставим в очередь задания и видим, сколько времени каждому пришлось ждать до тех пор, пока оно не будет обслужено.

Когда оноЧто касается Round Robin или любых других вытесняющих алгоритмов, то мы обнаруживаем, что долго выполняющиеся задания тратят немного времени на ЦП, когда они вытесняются, а затем ждут какое-то время для своей очереди, и в какой-то момент она исполняется до завершения.Я хотел найти лучший способ понять «время ожидания» заданий в таком алгоритме планирования.

Я нашел формулу , которая дает время ожидания как:

Waiting Time = (Final Start Time - Previous Time in CPU - Arrival Time)

Но я не понимаю причины этой формулы.Например, рассмотрим задание А, в котором время всплеска составляет 30 единиц, а циклический перебор происходит каждые 5 единиц.Есть еще два задания B (10) и C (15).

Порядок их обслуживания будет:

0 A 5 B 10 C 15 A 20 B 25 C 30 A 35 C 40 A 45 A 50 A 55

Время ожидания A = 40 - 5 -0

• Я выбираю 40, потому что после 40 А никогда не ждет.Он просто получает свои временные интервалы и продолжает и продолжает.
• Выберите 5, потому что A потратил в процессе ранее между 30 и 35.
• 0 - время начала.

Ну, у меня есть сомнения в этой формуле, почему не было учтено 15 A 20?Интуитивно, я не могу понять, как это дает нам время ожидания для A, когда мы просто учитываем только предпоследнее выполнение и затем вычитаем время прибытия.

По моему мнению, время ожидания для A должнобыть:

• Конечное время начала - (сумма всех затрат времени на обработку).

Если эта формула неверна, то почему?

Пожалуйста, помогите прояснить мое понимание этой концепции.

Answer 1

Вы неправильно поняли, что подразумевается под формулой «предыдущий раз в процессоре». На самом деле это означает то же самое, что вы называете «суммой всех затрат времени на обработку». (Я предполагаю, что «предыдущий раз в ЦП» должен быть сокращенным от «общего времени, потраченного ранее на работу в ЦП», где «ранее» означает «до окончательного запуска».)

Вам все еще нужно вычесть время прибытия, потому что процесс явно не ожидал до его прибытия. (На всякий случай это неясно: «время прибытия» - это время, когда задание было отправлено в планировщик.) В вашем примере время прибытия для всех процессов равно 0, так что это не имеет значения, но в общем случае время прибытия должно быть принято во внимание.

Редактировать: если вы посмотрите на пример на веб-странице, на которую вы ссылаетесь, процесс P1 берет два временных отрезка по четыре единицы времени каждый перед своим окончательным запуском, и его "предыдущий раз в ЦП" вычисляется как 8, в соответствии с толкование выше.

Answer 2

Последнее ожидание

значение- (квант времени × (n-1))

Здесь n обозначает время, когда процесс приходит на диаграмму Ганта.