Что обозначает аббревиатура fcfs в программировании

17) алгоритм планирования FCFS

Что такое метод «первым пришел, первым обслужен»?

First Come First Serve (FCFS) – это алгоритм планирования операционной системы, который автоматически выполняет запросы и процессы в очереди в порядке их поступления. Это самый простой и простой алгоритм планирования процессора. В алгоритме этого типа процессы, которые сначала запрашивают ЦП, сначала получают распределение ЦП. Это управляется с помощью очереди FIFO. Полной формой FCFS является First Come First Serve.

Когда процесс входит в готовую очередь, его PCB (блок управления процессом) связывается с хвостом очереди и, когда ЦП становится свободным, его следует назначить процессу в начале очереди.

Из этого руководства по операционной системе вы узнаете:

Характеристики метода FCFS

• Он поддерживает алгоритм упреждающего и упреждающего планирования.
• Задания всегда выполняются в порядке поступления.
• Это легко реализовать и использовать.
• Этот метод имеет низкую производительность, и общее время ожидания довольно велико.

Пример планирования FCFS

Реальный пример метода FCFS – покупка билета в кино на кассе. В этом алгоритме планирования человек обслуживается согласно порядку очереди. Человек, который прибывает первым в очереди, сначала покупает билет, а затем следующий. Это будет продолжаться до тех пор, пока последний человек в очереди не купит билет. Используя этот алгоритм, процесс ЦП работает аналогичным образом.

Как работает FCFS? Расчет среднего времени ожидания

Вот пример пяти процессов, прибывающих в разное время. Каждый процесс имеет разное время посылки.

Обработать	Время взрыва	Время прибытия
P1	6	2
P2	3	5
P3	8	1
P4	3	0
P5	4	4

Используя алгоритм планирования FCFS, эти процессы обрабатываются следующим образом.

Шаг 0) Процесс начинается с P4, который имеет время прибытия 0

Шаг 1) В момент времени = 1 приходит P3. P4 все еще выполняется. Следовательно, P3 хранится в очереди.

Обработать	Время взрыва	Время прибытия
P1	6	2
P2	3	5
P3	8	1
P4	3	0
P5	4	4

Шаг 2) В момент времени = 2 прибывает P1, который сохраняется в очереди.

Обработать	Время взрыва	Время прибытия
P1	6	2
P2	3	5
P3	8	1
P4	3	0
P5	4	4

Шаг 3) В момент времени = 3 процесс P4 завершает свое выполнение.

Шаг 4) В момент времени = 4, P3, который является первым в очереди, начинает выполнение.

Обработать	Время взрыва	Время прибытия
P1	6	2
P2	3	5
P3	8	1
P4	3	0
P5	4	4

Шаг 5) В момент времени = 5 приходит P2, и он сохраняется в очереди.

Обработать	Время взрыва	Время прибытия
P1	6	2
P2	3	5
P3	8	1
P4	3	0
P5	4	4

Шаг 6) В момент 11 P3 завершает свое выполнение.

Шаг 7) В момент времени = 11, P1 начинает выполнение. Он имеет время пакета 6. Он завершает выполнение через интервал времени 17

Шаг 8) В момент времени = 17, P5 начинает выполнение. Он имеет время пакета 4. Он завершает выполнение в момент времени = 21

Шаг 9) В момент времени = 21 P2 начинает выполнение. Он имеет время пакета 2. Он завершает выполнение через интервал времени 23

Шаг 10) Рассчитаем среднее время ожидания для приведенного выше примера.

Среднее время ожидания

Преимущества FCFS

Вот преимущества и преимущества использования алгоритма планирования FCFS:

First Come First Serve (FCFS) Scheduling

When we run a program, we create a particular instance of the program called a process. There might be a condition where more than one process is created at a given time and the CPU has to serve all the processes. There are various process scheduling algorithms that decide which process has to be executed at a given time by considering various factors. FCFS or First come first serve is one such algorithm that schedules the processes.

