MS

L05-Synchronization Issues

CS 439 Principles of Computing Systems

1. Overview of Processes and Threads

  • A process consists of an address space, an initial thread, and an initial stack.

  • Threads are lightweight and share the data segment (initialized, uninitialized data) and the heap.

  • Access to shared variables needs protections to prevent race conditions.

    • Synchronization Primitives Include:

      • Spinlocks

      • Blocking locks (Mutexes)

      • Binary semaphores

      • Monitors

  • Threads can be categorized as being implemented at the kernel level or user level.

  • Famous synchronization problems are crucial for understanding fundamental concepts and for job interviews.

2. Synchronization Problems

  • Important considerations:

    • Performance

    • Interaction with thread priorities

    • Starvation and Deadlock issues

    • Synchronization bugs

      • Heizenbugs (unpredictable behaviors)

      • Service denial bugs

3. Performance Considerations

  • Blocking Synchronization:

    • Leads to context switching if a mutex isn't available, freeing the CPU for other tasks.

  • Spinlock Synchronization:

    • Can waste CPU resources but is efficient if the mutex is expected to be available soon, avoiding context switch overhead.

4. Hybrid Synchronization (Solaris)

  • Utilizes a combination of spinlock and blocking synchronization:

    • Start with a spinlock; if the mutex is available, enter the critical section (C.S.).

    • Spin for a limited time; if the mutex is not available, switch to blocking synchronization.

  • Relevant primarily for multiprocessor systems.

5. False Sharing

  • An issue arising from hardware peculiarities, impacting performance in multi-threading scenarios.

6. The Priority Inversion Problem

  • Occurs when a low-priority thread holds a lock that a higher-priority thread needs, leading to a system halt if a medium-priority thread intervenes.

7. Solution: Priority Inheritance

  • Temporarily boost the priority of the low-priority thread holding the lock to match the higher-priority thread requesting it.

8. Starvation Problem

  • May occur if the synchronization mechanism is improperly implemented, for example, a semaphore implementing LIFO order.

9. Deadlock Problem

  • A condition where two or more threads are waiting indefinitely for each other to release resources.

  • Common in systems employing mutexes.

10. Example of Deadlock

  • A classic example illustrates cyclical wait:

    • Thread 1 requesting a resource held by Thread 2 while Thread 2 waits on Thread 1's resource.

11. Deadlock Prevention Strategies

  • Linear resource ordering

  • Threads must request resources in a specific order to prevent deadlocks.

  • While effective, this method can be inflexible and does not scale well.

12. Deadlock Resolution Strategies

  • Allow deadlock to occur and address it through analysis:

    • Identify and kill a victim process to break the deadlock.

13. Deadline Detection

  • Using a graph to identify deadlocks—the cyclic wait condition indicates a deadlock.

14. Synchronization Bugs

  • Bugs arising due to inadequate protection of shared variables can lead to unpredictable behaviors.

15. Denial of Service Problem

  • Conditions where liveness (ongoing progress) is not guaranteed due to unsafe synchronizations.

16. Transactions and Concurrency Control

  • An informal definition of a transaction: a piece of code that accesses shared resources without interference.

  • It is critical for the operations to execute atomically.

17. Real-World Use Cases of Transactions

  • Example involving bank transactions needs coordinated control over account updates, ensuring atomic outcomes.

18. Transaction Properties (ACID)

  • Atomicity: All operations must succeed or none at all.

  • Consistency: Database remains in a consistent state before and after transactions.

  • Isolation: Each transaction executes as if no other transactions are occurring concurrently.

  • Durability: Once committed, the transaction's effects should remain despite failures.

19. Performance Considerations in Transactions

  • Balancing throughput (transactions per second) and latency (time to transaction completion).

20. Challenges with Serializability

  • Goal: Identify a schedule equivalent to some serial order while maximizing throughput and concurrency.

  • Finding all possible serializable orders is NP-complete.

21. Cascaded Aborts

  • Occur when one transaction's abort affects others that have read its temporary values.

22. Practical Considerations for Scheduling

  • Dynamic transaction creation necessitates a reliable scheduling mechanism.

  • Two-phase locking (acquisition and release phases) is a common solution to avoid issues like cascaded aborts.

23. Two-Phase Commit Protocol

  • Protocol involving coordination across multiple databases where local transactions rely on each other, with a phase for voting to commit or abort.

24. Addressing Multi-Database Transactions

  • Multi-database transactions require communication protocols and a commitment to maintain data integrity among various databases.

25. Addressing Network Partitions

  • A network partition can complicate transaction management requiring quorum systems or alternative voting mechanisms.