Systems Comprehensive Exam Questions in Chronological Order

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.

1. (5 points) Describe the matrix model of protection.
2. (5 points) Describe the access-list method of protection and how it relates to the matrix model.

1. (5 points) Contrast the terms "write-through" and "write-back" when applied to cache line replacement.
2. (10 points) Explain how you can implement coherence on a shared bus multiprocessor system when each processor uses a write-back replacement policy.

1. (5 points) Given the example of 120 MB/S for the memory bus and 60 MB/S for the network, what is the effective message bandwidth if every message requires a memory copy (you should ignore other overheads that might be introduced). Repeat this calculation assuming that the memory bandwidth is 10 MB/S and the network bandwidth is 2 MB/S.
2. (15 points) Discuss the problems that must be addressed when delivering messages directly to the memory for an application

1. (3 points) In such a system it would be better to call the units of execution threads rather than processes. Explain why.
2. (8 points) Suppose you were to take a more conventional multiple-address-space operating system and convert it to a SAS operating system. Describe the changes you would have to make the accomplish this.
3. (6 points) What are the advantages and disadvantages of a SAS operating system over a multiple-address-space operating system?
4. (5 points) How would memory protection be handled in a SAS operating system?
5. (3 points) Some recent processors have 64-bit virtual address spaces. Why are SAS operating systems attractive for such processors?

1. (8 points) Explain what context switching in an operating system is. Go into some details and describe what happens in both the hardware and the software during a context switch. Explain what a half-context switch is. Talk about the registers and what happens to them.
2. (6 points) Context switching is not possible without some help from the hardware, that is, an instruction specially designed to do the critical part of context switching. Explain why such instructions are necessary. Be sure to describe the problem and why it cannot be handled with ordinary instructions.
3. (6 points) Context switching slows down the processor by quite a bit. We are not talking about the time to execute the context switch itself but side effects from the context switch. Explain why this is so, that is, describe why the process is slowed down after a context switch.

1. (6 points) Decide on a good size for each page and the number of address bits assigned to each level. Draw a diagram of the logical address and how each part is used.
2. (9 points) Draw a diagram that explains how the address is translated from a logical address coming in from the processor to a physical address to the bus. Include the TLB in your diagram and show where it fits it. Use text annotations so that the diagram stands by itself and can be understood easily.
3. (5 points) Suppose a memory read cycle for a physical address put on the bus takes 50 ns. The processor will not see this speed because of the overhead for address translation. Suppose we wanted the processor to see an average 60 ns memory read time for reads from logical addresses. What would the hit rate on the TLB have to be to achieve this goal.

Describe how an OS for a PDA will be different from an OS for a normal computer system. First, describe the differences in the OS services as seen by the users, that is, define how the set of system calls will differ. What is added, what is removed and what is modified? Second, describe how the implementation of the OS will differ. How are the new or modified system calls implemented? How are the same system calls implemented differently? How is the overall structure of the OS different? It is useful to think about the data structures the OS will maintain and how they are used and modified.

Consider three paging mechanisms: (1) ordinary paging with a single page table, (2) paging with two levels of page tables, and (3) inverted page tables. For each one of these mechanisms give the method used in operating systems to map logical file offsets to physical disk block numbers that most closely corresponds to the paging mechanism.

For each corresponding pair explain what the similarities are and what the differences are (because the correspondences will not often be exact). For each difference explain why they are different in terms of hardware differences or design goal differences. For each similarity explain why we were able to make them similar, that is, how the hardware or design goals allow them to be similar.

Note:To be sure you understand what we are talking about here, an example of a file block mapping method is the UNIX method where the file descriptor contains 13 disk block addresses, 10 direct, 1 indirect, 1 double indirect, and 1 triple indirect.

Paging also allows virtual memory as well as address translation. Is there any similar concept in the file system situation? If so explain what it is and if not explain why there is not one.

1. Explain what a file system driver is and why it is useful.
2. Give a list of typical functions that a file system driver would define for use by the rest of the operating system.
3. The device driver concept allows generalizations such as RAM disks, pseudo-ttys, and drivers that control disk partitions or several disks. File system drivers have also been generalized this way. Give some examples of the use of file system drivers that do not access a traditional file system on a disk.

1. (8 points) Explain what the benefit(s) is/are.
2. (6 points) Explain problems involved with respect to memory management if hardware DMA is set up for block transfer in such an environment.
3. (6 points) Which further optimizations to basic message passing are meaningful if communication is to be sped up, especially considering the fact that on Myrinet the data is not only to be transferred to the net but also between PC and Network Interface memory?

