flamer@omsvax.UUCP (Jim Trethewey) (04/11/84)
Run this through tbl and *roff -me.
-----------------------------------------
.bp
Copyright (C) 1983
.br
The Association for Computing Machinery
.br
SIGOPS, Special Interest Group on Operating Systems
.sp 2
Brinch Hansen, Per, "Using Personal Computers in Operating System Courses."
.i "ACM Operating Systems Review,"
Volume 17, Number 3, July 1983, pp. 41 - 50.
.sp 4
.ce 1000
.b "Using Personal Computers"
.b "In Operating System Courses"
.sp
PER BRINCH HANSEN
.sp
Computer Science Department
University of Southern California
Los Angeles, California 90089
.sp
June 1983
.sp 2
.i "Abstract"
.ce 0
.sp
.(q
By using personal computers it is now possible to make operating system
courses for computer science students as practical as compiler courses.
This paper describes a course in which undergraduates use the programming
language Edison to build operating systems for IBM Personal Computers.
.)q
.sp
.uh "Background"
.pp
The two most basic programming tools used by all computer programmers are
compilers and operating systems. Without reliable compilers and operating
systems, computers are practically useless. That is why computer science
departments emphasize courses on these important programs.
.pp
Compiler courses have always been very successful combinations of theory
and practice. In one semester, a student learns the theory of language
implementation and completes a working compiler of 1000 lines or more.
This is one of the few courses in which students learn engineering by
performing a difficult practical task.
.pp
In contrast, operating systems courses are mostly theoretical and do not
give students much practical experience. The theoretical orientation of
operating systems courses was established ten years ago when the first
text books were published [1, 2]. The most recent text books on the
subject continue this tradition [3, 4].
.sp
.pp
There are good technological reasons for this:
.ip (1)
Most large operating systems are concurrent programs that make a computer
perform many tasks simultaneously. Operating systems courses therefore
tend to become elementary introductions to the difficult art of writing
concurrent programs. Unfortunately, concurrent programming languages have
only been invented recently and have often been too complicated for
teaching purposes [5, 6]. Consequently, students have not been able to
run concurrent programs on university computers.
.ip (2)
Any experiments with operating system design on existing large computers
may disrupt the service of all other users on campus. So students are
seldom allowed to build working operating systems as part of their
education.
.sp
.pp
However, by using personal computers it is now possible to make operating
system courses as practical as compiler courses.
.sp
.uh "Personal Computers"
.sp
.pp
Personal computers are ideal for an operating system class. Since each
personal computer serves one student at a time only, it does not matter
if the use of that computer is disrupted temporarily by an experimental
operating system. And in one semester a student can easily complete a
single-user operating system for such a small computer.
.pp
In January 1983, USC opened a new teaching laboratory with 10 IBM Personal
Computers (now expanded to 40). Each computer has the following
configuration:
.sp
.(l
IBM Personal Computer (64K bytes)
Dual diskette drive (5\(14", 320K bytes each)
Parallel Display/Printer Adapter
Monochrome Display
Matrix Printer
.)l
.sp
.uh "The Edison System"
.sp
.pp
The students write operating systems for the IBM PC in the programming
language Edison. This language is well-suited for teaching operating
systems: It supports both modular and concurrent programming and is
simpler than Pascal.
.pp
Edison has already been used to write a complete software system for the
IBM PC known as the Edison System. It includes an operating system, an
Edison compiler, an 8088 assembler, a screen editor, a text formatter, and
a print program -- all written in the Edison language.
.pp
On the given IBM PC configuration, the Edison System has enough memory
and disk space to edit and compile its own operating system (or another
system written by a student). It can therefore be used as a development
tool for operating systems projects.
.pp
The Edison Language and System are described in a new book that includes
the text of the operating system [7]. This provides the students with a
detailed example of an operating system which they can study before
building their own.
.sp
.uh "A Student Project"
.sp
.pp
The first operating system built by students uses one diskette only and
supports text input, editing, compilation and printing. Files are stored
in contiguous segments on the disk and are compacted when space is needed.
.pp
Before the course started, I wrote a description of the project and built the
system to make sure that it could be done (the appendix contains the first
part of this description).
.pp
To get used to Edison, the students first wrote a few programs:
.sp
.TS
center;
l r.
Input program 20 lines
Print programs 20 lines
Edit program 200 lines
.TE
.sp
These programs were tested under the Edison System.
.pp
The operating system was developed one module at a time in the following
sequence:
.sp
.TS
center;
l r.
Terminal module 5 lines
Disk module 200 lines
Input/Output files 100 lines
User commands 100 lines
.TE
.sp
The terminal module was largely borrowed from the Edison System.
.pp
The student operating system was first tested as a user program under the
Edison System and was then moved to a new disk as an autonomous system.
The next step was to move the input, print and edit programs to the new
system. Finally, the Edison compiler was moved by rewriting 30 lines only.
.pp
Of the ten students who started the course, nine finished their operating
systems and were able to use them to edit, compile and execute Edison
programs.
.sp
.uh "Final Remarks"
.sp
.pp
The main goal of the course was to give the students a deep practical
understanding of how all the parts of a small operating system fit
together. No attempt was made to teach them concurrent programming or
machine-dependent details of input/output.
.pp
The control of peripheral devices by means of data channels, registers
and interrupts is a natural part of a course on computer architecture.
The Edison System hides these details in a system kernel that includes
procedures for reading and writing single characters (or blocks). An
operating system written in Edison calls these assembly language
procedures.
.pp
Concurrent programming is now a well-defined programming discipline that
can be taught independently of operating systems [8, 9]. The next step
at USC will be to offer such a course using Edison on personal computers.
.pp
Most students who take traditional operating system courses get very little
confidence in their ability to understand and build real operating systems.
However, if we replace the existing (theoretical) courses on operating
systems with programming courses of the type described here, students
will learn
.i "something"
about operating systems
.i "in depth"
and will then be able to appreciate the more advanced theories and
techniques through graduate courses or self-study.
.sp
.uh "References"
.sp
.ip 1.
Brinch Hansen, P.,
.i "Operating System Principles."
Prentice-Hall: Englewood Cliffs, New Jersey, 1973.
.ip 2.
Shaw, A. C.,
.i "The Logical Design of Operating Systems."
Prentice-Hall: Englewood Cliffs, New Jersey, 1974.
.ip 3.
Deitel, H. M.,
.i "An Introduction to Operating Systems."
Addison-Wesley: Reading, Massachusetts, 1983.
.ip 4.
Peterson, J., and Silberschatz, A.,
.i "Operating System Concepts."
Addison-Wesley: Reading, Massachusetts, 1983.
.ip 5
Brinch Hansen, P., "The Programming Language Concurrent Pascal."
.i "IEEE Transactions on Software Engineering 1,"
2 (June 1975), pp. 199 - 207.
.ip 6.
Wirth, N., "Modula: A Language for Modular Multiprogramming".
.i "Software - Practice and Experience 7,"
2 (March - April 1977), pp. 3 - 35.
.ip 7.
Brinch Hansen, P.,
.i "Programming a Personal Computer."
Prentice-Hall: Englewood Cliffs, New Jersey, April 1983.
.ip 8.
Holt, R. C., Graham, G. S., Lazowska E. D., and Scott, M. A.,
.i "Structured Concurrent Programming with Operating Systems Applications."
Addison-Wesley: Reading, Massachusetts, 1978.
.ip 9.
Ben-Ari, M.,
.i "Principles of Concurrent Programming."
Prentice-Hall: Englewood Cliffs, New Jersey, 1982.
.sp 2
.uh "Appendix: Student Operating System"
.sp
.pp
Use the Edison System on the IBM Personal Computer to build a Student
Operating System with the following properties:
.sp
.uh "Terminal Input"
.sp
.pp
The terminal operations are very similar to those used on the Edison System.
The only difference is that the backspace and tab keys are replaced by
the following keys:
.pp
.i "Left arrow:"
Moves the cursor one position to the left (if possible).
.pp
.i "Right arrow:"
Moves the cursor one position to the right (if possible).
.sp
.uh "Disk"
.sp
.pp
The system uses one disk only (inserted in drive 0). When the system is
started it inputs a catalog from the disk. After the execution of a
command, the system outputs the catalog to the disk if it has been
changed.
.pp
An insert operation
.sp
.ce 1
Command = \fBinsert\fR
.sp
inputs the catalog from the disk. You must perform this operation whenever
you have replaced the disk in the drive.
.pp
A list operation
.sp
.ce 1
Command = \fBlist\fR
.sp
displays a list of all the files described in the catalog. Each file is
described by its name, disk address and length, for example:
.sp
.ce 1
clock \ \ pageno 25 \ \ 4 pages \ \ 4017 words
.sp
The listing includes the number of files on the disk and the sizes of the
available and hidden disk spaces (described later), for example:
.sp
.ce 1
27 files \ \ 40 available pages \ \ 33 hidden pages
.sp
.pp
The operation
.sp
.ce 1
Command = \fBcompact\fR
.sp
moves all files on the disk to eliminate the hidden space and make the
available space as large as possible.
.pp
The operation
.sp
.ce 1
Command = \fBnewcatalog\fR
.sp
deletes all files from the disk and makes the catalog empty.
.sp
.uh "Files"
.sp
.pp
A file is a named sequence of words stored on a disk. It cannot be
empty and cannot be protected.
.pp
The rename, delete and copy operations have the same effect as in the
Edison System.
.pp
Examples:
.sp
.(c
Command = \fBrename\fR
Old name = \fBedit\fR
New name = \fBnewedit\fR
.sp
Command = \fBdelete\fR
File name = \fBprinttext\fR
.sp
Command = \fBcopy\fR
Input name = \fBprefix\fR
Output name = \fBclocktext\fR
.)c
.sp
.uh "Text Input"
.sp
.pp
An input operation enables you to input text from the terminal and
store it as a file on the disk.
.pp
Example:
.sp
.(c
Command = \fBinput\fR
File name = \fBreport\fR
.br
Start typing:
.)c
.pp
The text must be typed with the following syntax:
.sp
.(c
<input text> ::=
<text file> <end symbol>
.br
<text file> ::=
<line> [ <line> ]*
.br
<line> ::=
[ <graphic character> ]* <return>
.br
<end symbol> ::=
`$' <return>
.)c
.sp
.pp
The return typed at the end of a line is stored in the file as a
newline character (nl).
.pp
The end symbol is used only to define the end of the input text and is
not stored in the file.
.sp
.uh "Text Editing"
.sp
.pp
An edit operation enables you to change an existing file. You may go forward
only in the text and make corrections, insertions, and deletions on the
cursor line.
.pp
Example:
.sp
.(c
Command = \fBnewedit\fR
File name = \fBschedule\fR
.)c
.sp
.pp
When a text line first appears on the screen, it is shown at the bottom and the
cursor is placed under the first character position of the text line.
A line number is displayed in front of the text line.
.pp
A text line from the original file is shown with its original line number.
A new line inserted in the edited file is shown with the same line number
as the nearest preceding original line.
.pp
Initially, the first line of text is shown.
.pp
The input keys have the following effects on the file and the screen:
.pp
.i "Graphic character:"
Inserts a graphic character at the cursor position and moves the cursor one
position to the right (as in the Edison System).
.pp
.i "Del:"
Deletes a graphic character (if any) at the cursor position (as in the
Edison System).
.pp
.i "Left arrow:"
Moves the cursor one position to the left (if possible).
.pp
.i "Right arrow:"
Moves the cursor one position to the right (if possible).
.pp
.i "Down arrow:"
Moves the lines shown up one position and displays the next line (if any).
.pp
.i "Esc:"
Deletes the cursor line from the file and the screen. If the last line of
the file is deleted, the editor performs the operation normally invoked
by the end key (described below); otherwise, it shows the next line of the
file.
.pp
.i "Ins:"
Inserts a new line consisting of a newline character only after the cursor
line in the file. The editor then moves the lines shown up one position and
displays the new line.
.pp
.i "Home:"
Waits until you have typed a line number (which will not be shown as you type
it). The editor then repeats the down arrow operation (if possible) until the
line with this number is shown.
.pp
.i "End:"
Finishes the editing after asking the question
.sp
.ce 1
Replace original by edited file?
.sp
If you answer
.i "yes,"
the original file is replaced by the edited file on the disk. If you answer
.i "no,"
the original file is left unchanged on the disk while the edited file is
deleted.
.pp
The editor responds to an undefined command by ringing the bell.
.sp
.uh "Text Printing"
.sp
.pp
A print operation prints a text file as follows:
.pp
The printed file begins and ends with two blank pages. Each printed page
begins with a page number and two blank lines followed by 51 printed
lines (or less). Each printed line begins with a line number.
.pp
Example:
.sp
.(c
Command = \fBnewprint\fR
File name = \fBnewedittext\fR
.)c
.sp
.uh "Program Parameters"
.sp
.pp
An Edison program executed by the system must be compiles with the
following prefix:
.sp
.(c
\fBconst\fR nl = char (10);
sp = ' ';
linelength = 80 "characters";
namelength = 12 "characters"
.br
\fBset\fR charset (char)
.br
\fBarray\fR line [1:linelength] (char)
.br
\fBarray\fR name [1:namelength] (char)
.br
\fBarray\fR program [1:12300] (int)
.sp
\fBproc\fR NewPrefix (
\fBproc\fR select (normal: bool);
\fBproc\fR cursor (row, column: int);
\fBproc\fR erase;
\fBproc\fR display (value: char);
\fBproc\fR assume (condition: bool; text: line);
\fBproc\fR accept (\fBvar\fR value: char);
\fBproc\fR pause;
\fBproc\fR print (value: char);
\fBproc\fR openread (title: name);
\fBproc\fR more: bool;
\fBproc\fR read (\fBvar\fR value: char);
\fBproc\fR endread;
\fBproc\fR openwrite (title: name);
\fBproc\fR write (value: char);
\fBproc\fR endwrite;
\fBproc\fR delete (title: name);
\fBproc\fR rename (old, new: name);
\fBproc\fR readbool (\fBproc\fR read (\fBvar\fR c: char); \fBvar\fR value: bool);
\fBproc\fR readint (\fBproc\fR read (\fBvar\fR c: char); \fBvar\fR value: int);
\fBproc\fR readname (\fBproc\fR read (\fBvar\fR c: char); \fBvar\fR value: name);
\fBproc\fR writebool (\fBproc\fR write (\fBvar\fR c: char); \fBvar\fR value: bool);
\fBproc\fR writeint (\fBproc\fR write (\fBvar\fR c: char); \fBvar\fR value: int);
\fBproc\fR writename (\fBproc\fR write (\fBvar\fR c: char); \fBvar\fR value: name);
\fBproc\fR writeline (\fBproc\fR write (\fBvar\fR c: char); \fBvar\fR value: line);
\fBproc\fR subset (first, last: char): charset;
\fBproc\fR load (title: name): program)
.)c
.sp
.pp
A program can operate on two files at a time only: an input file and an
output file.
.pp
Openread makes an existing file with a given name accessible as the current
input file. More defines whether there are any more words to be read from
the input file. Endread makes the file inaccessible for further input.
.pp
Openwrite makes the system ready to output a new file in the available
disk space. Write puts the next word into the output file. Endwrite
describes the new file in the catalog and makes it inaccessible for
further output. (If another file of the same name already exists, it
will be deleted.)
.pp
The other procedures have the same effects as in the Edison System.
.sp
.uh "Disk Format"
.sp
.pp
The disk is divided into pages of 1024 words each:
.sp
.(c
\fBconst\fR pagelength = 1024
.br
\fBarray\fR page [1:pagelength] (char)
.)c
.pp
The disk pages are numbered 1 through 160:
.TS
center;
c c c,
c r l.
\fBPages\fR \fBK words\fR \fBContents\fR
1 - 3 3 Edison kernel
4 - 12 9 System code
13 1 Disk catalog
14 - 160 147 File area
.TE
.pp
The file area on the disk is divided into files, holes, and available
space:
.sp
.TS
center, allbox;
c c c c c c c.
File File Hole File Hole File \ \ \ Available\ \ \
.TE
.sp
.pp
Each file occupies one or more pages with consecutive numbers. A new
file is always placed at the beginning of the available space right after the
existing files. When files are deleted, holes appear on the disk. The set
of all holes is called the hidden disk space.
.pp
When the system has executed a command, it checks whether
the size of the hidden space exceeds the size of the available space.
In that case, the system does not accept another command until it has
moved all the files to the beginning of the file area, so that the
holes disappear and the available space becomes as large as possible:
.sp
.TS
center, allbox;
c c c c c s s.
File File File File \ \ \ \ \ \ \ Available space\ \ \ \ \ \ \ \
.TE
.sp
.pp
The user can also at any time ask the system to compact files in this
manner.
.pp
The files are described in a disk catalog:
.sp
.(c
\fBrecord\fR diskcatalog (available, hidden, files: int; table: filetable; filler: int)
.)c
.sp
The catalog defines the sizes of the available and hidden spaces (in pages)
and also the number of files kept on the disk.
.pp
The files are described in a table in the same oreder in which they
are stored in the file area:
.sp
.(c
\fBconst\fR maxitem = 68
.br
\fBarray\fR filetable [1:maxitem] (item)
.)c
.sp
.pp
Each file has a name of 12 characters (or less) and a set of attributes:
.sp
.(c
\fBrecord\fR item (title: name; attr: attributes)
.)c
.sp
.pp
The attributes are the starting address of the file (which is a page
number) and its length:
.sp
.(c
\fBrecord\fR attributes (address: int; length: filelength)
.)c
.sp
.pp
The length of a file is measured in the number of pages it occupies and the
number of words stored on its last page:
.sp
.(c
\fBrecord\fR filelength (pages, words: int)
.)c
.sp