神刀安全网

Learn Concurrency by Making a Countdown Latch in Ruby

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 -t flat 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/countdown latch spec.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/countdown latch spec.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/countdown latch/countdown latch.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!

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Learn Concurrency by Making a Countdown Latch in Ruby

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址