Index: doc/bibliography/pl.bib =================================================================== --- doc/bibliography/pl.bib (revision 912ccbcf495df9c8cccf8d1396d013895e717e1d) +++ doc/bibliography/pl.bib (revision 1c412aac6c86502bff9635802d6864e9f4fbda76) @@ -4524,4 +4524,13 @@ } +@misc{libfibre, + key = {libfibre}, + author = {Martin Karsten}, + title = {{libfibre:~User-Level Threading Runtime}}, + howpublished= {\href{https://git.uwaterloo.ca/mkarsten/libfibre} + {https://\-git.uwaterloo.ca/\-mkarsten/\-libfibre}}, + note = {[Online; accessed 2020-04-15]}, +} + @article{Linda, keywords = {Linda, concurrency}, @@ -5064,5 +5073,6 @@ title = {Multiple Inheritance for {C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}}}, booktitle = {Proceedings of the Spring '87 EUUG Conference}, - month = may, year = 1987 + month = may, + year = 1987, } @@ -8030,4 +8040,20 @@ } +@article{Karsten20, + author = {Karsten, Martin and Barghi, Saman}, + title = {{User-level Threading: Have Your Cake and Eat It Too}}, + year = {2020}, + issue_date = {March 2020}, + publisher = {Association for Computing Machinery}, + address = {New York, NY, USA}, + volume = {4}, + number = {1}, + url = {https://doi.org/10.1145/3379483}, + doi = {10.1145/3379483}, + journal = {Proc. ACM Meas. Anal. Comput. Syst.}, + month = mar, + numpages = {30}, +} + @techreport{Harmony, keywords = {messages, concurrency}, @@ -8045,9 +8071,11 @@ contributer = {gjditchfield@plg}, author = {Henry Lieverman}, - title = {Using Prototypical Objects to Implement Shared Behavior in - Object Oriented Systems}, + title = {Using Prototypical Objects to Implement Shared Behavior in Object Oriented Systems}, journal = sigplan, - month = nov, year = 1986, - volume = 21, number = 11, pages = {214-223} + month = nov, + year = 1986, + volume = 21, + number = 11, + pages = {214-223} } Index: doc/theses/thierry_delisle_PhD/comp_II/comp_II_PAB.tex =================================================================== --- doc/theses/thierry_delisle_PhD/comp_II/comp_II_PAB.tex (revision 912ccbcf495df9c8cccf8d1396d013895e717e1d) +++ doc/theses/thierry_delisle_PhD/comp_II/comp_II_PAB.tex (revision 1c412aac6c86502bff9635802d6864e9f4fbda76) @@ -15,9 +15,11 @@ \setlist{topsep=6pt,parsep=0pt} % global reduce spacing between points \newcommand{\uC}{$\mu$\CC} -\usepackage[hidelinks]{hyperref} +\usepackage[breaklinks=true,pagebackref=true,hidelinks]{hyperref} +\urlstyle{rm} \setlength{\abovecaptionskip}{5pt plus 3pt minus 2pt} \lstMakeShortInline$% % single-character for \lstinline %\usepackage[margin=1in]{geometry} %\usepackage{float} +%\usepackage{breakurl} \input{glossary} @@ -59,7 +61,7 @@ \section{Introduction} \subsection{\CFA and the \CFA concurrency package} -\CFA\cite{Moss18} is a modern, polymorphic, non-object-oriented, concurrent, backwards-compatible extension of the C programming language. +\CFA~\cite{Moss18} is a modern, polymorphic, non-object-oriented, concurrent, backwards-compatible extension of the C programming language. It aims to add high-productivity features while maintaining the predictable performance of C. -As such, concurrency in \CFA\cit aims to offer simple and safe high-level tools while still allowing performant code. +As such, concurrency in \CFA~\cite{Delisle19} aims to offer simple and safe high-level tools while still allowing performant code. \CFA concurrent code is written in the synchronous programming paradigm but uses \glspl{uthrd} in order to achieve the simplicity and maintainability of synchronous programming without sacrificing the efficiency of asynchronous programing. As such, the \CFA \newterm{scheduler} is a preemptive user-level scheduler that maps \glspl{uthrd} onto \glspl{kthrd}. @@ -327,5 +329,5 @@ How much scalability is actually needed is highly debatable. -\emph{libfibre}\cit has compared favorably to other schedulers in webserver tests\cit and uses a single atomic counter in its scheduling algorithm similarly to the proposed bitmask. +\emph{libfibre}~\cite{libfibre} has compared favorably to other schedulers in webserver tests~\cite{Karsten20} and uses a single atomic counter in its scheduling algorithm similarly to the proposed bitmask. As such, the single atomic instruction on a shared cacheline may be sufficiently performant. @@ -375,5 +377,5 @@ There are possible alternatives to the reader-writer lock solution. -This problem is effectively a memory reclamation problem and as such there is a large body of research on the subject\cit. +This problem is effectively a memory reclamation problem and as such there is a large body of research on the subject~\cite{michael2004hazard, brown2015reclaiming}. However, the reader-write lock-solution is simple and can be leveraged to solve other problems (\eg processor ordering and memory reclamation of threads), which makes it an attractive solution. @@ -421,5 +423,5 @@ Processors that are unnecessarily unblocked lead to unnecessary contention, CPU usage, and power consumption, while too many sleeping processors can lead to sub-optimal throughput. Furthermore, transitions from sleeping to awake and vice-versa also add unnecessary latency. -There is already a wealth of research on the subject \TODO{(reference Libfibre)} and I may use an existing approach for the idle-sleep heuristic in this project. +There is already a wealth of research on the subject~\cite{schillings1996engineering, wiki:thunderherd} and I may use an existing approach for the idle-sleep heuristic in this project, \eg~\cite{Karsten20}. \subsection{Asynchronous I/O} @@ -444,16 +446,27 @@ While there exists many different APIs for asynchronous I/O, it is not part of this proposal to create a novel API. It is sufficient to make one work in the complex context of the \CFA runtime. -\uC uses the $select$ as its interface, which handles ttys, pipes and sockets, but not disk. +\uC uses the $select$~\cite{select} as its interface, which handles ttys, pipes and sockets, but not disk. $select$ entails significant complexity and is being replaced in UNIX operating-systems, which make it a less interesting alternative. -Another popular interface is $epoll$\cit, which is supposed to be cheaper than $select$. -However, epoll also does not handle the file system and seems to have problem to linux pipes and $TTY$s\cit. -A very recent alternative that I am investigating is $io_uring$. -It claims to address some of the issues with $epoll$ but is too recent to be confident that it does. -Finally, a popular cross-platform alternative is $libuv$, which offers asynchronous sockets and asynchronous file system operations (among other features). +Another popular interface is $epoll$~\cite{epoll}, which is supposed to be cheaper than $select$. +However, $epoll$ also does not handle the file system and anecdotal evidence suggest it has problem with linux pipes and $TTY$s. +A popular cross-platform alternative is $libuv$~\cite{libuv}, which offers asynchronous sockets and asynchronous file system operations (among other features). However, as a full-featured library it includes much more than I need and could conflict with other features of \CFA unless significant effort is made to merge them together. +A very recent alternative that I am investigating is $io_uring$~\cite{io_uring}. +It claims to address some of the issues with $epoll$ and my early investigating suggest that the claim is accurate. +$io_uring$ uses a much more general approach where system calls are register to a queue and later executed by the kernel, rather than relying on system calls to return an error instead of blocking and subsequently waiting for changes on file descriptors. +I believe this approach allows for fewer problems, \eg the manpage for $open$~\cite{open} states: +\begin{quote} + Note that [the $O_NONBLOCK$ flag] has no effect for regular files and block devices; + that is, I/O operations will (briefly) block when device activity is required, regardless of whether $O_NONBLOCK$ is set. + Since $O_NONBLOCK$ semantics might eventually be implemented, applications should not depend upon blocking behavior when specifying this flag for regular files and block devices. +\end{quote} +This makes approach based on $epoll$/$select$ less reliable since they may not work for every file descriptors. +For this reason, I have started to use $io_uring$ as the OS abstraction for the \CFA runtime, until further work shows problems I have not encountered yet. +However, only a small subset of the features are available in Ubuntu as of April 2020~\cite{wiki:ubuntu-linux}, which limits performance comparisons. +The currently available features are sufficient to start basic socket performance experiments and comparisons. \paragraph{Event Engine} Laying on top of the asynchronous interface layer is the event engine. -This engine is responsible for multiplexing (batching) the synchronous I/O requests into asynchronous I/O requests and demultiplexing the results to appropriate blocked user threads. +This engine is responsible for multiplexing (batching) the synchronous I/O requests into asynchronous I/O requests and demultiplexing the results to appropriate blocked user-threads. This step can be straightforward for simple cases, but becomes quite complex when there are thousands of user threads performing both reads and writes, possibly on overlapping file descriptors. Decisions that need to be made include: @@ -469,7 +482,7 @@ \paragraph{Interface} Finally, for these non-blocking I/O components to be available, it is necessary to expose them through a synchronous interface because that is the \CFA concurrent programming style. -The interface can be novel but it is preferable to match the existing POSIX interface when possible to be compatible with existing code. +The interface can add novel features but it is preferable to match the existing POSIX interface when possible to be compatible with existing code. Matching allows C programs written using this interface to be transparently converted to \CFA with minimal effort. -Where new functionality is needed, I will create a novel interface to fill gaps and provide advanced features. +Where new functionality is needed, I will create a novel interface extensions to fill gaps and provide advanced features. @@ -477,10 +490,20 @@ % =============================================================================== \section{Discussion} - +I believe that runtime systems and scheduling are still open topics. +Many ``state of the art'' production frameworks still use single threaded event-loops because of performance considerations, \eg~\cite{nginx-design}, and, to my knowledge, no widely available system language offers modern threading facilities. +I believe the proposed work offers a novel runtime and scheduling package embedded in the \CFA programming language, where existing work only offers fragments that users must assemble themselves when possible. % =============================================================================== % =============================================================================== \section{Timeline} - +\begin{center} +\begin{tabular}{ | r @{--} l | p{4in} | } +\hline May 2020 & October 2020 & Creation of the performance benchmark. \\ +\hline November 2020 & March 2021 & Completion of the implementation. \\ +\hline March 2021 & April 2021 & Final Performance experiments. \\ +\hline May 2017 & August 2021 & Thesis writing and defense. \\ +\hline +\end{tabular} +\end{center} % B I B L I O G R A P H Y @@ -489,4 +512,5 @@ \phantomsection % allows hyperref to link to the correct page \addcontentsline{toc}{section}{\refname} +\lstDeleteShortInline$% turn off as $ used in bibliography entries \bibliographystyle{plain} \bibliography{pl,local} Index: doc/theses/thierry_delisle_PhD/comp_II/local.bib =================================================================== --- doc/theses/thierry_delisle_PhD/comp_II/local.bib (revision 912ccbcf495df9c8cccf8d1396d013895e717e1d) +++ doc/theses/thierry_delisle_PhD/comp_II/local.bib (revision 1c412aac6c86502bff9635802d6864e9f4fbda76) @@ -76,5 +76,5 @@ @article{finkel1987dib, - title={DIB—a distributed implementation of backtracking}, + title={DIB-a distributed implementation of backtracking}, author={Finkel, Raphael and Manber, Udi}, journal={ACM Transactions on Programming Languages and Systems (TOPLAS)}, @@ -266,4 +266,5 @@ % =============================================================================== @manual{open, + key = "open", title = "open(2) Linux User's Manual", year = "2020", @@ -272,4 +273,5 @@ @manual{epoll, + key = "epoll", title = "epoll(7) Linux User's Manual", year = "2019", @@ -278,4 +280,5 @@ @manual{select, + key = "select", title = "select(7) Linux User's Manual", year = "2019", @@ -289,10 +292,11 @@ month = "March", version = {0,4}, - url = {https://kernel.dk/io_uring.pdf} + howpublished = {\url{https://kernel.dk/io_uring.pdf}} } @misc{libuv, + key = "libuv", title = {libuv}, - url = {https://github.com/libuv/libuv} + howpublished = {\url{https://github.com/libuv/libuv}} } @@ -301,31 +305,9 @@ % =============================================================================== -% libfibre web server -@article{karstenuser, - title={User-level Threading: Have Your Cake and Eat It Too}, - author={KARSTEN, MARTIN and BARGHI, SAMAN} -} - -% libfibre -@misc{libfibre, - title={libfibre}, - author={KARSTEN, MARTIN}, - journal={URL: https://git.uwaterloo.ca/mkarsten/libfibre} -} - @misc{nginx-design, - title={Inside NGINX: How We Designed for Performance \& Scale}, - url = "https://www.nginx.com/blog/inside-nginx-how-we-designed-for-performance-scale/", -} - -@article{Delisle19, - keywords = {concurrency, Cforall}, - contributer = {pabuhr@plg}, - author = {Thierry Delisle and Peter A. Buhr}, - title = {Advanced Control-flow and Concurrency in \textsf{C}$\mathbf{\forall}$}, - year = 2019, - journal = spe, - pages = {1-33}, - note = {submitted}, + key = "nginx", + title={Inside {NGINX}: How We Designed for Performance \& Scale}, + howpublished= {\href{https://www.nginx.com/blog/inside-nginx-how-we-designed-for-performance-scale} + {https://\-www.nginx.com/\-blog/\-inside\--nginx\--how\--we\--designed\--for\--performance\--scale}}, } @@ -343,13 +325,15 @@ title = "Thundering herd problem --- {W}ikipedia{,} The Free Encyclopedia", year = "2020", - url = "https://en.wikipedia.org/wiki/Thundering_herd_problem", + howpublished = {\href{https://en.wikipedia.org/wiki/Thundering_herd_problem} + {https://\-en.wikipedia.org/\-wiki/\-Thundering\_herd\_problem}},}, note = "[Online; accessed 14-April-2020]" - } - - @misc{wiki:ubuntu-linux, +} + +@misc{wiki:ubuntu-linux, author = "{Wikipedia contributors}", title = "Ubuntu version history : Table of versions --- {W}ikipedia{,} The Free Encyclopedia", year = "2020", - url = "https://en.wikipedia.org/wiki/Ubuntu_version_history#Table_of_versions", + howpublished = {\href{https://en.wikipedia.org/wiki/Ubuntu_version_history\#Table_of_versions} + {https://\-en.wikipedia.org/\-wiki/\-Ubuntu\_version\_history\#Table\_of\_versions}}, note = "[Online; accessed 15-April-2020]" - } +}