Courses

# Test: CPU & I/O Scheduling- 1

## 15 Questions MCQ Test Operating System | Test: CPU & I/O Scheduling- 1

Description
This mock test of Test: CPU & I/O Scheduling- 1 for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam. This contains 15 Multiple Choice Questions for Computer Science Engineering (CSE) Test: CPU & I/O Scheduling- 1 (mcq) to study with solutions a complete question bank. The solved questions answers in this Test: CPU & I/O Scheduling- 1 quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Test: CPU & I/O Scheduling- 1 exercise for a better result in the exam. You can find other Test: CPU & I/O Scheduling- 1 extra questions, long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.
QUESTION: 1

### Consider three processes, all arriving at time zero, with total execution time of 10, 20 and 30 units, respectively. Each process spends the first 20% of execution time doing I/O, the next 70% of time doing computation, and the last 10% of time doing I/O again. The operating system uses a shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst. Assume that all I/O operations can be overlapped as much as possible. For what percentage of time does the CPU remain idle?

Solution:

Let three processes be p0, p1 and p2. Their execution time is 10, 20 and 30 respectively. p0 spends first 2 time units in I/O, 7 units of CPU time and finally 1 unit in I/O. p1 spends first 4 units in I/O, 14 units of CPU time and finally 2 units in I/O. p2 spends first 6 units in I/O, 21 units of CPU time and finally 3 units in I/O.

Total time spent = 47 Idle time = 2 + 3 = 5 Percentage of idle time = (5/47)*100 = 10.6 %

QUESTION: 2

### Consider three processes (process id 0, 1, 2 respectively) with compute time bursts 2, 4 and 8 time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the process with the lowest process id. The average turn around time is:

Solution:

Let the processes be p0, p1 and p2. These processes will be executed in following order.

Turn around time of a process is total time between submission of the process and its completion. Turn around time of p0 = 12 (12-0) Turn around time of p1 = 13 (13-0) Turn around time of p2 = 14 (14-0) Average turn around time is (12+13+14)/3 = 13.

QUESTION: 3

### Which of the following process scheduling algorithm may lead to starvation

Solution:

Shortest job next may lead to process starvation for processes which will require a long time to complete if short processes are continually added.

QUESTION: 4

Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.

Solution:

Let three process be P0, P1 and P2 with arrival times 0, 2 and 6 respectively and CPU burst times 10, 20 and 30 respectively. At time 0, P0 is the only available process so it runs. At time 2, P1 arrives, but P0 has the shortest remaining time, so it continues. At time 6, P2 arrives, but P0 has the shortest remaining time, so it continues. At time 10, P1 is scheduled as it is the shortest remaining time process. At time 30, P2 is scheduled. Only two context switches are needed. P0 to P1 and P1 to P2.

QUESTION: 5

A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?

Solution:

The scheduling algorithm works as round robin with quantum time equals to T. After a process's turn comes and it has executed for T units, its waiting time becomes least and its turn comes again after every other process has got the token for T units.

QUESTION: 6

If the quantum time of round robin algorithm is very large, then it is equivalent to:

Solution:

If time quantum is very large, then scheduling happens according to FCFS.

QUESTION: 7

Which of the following statements are true?
I. Shortest remaining time first scheduling may cause starvation
II. Preemptive scheduling may cause starvation
III. Round robin is better than FCFS in terms of response time

Solution:

I) Shortest remaining time first scheduling is a pre-emptive version of shortest job scheduling. In SRTF, job with the shortest CPU burst will be scheduled first. Because of this process, It may cause starvation as shorter processes may keep coming and a long CPU burst process never gets CPU.

II) Pre-emptive just means a process before completing its execution is stopped and other process can start execution. The stopped process can later come back and continue from where it was stopped. In pre-emptive scheduling, suppose process P1 is executing in CPU and after some time process P2 with high priority then P1 will arrive in ready queue then p1 is pre-empted and p2 will brought into CPU for execution. In this way if process which is arriving in ready queue is of higher priority then p1, then p1 is always pre-empted and it may possible that it suffer from starvation.

III) round robin will give better response time then FCFS ,in FCFS when process is executing ,it executed up to its complete burst time, but in round robin it will execute up to time quantum. So Round Robin Scheduling improves response time as all processes get CPU after a specified time. So, I,II,III are true which is option (D).

QUESTION: 8

Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.

Solution:

Shortest remaining time, also known as shortest remaining time first (SRTF), is a scheduling method that is a pre-emptive version of shortest job next scheduling. In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute. Since the currently executing process is the one with the shortest amount of time remaining by definition, and since that time should only reduce as execution progresses, processes will always run until they complete or a new process is added that requires a smaller amount of time. Solution: Let three process be P0, P1 and P2 with arrival times 0, 2 and 6 respectively and CPU burst times 10, 20 and 30 respectively. At time 0, P0 is the only available process so it runs. At time 2, P1 arrives, but P0 has the shortest remaining time, so it continues. At time 6, P2 also arrives, but P0 still has the shortest remaining time, so it continues. At time 10, P1 is scheduled as it is the shortest remaining time process. At time 30, P2 is scheduled. Only two context switches are needed. P0 to P1 and P1 to P2.

