CS 736 - Spring 2007 - Paper Discussion

The paper states the challenges that multiprogramming aims to resolve and provides a plausible solution to these challenges. The main challenge being the ability to fully utilize the given hardware and the sub goals being tackled to solve this issue are; efficient sharing of files, effective resources management, and safety (isolation of process to prevent undesired interference).

The main contribution that the paper makes are;
*protection of segments on a per-segment basis
*a capabilities list to control access to all of system resources.
*the supervisor, core of the msc, that handles resource management, scheduling, and exceptional conditions.
*the ability for a parent process to prepare and customize the environment for it's child process
*an admirable but flawed file system.

The file system is flawed for several reasons; the inability to rename files is an automatic strike against it, as is the inability to truly delete files. The complicated hand-shake, sharing mechanism, that needs to occur between the borrower and lender of a file (if the F indicator is off) seems highly unnecessary. Perhaps it would be clearer if the directories stored more protection/capability information about each object, this way the system need only consult the directory once and there would be no need for a complex handshake. I realize that the state information for the capabilities could get quite large but the groups mechanism could be leveraged.

Summary:

The paper by Dennis and Horn presents various “meta-instructions” which can by used by the programmer to achieve parallel processing in multiprogrammed computer systems. These instructions provide features such as protection mechanism, program debugging and data sharing between processes.

Problem Description:

The paper addresses the issue of having an architecture that supports multiprogramming, which supports parallel processing. In the authors’ time frame, multiprogrammed computer systems are going to be prevalent soon. Hence, there needs to be a way to utilize this idea of concurrently executing tasks, without any unwanted interferences or interruptions.

Contributions:

1) Concept of Segments, Protection and Processes. The paper introduces the concept of segments, which is a collection of ordered set of words. This definition is similar to the one we use currently for segments. Protection mechanism is also introduced by using a “list of capabilities” or C-list. This idea is very novel and is still used in today’s systems. Finally, the definition of processor and processes is presented in the paper. Again, these definitions are well described and are still prevalent in today’s technology.
2) Supervisor. Supervisor is part of the computer’s core that implements various system functions. These include allocation and scheduling of computing resources, accounting for and controlling the use of computing resources, and implementing the meta-instructions. The idea of giving one entity the control of system resources so that it can distribute it fairly among processes is original. Although no details are presented on the workings of the supervisor, we can get an idea of what the supervisor’s tasks are and what role it plays in the overall workings of the system.
3) List of meta-instructions. The rest of the paper describes various meta-instructions (instructions written in a language midway between an assembly language and an advanced algebraic language), with a few examples given to utilize them. The list is although not complete, it is still pretty thorough and shows that the authors thought a lot about the various scenarios possible in a multiprogrammed environment. Instructions such as fork and join are still used widely. There’s also the synchronization instructions that authors present, called lock and unlock instructions which are used when sharing data object between multiple processes.

Flaws:

One of the flaws I found was that the paper tried to cover so many topics that it failed to go into details for any of them. We are told that the supervisor will implement the meta-instructions, but the implementation of the supervisor is not presented at all. The algorithm used by the supervisor to schedule the resources among various principals and the method of accounting are some of the things the authors could go into more detail. Another problem with the paper is that the case of deadlock is not considered when describing locks. There is a time limit that the authors talk about, but what happens after the time limit expires? Do we have a processor state saved at the beginning of the lock so that we can roll back to it? Who sets the time limit? How do we set it? These are just a few of the questions that remain unanswered by the authors.

Relevance:

This paper was published in 1966 describing various concepts needed for parallel programming. Most of these are still widely used. Although the paper didn’t go into details of the exact implementation of the meta-instructions, we still get a basic idea of how they were intended to work, which is very similar to today’s working models. The idea of capabilities to implement protection is very novel and even used in some of today’s OS.

Summary
Dennis and Van Horn investigate existing "multiprogrammed" systems (SABRE, some NASA system, and Project MAC) and attempt to define an API that all multi-user, multiprogrammed systems require. The authors also describe several methods for preserving the efficiency of the system: segment permissions, exception handling, and a file system designed to eliminate redundancy.

