Using an example, let's illustrate how First-Come, First-Served (FCFS) process scheduling works in an operating system. We'll consider four processes, P1 to P4, each with its own arrival and burst times. We will then calculate the response, waiting, and turnaround times for each process and create a Gantt chart to visualize the scheduling.
Let's assume the following arrival and burst times for each process:
P1: Arrival Time = 0, Burst Time = 4
P2: Arrival Time = 1, Burst Time = 3
P3: Arrival Time = 2, Burst Time = 1
P4: Arrival Time = 3, Burst Time = 2
Step-by-Step Execution:
P1 arrives at time 0 and starts execution immediately since it's the first process. It runs for its entire burst time of 4 units.
P2 arrives at time 1, but it has to wait until P1 completes at time 4. P2 then starts executing and runs for 3 units.
P3 arrives at time 2, but waits for P1 and P2 to complete. P3 starts at time 7 and runs for 1 unit.
P4 arrives at time 3, but it waits for P1, P2, and P3 to complete. P4 starts at time 8 and runs for 2 units.
Calculating Times:
Response Time is the time from arrival to the first time the process gets the CPU.
Waiting Time is the total time the process has been in the ready queue.
Turnaround Time is the total time from arrival to completion.
For each process:
P1: Response = 0, Waiting = 0, Turnaround = Burst + Waiting = 4
P2: Response = 4 - 1 = 3, Waiting = 3, Turnaround = 3 + 3 = 6
P3: Response = 7 - 2 = 5, Waiting = 5, Turnaround = 1 + 5 = 6
P4: Response = 8 - 3 = 5, Waiting = 5, Turnaround = 2 + 5 = 7
Gantt Chart:
Time: 0 1 2 3 4 5 6 7 8 9 10
---------------------------------
Process: P1 P1 P1 P1 P2 P2 P2 P3 P4 P4
In this chart, you can see how each process occupies the CPU over time.
For the Shortest Job First (SJF) non-preemptive scheduling approach, we'll take a similar set of processes and schedule them based on their burst time, with the shortest jobs being executed first. Remember, in SJF, the next process to be executed is the one with the shortest burst time among the processes that have already arrived.
Given processes:
P1: Arrival Time = 5, Burst Time = 2
P2: Arrival Time = 3, Burst Time = 4
P3: Arrival Time = 5, Burst Time = 3
P4: Arrival Time = 3, Burst Time = 1
Step-by-Step Execution:
At time 3, both P2 and P4 have arrived. P4 has the shortest burst time (1 unit), so it is executed first.
After P4 completes at time 4, P2 is the only process available, so it runs next for its burst time of 4 units, completing at time 8.
At time 5, both P1 and P3 arrive. By the time P2 completes at time 8, P1 and P3 are waiting. P1 has the shortest burst time (2 units) among them, so it is executed next.
Finally, P3, with a burst time of 3 units, is executed last.
Calculating Times:
For each process:
P1: Response = 8 - 5 = 3, Waiting = 3, Turnaround = 2 + 3 = 5
P2: Response = 4 - 3 = 1, Waiting = 1, Turnaround = 4 + 1 = 5
P3: Response = 10 - 5 = 5, Waiting = 5, Turnaround = 3 + 5 = 8
P4: Response = 3 - 3 = 0, Waiting = 0, Turnaround = 1 + 0 = 1
Gantt Chart:
Time: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
--------------------------------------------
Process: P4 P2 P2 P2 P2 P1 P1 P3 P3 P3
This Gantt chart illustrates the SJF non-preemptive scheduling, where the shortest jobs are prioritized, leading to potentially improved average wait times compared to FCFS, especially for short jobs.
To illustrate the Shortest Remaining Time Next (SRTN) approach, which is a preemptive version of the Shortest Job First (SJF) scheduling, I'll define a new set of processes with arrival and burst times that are typical for demonstrating preemption and waiting scenarios.
Let's define the processes as follows:
P1: Arrival Time = 0, Burst Time = 8
P2: Arrival Time = 1, Burst Time = 4
P3: Arrival Time = 2, Burst Time = 2
P4: Arrival Time = 3, Burst Time = 1
Step-by-Step Execution:
P1 starts execution at time 0.
At time 1, P2 arrives with a burst time shorter than the remaining time of P1 (7 units). So, P1 is preempted and P2 starts executing.
At time 2, P3 arrives with an even shorter burst time. P2 is preempted and P3 starts executing.
At time 3, P4 arrives with the shortest burst time (1 unit). P3 is preempted and P4 starts executing.
P4 completes at time 4. Now, P3, with a remaining time of 1 unit, resumes execution.
At time 5, P3 completes. P2, with the next shortest remaining time (2 units), resumes.
At time 7, P2 completes. P1, the only remaining process, resumes and completes at time 15.
Calculating Times:
For each process:
P1: Response = 0, Waiting = 6, Turnaround = 8 + 6 = 14
P2: Response = 1 - 1 = 0, Waiting = 3, Turnaround = 4 + 3 = 7
P3: Response = 2 - 2 = 0, Waiting = 1, Turnaround = 2 + 1 = 3
P4: Response = 3 - 3 = 0, Waiting = 0, Turnaround = 1 + 0 = 1
Gantt Chart:
Time: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
----------------------------------------------------
Process: P1 P2 P3 P4 P3 P2 P2 P1 P1 P1 P1 P1 P1 P1 P1
This Gantt chart clearly shows the preemption and resumption of processes based on the shortest remaining time. Processes are frequently interrupted and resumed, prioritizing those with the least amount of time left to execute. This approach can significantly reduce waiting time for shorter processes but can lead to longer waiting times for longer processes, as seen in the example.
For Priority Scheduling (non-preemptive), where a lower priority number means higher priority, the arrival, burst times, and priorities for the processes are as follows:
P1: Arrival Time = 3, Burst Time = 1, Priority = 3
P2: Arrival Time = 1, Burst Time = 1, Priority = 1
P3: Arrival Time = 5, Burst Time = 4, Priority = 2
P4: Arrival Time = 2, Burst Time = 2, Priority = 1
Step-by-Step Execution:
At time 1, P2 is the only process that has arrived and it has the highest priority. So, P2 starts executing.
At time 2, P4 arrives and it also has high priority (same as P2). However, since Priority Scheduling is non-preemptive in this case, P2 continues until it completes at time 2.
Now, both P1 (priority 3) and P4 (priority 1) are ready. P4 with the higher priority executes next.
P4 completes at time 4. Now, P1 is the next in line based on its arrival time and priority.
P1 completes at time 5. Finally, P3 arrives at time 5 and starts executing as it's the only process left.
P3 completes at time 9.
Calculating Times:
For each process:
P1: Response = 4 - 3 = 1, Waiting = 1, Turnaround = 1 + 1 = 2
P2: Response = 1 - 1 = 0, Waiting = 0, Turnaround = 1 + 0 = 1
P3: Response = 5 - 5 = 0, Waiting = 0, Turnaround = 4 + 0 = 4
P4: Response = 2 - 2 = 0, Waiting = 0, Turnaround = 2 + 0 = 2
Gantt Chart:
Time: 0 1 2 3 4 5 6 7 8 9
----------------------------
Process: P2 P4 P4 P1 P3 P3 P3 P3
In this Gantt chart, the execution sequence is based on the priorities of the processes, with interruptions occurring only when a process with a higher priority arrives and the currently executing process completes. Priority scheduling can lead to improved response times for high-priority processes but might result in longer waiting times for low-priority processes.
For Priority Scheduling (preemptive), where a lower priority number means higher priority, the arrival, burst times, and priorities for the processes are as follows, with typical values conducive to preemption and waiting scenarios:
P1: Arrival Time = 0, Burst Time = 4, Priority = 3
P2: Arrival Time = 1, Burst Time = 6, Priority = 1
P3: Arrival Time = 1, Burst Time = 3, Priority = 2
P4: Arrival Time = 0, Burst Time = 4, Priority = 3
Step-by-Step Execution:
At time 0, both P1 and P4 arrive. They have the same priority, so let's assume P1 starts executing (arbitrarily chosen).
At time 1, P2 and P3 arrive. P2 has the highest priority, so it preempts P1 and starts executing.
P2 continues to execute as it has the highest priority among all available processes.
Once P2 completes at time 7, P3, having the next highest priority, starts executing.
P3 completes at time 10. Now, either P1 or P4 resumes (both have equal priority and remaining burst time). Let's assume P1 resumes.
P1 completes at time 14, and finally, P4 executes and completes at time 18.
Calculating Times:
For each process:
P1: Response = 0, Waiting = 9, Turnaround = 4 + 9 = 13
P2: Response = 1 - 1 = 0, Waiting = 0, Turnaround = 6 + 0 = 6
P3: Response = 7 - 1 = 6, Waiting = 6, Turnaround = 3 + 6 = 9
P4: Response = 14 - 0 = 14, Waiting = 14, Turnaround = 4 + 14 = 18
Gantt Chart:
Time: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
----------------------------------------------------------------
Process: P1 P2 P2 P2 P2 P2 P2 P3 P3 P3 P1 P1 P1 P1 P4 P4 P4 P4
This Gantt chart illustrates the preemptive nature of Priority Scheduling. Processes are frequently interrupted and resumed based on their priority, leading to improved response times for higher priority processes but potentially longer waiting times for lower priority ones.
For round-robin scheduling with a time quantum of 2, the arrival and burst times for the processes are as follows:
P1: Arrival Time = 2, Burst Time = 5
P2: Arrival Time = 0, Burst Time = 3
P3: Arrival Time = 0, Burst Time = 2
P4: Arrival Time = 3, Burst Time = 3
We will also maintain and show the ready queue, and prioritize newly arrived processes over processes whose time slice has just run out to improve response time.
Round Robin Execution:
Initial State: P2 and P3 arrive at time 0. They are added to the ready queue. (Queue: P2, P3)
Time 0-2: P2 executes for 2 units. (Remaining Burst Time: P2 - 1). P2 goes to the end of the queue. (Queue: P3, P2)
Time 2-4: P3 executes for 2 units and completes (Remaining Burst Time: P3 - 0). P1 arrives at time 2 and is added to the queue. (Queue: P2, P1)
Time 4-5: P2 executes for 1 unit and completes (Remaining Burst Time: P2 - 0). P4 arrives at time 3 and is added to the queue. (Queue: P1, P4)
Time 5-7: P1 executes for 2 units. (Remaining Burst Time: P1 - 3). P1 goes to the end of the queue. (Queue: P4, P1)
Time 7-9: P4 executes for 2 units. (Remaining Burst Time: P4 - 1). P4 goes to the end of the queue. (Queue: P1, P4)
Time 9-11: P1 executes for 2 units. (Remaining Burst Time: P1 - 1). P1 goes to the end of the queue. (Queue: P4, P1)
Time 11-12: P4 executes for 1 unit and completes (Remaining Burst Time: P4 - 0). (Queue: P1)
Time 12-13: P1 executes for 1 unit and completes (Remaining Burst Time: P1 - 0).
Calculating Times:
P1: Response = First Execution - Arrival = 5 - 2 = 3, Waiting = 6, Turnaround = Waiting + Burst = 6 + 5 = 11
P2: Response = 0, Waiting = 2, Turnaround = 2 + 3 = 5
P3: Response = 0, Waiting = 0, Turnaround = 2
P4: Response = 7 - 3 = 4, Waiting = 2, Turnaround = 2 + 3 = 5
Gantt Chart:
Time: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
--------------------------------------------
Process: P2 P2 P3 P3 P2 P1 P1 P4 P4 P1 P1 P4 P1
In this Gantt chart and the accompanying description, we can see how Round Robin scheduling works with a time quantum of 2, prioritizing newly arrived processes, and placing processes at the end of the queue when their time slice runs out. The waiting time for each process includes the time spent in the ready queue.