How to implement a semaphore using mutexes

This blog post shows an educational reference implementation of a semaphore using mutexes in Python.

Please note that the number of mutexes needed in this implementation is 1 + the number of threads waiting in the acquire operation while the value is 0. This is too much, 2 or 3 mutexes altogether would be enough, see the various implementations in Implementation of General Semaphores Using Binary Semaphores.

The implementation is available for download from http://pts-mini-gpl.googlecode.com/svn/trunk/script/semaphore.py.

import thread
from collections import deque


class Semaphore(object):
  def __init__(self, value=1):
    assert value >= 0, 'Semaphore initial value must be >= 0'
    self._lock = thread.allocate_lock()   # Create a mutex.
    self._waiters = deque()
    self._value = value

  def acquire(self, blocking=True):
    """Semaphore P primitive."""
    self._lock.acquire()
    while not self._value:
      if not blocking:
        break
      assert self._lock.locked(), 'wait() of un-acquire()d lock'
      waiter = thread.allocate_lock()
      waiter.acquire()
      self._waiters.append(waiter)
      self._lock.release()
      try:  # Restore state even if e.g. KeyboardInterrupt is raised.
        waiter.acquire()
      finally:
        self._lock.acquire()
    self._value -= 1
    self._lock.release()

  def release(self):
    """Semaphore V primitive."""
    self._lock.acquire()
    self._value += 1
    assert self._lock.locked(), 'notify() of un-acquire()d lock'
    _waiters = self._waiters
    if _waiters:
      _waiters.popleft().release()
    self._lock.release()


if __name__ == '__main__':
  s = Semaphore(3)
  def Reader():
    while True:
      raw_input()
      s.release()
  thread.start_new_thread(Reader, ())
  print 'Press <Enter> twice to continue.'
  for i in xrange(s._value + 2):
    print i
    s.acquire()
  print 'Done.'