CS 736 - Spring 2007 - Paper Discussion

Summary:
This paper describes several details about the implementation of the fourth revision of the Unix operating system. It focuses on two main, broad issues; the file system (from the user's, application programmer's, and implementation perspective) and processes (a handful of system calls and how they are used to implement various features of the shell).

The Problem:
The authors state that they didn't have any external requirements for what Unix should do or how it should behave, but came about because Thompson was "dissatisfied" with the other options at the time. They state that their most important goal was an interactive system to make it as easy as possible to use, and that it was designed by programmers, for programmers.

Contributions:
The work behind the paper is really quite remarkable, especially for computer science. The architecture of the Unix system as described is more or less the same as the Unix systems in use today, thirty years later. CS theory has staying power, and ideas have staying power, but few actual programs have that kind of staying power, especially without being considered legacy. What's more, most of the places where I know that things are different than what's described are additions (symbolic links for instance) rather than changes to what's described in the paper.

Unix also provides in some sense an existence proof that it's possible to create a useful system with a very modest effort (two person years) -- compared to five years and who knows how many people (a quick Google didn't turn up any promising hits) working on Windows Vista, almost for free.

Finally, a lot of the way Unix treats things are done by almost every OS today. For instance, the authors take care to mention a couple times that the OS doesn't impose any structure on file contents. The idea that the OS would do this seems completely foreign now, but apparently this couldn't be taken for granted at the time Unix was developed.

Flaws:
The paper does a good job at explaining highlights of Unix, but it does little else. For instance, they don't provide much discussion of *why* they designed things the way they did, alternatives they considered, tradeoffs they had to make, or really what they learned during the design and implementation. For instance, did they spend a long time deciding to go with the GENIE fork/exec method for running a program (as opposed to something along the lines of the Windows CreateProcess function, which more directly corresponds to the user-level view)? It seems clear that the fork/exec model makes a number of things easy or even possible, and I can't think of any major drawbacks, but it's hard to tell how much of that is due to careful planning and how much is due to luckily picking the better solution without fully realizing its benefits. (For instance, GDB does an interesting and useful operation with fork. You can give it a command that will cause it to fork the process being debugged and keep a pointer to the child in the background. Later you can switch to that process and start debugging from almost the same state the program was in when it was forked. I don't know if this technique is even possible on Windows through the Windows API.)

As far as problems with Unix itself, especially if considered in the paper's time period, I'm hard pressed to come up with noticeable flaws. One thing that I don't really understand at least though is the description in the paper as to why hard links to directories aren't permitted. The paper states that this would make it difficult to detect when a directory is no longer reachable from /, but I don't see why it would be much more difficult for directories than ordinary files. (Present-day Linux has this same restriction, so I guess there's a reason. The only thing I can come up with is that if the OS unlinks a file, the space should be reclaimed if the link count is 0. For a directory, the link count would depend on the number of subdirectories it would have.) They also gave reasons why the OS didn't support file locking. I don't fully buy these arguments, at least in today's world. OS-supported locking isn't a necessity, as applications can work around it by, for instance, creating explicit lock files. At the same time, the fact that programs do this is proof that the functionality is needed, and OS locks could be more elegant. (They wouldn't clutter the directory contents and could be automatically cleaned up if, for instance, a program segfaulted.) However, it's possible that this was less of a problem in the 70s. The fact that modern Unices seem to support locking with fnctl seems to support this.

Summary:

This paper by Ritchie and Thompson presents some of new features implemented in the fourth generation of the UNIX time-sharing operating system, used in the DEC PDP-11 and Interdata 8/32 computers. These features are: file system, process creation and execution, and the shell. The authors go into detail as to how they implemented these features and how would a user utilize them on the UNIX system, by giving examples and explaining the reasons behind them.

Problem Description:

The paper addresses the issue of having a powerful operating system, which is user-friendly and inexpensive. At the time this paper was published and this OS was developed, the availability of simple and elegant OS was nonexistent. The fourth generation UNIX OS was created for an audience who would use it for editing or programming purposes (a common audience at that time).

Contributions:

1) A novel file system. The paper mentions that a file system is one of the key features of any OS. The paper elaborates on how exactly the files and directories are created and maintained. There is a standardized way to access any file or directory, or even “special files” and I/O devices. This simplifies the user environment a lot as the user doesn’t need to worry about details about different access styles. Other important contributions include mountable file systems and existence of one root directory (which gives the file system a hierarchical form). The protection mechanism is in-built and standard for all the files. There is a “super-user” who has all the privileges, and doesn’t need to follow any protection requirements. This gives flexibility and control in the hand of the administrator when needed.
2) Standardized I/O accesses. As briefly mentioned in the previous contribution, accesses to I/O devices, or I/O calls, are standardized to eliminate differences between the various devices and styles of accesses. Reading and writing to I/O devices are sequential and buffered. This increases the throughput and performance of the system in most of the cases.
3) Process execution. The user-memory is divided into three segments: text, data and stack. This makes it easier to set sharing capabilities between the processes (text segment is shared, data segment isn’t). Also, the fork system call provides a way to create independent executing processes with a parent and a child process. Features such as pipes, wait and exit are also useful.
4) A simple yet elegant execution environment – the Shell. The shell is a command-line interpreter. It interprets the commands typed by the user and tries to execute the appropriate programs. It includes features for standard I/O, where the input or output of the program execution can be stored in files specified by the user. There are also other features like filters and command separators useful for multitasking.

