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.