Paper Discussion - Fall 2008 - CS 736

Summary:

This paper describes the design,development and verification of a hierarchically structured multiprogramming system in which all activities like storage allocation, processor allocation and execution of user programs are performed by mutually synchronized sequential processes. The hierarchical organization of processes into various levels such that higher level processes can depend only on lower level processes provides logical soundness to the design, introduces abstractions that help the implementation and also allows a level-by-level verification by which a good set of relevant test cases can be covered easily.

Description of the problem:

To design,build,verify and run a multiprogramming system that can process continuous flow of user programs with:
a) reduced turn-around time for short programs unlike the traditional batch systems
b) shared use of peripheral devices and processor between processes
c) automatic backing store ( core memory and drum memory )
d) feasibility to run programs that need the flexibility of the computer but their resource requirements are much smaller compared to the computer's capacity.

Contributions of the Paper:

a) Distinguishes between information units ( segments ) and memory units ( pages ) clearly and provides an early form of software based segmentation as part of the automatic control of backing store. This is much better than the earlier method where programmers were forced to identify all information using the physical addresses on the drum.
b) Introduces hierarchically layered system structure for development of a system software. This makes the implementation easier by abstracting at each level a part of the system from the higher levels.
c) Introduces the usage of synchonization primitives like semaphores and private semaphores for harmonious co-operation between sequential processes for sharing the system resources between them.
d) Recognizes that delaying the progress of a sequential process cannot affect the logic of the process and introduced a priority based time-sharing on the processor between sequential processes and also guaranteed that no single process can monopolize by using real-time clock interrupts.
e) A method of apriori verification of the system's functioning during design phase is introduced. This appraoch brings logical soundness to the design even before implementaion.
f) The paper stresses on the importance of taking verification and testing into consideration while desinging the System so that a set of relevant tests can be performed at each stage of testing and at the end enough confidence can be gained that no relevant tests might have been overlooked.

Flaws in the Paper:

a) Relies on programs to properly unlock semaphores after releasing a resource. Does not provide a mechanism for controlling malicious or buggy programs from holding resources ( other than CPU ) forever.
b) The technical description of the System structure could have been more detailed providing a few examples like how the state variables along with private semaphores are involved in sharing a peripheral device etc.
c) Performance numbers and data could have been provided to evaluate the final system against initial goals like reduction of turn-around time for programs of short duration , etc.

Relevance of the Paper today:

The paper has introduced concepts that have matured and found their way into modern operating systems.

a) The paper introduces early forms of software based memory segmentation.
b) Concept of layering of the kernel is introduced which is found in modern operating systems like Windows NT and Mac OS X to some extent. ( source : wikipedia)
c) Semaphores remain the primitive synchronization mechanism in many operating systems. The trend in programming language development, though, is towards more structured forms of synchronization, such as monitors. ( source wikipedia - http://en.wikipedia.org/wiki/Semaphore_(programming)#Semaphores_today_as_used_by_programmers )

Summary

The paper proposes a structural design for a multiprogramming system as a hierarchy of mutually cooperating sequential processes. It also describes why this design permits a rigorous verification of the soundness and correctness of the system.

Problem attempted

The author demonstrates the design multiprogramming system with the primary objective of bringing down the turn-around time for programs of short duration. Besides, the author aims to design a system which fails under no circumstance, by making the design lend itself to rigorous verification of its soundness and correctness. A brief description of how such an exhaustive testing can be performed is also attempted

Contributions

1. The paper proposes a hierarchical system that introduces a lot of useful abstractions
a) Level Zero processes processor interrupts and thus hides the processor away for all the higher levels.

b) A segment controller process ensures that information is identified as segments and not pages. The advantage is that dumping of pages to drum is much easier – any empty space is okay and hence the location with least latency can be chosen. What we see today as virtual memory perhaps had its origin here.

c) Level Two ensures that each process sees an individual private console

d) Level Three ensures that peripherals are seen as logical communication units

2. The author demonstrates the power of a hierarchical system by describing the advantage it offers in testing the system. For example, had the processor not been abstracted away and had it been made to respond to any time succession of interrupts, the number of to-be-tested states would have been exponentially high, thus obliterating any attempts at exhaustive testing.

3. The author makes a critical observation to the effect that it is the sequence of events getting executed that matters for correctness and not the relative speeds of the different sequential processes

4. The author introduces the elegant concept of a semaphore for mutual synchronization of parallel processes. This is a very simple and powerful method that is employed even today.

Flaws

