UNM Computer Science

The test monitor will answer some parts of these questions for you if you are unsure of what some of these terms mean. The only penalty is that you will not get any points for the part that was answered for you. You can still answer the other parts of the question. This can get you started on a question even if you are not sure of the definitions.

Do enough questions to total at least 100 points. It is okay to go over 100 points and you can answer as many questions as you wish but all the questions you answer will be counted in your grade and the total will be normalized to 100 points. We will not take the best 100 points.

1. (Election algorithms) (20 points) In a parallel operating system it is sometimes necessary to have an election, that is, one of the machines on the network is elected to fulfill some function (like be a file server). Describe as many situations as you can where such an election would be necessary. Sketch out one algorithm to do such an election. Analyze the algorithm in terms of the likelihood that different kinds of failures will cause the algorithm to fail.
2. (Device drivers and file system drivers) (20 points) The device driver interface essentially virtualizes a disk drive, that is, it provides a common set of function that can be used to control any disk drive. This allows the rest of the operating system to treat all disk alike. Give an example of a disk driver interface, that is, give on example of a common list of functions that a disk driver will provide.

   Most modern operating systems can handle several different file system organizations. Give two different file system organization and describe them briefly. Operating system usually provide this functionality with a file system driver. A file system driver is like a disk driver but it virtualized a file system with a common set of functions. Describe a possible interface to a file system driver, that is, a common set of functions that can be used to control any file system.

3. (Load control) (20 points) An important aspect of a virtual memory system is load control. Describe what the load control is and why it is important. Give one algorithm for load control and describe why you think it will work.
4. (Authentication) (20 points) What is authentication in an operating system? What is it used for and why is it important? What are some common methods of authentication? Why is authentication more difficult in a distributed operating system? How is cryptography used for authentication?
5. (Memory Caching) (20 points) Memory caches can work with either virtual addresses or physical addresses. Which is the most common? What are the tradeoffs between these two techniques? Describe two situations, one where each of the two techniques would be preferred.
6. (Pipelining) (20 points) The typical instruction interpretation pipeline for a RISC processor has four or five stages. Describe each of the stages in an instruction interpretation pipeline (four or five stages, your choice). Explain the difference between simple pipelining and super pipelining. What does the term superscalar mean?
7. (Memory latency) (20 points) Memory latency is probably the most fundamental problem in the design of modern computing systems. Why is memory latency such a fundamental problem? That is, if we can make processors so much faster, why can't we make memory so much faster? What is a ``multithreaded'' architecture? Explain how multithreaded architectures address the problem of memory latency. What does ``out of order execution'' mean? How does out of order execution address the problem of memory latency?