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.'

Feature comparison of Python non-blocking I/O libraries

This blog post is a tabular feature comparison of Syncless and the 6 most popular event-driven and coroutine-based non-blocking (asynchronous) networking I/O libraries for Python. It was inspired by http://nichol.as/asynchronous-servers-in-python (published on 2009-11-22), which compares the features and the performance of 14 Python non-blocking networking I/O libraries. We're not comparing generator-based (yield) solutions here. We haven't made performance measurements, so speed-related claims in this comparison are beliefs and opinions rather than well-founded facts. Here are the results:

	Concurrence	Eventlet	Tornado	Twisted	asyncore	gevent	circuits	Syncless
pure Python: can work without compiling C code	no	yes	yes	yes	yes	no	yes	no
pure Python: runs at full speed without compiling C code	no	yes	yes	yes	yes	no	yes	no
standard module in Python 2.6	no	no	no	no	yes	no	no	no
has asynchronous DNS resolver	no	yes, 1)	no	yes, 2)	no	yes, 3)	no	yes, 4)
supports running other tasklets while DNS resolving is in progress	no	yes	no	yes	no	yes	no	yes
has fully asynchronous and scalable DNS resolver	no	yes, 5)	no	yes	no	yes	no	yes
supports timeouts on individual socket send() and recv() operations	yes	yes	no	yes	no	yes	no	yes
has WSGI server	yes	yes	yes	yes	no	yes	yes--, 6)	yes
can work with CherryPy's WSGI server	no	yes--, 7)	no	no	no	yes--, 7)	no	yes
contains a custom, non-WSGI web framework	yes	no	yes	yes	no	no++, 8)	yes	no
can run external web frameworks using non-WSGI connectors	no	yes, 9)	no	no	no	no	no	yes++, 10)
runs with Stackless Python	yes	yes--, 11)	yes, 12)	yes, 12)	yes, 12)	no	yes, 12)	yes
runs with greenlet	yes--, 13)	yes	yes, 12)	yes, 12)	yes, 12)	yes	yes, 12)	yes
has fast non-blocking socket class implemented in C or Pyrex	no	no	no	no	no	no	no	yes
has fast read and write buffer code implemented in C or Pyrex	yes	no	no	no	no	yes, 14)	no	yes
uses fast (C or Pyrex) buffer code for its socket.socket.makefile()	yes	no	no	no	no	no	no	yes
uses fast (C or Pyrex) buffer code for its ssl.SSLSocket.makefile()	no, 15)	no	no	no	no	no	no	yes
has SSL support	no	yes, 16)	no	yes, 16)	no	yes, 16)	yes, 16)	yes, 16)
has monkey-patchig for socket.socket and other blocking I/O operations	no	yes	no, 12)	no, 12)	no, 12)	yes	no, 12)	yes
prints and recovers from an uncaught exception	yes, 17)	yes	yes	yes	yes	yes	no, 18)	no, 19)
can use libevent	yes	yes	no	yes	no	yes	no	yes
can use the libevent emulation of libev	yes	yes	no	yes	no	no, 20)	no	yes
works without libevent or an emulation installed	no	yes	yes	yes	yes	no	yes	yes
avoids C stack copying (which is slower than soft switching)	no	no, 21)	yes, 12)	yes, 12)	yes, 12)	no, 21)	yes, 12)	no, 22)
can use a high performance event notification primitive (e.g. epoll on Linux)	yes, 23)	yes	yes	yes	no, 24)	yes, 23)	yes	yes, 25)
nichol.as: What license does the framework have?	yes, 26)	yes, 26)	yes, 27)	yes, 26)	yes, 26)	yes, 26)	yes, 28)	yes, 29)
nichol.as: Does it provide documentation?	yes	yes	yes	yes++, 30)	no	yes	yes	yes--, 31)
nichol.as: Does the documentation contain examples?	yes	yes	yes	yes	no	yes	yes	yes
nichol.as: Is it used in production somewhere?	yes, 32)	yes, 33)	yes, 34)	yes	yes, 35)	yes, 36)	yes, 37)	no
nichol.as: Does it have some sort of community (mailinglist, irc, etc..)?	yes	yes	yes++, 38)	yes	no	yes	yes	no
nichol.as: Is there any recent activity?	no, 39)	yes	yes	yes	no	yes	yes	yes
nichol.as: Does it have a blog (from the owner)?	yes	yes	yes, 40)	yes++, 41)	no	yes	yes	yes--, 42)
nichol.as: Does it have a Twitter account?	yes	yes	yes	yes	no	yes	yes	yes--, 42)
nichol.as: Where can I find the repository? (without links)	yes, 43)	yes, 44)	yes, 43)	yes, 45)	yes, 46)	yes, 47)	yes, 44)	yes, 48)
nichol.as: Does it have a thread pool?	no	yes	no	yes	no	no	yes	yes--, 49)
nichol.as: Does it provide a HTTP server for WSGI applications?	yes	yes	yes--, 50)	yes	no	yes	yes--, 6)	yes
nichol.as: Does it provide access to a TCP Socket?	yes	yes	yes	yes	yes	yes	yes	yes
nichol.as: Does it have any Comet features?	no	no	no	no	no	no	no	no
nichol.as: Is it using epoll, if available?	yes, 23)	yes	yes	yes	no, 24)	yes, 23)	no++, 51)	yes, 25)
nichol.as: Does it have unit tests?	yes	yes	no	yes++, 52)	yes	yes	yes	yes, 53)
provides generic timeout for any block of code	yes	yes	yes	no	no	yes	no	yes
provides synchronization primitives (e.g. semaphore, codition variable)	yes--, 54)	yes	no	yes	no	yes	no	no
lets the programmer control event delivery order (e.g. with priorities)	no	no	no	no	no	no	no	no
provides callbacks (links) when some work is finished	no	yes	yes, 12)	yes, 12)	yes, 12)	yes	yes, 12)	no
has a high-level, comprehensive, consistent network programming framework	no	yes	yes--, 55)	yes	no, 56)	yes--, 55)	yes	no
has non-blocking select.select() implementation	no	yes	no, 12)	no, 12)	no, 12)	yes	no, 12)	yes
implements some application-level protocols beyond HTTP, WSGI and DNS	yes, 57)	no++, 58)	yes, 59)	yes++, 60)	no	no++, 58)	yes, 61)	no++, 62)
compatible with other non-blocking systems in the same process	no, 63)	yes, 64)	no, 63)	yes++, 65)	no, 63)	no++, 66)	yes, 67)	yes++, 68)