Though the proposed structure prunes the number of to-be-tested situations to a large extent, not enough data has been provided to make the strong claim that the system is flawless

Inter-process communication has been completely ignored
Relevance

The paper has introduced so many important concepts in Operating systems like semaphores, virtual memory, preemptive scheduling that are employed in today's systems at a time when the field was at its infancy.

This paper describes a multiprogramming system in which multiple sequential processes coexist. The structure of the system is described as a hierarchy of 6 levels and semaphores are introduced as the way of synchronizing the communication between the processes.

The goal for this research is to process a continuous flow of user programs as a service to the University. The look for a reduction in turn-around time for programs of short duration, economic use of peripheral devices and central processor.

This paper contributes with a hierarchy for the operating system and the introduction of synchronization primitives (semaphores) as way of synchronizing communications between different sequential processes.

The paper talks about the debugging of the system, and how the testing was performed exhaustively level by level from the lower one to the top level. They talk about how a set of relevant test cases should be used for this purpose, but they do never specify what programs are used.

This paper presents a simple and valid hierarchy and a synchronization mechanism that are still valid nowadays.

In The Structure of the “THE”-Multiprogramming System, Edsger Dijkstra described the design and creation of a general-purpose operating system capable of time-sharing CPU's within “a society of sequential processes”. This system, THE, sported many important features found in modern operating systems such as multiprocessing, virtual memory, resource sharing, and standardized buffered I/O.

More importantly, Dijkstra used this experiment to illustrate good approaches to building an operating system that both reduce the complexity of the software and work involved in testing it. In a broad sense, Dijkstra is tackling the problem of managing complexity in large software systems by use of tiered abstractions and vigorous proofs that guarantee the correctness of their operation.

Dijkstra's description of THE contributes a explanation of each abstraction and how it serves as layer that simplifies the creation of code that uses it. For example, he refers to a layer that tracks segments of memory that reside either in memory or “on drum”, automatically swapping them into memory when needed. He then notes that routines above this layer can simply refer to a logical identifier for each segment, greatly simplifying their logic. A proof this virtual memory abstraction is correct allows it to be used in correctness proofs for routines above it, greatly simplifying their correctness proofs.

Ultimately, Dijkstra elects to first abstract away the processors and their clock interrupt, followed by the physical storage details of memory pages, and finally the details of handling peripheral interrupts. He uses semaphores to restrict access to shared resources, but cleverly abstracts the details of this away from processes that read and write to the system console.

This paper has a few weaknesses. Dijkstra enumerates details about the computer his operating system runs on, yet omits information about the performance of THE (even after noting many in industry would view many of his abstractions with skepticism, presumably due to overhead concerns). He also does not expand on how his I/O abstraction could easily be expanded to perform IPC, choosing only to implement/discuss operator-to-process communication. Finally, he spends too much time describing the details of the journey of discovery instead of what he learned from it.

Summary
The paper presents an overview of a structured, hierarchical multiprogramming system as well as what was learned from the efforts involved in the design, implementation, testing, and verification of the system.

Problem
The problem is to implement a sound, verifiable, multiprogramming system so as to provide economic use of computing resources and reduce turn-around time for “short” programs, and in doing so, to advance the field of system design.

Proposed Organization>
The system is strictly hierarchical in nature, which later lends itself to the verification of the soundness of the system. Each level abstracts from and depends on only lower layers. Level 0 is responsible for scheduling of processes, and in doing so abstracts away the processor(s). Level 1 controls the allocation of “segments”, i.e. memory, and in doing so abstracts away the physical “pages” of memory. Level 2 introduces the “message interpreter”, and in doing so abstracts away the console as messages are addressed to a specific process. Level 3 manages buffering of and communication with peripherals, level 4 contains user programs, and level 5 is the operator. The organization makes writing programs using these abstractions easier, but seems to make it difficult to work in anything other than the provided abstractions.

Contributions
Although I cannot with any certainty say which aspects were new or merely improved upon, the paper presents a structured, hierarchical system that abstracts away from lower levels, a pattern than is seen to do this day. In particular, the system abstracts away physical memory, and in doing so, this can allow a program to occupy consecutive “pages” of physical memory without having to know the identity of these “pages.” The structured model allowed for the verification of the system. That is, it allowed for a reasonable number of relevant test cases at each level that could demonstrate that the level in question does what the design says it does. Due to the hierarchical nature as well as the use of semaphores, assuming each level does what it is supposed to, it is then proved that processes work well with each other (e.g. avoid giving rise to an infinite number of tasks, avoid deadlock).

