home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / parallel / 2742 < prev    next >
Encoding:
Text File  |  1992-12-15  |  2.0 KB  |  54 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!gatech!hubcap!fpst
  3. From: gottlieb@allan.ultra.nyu.edu (Allan Gottlieb)
  4. Subject: Re: Wanted: efficient software lock
  5. In-Reply-To: engler@cs.arizona.edu's message of 14 Dec 92 07:07:45 GMT
  6. Message-ID: <1992Dec15.134502.7384@hubcap.clemson.edu>
  7. Sender: fpst@hubcap.clemson.edu (Steve Stevenson)
  8. Nntp-Posting-Host: allan.ultra.nyu.edu
  9. Organization: New York University, Ultracomputer project
  10. References: <1992Dec14.133731.18997@hubcap.clemson.edu>
  11. Date: 14 Dec 92 11:59:26
  12. Approved: parallel@hubcap.clemson.edu
  13. Lines: 39
  14.  
  15. In article <1992Dec14.133731.18997@hubcap.clemson.edu> engler@cs.arizona.edu (Dawson R. Engler) writes:
  16.  
  17.    I need the algorithm for an efficient software lock that does not use
  18.    atomic instructions (except perhaps assignment).  Fairness is unnecessary:
  19.    in the situation I need this for, ~90% of the accesses are by the same
  20.    process, and if the accesses are by someone else, they are allowed to
  21.    have extra overhead.
  22.  
  23.    If anyone can suggest such an algorithm that has worked well for them
  24.    in practice, I would be grateful.
  25.  
  26.    Regards,
  27.        Dawson
  28.        engler@cs.arizona.edu
  29.  
  30.    P.S. An alternative solution would be a lock that is very effective in
  31.     the case of two processes.  Since each lock will belong to a
  32.     specific process, there is a natural dichotomy between the owner and
  33.     "everyone else".  From this distiction, two logical processes can
  34.     be created ("me" and "them").
  35.  
  36. I would suggest peterson's algorithm.  For two processes it is simply
  37. Code for process 1          Code for process 2
  38. ------------------          ------------------
  39. P1Wants <- TRUE                   P2Wants <- TRUE
  40. Turn <- P2                        Turn <- P1
  41. while P2Wants and Turn=P2      while P1Wants and Turn=P1
  42.  
  43. critical section                  critical section
  44.  
  45. P1Wants <- FALSE                  P2Wants <- FALSE
  46.  
  47. (the while loops have empty bodies)
  48.  
  49. For N processes (plus a proof and references) see Hofri's article in
  50. Operating Systems Review January 90.
  51.  
  52. Allan Gottlieb
  53.  
  54.