1 cfa37a7b 2004-04-10 devnull .TH LOCK 3
3 cfa37a7b 2004-04-10 devnull lock, canlock, unlock,
4 cfa37a7b 2004-04-10 devnull qlock, canqlock, qunlock,
5 cfa37a7b 2004-04-10 devnull rlock, canrlock, runlock,
6 cfa37a7b 2004-04-10 devnull wlock, canwlock, wunlock,
7 cfa37a7b 2004-04-10 devnull rsleep, rwakeup, rwakeupall
8 cfa37a7b 2004-04-10 devnull incref, decref
9 cfa37a7b 2004-04-10 devnull \- spin locks, queueing rendezvous locks, reader-writer locks, rendezvous points, and reference counts
10 cfa37a7b 2004-04-10 devnull .SH SYNOPSIS
13 cfa37a7b 2004-04-10 devnull #include <u.h>
14 cfa37a7b 2004-04-10 devnull #include <libc.h>
18 cfa37a7b 2004-04-10 devnull void lock(Lock *l)
19 cfa37a7b 2004-04-10 devnull int canlock(Lock *l)
20 cfa37a7b 2004-04-10 devnull void unlock(Lock *l)
24 cfa37a7b 2004-04-10 devnull void qlock(QLock *l)
25 cfa37a7b 2004-04-10 devnull int canqlock(QLock *l)
26 cfa37a7b 2004-04-10 devnull void qunlock(QLock *l)
30 cfa37a7b 2004-04-10 devnull void rlock(RWLock *l)
31 cfa37a7b 2004-04-10 devnull int canrlock(RWLock *l)
32 cfa37a7b 2004-04-10 devnull void runlock(RWLock *l)
36 cfa37a7b 2004-04-10 devnull void wlock(RWLock *l)
37 cfa37a7b 2004-04-10 devnull int canwlock(RWLock *l)
38 cfa37a7b 2004-04-10 devnull void wunlock(RWLock *l)
42 cfa37a7b 2004-04-10 devnull typedef struct Rendez {
43 cfa37a7b 2004-04-10 devnull QLock *l;
44 cfa37a7b 2004-04-10 devnull \fI...\fP
45 cfa37a7b 2004-04-10 devnull } Rendez;
49 cfa37a7b 2004-04-10 devnull void rsleep(Rendez *r)
50 cfa37a7b 2004-04-10 devnull int rwakeup(Rendez *r)
51 cfa37a7b 2004-04-10 devnull int rwakeupall(Rendez *r)
54 cfa37a7b 2004-04-10 devnull #include <thread.h>
58 cfa37a7b 2004-04-10 devnull typedef struct Ref {
59 cfa37a7b 2004-04-10 devnull long ref;
64 cfa37a7b 2004-04-10 devnull void incref(Ref*)
65 cfa37a7b 2004-04-10 devnull long decref(Ref*)
67 cfa37a7b 2004-04-10 devnull .SH DESCRIPTION
68 cfa37a7b 2004-04-10 devnull These routines are used to synchronize processes sharing memory.
71 cfa37a7b 2004-04-10 devnull are spin locks,
72 cfa37a7b 2004-04-10 devnull .B QLocks
74 cfa37a7b 2004-04-10 devnull .B RWLocks
75 058b0118 2005-01-03 devnull are different types of queueing locks,
77 cfa37a7b 2004-04-10 devnull .B Rendezes
78 cfa37a7b 2004-04-10 devnull are rendezvous points.
80 058b0118 2005-01-03 devnull Locks and rendezvous points have trivial implementations in programs
81 058b0118 2005-01-03 devnull not using the thread library
83 d32deab1 2020-08-16 rsc .MR thread (3) ),
84 058b0118 2005-01-03 devnull since such programs have no concurrency.
86 cfa37a7b 2004-04-10 devnull Used carelessly, spin locks can be expensive and can easily generate deadlocks.
87 cfa37a7b 2004-04-10 devnull Their use is discouraged, especially in programs that use the
88 cfa37a7b 2004-04-10 devnull thread library because they prevent context switches between threads.
91 cfa37a7b 2004-04-10 devnull blocks until the lock has been obtained.
92 cfa37a7b 2004-04-10 devnull .I Canlock
93 cfa37a7b 2004-04-10 devnull is non-blocking.
94 cfa37a7b 2004-04-10 devnull It tries to obtain a lock and returns a non-zero value if it
95 cfa37a7b 2004-04-10 devnull was successful, 0 otherwise.
96 cfa37a7b 2004-04-10 devnull .I Unlock
97 cfa37a7b 2004-04-10 devnull releases a lock.
99 cfa37a7b 2004-04-10 devnull .B QLocks
100 cfa37a7b 2004-04-10 devnull have the same interface but are not spin locks; instead if the lock is taken
101 cfa37a7b 2004-04-10 devnull .I qlock
102 058b0118 2005-01-03 devnull will suspend execution of the calling thread until it is released.
104 cfa37a7b 2004-04-10 devnull Although
105 cfa37a7b 2004-04-10 devnull .B Locks
106 cfa37a7b 2004-04-10 devnull are the more primitive lock, they have limitations; for example,
107 cfa37a7b 2004-04-10 devnull they cannot synchronize between tasks in the same
108 cfa37a7b 2004-04-10 devnull .IR proc .
110 cfa37a7b 2004-04-10 devnull .B QLocks
111 cfa37a7b 2004-04-10 devnull instead.
113 cfa37a7b 2004-04-10 devnull .B RWLocks
114 cfa37a7b 2004-04-10 devnull manage access to a data structure that has distinct readers and writers.
115 cfa37a7b 2004-04-10 devnull .I Rlock
116 cfa37a7b 2004-04-10 devnull grants read access;
117 cfa37a7b 2004-04-10 devnull .I runlock
118 cfa37a7b 2004-04-10 devnull releases it.
119 cfa37a7b 2004-04-10 devnull .I Wlock
120 cfa37a7b 2004-04-10 devnull grants write access;
121 cfa37a7b 2004-04-10 devnull .I wunlock
122 cfa37a7b 2004-04-10 devnull releases it.
123 cfa37a7b 2004-04-10 devnull .I Canrlock
125 cfa37a7b 2004-04-10 devnull .I canwlock
126 cfa37a7b 2004-04-10 devnull are the non-blocking versions.
127 cfa37a7b 2004-04-10 devnull There may be any number of simultaneous readers,
128 cfa37a7b 2004-04-10 devnull but only one writer.
129 cfa37a7b 2004-04-10 devnull Moreover,
130 cfa37a7b 2004-04-10 devnull if write access is granted no one may have
131 cfa37a7b 2004-04-10 devnull read access until write access is released.
133 cfa37a7b 2004-04-10 devnull All types of lock should be initialized to all zeros before use; this
134 cfa37a7b 2004-04-10 devnull puts them in the unlocked state.
136 cfa37a7b 2004-04-10 devnull .B Rendezes
137 cfa37a7b 2004-04-10 devnull are rendezvous points. Each
138 cfa37a7b 2004-04-10 devnull .B Rendez
140 cfa37a7b 2004-04-10 devnull is protected by a
141 cfa37a7b 2004-04-10 devnull .B QLock
142 cfa37a7b 2004-04-10 devnull .IB r -> l \fR,
143 cfa37a7b 2004-04-10 devnull which must be held by the callers of
144 cfa37a7b 2004-04-10 devnull .IR rsleep ,
145 cfa37a7b 2004-04-10 devnull .IR rwakeup ,
147 cfa37a7b 2004-04-10 devnull .IR rwakeupall .
148 cfa37a7b 2004-04-10 devnull .I Rsleep
149 cfa37a7b 2004-04-10 devnull atomically releases
150 cfa37a7b 2004-04-10 devnull .IB r -> l
151 cfa37a7b 2004-04-10 devnull and suspends execution of the calling task.
152 cfa37a7b 2004-04-10 devnull After resuming execution,
153 cfa37a7b 2004-04-10 devnull .I rsleep
154 cfa37a7b 2004-04-10 devnull will reacquire
155 cfa37a7b 2004-04-10 devnull .IB r -> l
156 cfa37a7b 2004-04-10 devnull before returning.
157 cfa37a7b 2004-04-10 devnull If any processes are sleeping on
159 cfa37a7b 2004-04-10 devnull .I rwakeup
160 cfa37a7b 2004-04-10 devnull wakes one of them.
161 1cccddd6 2008-07-09 devnull It returns 1 if a process was awakened, 0 if not.
162 cfa37a7b 2004-04-10 devnull .I Rwakeupall
163 cfa37a7b 2004-04-10 devnull wakes all processes sleeping on
165 cfa37a7b 2004-04-10 devnull returning the number of processes awakened.
166 cfa37a7b 2004-04-10 devnull .I Rwakeup
168 cfa37a7b 2004-04-10 devnull .I rwakeupall
169 cfa37a7b 2004-04-10 devnull do not release
170 cfa37a7b 2004-04-10 devnull .IB r -> l
171 cfa37a7b 2004-04-10 devnull and do not suspend execution of the current task.
173 cfa37a7b 2004-04-10 devnull Before use,
174 cfa37a7b 2004-04-10 devnull .B Rendezes
175 cfa37a7b 2004-04-10 devnull should be initialized to all zeros except for
176 cfa37a7b 2004-04-10 devnull .IB r -> l
177 cfa37a7b 2004-04-10 devnull pointer, which should point at the
178 cfa37a7b 2004-04-10 devnull .B QLock
179 cfa37a7b 2004-04-10 devnull that will guard
184 cfa37a7b 2004-04-10 devnull contains a
186 cfa37a7b 2004-04-10 devnull that can be incremented and decremented atomically:
187 cfa37a7b 2004-04-10 devnull .I Incref
188 cfa37a7b 2004-04-10 devnull increments the
190 cfa37a7b 2004-04-10 devnull in one atomic operation.
191 cfa37a7b 2004-04-10 devnull .I Decref
192 cfa37a7b 2004-04-10 devnull atomically decrements the
194 cfa37a7b 2004-04-10 devnull and returns zero if the resulting value is zero, non-zero otherwise.
195 cfa37a7b 2004-04-10 devnull .SH SOURCE
196 c3674de4 2005-01-11 devnull .B \*9/src/lib9/qlock.c
198 c3674de4 2005-01-11 devnull .B \*9/src/libthread
199 cfa37a7b 2004-04-10 devnull .SH BUGS
200 cfa37a7b 2004-04-10 devnull .B Locks
201 058b0118 2005-01-03 devnull are not always spin locks.
202 058b0118 2005-01-03 devnull Instead they are usually implemented using the
203 058b0118 2005-01-03 devnull .I pthreads
204 058b0118 2005-01-03 devnull library's
205 058b0118 2005-01-03 devnull .BR pthread_mutex_t ,
206 058b0118 2005-01-03 devnull whose implementation method is not defined.
209 058b0118 2005-01-03 devnull .IR pthreads -based
210 058b0118 2005-01-03 devnull systems, the implementation of
212 058b0118 2005-01-03 devnull never calls
213 058b0118 2005-01-03 devnull .I pthread_mutex_destroy
214 058b0118 2005-01-03 devnull to free the
215 058b0118 2005-01-03 devnull .BR pthread_mutex_t 's.
216 058b0118 2005-01-03 devnull This leads to resource leaks on FreeBSD 5
217 058b0118 2005-01-03 devnull (though not on Linux 2.6, where
218 058b0118 2005-01-03 devnull .I pthread_mutex_destroy
219 058b0118 2005-01-03 devnull is a no-op).
222 058b0118 2005-01-03 devnull On systems that do not have a usable
223 058b0118 2005-01-03 devnull .I pthreads
224 058b0118 2005-01-03 devnull implementation, the
226 058b0118 2005-01-03 devnull implementation provided by
227 058b0118 2005-01-03 devnull .I libthread
228 058b0118 2005-01-03 devnull is still not exactly a spin lock.
229 cfa37a7b 2004-04-10 devnull After each unsuccessful attempt,
232 cfa37a7b 2004-04-10 devnull .B sleep(0)
233 cfa37a7b 2004-04-10 devnull to yield the CPU; this handles the common case
234 cfa37a7b 2004-04-10 devnull where some other process holds the lock.
235 cfa37a7b 2004-04-10 devnull After a thousand unsuccessful attempts,
237 cfa37a7b 2004-04-10 devnull sleeps for 100ms between attempts.
238 cfa37a7b 2004-04-10 devnull Another another thousand unsuccessful attempts,
240 cfa37a7b 2004-04-10 devnull sleeps for a full second between attempts.
241 cfa37a7b 2004-04-10 devnull .B Locks
242 cfa37a7b 2004-04-10 devnull are not intended to be held for long periods of time.
243 cfa37a7b 2004-04-10 devnull The 100ms and full second sleeps are only heuristics to
244 cfa37a7b 2004-04-10 devnull avoid tying up the CPU when a process deadlocks.
245 cfa37a7b 2004-04-10 devnull As discussed above,
246 cfa37a7b 2004-04-10 devnull if a lock is to be held for much more than a few instructions,
247 cfa37a7b 2004-04-10 devnull the queueing lock types should be almost always be used.