Flaws/Questions
The system may be correct, but does it perform well? Despite that they were able to locate each of the coding errors in the system within 10 minutes and convince themselves that they had tested all relevant test cases, is this approach scalable, especially as motivations other than correctness are very important to industry? If this approach is followed and a coding error is missed, what impact does this have on the reliability and security of the system?

Summary
In this paper, Djikstra talks about a new design for an operating system that is easier to build and can be tested rigorously. He does this by introducing new concepts in storage/processor allocation and a hierarchical design for the system.

Problem
The multiprogramming systems that were being designed in that age had various limitations such as
a. Available memory limited by system core memory
b. All the processes were run sequentially without any switching
c. To finally test a system, the number of possible test cases were very large as each component could have multiple relevant(possible) states.

Contributions
In this paper, he introduces many new concepts that form the basis of many modern technologies.
a. He introduces the concept of virtual memory by using the drum as swap space. Segment ids provide a level of indirection between the pages used by a process and pages actually stored on core memory/drums.
b. Context switch between processes is introduced by pre-empting the processes. It also uses semaphores for synchronizing multiple processes using the same set of resources.
c. Most importantly, he gives a hierarchical design for the operating system that allows for designing and testing the system, layer by layer. This reduces the number of possible test cases from m*n*o*p*... to m + n + o + p +... if each layer has m,n,o,p... test cases.

Flaws
a. He makes claims that his system can be rigorously tested for all possible cases but doesn't give any details on how did he make such an assumption.
b. It has many restrictions on the processes such as no sharing and no machine language code.
c. Djikstra tends to deviate a lot from the subject and talks about his team, the problems faced by their team, mistakes made, so on and so forth which tends to dilute the subject matter.

Relevance
Djikstra's work from this paper seems to be the foundation stone for many currently used concepts such as virtual memory management, context switching, interprocess synchronization, hierarchical systems design. It makes building and testing an OS a lot simpler.

Dijkstra and his students, with the THE System, attempt to answer the question: What is a good way to organize and develop a multiprogramming operating system? At the time of writing (and as may be surmised from his relaxed use of the term), multiprogramming systems already existed and could in fact be bought. Multiprogramming was new, however, and it had evidently introduced complexity which, Dijkstra claims, made system correctness difficult or impossible to verify. His solution to this problem, a new design for an OS, is the core contribution of this paper.
THE resembles what we now call a monolithic kernel, and is organized very strictly in layers of abstraction. By writing the OS in layers and testing each layer in the order of their construction, Dijkstra claims to have made a "flawless" system. Many of the layers chosen by the authors have, in fact, survived the 40 years since their writing in more or less the same form. Virtualization of the processors (layer 0), memory (layer 1), and of devices (layers two and three) are all functions of modern operating systems and are layered in this order. Layered abstraction, itself, is a software engineering technique which now pervades the field because it has been found to make verification a more tractable problem. This paper is still relevant today because it introduces these basic tenets of modern system design.
Dijkstra's claims to the "flawless" results of his techniques, however, have not survived the test of time. Time instead has demonstrated that, as systems become more complex, the difficulty of testing returns and becomes quickly intractable despite continuing efforts at organization. This is evident, as we currently do not have access to a bug-free general-purpose operating system. As systems have grown more complex, generally through the addition of features, performance demands have also challenged Dijkstra's strict layering system. The Windows OS, for example, until the recent MinWin effort, was nearly impossible to reduce in size due to long circular dependencies in the code. THE furthermore makes no provision for malicious or incorrect code (even exposing system-level semaphores to a user process), which are visible problems influencing system design today.
We cannot say, however, that Dijkstra's ideas are misguided even in light of these flaws. Arguably, we still pursue the pureness of his design as part of the ideal system. Rather, the compromises made in modern systems indicate his (and everyone else's) limited perspective on how vastly the role of an OS would expand. As the set of services demanded of a system has grown, the "flawless" implementation has again slipped out of reach.

Summary :
New multiprogramming system is defined in which operating system services like Process Management , Disk Management , I/O management and Device Drivers has been abstracted and defined as sequential processes . A hierarchy structure of these processes is also proposed . This hierarchical structure helps in testing the each sequential process.

Work Summary / Contribution :

1. New structure/Approach for storage allocation is proposed . Terms 'pages' and 'Segment' is defined by author. New approach resolve the issue of consecutive allocation of segments in Drum ( hard Disk ) . Moving information block ( segment ) back to Drum is also faster in this approach . These terms and approach is still relevant in Disk management.

