Cpu Scheduling Practice Questions

Using the Shortest Remaining Time First (SRTF) algorithm:

1. From $T=0$ to $T=10$, process $P_1$ executes (remaining time $10 \to 0$).
2. At $T=10$, $P_1$ finishes, so the OS performs a context switch to start $P_2$ (which arrived at $T=2$ with $20$ units).
3. From $T=10$ to $T=30$, $P_2$ executes (remaining time $20 \to 0$).
4. At $T=30$, $P_2$ finishes, so the OS performs a context switch to start $P_3$ (which arrived at $T=6$ with $30$ units).
5. From $T=30$ to $T=60$, $P_3$ executes until completion.

Since $P_1$ is always the shortest process while it is running, no preemption occurs, and context switches only occur when a process completes at $T=10$ and $T=30$. Excluding start/end, this results in 2 context switches.

With non-preemptive priority scheduling, the CPU selects the ready process with the highest priority (lowest number).

1. At $t=0$, $P2$ (priority 2) runs, finishing at $t=5$.
2. At $t=5$, $P3$ (priority 1), $P4$ (priority 4), and $P1$ (priority 5) are ready. $P3$ runs until $t=8$.
3. At $t=8$, $P4$ (priority 4) runs because it has a higher priority than $P1$ (priority 5), finishing at $t=28$.
4. At $t=28$, $P5$ (priority 3) is ready and runs until $t=30$. Finally, $P1$ runs until $t=40$.
   The waiting times are: $P1: 40-10=30$, $P2: 0$, $P3: 5-2=3$, $P4: 8-5=3$, and $P5: 28-10=18$.
   The average waiting time is $\frac{30+0+3+3+18}{5} = \frac{54}{5} = 10.8$ ms.

The $SCAN$ algorithm (ii) is a standard disk scheduling technique used to optimize disk head movement. $Batch\ processing$ (B) typically utilizes the $FIFO$ ($First-In, First-Out$) queueing discipline (iv). $Time\ sharing$ (C) relies on the $Round\ robin$ algorithm (i) to effectively distribute CPU time among multiple processes. $Stack\ operation$ (D) inherently follows the $LIFO$ ($Last-In, First-Out$) principle (iii) for data management. Combining these pairs yields A-ii, B-iv, C-i, and D-iii.

In the Round Robin scheduling algorithm, every process is allocated a fixed time slice known as the time quantum ($q$). If $q$ is excessively large, the algorithm behaves like First-Come, First-Served (FCFS), which can lead to poor responsiveness. Conversely, if $q$ is too small, the overhead incurred by frequent context switching becomes significant, negatively impacting system efficiency. Therefore, the optimal balance between throughput, responsiveness, and overhead is entirely determined by the chosen value of $q$. Consequently, the overall performance of the Round Robin algorithm depends heavily on the size of the time quantum.

With a time slice of 1 unit, jobs execute in the order A, B, C, D, A, C, A, C, A, ...

• $t=0-1$: A runs (rem: 3), $t=1-2$: B runs (finishes), $t=2-3$: C runs (rem: 7), $t=3-4$: D runs (finishes).
• $t=4-5$: A runs (rem: 2), $t=5-6$: C runs (rem: 6), $t=6-7$: A runs (rem: 1), $t=7-8$: C runs (rem: 5).
• $t=8-9$: A runs (rem: 0).
  Thus, job A completes its last time unit at $t=9$.

Feedback Queues, or Multilevel Feedback Queues (MLFQ), dynamically classify processes based on their behavior rather than prior knowledge. By monitoring if a process exhausts its entire time quantum ($\Delta t$) before blocking for I/O, the scheduler distinguishes between CPU-bound and I/O-bound tasks. CPU-bound processes are demoted to lower-priority queues to prevent starvation, while I/O-bound processes are maintained in higher-priority queues to improve responsiveness. This adaptive mechanism allows the system to automatically optimize scheduling decisions by dispatching tasks according to their observed execution characteristics.

In Round-Robin (RR) scheduling, each process is assigned a fixed time quantum, $q$. If a process's burst time is less than $q$, it completes execution before the quantum expires. When $q$ is set to a value larger than the burst time of all processes in the queue ($q \ge \max(\text{burst \times })$), no process is preempted before completing. As a result, processes are executed sequentially based strictly on their arrival order, which is the defining characteristic of the First-Come First-Served (FCFS) algorithm. Therefore, using very large time slices causes Round-Robin to degenerate into FCFS.

In Round-Robin scheduling, processes are assigned a fixed time quantum $q$ to execute. If $q$ is set greater than the burst time $T_i$ for every process, every task will complete its execution entirely within its first allocated time slice. Because no process is ever preempted or returned to the end of the ready queue, the scheduler processes tasks strictly in their order of arrival. This eliminates the cyclical switching behavior of Round-Robin, causing the policy to function identically to First-Come-First-Serve (FCFS).

Here's the matching of CPU scheduling algorithms to their applications:

