CPU-Scheduling
Question 1 |
- The fastest computer gets the toughest job and the slowest computer gets the easiest job.
- Every computer gets at least one job.
65 |
Let the levels be 1,2,3,4,5,6. (1 is the least difficult, 6 is the most difficult level)
Let the computers be F,M,S( fast, medium, slow).
As per the given constraint, 1 must be given to F and 6 must be given to S.
Now we are left with 2,3,4,5 and F being assigned 1, S being assigned 6 and M being assigned none.
Another constraint is that, every computer must be assigned atleast one.
So compute with assigning one job to M, two jobs to M, three jobs to M and four jobs to M.
Assigning one job to M: we can assign 1 out of 4 jobs in (4C1 ways) and remaining 3 jobs to F,S in 2*2*2 = 8 ways. (each job has two options, either F or S),
Assigning two jobs to M: we can select two jobs from 4 in 4C2 ways and remaining 2 can be distributed to F and S in 2*2 ways ( each job has two options either F or S)
Assigning three jobs to M: we can select 3 out of 4 in 4C3 ways remaining can be distributed to F,M in 2 ways.
Assigning 4 jobs to M: it can be done in only one way.
Total : 4c1*8 + 4C2* 4 + 4C3*2 + 1
= 32+24+8+1
=65
Question 2 |
12 |
Question 3 |
The sequence …………… is an optimal non-preemptive scheduling sequence for the following jobs which leaves the CPU idle for …………… unit(s) of time.
{3,2,1),1 | |
(2,1,3},0 | |
{3,2,1),0 | |
{1,2,3},5 |
So, (B) and (C) will be eliminated.
Now in (A) and (D):
For r(A),
So, idle time is between 0 to 1 which in case of option (A).
For option(D),
We can see there is no idle time at all, but in option given idle time is 5, which is not matching with our chart. So option (D) is eliminated.
Therefore, the correct sequence is option (A).
Question 4 |
Which scheduling policy is most suitable for a time shared operating system?
Shortest Job First | |
Round Robin | |
First Come First Serve | |
Elevator |
Question 5 |
Implementing preemptive scheduling needed hardware support. | |
Turnaround time includes waiting time | |
Round-robin policy can be used even when the CPU time required by each of the processes is not known apriori. | |
The goal is to only maximize CPU utilization and minimize throughput. |
- True. Preemptive scheduling needs hardware support such as a timer
- True. Turnaround time = Burst time + Waiting time
- True, RR assigns qunatume to each process equally. Hence, it is not required to know burst size apriori
- False. Maximize CPU utilization and throughput, and minimize waiting time etc.
Question 6 |
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):
The average waiting time (in milliseconds) of the processes is
5.5 | |
5.6 | |
5.7 | |
5.8 |
WT - Waiting Time
CT - Completion Time
TAT - Turn Around Time
TAT = CT - AT < br> WT = TAT - BT
Gantt chart using Shortest remaining time first,
Avg. WT = 15+0+3+4/4 = 22/4 = 5.5
Question 7 |
First-in First-Out | |
Round Robin | |
Priority Scheduling | |
Shortest Job First |
Question 8 |
Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequence:
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1ms to move from one cylinder to adjacent one and shortest seek time first policy is used?
95 ms | |
119 ms | |
233 ms | |
276 ms |
4, 34, 10,7, 19, 73, 2, 15, 6, 20
Arrange the sequence in order
2, 4, 6, 10, 15, 19, 20, 34, 73
⇒ 1 ms to move from one cylinder to adjacent one
⇒ (16*1)+(14*1)+(1*1)+(4*1)+(5*1)+(3*1)+(1*1)+(2*1)+(2*1)+(71*1)
⇒ 16+14+1+4+5+3+1+2+2+71
⇒ 119 ms
Question 9 |
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?
This algorithm is equivalent to the first-come-first-serve algorithm. | |
This algorithm is equivalent to the round-robin algorithm. | |
This algorithm is equivalent to the shortest-job-first algorithm. | |
This algorithm is equivalent to the shortest-remaining-time-first algorithm. |
Question 10 |
Non-preemptive priority scheduling | |
Preemptive priority scheduling and time sharing CPU scheduling | |
Time sharing scheduling only | |
Priority scheduling only |
Question 11 |
Identify the circumstances under which preemptive CPU scheduling is used :
(a) A process switches from Running state to Ready state
(b) A process switches from Waiting state to Ready state
(c) A process completes its execution
(d) A process switches from Ready to Waiting state Choose the correct option:
(a) and (b) only | |
(a) and (d) only | |
(c) and (d) only | |
(a), (b), (c) only |
1. When a process switches from the running state to the waiting state, such as for an I/O request or invocation of the wait( ) system call.
2. When a process switches from the running state to the ready state, for example in response to an interrupt.
3. When a process switches from the waiting state to the ready state, say at completion of I/O or a return from wait( ).
4. When a process terminates.
For conditions 1 and 4 there is no choice - A new process must be selected.
For conditions 2 and 3 there is a choice - To either continue running the current process, or select a different one.
Note: If scheduling takes place only under conditions 1 and 4, the system is said to be non-preemptive, or cooperative. Under these conditions, once a process starts running it keeps running, until it either voluntarily blocks or until it finishes. Otherwise the system is said to be preemptive.
Question 12 |
Given CPU time slice of 2ms and following list of processes.
Find average turnaround time and average waiting time using round robin CPU scheduling?4.0 | |
5.66, 1.66 | |
5.66, 0 | |
7, 2 |
Average Turnaround Time= (5+5+7)/3
= 5.66
Average Waiting Time= (2+1+2)/3
= 1.66
Question 13 |
8 | |
16 | |
32 | |
48 |