Grokking Multithreading and Concurrency for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Problem 13: Synchronization of Dual Threads
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Overview

The "Synchronization of Dual Threads" problem is a classic demonstration of concurrent thread management. Given two threads, A and B, with the responsibilities of printing "foo" and "bar" respectively, the task is to ensure a synchronized output of "foobar" repetitively for a given 'n' times. This problem emphasizes the significance of thread synchronization in producing consistent and predictable results in concurrent systems.

Pseudocode

Initialize a semaphore or mutex called fooLock with a value of 1
Initialize a semaphore or mutex called barLock with a value of 0

Function printFoo():
    for i from 1 to n do:
        Acquire fooLock
        Print "foo"
        Release barLock

Function printBar():
    for i from 1 to n do:
        Acquire barLock
        Print "bar"
        Release fooLock

Main:
    Start Thread A -> Target: printFoo
    Start Thread B -> Target: printBar

Explanation

  1. We start by defining a FooBar class that has methods foo and bar to print "foo" and "bar" respectively.
  2. The synchronization is achieved using a mutex mtx and two condition variables fooPrinted and barPrinted.
  3. In the foo method, we ensure that "foo" is printed first. Once printed, it sets fooDone to true and signals the barPrinted condition variable to allow the bar method to print "bar".
  4. The bar method waits for fooDone to be true. Once "bar" is printed, it resets fooDone to false and signals the fooPrinted condition variable to allow the next iteration.
  5. In the main function, we create two threads, threadFoo and threadBar, to execute the foo and bar methods respectively.
  6. The pthread_join function ensures the main thread waits for both threads to finish their execution.

Algorithm Walkthrough

Let’s emphasize synchronization aspects in the walkthrough to help understand how the program ensures proper ordering of "foo" and "bar" printing.

Initial Setup

  • Create foobar: An instance of FooBar with n = 5.
  • Initialize Synchronization Primitives: mtx, fooPrinted, and barPrinted.
  • Set Flag: fooDone is set to false.

Starting Threads

  • Start threadFoo: Initiates foobar.foo(), which contains the logic to print "foo".
  • Start threadBar: Initiates foobar.bar(), which contains the logic to print "bar".

Walkthrough of Loop Iterations with Synchronization Focus:

Iteration 1

  • threadFoo:

    1. Acquire Lock: Locks mtx to enter the critical section.
    2. Check Condition: Since fooDone is false, it proceeds without waiting.
    3. Print "foo": Outputs "foo" to the console.
    4. Update Flag: Sets fooDone to true.
    5. Signal threadBar: Signals barPrinted to wake up threadBar (if it's waiting).
    6. Release Lock: Unlocks mtx.

  • threadBar

    1. Acquire Lock: Locks mtx to enter the critical section.
    2. Wait for "foo": Waits on barPrinted until fooDone is true (ensures "foo" is printed before "bar").
    3. Print "bar": Outputs "bar" to the console (completing "foobar").
    4. Update Flag: Sets fooDone to false.
    5. Signal threadFoo: Signals fooPrinted to wake up threadFoo for the next iteration.
    6. Release Lock: Unlocks mtx.

Iterations 2 to 5

  • Repeat the Steps: The same synchronization-focused steps as Iteration 1 are repeated. This ensures that "foo" is always printed before "bar" and "foobar" is printed 5 times in total.

Joining Threads

  • Wait for threadFoo: pthread_join(thread1, NULL) ensures the main thread waits until threadFoo has finished executing.
  • Wait for threadBar: pthread_join(thread2, NULL) ensures the main thread waits until threadBar has finished executing.

Final Result

  • By the end of the program, "foobar" has been printed 5 times. The synchronization constructs (mutex and condition variables) have ensured that "foo" is always printed before "bar", maintaining the proper order despite the concurrent execution of threads. The program showcases a critical aspect of multithreading – ensuring coordinated execution and maintaining the integrity of shared resources (in this case, the order of "foo" and "bar" printing).
Flow Chart
Flow Chart
Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible