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.'
2 comments:
If value == 1, then I think 1 mutex is enough, because then a semaphore is actually a mutex. For value > 1 my guess is that two mutexes should be enough. What do you think?
Yes, 2 or 3 mutexes altogether are enough, see http://webhome.csc.uvic.ca/~mcheng/460/notes/gensem.pdf
Post a Comment