2010-05-29

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

2010-05-18

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:

ConcurrenceEventletTornadoTwistedasyncoregeventcircuitsSyncless
pure Python: can work without compiling C codenoyesyesyesyesnoyesno
pure Python: runs at full speed without compiling C codenoyesyesyesyesnoyesno
standard module in Python 2.6nonononoyesnonono
has asynchronous DNS resolvernoyes, 1)noyes, 2)noyes, 3)noyes, 4)
supports running other tasklets while DNS resolving is in progressnoyesnoyesnoyesnoyes
has fully asynchronous and scalable DNS resolvernoyes, 5)noyesnoyesnoyes
supports timeouts on individual socket send() and recv() operationsyesyesnoyesnoyesnoyes
has WSGI serveryesyesyesyesnoyesyes--, 6)yes
can work with CherryPy's WSGI servernoyes--, 7)nononoyes--, 7)noyes
contains a custom, non-WSGI web frameworkyesnoyesyesnono++, 8)yesno
can run external web frameworks using non-WSGI connectorsnoyes, 9)nononononoyes++, 10)
runs with Stackless Pythonyesyes--, 11)yes, 12)yes, 12)yes, 12)noyes, 12)yes
runs with greenletyes--, 13)yesyes, 12)yes, 12)yes, 12)yesyes, 12)yes
has fast non-blocking socket class implemented in C or Pyrexnononononononoyes
has fast read and write buffer code implemented in C or Pyrexyesnonononoyes, 14)noyes
uses fast (C or Pyrex) buffer code for its socket.socket.makefile()yesnonononononoyes
uses fast (C or Pyrex) buffer code for its ssl.SSLSocket.makefile()no, 15)nonononononoyes
has SSL supportnoyes, 16)noyes, 16)noyes, 16)yes, 16)yes, 16)
has monkey-patchig for socket.socket and other blocking I/O operationsnoyesno, 12)no, 12)no, 12)yesno, 12)yes
prints and recovers from an uncaught exceptionyes, 17)yesyesyesyesyesno, 18)no, 19)
can use libeventyesyesnoyesnoyesnoyes
can use the libevent emulation of libevyesyesnoyesnono, 20)noyes
works without libevent or an emulation installednoyesyesyesyesnoyesyes
avoids C stack copying (which is slower than soft switching)nono, 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)yesyesyesno, 24)yes, 23)yesyes, 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?yesyesyesyes++, 30)noyesyesyes--, 31)
nichol.as: Does the documentation contain examples?yesyesyesyesnoyesyesyes
nichol.as: Is it used in production somewhere?yes, 32)yes, 33)yes, 34)yesyes, 35)yes, 36)yes, 37)no
nichol.as: Does it have some sort of community (mailinglist, irc, etc..)?yesyesyes++, 38)yesnoyesyesno
nichol.as: Is there any recent activity?no, 39)yesyesyesnoyesyesyes
nichol.as: Does it have a blog (from the owner)?yesyesyes, 40)yes++, 41)noyesyesyes--, 42)
nichol.as: Does it have a Twitter account?yesyesyesyesnoyesyesyes--, 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?noyesnoyesnonoyesyes--, 49)
nichol.as: Does it provide a HTTP server for WSGI applications?yesyesyes--, 50)yesnoyesyes--, 6)yes
nichol.as: Does it provide access to a TCP Socket?yesyesyesyesyesyesyesyes
nichol.as: Does it have any Comet features?nononononononono
nichol.as: Is it using epoll, if available?yes, 23)yesyesyesno, 24)yes, 23)no++, 51)yes, 25)
nichol.as: Does it have unit tests?yesyesnoyes++, 52)yesyesyesyes, 53)
provides generic timeout for any block of codeyesyesyesnonoyesnoyes
provides synchronization primitives (e.g. semaphore, codition variable)yes--, 54)yesnoyesnoyesnono
lets the programmer control event delivery order (e.g. with priorities)nononononononono
provides callbacks (links) when some work is finishednoyesyes, 12)yes, 12)yes, 12)yesyes, 12)no
has a high-level, comprehensive, consistent network programming frameworknoyesyes--, 55)yesno, 56)yes--, 55)yesno
has non-blocking select.select() implementationnoyesno, 12)no, 12)no, 12)yesno, 12)yes
implements some application-level protocols beyond HTTP, WSGI and DNSyes, 57)no++, 58)yes, 59)yes++, 60)nono++, 58)yes, 61)no++, 62)
compatible with other non-blocking systems in the same processno, 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