2. Author has abstracted OS services into different sequential process -

Level 0 : equivalent to process management of modern OS architecture .
Level 1(Segement Controller)- file system or Disk Management of modern OS Architecture
level 2(Keyboard and physical console) - I/O management od modern OS architecture
level 3 (Abstraction of peripherals devices) - Which is equivalent to device driver of modern OS

3. Binary Synchronizing Primitive proposed in paper . Binary semaphore proposed in 1968 are still relevant in multiprogramming system . process extensively use these semaphore for synchronization .

Flaws :
1. Interaction among different layer is not very clear. Paper doesn't describe what kind of operation/API are exposed by one particular layer.
2. Core memory management is not defined as one of the sequential process. paper just talk about moving page fro memory to Drum but which page to move .

Summary:

The paper describes one of multiprogramming system, in which the divided sequential processes are placed at various hierarchical levels, the author also describes the design procedure and the objective of the system, the mistakes made in the design process and some testing results.

The problem the paper was trying to deal with:

The paper describes a procedure and result of designing a multi-programming system, the system was supposed to have the following features: (1) a reduction of turn-around time for programs of short duration, (2) economic use of peripheral devices, (3) automatic control Communications and the economic feasibility to use the machine for some applications.

Contributions
1． For storage allocation of “THE”-Multiprogramming System, a new approach was proposed, by which the one with minimum latency time will be selected among the free drum pages, and it also causes that there is no reason a program should occupy consecutive drum pages, which makes multiprogramming environment more convenient.
2． For processor allocation of the system, by realizing the explicit mutual synchronization of “sequential processes”, the whole group of cooperating sequential processes can be independent of the actual number of processors in this system.
3． For system hierarchy, the paper proposes a system with a strict hierarchical structure from level 0 to level 5, and the lower layer is independent to the higher layer.
Flaws
Although testing of the system has done quite well, and a lot of happy results have been achieved, the testing is still not completed yet.
The system is not intended as a multi-access system. There is no common data base via which independent users can communicate with each other:

Summary: The authors of this paper present a layered system approach to developing a multiprogramming system called “THE”. The hierarchical structural and the introduction of pages and semaphores lead to a system design that is easy to test and effectively handles storage allocation, and process allocation of sequential processes.

Problem to Solve: The authors needed to develop a system that was feasible for a variety of applications that made efficient use of disk store and CPU resources while still allowing for the use of peripheral devices and quick turn around time for program completion.

Contributions: One of the largest contributions of this paper is the notion of semaphores; which allows a process to restrict access of certain variables/resources from another process until the original process completes. This led the way for mutual exclusion and private semaphores so that multiple processes could be executed in parallel. Another contribution of the paper is the idea of segments and pages to replace drum pages and core pages (basically abstracting memory). This, for the first time allowed for a process to be contained in a segment which consisted of many pages that need not be in consecutive memory allocation.

Flaws: Although the authors are able to provide logical soundness before implementation, complete testing of the implementation for layers 2 and 3 is not provided but they still stated their system was flawless.

OS Organization Advantages: The layered approach of the “THE” makes design, implementation and testing of the system easier as individual pieces can be constructed and then tested as each is then added to the base. This also allows for easy abstraction, which allows for the simplified communication between layers because the higher level doesn’t need to know the specifics of layer below it. Another important note is that the introduction of pages eliminated the need for drum pages to be consecutive. This makes the system more robust because it is now allowed to use any free memory instead of having to ensure the required resources a process stayed within a given boundary.
Disadvantages Semaphores are an effective way to implement locks on system resources, but if a process “crashes” with a lock in place, it can be difficult for a system to determine it needs to free that lock or re-establish the state of the process so that the process can release the lock.

Summary
The author aims to build an efficient multiprogramming system given limited resources. In doing so, the author describes early fundamentals of multiprogramming systems.

Contributions:
Layers – The system is written in layers so that each may be developed and tested fairly independently of the others, and as a result greatly reduces the probability of weird interactions between systems.
Virtual memory – the paper describes the benefits of using a virtual memory scheme – eg. Space in storage does not need to be allocated sequentially per process.
Mutual exclusion – The paper describes semaphores as a method for ensuring exclusive access by a process to a resource.

Flaws:
One major flaw as I see it is that the author asserts that he has proven his system to work by mathematical proof, rather than by rigorous testing. As the Pentium FDIV flaw shows us, even things that have been “proven” correct can be buggy if the proof is incorrect.

Summary:

