Some links to papers are links to the ACM’s site. You may need to use the Harvard VPN to get access to the papers via those links. Alternate links will be provided.
“Multics—The first seven years”, Corbató FJ, Saltzer JH, and Clingen CT (1972)
“Protection in an information processing utility”, Graham RM (1968)
“The evolution of the Unix time-sharing system”, Ritchie DM (1984)
The Multicians web site for additional information on Multics, including extensive stories and Multics source code.
Technical: The Multics input/output system, Feiertag RJ and Organick EI, for a description of Multics I/O to contrast with Unix I/O.
Unix and Multics, Tom Van Vleck.
… I remarked to Dennis that easily half the code I was writing in Multics was error recovery code. He said, "We left all that stuff out. If there's an error, we have this routine called
panic(), and when it is called, the machine crashes, and you holler down the hall, 'Hey, reboot it.'"
This describes the history of the system that preceded Multics, CTSS (the Compatible Time Sharing System). It also contains one of my favorite stories about the early computing days: “IBM had been very generous to MIT in the fifties and sixties, donating or discounting its biggest scientific computers. When a new top of the line 36-bit scientific machine came out, MIT expected to get one. In the early sixties, the deal was that MIT got one 8-hour shift, all the other New England colleges and universities got a shift, and the third shift was available to IBM for its own use. One use IBM made of its share was yacht handicapping: the President of IBM raced big yachts on Long Island Sound, and these boats were assigned handicap points by a complicated formula. There was a special job deck kept at the MIT Computation Center, and if a request came in to run it, operators were to stop whatever was running on the machine and do the yacht handicapping job immediately.”
Using Ring 5, Randy Saunders.
"All Multics User functions work in Ring 5." I have that EMail (from Dave Bergum) framed on my wall to this date. … All the documentation clearly states that system software has ring brackets of [1,5,5] so that it runs equally in both rings 4 and 5. However, the PL/I compiler creates segments with ring brackets of [4,4,4] by default. … I found each and every place CNO had fixed a program without resetting the ring brackets correctly. It started out 5 a day, and in 3 months it was down to one a week.”
Bell Systems Technical Journal 57(6) Part 2: Unix Time-sharing System (July–August 1978)
This volume contains some of the first broadly-accessible descriptions of Unix. Individual articles are available on archive.org. As of late January 2021, you can buy a physical copy on Amazon for $2,996. Interesting articles include Thompson on Unix implementation, Ritchie’s retrospective, and several articles on actual applications, especially document preparation.
“The nucleus of a multiprogramming system”, Brinch Hansen P (1970).
“Toward real microkernels”, Liedtke J (1996).
“Are virtual machine monitors microkernels done right?”, Hand S, Warfield A, Fraser K, Kotsovinos E, Magenheimer DJ (2005).
“Improving IPC by kernel design”, Liedtke J (1993). Article introducing the first microbenchmark-performant microkernel.
“Are virtual machine monitors microkernels done right?”, Heiser G, Uhlig V, LeVasseur J (2006).
“From L3 to seL4: What have we learnt in 20 years of L4 microkernels?”, Elphinstone K, Heiser G (2013).
Retained: Minimality as key design principle.
Replaced: Synchronous IPC augmented with (seL4, NOVA, Fiasco.OC) or replaced by (OKL4) asynchronous notification.
Replaced: Physical by virtual message registers.
Abandoned: Long IPC.
Replaced: Thread IDs by port-like IPC endpoints as message destinations.
Abandoned: IPC timeouts in seL4, OKL4.
Abandoned: Clans and chiefs.
Retained: User-level drivers as a core feature.
Abandoned: Hierarchical process management.
Multiple approaches: Some L4 kernels retain the model of recursive address-space construc- tion, while seL4 and OKL4 originate mappings from frames.
Added: User-level control over kernel memory in seL4, kernel memory quota in Fiasco.OC.
Unresolved: Principled, policy-free control of CPU time.
Unresolved: Handling of multicore processors in the age of verification.
Replaced: Process kernel by event kernel in seL4, OKL4 and NOVA.
Abandoned: Virtual TCB addressing. …
Abandoned: C++ for seL4 and OKL4.
“Exterminate all operating systems abstractions”, Engler DE, Kaashoek MF (1995).
“Exokernel: an operating system architecture for application-level resource management”, Engler DE, Kaashoek MF, O’Toole J (1995).
“The nonkernel: a kernel designed for the cloud”, Ben-Yehuda M, Peleg O, Ben-Yehuda OA, Smolyar I, Tsafrir D (2013).
“Application performance and flexibility on exokernel systems”, Kaashoek MF, Engler DR, Ganger GR, Briceño HM, Hunt R, Mazières D, Pinckney T, Grimm R, Jannotti J, Mackenzie K (1997).
Particularly worth reading is section 4, Multiplexing Stable Storage, which contains one of the most overcomplicated designs for stable storage imaginable. It’s instructive: if your principles end up here, might there be something wrong with your principles?
“Fast and flexible application-level networking on exokernel systems”, Ganger GR, Engler DE, Kaashoek MF, Briceño HM, Hunt R, Pinckney T (2002).
Particularly worth reading is section 8, Discussion: “The construction and revision of the Xok/ExOS networking support came with several lessons and controversial design decisions.”
“EROS: A fast capability system”, Shapiro JS, Smith JM, Farber DJ (1999).
“Labels and event processes in the Asbestos operating system”, Vandebogart S, Efstathopoulos P, Kohler E, Krohn M, Frey C, Ziegler D, Kaashoek MF, Morris R, Mazières D (2007).
This paper covers too much ground. On the first read, skip sections 4–6.
“Arrakis: The operating system is the control plane” (PDF), Peter S, Li J, Zhang I, Ports DRK, Woos D, Krishnamurthy A, Anderson T, Roscoe T (2014)
“The IX Operating System: Combining Low Latency, High Throughput, and Efficiency in a Protected Dataplane”, Belay A, Prekas G, Primorac M, Klimovic A, Grossman S, Kozyrakis C, Bugnion E (2016) — read Sections 1–4 first (return to the rest if you have time)
“I'm Not Dead Yet!: The Role of the Operating System in a Kernel-Bypass Era”, Zhang I, Liu J, Austin A, Roberts ML, Badam A (2019)
From least to most speculative:
“Unified high-performance I/O: One Stack to Rule Them All” (PDF), Trivedi A, Stuedi P, Metzler B, Pletka R, Fitch BG, Gross TR (2013)
“The Case for Less Predictable Operating System Behavior” (PDF), Sun R, Porter DE, Oliveira D, Bishop M (2015)
“Quantum operating systems”, Corrigan-Gibbs H, Wu DJ, Boneh D (2017)
“Pursue robust indefinite scalability”, Ackley DH, Cannon DC (2013)
“The Design and Implementation of a Log-Structured File System”, Rosenblum M, Ousterhout J (1992)
“Logging versus Clustering: A Performance Evaluation”
“Generalized file system dependencies”, Frost C, Mammarella M, Kohler E, de los Reyes A, Hovsepian S, Matsuoka A, Zhang L (2007)
“Application crash consistency and performance with CCFS”, Sankaranarayana Pillai T, Alagappan R, Lu L, Chidambaram V, Arpaci-Dusseau AC, Arpaci-Dusseau RH (2017)
“Rethink the sync”, Nightingale EB, Veeraraghavzn K, Chen PM, Flinn J (2006)
“Operating system transactions”, Porter DE, Hofmann OS, Rossbach CJ, Benn E, Witchel E (2009)
More, if you’re hungry for it
“Xen and the Art of Virtualization”, Barham P, Dragovic B, Fraser K, Hand S, Harris T, Ho A, Neugebauer R, Pratt I, Warfield A (2003)
“Blending containers and virtual machines: A study of Firecracker and gVisor”, Anjali, Caraz-Harter T, Swift MM (2020)
“Memory resource management in VMware ESX Server”, Waldspurger CA (2002)
“Opportunistic flooding to improve TCP transmit performance in virtualized clouds”, Gamage S, Kangarlou A, Kompella RR, Xu D (2011)
“The Best of Both Worlds with On-Demand Virtualization”, Kooburat T, Swift M (2011)
“The NIC is the Hypervisor: Bare-Metal Guests in IaaS Clouds”, Mogul JC, Mudigonda J, Santos JR, Turner Y (2013)
“vPipe: One Pipe to Connect Them All!”, Gamage S, Kompella R, Xu D (2013)
“Scalable Cloud Security via Asynchronous Virtual Machine Introspection”, Rajasekaran S, Ni Z, Chawla HS, Shah N, Wood T (2016)
“Grapevine: an exercise in distributed computing”, Birrell AD, Levin R, Schroeder MD, Needham RM (1982)
“Implementing remote procedure calls”, Birrell AD, Nelson BJ (1984)
Skim: “Time, clocks, and the ordering of events in a distributed system”, Lamport L (1978)
“Paxos made simple”, Lamport L (2001)
“Paxos made live: an engineering perspective”, Chanra T, Griesemer R, Redston J (2007)
“In search of an understandable consensus algorithm”, Ongaro D, Ousterhout J (2014)
“Scaling Memcache at Facebook”, Nishtala R, Fugal H, Grimm S, Kwiatkowski M, Lee H, Li HC, McElroy R, Paleczny M, Peek D, Saab P, Stafford D, Tung T, Venkataramani V (2013)
“Millions of Tiny Databases”, Brooker M, Chen T, Ping F (2020)
“Scalability! But at what COST?”, McSherry F, Isard M, Murray DG (2015)
“What bugs cause production cloud incidents?”, Liu H, Lu S, Musuvathi M, Nath S (2019)
“Escape Capsule: Explicit State Is Robust and Scalable”, Rajagopalan S, Williams D, Jamjoom H, Warfield A (2013)
“Music-defined networking”, Hogan M, Esposito F (2018)
“All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications”, Pillai TS, Chidambaram V, Alagappan R, Al-Kiswany S, Arpaci-Dusseau AC, Arpaci-Dusseau RH (2014)
“Crash Consistency Validation Made Easy”, Jiang Y, Chen H, Qin F, Xu C, Ma X, Lu J (2016)
“Persistent Memcached: Bringing Legacy Code to Byte-Addressable Persistent Memory”, Marathe VJ, Seltzer M, Byan S, Harris T
“NVMcached: An NVM-based Key-Value Cache”, Wu X, Ni F, Zhang L, Wang Y, Ren Y, Hack M, Shao Z, Jiang S (2016)
“Cloudburst: stateful functions-as-a-service”, Sreekanti V, Wu C, Lin XC, Schleier-Smith J, Gonzalez JE, Hellerstein JM, Tumanov A (2020)