FCFS Process Execution Trace
The First Come First Serve (FCFS) scheduling policy processes tasks strictly in the order of their arrival. This scenario involves two types of processes: Actuators (A) with a CPU burst of 6 seconds and Controllers (C) with a CPU burst of 8 seconds. New processes of type A arrive at $t=10, 20, 30, 40, 50$, and type C at $t=11, 22, 33, 44, 55$. The first process of type A begins execution at $t=10$.
We track the start and completion times for each process to determine waiting times.
| Process | Arrival Time ($t_a$) | Burst Time ($t_b$) | Start Time ($t_s$) | Completion Time ($t_c$) | Waiting Time ($t_w$) |
|---|---|---|---|---|---|
| A1 | 10 | 6 | 10 | 16 | 0 |
| C1 | 11 | 8 | 16 | 24 | 5 |
| A2 | 20 | 6 | 24 | 30 | 4 |
| C2 | 22 | 8 | 30 | 38 | 8 |
| A3 | 30 | 6 | 38 | 44 | 8 |
| C3 | 33 | 8 | 44 | 52 | 11 |
| A4 | 40 | 6 | 52 | 58 | 12 |
| C4 | 44 | 8 | 58 | 66 | 14 |
| A5 | 50 | 6 | 66 | 72 | 16 |
| C5 | 55 | 8 | 72 | 80 | 17 |
Waiting Time Calculation
The waiting time ($t_w$) for each process is calculated using the formula: $t_w = t_s - t_a$, where $t_s$ is the start time and $t_a$ is the arrival time.
The individual waiting times are listed in the table above.
To find the average waiting time, we sum the waiting times of all 10 processes:
$ \text{Total Waiting Time} = 0 + 5 + 4 + 8 + 8 + 11 + 12 + 14 + 16 + 17 = 95 \text{ seconds} $
There are 10 processes in total. The average waiting time is computed as:
$ \text{Average Waiting Time} = \frac{\text{Total Waiting Time}}{\text{Number of Processes}} = \frac{95}{10} = 9.5 \text{ seconds} $
The average waiting time for the 10 processes is 9.5 seconds, rounded to one decimal place.
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?
