Galvin Eighth Edition

Question

Consider a system running ten I/O-bound tasks and one CPU-bound task. Assume that the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context-switching overhead is 0.1 millisecond and that all processes are long-running tasks. Describe the CPU utilization for a round-robin scheduler when:

1. The time quantum is 1 millisecond
2. The time quantum is 10 milliseconds

Answer 1

(a) Time quantum is 1 ms.

Whether a CPU bound or I/O bound process, it switches every one millisecond and when doing so, it incurs a 0.1 ms overhead. Thus, for every 1.1 ms, the CPU is actually utilized only 1 ms. So CPU utilization is $\frac{1}{1.1}*100=91$%

(b) Time quantum is 10 ms.

Here, there is a difference between CPU bound and I/O bound processes. A CPU bound process can use the full 10 ms time slot, whereas an I/O bound process can have it only for 1 ms because another I/O bound process in the queue will snatch the time from it. So a CPU bound process takes 10 ms, 10 I/O bound processes would take 10*1=10ms. So, the CPU would be utilized for a total of 20 ms out of 21.1 ms. (Total time is 10*1.1 + 10.1=21.1ms). Thus the CPU utilization is $\frac{20}{21.1}*100=95$%

Comments

I understand the part A but I didnot understand the part B or i got wrong ans since no info. is given regrading the CPU bound process.

For part B I got CPU utilization =9.99% since TQ is big and it cause inefficiency.

---

what ever may be the Burst time of CPU BOUND process( but it should be grater than TQ ), it will run upto 1 TQ. after that already  I/O bound process₁ should come into ReadyQueue.

==> Total time utilized = (1*1*...*1 ten times for I/O bound processes ) + 1 TQ for CPU Bound

===> Extra time consumed  = 1 context switch for each process ===> 11*0.1 = 1.1ms

1) if TQ = $\color{red}1$ ms ===> efficiency = $\frac{10 ms\; + \;\color{red}1\; ms}{10ms\;+\;\color{red}1\;ms+\;1.1ms}$ = $\frac{11}{12.1}$ = 90.90%

2) if TQ = $\color{red}{10}$ ms ===> efficiency = $\frac{10 ms\; + \;\color{red}{10}\; ms}{10ms\;+\;\color{red}{10}\;ms+\;1.1ms}$ = $\frac{20}{21.1}$ = 94.78%

Answer 2

i/o1

i/o2

i/o3

i/o4

i/o5

i/o6

i/o7

i/o8

i/o9

i/o10

cpu1

.....

according to question given at every 1ms i/o operation done . and it will be completed in 10 ms . so 10 i/o operation have 

time = 10*1+.1*10 = 11ms ...(here 0.1 switching overhead )

cpu task ,for which we can consider it runs for 10ms bcoz i/o operation will be completed in 10ms ... (given as all process are long running tasks) 

so if case 1 ... time quantum is 1ms then cpu task takes = 10*1+10*0.1(switching after every 1ms quantum time)= 11ms 

so cpu utilization = useful work/ total work

                                (10*1+10*1)/11+11= 20/22=90.90%

case 2 time quantum =10ms so cpu takes = 10*1+1*.1=10.1

cpu utilization = 20/ 11+10.1= 20/ 21.1 = 94.78%

Answer 3

all task are long running task so we cannot wait to complete as no limit is given so i take one cycle in consideration.

the efficency will be same in one cycle or 100 cycles.

one cycle will be from the execution of P0 till it comes back again.

now starting with p0 context switch is taken by this symbol ]

p0 ] p1 ] p2 ]..........p10 ] total ( 11 process)

thsi will be one cycle .. not to forget the last context switch as we have not considered a context switch on before p0. so we have to consider the last one .

now p1 will execute for 1 unit and then will go for i/o and will come back after 10 ms which is 11 ms.

well as no cpu time will be wasted as it will always have a job to execute and i/o will be overlapped like the normal day practice it will work like normal and only wastage will be context switch time which will be 11 *0.1=1.1 ms

efficiency = (11-1.1)/11*100= 90%. well the process which is cpu bound will not have to go to i/o so he will just exit the queue and again come in line.  it will not have any effect here .

 

2 case.

now time quantum is 10 ms

so we know after every 1ms process goes to i/o. but a process will only be preempted when time quantum expires .

so now the cycle time will be 110 as every process is running for 10 ms. and all are long tasks not completing in one or 2 cycles

so the context switch will be the same and the wastage will also be same 1.1.

but in the time quantum every process will only do 1 ms of usefull time and all 9 ms will be wasted . except the process which is cpu bound . he will work the whole time. so usefull time will be 1*10+10

20 unit will be only the usefull work .minus the context switch overhead = 20-1.1

18.9 is the actual useful work out of 110. so efficiency = 18.9/110*100= 17.18 %

Comments

@Ravi 

as you explain in first part

p1 will execute for 1 unit and then will go for i/o and will come back after 10 ms which is 11 ms.
here context switch time is 1.1

so totla time is 12.1 and efficiency is (11/12.1)*100=90%..

correct me if i wrong

---

Total time in 1st part must 12.1    as (11x0.1)+11= 12.1

then the ans. will be 90.9% which is close to the correct ans 91%

---

In 2nd part as you said context switch will be only if the time quantum expires..right..
Then during 10 ms , there will be process in the cpu ..it doesn't do any useful work as the process has to do i/o
after 1 msec. of CPU consumption, but it will still occupy cpu for rest 9ms..so as the cpu is occupied for whole 10ms by a process irrespective of that it is not doing any useful work..but still cpu is occupied so cpu will be busy and utilization will be considered for 10ms isnt it?