Final Exam
Operating Systems
CS-521
Spring 2012
Answer any five from the following
1. Operating systems designers all tend to support the observation that Kernel Level Threads (KLTs) are slower than User Level Threads (ULT) because KLTs “involve two mode switches per thread switch”. Comment rationally on this observation using all thread models including the Solaris one. If KLTs are slower than ULTs why use the KLTs at all if an alternative to KLT is available?
2. In real memory allocation problems, various composite allocation strategies could be designed that might offer some advantages over the standard allocation schemes. Assume our hypothetical free-memory list to be as shown in the diagram below.
One composite allocation design could be to launch First Fit scheme alternately from the opposite ends. For instance, if the last First Fit allocation traversal had started from the list position ‘a’, the current search would begin from position ‘b’ along the direction shown. How does this scheme perform compared to the standard ones?
3. In this question, we again consider the real memory allocation scheme. We assume our free list to be circular, and we use a modified ‘Next Fit’ allocation scheme with the following changes. Instead of beginning the list traversal from the position where we last halted, we generate a uniformly distributed random number , and begin searching the list sequentially from the position . How does this scheme fare against the conventional schemes?
4. If average response time of all processes in a given system is not a crucial parameter, one might surmise that deadlock ‘avoidance’ should be considered system’s operational policy as opposed to having no specific operational policy on deadlock events. Comment on this strategy.
5. Suppose that the virtual page reference stream contains repetitions of long sequences of page references, followed occasionally by a random page reference. For example, the sequence: 0,1, 2, …,511, 431, 0, 1, 2, …,511, 275, 0, 1, 2 … consists of repetitions of the sequence 0, 1, 2, …511 followed by a random reference to pages 431, 275, etc.
a. Why won’t the standard replacement algorithms (LRU, FIFO, Clock) be effective in handling this workload for a page allocation that is less than the sequence length?
b. If this program were allocated 500 page frames, describe a page replacement approach that would perform much better than the LRU, FIFO or Clock algorithm.
6. Show and explain how one could depict the following situations using appropriate Petri Nets. (a) Deadlock state (b) Mutually exclusive sharing of a common resource by processes. Suppose instead of using only one type of tokens, the system is allowed to use colored tokens. Can you suggest how this could expand the conventional net semantics to a more enriched one?
7. Show that for a disk head initially moving in the direction of increasing or decreasing track number, SCAN and C-SCAN results would be different. Why would you claim that SSTF and LOOK could be considered reasonably well behaved algorithms?
8. A RAID can fail if two or more of its drives crash within a short time interval. Suppose the probability of a drive crashing within a given time is . What is the probability of drives crashing within the same time bracket? RAID level 3 is able to correct single bit errors using only one parity drive. What is the point of RAID level 2? After all, it also can only correct one error and takes more drives to do so.
9. If a CPU’s maximum voltage, , is cut to its power consumption would drop. Suppose that a user is typing 1 char/sec, and the CPU needs 100 msec to process each character. What is the optimal value of and what is the corresponding energy saved compared to not cutting the voltage? Assume that when the CPU idle it consumes no energy.