CS 736 - Spring 2007 - Paper Discussion

Here's a link to the Story of Mel that was mentioned in class today about an optimized blackjack program on a drum memory machine:
http://www.cs.utah.edu/~elb/folklore/mel.html

Summary:
Dijkstra mainly concerns himself with chronicling the "THE" team's progress in designing one of the first batch processing operating systems. By designing such a novel system, Dijkstra and his team stumble upon core operating system design problems, and then they come up with solutions that are largely in use today.

Problem:
The "THE" system had to "smoothly" process a flow of user programs on limited hardware. Addressing this problem elegantly meant that the team had to address sub-problems such as API design, memory management, and execution order.

Relevance:
"THE"'s solutions to the above problems became fundamental tenets of operating system design. Dijkstra's paper introduces a primitive form of virtual memory, the concept of semaphores, a form of protection rings, and his attempts to logically verify the correctness of "THE"'s hierarchical design hint at API design.

Evaluation:
Dijkstra is pretty bad at detailing how "THE" was evaluated. We are left with happy anecdotes about extensive testing, enabling successive layers, and so on. Dijkstra then teases us with the claim that "THE"'s memory management is so amazing that the storage mechanism can fail entirely and the system will still work.

Cool Ideas:

• Program correctness is entirely dependent upon the sequence of execution. The speed of the execution is irrelevant.
  
• Corollary to the above: multi-tasking made possible by introduction of semaphores.
  
• Attempting to logically prove that the system will work flawlessly.
  
• Primitive virtual memory
  
• Generally abstracting the hardware into a black box.
  

Nits:

• I could have done without Dijkstra whining in the introduction.
  
• Dijkstra makes some pretty astounding claims without providing much information or data confirming his statements. Perhaps that is due to this paper being a progress report, still...
  
• I am not used paper authors ranting in their papers!
  
• Their evaluation of "THE" leaves a lot to be desired.
  

All in all, an amazing and even entertaining paper.

Summary:
This paper suggested design of a multiprogramming system. It proposed the ideas of memory paging, the relocation of inactive process from main memory into the storage, hierarchical jobs, and mutual exclusion. These novel ideas of the time are still in use today.

Contributions:
- The paper divided processes into hierarchical jobs, and made each process independent of each other.
- The paper proposed the “Synchronizing Primitives” to implement explicit “Mutual Exclusion”, the mechanism for preventing different processes access to the using resources.
- Processes could run parallel as a result of aforementioned methods.
- The author invented new technique in organizing memory instead of using core memory as an index to a process location on drum; he put the an active process into core memory while removed inactive one from main memory to the drum. . This technique, memory paging, makes the short process run faster.
- The concept of small independent processes, mutual exclusion, memory paging creates better environment for multiprogramming and yields better performance.

Flaws:
- In the proving the Harmonious Cooperation, the writer claimed THE system lacked of "circular waits" (deadlock) by refering to A.N. Haberman's work. However, we have found that the proposed mechanism not enough for preventing the deadlock.
- The writer spent so much space complaining about his research limitation and lost his focus to make his research an efficient "process." It is possible that writer want to implicitly compare his working environment to the system designed.

Dijkstra talks about the design and development of a multi programming operating system, which he named "THE-Multiprogramming System". The system was designed for a specific hardware, and employed (now-)primitive versions of virtual memory management, multi-process synchronization and process hierarchy.

Problem:
To create a multi-programming system that provides automatic storage control and makes best use of processor and peripherals, with a special focus on shorter programs for which flexibility was more important than power of computation.

Contributions:
The paper presents a number of concepts that are still used in modern operating systems (though in more refined way)
+ A new storage allocation mechanism was proposed and used: dividing memory and secondary store to pages, and filling them with information units called segments. Segments had special identification mechanisms that allowed them to be read-from or written-to any available memory or drum pages.
+ A new processor allocation scheme, which seem to be the first implementation of pre-emptive (he uses the word 'undefined speed ratio') scheduling.
+ Exclusive use of synchronization mechanisms, like semaphores to ensure proper operation of multiple processes accessing shared peripherals
+ Employment of hierarchical process structure, where the lowest level (or the root of the hierarchy) providing the most basic functions to the higher levels.

