Operating Systems

Literature references and annotations by Dick Grune, dick@dickgrune.com.
Last update: Wed Sep 04 17:34:52 2024.

These references and annotations were originally intended for personal use and are presented here only in the hope that they may be useful to others. There is no claim to completeness or even correctness. Each annotation represents my understanding of the text at the moment I wrote the annotation.
No guarantees given; comments and content criticism welcome.

Paul C. Attie, E. Allen Emerson, Synthesis of concurrent systems with many similar processes, ACM TOPLAS, vol. 20, #1, Jan. 1998, pp. 51-115.
Summary of the first two pages: Each concurrent process is viewed as a finite-state machine, and all states are in principle combined into one big state. The problem with this is that it is exponential in the number of processes; often say four processes is already beyond our reach of computation. The trick is to reduce all interaction to pair-wise interaction; this makes it all manageable.
     The other 64 pages are full of theorems, examples and graphs, all supported by fair amounts of math. Heavy reading but probably worth it.

Carl Ponder, Organizing UNIX directories as lattices, ACM SIGOPS, vol. 31, #4, Oct. 1997, pp. 72-77.
Should one put a directory Prolog under 5th_Generation, Languages or Logic? The answer is: all of the above. This is done simply by using symbolic links, but the problems is that cd .. then does the wrong thing. This is corrected by having a set of parent links + a special cd (and mkdir, etc.). It still does not solve "UNIX directories as sets": ACM/Letters/Bills should be the same as Letters/Bills/ACM.

Luigi Rizzo, A very fast algorithm for RAM compression, SIGOPS, vol. 31, #2, April 1997, pp. 36-45.
Swapping to disk is replaced by compressing to RAM; the compression essentially squeezes the zeroes out. Compression is performed in two steps. The first replaces each 32-bit zero word by a single 0 and each 32-bit non-zero word by a 1 followed by the 32 bits. The result is compressed again using a more complicated Huffman-like compression. The algorithm operates at speeds of 40 k-bytes/sec and achieves compression ratios between 40 and 97 percent.

from PS file, , Inferno, preprint ???, vol. ???, #???, 1997, pp. 5.
Inferno is a very lean but powerful operating system intended to run on bare hardware, in telephones, video-recorders, etc., or as a user program under UNIX, Windows, etc. Its main task is to provide program interfaces.
     Graphical interfaces include multiple levels of sophistication. Hardware interfaces are mapped to files, in good Unix/Richie/Pike style. Likewise, communication is file-mapped; reads and writes on the file are transformed into RPCs using a uniform protocol called Styx.
     The programming language of Inferno is Limbo, a Java-like language with a C/Pascal syntax; it is more low-level than Java in that it has pointers, but is (claimed to be) fully checked at compile and run time. As with Java, programs are exchanged in byte code, which can be checked and expanded by the receiver.
     The paper is an obvious plug for the commercial Inferno system and somehow reminds me of a Metallica video clip.

Andrew S. Tanenbaum, Distributed Operating Systems, Prentice Hall, Englewood Cliffs, N.J., 1995, pp. 614.
Second of the trilogy. Six grand chapters (Introduction, Communication, Synchronization, Processes, File Systems and Shared Memory) and four case studies (Amoeba, Mach, Chorus, DCE).

John H. Hartman, John K. Ousterhout, The Zebra striped network file system, TOCS, vol. 13, #3, Aug. 1995, pp. 274-310.
Combines striping (writing date across multiple servers) with log-structure.

Xiaohua Jia, Mamoru Maekawa, Operating system kernel automatic construction, ACM OSR, vol. 29, #3, July 1995, pp. 91-96.
Describes a kernel-generating system KGS à la yacc; an example of a driver specification is given.

