CS 134

Key Points: Synchronization Primitives

Starvation

  1. Definition: A thread is perpetually denied access to a resource it needs.
  2. Causes: Unfair scheduling or resource allocation.
  3. Example: In semaphores, threads can be starved if new threads always take precedence.
  4. Prevention: Implement fair scheduling algorithms or use synchronization primitives that ensure fairness.

Deadlock

  1. Definition: A circular waiting condition where threads are blocked forever, waiting on each other.
    • A waits for B, B waits for C, C waits for A, and so on.
  2. Example: The Dining Pirates (Philosophers) problem.
  3. Prevention Strategies:
    • Break the circular wait (e.g., by imposing a total order on resources).
    • Use higher-level synchronization designs that eliminate the possibility of a circular wait.
  4. Detection: Some systems (e.g., OS/161's Hangman) can detect potential deadlocks.
    • More typically, deadlock from user code is considered a bug and not explicitly detected (following the “worse is better” philosophy of keeping the implementation simple).
    • We'll discuss deadlock detection and avoidance in more detail in a future lesson.

Reader–Writer Locks

  1. Purpose: Allow multiple readers or one writer to access a shared resource.
  2. Challenges:
    • Preventing writer starvation.
    • Balancing reader and writer access.
  3. Implementations:
    • Basic implementation (prone to writer starvation).
    • Writer-preference implementation (can lead to reader starvation).
    • Balanced approach (uses a “gate” mechanism to alternate fairly).

General Principles

  1. Fairness vs. Efficiency: Often a trade-off between ensuring fair access and maximizing throughput.
  2. Complexity: More sophisticated synchronization mechanisms can prevent issues like starvation but may be more complex to implement and reason about.
  3. Testing: Concurrency bugs can be hard to reproduce; thorough testing with various scenarios is crucial.
  4. Real-World Implementations: Production-grade synchronization primitives often include additional complexity to handle edge cases, ensure fairness, and make common scenarios more efficient.

Remember

  • Always consider the potential for starvation and deadlock when designing concurrent systems.
  • Choose the appropriate synchronization primitive based on your specific use case and requirements.
  • Be aware that seemingly simple solutions may have hidden pitfalls in edge cases or under high contention.
  • On the other hand, the complexity we see in decades-old, real-world operating systems is usually the result of years of refinement and optimization to handle a wide range of scenarios. The key lesson for us here isn't that we should begin by trying to implement these complex mechanisms ourselves, but rather that we can begin with something that works well enough for most cases, and then think critically, experiment, and refine as needed.

(When logged in, completion status appears here.)