CS 414 Prelim 2 Solution Set

1 hour, closed book. 100 points Each question is worth 20 points, and if a question has n parts, each part is worth the same number of points.

1. Suppose that an operating system uses the Banker’s Algorithm for resource allocation. People make accurate worst-case estimates of resource use. But “worst case” is rarely the “typical case. Suppose that we measure the actual performance of the operating system, and find that there is always about 10% or more of each type of resource free – unused.

a) Explain why this might happen with the Banker’s Algorithm.

The Banker’s Algorithm operates very conservatively: it only grants a request if it is sure that some scheduling sequence still exists in which every process can make worst-case requests and that it would still be possible to execute each one to completion in this scheduling order. If worst-case estimates are very pessimistic, this can lead to executions in which the Banker is constantly worrying about scenarios that don’t actually occur.

b) What if we modify the Banker’s Algorithm so that the safety test pretends to have 10% “extra” available for all resources that have large numbers of units. That is, if we actually have 20000 disk blocks and 10 magnetic tape drives, we would pretend to have 22000 disk blocks and 11 magnetic tape drives, etc. Presumably, if we re-measure the performance of the operating system, it will no longer be leaving resources unused. But what other consequences would this change have?

Technically speaking, this change creates the potential for deadlock. But if the observation was 100% accurate and we never demanded the worst-case amount of resources, deadlock should never be observed. We could get the same result by fixing the estimates maximum utilization (which would also seem a bit more honest as a way to address the underlying issue).

Were one to actually make this change, it would be wise to also use a deadlock detection algorithm of some sort, and to terminate deadlocked processes – just in case…

2. Suppose that UNIX user A and user B are working together on a project at their company, and they are both editing a file called “recommendations.” B has the real file and A has a link to it.

a) Suppose that A had a symbolic link to recommendations, and B edits the file using a program that creates a new version, then deletes the old version, and then renames the new version using the old name. A now opens the file. Does A get the new version or the old one (the one that was deleted by B)? Explain your answer.

In this case, A gets the modified version of the file. There is a brief period when A’s symbolic link points to a non-existent file, but then B re-creates the file with the same name, and so A’s link now points to the new version.

b) If A had a real link in part (a), and opens the file after B finishes editing it, which version does it get?

Here, A ends up with a private copy of the old version of the file, before B’s changes were made. The problem is that when B deletes the file, A’s hard link remains in place, so A still has a link to a valid unchanged copy of the old file. Now when B recreates the file, A’s link is using the inode number of the old file, so A sees the old file while B sees the new version.

c) Suppose that the editing program was changed to not delete the old file. Instead, it simply copies the new version on top of the old one, truncating the file if necessary so that the result will have the right length. Would either of your two answers be different if B used this editing program?

In this case, the answer to (a) remains the same, but the answer to (b) changes. Here, B never actually deletes the old file, hence A has a link to the object that B is actually changing. (Hopefully, A doesn’t look at it while it is changing, since this would be confusing). After the file has been updated, A’s link points to the modified version. The key difference between this and (b) is that the file has the same inode number in this case, whereas the inode number changes in (b).

3. Deadlock:

a) List the four required conditions for deadlock.

Hold and wait: Once a resource is acquired you hold it until finished.

Cyclic wait: A waits for B, which waits for C… which waits for A

No preemption: A can’t take a resource away from B while B holds it

Mutual exclusion: if A holds the resource, B can’t hold it at the same time

b) Consider the Dining Philosophers. Describe how each of the conditions you just listed maps to something in the scenario where a deadlock occurs.

Hold and wait: each philosopher picks up one fork and doesn’t put it down until finished eating

Cyclic wait: each is holding one fork and waiting for the fork held by the philosopher to it’s left, causing a cycle of waiting around the table

No preemption: if a philosopher lacks a fork, it can’t grab it from a neighbor who is holding it

Mutual exclusion: only one can hold a given fork at a time.

c) Suppose that one of the philosophers at the table is especially important and famous – people call this person “old graybeard” and tend to defer to him. In particular, when old graybeard wants to eat, everyone else waits (and if someone is holding a fork, they put it down, even if they haven’t eaten yet). Can deadlock arise? Why or why not?