Özalp Babao&gcaron;lu, Keith Marzullo, Consistent global states of distributed systems: fundamental concepts and mechanisms, ed. by Sape Mullender, in Distributed Systems, (2nd ed.), Addison-Wesley / ACM Press, New York, 1993, pp. 55-96.
Consistent cut: does not include a receive whose send is not also included. Active Monitor: asks questions; reactive monitor: sits and watches. Delivery Rules: DR1($delta$) at any time t, all messages with time stamp < t - $delta$ have been delivered. Time stamps are generated using logical clocks. Logical clocks count events, not time. FIFO delivery: all messages sent by A to B are delivered to B in the same order as they are sent by A, regardless of the order in which they actually arrive at B. Gap detection: between two events/messages was there a third event/message? Causal delivery: if sending a message $ m sub A $ by A causally precedes sending message $ m sub B $ by B, then $m sub A$ is delivered to C earlier than $m sub B$. Causal history: each process attaches to each message sent its own history plus all histories it has received. Vector clock: rather than the entire history, the local clock values of all processes are sent around. Vector clocks supply a strong Clock Condition and all kinds of goodies, including Causal delivery. A reactive monitor can wait for all event messages and order them according to Causal Delivery; then all global states it sees are consistent.

Steven Mikes, X Window System Program Design and Development, Addison-Wesley, Reading, Mass., 1992, pp. 296.
Mostly about user interfaces: twm, Open Look, Motif, UIM/X (an interactive user interface generator for X). The book contains much text, many included files but few diagrams. Slushy reading. The best part is probably the annotated (and critical) bibliography.

Andrew S. Tanenbaum, Modern Operating Systems, Prentice-Hall, Englewood Cliffs, N.J. 07632, 1992, pp. 728.
Partly an update of "Operating Systems: Design and Implementation", which constitutes part 1: traditional OSs. It pays more attention to MSDOS than its predecessor did. ???. Part 2 concerns distributed OSs, their communication, synchronization, processes and file systems. Amoeba and Mach are case studies.

Erik H. Baalbergen, The Declarative Operating System Model, (PhD Thesis), Vrije Univ., Amsterdam, March 26, 1992, pp. 268.
Design and implementation of an OS in which the user can declare condition-action rules. An example of such a rule could be "If a .c file changes, compile it into a .o file using command cc -c". Background CPU power or distributed processes are then used to keep all rules obeyed, using functional processes (i.e. to the user the processes are indivisible actions). The implementation resulted in EOOS, which is Greek for "dawn", and also "Erik's Own Operating System".

Microsoft, MS-DOS Programmer's Reference: version 5.0, Microsoft Press, Redmont, Wash., 1991, pp. 464.
Describes all internal and external structures and all system calls and their interrelationships. Terse, even more so than the UNIX manuals. Requires considerable prior knowledge of MS-DOS. Encyclopaedic, and by definition complete.

Andrew S. Tanenbaum, Robbert van Renesse, Hans van Staveren, Gregory J. Sharp, Sape J. Mullender, Jack Jansen, Guido van Rossum, Experiences with the Amoeba distributed operating system, Commun. ACM, vol. 33, #12, Dec. 1990, pp. 46-63.
See amoeba.doc for abstract.

Paul J. Asente, Ralph R. Swick, X Windows System Toolkit -- The Complete Programmer's Guide and Specification -- X11R4, Digital Press, Bedford, Mass., 1990, pp. 967.
The book starts by summarizing the X Window System principles. The X Server runs the actual windows. Xlib is an interface to communicate with the X Server. The X Toolkit is an interface for writing widgets; it uses Xlib. This leaves the question of what a widget is.
     To the user, a widget is an area on the screen that is perceived as a coherent unit; the area has attributes, which are part of the widget. There are widgets of many different types, and widget writers can create more.
     In an application, a widget is represented as an ADT (opaque data structure) corresponding to the type of the screen widget. The application manipulates the application widget by using the widget interface for that type. The interface consists of a number of general widget routines (the Intrinsics) and some routines specific to the given type of the widget. The latter were written by a widget writer.
     The X Toolkit provides the Intrinsics and the widget writer can use the Intrinsics and Xlib to implement widget-specific routines. Widgets are implemented as objects in C with single inheritance, by stretching normal C.
     The book consists of two parts, a Programmer's Guide (pp. 1-628) and a technical manual called the Specification (pp. 629-876), plus appendices. Each chapter in the Programmer's Guide consists of two parts: writing applications and writing widgets. An important aspect of X is learning to speak the jargon, and the authors are fully aware that they are describing one weird system. Excellent book.

