## Process-Scheduling

 Question 1

Consider the following statements about process state transitions for a system using preemptive scheduling.

I. A running process can move to ready state.
II. A ready process can move to running state.
III. A blocked process can move to running state.
IV. A blocked process can move to ready state.

Which of the above statements are TRUE?

 A II and III only B I, II and III only C I, II, III and IV D I, II and IV only
Question 1 Explanation:
 Question 2

Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume that the processes are scheduled in the order P1,P2,P3,P4.

If the time quantum for RR is 4 ms, then the absolute value of the difference between the average turnaround times (in ms) of SJF and RR (round off to 2 decimal places) is _____.

 A 5.25
Question 2 Explanation:
SJF:

Turn Around Time = (21 – 0) + (13 – 0) + (2 – 0) + (6 – 0), Average = 42/4 = 10.50

Turn Around Time (TAT) = (18 – 0) + (21 – 0) + (10 – 0) + (14 – 0), Average = 63/4 = 15.75
Absolute difference = |10.50-15.75| = 5.25
 Question 3

Consider the 3 processes, P1, P2 and P3 shown in the table.

Process           Arrival time         Time Units Required
P1                0                         5
P2                1                         7
P3                3                         4

The completion order of the 3 processes under the policies FCFS and RR2 (round robin scheduling with CPU quantum of 2 time units) are

 A FCFS: P1, P2, P3 RR2: P1, P2, P3 B FCFS: P1, P3, P2 RR2: P1, P3, P2 C FCFS: P1, P2, P3 RR2: P1, P3, P2 D FCFS: P1, P3, P2 RR2: P1, P2, P3
Question 3 Explanation:
FCFS is - P1, P2, P3
FCFS is clear.
RR Queue: In RR queue time slot is of 2 units.
Processes are assigned in following order
P1, P2, P1, P3, P2, P1, P3, P2, P2
This question used the ready queue concept. At t=2, P2 starts and P1 is sent to the ready queue and at t=3 P3 arrives so then the job P3 is queued in the ready queue after P1. So at t=4, again P1 is executed then P3 is executed for the first time at t=6.
RR2: P1, P3, P2
So option C.
 Question 4

The process state transition diagram in below figure is representative of

 A a batch operating system B an operating system with a preemptive scheduler C an operating system with a non-preemptive scheduler D a uni-programmed operating system
Question 4 Explanation:
Transaction from running → ready present.
So this is preemptive.
 Question 5

Four jobs to be executed on a single processor system arrive at time 0+ in the order A, B, C, D. their burst CPU time requirements are 4, 1, 8, 1 time units respectively. The completion time of A under round robin scheduling with time slice of one time unit is

 A 10 B 4 C 8 D 9
Question 5 Explanation:
Time quantum is 1 unit.

∴ Completion time of A is 9 unit.
 Question 6

Consider n processes sharing the CPU in a round-robin fashion. Assuming that each process switch takes s seconds, what must be the quantum size q such that the overhead resulting from process switching is minimized but at the same time each process is guaranteed to get its turn at the CPU at least every t seconds?

 A q ≤ t-ns/n-1 B q ≥ t-ns/n-1 C q ≤ t-ns/n+1 D q ≥ t-ns/n+1
Question 6 Explanation:
 Question 7

Consider a set of n tasks with known runtimes r1, r2, ..., rn to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput?

 A Round-Robin B Shortest-Job-First C Highest-Response-Ratio-Next D First-Come-First-Served
Question 7 Explanation:
First we know what is throughput. It means total number of tasks executed per unit time. SJF executes shortest job very early so throughput increases in the case of SJF.
 Question 8

Which of the following scheduling algorithms is non-preemptive?

 A Round Robin B First-In First-Out C Multilevel Queue Scheduling D Multilevel Queue Scheduling with Feedback
Question 8 Explanation:
First-in first-out scheduling algorithm is non-preemptive. In this whichever the process enter into ready queue first that will be served first.
 Question 9

