home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / parallel / 2022 < prev    next >
Encoding:
Text File  |  1992-08-31  |  3.3 KB  |  138 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!gatech!hubcap!fpst
  3. From: bmw@isgtec.com (Bruce M. Walker)
  4. Subject: Re: Locks without using atomic instructions
  5. Message-ID: <1992Sep1.134249.6189@hubcap.clemson.edu>
  6. Summary: one implementation in C
  7. Keywords: Lock asynchronous
  8. Sender: fpst@hubcap.clemson.edu (Steve Stevenson)
  9. Organization: ISG Technologies Inc., Mississauga Ontario
  10. References: <1992Aug31.124322.2555@hubcap.clemson.edu>
  11. Date:     Tue, 1 Sep 1992 09:02:50 -0400
  12. Approved: parallel@hubcap.clemson.edu
  13. Lines: 123
  14.  
  15.  
  16. In article <1992Aug31.124322.2555@hubcap.clemson.edu> iane@werple.pub.uu.oz.au (Ian Evans) writes:
  17. > Let's say that there is a system (unfortunately there is) where some
  18. > person (me) wants to get a few different computers communicating reliably,
  19. > and the only available mechanism is reading a shared memory location, or
  20. > writing a location, but there is no atomic set & test type instruction.
  21. > It is possible, however, to get a unique system-wide process ID.
  22.  
  23. A working algorithm is described (in a Pascalish dialect) in "Operating
  24. Systems Concepts", by Silberschatz et al.  I know it works because I've
  25. tested it on an 8-cpu multiprocessor.
  26.  
  27. I translated it into C, and it's pretty small, so what the heck!
  28. here it is ...
  29.  
  30. ------ begin spinlock.c -----
  31. /*
  32.  * spinlock.c -- critical regions support
  33.  *
  34.  * This algorithm is from "Operating System Concepts, 2nd Ed., Peterson &
  35.  * Silberschatz; Addison Wesley"; chapter 9, Algorithm 5.
  36.  * Algorithm is due to Eisenberg and McGuire 1972.
  37.  */
  38.  
  39. /*
  40.  * Instructions:
  41.  *
  42.  * Define a spin-lock structure with the macro DEF_SPIN().
  43.  * Lock a critical region by calling lock() and passing the address
  44.  *  of a spin-lock structure to it.
  45.  * Un-lock the critical region by calling unlock() with the same address.
  46.  *
  47.  * You must supply a routine my_proc_id() that yields a system-wide unique
  48.  * integer identifier for each cpu, and a value for the macro MAX_CPU.
  49.  *
  50.  * Example:
  51.  *
  52.  *   DEF_SPIN(lck)
  53.  *
  54.  *   one_at_a_time()
  55.  *   {
  56.  *       lock(&lck);
  57.  *       ...
  58.  *       unlock(&lck);
  59.  *   }
  60.  */
  61.  
  62. #include "spinlock.h"
  63.  
  64. /*
  65.  * attempt to lock a critical region; spin until successful.
  66.  */
  67. void
  68. lock(SPIN *c)
  69. {
  70.     register int j, i = my_proc_id();
  71.  
  72.     for (;;) {
  73.         c->flag[i] = WANT_IN;
  74.         j = c->turn;
  75.         while (j != i)
  76.             if (c->flag[j] != IDLE)
  77.                 j = c->turn;
  78.             else
  79.                 j = (j+1) % MAX_CPU;
  80.         for (c->flag[i] = IN_CS;
  81.              j < MAX_CPU && (j == i || c->flag[j] != IN_CS);
  82.              j++)
  83.             ; /* empty */
  84.         if (j >= MAX_CPU && (c->turn == i || c->flag[c->turn] == IDLE))
  85.             break;
  86.     }
  87.     c->turn = i;
  88. }
  89.  
  90. /*
  91.  * unlock a critical region.
  92.  */
  93. void
  94. unlock(SPIN *c)
  95. {
  96.     int j = (c->turn+1) % MAX_CPU;
  97.     while (c->flag[j] == IDLE)
  98.         j = (j+1) % MAX_CPU;
  99.     c->turn = j;
  100.     c->flag[my_proc_id()] = IDLE;
  101. }
  102. ------ end spinlock.c -----
  103.  
  104. ------ begin spinlock.h -----
  105. /*
  106.  * spinlock.h -- critical regions def'ns
  107.  */
  108.  
  109. #ifndef _SPINLOCK_H_
  110. #define _SPINLOCK_H_
  111.  
  112. typedef struct {
  113.     int turn;
  114.     int flag[MAX_CPU];
  115. } SPIN;
  116.  
  117. /* flags */
  118. #define IDLE    0
  119. #define WANT_IN    1
  120. #define IN_CS    2
  121.  
  122. #define DEF_SPIN(x)    SPIN x = {0}    /* initialize whole thing to zero */
  123.  
  124. /* critical.c */
  125. void lock(SPIN *c);
  126. void unlock(SPIN *c);
  127.  
  128. #endif /* _SPINLOCK_H_ */
  129. ------ end spinlock.h -----
  130.  
  131. ObEnjoy: Enjoy!
  132.  
  133. --
  134. "The path of my life is strewn with cowpats from the devils' own herd."
  135.                                           -- Edmund Blackadder II
  136. bmw@isgtec.com   [ ...!uunet.ca!isgtec!bmw ]  Bruce Walker
  137.  
  138.