Xv6 - MIT OpenCourseWare

xv6

a simple, Unixlike teaching operating system

Russ Cox

Frans Kaashoek

Robert Morris

Draft as of August 28, 2012

Contents

0 Operating system interfaces

7

1 The first process

17

2 Page tables

25

3 Traps, interrupts, and drivers

33

4 Locking

45

5 Scheduling

53

6 File system

67

A PC hardware

83

B The boot loader

87

Index

93

DRAFT as of August 28, 2012

2



Foreword and acknowledgements

This 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. xv6 is a reim 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 multiprocessor.

The text should be read along with the source code for xv6. This approach is inspired by John Lions's Commentary on UNIX 6th Edition (Peer to Peer Communications; IS BN: 1573980137; 1st edition (June 14, 2000)). See for pointers to online resources for v6 and xv6.

We have used this text in 6.828, the operating system class at MIT. We thank the fac ulty, TAs, and students of 6.828 who all directly or indirectly contributed to xv6. In particular, we would like to thank Austin Clements and Nickolai Zeldovich.

DRAFT as of August 28, 2012

3



Chapter 0 Operating system interfaces

interface design kernel process system calls user space kernel space

The job of an operating system is to share a computer among multiple programs and to provide a more useful set of services than the hardware alone supports. The operating system manages and abstracts the lowlevel hardware, so that, for example, a word processor need not concern itself with which type of disk hardware is being used. It also multiplexes the hardware, allowing many programs to share the computer and run (or appear to run) at the same time. Finally, operating systems provide con trolled ways for programs to interact, so that they can share data or work together.

An operating system provides services to user programs through an interface. Designing a good interface turns out to be difficult. On the one hand, we would like the 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 sophisticated features to applications. The trick in resolving this tension is to design interfaces that rely on a few mechanisms that can be combined to provide much generality.

This book uses 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 well as mim icking Unix's internal design. Unix provides a narrow interface whose mechanisms combine well, offering a surprising degree of generality. This interface has been so successful that modern operating systems--BSD, Linux, Mac OS X, Solaris, and even, to a lesser extent, Microsoft Windows--have Unixlike interfaces. Understanding xv6 is a good start toward understanding any of these systems and many others.

As shown in Figure 01, xv6 takes the traditional form of a kernel, a special pro gram that provides services to running programs. Each running program, called a process, has memory containing instructions, data, and a stack. The instructions im plement the program's computation. The data are the variables on which the computa tion acts. The stack organizes the program's procedure calls.

When a process needs to invoke a kernel service, it invokes a procedure call in the operating system interface. Such procedures are call system calls. The system call enters the kernel; the kernel performs the service and returns. Thus a process al ternates between executing in user space and kernel space.

The kernel uses the CPU's hardware protection mechanisms to ensure that each process executing in user space can access only its own memory. The kernel executes with the hardware privileges required to implement these protections; user programs execute without those privileges. When a user program invokes a system call, the hardware raises the privilege level and starts executing a prearranged function in the kernel.

The collection of system calls that a kernel provides is the interface that user pro grams see. The xv6 kernel provides a subset of the services and system calls that Unix kernels traditionally offer. The calls are:

DRAFT as of August 28, 2012

4



user space

kernel space

shell

cat

system

call

Kernel

Figure 01. A kernel and two user processes.

process

System call

Description

fork()

Create process

exit()

Terminate current process

wait()

Wait for a child process to exit

kill(pid)

Terminate process pid

getpid()

Return current process's id

sleep(n)

Sleep for n seconds

exec(filename, *argv)

Load a file and execute it

sbrk(n)

Grow process's memory by n bytes

open(filename, flags)

Open a file; flags indicate read/write

read(fd, buf, n)

Read n byes from an open file into buf

write(fd, buf, n)

Write n bytes to an open file

close(fd)

Release open file fd

dup(fd)

Duplicate fd

pipe(p)

Create a pipe and return fd's in p

chdir(dirname)

Change the current directory

mkdir(dirname)

Create a new directory

mknod(name, major, minor) Create a device file

fstat(fd)

Return info about an open file

link(f1, f2)

Create another name (f2) for the file f1

unlink(filename)

Remove a file

The rest of this chapter outlines xv6's services--processes, memory, file descrip

tors, pipes, and file system--and illustrates them with code snippets and discussions of

how the shell uses them. The shell's use of system calls illustrates how carefully they

have been designed.

The shell is an ordinary program that reads commands from the user and exe

cutes them, and is the primary user interface to traditional Unixlike systems. The fact

that the shell is a user program, not part of the kernel, illustrates the power of the sys

tem call interface: there is nothing special about the shell. It also means that the shell

is easy to replace; as a result, modern Unix systems have a variety of shells to choose

from, each with its own user interface and scripting features. The xv6 shell is a simple

implementation of the essence of the Unix Bourne shell. Its implementation can be

found at line (7850).

Processes and memory

DRAFT as of August 28, 2012

5



 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download