Flaws:

One of the biggest flaws in the paper is the lack of experiments/results section to validate the performance and usefulness of the OS. The reader is blindly expected to believe the greatness of all the novel features, without any proper proof of their contributions to the system. One of the other flaws is the implementation of locks is not described properly. If there are no locks and there is a possibility of a file getting scrambled due to multiple users writing to it, then saying that “in practice difficulties do not arise” is not sufficient to completely solve this problem. This shows that the authors haven’t taken care of this corner case and have safely made an assumption that they are not relevant. No clear description or proof is given that shows how the problem of multiple user accessing the same file is solved.

Relevance:

This paper was published in 1974 describing the UNIX time-sharing system. Although more than 30 years old, the work done for this OS is still mostly used in today’s systems. The concept of file-system is still the same in today’s UNIX OS and many of the features are still present and widely used. This system was geared towards programmers and editors, and it has mostly managed to kept its audience even now. The project was a successful one and very novel.

Summary:

Ritchie and Thompson discuss the nature and implementation of: 1) the hierarchical file system incorporating demountable volumes of UNIX; 2) UNIX’s user command interface, named as shell.

Description of the Problem:

At the time when the paper was published, UNIX, a small and powerful OS had just emerged and was still in development. The goal of UNIX is to serve as an OS, which is simple, elegant and easy of use. The paper discusses some more advanced features of the fourth version of UNIX time-sharing system than those of first three versions. These features are listed in the contributions section.

Contributions

1). The hierarchical file system, which includes 3 kind of files: ordinary disk files containing whatever information the user places on it; directories mapping between the name of files and the files themselves and inducing a structure on the file system as a whole; special files, which are mainly I/O devices. By treating I/O devices as special files, file and devices are as similar as possible. And the system calls to do I/O are designed to eliminate the differences between the various devices and styles of access. In this way, UNIX provides compatible file, devices and inter-process I/O. This file system also supports removable volume by replacing a leaf of the hierarchy tree by a whole new subtree (the removable volume), which is treated virtually the same as those on the permanent file system except that there is no link existing between one file system hierarchy and another for the removable volume. The file system is of per-user basis. Each user gets a unique identification number. Also in each file, there are protection bits, in which the current user’s identification number is encoded.

2). Multi-process supported by a series of system calls: fork () makes a clone of the process except different processids. pipe() is used for process communication; wait() suspends the caller until one of its children has completed and then returns the processed of the terminated process. exit() terminate the process.

