The ultimate guide to Ruby concurrency interviews. Developed by FAANG engineers, this course covers Monitors, Deferred Callbacks and problem-solving strategies for Reader-Writer and Dining Philosopher Problems.

Concurrency in Ruby is one of the most complex and advanced topics brought up during senior engineering interviews. Knowledge of concurrency and multithreading can put interviewees at a considerable advantage. This course lays the foundations of advanced concurrency and multithreading and explains concepts such as Monitors and Deferred Callbacks in depth. It also builds simple and complete solutions to popular concurrency problems that can be asked about in interviews like the Reader-Writer Problem and the Dining Philosopher Problem. While prior knowledge of concurrency is not required to follow through with this course, familiarity with the basics of Ruby would be helpful.

Ruby Concurrency for Senior Engineering Interviews

<div class="card">
   # Implementing Semaphore
    <div class="ans">
    <p>Ruby's concurrent gem does provide its own implementation of <code class="clazz">Semaphore</code>; however, it is an interesting exercise to learn to implement a semaphore using a monitor.</p>

<p> Briefly, a semaphore is a construct that allows some threads to access a fixed set of resources in parallel. Always think of a semaphore as having a fixed number of permits to give out. Once all the permits are given out, requesting threads need to wait for a permit to be returned before proceeding forward.</p>

<p>Your task is to implement a semaphore which takes in its constructor the maximum number of permits allowed and is also initialized with the same number of permits. Additionally, if all the permits have been given out, the semaphore blocks threads attempting to acquire it.</p>
</div>
</div>

  <div class="card">
   # Solution
  <div class="ans">
<p>Given the above definition, we can now start to think of what functions our Semaphore class will need to expose. We need a function to "gain the permit" and a function to "return the permit".</p>

<ol>
  <li><code class="mthd">acquire()</code> function to simulate gaining a permit</li>
  <li><code class="mthd">release()</code> function to simulate releasing a permit</li>
  </ol>

<p>The constructor accepts an integer parameter defining the number of permits available with the semaphore. Internally we need to store a count which keeps track of the permits given out so far.

The skeleton for our Semaphore class looks something like this so far.</p>
<b>

```ruby
class CountingSemaphore

  def initialize(maxPermits)
    @maxPermits = maxPermits
    @givenOut = 0
  end

  def acquire()

  end

  def release()

  end

end
```
</b>

<p>Realize that the two methods <code class="mthd">acquire()</code> and <code class="mthd">release()</code> can be invoked at the same time by different threads and therefore we need to guard the logic inside of them by some kind of lock.</p>

<p>We can use the <code class="clazz">Monitor</code> class for mutual exclusion as well as for signaling among threads.</p>

<p>Now let us fill in the implementation for our <code class="mthd">acquire()</code> method. When can a thread not be allowed to acquire a semaphore? When all the permits are given out. This implies we'll need to wait for a permit to become available when <code class="mthd"> givenOut == maxPermits</code> If this condition isn't true we simply increment <code class="mthd">givenOut</code> to simulate giving out a permit. The fact that we need to <i>wait</i> for a permit if none is available should ring a bell. We can create a condition variable using the monitor object and <code class="mthd">wait()</code> on the condition variable.</p>

</p>The implementation of the <code class="mthd">acquire()</code> method appears below. Note that we are also <code class="mthd">broadcast()</code>-ing the condition variable <code class="mthd">condVar</code> at the end of the method. We'll talk shortly, about why we broadcast instead of signal.</p>


```ruby
  def acquire()

    @monitor.enter()

    while @givenOut == @maxPermits
      @condVar.wait()
    end

    @givenOut += 1
    @condVar.broadcast()
    
    @monitor.exit()
  end
```

<p>Implementing the <code class="mthd">release()</code> method should require a simple decrement of the <code class="mthd">givenOut</code> variable. However, when should we block a thread from proceeding forward like we did in <code class="mthd">acquire()</code> method? If <code class="mthd">givenOut == 0</code> then it won't make sense to decrement <code class="mthd">givenOut</code> and we should block on this predicate.</p> 

<p>This might seem counter-intuitive, you might ask why would someone call <code class="mthd">release()</code> before calling <code class="mthd">acquire()</code> - This is entirely possible since semaphore can also be used for signaling among threads. A thread can call <code class="mthd">release()</code> on a semaphore object before another thread calls <code class="mthd">acquire()</code> on the same semaphore object. There is no concept of ownership for a semaphore! Hence different threads can call acquire or release methods as they deem fit.</p>

