\chapter{Overview of Functions of an Operating System}
\label{chap:os}

\section{Introduction}

\subsection{It's Just a Program!}

First and foremost, it is vital to understand that an \textbf{operating
system} (OS) is just a program---a very large, very complex program, but
still just a program. The OS provides support for the loading and
execution of other programs (which we will refer to below as
{}``application programs{}''), and the OS will set things up so that it
has some special privileges which user programs don't have, but in the
end, the OS is simply a program.  

The source code for Linux, for instance, consists of millions of lines,
mainly C but some assembly language for certain low-level
machine-specific tasks.  The binary for the program typically has a name
which is some variant of {\bf vmlinuz}.  Look for it in your Linux
machine, say in the directory {\bf /boot}.

For example, when your program, say \textbf{a.out},\footnote{ Or it
could be a program which you didn't write yourself, say \textbf{gcc}.  }
is running, the OS is \textit{not} running, Thus the OS has no power to
suspend your program while your program is running---since the OS isn't
running! This is a key concept, so let's first make sure what the
statement even means.

What does it mean for a program to be {}``running{}'' anyway? Recall
that the CPU is constantly performing its fetch/execute/fetch/execute/... 
cycle.  For each fetch, it fetches whatever instruction the Program
Counter (PC) is pointing to. If the PC is currently pointing to an
instruction in your program, then your program is running! Each time an
instruction of your program executes, the circuitry in the CPU will
update the PC, having it point to either the next instruction (the usual
case) or an instruction located elsewhere in your program (in the case
of jumps).

The point is that the only way your program can stop running is if the
PC is changed to point to another program, say the OS. How might this
happen?  There are only two ways this can occur:

\begin{itemize}

\item Your program can \textit{voluntarily} relinquish the CPU to the
OS. It does this via a \textbf{system call}.which is a call to some
function in the operating system which provides some useful service. \\
For example, suppose the C source file from which \textbf{a.out} was
compiled had a call to \textbf{scanf()}. The \textbf{scanf()} function
is a C library function, which was linked into \textbf{a.out}.  But
\textbf{scanf()} itself calls \textbf{read()}, a function within the OS.
So, when \textbf{a.out} reaches the \textbf{scanf()} call, that will
result in a call to the OS, but after the OS does the read from the
keyboard, the OS will return to \textbf{a.out}.

\item The other possibility is that a hardware interrupt occurs.  This
is a signal---a physical pulse of current along an
\textbf{interrupt-request} line in the bus---from some input/output
(I/O) device such as the keyboard to the CPU. The circuitry in the CPU
is designed to then jump to a place in memory which we designated upon
bootup of the machine. This will be a place in the OS, so the OS will
now run. The OS will attend to the I/O device, e.g. record the
keystroke in the case of the keyboard, and then return to the
interrupted program via an IRET instruction.

Note in our keystroke example that the keystroke may not have been made
by you.  While your program is running, some other user of the machine
may hit a key.  The interrupt will cause your program to be suspended;
the OS will run the device driver for whichever device caused the
interrupt---the keyboard, if the person was sitting at the console of
the machine, or the network interface card, if the person was logged in
remotely, say via \textbf{ssh}---which will record the keystroke in
the buffer belonging to that other user; and the OS will execute an {\bf
iret} to return from the interrupt, causing your program to resume.

A hardware interrupt can also be generated by the CPU itself, e.g. if
your program attempts to divide by 0, or tries to access memory which
the hardware finds is off limits to your program.  (The latter case
describes a seg fault; more on this later.)

\end{itemize}

\checkpoint

So, when your program is running, it is king. The OS has no power to
stop it, since it is NOT running.  The only ways your program can stop
running is if it voluntarily does so or is forced to stop by action
occuring at an I/O device.

\subsection{What Is an OS for, Anyway?}

A computer might not even have an OS, say in embedded applications.  A
computer embedded in a washing machine will just run one program (in
ROM).  So, there are no files to worry about, no issues of timesharing,
etc., and thus no need for an OS.

But on a general-purpose machine, we need an OS to do:

\begin{itemize}

\item Input/output device management:

If you recall the example in Chapter \ref{chap:io}, we saw that at the machine
level it takes about a dozen lines of code just to read one character
from the keyboard.  We certainly would not want to have to deal with
that in our own programs, but fortunately the OS provides this service
for us.  Let's see what that means in the case of the keyboard. 

First, the OS includes the keyboard device driver, so that we do not
need to write our own.  Second, the OS provides the {\bf read()}
function for us to call in order to pick up the characters the keyboard
driver has collected for us.  Suppose for instance that you have a {\bf
scanf()} call or a {\bf cin} statement in your program.  When the user
types some characters, each keystroke will cause an
interrupt.\footnote{Actually two interrupts, one for key press and one
for release, but let's say one here, for simplicity.}  When the
interrupt occurs, the keyboard driver will add the character to an
array, typically referred to as a {\bf buffer}.  Your program's {\bf
scanf()} call or {\bf cin} statement will include to a call to {\bf
read()}, a function in the OS.  That function will then pick up the
characters in the keyboard buffer, parse them according to whatever kind
of read format you asked for, and return the result to your program.

Again, the central point here is that the OS is doing a big service for
you, in that it is alleviating you of the burden of writing all this
code.

\item File management:

For example, suppose you are writing a program to write a new file.  You
wouldn't want to have to deal with the details of knowing where the
empty space is on the disk, choosing some of it for the file, etc.
Again, the OS does this for you.

\item Process management:

When you want to run a program, the OS loads it into memory for you and
starts its execution. 

The OS enables \textbf{timesharing}, in which many application programs
seem to be running simultaneously but are actually {}``taking turns,{}''
\textit{by coordinating with hardware operations}.

\item Memory management:

The OS must keep track of which parts of memory are currently in use, so
that it knows what areas it can load a program to when the program is
requested for execution.

The OS also enables \textbf{virtual memory} operations for application
programs, which both allows flexible use of memory and enforces
security, again by \textit{by coordinating with hardware operations}.

\end{itemize}

How the OS does these things is explained in the following sections. We
will model the discussion after a Unix system, but the description here
applies to most modern OSs. It is assumed here that the reader is
familiar with basic Unix commands; a Unix tutorial is available at
\url{http://heather.cs.ucdavis.edu/~matloff/unix.html}

\section{Application Program Loading}

\subsection{Basic Operations}

Suppose you have just compiled a program, producing, say for a Linux system,
an executable file \textbf{a.out}.  (And the following would apply
equally well to {\bf gcc} or any other program.)  To run it, you type

\begin{Verbatim}[fontsize=\relsize{-2}]
% a.out
\end{Verbatim}

For the time being, assume a very simple machine/OS combination, with no
\textbf{virtual memory}. Here is what will occur:

\begin{itemize}

\item During your typing of the command, the shell is running, say
\textbf{tcsh} or \textbf{bash}. Again, the shell is just a program (one
which could be assigned as a homework problem in a course).  It prints
out the `\%' prompt using {\bf printf()},\footnote{Most shells are
written in C.} and enters a loop in which it reads the command you type
using {\bf scanf()}.\footnote{Note that there will be an interrupt each
time you type a character.  The OS will store these characters until you
hit Enter, in which case the OS will finally ``wake'' the shell program,
whose {\bf scanf()} will now finally execute.  See also Sleep and Run
states later in this chapter.}

\item The shell will then make a system call, {\bf execve()},\footnote{It
will also call another system call, {\bf fork()}, but we will not go into that
here.} asking the OS to run \textbf{a.out}. The OS is now running. 

\item The OS will look in its disk directory, to determine where on disk
the file \textbf{a.out} is. It will read the {\bf header}, i.e.
beginning section of \textbf{a.out}, which contains information on the
size of the program, a list of the data sections used by the program,
and so on.\footnote{You can read that information yourself, using the
{\bf readelf} command in Linux.}

\item The OS will check its memory-allocation table (this is just an
array in the OS) to find an unused region or regions of memory large
enough for \textbf{a.out}.  (Note that the OS has loaded all
currently-active programs in memory up to now, just like it is loading
\textbf{a.out} now, so it knows exactly which parts of memory are in use
and which are free.) We need space both for \textbf{a.out}'s
instructions, in the {\bf .text} section, its static data (in the {\bf
.data} section for uninitialized variables, and in the {\bf .bss} section
for initialized variables), as well as for stack space and the
\textbf{heap}.  

The heap is used for calls to {\bf malloc()} or for invocations of the
C++ operator {\bf new}.  With the GCC compiler, these are one and the
same, since the internal implementation of {\bf new} calls {\bf
malloc()}.  There will be a data structure there which keeps track of
which parts of the heap are in use and which are free.  Of course, they
are initially all free.  Each time we need new memory, we use parts of
the heap, and they will be marked as in use.  Calling {\bf free()} or
invoking {\bf delete} will result in the space being marked as free
again.  All the marking is done by {\bf malloc()}.

\item The OS will then load \textbf{a.out} (including text and data)
into those regions of memory, and will update its memory-allocation
table accordingly. 

\item The OS will check a certain section of the \textbf{a.out} file, in
which the linker previously recorded \textbf{a.out}'s \textbf{entry
point}, i.e. the instruction in \textbf{a.out} at which execution is to
begin.   (This for example is \_start in our previous assembly language
examples.)

\item The OS is now ready to initiate execution of \textbf{a.out}. It
will set the stack pointer to point to the place it had chosen earlier
for \textbf{a.out}'s stack. (The OS will save its own register values,
including stack pointer value, beforehand.) Then it will place any
command-line arguments on {\bf a.out}'s stack, and then actually start
\textbf{a.out}, say by executing a JMP instruction (or equivalent) to
jump to \textbf{a.out}'s entry point. 

\item The \textbf{a.out} program is now running! 

\end{itemize}

\checkpoint

\subsection{Chains of Programs Calling Programs}

Note that \textbf{a.out} itself may call {\bf execve()} and start other
programs running.  We mentioned above that the shell does this, and so
for example does \textbf{gcc}.\footnote{Remember, a compiler is just a
program too. It is a very large and complex program, but in principle no
different from the programs you write.} It first runs the \textbf{cpp} C
preprocessor (which translates {\bf \#include}, {\bf \#define} etc. from
your C source file). Then it runs \textbf{cc1}, which is the
{}``real{}'' compiler (\textbf{gcc} itself is just a manager that runs
the various components, as you can see now); this produces an assembly
language file.\footnote{You can view this file by running \textbf{gcc}
with its -S option. This is often handy if you are going to write an
assembly-language subroutine to be called by your C code, so that you
can see how the compiler will deal with the parameters in the call to
the subroutine.  } Then \textbf{gcc} runs \textbf{as}, the assembler, to
produce a {\bf .o} machine code file. The latter must be linked with
some code, e.g. {\bf /usr/lib/crt1.o} and other files which set up the
{\bf main()} structure, e.g. access to the {\bf argv} command-line
arguments, and also linked to the C library, {\bf /lib/libc.so.6}; so,
\textbf{gcc} runs the linker, \textbf{ld}. In all these cases,
\textbf{gcc} starts these programs by calling {\bf execve()}.

\subsection{Static Versus Dynaming Linking}

Say your C code includes a call to {\bf printf()}.  Even though someone
else wrote {\bf printf()}, when you link it in to your program (which
GCC does for you when it calls LD), it becomes part of your program.
The question is when this occurs.

With {\bf static} linking, LD will put {\bf printf()}'s machine code
into your {\bf a.out} executable.  However, since most programs make use
of the C library, they would collectively take up a lot of disk space if
static linking were used.  

So, the default is that GCC and LD would set up {\bf dynamic} linking
for {\bf printf()} in your program.  In your {\bf a.out} file, there
will be a message saying that your code calls {\bf printf()}, and that
when your program is loaded into memory and is run, {\bf printf()}
should be linked in to it at that time.

\subsection{Making These Concepts Concrete: Commands You Can Try Yourself}

\subsubsection{Mini-Example}

Below is a simple illustration of {\bf execve()} in action.  The program
{\bf run.c} makes this system call to get the program {\bf greeting.c}
running.  Assume the executable files are named {\bf greeting} and {\bf
run}.

\begin{Verbatim}[fontsize=\relsize{-2},numbers=left]
// greeting.c

main()
{  printf("hello\n");  }
\end{Verbatim}

\begin{Verbatim}[fontsize=\relsize{-2},numbers=left]
// run.c

main()
{  char **a[2],  // arguments to "greeting" (none here; see man page)
        **p[2];  // environment for "greeting" (none here)

   a[0] = ""; a[1] = 0;
   p[0] = ""; p[1] = 0;
   execve("./greeting",a,p);  }
\end{Verbatim}

\begin{Verbatim}[fontsize=\relsize{-2},numbers=left]
% run
hello
\end{Verbatim}

\checkpoint

Note that the shell will do something like this too, when you request
that your program {\bf a.out} be run. 

\subsubsection{The strace Command}

The Unix \textbf{strace} command will report which system calls your
program makes. Place it before your program name on the command line, 
e.g.

\begin{Verbatim}[fontsize=\relsize{-2}]
% strace a.out
\end{Verbatim}

The output will be rather overwhelming, but if you sift through
it\footnote{I recommend running the Unix {\bf script} command before you
run {\bf strace}.  It will keep a record of everything that appears on
your screen.  After you are done running {\bf strace}, type {\tt exit}
to leave the shell created by {\bf script}.  Then the record of your
session is in a file named {\bf typescript}.  You can then browse
through it using your favorite text editor.} You will see that a call
{\bf execve()} is made by the shell to launch {\bf a.out}, as well as
the various systems call made by {\bf a.out}.

\section{OS Bootup}

As was explained earlier, when we wish to run an application program,
the OS loads the program into memory. But wait!  The OS is a program
too, so how does {\it it} get loaded into memory and begin execution?
The answer is that another program, the {\bf boot loader}, will load the
OS into memory.  But then how does the boot loader get loaded in
memory?!  It sounds like we have an endless, ``chicken and egg''
problem.  The resolution is that the boot loader is permanently in
memory, in ROM, so it doesn't have to be loaded.

The process by which the OS is loaded into memory is called
\textbf{bootup}.  We will explain this using the Intel Pentium
architecture for illustration.\footnote{An overview of that architecture
is presented in Section \ref{pentium}.}

The circuitry in the CPU hardware will be designed so that upon powerup
the Program Counter (PC) is initialized to some specific value,
0xfffffff0 in the case of Intel CPUs.  And those who \textbf{fabricate}
the computer (i.e. who put together the CPU, memory, bus, etc. to form a
complete system) will include a small ROM at that same address, again
0xfffffff0 in the Intel case. The contents of the ROM include the boot
loader program.  So, immediately after powerup, the boot loader program
is running!

The goal of the boot loader is to load in the OS from disk to memory. In
the simple form, the boot loader reads a specified area of the disk,
copies the contents there---which will be part of the OS---to some
section of memory, and then finally executes a JMP instruction (or
equivalent) to that section of memory---so that now the OS is running.
The OS then reads the rest of itself into memory.

For the sake of concreteness, let's look more closely at the Intel case.
The program in ROM here is the BIOS, the Basic I/O System. It contains
parts of the device drivers for that machine,\footnote{These may or may
not be used, depending on the OS. Windows uses them, but Linux doesn't.}
and also contains the first-stage boot loader program.

The boot loader program in the BIOS has been written to read some
information, to be described now, from the first physical sector of the
disk.\footnote{The boot device could be something else instead of a hard
drive, such as a floppy or a CD-ROM.  This is set in the BIOS, with a
priority ordering of which device to try to boot from first.} That
sector is called the Master Boot Record (MBR).

There will be one or more {\bf partitions} for the disk.  If, say, the
disk has 1,000 cylinders, then for example we may have the first 200 as
one partition and the remaining 800 as the second
partition.\footnote{You should review the material on disks in Chapter
\ref{chap:io}.} These simply divide up parts of the disk for different
purposes.  A typical example would be that there are two partitions, one
for Windows and the other for Linux.  Your machine was probably shipped
with the entire disk consisting of just one partition, but you can split
it into several partitions to accommodate different OSs.  

These partitions are defined in the {\bf partition table} in the MBR.
Note that there is no physical separation from one partition to the
next; the boundary between one partition and the next is only defined by
the partition table.  Exactly one of the primary partitions will be
marked in the table as {\bf active}, meaning bootable.

The MBR also contains the second-stage boot loader program.  The boot
loader program in the BIOS will read this second-stage code into memory
and then jump to it, so that that program is now running.  That program
reads the partition table, to determine which partition is the active
one.  It then goes to the first sector in that partition, reads in the
third-stage boot loader program into memory from there, and then jumps
to that program.

% The first-stage boot loader in ROM will copy the second-stage code to
% memory, starting at memory location 0x00007c00. It then does a jump to
% that address, so that that code is now running.

Now if the machine had originally been shipped with Windows installed,
the second-stage code in the MBR had been written to then load into
memory the third-stage code from the Windows partition.  If on the other
hand the machine had been shipped with Linux or some other OS installed,
there would be a partition for that OS; the code in the MBR would have
been written accordingly, and that OS would now be loaded into memory.

Many people who use Linux retain both Windows and Linux on their hard
drives, and have a \textbf{dual-boot} setup. They start with a Windows
machine, but then install Linux as well, so both OSs are on the machine.
As part of the process of installing Linux, the old MBR is copied
elsewhere, and a program named LILO (Linux Loader) is written into the
MBR.\footnote{A newer, now more popular alternative to LILO is GRUB.
But the principle is the same for both, so we will just refer to LILO
here for simplicity.}  In other words, LILO will be the second-stage
boot loader.  LILO will ask the user whether he/she wants to boot Linux
or Windows, and then go to the corresponding partition to load and
execute the third-stage boot loader which is there.\footnote{The
partition does not have to be the active one.  The term {\it active}
applies only from the point of view of the Windows second-stage boot
loader which had originally been installed in the MBR.}

In any case, after the OS is loaded into memory by the third-stage code,
that code will perform a jump to the OS, so the OS is running. 

\checkpoint

\section{Timesharing}

\subsection{Many Processes, Taking Turns}

Suppose you and someone else are both using the computer {\bf pc12} in
our lab, one of you at the console and the other logged in remotely.
Suppose further that the other person's program will run for five hours!
You don't want to wait five hours for the other person's program to end.
So, the OS arranges things so that the two programs will take turns
running.  It won't be visible to you, but that is what happens.

\textbf{Timesharing} involves having several programs running in what
\underbar{appears} to be a simultaneous manner.\footnote{These programs
could be from different users or the same user; it doesn't matter.} If
the system has only one CPU (for simplicity, we will exclude the case of
multiprocessor systems in this discussion), this simultaneity is of
course only an illusion, since only one program can run at any given
time, but it is a worthwhile illusion, as we will see.

First of all, how is this illusion attained? The answer is that we have
the programs all take turns running, with each turn---called a
\textbf{quantum} or \textbf{timeslice}---being of very short duration,
for example 50 milliseconds.  Say we have four programs, {\bf u}, {\bf
v}, {\bf x} and {\bf y}, running currently. What will happen is that
first {\bf u} runs for 50 milliseconds, then {\bf u} is suspended and
{\bf v} runs for 50 milliseconds, then {\bf v}  is suspended and {\bf x}
runs for 50 milliseconds, and so on.  After {\bf y} gets its turn, then
{\bf u} gets a second turn, etc.  Since the turn-switching, formally
known as \textbf{context-switching},\footnote{We are switching from the
``context'' of one program to another.} is happening so fast (every 50
milliseconds), it appears to us humans that each program is running
continuously (though at one-fourth speed), rather than on and off, on
and off, etc.\footnote{Think of a light bulb turning on and off
extremely rapidly, with half the time on and half off.  If it is
blinking rapidly enough, you won't see it go on and off.  You'll simply
see it as shining steadily at half brightness.}

But how can the OS enforce these quanta? For example, how can the OS
force the program {\bf u} above to stop after 50 milliseconds? As
discussed earlier, the answer is, {}``It can't! The OS is dead while
{\bf u} is running.{}'' Instead, the turns are implemented via a timing
device, which emits a hardware interrupt at the proper time. For
example, we could set the timer to emit an interrupt every 50
milliseconds. We would write a timer device driver, and incorporate it
into the OS.

We will make such an assumption here. However, what is more common is to
have the timer interrupt more frequently than the desired quantum size.
On a PC, the 8253 timer interrupts 100 times per second.  Every sixth
interrupt, the Linux OS will perform a context switch.  That results in
a quantum size of 60 milliseconds.  But this can be changed, simply by
changing the count of interrupts needed to trigger a context switch.

The timer device driver saves all {\bf u}'s current register values,
including its PC value and the value in its EFLAGS register. Later, when
{\bf u}'s next turn comes, those values will be restored, and {\bf u}
will resume execution as if nothing ever happened. For now, though, the
OS routine will restore {\bf v}'s's previously-saved register values,
making sure to restore the PC value last of all. That last action forces
a jump from the OS to {\bf v}, right at the spot in {\bf v}  where {\bf
v} was suspended at the end of its last quantum. (Again, the CPU just
{}``minds its own business,{}'' and does not {}``know{}'' that one
program, the OS, has handed over control to another, {\bf v}; the CPU
just keeps performing its fetch/execute cycle, fetching whatever the PC
points to, oblivious to which process is running.)

\checkpoint

At any given time, there are many different \textbf{processes} in
memory. These are instances of executions of programs. If for instance
there are three users running the \textbf{gcc} C compiler right now on a
given machine, here one program corresponds to three processes.

\subsection{Example of OS Code: Linux for Intel CPUs}

Here is a bit about how the context switch is done in Linux, in the
version for Intel machines.\footnote{This was as of Linux kernel version
2.3.  I have slightly modified some of this section for the sake
of simplicity.}

The OS maintains a {\bf process table}, which is simply an array of {\bf
struct}s, one for each process.  The {\bf struct} for a process is
called the Task State Segment (TSS) for that process, and stores various
pieces of information about that process, such as the register values
which the program had at the time its last turn ended.  Remember, these
need to be stored somewhere so that we can restore them at the program's
next turn; here's where we store them.

As an example of the operations performed, and to show you concretely
that the OS is indeed really a program with real code, here is a typical
excerpt of Linux internal code:\footnote{Linux is constantly evolving.
This code existed in Linux at the time it was included in this book, but
could have changed subsequently.}

\begin{Verbatim}[fontsize=\relsize{-2},numbers=left]
pushl %esi
pushl %edi
pushl %ebp 
movl %esp, 532(%ebx) 
...
movl 532(%ecx), %esp
...
popl %ebp
popl %edi
popl %esi
...
iret
\end{Verbatim}

This code is the ISR for the timer.  Upon entry, {\bf u}'s turn has just
ended, having been interrupted by the timer.  In code not shown here,
the OS has pointed the registers EBX and ECX to the TSSs of the process
whose turn just ended, {\bf u}, and the process to which we will give
the next turn, say {\bf v}.

By the way, how does the OS know that the process whose turn just ended
was {\bf u}'s?  The answer is that whenever the OS gives a process a
turn, it records which process it was.  In Linux this is information is
stored at address 0xffffe000, and the macro {\bf GET\_CURRENT()} is used
to fetch it and place it into a register specified by the programmer; in
our situation here, the register would be EBX.  So the OS knows where to
point EBX.  The OS will make a decision as to which process to next give
a turn to, and point ECX to it.

Here is what that code does.  The source code for Linux includes a
variable {\bf tss}, which is the TSS {\bf struct} for the current
process.  In that struct is a field named {\bf esp}.  So, {\bf tss.esp}
contains the previously-stored value of ESP, the stack pointer, for this
process; this field happens to be located 532 bytes past the beginning
of the TSS.\footnote{In the C source code, this field is referred to as
{\bf tss.esp}, but in assembly language we can only use the 532, as
field names of {\bf struct}s are not shown.}

Now, upon entry to the above OS code, ESP is still pointing to {\bf u}'s
stack, so the three PUSH instructions save {\bf u}'s values of the ESI,
EDI and EBP registers on {\bf u}'s own stack.\footnote{ Note the need to
write this in assembly language instead of C, since C would not give us
direct access to the registers or the stack. Most of Linux is written in
C, but machine-dependent operations like the one here must be done in
assembly language.  } The other register values of {\bf u} must be saved
too, including its value of ESP.  The latter is done by the MOV, which
copies the current ESP value, i.e. {\bf u}'s ESP value, to {\bf tss.esp}
in {\bf u}'s TSS. Other register saving is similar, though not shown
here.

Now the OS must prepare to start {\bf v}'s next turn. Thus {\bf v}'s
previously-saved register values must be restored to the registers. To
understand how that is done, you must keep in mind that that same code
we see above had been executed when {\bf v}'s last turn ended. Thus {\bf
v}'s value of ESP is in {\bf tss.esp} of its TSS, and the second MOV we
see above copies that value to ESP. So, now we are using {\bf v}'s
stack.

Next, note similarly that at the end of {\bf v}'s last turn, its values
of ESI, EDI and EBP were pushed onto its stack, and of course they are
still there. So, we just pop them off, and back into the registers,
which is what those three POP instructions do.

Finally, what actually get's {\bf v}'s new turn running?  To answer
this, note that the mechanism which made {\bf v}'s last turn end was a
hardware interrupt from the timer. At that time, the values of the Flags
Register, CS and PC were pushed onto the stack. Now, the IRET
instruction you see here pops all that stuff back into the corresponding
registers.  Note only does that restore registers, but since {\bf v}'s
old PC value is restored to the PC register, {\bf v} is now running!

\checkpoint

\subsection{Process States}

The OS maintains a \textbf{process table} which shows the state of each
process in memory, mainly Run state versus Sleep state. A process which
is in Run state means that it is ready to run but simply waiting for its
next turn. The OS will repeatedly cycle through the process table,
starting turns for processes which are in Run state but skipping over
those in Sleep state. The processes in Sleep state are waiting for
something, typically an I/O operation, and thus currently ineligible for
turns. So, each time a turn ends, the OS will browse through its process
table, looking for a process in Run state, and then choosing one for its
next turn.

Say our application program {\bf u} above contains a call to {\bf scanf()} to
read from the keyboard. Recall that {\bf scanf()} calls the OS function
{\bf read()}. The latter is in the OS, so now the OS is running, and
this function will check to see whether there are any characters
ready in the keyboard buffer.  Typically there won't be any characters
there yet, because the user has not started typing yet. In this case the
OS will place this process in Sleep state, and then start a turn for
another process.

How does a process get switched to Run state from Sleep state? Say our
application program {\bf u} was in Sleep state because it was waiting
for user input from the keyboard, waiting for just a single character,
in {\bf raw} mode.\footnote{Recall from Chapter \ref{chap:io} that in
this mode, a character is made available to a program as input the
minute the user strikes the key.  In ordinary, {\bf cooked}, mode, the
program doesn't see the input until the user hits the Enter key.} 

As explained earlier, when the user hits a key, that causes
a hardware interrupt from the keyboard, which forces a jump to the OS.
Suppose at that time program {\bf v}  happened to be in the midst of a
quantum. The CPU would temporarily suspend {\bf v}  and jump to the
keyboard driver in the OS. The latter would notice that the program {\bf
u} had been in Sleep state, waiting for keyboard input, and would now
move {\bf u} to Run state.

Note, though, that that does not mean that the OS now starts {\bf u}'s
next turn; {\bf u} simply becomes eligible to run. Recall that each time
one process' turn ends, the OS will select another process to run, from
the set of all processes currently in Run state, and {\bf u} will now be
in that set.  Eventually it will get a turn. 

\checkpoint

To make all this concrete, say {\bf u} is running the {\bf vi} text
editor, {\bf v} is running a long computational program, and user
{\bf w} is also running some long computational program.  Remember,
{\bf vi} \underline{is} a program; its source code might have a section
like this:

\begin{Verbatim}[fontsize=\relsize{-2}]
while (1)  {
   KeyStroke = getch();
   if (KeyStroke == 'x') DeleteChar();
   else if (KeyStroke = 'j') CursorDown();
   else if ...
}
\end{Verbatim}

Here you see how {\bf vi} would read in a command from the user, such as
{\bf x} (delete a character), {\bf j} (move the cursor down one line)
and so on.  Of course, {\bf DeleteChar()} etc. are functions, whose code is
not shown here.

When during a turn for {\bf u}, {\bf vi} hits the {\bf getch()} line,
the latter calls {\bf read()}, which is in the OS, so now the OS is
running.  Assuming {\bf u} has not hit a key yet (almost certainly the
case, since the CPU is a lot faster than {\bf u}'s hand, not to mention
the fact that {\bf u} might have gone for a lunch break), the OS will
mark {\bf u}'s process as being in Sleep state in the OS's Process Table.

Then the OS will look for a process in Run state to give the next turn
to.  This might be, say, {\bf v}.  It will run until the timer interrupt
comes.  That pulse of current will cause the CPU to jump to the OS, so
the OS is running again.  This time, say, {\bf w} will be run.

Say during {\bf w}'s turn, {\bf u} finally hits a key.  The resulting
interrupt from the keyboard again forces the CPU to jump to the OS.  The
OS read the character that {\bf u} typed, notices in its Process Table
that {\bf u}'s process was in Sleep state pending keyboard input, and
thus changes {\bf u}'s entry in the Process Table to Run state.  The OS
then does IRET, which makes {\bf w}'s process resume execution, but when
the next timer interrupt comes, the OS will likely give {\bf u} a turn
again.

\subsection{What About Background Jobs?}

For example, you could run the Firefox Web browser by typing

\begin{Verbatim}[fontsize=\relsize{-2}]
% firefox 
\end{Verbatim}

at the command line.  But that would tie up the window you typed it
into; you wouldn't be able to run any other commands until you quit
Firefox, which might be a very long time.  To solve this problem, you
can run it {\it in the background}, as follows.

You could type

\begin{Verbatim}[fontsize=\relsize{-2}]
% firefox &
\end{Verbatim}

with the ampersand meaning, ``Run this job in the background.''  The
shell would start Firefox, and then print out a prompt, inviting you to
run other commands.  What is really happening here?

The first point to be made here is that it really means nothing to the
OS.  The entry for the Firefox process in the OS' process table
will not state whether this program is background or foreground; the OS
doesn't know.

The only meaning of that ampersand was for the shell.  We used it to
tell the shell, ``Go ahead and launch {\bf a.out} for me, but don't wait
for it to finish before giving me your `\%' prompt again.  Give me the
prompt right away, because I want to run some other programs
too.''\footnote{To do this, the shell must first create a new process,
by calling the {\bf fork()} system call, and then calling {\bf execve()}
from the child process.  That way, the parent process---the shell--can
keep running and give you the prompt.}

\subsection{Threads:  ``Lightweight Processes''}

A very important type of application programming is that of {\bf
threads}.  Thread libraries are offered by any modern OS.  On
Unix-family systems, for instance, a popular thread package is {\bf
pthreads}, which we will assume for concreteness here.  

Threading is pervasive in computing today.  Most Web servers are
threaded, for instance.  Also many GUI (``graphical user interface'')
programs are threaded too.  

Threading is also the standard way of programming on multiprocessor
systems.  Since such systems are now common even at the household
level---the term {\bf dual core} means two CPUs---you can see how
important threaded programming has become.

\subsubsection{The Mechanics}

Threads, of the ``system'' type discussed here, are
processes.\footnote{What we are describing here are {\bf system-level}
threads, i.e. those provided by the OS, which is the case for {\bf
pthreads}.  There are also {\bf user-level} threads.  These, exemplified
by the GNU {\bf pth} library, are handled internally to the application
program.  Basically, the library runs its own private processes, with
its own private process table!} If your program creates three threads on
a Unix-family system such as Linux, for example, you may (depending on
the OS)  see three entries for them in the output of the {\bf ps}
command which displays processes.  (For Linux, type {\bf ps axH}).
These will correspond to three entries in the process table.  Thus the
threads take turns running, in the usual timesharing manner.  The turn
taking includes the other processes too, of course.  

From the programmer's point of view, the main difference between threads
and processes is that in threaded programs all global variables of the
program are shared.\footnote{It is actually possible to have different
processes share memory too, using the system call {\bf shmget()}.
However, this is unwieldy and involves a lot of system overhead, and is
not commonly done.}  This is the way the different threads communicate
with each other, by reading and writing these shared variables.

This may come as a shock to readers who were taught that shared
variables are ``evil.''  In my opinion, shared variables are fine for
general programming (within reason), but whether one agrees with that
notion or not, {\bf the fact is that in threaded programming one
\underline{must} use global variables.}

Each thread does have its own local variables, though.  So, the various
threads of a program will share the same {\bf .data} and {\bf \.comm}
sections, but each will have its own separate stack.

One creates a thread by calling {\bf pthread\_create()}.  One of its
arguments must be a pointer to a function in the application program.
For instance, in a GUI program, we might have one thread for the mouse,
one thread for the keyboard, etc.  The function which handles mouse
events (movement and clicks) would be specified as an argument to {\bf
pthread\_create()}, and basically the thread would consist of executing
that function.  There would also be a function for the keyboard, etc.

Key to threaded programming is {\bf locks}.  Suppose for instance that
an airline reservation system is threaded, and that there is one seat
left for a particular flight.  We want to make sure to avoid a situation
in which two clerks both sell that last seat.  (Ignore the issue of
overbooking.)  So, the two threads running for the two clerks must
cooperate, and not try to access that flight's record at the same time.
In other words, we want access to that record to be {\bf atomic}.  Lock
variables, of type {\bf pthread\_mutex\_t}, are locked and unlocked via
calls to {\bf pthread\_mutex\_lock()} and {\bf
pthread\_mutex\_unlock()}, take care of this for us.

Threads are often called {\bf lightweight processes}.  The term {\it
lightweight} here refers to the fact that creating a thread involves
much less overhead than creating a process.  In {\bf pthreads}, for
instance, calling {\bf pthread\_create()} has a lot less work to do than
would be involved in calling {\bf execve()} to make a new process.
Among other things, the latter requires finding memory for the new
process, whereas a new thread would simply use the same memory.

\subsubsection{Threads Example}

Examples of threaded programming tend to be rather elaborate, so I've
written the following simple (if a bit contrived) example:

\begin{Verbatim}[fontsize=\relsize{-2},numbers=left]
// HelloWorld.c, a baby-level first example of threaded programming.

// Doesn't actually print out "hello world." :-)  But it's of that level
// of simplicity, so I gave it that name anyway.

// The program reads from each of several keyboard input sources.  To
// avoid having to introduce network programming, we will have these
// sources be from several windows on the same console on the same
// machine.  

// The issue here is that we don't know which keyboard input will have
// some activity next.  If we simply call scanf() in nonthreaded fashion
// (and don't resort to something called nonblocking I/O), our program
// would wait forever for input from one nonactive window when there is
// input waiting at another window.  The solution is to use threads,
// with one thread for each window.

// Each source of keyboard input is considered a different file.  (In
// Unix, I/O devices are considered "files.")  We determine the file
// name by running the "who am i" command in the given window.  If for
// instance the answer is pts/6, the keyboard input there is /dev/pts/6.

// Each time there is keyboard input from somewhere, the program will
// report what number was typed.

// For simplicity, the program has no mechanism for stopping.

// Linux compilation:  gcc -g -o hw HelloWorld.c -lpthread 

// usage:  hw first_keybd_input_filename second_keybd_input_filename ...
// e.g. hw /dev/pts/4 /dev/pts/6

#define MAX_THREADS 20

#include <stdio.h>
#include <pthread.h>  // required for threads usage

int nthreads;  // number of threads to be run

// lock, needed so that the printf() in one thread does not rudely  
// interrupt the printf() in another when a context switch occurs
pthread_mutex_t numlock = PTHREAD_MUTEX_INITIALIZER;
// ID structs for the threads
pthread_t id[MAX_THREADS];

// each thread runs this routine
void *worker(char *fname)  // fname is file name
{  FILE *kb;  // note separate stacks, so separate kb's
   int num;  // separate num's too
   kb = fopen(fname,"r");  // open this keyboard input, read only
   while(1)  {
      fscanf(kb,"%d",&num);  // wait for user to type in this window
      pthread_mutex_lock(&numlock);
      printf("read %d from %s\n",num,fname);
      pthread_mutex_unlock(&numlock);
   } 
}

main(int argc, char **argv)
{  int i; 
   nthreads = argc - 1;
   // get threads started
   for (i = 0; i < nthreads; i++)  {
      // this next call says to create a thread, record its ID in the array
      // id, and get the thread started executing the function worker(), 
      // passing the argument argv[i+1] to that function
      pthread_create(&id[i],NULL,worker,argv[i+1]);
   }
   while(1) ;  // dummy loop, to keep main() from exiting, killing
               // the other threads
}
\end{Verbatim}

The program reads keyboard input from two different windows on the same
console on the same machine.  This is the contrived part.  A typical
example would have input coming from keyboards on other machines, with
the characters being sent across a network.  But I wanted to avoid
bringing in network programming.

As you can see, {\bf main()} starts up the threads.  Once they are
started, they take turns running, like processes.  Note that {\bf
main()} is considered a thread too, the parent of those created by it.

I ran the program on the windows {\bf /dev/pts/4} and {\bf /dev/pts/6}
on my Linux machine at home.\footnote{As the comments in the code
indicate, I determined their device names by running the {\bf who am i}
command in each window.}  In each window I typed

\begin{Verbatim}[fontsize=\relsize{-2}]
% sleep 10000
\end{Verbatim}

to put the shell to sleep, ensuring that the input I type in those
windows would go to my program rather than to the shells.

In a third window, I ran the program.  In window 6 I then typed 5 and
12, and then 13 in window 5, then 168 in window 6 again.  The output in
the third window was

\begin{Verbatim}[fontsize=\relsize{-2}]
% a.out /dev/pts/4 /dev/pts/6
read 5 from /dev/pts/6
read 12 from /dev/pts/6
read 13 from /dev/pts/4
read 168 from /dev/pts/6
\end{Verbatim}

{\bf REMINDER TO THE READER:}  Don't worry so much about how to do 
{\bf pthreads} programming; focus on the concepts relevant to our
course.  Think especially of the role of interrupts here.  Threads take
turns running, with a turn ending either from a timer interrupt or from
a thread voluntarily relinquishing its turn via a system call, in this
case {\bf read()} being called by {\bf fscanf()}.  In the latter
situation, an interrupt from the keyboard will change a thread from
Sleep to Run state. 

\subsection{Making These Concepts Concrete: Commands You Can Try Yourself}

First, try the \textbf{ps} command. On Unix systems, much information on current
processes is given by the \textbf{ps} command, including:

\begin{itemize}

\item state (Run, Sleep, etc.) 

\item page usage (how many pages, number of page faults, etc.; see
material on virtual memory below) 

\item ancestry (which process is the {}``parent{}'' of the given
process, via a call to {\bf execve()}) 

\end{itemize}

\textbf{The reader is urged to try this out. You will understand the
concepts presented here much better after seeing some concrete
information which the {\bf ps} command can give you.} The format of this
command's options varies somewhat from machine to machine (on Linux, I
recommend {\bf ps axms}), so check the {\bf man} page for details, but run
it with enough options that you get the fullest output possible.

Another command to try is \textbf{w.} One of the pieces of information given
by the \textbf{w} command is the average number of processes in Run state in
the last few minutes. The larger this number is, the slower will be the response
time of the machine as perceived by a user, as his program is now taking turns
together with more programs run by other people.

On Linux (and some other Unix) systems, you can also try the \textbf{pstree}
command, which graphically shows the {}``family tree{}'' (ancestry relations)
of each process. For example, here is the output I got by running it on one
of our CSIF PCs:

\begin{Verbatim}[fontsize=\relsize{-2}]
% pstree
init-+-atd
     |-crond
     |-gpm
     |-inetd---in.rlogind---tcsh---pstree
     |-kdm-+-X
     |     `-kdm---wmaker-+-gnome-terminal-+-gnome-pty-helpe
     |                    |                `-tcsh-+-netscape-commun---netscape-+
     |                    |                       `-vi
     |                    |-2*[gnome-terminal-+-gnome-pty-helpe]
     |                    |                   `-tcsh]
     |                    |-gnome-terminal-+-gnome-pty-helpe
     |                    |                `-tcsh---vi
     |                    `-wmclock
     |-kerneld
     |-kflushd
     |-klogd
     |-kswapd
     |-lpd
     |-6*[mingetty]
     |-2*[netscape-commun---netscape-commun]
     |-4*[nfsiod]
     |-portmap
     |-rpc.rusersd
     |-rwhod
     |-sendmail
     |-sshd
     |-syslogd
     |-update
     |-xconsole
     |-xntpd
     `-ypbind---ypbind
%
\end{Verbatim}

On Unix systems, the first thing the OS does after bootup is to start a
process named \textbf{init}, which will be the parent (or grandparent,
great-grandparent, etc.) of all processes.  That {\bf init} process then
starts several OS {\bf daemons}.  A {\bf daemon} in Unix parlance means
a kind of server program.  In Unix, the custom is to name such programs
with a `d' at the end, standing for ``daemon.''

For example, you can see above that {\bf init} started {\bf lpd} (``line
printer daemon''), which is the print server.\footnote{Another common
print server daemon is {\bf cupsd}.} When users issue {\bf lpr} and
other print commands, the OS refers them to {\bf lpd}, which arranges
for the actual printing to be done.

Often daemons spawn further processes.  For example, look at the line

\begin{Verbatim}[fontsize=\relsize{-2}]
     |-inetd---in.rlogind---tcsh---pstree
\end{Verbatim}

The {\bf inetd} is an Internet request server.  The system administrator
can optionally run this daemon in lieu of some other network daemons
which are assumed to run only rarely.  Here the user (me) had done {\bf
rlogin}, a login program like {\bf ssh}\footnote{But no longer allowed
on CSIF.}, to remotely login to this machine.  The system administrators
had guessed that {\bf rlogin} would be used only rarely, so they did not
have {\bf init} start the corresponding daemon, {\bf in.rlogind}, upon
bootup.  Instead, any network daemon not started at bootup will be
launched by {\bf inetd} when the need arises, which as you can see
occurred here for {\bf in.rlogind}.  The latter then started a shell for
the user who logged in (me), who then ran {\bf pstree}.  Note again that
the shell is the entity which got {\bf pstree} started.

\section{Virtual Memory}

\subsection{\label{goals}Make Sure You Understand the Goals}

Now let us add in the effect of virtual memory (VM). VM has the
following basic
goals, which are so important to understand that I am describing in 
separate short sub-subsections:

\subsubsection{Overcome Limitations on Memory Size}

We want to be able to run a program, or collectively several programs,
whose memory needs are larger than the amount of physical memory
available.

\subsubsection{Relieve the Compiler and Linker of Having to Deal with
Real Addresses}

We want to facilitate \textbf{relocation} of programs, meaning that the
compiler and linker do not have to worry about where in memory a
program will be loaded when it is run. 

\subsubsection{Enable Security}

We want to ensure that one program will not accidentally (or
intentionally) harm another program's operation by writing to the
latter's area of memory, read or write to another program's I/O streams,
etc.

\subsection{The Virtual Nature of Addresses}

The word \textit{virtual} means {}``apparent.{}'' It will
\underbar{appear} that a program resides entirely in main memory, when
in fact only part of it is there.  It will \underbar{appear} that your
program variables are stored at the places the linker assigned to
them,\footnote{You can determine these by running {\bf readelf} on your
executable file, with the {\bf -s} option.} when in fact they actually
will be stored somewhere else.

(For the time being, it will be easier to understand VM by assuming
there is no cache.  We will return to this in Section \ref{cacherole}.)

To make this more concrete, suppose our C source file 
includes the following statements:

\begin{Verbatim}[fontsize=\relsize{-2}]
int x;
...
x = 8;
printf("%d",&x);
\end{Verbatim}

Recall that addresses of variables are set in the following manner.  Say
{\bf x} is global.  Then the compiler will generate a {\bf .comm} line
in assembly language it produces.\footnote{If {\bf x} had been declared
in initialzed form, e.g. {\bf int x = 28;} then it would have been in a
{\bf .data} section.} The latter will be translated by the assembler,
and then the linker will deal with the machine code.  Among other
things, the linker will assign an address for {\bf x}.  It will be this
address which is printed out above.

If {\bf x} had been local, it would be stored on the stack, but that is
still memory of course, and thus it would have an address too.  Again,
that would be printed out.  

In any case, either of these addresses would be fake.  Let's see what
this really means.  Suppose that {\bf x} is global, and that the
compiler and linker assign it address 200, i.e. {\bf \&x} is 200.  Then
the above code 

\begin{Verbatim}[fontsize=\relsize{-2}]
x = 8;
\end{Verbatim}

would correspond to an instruction in {\bf a.out} something like

\begin{Verbatim}[fontsize=\relsize{-2}]
movl $8, 200
\end{Verbatim}

At the time \textbf{a.out} is loaded by the OS into memory, the OS will
divide both the {\bf .text} (instructions) and data portions of \textbf{a.out}
({\bf .data}, {\bf .bss}, stack, heap, etc.) into chunks, and find
unused places in memory at which to place these chunks. The chunks are
called \textbf{pages} of the program, and the same-sized places in
memory in which the OS puts them are called pages of memory.\footnote{As
with the stack, etc., keep in mind that these pages are only conceptual;
there is no ``fence'' or any other physical demarcation between one page
in memory and the next.  A page is simply a unit of measurement, like
acres and liters.} The OS sets up a \textbf{page table} for this
process, which is an array which is maintained by the OS, in which the
OS records the correspondences, i.e. lists which page of the process is
stored in which page of memory.  Remember, the OS is a program, and the
page table is an array in that program, and thus it too is in memory.

What appears to be in word 200 in memory from the program code above may
actually be in, say, word 1204. At the time the CPU executes that instruction,
the CPU will determine where `Word 200'' really is by doing a lookup
in the page table. In our example here, the table will show that the item we
want is actually in word 1204, and the CPU will then write to that location.
The hardware would put 1204 on the address bus, 8 on the data bus, and
would assert the Memory Write line in the control bus.

\checkpoint

In this example, we say the \textbf{virtual address} is 200, and the
\textbf{physical address} is 1204.

Note that while virtual addressing is enabled (it is turned off in
Kernel Mode), all addresses seen by the hardware will be virtual.  For
example, the contents of ESP will be a virtual address, with the real
top-of-stack address being something else, not what ESP says.  A similar
statement holds for the PC, etc.

\subsection{Overview of How the Goals Are Achieved}

Let's look at our stated goals in Section \ref{goals} above, and take a
first glance at how they are achieved (details will be covered later):

\subsubsection{Overcoming Limitations on Memory Size}

To conserve memory space, the OS will initially load only part of
\textbf{a.out} into memory, with the remainder being left back on disk.
The pages of the program which are not loaded will be marked in the page
table as currently being {\bf nonresident}, meaning not in memory, and
their locations on disk will be shown in the table. During execution of
the program, if the program needs one of the nonresident pages, the CPU
will notice that the requested page is nonresident.  This is called a
{\bf page fault}, and it causes an internal interrupt.  The interrupt
number is 0xe, i.e. entry 0xe in the IDT.  That causes a jump to the OS,
which will bring in that page from disk, and then jump back to the
program, which will resume at the instruction which accessed the missing
page.  

Note that pages will often go back and forth between disk and memory in this
manner. Each time the program needs a missing page, that page is brought in
from disk and a page which had been resident is written back to disk in order
to make room for the new one.   Note also that a given virtual page
might be in different physical pages at different times.

A big issue is the algorithm the OS uses to decide which page to move
back to disk (i.e. which page to replace) whenever it brings a page from
disk after a page fault.  Due to the huge difference in CPU and disk
speeds, a page fault is a catastrophic even in terms of program speed.
We hope to have as few page faults as possible when our program runs.

So, we want to check the pages to evict very carefully.  If we often
evict a page which is needed again very soon, our program's performance
will really suffer.  This is called {\bf thrashing}.  Details of page
replacement policies are beyond the scope of this document here, but one
point to notice is that the policy will be chosen so as to work well on
``most'' programs.  For any given policy, it will do well on some
programs (i.e. produce few page faults) while doing poorly on some other
programs (produce many page faults).  

So, what they try to do is come up with a policy which works reasonably
well on a reasonably broad variety of programs.  Most policies are some
variation on the Least Recently Used policy common for associative
caches.

\subsubsection{Relieving the Compiler and Linker of Having to Deal with
Real Addresses}

This is clear from the example above, where the location {}``200{}''
which the compiler and linker set up for {\bf x} was in effect changed by the
OS to 1204 at the time the program was loaded. The OS recorded this in
the page table, and then during execution of the program, the VM
hardware in the CPU does lookups in the page table to get the correct
addresses.  The point is that the compiler and linker can assign {\bf x} 
to location 200 without having to worry whether location is actually
available at the time the program will be run, because that variable
actually {\bf won't} be at 200.

\subsubsection{Enabling Security}

The page table will consist of one entry per page. That entry will, as
noted earlier, include information as to where in memory that page of
the program currently resides, of if currently nonresident, where on
disk the page is stored.  But in addition, the entry will also list the
permissions the program has to access this particular page---read,
write, execute---in a manner analogous to file-access permissions.  If .
an {\bf access violation} occurs, the VM hardware in the CPU will cause
an internal interrupt (again it's interrupt number 0xe, as for page
faults), causing the OS to run.  The OS will then kill the process, i.e.
remove it from the process table. 

Normally data-related sections such as {\bf .data} and the stack will be
the only ones with write permission.  However, you can also arrange for
the {\bf .text} section to be writable, via the {\bf -N} option to {\bf
ld}.

You might wonder why execute permission is included.  One situation in
which this would be a useful check is that in which we have a pointer to
a function.  If for example we forgot to initialize the pointer, a
violation will be detected.

Suppose for instance your program tries to read from virtual page number
40000 but that virtual address is out of the ranges of addresses which
the program is allocated.  The hardware will check the entry for 40000
in the page table, and find that not only is that page not resident, but
also it isn't on disk either.  Instead, the entry will say that there is
no virtual page 40000 among the pages allocated to this program.

We don't want an ordinary user programs to be able to, say maliciously, 
access the I/O streams of other programs.  To accomplish this, we want
to forbid a user program from accessing the I/O buffer space of another
program, which is easy to to accomplish since that space is in memory;
we simply have the OS set up the page table for that program
accordingly.  But we also need to forbid a user program from directly
performing I/O, e.g. the INB and OUTB instructions on Intel machines.

This latter goal is achieved by exploiting the fact that most modern
CPUs run in two or more \textbf{privilege levels}.  The CPU is designed
so that certain instructions, for example those which perform I/O such
as INB and OUTB, can be executed only at higher privilege levels, say
Kernel Mode. (The term \textbf{kernel} refers to the OS.)

But wait!  Since the OS is a program too, how does {\it it} get into
Kernel Mode?  Obviously there can't be some instruction to do this;
if there were, then ordinary user programs could use it to put
themselves into Kernel Mode.  So, how is it done?

When the machine boots up, it starts out in Kernel Mode.  Thus the OS
starts out in Kernel Mode.  Among other things, the interrupts can be
configured to change the privileges level of the CPU.  Recall that the
OS starts a turn for a user program (including that program's first
turn) by executing an IRET instruction, a software interrupt.  So, the
OS can arrange both for user programs to run in non-Kernel Mode and for
Kernel Mode to be restored when an interrupt comes during a user program
is running.  So for example, an interrupt from the timer will not only
end a user program's turn, but also will place the CPU in Kernel Mode,
thus having the OS run in that mode. 

\subsubsection{Is the Hardware Support Needed?}

It is instructive to think about the role of the VM hardware in
achieving the three goals above---being able to run larger programs than
our RAM size; being able to shift memory addresses of programs; enabling
security.  In the first two cases, we could accomplish our goal without
the hardware, even though it would be inconvenient; but in the third
case, the hardware is really necesary.

In the pre-VM days, programmers used {\bf overlays}.  A program might
need a very large array, but not have enough RAM.  If so, the programmer
could insert code to move portions of the array in from disk when they
were needed, and write them back to disk when they are no longer needed.
Of course, this was a nuisance for the programmer, but anyway the goal
could be accomplished.

Similarly, an executable file could be rewritten just before loading it
into memory for execution, so that it could be stored at a different
address than originally planned.  Depending on the archicture of the
machine, there may be some register who usage in effect shifted
everything to another place in memory.

But for the security goal, there really isn't anything we can do.  We
need something to check every memory access, and unless we run
interpreted code, the hardware is needed.

\subsection{Who Does What When?}

Note carefully the roles of the players here: It is the software, the
OS, that creates and maintains the page table, but it is the hardware
that actually uses the page table to generate physical addresses, check
page residency and check security.  In the event of a page fault or
security violation, the hardware will cause a jump to the OS, which
actually responds to those events.

The OS writes to the page table (including creating it in the first
place), and the hardware reads it.

\checkpoint

The hardware will have a special Page Table Register (PTR) to point to
the page table of the current process. When the OS starts a turn for a
process, it will restore the previously-saved value of the PTR, and thus
this process' page table will now be in effect.

On the Pentium, the name of the PTR is CR3.  (Actually, the Pentium uses
a two-level hierarchy for its page tables, but we will not pursue that
point here.)  

\subsection{Details on Usage of the Page Table}

\subsubsection{\label{trans}Virtual-to-Physical Address Translation,
Page Table Lookup}

Whenever the running program generates an address---either the address
of an instruction, as will be the case for an instruction fetch, or the
address of data, as will be the case during the execution of instructions
which have memory operands---this address is only virtual. It must be
translated to the physical address at which the requested item actually
resides.  The circuitry in the CPU is designed to do this translation by
performing a lookup in the page table.

For convenience, say the page size is 4096 bytes, which is the case for
Pentium CPUs.  (The treatment here is somewhat simplified, though.)
Both the virtual and physical address spaces are broken
into pages.  For example, consider virtual address 8195.  Since 

\begin{equation}
\label{ex8195}
8195 = 2 \times 4096 + 3
\end{equation}

that address would be in virtual page 2 (the first page is page 0).  We
can then speak of how far into a page a given address is.  Here, because
of the remainder 3 in Equation (\ref{ex8195}), we see that virtual
address 8195 is byte 3 in virtual page 2.  We refer to the 3 as the 
{\bf offset} within the page, i.e. its distance from the beginning of
the page.  

You can see that for any virtual address, the virtual page number is
equal to the address divided by the page size, 4096, and its offset
within that page is the address mod 4096.  Using our knowledge of the
properties of powers of 2 and the fact that $4096 = 2^{12}$, this means
that for a 32-bit address (which we'll assume throughout), the upper 20
bits contain the page number and the lower 12 bits contain the offset.

The page/offset description of the position of a byte is quite analogous
to a feet/inches description of distance.  We could measure everything
in inches, but we choose to use a larger unit, the foot, to give a rough
idea of the distance, and then use inches to describe the remainder.
The concept of offset will be very important in what follows.

Now, to see how the page table is used to convert virtual addresses to
physical ones,  consider for example the Intel instruction

\begin{Verbatim}[fontsize=\relsize{-2}]
movl $6, 8195
\end{Verbatim}

This would copy the constant 6 to location 8195.  Remember, this is page
2, offset 3.  However, it is a virtual address.  The hardware would see
the 8195,\footnote{Remember, it will be embedded within the instruction
itself, as this is direct addressing mode.}  The hardware knows that any
address given to it is a virtual one, which must be converted to a
physical one.  So, the hardware would look at the entry for virtual page
2, and find what physical page that is; suppose it is 5.  Then that page
starts at physical memory location $5 \times 4096 = 20480$.  

What about the offset within that physical page 5?  The custom is that an
item will have the same offset, no matter whether we are talking about
its virtual address or its physical one.  So, the offset of our
destination in physical page 5 would be 3.  In other words, the
physical address is

\begin{equation}
5 \times 4096 + 3 = 20483
\end{equation}

The CPU would now be ready to execute the instruction, which, to refresh
your memory, was

\begin{Verbatim}[fontsize=\relsize{-2}]
movl $6, 8195
\end{Verbatim}

The CPU knows that the real location of the destination is 20483, not
8195.  It would put 20483 on the address bus, put 6 on the data bus, and
assert the Memory Write line in the control bus, and the instruction
would be done. 

\checkpoint

\subsubsection{Layout of the Page Table}

Suppose the entries in our page table are 32 bits wide, i.e. one word
per entry.\footnote{If we were to look at the source code for the OS, we
would probably see that the page table is stored as a very long array of
type \textbf{unsigned int}, with each array element being one page table
entry.  } Let's label the bits of an entry 31 to 0, where Bit 31 is in
the most-significant (i.e. leftmost) position and Bit 0 is in the least
significant (i.e. rightmost) place. Suppose the format of an entry is as
follows:

\begin{itemize}
\item Bits 31-12: physical page number if resident, disk location if not 
\item Bit 11: 1 if page is resident, 0 if not 
\item Bit 10: 1 if have read permission, 0 if not 
\item Bit 9: 1 if have write permission, 0 if not 
\item Bit 8: 1 if have execute permission, 0 if not 
\item Bit 7: 1 if page is ``dirty,'' 0 if not (see below)
\item Bits 6-0: other information, not discussed here 
\end{itemize}

Now, here is what will happen when the CPU executes the instruction

\begin{Verbatim}[fontsize=\relsize{-2}]
movl $6, 8195
\end{Verbatim}

above:

\begin{itemize}

\item The CPU does the computation $\times 4096 + 3 = 20483$ and finds
that virtual addrss 8195 is virtual page number 2, offset 3.

\item Since we are dealing with virtual page 2, the CPU will go to get
the entry for that virtual page in the page table, as follows. Suppose
the contents of the PTR is 5000.  Then since each entry is 4 bytes long,
the table entry of interest here, i.e. the entry for virtual page 2, is
at location 

\begin{equation}
5000 + 4 \times 2 = 5008
\end{equation}

The CPU will read the desired entry from that location, getting, say,
0x000005e0. 

\item The CPU looks at Bits 11-8 of that entry, getting 0xe, finding
that the page is resident (Bit 11 is 1) and that the program has read
and write permission (Bits 10 and 9 are 1) but no execute permission
(Bit 8 is 0). The permission requested was write, so this is OK. 

\item The CPU looks at Bits 31-12, getting 5, so the hardware would know
that virtual page 2 is actually physical page 5.
The virtual offset,
which we found earlier to be 3, is always retained, so the CPU now
knows that the physical address of the virtual location 8195 is

\begin{equation}
5 \times 4096 + 3 = 20483
\end{equation}

\item  The CPU puts the latter on the address bus, puts 6 on the data
bus, and asserts the Write line in the bus. This writes 6 to memory
location 20483, and we are done. 

\checkpoint

\end{itemize}

By the way, all this was for Step C of the above MOV instruction.  The
same actions would take place in Step A.  The value in the PC would be
broken down into a virtual page number and an offset; the virtual page
number would be used as an index into the page table; Bits 10 and 8 in
the page table element would be checked to see whether we have
permission to read and execute that instruction; assuming the
permissions are all right, the physical page number would be obtained
from Bits 31-12 of the page table element; the physical page number
would be combined with the offset to form the physical address; and the
physical address would be placed in the MAR and the instruction fetched.

Recall from above that the upper 20 bits of an address form the page
number, and the lower 12 bits form the offset.  A similar statement
holds for physical addresses and physical page numbers.  So, all the
hardware need do is:  use the upper 20 bits of the virtual address as an
index in the page table (i.e. multiply this by 4 and add to c(PTR); take
bits 31-12 of from the table entry reached in this manner, to get the
physical page number; and finally, concatenate this physical page number
with the lower 12 bits of the original virtual address.  Then the
hardware has the physical address, which it places on the address bus. 

\subsubsection{Page Faults}

Suppose in our example above Bit 11 of the page table entry had been 0,
indicating that the requested page was not in memory.  As mentioned
earlier, this event is known as a \textbf{page fault}. If that occurs,
the CPU will perform an internal interrupt, and will also record the PC
value of the instruction which caused the page fault, so that that
instruction can be restarted after the page fault is processed.  In
Pentium CPUs, the CR2 register is used to store this PC value.  This
will force a jump to the OS. 

The OS will first decide which currently-resident page to replace, then
will write that page back to disk, if the Dirty Bit is set (see below).
The OS will then bring in the requested page from disk.  The OS would
then update two entries in the page table: (a) it would change the entry
for the page which was replaced, changing Bit 11 to 0 to indicate the
page is not resident, and changing Bits 31-12 and possible Bit 7; and
(b) the OS would update the page table entry of the new item's page, to
indicate that the new item is resident now in memory (setting Bit 11 to
1), show where it resides (by filling in Bits 31-12), and setting Bit 7
to 0.

The role of the Dirty Bit is as follows:  When a page is brought into
memory from disk, this bit will be set to 0.  Subsequently, if the page
is written to, the bit will be changed to 1.  So, when it comes time to
evict the page from memory, the Dirty Bit will tell us whether there is
any discrepancy between the contents of this page in memory and its copy
on disk.  If there is a difference, the OS must write the new contents
back to disk.  That means all 4096 bytes of the page.  We must
write back the whole page, because we don't know what bytes in the page
have changed.  The Dirty Bit only tells us that there has been some
change(s), not where the change(s) are.  So, if the Dirty Bit is 0, we
avoid a time-consuming disk write.

\checkpoint

Since accessing the disk is far, far slower than accessing memory, a program
will run quite slowly if it has too many page faults. If for example your PC
at home does not have enough memory, you will find that you often have to wait
while a large application program is loading, during which time you can hear
the disk drive doing a lot of work, as the OS ejects many currently-resident
pages to bring in the new application.


\subsubsection{Access Violations}

If on the other hand an access violation occurs, the OS will announce an
error---in Unix, referred to as a \textbf{segmentation fault}---and
kill the process, i.e. remove it from the process table.

For example, considering the following code:

\begin{Verbatim}[fontsize=\relsize{-2},numbers=left]
int q[200];

main()

{  int i;

   for (i = 0; i < 2000; i++) {
      q[i] = i;
   }

}
\end{Verbatim}

Notice that the programmer has apparently made an error in the loop, setting
up 2000 iterations instead of 200. The C compiler will not catch this at compile
time, nor will the machine code generated by the compiler check that the array
index is out of bounds at execution time.

If this program is run on a non-VM platform,\footnote{ Recall that
{}``VM platform{}'' requires both that our CPU has VM capability, and
that our OS uses this capability.  } then it will merrily execute
without any apparent error. It will simply write to the 1800 words which
follow the end of the array {\bf q}. This may or may not be harmful,
depending on what those words had been used for.

But on a VM platform, in our case Unix, an error will indeed be
reported, with a {}``Segmentation fault{}'' message.\footnote{On
Microsoft Windows systems, it's called a ``general protection error.''}
However, as we look into how this comes about, the timing of the error
may surprise you. The error is not likely to occur when {\bf i} = 200;
it is likely to be much later than that.

To illustrate this, I ran this program under {\bf gdb} so that I could
take a look at the address of {\bf q[199]}.\footnote{Or I could have
added a {\bf printf()} statement to get such information.  Note by the
way that either running under {\bf gdb} or adding {\bf printf()}
statement will change the load locations of the program, and thus
affect the results.}  After running this program, I found that the seg
fault occurred not at {\bf i} = 200, but actually at {\bf i} = 728.
Let's see why.

From queries to {\bf gdb} I found that the array {\bf q} ended at
0x080497bf, i.e. the last byte of {\bf q[199]} was at that address.  On
Intel machines, the page size is 4096 bytes, so a virtual address breaks
down into a 20-bit page number and a 12-bit offset, just as in Section
\ref{trans} above. In our case here, {\bf q} ends in virtual page number
0x8049 = 32841, offset 0x7bf = 1983.  So, after {\bf q[199]}, there are
still 4096-1984 = 2112 bytes left in the page.  That amount of space
holds 2112/4 = 528 {\bf int} variables, i.e. elements ``200'' through
``727'' of {\bf q}.  Those elements of {\bf q} don't exist, of course,
but as discussed in Chapter \ref{chap:datarep} the compiler will not complain.
Neither will the hardware, as we will be writing to a page for which we
do have write permission.  But when {\bf i} becomes 728, that will take
us to a new page, one for which we don't have write (or any other)
permission; the hardware will detect this and trigger the seg fault.

\checkpoint

We could get a seg fault not only by accessing off-limits data items,
but also by trying to execute code at an off-limits location.  For
example, suppose in the above example {\bf q} had been local instead of
global.  Then it would be on the stack.  As we go past the end of {\bf
q}, we would go deeper and deeper into the stack.  This may not directly
cause a seg fault, if the stack already starts out fairly large and is
stored in physically contiguous pages in memory.  But we would overwrite
all the preceding stack frames, including return addresses.  When we
tried to ``return'' to those addresses,\footnote{Recall that {\bf
main()} is indeed called by other code, as explained in Chapter
\ref{chap:sub}.} we would likely attempt to execute in a page for which
we do not have execute permission, thus causing a seg fault.

As another example of violating execute permission, consider the
following code, with a pointer to a function:\footnote{If your classes
on C/C++ did not cover this important topic of pointers to functions,
the comments in the code below should be enough to introduce it to you.
Pointers to functions are used in many applications, such as threaded
programs, as mentioned earlier.}

\begin{Verbatim}[fontsize=\relsize{-2},numbers=left]
int f(int x)
{ return x*x; }

// review of pointers to functions in C/C++: below p is a pointer to a
// function; the first int means that whatever function p points to, it
// returns an int value; the second int means that whatever function p
// points to, it has one argument, an int
int (*p)(int);

main()
{  int u;

   p = f;  // point p to f
   u = (*p)(5);  // call f with argument 5 
   printf("%d\n",u);  // prints 25
}
\end{Verbatim}

If we were to forget to include the line

\begin{verbatim}
   u = (*p)(5);
\end{verbatim}

then the variable {\bf p} would not point to a function, and we would
attempt to execute ``code'' in a location off limits to us.  A seg fault
would result.

\checkpoint

\subsection{VM and Context Switches}

A context switch will be accompanied by a switch to a new page table.

Say for example Process A has been running, but its turn ends and
Process B is given a turn.  Of course we must now use B's page table.
So, before starting B's turn, the OS must change the PTR to point to B's
page table. 

Thus, there is actually no such thing as ``the'' page table.  There are
many page tables.  The term ``the'' page table merely means the page
table which PTR currently points to.

\subsection{Improving Performance---TLBs}

Virtual memory comes at a big cost, in the form of overhead incurred by
accessing the page tables. For this reason, the hardware will also
typically include a \textbf{translation lookaside buffer} (TLB). This is
a special cache to keep a copy of part of the page table in the CPU, to
reduce the number of times one must access memory, where the page table
resides.

One might ask, why not store the entire page table in the TLB?  First of
all, the page table theoretically consists of $2^{32}/2^{12}$ entries.
This is somewhat large. Though there are ways around this, but we would
need to change this large amount of data at each context switch, which
would really slow down context switching.  Note by the way that we would
need to have special instructions which the OS could use to write to the
TLB.  That's OK, though, and there are other special instructions for
the OS already.

% \subsection{Intel Page Tables}
% 
% On Intel machines, each process actually has many tables, not just one. And
% some of them may even be nonresident currently; in other words, even the page
% tables are paged!
%
% There is a {}``page table table,{}'' which serves as directory of page
% tables for the current process. A special register, CR3, points to the
% page table table.
%
% A virtual address is broken down into three fields, rather than the two in our
% descriptions above:
% 
% \begin{itemize}
% \item Bits 31-22: i, the index into the page table table 
% \item Bits 21-12: j, index into some page table 
% \item Bits 11-0: the offset 
% \end{itemize}
% 
% So, in processing a virtual address, the CPU will first fetch from the
% address c+4{*}i, where c is the current contents of CR3. That fetched
% word w will tell the CPU whether the page table for this virtual address
% is currently resident in memory. If that table is resident, w will show
% the address of the table, d, while if it is nonresident, it will show
% where on disk to get it. The CPU will bring in the table from disk in
% the latter case. Once the CPU has d, it will then fetch from the address
% d+4{*}j, yielding the page table entry for the item our running program
% has requested. At this point, the operations are the same as described
% earlier.

\subsection{The Role of Caches in VM Systems}
\label{cacherole}

Up to now, we have been assuming that the machine doesn't have a
cache.\footnote{Except for a TLB, which is of course very specialized.}
But in fact most machines which use VM also have caches, and in such
cases, what roles do the caches play?

The central point is that speed is still an issue.  The CPU will look
for an item in its cache first, since the cache is internal to (or at
least near) the CPU.  If there is a cache miss, the CPU will go to
memory for the item.  If the item is resident in memory, the entire
block containing the item will be copied to the cache.  If the item is
not resident, then we have a page fault, and the page must be copied to
memory from disk, a very slow process, before the processing of the
cache miss can occur.

\subsubsection{Addressing}

An issue that arises is whether the cache is the CPU will {\bf virtually
addressed} or {\bf physically addressed}.  Suppose for instance the
instruction being executed reads from virtual address 200.  If the cache
is virtually addressed, then the CPU would do its cache lookup using 200
as its index.  On the other hand, if the cache is physically addressed,
then the CPU would first convert the 200 to its physical address (by
checking the TLB, and then the page table if need be), and then do the
cache lookup based on that address.

A possible advantage of virtual addressing of caches would be that if we
have a cache hit, we eliminate the time delay needed for the
virtual-to-physical address translation.  Moreover, since we usually
will have a hit, we can afford to put the TLB in not-so-fast memory
external to the CPU, which is done in some MIPS models.

On the other hand, with physical cache addressing, two different
processes could both have separate, unrelated copies of different blocks
in the cache at the same time, but with the same virtual addresses.
They could coexist in the cache since their physical addresses would be
different.  That would mean we would not have to flush the cache at each
new timeslice, possible increasing performance. 

\checkpoint

\subsubsection{Hardware Vs. Software}

Note that cache design is entirely a hardware issue.  The cache lookup
and the block replacement upon a miss is hard-wired into the circuitry.
By contrast, in the VM case it is a mixture of hardware and software.
The hardware does the page table lookup, and checks page residency and
access permissions.  But it is the software---the OS---which creates and
maintains the page table.  Moreover, when a page fault occurs, it is the
OS that does the page replacement and updates the page table.

So, you could have two different versions of Unix, say,\footnote{Or,
Linux versus Windows, etc.} running on the same machine, using the same
compiler, etc. and yet they may have quite different page fault rates.
The page replacement policy for one OS may work out better for this
particular program than does the one of the other OS.  

Note that the OS can tell you how many page faults your program has had
(see the {\bf time} command below); each page fault causes the OS to run,
so the OS can keep track of how many page faults your program had
incurred.  By contrast, the OS can NOT keep track of how many cache
misses your program has had, since the OS is not involved in handling
cache misses; it is done entirely by the hardware.

\subsection{Making These Concepts Concrete: Commands You Can Try Yourself}

The Unix \textbf{time} command will report how much time your program
takes to run, how many page faults it generated, etc. Place it just
before your program's name on the command line. (This program could be
either one you wrote, or something like, say, \textbf{gcc}.) For
example, if you have a program \textbf{x} with argument 12, type

\begin{verbatim}
% time x 12
\end{verbatim}

instead of

\begin{verbatim}
% x 12
\end{verbatim}

In fact, trying running this several times in quick succession.  You
main find a reduction in page faults, since the required pages which
caused page faults in the first run might be resident in later runs.

Also, the {\bf top} program is very good, displaying lots of good
information on the memory usage of each process.

\section{A Bit More on System Calls}

Recall that the OS makes available to application programs services such
as I/, process management, etc.  It does this by making available
functions that application programs can call.  Since these are function
in the OS, calls to them are known as {\bf system calls}.

When you call {\bf printf()}, for instance, it is just in the C library,
not the OS, but it in turn calls {\bf write()} which \textit{is} in the
OS.\footnote{There is a slight complication here.  Calling {\bf write()}
from C will take us to a function in the C library of that name.  It in
turn will call the OS function.  We will ignore this distinction here.} 
The call to {\bf write()} is a system call.  

Or you can make system calls in your own code.  For example, try
compiling and running this code:

\begin{Verbatim}[fontsize=\relsize{-2}]
main()
{ write(1,"abc\n",4); }  
\end{Verbatim}

The function {\bf write()} takes three arguments:  the file handle
(here 1, for the Unix ``file'' {\bf stdout}, i.e. the screen); a pointer
to the array of characters to be written [note that NULL characters mean
nothing to {\bf write()}]; and the number of characters to be
written.  

Similarly, executing a {\bf cout} statement in C++ ultimately results in
a call to {\bf write()} too.  In fact, the G++ compiler in GCC
translates {\bf cout} statements to calls to {\bf printf()}, which as we
saw calls {\bf write()}.  Check this by writing a small C++ program with
a {\bf cout} in it, and then running the compiled code under {\bf
strace}.

A non-I/O example familiar to you is the {\bf execve()} service is used
by one program to start the execution of another.  Another non-I/O
example is {\bf getpid()}, which will return the process number of the
program which calls it. 

Calling {\bf write()} means the OS is now running, and {\bf write()}
will ultimately result in the OS running code which uses the OUT machine
instruction.  Recall, though, that we want to arrange things so that
\underline{only} can execute instructions like Intel's IN and OUT.  So
the hardware is designed so that these instructions can be executed only
in Kernel Mode.

For this reason, one usually cannot implement a system call using an
ordinary subroutine CALL instruction, because we need to have a
mechanism that will change the machine to Kernel Mode. (Clearly, we
cannot just have an instruction to do this, since ordinary user programs
could execute this instruction and thus get into Kernel Mode themselves,
wreaking all kinds of havoc!) Another problem is that the linker will
not know where in the OS the desired subroutine resides.

Instead, system calls are implemented via an instruction type which is
called a \textbf{software interrupt}. On Intel machines, this takes the
form of the INT instruction, which has one operand.

We will assume Linux in the remainder of this subsection, in which case
the operand is 0x80.\footnote{Windows uses 0x21.} In other words, the
call to {\bf write()} in your C program (or in {\bf printf()} or {\bf
cout}, which call {\bf write()} will execute

\begin{verbatim}
...  # code to put parameters values into designated registers
int $0x80
\end{verbatim}

The INT instruction works like a hardware interrupt, in the sense
that it will force a jump to the OS, and change the privilege level to
Kernel Mode, enabling the OS to execute the privileged instructions it
needs. You should keep in mind, though, that here the {}``interrupt{}''
is caused deliberately by the program which gets {}``interrupted,{}''
via an INT instruction. This is much different from the case of a
hardware interrupt, which is an action totally unrelated to the program
which is interrupted.

The operand, 0x80 above, is the analog of the device number in the case
of hardware interrupts. The CPU will jump to the location indicated by
the vector at c(IDT)+8{*}0x80.\footnote{By the way, users could cause
mischief by changing this area of memory, so the OS would set up their
page tables to place it off limits.}

When the OS is done, it will execute an IRET instruction to return
to the application program which made the system call. The {\bf iret}
also makes a change back to User Mode.

\checkpoint

As indicated above, a system call generally has parameters, just as
ordinary subroutine calls do. One parameter is common to all the
services---the service number, which is passed to the OS via the EAX
register. Other registers may be used too, depending on the service.

As an example, the following Intel Linux assembly language program
writes the string ``ABC'' and an end-of-line to the screen, and then
exits:

\begin{Verbatim}[fontsize=\relsize{-2}]
.text
hi:  .string "ABC\n"
_start:

      # write "ABC\n" to the screen
      movl $4, %eax     # the write() system call, number 4 obtained
                        # from /usr/include/asm/unistd.h
      movl $1, %ebx     # 1 = file handle for stdout
      movl $hi, %ecx    # write from where
      movl $4, %edx     # write how many bytes
      int $0x80         # system call

      # call exit()
      movl $1, %eax     # exit() is system call number 1
      int $0x80         # system call
\end{Verbatim}

For this particular OS service, {\bf write()}, the parameters are passed in
the registers EBX, ECX and EDX (and, as mentioned before, with EAX
specifying which service we want).  Whoever wrote {\bf write()} has
forced us to use those registers for those purposes.

Note that we do indeed need to tell {\bf write()} how many bytes to
write.  It will NOT stop if it encounters a null character.

Here are some examples of the numbers (to be placed in EAX before
calling {\bf int \$0x80}) of other system services:

\begin{verbatim}
read              3
file open         5
execve           11
chdir            12
kill             37
\end{verbatim}

\section{OS File Management}

The OS will maintain a table showing the starting sectors of all files
on the disk.  (The table itself is on the disk.)  The reason that the
table need store only the starting sector of a given file is that the
various sectors of the file can be linked together in ``linked-list''
fashion.  In other words, at the end of the first sector of a file, the
OS will store information stating the track and sector numbers of the
next sector of the file.

The OS must also maintain a table showing unused sectors.  When a
user creates a new file, the OS checks this table to find space to put
the file.  Of course, the OS must then update its file table
accordingly.

If a user deletes a file, the OS will update both tables, removing the
file's entry in the file table, and adding the former file's space to
the unused sector table.\footnote{However, the file contents are still
there.  This is how ``undelete'' programs work, by attempting to recover
the sectors liberated when the user (accidentally) deleted the file.}

As files get created and deleted throughout the usage of a machine, the
set of unused sectors typically becomes like a patchwork quilt, with the
unused sectors dispersed at random places all around the disk.  This
means that when a new file is created, then {\it its} sectors will be
dispersed all around the disk.  This has a negative impact on
performance, especially seek time.  Thus OSs will often have some kind
of {\bf defragmenting} program, which will rearrange the positioning of
files on the disk, so that the sectors of each individual file are
physically close to each other on the disk.

\section{To Learn More}

There are several books on the Linux OS kernel.  Before you go into such
detail, though, you may wish to have a look at the Web pages
\url{http://www.tldp.org/LDP/tlk/tlk.html} and
\url{http://learnlinux.tsf.org.za/courses/build/internals/}, which
appear to be excellent overviews.  

\section{Intel Pentium Architecture}
\label{pentium}

We will assume Pentia with 32-bit word and address size.  On Linux the
CPU runs in {\bf flat mode}, meaning that the entire address space of
$2^{32}$ bytes is available to the programmer.

The main registers of interest to us here are named EAX, EBX, ECX, EDX,
ESI, EDI, EBP and ESP.\footnote{We will use the all-caps notation, EAX,
EBX, etc. to discuss registers in the text, even though in program code
they appear as {\bf \%eax}, {\bf \%ebx}, ...}  ESP is used as the stack
pointer.  The program counter is EIP.  There is also a condition codes
register EFLAGS, which is used to record whether the results of
operations are zero, negative and so on.

In this document we use AT\&T syntax for assembly code.  Here is some
sample code, which adds 4 elements of an array pointed to by ECX, with
the sum being stored in EBX:

\begin{Verbatim}[fontsize=\relsize{-2},numbers=left]
      movl $4, %eax  # copy the number 4 to EAX
      movl $0, %ebx  # copy the number 0 to EBX
      movl $x, %ecx  # copy the address of the memory location
                     # whose label is x to ECX
top:  addl (%ecx), %ebx  # add the memory word pointed to by ECS to EBX
      addl $4, %ecx  # add the number 4 to ECS
      decl %eax  # decrement EAX by 1
      jnz top  # if EAX not 0, then jump to top
\end{Verbatim}

Pentia use vector tables for interrupt handlers.  Typical Pentium-based
computers include one or more Intel 8259A chips for controlling and
prioritizing bus access by input/output devices. 

As with most modern processor chips, Pentia are highly pipelined and
superscalar, the latter term meaning muliple ALU compoents, thus
allowing more than one instruction to execute per clock cycle.

For more information see the various PDF files in
\url{http://heather.cs.ucdavis.edu/~matloff/50/PLN}.