Problem
The problem was determining the set of functionality required by a true multi-user MCS.

Contributions

• Access controlling mechanisms, including the idea that child processes inherit some permission subset from parent processes.
  
• Using kernel-level system calls to enable parallel processing.
  
• Rudimentary exception handling.
  
• Hierarchical file system that allows multiple users to share the same... files while preserving access permissions.
  

Criticisms

• There was no evaluation in the paper. How are we supposed to know if these ideas merit further research?
  
• The authors have multiple definitions for segments.
  
• The segment delete method seems like a form of reference counting. This would become a burden as your number of segments increases.
  
• Corollary to the above: the authors essentially admit that they don't know what to do when the original segment owner deletes a file being used by other "principals."
  

Summary:
The paper is about defining a set of meta instructions that would be helpful in a multiprogrammed computer systems. These meta instructions (or programming primitives) are for parallel processing, protection of processes, debugging and sharing of resources.

Problem:
Though multiprogramming systems were getting popular, most programming languages at the time of writing the paper lacked meta instructions to do very useful parallel programming tasks. These tasks included concurrent operation of processes (possibly for multiple users), naming objects (so they can be uniquely addressed by multiple computations/processes), management of resources (varying demands for memory, peripherals, etc), sharing of information/resources between processes and protection of processes and their resources. The paper proposes a set of meta-instructions to perform these activities while not going to implementation details and staying at intermediate level of programming (between assembly level and high-level).

Contributions:
- Concept of "sphere of protection" for preventing unauthorized access to objects using what is called a "list of capabilities" or "C-list".
- A "Supervisor", which is a combination of hardware and software elements, that performs resource allocation and scheduling, resource accounting and implements the meta-instructions.
- Definition of meta-instructions to manage processes (fork, join, quit, etc), synchronization (lock/unlock), i/o operations, debugging (creating "inferior sphere", granting "capabilities" and permissions, etc), protected entry points (like "system calls" of modern operating systems - switching to kernel mode and returning to user mode) and unique naming of objects through hierarchy (directories) to enable sharing.

Flaws:
- Though many ideas in the paper sound practical, there is no mention of creating a system/prototype of the ideas presented on the paper. It is not clear if it was ever done or any kind of evaluation performed.

Relevance:
Ideas persented in the paper like Process management primitives, spheres of protection, etc are still used in modern operating systems. The paper gives a good insight to the evolution of multiprogrammed systems, though none of the ideas are covered in much of a detail.

Summary:
This paper proposed the framework for “multiprogramming computation”. It showed characteristics of multiprogrammed computer systems (MCS) and the benefits of MCS that enable concurrent processes to share resources effectively. It suggested some basic ideas, fundamental commands, protection mechanisms, and file system required for MCS.

Problem:
The paper tries to establish the guideline for OS design in MCS that process multiple “computations” and multiple processes simultaneously.

Contribution:
- The ideas of grouping processes with the same C-list to create a “computation” and access indicators simplified MCS and gave the foundation for future work on MCS
- The concept of protection sphere for each computation and inheritance of the privilege defines how the MCS should function and provide the synchronization and protection for each process/computation to enable multiprogramming environment.
- Although inefficient (will be explained in flaws), the file system that let other access the same file with different name and privilege is an excellent idea in solving name conflict for each “principal” and a good way to share the media.

Flaws:
- The paper admitted that deadlock might occur and claimed to have small possibility for such an event. However, it state neither solution to fix this nor evidence to support its claim.
- The file system seemed to be complicate that every principal has his own root directory and file structure. In my view, UNIX file system is simpler for sharing resources and yields more performance.

SUMMARY

"Programming Semantics for Multiprogrammed Computations" by Dennis and Van Horn describes a framework of operation designed for multiuser computers. Topics include definition of basic conceptual building blocks (e.g. segments, processes, process supervisor), memory organization and protection, parallel programming primitives, including synchronization, i/o, spheres of protection, exception handling and filesystem.

---------------------------------------------

PROBLEM

