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 - это дисциплина обслуживания без переключения, поэтому ее не рекомендуется применять в системах разделения времени, где необходимо гарантировать приемлемые времена ответа.