Jump to content
Urch Forums

From Schaum's OS


wood

Recommended Posts

 

2.26 Given a system that uses round-robin scheduling, assume it can perform a context-switch in zero time. Each process is allowed to run only one instruction before the next instruction is allocated to the CPU. The ready queue always contains n processess. If a process takes t seconds to execute in a uniprocessing environment, how long will it take to execute on this system?

 

Link to comment
Share on other sites

Assuming pure CPU activity (no IO for the processes) I believe running time would be (n+1)t, since there are n+1 processes at the system, and they evenly share the cpu resource.

 

"Each process is allowed to run only one instruction.." bothers me. What they really mean is that caching efficiency is hurt? pipelining is not allowed (or sabotaged)?

In that case the running time would be >= (n+1)t.

 

Rafi

Link to comment
Share on other sites

Rafi, I believe what they mean by "Each process .. instruction.." is that the quantum for the round-robin algorithm is 1, i.e., a given process can just run 1 instruction of its program at a time when it gets the CPU's privileges.

 

Assuming that the context switch time is neglegible, my solution is something along those lines: imagine three process (P1, P2, P3) and that each one takes 4 seconds to finish. Since I can just execute one instruction at a time, the CPU allocation would be:

 

P1 | P2 | P3 | P1 | P2 | P3 | P1 | P2 | P3 | P1 ...

 

As you can see, P1 finishes its job in the CPU's 10th cycle. That makes the answer n(t-1) + 1. In this case, 3(3) + 1 = 10. If it was 5 seconds, the job would finish in the 13th cycle, making it 3(4) + 1 = 13.

 

However, neither mine nor yours are correct. The answer is nt.

 

Any clues?

Link to comment
Share on other sites

Wood, I see your point...

But when the process arrives to the queue it does not necessarily immediatly executed.

 

I guess the unclear point in this question is whether the ready queue contains the running process or not. (or in other words: are there n or n+1 processes in the system).

 

If it contains (thus in any given moment 1 process is running and other n-1 are in ready state) then assume a worst case where our process is the last in the RR sequence (It arrived to the queue, but had to wait for the n-1 procceses to run before it) than the total running time of our process would be

[ (n-1) + 1 ] t = nt

since in any sequence it waits for n-1 and than Executes:

|wait n-1|E|wait n-1|E|...

 

Wood, Can you check in the book how did they define the ready queue? [does it contains the running process?] I'm not sure if there is a convention in this matter...

Link to comment
Share on other sites

Thanks for the explanation.

 

I don't think it contains the running process. The ready queue is defined as a queue of jobs that are not running, but instead ready to take the CPU's cycle. So, to get the next process to run, it must come from the ready queue, which will remain with n-1 process as you pointed out.

 

However, the question never asks for the worst case scenario. Should we assume that by default?

 

Link to comment
Share on other sites

I guess the question is not proper if there is a doubt... I hope ETS' definitions are better...

 

About the n or n+1 matter:

The book "OS Concepts" by silberschatz defines the ready queue as you did (without the running process) I wonder how the book (the one you took the question from) defines it. I really think there is no convention in this matter...

 

Link to comment
Share on other sites

It also defines the ready queue as not having the running process as silberschatz's book.

 

But what I meant is that the running process has to come from somewhere... and this place is definitely the ready queue.

 

Yeah... ETS's definition should be much better. Schaum's outline book series have good exercises but sometimes are not totally comprehensive.

Link to comment
Share on other sites

hi guys

according to definition of rr when process comes to system it is added to the tail of the queue and as far as i understood the task system always has n processes it means that when our one gets into the system one of the processes that were in system before leaves it.

what make u think that quantum of rr equals 1?(one instruction per timeslice? does book have any convention about this matter?)

 

Link to comment
Share on other sites

Romanrostov, "Each process is allowed to run only one instruction before the next instruction is allocated to the CPU." By the definition of RR, a process has a predefined timeslice it can use once it gets the CPU. The statment says that it can only run one instruction before another instruction (of another process or for the same process if the number of proc. is just 1) is allocated to the CPU. Hence the quantum is 1.

 

With the definition of adding to the tail, the problem makes sense then. Thanks!

Link to comment
Share on other sites

taking 3 processes(n) and 4 sec execution time (t)

 

total execution time = waiting time + execution time

 

waiting time can be calculated using Gantt chart.

 

so when p1 enters first, it doesnt wait. then it waits 2 secs. then again 2 and then again 2 secs. after this it is again added to tail nd wait for 2 secs.(for p2 n p3) but will not excute furthur coz its finished and release its resources.

 

so waiting time is 2+2+2+2=8 secs.

exec time = 4 secs

so total exec time = 8+4 = 12 secs = 3.4(n.t)

 

If im wrong then pls correct me...

 

Vinay

Link to comment
Share on other sites

Vinay, you're basically saying that p1 will wait unecessarily for p2 and p3 to complete so that it can have closure?? Why at the 10th cycle, p1 just doesn't finish since it already performed its last instruction?

 

I believe the key is exactly what Romanrostov said. Once a process enter into the system, there's already n-1 processes there and he must wait before executing its first instruction...

Link to comment
Share on other sites

hmmmm then tht makes the worst case scenario thing suggested by rafi valid. I think this is right. by mentioning n processes all the time it is indicating tht thr r n processes already.

 

although if this system is looked as a batch system which contains n processes only which r scheduled among themselves then my intrepretation looks okay. since its written "The ready queue always contains n processess".

Link to comment
Share on other sites

p1 is p1 just for our convenience. whtever process will b first in the queue will not wait. coz in such a system thr will only b n processes which r jobs tht have to run accrding to scheduling algo so as to use system resources efficiently.

 

and moreover thr is no reference to a process running already in the system so assuming tht it shud wait is also not looking correct.

 

but i think here in this ques tht n-1 funda looks correct.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...