Learn Concurrency by Making a Countdown Latch in Ruby
A Countdown Latch is a concurrency abstraction that allows one or more threads to wait until all other threads are done with what they are doing. Therefore, a countdown latch is often referred to as a thread synchronization primitive.
How are Countdown Latches Useful?
Let say you have a bunch of threads that are fetching, say, Chuck Norris jokes. You create ten threads and you want to ensure that they all complete before you proceed on with the next step.
In this instance, you can create a countdown latch with a counter of ten. Then, right before your next step in the code, you can wait for your threads to complete. Until then, your code cannot proceed until all the threads are done.
When each thread fetches a joke, it will decrement the counter. Eventually as all ten threads are done fetching jokes, the counter in the countdown latch will eventually hit zero. That’s when the code is allowed to proceed.
Implementing Your Own Countdown Latch: Test First!
In a previous article, we went though how to implement Futures in Ruby. In this article, we are going test-drive an implementation of a Countdown Latch. Let’s get started!
Setting Up
Let’s bootstrap a new Ruby project. My favorite way is to create a Ruby gem:
% bundle gem countdown_latch -t
Creating gem 'countdown_latch'...
MIT License enabled in config
create countdown_latch/Gemfile
create countdown_latch/.gitignore
create countdown_latch/lib/countdown_latch.rb
create countdown_latch/lib/countdown_latch/version.rb
create countdown_latch/countdown_latch.gemspec
create countdown_latch/Rakefile
create countdown_latch/README.md
create countdown_latch/bin/console
create countdown_latch/bin/setup
create countdown_latch/LICENSE.txt
create countdown_latch/.travis.yml
create countdown_latch/.rspec
create countdown_latch/spec/spec_helper.rb
create countdown_latch/spec/countdown_latch_spec.rb
Initializing git repo in /Users/benjamintan/workspace/countdown_latch
Did you notice the
-tflat appended? This flag adds RSpec as a development dependency.
Next, go into the project directory:
% cd countdown_latch
Run bin/setup to install the dependencies:
% bin/setup
Resolving dependencies...
Using rake 10.4.2
Using bundler 1.10.6
Using countdown_latch 0.1.0 from source at .
Using diff-lcs 1.2.5
Using rspec-support 3.3.0
Using rspec-core 3.3.2
Using rspec-expectations 3.3.1
Using rspec-mocks 3.3.2
Using rspec 3.3.0
Bundle complete! 4 Gemfile dependencies, 9 gems now installed.
Use `bundle show [gemname]` to see where a bundled gem is installed.
Creating the Countdown Latch
Now, on to the fun stuff! Since we are doing this test-first. The tests will help us drive towards the implementation that we will flesh out in order to get the tests to pass.
As a sanity check, we can quickly make sure everything is hooked up as expected:
% rspec
CountdownLatch
has a version number
does something useful (FAILED - 1)
Failures:
1) CountdownLatch does something useful
Failure/Error: expect(false).to eq(true)
expected: true
got: false
(compared using ==)
# ./spec/countdown_latch_spec.rb:9:in `block (2 levels) in <top (required)>'
Finished in 0.01957 seconds (files took 0.07757 seconds to load)
2 examples, 1 failure
Failed examples:
rspec ./spec/countdown_latch_spec.rb:8 # CountdownLatch does something useful
Excellent! RSpec is working fine! Now, open up the test file located at spec/countdownlatchspec.rb. We are going to write the first test.
A Countdown Latch Requires a Non-negative Integer as an Argument
You should delete everything in spec/countdownlatchspec.rb and replace it with this skeleton:
module CountdownLatch
describe CountdownLatch do
end
end
The first test is to make sure that the argument passed into the constructor of the countdown latch is a non-negative integer:
module CountdownLatch
describe CountdownLatch do
it "requires a non-negative integer as an argument" do
latch = CountdownLatch.new(3)
expect(latch.count).to eq(3)
end
end
end
In order to get this to pass, we need a constructor that accepts a non-negative integer as an argument. Getting this test to pass is simple:
module CountdownLatch
class CountdownLatch
def initialize(count)
if count.is_a?(Fixnum) && count > 0
@count = count
end
end
end
end
At this point, the test will pass. Let’s also make sure that 0 is accepted:
module CountdownLatch
describe CountdownLatch do
it "zero is a valid argument" do
latch = CountdownLatch.new(0)
expect(latch.count).to eq(0)
end
end
end
Whoops! Our test caught something:
Failures:
1) CountdownLatch::CountdownLatch zero is a valid argument
Failure/Error: expect(latch.count).to eq(0)
expected: 0
got: nil
(compared using ==)
Turns out, we have an off by one error when comparing count and zero:
module CountdownLatch
class CountdownLatch
def initialize(count)
if count.is_a?(Fixnum) && count >= 0
@count = count
end
end
end
end
The countdown latch cannot be initialized with a negative number, or a Float, for example, since those two cases do not make sense. Let’s add the tests:
module CountdownLatch
describe CountdownLatch do
it "throws ArgumentError for negative numbers" do
expect { CountdownLatch.new(-1) }.to raise_error(ArgumentError)
end
it "throws ArgumentError for non-integers" do
expect { CountdownLatch.new(1.0) }.to raise_error(ArgumentError)
end
end
end
Now the tests will fail:
Failures:
1) CountdownLatch::CountdownLatch throws ArgumentError for negative numbers
Failure/Error: expect { CountdownLatch.new(-1) }.to raise_error(ArgumentError)
expected ArgumentError but nothing was raised
# ./spec/countdown_latch_spec.rb:17:in `block (2 levels) in <module:CountdownLatch>'
2) CountdownLatch::CountdownLatch throws ArgumentError for non-integers
Failure/Error: expect { CountdownLatch.new(1.0) }.to raise_error(ArgumentError)
expected ArgumentError but nothing was raised
# ./spec/countdown_latch_spec.rb:21:in `block (2 levels) in <module:CountdownLatch>'
Thankfully, this too is an easy fix. We just have to get the initializer to raise an ArgumentError for well, errors in the argument. In lib/countdownlatch/countdownlatch.rb:
module CountdownLatch
class CountdownLatch
def initialize(count)
if count.is_a?(Fixnum) && count >= 0
@count = count
@mutex = Mutex.new
@condition = ConditionVariable.new
else
raise ArgumentError
end
end
end
end
Now the tests should all pass.
Counting Down
A countdown latch has to know how to count down its own internal counter.
module CountdownLatch
describe CountdownLatch do
it "#count decreases when #count_down is called" do
latch = CountdownLatch.new(3)
latch.count_down
expect(latch.count).to eq(2)
end
end
end
Now we need have access to the @count field. That is easy enough:
module CountdownLatch
class CountdownLatch
def initialize(count)
# ...
end
def count
@count
end
end
end
The count_down method looks almost simplistic:
module CountdownLatch
class CountdownLatch
def count_down
@count -= 1
end
end
end
Resist the temptation to add more behavior and “smarter” logic until the tests are forcing you to do something about it. In this case, the tests should be all green now.
However, our tests are not complete. The countdown latch should only count down to zero and nothing less. Let’s add a test for that:
module CountdownLatch
describe CountdownLatch do
it "#count never reaches below zero" do
latch = CountdownLatch.new(0)
latch.count_down
expect(latch.count).to eq(0)
end
end
end
The above test fails:
1) CountdownLatch::CountdownLatch #count never reaches below zero
Failure/Error: expect(latch.count).to eq(0)
expected: 0
got: -1
(compared using ==)
We just need to check if @count is zero:
module CountdownLatch
class CountdownLatch
def count_down
unless @count.zero?
@count -= 1
end
end
end
end
Everything should be green!
Awaiting for Threads
Till now, we simply have a glorified countdown object. It is not even thread-safe! This is because count_down can be called by multiple threads and since @count is not synchronized in anyway, race conditions can occur.
This is the first test that will drive us to implement the concurrency features in our countdown latch:
module CountdownLatch
describe CountdownLatch do
it "#await will wait for a thread to finish its work" do
latch = CountdownLatch.new(1)
Thread.new do
latch.count_down
end
latch.await
expect(latch.count).to eq(0)
end
end
end
The test creates a countdown latch initialized to 1. We then create a thread that decrements the latch. Outside of the thread, we call latch.await.
This is basically saying that the program will wait for the thread to finish its work. Again, once the thread is done with its work, it will call latch.count_down. Therefore, we expect that the count of the latch to be zero.
In order to see the test fail correctly, we need an empty implementation of await:
module CountdownLatch
class CountdownLatch
def await
end
end
end
When you run the tests, the following will fail:
Failures:
1) CountdownLatch::CountdownLatch #await will wait for a thread to finish its work
Failure/Error: expect(latch.count).to eq(0)
expected: 0
got: 1
(compared using ==)
Since await does nothing, the program doesn’t wait for the thread to tell the countdown latch that it’s OK to proceed. Instead, the program simply runs straight through. In order to get this test to pass, you need to know about condition variables.
Condition Variables
A condition variable is essentially a synchronization primitive (recall that a countdown latch is also a synchronization primitive) that allows threads to wait until some condition occurs. In the case of a countdown latch, that condition is when @count hits zero.
When that happens, the broadcast method has to be called on the condition variable to tell all the waiting threads that they can stop waiting and proceed.
First, we’ll add the condition variable to the implementation and tell it to broadcast to all waiting threads when the condition has been met. Do not forget to include require "thread" too:
require "thread" # <----
module CountdownLatch
class CountdownLatch
def initialize(count)
if count.is_a?(Fixnum) && count >= 0
@count = count
@condition = ConditionVariable.new # <----
else
raise ArgumentError
end
end
def count_down
unless @count.zero?
@count -= 1
else
@condition.broadcast # <----
end
end
end
end
Now, to deal with the other side of the equation: Making threads suspend execution and wait till the condition is met. Here’s the first attempt. ConditionVariable has a method called wait:
module CountdownLatch
class CountdownLatch
def await
@condition.wait
end
end
end
However, this doesn’t work because ConditionVariable#wait requires an argument that takes in a Mutex object. A mutex is essentially a lock that protects a section of code from being entered by more than one thread. Recall that I mentioned @count is , until now, not thread-safe. We are going to fix this.
In this case, we need to supply a mutex to the condition variable, so that only one thread can read/write to the condition variable at any one time.
First, we will create a mutex for the countdown latch:
module CountdownLatch
class CountdownLatch
def initialize(count)
if count.is_a?(Fixnum) && count >= 0
@count = count
@condition = ConditionVariable.new
@mutex = Mutex.new <----
else
raise ArgumentError
end
end
end
end
Next, we will use @mutex.synchronize to demarcate a critical section. A critical section is an area of code where only one thread can enter. First, let’s handle the count_down method:
module CountdownLatch
class CountdownLatch
def count_down
@mutex.synchronize {
unless @count.zero?
@count -= 1
else
@condition.broadcast
end
}
end
end
end
We finally have a mutex to pass into @condition.wait :
module CountdownLatch
class CountdownLatch
def await
@condition.wait(@mutex)
end
end
end
However, just like the count_down method, you need a critical section. Here it is:
module CountdownLatch
class CountdownLatch
def await
@mutex.synchronize {
@condition.wait(@mutex)
}
end
end
end
While we are add it, let’s wrap the @count in the count method with a mutex too:
module CountdownLatch
class CountdownLatch
def count
@mutex.synchronize {
@count
}
end
end
end
Run the test again and we should be green! Woot!
A Sample Run
Create a folder under lib called sample. In that folder, I create a file called chucky.rb with the following contents:
require 'open-uri'
require 'json'
module CountdownLatch
class Chucky
URL = 'http://api.icndb.com/jokes/random'
def get_fact
open(URL) do |f|
f.each_line { |line| puts JSON.parse(line)['value']['joke'] }
end
end
def get_facts(num)
latch = CountdownLatch.new(num) # <---- Latch
facts = []
(1..num).each do |x|
Thread.new do
facts << get_fact
latch.count_down
end
end
latch.await
facts
end
end
end
This class fetches jokes from a third-party API, parses the JSON response and returns the joke as a String. We can use a test to drive Chucky and get us some facts:
require 'spec_helper'
require 'sample/chucky' # <---- Remember to add this!
module CountdownLatch
describe CountdownLatch do
it "sample run", :speed => 'slow' do
chucky = Chucky.new
facts = chucky.get_facts(5)
expect(facts.size).to eq(5)
end
end
end
As expected, the tests will pass. Try removing the latch and see what happens.
Limitations, Acknowledgments, and Where to Learn More
This implementation doesn’t handle spurious wakeups, an interesting phenomenon where threads can wake up even though the condition variable hasn’t signaled/broadcasted yet.
If you want a more solid and refined implementation of a countdown latch, take a look at the fantastic Ruby Concurrency GitHub repository.
Thanks for Reading!
I hope you have learned something new about condition variables, mutexes, and, of course, creating your own countdown latch! More importantly, I hope you had lots of fun following along. You can grab the full source here. Thanks for reading!
