# The UNIX Time-Sharing Operating System

2018-01-18 · https://fsgeek.ca/log/the-unix-time-sharing-operating-system/

[The UNIX Time-Sharing Operating System](https://compas.cs.stonybrook.edu/~nhonarmand/courses/fa17/cse306/papers/unix.pdf) Dennis M. Ritchie and Ken Thompson, Bell Labs, _Communications of the ACM,__July 1974, Volume 17, Number 7, pp. 365-375._ This paper describes **Version 3** of UNIX. It was Version 6 that became the basis of the Berkeley Software Distribution (BSD) version of UNIX. The only other operating system in CS history to date that has had so much impact on operating systems development is [MULTICS](/log/multics/), and UNIX is a direct descendant. Developed by several Bell Labs researchers that had been involved in MULTICS, its goal was to try and build a smaller operating system that retained what they viewed as the key benefits of MULTICS. Much of UNIX Version 3 was written in the C programming language, itself derived from BCPL, a language that had been used on the MULTICS project. 

> "_The most important job of UNIX is to provide a file system._ "

These words leave little doubt about the role of file systems in UNIX and the importance assigned to them. The paper then goes on to describe files, in similar terms to MULTICS: files, directories, and special files (devices). We see the hierarchical file system of MULTICS reflected back in the description of the system. They talk about file names being 14 characters or less, the formation of paths, and the iterative walk of names through the file system name space to find other directories, as well as the terminal file nodes. 

> "_The directory structure is constrained to have the form of a rooted tree._ "

This is what I am looking for - the  _why_ of hierarchical file systems. I found the answer here, unsurprising yet ironically disappointing: 

> "_The reason for this is to simplify the writing of programs which visit subtrees of the directory structure, and more important, to avoid the separation of portions of the hierarchy._ "

Not surprising, yet not precisely what I had expected. I had  _expected_ the reason to be for the simplicity of the operating system (though they do allude to this by discussing the difficulty of knowing when it is safe to delete a directory. They describe  _links_ to files, however, so their file system is not really a tree. Rather, it is more like a directed acyclic graph (DAG). Files do not have pointers back to their directories, but directories have pointers back to their parent. Thus we have the distinction. The namespace is a DAG. Files don't really live in the name space directly, they are referenced  _from_ the namespace, but have a reference count. Oddly, with that, I found what I came for, at least in terms of insight for my own research area. There is a certain satisfaction in being able to point to this seminal document and say "this is why we got to where we are now." But if I stopped at this point, I would be leaving out the bits I had not expected to find. First, the mundane: they discuss removable file systems, the fact that this is in fact a  _collection_ of name spaces, combining persistent name spaces with one another using a non-persistent mechanism (mounting), There is a simple description of how the file system is itself implemented. They describe the  _i-number****_(now the inode number) as an index into the file table. Thus, a directory entry is where the name lives, it merely refers to the file using its  _i-number_. These entries are then called  _i-node_ s. The i-node contains information about the owner of the file, the protection bits governing the file, the location information for where logical data is physically stored on the medium, the size of the file, its timestamps, it's attribute bits, and the number of directory entries referencing the given  _i-node_. Surprisingly, not all that different than it is now, 45 years later. Implementation details  _have_ changed, as we no longer limit files to 10MB in size. They describe bufering, they describe sector sized I/O and how it is more efficient for a program to do sector-sized I/O operations. Much of the paper has nothing to do with file systems. I leave that to the interested reader to explore beyond that. There are two interesting tid-bits remaining: 

  * They lost data once, on a hard disk that failed. The backup was 3 days old.
  * They considered the  _permuted index_ application as one of the "major programs available".

The fact they considered the permuted index important at this early stage  _was_ an interesting insight to me. Clearly, the ability to "find our stuff" is one that's been around since the dawn of time. Maybe this research direction of mine _does_ make sense.