AlbaLed Posted October 30, 2003 Share Posted October 30, 2003 1. Can a process make a transition from the Ready state to the Blocked state? Why or why not? 2. In the round-robin scheduling, why can't you start new processes at the front of the queue instead of at the end? 3. Provide definitions for the following terms: program process process state processor multiprogramming time sharing non-determinism 4. What is spooling? Why is a printer spooling system better than direct user access to printers? Other OS questions 5. Why do computers have (at least) two modes, a user mode and a kernel mode? How does one go from one mode to the other and viceversa? Explain in detail then for each of the following operations indicate if it should be done in user or kernel mode: (a) Read the time of day clock (b) Set the time of day clock (c) Start an IO operation (d) Disable interrupts 6.Consider busy waiting for entry into a critical section in a shared memory system. In which scenario (or scenarios) below would this not be considered an unreasonable approach? a. When there are few CPU-bound processes in existence b. When a dedicated processor can be assigned to perform the busy wait c. When the expected wait is less than the time needed to perform a context switch d. None of the above- busy waiting is always unreasonable since it does nothing but waste processor 7. What is the distinction, if any, between Interrupts, Exceptions, and Traps. [color=Red] 8. Tasks T1 and T2 execute concurrently & share the integer variables X, Y initially set to 0. Task T1 executes: | and T2 executes: | X := 0; | Y := 0; if X X := X + 1; | X := X - 1; Y := 2; | Y := 1; What are the possible values of X and Y when these tasks terminate? 9. Here is a possible implementation of the lock operation for a spinlock. void lock(int &s){ while (TestAndSet(s)) while (*s == 1); } Explain in detail what is being done and why. [TestandSet sets s to 1 and returns the value it had when the instruction was called]. [/color] Quote Link to comment Share on other sites More sharing options...
wood Posted October 30, 2003 Share Posted October 30, 2003 1. Can a process make a transition from the Ready state to the Blocked state? Why or why not? Unless there's a catch, I don't it can. In order to get to a blocked state, the process must start running and initiate an I/O operation. 2. In the round-robin scheduling, why can't you start new processes at the front of the queue instead of at the end? It wouldn't be fair to processes that take a long time versus very small processes that takes few quantas to complete. Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted October 30, 2003 Author Share Posted October 30, 2003 Originally posted by wood 1. Can a process make a transition from the Ready state to the Blocked state? Why or why not? Unless there's a catch, I don't it can. In order to get to a blocked state, the process must start running and initiate an I/O operation. Good!! No catch, what were you thinking, everyone thinks like ETS !!! 2. In the round-robin scheduling, why can't you start new processes at the front of the queue instead of at the end? It wouldn't be fair to processes that take a long time versus very small processes that takes few quantas to complete. I think the question asks when a new process is inserted in the queue why not insert it in front of the queue. If this is how you understood the question, can you please be a bit more elaborate and give an elucidating example? Quote Link to comment Share on other sites More sharing options...
procastinator Posted October 30, 2003 Share Posted October 30, 2003 1. Can a process make a transition from the Ready state to the Blocked state? Why or why not? I think the answer is yes!!! eg: time-sharing, waiting for I/O..... Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted October 30, 2003 Author Share Posted October 30, 2003 Originally posted by procastinator 1. Can a process make a transition from the Ready state to the Blocked state? Why or why not? I think the answer is yes!!! eg: time-sharing, waiting for I/O..... wood can you explain, plz Quote Link to comment Share on other sites More sharing options...
wood Posted October 30, 2003 Share Posted October 30, 2003 Alba, what I meant was: let's assume that processes that get added to the front of the queue are the next ones to be picked by the RR algorithm. If that is the case, in a system where many many processes are being constantly fired off, old processes could starve since the new ones will have "higher priority" and therefore the old ones will never getting a chance to have their share of the CPU. Hope that's clear... huge headache today... hard to put words on paper, well, on the screen. Wood PS: by the way, can you remove the annoying [ quote ] [ /quote ] when you reply? That will make my eyes feel much better. The font size for quoted messages are killing my eyes, specially during late nights... :) Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted October 30, 2003 Author Share Posted October 30, 2003 You got it right this time, and making much more sense, keyword "starve". Hey here is a tip for your eyes, if you have a scroll mouse, and using ie, press control and scroll, you should be able to change the size of the font, I use it all the time. No more quote Quote Link to comment Share on other sites More sharing options...
Vinay Posted October 30, 2003 Share Posted October 30, 2003 2) as long as time quantum is thr it can be implemented in any of the way whether front loading or back loading. 3) - program is refered to as code tht is to be executed stored in a file. - process is program in execution in CPU or waiting for it in ready queue - process state is the state of process whether ready,blocked,supended,running,new - processor is the machine tht executes process instructions, comprises of various components tht aid it in doin so like math coprocessor etc. - multiprogramming is ability of a system to run multiple programs on the same cpu. - time sharing means sharing resources of system including processor by multiple users on the basis of time. - non determinism means state of not being able to be determined by following set order of procedure. 4) spooling - simultaneous peripheral operation on-line is a mechanism in which a seperate buffer called spool is used to provide multiple access to device like printer. this is required coz otherwise ouputs frm different users can get mixed up. in this mechanism output is copied as a file and queued up to be sent to rpinter one by one thus avoiding complete mess. Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted October 30, 2003 Author Share Posted October 30, 2003 Vinay, assuming by front/back you mean front = side from where ready porcs are taken for execution, back = not front See wood's explanation, basic idea is it may result to starvation, not of just one process but to a whole bunch of processes, imagine a new process is created deliberately or not every quantum, all process in the queue will be there for a quite long amount of time Spooling, also it makes it easier for programmers, no need to manage connection, processes can also return quickly after calling a spooling function such as print(document) Nice job vinay Quote Link to comment Share on other sites More sharing options...
Vinay Posted October 30, 2003 Share Posted October 30, 2003 wht I m saying is tht rather thn taking out front one and puttin it at end as is usually done in queue, the first one get executed and then last one is brought to the front and the original one will get pushed back till it gets its turn. in this interchange of front and rear, the things will not change coz the new process will simply execute for quantum time. after its quantum is over it is pushed and new process is brought frm back to front. waiting time remains the same as each process executes only for its quantum as in the original case. The scenario tht you have put abt aging can also occur in usual span of working coz same thing will happen thr. new processes will be added to end and when the front processes finish they move to the end. infact the organisation doesnt affect the performance of RR wht affects performance is time quantum. Quote Link to comment Share on other sites More sharing options...
wood Posted October 30, 2003 Share Posted October 30, 2003 No Vinay. I think you're missing the point. Let's say you have P1, P2, P3, and P4 on the queue. Now, a burst of P5 until P2005 come in, in just a fraction of a second. P5 will thus get its nice quick quantum share for 1ns, for example. After P5 finishes, it goes to the end of the queue. Now, P6 will come in right after P5 and get its share too (1ns)... P7 too... P8 again... until P2005. There will be therefore 2000 processes that got the CPU prior to P1, P2, P3 or P4!! Let's say now that at the end of P2005, a whole bunch of more than a sum of googolplex processes come in!! Stil... your initial P1, P2, P3, and P4 didn't get a chance to run yet.. So they might starve if this vicious cycle of starting processes never ends. Wood Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted October 30, 2003 Author Share Posted October 30, 2003 googolplex Quote Link to comment Share on other sites More sharing options...
wood Posted October 30, 2003 Share Posted October 30, 2003 Thanks... I love that number for some eerie reason! I don't know though when I'll need to use it... but, I use it in my day-to-day vocabulary as well. People get perplexed. :D Quote Link to comment Share on other sites More sharing options...
Vinay Posted October 30, 2003 Share Posted October 30, 2003 wht you r saying is wht I am the thing is I have reversed the queue direction. its is still FIFO and not LIFO as you might think wht I m saying. In case of LIFO obviously aging or in your example super aging will occur, infact process P1 will not be able to walk forever and remain stuck in the bottom of tht queue ;-) Quote Link to comment Share on other sites More sharing options...
Vinay Posted October 30, 2003 Share Posted October 30, 2003 5) majorly for security purposes and also to provide a kind of layering between wht user can do and wht user cant do so tht their functionality remains independent. thru interrupts the modes r changed. a) user mode b) kernel mode c) kernel mode d) kernel mode Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted October 30, 2003 Share Posted October 30, 2003 1. Can a process make a transition from the Ready state to the Blocked state? Why or why not? Yes. If the OS steals a resource that it was using. Not all OS's can steal resources, though. 2. In the round-robin scheduling, why can't you start new processes at the front of the queue instead of at the end? Because the other processes might starve. Just like at the baseball game, if some pig kept repeatedly skipping to the front of the line to get another basket of nachos, the rest of us would never get to buy our Cokes. 3. Provide definitions for the following terms: program = a sequence of binary instructions process = an instance of a program process state = the present set of voltages in all sequential (non-combinatorial) circuits utilized by this instance of the program processor = a piece of hardware that obeys the instructions multiprogramming = multitasking time sharing = supporting multiple simultaneous users by allocating some resources to each non-determinism = a program's output is not a strict function of the program's input 4. What is spooling? Why is a printer spooling system better than direct user access to printers? Spooling is buffering I/O for asynchronous handling. It is good, when you can do it, because it evens out load spikes. 6.Consider busy waiting for entry into a critical section in a shared memory system. In which scenario (or scenarios) below would this not be considered an unreasonable approach? a. When there are few CPU-bound processes in existence b. When a dedicated processor can be assigned to perform the busy wait c. When the expected wait is less than the time needed to perform a context switch d. None of the above- busy waiting is always unreasonable since it does nothing but waste processor © This is typically the case on a multiprocessor system when you are on one CPU and want some resource held by a proc on another CPU. If you know for a fact that the other process is being run, and that it won't be very long before it releases the resource, and you know that there's nothing else useful for your process to do (think about user-level threading), then you might as well wait. Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted October 30, 2003 Author Share Posted October 30, 2003 1. Can a process make a transition from the Ready state to the Blocked state? Why or why not? Yes. If the OS steals a resource that it was using. Not all OS's can steal resources, though A process can move to different states only when it is running, the question however asks about Ready state. What do you mean by resource stealing, the OS steals resources from processes is queues??? Quote Link to comment Share on other sites More sharing options...
nonevent99 Posted October 30, 2003 Share Posted October 30, 2003 Originally posted by AlbaLed 1. Can a process make a transition from the Ready state to the Blocked state? Why or why not? Yes. If the OS steals a resource that it was using. Not all OS's can steal resources, though A process can move to different states only when it is running, the question however asks about Ready state. What do you mean by resource stealing, the OS steals resources from processes is queues??? In general, it is definitely true that a process cannot go directly from ready to blocked. Even if resources were stolen while the process was in a queue, in most OS's, the process would have to move to the running state before it would "discover" that it no longer has the resources that it needed. From there it would move to the blocked state. cf, for example http://arcib.dowling.edu/~KichukoG/OS/hw/hw2/hw2.txt http://www.cs.mu.oz.au/332/tute/s2_proc.a On the other hand, if the OS knows more about what's going on inside the process, or if it doesn't distinguish between ready and running, then it might decide to do the process a favor and simply move it to the blocked state (thereby shortening up the queue). See, for example, http://perso.wanadoo.fr/wilhem/documentation.htm http://www.csee.wvu.edu/~jdm/classes/cs450/exams/Sp2002/exam1.key.pdf This last link, in particular, states on pg 4 that "A transition from ready to blocked is unlikely, but may occur in preemptive systems." However, given that the bulk of the pages out on the web say ready->blocked is impossible, I might have to change my answer to say that it is impossible (ie: simply forget about nutsy preemptive systems that violate fundamental rules of state). Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted October 30, 2003 Author Share Posted October 30, 2003 Wood, how long would it take a computer running at 999YHz (Yotta-Herz, 10^24), to simply count up to a googolplex? Quote Link to comment Share on other sites More sharing options...
wood Posted October 31, 2003 Share Posted October 31, 2003 Well, Googol is 10^100. Googolplex is 10^Googol. Running in a computer which can print 10^24 integers per second and considering that in a year we have in average, approximately, 3.155*10^7 seconds, the kick-butt computer can generate 3.155*10^31 integers per year. The computer would take 10^100 / 3.155*10^31 = 3.17*10^68 years to count to Googol! And counting to Googolplex, it would take approximately a little less than 3.17*10^Googol !! Wood Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted October 31, 2003 Author Share Posted October 31, 2003 So now, if I had googol $ would you help me count them ???!!! I found this prob. in the internet, where some guy wanted not only to count but store them, where in the very same page he was saying that in the universe there are 10^80 particles, what a genious!!! Quote Link to comment Share on other sites More sharing options...
wood Posted October 31, 2003 Share Posted October 31, 2003 Hehe... there's actually ongoing research on this (don't know how serious is that). People are trying to see how long should they wait (considering Moore's law of performance) to start "counting" Googolplex. I'll see if I can find some links... Quote Link to comment Share on other sites More sharing options...
randhawa Posted October 31, 2003 Share Posted October 31, 2003 Ans 6) b and c a) If there are few CPU bound processes and more resource-bound processes, things get worst since the less CPU bound processes have to wait for the (many) IO bound process to complete. Hence a is wrong b) If we have a dedicated processor for the task then it doesn't cast ant sideeffect on other processor's execution. (No cycle stealing needs to take place since the processor would wait without acessing the bus too often) c) As nonevent99 has pointed out 8) I assume there has been some typo... X is not incremented anywhere hence the condition "if X > 0" would allways be false. T2 would finish after T1 finishes and sets Y = 2 hence the final vale of Y=1.. whereas the value of X can be anything ( 9. I think "s" is the resource for which lock is intended. while (TestAndSet(s)) loop performs the spin operation over s. as soon as s is in unlocked, TestAndSet returns 1 and *s is set 1 (what does it do... donnt know.. guess, would allocate the resource to the calling prog) Quote Link to comment Share on other sites More sharing options...
AlbaLed Posted October 31, 2003 Author Share Posted October 31, 2003 randhawa, thanks for pointing out the typo, it should have been if(x Question 6. I think nonevent got it right, but only in the case of multiprocessor system, in the case of a uniprocessor system answer would be E. Adding another processor for the sole purpose of busy waiting does not seem a reasonable solution, because the process holding the resource needs to run on the other "doing-work" processor. What would happen if two processes were to wait, we would need two busy-wait processors? If we add another processor, it is much better for the added processor to help in doing real work so that resources are released faster. About the spinlock question (9) void lock(int &s){ while (TestAndSet(s)) while (*s == 1); } The first while loop will "spin" if the current value of s is 1, then the next while waits until this value becomes 0, at this time this process may be preempted and another process might set s to 1, so when this process gets the cpu again s would be 1 again and it will spin again. If the process is not preempted after loop 2, loop 1 will run again and set the s to 1, making all other processes wanting this s "spin". Does this make sense? Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.