In this paper, Dijkstra suggests a method to design and develop a multiprogramming system which processes a flow of user programs. He introduces the concepts of memory segmentation, resource sharing and hierarchical structure of the system. Special emphasis is given on the logical soundness and correctness of the system.

Problem:

The main problem is to find a way to build an efficient and correct multiprogramming operating system that will make best use of the resources and will reduce turnaround time of small programs. In this effort, Dijkstra faces the subproblems of storage and processor allocation and process synchronization .

Contributions:

a) The concept of memory segmentation is introduced. Active processes reside in core pages and inactive processes in the drum memory. Programmers won’t have to use physical locations on the drum memory.
b) He makes the important claim that we can’t make assumptions about the speed of execution of each process when considering the problem of process synchronization.
c) He proposes the use of semaphores for mutual exclusion and ordering of process execution.
d) He introduces the idea of a hierarchical structure of the system that leads to different levels of abstraction,helps prove the logical soundness of the system and facilitates testing.
e) He attempts to prove formally the correctness of the system.

Flaws:

Dijkstra claims that his system is flawless. However, there is no proof to support his statements. He doesn’t present the procedures he and his team used to prove the logical soundness of the system, before testing it. Moreover, he seems not to give enough attention to testing .Today, it is generally accepted that debugging and testing constitute some of the most important parts of the development of an operating system.

The Structure of the “THE”- Multiprogramming System splits up all the operating system activities over a number of sequential processes that are hierarchically developed. This hierarchy of development results in efficient verification which leads to a logically sound and correctly implemented system.

The desired goal for the project was to smoothly process a continuous flow of user programs. In achieving this, the fear of debugging an irreproducible program error became the problem to solve when designing this system. This led to the contribution of a structured system hierarchy that was functionally capable of being tested at each layer to eliminate program errors. The hierarchical design makes it possible to bring the number of test cases to a manageable number to squeeze out the programming errors more efficiently. A flaw with this paper is that it doesn’t discuss measurable differences of using a hierarchical design in relation to a non-hierarchical design in terms of time and program efficiency.

The proposed organization makes debugging more effective. The downfall is that it requires a lot of design preparation. Additionally, the verification at each level is time consuming.

General Comments: To better understand this paper, and it's contribution
to modern OS design, it's useful to know the historical context in which the THE
system was developed. The
wikipedia entry and
this more detailed article were helpful in understanding parts of the paper.

What were they trying to solve: The primary aim of the paper was to come up
with a design for a multiprogramming system, which would allow a single computer
to be used for multiple tasks in a way that the turn-around time for small jobs
could be reduced, and system utilization could be increased.

Contributions: This paper introduces some of the concepts and approaches which are
used almost universally in operating systems today: the idea of a "process" being a
sequential set of instructions decoupled from "real time"; a layered architecture
with clear boundaries which modern OS follow (to some degree); Main memory
virtualization via pages (not sure if this was the first system to do this);
use of semaphores for synchronization between processes.

Flaws: The inability to run binary programs is an artificial restriction
(though one which is necessitated by the lack of hardware paging support); The
lack of shared memory/inter process communication; Its not clear who the
onus of locking/releasing resources is on: if it's the individual process then
there is a chance of a rouge program causing deadlocks; the rather fanciful
claim that the system is "guaranteed to be flawless" is unsubstantiated.

OS Organization: The OS is organized into strict layers, with each layer
communicating only with the layer below it. Advantages: Each layer
abstracts away the underlying detail, which makes developing and debugging
the layers easier. Disadvantages: The specific layer structure would
seem rigid by modern standards.

Summary:
In this paper, Dijkstra describes the multiprogramming system they developed at TU/e. "THE" is a single-user multiprocessor operating system that uses hierarchical layering and mutual exclusion to hide details of resource sharing from the user program.

Problem at hand:
The "THE" system was built to service user programs for TU/e. Main focuses were to maximize utilization of resources, reduce turn-around time for small programs, and allow lighter workloads in an economic manner. Dijkstra's team also aimed to build the system in a manner conducive to verifiability of correctness.

Key contributions:
# "THE" shows a transition from batch operating systems towards multiprocessing ones. Dijkstra's proposition that "delaying a process temporarily can never be harmful to the interior logic of the process delayed" is central to the idea of multiprocessing. "THE" uses clock interrupts to context-switch between processes.
# "THE" introduces an early form of software-managed paging, through the concept of segments which can be mapped to core or drum pages in a manner transparent to the application.
# The use of semaphores to enable mutually-exclusive access to resources is worth attention. It should be noted that since the kernel enforces this mutual exclusion, Dijkstra's arguments towards logical correctness follows through.
# The layered approach towards building the operating system is also significant. Each layer abstracts away some underlying details and presents this abstraction to the layer above so that at layer 4 where programs run, the programs see only a single system where they have total access.
# The paper also describes the use of an incremental testing scheme which allows for more efficient testing, as each layer from bottom up are verified before proceeding to the next layer.

