Process CPU Burst Time (MS) P1 24 P2 3 P3 3
What is the average waiting time of these processes executed using FCFS algorithm.
FCFS Algorithm Explanation
The First-Come, First-Served (FCFS) scheduling algorithm is the simplest CPU scheduling method. In this method, processes are executed in the order they arrive in the ready queue. Once a process starts executing, it continues until it completes or voluntarily relinquishes the CPU.
Process Details and Arrival
We have three processes: P1, P2, and P3. All of them arrived at the same time (time 0). Their respective CPU burst times are given:
| Process | CPU Burst Time (ms) |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
FCFS Execution Order
Since all processes arrived at time 0, they are processed based on their arrival sequence, which is P1, followed by P2, and then P3.
- P1 starts first.
- P2 starts after P1 finishes.
- P3 starts after P2 finishes.
Calculating Waiting Times
The waiting time for a process is the total time it spends waiting in the ready queue before it gets the CPU. For FCFS, when all arrive at time 0:
- Waiting Time for P1: P1 is the first process, so it starts executing immediately. Its waiting time is 0 ms.
Using the formula: Waiting Time = Turnaround Time - Burst Time. Turnaround Time = Completion Time - Arrival Time. Since Arrival Time is 0, Turnaround Time = Completion Time.
Completion Time (P1) = Burst Time (P1) = 24 ms.
Waiting Time (P1) = 24 ms - 24 ms = 0 ms.
- Waiting Time for P2: P2 has to wait for P1 to complete its execution. P1's burst time is 24 ms. So, P2 starts at 24 ms.
Completion Time (P2) = Completion Time (P1) + Burst Time (P2) = 24 ms + 3 ms = 27 ms.
Waiting Time (P2) = Completion Time (P2) - Burst Time (P2) = 27 ms - 3 ms = 24 ms.
- Waiting Time for P3: P3 has to wait for both P1 and P2 to complete. P2 completes at 27 ms. So, P3 starts at 27 ms.
Completion Time (P3) = Completion Time (P2) + Burst Time (P3) = 27 ms + 3 ms = 30 ms.
Waiting Time (P3) = Completion Time (P3) - Burst Time (P3) = 30 ms - 3 ms = 27 ms.
Average Waiting Time Calculation
To find the average waiting time, we sum the waiting times of all processes and divide by the total number of processes.
Total Waiting Time = Waiting Time (P1) + Waiting Time (P2) + Waiting Time (P3)
Total Waiting Time = 0 ms + 24 ms + 27 ms = 51 ms.
Number of Processes = 3.
Average Waiting Time = Total Waiting Time / Number of Processes
Average Waiting Time = $ \frac{51 \text{ ms}}{3} $
Average Waiting Time = $ 17 \text{ ms} $.
Therefore, the average waiting time for these processes using the FCFS algorithm is 17 ms.
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 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? - Consider a CPU that has to execute two types of processes. The first type, Actuators (A), requires a CPU burst of 6 seconds. The second type, Controllers (C), requires a CPU burst of 8 seconds. A new process of type A arrives at time $t = 10$, 20, 30, 40, and 50 (in seconds). Similarly, a new process of type C arrives at time $t = 11$, 22, 33, 44, and 55 (in seconds). The CPU scheduling policy is First Come First Serve (FCFS). The first process of type A starts running at $t = 10$ seconds. The average waiting time (in seconds) for the 10 processes is ___________. (rounded off to one decimal place)
