Алгоритмы диспетчеризации с одной очередью

При выборе конкретного алгоритма диспетчеризации необходимо обратить внимание на то, какое влияние она оказывает на время ожидания обработки, т. е. на время, которое готовый к выполнению процесс тратит на ожидание исполнения. Известно, что пользователь тем более нетерпелив к длительному ожиданию, чем короче его процесс; это справедливо как для интерактивных, так и фоновых работ. Следовательно, алгоритм диспетчеризации должна уменьшать среднее время ожидания самых коротких процессов.

Время ожидания обработки вместе с временем выполнения процесса (в течение которого центральный процессор выделяется процессу) составляют длительность цикла обработки. Последняя, в свою очередь, представляет собой интервал между временем поступления процесса в систему и временем завершения его обработки.

5.3.1. Алгоритм FCFS (первый пришедший обслуживается первым)

Алгоритм FCFS (First-Come-First-Served) - первый пришедший обслуживается первым - является наиболее простым алгоритмом диспетчеризации (рис.5.1). Центральный процессор предоставляется процессам в порядке их прихода в очередь готовности. После того как процесс получает ЦП в свое распоряжение, он выполняется до завершения (за исключением, конечно, тех случаев, когда процесс переходит в заблокированное состояние). Алгоритм FCFS - это дисциплина диспетчеризации без переключения. Если рассуждать формально, то этот алгоритм можно считать справедливым, однако он все-таки в определенном смысле несправедлив тем, что длинные процессы заставляют ждать короткие, а менее важные процессы - более важные. Другими недостатками алгоритма FCFS является то, что, во-первых, среднее время ожидания может неограниченно расти по мере того, как система приближается к пределу своей загруженности, а во-вторых, с увеличением дисперсии времени выполнения процессов среднее время ожидания увеличивается. Для интерактивного режима алгоритм FCFS непривлекателен еще и потому, что в связи с отсутствием переключения центрального процессора исполняющийся процесс будет задерживать остальные процессы, что не позволяет гарантировать приемлемое время ответа.

Рис. 5.1. Планирование по принципу FCFS

(первый пришедший обслуживается первым)

В современных системах алгоритм FCFS редко используется самостоятельно в качестве основной дисциплины обслуживания, а чаще комбинируется с другими схемами. Например, во многих схемах предусматривается диспетчеризация процессов в соответствии с их приоритетами, однако процессы с одинаковыми уровнями приоритета диспетчируются по принципу FCFS.

5.3.2. Алгоритм SPN (кратчайший процесс - следующий)

Алгоритм SPN (Shortest-Process-Next) (кратчайший процесс - следующий) - это дисциплина планирования без переключения, согласно которой следующим для выполнения выбирается ожидающий процесс с минимальным оценочным рабочим временем. Алгоритм SPN обеспечивает уменьшение среднего времени ожидания по сравнению с дисциплиной FCFS. Однако времена ожидания при этом колеблются в более широких пределах (т. е. менее предсказуемы), чем в случае FCFS, особенно при больших по длительности процессах. В результате трудно предсказать, когда процесс будет обслужен.

Механизм SPN выбирает для обслуживания процессы таким образом, чтобы очередной процесс завершался и покидал систему как можно быстрее. Благодаря этому обеспечивается уменьшение количества ожидающих процессов, а также количества процессов, стоящих в очереди за длинными процессами. В результате алгоритм SPN позволяет свести к минимуму среднее время ожидания для процессов, проходящих через систему.

Дисциплина SPN оказывает предпочтение коротким процессам за счет более длинных. Многие разработчики считают, что чем короче процесс, тем лучшие условия для его выполнения следует создавать. Далеко не все специалисты придерживаются подобного мнения, особенно применительно к случаям, когда необходимо учитывать приоритетность процессов. Кроме того, имеется риск увеличения времени ожидания для длинных процессов при повышенной норме поступления в систему коротких процессов. для устранения этого недостатка следует придавать процессам приоритет, возрастающий с ростом времени их пребывания в очереди.

Другая очевидная проблема, связанная с реализацией алгоритма SPN, состоит в том, что он требует точно знать, сколько времени будет выполняться процесс, а такой информации обычно не бывает. Самое большее, что может сделать механизм SPN, - это полагаться на оценочные значения времен выполнения, указываемые пользователями. В условиях производственного счета, когда одни и те же задачи выполняются регул­ярно, довольно точные и обоснованные оценки, по-видимому, возможны. Однако в исследовательской работе пользователи редко знают, как долго будут выполняться их программы.

