Half Baked Python Mutex

If you find yourself in the following situation : you have to use separate processes because Python doesn't really support sending signals with multiple threads but you need some sort of mutual exclusion between these processes. Your additional Iron Python ingredient is that you don't really want to have dependencies on any external modules not shipped with Python that implement SysV IPC or shared objects (though this is probably the most correct solution).

If you're a Python programmer and not a C programmer, you may not realise that mmap can map memory anonymously (see AnonymousMmap). In this case, anonymously means that it is not really backed by a file, but by system memory. This doesn't seem to be documented in the Python documenation, but will work with most any reasonable Unix system.

Here is (the second version) of a Half Baked Mutex based on anonymous shared memory. This version really is half baked, because it uses the "Bakery Algorithm" designed by Lamport (which PeterChubb taught me about in distributed systems). It differs slightly though -- our maximum ticket number must be less than 256 because of interactions between the python mmap, which treats the mmaped area as a string and the ascii character set (via ord and chr). This means heavily contested locks will be a bit "jerky" as the system waits to free up a few slots before continuing. We have a smattering of calls to sleep to attempt to reduce busy waiting. The only other caveat is "hashing" the PID down to a 1024 byte array -- a collision would probably be fatal to the algorithm 1.

   1 import os
   2 import sys
   3 from time import sleep
   4 
   5 class HalfBakedMutex:
   6     def __init__(self):
   7         import mmap
   8         #C is an array of people waiting for a ticket
   9         self.C = mmap.mmap(-1, 1024,
  10                                   mmap.MAP_SHARED|mmap.MAP_ANONYMOUS)
  11         #N is list of tickets people are holding
  12         self.N = mmap.mmap(-1, 1024,
  13                            mmap.MAP_SHARED|mmap.MAP_ANONYMOUS)
  14 
  15     def take_a_number(self):
  16         #pick a number to "see the baker"
  17         i = os.getpid() % 1024 
  18 
  19         #find current maximum number
  20         while True:
  21             #indicate we are currently getting a number
  22             self.C[i] = chr(1)
  23 
  24             max = 0
  25             for j in range(1024):
  26                 if (ord(self.N[j])) > max:
  27                     max = ord(self.N[j])
  28             #we can't have max > 256 as chr(256) will fail
  29             if (max + 1 < 256):
  30                 break
  31             else:
  32                 self.C[i] = chr(0)
  33                 sleep(0.1)
  34 
  35         #take next maximum
  36         self.N[i] = chr(max + 1)
  37         self.C[i] = chr(0)
  38         
  39     def lock(self):
  40 
  41         #first, take a number to see the baker
  42         self.take_a_number()
  43 
  44         i = os.getpid() % 1024
  45 
  46         for j in range(1024):
  47             #make sure the process isn't currently getting a ticket
  48             while ord(self.C[j]) == 1:
  49                 sleep(0.1)
  50                 continue
  51 
  52             # If process j has a ticket, i.e.
  53             #    N[j] > 0
  54             # AND either the process has a lower ticket, or the same
  55             # ticket and a lower PID, i.e.
  56             #   (N[j],j) < (N[i],i)
  57             # wait for it to run
  58             while (ord(self.N[j]) > 0) and (ord(self.N[j]),j) < (ord(self.N[i]),i) :
  59                 sleep(0.1)
  60                 continue
  61 
  62         #if we made it here, it is our turn to run!
  63         return
  64     
  65     def unlock(self):
  66         i = os.getpid() % 1024
  67         self.N[i] = chr(0)
  68         
  69 
  70 mut = HalfBakedMutex()
  71 
  72 os.fork()
  73 os.fork() # 4 processes
  74 os.fork() # 8 processes
  75 os.fork() # 16 processes
  76 os.fork() # 32 processes
  77 os.fork() # 64 processes
  78 
  79 while True:
  80     mut.lock()
  81     print(" ------ " + `os.getpid()` + " ------ ")
  82     mut.unlock()

If you're otherwise stuck, this might fit the bill. Any feedback to ianw

  1. I can't think of a good way around this, but chances of a collision if you're using < 1024 processes are minimal (1)

IA64wiki: HalfBakedPythonMutex (last edited 2009-12-10 03:13:41 by localhost)

Gelato@UNSW is sponsored by
the University of New South Wales National ICT Australia The Gelato Federation Hewlett-Packard Company Australian Research Council
Please contact us with any questions or comments.