Abstract design of a multi-user OS. How should a multi-user system be defined? Which properties should guide the design of a multi-user OS? Which features should be provided by the system? How should those features interact? How should those features be implemented?

---------------------------------------------

CONTRIBUTIONS

A coherent and complete, fairly abstract design of a multi-user OS for a well-defined specification. It is difficult to say which concepts from this paper are contributions in the sense of being novel ideas. If nothing else, the paper presents a detailed, though high-level system design. The paper discussed the following topics: definition of basic conceptual building blocks (e.g. segments, processes, process supervisor), memory organization and protection, parallel programming primitives, including synchronization, i/o, spheres of protection, exception handling and filesystem.

---------------------------------------------

FLAWS
Although the authors list the "properties of multiprogrammed computer systems" that they aim to satisfy, no design philosophy (e.g. simplicity) is made explicit.

The authors seem too willing to create system-imposed restrictions for the users. E.g. in discussion of ambiguous names they mention restricting the structure of file names, without much justification for it. Such decision may become detrimental for the system and its users in the future and the authors do not address that issue.

The paper seems poorly organized and not very well written. More diagrams would be helpful.

It is difficult to critique system components without knowing limitations the authors designed for and the workloads they expected to face. Without such contextual information it is almost impossible to judge which design desicions were poor, and which were good enough.

The authors offer too little insight into why they made their choices, and do not explore alternatives. With that it is hard for a reader to learn from good and bad choices that were made.

No evaluation. The paper's content impresses, given the date of publication, but lack of evaluation, even if it is justifyiable weakens a paper.

I am not sure that the authors chose the most effective level of abstraction to present their ideas. In my view discussion of concepts (e.g. memory capability of filesystem) and implementation pseudo-code should have been separated more in the text.

I fail to see the main big idea/insight/observation of the paper. This diminishes long-term value of the paper to a reader, except as a reference.

---------------------------------------------

RELEVANCE

Many of the concepts discussed in the paper are still in use today, which others could be used to better understand the evolution of various ideas. to me, the paper is merely of historical interest. If the goal is to understand inner workings of an OS, better texts are available.

Summary
In this paper the authors introduce key concepts of a Multiprogrammed computer system, drawing from existing systems and introducing new concepts. Areas discussed include parallel processing, naming objects of computation, and "protectin of computing entities from unauthorized access"
Problem
Design a system that can be shared by several users running lots of different programs at once. These concepts were completely new at this point and they didn't quite know what they wanted to do.

