xv6 - DRAFT as of September 4, 2018

1 Xv6a simple, Unix-like teaching operating systemRuss CoxFrans KaashoekRobert as of September 4, 2018 Contents0 Operating system interfaces71 Operating system organization172 Page tables293 Traps, interrupts, and drivers394 Locking515 Scheduling616 File system757 Summary93 APC hardware95 BThe boot loader99 Index105 DRAFT as of September 4, 20183 and acknowledgementsThis is a DRAFT text intended for a class on operating systems. It explains the main con-cepts of operating systems by studying an example kernel, named xv6.

2 Xv6 is a re-im-plementation of Dennis Ritchie s and Ken Thompson s Unix Version 6 (v6). xv6 loose-ly follows the structure and style of v6, but is implemented in ANSI C for an x86-based text should be read along wit h the source code for xv6. Thi s approach is inspiredby John Lions s Commentary on UNIX 6th Edition (Pee r to Pee r Communications; IS-BN: 1-57398-013-7; 1st edition (June 14, 2000)). See forpointers to on-line resources for v6 and xv6, including several hands-on homework as-signments using have use d thi s text in , the operating systems class at MIT.

3 We thank the fac-ulty, teaching assistants, and students of who have all directly or indirectly con-tributed to xv6. In particular, we would lik e to thank Austin Clements and NickolaiZeldovich. Finally, we would lik e to thank people who emailed us bugs in the text orsuggestions for provements: Abutalib Aghayev, Sebastian Boehm, Anton Burtsev,Raphael Carvalho, Rasit Eskicioglu, Color Fuzzy, Giuseppe, Tao Guo, Robert Hilder-man, Wolfgang Keller, Austin Liew, Pavan Maddamsetti, Jacek Masiulaniec, MichaelMcConville, miguelgvieira, Mark Morrissey, Harry Pan, Askar Safin, Salman Shah, Rus-lan Savchenko, Pawel Szczurko, Warren Toomey, tyfkda, and Zou Chang you spot errors or have suggestions for improvement.

4 Please send email to FransKaashoek and Robert Morris as of September 4, 20185 0 Operating system interfacesThe job of an operating system is to share a computer among multiple programsand to provide a mor e useful set of services than the hardware alone supports. Theoperating system manages and abstracts the low-level hardware, so that, for example, aword processor nee d not concern itself wit h which type of dis k hardware is beingused. It also shares the hardware among multiple programs so that they run (or ap-pear to run) at the same time.

5 Finally, operating systems provide controlled ways forprograms to interact, so that they can share data or wor k operating system provides services to use r programs through an a good interface turns out to be difficult. On the one hand, we would liketh e interface to be simple and narrow because that makes it easier to get the imple-mentation right. On the other hand, we may be tempted to offer many sophisticatedfeatures to applications.

6 The trick in resolving thi s tension is to design interfaces thatrely on a few mechanisms that can be combined to provide much book use s a single operating system as a concrete example to illustrate oper-ating system concepts. That operating system, xv6, provides the basic interfaces intro-duced by Ken Thompson and Dennis Ritchie s Unix operating system, as wel l as mim-icking Unix s internal design. Unix provides a narrow interface whose mechanismscombine well, offering a surprising degree of generality.

7 Thi s interface has bee n sosuccessful that modern operating systems BSD, Lin ux, Mac OS X, Solaris, and even,to a lesser extent, Microsoft Windows have Unix-like interfaces. Understanding xv6is a good start toward understanding any of these systems and many shown in Figure 0-1, xv6 takes the traditional for m of akernel, a special pro-gram that provides services to running programs. Each running program, called apro-cess, has memory containing instructions, data, and a stack.

8 The instructions imple-ment the program s computation. The data are the variables on which the computa-tion acts. The stack organizes the program s procedure a process needs to invoke a kernel service, it invokes a procedure call inth e operating system interface. Such a procedure is called asystem call. The systemcall enters the kernel; the kernel performs the service and returns. Thus a process al-ternates between executing inuser spaceandkernel kernel use s the CPU s hardware protection mechanisms to ensure that eachprocess executing in use r space can access onl y its own memory.

9 The kernel executeswith the hardware privileges required to implement these protections; use r programsexecute without those privileges. When a use r program invokes a system call, thehardware raise s the privilege level and starts executing a pre-arranged function in collection of system calls that a kernel provides is the interface that use r pro-grams see . The xv6 kernel provides a subset of the services and system calls that Unixkernels traditionally offer.

10 Figure 0-2lis ts all of xv6 s system as of September 4, 20187 designkernelprocesssystem calluser spacekernel spaceKernelshellcatuserspacekernelspaces ystemcallFigure 0-1. A kernel and two use r res t of thi s chapter outlines xv6 s services processes, memory, file descrip-tors, pipes, and file system and illustrates them wit h code snippets and discussions ofhow theshell, which is the primary use r interface to traditional Unix-like systems, usesthem. The shell s use of system calls illustrates how carefully they have bee n shell is an ordinary program that reads commands fro m the use r and exe-cutes them.