Flaws:
- Though the paper is mostly about "THE system", it wanders in some needless topics - about team selection, software development practices and testing.The author spent a considerable time/space describing Semaphore operation, which is just a part of the whole picture. Could have a been more focussed on "THE system".
- The paper understates the usefulness of debuggabilty of the system. It is widely accepted today that this is a critical feature for the development and extension of OS (testing different hardwares, testing algorithms for scheduling, memory management etc)
- There are some claims which are not proven, like 'system will be flawless'. Granted, It is comparitively easy to develop such a system when the underlying hardware is just one (which is the case here, as opposed to tens of hardware that most common operating systems support); but it is quite impossible to implement a system with no flaws even if it is backed by a robust design.

Relevance:
As mentioned above the paper presents many concepts that are being used even in modern operating systems. These include the hierarchical process architecture, multi-process synchronization mechanisms including semaphores, and memory management.

Dijkstra talks about the design and development of a multi programming operating system, which he named "THE-Multiprogramming System". The system was designed for a specific hardware, and employed (now-)primitive versions of virtual memory management, multi-process synchronization and process hierarchy.

Problem:
To create a multi-programming system that provides automatic storage control and makes best use of processor and peripherals, with a special focus on shorter programs for which flexibility was more important than power of computation.

Contributions:
The paper presents a number of concepts that are still used in modern operating systems (though in more refined way)
+ A new storage allocation mechanism was proposed and used: dividing memory and secondary store to pages, and filling them with information units called segments. Segments had special identification mechanisms that allowed them to be read-from or written-to any available memory or drum pages.
+ A new processor allocation scheme, which seem to be the first implementation of pre-emptive (he uses the word 'undefined speed ratio') scheduling.
+ Exclusive use of synchronization mechanisms, like semaphores to ensure proper operation of multiple processes accessing shared peripherals
+ Employment of hierarchical process structure, where the lowest level (or the root of the hierarchy) providing the most basic functions to the higher levels.

Flaws:
- Though the paper is mostly about "THE system", it wanders in some needless topics - about team selection, software development practices and testing.The author spent a considerable time/space describing Semaphore operation, which is just a part of the whole picture. Could have a been more focussed on "THE system".
- The paper understates the usefulness of debuggabilty of the system. It is widely accepted today that this is a critical feature for the development and extension of OS (testing different hardwares, testing algorithms for scheduling, memory management etc)
- There are some claims which are not proven, like 'system will be flawless'. Granted, It is comparitively easy to develop such a system when the underlying hardware is just one (which is the case here, as opposed to tens of hardware that most common operating systems support); but it is quite impossible to implement a system with no flaws even if it is backed by a robust design.

Relevance:
As mentioned above the paper presents many concepts that are being used even in modern operating systems. These include the hierarchical process architecture, multi-process synchronization mechanisms including semaphores, and memory management.

Nuri Eady

Summary
Described in this paper is the design process of a system used for running multiple programs in a timesharing manor while enforcing resource sharing. The system organization is explained and a lot of emphasis is put on the structure and scheduling of the project.


Problems explored
The main issues addressed with the design of this system are 1) reduction of turnaround times for short jobs. 2) economic use of the peripherals and 3) effective use of the backing store and the processor. In a batch of jobs run sequentially long jobs tend to create high response times for shorter jobs waiting behind the long job. Generally the ability to schedule a short job before or during a longer job is advantageous. Also when running a single job at a time peripherals or the processor may not be used effectively since a process tends to use only a single resource at a time (processor, backing store, ect.).


Contributions
There appear to be several contributions in this work that are still wildly used today. A variant of memory paging has been implemented that helps in sharing of memory between several different processes. Also implemented here is an early scheduling protocol that enforces mutual exclusion between processes and reduces the latency of short running jobs. The layered approach to the system is also very important when dealing with more complex systems and is used wildly today. The ability to create different levels of abstraction facilitates things from easier testing and verification to more understandable programs. Finally aspects of the testing regiment were very significant. Namely fully testing each level of the system before building the next. This leads to more assurance in the end that the whole system will function deterministically.


Flaws
The small amount of emphasis that was put on debugging seems like it could become an issue. The author argues that this forces the designer to put a lot of effort into building a machine that is bug free and in their case it turned out ok however designers may not always be able to perceive all the issues that may arise in a system and if bugs due occur determining where they are could be a nightmare. Especially as systems become more and more complex debugging support becomes more important.


Relevance
The ideas of memory paging, processor scheduling, several layers of abstraction and hiding of lower levels of the system from higher levels are all very important ideas that are widely used in systems today.

Mr. Dijkstra presents his thoughts about efficient R&D practices (mainly the use of abstract layers, along with the avoidance of scope creep) and technical achievements (a novel paging system and sequential processes) from a recent system development.