3) the user-friendly command-line interface: shell, which interprets the user’s input and executes the commands. The main loop of shell never terminates until it discovers an end-of-file condition on its input file.

Flaws:

1. the structure of this paper: it seems to lack a validation/evaluation part. Most part of this paper is simply representing the authors’ ideas without validating them.
2. back to the content of the paper, the new system was implemented by C and its size is bigger than those of earlier version. Though the author mentioned it is acceptable, “size” was much more important at that time compared to nowadays.
3. the unusual notion of UNIX: i-list induces something funny that are not found in other file systems: e.g. who is to be charged for the space of file. If a created a file and b links to it, then a deletes the file. a could be still charged, however b should be charged. The authors made the round of this problem.

Summary:
This paper introduces key aspects of UNIX including the file system, the execution environment, and the shell.

Problem Description:
At the time of the writing of this paper, other operating systems that had been written which allowed for interactive usage were expensive both in terms of hardware cost and in software development cost. UNIX strove to achieve these goals at a lower cost in both areas.

Contributions:
The major contributions in this paper are the description of the file system and it's implementation, the execution environment, and the shell.

Important contributions from the file system include directories, special files for devices which allow many devices to be communicated with in a standardized manner, mountable file devices and the concept of root, and file access protections.

In the area of the execution environment important contributions include the the use of images to define a programs execution environment, the use of processes with fork(), exit() etc.

In the area of the shell, the important contributions include the redirection of output to files, the ability for uses to use programs together in new and innovative ways by directing output of one program into another, and the ability to run programs in the background.

Flaws
The lack of the ability to link files across mounted devices seems an unecessary restriction because a link can be checked if it is dead at the time it is followed and an error generated.

The paper does not adequately address possible concerns with malicious users. For instance what would happen to system resources if a user wrote a fork bomb.

The Unix paper describes the key features available in unix as well as these features are implemented. A few of the features covered in this paper are the file system (types of files, io api, protection bits, and mounting); the process; and the shell. I'd rather not go into much detail or summarize their descriptions of the unix's features. The paper also states some of the concepts that unix borrowed and where it got them from.

I found the paper lacking in the amount of technical detail that was provided to the reader. The paper should have elaborated on why creating links to directories are not allowed [linking directories can create cycles which make it difficult to determine when a directory has been deleted]. A brief summary of how the file system allocates free space and deals with fragmentation would have been informative in section 4. The subsection about filters spends a great deal of time explaining the advantages of pipe which is itself not a filter – to the best of my knowledge pipe doesn't perform any processing or does it? My final grievance with the paper has to do with treatment of file and devices by programs – in the perspective section the authors describe two ways to let programs use devices as input and output however they don't state which is used. The only ways for programs to interact with the devices, being files, is via the I/O calls and the read,write, and seek methods have been doctored to be act different when working with devices.

I was impressed by how the authors were able to link the personal interests of the coder to the final design that arose.

SUMMARY

"The UNIX Time-Sharing System" by D.M. Ritchie and K. Thompson concisely
describes features of the Unix operating system designed to run on DEC PDP-11
and Interdata 8/32 minicomputers.
The authors give an overview of the hardware for which their OS was designed,
the file system, lives of processes, the shell, traps and interrupts. The depth of
discussion of those areas varies from mere overview to some implementation
details. Lastly the authors present some of their design goals and
influences.

PROBLEM

The article addresses issues of design and implementation of a general-purpose
multi-user operating system.

CONTRIBUTIONS

* development of an operating system that is geared toward overall performance
and and ease of use, as opposed to focusing on a specific task.

* limitation of operating system complexity for users. For example, Unix
presented an (almost) uniform interface for file access, sequential and
random-access devices, and inter-process communication.

* it is demonstrated treating various OS concepts (e.g. devices) as files allows the file system to provide elegant solutions for tasks such a device mounting.

* authors appear to have made an effort to minimize OS-imposed restrictions.
For example, arbitrary program can be used as the "shell", or not placing
restrictions on contents of a program's address space.

