A workload consists of four processes arriving for System A at times 0, 2, 4, an

Question

A workload consists of four processes arriving for System A at times 0, 2, 4, and 6. These four processes have service times of 4, 8, 10 and 3, respectively. a) System A explores the use of two policies (FCFS and Round-Robin) to schedule these processes. Can you draw the Gantt Charts for these processes under the two scheduling policies? Assume the time quantum is set at 2 time units for the Round-Robin policy. b) Can you also calculate these three metrics at the completion of all processes: average waiting time, average latency, and the system throughput?

Explanation / Answer

a)

First Let us draw the Gantt chart for First Come First Serve (FCFS) Algorithm.

The FCFS scheduler simply completes the execution of the processes in the order they are submitted.

In our question, there are four processes for system A. Let us name our four processes P1, P2, P3, and P4.

Let us tabulate the given data

The order of the processes P1, P2, P3, and P4 are 1, 2, 3, and 4 respectively. Because the arrival times of P1, P2, P3, and P4 are 0, 2, 4, and 6.

Now let us draw the Gantt Chart for FCFS for the above data

0 4 12 22 25

The process P1 arrives at time 0 and it has 4 units of service time, so P1 has completed its execution at time 4. But the process P2 has arrived at time 2, but during that time P1 is under execution. So P2 has to wait for the process P1 to complete. Once P1 has completed its execution, P2 starts its execution with service time 8 units. P2 completes its execution at 12 and the process P3 is already waiting because its arrival time is 4. Once P2 completes its execution P3 starts its execution with service time 10 units and finishes its execution at 22. Similarly, the last process P4 completes its execution at 25 with 3 units of service time.

Now Let us draw the Gantt Chart for Round-Robin (RR) Algorithm

RR is a preemptive scheduler, which is designed especially for time sharing systems. It does not wait for a process to complete its execution. In RR, each process is given a slot called time quantum to run the process.

In our example, the time slot or time quantum is 2. so every process runs for 2 units of time and comes out. when all the processes complete their execution with 2 units of time in the order in which they have come, they start executing the same processes in the same order for the time slot of 2 units. This process is repeated until all the processes finish their execution.

Let us tabulate the given data

Time Quantum=2

Let us draw the Gantt Chart for the RR Scheduler

0 2 4 6 8 10 12 14 15 17 19 21 23 25

First P1 starts its execution and it executes for 2 units as the time quantum is 2. Later P2 starts its execution and executes for 2 units. Similarly, P3 and P4 execute for 2 units respectively. Once all the processes are completed their execution for 2 units they start executing in the same order again until they complete their execution for the given service time.

b)

The metrics for FCFS scheduler

waiting time of a process= finish time of that process - execution time - arrival time

For process P1 waiting time is 4-4-0 = 0

P2 waiting time is 12-8-2 = 2

P3 waiting time is 22-10-4 = 8

P4 waiting time is 25-3-6 = 16

so Average waiting time is (0+2+8+16)/4=6.5

The operating system incurs overhead each time it switches between processes due to context switching. we will call this overhead "cs"

Throughput=Number of processes/(Complete time of all the processes+number of context switches)

Throughput=4/(25+3cs)

The metrics for RR-scheduler

The Waiting times

P1=6, P2=11, P3=11, P4=6

Average Waiting time=(6+11+11+6)/4=8.5

Throughput=4/(25+12cs)

Process Service Time Order Arrival Time P1 4 1 0 P2 8 2 2 P3 10 3 4 P4 3 4 6

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.