Учебники

22) Упреждающий против Не вытесняющий

Декабрь 1, 2019

What is Preemptive Scheduling?

Preemptive Scheduling is a scheduling method where the tasks are mostly assigned with their priorities. Sometimes it is important to run a task with a higher priority before another lower priority task, even if the lower priority task is still running.

At that time, the lower priority task holds for some time and resumes when the higher priority task finishes its execution.

In this Operating system tutorial, you will learn:

What is Non- Preemptive Scheduling?

In this type of scheduling method, the CPU has been allocated to a specific process. The process that keeps the CPU busy will release the CPU either by switching context or terminating.

It is the only method that can be used for various hardware platforms. That’s because it doesn’t need specialized hardware (for example, a timer) like preemptive Scheduling.

Non-Preemptive Scheduling occurs when a process voluntarily enters the wait state or terminates.

Difference Between Preemptive and Non-Preemptive Scheduling in OS

Here, are Preemptive and Non-Preemptive Scheduling in OS

Preemptive Scheduling Non-preemptive Scheduling
A processor can be preempted to execute the different processes in the middle of any current process execution. Once the processor starts its execution, it must finish it before executing the other. It can’t be paused in the middle.
CPU utilization is more efficient compared to Non-Preemptive Scheduling. CPU utilization is less efficient compared to preemptive Scheduling.
Waiting and response time of preemptive Scheduling is less. Waiting and response time of the non-preemptive Scheduling method is higher.
Preemptive Scheduling is prioritized. The highest priority process is a process that is currently utilized. When any process enters the state of running, the state of that process is never deleted from the scheduler until it finishes its job.
Preemptive Scheduling is flexible. Non-preemptive Scheduling is rigid.
Examples: — Shortest Remaining Time First, Round Robin, etc. Examples: First Come First Serve, Shortest Job First, Priority Scheduling, etc.
Preemptive Scheduling algorithm can be pre-empted that is the process can be Scheduled In non-preemptive scheduling process cannot be Scheduled
In this process, the CPU is allocated to the processes for a specific time period. In this process, CPU is allocated to the process until it terminates or switches to the waiting state.
Preemptive algorithm has the overhead of switching the process from the ready state to the running state and vice-versa. Non-preemptive Scheduling has no such overhead of switching the process from running into the ready state.

Advantages of Preemptive Scheduling

Here, are pros/benefits of Preemptive Scheduling method:

  • Preemptive scheduling method is more robust, approach so one process cannot monopolize the CPU
  • Choice of running task reconsidered after each interruption.
  • Each event cause interruption of running tasks
  • The OS makes sure that CPU usage is the same by all running process.
  • In this, the usage of CPU is the same, i.e., all the running processes will make use of CPU equally.
  • This scheduling method also improvises the average response time.
  • Preemptive Scheduling is beneficial when we use it for the multi-programming environment.

Advantages of Non-preemptive Scheduling

Here, are pros/benefits of Non-preemptive Scheduling method:

  • Offers low scheduling overhead
  • Tends to offer high throughput
  • It is conceptually very simple method
  • Less computational resources need for Scheduling

Disadvantages of Preemptive Scheduling

Here, are cons/drawback of Preemptive Scheduling method:

  • Need limited computational resources for Scheduling
  • Takes a higher time by the scheduler to suspend the running task, switch the context, and dispatch the new incoming task.
  • The process which has low priority needs to wait for a longer time if some high priority processes arrive continuously.

Disadvantages of Non-Preemptive Scheduling

Here, are cons/drawback of Non-Preemptive Scheduling method:

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

Пример не вытесняющего планирования

При неперегрузочном планировании SJF, когда цикл ЦП выделен для обработки, процесс удерживает его, пока не достигнет состояния ожидания или не завершится.

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

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

Шаг 0) Во время = 0, P4 прибывает и начинает выполнение.

Шаг 1) В момент времени = 1 приходит процесс P3. Но P4 по-прежнему нужно 2 исполнительных блока для завершения. Это продолжит исполнение.

Шаг 2) В момент времени = 2, процесс P1 прибывает и добавляется в очередь ожидания. P4 продолжит исполнение.

Шаг 3) В момент времени = 3 процесс P4 завершит свое выполнение. Время всплеска P3 и P1 сравнивается. Процесс P1 выполняется, потому что его время пакета меньше по сравнению с P3.

Шаг 4) В момент времени = 4, процесс P5 прибывает и добавляется в очередь ожидания. P1 продолжит выполнение.

Шаг 5) Во время = 5, процесс P2 прибывает и добавляется в очередь ожидания. P1 продолжит выполнение.

Шаг 6) В момент времени = 9 процесс P1 завершит свое выполнение. Время всплеска P3, P5 и P2 сравнивается. Процесс P2 выполняется, потому что его время пакета является самым низким.

Шаг 7) В момент времени = 10 выполняется P2, а P3 и P5 находятся в очереди ожидания.

Шаг 8) В момент времени = 11 процесс P2 завершит свое выполнение. Время всплеска P3 и P5 сравнивается. Процесс P5 выполняется, потому что его время пакета меньше.

Шаг 9) В момент времени 15 процесс P5 завершит свое выполнение.

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

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

Время ожидания 
P4 = 0-0 = 0
P1 = 3-2 = 1
P2 = 9-5 = 4
P5 = 11-4 = 7
P3 = 15-1 = 14
Среднее время ожидания = 0 + 1 + 4 + 7 + 14/5 = 26/5 = 5,2

Пример упреждающего планирования

Рассмотрим это после трех процессов в циклическом

Очередь процессов Время взрыва
P1 4
P2 3
P3 5

Шаг 1) Выполнение начинается с процесса P1, который имеет время пакета 4. Здесь каждый процесс выполняется в течение 2 секунд. P2 и P3 все еще находятся в очереди ожидания.

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

Шаг 3) В момент времени = 4 P2 выгружается и добавляется в конец очереди. P3 начинает выполнение.

Шаг 4) В момент времени = 6 P3 выгружается и добавляется в конец очереди. P1 начинает выполнение.

Шаг 5) В момент времени = 8 P1 имеет время пакета 4. Он завершил выполнение. P2 начинает выполнение

Шаг 6) У P2 есть время пакета 3. Это уже выполнено в течение 2 интервалов. В момент времени = 9 P2 завершает выполнение. Затем P3 начинает выполнение до его завершения.

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

Время ожидания 
P1 = 0+ 4 = 4
P2 = 2 + 4 = 6
P3 = 4 + 3 = 7

ОСНОВНЫЕ РАЗЛИЧИЯ

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

 

42
Share: