Chapter 0: What are Operating Systems Good For?
----------------------------------------------

To see why operating systems are in widespread use, imagine a
"naked" computer, consisting of a processing unit, which is able
to fetch instructions from memory, and to interpret and execute
these instructions.

Program loading
---------------
A program has to be entered into memory before it can be executed by
the processing unit. Thus a computer without an operating system needs
a device, called a "console", which can be used to change the contents
of the memory. The memory can be viewed as an array of numbered cells,
each containing a nonnegative integer.  With switches on the console
you enter the binary digits (a.k.a bits)of the number of the cell --
which is called address -- and then the bits of the contents of the
cell.  If you are finished entering the whole programm, you enter the
address of the first instruction (i. e. the number of the memory cell)
and press some start button to execute the program.

This whole cumbersome process is called "loading a program".  If
the program to be loaded is already stored on a permanent medium
like a disk or a tape, the loading can be done by the computer
executing another program, the so called loader.  The loader has
to control the disk in order to copy the program into memory.
Loading and controlling the execution of other programs is one of
the tasks operating systems do for you.

Better interface to the hardware
--------------------------------
The user written program usually has to do some I/O, which means
it has to control I/O devices. For this task, the programmer has
to acquire intimate knowledge of how the device is to be programmed.
This knowledge as well as the resulting program depends heavily on
the particular type and model of the device.  So another task of
the operating system is to provide a device and model independent
application programm interface (API), which hides the hardware
specific details in so called ``drivers''. This makes it easier to
adapt the application programs to another disk model.

A typical disk driver presents the contents of a disk to the
application program as an array of fixed sized sectors (ranging
from 256 to 8192 Bytes). There is a need to partition this lump of
sectors in files, which are addressed by names, not by sector
numbers. The mapping between filenames and sector numbers as well
as creation, changing and deletion of files is done by a filesystem,
which is one of the most important parts of an operating system.

Furthermore the operating system provides a user interface, by
which a user can specify the program to be loaded and the files to
worked on by the loaded program. This can be a so called
command interpreter (MS-DOS) or a graphical user interface as
implemented by the Finder of the Macintosh Operating System or
Windows "Explorer".

Multiprogramming / Multiuser
----------------------------
The need to run several programs simultaneously is addressed by a
multiprogramming system.  The original use of this feature was to
enhance the throughput of a so called "batch", which is a set of
programs. If one program were run after the other, the processor
would be idle during the time an I/O request is serviced. In a
multiprogramming system the CPU is kept busy executing some other
program of the batch. Even though this switching from one program
to another adds some overhead, the time needed to complete the whole
batch turned out to be shorter.

If the computer is used interactivly, a multiprogramming system
allows the user to enter a command while another command is still
running.  This way the computer can be used editing a file while
downloading another file at the same time.

Multiprogramming is pushed further by interactive systems which
let more than one person use the system simultaneously. Operating
systems with this feature are termed "multiuser systems" or "time
sharing systems", because the processor time is shared by several
to many users.

The original incentive for a time sharing system was to share the
expensive computer. But even today with cheap computers it is
necessary to centralize and share resources like printers, files,
communication lines, databases, tape libraries and last but not
least system administration. This is done by central computers, so
called servers, which let thousands of users login simultaneously.

The multiuser operating system has the obligation to allocate the
resources (processor, memory, I/O devices) to competing programs.
Since a crash of the system might effect thousands of users, it
has to protect itself and simultaneously running programs from
each other.

Another challange introduced by multiuser systems is security. The
operating system has to provide some means to control access to
the files.  Not every file may be changed or read by every user.

UNIX V6 and PDP-11
------------------
In this course we will study how operating systems are implemented.
We will use the UNIX Version 6 (V6) running on the Programmable
Data Processor 11/40 (PDP-11/40) as a case study.

Although released 1975, V6 still qualifies for an operating system
course, because

- it is small enough to be comprehended by a single person. The kernel
  source counts at about 9000 lines -- compare this to MINIX, which
  needs 27000 lines to implement only a subset of V6.

- it is powerful enough i. e. it is a multiprogramming/multiuser operating
  system. Since it was heavily used by its programmers (Ken Thompson,
  Dennis Ritchie) it exhibits all the features needed and -- not
  more. The core is not hidden by layers of code designed to serve
  the needs of marketing departments.

- The complete source is available -- well documented by the original
  authors and by others who used V6 in operating system courses -
  notably by John Lions whose "Commentary on UNIX 6th Edition" was
  heavily used in preparation of this course.

- Most of the V6 features are employed in modern operating systems.
  So V6 being outdated does not mean that the knowledge of how V6
  works is outdated as well.

The PDP-11 was in widespread use during the seventies and eighties.
Its hardware architecture heavily influenced the design of contemporary
CISC microprocessors, especially Motorolas 68000 Series and
regrettable to a lesser degree Intel's 80x86 family of processors.

UNIX V6 and the PDP-11 heavily influence both contemporary operating
systems and hardware architecture. This makes them a model for computing
in the 21st century.

Overview of the rest of this course:
------------------------------------
This course takes a bottum up approach:

Chapter 1 starts describing the hardware, i. e. CPU and I/O devices.
It introduces the notions of machine and assembler program. This will
enable you to understand how the installation and booting programs of
V6 are implemented.  At the end of this chapter you should be able to
install V6 on the SUPNIK Simulator (a.k.a.  SIMH), work with the V6
documentation, be able to configure and install a new kernel.

Chapter 2 is about process control, interrupt handling and memory
management. At the end of this chapter, you should know about the
synchronization problem and its solution in the V6 kernel, the pitfalls
of interrupt service routines and the way the hardware supports memory
management.

Chapter 3 will cover the I/O subsystem, i. e. the programming of
devices and the management of blocked I/O.

Chapter 4 is devoted to the filesystem, i. e. the data structures
and algorithm that name a file and allocate disk blocks to a file.

Chapter 5 is about the implementation of the programs needed to build
programs, namely assembler, C compiler, linkage editor. It describes
implementation of the part of the kernel that loads programs.


Courseware:
There are some files at http://www.ba-stuttgart.de/~helbig/os:
- script/ contains (part of) the script to this course.

- v6/doc/ contains most of the documentation distributed with V6 in
  postscript format. The Programmers manual is provided as a set of
  html pages.

- v6/dist.tap is a file ready to be used by SIMH. It resembles the
  original distribution tape for Unix V6.

- pdp11/doc	Instruction Set and H/W Interface to some PDP-11 devices
		These papers are meant to be studied in parallel to
		the script.

- pdp11/progs   Some PDP-11 machine programs stored as SIMH command files.