Advanced Systems Topics
2006-07

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
  • Non-blocking steal-half work queues
  • Language support for lightweight transactions
  • OpenMP C and C++ APIs

Advanced operating systems

• Slides in PDF format.
• Additional slides on EROS (from a guest lecture given in 2004)
• 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

Experimental performance analysis

• Measuring performance (metrics, means, errors)
• Comparing alternatives (1-factor ANOVA)
• Experimental design