* simplicity is often emphasized. When a solution seemed to be too simple
(e.g. the decision not to implement user-space file locking) arguments are
given why the chosen approach is sufficient

Many of the contributions mentioned in the article are so common today that it is hard to recognize them as significant. For example, tree-like directory structure.

FLAWS

Unix is not compared to other operating systems and approaches alternative to
those taken by the authors were usually omitted.

The article is geared for a reader from the 70s. Some points are difficult to
appreciate today. A little more context about the state of computing at time
of writing could be helpful.

Generally discussion is not very deep and often it seems that the authors are
mostly interested in presenting what they have done, as opposed to why it is
good. The Unix file locking approach is one example. The authors claim that
their implementation is good enough given the workload of their system.
However, since Unix is meant to be a general-purpose OS, a little more
discussion here would be in order.

OS usability and secuirity tradeoffs were not discussed.

The article gives only limited insight into the design of Unix, however, a lot
of information is packed in 14 pages.

No evaluation has been performed. The article hardly aims to convince a
sceptic about superiority of the Unix approach. The authors seem to simply
share what they think makes a good operating system.

Weaknesses of the taken approach are not really discussed.

RELEVANCE

Although the article is quite old, a lot of the presented material is relevant
today, at least for Linux. The ideas presented in a fairly abstract yet very accessible
manner, which makes it easy to better understand how Linux works today.

Also some timeless ideas are presented, that are unlikely to become obsolete
in the forseeable future. For example, emphasis on simplicity and generality
whereby the OS assumes little about the user and tries to impose few limits.

However, without evaluation and comparison to other work it is difficult to
see how effective authors' approach is.

Summary

This paper discusses three important features provided by the UNIX operating system developed for Digital Equipment Corporation PDP-11 and the Interdata 8/32 computers. These features include,
• The File System.
• Process creation and inter-process communication.
• Command Line Interface called Shell.
The authors present the implementation details along with the usage model of these features.

Problem Description

This paper was published in 1974. At that time the advances in the field of operating systems had just started. The available operating systems were in a very crude form and did not provide the users with that much of functionality. This paper presents some of the new features provided to the user by the UNIX environment like very well organized file system, multi-process environment, relatively friendly command line interface with a lot of functionality (I used the word ‘relatively’ because comparing to modern operating systems like Windows, UNIX user interface mentioned in the paper is not that user friendly.), etc.

Contributions

Major contributions of this paper are mentioned below. It should be noted that almost all of these contributions exist in the modern day UNIX based operating systems.

Firstly, the paper presents a very well organized hierarchical file system which comprises three different types of files i.e. ordinary files, directories, and special files.
• Ordinary files can contain symbolic or binary programs or can be text documents.
• Directories are used to organize the file structure and they are also treated as ordinary files except that they can not be written by unprivileged programs.
• Special files are a very important feature provided by UNIX by which I/O devices are associated with at least one file and are read and written like ordinary files. As a result, files and device I/O can be treated in the same manner. This is quite in accordance with “the law of least astonishment”, since the users are not overwhelmed with new ways to handle the device I/O.

UNIX also supports a feature called linking; using which the user can have multiple pointers to the same file. As a result, there is just one physical copy of the file which is independent of any directory entry. UNIX also provides removable file system. Due to this feature, other file systems can also be mounted to an ordinary file in the root file system. All the files are protected using a set of 10 protection bits. All the files created are marked by the user ID and depending on the protection bits access to the file in controlled by the owner of the file. UNIX also provides both random and sequential access to read or write a file. Important information related to different files is stored in a system table called i-list. When a file is opened or created, its i-node is accessed which provides the file access permissions, physical location of the file in the disk and other important information. Each file is divided into a number of 512-byte blocks. The information about the total number of 512-byte blocks used by a file is also stored in the i-node. When a file is being read or written, it is brought to the main memory in chunks of 512-bytes. The OS also pre-fetches next 512-byte block while the previous block is being accessed which reduces the running time of the programs.

