Ignore:
Timestamp:
Jul 25, 2022, 11:47:36 AM (2 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, ast-experimental, master, pthread-emulation, qualifiedEnum
Children:
8fe35be
Parents:
6a6544d (diff), 24a3d2b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/thierry_delisle_PhD/thesis/text/practice.tex

    r6a6544d r970fa54  
    199199Interestingly, general notification, \ie waking any idle processor versus a specific one, does not strictly require modifying the list.
    200200Here, contention can be reduced notably by having notifiers avoid the lock entirely by adding a pointer to the event @fd@ of the first idle \proc, as in Figure~\ref{fig:idle2}.
    201 To avoid contention among notifiers, notifiers atomically exchange it to @NULL@ so only one notifier contends on the system call.
    202 The first notifier will succeed the atomic exchange and obtain the @fd@ of an idle \proc.
    203 The notifier will the normally write to the @fd@, which will wake a \proc.
    204 The woken \proc can then update the atomic pointer while it is updating the head of the list.
    205 Notifiers that obtained a @NULL@ in the exchange simply move on, knowing that another notifier is already waking a \proc.
     201To avoid contention among notifiers, notifiers atomically exchange the pointer with @NULL@.
     202The first notifier succeeds on the exchange and obtains the @fd@ of an idle \proc;
     203hence, only one notifier contends on the system call.
     204This notifier writes to the @fd@ to wake a \proc.
     205The woken \proc then updates the atomic pointer, while it is updating the head of the list, as it removes itself from the list.
     206Notifiers that obtained a @NULL@ in the exchange simply move on knowing that another notifier is already waking a \proc.
    206207This behaviour is equivalent to having multiple notifier write to the @fd@ since reads consume all previous writes.
    207208Note that with and without this atomic pointer, bursts of notification can lead to an unspecified number of \procs being woken up, depending on how the arrival notification compares witht the latency of \procs waking up.
     
    217218
    218219The next optimization is to avoid the latency of the event @fd@, which can be done by adding what is effectively a binary benaphore\cit{benaphore} in front of the event @fd@.
    219 A simple three state flag is added beside the event @fd@ to avoid unnecessary system calls, as shown in Figure~\ref{fig:idle:state}.
     220The benaphore over the event @fd@ logically provides a three state flag to avoid unnecessary system calls, where the states are expressed explicit in Figure~\ref{fig:idle:state}.
    220221A \proc begins its idle sleep by adding itself to the idle list before searching for an \at.
    221222In the process of adding itself to the idle list, it sets the state flag to @SEARCH@.
Note: See TracChangeset for help on using the changeset viewer.