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">
 # Amdahl's Law 
 <div class="ans">
No text on concurrency is complete without mentioning Amdahl's Law. The law specifies the cap on the maximum speedup that can be achieved when parallelizing the execution of a program.

If you have a poultry farm where a hundred hens lay eggs each day, then no matter how many people you hire to process the laid eggs, you still need to wait an entire day for the 100 eggs to be laid. Increasing the number of workers on the farm can't shorten the time it takes for a hen to lay an egg. Similarly, software programs consist of parts that can't be sped up even if the number of processors is increased. These parts of the program must execute serially and aren't amenable to parallelism.

Amdahl's law describes the theoretical speedup a program can achieve at best by using additional computing resources. We'll skip the mathematical derivation and go straight to the simplified equation expressing Amdahl's law: 

<img alt="S(n)=\frac{1}{(1-P)+\frac{P}{n}}" class="img-responsive" src="https://latex.codecogs.com/gif.latex?S%28n%29%3D%5Cfrac%7B1%7D%7B%281-P%29+%5Cfrac%7BP%7D%7Bn%7D%7D" style="margin: 0px auto; height: auto;">
 

<ul>
<li>S(n) is the speed-up achieved by using n cores or threads.</li>

<li>P is the fraction of the program that is parallelizable.</li>

<li>(1 - P) is the fraction of the program that must be executed serially.</li>
</ul>

 ## Example
Say our program has a parallelizable portion of P = 90% = 0.9. Now let's see how the speed-up occurs as we increase the number of processes. 
<ul>
<li>n = 1 processor 
<img alt="S(1) = \frac{1}{(1-P) + \frac{P}{1}} = \frac{1}{1-P + P} = 1" class="img-responsive" src="https://latex.codecogs.com/gif.latex?S(1)%20%3D%20%5Cfrac%7B1%7D%7B(1-P)%20%2B%20%5Cfrac%7BP%7D%7B1%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B1-P%20%2B%20P%7D%20%3D%201" style="margin: 0px auto; height: auto;">
</li>
<li>n = 2 processors 
<img alt="S(2) = \frac{1}{(1-0.9) + \frac{0.9}{2}} = \frac{1}{0.1 + 0.45} = 1.81" class="img-responsive" src="https://latex.codecogs.com/gif.latex?S(2)%20%3D%20%5Cfrac%7B1%7D%7B(1-0.9)%20%2B%20%5Cfrac%7B0.9%7D%7B2%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B0.1%20%2B%200.45%7D%20%3D%201.81" style="margin: 0px auto; height: auto;">
</li>
<li>n = 5 processors 
<img alt="S(5) = \frac{1}{(1-0.9) + \frac{0.9}{5}} = \frac{1}{0.1 + 0.18} = 3.57" class="img-responsive" src="https://latex.codecogs.com/gif.latex?S(5)%20%3D%20%5Cfrac%7B1%7D%7B(1-0.9)%20%2B%20%5Cfrac%7B0.9%7D%7B5%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B0.1%20%2B%200.18%7D%20%3D%203.57" style="margin: 0px auto; height: auto;">
</li>
<li>n = 10 processors 
<img alt="S(10) = \frac{1}{(1-0.9) + \frac{0.9}{10}} = \frac{1}{0.1 + 0.45} = 5.26" class="img-responsive" src="https://latex.codecogs.com/gif.latex?S(10)%20%3D%20%5Cfrac%7B1%7D%7B(1-0.9)%20%2B%20%5Cfrac%7B0.9%7D%7B10%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B0.1%20%2B%200.09%7D%20%3D%205.26" style="margin: 0px auto; height: auto;">
</li>
<li>n = 100 processors 
<img alt="S(100) = \frac{1}{(1-0.9) + \frac{0.9}{100}} = \frac{1}{0.1 + 0.45} = 9.17" class="img-responsive" src="https://latex.codecogs.com/gif.latex?S(100)%20%3D%20%5Cfrac%7B1%7D%7B(1-0.9)%20%2B%20%5Cfrac%7B0.9%7D%7B100%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B0.1%20%2B%200.009%7D%20%3D%209.17" style="margin: 0px auto; height: auto;">
</li>
<li>n = 1000 processors 
<img alt="S(1000) = \frac{1}{(1-0.9) + \frac{0.9}{1000}} = \frac{1}{0.1 + 0.0009} = 9.91" class="img-responsive" src="https://latex.codecogs.com/gif.latex?S(1000)%20%3D%20%5Cfrac%7B1%7D%7B(1-0.9)%20%2B%20%5Cfrac%7B0.9%7D%7B1000%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B0.1%20%2B%200.0009%7D%20%3D%209.91" style="margin: 0px auto; height: auto;">
</li>
<li>n = infinite processors 
<img alt="S(infinite) = \frac{1}{(1-0.9) + \frac{0.9}{1000}} = \frac{1}{0.1 + 0.0009} = 9.91" class="img-responsive" src="https://latex.codecogs.com/gif.latex?S(\infty)%20%3D%20%5Cfrac%7B1%7D%7B(1-0.9)%20%2B%20%5Cfrac%7B0.9%7D%7B%5Cinfty%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B0.1%20%2B%200%7D%20%3D%2010" style="margin: 0px auto; height: auto;">
</li>
</ul>