Scope

• This article will explain the fcfs algorithm along with the Gantt chart.
• Implementation of FCFS algorithm using cpp.
• Advantages and disadvantages of the algorithm.

What is First Come First Serve Scheduling?

The First come first serve scheduling algorithm is non-preemptive in nature i.e, if a process is already running, then it is not interrupted by another process until the currently running process is executed completely.

Buying a movie ticket from the ticket counter is a perfect real-life example of a first come first serve (FCFS) algorithm. The person who comes first and stands in the queue gets to buy the ticket first. Similarly in the fcfs scheduling algorithm, the process which arrives first gets executed first.

How does FCFS Scheduling Work?

Let us consider an example where 4 processes with different burst times arrive at different times.

Process	Burst Time	Arrival time
P1	6	2
P2	8	1
P3	3	0
P4	4	4

Let us see how the above processes are handled using the First come first serve scheduling algorithm.

• At time t=0

Process	Burst Time	Arrival time
P1	6	2
P2	8	1
P3	3	0 (please add this row in different color)
P4	4	4

Queue

Gantt Chart

From the above chart, we can see that at time 0, the process P3 arrives. Once the process P3 arrives, the process is served as there is no other process that is being executed.

At time t=1

Process	Burst Time	Arrival time
P1	6	2
P2	8	1 (please add this row in different color but same color as the one used in previous image)
P3	3	0
P4	4	4

The process P2 arrives at time t=1, but the program P3 is still executing. The process P2 will be kept in a queue which will be executed after the existing process finishes its execution. Queue Gantt Chart

• At time t=2

Process	Burst Time	Arrival time
P1	6	2 (please add this row in different color but same color as the one used in previous image)
P2	8	1
P3	3	0
P4	4	4

At time t=2, Process P1 arrives and waits in the queue as there is another process being executed.

Queue

Gantt Chart

• At time t=3

At time t=3, Process P3 finished execution after 3 seconds. In the queue, the process P2 is waiting for the execution Therefore process P2 begins its execution.

Queue Gantt Chart

• At time t=5

Process	Burst Time	Arrival time
P1	6	2
P2	8	1
P3	3	0
P4	4	4 (please add this row in different color but same color as the one used in previous image)

At time t=5, Process P4 arrives and waits in the queue.

Queue Gantt Chart

• At time t=21

In the end, at time t=21 we get a Gantt chart as shown below.

Gantt Chart

Characteristics of FCFS Algorithm

• The first come first serve is a simple scheduling algorithm
• The process which arrives first would be served first based on a first come first serve basis.
• This method is easy to understand and implement.

Implementation of FCFS Scheduling Using a Programming Language

C++ code

Output

Explanation In the above code, we created 4 processes with the burst time of 6, 8, 3, and 4. We make a call to the avgTime function, The avgTime function calls the waitingTime and turnAroundTime functions which return the waiting time and turn around time respectively.

Example of FCFS

Billing counters in a supermarket is a real-life example of the FCFS algorithm. The first person to come to the billing counter will be served first, later the next person, and so on. The second customer will only be served if the first person's complete billing is done. Similarly in the FCFS scheduling algorithm, the process which arrives first will be completely served and late the next process waiting will be served.

Calculating Average Waiting Time

Turn around time is the amount of time taken to fulfill the request by the process. It can be calculated by taking the difference between the completion time and the arriving time.

Waiting time is the time spent by a process in the queue waiting to get executed. difference between the turn around time and the burst time. The sum of all the waiting times divided by the number of the process gives the average waiting time.

Now let us find the average waiting time for the previous example we considered.

First, let us find the Turn Around Time (T.A.T). Turn Around Time = Completion Time – Arrival Time.

Process	Burst Time	Arrival time	Completion Time	Turn Around Time
P1	6	2	17	15
P2	8	1	11	10
P3	3	0	3	3
P4	4	4	21	17