QUESTION: 9

An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds):

Process   Arrival Time    Burst Time
P1           0                    12
P2           2                     4
P3           3                     6
P4           8                     5

The average waiting time (in milliseconds) of the processes is _________.

Solution:

Process   Arrival Time   Burst Time
P1           0                   12
P2           2                    4
P3           3                    6
P4           8                    5

Burst Time - The total time needed by a process from the CPU for its complete execution. Waiting Time - How much time processes spend in the ready queue waiting their turn to get on the CPU Now, The Gantt chart for the above processes is :

P1 - 0 to 2 milliseconds

P2 - 2 to 6 milliseconds

P3 - 6 to 12 milliseconds

P4 - 12 to 17 milliseconds

P1 - 17 to 27 milliseconds

Process p1 arrived at time 0, hence cpu started executing it. After 2 units of time P2 arrives and burst time of P2 was 4 units, and the remaining time of the process p1 was 10 units,hence cpu started executing P2, putting P1 in waiting state(Pre-emptive and Shortest remaining time first scheduling). Due to P1's highest remaining time it was executed by the cpu in the end.

Now calculating the waiting time of each process:
P1 -> 17 -2 = 15
P2 -> 0
P3 -> 6 - 3 = 3
P4 -> 12 - 8 = 4

Hence total waiting time of all the processes is
= 15+0+3+4=22
Total no of processes = 4
Average waiting time = 22 / 4 = 5.5

QUESTION: 10

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 ?

Solution:

When Round Robin scheduling is used We are given that the time slice is 5ms. Consider process P and Q. Say P utilizes 5ms of CPU and then Q utilizes 5ms of CPU. Hence after 15ms P starts with I/O And after 20ms Q also starts with I/O. Since I/O can be done in parallel, P finishes I\O at 105th ms (15 + 90) and Q finishes its I\O at 110th ms (20 + 90). Therefore we can see that CPU remains idle from 20th to 105th ms. That is when Round Robin scheduling is used, Idle time of CPU = 85ms CPU Utilization = 20/105 = 19.05% When First Come First Served scheduling scheduling or Shortest Remaining Time First is used Say P utilizes 10ms of CPU and then starts its I/O. At 11th ms Q starts processing. Q utilizes 10ms of CPU. P completes its I/O at 100ms (10 + 90) Q completes its I/O at 110ms (20 + 90) At 101th ms P again utilizes CPU. Hence, Idle time of CPU = 80ms CPU Utilization = 20/100 = 20% Since only two processes are involved and I\O time is much more than CPU time, "Static priority scheduling with different priorities" for the two processes reduces to FCFS or Shortest remaining time first. Therefore, Round robin will result in least CPU utilization.

QUESTION: 11

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 ?

Solution:

The following is Gantt Chart of execution
P1    P2    P4    P3    P1
1       4       5       8    12

Turn Around Time = Completion Time - Arrival Time   Avg Turn Around Time  =  (12 + 3 + 6+  1)/4 = 5.50

QUESTION: 12

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?

Solution:

Throughput means total number of tasks executed per unit time i.e. sum of waiting time and burst time.
Shortest job first scheduling is a scheduling policy that selects the waiting process with the smallest execution time to execute next.
Thus, in shortest job first scheduling, shortest jobs are executed first. This means CPU utilization is maximum. So, maximum number of tasks are completed.
Thus, option (B) is correct.

QUESTION: 13

Which of the following scheduling algorithms is non-preemptive?

Solution:

Round Robin - Preemption takes place when the time quantum expires First In First Out - No Preemption, the process once started completes before the other process takes over Multi Level Queue Scheduling - Preemption takes place when a process of higher priority arrives Multi Level Queue Scheduling with Feedback - Preemption takes a place when process of higher priority arrives or when the quantum of high priority queue expires and we need to move the process to low priority queue So, B is the correct choice.

QUESTION: 14

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 milliseconds and task preemptions are allowed, the first instance of T3 completes its execution at the end of ______________ milliseconds.

Solution:

Periods of T1, T2 and T3 are 3ms, 7ms and 20ms. Since priority is inverse of period, T1 is the highest priority task, then T2 and finally T3 Every instance of T1 requires 1ms, that of T2 requires 2ms and that of T3 requires 4ms Initially all T1, T2 and T3 are ready to get processor, T1 is preferred Second instances of T1, T2, and T3 shall arrive at 3, 7, and 20 respectively. Third instance of T1, T2 and T3 shall arrive at 6, 14, and 40 respectively.
0-1            T1
1-2            T2
2-3            T2
3-4            T1  [Second Instance of T1 arrives]
4-5            T3
5-6            T3
6-7            T1  [Third Instance of T1 arrives]

[Therefore T3 is preempted]
7-8            T2  [Second instance of T2 arrives]
8-9            T2
9-10          T1  [Fourth Instance of T1 arrives]

10-11        T3
11-12         T3 [First Instance of T3 completed]

QUESTION: 15

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

Solution:

The size of ready queue doesn't depend on number of processes. A single processor system may have a large number of processes waiting in ready queue.