The speed-up steadily increases as we increase the number of processors or threads. However, as you can see the theoretical maximum speed-up for our program with 10% serial execution will be 10. We can't speed-up our program execution more than 10 times compared to when we run the same program on a single CPU or thread. To achieve greater speed-ups than 10 we must optimize or parallelize the serially executed portion of the code.

Another important aspect to realize is that when we speed-up our program execution by roughly 5 times, we do so by employing 10 processors. The utilization of these 10 processors, in turn, decreases by roughly 50% because now the 10 processors remain idle for the rest of the time that a single processor would have been busy. Utilization is defined as the speed-up divided by the number of processors.

As an example, say the program runs in 10 minutes using a single core. We assumed the parallelizable portion of the program is 90%, which implies 1 minute of the program time must execute serially. The speedup we can achieve with 10 processors is roughly 5 times, which comes out to be 2 minutes of total program execution time. Out of those 2 minutes, 1 minute is of mandatory serial execution while the rest can all be parallelized. This implies that 9 of the processors will complete 90% of the non-serial work in 1 minute while 1 processor remains idle and then one out of the 10 processors, will execute the serial portion for another minute. The rest of the 9 processors are idle for that 1 minute during which the serial execution takes place. In effect, the combined utilization of the ten processors drops by 50%.

As N approaches infinity, the Amdahl's law takes the following form:

 

<img alt="S(n)=\frac{1}{(1-P)+\frac{P}{n}}" class="img-responsive" src="https://latex.codecogs.com/gif.latex?S(n)%3D%5Cfrac%7B1%7D%7B(1-P)%7D%20%3D%20%5Cfrac%7B1%7D%7Bfraction%5C%3Aof%5C%3Aprogram%5C%3Aserially%5C%3Aexecuted%7D" style="margin: 0px auto; height: auto;">

 

One should take the calculations using Amdahl's law with a grain of salt. If the formula spits out a speed-up of 5x, it doesn't imply that, in reality, one would observe a similar speed-up. There are other factors such as the memory architecture, cache misses, network and disk I/O, etc, that can affect the execution time of a program. The actual speed-up might be less than the calculated one.

Amdahl's law works on a problem of fixed size. However, as computing resources are improved, algorithms run on larger and even larger datasets. As the dataset size grows, the parallelizable portion of the program grows faster than the serial portion and a more realistic assessment of performance is given by Gustafson's law, which we won't discuss here as it is beyond the scope of this text.



</div>

</div>

<div>
 # Amdahl's Law 
 <div>
No text on concurrency is complete without mentioning Amdahl's Law. The law specifies the cap on the maximum speedup that can be achieved when parallelizing the execution of a program.

If you have a poultry farm where a hundred hens lay eggs each day, then no matter how many people you hire to process the laid eggs, you still need to wait an entire day for the 100 eggs to be laid. Increasing the number of workers on the farm can't shorten the time it takes for a hen to lay an egg. Similarly, software programs consist of parts that can't be sped up even if the number of processors is increased. These parts of the program must execute serially and aren't amenable to parallelism.

Amdahl's law describes the theoretical speedup a program can achieve at best by using additional computing resources. We'll skip the mathematical derivation and go straight to the simplified equation expressing Amdahl's law: 

<img alt="S(n)=\frac{1}{(1-P)+\frac{P}{n}}" src="https://latex.codecogs.com/gif.latex?S%28n%29%3D%5Cfrac%7B1%7D%7B%281-P%29+%5Cfrac%7BP%7D%7Bn%7D%7D" style="margin: 0px auto; height: auto;">
 

<ul>
<li>S(n) is the speed-up achieved by using n cores or threads.</li>

<li>P is the fraction of the program that is parallelizable.</li>

<li>(1 - P) is the fraction of the program that must be executed serially.</li>
</ul>

 ## Example
Say our program has a parallelizable portion of P = 90% = 0.9. Now let's see how the speed-up occurs as we increase the number of processes. 
<ul>
<li>n = 1 processor 
<img alt="S(1) = \frac{1}{(1-P) + \frac{P}{1}} = \frac{1}{1-P + P} = 1" src="https://latex.codecogs.com/gif.latex?S(1)%20%3D%20%5Cfrac%7B1%7D%7B(1-P)%20%2B%20%5Cfrac%7BP%7D%7B1%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B1-P%20%2B%20P%7D%20%3D%201" style="margin: 0px auto; height: auto;">
</li>
<li>n = 2 processors 
<img alt="S(2) = \frac{1}{(1-0.9) + \frac{0.9}{2}} = \frac{1}{0.1 + 0.45} = 1.81" src="https://latex.codecogs.com/gif.latex?S(2)%20%3D%20%5Cfrac%7B1%7D%7B(1-0.9)%20%2B%20%5Cfrac%7B0.9%7D%7B2%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B0.1%20%2B%200.45%7D%20%3D%201.81" style="margin: 0px auto; height: auto;">
</li>
<li>n = 5 processors 
<img alt="S(5) = \frac{1}{(1-0.9) + \frac{0.9}{5}} = \frac{1}{0.1 + 0.18} = 3.57" src="https://latex.codecogs.com/gif.latex?S(5)%20%3D%20%5Cfrac%7B1%7D%7B(1-0.9)%20%2B%20%5Cfrac%7B0.9%7D%7B5%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B0.1%20%2B%200.18%7D%20%3D%203.57" style="margin: 0px auto; height: auto;">
</li>
<li>n = 10 processors 
<img alt="S(10) = \frac{1}{(1-0.9) + \frac{0.9}{10}} = \frac{1}{0.1 + 0.45} = 5.26" src="https://latex.codecogs.com/gif.latex?S(10)%20%3D%20%5Cfrac%7B1%7D%7B(1-0.9)%20%2B%20%5Cfrac%7B0.9%7D%7B10%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B0.1%20%2B%200.09%7D%20%3D%205.26" style="margin: 0px auto; height: auto;">
</li>
<li>n = 100 processors 
<img alt="S(100) = \frac{1}{(1-0.9) + \frac{0.9}{100}} = \frac{1}{0.1 + 0.45} = 9.17" src="https://latex.codecogs.com/gif.latex?S(100)%20%3D%20%5Cfrac%7B1%7D%7B(1-0.9)%20%2B%20%5Cfrac%7B0.9%7D%7B100%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B0.1%20%2B%200.009%7D%20%3D%209.17" style="margin: 0px auto; height: auto;">
</li>
<li>n = 1000 processors 
<img alt="S(1000) = \frac{1}{(1-0.9) + \frac{0.9}{1000}} = \frac{1}{0.1 + 0.0009} = 9.91" src="https://latex.codecogs.com/gif.latex?S(1000)%20%3D%20%5Cfrac%7B1%7D%7B(1-0.9)%20%2B%20%5Cfrac%7B0.9%7D%7B1000%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B0.1%20%2B%200.0009%7D%20%3D%209.91" style="margin: 0px auto; height: auto;">
</li>
<li>n = infinite processors 
<img alt="S(infinite) = \frac{1}{(1-0.9) + \frac{0.9}{1000}} = \frac{1}{0.1 + 0.0009} = 9.91" src="https://latex.codecogs.com/gif.latex?S(\infty)%20%3D%20%5Cfrac%7B1%7D%7B(1-0.9)%20%2B%20%5Cfrac%7B0.9%7D%7B%5Cinfty%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B0.1%20%2B%200%7D%20%3D%2010" style="margin: 0px auto; height: auto;">
</li>
</ul>

