Course Overview and Entrance Exam In class written exam to ensure that all students embarking on this course have adequate knowledge of Operating Systems concepts at the undergraduate level. If you do not have adequate knowledge you will be advised to defer taking this class until after you have completed CS333. Reading:
|
Threads and Concurrency
Review of answers to the entrance exam. Review of the thread concept; concurrency and the need for synchronization; complexity of concurrent programming.
Reading:
Useful Links:
- An introduction to multi-threaded programming based on sequential consistency and data-race-free concepts, by Hans Boem of HP Labs.
- A tutorial on Pthreads (POSIX Threads) programming from LLNL.
|
Event-Based Systems
Steps toward automatic detection of race conditions, the case against thread-based programming; the reactive programming model; event-based programming.
Reading:
- "Eraser: A Dynamic Data Race Detector for Multithreaded Programs" by Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson, ACM Transactions on Computer Systems, volume 15, number 4, pages 391-411, November 1997.
Presenter: Jonathan Walpole
Slides: [.ppt] [.pdf]
- "Why Threads Are A Bad Idea (for most purposes)" by John Ousterhout, Talk Slides, Sun Microsystems Laboratories.
Presenter: Jonathan Walpole
Slides: [.pdf]
- Discussion slides: [.ppt] [.pdf]
|
Duality of Threads and Events
The performance and load management implications of thread-based vs event-based programming; the duality of event-based systems and thread-based systems; the case against event-based programming.
Reading:
- "SEDA: An Architecture for Well-Conditioned, Scalable Internet Services" Services" by Matt Welsh, David Culler, and Eric Brewer, In Proceedings of the Eighteenth Symposium on Operating Systems Principles (SOSP-18), Banff, Canada, October, 2001.
Presenter: Stephen Coward
Slides: [.pptx] [.pdf]
- "On the Duality of Operating System Structures" by Hugh Lauer, Roger Needham, in Proc. Second International Symposium on Operating Systems Principles, Oct 1978. Reprinted in SIGOPS Operating Systems Review, 13,2, Pages 3-19, April 1979.
Presenter: Vidhya Priyadhar Palaniswamy Gnanam
Slides: [.ppt] [.pdf]
- Discussion slides: [.ppt] [.pdf]
|
Integrated Task and Stack Management
Relationship between task management and stack management; Managing state across blocking I/O calls; Cooperative task management with automatic stack management; Integration of legacy code that uses both manual stack management and automatic stack management;
Reading:
- "Why Events Are A Bad Idea (for high-concurrency servers)" by Rob von Behren, Jeremy Condit and Eric Brewer, in proceedings HotOS IX, Kauai, Hawaii, May 2003.
Presenter: Loren Davis
Slides: [.ppt] [.pdf]
- "Cooperative Task Management without Manual Stack Management, or, Event-driven Programming is Not the Opposite of Threaded Programming" by Atul Adya, Jon Howell, Marvin Theimer, William Bolosky, and John Douceur, In Proceedings of the USENIX 2002 Annual Conference, pages 289-302, June 2002.
Presenter: Li Lei
Slides: [.pptx] [.pdf]
- Discussion slides: [.pptx]
|
Scheduler Activations and RPC
Kernel support for user-level cooperative threading on shared memory multiprocessors. Design and implementation issues for remote procedure calls (RPC).
Reading:
- "Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism" by Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, Henry M. Levy, ACM Transactions on Computer Systems, 10(1):53--79, February 1992.
Presenter: Anitha Suryanarayan
Slides: [.ppt] [.pdf]
- "Implementing Remote Procedure Calls" by A. D. Birrell and B. J. Nelson, ACM Transactions on Computer Systems, Vol. 2, No. 1, pp. 39-59, February 1984.
Presenter: Kai Cong
Slides: [.pptx] [.pdf]
- Discussion slides: [.ppt]
|
RPC Implementation on Shared Memory Multiprocessors
Optimization of RCP for cross-address-space local communication. How to implement RPC efficiently on a shared memory multiprocessor among user-level threads in different address spaces.
Reading:
- "Lightweight Remote Procedure Call" by B. N. Bershad, T. E. Anderson, E. D. Lazowska, and H. M. Levy, Proceedings of the 12th Symposium on Operating Systems Principles, pp. 102-113, December 1989.
Presenter: Matthaus Litteken
Slides: [.ppt] [.pdf]
- "User Level Interprocess Communication for Shared Memory Multiprocessor" by Bershad, B.N. Anderson, T.E., Lazowska, E.D., and Levy, H.M., ACM Transactions on Computer Systems, 9, 2, pgs. 175-198, May 1991.
Presenter: Elakkiya Pandian
Slides: [.ppt] [.pdf]
- Discussion slides: [.ppt]
|
System Structuring Using Layers
The advantages and disadvantages of layering as a kernel structuring approach.
Reading:
|
Micro-Kernels
Modular operating systems; implementing operating system server modules as user level processes that interact via IPC; micro-kernel based OS architectures and abstractions.
Reading:
- "The Mach System" appears in "Operating Systems Concepts, Sixth Edition" by Abraham Silberschatz, Peter Baer Galvin, and Greg Gagne, published by J Wiley, 2002.
Presenter: Shweta Ojha
Slides: [.pptx] [.pdf]
- Discussion slides: [.ppt]
|
In Class Midterm Exam |
Improving Micro-Kernel Performance
Strategies for improving IPC performance in micro-kernel operating systems that utilize hardware-based protection; analysis of potential performance improvements and their impact on higher level performance at the OS and application level.
Reading:
- "Improving IPC by Kernel Design" by J. Liedtke, Proceedings of the 14th ACM Symposium on Operating Systems Principles, Ashville, North Carolina, December 1993.
Presenter: Srinivas Sundaravaradan
Slides: [.pptx] [.pdf]
- "The Performance of Micro-Kernel- Based Systems" by H. Haertig, M. Hohmuth, J. Liedtke, S. Schoenberg, J. Wolter, Proceedings of the 16th Symposium on Operating Systems Principles, October 1997, pp. 66-77.
Presenter: Jonathan Walpole
Slides: [.pptx] [.pdf]
- Discussion slides: [.ppt]
|
Software-Based Protection for Improving Micro-Kernel Performance
Alternatives to hardware-based protection for structuring operating systems; implementing protection at the assembly language level; supporting operating system extensibility and safety using high-level language support. Virtual machines; supporting multiple operating systems simultaneously on a single hardware platform; running one operating system on top of another. Reducing the software engineering effort of developing operating systems for new hardware architectures. (select two of the following three papers)
Reading:
- "Efficient Software-based Fault Isolation" by R. Wahbe, S. Lucco, T. E. Anderson, and S. L. Graham. In Proceedings of the 14th ACM Symposium on Operating Systems Principles, pages 203--216, December 1993.
Presenter: Robert Terashima
Slides: [.ppt] [.pdf]
- "Extensibility, Safety and Performance in the SPIN Operating System" by Brian Bershad, Stefan Savage, Przemyslaw Pardyak, Emin Gun Sirer, David Becker, Marc Fiuczynski, Craig Chambers, Susan Eggers, in Proceedings of the 15th ACM Symposium on Operating System Principles (SOSP-15), Copper Mountain, CO. pp. 267--284.
Presenter: James Whiteneck
Slides: [.pptx] [.pdf]
- Discussion slides: [.pptx]
|
Virtualization
Virtual machines; supporting multiple operating systems simultaneously on a single hardware platform; running one operating system on top of another. Reducing the software engineering effort of developing operating systems for new hardware architectures. True or pure virualization. Para virtualization; optimizing performance of virtualization system; hypervisor call interface.
Reading:
- "Disco: Running Commodity Operating Systems on Scalable Multiprocessors" by Edouard Bugnion, Scott Devine, and Mendel Rosenblum. In Proceedings of The 16th ACM Symposium on Operating Systems Principles, October 1997
Presenter: Jonathan Walpole
Slides: [.ppt] [.pdf]
- "Xen and the Art of Virtualization," P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield, Proceedings of the 19th Symposium on Operating System Principles, October, 2003.
Presenter: Karan Sharma
Slides: [.pdf]
- Discussion slides: [.ppt]
|
Exo-Kernels
Exo-kernel concept; minimal operating system functionality; separation of mechanism and policy; techniques for implementing application specific handlers; dynamic specialization of packet filters.
Reading:
|
Synchronization and Scalability on Multiprocessors
A discussion of various forms of lock-based synchronization used in OS kernels. A case study of the locking primitives used in the Linux kernel. Implementation strategies for spin locks, with emphasis on contention issues and design strategies that improve performance and scalability.
Reading:
|
Transactional Memory
A discussion of transactional memory and an attempt to use it in the Linux kernel.
|
Memory Consistency Models
Memory consistency models of modern CPUs, sequential consistency, weak consistency models, memory barriers, and implications for performance and scalability.
|
Scalability Issues on Multiprocessors
Design of operating systems for high scalability on multiprocessor systems: locality issues, object distribution and replication, scalable locking and interaction with memory management. Multi-kernel design strategies.
- "The Multikernel: A New OS Architecture for Scalable Multicore Systems," Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Schüpbach, Akhilesh Singhania, In Proceedings of the 22nd ACM Symposium on Operating Systems Principles (SOSP '09) , Big Sky, MT October 2007.
Submit position papers by email to walpole@cs.pdx.edu before class.
|
Local Research on Scalable Concurrent Programming
Relativistic Programming.
Reading:
|