Limitations:
# "THE" has a limited scope executing only user programs written in a variant of ALGOL'60, and with each program blissfully ignorant of the existance of others (No IPC). While within this scope, mutual exclusion through use of semaphores works perfectly, modern systems cannot reliably enforce such mutual exclusion schems and are often confronted with black-sheep processes which flout guidelines.
# Dijkstra seems to under-emphasize the importance of debuggability of operating systems in his statement that "logical soundness can be proved a-priori and it's implementation can admit exhaustive testing."

Relevance:
The "THE" system, albeit dated, is significant because it employs many key concepts which are supreme even in contemporary operating systems. Multi-processing and preemptive scheduling, mutual exclusion etc today are integral to most present day operating systems. The paging scheme used in "THE" has evolved a lot and plays a vital role in supporting multi-processing today. And many operating systems today employ some form of layering to organize the kernel and are often assisted by hardware support for layering.

What it makes easier:
The system increases resource utilization and reduces turn around time of processes thereby meeting the major design goals.

What it makes harder:
No comment.

Summary:
In this paper, Dijkstra describes the multiprogramming system they developed at TU/e. "THE" is a single-user multiprocessor operating system that uses hierarchical layering and mutual exclusion to hide details of resource sharing from the user program.

Problem at hand:
The "THE" system was built to service user programs for TU/e. Main focuses were to maximize utilization of resources, reduce turn-around time for small programs, and allow lighter workloads in an economic manner. Dijkstra's team also aimed to build the system in a manner conducive to verifiability of correctness.

Key contributions:
# "THE" shows a transition from batch operating systems towards multiprocessing ones. Dijkstra's proposition that "delaying a process temporarily can never be harmful to the interior logic of the process delayed" is central to the idea of multiprocessing. "THE" uses clock interrupts to context-switch between processes.
# "THE" introduces an early form of software-managed paging, through the concept of segments which can be mapped to core or drum pages in a manner transparent to the application.
# The use of semaphores to enable mutually-exclusive access to resources is worth attention. It should be noted that since the kernel enforces this mutual exclusion, Dijkstra's arguments towards logical correctness follows through.
# The layered approach towards building the operating system is also significant. Each layer abstracts away some underlying details and presents this abstraction to the layer above so that at layer 4 where programs run, the programs see only a single system where they have total access.
# The paper also describes the use of an incremental testing scheme which allows for more efficient testing, as each layer from bottom up are verified before proceeding to the next layer.

Limitations:
# "THE" has a limited scope executing only user programs written in a variant of ALGOL'60, and with each program blissfully ignorant of the existance of others (No IPC). While within this scope, mutual exclusion through use of semaphores works perfectly, modern systems cannot reliably enforce such mutual exclusion schems and are often confronted with black-sheep processes which flout guidelines.
# Dijkstra seems to under-emphasize the importance of debuggability of operating systems in his statement that "logical soundness can be proved a-priori and it's implementation can admit exhaustive testing."

Relevance:
The "THE" system, albeit dated, is significant because it employs many key concepts which are supreme even in contemporary operating systems. Multi-processing and preemptive scheduling, mutual exclusion etc today are integral to most present day operating systems. The paging scheme used in "THE" has evolved a lot and plays a vital role in supporting multi-processing today. And many operating systems today employ some form of layering to organize the kernel and are often assisted by hardware support for layering.

What it makes easier:
The system increases resource utilization and reduces turn around time of processes thereby meeting the major design goals.

What it makes harder:
No comment.

Summary
In this paper, Dijkstra describes the design and construction of “THE”-multiprogramming system—an operating system designed to process batch jobs. The design for this system introduces such concepts as virtual memory, job scheduling, and resource sharing, all while emphasizing testability and correctness in the design.

Problem
Although multiprogramming systems existed before this paper, a better approach to designing, implementing, and testing these systems was needed since the continued growth resulted in ever more complex systems and an ever increasing difficulty in managing them.