Give a brief description of the most important trends that have led to the development of PIMs. Give a brief description of one way in which PIMs could be used in the design of a computing system.

Suppose that a TCP implementation advertises a larger flow control window than it has buffer space available. Discuss the possible advantages and problems associated with doing this.

1. Define sequential consistency. Pick and describe one specific weak consistency model.
2. Construct and show an example in which sequential consistency and your chosen form of weak consistency will return different results.

1. What are the advantages and disadvantages of each approach?
2. How does the choice of a caching mechanism relate to options for maintaining consistency and coherency in the file system?
3. How suitable is of each approach to dealing with disconnected operation (i.e., the access of cached data when disconnected from the network)?

1. Assuming a two-level page table, show the actions necessary for providing copy-on-write sharing for one page of data between two processes.
2. In some cases, immediately copying the data may be quicker than remapping the data. Which factors should you consider in determining which approach is better, and how do each of these factors effect the performance of each approach?

1. What is the difference between normal data and metadata in a file system?
2. In what ways do these differences impact file system design?

1. A method that is transparent to the application
2. A method that exposes the state of the hard disk to the application, allowing the application to participate in the decision of when to spin up the hard disk

Background

System Optimization

1. What restrictions on application behavior are necessary with this approach? Are these restrictions fundamental, or could they be worked around with modifications to the proposed optimization scheme?
2. As it involves changes to both the hardware configuration and the system software runtime, the pro- posed optimization affects application performance in a variety of ways. Describe in detail the potential costs and benefits of this optimization in terms of its effect on expected total application runtime.
3. Given your answers to the previous questions, under what circumstances is this optimization worth doing? For a given hardware system and application, what measurements would you suggest taking to determine whether or not to perform this optimization?

1. Discuss the potential benefits and costs associated with page pre-fetching in general terms.
2. Consider the following four levels: language implementation, runtime/libraries, operating systems, and architecture. For each of these levels, describe the relevant information that could be obtained to support page pre-fetching and how this could be used to implement page pre-fetching.
3. Describe one instance of how you could integrate information provided by multiple levels to improve the benefits of page pre-fetching.
4. Suppose that you have to choose one of the four levels to instrument. Which do you believe will yield the best benefit/cost ratio and why?

To make this scenario plausible, there are at least two research areas that must be explored:

1. Communication infrastructure services are needed that take into account speed and direction of travel.
2. Coherence and consistency of the information exchanged in these conversations must be addressed.

• A single global scheduler
• Individual per-processor schedulers that interact with a global scheduler that assigns jobs to processors.
• A hierarchy of interacting processor schedulers.

• The size of the machine (which can range from two processors up to several hundred processors)
• Application characteristics (e.g. job lengths, job-level parallelism, and synchronization behavior)
• Operating system parameters (e.g. length of scheduling quantum)

How might you use such a router in the implementation of a parallel file system where one of the port pair will be used to connect the parallel file system to the outside world and the remaining port pairs would be used to connect systems that provide the processing and storage space needed for the file system? Pay particular attention to how you would partition functionality betweeen the switch and the systems connected to the switch.

• Unified versus split caches
• Direct-mapped versus associative caches
• Cache size, cache access time, line length, and number of cache levels

• What metrics are appropriate to determining the quality of service provided by such an elevator system?
• How can such a system fail to provide adequate service under heavy load?
• Are the metrics the system seeks to optimize different under light and heavy loads?
• How can the system be changed to provide adequate service under heavy load, for example by having separate service policies for light and heavy load?
• In such a system, how and when would the elevator system switch between policies for light and heavy loads?

1. Carefully define what is meant by the memory wall problem.
2. How have normal processor architectures (e.g. Intel x86/Motorola PowerPC) attempted to deal with this problem, and why is or isn't this approach sufficient?
3. Does a PIM architecture like that described above address the memory wall problem, and what new difficulties does it present?

1. How does the optimistic synchronization and concurrecy control differ from the normal pessimistic approach both in general and in your example?
2. What are the general advantages and disadvantages of the optimistic and pessimistic approaches? For your example, under what conditions would an optimistic and pessimistic approaches be preferable?

Consider a system where each sensor system has local power (e.g. solar/battery), limited storage, and connectivity to first responders in its immediate physical vicinity. The primary goal of this system is to make local sensor information available to local first responders while it logs updates to send to central facilities when long-range connectivity becomes available.

Such a system is similar in ways to a disconnected/weakly-connected file systems like Coda. Compare and contrast approaches for utilizing or dealing with the following issues with how they are handled in systems like Coda:

• Replication and consistency
• Caching
• Transactional semantics