The following paper was presented at the 1992 ACM SIGCSE Symposium held in Kansas City.
Operating systems are an example of a subject that, given the right tools, can be taught in a practical manner, allowing students to understand, and hence appreciate, the internal workings of commercial operating systems such as VMS, Unix, or VM. Not surprisingly, the tools needed in an operating systems course are, at a minimum, a hardware testbed and a programming language into which algorithms can be translated. This paper describes how many of the salient points concerning operating systems can be covered in a practical manner using the PC and Turbo C.
Keywords: Operating systems, Turbo C, PC.
An operating system is one of those tools that everyone uses but few actually understand. Accordingly, a certain degree of mysticism is often associated with any discussion about operating systems. If one of the objectives of an undergraduate computing science program is to remove the 'magic' associated with computers, then a course in operating systems goes a long way toward meeting this objective. For example, a course in operating systems allows:
A course in operating systems, like many other computing science courses, has three basic components:
Although it is possible to teach a course in operating systems using any one of the aforementioned components, most courses incorporate at least two of the three: typically the first two. The practical component is often left out because software tools are lacking; since, in many cases, all or part of the work must be done in assembler [2]. On the other hand, existing software tools such as Minix [3], although extremely educational, do not necessarily fit 'nicely' into a one semester course on operating systems.
Fortunately, it is possible to cover many of the practical aspects of an operating system in a structured fashion using Turbo C, since Turbo C offers a number of extensions to the C language that permit the design, development, and implementation of a meaningful operating system.
This paper explains how the author uses Turbo C and the PC to help teach the practical component of a senior-level course in operating systems. This portion of the course requires the students to write a small kernel that supports multiple processes, messaging, and a number of applications.
The operating systems course is open to students in either their junior or senior year. Students are expected have taken a one semester course in assembler, a one semester course in machine architecture, and a two semester course in data structures. The majority of students have experience with Pascal and VAX assembler only.
The operating systems course is intended to cover all three components described in the previous section. By the end of the course, the students are expected to demonstrate an understanding of:
The course itself is divided into three parts:
Students are evaluated through a series of quizzes (one at the end of each part) and a final examination covering both the techniques and theoretical components of the course. There is also a series of assignments that constitute the practical aspects of the course. The semester is 13 weeks long: two 90-minute classes are held each week. At present, the course does not include a formal laboratory.
The practical component of the course is intended to give the students a clearer understanding of what takes place within an operating system, the machine on which it runs, and user applications. Accordingly, students are required to write a kernel that supports message passing between processes. The kernel itself is based upon the Lego research project headed by the author which is currently examining the incorporation of multimedia and hypermedia into a distributed multicast environment [4, 5, 6]. The practical component involves the students designing and implementing a series of assignments. The experience gained from each assignment is used as the basis for the next.
Before the students can be expected to start development of the kernel, they must have an understanding of the underlying hardware. In this case, the hardware is the IBM PC [4]; more specifically, the 80x86 processor chip, the keyboard, and the clock.
Registers on the 80x86 are 16-bits long, meaning that they can access at most 64k of memory. The 64k limit has been overcome by using 16-bit segmentation registers (one each for code, data, and stack). For example, when accessing the stack, the 80x86 combines the stack segment register and the stack pointer to obtain a 20-bit stack address [7].
All hardware devices communicate with the processor through the 8259 Interrupt Controller: when a device interrupts, the 8259 signals the 80x86 via a single interrupt channel. After determining which device is interrupting, the 80x86 disables interrupts, saves the current code segment and instruction pointer on the stack, and transfers control to the interrupt service routine associated with the interrupting device. Upon completion of the interrupt, the 8259 is signalled (to allow other devices to interrupt) and control returns to the code executing prior to the interrupt [8].
There are a total of four assignments that the students are expected to complete by the end-of-term. Each assignment, its objectives and requirements are now considered.
The objective of the first assignment is to introduce the students to 80x86 interrupts, device drivers, and race conditions [9]. The students are expected to design and implement an application that allows a user to set and query the time-of-day.
Two interrupt service routines are required: one for the clock, the other for the keyboard. The clock is programmed to interrupt about 1000 times a second (i.e. once a millisecond); the clock interrupt service routine updates a global data structure representing the time-of-day (hours, minutes, and seconds). The keyboard interrupt service routine accepts characters from the keyboard, placing each character in a queue that can be read by the application.
The application supports two commands: SET and TIME. The SET command requires the user to enter a string in the form hh:mm:ss. If the time string is valid, the application sets a global time data structure to the supplied time value. The TIME command causes the application to read the global time data structure, convert the internal integers into ASCII and then display the resulting string.
A race condition can occur should a clock interrupt happen at the same moment the application is processing a SET command and both the application and the interrupt service routine attempt to update the global time data structure. The problem is overcome by making the time data structure a critical region and protecting it either by semaphores or by simply disabling interrupts.
The time allotted for this assignment is three weeks. The students are given a keyboard translation table as well as the basic algorithms for handling clock and keyboard interrupts.
The objective of the second assignment is to design and implement software that (1) allows multiple processes to function 'simultaneously', (2) handles process creation and deletion, and (3) supports memory allocation and deallocation.
The students are expected to design the data structures that represent a process (i.e. a register table and a list of active memory) and the algorithms required that allow the concurrent execution of up to 8 processes. From this design, the students implement a rudimentary kernel that handles the following:
Process deletion is signalled by the process executing a termination routine that calls the kernel with a deletion request. The address of the termination routine is put onto the process's stack when the process is created. The kernel returns the stack space to the list of free memory (see below) and makes the process table entry available for the next creation request.
The various kernel calls are executed using a software interrupt to a kernel entry point.
All processes are statically loaded. That is, they are compiled, linked, and loaded into memory with the kernel and cannot be changed over time. However, if the code is made re-entrant and global variables are avoided, the same code can be executed simultaneously by a number of different processes, each supporting its own stack. Processes can perform output since a call to the DOS output routine takes place while the process has control of the machine.
The time allotted for this assignment is three weeks. Several processes are given to the students for testing purposes: a 'boot' process that continously starts processes (if free process space is available); a short 'print-and-terminate' process that prints a message and then terminates; and a 'run-forever' process that runs continuously, periodically printing to the screen.
The rudimentary kernel developed in the second assignment and the two device drivers developed in the first can be combined to make a kernel that supports dynamic process swapping and interprocess communication using messages. The objective of the third assignment is to design and implement such a kernel.
The new kernel supports the following:
The send() primitive passes a message, MSG, of SIZE bytes, to the kernel. The kernel is responsible for placing the message on the queue indicated by DST.
A send can fail if the specified destination, DST, does not exist or if the size of the message exceeds the allowable message-size limits (1 to 256 bytes). The kernel returns an error code in each of these cases.
If the transmission is successful, the kernel returns the number of bytes (originally specified in SIZE).
A call to the receive() primitive allows a process to receive a message from its message queue. The kernel returns the identifier of the process that sent the message, SRC, and the message, MSG. The value of SIZE indicates the maximum number of bytes that can be stored in MSG. The number of bytes copied is the lesser of the specified size and the queued message's size.
A process issuing a receive() is blocked until a message becomes available.
If there are no processes on the ready-to-run queue (i.e. all processes are waiting for some type of input), an idle process is activated.
The students are given four weeks to complete this assignment. Throughout this period they are expected to produce brief reports explaining what they have achieved; thereby ensuring that the students do not leave the entire assignment to the last week and submit nothing. The students develop their own test routines.
The final assignment expects the students to modify the kernel so that high-level applications, such as editors or other executable software, can be run on the kernel. The main change required to the kernel is the design and implementation of a memory manager that can handle memory requests from a process. All memory beyond the end of the kernel is made available for code, data, or stack segments.
Several utilities are taken from the Lego project, modified, and given to the students to test their software:
The students are given two weeks in which to complete this assignment. In addition, they are required to write a small shell that utlitizes the send() and receive() primitives, demonstrating their understanding of messaging.
All of the assignments are written in Turbo C. The reasons for using Turbo C include (1) its price, (2) the code it produces is re-entrant, (3) the compiler is reliable, and (4) the widespread availablilty of PCs at Saint Mary's. As importantly, the language extensions supported by the compiler all but eliminate the need for writing assembler-language software [10]. The extensions and their uses are now considered in turn.
The Turbo C compiler supports language extensions that allow the declaration of procedures as device handlers or kernel entry points. Any function of type void interrupt causes the compiler to generate assembler instructions to push (i.e. save) all registers onto the stack. There are corresponding assembler instructions to pop (i.e., restore) the registers from the stack upon exit from a void interrupt function. Since all interrupts initially push the flag register, the code segment register, and the instruction pointer onto the stack, the compiler generates an iret (interrupt return) instruction, rather than a ret (subroutine return). Furthermore, the registers on the stack can be accessed by declaring a series of unsigned (16-bit) parameters. Each parameter corresponds to the value of the register on the stack (the order defined by Turbo C is: bp, di, si, ds, es, dx, cx, bx, ax, ip, cs, and flags).
For example, a simple clock interrupt service routine that is interrupted once a millisecond can be made to signal whenever one second has passed using the following code:
void interrupt clock_interrupt()
{
static ticks = 0;
if (ticks++ != MILLISEC)
{
second = TRUE;
ticks = 0;
}
}
Other than the declaration of the function to be of type interrupt, the
same rules apply to writing a C function of type interrupt as they do
for any other function: static and local variables can be declared, global
variables can be accessed, and other procedures and functions can be called.
To permit the operating system to change the various segments in which the processes reside, it is necessary to access the hardware registers. Turbo C allows all hardware registers to be accessed through a set of variables known as pseudo variables. A pseudo variable is simply the common abbreviation of the register, capitalized and prefixed with an underscore. For example, the stack segment register is _SS, while the 'ax' register is referred to as _AX.
Pseudo variables allow, for example, the stack segment and pointer to be changed when processes are swapped. The following example illustrates the use of pseudo variables within an interrupt service routine:
void interrupt clock_interrupt()
{
running->regs.ss = _SS;
running->regs.sp = _SP;
_SS = kernel_ss;
_SP = kernel_sp;
swap();
_SS = running->regs.ss;
_SP = running->regs.sp;
}
In the above example, when the interrupt occurs, the current stack segment and stack pointer are saved in the process table of the currently running process (pointed to by running). The stack segment and pointer are then changed to point to the kernel's stack. Procedure swap() is called (using the kernel's stack), the variable running is changed to point to a new process table entry. Upon return from swap(), the stack segment and stack pointer of the new process are assigned to the pseudo variables _SS and _SP. Assuming that the registers are stored correctly on the (new) process's stack, control will be returned to the process upon exit from the interrupt service routine.
Turbo C supports a number of functions to handle the pecularities of the 80x86 (described above, Hardware Testbed). The following lists those functions that are used in the operating systems course:
The disable() function allows interrupts to be disabled by clearing the interrupt bit in the flags register. The function is limited in that the old value of the flags register is not saved. This means that it is not possible to restore the machine to its previous interrupt state.
Interrupts are enabled (i.e., the interrupt bit in the flag register is set) when the enable() function is called.
The MK_FP() macro creates a far pointer (20-bit) from a segment and an offset, that permits access to any memory location in the machine. For example, the code to copy the register values from the top-of-stack into a process table could be written as follows:
void swap()
{
unsigned far *tos;
tos = MK_FP(running->regs.ss, running->regs.sp);
running->regs.bp = *tos++;
running->regs.di = *tos++;
/* And so on for the remaining registers */
}
The segment and offset of a far pointer, pointing to any memory location, can be obtained using the macros FP_SEG() and FP_OFF(), respectively. For example, to initialize the code segment and instruction pointer to a process's entry point, one could write:
void start_up(void far *starting_addr)
{
process_tbl->regs.cs = FP_SEG(starting_addr);
process_tbl->regs.ip = FP_OFF(starting_addr);
/* Initialize other registers */
}
The 80x86 allows the status of any device to be obtained and the device controlled by software using the assembler instructions in and out. Turbo C supports high-level language constructs for each of these instructions: inportb(), obtain a byte from a port; outportb(), write a byte to a port; and outport(), write a word to a pair of consecutive ports.
The address of the interrupt service routine can be stored in its correct interrupt vector using the setvect() function. Setvect() takes two parameters: the number of the interrupt vector and the address of the interrupt vector (any function of type interrupt).
For example, the code fragments required to initialize interrupt vector 0x50 as the kernel entry point could be written as follows:
#define KERNEL0x50
void interrupt kernel_entry()
{
/* Kernel code */
}
void start_kernel()
{
setvect(KERNEL, kernel_entry);
/* Other initialization code */
}
Software interrupts to any interrupt service routine can be achieved using the geninterrupt() function. The interrupt vector in question is specified as the parameter to geninterrupt(). As with any 80x86 interrupt, the flags register, the code segment, and instruction pointer are all stacked; interrupts are disabled. For example, the code to pass a message to the kernel (pointed to by the 'bx' register) could be written as follows:
int example()
{
struct kmsg msg;
/* Setup data in msg */
_BX = &msg;
geninterrupt(KERNEL);
}
The operating systems course described in this paper has been taught three times by the author; based on this experience, the following observations can be made:
The author would like to thank those people who have worked on the Lego project and the students who have taken the operating system course; as well as the anonymous referees who made several positive and helpful suggestions. Thanks are also due to Sandy Cook who has patiently listened to and commented on the author's ideas for this and many other courses. Funding for the Lego project has come from the Natural Sciences and Engineering Research Council of Canada and the Scottish Rite Charitable foundation.