Distributed System

Definition

• A collection of independent computers that appears to its users as a single coherent system.
• Ideal: looks like a single computer

Benefits

• Cheaper/Easier to build lots of simple computers
• Easier to add power incrementally
• Users can have complete control over some components
• Much easier for users to collaborate through network

Goals

1. Resource sharing
2. Transparency
3. Openness (use Interface Definition/Description Language to describe the interfaces between software components, usually RPC-based)
4. Scalability

How to implement?

• Middleware.

Review of Classic Concurrency

Why is it important/useful?

• Allows safe/multiplexed access to shared resources.
• Concurrency $\neq$ parallelism, although it enables parallelism.

Terminology

• Critical Section: piece of code accessing a shared resource, usually variables or data structures.
• Race Condition: Multiple threads of execution enter CS at the same time, update shared resource, leading to undesirable outcome.
• Solution: mutual exclusion (mutex).
  • guarantee that only a single thread/process enters a CS, avoiding races

Desired Properties of Mutex

1. Mutual Exclusion (Correctness)
2. Bounded Waiting (Fairness)
3. Progress (Efficiency)

Classic Concurrency Model

Semaphores

• P() (wait/decrement)
• V() (signal/increment)
• Atomic operations.
• Hard to implement a FIFO queue.
  • Correctness.
  • Avoid spin-lock.
  • Avoid deadlock.

Condition Variables (cvars)

• cvars provide a sync point, one thread suspended until activated by another. (more efficient way to wait than spin lock )
• associated with a mutex.
• cvar.wait(&mutex) and cvar.signal()

Mesa monitor semantics: when a thread is signaled, it is simply put on the ready queue. It must re-acquire the mutex before returning from wait.

Hoare monitor semantics: when a thread is signaled, it runs immediately. The signaling thread is suspended until the signaled thread gives up the monitor.

In real implementations, Mesa semantics is used.

• Simple Rule: With Mesa semantics, use while loops to recheck the condition. Always safe to do so.

Concurrency in Go

Concepts

• Instead of communicating by sharing memory, share memory by communication.

Goroutines

• Independently executing function, launched by go f().
• Independent call stack, very inexpensive, 1000s of them.

Channels

• Passing (typed) information around (int, char, ...)
• Synchronization goroutines
• Providing pointer to return location (like a “callback”)
• ch := make(chan int, 5) creates a channel of type int with buffer size 5
• ch <- x sends x to channel ch
• x := <- ch receives from channel ch
• Note, when channel capacity is 0, Insert/Remove is a rendezvous. i.e. sync point.

Limitations

1. Size: bounded when initialized, cannot have unbounded buffer
2. No way to test for emptiness. When read from channel cannot put back value to head of channel
3. No way to flush channel
4. No way to examine first element

• Go channels are low level primitives.
• Go also has support for mutexes and condition variables in sync package.