• (P) Gang Scheduling involves scheduling a group of related processes or threads to run simultaneously on different processors. Therefore, P matches (3) Thread Scheduling.
• (Q) Rate Monotonic Scheduling is a priority-based algorithm widely used in real-time scheduling systems where tasks have deadlines. Therefore, Q matches (2) Real-time Scheduling.
• (R) Fair Share Scheduling ensures that each user or group receives a guaranteed share of the CPU's processing time. Therefore, R matches (1) Guaranteed Scheduling.

Thus, the correct matching is P - 3, Q - 2, R - 1.

The Shortest Remaining Time First (SRT) algorithm is preemptive. We track the ready queue and remaining execution times.

1. $t=0$: P1 arrives (remaining = 20). P1 starts execution.
2. $t=15$: P2 arrives (remaining = 25). P1's remaining time is $20 - 15 = 5$. Since P1's remaining time (5) is less than P2's (25), P1 continues.
3. $t=20$: P1 completes. P2 is the only process, so P2 starts execution.
4. $t=30$: P3 arrives (remaining = 10). P2 has executed for $30 - 20 = 10$ units, so its remaining time is $25 - 10 = 15$. P3 (10) has a shorter remaining time than P2 (15), so P3 preempts P2 and starts execution.
5. $t=40$: P3 completes. P2 resumes execution.
6. $t=45$: P4 arrives (remaining = 15). P2 has executed for $45 - 40 = 5$ units, so its remaining time is $15 - 5 = 10$. P2 (10) has a shorter remaining time than P4 (15), so P2 continues.
7. $t=55$: P2 completes ($45 + 10 = 55$).

Waiting time for P2:
P2 arrived at $15$.
P2 started its first execution at $20$.
P2 was preempted at $30$.
P2 resumed at $40$.
P2 finished at $55$.

$\text{Waiting Time for P2} = (\text{Time P2 first started} - \text{Arrival Time of P2}) + (\text{Time P2 resumed} - \text{Time P2 was preempted})$
$\text{Waiting Time for P2} = (20 - 15) + (40 - 30) = 5 + 10 = 15$

The total waiting time for process P2 is 15.

Throughput is defined as the number of completed tasks per unit time. To maximize throughput, the scheduler must complete as many tasks as possible in the minimum amount of time. By scheduling tasks with the smallest runtimes $r_i$ first, the Shortest Job First (SJF) algorithm minimizes the average waiting time and completes the largest number of tasks within any given interval. In contrast, algorithms like First Come First Served (FCFS) or Round Robin may prioritize longer tasks, which delays the completion of multiple shorter tasks and reduces the overall task completion rate. Therefore, SJF ensures that the machine spends its time finishing the maximum number of jobs.

FIFO (or First-Come-First-Served) is a non-preemptive scheduling algorithm where processes run to completion based strictly on their arrival order. Round Robin (RR) is its preemptive counterpart, which introduces a fixed time quantum $q$ to limit the execution duration of each process. In RR, if a process does not complete within $q$, it is preempted and returned to the ready queue, allowing other processes to execute. If $q$ is set to infinity ($q \to \infty$), preemption never occurs, and RR behaves identically to FIFO. Thus, Round Robin is essentially the preemptive version of FIFO.

To minimize the average waiting time in a non-preemptive scheduling system, the Shortest Job First (SJF) algorithm must be used. SJF prioritizes tasks with the shortest execution times, which minimizes the cumulative waiting time by ensuring shorter processes complete early and do not block longer ones. Given the process burst times $\{5, 18, 9, 12\}$, we sort them in ascending order: $5 < 9 < 12 < 18$. Ordering the processes as $5, 9, 12, 18$ results in the minimum waiting time, as any other sequence would cause smaller processes to wait behind larger ones, increasing the average wait.

In operating systems, 'aging' is a scheduling technique specifically designed to prevent starvation in priority-based algorithms. It operates by gradually increasing the priority of processes that have been waiting in the ready queue for an extended period, expressed as $Priority_{current} = Priority_{initial} + \Delta(t)$. By continuously incrementing the priority over time, the system guarantees that even low-priority tasks eventually achieve a high enough priority to be scheduled for execution. This mechanism effectively eliminates the problem of infinite blocking (starvation), making Option B the correct definition.

At $t=0$, $P_1$ runs CPU (1) then I/O (5). $P_2$ starts CPU (1) at $t=2$ but is preempted by $P_3$ at $t=3$. $P_3$ completes CPU (2) at $t=5$. $P_2$ resumes until $t=6$, where $P_1$ (ready from I/O) preempts $P_2$ (priority $P_1 > P_2$). $P_1$ executes CPU (2) until $t=8$. Then $P_3$ (ready from I/O) preempts $P_1$ and finishes its final CPU (1) at $t=9$. $P_1$ resumes and finishes its final CPU (1) at $t=10$. Finally, $P_2$ completes its remaining CPU burst, I/O burst (3), and final CPU burst (1), finishing at $t=15$.

