Changeset 6726a3a for doc/theses/thierry_delisle_PhD

Timestamp:

Jul 20, 2022, 2:37:57 PM (2 years ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, ast-experimental, master, pthread-emulation, qualifiedEnum

Children:

6bf35d1, e6662f5

Parents:

d677355 (diff), 2fd0de0 (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

Location:

doc/theses/thierry_delisle_PhD/thesis/text

Files:

• existing.tex (modified) (2 diffs)
• io.tex (modified) (8 diffs)

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

@@ -14 +14 @@
 
 \section{Naming Convention}
-Scheduling has been studied by various communities concentrating on different incarnation of the same problems. As a result, there are no standard naming conventions for scheduling that is respected across these communities. This document uses the term \newterm{\Gls{at}} to refer to the abstract objects being scheduled and the term \newterm{\Gls{proc}} to refer to the concrete objects executing these \ats.
+Scheduling has been studied by various communities concentrating on different incarnation of the same problems. 
+As a result, there are no standard naming conventions for scheduling that is respected across these communities. 
+This document uses the term \newterm{\Gls{at}} to refer to the abstract objects being scheduled and the term \newterm{\Gls{proc}} to refer to the concrete objects executing these \ats.
 
 \section{Static Scheduling}
@@ -26 +28 @@
 \section{Dynamic Scheduling}
 \newterm{Dynamic schedulers} determine \ats dependencies and costs during scheduling, if at all.
-Hence, unlike static scheduling, \ats dependencies are conditional and detected at runtime. This detection takes the form of observing new \ats(s) in the system and determining dependencies from their behaviour, including suspending or halting a \ats that dynamically detects unfulfilled dependencies.
+Hence, unlike static scheduling, \ats dependencies are conditional and detected at runtime. 
+This detection takes the form of observing new \ats(s) in the system and determining dependencies from their behaviour, including suspending or halting a \ats that dynamically detects unfulfilled dependencies.
 Furthermore, each \ats has the responsibility of adding dependent \ats back into the system once dependencies are fulfilled.
 As a consequence, the scheduler often has an incomplete view of the system, seeing only \ats with no pending dependencies.

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

@@ -1 +1 @@
 \chapter{User Level \io}
-As mentioned in Section~\ref{prev:io}, user-Level \io requires multiplexing the \io operations of many \glspl{thrd} onto fewer \glspl{proc} using asynchronous \io operations.
+As mentioned in Section~\ref{prev:io}, user-level \io requires multiplexing the \io operations of many \glspl{thrd} onto fewer \glspl{proc} using asynchronous \io operations.
 Different operating systems offer various forms of asynchronous operations and, as mentioned in Chapter~\ref{intro}, this work is exclusively focused on the Linux operating-system.
 
@@ -72 +72 @@
 
 \paragraph{\lstinline{poll}} is the next oldest option, and takes as input an array of structures containing the FD numbers rather than their position in an array of bits, allowing a more compact input for interest sets that contain widely spaced FDs.
-(For small interest sets with densely packed FDs, the @select@ bit mask can take less storage, and hence, copy less information into the kernel.)
+For small interest sets with densely packed FDs, the @select@ bit mask can take less storage, and hence, copy less information into the kernel.
 Furthermore, @poll@ is non-destructive, so the array of structures does not have to be re-initialize on every call.
 Like @select@, @poll@ suffers from the limitation that the interest set cannot be changed by other \gls{kthrd}, while a manager thread is blocked in @poll@.
@@ -277 +277 @@
 While this example is artificial, in the presence of many \glspl{thrd}, it is possible for this problem to arise ``in the wild''.
 Furthermore, this pattern is difficult to reliably detect and avoid.
-Once in this situation, the only escape is to interrupted the spinning \gls{thrd}, either directly or via some regular preemption (\eg time slicing).
+Once in this situation, the only escape is to interrupted the spinning \gls{thrd}, either directly or via some regular preemption, \eg time slicing.
 Having to interrupt \glspl{thrd} for this purpose is costly, the latency can be large between interrupts, and the situation may be hard to detect.
-% However, a more important reason why interrupting the \gls{thrd} is not a satisfying solution is that the \gls{proc} is using the instance it is tied to.
-% If it were to use it, then helping could be done as part of the usage.
 Interrupts are needed here entirely because the \gls{proc} is tied to an instance it is not using.
 Therefore, a more satisfying solution is for the \gls{thrd} submitting the operation to notice that the instance is unused and simply go ahead and use it.
@@ -301 +299 @@
 Free SQEs, \ie, SQEs that are not currently being used to represent a request, can be written to safely and have a field called @user_data@ that the kernel only reads to copy to @cqe@s.
 Allocation also requires no ordering guarantee as all free SQEs are interchangeable.
-% This requires a simple concurrent bag.
 The only added complexity is that the number of SQEs is fixed, which means allocation can fail.
 
@@ -310 +307 @@
 
 Once an SQE is filled in, it is added to the submission ring buffer, an operation that is not thread-safe, and then the kernel must be notified using the @io_uring_enter@ system call.
-The submission ring buffer is the same size as the pre-allocated SQE buffer, therefore pushing to the ring buffer cannot fail because it is invalid to have the same \lstinline{sqe} multiple times in a ring buffer.
+The submission ring buffer is the same size as the pre-allocated SQE buffer, therefore pushing to the ring buffer cannot fail because it would mean a \lstinline{sqe} multiple times in the ring buffer, which is undefined behaviour.
 However, as mentioned, the system call itself can fail with the expectation that it can be retried once some submitted operations complete.
 
@@ -346 +343 @@
 While instance borrowing looks similar to work sharing and stealing, I think it is different enough to warrant a different verb to avoid confusion.}
 
-In this approach, each cluster (see Figure~\ref{fig:system}) owns a pool of @io_uring@ instances managed by an \newterm{arbiter}.
+In this approach, each cluster, see Figure~\ref{fig:system}, owns a pool of @io_uring@ instances managed by an \newterm{arbiter}.
 When a \gls{thrd} attempts to issue an \io operation, it ask for an instance from the arbiter and issues requests to that instance.
 This instance is now bound to the \gls{proc} the \gls{thrd} is running on.
 This binding is kept until the arbiter decides to revoke it, taking back the instance and reverting the \gls{proc} to its initial state with respect to \io.
 This tight coupling means that synchronization can be minimal since only one \gls{proc} can use the instance at a time, akin to the private instances approach.
-However, it differs in that revocation by the arbiter (an interrupt) means this approach does not suffer from the deadlock scenario described above.
+However, it differs in that revocation by the arbiter means this approach does not suffer from the deadlock scenario described above.
 
 Arbitration is needed in the following cases:
@@ -377 +374 @@
 
 \paragraph{External Submissions} are handled by the arbiter by revoking the appropriate instance and adding the submission to the submission ring.
-However,  there is no need to immediately revoke the instance.
+However, there is no need to immediately revoke the instance.
 External submissions must simply be added to the ring before the next system call, \ie, when the submission ring is flushed.
 This means whoever is responsible for the system call, first checks if the instance has any external submissions.
@@ -453 +450 @@
 
 \section{Interface}
-
 The last important part of the \io subsystem is its interface.
 There are multiple approaches that can be offered to programmers, each with advantages and disadvantages.