OS Exam Notes

From SubfireWiki

Contents 1 System call 2 LRU 3 Belady 4 Titles 5 Papers

System call

1. Push operands (with syscall number)
2. trigger software interrupt
3. software interrupt causes O/S to handle it
4. Switch to kernel mode (address space switch)
5. flip mode bit
6. look up function by syscall number in interrupt service handler vector
7. call service handler
8. package result for userspace
9. switch address space back to user process
10. return result
11. set IP at the next instruction

LRU

• LRU requires some hardware support because there's (effectively) no way the OS can know about page accesses that don't generate page faults
• A Reference Bit is provided by some hardware which allows the implementation of the approximation algorithsm (Additional-Reference-Bits, Second-Chance)

Belady

1 2 3 4 1 2 5 1 2 3 4 5

1 1 1 4 4 4 5     5 5  
- 2 2 2 1 1 1     3 3  
- - 3 3 3 2 2     2 4  

1 1 1 1     5 5 5 5 4 4
- 2 2 2     2 1 1 1 1 5
- - 3 3     3 3 2 2 2 2
- - - 4     4 4 4 3 3 3

Titles

1. • Dealocks
   • Virtual memory
   • process
   • memory management
   • page replacement

Papers

• Consider the Berkeley Fast File System (FFS). How does FFS allocate files on disk? What types of workloads work well on FFS?
• This question considers the exokernel approach to operating system design.
  • 1A. The exokernel introduces the concept of a library operating system (libOS). Discuss what a libOS is, and why it is important to the exokernel approach (a picture is worth a thousand words, it has been said). Which pieces of functionality found in a typical OS would be placed within a libOS, and which pieces within the exokernel itself?
  • 1B. Consider CPU scheduling in the exokernel. Given mutually untrusting applications, how are they scheduled by the exokernel? Can you think of a workload where the exokernel scheduler would perform poorly, as compared to a typical scheduler found in a modern Unix-based system?
  • 1C. Sometimes an exokernel has to use "downloaded code", i.e. code loaded into the exokernel from an untrusted application. What are the main issues that must be dealt with in order to allow downloaded code within the exokernel? Could downloaded code be useful in improving the performance of the exokernel CPU scheduler, as discussed in part (1B)?
• You have been asked to modify/optimize the Berkeley Fast File System(FFS) for a specific workload as follows:

   ** There is a flat name-space for files; that is, there are no directories.
   ** Users tend to access files around the same time that have file names that are alphabetically close to each other.
   ** Most files are small but most of the data (and most of the data transfers) are in large files. 

You should also target the following storage technology:

   ** Multi-zone disks (a zone is a region with a constant density of sectors/track; zones further from the disk spindle have a higher density).
   ** Disks where it is very expensive to activate different disk heads; in fact, switching between disk heads is much more costly than seek time or rotational delay. 

Since you are starting with a working code base, we recommend that you use as many abstractions already defined in FFS as possible.

• • A.

   Thoroughly explain how both data blocks and i-nodes are allocated to maintain the locality of the workload. Specifically, you should focus on the global heuristics for allocating blocks of existing files and of new files. Be sure to explain why your layout will optimize the performance of the disk.

• • B.

   What is the problem with using a disk scheduling algorithm such as SCAN in this environment? How should it be changed?

• a) [5pts] FFS is important in part because it is the first file system to have been designed to consider

hardware characteristics of disks, memory systems, processors, etc. But the paper we read was published in 1984; clearly there have been significant changes and advances in hardware since then! Does this ren- der the paper and FFS itself worthy of studying only from a historical perspective? Answer â�?��?Yesâ�?� or â�?��?Noâ�?� and then clearly explain why you feel that way. Listed below are three hardware characteristics that influenced some aspect of FFS design. For each of the three, identify the aspect in FFS that is influenced by it, and briefly describe how. (i) [2pts] Physical Disks contain platters and cylindars (ii) [2pts] Seeks are slow (iii) [2pts] Some systems cannot read contiguous blocks one after another without processor intervention.

• What are the two different primary advantages of PCC over segmenting and sandboxing?

5. Lampson���?�s Hints for System Design (5 pts) (a) Do you agree or disagree with the following statement.... If we���?�re designing and build- ing a system that already has a predetermined standard external user interface, then Lampson���?�s hints for system design are of limited use, because many of the most important ones (e.g. keeping interfaces simple and stable, keeping a place to stand, keeping implementation secrets without hiding power, etc.) have to do with interface design... and if the interface is essentially a constraint within which we need to operate, then the opportunity to employ the hints is limited. Explain your answer. Disagree... Lampson���?�s hints, including and especially the ones that have to do with interface design, are really about subsystem design. Even if the overall system functionality is set in stone, the design of the system still should consider his recommendations.

(8 pts) (b) What are the main advantages to â�?��?leaving functionality to the clientâ�?� (or the â�?��?end to endâ�?� argument)? Name at least two distinct advantages. Avoids paying for what you donâ�?��?�t use... some users of a module may not need some function- ality, and if itâ�?��?�s pushed to the end points (or clients), then it wonâ�?��?�t be invoked when itâ�?��?�s not necessary. Avoids redundancy... sometimes you have to reimplement a service at the end points any- way, even if it is provided elsewhere (Saltzer paper discussion)... if itâ�?��?�s done at the client as a rule, it can be done just once, there. Makes subsystems simpler, allows them to focus on a single abstraction.