Changes in / [878be178:62c5a55]


Ignore:
Location:
doc/theses/thierry_delisle_PhD/thesis
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/thierry_delisle_PhD/thesis/local.bib

    r878be178 r62c5a55  
    429429}
    430430
     431@inproceedings{Albers12,
     432    author      = {Susanne Albers and Antonios Antoniadis},
     433    title       = {Race to Idle: New Algorithms for Speed Scaling with a Sleep State},
     434    booktitle   = {Proceedings of the 2012  Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
     435    doi         = {10.1137/1.9781611973099.100},
     436    URL         = {https://epubs.siam.org/doi/abs/10.1137/1.9781611973099.100},
     437    eprint      = {https://epubs.siam.org/doi/pdf/10.1137/1.9781611973099.100},
     438    year        = 2012,
     439    month       = jan,
     440    pages       = {1266-1285},
     441}
     442
     443@inproceedings{atikoglu2012workload,
     444  title={Workload analysis of a large-scale key-value store},
     445  author={Atikoglu, Berk and Xu, Yuehai and Frachtenberg, Eitan and Jiang, Song and Paleczny, Mike},
     446  booktitle={Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems},
     447  pages={53--64},
     448  year={2012}
     449}
     450
     451@article{schillings1996engineering,
     452  title={Be engineering insights: Benaphores},
     453  author={Schillings, Benoit},
     454  journal={Be Newsletters},
     455  volume={1},
     456  number={26},
     457  year={1996}
     458}
     459
     460
     461
    431462% --------------------------------------------------
    432463% ULE FreeBSD scheduler
     
    582613}
    583614
     615@misc{apache,
     616  key = {Apache Software Foundation},
     617  title = {{T}he {A}pache Web Server},
     618  howpublished = {\href{http://httpd.apache.org}{http://\-httpd.apache.org}},
     619  note = "[Online; accessed 6-June-2022]"
     620}
     621
     622@misc{memcached,
     623  key = {Brad Fitzpatrick},
     624  title = {{M}emcached},
     625  year = {2003},
     626  howpublished = {\href{http://httpd.apache.org}{http://\-httpd.apache.org}},
     627  note = "[Online; accessed 6-June-2022]"
     628}
     629
     630@misc{libuv,
     631  author = {libuv team},
     632  title = {libuv: Asynchronous I/O made simple.},
     633  howpublished = {\href{https://libuv.org/}{https://\-libuv.org/}},
     634  note = "[Online; accessed 5-August-2022]"
     635}
     636
     637@misc{SeriallyReusable,
     638    author      = {IBM},
     639    title       = {Serially reusable programs},
     640    month       = mar,
     641    howpublished= {\href{https://www.ibm.com/docs/en/ztpf/1.1.0.15?topic=structures-serially-reusable-programs}{https://www.ibm.com/\-docs/\-en/\-ztpf/\-1.1.0.15?\-topic=structures\--serially\--reusable-programs}},
     642    year        = 2021,
     643}
     644
     645@misc{GITHUB:mutilate,
     646  title = {Mutilate: high-performance memcached load generator },
     647  author = { Jacob Leverich },
     648  howpublished = {\href{https://github.com/leverich/mutilate}{https://\-github.com/\-leverich/\-mutilate}},
     649  version = {Change-Id: d65c6ef7c2f78ae05a9db3e37d7f6ddff1c0af64}
     650}
     651
     652% --------------------------------------------------
     653% Tech documents
     654@techreport{rfc:tcp,
     655  title={Transmission control protocol},
     656  author={Postel, Jon},
     657  year={1981}
     658}
     659
     660@manual{win:priority,
     661  key = {TaskSettings Priority},
     662  title = {TaskSettings.Priority property},
     663  year = "2020",
     664  month = "September",
     665  howpublished = {\href{https://docs.microsoft.com/en-us/windows/win32/taskschd/tasksettings-priority}{https://\-docs.microsoft.com/\-en-us/\-windows/\-win32/\-taskschd/\-tasksettings-priority}},
     666  note = "[Online; accessed 5-August-2022]"
     667}
     668
     669@manual{win:overlap,
     670  key = {Synchronous and Asynchronous IO},
     671  title = {Synchronous and Asynchronous I\/O},
     672  year = "2021",
     673  month = "March",
     674  howpublished = {\href{https://docs.microsoft.com/en-us/windows/win32/fileio/synchronous-and-asynchronous-i-o}{https://\-docs.microsoft.com/\-en-us/\-windows/\-win32/\-fileio/\-synchronous-and-asynchronous-i-o}},
     675  note = "[Online; accessed 5-August-2022]"
     676}
     677
     678@book{russinovich2009windows,
     679  title={Windows Internals},
     680  author={Russinovich, M.E. and Solomon, D.A. and Ionescu, A.},
     681  isbn={9780735625303},
     682  lccn={2009927697},
     683  series={Developer Reference Series},
     684  url={https://books.google.ca/books?id=SfglSQAACAAJ},
     685  year={2009},
     686  publisher={Microsoft Press}
     687}
     688
     689@manual{apple:gcd,
     690  key = {Grand Central Dispatch},
     691  title = {Grand Central Dispatch},
     692  year = "2022",
     693  author = {Apple Inc.},
     694  howpublished = {https://developer.apple.com/documentation/DISPATCH},
     695  note = "[Online; accessed 5-August-2022]"
     696}
     697
     698@techreport{apple:gcd2,
     699  key = {Grand Central Dispatch},
     700  title = {Grand Central Dispatch, A better way to do multicore.},
     701  year = "2009",
     702  month = "August",
     703  author = {Apple Inc.},
     704  howpublished = {\href{http://web.archive.org/web/20090920043909/http://images.apple.com/macosx/technology/docs/GrandCentral_TB_brief_20090903.pdf}{http://web.archive.org/web/20090920043909/http://\-images.apple.com/\-macosx/\-technology/\-docs/\-GrandCentral\_TB\_brief\_20090903.pdf}},
     705  note = "[Online; accessed 5-August-2022]"
     706}
     707
     708
    584709% --------------------------------------------------
    585710% Man Pages
     
    617742  year       = "2019",
    618743  month      = "March",
     744}
     745
     746@manual{MAN:sendfile,
     747  key        = "sendfile",
     748  title      = "sendfile(2) Linux User's Manual",
     749  year       = "2017",
     750  month      = "September",
     751}
     752
     753@manual{MAN:splice,
     754  key        = "splice",
     755  title      = "splice(2) Linux User's Manual",
     756  year       = "2019",
     757  month      = "May",
    619758}
    620759
     
    709848}
    710849
    711 % RMR notes :
    712 % [05/04, 12:36] Trevor Brown
    713 %     i don't know where rmr complexity was first introduced, but there are many many many papers that use the term and define it
    714 % [05/04, 12:37] Trevor Brown
    715 %     here's one paper that uses the term a lot and links to many others that use it... might trace it to something useful there https://drops.dagstuhl.de/opus/volltexte/2021/14832/pdf/LIPIcs-DISC-2021-30.pdf
    716 % [05/04, 12:37] Trevor Brown
    717 %     another option might be to cite a textbook
    718 % [05/04, 12:42] Trevor Brown
    719 %     but i checked two textbooks in the area i'm aware of and i don't see a definition of rmr complexity in either
    720 % [05/04, 12:42] Trevor Brown
    721 %     this one has a nice statement about the prevelance of rmr complexity, as well as some rough definition
    722 % [05/04, 12:42] Trevor Brown
    723 %     https://dl.acm.org/doi/pdf/10.1145/3465084.3467938
    724 
    725 % Race to idle notes :
    726 % [13/04, 16:56] Martin Karsten
    727 %       I don't have a citation. Google brings up this one, which might be good:
    728 %
    729 % https://doi.org/10.1137/1.9781611973099.100
    730 
    731 
     850@misc{wiki:ma,
     851  author = "{Wikipedia contributors}",
     852  title = "Bin packing problem --- {W}ikipedia{,} The Free Encyclopedia",
     853  year = "2022",
     854  howpublished = "\href{https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average}{https://\-en.wikipedia.org/\-wiki/\-Moving\_average\#Exponential\_moving\_average}",
     855  note = "[Online; accessed 5-August-2022]"
     856}
     857
     858@misc{wiki:jni,
     859  author = "{Wikipedia contributors}",
     860  title = "Java Native Interface --- {W}ikipedia{,} The Free Encyclopedia",
     861  year = "2021",
     862  howpublished = "\href{https://en.wikipedia.org/wiki/Java_Native_Interface}{https://\-en.wikipedia.org/\-wiki/\-Java\_Native\_Interface}",
     863  note = "[Online; accessed 5-August-2022]"
     864}
     865
     866% --------------------------------------------------
     867% True Misc
    732868@misc{AIORant,
    733869  author = "Linus Torvalds",
     
    739875}
    740876
    741 @misc{apache,
    742   key = {Apache Software Foundation},
    743   title = {{T}he {A}pache Web Server},
    744   howpublished = {\href{http://httpd.apache.org}{http://\-httpd.apache.org}},
    745   note = "[Online; accessed 6-June-2022]"
    746 }
    747 
    748 @misc{SeriallyReusable,
    749     author      = {IBM},
    750     title       = {Serially reusable programs},
    751     month       = mar,
    752     howpublished= {\href{https://www.ibm.com/docs/en/ztpf/1.1.0.15?topic=structures-serially-reusable-programs}{https://www.ibm.com/\-docs/\-en/\-ztpf/\-1.1.0.15?\-topic=structures\--serially\--reusable-programs}},
    753     year        = 2021,
    754 }
    755 
    756 @inproceedings{Albers12,
    757     author      = {Susanne Albers and Antonios Antoniadis},
    758     title       = {Race to Idle: New Algorithms for Speed Scaling with a Sleep State},
    759     booktitle   = {Proceedings of the 2012  Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
    760     doi         = {10.1137/1.9781611973099.100},
    761     URL         = {https://epubs.siam.org/doi/abs/10.1137/1.9781611973099.100},
    762     eprint      = {https://epubs.siam.org/doi/pdf/10.1137/1.9781611973099.100},
    763     year        = 2012,
    764     month       = jan,
    765     pages       = {1266-1285},
    766 }
     877@misc{xkcd:dynamicentropy,
     878  author = "Randall Munroe",
     879  title = "2318: Dynamic Entropy",
     880  year = "2020",
     881  month = "June",
     882  howpublished = "\href{https://xkcd.com/2318/}",
     883  note = "[Online; accessed 10-June-2020]"
     884}
     885
     886@misc{go:safepoints,
     887  author = "The Go Programming Language",
     888  title = "src/runtime/preempt.go",
     889  howpublished = {\href{https://go.dev/src/runtime/preempt.go}},
     890  note = "[Online; accessed 5-August-2022]"
     891}
     892
     893@misc{go:cgo,
     894  author = "The Go Programming Language",
     895  title = "cgo",
     896  howpublished = {\href{https://pkg.go.dev/cmd/cgo}},
     897  note = "[Online; accessed 5-August-2022]"
     898}
  • doc/theses/thierry_delisle_PhD/thesis/text/core.tex

    r878be178 r62c5a55  
    1515For threading, a simple and common execution mental-model is the ``Ideal multi-tasking CPU'' :
    1616
    17 \begin{displayquote}[Linux CFS\cit{https://www.kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt}]
     17\begin{displayquote}[Linux CFS\cite{MAN:linux/cfs}]
    1818        {[The]} ``Ideal multi-tasking CPU'' is a (non-existent  :-)) CPU that has 100\% physical power and which can run each task at precise equal speed, in parallel, each at [an equal fraction of the] speed.  For example: if there are 2 tasks running, then it runs each at 50\% physical power --- i.e., actually in parallel.
    1919        \label{q:LinuxCFS}
     
    183183This suggests to the following approach:
    184184
    185 \subsection{Dynamic Entropy}\cit{https://xkcd.com/2318/}
     185\subsection{Dynamic Entropy}\cite{xkcd:dynamicentropy}
    186186The Relaxed-FIFO approach can be made to handle the case of mostly empty subqueues by tweaking the \glsxtrlong{prng}.
    187187The \glsxtrshort{prng} state can be seen as containing a list of all the future subqueues that will be accessed.
    188188While this concept is not particularly useful on its own, the consequence is that if the \glsxtrshort{prng} algorithm can be run \emph{backwards}, then the state also contains a list of all the subqueues that were accessed.
    189 Luckily, bidirectional \glsxtrshort{prng} algorithms do exist, \eg some Linear Congruential Generators\cit{https://en.wikipedia.org/wiki/Linear\_congruential\_generator} support running the algorithm backwards while offering good quality and performance.
     189Luckily, bidirectional \glsxtrshort{prng} algorithms do exist, \eg some Linear Congruential Generators\cite{wiki:lcg} support running the algorithm backwards while offering good quality and performance.
    190190This particular \glsxtrshort{prng} can be used as follows:
    191191\begin{itemize}
     
    220220        \input{base.pstex_t}
    221221        \caption[Base \CFA design]{Base \CFA design \smallskip\newline A pool of subqueues offers the sharding, two per \glspl{proc}.
    222         Each \gls{proc} can access all of the subqueues. 
     222        Each \gls{proc} can access all of the subqueues.
    223223        Each \at is timestamped when enqueued.}
    224224        \label{fig:base}
     
    245245\end{figure}
    246246
    247 A simple solution to this problem is to use an exponential moving average\cit{https://en.wikipedia.org/wiki/Moving\_average\#Exponential\_moving\_average} (MA) instead of a raw timestamps, shown in Figure~\ref{fig:base-ma}.
     247A simple solution to this problem is to use an exponential moving average\cite{wiki:ma} (MA) instead of a raw timestamps, shown in Figure~\ref{fig:base-ma}.
    248248Note, this is more complex because the \at at the head of a subqueue is still waiting, so its wait time has not ended.
    249249Therefore, the exponential moving average is actually an exponential moving average of how long each dequeued \at has waited.
  • doc/theses/thierry_delisle_PhD/thesis/text/eval_macro.tex

    r878be178 r62c5a55  
    1010
    1111\section{Memcached}
    12 Memcached~\cit{memcached} is an in memory key-value store that is used in many production environments, \eg \cit{Berk Atikoglu et al., Workload Analysis of a Large-Scale Key-Value Store,
    13 SIGMETRICS 2012}.
    14 This also server also has the notable added benefit that there exists a full-featured front-end for performance testing called @mutilate@~\cit{mutilate}.
     12Memcached~\cite{memcached} is an in memory key-value store that is used in many production environments, \eg \cite{atikoglu2012workload}.
     13This also server also has the notable added benefit that there exists a full-featured front-end for performance testing called @mutilate@~\cite{GITHUB:mutilate}.
    1514Experimenting on memcached allows for a simple test of the \CFA runtime as a whole, it will exercise the scheduler, the idle-sleep mechanism, as well the \io subsystem for sockets.
    1615This experiment does not exercise the \io subsytem with regards to disk operations.
     
    9897Most of the implementation is fairly straight forward however the inclusion of file \io introduces a new challenge that had to be hacked around.
    9998
    100 Normally, webservers use @sendfile@\cit{sendfile} to send files over the socket.
    101 @io_uring@ does not support @sendfile@, it supports @splice@\cit{splice} instead, which is strictly more powerful.
     99Normally, webservers use @sendfile@\cite{MAN:sendfile} to send files over the socket.
     100@io_uring@ does not support @sendfile@, it supports @splice@\cite{splice} instead, which is strictly more powerful.
    102101However, because of how linux implements file \io, see Subsection~\ref{ononblock}, @io_uring@'s implementation must delegate calls to splice to worker threads inside the kernel.
    103102As of Linux 5.13, @io_uring@ caps the numer of these worker threads to @RLIMIT_NPROC@ and therefore, when tens of thousands of splice requests are made, it can create tens of thousands of \glspl{kthrd}.
     
    108107When the saturation point of the server is attained, latency will increase and inevitably some client connections will timeout.
    109108As these clients close there connections, the server must close these sockets without delay so the OS can reclaim the resources used by these connections.
    110 Indeed, until they are closed on the server end, the connection will linger in the CLOSE-WAIT tcp state~\cit{RFC793} and the tcp buffers will be preserved.
     109Indeed, until they are closed on the server end, the connection will linger in the CLOSE-WAIT tcp state~\cite{rfc:tcp} and the tcp buffers will be preserved.
    111110However, this poses a problem using blocking @sendfile@ calls.
    112111The calls can block if they do not have suffcient memory, which can be caused by having too many connections in the CLOSE-WAIT state.
  • doc/theses/thierry_delisle_PhD/thesis/text/existing.tex

    r878be178 r62c5a55  
    1414
    1515\section{Naming Convention}
    16 Scheduling has been studied by various communities concentrating on different incarnation of the same problems. 
    17 As a result, there are no standard naming conventions for scheduling that is respected across these communities. 
     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.
    1818This 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.
    1919
     
    2828\section{Dynamic Scheduling}
    2929\newterm{Dynamic schedulers} determine \ats dependencies and costs during scheduling, if at all.
    30 Hence, unlike static scheduling, \ats dependencies are conditional and detected at runtime. 
     30Hence, unlike static scheduling, \ats dependencies are conditional and detected at runtime.
    3131This 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.
    3232Furthermore, each \ats has the responsibility of adding dependent \ats back into the system once dependencies are fulfilled.
     
    5151Most common operating systems use some variant on priorities with overlaps and dynamic priority adjustments.
    5252For example, Microsoft Windows uses a pair of priorities
    53 \cit{https://docs.microsoft.com/en-us/windows/win32/procthread/scheduling-priorities,https://docs.microsoft.com/en-us/windows/win32/taskschd/taskschedulerschema-priority-settingstype-element}, one specified by users out of ten possible options and one adjusted by the system.
     53\cite{win:priority}, one specified by users out of ten possible options and one adjusted by the system.
    5454
    5555\subsection{Uninformed and Self-Informed Dynamic Schedulers}
     
    137137The scheduler may also temporarily adjust priorities after certain effects like the completion of I/O requests.
    138138
    139 \todo{load balancing}
     139In~\cite{russinovich2009windows}, Chapter 1 section ``Processes, Threads, and Jobs'' discusses the scheduling policy more in depth.
     140Multicore scheduling is based on a combination of priorities, preferred \proc.
     141Each \at is assigned an \newterm{ideal} \proc using a round-robin policy.
     142\Ats are distributed among the \procs according to their priority, preferring to match \ats to their ideal \proc and then to the last \proc they ran on.
     143This is similar to a variation of work stealing, where the stealing \proc restore the \at to its original \proc after running it, but with priorities added onto the mix.
    140144
    141145\paragraph{Apple OS X}
     
    156160\paragraph{Go}\label{GoSafePoint}
    157161Go's scheduler uses a randomized work-stealing algorithm that has a global run-queue (\emph{GRQ}) and each processor (\emph{P}) has both a fixed-size run-queue (\emph{LRQ}) and a high-priority next ``chair'' holding a single element~\cite{GITHUB:go,YTUBE:go}.
    158 Preemption is present, but only at safe-points,~\cit{https://go.dev/src/runtime/preempt.go} which are inserted detection code at various frequent access boundaries.
     162Preemption is present, but only at safe-points,~\cite{go:safepoints} which are inserted detection code at various frequent access boundaries.
    159163
    160164The algorithm is as follows :
     
    199203
    200204\paragraph{Grand Central Dispatch}
    201 An Apple\cit{Official GCD source} API that offers task parallelism~\cite{wiki:taskparallel}.
     205An Apple\cite{apple:gcd} API that offers task parallelism~\cite{wiki:taskparallel}.
    202206Its distinctive aspect is multiple ``Dispatch Queues'', some of which are created by programmers.
    203207Each queue has its own local ordering guarantees, \eg \ats on queue $A$ are executed in \emph{FIFO} order.
    204208
    205 \todo{load balancing and scheduling}
    206 
    207 % http://web.archive.org/web/20090920043909/http://images.apple.com/macosx/technology/docs/GrandCentral_TB_brief_20090903.pdf
    208 
    209 In terms of semantics, the Dispatch Queues seem to be very similar to Intel\textregistered ~TBB @execute()@ and predecessor semantics.
     209While the documentation only gives limited insight into the scheduling and load balancing approach, \cite{apple:gcd2} suggests an approach fairly classic;
     210Where each \proc has a queue of \newterm{blocks} to run, effectively \ats, and they drain their respective queues in \glsxtrshort{fifo}.
     211They seem to add the concept of dependent queues with clear ordering, where a executing a block ends-up scheduling more blocks.
     212In terms of semantics, these Dispatch Queues seem to be very similar to Intel\textregistered ~TBB @execute()@ and predecessor semantics.
    210213
    211214\paragraph{LibFibre}
  • doc/theses/thierry_delisle_PhD/thesis/text/io.tex

    r878be178 r62c5a55  
    141141In the worst case, where all \glspl{thrd} are consistently blocking on \io, it devolves into 1-to-1 threading.
    142142However, regardless of the frequency of \io operations, it achieves the fundamental goal of not blocking \glspl{proc} when \glspl{thrd} are ready to run.
    143 This approach is used by languages like Go\cit{Go}, frameworks like libuv\cit{libuv}, and web servers like Apache~\cite{apache} and Nginx~\cite{nginx}, since it has the advantage that it can easily be used across multiple operating systems.
     143This approach is used by languages like Go\cite{GITHUB:go}, frameworks like libuv\cite{libuv}, and web servers like Apache~\cite{apache} and Nginx~\cite{nginx}, since it has the advantage that it can easily be used across multiple operating systems.
    144144This advantage is especially relevant for languages like Go, which offer a homogeneous \glsxtrshort{api} across all platforms.
    145145As opposed to C, which has a very limited standard api for \io, \eg, the C standard library has no networking.
     
    148148These options effectively fall into two broad camps: waiting for \io to be ready versus waiting for \io to complete.
    149149All operating systems that support asynchronous \io must offer an interface along one of these lines, but the details vary drastically.
    150 For example, Free BSD offers @kqueue@~\cite{MAN:bsd/kqueue}, which behaves similarly to @epoll@, but with some small quality of use improvements, while Windows (Win32)~\cit{https://docs.microsoft.com/en-us/windows/win32/fileio/synchronous-and-asynchronous-i-o} offers ``overlapped I/O'', which handles submissions similarly to @O_NONBLOCK@ with extra flags on the synchronous system call, but waits for completion events, similarly to @io_uring@.
     150For example, Free BSD offers @kqueue@~\cite{MAN:bsd/kqueue}, which behaves similarly to @epoll@, but with some small quality of use improvements, while Windows (Win32)~\cite{win:overlap} offers ``overlapped I/O'', which handles submissions similarly to @O_NONBLOCK@ with extra flags on the synchronous system call, but waits for completion events, similarly to @io_uring@.
    151151
    152152For this project, I selected @io_uring@, in large parts because of its generality.
  • doc/theses/thierry_delisle_PhD/thesis/text/practice.tex

    r878be178 r62c5a55  
    6060To achieve this goal requires each reader to have its own memory to mark as locked and unlocked.
    6161The read acquire possibly waits for a writer to finish the critical section and then acquires a reader's local spinlock.
    62 The write acquire acquires the global lock, guaranteeing mutual exclusion among writers, and then acquires each of the local reader locks.
     62The write acquires the global lock, guaranteeing mutual exclusion among writers, and then acquires each of the local reader locks.
    6363Acquiring 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.
    64 
    6564Figure~\ref{f:SpecializedReadersWriterLock} shows the outline for this specialized readers-writer lock.
    6665The lock in nonblocking, so both readers and writers spin while the lock is held.
    67 \todo{finish explanation}
     66This very wide sharding strategy means that readers have very good locality, since they only ever need to access two memory location.
    6867
    6968\begin{figure}
     
    138137
    139138\subsection{Event FDs}
    140 Another interesting approach is to use an event file descriptor\cit{eventfd}.
     139Another interesting approach is to use an event file descriptor\cite{eventfd}.
    141140This Linux feature is a file descriptor that behaves like \io, \ie, uses @read@ and @write@, but also behaves like a semaphore.
    142141Indeed, all reads and writes must use a word-sized values, \ie 64 or 32 bits.
     
    218217\end{figure}
    219218
    220 The 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@.
     219The 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@.
    221220The 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}.
    222221A \proc begins its idle sleep by adding itself to the idle list before searching for an \at.
  • doc/theses/thierry_delisle_PhD/thesis/text/runtime.tex

    r878be178 r62c5a55  
    6262Only UNIX @man@ pages identify whether or not a library function is thread safe, and hence, may block on a pthreads lock or system call; hence interoperability with UNIX library functions is a challenge for an M:N threading model.
    6363
    64 Languages like Go and Java, which have strict interoperability with C\cit{JNI, GoLang with C}, can control operations in C by ``sandboxing'' them, \eg a blocking function may be delegated to a \gls{kthrd}. Sandboxing may help towards guaranteeing that the kind of deadlock mentioned above does not occur.
     64Languages like Go and Java, which have strict interoperability with C\cite{wiki:jni,go:cgo}, can control operations in C by ``sandboxing'' them, \eg a blocking function may be delegated to a \gls{kthrd}. Sandboxing may help towards guaranteeing that the kind of deadlock mentioned above does not occur.
    6565
    6666As mentioned in Section~\ref{intro}, \CFA is binary compatible with C and, as such, must support all C library functions. Furthermore, interoperability can happen at the function-call level, inline code, or C and \CFA translation units linked together. This fine-grained interoperability between C and \CFA has two consequences:
Note: See TracChangeset for help on using the changeset viewer.