Changeset 7ed01be for doc/theses/colby_parsons_MMAth
- Timestamp:
- Jul 17, 2023, 12:03:56 PM (13 months ago)
- Branches:
- master
- Children:
- 494a7e5
- Parents:
- dbf5e18
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/colby_parsons_MMAth/text/waituntil.tex
rdbf5e18 r7ed01be 15 15 16 16 Now the problem is extended. 17 Some stalls are wheelchair accessible and some stalls have specific sexual orientation.17 Some stalls are wheelchair accessible and some stalls have specific gender identification. 18 18 Each person (thread) may be limited to only one kind of stall or may choose among different kinds of stalls that match their criteria. 19 19 Immediately, the problem becomes more difficult. … … 44 44 Guards are a conditional operator similar to an @if@, except they apply to the resource being waited on. 45 45 If a guard is false, then the resource it guards is not in the set of resources being waited on. 46 If all guards are false, the ALT does nothing and the thread continues.46 If all guards are false, the ALT, Occam's \gls{synch_multiplex} statement, does nothing and the thread continues. 47 47 Guards can be simulated using @if@ statements as shown in~\cite[rule~2.4, p~183]{Roscoe88} 48 48 \begin{lstlisting}[basicstyle=\rm,mathescape] … … 377 377 378 378 \section{\lstinline{waituntil} Implementation} 379 The @waituntil@ statement is not inherently complex, and the pseudo code i npresented in Figure~\ref{f:WU_Impl}.379 The @waituntil@ statement is not inherently complex, and the pseudo code is presented in Figure~\ref{f:WU_Impl}. 380 380 The complexity comes from the consideration of race conditions and synchronization needed when supporting various primitives. 381 381 The basic steps of the @waituntil@ statement are: … … 388 388 while ( statement predicate not satisfied ) { $\C{// check predicate}$ 389 389 // block 390 for ( resource in waituntil statement ) $\C{// run true code blocks}$ 390 for ( resource in waituntil statement ) { $\C{// run true code blocks}$ 391 if ( statement predicate is satisfied ) break; 391 392 if ( resource is avail ) run code block 392 } 393 for ( resource in waituntil statement ) { 394 if ( statement predicate is run-satisfied ) break; 395 if ( resource is avail ) run code block 393 } 396 394 } 397 395 for ( node in s ) $\C{// deregister nodes}\CRT$ 398 if (unregister_select( resource, node ) ) run code block 399 \end{cfa} 400 Each clause has a couple of statuses, UNSAT when not available, SAT when available and not run and RUN when it is available and the associated code block was run. 401 The first while ( statement predicate not satisfied) waits until the predicate is satisfied, where UNSAT = false and SAT = true and RUN = true. 402 The if ( statement predicate is run-satisfied ) considers a status of RUN = true and all other statuses to be false. 403 396 if ( unregister_select( resource, node ) ) run code block 397 \end{cfa} 404 398 \caption{\lstinline{waituntil} Implementation} 405 399 \label{f:WU_Impl} … … 416 410 The thread executing the @waituntil@ then loops until the statement's predicate is satisfied. 417 411 In each iteration, if the predicate is unsatisfied, the thread blocks. 418 If clauses becomes satisfied, the thread unblocks, and for each satisfied the block fails and the thread proceeds, otherwise the block succeeds.412 If clauses becomes satisfied, the thread unblocks, and for each satisfied clause the block fails and the thread proceeds, otherwise the block succeeds (like a semaphore where a block is a @P()@ and a satisfied clause is a @V()@). 419 413 After proceeding past the block all clauses are checked for completion and the completed clauses have their code blocks run. 414 While checking clause completion, if enough clauses have been run such that the statement predicate is satisfied, the loop exits early. 420 415 In the case where the block succeeds, the thread will be woken by the thread that marks one of the resources as available. 421 416 … … 423 418 Once the thread escapes the loop, the @select_nodes@ are unregistered from the resources. 424 419 \end{enumerate} 425 Pseudocode detailing these steps is presented in the following code block.426 420 427 421 These steps give a basic overview of how the statement works. … … 445 439 In detail, when a thread waits on multiple locks via a @waituntil@, it enqueues a @select_node@ in each of the lock's waiting queues. 446 440 When a @select_node@ reaches the front of the lock's queue and gains ownership, the thread blocked on the @waituntil@ is unblocked. 447 Now, the lock is temporarily held by the @waituntil@ thread until the node is unregistered, versus the thread waiting on the lock 441 Now, the lock is temporarily held by the @waituntil@ thread until the node is unregistered, versus the thread waiting on the lock. 448 442 To prevent the waiting thread from holding many locks at once and potentially introducing a deadlock, the node is unregistered right after the corresponding code block is executed. 449 443 This prevents deadlocks since the waiting thread will never hold a lock while waiting on another resource. … … 510 504 Not all types in a @waituntil@ have an internal lock, and when using non-channel types acquiring all the locks incurs extra unneeded overhead. 511 505 Instead this race is consolidated in \CFA in two phases by having an intermediate pending status value for the race. 512 This race case is detectable, and if detected the thread attempting to signal will first race to set therace flag to be pending.506 This race case is detectable, and if detected, producer will first race to set its own race flag to be pending. 513 507 If it succeeds, it then attempts to set the consumer's race flag to its success value. 514 508 If the producer successfully sets the consumer race flag, then the operation can proceed, if not the signalling thread will set its own race flag back to the initial value. … … 518 512 Channels in \CFA have exception based shutdown mechanisms that the @waituntil@ statement needs to support. 519 513 These exception mechanisms were what brought in the @on_selected@ routine. 520 This routine is needed by channels to detect if they are closed upon waking from a @waituntil@ statement, to ensure that the appropriate behaviour is taken .514 This routine is needed by channels to detect if they are closed upon waking from a @waituntil@ statement, to ensure that the appropriate behaviour is taken and an exception is thrown. 521 515 522 516 \subsection{Guards and Statement Predicate}\label{s:wu_guards}
Note: See TracChangeset
for help on using the changeset viewer.