Contributions
* introduction and definition of terms (segments, words, spheres of protection, c-list, processes, computations, principals
* Discussion of the supervisor and the associated functionality both for distributing resources and accounting for their usage.
* Discussion of parallel programming/threads with fork, quit and join commands, and lock/unlock commands to deal with data sharing.
* Inferior spheres of protection, the idea that a processes resources are allocated by another process which has access to all of the resources assigned to it, along with debugging capabilities.
* Directories and naming: Each principle has their wn hierarchy of files, with a mechanism for sharing

Flaws
I do not know if these can properly be considered flaw, but alot of the abstractions here seem to be more complex than in other systems. UNIX for instance is much cleaner. The file system hierarchy is one example of this.

Also the paper is somewhat unclear on what comes from existing systems, what is a new idea, and what has been tested and what has not been tested. No comparison to existing systems was done.

Summary:
In this paper, the author discuss the design of “Multi-programmed computer system” (MCS) by describing the outline of a combination of key concepts that can manage multiple processes running concurrently, handle resources correctly, and enable to manage files in a hierarchical directories with access control.

Problems to Solve:
The author proposes at the begging of the paper that MCS should include features such as Concurrent Processing, Resource Sharing, Protection, and Flexibility that could handle dynamically changing needs. They did not have a system that could satisfy their requirements and a new system with well organized features was needed.

Contributions:
First of all, organizing and sorting problems of current systems (at that time) and requirements of capable system for multi-programming environment (which is much more like current systems) including the idea of capability for future change in simple and clear way was valuable.
I am not sure about which key feature is completely new in this paper, but combining, organizing, improving functions is important. For example, providing interfaces that enables managing accessibility of processes and files by using hierarchical architecture of process and segments including access control and mutual exclusion connects to the characteristic of UNIX that enables multiple tasks (“computations”) processed concurrently.
Also, Hierarchical Structure of files using Directories, solving naming problem by using principals’ name (user name) creates a well organized data structure. But this file system like structure still needs some improvements and I guess it is improved a lot at the previous paper.
As a whole paper, I felt that the design of system proposed has more weight on ideas such as access control, security, safety rather than performance or efficiency.

Flaws:
Like the previous paper, even it is difficult to evaluate the system, I thought it might be easier to grasp the strength of the system by clarifying the difference between designed MCS and current systems.
The way that Directories’ hierarchy are organized based on principals (users) might be little complicated if there are many applications, services, and users were added later on.
I think it is a difficult decision were to place the line between the programmer and system, but I guess there are still some more that system can do for lock and unlock (mutual exclusion). It can stop multiple access or at the same time, but still the way they avoid dead lock by restricting the API increases the responsibility of programmers and it could be managed by the system like UNIX.

Summary
This paper is primarily an analysis and summary of techniques used to facilitate multi-programming. Certain ideas have been taken from systems that have been implemented and a number of new ideas are added to create a more complete package suited for a multi-program, multi-user system.


Problems explored
Many of the problems associated with systems that must run multiple processes and service requests from multiple users are explored. Some of the properties common to multiple programming are as follows... 1) Concurrent operations for multiple users. 2) Computations share a number of resources among processes. 3) Different computations can vary widely in the types of resources needed. 4) Multiple processes may reference common data. 5) The system must be able to adapt to changing requirements. All of these properties that are common to multi-programming systems have potential problems and issues which are addressed in this paper.


Contributions
Some interesting features that were spoken about include the memory protection scheme that appears to be a variant of the current scheme used in unix . Also the use of a supervisor process that would implement a set of core system functions that take over control on occasion to provide a specific function is an important idea that persists today. Processes are protected from each other by creating spheres that each process runs within. The spheres have a capability list associated with them them that contains pointers to objects that the sphere has access too. If a sphere attempts to access an object or capability that it does not have access too the system will intervene to prevent access. I found the discussion of the reasoning behind a hierarchical naming structure for the file system interesting. Creating the hierarchical structure that we are so accustom to today can prevent many naming problems that can arise especially when multiple people use the system.


Flaws
Locks are used for mutual exclusive access to data and a bit of thought is put into situations where deadlock could occur however it seems as though problems where multiple locks are used is not fully developed and needs more thought in order to guarantee forward progress of the running processes. A lot of the paper is also quite theoretical and besides the parts spoken about that have already been implemented in other systems much of the work appears to be untested. The ideas proposed I would suspect were quite novel at the time but additional work to implement parts of the system would have been nice to see.


Relevance
Many of the ideas discussed in this paper are relevant today and some are even more so now that multi-threaded applications are becoming popular to take advantage of multi-processor or multi-core machines. The ideas of process protection, process management (eg. fork and quit), mutual exclusion, and a file system hierarchy are all ideas that have proved to be sound and are used in modern systems.

Summary

In this paper, the authors present a parallel programming model along with the programming semantics. Initially, the authors discuss review some properties of a Multi-programmed Computer System (MCS). Then they define various concepts and terminology that are proven useful in studying the properties of a multi-programmed model. They also present the concept of a scheduler which they refer to as "The Supervisor". Afterwards, the authors discuss various parallel programming semantics "meta-instructions" that they introduced in this paper. Towards the end, the authors present various protection issues and they also discuss the directory structure and naming that they propose for their multi-programming model.

Problem Description

The authors claim that even though there a several programming languages available, they lack important features required to implement computations (a collection of processes working together on the same problem or job) in an MCS. These features relate to parallel processing, naming objects of computations, and protection of computing entities from unauthorized access. The authors propose a set of meta-instructions in order to provide these features.

Summary of Contributions