Next, let us find the waiting time. Waiting Time = Turn Around Time – Burst Time.

Process	Burst Time (ms)	Arrival Time (ms)	Completion Time (ms)	Turn Around Time (ms)	Waiting Time (ms)
P1	6	2	3	15	9
P2	8	1	11	10	9
P3	3	0	17	3	3
P4	4	4	21	17	13

The average waiting time is calculated by taking the sum of all the waitings and dividing it by the number of processes.

FCFS Scheduling Algorithm: What is, Example Program

First Come First Serve (FCFS) is an operating system scheduling algorithm that automatically executes queued requests and processes in order of their arrival. It is the easiest and simplest CPU scheduling algorithm. In this type of algorithm, processes which requests the CPU first get the CPU allocation first. This is managed with a FIFO queue. The full form of FCFS is First Come First Serve.

As the process enters the ready queue, its PCB (Process Control Block) is linked with the tail of the queue and, when the CPU becomes free, it should be assigned to the process at the beginning of the queue.

In this operating system tutorial, you will learn:

Characteristics of FCFS method

• It supports non-preemptive and pre-emptive scheduling algorithm.
• Jobs are always executed on a first-come, first-serve basis.
• It is easy to implement and use.
• This method is poor in performance, and the general wait time is quite high.

Example of FCFS scheduling

A real-life example of the FCFS method is buying a movie ticket on the ticket counter. In this scheduling algorithm, a person is served according to the queue manner. The person who arrives first in the queue first buys the ticket and then the next one. This will continue until the last person in the queue purchases the ticket. Using this algorithm, the CPU process works in a similar manner.

How FCFS Works? Calculating Average Waiting Time

Here is an example of five processes arriving at different times. Each process has a different burst time.

Process	Burst time	Arrival time
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Using the FCFS scheduling algorithm, these processes are handled as follows.

Step 0) The process begins with P4 which has arrival time 0

Step 1) At time=1, P3 arrives. P4 is still executing. Hence, P3 is kept in a queue.

Process	Burst time	Arrival time
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Step 2) At time= 2, P1 arrives which is kept in the queue.

Process	Burst time	Arrival time
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Step 3) At time=3, P4 process completes its execution.

Step 4) At time=4, P3, which is first in the queue, starts execution.

Process	Burst time	Arrival time
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Step 5) At time =5, P2 arrives, and it is kept in a queue.

Process	Burst time	Arrival time
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Step 6) At time 11, P3 completes its execution.

Step 7) At time=11, P1 starts execution. It has a burst time of 6. It completes execution at time interval 17

Step 8) At time=17, P5 starts execution. It has a burst time of 4. It completes execution at time=21

Step 9) At time=21, P2 starts execution. It has a burst time of 2. It completes execution at time interval 23

Step 10) Let’s calculate the average waiting time for above example.

First-Come, First-Served (FCFS)

Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия — First Come, First Served (первым пришел, первым обслужен). Представим себе, что процессы, находящиеся в состоянии готовность, организованы в очередь. Когда процесс переходит в состояние готовность, он, а точнее ссылка на его PCB, помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его PCB. Очередь подобного типа имеет в программировании специальное наименование FIFO — сокращение от First In, First Out (первым вошел, первым вышел). Процесс, получивший в свое распоряжение процессор, занимает его до истечения своего текущего CPU burst. После этого для выполнения выбирается новый процесс из начала очереди.

Процесс	p0	p1	p2
Продолжительность очередного CPU burst

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

Пусть в состоянии готовность находятся три процесса p₀, p₁ и p₂, для которых известны времена их очередных CPU burst. Эти времена приведены в таблице 8.1. в некоторых условных единицах. Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst, что процессы не совершают операций ввода-вывода, и что время переключения контекста пренебрежимо мало.

Round Robin (RR)

Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin – это вид детской карусели в США) или сокращенно RR. По сути дела это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически — процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 — 100 миллисекунд (см. рисунок 8.4.). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.

