The Unix Time-Sharing System Notes

Sep 2, 2014

source: http://cm.bell-labs.com/cm/cs/who/dmr/cacm.html
published: ACM 1974

The File System

From the user's point of view, three kinds of files:

ordinary disk files - no particular structure expected by system. Structure of files is controlled by programs (object files generated by assembler). Could be binary files or simple text files.
directories - mapping between the names of files and the files themselves.
- System maintains several directories for its own use.
  - root directory: the starting point for other files in the system.
  - directory that contains commands to be executed. (not required, for convinience since commands can be placed anywhere).
  - null filename refers to current directory. 
- A non-directory file may appear in several other directories under different names. - linking
  - A directory entry for this file is called a link
  - Hard Links: ln file1 file2 - file2 now links to file1. Both file1 and file2 have same status. File doesn't exist in any directory in general, the directory entry contains link between filename and a pointer to the information describing the file.
- Each directory has atleast two enteries with name '.' and '..' referring to current and parent directories resp.
- The directory structure is constrained to have a rooted tree structure.
- Cycles are not allowed in the file system. However Kernel mainains two restricted types of cycles in each directory: . and ..
special files: Each I/O device supported by UNIX is associated with at least one such file. Special files are read and written just like ordinary files. However, request to these files leads to activation of the associated device. An entry for each special devices exists in /dev.

Removable File Systems

It is not necessary that the entire file system hierarchy reside on this device.

mount causes the heretofore ordinary file to refer instead to the root directory of the file system on the removable volume. In effect, mount replaces a leaf of the hierarchy tree by a whole new subtree.

No link may exist between one file system hierarchy and another.
'..' refers to the directory itself instead to its parent.

Protection

Each user is assigned a unique user identification number. When a file is created it is marked with the user ID of the owner.
10 bits are used. 9 bits are used for R/W/X for self, group and others.
if the 10th bit is on, the system will temporarily change the user ID to the user ID of the user that created the file.

I/O Calls

There is no distinction between random and sequential I/O, nor is any logical record size imposed by system.
The size of the ordinary file is determined by the highest byte written on it; no predetermination of the size of a file is necessary or possible.
open / create system calls opens / creates file. There are no user-visible locks in the file system, nor is there any restriction on the number of users who may have a file open for reading or writing. The text may be scrambled if multiple users are writing at the same time.
System has sufficient interlocks present internally to maintain the logical consistency of the file system when two users are writing on same file, creating files in the same directory or deleting each other's open files.

Implementation of the File System

Directory:
  filename -> pointer to file info [called i-number]

When a file is accessed, it's i-number is used as an index into a system table (the i-list)

users/myfile

Directory: users
myfile -> 4;

i-list (system table)
0 - i-node1
1 - i-node2
...
4 - i-node4

i-node

Content of i-node:

Its owner
Its protection bits
The physical disk or tape address for the file contents.
Its size
Time of last modification
The number of links to the file, that is, the number of times it appears in a directory.
A bit indicating whether the file is a directory
A bit indicating whether the file is a special file
A bit indicating whether the file is "large" or "small"

The purpose of open/create call is to turn the pathname to i-number by searching the directories. Once a file is open, its device, i-number, and read/write pointer are stored in a system table indexed by the file descriptor return by open or create.

There is a space in i-node for 13 device addresses.

For special files 12 of the 13 devices addresses are ignored and the first specifies an internal device name, which is interpreted as a pair of numbers representing, resp, a device type and subdevice number. Device type -> system routine to deal with I/O on that device and SubDevice number -> selects a disk drive attached to a particular controller.

mount system call maintains a system table whose arguments(keys) are (i-number, device name of the ordinary file specied in mount command) and value is device name of the indicated special file. This table is searched for i-number/device pair during an open/create. If the match is found the i-number is replaced by the root directory and the device name is replaced by table value.

Processes and Images

An image is a computer execution environment. It includes a memory image, general register value, status of open files and the like.

A process is execution of image.

fork: to create a new process. The new processes after fork has copies of same image and share all open files.

Implementation of Shell

Shell most of the time waits for user to type command. At newline character shell's read calls returnds and shell analyzes the command line, putting the arg in form of execute and then the fork is called. The child process executes the command and parent process waits for the child process to finish. When child process finishes parent shell returns prompt back to the user.

Whenever '&' is used, shell simply doesn't wait for the child process to finish before giving the prompt to user.