(ref.doc)Goscinski

Distributed Operating Systems - The Logical Design
Andrzej Goscinski, Addison-Wesley 1991

Own comments:
More a reference than a guide. A compilation of works. Quite
repetitive. Tries to be exhaustive. Probably already obsolete in
local topics.

Contents, p xv-xxix
1 Introduction
2 Network operating systems versus distributed operating systems
3 Communication issues of distributed computer systems
4 Research and design issues of distributed operating systems
5 Interprocess communication
6 Synchronization
7 Naming facility
8 Process management
9 Resource allocation
10 Deadlock detection
11 Resource protection
12 Communication security and user authentication
13 File service
14 Survey of experimental distributed operating systems

6.8 p 271-279, Concurrency control in transaction processing
- Concurrency control mechanism requirements
- Locking
- Optimistic concurrency control
- Timestamps - basic timestamp ordering algorithm
- Timestamp ordering algorithm with two-phase commit

6.9 p 279, Evaluation criteria for synchronisation methods
- Response time and throughput
- Resiliency
- Overhead
- Convergence and fairness
- Extensibility
- Determinacy
- Recovery
- Connectivity
- Initialization
- Utilization
- Understandability/simplicity

6.10 p 281
Synchronization algorithms:
- timestamp (Lamport)
- token passing
- priority-based

8.1 p 373-374
- fork/join: parent-child, parent driven
- cobegin/coend: (Dijkstra)

p 375
Four models for implementing concurrency:
- CSP (Hoare 1978)
- DP (Brinch Hansen 1978)
- ADA (Gehani 1983)
- CMAY (Bagrodia and Chandy 1985)

p 379
- Lightweight: several threads with shared stack, shared data.
- Heavyweight: one thread, separate address space.
- Mediumweight: each thread has its own stack; data shared.

p 385-386
The 'fork' operation in Unix (separate stacks and data, shared
code) and in Sprite (separate stacks, shared data and code).

10.1 p 523, Methods of deadlock handling
- deadlock prevention (static). Summary: impractical except for
  systems which have a predefined structure.
- deadlock avoidance (dynamic). Summary: not practical in distributed
  systems; inefficient.
- deadlock detection and resolution. Summary: generally recommended in
  distributed systems.
(Note: Specially verbose, repetitive and non conclusive though!)

10.2.2 p 528
Resource deadlock detection algorithms function by detecting cycles in
the dependency graphs of blocked processes.

p 533-534
In the case of a resource deadlock, a process can proceed if it has
acquired all resources, whereas in the case of communication deadlock
a process can proceed upon receiving any one resource.

p 534
A wait-for-graph (WFG) belongs to a class of directed graphs. The
vertices of this graph are used to model processes. Directed edges in
the graph represent blocking relations between processes. A vertex
with outgoing edges correspond to a blocked process. [...] A deadlock
is indicated by a cycle in the WFG.

10.4 p 537-539, Centralized, distributed or hierarchical deadlock detection
Problems with distribution:
- false deadlocks due to outdated information
- double detection by different systems

10.5 p 540-544, Basic concepts for distributed deadlock detection algorithms
- path-pushing (building of a global WFG)
- edge-chasing (propagation of probe messages along the edges)
- diffusing computation (queries and replies)
- global state detection

p 544-545
Two conditions for correctness of detection algorithms:
- progress property
- safety property