COMP 521: Advanced Operating Systems

Description

Advanced topics in the design and implementation of state-of-the-art operating systems for general-purpose computation, emphasizing solutions to performance and scalability bottlenecks that are common with today's commercial and scientific workloads: scalable process and thread management; NUMA memory management; superpage support; SMP memory and address translation coherence; low-overhead, high-throughput I/O systems; robustness versus performance in file systems.

Prerequisites

COMP 421

Meeting Time and Place

Today only, August 31st, we will meet at 2:30PM in DH3092. Starting Thursday, September 2nd, we will meet at 2:30PM in DH3110. This will be the regular meeting time and place.

Reading List

Motivational

Why Aren't Operating Systems Getting Faster as Fast as Hardware? J. K. Ousterhout. In the Proceedings of the USENIX Summer Conference, June 1990, pages 247-256.

Process and Thread Management

Scheduler Activations: Effective kernel support for the user-level management of parallelism. T. E. Anderson, B. N. Bershad, E. D. Lazowska, and H. M. Levy. ACM Transactions on Computer Systems, Volume 10, Number 1, February 1992, pages 53-79.

See also: An Implementation of Scheduler Activations on the NetBSD Operating System. N. J. Williams. This paper describes and evaluates an implementation that is in use today.
See also: Page 14 of Multithreading in the Solaris Operating Environment briefly describes the implementation in Solaris 2.5 and onward. Solaris "doors" are an LRPC-like mechanism.

Using Continuations to Implement Thread Management and Communication in Operating Systems. R. P. Draves, B. N. Bershad, R. F. Rashid, and R. W. Dean. In the Proceedings of the 13th ACM Symposium on Operating Systems Principle, pages 122-136, 1991.

Note: I've found that some versions of Ghostscript crash while rendering a figure in the middle of this paper. The version of Ghostscript installed on Noel can render this figure.

Memory Management

The Slab Allocator: An Object-Caching Kernel Memory Allocator. J. Bonwick. In Proceedings of the Summer 1994 Usenix Conference, pages 87-98, 1994.

See also: Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources. J. Bonwick and J. Adams. In Proceedings of the USENIX 2001 Annual Technical Conference, pages 15-34, 2001.

The UVM Virtual Memory System. C. D. Cranor and G. M. Parulkar. In the Proceedings of the 1999 USENIX Annual Technical Conference, pages 117-130, June 1999.
Translation lookaside buffer consistency: a software approach. D. L. Black, R. F. Rashid, D. B. Golub, C. R. Hill, and R. V. Baron. In the Proceedings of the Third International Conference on Architectural Support for Programming Languages and Operating Systems, pages 113-122, 1989. Presented by: H.-Y. John Kim. Date: 9/16.
Page Placement Algorithms for Large Real-Indexed Caches. R. E. Kessler and M. D. Hill. ACM Transactions on Computer Systems, Volume 10, Number 4, pages 338-359, 1992.
NUMA policies and their relation to memory architecture. W. J. Bolosky, M. L. Scott, R. P. Fitzgerald, R. J. Fowler, and A. L. Cox. In the Proceedings of the 4th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 212-221, 1991. Presented by: Michael Calhoun. Date: 9/23.
Practical, transparent operating system support for superpages. J. Navarro, S. Iyer, P. Druschel and A. Cox. In the Proceedings of the Fifth Symposium on Operating Systems Design and Implementation, Dec 2002. Presented by: Benedict Lee. Date: 9/28.

I/O, IPC and Event Notification

Eliminating Receive Livelock in an Interrupt-Driven Kernel. J. C. Mogul and K. K. Ramakrishnan. ACM Transactions on Computer Systems, Volume 15, Number 3, pages 217-252, 1997. Presented by: Atul Singh. Date: 9/30.
Kqueue: A generic and scalable event notification facility. J. Lemon. In the Proceedings of the FREENIX Track: 2001 USENIX Annual Technical Conference. Presented by: Khaled Elmeleegy. Date: 10/5.
Lightweight Remote Procedure Call. B.N. Bershad, T.E. Anderson, E.D. Lazowska and H.M. Levy. ACM Transactions on Computer Systems, Vol. 8, No. 1, pages 37-55, February 1990.
Zero-Copy TCP in Solaris. H. K. J. Chu. In the Proceedings of the USENIX 1996 Annual Technical Conference, pages 253-264, Jan 1996. Presented by: Michael Calhoun.
IO-Lite: A Unified I/O Buffering and Caching System. V. S. Pai, P. Druschel, and W. Zwaenepoel. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, pages 15-28, Feb 1999. Presented by: Khaled Elmeleegy

File Systems

The Design and Implementation of a Log-Structured File System. M. Rosenblum and J. K. Ousterhout. ACM Transactions on Computer Systems, Volume 10, Number 1, pages 26-52, 1992. Presented by: Anwis Das
Scalability in the XFS File System. A. Sweeney, D. Doucette, W. Hu, C. Anderson, M. Nishimoto, and G. Peck. In the Proceedings of the USENIX 1996 Annual Technical Conference, Jan 1996. Presented by: Benedict Lee
Soft Updates: A Solution to the Metadata Update Problem in File Systems. G. R. Ganger, M. K. McKusick, C. A. N. Soules, Y. N. Patt. ACM Transactions on Computer Systems, Vol. 18, No. 2, pages 127-153, May 2000. Presented by: Guoqiang Pan
Journaling versus Soft Updates: Asynchronous Meta-data Protection in File Systems. M. I. Seltzer, G. R. Ganger, M. K. McKusick, K. A. Smith, C. A. N. Soules, and C. A. Stein. In the Proceedings of the 2000 USENIX Annual Technical Conference, pages 71-84, June 2000. Presented by: Paul Willman

Virtualization

Disco: Running Commodity Operating Systems on Scalable Multiprocessors. E. Bugnion, S. Devine, K. Govil, M. Rosenblum. ACM Transactions on Computer Systems, Vol. 15, Number 4, pages 412-447, 1997. Presented by: Paul Willmann

Breaking the Mold

Sharing and protection in a single address space operating system. J. S. Chase, H. M. Levy, M. J. Feeley, and E. D. Lazowska. ACM Transactions on Computer Systems, Volume 12, Number 4, 1994. Presented by: Anupam Chanda
A Caching Model of Operating System Kernel Functionality. D. Cheriton and K. Duda. In the Proceedings of the First Symposium on Operating Systems Design and Implementation. November 1994. Presented by: Scott Crosby. Date: 11/16.
Exokernel: An Operating System Architecture for Application-Level Resource Management. D. R. Engler, M. F. Kaashoek, and J. O'Toole. In the Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, pages 251-266, 1995.

Grading

Final grades will be based upon a weighted average of a project (50%), class presentations (34%), and class participation (16%).

Each student will be required to make one or two class presentations of research papers from the reading list. Submission of a presentation outline and a practice presentation are required.

Students will undertake course projects in teams of two to three members; written project proposals, intermediate reports, a high-quality final paper and a project presentation are required.

There will be no exams!

Students with Disabilities

Any student with a documented disability needing academic adjustments or accommodations is requested to speak with me during the first two weeks of class. All discussions will remain confidential. Students with disabilities will need to also contact Disability Support Services in the Ley Student Center.