Niall Mansfield, The X Window System: a User's Guide, Addison-Wesley, Amsterdam, 1990, pp. 344.
Excellent, easy-going introduction to using X. Consists of four parts: I. overview of X: principles, basic system model, user interface; II. using X: xinit, uwm, xhost, xterm + utilities (e.g. xev); III. customizing X: fonts, colors, bitmaps, resources, translations, xdm; IV. road maps to: documentation, installation, network ftp. Uses X11R3, but does not delve deep enough to be obsolete.

Panos E. Livadas, File Structures, Theory and Practice, Prentice Hall, Englewood Cliffs, NJ, 1990, pp. 433.
Detailed treatment of existing file systems and file structures. BISAM, VSAM, Version 7 UNIX, MVS, locate mode, cylinder overflow areas, etc., it's all there. Covers timing and tuning. Includes chapters on inverted file systems and external sorting. With many footnotes. No literature references.

Douglas A. Young, X Window Systems: Programming and Applications with Xt, Prentice Hall, Englewood Cliffs, N.J., 1989, pp. 468.
Good explanation, with small programs, of using the X Toolkit, creating widgets, etc. Good intro to X Windows. Uses X11R3.

Oliver Jones, Introduction to the X Window System, Prentice Hall, Englewood Cliffs, N.J., 1989, pp. 511.
As it says on page 12: "The purpose of this book is to explain how to understand and use Xlib". Which it does well. Hardly touches upon toolkits. Recommended by Mikes [OS 1992].

Joel M. Crichlow, An Introduction to Distributed and Parallel Computing, Prentice Hall, New York, N.Y., 1988, pp. 209.
Covers the range from hardware, networks and operating systems to client-server models, distributed database systems and parallel programming languages (Actus, Concurrent Pascal, Ada, SR, C, Multilisp, etc.)

Ray Duncan, Advanced MS-DOS Programming, (2nd Edn.), Microsoft Press, Redmont, Wash., 1988, pp. 669.
For the experienced C or ASM programmer. Detailed and readable account of many hardware and software features. Yet by no means complete: TSR is explained only while describing the system call in the manual section; likewise for code pages, the format of which is not described. Chapter 15 on Filters (i.e. how to use pipes) seems a waste.

Andrew S. Tanenbaum, Operating Systems: Design and Implementation, Prentice Hall, Englewood Cliffs, N.J., 1987, pp. 719.
First of the trilogy.

J.H. Saltzer, D.P. Reed, D.D. Clark, End-to-end arguments in systems design, TOCS, vol. 2, #4, 1984, pp. 277-288.
Systems should not do too much. They almost never do exactly what the user wants, so the user will have to check conditions at the end anyway and specify action. There is more profit in simple primitives.

Per Brinch-Hansen, Programming a Personal Computer, Englewood Cliffs, New Jersey, Prentice-Hall, 1982, pp. 388.
In 388 pages, it defines a complete programming language, Edison, with concurrency and modules, most of an operating system, and a kernel for a PDP-11 computer. Source listing and all.

Leslie Lamport, Robert Shostak, Marshall Pease, The Byzantine generals problem, ACM TOPLAS, vol. 4, #3, July 1982, pp. 382-401.
[ solved under various hypotheses using graph theory ]

B. Hebbart, et al., Penetration analysis of MTS, ACM SIGOPS, vol. 14, #1, Jan. 1980, pp. 7-??.
Guided student attack on MTS. Main loopholes: 1. system calls with more than one output parameter, each implemented by pointer: make parameter one point to parameter two; filling parameter one will ruin the (checked) pointer in parameter 2. 2. system calls that call user code, still in priviliged mode, possibly combined with trick 1.