Reading: Questions

Students are required to turn in their answers to the assigned questions before lecture. These notes are graded. Student will earn 3 points each time: 3 for excellent understanding, 2 for good understanding, 1 for understanding a little, and 0 for no understanding. If you submit your notes after the class, you will not receive any points. 

You can click the “submit” link in the reading assignments section on the course main webpage.  We only accept online submissions.   

MOS 1.4-1.5

Goal: Understand the responsibilities, components, and services of an operating system.

• BIOS (Basic Input/Output System) is typically held in a flash memory. Is it possible to put the BIOS on disk instead? Please tell briefly the pros and cons of on flash memory and on disk.
• The simplest way to bootstrap an operating system is to boot from a binary image on a disk. What would you need to do if you are building a diskless workstation or a network computer which needs to bootstrap from a network file server? Explain your idea of how to do that.

MOS 1.6-1.7

Goal: Understand the OS structure and the implementation of system calls and libraries.

• What is the difference between a system call and a library call?
• What are the advantages and disadvantages of the micro-kernel approach?

MOS 2.1-2.2.1-2.2.3

Goal: Understand the concept of program, process, and thread.

• What are the differences between a program and a process?
• What are the differences between a process and a thread?
• Write the psuedo-code to perform a process context switch

MOS 2.2.4-2.2.9

Goal: Understand different kinds of threads as well as the concept of a critical section.

• What are the differences between a kernel thread and a user-level thread?
• Suppose two students share a house and they share the responsibility of buying milk, but their fridge is small. So, they would like to avoid buying too much milk. One day,

• At each step, the student can be distracted and do other things. How would you solve this problem?

MOS 2.3.3, 2.3.6

Goal: Understand how to use disabled interrupts and atomic read-modify-write to implement mutual exclusion.

• The simplest way to implement Acquire() and Release() is:

Acquire() { disable interrupts; } Release() { enable interrupts; }

Do you think it works? If so, under what conditions? If do not think so, explain why it does not work and how would you make it work.

• The textbook mentioned using a test-and-set instruction to implement mutual exclusion. How would you use it to implement Acquire() and Release()?

MOS 2.4 (2e: 2.5)

Goal: Understand the criteria and methods of CPU scheduling

• The non-preemptive scheduler in project 2 uses the First-Come-First-Serve (FCFS) method. Compare this approach with the round-robin scheduling. Under what conditions is the FCFS approach preferred? Under what conditions is round-robin preemptive scheduling approach better?
• Round-robin schedulers normally maintain a list of ready processes or threads without duplicates. What would happen if a process or thread occurs more than once in this list? Is there a case where you would like to do that?

MOS 2.3.5, 2.3.7, Birrell

Goal: Understand the concept of semaphores and monitors and know about how to use them.

• What is the difference between Hoare's monitor and the monitor in Birrell's paper?
• The textbook has an example (Figure 2-27) of using a Monitor to solve the consumer-producer problem. How would you use the primitives in Birrell's paper to solve the problem?

MOS 6 (2e: 3)

Goal: Understand the cause of deadlocks and think about the best solution.

• The textbook lists four conditions for a deadlock (3.2.1) to occur. Discuss what happen if we remove any one of them.
• The textbook also lists four strategies to deal with deadlocks (3.3.2):

• ignore the problem
• detect and recover
• avoid deadlocks by careful resource allocation
• prevent deadlocks by negating a necessary condition

Explain which strategy you prefer and how you would implement it.

MOS 5.1-5.3, 5.5-5.9

Goal: Understand I/O devices, their interrupt handlers, and device drivers.

A complicated issue in designing a device driver is to provide asynchronous operations.

• What design and implementation issues will you need to consider if you want to provide users with asynchronous operations? List the issues you can think of and make some comments on each.

MOS 2.3.8, 8.2.1-8.2.4

Goal: Understand the issues in designing message-passing APIs and how to implement them.

• Consider implementing inter-process communication primitives send(destination, msg, n) and recv(source, buffer, max), where destination and source specify the destination process and source process respectively. Provide psuedo-code to show how to implement the two primitives. Your code should consider issues with synchronization and buffer management.

