Systems Comprehensive Exam Questions Sorted by Topic

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.

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.

1. A web indexing system used by companies such as Google, where the data updates are web pages crawled by concurrent web spiders, and the backend processes the resulting archived graph of web pages to generate indexes that are used to satisfy search requests.
2. A business database/intelligence system for a web retailer such as amazon, where the data updates are sales orders generated by web servers which include the contents of the order, the customer ID of the person placing the order. The resulting database is used both for:
3. 1. Tracking inventory and order status by web applications
   2. Mining suggestions to customers about what to purchase

The potential need for consistent snapshots of the data being acquired by the front-end systems;

The potential need for consistency versus data acquisition performance between multiple writers in the front-end data acquisistion systems;

The potential need for consistency versus data analysis performance between front-end data acquisition writers and back-end data analysis readers.

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

The code in figure 1 implements a simple lock-free single-reader/single-writer FIFO ring buffer. Indicate where if anywhere write barriers must be added to guarantee correctness of this code on a modern multiprocessor system, and what specific error each write barrier you add is needed to guard against. Because write barriers are expensive on multiprocessor systems, it is important that you not add any unnecessarily!

 1   typedef struct ringbuffer {
 2       /* Buffer is empty if rb->head == rb->tail. Buffer is full if
 3        * next(rb->tail) == rb->head */
 4       void **head, /* Points to first occupied element in buffer */
 5            **tail, /* Points to first free element in buffer */
 6       void **buf, /* Points to the start of the allocated ring */
 7            **end; /* Points one element *past* the allocated ring */
 8   } ringbuffer_t;
 9
10   void **RingbufferNext(ringbuffer_t *rb, void **item)
11   {
12       void **next = item + 1;
13       if (next >= rb->end)
14           return rb->buf;
15       else
16           return next;
17   }
18
19   int RingbufferAppendSingle(ringbuffer_t *rb, void *value)
20   {
21       void **next = RingbufferNext(rb, rb->tail);
22       if (next == rb->head)
23           return -1;
24       *rb->tail = value;
25       rb->tail = next;
26       return 0;
27   }
28
29   int RingbufferRemoveSingle(ringbuffer_t *rb, void **value)
30   {
31       if (rb->head == rb->tail)
32           return -1;
33       *value = *rb->head;
34       rb->head = RingbufferNext(rb, rb->head);
35       return 0;
36   }

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. (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?

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.

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.

1. Assuming short messages that can fit in registers, what steps are involved in the complete Mach- style synchronous RPC, and which steps can be removed in the optimized migrating threads version?
2. One difficulty with a migrating threads model of RPC is that the thread usually runs entirely in the resource allocation context of the caller. With multiple callers to a single service, show how this can lead to priority inversion.

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. 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. (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.

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?

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.

• 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)

• 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. (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. (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?

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. 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. 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?