The problem was creating a system to execute user programs with very limited time and resources.

Contributions:
-The first few pages of the paper listed a number of tips for system developers. Including: seek highly-skilled full-time developers, avoid scope creep, focus on the big picture, plan for debugging.
-Next a unique storage approach was briefly described. Pages in memory were mapped to segments on the drum, which allowed pages to be written to any location on disk.
-Processes were designed so they could be run independently of each other. Sequential bits of code were controlled using mutexs and clock interrupts. It is unclear if the idea of using a mutex is also a novel contribution of this article.
-Sequential processes were devided into a hierarchy with each level responsible for a set task. In this way levels did not need to concern themselves with the details of lower levels. For example the segment controller can operate without worrying about processor allocation and clock interrupts. Abstracting away lower levels allowed for incremental testing of each level. Once level 0 was verified, the testing for level 1 functionality can focus on new features at level 1 without worrying if level 0 features are working correctly.

Flaws:
The paper is disguised as a discussion of efficient programming approaches, when in fact it contained mostly technical concepts. The paper begins by illustrating Dijkstra’s reason for writing the paper, to answer a call for papers on timely research and development efforts. After a short list of suggestions for the programming looking for better efficiency the paper quickly switches to technical details. Even the end of the first page lists the specifications of the computer used. The misclassification of the paper is unfortunate for two reasons: 1) The wrong audience likely read this paper (programmers interested in efficiency, not algorithms) 2) The efficiency tips listed used space that could have better elaborated the concepts.
At times the paper made claims so extreme that lead me to question the justificaiton behind some of the paper’s other claims. Such as: “the testing had not yet been completed, …system is guaranteed to be flawless”. Even if Dijkstra showed “Harmonious Cooperation” the system is far from guaranteed to be flawless. Also the stance against black box testing seemed severe with little justification for the statement provided.

Paper Review: The Structure of the "THE"-Multiprogramming System [Edsger Dijkstra]

This paper is a brief report on a multi-tasking operating system named
"THE", for "Technische Hogeschool Eindhoven" - the university at which
it was implemented in the late 1960s on the Electrologica X8 computer.
This operating system was organized into five levels that helped to
verify its correctness, simplified its implementation and testing, and
contributed to virtualization or abstraction of the hardware for user
programs.

Dijkstra and his mathematician team's goal was to contribute to the art
of system design by building an advanced operating system as an
ambitious project. The system was to process a continuous flow of user
programs, written in a modified version of ALGOL 60, by multi-tasking so
that (1) it could turnaround short programs quickly, (2) it would make
economical use of peripheral devices, (3) automatically control backing
store (manage memory) and processor economy, and (4) to run applications
that required a general purpose computer, but each not needing its
entire capacity.

This work's contributions include:

THE had an early virtual segmented memory system that has system and
user processes access memory segments that map to pages in real memory.
This also enables performance increases by storing segments to be moved
to more optimal locations.

The author offers system design guidance: Too much time can be wasted on
trying to create a "perfect" system, such that one might overlook
designing how to deal with common failures, such as for some of its
component parts.

Since operating systems are hard to debug, especially since the
conditions to reproduce a problem require precisely replaying arrival
times of interrupts and such, the soundness of its design should be
verified before implementation and development is best done
incrementally and modularly.

Lower foundation layers of the operating system including scheduling and
preemption (level 0), memory management (level 1), operator control
(level 2), and I/O (level 3), can be prioritized in approximately that
order to reliably provide virtual functionality to user processes (layer 4)
that run on a somewhat virtual machine that those lower layers provide
atop the physical hardware.

This work's possible short-comings include:

The THE operating system project was modest in that it was not a
multi-user system, even though it was meant to serve many University
users. It could be asked to run multiple user's programs, but the
system had no database of user's identities nor their respective
privileges.

In hindsight, it is now clear that an operating system's design need not
be formally provably correct in order for it to be functional, as there
are many reliable operating systems that came from diligent design and
implementation.

While some sort of correctness measure would likely avoid basic design
errors, perhaps it is poor implementation management and feature-creep
that make modern operating system development most challenging. For
instance, operating system design flaws, such as early Unixes' short
file names, unreliable signal handling, or small number space for
user-ids, might not have been proved incorrect because they are only
design flaws under newly evolved application requirements.

Related references:

THE multiprogramming system
http://en.wikipedia.org/wiki/THE_multiprogramming_system

The Electrologica X1 and X8 computers
http://www.science.uva.nl/faculteit/museum/X1.html