Deadlock cannot arise in this case. Fundamentally, the change eliminates the possibility of cycles. It does this by allowing preemption: graybeard preempts forks held by his neighbors at the table. (This also means that hold-and-wait is violated).

4. A large number of processes are running concurrently. The number of processes is N and the working-set-window size is D, and D is large compared to typical “true” working set sizes. Let d denote the average true working set size for a process. In answering these questions, assume that we are interested in the long-term behavior of the system (don’t worry about weird effects associated with starting a program up, when many of its pages are not yet paged into memory).

a) True or false (explain why): If the paging system is using the working set algorithm, the computer needs D*N pages of physical memory to avoid thrashing.

False. We know that D is larger than necessary – this is stated in the assumptions. We need the true working sets in memory, which may be much smaller than the working set window size that was used.

b) True or false (explain why): Using the working set algorithm, if the computer has less than d*N pages of physical memory, it would be a good idea to implement some form of swapping so that when context switching from process P to process Q, P might be swapped out and Q might be swapped in.

True. In this situation, we won’t have enough memory to hold all the true working sets at the same time, and if we keep less than the whole working set for a process, that process will page heavily. By swapping a whole process at a time, like NT does for DLL’s, we can ensure that when a process is running, it’s entire working set fits in memory, avoiding excessive paging activity.

c) True or false (explain why): Among the fixed-partition algorithms, a good choice would be LRU with partition size d.

True. This might not be the ideal algorithm – LFU could probably do a little better – but as a practical matter, we rarely have the reference frequency information needed to implement LFU, whereas LRU is relatively easy to implement. As a stack algorithm, LRU is generally a safe choice, and the principle of locality suggests that if a page hasn’t be referenced in a while, it probably won’t be referenced again any time soon.

d) True or false (explain why): No matter what form of paging algorithm we use, the performance of any virtual memory system will always be much worse than for a system where the entire memory (not just the working set – all the memory) of all the processes can fit into physical memory.

False. A paging algorithm with the actual working set in memory may have no page faults at all. Having extra pages in memory that turn out never to be referenced won’t speed things up at all. Moreover, the cost of paging may be so small as to be completely negligible even if paging does occur. A well tuned paging algorithm normally runs nearly as fast as having the entire program in memory.

5. Suppose that process p has a virtual address space of 9,000 pages each of size 1000 bytes. Process q has a virtual address space of 5,000 pages. The machine has 100 physical pages. The processes are running concurrently on a single processor.

a. Using a normal (unpaged) page table, with PTE size of 10 bytes, how much memory, in pages, will the page tables for p consume?

90 pages: 9000*10/1000

b. Same question for process q.

50 pages: 5000*10/1000

c. Processes p and q each turn out to have a working set of about 75 pages. Which paging algorithm would you recommend for this case (if no algorithm is suitable, explain why).

In this situation neither p nor q can fit in memory with the page table needed by the hardware while executing either process. If we page the page table, we can presumably keep a single first-level page of PTE entries in memory and a single page of the page table for the current process, leaving enough memory to run one or the other at a time. So one option is to page the page table and swap when context switching from P to Q or back, keeping the actual working set of each in memory when running it. We’ll actually be able to fit 24 pages of PTE entries too, so with luck, we won’t get any overhead associated with page faults on the page tables themselves.

Any attempt to actually fit both in memory at the same time will lead to thrashing, since the working set sizes add up to 150 pages, much more than we have.

d. Using an inverted page table with PTE size still equal to 10 bytes, how much memory, in pages, will be needed for page tables? Would your answer to part c be different in this case?

We’ll need 10 bytes per physical page, hence 10*100 /1000 or 1 page of PTE entries. It will still be necessary to swap when context switching from P to Q or from Q to P, but we can easily fit the working set for the current process into memory if we adopt this approach. This is how NT would do it, for example. While this does give us more “breathing room” we still won’t have enough room to fit both working sets at the same time, so the system will still thrash if we don’t use some form of swapping algorithm.