Final Examination A from Spring 2000

This was a similar course, but not exactly the same schedule, syllabus, or text

Question 1. Virtual Memory - Page Replacement

No. Never say, "never" or "always."

Impossible goal of page replacement: Predict future access patterns to minimize the number of page faults. Consider also

1. Shared page is probably read only
2. Which page has been modified?
3. Priority of using processes
4. Shared does not necessarily imply frequent access
5. What process generated the page fault leading to selecting this victim? Does the choice affect the working set size?
6. Even if the page is shared, removing it only generates a page fault in the next requesting process

Question 2. Virtual Memory - Locality

1. Top-down approach
2. Minimal use of GOTOs
3. Modularity
4. Recursion
5. Iteration
6. Object-oriented

Define "locality." See Section 9.7.

Beware of "party lines." Each technique can be good or bad, depending on how it is used.

Question 3. File Operations

Question 4. File Protections

This is probably the hardest question on the exam. There is much you can say about access lists and about user control lists, but "Discuss the relative merits ..." is harder.

Access list: Who can access this file?

User control list: What can this user do?

Criteria:

• Effective: Both work, in theory
• Speed: Neither works, in practice
• Improvements to make practical: Both are too large to implement. In the pure form, each has the same number of entries, the number of non-empty entries in the access matrix. To make a practical implementation, we need to group users (for the access list, e.g. owner, group, world) or group files (for user control list, e.g. mine, other users, system).
• Who owns the data? In general, it makes sense for the owner of a resource to control who has what access to the resource. For user control lists, that implies that one user, through the OS, alters the user control lists of other users, a potential security hole.

Operations:

• Create or remove file/user. If information is stored by file (access list), it is hard to update when a user is created or removed. If the information is stored by user (user control list), it is hard to update when a file is created or removed.
• Access. Not much difference. Several people suggested the OS needs to read the disk to retrieve the file access list. True. However, although it would make more logical sense to have the user control list in memory, it is FAR too large to do so, unless files are grouped.
• Backup & restore. If we backup files (including the user control list) and restore them later, do we get accurate access lists or user control lists? Probably not.

Both are essentially the same in many ways. Both Windows and Unix use access lists with very coarse groupings of users, so we have been trained to say that is the right answer. I rather prefer grouping users as owner, group, world to the alternative of grouping files as mine, yours, system. Hence, I tend to prefer the access list approach.

Question 5. Distributed Architecture - Token Ring

Detect: timer. Either one special or each computer times how long it has been since it last saw the token. How long is, "Too long?" It may help if each machine has a different (somewhat random) time threshold to reduce the chance of two machines detecting a lost token at the same time.

Generate replacement. Hard. Do not want two tokens. No one can send to its neighbor without the token. Treat an "election" as a special emergency situation. If a machine suspects the token is lost, it sends a ballot with its ID. When a machine receives a ballot, if it has recently generated a ballot itself, it assumes this is a duplicate, and destroys this one. A sophisticated time stamping system is necessary to prevent that ALL ballots are destroyed. If a machine determines this is not a duplicate, it adds its ID to the list and passes the ballot on.

If a machine receives a ballot that already contains its ID, the election is complete. If its ID is the largest, this machine won the election and generates the replacement token. If this machine did not win the election, it passes the ballot along and does nothing. Eventually, the ballot gets to the machine with the largest ID, which declares itself the winner and generates a token.

Alternative by Jessica Barrington: Use a pseudo-token rotating behind the real one. If a machine sees the pseudo-token twice without seeing the real one, it promotes the pseudo-token to a real one and then generates a new pseudo-token. Similarly, if a machine sees the real token twice without seeing a pseudo-token, it generates a new pseudo-token.

Another alternative is to have a dedicated monitor machine, but that adds to the cost. What happens if the monitor goes down?

Question 6. Connection-Oriented vs. Connectionless

"Compare and contrast X and Y" should invoke a standard response template:

1. Define X.
2. Define Y.
3. How are X and Y similar?
4. How are X and Y different?

A typical "compare and contrast" answer addresses both similarities and differences, but tends to emphasize one over the other. Your answer to this question should be structured by the question:

1. Describe Connection-oriented service. Give an example.
2. Describe Connectionless service. Give an example.
3. More predictable? Connection-oriented
4. Better network utilization? Connection-oriented for large data transfers. Connectionless for little data.
5. Problems with sequencing? Connectionless
6. Higher user charges? Connection-oriented for large data transfers. Connectionless for little data.
7. Addressing information? Connectionless

Tell why.