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.