Some of the contributions of this paper are outlined below.
1. The paper presents the idea of a scheduler which is referred to as "The Supervisor". The Supervisor maintains a list of each process that exists in the system and it is responsible for scheduling a process and allocating resources to it. The Supervisor is also responsible for accounting various resources used by a process so that later on users of the system can be charged.
2. A number of parallel programming semantics are presented in this paper. A new process can be created using a "fork" meta-instruction. Another interesting instruction is "join" using which main program can wait for all its child processes to finish before proceeding any further. The authors introduce "locks" to synchronize access to shared data and also briefly discuss some deadlocks that might occur if locks are used to synchronize access to shared variables. The authors present "execute" instruction to communicate with I/O devices. Using "fork" with "execute", the authors present a way to specify computations that can compute in parallel with I/O operations.
3. The authors also present the idea of declaring “private” variables. If a variable is declared private, it is passed “by value” to the forked processes. This means that a copy of that variable is made and that copy is sent to the forked processes.
4. The authors also introduce the notion of "Inferior Spheres of Protection" using which a computation's sphere of protection is established by another computation. The scheme can help a lot in debugging programs written in a programming language. Since the process being debugged can be faulty, using this approach prevents the program from damaging or corrupting other programs. The authors provide "create sphere" instruction to create a new sphere and "grant" instruction to grant capabilities to that sphere. The authors also introduce various exceptional conditions that might occur when a process is running in an inferior sphere of protection. Some of these conditions call for actions from the Supervisor. In case of an exception, the process is suspended and a new process is started by the superior process. This new process contains the reason because of which the inferior process got suspended along with pointer to its capabilities. The authors also present various instructions to manipulate the state of the suspended process.
5. In order to protect or synchronize access to shared data or resources, the authors suggest the idea of using entry points. Entry points are also used to call protected procedures.
6. The authors also present directory structure and names in order to share routines and mechanisms without any confusion. In order to avoid ambiguities in names, the authors suggest appending the user name before the names of his object. The authors also present the idea that each user should have a root directory. The authors also provide constructs to add, remove and modify entries in a directory.
7. In order to share retained objects, the authors propose two schemes. "Acquire" gives complete authority to all computations to access the shared object. "Link" requires the owner of an object to specifically authorize each instance of its sharing.

Flaws

Some of the flaws in this paper are as follows.
1. Even though the authors mention that are other Multi-Programmed Computer Systems are available, they do not provide any drawbacks of those systems and do not compare their model with already existing ones.
2. The authors suggest that a scheduler "The Supervisor" is required for scheduling, resource allocation, and accounting but they do not evaluate how much overhead a scheduler will incur to the performance of the system.
3. The authors totally ignore the fact that deadlocks can occur while sharing resource in a multi-programming model. The paper provides no information on the deadlocks that might occur in their proposed multiprogramming model.
4. The directory structure presented is overly complex. Instead of having separate root directory for each principal, a much simple and better approach is to implement just one root directory and provide a home directory to each principal as is done in UNIX.

Summary
The paper presented a standard API for multiprogrammed computers, along with ideas for a directory structure and unique naming.

Problem
Multiprogamming computers were becoming more popular, but each computer had a separate, but similar, set of instructions.

Contributions

• Set of RWX permissions on computations (libraries), files, and directories.
• Ownership: The ability to grant permissions
• Debugging: One sphere of protection can own another sphere. Parent sphere can stop/start child spheres
• Also introduced (I think) the idea of an exception
• Very close to exception handling


• Setting permissions of executed code (pass in C-list when entering a protected entry point). This allows the caller to limit what the procedure can access.
• Directory/File naming. Created a way to share unique names between processes using a directory hierarchy.

Flaws
The paper discussed ideas well on a high level, but it was not clear if these where simply abstract ideas or had been pulled from working systems. All that is said is, “… we define a number of meta-instruction …”. This seems to indicate these are simply abstract ideas, but it is obvious from their discussion of the three diverse systems that the authors have used a number of multiprogramming systems. The authors might have consolidated these ideas from a number of implementations they reviewed. I feel the ideas would have had much more credibility if there was some idea of how realistic it would have been to implement them.

