How does this formula that calculates CPU utilization work?

Question

I've been given this question

Consider a system running ten I/0-bound tasks and one CpU-bound task. Assume that the I/O-bound tasks issue and 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 .1 millisecond and that all processes are long running tasks Describe the CPU utilization for round-robin scheduler when:

a. The time quantum is 1 millisecond

b. The time quantum is 10 milliseconds

and I found answer for it

The time quantum is 1 millisecond: Irrespective of which process is scheduled, the scheduler incurs a 0.1 millisecond context-switching cost for every context-switch. This results in a CPU utilization of 1/1.1 * 100 = 91%.

The time quantum is 10 milliseconds: The I/O-bound tasks incur a context switch after using up only 1 millisecond of the time quantum. The time required to cycle through all the processes is therefore 10*1.1 + 10.1 (as each I/O-bound task executes for 1millisecond and then incur the context switch task, whereas the CPU- bound task executes for 10 milliseconds before incurring a context switch). The CPU utilization is therefore 20/21.1 * 100 = 94%.

My only question how is this person deriving the formula for CPU Utilization? I can't seem to under stand where he/she is getting the numbers 20/21.1 * 100 = 94%, and 1/1.1 * 100 = 91%.

Milestone

Answer 1

For the first case, every task uses 1msec to do work and .1msec to switch; thus, it is spending 1 of every 1.1 msec doing work.

For the second case, it is similar: of the 21.1 msec spent to go through all tasks, only 20 of that is doing actual work.

Cynosure

Thanks for the clearing this up I knew I was missing something. – Milestone

I'm confused, I read somewhere CPU and I/O tasks are performed independent to each other hence they can be performed parallel, so why is there even context switch in CPU task? – Toul

Answer 2

This is the best possible explanation to above problem :

http://jade-cheng.com/uh/coursework/ics-412/homework-4.pdf

Arak

Note that link-only answers are discouraged, references tend to get stale over time. Please consider adding a stand-alone synopsis here, keeping the link as a reference. – Stein

Answer 3

for part a

we have 11 process(10 i/o,1 cpu). Each takes 1ms execution time and 0.1ms switching time.

So total time taken by a process is: 10(I/o)*1(1ms of cpu)+1(CPU bounded process)*1(1ms of cpu)+11*0.1(total switching time)=12.1ms.

In this 12.1ms, time for which cpu was busy/doing execution=10*1(For 10 I/O precoess)+1*1(for 1 CPU process)=10+1=11

CPU utilisation=(11/12.1)*100=(1/1.1)*100=91%approx

for part b

Though time quantum is 10ms, but I/O bound process will only occupy 1ms of cpu and then go to block state as it need I/O, and thus there is 0.1ms of context switching.

So total time taken by I/O bound process will be= 10*1

But CPU bounded process uses its whole 10ms of time slice and 0.1ms of switching. So it takes total time of 1*10=10ms

And total context switching time=11*0.1=1.1ms

Therefor total time taken=10+10+1.1=21.1ms

and time for which cpu was busy/doing execution=10*1+1*10=20

CPU utilisation=(20/21.1)*100=94%approx

Nullification

Answer 4

I was going through the same question. this is how i understood it In first case , when time quantum is 1 msec, if we think about gantt chart, all I/O bound process will come (lets call p1-p10) followed by p11 which is CPU bound. so total 10 context switches in 11 ms. so effective work done by CPU in that 11 msec is only 11-(10*.1ms) ie 10 ms. so CPU utilization is (10/11)*100= 90%

same way, in 2nd case, there will be 11 switches(last one is of CPU bound process) if i consider 20.1 msec of time. so effective time cpu worked is 20.1-(11*.1)= 19ms. so CPU utilization (19/20.1)*100=94%

Catholicize

Answer 5

I was confused beyond belief for some reason on this question...after looking at all the answers here I finally understood through carefully looking at the jade-cheng link given by another user. There was no formula I could find in the book (maybe I missed it) but here is my version of the answer, in a kind of pseudo-formula style:

WARNING: This is probably wrong, but maybe you can show me where I went wrong.

a)

[(10 I/O processes)(1ms) + (1 cpu process)(1ms)] / [(10 I/O processes)(1ms) + (1 cpu process)(1ms) + (10 context switches)*(0.1ms)] = 10/11 = 91%

b)

[(10 I/O processes)(1ms) + (1 cpu process)(10ms)] / [(10 I/O processes)(1ms) + (1 cpu process)(10ms) + (10 context switches)*(0.1ms)] = 20/21 = 95%

Coryden