Contributions
• Showing that a multiprogramming system can be designed in such a way that allows for “logical soundness [to be] proved [and implemented in a way that allows for] exhaustive testing” and describing a good way to design such a system.
• Designing a layered organizational structure. Layers only depended on lower layers, allowing proofs about system correctness to be made through induction and for implementation and testing to be performed incrementally, thus simplifying the process since problems could be found and fixed in increments.
• Advocacy for using virtual memory—though it had already been tried before it was not yet completely prominent and Dijkstra helped draw attention to it by describing the benefits.

Flaws
• Lack of attention to testing. Dijkstra specifically mentioned that though “testing had not yet been completed, [the] system is guaranteed to be flawless.” Until testing was actually completed, the correctness of the system should not have been assumed.

Summary: This is a seminal paper ('1968), which developed one of the first (or probably first, no bibliography in the paper) multiprogramming system. It also introduced several new concepts which laid the foundation of the OSes today, particularly multi-layered kernel design, sequential processes, synch. primitives, memory segmentation, etc.

Description: Developed a multiprogramming system with the following layers:
- level 0: processor allocator, real time clock.
- level 1: memory management unit (segment controller)
- level 2: IPC, console management (message interpreter)
- level 3: device I/O
- level 4: application and level 5: user/operator.

Contributions:
- One of the first multiprogramming system.
- Multi-layered architecture with stress on the idea that lower layers are independent of higher layers. On a semi-related note, upcalls are usually avoided in the kernel even today due to possibility of blocking. \cite{Linux Kernel Archive: http://www.ussg.iu.edu/hypermail/linux/kernel/9809.3/0922.html}.

- Synch primitives (semaphores), soft mem. management, logical soundness proofs.
- Idea of processes and their states (2 states: Homing position/idle, and running).
- Livelocks and deadlocks among processes \ref{appendix}.

Flaws:

- Single User Access.
- Finite number of processes and just two states (oversimplified design - though commendable for '1968).
- No performance evaluation figures, except bug density (~1 error/500 lines).
- Static processes, unlike the ones in \cite{Nucleus Paper} where processes can be forked and killed.

Proposed Organization:

- What it makes easier: Seminal paper, introduces ideas which form the semantics of today's OSes.
- What it makes harder: As almost all the ideas are completely novel, hence commenting this is slightly inappropriate. Though, as it is well known multi-layering introduces rigidness in a system, and is also responsible for multiple context switches and copy overheads.

Summary: This is a seminal paper ('1968), which developed one of the first (or probably first, no bibliography in the paper) multiprogramming system. It also introduced several new concepts which laid the foundation of the OSes today, particularly multi-layered kernel design, sequential processes, synch. primitives, memory segmentation, etc.

Description: Developed a multiprogramming system with the following layers:
- level 0: processor allocator, real time clock.
- level 1: memory management unit (segment controller)
- level 2: IPC, console management (message interpreter)
- level 3: device I/O
- level 4: application and level 5: user/operator.

Contributions:
- One of the first multiprogramming system.
- Multi-layered architecture with stress on the idea that lower layers are independent of higher layers. On a semi-related note, upcalls are usually avoided in the kernel even today due to possibility of blocking. \cite{Linux Kernel Archive: http://www.ussg.iu.edu/hypermail/linux/kernel/9809.3/0922.html}.

- Synch primitives (semaphores), soft mem. management, logical soundness proofs.
- Idea of processes and their states (2 states: Homing position/idle, and running).
- Livelocks and deadlocks among processes \ref{appendix}.

Flaws:

- Single User Access.
- Finite number of processes and just two states (oversimplified design - though commendable for '1968).
- No performance evaluation figures, except bug density (~1 error/500 lines).
- Static processes, unlike the ones in \cite{Nucleus Paper} where processes can be forked and killed.

Proposed Organization:

- What it makes easier: Seminal paper, introduces ideas which form the semantics of today's OSes.
- What it makes harder: As almost all the ideas are completely novel, hence commenting this is slightly inappropriate. Though, as it is well known multi-layering introduces rigidness in a system, and is also responsible for multiple context switches and copy overheads.

Summary: This is a seminal paper ('1968), which developed one of the first (or probably first, no bibliography in the paper) multiprogramming system. It also introduced several new concepts which laid the foundation of the OSes today, particularly multi-layered kernel design, sequential processes, synch. primitives, memory segmentation, etc.

Description: Developed a multiprogramming system with the following layers:
- level 0: processor allocator, real time clock.
- level 1: memory management unit (segment controller)
- level 2: IPC, console management (message interpreter)
- level 3: device I/O
- level 4: application and level 5: user/operator.

Contributions:
- One of the first multiprogramming system.
- Multi-layered architecture with stress on the idea that lower layers are independent of higher layers. On a semi-related note, upcalls are usually avoided in the kernel even today due to possibility of blocking. \cite{Linux Kernel Archive: http://www.ussg.iu.edu/hypermail/linux/kernel/9809.3/0922.html}.

- Synch primitives (semaphores), soft mem. management, logical soundness proofs.
- Idea of processes and their states (2 states: Homing position/idle, and running).
- Livelocks and deadlocks among processes \ref{appendix}.

Flaws:

- Single User Access.
- Finite number of processes and just two states (oversimplified design - though commendable for '1968).
- No performance evaluation figures, except bug density (~1 error/500 lines).
- Static processes, unlike the ones in \cite{Nucleus Paper} where processes can be forked and killed.

Proposed Organization:

- What it makes easier: Seminal paper, introduces ideas which form the semantics of today's OSes.
- What it makes harder: As almost all the ideas are completely novel, I believe commenting this will be inappropriate.

Objective of the paper:
The authors aim to conceptualize and build multiprogramming system which should be able to service continuous flow of user programs in an efficient and cost effective way. The work gives us design fundamentals of early multiprogramming systems.

Contributions and relevance/ Work summary:

The system's design has three major focal points, namely the design of storage systems, processor allocation and its hierarchical structure.
In terms of storage system it introduced a level of indirection in addressing a particular data by the process. This allowed data to be loosely bound to its actual physical location and thus helping in better performance of storage system. More over this helped to tide over the data fragmentation problem by not requiring related data to be placed physically consecutive addresses. This concept later evolved in paging schemes of today.
It also introduced the concept of sequential process as time succession of states with a logical binding, irrespective of actual time units required for performing the task in the process. It also introduced a totally asynchronous system where various processes can be made to synchronize with respect to each other through explicit mutual synchronization ( e.g semaphores).
The system has been designed following strict hierarchy, where details of a lower level is abstracted away on all the upper layer of it. Lowest level ( level 0) handles processor allocation to the processes. while next higher level ( level 1) provides layer of indirection for memory addressing( called "segment controller"). At level 2, "message interpreter" facilitates conversation between operator and higher level processes. At level 3, I/O abstraction/buffering is implemented. In level4 and 5 there are independent user programs and operator, respectively.
Apart from these fundamental concepts the paper indicates towards possible challenges in designing a system, which is still relevant even after four decades. It correctly points "debugging" as one of the main challenges, especially in the presence of non-deterministic interrupts that make re-production of an error tough. This problem has taken enormous shape in context of today's multi-core systems and parallel programming paradigm, where non-deterministic races are tough to debug. Moreover it shows the ease of verifying a hierarchical/modular systems as well.

Possible Flaws/ avenues of improvement:

It seems although there is fairness in processor time sharing there is no fairness in sharing of peripherals among processes. A process can hold on to a peripheral as long it wants.
The system looks too restrictive in the sense that it allows only programs written in ALGOL. It also does not allow any kind of inter process communication.

The author, Edsger W. Dijkstra, presents a multiprogramming system named THE and his experience as a leader of the design team.

I identify four contributions: The first one is the introduction of semaphores (in the appendix) as a method of achieving synchronization of processes. The author demonstrates how the semaphore construct can enforce mutual exclusion and can implement a barrier. Another contribution of the paper is the proposition of a hierarchical structure of the system: each level in the hierarchy only interacts with the level underneath it and is unaware of the implementation details of the levels below that. A direct gain from that design is the ability to provide abstractions to the higher levels of the hierarchy. The proposed system takes advantage of that by abstracting storage resources away and providing memory segments to user programs, instead of drum locations. The system can decide where the segments will be placed in the drum. Finally, the system design methodology has strong mathematical foundations: first create a model, then prove the model right, then program the system so that it conforms to the model. Therefore the correctness of a system can be formally proven.

One flaw of the presentation is that although the author states that they designed the system first on paper and proved it correct before programming, there is no evidence to support this claim. Even a description or a reference to the formal model and the algorithms they used to prove correctness is lacking.

The proposed system architecture allows each level to provide abstractions to the layers above. This has the important property that testing can be done in a limited and well-controlled way. Also this design enforces different spheres of control, allowing the possibility of isolation and control between code that runs in different levels in the hierarchy. An undesirable consequence of this decision is that direct access to hardware is prohibited, unless the underlying level in the hierarchy provides abstractions for it. This is less of a problem today that the interfaces are well standardized, but could prove prohibitive for the commercial success of a system back in the 60's.