A uni-processor computer system only has two processes, both of which alternate 10ms CPU bursts with 90ms I/O bursts. Both the processes were created at nearly the same time. The I/O of both processes can proceed in parallel. Which of the following scheduling strategies will result in the least CPU utilization (over a long period of time) for this system?

 A First come first served scheduling B Shortest remaining time first scheduling C Static priority scheduling with different priorities for the two processes D Round robin scheduling with a time quantum of 5 ms
Question 9 Explanation:
We have two processes P and Q. These process have 10ms CPU burst time and 90ms I/O bursts.
(i) FCFS:
0-10: Process 1 can execute
10-20: Process 2 can execute
100-110: Process 1 Terminate
110-120: Process 2 Terminate
CPU utilization = 20/100 [In every 100ms it utilizes]
=20%
(ii) SRTF: can process P and Q same as FCFS
then CPU utilization = 20%
(iii) Round robin: with TQ-5
0-5: Process P1
5-10: Process P2
10-15: Process P1
15-20: Process P2
105-110: Process P1
110-115: Process P2
CPU utilization = 20/105 = 19.5
 Question 10

The process state transition diagram of an operating system is as given below.

Which of the following must be FALSE about the above operating system?

 A It is a multiprogrammed operating system B It uses preemptive scheduling C It uses non-preemptive scheduling D It is a multi-user operating system
Question 10 Explanation:
Option B is wrong. Because given OS is non-preempting scheduling algorithm.
 Question 11

The arrival time, priority, and duration of the CPU and I/O bursts for each of three processes P1, P2 and P3 are given in the table below. Each process has a CPU burst followed by an I/O burst followed by another CPU burst. Assume that each process has its own I/O resource.

The multi-programmed operating system uses preemptive priority scheduling. What are the finish times of the processes P1, P2 and P3 ?

 A 11, 15, 9 B 10, 15, 9 C 11, 16, 10 D 12, 17, 11
Question 11 Explanation:
Gantt-chart:

Hence, finish times of process.
P1 - 10
P2 - 11
P3 - 9
 Question 12

Let a memory have four free blocks of sizes 4k, 8k, 20k, 2k. These blocks are allocated following the best-fit strategy. The allocation requests are stored in a queue as shown below.

The time at which the request for J7 will be completed will be

 A 16 B 19 C 20 D 37
Question 12 Explanation:
At t = 0

At t = 8

At t = 10

At t = 11

J7 can be finished at t = 19.
 Question 13

Consider n jobs J1, J2,......Jn such that job Ji has execution time ti and a non-negative integer weight wi. The weighted mean completion time of the jobs is defined to be , where Ti is the completion time of job Ji. Assuming that there is only one processor available, in what order must the jobs be executed in order to minimize the weighted mean completion time of the jobs?

 A Non-decreasing order of ti B Non-increasing order of wi C Non-increasing order of witi D None-increasing order of wi/ti
Question 13 Explanation:
Like OS concept, execute job which have more completion time in 1 sec i.e., find wi/ti for every process then arrange it in the decreasing order. So, we get complete time is minimum always.
So answer is the non-increasing order of wi/ti.
 Question 14

Consider the following set of processes, with the arrival times and the CPU-burst times given in milliseconds.

Process   Arrival Time    Burst Time
P1          0              5
P2          1              3
P3          2              3
P4          4              1

What is the average turnaround time for these processes with the preemptive shortest remaining processing time first (SRPT) algorithm?

 A 5.5 B 5.75 C 6 D 6.25
Question 14 Explanation:
Uses SRPT Algorithm:

Avg. TAT = 12+3+6+1/4 = 22/4 = 5.50
 Question 15

