Advanced Systems Topics
2003-04

Advanced operating systems

• Slides in PDF and PostScript formats.
• Slides for guest lecture on capability systems (EROS case study)
• Past exam questions and some sample supervision questions.
• Some sketch answers to the above sample questions; please read these only after attempting the sample questions.
• Recommended books:
  • Singal, M. & Shivaratri, N. (1994). Advanced Concepts in Operating Systems: Distributed, Database, and Multiprocessor Operating Systems. McGraw-Hill.
  • Stonebraker, M. & Shivaratri, N. (1998). Readings in Database Systems. Morgan Kaufmann (3rd ed.).
• Additional reading:
  • Memory Coherence in Shared Virtual Memory Systems, Li et al, PODC 1986.
  • Munin: distributed shared memory based on type-specific memory coherence, Bennet et al, PPOPL 1990.
  • The Multics Virtual Memory: Concepts and Design, Bensoussan et al, CACM May 1972 15(5)
  • Texas: An Efficient, Portable Persistent Store, Singhal et al, POS 1982
  • Lightweight Recoverable Virtual Memory, Satya et al et al, TOCS 1994
  • Free Transactions with Rio Vista, Lowell and Chen, SOSP 1997
  • The Cambridge CAP Computer, Levy, 1998
  • The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System (aka Mach), Young et al, SOSP 1987
  • On Microkernel Construction, Liedtke, SOSP 1995
  • The Performance of Microkernel-based Systems (aka L4), Haertig et al, SOSP 1997
  • State-caching in the EROS Kernel, Shapiro et al, POS 1996
  • Disco: Running Commodity Operating Systems on Scalable Multiprocessors, Buignon et al, SOSP 1997
  • Scale and Performance in the Denali Isolation Kernel, Whitaker et al, OSDI 2002
  • Xen and the Art of Virtualization, Barham et al, SOSP 2003
  • Extensibility, Safey and Performance in the SPIN Operating System, Bershad et al, SOSP 1995
  • Dealing with Disaster: Surviving Misbehaved Kernel Extensions (aka Vino), Seltzer et al, OSDI 1996
  • Exterminate All Operating System Abstractions (aka ExoKernel), Engler et al, HotOS 1995
  • Application Performance and Flexibility on Exokernel Systems, Kaashoek et al, SOSP 1997
  • Self-paging in the Nemesis Operating System, Hand, OSDI 1999
  • The Ubiquitous B-Tree, Comer, ACM Computing Surveys 1979
  • The Implementation of Postgres, Stonebraker et al, IEEE KDE 1990
  • Operating System Support for Database Management, Stonebraker, CACM 1981
  • RFC 1813: NFS Version 3 Protocol Specification (1995) and RFC 3530: Network File System (NFS) Version 4 Protocol (2003)
  • Interposed Request Routing for Scalable Network Storage, Anderson et al, OSDI 2000
  • Disconnected Operation in the Coda File System, Kistler and Satya, ACM TOCS 1992
  • A Low-bandwidth Network File System, Muthitacharoen et al, SOSP 2001
  • Serverless Network File Systems (aka xFS), Anderson et al, SOSP 1995
  • A Case for Network-Attached Secure Disks, Gibson et al, CMU Tech Report 1996
  • The Design of a Mutlicast-based Distributed File System (aka JetFile), Gronvall et al, OSDI 1999
  • Petal: Distributed Virtual Disks, Thekkath et al, ASPLOS 1996
  • Frangipani: A Scalable Distributed File System , Thekkath et al, SOSP 1996
  • Venti: a new approach to archival storage, Quinlan and Dorward, FAST 2003

Scalable synchronization

• Slides and example questions in PDF and PostScript formats
• Supervisors' guide / solution notes in PDF and PostScript formats
• Recommended books:
  • Chapter 2 from Lea, D. (1999). Concurrent Programming in Java. Addison-Wesley (2nd ed.)
  • Chapter 6 from Hennessy, J. and Petterson, D. Computer Architecture, a Quantitative Approach. Morgan Kaufmann (3rd ed.)
• Additional material for background reading:
  • The util.concurrent library
  • Algorithms for scalable synchronization on shared-memory multiprocessors
  • Simple, fast, and practical non-blocking and blocking concurrent queue algorithms
  • Language support for lightweight transactions
  • OpenMP C and C++ APIs

Decentralised Computing

There are five lectures, covering 3 aspects of such systems. The top and tail of the lectures are about peer-to-peer systems, with a brief introduction with history from napster to kazaa, then there is a guest slot from the Intel lab here, about Internet coordinate systems and service discovery, which allow one to optimise dicentralised systems for latency, or other target performance parameters; Then we have a talk from the Lab for Communications Engineering, about ubiquitous systems and the impact on security; following that there is a lecture on two different algorithms for content request routing, based on two Distributed Hash Table Techniques, namely CAN (a multi-dimension hash) and Pastry (based on Plaxton prefix routing); finally, we wrap up with a guest slot from Microsoft Research Cambridge, on comparing unstructured p2p systems (the ones every one uses) with structured ones (the ones everyone researchers, e.g. Pastry, CAN and others)

• intro
• practical internet coordinates (PIC), plus the original lighthouse paper and the powerpoint slides for the lecture.
• security
• CAN
• pastry/plaxton
• Structured v. Unstructured to be provided!