MOS 3.1-3.3.3 (2e: 4.1-4.3.3)

Goal: Understand the basic concept of virtual memory and various address translations

• What virtual memory related states do you need to keep in a PCB?
• What virtual memory related tasks does an OS kernel need to do during a context switch?

MOS 3.4 (2e: 4.4)

Goal: Understand the properties of various page replacement algorithms.

The textbook describes 10 page replacement algorithms in Section 4.4.

• Which two algorithms do you like the best? Explain why.
• What minimal hardware mechanisms do your favorite algorithms need?

MOS 3.5-3.6 (2e: 4.6-4.7)

Goal: Understand implementation issues.

• How do you avoid virtual memory thrashing?
• When a process forks off a child process, it needs to replicate its address space. This operation may take a while to complete. One technique to speed this up is to create an address space mapping to the same set of pages without copying data and mark all pages read-only. On a write, the kernel will catch the access fault, allocates a page frame, copy the page from its parent process, mark the page to be read-write, and then return to the faulting instruction. This technique is called "copy-on-write." How would you implement copy-on-write?

DARPA Internet Protocols

Goal: Understand the design principles of the Internet.

• What are the main differences between datagram protocol and TCP?
• List two main technological successes in the development of DARPA internet protocols? Briefly state why you think they are so.

MOS 5.4

Goal: Understand how disks work and learn about various disk scheduling algorithms.

• The textbook describes two disk arm scheduling algorithms (SSF and Elevator). Discuss which you prefer and why?
• The textbook mentions RAID. What are the advantages and disadvantages of level 4 and level 5?

MOS 4.1, 9.3.1-9.3.3 (2e: 6.1, 9.6)

Goal: Understand file system interfaces and protection.

• If you are in charge of designing a file system API, what issues must you consider? List a number of issues and explain, using a sentence for each, why it must be considered.
• The textbook mentioned three protection mechanisms in Section 9.6. Could you apply them to file systems? Please state your opinion and briefly provide your supporting arguments.

MOS 4.2-4.3.3, 4.5.2-4.5.3 (2e: 6.2-6.3.3, 6.4.3, 6.4.5)

Goal: Understand file directories and file layout alternatives.

• The textbook lists three ways to implement files: linked list allocation scheme, linked list allocation with an index, and i-node. What is your favorite scheme and why.
• What is your favorite method to implement file directories? Discuss why you like your choice.

MOS 4.4.2-4.4.4, 4.3.5 (2e: 6.3.6-6.3.8)

Goal: Understand the issues and some solutions for file system reliability.

• State very briefly what to do in order to make a log-structured file system be consistent after a crash.
• What is the difference between a file buffer cache and virtual memory?

MOS 10.6.3-10.6.4, NetApp

Goal: Understand the design and issue of the original NetApp file server.

This paper describes the internals of WAFL, the NetApp's file system which has a built-in mechanism to take snapshots.

• Is possible to implement snapshots as an "add-on" to an ordinary file system that has no built-in snapshot mechanisms?
• If you think the answer is yes, outline how you would build the add-on snapshots. If you think the answer is no, briefly explain why not.

Virtual Machine Monitor

Mendel Rosenblum and Tal Garfinkel, Virtual Machine Monitors: Technology and Future Trends. Computer.  38(5) 39-47, May 2005.

Goal: Understand the benefits and challenges of virtual machine monitors.

·         What is the main benefit of using a virtual machine monitor?

·         What is the main challenge of implementing virtual machine monitors and briefly explain why.

Deduplication

Benjamin Zhu, Kai Li, and Hugo Patterson.  Avoiding the Disk Bottleneck in Data Domain Deduplication File System.  Proceedings of the 6th USENIX Conference on File and Storage Technologies.  San Jose, California.  February 2008.

Goal: Understand the benefits and challenges of deduplication storage systems.

·         What is the main idea of deduplication storage system?

·         What is the main idea to achieve high-throughput deduplication?

COS 318: Operating Systems
Princeton University
Department of Computer Science