Context Navigation

-                      r1260224
+                      r3e8dacc
 } // delete 4 kernel threads
 \end{cfa}
 Dynamically allocated processors can be deleted an any time, \ie their lifetime exceeds the block of creation.
+Dynamically allocated processors can be deleted at any time, \ie their lifetime exceeds the block of creation.
 The consequence is that the scheduler and \io subsystems must know when these \procs come in and out of existence and roll them into the appropriate scheduling algorithms.
 \section{Manual Resizing}
 Manual resizing is expected to be a rare operation.
 Programmers normally create/delete processors on a clusters at startup/teardown.
+Programmers normally create/delete processors on a cluster at startup/teardown.
 Therefore, dynamically changing the number of \procs is an appropriate moment to allocate or free resources to match the new state.
 As such, all internal scheduling arrays that are sized based on the number of \procs need to be @realloc@ed.
 This requirement also means any references into these arrays, \eg pointers or indexes, may need to be updated if elements are moved for compaction or for any other reason.
+This requirement also means any references into these arrays, \eg pointers or indexes, may need to be updated if elements are moved for compaction or any other reason.
 There are no performance requirements, within reason, for resizing since it is expected to be rare.
 However, this operation has strict correctness requirements since updating and idle sleep can easily lead to deadlocks.
 It should also avoid as much as possible any effect on performance when the number of \procs remain constant.
+It should also avoid as much as possible any effect on performance when the number of \procs remains constant.
 This later requirement prohibits naive solutions, like simply adding a global lock to the ready-queue arrays.
 \subsection{Read-Copy-Update}
 One solution is to use the Read-Copy-Update pattern~\cite{wiki:rcu}.
 In this pattern, resizing is done by creating a copy of the internal data structures, \eg see Figure~\ref{fig:base-ts2}, updating the copy with the desired changes, and then attempt an Indiana Jones Switch to replace the original with the copy.
+In this pattern, resizing is done by creating a copy of the internal data structures, \eg see Figure~\ref{fig:base-ts2}, updating the copy with the desired changes, and then attempting an Indiana Jones Switch to replace the original with the copy.
 This approach has the advantage that it may not need any synchronization to do the switch.
 However, there is a race where \procs still use the original data structure after the copy is switched.
 This race not only requires adding a memory-reclamation scheme, it also requires that operations made on the stale original version are eventually moved to the copy.
+This race not only requires adding a memory-reclamation scheme, but it also requires that operations made on the stale original version are eventually moved to the copy.
 Specifically, the original data structure must be kept until all \procs have witnessed the change.
 …
 If all operations need synchronization, then the overall cost of this technique is likely to be similar to an uncontended lock approach.
 In addition to the classic challenge of memory reclamation, transferring the original data to the copy before reclaiming it poses additional challenges.
 Especially merging subqueues while having a minimal impact on fairness and locality.
 For example, given a linked-list, having a node enqueued onto the original and new list is not necessarily a problem depending on the chosen list structure.
+Especially merging sub-queues while having a minimal impact on fairness and locality.
+For example, given a linked list, having a node enqueued onto the original and new list is not necessarily a problem depending on the chosen list structure.
 If the list supports arbitrary insertions, then inconsistencies in the tail pointer do not break the list;
 however, ordering may not be preserved.
 …
 To maximize reader scalability, readers should not contend with each other when attempting to acquire and release a critical section.
 To achieve this goal requires each reader to have its own memory to mark as locked and unlocked.
 The read acquire possibly waits for a writer to finish the critical section and then acquires a reader's local spinlock.
 The write acquires the global lock, guaranteeing mutual exclusion among writers, and then acquires each of the local reader locks.
+Achieving this goal requires that each reader have its own memory to mark as locked and unlocked.
+The read-acquire possibly waits for a writer to finish the critical section and then acquires a reader's local spinlock.
+The writer acquires the global lock, guaranteeing mutual exclusion among writers, and then acquires each of the local reader locks.
 Acquiring all the local read locks guarantees mutual exclusion among the readers and the writer, while the wait on the read side prevents readers from continuously starving the writer.
 Figure~\ref{f:SpecializedReadersWriterLock} shows the outline for this specialized readers-writer lock.
 The lock in nonblocking, so both readers and writers spin while the lock is held.
 This very wide sharding strategy means that readers have very good locality, since they only ever need to access two memory location.
+This very wide sharding strategy means that readers have very good locality since they only ever need to access two memory locations.
 \begin{figure}
 …
 \section{Idle-Sleep}\label{idlesleep}
 While manual resizing of \procs is expected to be rare, the number of \ats can vary significantly over an application's lifetime, which means there are times when there are too few or too many \procs.
 For this work, it is the programer's responsibility to manually create \procs, so if there are too few \procs, the application must address this issue.
