Changes in / [62c5a55:878be178]


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

Legend:

Unmodified
Added
Removed

  • doc/theses/thierry_delisle_PhD/thesis/local.bib

    r62c5a55 r878be178  
    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 
    462431% --------------------------------------------------
    463432% ULE FreeBSD scheduler
    … …  
    613582}
    614583
    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 
    709584% --------------------------------------------------
    710585% Man Pages
    … …  
    744619}
    745620
    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",
    758 }
    759 
    760621@manual{MAN:aio,
    761622  key        = "aio",
    … …  
    848709}
    849710
    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
     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
    868732@misc{AIORant,
    869733  author = "Linus Torvalds",
    … …  
    875739}
    876740
    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 }
     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}

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

    r62c5a55 r878be178  
    1515For threading, a simple and common execution mental-model is the ``Ideal multi-tasking CPU'' :
    1616
    17 \begin{displayquote}[Linux CFS\cite{MAN:linux/cfs}]
     17\begin{displayquote}[Linux CFS\cit{https://www.kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt}]
    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}\cite{xkcd:dynamicentropy}
     185\subsection{Dynamic Entropy}\cit{https://xkcd.com/2318/}
    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\cite{wiki:lcg} support running the algorithm backwards while offering good quality and performance.
     189Luckily, 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.
    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\cite{wiki:ma} (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\cit{https://en.wikipedia.org/wiki/Moving\_average\#Exponential\_moving\_average} (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

    r62c5a55 r878be178  
    1010
    1111\section{Memcached}
    12 Memcached~\cite{memcached} is an in memory key-value store that is used in many production environments, \eg \cite{atikoglu2012workload}.
    13 This also server also has the notable added benefit that there exists a full-featured front-end for performance testing called @mutilate@~\cite{GITHUB:mutilate}.
     12Memcached~\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,
     13SIGMETRICS 2012}.
     14This also server also has the notable added benefit that there exists a full-featured front-end for performance testing called @mutilate@~\cit{mutilate}.
    1415Experimenting 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.
    1516This experiment does not exercise the \io subsytem with regards to disk operations.
    … …  
    9798Most of the implementation is fairly straight forward however the inclusion of file \io introduces a new challenge that had to be hacked around.
    9899
    99 Normally, 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.
     100Normally, 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.
    101102However, 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.
    102103As 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}.
    … …  
    107108When the saturation point of the server is attained, latency will increase and inevitably some client connections will timeout.
    108109As these clients close there connections, the server must close these sockets without delay so the OS can reclaim the resources used by these connections.
    109 Indeed, 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.
     110Indeed, 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.
    110111However, this poses a problem using blocking @sendfile@ calls.
    111112The 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

    r62c5a55 r878be178  
    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 \cite{win:priority}, one specified by users out of ten possible options and one adjusted by the system.
     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.
    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 In~\cite{russinovich2009windows}, Chapter 1 section ``Processes, Threads, and Jobs'' discusses the scheduling policy more in depth.
    140 Multicore scheduling is based on a combination of priorities, preferred \proc.
    141 Each \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.
    143 This 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.
     139\todo{load balancing}
    144140
    145141\paragraph{Apple OS X}
    … …  
    160156\paragraph{Go}\label{GoSafePoint}
    161157Go'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}.
    162 Preemption is present, but only at safe-points,~\cite{go:safepoints} which are inserted detection code at various frequent access boundaries.
     158Preemption 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.
    163159
    164160The algorithm is as follows :
    … …  
    203199
    204200\paragraph{Grand Central Dispatch}
    205 An Apple\cite{apple:gcd} API that offers task parallelism~\cite{wiki:taskparallel}.
     201An Apple\cit{Official GCD source} API that offers task parallelism~\cite{wiki:taskparallel}.
    206202Its distinctive aspect is multiple ``Dispatch Queues'', some of which are created by programmers.
    207203Each queue has its own local ordering guarantees, \eg \ats on queue $A$ are executed in \emph{FIFO} order.
    208204
    209 While the documentation only gives limited insight into the scheduling and load balancing approach, \cite{apple:gcd2} suggests an approach fairly classic;
    210 Where each \proc has a queue of \newterm{blocks} to run, effectively \ats, and they drain their respective queues in \glsxtrshort{fifo}.
    211 They seem to add the concept of dependent queues with clear ordering, where a executing a block ends-up scheduling more blocks.
    212 In terms of semantics, these Dispatch Queues seem to be very similar to Intel\textregistered ~TBB @execute()@ and predecessor semantics.
     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
     209In terms of semantics, the Dispatch Queues seem to be very similar to Intel\textregistered ~TBB @execute()@ and predecessor semantics.
    213210
    214211\paragraph{LibFibre}

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

    r62c5a55 r878be178  
    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\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.
     143This 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.
    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)~\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@.
     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)~\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@.
    151151
    152152For this project, I selected @io_uring@, in large parts because of its generality.

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

    r62c5a55 r878be178  
    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 acquires the global lock, guaranteeing mutual exclusion among writers, and then acquires each of the local reader locks.
     62The write acquire 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
    6465Figure~\ref{f:SpecializedReadersWriterLock} shows the outline for this specialized readers-writer lock.
    6566The lock in nonblocking, so both readers and writers spin while the lock is held.
    66 This very wide sharding strategy means that readers have very good locality, since they only ever need to access two memory location.
     67\todo{finish explanation}
    6768
    6869\begin{figure}
    … …  
    137138
    138139\subsection{Event FDs}
    139 Another interesting approach is to use an event file descriptor\cite{eventfd}.
     140Another interesting approach is to use an event file descriptor\cit{eventfd}.
    140141This Linux feature is a file descriptor that behaves like \io, \ie, uses @read@ and @write@, but also behaves like a semaphore.
    141142Indeed, all reads and writes must use a word-sized values, \ie 64 or 32 bits.
    … …  
    217218\end{figure}
    218219
    219 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@.
     220The 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@.
    220221The 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}.
    221222A \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

    r62c5a55 r878be178  
    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\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.
     64Languages 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.
    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.