Ignore:
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:
2 edited

Legend:

Unmodified
Added
Removed

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

    rd677355 r6726a3a  
    1414
    1515\section{Naming Convention}
    16 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.
     16Scheduling has been studied by various communities concentrating on different incarnation of the same problems.
     17As a result, there are no standard naming conventions for scheduling that is respected across these communities.
     18This 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.
    1719
    1820\section{Static Scheduling}
    … …  
    2628\section{Dynamic Scheduling}
    2729\newterm{Dynamic schedulers} determine \ats dependencies and costs during scheduling, if at all.
    28 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.
     30Hence, unlike static scheduling, \ats dependencies are conditional and detected at runtime.
     31This 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.
    2932Furthermore, each \ats has the responsibility of adding dependent \ats back into the system once dependencies are fulfilled.
    3033As 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

    rd677355 r6726a3a  
    11\chapter{User Level \io}
    2 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.
     2As 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.
    33Different 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.
    44
    … …  
    7272
    7373\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.
    74 (For small interest sets with densely packed FDs, the @select@ bit mask can take less storage, and hence, copy less information into the kernel.)
     74For small interest sets with densely packed FDs, the @select@ bit mask can take less storage, and hence, copy less information into the kernel.
    7575Furthermore, @poll@ is non-destructive, so the array of structures does not have to be re-initialize on every call.
    7676Like @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@.
    … …  
    277277While this example is artificial, in the presence of many \glspl{thrd}, it is possible for this problem to arise ``in the wild''.
    278278Furthermore, this pattern is difficult to reliably detect and avoid.
    279 Once in this situation, the only escape is to interrupted the spinning \gls{thrd}, either directly or via some regular preemption (\eg time slicing).
     279Once in this situation, the only escape is to interrupted the spinning \gls{thrd}, either directly or via some regular preemption, \eg time slicing.
    280280Having to interrupt \glspl{thrd} for this purpose is costly, the latency can be large between interrupts, and the situation may be hard to detect.
    281 % 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.
    282 % If it were to use it, then helping could be done as part of the usage.
    283281Interrupts are needed here entirely because the \gls{proc} is tied to an instance it is not using.
    284282Therefore, 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.
    … …  
    301299Free 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.
    302300Allocation also requires no ordering guarantee as all free SQEs are interchangeable.
    303 % This requires a simple concurrent bag.
    304301The only added complexity is that the number of SQEs is fixed, which means allocation can fail.
    305302
    … …  
    310307
    311308Once 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.
    312 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.
     309The 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.
    313310However, as mentioned, the system call itself can fail with the expectation that it can be retried once some submitted operations complete.
    314311
    … …  
    346343While instance borrowing looks similar to work sharing and stealing, I think it is different enough to warrant a different verb to avoid confusion.}
    347344
    348 In this approach, each cluster (see Figure~\ref{fig:system}) owns a pool of @io_uring@ instances managed by an \newterm{arbiter}.
     345In this approach, each cluster, see Figure~\ref{fig:system}, owns a pool of @io_uring@ instances managed by an \newterm{arbiter}.
    349346When a \gls{thrd} attempts to issue an \io operation, it ask for an instance from the arbiter and issues requests to that instance.
    350347This instance is now bound to the \gls{proc} the \gls{thrd} is running on.
    351348This 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.
    352349This 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.
    353 However, it differs in that revocation by the arbiter (an interrupt) means this approach does not suffer from the deadlock scenario described above.
     350However, it differs in that revocation by the arbiter means this approach does not suffer from the deadlock scenario described above.
    354351
    355352Arbitration is needed in the following cases:
    … …  
    377374
    378375\paragraph{External Submissions} are handled by the arbiter by revoking the appropriate instance and adding the submission to the submission ring.
    379 However,  there is no need to immediately revoke the instance.
     376However, there is no need to immediately revoke the instance.
    380377External submissions must simply be added to the ring before the next system call, \ie, when the submission ring is flushed.
    381378This means whoever is responsible for the system call, first checks if the instance has any external submissions.
    … …  
    453450
    454451\section{Interface}
    455 
    456452The last important part of the \io subsystem is its interface.
    457453There are multiple approaches that can be offered to programmers, each with advantages and disadvantages.
Note: See TracChangeset for help on using the changeset viewer.