+For this work, it is the programmer's responsibility to manually create \procs, so if there are too few \procs, the application must address this issue.
 This leaves too many \procs when there are not enough \ats for all the \procs to be useful.
 These idle \procs cannot be removed because their lifetime is controlled by the application, and only the application knows when the number of \ats may increase or decrease.
 …
 An interesting sub-part of this heuristic is what to do with bursts of \ats that become ready.
 Since waking up a sleeping \proc can have notable latency, it is possible multiple \ats become ready while a single \proc is waking up.
 This facts begs the question, if many \procs are available, how many should be woken?
 If the ready \ats will run longer than the wake-up latency, waking one \proc per \at will offer maximum parallelisation.
+Since waking up a sleeping \proc can have notable latency, multiple \ats may become ready while a single \proc is waking up.
+This fact begs the question, if many \procs are available, how many should be woken?
+If the ready \ats will run longer than the wake-up latency, waking one \proc per \at will offer maximum parallelization.
 If the ready \ats will run for a short very short time, waking many \procs may be wasteful.
 As mentioned, a heuristic to handle these complex cases is outside the scope of this thesis, the behaviour of the scheduler in this particular case is left unspecified.
 \section{Sleeping}
 As usual, the corner-stone of any feature related to the kernel is the choice of system call.
+As usual, the cornerstone of any feature related to the kernel is the choice of system call.
 In terms of blocking a \gls{kthrd} until some event occurs, the Linux kernel has many available options.
 …
 The classic option is to use some combination of the pthread mutual exclusion and synchronization locks, allowing a safe \park/\unpark of a \gls{kthrd} to/from a @pthread_cond@.
 While this approach works for \glspl{kthrd} waiting among themselves, \io operations do not provide a mechanism to signal @pthread_cond@s.
 For \io results to wake a \proc waiting on a @pthread_cond@ means a different \glspl{kthrd} must be woken up first, which then signals the \proc.
