THE multiprogramming system
Encyclopedia
The THE multiprogramming system was a computer operating system
designed by a team led by Edsger W. Dijkstra, described in monographs in 1965-66 and published in 1968.
Dijkstra never named the system; "THE" is simply the abbreviation of "Technische Hogeschool Eindhoven", then the name (in Dutch
) of the Eindhoven University of Technology
of the Netherlands
. The THE system was primarily a batch system that supported multitasking
; it was not designed as a multi-user
operating system. It was much like the SDS 940
, but "the set of processes in the THE system was static."
The THE system apparently introduced the first forms of software-based memory segment
ation (the Electrologica X8
did not support hardware-based memory management
), freeing programmers from being forced to use actual physical locations on the drum memory
. It did this by using a modified ALGOL
compiler (the only programming language
supported by Dijkstra's system) to "automatically generate calls to system routines, which made sure the requested information was in memory, swapping if necessary."
The constraint that higher layers can only depend on lower layers was imposed by the designers in order to make reasoning about the system (using quasi-formal methods
) more tractable, and also to facilitate building and testing the system incrementally. The layers were implemented in order, layer 0 first, with thorough testing of the abstractions provided by each layer in turn. This formal design process was highly successful, as reported by Dijkstra:
This division of the kernel into layers was similar in some ways to Multics
' later ring-segmentation
model. Several subsequent operating systems have used layering to some extent, including Windows NT
and Mac OS X
, although usually with fewer layers.
The code of the system was written in assembly language
for the Dutch Electrologica X8
computer. This computer had 32kiloword core memory of 27-bit words, a 512kword drum providing backing store for the LRU algorithm, paper tape readers, paper tape punches, and printers.
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
designed by a team led by Edsger W. Dijkstra, described in monographs in 1965-66 and published in 1968.
Dijkstra never named the system; "THE" is simply the abbreviation of "Technische Hogeschool Eindhoven", then the name (in Dutch
Dutch language
Dutch is a West Germanic language and the native language of the majority of the population of the Netherlands, Belgium, and Suriname, the three member states of the Dutch Language Union. Most speakers live in the European Union, where it is a first language for about 23 million and a second...
) of the Eindhoven University of Technology
Eindhoven University of Technology
The ' is a university of technology located in Eindhoven, Netherlands. The motto of the university is: Mens agitat molem . The university was the second of its kind in the Netherlands, only Delft University of Technology existed previously. Until mid-1980 it was known as the...
of the Netherlands
Netherlands
The Netherlands is a constituent country of the Kingdom of the Netherlands, located mainly in North-West Europe and with several islands in the Caribbean. Mainland Netherlands borders the North Sea to the north and west, Belgium to the south, and Germany to the east, and shares maritime borders...
. The THE system was primarily a batch system that supported multitasking
Computer multitasking
In computing, multitasking is a method where multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for...
; it was not designed as a multi-user
Multi-user
Multi-user is a term that defines an operating system or application software that allows concurrent access by multiple users of a computer. Time-sharing systems are multi-user systems. Most batch processing systems for mainframe computers may also be considered "multi-user", to avoid leaving the...
operating system. It was much like the SDS 940
SDS 940
The SDS 940 was Scientific Data Systems' first machine designed to support time sharing directly, and was based on the SDS 930's 24-bit CPU built primarily of integrated circuits. It was announced in February 1966 and shipped in April, becoming a major part of Tymshare's expansion during the 1960s...
, but "the set of processes in the THE system was static."
The THE system apparently introduced the first forms of software-based memory segment
Memory segment
x86 memory segmentation refers to the implementation of memory segmentation on the x86 architecture. Memory is divided into portions that may be addressed by a single index register without changing a 16-bit segment selector. In real mode or V86 mode, a segment is always 64 kilobytes in size . In...
ation (the Electrologica X8
Electrologica X8
The Electrologica X8 was a digital computer designed as a successor to the Electrologica X1 and manufactured in the Netherlands by Electrologica NV from 1965 onwards....
did not support hardware-based memory management
Memory management
Memory management is the act of managing computer memory. The essential requirement of memory management is to provide ways to dynamically allocate portions of memory to programs at their request, and freeing it for reuse when no longer needed. This is critical to the computer system.Several...
), freeing programmers from being forced to use actual physical locations on the drum memory
Drum memory
Drum memory is a magnetic data storage device and was an early form of computer memory widely used in the 1950s and into the 1960s, invented by Gustav Tauschek in 1932 in Austria....
. It did this by using a modified ALGOL
ALGOL
ALGOL is a family of imperative computer programming languages originally developed in the mid 1950s which greatly influenced many other languages and became the de facto way algorithms were described in textbooks and academic works for almost the next 30 years...
compiler (the only programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
supported by Dijkstra's system) to "automatically generate calls to system routines, which made sure the requested information was in memory, swapping if necessary."
Design
The design of the THE multiprogramming system is significant for its use of a layered structure, in which "higher" layers only depend on "lower' layers:- Layer 0 was responsible for the multiprogramming aspects of the operating system. It decided which process was allocated to the CPU, and accounted for processes that were blocked on semaphoreSemaphore (programming)In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment....
s. It dealt with interrupts and performed the context switches when a process change was required. This is the lowest level. In modern terms, this was the scheduler. - Layer 1 was concerned with allocating memory to processes. In modern terms, this was the pager.
- Layer 2 dealt with communication between the operating system and the console.
- Layer 3 managed all I/O between the devices attached to the computer. This included buffering information from the various devices.
- Layer 4 consisted of user programs. There were 5 processes: in total, they handled the compilationCompilerA compiler is a computer program that transforms source code written in a programming language into another computer language...
, execution, and printingPrintingPrinting is a process for reproducing text and image, typically with ink on paper using a printing press. It is often carried out as a large-scale industrial process, and is an essential part of publishing and transaction printing....
of users' programs. When finished, they passed control back to the schedule queue, which was priority-based, favoring recently started processes and ones that blocked because of I/OI/OI/O may refer to:* Input/output, a system of communication for information processing systems* Input-output model, an economic model of flow prediction between sectors...
. - Layer 5 was the user (as Dijkstra notes, "not implemented by us").
The constraint that higher layers can only depend on lower layers was imposed by the designers in order to make reasoning about the system (using quasi-formal methods
Formal methods
In computer science and software engineering, formal methods are a particular kind of mathematically-based techniques for the specification, development and verification of software and hardware systems...
) more tractable, and also to facilitate building and testing the system incrementally. The layers were implemented in order, layer 0 first, with thorough testing of the abstractions provided by each layer in turn. This formal design process was highly successful, as reported by Dijkstra:
We have found it is possible to design a refined multiprogramming system in such a way that its logical soundness can be proved a priori and that its implementation admits exhaustive testing. The only errors that showed up during testing were trivial coding errors (occurring with a density of only one error per 500 instructions), each of them located with 10 minutes (classical) inspection at the machine and each of them correspondingly easy to remedy.
This division of the kernel into layers was similar in some ways to Multics
Multics
Multics was an influential early time-sharing operating system. The project was started in 1964 in Cambridge, Massachusetts...
' later ring-segmentation
Ring (computer security)
In computer science, hierarchical protection domains, often called protection rings, are a mechanism to protect data and functionality from faults and malicious behaviour . This approach is diametrically opposite to that of capability-based security.Computer operating systems provide different...
model. Several subsequent operating systems have used layering to some extent, including Windows NT
Windows NT
Windows NT is a family of operating systems produced by Microsoft, the first version of which was released in July 1993. It was a powerful high-level-language-based, processor-independent, multiprocessing, multiuser operating system with features comparable to Unix. It was intended to complement...
and Mac OS X
Mac OS X
Mac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
, although usually with fewer layers.
The code of the system was written in assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
for the Dutch Electrologica X8
Electrologica X8
The Electrologica X8 was a digital computer designed as a successor to the Electrologica X1 and manufactured in the Netherlands by Electrologica NV from 1965 onwards....
computer. This computer had 32kiloword core memory of 27-bit words, a 512kword drum providing backing store for the LRU algorithm, paper tape readers, paper tape punches, and printers.