Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 1 | # Defines classes that provide synchronization objects. Note that use of |
| 2 | # this module requires that your Python support threads. |
| 3 | # |
Guido van Rossum | a697058 | 1994-05-18 08:14:04 +0000 | [diff] [blame] | 4 | # condition(lock=None) # a POSIX-like condition-variable object |
| 5 | # barrier(n) # an n-thread barrier |
| 6 | # event() # an event object |
| 7 | # semaphore(n=1) # a semaphore object, with initial count n |
| 8 | # mrsw() # a multiple-reader single-writer lock |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 9 | # |
| 10 | # CONDITIONS |
| 11 | # |
| 12 | # A condition object is created via |
| 13 | # import this_module |
Guido van Rossum | a697058 | 1994-05-18 08:14:04 +0000 | [diff] [blame] | 14 | # your_condition_object = this_module.condition(lock=None) |
| 15 | # |
| 16 | # As explained below, a condition object has a lock associated with it, |
| 17 | # used in the protocol to protect condition data. You can specify a |
| 18 | # lock to use in the constructor, else the constructor will allocate |
| 19 | # an anonymous lock for you. Specifying a lock explicitly can be useful |
| 20 | # when more than one condition keys off the same set of shared data. |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 21 | # |
| 22 | # Methods: |
| 23 | # .acquire() |
| 24 | # acquire the lock associated with the condition |
| 25 | # .release() |
| 26 | # release the lock associated with the condition |
| 27 | # .wait() |
| 28 | # block the thread until such time as some other thread does a |
| 29 | # .signal or .broadcast on the same condition, and release the |
| 30 | # lock associated with the condition. The lock associated with |
| 31 | # the condition MUST be in the acquired state at the time |
| 32 | # .wait is invoked. |
| 33 | # .signal() |
| 34 | # wake up exactly one thread (if any) that previously did a .wait |
| 35 | # on the condition; that thread will awaken with the lock associated |
| 36 | # with the condition in the acquired state. If no threads are |
| 37 | # .wait'ing, this is a nop. If more than one thread is .wait'ing on |
| 38 | # the condition, any of them may be awakened. |
| 39 | # .broadcast() |
| 40 | # wake up all threads (if any) that are .wait'ing on the condition; |
| 41 | # the threads are woken up serially, each with the lock in the |
| 42 | # acquired state, so should .release() as soon as possible. If no |
| 43 | # threads are .wait'ing, this is a nop. |
| 44 | # |
| 45 | # Note that if a thread does a .wait *while* a signal/broadcast is |
Guido van Rossum | 846c322 | 1994-05-17 08:34:33 +0000 | [diff] [blame] | 46 | # in progress, it's guaranteeed to block until a subsequent |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 47 | # signal/broadcast. |
| 48 | # |
| 49 | # Secret feature: `broadcast' actually takes an integer argument, |
| 50 | # and will wake up exactly that many waiting threads (or the total |
| 51 | # number waiting, if that's less). Use of this is dubious, though, |
| 52 | # and probably won't be supported if this form of condition is |
| 53 | # reimplemented in C. |
| 54 | # |
| 55 | # DIFFERENCES FROM POSIX |
| 56 | # |
| 57 | # + A separate mutex is not needed to guard condition data. Instead, a |
| 58 | # condition object can (must) be .acquire'ed and .release'ed directly. |
| 59 | # This eliminates a common error in using POSIX conditions. |
| 60 | # |
| 61 | # + Because of implementation difficulties, a POSIX `signal' wakes up |
| 62 | # _at least_ one .wait'ing thread. Race conditions make it difficult |
| 63 | # to stop that. This implementation guarantees to wake up only one, |
| 64 | # but you probably shouldn't rely on that. |
| 65 | # |
| 66 | # PROTOCOL |
| 67 | # |
| 68 | # Condition objects are used to block threads until "some condition" is |
| 69 | # true. E.g., a thread may wish to wait until a producer pumps out data |
| 70 | # for it to consume, or a server may wish to wait until someone requests |
| 71 | # its services, or perhaps a whole bunch of threads want to wait until a |
| 72 | # preceding pass over the data is complete. Early models for conditions |
| 73 | # relied on some other thread figuring out when a blocked thread's |
| 74 | # condition was true, and made the other thread responsible both for |
| 75 | # waking up the blocked thread and guaranteeing that it woke up with all |
| 76 | # data in a correct state. This proved to be very delicate in practice, |
| 77 | # and gave conditions a bad name in some circles. |
| 78 | # |
| 79 | # The POSIX model addresses these problems by making a thread responsible |
| 80 | # for ensuring that its own state is correct when it wakes, and relies |
| 81 | # on a rigid protocol to make this easy; so long as you stick to the |
| 82 | # protocol, POSIX conditions are easy to "get right": |
| 83 | # |
| 84 | # A) The thread that's waiting for some arbitrarily-complex condition |
| 85 | # (ACC) to become true does: |
| 86 | # |
| 87 | # condition.acquire() |
| 88 | # while not (code to evaluate the ACC): |
| 89 | # condition.wait() |
| 90 | # # That blocks the thread, *and* releases the lock. When a |
| 91 | # # condition.signal() happens, it will wake up some thread that |
| 92 | # # did a .wait, *and* acquire the lock again before .wait |
| 93 | # # returns. |
| 94 | # # |
| 95 | # # Because the lock is acquired at this point, the state used |
| 96 | # # in evaluating the ACC is frozen, so it's safe to go back & |
| 97 | # # reevaluate the ACC. |
| 98 | # |
| 99 | # # At this point, ACC is true, and the thread has the condition |
| 100 | # # locked. |
| 101 | # # So code here can safely muck with the shared state that |
| 102 | # # went into evaluating the ACC -- if it wants to. |
| 103 | # # When done mucking with the shared state, do |
| 104 | # condition.release() |
| 105 | # |
| 106 | # B) Threads that are mucking with shared state that may affect the |
| 107 | # ACC do: |
| 108 | # |
| 109 | # condition.acquire() |
| 110 | # # muck with shared state |
| 111 | # condition.release() |
| 112 | # if it's possible that ACC is true now: |
| 113 | # condition.signal() # or .broadcast() |
| 114 | # |
| 115 | # Note: You may prefer to put the "if" clause before the release(). |
| 116 | # That's fine, but do note that anyone waiting on the signal will |
| 117 | # stay blocked until the release() is done (since acquiring the |
| 118 | # condition is part of what .wait() does before it returns). |
| 119 | # |
| 120 | # TRICK OF THE TRADE |
| 121 | # |
| 122 | # With simpler forms of conditions, it can be impossible to know when |
| 123 | # a thread that's supposed to do a .wait has actually done it. But |
| 124 | # because this form of condition releases a lock as _part_ of doing a |
| 125 | # wait, the state of that lock can be used to guarantee it. |
| 126 | # |
| 127 | # E.g., suppose thread A spawns thread B and later wants to wait for B to |
| 128 | # complete: |
| 129 | # |
| 130 | # In A: In B: |
| 131 | # |
| 132 | # B_done = condition() ... do work ... |
| 133 | # B_done.acquire() B_done.acquire(); B_done.release() |
| 134 | # spawn B B_done.signal() |
| 135 | # ... some time later ... ... and B exits ... |
| 136 | # B_done.wait() |
| 137 | # |
| 138 | # Because B_done was in the acquire'd state at the time B was spawned, |
| 139 | # B's attempt to acquire B_done can't succeed until A has done its |
| 140 | # B_done.wait() (which releases B_done). So B's B_done.signal() is |
| 141 | # guaranteed to be seen by the .wait(). Without the lock trick, B |
| 142 | # may signal before A .waits, and then A would wait forever. |
| 143 | # |
| 144 | # BARRIERS |
| 145 | # |
| 146 | # A barrier object is created via |
| 147 | # import this_module |
| 148 | # your_barrier = this_module.barrier(num_threads) |
| 149 | # |
| 150 | # Methods: |
| 151 | # .enter() |
| 152 | # the thread blocks until num_threads threads in all have done |
| 153 | # .enter(). Then the num_threads threads that .enter'ed resume, |
| 154 | # and the barrier resets to capture the next num_threads threads |
| 155 | # that .enter it. |
| 156 | # |
| 157 | # EVENTS |
| 158 | # |
| 159 | # An event object is created via |
| 160 | # import this_module |
| 161 | # your_event = this_module.event() |
| 162 | # |
| 163 | # An event has two states, `posted' and `cleared'. An event is |
| 164 | # created in the cleared state. |
| 165 | # |
| 166 | # Methods: |
| 167 | # |
| 168 | # .post() |
| 169 | # Put the event in the posted state, and resume all threads |
| 170 | # .wait'ing on the event (if any). |
| 171 | # |
| 172 | # .clear() |
| 173 | # Put the event in the cleared state. |
| 174 | # |
| 175 | # .is_posted() |
| 176 | # Returns 0 if the event is in the cleared state, or 1 if the event |
| 177 | # is in the posted state. |
| 178 | # |
| 179 | # .wait() |
| 180 | # If the event is in the posted state, returns immediately. |
| 181 | # If the event is in the cleared state, blocks the calling thread |
| 182 | # until the event is .post'ed by another thread. |
| 183 | # |
| 184 | # Note that an event, once posted, remains posted until explicitly |
| 185 | # cleared. Relative to conditions, this is both the strength & weakness |
| 186 | # of events. It's a strength because the .post'ing thread doesn't have to |
| 187 | # worry about whether the threads it's trying to communicate with have |
| 188 | # already done a .wait (a condition .signal is seen only by threads that |
| 189 | # do a .wait _prior_ to the .signal; a .signal does not persist). But |
| 190 | # it's a weakness because .clear'ing an event is error-prone: it's easy |
| 191 | # to mistakenly .clear an event before all the threads you intended to |
| 192 | # see the event get around to .wait'ing on it. But so long as you don't |
| 193 | # need to .clear an event, events are easy to use safely. |
| 194 | # |
Guido van Rossum | 846c322 | 1994-05-17 08:34:33 +0000 | [diff] [blame] | 195 | # SEMAPHORES |
| 196 | # |
| 197 | # A semaphore object is created via |
| 198 | # import this_module |
| 199 | # your_semaphore = this_module.semaphore(count=1) |
| 200 | # |
| 201 | # A semaphore has an integer count associated with it. The initial value |
| 202 | # of the count is specified by the optional argument (which defaults to |
| 203 | # 1) passed to the semaphore constructor. |
| 204 | # |
| 205 | # Methods: |
| 206 | # |
| 207 | # .p() |
| 208 | # If the semaphore's count is greater than 0, decrements the count |
| 209 | # by 1 and returns. |
| 210 | # Else if the semaphore's count is 0, blocks the calling thread |
| 211 | # until a subsequent .v() increases the count. When that happens, |
| 212 | # the count will be decremented by 1 and the calling thread resumed. |
| 213 | # |
| 214 | # .v() |
| 215 | # Increments the semaphore's count by 1, and wakes up a thread (if |
| 216 | # any) blocked by a .p(). It's an (detected) error for a .v() to |
| 217 | # increase the semaphore's count to a value larger than the initial |
| 218 | # count. |
Guido van Rossum | a697058 | 1994-05-18 08:14:04 +0000 | [diff] [blame] | 219 | # |
| 220 | # MULTIPLE-READER SINGLE-WRITER LOCKS |
| 221 | # |
| 222 | # A mrsw lock is created via |
| 223 | # import this_module |
| 224 | # your_mrsw_lock = this_module.mrsw() |
| 225 | # |
| 226 | # This kind of lock is often useful with complex shared data structures. |
| 227 | # The object lets any number of "readers" proceed, so long as no thread |
| 228 | # wishes to "write". When a (one or more) thread declares its intention |
| 229 | # to "write" (e.g., to update a shared structure), all current readers |
| 230 | # are allowed to finish, and then a writer gets exclusive access; all |
| 231 | # other readers & writers are blocked until the current writer completes. |
| 232 | # Finally, if some thread is waiting to write and another is waiting to |
| 233 | # read, the writer takes precedence. |
| 234 | # |
| 235 | # Methods: |
| 236 | # |
| 237 | # .read_in() |
| 238 | # If no thread is writing or waiting to write, returns immediately. |
| 239 | # Else blocks until no thread is writing or waiting to write. So |
| 240 | # long as some thread has completed a .read_in but not a .read_out, |
| 241 | # writers are blocked. |
| 242 | # |
| 243 | # .read_out() |
| 244 | # Use sometime after a .read_in to declare that the thread is done |
| 245 | # reading. When all threads complete reading, a writer can proceed. |
| 246 | # |
| 247 | # .write_in() |
| 248 | # If no thread is writing (has completed a .write_in, but hasn't yet |
| 249 | # done a .write_out) or reading (similarly), returns immediately. |
| 250 | # Else blocks the calling thread, and threads waiting to read, until |
| 251 | # the current writer completes writing or all the current readers |
| 252 | # complete reading; if then more than one thread is waiting to |
| 253 | # write, one of them is allowed to proceed, but which one is not |
| 254 | # specified. |
| 255 | # |
| 256 | # .write_out() |
| 257 | # Use sometime after a .write_in to declare that the thread is done |
| 258 | # writing. Then if some other thread is waiting to write, it's |
| 259 | # allowed to proceed. Else all threads (if any) waiting to read are |
| 260 | # allowed to proceed. |
Guido van Rossum | 6910f42 | 1994-10-08 19:07:57 +0000 | [diff] [blame] | 261 | # |
| 262 | # .write_to_read() |
| 263 | # Use instead of a .write_in to declare that the thread is done |
| 264 | # writing but wants to continue reading without other writers |
| 265 | # intervening. If there are other threads waiting to write, they |
| 266 | # are allowed to proceed only if the current thread calls |
| 267 | # .read_out; threads waiting to read are only allowed to proceed |
| 268 | # if there are are no threads waiting to write. (This is a |
| 269 | # weakness of the interface!) |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 270 | |
| 271 | import thread |
| 272 | |
| 273 | class condition: |
Guido van Rossum | a697058 | 1994-05-18 08:14:04 +0000 | [diff] [blame] | 274 | def __init__(self, lock=None): |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 275 | # the lock actually used by .acquire() and .release() |
Guido van Rossum | a697058 | 1994-05-18 08:14:04 +0000 | [diff] [blame] | 276 | if lock is None: |
| 277 | self.mutex = thread.allocate_lock() |
| 278 | else: |
| 279 | if hasattr(lock, 'acquire') and \ |
| 280 | hasattr(lock, 'release'): |
| 281 | self.mutex = lock |
| 282 | else: |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 283 | raise TypeError('condition constructor requires ' \ |
| 284 | 'a lock argument') |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 285 | |
| 286 | # lock used to block threads until a signal |
| 287 | self.checkout = thread.allocate_lock() |
| 288 | self.checkout.acquire() |
| 289 | |
| 290 | # internal critical-section lock, & the data it protects |
| 291 | self.idlock = thread.allocate_lock() |
| 292 | self.id = 0 |
| 293 | self.waiting = 0 # num waiters subject to current release |
| 294 | self.pending = 0 # num waiters awaiting next signal |
| 295 | self.torelease = 0 # num waiters to release |
| 296 | self.releasing = 0 # 1 iff release is in progress |
| 297 | |
| 298 | def acquire(self): |
| 299 | self.mutex.acquire() |
| 300 | |
| 301 | def release(self): |
| 302 | self.mutex.release() |
| 303 | |
| 304 | def wait(self): |
| 305 | mutex, checkout, idlock = self.mutex, self.checkout, self.idlock |
| 306 | if not mutex.locked(): |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 307 | raise ValueError("condition must be .acquire'd when .wait() invoked") |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 308 | |
| 309 | idlock.acquire() |
| 310 | myid = self.id |
| 311 | self.pending = self.pending + 1 |
| 312 | idlock.release() |
| 313 | |
| 314 | mutex.release() |
| 315 | |
| 316 | while 1: |
| 317 | checkout.acquire(); idlock.acquire() |
| 318 | if myid < self.id: |
| 319 | break |
| 320 | checkout.release(); idlock.release() |
| 321 | |
| 322 | self.waiting = self.waiting - 1 |
| 323 | self.torelease = self.torelease - 1 |
| 324 | if self.torelease: |
| 325 | checkout.release() |
| 326 | else: |
| 327 | self.releasing = 0 |
| 328 | if self.waiting == self.pending == 0: |
| 329 | self.id = 0 |
| 330 | idlock.release() |
| 331 | mutex.acquire() |
| 332 | |
| 333 | def signal(self): |
| 334 | self.broadcast(1) |
| 335 | |
| 336 | def broadcast(self, num = -1): |
| 337 | if num < -1: |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 338 | raise ValueError('.broadcast called with num %r' % (num,)) |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 339 | if num == 0: |
| 340 | return |
| 341 | self.idlock.acquire() |
| 342 | if self.pending: |
| 343 | self.waiting = self.waiting + self.pending |
| 344 | self.pending = 0 |
| 345 | self.id = self.id + 1 |
| 346 | if num == -1: |
| 347 | self.torelease = self.waiting |
| 348 | else: |
| 349 | self.torelease = min( self.waiting, |
| 350 | self.torelease + num ) |
| 351 | if self.torelease and not self.releasing: |
| 352 | self.releasing = 1 |
| 353 | self.checkout.release() |
| 354 | self.idlock.release() |
| 355 | |
| 356 | class barrier: |
| 357 | def __init__(self, n): |
| 358 | self.n = n |
| 359 | self.togo = n |
| 360 | self.full = condition() |
| 361 | |
| 362 | def enter(self): |
| 363 | full = self.full |
| 364 | full.acquire() |
| 365 | self.togo = self.togo - 1 |
| 366 | if self.togo: |
| 367 | full.wait() |
| 368 | else: |
| 369 | self.togo = self.n |
| 370 | full.broadcast() |
| 371 | full.release() |
| 372 | |
| 373 | class event: |
| 374 | def __init__(self): |
| 375 | self.state = 0 |
| 376 | self.posted = condition() |
| 377 | |
| 378 | def post(self): |
| 379 | self.posted.acquire() |
| 380 | self.state = 1 |
| 381 | self.posted.broadcast() |
| 382 | self.posted.release() |
| 383 | |
| 384 | def clear(self): |
| 385 | self.posted.acquire() |
| 386 | self.state = 0 |
| 387 | self.posted.release() |
| 388 | |
| 389 | def is_posted(self): |
| 390 | self.posted.acquire() |
| 391 | answer = self.state |
| 392 | self.posted.release() |
| 393 | return answer |
| 394 | |
| 395 | def wait(self): |
| 396 | self.posted.acquire() |
Guido van Rossum | 846c322 | 1994-05-17 08:34:33 +0000 | [diff] [blame] | 397 | if not self.state: |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 398 | self.posted.wait() |
| 399 | self.posted.release() |
| 400 | |
Guido van Rossum | 846c322 | 1994-05-17 08:34:33 +0000 | [diff] [blame] | 401 | class semaphore: |
| 402 | def __init__(self, count=1): |
| 403 | if count <= 0: |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 404 | raise ValueError('semaphore count %d; must be >= 1' % count) |
Guido van Rossum | 846c322 | 1994-05-17 08:34:33 +0000 | [diff] [blame] | 405 | self.count = count |
| 406 | self.maxcount = count |
| 407 | self.nonzero = condition() |
| 408 | |
| 409 | def p(self): |
| 410 | self.nonzero.acquire() |
| 411 | while self.count == 0: |
| 412 | self.nonzero.wait() |
| 413 | self.count = self.count - 1 |
| 414 | self.nonzero.release() |
| 415 | |
| 416 | def v(self): |
| 417 | self.nonzero.acquire() |
| 418 | if self.count == self.maxcount: |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 419 | raise ValueError('.v() tried to raise semaphore count above ' \ |
| 420 | 'initial value %r' % self.maxcount) |
Guido van Rossum | 846c322 | 1994-05-17 08:34:33 +0000 | [diff] [blame] | 421 | self.count = self.count + 1 |
| 422 | self.nonzero.signal() |
| 423 | self.nonzero.release() |
| 424 | |
Guido van Rossum | a697058 | 1994-05-18 08:14:04 +0000 | [diff] [blame] | 425 | class mrsw: |
| 426 | def __init__(self): |
| 427 | # critical-section lock & the data it protects |
| 428 | self.rwOK = thread.allocate_lock() |
| 429 | self.nr = 0 # number readers actively reading (not just waiting) |
| 430 | self.nw = 0 # number writers either waiting to write or writing |
| 431 | self.writing = 0 # 1 iff some thread is writing |
| 432 | |
| 433 | # conditions |
| 434 | self.readOK = condition(self.rwOK) # OK to unblock readers |
| 435 | self.writeOK = condition(self.rwOK) # OK to unblock writers |
| 436 | |
| 437 | def read_in(self): |
| 438 | self.rwOK.acquire() |
| 439 | while self.nw: |
| 440 | self.readOK.wait() |
| 441 | self.nr = self.nr + 1 |
| 442 | self.rwOK.release() |
| 443 | |
| 444 | def read_out(self): |
| 445 | self.rwOK.acquire() |
| 446 | if self.nr <= 0: |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 447 | raise ValueError('.read_out() invoked without an active reader') |
Guido van Rossum | a697058 | 1994-05-18 08:14:04 +0000 | [diff] [blame] | 448 | self.nr = self.nr - 1 |
| 449 | if self.nr == 0: |
| 450 | self.writeOK.signal() |
| 451 | self.rwOK.release() |
| 452 | |
| 453 | def write_in(self): |
| 454 | self.rwOK.acquire() |
| 455 | self.nw = self.nw + 1 |
| 456 | while self.writing or self.nr: |
| 457 | self.writeOK.wait() |
| 458 | self.writing = 1 |
| 459 | self.rwOK.release() |
| 460 | |
| 461 | def write_out(self): |
| 462 | self.rwOK.acquire() |
| 463 | if not self.writing: |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 464 | raise ValueError('.write_out() invoked without an active writer') |
Guido van Rossum | a697058 | 1994-05-18 08:14:04 +0000 | [diff] [blame] | 465 | self.writing = 0 |
| 466 | self.nw = self.nw - 1 |
| 467 | if self.nw: |
| 468 | self.writeOK.signal() |
| 469 | else: |
| 470 | self.readOK.broadcast() |
| 471 | self.rwOK.release() |
| 472 | |
Guido van Rossum | 6910f42 | 1994-10-08 19:07:57 +0000 | [diff] [blame] | 473 | def write_to_read(self): |
Guido van Rossum | 4117e54 | 1998-09-14 16:44:15 +0000 | [diff] [blame] | 474 | self.rwOK.acquire() |
| 475 | if not self.writing: |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 476 | raise ValueError('.write_to_read() invoked without an active writer') |
Guido van Rossum | 4117e54 | 1998-09-14 16:44:15 +0000 | [diff] [blame] | 477 | self.writing = 0 |
| 478 | self.nw = self.nw - 1 |
| 479 | self.nr = self.nr + 1 |
| 480 | if not self.nw: |
| 481 | self.readOK.broadcast() |
| 482 | self.rwOK.release() |
Guido van Rossum | 6910f42 | 1994-10-08 19:07:57 +0000 | [diff] [blame] | 483 | |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 484 | # The rest of the file is a test case, that runs a number of parallelized |
| 485 | # quicksorts in parallel. If it works, you'll get about 600 lines of |
| 486 | # tracing output, with a line like |
| 487 | # test passed! 209 threads created in all |
| 488 | # as the last line. The content and order of preceding lines will |
| 489 | # vary across runs. |
| 490 | |
| 491 | def _new_thread(func, *args): |
| 492 | global TID |
| 493 | tid.acquire(); id = TID = TID+1; tid.release() |
| 494 | io.acquire(); alive.append(id); \ |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 495 | print('starting thread', id, '--', len(alive), 'alive'); \ |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 496 | io.release() |
| 497 | thread.start_new_thread( func, (id,) + args ) |
| 498 | |
| 499 | def _qsort(tid, a, l, r, finished): |
| 500 | # sort a[l:r]; post finished when done |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 501 | io.acquire(); print('thread', tid, 'qsort', l, r); io.release() |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 502 | if r-l > 1: |
| 503 | pivot = a[l] |
| 504 | j = l+1 # make a[l:j] <= pivot, and a[j:r] > pivot |
| 505 | for i in range(j, r): |
| 506 | if a[i] <= pivot: |
| 507 | a[j], a[i] = a[i], a[j] |
| 508 | j = j + 1 |
| 509 | a[l], a[j-1] = a[j-1], pivot |
| 510 | |
| 511 | l_subarray_sorted = event() |
| 512 | r_subarray_sorted = event() |
| 513 | _new_thread(_qsort, a, l, j-1, l_subarray_sorted) |
| 514 | _new_thread(_qsort, a, j, r, r_subarray_sorted) |
| 515 | l_subarray_sorted.wait() |
| 516 | r_subarray_sorted.wait() |
| 517 | |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 518 | io.acquire(); print('thread', tid, 'qsort done'); \ |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 519 | alive.remove(tid); io.release() |
| 520 | finished.post() |
| 521 | |
| 522 | def _randarray(tid, a, finished): |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 523 | io.acquire(); print('thread', tid, 'randomizing array'); \ |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 524 | io.release() |
| 525 | for i in range(1, len(a)): |
| 526 | wh.acquire(); j = randint(0,i); wh.release() |
| 527 | a[i], a[j] = a[j], a[i] |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 528 | io.acquire(); print('thread', tid, 'randomizing done'); \ |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 529 | alive.remove(tid); io.release() |
| 530 | finished.post() |
| 531 | |
| 532 | def _check_sort(a): |
| 533 | if a != range(len(a)): |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 534 | raise ValueError('a not sorted', a) |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 535 | |
| 536 | def _run_one_sort(tid, a, bar, done): |
| 537 | # randomize a, and quicksort it |
| 538 | # for variety, all the threads running this enter a barrier |
| 539 | # at the end, and post `done' after the barrier exits |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 540 | io.acquire(); print('thread', tid, 'randomizing', a); \ |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 541 | io.release() |
| 542 | finished = event() |
| 543 | _new_thread(_randarray, a, finished) |
| 544 | finished.wait() |
| 545 | |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 546 | io.acquire(); print('thread', tid, 'sorting', a); io.release() |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 547 | finished.clear() |
| 548 | _new_thread(_qsort, a, 0, len(a), finished) |
| 549 | finished.wait() |
| 550 | _check_sort(a) |
| 551 | |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 552 | io.acquire(); print('thread', tid, 'entering barrier'); \ |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 553 | io.release() |
| 554 | bar.enter() |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 555 | io.acquire(); print('thread', tid, 'leaving barrier'); \ |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 556 | io.release() |
| 557 | io.acquire(); alive.remove(tid); io.release() |
| 558 | bar.enter() # make sure they've all removed themselves from alive |
| 559 | ## before 'done' is posted |
| 560 | bar.enter() # just to be cruel |
| 561 | done.post() |
| 562 | |
| 563 | def test(): |
| 564 | global TID, tid, io, wh, randint, alive |
Guido van Rossum | 6c3a2cb | 1998-05-20 17:13:01 +0000 | [diff] [blame] | 565 | import random |
| 566 | randint = random.randint |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 567 | |
| 568 | TID = 0 # thread ID (1, 2, ...) |
| 569 | tid = thread.allocate_lock() # for changing TID |
| 570 | io = thread.allocate_lock() # for printing, and 'alive' |
Guido van Rossum | 6c3a2cb | 1998-05-20 17:13:01 +0000 | [diff] [blame] | 571 | wh = thread.allocate_lock() # for calls to random |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 572 | alive = [] # IDs of active threads |
| 573 | |
| 574 | NSORTS = 5 |
| 575 | arrays = [] |
| 576 | for i in range(NSORTS): |
| 577 | arrays.append( range( (i+1)*10 ) ) |
| 578 | |
| 579 | bar = barrier(NSORTS) |
| 580 | finished = event() |
| 581 | for i in range(NSORTS): |
| 582 | _new_thread(_run_one_sort, arrays[i], bar, finished) |
| 583 | finished.wait() |
| 584 | |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 585 | print('all threads done, and checking results ...') |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 586 | if alive: |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 587 | raise ValueError('threads still alive at end', alive) |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 588 | for i in range(NSORTS): |
| 589 | a = arrays[i] |
| 590 | if len(a) != (i+1)*10: |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 591 | raise ValueError('length of array', i, 'screwed up') |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 592 | _check_sort(a) |
| 593 | |
Collin Winter | 6f2df4d | 2007-07-17 20:59:35 +0000 | [diff] [blame^] | 594 | print('test passed!', TID, 'threads created in all') |
Guido van Rossum | 48a69b7 | 1994-05-16 09:35:22 +0000 | [diff] [blame] | 595 | |
| 596 | if __name__ == '__main__': |
| 597 | test() |
| 598 | |
| 599 | # end of module |