<p>This also means that whenever we decrement or increment the <code class="mthd">givenOut</code> variable we need to invoke <code class="mthd">broadcast()</code> method on the condition variable so that any waiting thread in the other method is able to move forward. The full implementation appears below:</p>
<b>

```ruby
class CountingSemaphore

  def initialize(maxPermits)
    @maxPermits = maxPermits
    @givenOut = 0
    @monitor = Monitor.new
    @condVar = @monitor.new_cond()
  end

  def acquire()
    @monitor.enter()

    while @givenOut == @maxPermits
      @condVar.wait()
    end

    @givenOut += 1
    @condVar.broadcast()

    @monitor.exit()
  end

  def release()
    @monitor.enter()

    while @givenOut == 0
      @condVar.wait()
    end

    @givenOut -= 1
    @condVar.broadcast()

    @monitor.exit()
  end

end
```
</b>
<br/>

## Follow up Question#1
<p>Note that in both the methods, we increment or decrement the variable <code class="mthd">givenOut</code> before invoking <code class="mthd">broadcast()</code> on the <code class="mthd">padlock</code> variable. Does it matter if we switch the order of the two statements in the two methods? The answer is no. A thread inside either of the methods holds the lock associated with the monitor until the point the thread invokes <code class="mthd">monitor.exit()</code>, which is the last statement in both the methods. A thread waiting on the condition variable when notified must acquire the monitor again, before resuming execution, therefore, the order of the two statements doesn't matter.</p>

## Follow up Question#2
<p>Does it matter whether we use <code class="mthd">broadcast()</code> or <code class="mthd">signal()</code>? Reason about it this way: is it possible that two threads are blocked on the condition variable in both the <code class="mthd">acquire()</code> and <code class="mthd">release()</code> methods at the same time? Let's assume they are then a <code class="mthd">signal()</code> may wake-up the wrong thread whose predicate is still false. The woken-up thread will go back to waiting and the program would hang since <code class="mthd">signal()</code> wakes up a single thread. However, if threads can only be waiting on the condition variable in the method other than the one from which we signal the condition variable then it should not matter whether we use <code class="mthd">broadcast()</code> or <code class="mthd">signal()</code>. Using <code class="mthd">PulseAll()</code> will allow only one thread out of the waiting ones to make progress and the rest would go back to waiting.</p>

## Test Case
<p>In the example below, we have two threads, one always acquires the semaphore while the other always releases it. The execution of the two threads is staggered. We are using the semaphore as a signaling mechanism between the two threads.</p>

</div>
</div>

<div>
   # Implementing Semaphore
    <div>
    <p>Ruby's concurrent gem does provide its own implementation of <code>Semaphore</code>; however, it is an interesting exercise to learn to implement a semaphore using a monitor.</p>

<p> Briefly, a semaphore is a construct that allows some threads to access a fixed set of resources in parallel. Always think of a semaphore as having a fixed number of permits to give out. Once all the permits are given out, requesting threads need to wait for a permit to be returned before proceeding forward.</p>

<p>Your task is to implement a semaphore which takes in its constructor the maximum number of permits allowed and is also initialized with the same number of permits. Additionally, if all the permits have been given out, the semaphore blocks threads attempting to acquire it.</p>
</div>
</div>

  <div>
   # Solution
  <div>
<p>Given the above definition, we can now start to think of what functions our Semaphore class will need to expose. We need a function to "gain the permit" and a function to "return the permit".</p>

<ol>
  <li><code>acquire()</code> function to simulate gaining a permit</li>
  <li><code>release()</code> function to simulate releasing a permit</li>
  </ol>

<p>The constructor accepts an integer parameter defining the number of permits available with the semaphore. Internally we need to store a count which keeps track of the permits given out so far.

The skeleton for our Semaphore class looks something like this so far.</p>
<b>

```ruby
class CountingSemaphore

  def initialize(maxPermits)
    @maxPermits = maxPermits
    @givenOut = 0
  end

  def acquire()

  end

  def release()

  end

end
```
</b>

<p>Realize that the two methods <code>acquire()</code> and <code>release()</code> can be invoked at the same time by different threads and therefore we need to guard the logic inside of them by some kind of lock.</p>

