CPU Scheduling Algorithm Non-Preemptive Analysis
CPU scheduling algorithms determine how processes are allocated to the CPU. A key distinction lies in whether the algorithm is preemptive or non-preemptive.
- Preemptive Scheduling: The operating system can interrupt a currently running process and allocate the CPU to another process (e.g., when a higher-priority process arrives or a time slice expires).
- Non-preemptive Scheduling: Once a process starts executing, it continues until it completes its CPU burst, voluntarily yields the CPU (e.g., for I/O), or terminates. It cannot be forcibly interrupted by the scheduler.
Algorithm Comparison
Let's analyze the given CPU scheduling algorithms:
- Shortest Remaining Time First (SRTF): This is a preemptive algorithm. If a new process arrives with a CPU burst length less than the remaining time of the currently executing process, the current process is preempted.
- First Come First Serve (FCFS): This is a non-preemptive algorithm. Processes are executed in the order of their arrival. Once a process begins execution, it runs to completion or until it blocks, without interruption based on arrival of other processes.
- Round Robin Scheduling: This is a preemptive algorithm. Each process is assigned a fixed time slice (quantum). If a process does not complete within its quantum, it is preempted and moved to the ready queue.
- Priority Scheduling: This algorithm can be implemented in both preemptive and non-preemptive modes. However, the fundamental nature of FCFS is strictly non-preemptive.
Conclusion
Based on the definitions, First Come First Serve (FCFS) is the CPU scheduling algorithm that inherently cannot be preemptive. It executes processes strictly in the order they arrive until completion or voluntary I/O blocking.
Important Questions from CPU Scheduling
Assume that the following tasks are to be executed on a single processor system. All tasks have arrived at 0 msec.
Job ID CPU a 4 b 1 c 7 d 2 How long does it take for task "a" to complete if the scheduling time slice is a round-robin with 1 ms?
- Consider the following processes with CPU Burst time P1, P2, P3 arrived at time 0.
Process CPU Burst Time (MS) P1 24 P2 3 P3 3
What is the average waiting time of these processes executed using FCFS algorithm. Consider the following table about processes, their burst time and arrival time
Process Burst Time Arrival Time P1 09 0 P2 30 0 P3 04 0 P4 08 2 P5 11 6
Now which of the process shall finish second last as per the respective GANTT charts for the non- preemptive SJF and Round Robin (time quantum = 10) scheduling methods.- A computer has two processors, $M_1$ and $M_2$. Four processes $P_1, P_2, P_3, P_4$ with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows:
- $M_1$ uses priority of execution for the processes as, $P_1 > P_3 > P_2 > P_4$, i.e., $P_1$ and $P_4$ have highest and lowest priorities, respectively.
- $M_2$ uses priority of execution for the processes as, $P_2 > P_3 > P_4 > P_1$, i.e., $P_2$ and $P_1$ have highest and lowest priorities, respectively.
- Processes $P_1, P_2, P_3, P_4$ arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively.
Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times.
Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?