The speed-up steadily increases as we increase the number of processors or threads. However, as you can see the theoretical maximum speed-up for our program with 10% serial execution will be 10. We can't speed-up our program execution more than 10 times compared to when we run the same program on a single CPU or thread. To achieve greater speed-ups than 10 we must optimize or parallelize the serially executed portion of the code.

Another important aspect to realize is that when we speed-up our program execution by roughly 5 times, we do so by employing 10 processors. The utilization of these 10 processors, in turn, decreases by roughly 50% because now the 10 processors remain idle for the rest of the time that a single processor would have been busy. Utilization is defined as the speed-up divided by the number of processors.

As an example, say the program runs in 10 minutes using a single core. We assumed the parallelizable portion of the program is 90%, which implies 1 minute of the program time must execute serially. The speedup we can achieve with 10 processors is roughly 5 times, which comes out to be 2 minutes of total program execution time. Out of those 2 minutes, 1 minute is of mandatory serial execution while the rest can all be parallelized. This implies that 9 of the processors will complete 90% of the non-serial work in 1 minute while 1 processor remains idle and then one out of the 10 processors, will execute the serial portion for another minute. The rest of the 9 processors are idle for that 1 minute during which the serial execution takes place. In effect, the combined utilization of the ten processors drops by 50%.

As N approaches infinity, the Amdahl's law takes the following form:

 

<img alt="S(n)=\frac{1}{(1-P)+\frac{P}{n}}" src="https://latex.codecogs.com/gif.latex?S(n)%3D%5Cfrac%7B1%7D%7B(1-P)%7D%20%3D%20%5Cfrac%7B1%7D%7Bfraction%5C%3Aof%5C%3Aprogram%5C%3Aserially%5C%3Aexecuted%7D" style="margin: 0px auto; height: auto;">

 

One should take the calculations using Amdahl's law with a grain of salt. If the formula spits out a speed-up of 5x, it doesn't imply that, in reality, one would observe a similar speed-up. There are other factors such as the memory architecture, cache misses, network and disk I/O, etc, that can affect the execution time of a program. The actual speed-up might be less than the calculated one.

Amdahl's law works on a problem of fixed size. However, as computing resources are improved, algorithms run on larger and even larger datasets. As the dataset size grows, the parallelizable portion of the program grows faster than the serial portion and a more realistic assessment of performance is given by Gustafson's law, which we won't discuss here as it is beyond the scope of this text.



</div>

</div>

Blindly adding threads to speed up program execution may not always be a good idea. In this lesson, let’s find out what Amdahl's Law says about parallelizing a program.

The Basics

API Overview

Brief Intro to Asynchronous Programming

Interview Practice Problems

Bonus Questions

Epilogue

Amdahl's Law

Amdahl’s Law