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

0% completed

Vote For New Content
Problem 9: Print in Order using multithreading
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 problem at hand is ensuring the ordered execution of methods across different threads. Essentially, we have three methods: first(), second(), and third(). The objective is to guarantee that irrespective of the order in the threads are triggered or scheduled, first() must execute before second(), and second() must execute before third().

In concurrent programming, it's challenging to ensure the execution order because the operating system can schedule threads in any sequence. This means even if you start thread A (that calls first()) before thread B (that calls second()), there's no guarantee A will execute before B.

To ensure the desired order of execution, we need to use synchronization primitives. These primitives will block or allow threads to proceed based on certain conditions, thus ensuring our desired order.

Step-by-step Algorithm

To solve this problem, we need synchronization mechanisms that will enable one thread to wait until another thread completes its task. For this, we'll use semaphores.

Semaphores are signaling mechanisms. A thread waiting (or sleeping) on a semaphore can be notified to wake up by another thread which signals the semaphore. For our scenario:

  1. Initialize two semaphores: semFirstDone and semSecondDone.
  2. semFirstDone will be signaled once first() completes. Until then, any thread trying to execute second() will wait.
  3. Similarly, semSecondDone will be signaled once second() completes. Until then, any thread trying to execute third() will wait.
initialize semFirstDone = 0 // This means no thread can pass without a signal initialize semSecondDone = 0 // Same for this semaphore function first(): // execute the 'first' task print("first") signal semFirstDone // Inform that the 'first' task is done function second(): wait on semFirstDone // Wait until 'first' is done // execute the 'second' task print("second") signal semSecondDone // Inform that the 'second' task is done function third(): wait on semSecondDone // Wait until 'second' is done // execute the 'third' task print("third")

The key insight here is that semFirstDone starts at 0, so any thread calling second() will have to wait until it's signaled. Similarly, semSecondDone ensures the third() function waits for second() to complete. This setup guarantees our desired order of execution, regardless of the order in which threads are started.

mediaLink

1 of 4

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