Concurrency Control

Concurrency Control via Synchronization

1. Need for Synchronization

• Activities in computing often share resources.

• It is crucial to coordinate their progress to ensure that these shared resources are utilized properly.

2. Examples of Coordination

• Scenario 1:

  • John and Mary are each printing different 10-page documents on the same printer.

  • Objective: Prevent interleaving of their pages/output.

  • Concept: Exclusion is necessary.

• Scenario 2:

  • John and Mary share a bank account.

  • If John deposits $10, Mary should be allowed to withdraw from the account only after the deposit has been successfully processed.

  • Concept: Ordering is essential to maintain the integrity of transactions.

3. Resources

• Shared resources can be categorized as follows:

  • Physical Resources:

    • Examples include terminals, disks, networks, etc.

  • Logical Resources:

    • Examples include files, sockets, memory, etc.

• Focus Area:

  • For this discussion, we will concentrate on memory as the shared resource.

  • Multiple threads can read from and write to shared memory variables.

4. Problems Due to Sharing

• Example with a Shared Printer Queue:

  • Consider a shared printer queue denoted as spool_queue[N].

  • Two threads are attempting to enqueue an element into this queue.

  • The variable tail points to the current end of the queue.

  • Each thread needs to execute the following steps:

  • tail = tail + 1;

  • spool_queue[tail] = "element";

5. The Execution Process

• Visualization of Threads:

  • As both threads (Thread 1 and Thread 2) execute their operations, the process can be illustrated as follows:

  • Thread 1:

    • tail = tail + 1;

    • spool_queue[tail] = X

  • Thread 2:

    • tail = tail + 1;

    • spool_queue[tail] = Y

6. What is the Problem?

• The instruction tail = tail + 1 is not a single machine instruction.

• This operation can be broken down into three separate machine instructions:

  • Load tail, R1

  • Add R1, 1, R2

  • Store R2, tail

• Implication: These three machine instructions may not execute atomically.

7. Context Switching Between Threads

• While each thread is executing this triplet of instructions, context switching can occur.

• Illustrative Sequence of Executed Instructions:

  • 1: Load tail, R1

  • 2: Load tail, R1

  • 1: Add R1, 1, R2

  • 2: Add R1, 1, R2

  • 1: Store R2, tail

  • 2: Store R2, tail

8. Resulting Sequence and Problems

• The sequential executions lead to potential erroneous behavior:

  • Final State After Execution:

    • Thread 1:

      • tail = tail + 1;

      • spool_queue[tail] = X

    • Thread 2:

      • tail = tail + 1;

      • spool_queue[tail] = Y

9. Race Conditions

• The various scenarios that can arise from the interleaving of threads leading to unexpected behaviors are termed race conditions.

• Challenge: Debugging race conditions proves to be difficult, as errors are often non-repeatable.

10. Avoiding Race Conditions

• A potential solution to race conditions is to ensure that the execution of the series of three instructions is atomic.

  • This means while one thread is executing the instructions, no other thread can execute the same instructions concurrently.

• These three instructions are considered to form a critical section.

  • Mutual Exclusion: While one thread is within a critical section, another thread should not be permitted to execute the same critical section, thereby ensuring orderly access to shared resources.