+For \io results to wake a \proc waiting on a @pthread_cond@ means a different \gls{kthrd} must be woken up first, which then signals the \proc.
 \subsection{\lstinline{io_uring} and Epoll}
 …
 Another interesting approach is to use an event file descriptor\cite{MAN:eventfd}.
 This Linux feature is a file descriptor that behaves like \io, \ie, uses @read@ and @write@, but also behaves like a semaphore.
 Indeed, all reads and writes must use a word-sized values, \ie 64 or 32 bits.
 Writes \emph{add} their values to a buffer using arithmetic addition versus buffer append, and reads zero out the buffer and return the buffer values so far.\footnote{
+Indeed, all reads and writes must use word-sized values, \ie 64 or 32 bits.
+Writes \emph{add} their values to a buffer using arithmetic addition versus buffer append, and reads zero-out the buffer and return the buffer values so far.\footnote{
 This behaviour is without the \lstinline{EFD_SEMAPHORE} flag, which changes the behaviour of \lstinline{read} but is not needed for this work.}
 If a read is made while the buffer is already 0, the read blocks until a non-0 value is added.
 …
 \section{Tracking Sleepers}
 Tracking which \procs are in idle sleep requires a data structure holding all the sleeping \procs, but more importantly it requires a concurrent \emph{handshake} so that no \at is stranded on a ready-queue with no active \proc.
+Tracking which \procs are in idle sleep requires a data structure holding all the sleeping \procs, but more importantly, it requires a concurrent \emph{handshake} so that no \at is stranded on a ready queue with no active \proc.
 The classic challenge occurs when a \at is made ready while a \proc is going to sleep: there is a race where the new \at may not see the sleeping \proc and the sleeping \proc may not see the ready \at.
 Since \ats can be made ready by timers, \io operations, or other events outside a cluster, this race can occur even if the \proc going to sleep is the only \proc awake.
 …
 The handshake closing the race is done with both the notifier and the idle \proc executing two ordered steps.
 The notifier first make sure the newly ready \at is visible to \procs searching for \ats, and then attempt to notify an idle \proc.
+The notifier first makes sure the newly ready \at is visible to \procs searching for \ats, and then attempts to notify an idle \proc.
 On the other side, \procs make themselves visible as idle \procs and then search for any \ats they may have missed.
 Unlike regular work-stealing, this search must be exhaustive to make sure that pre-existing \at is missed.
 These steps from both sides guarantee that if the search misses a newly ready \at, then the notifier is guaranteed to see at least one idle \proc.
 Conversly, if the notifier does not see any idle \proc, then a \proc is guaranteed to find the new \at in its exhaustive search.
+Conversely, if the notifier does not see any idle \proc, then a \proc is guaranteed to find the new \at in its exhaustive search.
 Furthermore, the ``Race-to-Idle'' approach means that there may be contention on the data structure tracking sleepers.
 Contention can be tolerated for \procs attempting to sleep or wake-up because these \procs are not doing useful work, and therefore, not contributing to overall performance.
+Contention can be tolerated for \procs attempting to sleep or wake up because these \procs are not doing useful work, and therefore, not contributing to overall performance.
 However, notifying, checking if a \proc must be woken-up, and doing so if needed, can significantly affect overall performance and must be low cost.
 \subsection{Sleepers List}
 Each cluster maintains a list of idle \procs, organized as a stack.
 This ordering allows \procs at the tail to stay in idle sleep for extended period of times while those at the head of the list wake-up for bursts of activity.
+This ordering allows \procs at the tail to stay in idle sleep for extended periods while those at the head of the list wake up for bursts of activity.
 Because of unbalanced performance requirements, the algorithm tracking sleepers is designed to have idle \procs handle as much of the work as possible.
 The idle \procs maintain the stack of sleepers among themselves and notifying a sleeping \proc takes as little work as possible.
 …
 This approach also simplifies notification.
 Indeed, \procs not only need to be notify when a new \at is readied, but also must be notified during manual resizing, so the \gls{kthrd} can be joined.
+Indeed, \procs not only need to be notified when a new \at is readied, but also must be notified during manual resizing, so the \gls{kthrd} can be joined.
 These requirements mean whichever entity removes idle \procs from the sleeper list must be able to do so in any order.
 Using a simple lock over this data structure makes the removal much simpler than using a lock-free data structure.
 The single lock also means the notification process simply needs to wake-up the desired idle \proc, using @pthread_cond_signal@, @write@ on an @fd@, \etc, and the \proc handles the rest.
+The single lock also means the notification process simply needs to wake up the desired idle \proc, using @pthread_cond_signal@, @write@ on an @fd@, \etc, and the \proc handles the rest.
 \subsection{Reducing Latency}
 As mentioned in this section, \procs going to sleep for extremely short periods of time is likely in certain scenarios.
 Therefore, the latency of doing a system call to read from and writing to an event @fd@ can negatively affect overall performance in a notable way.
+As mentioned in this section, \procs going to sleep for extremely short periods is likely in certain scenarios.
+Therefore, the latency of doing a system call to read from and write to an event @fd@ can negatively affect overall performance notably.
 Hence, it is important to reduce latency and contention of the notification as much as possible.
 Figure~\ref{fig:idle1} shows the basic idle-sleep data structure.
 …
 The woken \proc then updates the atomic pointer, while it is updating the head of the list, as it removes itself from the list.
 Notifiers that obtained a @NULL@ in the exchange simply move on knowing that another notifier is already waking a \proc.
 This behaviour is equivalent to having multiple notifier write to the @fd@ since reads consume all previous writes.
 Note 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.
+This behaviour is equivalent to having multiple notifiers write to the @fd@ since reads consume all previous writes.
+Note 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 with the latency of \procs waking up.
 As mentioned in section~\ref{idlesleep}, there is no optimal approach to handle these bursts.
 It is therefore difficult to justify the cost of any extra synchronization here.
 …
 The next optimization is to avoid the latency of the event @fd@, which can be done by adding what is effectively a binary benaphore\cite{schillings1996engineering} in front of the event @fd@.
 The 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}.
 A \proc begins its idle sleep by adding itself to the idle list before searching for an \at.
+The benaphore over the event @fd@ logically provides a three-state flag to avoid unnecessary system calls, where the states are expressed explicitly in Figure~\ref{fig:idle:state}.
+A \proc begins its idle sleep by adding itself to the idle list before searching for a \at.
 In the process of adding itself to the idle list, it sets the state flag to @SEARCH@.
 If no \ats can be found during the search, the \proc then confirms it is going to sleep by atomically swapping the state to @SLEEP@.
 If the previous state is still @SEARCH@, then the \proc does read the event @fd@.
 Meanwhile, notifiers atomically exchange the state to @AWAKE@ state.
+Meanwhile, notifiers atomically exchange the state to the @AWAKE@ state.
 If the previous state is @SLEEP@, then the notifier must write to the event @fd@.
 However, if the notify arrives almost immediately after the \proc marks itself idle, then both reads and writes on the event @fd@ can be omitted, which reduces latency notably.
 These extensions leads to the final data structure shown in Figure~\ref{fig:idle}.
+These extensions lead to the final data structure shown in Figure~\ref{fig:idle}.
 \begin{figure}
         \centering
         \input{idle_state.pstex_t}
         \caption[Improved Idle-Sleep Latency]{Improved Idle-Sleep Latency \smallskip\newline A three state flag is added to the event \lstinline{fd}.}
+        \caption[Improved Idle-Sleep Latency]{Improved Idle-Sleep Latency \smallskip\newline A three-state flag is added to the event \lstinline{fd}.}
         \label{fig:idle:state}
 \end{figure}

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 3e8dacc for doc/theses

Legend:

doc/theses/thierry_delisle_PhD/thesis/text/practice.tex

Download in other formats: