O perating s ystems t hree e asy p ieces

standard library

to applications.

Finally, because virtualization allows many programs to run (thus shar-

ing the CPU), and many programs to concurrently access their own in-

structions and data (thus sharing memory), and many programs to access

devices (thus sharing disks and so forth), the OS is sometimes known as

a resource manager. Each of the CPU, memory, and disk is a resource

of the system; it is thus the operating system’s role to manage those re-

sources, doing so efficiently or fairly or indeed with many other possible

goals in mind. To understand the role of the OS a little bit better, let’s take

a look at some examples.

3

Another early name for the OS was the supervisor or even the master control program.

Apparently, the latter sounded a little overzealous (see the movie Tron for details) and thus,

thankfully, “operating system” caught on instead.

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

I

NTRODUCTION TO

O

PERATING

S

YSTEMS

5

1

#include 

2

#include 

3

#include 

4

#include 

5

#include "common.h"

6

7

int

8

main(int argc, char *argv[])

9

{

10

if (argc != 2) {

11

fprintf(stderr, "usage: cpu \n");

12

exit(1);

13

}

14

char *str = argv[1];

15

while (1) {

16

Spin(1);

17

printf("%s\n", str);

18

}

19

return 0;

20

}

Figure 2.1: Simple Example: Code That Loops and Prints

2.1 Virtualizing the CPU

Figure

2.1

depicts our first program. It doesn’t do much. In fact, all

it does is call Spin(), a function that repeatedly checks the time and

returns once it has run for a second. Then, it prints out the string that the

user passed in on the command line, and repeats, forever.

Let’s say we save this file as cpu.c and decide to compile and run it

on a system with a single processor (or CPU as we will sometimes call it).

Here is what we will see:

prompt> gcc -o cpu cpu.c -Wall

prompt> ./cpu "A"

A

A

A

A

ˆC

prompt>

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 the user

(in this example, the letter “A”), and continues. Note the program will

run forever; only by pressing “Control-c” (which on U

NIX

-based systems

will terminate the program running in the foreground) can we halt the

program.

Now, let’s do the same thing, but this time, let’s run many different in-

stances of this same program. Figure

2.2

shows the results of this slightly

more complicated example.

c

 2014, A

RPACI

-D

USSEAU

T

HREE

E

ASY

P

IECES

---

6

I

NTRODUCTION TO

O

PERATING

S

YSTEMS

prompt> ./cpu A & ; ./cpu B & ; ./cpu C & ; ./cpu D &

[1] 7353

[2] 7354

[3] 7355

[4] 7356

A

B

D

C

A

B

D

C

A

C

B

D

...

Figure 2.2: Running Many Programs At Once

Well, now things are getting a little more interesting. Even though we

have only one processor, somehow all four of these programs seem to be

running at the same time! How does this magic happen?

4

It turns out that the operating system, with some help from the hard-

ware, is in charge of this illusion, i.e., the illusion that the system has a

very large number of virtual CPUs. Turning a single CPU (or small set of

them) into a seemingly infinite number of CPUs and thus allowing many

programs to seemingly run at once is what we call virtualizing the CPU,

the focus of the first major part of this book.

Of course, to run programs, and stop them, and otherwise tell the OS

which programs to run, there need to be some interfaces (APIs) that you

can use to communicate your desires to the OS. We’ll talk about these

APIs throughout this book; indeed, they are the major way in which most

users interact with operating systems.

You might also notice that the ability to run multiple programs at once

raises all sorts of new questions. For example, if two programs want to

run at a particular time, which should run? This question is answered by

a policy of the OS; policies are used in many different places within an

OS to answer these types of questions, and thus we will study them as

we learn about the basic mechanisms that operating systems implement

(such as the ability to run multiple programs at once). Hence the role of

the OS as a resource manager.

4

Note how we ran four processes at the same time, by using the & symbol. Doing so runs a

job in the background in the tcsh shell, which means that the user is able to immediately issue

their next command, which in this case is another program to run. The semi-colon between

commands allows us to run multiple programs at the same time in tcsh. If you’re using a

different shell (e.g., bash), it works slightly differently; read documentation online for details.

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

I

NTRODUCTION TO

O

PERATING

S

YSTEMS

7

1

#include 

2

#include 

3

#include 

4

#include "common.h"

5

6

int

7

main(int argc, char *argv[])

8

{

9

int *p = malloc(sizeof(int));

// a1

10

assert(p != NULL);

11

printf("(%d) address of p: %08x\n",

12

getpid(), (unsigned) p);

// a2

13

*p = 0;

// a3

14

while (1) {

15

Spin(1);

16

*p = *p + 1;

17

printf("(%d) p: %d\n", getpid(), *p); // a4

18

}

19

return 0;

20

}

Figure 2.3: A Program that Accesses Memory

2.2 Virtualizing Memory

Now let’s consider memory. The model of physical memory pre-

sented by modern machines is very simple. Memory is just an array of

bytes; to read memory, one must specify an address to be able to access

the data stored there; to write (or update) memory, one must also specify

the data to be written to the given address.

Memory is accessed all the time when a program is running. A pro-

gram keeps all of its data structures in memory, and accesses them through

various instructions, like loads and stores or other explicit instructions

that access memory in doing their work. Don’t forget that each instruc-

tion of the program is in memory too; thus memory is accessed on each

instruction fetch.

Let’s take a look at a program (in Figure

2.3

) that allocates some mem-

ory by calling malloc(). The output of this program can be found here:

prompt> ./mem

(2134) memory address of p: 00200000

(2134) p: 1

(2134) p: 2

(2134) p: 3

(2134) p: 4

(2134) p: 5

ˆC

The program does a couple of things. First, it allocates some memory

(line a1). Then, it prints out the address of the memory (a2), and then

puts the number zero into the first slot of the newly allocated memory

(a3). Finally, it loops, delaying for a second and incrementing the value

stored at the address held in p. With every print statement, it also prints

out what is called the process identifier (the PID) of the running program.

This PID is unique per running process.

c

 2014, A

RPACI

-D

USSEAU

T

HREE

E

ASY

P

IECES

---

8

I

NTRODUCTION TO

O

PERATING

S

YSTEMS

prompt> ./mem &; ./mem &

[1] 24113

[2] 24114

(24113) memory address of p: 00200000

(24114) memory address of p: 00200000

(24113) p: 1

(24114) p: 1

(24114) p: 2

(24113) p: 2

(24113) p: 3

(24114) p: 3

(24113) p: 4

(24114) p: 4

...

Figure 2.4: Running The Memory Program Multiple Times

Again, this first result is not too interesting. The newly allocated mem-

ory is at address 00200000. As the program runs, it slowly updates the

value and prints out the result.

Now, we again run multiple instances of this same program to see

what happens (Figure

2.4

). We see from the example that each running

program has allocated memory at the same address (00200000), and yet

each seems to be updating the value at 00200000 independently! It is as

if each running program has its own private memory, instead of sharing

the same physical memory with other running programs

5

.

Indeed, that is exactly what is happening here as the OS is virtualiz-