UNM Computer Science

Operating Systems and Architecture

Comprehensive Exam
Computer Science Department
University of New Mexico
August 14, 2001

Do any five questions. Answer only one question on a sheet of paper and write only on one side of each sheet. An answer can continue on several sheets. In this case, only write on one side of each sheet and number the sheets. Write on each sheet the number of the question you are answering.

You can use a computer as a word processor for this exam but you cannot access any information on the computer or on the internet or run any other programs to help you answer the questions.

1. PDA operating systems (20 points)

   Development of computers has gone below the notebook scale toward personal digital assistants (PDAs) such as the Palm Pilot. These computers have operating systems like larger computers but they are structured differently because of the different hardware environment. Among the issues to consider are things like: no disk, the need to minimize power consumption, accommodating a range of hardware add-ins, etc.

   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.

2. Logical Addressing (20 points)

   There are two parts of an operating system than map logical to physical addresses, the paging system and the part of the file system that maps logical file offsets to physical disk offsets. They use similar but not identical techniques to do this.

   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.

3. File systems (20 points)

   Many years ago operating system designers developed the concept of a device driver as a way of easily integrating many different devices into an operating system. More recently there has been an expansion in the number of a different file system formats. To meet this challenge more recent operating systems have a concept of a file system driver.

   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.
      
      
4. Caching (20 points)

   Caching is the main way to speed up a computational process. Give several examples (at least three for each) of the use of caching in an operating system and in a computer system.

5. Architecture (20 points)

   Branching poses a significant problem when the goal is to maximize instruction throughput. Describe how you would design an experiment to determine the frequency of branching instructions. To what extent can the problems of branching be dealt with by a compiler and to what extent must they be addressed during execution. Describe the techniques that have been introduced in modern processors to deal with the problems associated with branches.

6. SMP (20 points)

   Suppose we have a typical operating system that runs on a single processor and we want to modify the operating system to work on a symmetric, shared-memory multiprocessor system. What changes will have to be made to accomplish this? For each change, indicate what the new design problem is and what are some possible solutions to the design problem.

7. Cluster architectures (20 points)

   Cluster communications with standard OS like Linux employs user-level communication, bypassing to a large degree the OS.

   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?