Ориентация механизма планирования на оценки пользователей приводит к любопытным последствиям. Если пользователи знают, что система оказывает предпочтение процессам с малыми оценочными временами выполнения, они могут задавать малые оценочные времена. Можно, однако, спроектировать диспетчер таким образом, чтобы избавить пользователей от подобного соблазна. Пользователя можно заранее предупредить о том, что в случае, если его процесс будет выполняться дольше оценочного времени, то он (процесс) будет просто выводиться из системы, причем пользователю придется платить за всю работу. Второе возможное решение заключается в том, чтобы исполнять процесс в течение указанного оценочного времени плюс небольшой дополнительный процент, а затем выполнять переключение контекста, т. е. запоминать процесс в текущем виде, с тем, чтобы впоследствии можно было вновь продолжить его исполнение. При этом пользователю, естественно, придется оплачивать затраты на сохранение и последующий перезапуск, и, кроме того, он пострадает от задержки в завершении его процесса. Существует еще одно возможное решение - выполнять процесс в течение оценочного времени по обычному тарифу, а затем за дополнительное время предъявлять счет по повышенному тарифу, значительно превышающему обычный. При таких условиях пользователь, указывающий нереально низкие оценочные времена, чтобы получить улучшенное обслуживание, будет в итоге платить значительно больше, чем обычно.

Алгоритм SPN подобно FCFS - это дисциплина обслуживания без переключения, поэтому ее не рекомендуется применять в системах разделения времени, где необходимо гарантировать приемлемые времена ответа.

5.3.3. Алгоритм SRT (по наименьшему остающемуся времени)

Алгоритм SRT (Shortest-Remaining-Time) - следующий с минимальным оставшимся временем - аналог алгоритма SPN, но с переключением, применимый в системах с разделением времени. Оставшееся время - это разность между временем, запрошенным пользователем (временем выполнения), и временем, которое процесс уже получил и которое измеряется системой с помощью аппаратного таймера. По принципу SRT первым всегда выполняется процесс, имеющий минимальное оценочное время до завершения, причем с учетом новых поступающих процессов. Если в соответствии с алгоритмом SPN процесс, запущенный в работу, выполняется до своего завершения, то по алгоритму SRT выполняющийся процесс может быть прерван при поступлении нового процесса, имеющего более короткое оценочное время работы. Чтобы механизм SRT был эффективным, опять-таки нужны достаточно точные оценки будущего, причем разработчик системы должен позаботиться о мерах против неправильного использования прикладными программистами особенностей стратегий диспетчеризации.

Дисциплина SRT характеризуется более высокими накладными расходами, чем SPN. Механизм SRT должен следить за текущим временем обслуживания выполняющегося задания и обрабатывать возникающи­е прерывания. Поступающие в систему небольшие процессы будут выполняться почти немедленно. Однако более длительные процессы будут иметь даже большее среднее время ожидания и большую дисперсию времени ожидания, чем в случае SPN.

Реализация принципа SRT требует, чтобы­ регистрировались истекшие времена обслуживания, а это при­вод­ит к увеличению накладных расходов. Теоретически алгоритм SRT обеспечивает минимальные времена ожидания. Однако из­-за издержек на переключения может оказаться так, что в определенных ситуациях в действительности лучшие показатели будет иметь SPN.

Предположим, что поступает процесс, оценочное время которого лишь немногим меньше времени, необходимого для завершения текущего процесса. В этом случае механизм, реализующий чистый принцип SRT, выполнит переключение. Если, однако, затраты на переключение превышают разность времен обслуживания обоих процессов, то прерывание текущего процесса фактически приведет к снижению производительности системы. Поэтому разработчики операционных систем должны тщательно взвешивать накладные расходы механизмов управления ресурсами в сравнении с предположительными выгодами.

5.3.4. Алгоритм HRRN (по наибольшему относительному времени ответа)

Алгоритм HRRN (Highest Response Ratio Next) - следующий с наибольшим относительным временем ответа - компенсирует некоторые из слабостей, присущих дисц­иплине SPN­, в частности чрезмерное предубеждение против длинных процессов и чрезмерную благосклонность по отношению к коротким новым процессам. ­ HRRN - это алгоритм диспетчеризации без переключения, согласно которому приоритет каждого процесса является не только функцией времени выполнения этого процесса, но также времени, затраченного процессом на ожидание выполнения. После того как процесс получает в свое распоряжение центральный процессор, он выполняется до завершения. Динамические приоритеты при дисциплине HRRN ­ вычисляются по формуле

время ожидания + время выполнения

приоритет = .

время выполнения

Поскольку время выполнения находится в знаменателе, предпочтение будет оказываться более коротким процессам. Однако, поскольку в числителе имеется время ожидания, более длинные процессы, которые уже довольно долго ждут, будут также получать определенное предпочтение. На практике приоритеты пересчитываются через определенные промежутки времени, и в соответствии с изменениями очередь переупорядочивается. Отметим, что сумма

время ожидания + время обслуживания

есть длительность цикла обработки (время ответа системы) для данного процесса, если бы этот процесс инициировался немедленно после поступления в систему.

Не нашли, что искали? Воспользуйтесь поиском по сайту: