Tech Taleem Logo

Pre-Emptive Scheduling

In Pre-emptive Scheduling if a process enters the ready state and it is high priority process the current process can be interrupted or stopped. It means that if a high priority process arrives than the CPU leave the current interrupt and goes to the high priority process. The CPU can be given to the high priority process. A process can also switches from running state to ready state because its time to quantum expire. In pre-emptive scheduling, the CPU can be taken only from a running process forcibly. The operating system interrupt the process before it complete execution. It means that in pre-emptive scheduling, the operating system can stop the running process before it finishes it and give the CPU to another process. It is happens when a high priority process arrives. The stopped process can executed be later again. There are four most important types of pre-emptive scheduling are given below.

Types of Pre-Emptive Scheduling

Real Life Example

Suppose you are listening to music on your mobile phone. When a call comes, the music stops, the phone handles the call first. It means that call has a higher priority for the CPU than the music.

Examples of Pre-Emptive Scheduling Algorithm

  • Round Robin
  • Shortest Remaining Time First
  • Longest Remaining Time First

Types of Pre-Emptive Scheduling

There are four most important types of Pre-Emptive Scheduling as given below.

i) Priority Scheduling

ii) Shortest Remaining Job First (SRJF)

iii) Longest Remaining Job First (LRJF)

iv) Round Robin (RR)

1. Priority Scheduling

Priority Scheduling is Pre-Emptive or Non Pre-Emptive Scheduling. In Priority Scheduling, a priority is associated with each process and the CPU is allocated to the process with the highest priority. It means that every process has a one priority. If both processes are priority are equal then the process that arrives first gets the CPU firsts ((FCFS). Priority can be represented by number and lower number have higher priority. All ready process enters in ready queue and CPU selects a process according to its priority.

Note: Priority scheduling may be pre-emptive or non pre-emptive scheduling.

Example

Suppose that there are three processes P1, P2, and P3 are a waiting for the CPU. there priorities are 3, 1 and 2 respectively. We know that a lower number has a higher priority. Therefore, P2 gets the CPU first because it has a higher priority. After P2, P3 gets the CPU and then P1.

Note: Execution Order: P2 → P3 → P1

2. Shortest Remaining Job First (SRJF)

SRJF stand for Shortest Remaining Job First ( SRJF). Shortest Remaining Job First is also called  Shortest Remaining Time First. SRJF is a type of pre-emptive scheduling. In Shortest Remaining Job First if a new process arrives with a shorter CPU burst time than the remaining time of the currently running process, the CPU switches to the new process. It means that in easy words we can say that in SRJF if a new process comes with less execution time than the OS stops current process and gives the CPU to the new process.

Note: SRJF is a type of pre-emptive scheduling and in process with the shorter remaining time.

Example

Suppose there are three processes P1, P2 and P3, arrive at different times. Their arrival time and burst time given below. Arrival time mean when does process arrive and burst time mean how much CPU time is required. So the data of arrival time and burst time given below.

Explanation

  • At time 0, P1 starts. At time 1 P2 arrives with a shorter time, so P1 stops and P2 start.
  • At time 2, P3 arrives with the shortest time, so P2 stops and P3 starts. P3 Finishes at time 4.
  • P2 starts again and finishes at time 7. Finally P1 starts again and finishes at time 14.

3. Longest Remaining Job First (LRJF)

LRJF stand for Longest Remaining Job First (LRJF). It is a type of Pre-Emptive Scheduling. LRJF is called as Longest Remaining Time First (LRTF). In this method, the CPU is assigned to available process that has longest remaining execution time. If another process has a longer remaining time, the CPU can switch to that process. It means that we can say that CPU those process which have a longest remaining execution time. If a new process arrives with a longer remaining time, the CPU can stop the current process and goes to the the new process. After see the new process the stopped process can continue later.

Note: LRJF is a type of pre-emptive scheduling and in process with the longest remaining time.

Example

Suppose there are three processes P1, P2 and P3, arrive at different times. Their arrival time and burst time given below. Arrival time mean when does process arrive and burst time mean how much CPU time is required. The CPU select the process with the longest remaining execution time. So the data of arrival time and burst time given below.

  • At time 0, P1 starts executing because it is only available process.
  • At time 1, P2 arrives. P1 has 7 units remaining, which is greater than P2’s 4 units, so P1 continues.
  • At time 2, P3 arrives, but P1 has the longest remaining time, so P1 continues. After P1 finishes, P2 runs, and then P3.

4. Round Robin (RR)

RR stand for Round Robin. Round Robin is an important type of preemptive CPU scheduling. It is also designed for time sharing system, where each process gets fixed amount of CPU time. If a process is not completed within this time, the CPU switches to the next process. The uncomplete process goes to the end of the queue and uses the CPU again when its turn comes. In this method, each process gets a fixed amount of CPU time called a time quantum.

Note: Round Robin (RR) is an important type of pre-emptive CPU scheduling algorithm.

Example

  • If a time quantum is five milliseconds, each process can use the CPU up to five milliseconds in one turn.