To find the CPU idle time, we first determine the CPU compute bursts for each process based on their total execution time:

• $P_1$: $10 \times 0.7 = 7$ units.
• $P_2$: $20 \times 0.7 = 14$ units.
• $P_3$: $30 \times 0.7 = 21$ units.

All processes arrive at $t=0$ and begin with an I/O burst:

• $P_1$: I/O until $t=2$, then ready.
• $P_2$: I/O until $t=4$, then ready.
• $P_3$: I/O until $t=6$, then ready.

Using the SRCTF scheduling algorithm:

• $t=0-2$: CPU is idle because no processes have completed their first I/O.
• $t=2-9$: $P_1$ executes for 7 units.
• $t=9-23$: $P_2$ executes for 14 units.
• $t=23-44$: $P_3$ executes for 21 units.

The CPU finishes its computation at $t=44$. The final process ($P_3$) finishes its last I/O burst at $t=44+3=47$. The total idle time is the initial idle period ($2$ units) plus the time after the final computation until the system completes ($47-44=3$ units), totaling 5 units of idle time. The percentage of idle time is:
$\frac{5}{47} \approx 10.64\%$
This matches the provided option.

In LRTF scheduling, the process with the longest remaining time is executed, with ties resolved by the lowest PID. Given processes $P_0(2), P_1(4), P_2(8)$ all arriving at $t=0$, the execution order is determined by continuously selecting the longest remaining burst:

1. $t=0 \to 4: P_2$ runs (rem: $P_0:2, P_1:4, P_2:4$).
2. $t=4 \to 5: P_1$ runs (rem: $P_0:2, P_1:3, P_2:4$).
3. $t=5 \to 6: P_2$ runs (rem: $P_0:2, P_1:3, P_2:3$).
4. $t=6 \to 7: P_1$ runs (rem: $P_0:2, P_1:2, P_2:3$).
5. $t=7 \to 8: P_2$ runs (rem: $P_0:2, P_1:2, P_2:2$).
6. $t=8 \to 9: P_0$, $t=9 \to 10: P_1$, $t=10 \to 11: P_2$, $t=11 \to 12: P_0$, $t=12 \to 13: P_1$, $t=13 \to 14: P_2$.
   Completion times are $CT_0=12$, $CT_1=13$, and $CT_2=14$. With arrival times $AT_i=0$, the turnaround times are $TAT_0=12, TAT_1=13, TAT_2=14$.
   Average Turnaround Time $= \frac{12+13+14}{3} = \frac{39}{3} = 13$ units.

At $t=0$, process $P_1$ ($10$ units) starts execution.
At $t=2$, $P_2$ ($20$ units) arrives; since $P_1$ remaining time ($8$) is less than $P_2$ ($20$), $P_1$ continues.
At $t=6$, $P_3$ ($30$ units) arrives; since $P_1$ remaining time ($4$) is the shortest ($4 < 20 < 30$), $P_1$ continues.
At $t=10$, $P_1$ finishes, and $P_2$ begins executing ($1^{st}$ context switch).
At $t=30$, $P_2$ finishes, and $P_3$ begins executing ($2^{nd}$ context switch).
At $t=60$, $P_3$ finishes. Thus, there are 2 context switches.

In Preemptive scheduling, $P3$ starts at $0$s, but is preempted by $P2$ at $3$s. At $5$s, $P1$ (priority $10$) preempts $P2$ (priority $9$) and runs until $25$s. $P2$ then resumes for its remaining $8$s, finishing at $33$s. Thus, $TAT_{preemptive} = 33 - 3 = 30\text{ sec}$.
In Non-preemptive scheduling, $P3$ executes uninterrupted until $15$s. At $15$s, $P1$ and $P2$ are both available; the scheduler selects $P1$ (higher priority $10$), which finishes at $35$s. Finally, $P2$ executes and completes at $45$s. Thus, $TAT_{non-preemptive} = 45 - 3 = 42\text{ sec}$.

Under the Preemptive Shortest Remaining Processing Time (SRPT) algorithm, we schedule the process with the smallest remaining burst time at every time interval:

• $t=0-1$: $P1$ runs (remaining: $4$).
• $t=1-4$: $P2$ runs (remaining: $3 \rightarrow 0$, finishes at $4$).
• $t=4-5$: $P4$ arrives and has the shortest remaining time ($1$), so $P4$ runs (finishes at $5$).
• $t=5-8$: $P3$ (remaining $3$) has the shortest time, so $P3$ runs (finishes at $8$).
• $t=8-12$: $P1$ resumes and finishes (remaining $4 \rightarrow 0$, finishes at $12$).
  Turnaround times ($TAT = Finish - Arrival$): $P1 = 12-0 = 12$, $P2 = 4-1 = 3$, $P3 = 8-2 = 6$, $P4 = 5-4 = 1$.
  Average $TAT = \frac{12 + 3 + 6 + 1}{4} = \frac{22}{4} = 5.5$.