Рис 8.4. Процессы на карусели.

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

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

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

30. Алгоритм планирования Shortest-Job-First (SJF).

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

Рассмотрим пример работы невытесняющего алгоритма SJF. Пусть в состоянии готовность находятся четыре процесса p₀, p₁, p₂ и p₃, для которых известны времена их очередных CPU burst. Эти времена приведены в таблице 8.4. Как и прежде, будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst, что процессы не совершают операций ввода-вывода, и что время переключения контекста пренебрежимо мало.

Процесс	p0	p1	p2	p3
Продолжительность очередного CPU burst

При использовании невытесняющего алгоритма SJF первым для исполнения будет выбран процесс p₃, имеющий наименьшее значение очередного CPU burst. После его завершения для исполнения выбирается процесс p₁, затем p₀ и, наконец, p₂. Вся эта картина изображена в таблице 8.5.

время

p0

Г

Г

Г

Г

И

И

И

И

И

p1

Г

И

И

И

p2

Г

Г

Г

Г

Г

Г

Г

Г

Г

И

И

И

И

И

И

И

p3

И

Как видим, среднее время ожидания для алгоритма SJF составляет (4 + 1 + 9 + 0)/4 = 3,5 единицы времени. Легко посчитать, что для алгоритма FCFS при порядке процессов p₀, p₁, p₂, p₃ эта величина будет равняться (0 + 5 + 8 + 15)/4 = 7 единицам времени, т. е. будет в 2 раза больше, чем для алгоритма SJF. Можно показать, что для заданного набора процессов (если в очереди не появляются новые процессы) алгоритм SJF является оптимальным с точки зрения минимизации среднего времени ожидания среди класса всех невытесняющих алгоритмов.

Для рассмотрения примера вытесняющего SJF планирования мы возьмем ряд процессов p₀, p₁, p₂ и p₃с различными временами CPU burst и различными моментами их появления в очереди процессов готовых к исполнению (см. таблицу 8.6.).

Процесс	Время появления в очереди	Продолжительность очередного CPU burst
p0
p1
p2
p3

В начальный момент времени в состоянии готовность находятся только два процесса p₀ и p₄. Меньшее время очередного CPU burst оказывается у процесса p₃, поэтому он и выбирается для исполнения (см. таблицу 8.7.). По прошествии 2-х единиц времени в систему поступает процесс p₁. Время его CPU burst меньше, чем остаток CPU burst у процесса p₃, который вытесняется из состояния исполнение и переводится в состояние готовность. По прошествии еще 2-х единиц времени процесс p₁ завершается, и для исполнения вновь выбирается процесс p₃. В момент времени t = 6 в очереди процессов готовых к исполнению появляется процесс p₂, но поскольку ему для работы нужно 7 единиц времени, а процессу p₃осталось трудиться всего 2 единицы времени, то процесс p₃ остается в состоянии исполнение. После его завершения в момент времени t = 7 в очереди находятся процессы p₀ и p₂, из которых выбирается процесс p₀. Наконец, последним получит возможность выполняться процесс p₂.

время
p0	Г	Г	Г	Г	Г	Г	Г	И	И	И
p1	И	И
p2	Г	Г	Г	Г
p3	И	И	Г	Г	И	И	И

время
p0	И	И	И
p1
p2
p3	Г	Г	Г	И	И	И	И	И	И	И

Основную сложность при реализации алгоритма SJF представляет невозможность точного знания времени очередного CPU burst для исполняющихся процессов. В пакетных системах количество процессорного времени, требующееся заданию для выполнения, указывает пользователь при формировании задания. Мы можем брать эту величину для осуществления долгосрочного SJF планирования. Если пользователь укажет больше времени, чем ему нужно, он будет ждать получения результата дольше, чем мог бы, так как задание будет загружено в систему позже. Если же он укажет меньшее количество времени, задача может не досчитаться до конца. Таким образом, в пакетных системах решение задачи оценки времени использования процессора перекладывается на плечи пользователя. При краткосрочном планировании мы можем делать только прогноз длительности следующего CPU burst, исходя из предыстории работы процесса. Пусть (n) – величина n -го CPU burst, T(n + 1)– предсказываемое значение для n + 1-го CPU burst,  – некоторая величина в диапазоне от 0 до 1.

Определим рекуррентное соотношение

T(0) положим произвольной константой. Первое слагаемое учитывает последнее поведение процесса, тогда как второе слагаемое учитывает его предысторию. При  = 0 мы перестаем следить за последним поведением процесса, фактически полагая

т.е. оценивая все CPU burst одинаково, исходя из некоторого начального предположения.

Положив  = 1, мы забываем о предыстории процесса. В этом случае мы полагаем, что время очередного CPU burst будет совпадать со временем последнего CPU burst:

для равноценного учета последнего поведения и предыстории. Надо отметить, что такой выбор  удобен и для быстрой организации вычисления оценки T(n + 1). Для подсчета новой оценки нужно взять старую оценку, сложить с измеренным временем CPU burst и полученную сумму разделить на 2, например, с помощью ее сдвига на 1 бит вправо. Полученные оценки T(n + 1) применяются как продолжительности очередных промежутков времени непрерывного использования процессора для краткосрочного SJF планирования.

31. Алгоритм планирования «Гарантированное планирование».

При интерактивной работе  пользователей в вычислительной системе можно применить алгоритм планирования, который гарантирует, что каждый из пользователей будет иметь в своем распоряжении  часть процессорного времени. Пронумеруем всех пользователей от  до . Для каждого пользователя с номером i введем две величины: _i — время нахождения пользователя в системе, или, другими словами длительность сеанса его общения с машиной, и _i — суммарное процессорное время уже выделенное всем его процессам в течение сеанса. Справедливым для пользователя было бы получение _i/ процессорного времени. Если

то i — й пользователь несправедливо обделен процессорным временем. Если же

то система явно благоволит к пользователю с номером i. Вычислим для каждого пользовательского процесса значение коэффициента справедливости

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

32. Приоритетное планирование.

Приоритетное планирование

Алгоритмы SJF и гарантированного планирования представляют собой частные случаи приоритетного планирования. При приоритетном планировании каждому процессу присваивается определенное числовое значение — приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS. Для алгоритма SJF в качестве такого приоритета выступает оценка продолжительности следующего CPU burst. Чем меньше значение этой оценки, тем более высокий приоритет имеет процесс. Для алгоритма гарантированного планирования приоритетом служит вычисленный коэффициент справедливости. Чем он меньше, тем больше приоритет у процесса.

Принципы назначения приоритетов могут опираться как на внутренние критерии вычислительной системы, так и на внешние по отношению к ней. Внутренние используют различные количественные и качественные характеристики процесса для вычисления его приоритета. Это могут быть, например, определенные ограничения по времени использования процессора, требования к размеру памяти, число открытых файлов и используемых устройств ввода-вывода, отношение средних продолжительностей I/O burst к CPU burst и т. д. Внешние критерии исходят из таких параметров, как важность процесса для достижения каких-либо целей, стоимость оплаченного процессорного времени и других политических факторов. Высокий внешний приоритет может быть присвоен задаче лектора или того, кто заплатил $100 за работу в течение одного часа.

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

Пусть в очередь процессов, находящихся в состоянии готовность, поступают те же процессы, что и в примере из параграфа 8.5.3. для вытесняющего алгоритма SJF, только им дополнительно еще присвоены приоритеты (см. таблицу 8.8.). В вычислительных системах не существует определенного соглашения, какое значение приоритета — 1 или 4 считать более приоритетным. Во избежание путаницы, во всех наших примерах мы будем предполагать, что большее значение соответствует меньшему приоритету, т.е. наиболее приоритетным в нашем примере является процесс p₃, а наименее приоритетным — процесс p₀.

