CONCEPTS OF OPERATING SYSTEMS PPT

CONCEPTS OF OPERATING SYSTEMS PPT

Schedule & Syllabus

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: "Efficient Reading of Papers in Science and Technology" by Michael J. Hansen and Dylan J. McNamee, unpublished. Presenter: Jonathan Walpole Slides: [.pptx] [.pdf]

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: "An Introduction to Programming with Threads" by Andrew Birrell, Digital Systems Research Lab Technical Report, January 1989. Presenter: Jonathan Walpole Slides: [.ppt] [.pdf] 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: "The Structure of the "THE" Multiprogramming System" by E. W. Dijkstra, Communications of the ACM, 11(5):341--346, 1968. Presenter: Seema Saijpaul Slides: [.pptx] [.pdf] "The Structuring of Systems using Upcalls," D. D. Clark, Proceedings of the 10th Symposium on Operating Systems Principles. pp. 171-180, December 1985. Presenter: Frank Sliz Slides: [.ppt] [.pdf] Discussion slides: [.ppt]

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: "Exokernel: An Operating System Architecture for Application-Level Resource Management" by Dawson R. Engler, M. Frans Kaashoek, and James O'Toole Jr., in Proceedings of the Symposium on Operating Systems Principles, pages 251-266, Copper Mountain, Colorado, December 1995. Presenter: Keith Billings Slides: [.pptx] [.pdf] Discussion slides: [.ppt]

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: "Kernel Locking Techniques," Robert Love, LINUX Journal, Aug 2002. Presenter: Jonathan Walpole Slides: [.ppt] [.pdf] "The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors," T. E. Anderson, IEEE Trans. on Parallel and Distributed Systems, 1(1):6--16, Jan. 1990. Presenter: Jonathan Walpole Slides: [.ppt] [.pdf] Discussion slides: [.ppt]

Transactional Memory A discussion of transactional memory and an attempt to use it in the Linux kernel. "TxLinux: Using and Managing Transactional Memory in an Operating System," Christopher J. Rossbach, Owen S. Hofmann, Donald E. Porter, Hany E. Ramadan, A ditya Bhandari, Emmett Witchel, In Proceedings of the 21st ACM Symposium on Operating Systems Principles (SOSP '07) , Stevenson, WA October 2007. Presenter: Jonathan Walpole Slides: [.ppt] [.pdf] Discussion slides: [.ppt]

Memory Consistency Models Memory consistency models of modern CPUs, sequential consistency, weak consistency models, memory barriers, and implications for performance and scalability. "Shared Memory Consistency Models: A Tutorial," Sarita V. Adve, Kourosh Gharachorloo, digital Western Research Laboratory Research Report 95/7, September 1995. Presenter: Jim Larson Slides: [.ppt] [.pdf] Discussion slides: [.ppt]

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. "Tornado: Maximizing Locality and Concurrency in a Shared Memory Multiprocessor Operating System," Ben Gamsa, Orran Krieger, Jonathan Appavoo, and Michael Stumm, In Proceedings OSDI'99, pages 87-100, 1999. Presenter: Priya Limaye Slides: [.pptx] [.pdf] "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. Presenter: Joanna Solmon Slides: [.ppt] [.pdf] Discussion slides: [.ppt] Submit position papers by email to walpole@cs.pdx.edu before class.

Local Research on Scalable Concurrent Programming Relativistic Programming. Reading: "A Comparison of Conventional and Relativistic Approaches to Reader-Writer Locking" Philip W. Howard, Josh Triplett and Jonathan Walpole, In submission, February 2011. Presenter: Philip Howard Slides: [.pdf] "Generalized Construction of Scalable Concurrent Data Structures via Relativistic Programming" Josh Triplett, Philip W. Howard, Paul E. McKenney, and Jonathan Walpole, In submission, March 2011. Presenter: Josh Triplett Slides: [.pdf] ·  Discussion slides: [.ppt]