home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / os / research / 873 < prev    next >
Encoding:
Internet Message Format  |  1992-08-29  |  1.7 KB
  1. Path: sparky!uunet!sun-barr!olivea!hal.com!darkstar.UCSC.EDU!osr
  2. From: Guido.van.Rossum@cwi.nl (Guido van Rossum)
  3. Newsgroups: comp.os.research
  4. Subject: implementing counting semaphores w. binary mutexes
  5. Message-ID: <17n07jINN794@darkstar.UCSC.EDU>
  6. Date: 29 Aug 92 04:59:31 GMT
  7. Organization: University of California, Santa Cruz
  8. Lines: 48
  9. Approved: comp-os-research@ftp.cse.ucsc.edu
  10. NNTP-Posting-Host: ftp.cse.ucsc.edu
  11. Originator: osr@ftp
  12.  
  13.  
  14. (Excuse me if this is a bozo question -- I'm somewhat out of touch
  15. with this field.)
  16.  
  17. I have a threads package that efficiently implements mutexes (binary
  18. semaphores) with the usual lock and unlock operations.  Now I have the
  19. need for a counting semaphore with down and up operations.  My
  20. proposal to implement this is the following:
  21.  
  22. - a semaphore is a structure containing an integer "level" and two
  23. mutexes, "mutex" (used to protect the data structure) and "block"
  24. (used to block when a down operation finds the level at zero).
  25.  
  26. - to initialize a semaphore s:
  27.  
  28.     s.level = 0
  29.     s.block = new_mutex()
  30.     s.mutex = new_mutex()
  31.     lock(s.block)
  32.  
  33. - to implement down(s):
  34.  
  35.     lock(s.block)
  36.     lock(s.mutex)
  37.     s.level = s.level - 1
  38.     if s.level > 0: unlock(s.block)
  39.     unlock(s.mutex)
  40.  
  41. - to implement up(s):
  42.  
  43.     lock(s.mutex)
  44.     s.level = s.level + 1
  45.     if s.level == 1: unlock(s.block)
  46.     unlock(s.mutex)
  47.  
  48. I have two questions about this:
  49.  
  50. (a) has this implementation been described in the literature, and if
  51. so, where?
  52.  
  53. (b) is it better or worse than other implementations, and why? (under
  54. the assumptions that only binary mutexes are available)
  55.  
  56. (Note: I put this code in the Amoeba 4.0 library so some readers may
  57. be familiar with it -- I'm asking for descriptions elsewhere...)
  58.  
  59. --Guido van Rossum, CWI, Amsterdam <guido@cwi.nl>
  60. "Well I'm a plumber.  I can't act"
  61.