Introduction to Operating Systems

1 2 Introduction to Operating SystemsIf you are taking an undergraduate Operating Systems course, youshouldalready have some idea of what a computer program does when it not, this book (and the corresponding course) is going to be difficult so you should probably stop reading this book, or run to the near-est bookstore and quickly consume the necessary background materialbefore continuing (both Patt & Patel [PP03] and Bryant & O Hallaron[BOH10] are pretty great books).So what happens when a program runs?Well, a running program does one very simple thing: it executes in-structions.

2 Many millions (and these days, even billions) of times ev-ery second, the processorfetchesan instruction from memory,decodesit ( , figures out which instruction this is), andexecutesit ( , it doesthe thing that it is supposed to do, like add two numbers together, accessmemory, check a condition, jump to a function, and so forth). Afterit isdone with this instruction, the processor moves on to the next instruction,and so on, and so on, until the program finally , we have just described the basics of theVon Neumannmodel ofcomputing2. Sounds simple, right? But in this class, we will be learningthat while a program runs, a lot of other wild things are going on withthe primary goal of making the systemeasy to is a body of software, in fact, that is responsible for makingiteasy to run programs (even allowing you to seemingly run many at thesame time), allowing programs to share memory, enabling programs tointeract with devices, and other fun stuff like that.

3 That bodyof software1Of course, modern processors do many bizarre and frightening things underneath thehood to make programs run faster, , executing multiple instructions at once, and even issu-ing and completing them out of order! But that is not our concern here; we are just concernedwith the simple model most programs assume: that instructions seemingly execute one at atime, in an orderly and sequential Neumann was one of the early pioneers of computing Systems . He also did pioneer-ing work on game theory and atomic bombs, and played in the NBA for sixyears. OK, one ofthose things isn t TOOPERATINGSYSTEMSTHECRUX OF THEPROBLEM:HOWTOVIRTUALIZERESOURCESOne central question we will answer in this book is quite simple:howdoes the Operating system virtualize resources?

4 This is the crux of OS does this is not the main question, as the answershould be obvious: it makes the system easier to use. Thus, we focus onthehow: what mechanisms and policies are implemented by the OS toattain virtualization? How does the OS do so efficiently? What hardwaresupport is needed?We will use the crux of the problem , in shaded boxes such as thisone,as a way to call out specific problems we are trying to solve in buildingan Operating system. Thus, within a note on a particular topic, youmayfind one or morecruces(yes, this is the proper plural) which highlight theproblem.

5 The details within the chapter, of course, present thesolution,or at least the basic parameters of a called theoperating system(OS)3, as it is in charge of making sure thesystem operates correctly and efficiently in an easy-to-use primary way the OS does this is through a general technique thatwe callvirtualization. That is, the OS takes aphysicalresource (such asthe processor, or memory, or a disk) and transforms it into a more gen-eral, powerful, and easy-to-usevirtualform of itself. Thus, we sometimesrefer to the Operating system as avirtual course, in order to allow users to tell the OS what to do and thusmake use of the features of the virtual machine (such as runninga pro-gram, or allocating memory, or accessing a file), the OS also providessome interfaces (APIs) that you can call.

6 A typical OS, in fact, exportsa few hundredsystem callsthat are available to applications. Becausethe OS provides these calls to run programs, access memory and devices,and other related actions, we also sometimes say that the OS provides astandard libraryto , because virtualization allows many programs to run (thus shar-ing the CPU), and many programs to concurrently access their ownin-structions and data (thus sharing memory), and many programs toaccessdevices (thus sharing disks and so forth), the OS is sometimes known asaresource manager. Each of the CPU, memory, and disk is aresourceof the system; it is thus the Operating system s role tomanagethose re-sources, doing so efficiently or fairly or indeed with many other possiblegoals in mind.

7 To understand the role of the OS a little bit better, let s takea look at some early name for the OS was thesupervisoror even themaster control , the latter sounded a little overzealous (see the movie Tron for details) and thus,thankfully, Operating system caught on [ ] TOOPERATINGSYSTEMS31#include < >2#include < >3#include < >4#include < >5#include " "67int8main(int argc, char*argv[])9{10if (argc != 2) {11fprintf(stderr, "usage: cpu <string>\n");12exit(1);13}14char*str = argv[1];15while (1) {16 Spin(1);17printf("%s\n", str);18}19return 0;20}Figure :Simple Example: Code That Loops And Prints ( ) Virtualizing The CPUF igure depicts our first program.

8 It doesn t do much. In fact, allit does is callSpin(), a function that repeatedly checks the time andreturns once it has run for a second. Then, it prints out the stringthat theuser passed in on the command line, and repeats, s say we save this file decide to compile and run iton a system with a single processor (orCPUas we will sometimes call it).Here is what we will see:prompt> gcc -o cpu -Wallprompt> ./cpu "A"AAAA Cprompt>Not too interesting of a run the system begins running the program,which repeatedly checks the time until a second has elapsed. Once a sec-ond has passed, the code prints the input string passed in by theuser (inthis example, the letter A ), and continues.

9 Note the program will runforever; by pressing Control-c (which on UNIX-based Systems will ter-minate the program running in the foreground) we can halt the 2008 20, ARPACI-DUSSEAUTHREEEASYPIECES4 Introduction TOOPERATINGSYSTEMS prompt> ./cpu A & ./cpu B & ./cpu C & ./cpu D &[1] 7353[2] 7354[3] 7355[4] :Running Many Programs At OnceNow, let s do the same thing, but this time, let s run many different in-stances of this same program. Figure shows the results of thisslightlymore complicated , now things are getting a little more interesting. Even though wehave only one processor, somehow all four of these programs seem to berunning at the same time!

10 How does this magic happen?4It turns out that the Operating system, with some help from the hard-ware, is in charge of thisillusion, , the illusion that the system hasa very large number of virtual CPUs. Turning a single CPU (or a smallset of them) into a seemingly infinite number of CPUs and thus allowingmany programs to seemingly run at once is what we callvirtualizing theCPU, the focus of the first major part of this course, to run programs, and stop them, and otherwise tell the OSwhich programs to run, there need to be some interfaces (APIs) that youcan use to communicate your desires to the OS.