Процесс	Время появления в очереди	Продолжительность очередного CPU burst	Приоритет
p0
p1
p2
p3

Как будут вести себя процессы при использовании невытесняющего приоритетного планирования? Первым для выполнения в момент времени t = 0 выбирается процесс p₃, как обладающий наивысшим приоритетом. После его завершения в момент времени t = 5 в очереди процессов готовых к исполнению окажутся два процесса p₀ и p₁. Больший приоритет из них у процесса p₁ он и начнет выполняться (см. таблицу 8.9.). Затем в момент времени t = 8 для исполнения будет избран процесс p₂ и лишь потом процесс p₀.

время
p0	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г
p1	Г	Г	Г	И	И
p2	Г	И	И	И
p3	И	И	И	И	И

время
p0	Г	Г	Г	Г	И	И	И	И	И	И
p1
p2	И	И	И	И
p3

Иным будет предоставление процессора процессам в случае вытесняющего приоритетного планирования (см. таблицу 8.10.). Первым, как и в предыдущем случае, исполняться начнет процесс p₃, а по его окончании процесс p₁. Однако в момент времени t = 6 он будет вытеснен процессом p₂ и продолжит свое выполнение только в момент времени t = 13. Последним, как и раньше будет исполнен процесс p₀.

время
p0	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г
p1	Г	Г	Г	И	Г	Г	Г	Г
p2	И	И	И	И
p3	И	И	И	И	И

время
p0	Г	Г	Г	Г	И	И	И	И	И	И
p1	Г	Г	Г	И
p2	И	И	И
p3

В рассмотренном выше примере приоритеты процессов не изменялись с течением временем. Такие приоритеты принято называть статическими. Механизмы статической приоритетности легко реализовать, и они сопряжены с относительно небольшими издержками на выбор наиболее приоритетного процесса. Однако статические приоритеты не реагируют на изменения ситуации в вычислительной системе, которые могут сделать желательной корректировку порядка исполнения процессов. Более гибкими являются динамические приоритеты процессов, изменяющие свои значения по ходу исполнения процессов. Начальное значение динамического приоритета, присвоенное процессу, действует в течение лишь короткого периода времени, после чего ему назначается новое, более подходящее значение. Изменение динамического приоритета процесса является единственной операцией над процессами, которую мы до сих пор не рассмотрели. Как правило, изменение приоритета процессов проводится согласованно с совершением каких-либо других операций: при рождении нового процесса, при разблокировке или блокировании процесса, по истечении определенного кванта времени или по завершении процесса. Примерами алгоритмов с динамическими приоритетами являются алгоритм SJF и алгоритм гарантированного планирования. Схемы с динамической приоритетностью гораздо сложнее в реализации и связанны с большими издержками по сравнению со статическими схемами. Однако их использование предполагает, что эти издержки оправдываются улучшением поведения системы.

Главная проблема приоритетного планирования заключается в том, что при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут быть не запущены неопределенно долгое время. Обычно случается одно из двух. Или они все же дожидаются своей очереди на исполнение (в девять часов утра в воскресенье, когда все приличные программисты ложатся спать). Или вычислительную систему приходится выключать, и они теряются (при остановке IBM 7094 в Массачусетском технологическом институте в 1973 году были найдены процессы, запущенные в 1967 году и ни разу с тех пор не исполнявшиеся). Решение этой проблемы может быть достигнуто с помощью увеличения со временем значения приоритета процесса, находящегося в состоянии готовность. Пусть изначально процессам присваиваются приоритеты от 128 до 255. Каждый раз, по истечении определенного промежутка времени, значения приоритетов готовых процессов уменьшаются на 1. Процессу, побывавшему в состоянии исполнение, восстанавливается первоначальное значение приоритета. Даже такая грубая схема гарантирует, что любому процессу в разумные сроки будет предоставлено право на исполнение.