Comments:
1) thread pool or Twisted
2) built-in
3) evdns
4) evdns or its equivalents: minihdns or evhdns
5) if Twisted is available
6) does not implement the WSGI spec properly (no write or close)
7) by manually monkey-patching socket and thread
8) has its own simple HTTPServer class
9) BaseHTTPServer
10) BaseHTTPServer, CherryPy, web.py, Google webapp
11) has partial, incomplete and incomatible greenlet emulation
12) event-driven
13) has partial and incompatible Stackless Python emulation
14) evbuffer
15) no SSL support
16) client and server
17) in the Tasklet class
18) sliently ignores exceptions and keeps the connection hanging
19) the process exits
20) needs evdns
21) uses greenlet
22) calls stackless.schedule() from C code
23) uses libevent
24) but uses poll and epoll could be added asily
25) can use libev or libevent
26) MIT
27) Apache
28) GNU GPL v2 or later
29) Apache License, Version 2.0
30) exensive
31) README and docstrings
32) Hyves.nl (a Dutch social networking site)
33) Second Life (a virtual reality game)
34) FriendFeed (a social networking site)
35) pyftpdlib, supervisor [link] (via medusa)
36) many, [link] and [link]
37) Naali, TAMS, website-profiler, kdb IRC bot, python-brisa uPnP
38) huge
39) not since 2009-11-19
40) at facebook
41) lots
42) the author writes Syncless-related stuff to his blog
43) GIT on github
44) Mercurial on bitbucket
45) in its own Subversion + Trac repository
46) in Python's Subversion
47) Mercurial on bitbuckig
48) Subversion on Google Code
49) not tested in production for robustness and speed
50) limited
51) it can be enabled manually
52) extensive
53) unit tests cover only parts of the functionality
54) provides queues
55) not comprehensive
56) low-level
57) MySQL client
58) Python console backdoor, can monkey-patch external modules
59) storage server compatible with Amazon S3; OpenID
60) tons of protocols
61) pygame, GTK+, inotify and pygame
62) can monkey-patch external modules
63) not by default
64) has Twisted reactor
65) many including GTK+ and Qt
66) not by default, but there is the project gTornado
67) pygame and GTK
68) has monkey-patching for Concurrence, Eventlet, Tornado, Twisted, gevent, circuits and asyncore