I also think it might have been nice if the authors proposed a method for automatic management of the C-lists. I would find it difficult and time consuming to manually managing a large number of C-list indexes. I assume this idea was left out, due to the extra overhead that automatic management would require.

Paper Review: Programming Semantics for Multiprogrammed Computations [Dennis & Van Horn]

Summary:

This paper proposes the set of operations that should be available in a
multiprogrammed, multi-user computer operating system for it to support
parallel processing, access control, debugging, and shared memory or
other communication mechanisms.

Problem:

While not explicitly stated, the problem was presumably that most
existing systems didn't yet contain all the required primitives to
conveniently, securely provide a development and production execution
multi-user environment for applications that benefit from
multiprogramming.

Contributions:

The paper offers a coherent, complete set of programming primitives to
control parallel programming in a multi-user environment offering a
somewhat reasonable naming convention for persistent (retained) data
objects.

The proposed meta-instructions' semantics are similar, and sometimes
even a bit more general, than the system programming APIs of early Unix.
For instance, its join instruction supports wait(2)-like functionality
but more like that implemented in modern languages and systems that
support process threads.

Flaws:

A number of the facilities seem cumbersome. Firstly, the proposed
multi-rooted directory hierarchy (containing roots for each user and
virtual user, so called "principals") is more complex than a
single-rooted hierarchy, such as the Unix file-system, that provides the
same functionality. As in Figure 6, the proposed directory structure is
unnecessarily complex.

Secondly, "spheres of protection" implemented as a list of capabilities
(or "C-list") contain a reasonable set of capabilities, but these
meta-instructions seem cumbersome as an API. By contrast, Unix has
similar control but seems to have identified a sub-set of capabilities,
each with its own API, such that a complicated control block for access
control does not need to be manipulated by system programmers.

Lastly, a point of confusion: it was not completely clear to me whether
"computations", in their terminology, are roughly a modern process with
multiple threads, launching new threads to execute specific routines, or
a group of related processes. I think it's more likely the latter, but
in one instance they wrote of launching new processes to perform very
light-weight operations, like when debugging.

Summary:
This paper describes a set of primitives ("meta-instructions") for a
multiprogramming system, and descriptions of how they can be used.

Problem:
Multiprogramming was at the time a new field, and people were still
trying to figure out what the system would have to support in order
for it to work properly.

Contributions:
First, the paper describes the number of primitives that are useful
for multiprocessing systems. Many of them are either used or similar
to other operations that are still used. For instance, 'fork' is only
slightly different in use (and conceptually not really different at
all) from Unix's fork; the paper's 'lock' and 'unlock' instructions
are essentially the same as mutex locks now except that they operate
on an otherwise hidden bit of each word of memory instead of an
explicit lock object; etc.

Second, in addition to providing these primitives, they also are
really describing a substantial part of the interface to a whole
system. Everything down to the "file system" naming scheme is
described. (It's not a low-level description like the other papers
we've read, but there are still quite a number of design decisions
they've made. This isn't *just* a description of things that any
multiprogramming system will need.)

One more point: as I was reading it I thought they were saying that
they use the same primitive (segments) to refer to both memory and
files. After the reading group meeting, I'm not entirely certain as to
if they meant that memory itself is segments and thus access is done
via capabilities (so files and memory are treated the same). If so,
then this is a very interesting idea (I've wondered if at some point
the distinction between RAM memory and persistent memory will go
away). If not, it's at least very close to the idea of memory-mapped
files today.

Flaws:

One thing I noticed was that, unless I'm missing something, it's possible for capabilities to
"leak." Almost at the end of the paper it
talks about how capabilities can be shared between processes, and it
describes a method by which some process A can use a protected entry
point in order to validate another process B that is requesting a
capability from A. After A verifies B and gives it the requested
capability, nothing is to stop B from putting that capability in a
public (free) entry in its principal's directory. You really need a
capability to place a capability into a directory... (More generally, the capability to propagate a capability.)

I also have a nit with the presentation, which is that on p. 145, it
defines a computation as "a set of processes having a common C-list
such that all processes using that same C-list are members of the
same computation." Seems a bit like saying that a definition is "a set
of words that together comprise a definition" to me.