<p>We can use the <code>Monitor</code> class for mutual exclusion as well as for signaling among threads.</p>

<p>Now let us fill in the implementation for our <code>acquire()</code> method. When can a thread not be allowed to acquire a semaphore? When all the permits are given out. This implies we'll need to wait for a permit to become available when <code> givenOut == maxPermits</code> If this condition isn't true we simply increment <code>givenOut</code> to simulate giving out a permit. The fact that we need to <i>wait</i> for a permit if none is available should ring a bell. We can create a condition variable using the monitor object and <code>wait()</code> on the condition variable.</p>

</p>The implementation of the <code>acquire()</code> method appears below. Note that we are also <code>broadcast()</code>-ing the condition variable <code>condVar</code> at the end of the method. We'll talk shortly, about why we broadcast instead of signal.</p>


```ruby
  def acquire()

    @monitor.enter()

    while @givenOut == @maxPermits
      @condVar.wait()
    end

    @givenOut += 1
    @condVar.broadcast()
    
    @monitor.exit()
  end
```

<p>Implementing the <code>release()</code> method should require a simple decrement of the <code>givenOut</code> variable. However, when should we block a thread from proceeding forward like we did in <code>acquire()</code> method? If <code>givenOut == 0</code> then it won't make sense to decrement <code>givenOut</code> and we should block on this predicate.</p> 

<p>This might seem counter-intuitive, you might ask why would someone call <code>release()</code> before calling <code>acquire()</code> - This is entirely possible since semaphore can also be used for signaling among threads. A thread can call <code>release()</code> on a semaphore object before another thread calls <code>acquire()</code> on the same semaphore object. There is no concept of ownership for a semaphore! Hence different threads can call acquire or release methods as they deem fit.</p>

<p>This also means that whenever we decrement or increment the <code>givenOut</code> variable we need to invoke <code>broadcast()</code> method on the condition variable so that any waiting thread in the other method is able to move forward. The full implementation appears below:</p>
<b>

```ruby
class CountingSemaphore

  def initialize(maxPermits)
    @maxPermits = maxPermits
    @givenOut = 0
    @monitor = Monitor.new
    @condVar = @monitor.new_cond()
  end

  def acquire()
    @monitor.enter()

    while @givenOut == @maxPermits
      @condVar.wait()
    end

    @givenOut += 1
    @condVar.broadcast()

    @monitor.exit()
  end

  def release()
    @monitor.enter()

    while @givenOut == 0
      @condVar.wait()
    end

    @givenOut -= 1
    @condVar.broadcast()

    @monitor.exit()
  end

end
```
</b>
<br/>

## Follow up Question#1
<p>Note that in both the methods, we increment or decrement the variable <code>givenOut</code> before invoking <code>broadcast()</code> on the <code>padlock</code> variable. Does it matter if we switch the order of the two statements in the two methods? The answer is no. A thread inside either of the methods holds the lock associated with the monitor until the point the thread invokes <code>monitor.exit()</code>, which is the last statement in both the methods. A thread waiting on the condition variable when notified must acquire the monitor again, before resuming execution, therefore, the order of the two statements doesn't matter.</p>

## Follow up Question#2
<p>Does it matter whether we use <code>broadcast()</code> or <code>signal()</code>? Reason about it this way: is it possible that two threads are blocked on the condition variable in both the <code>acquire()</code> and <code>release()</code> methods at the same time? Let's assume they are then a <code>signal()</code> may wake-up the wrong thread whose predicate is still false. The woken-up thread will go back to waiting and the program would hang since <code>signal()</code> wakes up a single thread. However, if threads can only be waiting on the condition variable in the method other than the one from which we signal the condition variable then it should not matter whether we use <code>broadcast()</code> or <code>signal()</code>. Using <code>PulseAll()</code> will allow only one thread out of the waiting ones to make progress and the rest would go back to waiting.</p>

## Test Case
<p>In the example below, we have two threads, one always acquires the semaphore while the other always releases it. The execution of the two threads is staggered. We are using the semaphore as a signaling mechanism between the two threads.</p>

</div>
</div>

In this lesson, you will learn how to design and implement a simple semaphore class in Ruby.

The Basics

API Overview

Brief Intro to Asynchronous Programming

Interview Practice Problems

Bonus Questions

Epilogue

Implementing Semaphore

Implementing Semaphore