CPU Scheduling Algorithms Questions and Answers

Answer: A

Pre-emptive scheduling suspends a running process before the CPU time slice expires.

In pre-emptive scheduling the operating system can take the CPU from a process that is still running, for example because a higher priority process has arrived, without waiting for the process to finish its quantum or give up the CPU. Allowing starving processes to run (B) is an aim of aging, suspension on an I/O request (C) happens in non-pre-emptive systems too, and avoiding collision (D) is not a scheduling concept.

Answer: D

The average turn around time varies irregularly as the time quantum is increased.

In round robin scheduling, a larger quantum does not make the average turn around time rise or fall in a steady way. It depends on the burst lengths of the processes, and a small change in the quantum can cause a process to finish within one slice or to need another, so the average moves up and down. When the quantum becomes larger than every burst, round robin behaves like first come first served. Options (A), (B) and (C) claim a steady trend that does not hold in general.

Answer: B

The finish times are 8, 2, 7 and 5. Because every process gets priority 0 whenever it enters the ready queue, each preempted process restarts at 0 and gains 2 per unit of waiting. Ties go to the process that has not run recently.

At t = 1, P1 rejoins with 0 and P2 arrives with 0, so P2 runs and finishes at 2. P1 has waited, so it gets priority 2 at t = 2 and runs until 3. P3 then runs 3 to 4, P4 (waiting from 3) ties with P1 at 4 and runs 4 to 5, finishing at 5. P1 runs 5 to 6, P3 runs 6 to 7 and finishes at 7, and P1 runs 7 to 8 and finishes at 8.

The other options have a different finish time for P2 or give P3 and P4 the wrong way round.

Answer: B

Linux uses fair preemptive scheduling. The kernel gives each runnable task a share of the processor and can preempt a running task when another deserves the CPU, in order to keep tasks treated fairly by priority and past use.

Affinity scheduling ties a thread to a CPU and is not the general Linux policy. Hand shaking is a communication term, and Highest Penalty Ratio Next is a variant of response-ratio scheduling that Linux does not use.

Answer: C

When a virtual memory based memory management algorithm swaps out a process partly to relieve memory pressure, it is carrying out medium term scheduling, option (C). The medium term scheduler removes processes from memory, reducing the degree of multiprogramming, and later brings them back, so it is the swapping level of the scheduler. Short term scheduling picks which ready process gets the CPU next, long term scheduling decides which jobs are admitted into the system, and mutual exclusion is a synchronisation property and not a scheduling level. So (A), (B) and (D) are wrong.

Answer: B

Round robin with a time slice of 4 ms gives the order A (0-4), B (4-8), C (8-12), D (12-16), A (16-20), C (20-24), D (24-25) and C (25-26). B finishes at 8, A at 20, D at 25 and C at 26.

\[ \text{turnaround} = \text{finish} - \text{arrival} \]

\[ A: 20,\; B: 7,\; C: 24,\; D: 22 \]

\[ \frac{20 + 7 + 24 + 22}{4} = 18.25 \text{ ms} \]

This is option (B). Options (A), (C) and (D) come from a different order of the queue or from using waiting time in place of turnaround time.

Answer: A

The average turn around time is 8.4 ms. With a time slice of 1 ms, the processes take turns in the order A, B, C, D, E and the finishing times are found by following the queue.

\[ B = 2,\ D = 4,\ C = 7,\ E = 14,\ A = 15 \]

\[ \frac{2 + 4 + 7 + 14 + 15}{5} \]

\[ = \frac{42}{5} = 8.4 \text{ ms} \]

The priorities in the table are not used in round robin. The other options come from different orders or from adding the waiting times rather than the finishing times.

Answer: D

The matching is multilevel feedback queue with the criteria to move processes between queues (ii), FCFS with batch processing (iii), shortest process next with exponential smoothing (iv) and round robin with time slicing (i), the code ii, iii, iv, i. A multilevel feedback queue moves processes between queues by rules such as the use of the time slice, FCFS is the method of batch systems, shortest process next predicts the length of the next burst by exponential averaging, and round robin gives each process a time slice. The other codes give time slicing to the wrong method.

Answer: B

The CPU utilisation is 50 percent.

Arrivals are 5 per minute and each needs 6 seconds, so the demand is \[ 5 \times 6 = 30 \text{ seconds of service per minute}, \] and the utilisation is \[ \frac{30}{60} = 50\%. \]

80, 60 and 30 percent would need a different arrival rate or service time. The same result follows from the definition of utilisation as the arrival rate times the mean service time. Five processes a minute is 1/12 of a process per second and 6 seconds each gives 0.5, so the CPU is busy half of the time and idle for the other half.