diff --git a/asio/include/asio/detail/impl/strand_service.hpp b/asio/include/asio/detail/impl/strand_service.hpp
index a626682..ec7008a 100644
--- a/asio/include/asio/detail/impl/strand_service.hpp
+++ b/asio/include/asio/detail/impl/strand_service.hpp
@@ -28,7 +28,7 @@
 
 inline strand_service::strand_impl::strand_impl()
   : operation(&strand_service::do_complete),
-    count_(0)
+    locked_(false)
 {
 }
 
@@ -40,7 +40,8 @@
   ~on_dispatch_exit()
   {
     impl_->mutex_.lock();
-    bool more_handlers = (--impl_->count_ > 0);
+    impl_->ready_queue_.push(impl_->waiting_queue_);
+    bool more_handlers = impl_->locked_ = !impl_->ready_queue_.empty();
     impl_->mutex_.unlock();
 
     if (more_handlers)
diff --git a/asio/include/asio/detail/impl/strand_service.ipp b/asio/include/asio/detail/impl/strand_service.ipp
index 4d05ad5..d89554d 100644
--- a/asio/include/asio/detail/impl/strand_service.ipp
+++ b/asio/include/asio/detail/impl/strand_service.ipp
@@ -32,7 +32,8 @@
   ~on_do_complete_exit()
   {
     impl_->mutex_.lock();
-    bool more_handlers = (--impl_->count_ > 0);
+    impl_->ready_queue_.push(impl_->waiting_queue_);
+    bool more_handlers = impl_->locked_ = !impl_->ready_queue_.empty();
     impl_->mutex_.unlock();
 
     if (more_handlers)
@@ -55,8 +56,13 @@
   asio::detail::mutex::scoped_lock lock(mutex_);
 
   for (std::size_t i = 0; i < num_implementations; ++i)
+  {
     if (strand_impl* impl = implementations_[i].get())
-      ops.push(impl->queue_);
+    {
+      ops.push(impl->waiting_queue_);
+      ops.push(impl->ready_queue_);
+    }
+  }
 }
 
 void strand_service::construct(strand_service::implementation_type& impl)
@@ -80,41 +86,55 @@
 
 bool strand_service::do_dispatch(implementation_type& impl, operation* op)
 {
-  // If we are running inside the io_service, and no other handler is queued
-  // or running, then the handler can run immediately.
+  // If we are running inside the io_service, and no other handler already
+  // holds the strand lock, then the handler can run immediately.
   bool can_dispatch = io_service_.can_dispatch();
   impl->mutex_.lock();
-  bool first = (++impl->count_ == 1);
-  if (can_dispatch && first)
+  if (can_dispatch && !impl->locked_)
   {
     // Immediate invocation is allowed.
+    impl->locked_ = true;
     impl->mutex_.unlock();
     return true;
   }
 
-  // Immediate invocation is not allowed, so enqueue for later.
-  impl->queue_.push(op);
-  impl->mutex_.unlock();
-
-  // The first handler to be enqueued is responsible for scheduling the
-  // strand.
-  if (first)
+  if (impl->locked_)
+  {
+    // Some other handler already holds the strand lock. Enqueue for later.
+    impl->waiting_queue_.push(op);
+    impl->mutex_.unlock();
+  }
+  else
+  {
+    // The handler is acquiring the strand lock and so is responsible for
+    // scheduling the strand.
+    impl->locked_ = true;
+    impl->mutex_.unlock();
+    impl->ready_queue_.push(op);
     io_service_.post_immediate_completion(impl);
+  }
 
   return false;
 }
 
 void strand_service::do_post(implementation_type& impl, operation* op)
 {
-  // Add the handler to the queue.
   impl->mutex_.lock();
-  bool first = (++impl->count_ == 1);
-  impl->queue_.push(op);
-  impl->mutex_.unlock();
-
-  // The first handler to be enqueue is responsible for scheduling the strand.
-  if (first)
+  if (impl->locked_)
+  {
+    // Some other handler already holds the strand lock. Enqueue for later.
+    impl->waiting_queue_.push(op);
+    impl->mutex_.unlock();
+  }
+  else
+  {
+    // The handler is acquiring the strand lock and so is responsible for
+    // scheduling the strand.
+    impl->locked_ = true;
+    impl->mutex_.unlock();
+    impl->ready_queue_.push(op);
     io_service_.post_immediate_completion(impl);
+  }
 }
 
 void strand_service::do_complete(io_service_impl* owner, operation* base,
@@ -124,12 +144,6 @@
   {
     strand_impl* impl = static_cast<strand_impl*>(base);
 
-    // Get the next handler to be executed.
-    impl->mutex_.lock();
-    operation* o = impl->queue_.front();
-    impl->queue_.pop();
-    impl->mutex_.unlock();
-
     // Indicate that this strand is executing on the current thread.
     call_stack<strand_impl>::context ctx(impl);
 
@@ -137,7 +151,13 @@
     on_do_complete_exit on_exit = { owner, impl };
     (void)on_exit;
 
-    o->complete(*owner, ec, 0);
+    // Run all ready handlers. No lock is required since the ready queue is
+    // accessed only within the strand.
+    while (operation* o = impl->ready_queue_.front())
+    {
+      impl->ready_queue_.pop();
+      o->complete(*owner, ec, 0);
+    }
   }
 }
 
diff --git a/asio/include/asio/detail/strand_service.hpp b/asio/include/asio/detail/strand_service.hpp
index 6cb97d5..82aab3f 100644
--- a/asio/include/asio/detail/strand_service.hpp
+++ b/asio/include/asio/detail/strand_service.hpp
@@ -56,11 +56,20 @@
     // Mutex to protect access to internal data.
     asio::detail::mutex mutex_;
 
-    // The count of handlers in the strand, including the upcall (if any).
-    std::size_t count_;
+    // Indicates whether the strand is currently "locked" by a handler. This
+    // means that there is a handler upcall in progress, or that the strand
+    // itself has been scheduled in order to invoke some pending handlers.
+    bool locked_;
 
-    // The handlers waiting on the strand.
-    op_queue<operation> queue_;
+    // The handlers that are waiting on the strand but should not be run until
+    // after the next time the strand is scheduled. This queue must only be
+    // modified while the mutex is locked.
+    op_queue<operation> waiting_queue_;
+
+    // The handlers that are ready to be run. Logically speaking, these are the
+    // handlers that hold the strand's lock. The ready queue is only modified
+    // from within the strand and so may be accessed without locking the mutex.
+    op_queue<operation> ready_queue_;
   };
 
   typedef strand_impl* implementation_type;