Secondly, the paper also present the multi-processing support provided in the UNIX environment. User can fork a child process. Both the parent and child process get an independent copy of the original memory image and share all open files. Pipes are used for inter-process communication. A program can also use the execute primitive to overwrite its code and data part with the code and data of the program provided to the execute primitive. UNIX also provides process synchronization using the wait command.

Finally, the paper provides the structure of the command line interface provided to the user which is called Shell. Shell is a command line interpreter. It reads a line provided by the user and interprets it to execute the desired operation. UNIX also provides features to redirect the output of a program being executed on shell to a file or read the input to the program from a file. Similarly, output of one program can be piped to the input of another program using ‘|’. If this second program processes the input and generates an output to be fed to another program, then it is called a filter. User can write the Shell commands in file and use sh command to process that file. Whenever Shell gets a valid command, it forks a new child that processes that command. Shell also has the capability to run various programs in background. In UNIX, every process is a child of another process and the parent of all the processes in the init process. Init process authenticates a user’s ID and password and opens a shell for the user and sets the directory to the user’s default directory.

One of the great achievements of the authors’ of this paper is that the ideas they provided in this paper are still used in the UNIX environment exactly as it is or with very minor improvements even after more than 30 years.

Flaws

A few flaws that exist in the paper are outlined below.
1. The authors mention that the early version of the operating system (OS) was written in the assembly language but in 1973, it was rewritten in C. The authors mention that the total size of the new OS was one third more than the older one but they do not comment on the impact of this translation on the performance of the new OS. At that time compilers were not as good as they are today. The un-optimized assembly code generated by the C compiler for the new OS could have severe impacts on its performance as compared to the OS that was actually written in native assembly language.
2. The suggested file system does not maintain any locks visible to the user. This means that multiple users can modify a file at the same time. This can result is a lot of confusion as two users can modify a file at the same time and only the changes made by one of them are saved. Locks should be provided to control the access to a file so that if someone is modifying a file other users are not allowed to modify it. This scheme is quite simple and can prevent loss of data.
3. It is claimed that the directories behave exactly as files. If so, then links to directories should be allowed. Similarly, linking between different file systems’ hierarchies is not allowed. This is also an unnecessary restriction. These features are allowed in modern UNIX Operating Systems. If a disk containing the physical copy of the file is un-mounted, then the links can be quite easily declared dead and there is not need to remove them. When the file system is mounted again, the links can again start pointing to the physical file.

This paper introduces fourth version of Unix system by describing key aspects and implementation of Unix system especially focusing on a design and implementation of file system and a user command interface.
Unix is an operating system which is very compact and still holding important features such as multi-user support and interactiveness by simple & well-organized file system, process management, and user interface. Readability is another key of Unix system because Unix is written in C language comparing to other operating systems written in assembly language.

Initial purpose of developing Unix was creating an operating system for PDP-7 so that they could use PDP-7 more practically because powerful computers with Operating Systems such as Multics were widely used and not PDP-7 around that time. Writing a readable and compact operating system resulted in solved the problem of not only the space efficiency but an understandability and a developability of the system.

Some of the key aspects are adopted from other systems and are not innovative, but a major contribution of this paper is that this compact and powerful operating system Unix showed the possibility of utilizing small computers and suggesting a key aspects to build the system. Also, the fact that the system was written in C language openly accelerated developing the system and demonstrated the benefit and power of open source system and encouraged other programmers in the world.

The way of managing inter process communication seems to have a big problem. According to the paper, inter process communications in Unix are done by pipe and pipe can be established only between two processes which has same parent. This restricts some application to application communication and might have been a bottle neck of developing such programs. Nowadays we have “socket” that can cover that problem.
Since Unix is working on a single mini-computer, there is only a limited resource for multiple users. If there are a larger number of users in a domain than the system can manage, they will need to use separate systems and this seems to be violating the main concept of multi-user system so that a number of users can share the resources and data. It might have been more interesting if the author considered a possibility of communication between multiple systems to create a large one system for scalability.