Consider a uniprocessor system executing three tasks T1, T2 and T3, each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 milliseconds, respectively. The priority of each task is the inverse of its period and the available tasks are scheduled in order of priority, with the highest priority task scheduled first. Each instance of T1, T2 and T3 requires an execution time of 1, 2 and 4 milliseconds, respectively. Given that all tasks initially arrive at the beginning of the 1st millisecond and task preemptions are allowed, the first instance of T3 completes its execution at the end of ______________ milliseconds.

 A 13 B 12 C 15 D 16
Question 15 Explanation:
All the processes or tasks are available at the begining of 1st millisecond, means at t=0. So, Gantt chart will be as follows:

∴ At the end of 12 milliseconds, 1st instance of T3 will complete its execution.
 Question 16

Consider the following processes, with the arrival time and the length of the CPU burst given in milliseconds. The scheduling algorithm used is preemptive shortest remaining-time ﬁrst.

The average turn around time of these processes is _________ milliseconds.

 A 8.25 B 8.26 C 8.27 D 8.28
Question 16 Explanation:
Here the scheduling algorithm used is preemptive shortest remaining-time first.
To answer the question we need to design the gantt chart:

In this algorithm, the processes will be scheduled on the CPU which will be having least remaining burst time.
Turnaround Time (TAT) = Completion Time (CT) - Arrival Time (AT)
TAT for P1 = 20 - 0 = 20,
TAT for P2 = 10 - 3 = 7,
TAT for P3 = 8 - 7 = 1,
TAT for P4 = 13 - 8 = 5.
Total TAT = 20 + 7 + 1 + 5 = 33 / 4 = 8.25 (Avg. TAT)
 Question 17

Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?

 A Shortest remaining time ﬁrst B Round-robin with time quantum less than the shortest CPU burst C Uniform random D Highest priority ﬁrst with priority proportional to CPU burst length
Question 17 Explanation:
From the above question, we can get the following information.
We can consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system.
We have to choose the appropriate process scheduling algorithms, which would minimize the average waiting time in the ready queue.
Waiting time is the time for which process is ready to run but not executed by CPU scheduler.
In all CPU Scheduling algorithms, shortest job first is optimal.
It gives minimum turnaround time, minimum average waiting time and high throughput and the most important thing is that shortest remaining time first is the preemptive version of shortest job first.
This scheduling algorithm may lead to starvation because if the short processes are added to the CPU scheduler continuously then the currently running process will never be able to execute as they will get pre-empted but here all the processes are arrived at same time so there will be no issue such as starvation.
SRTF would be same as SJF.
So, A is the answer. Shortest remaining time first.
 Question 18

Consider the set of processes with arrival time (in milliseconds), CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time.

The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is __________.

 A 29 B 30 C 31 D 32
Question 18 Explanation:

Waiting Time = 0 + (33 - 5) + (40 - 2) + (49 - 12) + (51 - 9) = 145
Average waiting time: 145/5 = 29
 Question 19

Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below:

If the pre-emptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is __________ milliseconds.

 A 3 B 4 C 5 D 6
Question 19 Explanation:
 Question 20

Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below:

These processes are run on a single processor using preemptive Shortest Remaining Time First scheduling algorithm. If the average waiting time of the processes is 1 millisecond, then the value of Z is _____.

 A 2 B 7 C 1 D 4
Question 20 Explanation:
This is the Gantt chart till time = 4 units

At this point P4 arrives with burst 'Z' & P3 is in queue with burst 3.
P1 & P2 have executed with P1 incurred delay 1unit & P2 0units.
Hence, Avg = 0+1+x/4 =1
⇒ x=3, the next delay should be 3. It would happen if assume Z=2.
It executes and completes at 6.
P3 will wait totally for 3units.
Hence, Avg=1.

Z=2
 Question 21

The maximum number of processes that can be in Ready state for a computer system with n CPUs is

 A n B n2 C 2n D Independent of n
Question 21 Explanation:
Number of processes which are in running processes will be atmost n as there are n processors.
Maximum number of processes that will be in ready state is independent of number of processors.
There are 21 questions to complete.

Register Now