Operating System Test 2

Shortest job first scheduling algorithm uses min heap data structure for its implementation. 

If there are n tasks and each task has to be inserted to the heap and later extracted from the heap, it results in a running time of O(nlogn).

Therefore, Shortest job first scheduling algorithm uses min heap data structure and has O(nlogn) time complexity.​

Data:

7^th burst time = t7 = 8 ms

\({\tau _7}\) = 6

α = 0.7

Formula:

\({\tau _{n + 1}} = \;\alpha {t_n} + \left( {1 - \alpha } \right){\tau _n}\)

Calculation:

\({\tau _8}\) = 0.7(8) + (0.3)6

\({\tau _8}\) = 5.6 + 1.8 = 7.4 ms

The performance of the Round Robin algorithm depends heavily on the size of the time quantum.

• If time quantum is too large, RR reduces to the FCFS algorithm.
• If time quantum is too small, overhead increases due to the amount of context switching needed.

Round robin scheduling algorithm is designed especially for time-sharing systems

Average waiting is Shortest remaining time first is always less than or equal to round robin scheduling algorithm. Therefore option 4 is not true.

Scheduling Algorithm: Shortest Remaining Time First

Gantt chart:

0          3            7           8           10          13        21

Process Table:

Average turnaround time = \(\frac{{21 + 7 + 1 + 5}}{4} = 8.5\)

Average waiting time = \(\frac{{10 + 1 + 0 + 2}}{4} = 3.25\)

| 8.5 - 3.25 | = 5.25

Important Points:

TAT = CT - AT

WT = TAT - BT

Gantt chart:

0             3             5            X+5        X+6

Process table:

Average waiting time = \(\frac{X -1 }{4} = \frac{3}{4}\)

X - 1 = 3

∴ X = 4 ms

Important Points:

TAT = CT – AT

WT = TAT – BT 

Switching the CPU to another process requires performing a state save of the current process and a state restore of a different process. This task is known as a context switch. When a context switch occurs, the kernel saves the context of the old process in its PCB and loads the saved context of the new process scheduled to run. Context-switch time is pure overhead, because the system does no useful work while switching.

Gantt chart for above process:

 Here, total 4 context switch occur. From process P1 to P2, from process P2 to P1, from process P1 to P4  and from P4 to P3. 

Scheduling Algorithm: Round-Robin

Time Quantum: 4 milliseconds

Gantt chart:

0 4 8 12 16 17 20 22

Process Table:

the average waiting time = \(\frac{12+13+16+12}{4} = 13.25\)

Formula used:

TAT = CT – AT

WT = TAT – BT

AT: ARRIVAL TIME

CT:    COMPLETION TIME

TAT:  TURN AROUND TIME

WT:    WAITING TIME

BT:     BURST TIME(CPU TIME)

GANTT CHART: