\boolfalse {citerequest}\boolfalse {citetracker}\boolfalse {pagetracker}\boolfalse {backtracker}\relax 
\defcounter {refsection}{0}\relax 
\select@language {english}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {1}Introduction}{5}{section.0.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {1.1}goal}{7}{subsection.0.1.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {1.2}criticality groups}{7}{subsection.0.1.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {1.3}real-time isolation}{9}{subsection.0.1.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {1.4}different kinds of computer systems}{10}{subsection.0.1.4}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {1.4.1}hybrids and gray zones}{11}{subsubsection.0.1.4.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {1.4.2}where does this project fit in?}{12}{subsubsection.0.1.4.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {1.5}why a real-time multicore?}{13}{subsection.0.1.5}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {1.6}meta}{14}{subsection.0.1.6}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {2}Related work}{15}{section.0.2}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {3}System overview: two cores, shared DRAM}{18}{section.0.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {3.1}the critical core}{18}{subsection.0.3.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {3.2}isolation between the cores}{18}{subsection.0.3.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {3.3}the best-effort core}{18}{subsection.0.3.3}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {4}The Linux implementation}{20}{section.0.4}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {4.1}the real-time system}{20}{subsection.0.4.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {4.2}the critical tasks}{21}{subsection.0.4.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {4.3}\texttt {perf\_event\_open(2)}}{21}{subsection.0.4.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {4.4}\texttt {cgroups}}{22}{subsection.0.4.4}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {5}Real-time Linux and Unix}{23}{section.0.5}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {5.1}Linux real-time schedulers}{23}{subsection.0.5.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {5.2}the Linux and C++ clocks}{24}{subsection.0.5.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {5.3}hardware}{26}{subsection.0.5.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {5.4}isolation}{29}{subsection.0.5.4}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {5.4.1}starvation}{30}{subsubsection.0.5.4.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {5.4.2}isolating the cores on Linux}{30}{subsubsection.0.5.4.2}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {6}Scheduling}{32}{section.0.6}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {6.1}algorithm}{33}{subsection.0.6.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {6.2}step-by-step description}{34}{subsection.0.6.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {6.3}task priority}{34}{subsection.0.6.3}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {7}The task finite state machine}{36}{section.0.7}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {7.1}transitions}{36}{subsection.0.7.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {7.2}states}{37}{subsection.0.7.2}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {8}System description}{38}{section.0.8}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {8.1}the top-scheduler}{39}{subsection.0.8.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {8.2}how the time parameters relate}{40}{subsection.0.8.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {8.3}task scheduler}{40}{subsection.0.8.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {8.3.1}$m_{i}$, the maximum best-effort core memory accesses}{41}{subsubsection.0.8.3.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {8.3.2}$b_{i}$, the CPU-budget}{41}{subsubsection.0.8.3.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {8.3.3}$\alpha _{i}$, the (task) scheduling algorithm}{41}{subsubsection.0.8.3.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {8.4}$P_{i}$, the sporadic task set}{42}{subsection.0.8.4}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {8.5}the sporadic task model}{42}{subsection.0.8.5}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {8.5.1}task parameters}{42}{subsubsection.0.8.5.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {8.5.2}task properties}{43}{subsubsection.0.8.5.2}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {9}Schedulability method: response time}{44}{section.0.9}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {9.1}$r_{j}$, the worst-case response-time for $t_{j}$}{44}{subsection.0.9.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {9.1.1}$Q_{j}$, queuing}{44}{subsubsection.0.9.1.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {9.1.2}$z$, the response time in global periods}{45}{subsubsection.0.9.1.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {9.1.3}$Q^{g}_{j}$, group deadline queuing}{45}{subsubsection.0.9.1.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {9.1.4}$Q^{s}_{j}$, cross-group (system) deadline queuing}{45}{subsubsection.0.9.1.4}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {9.1.5}depletion queuing}{46}{subsubsection.0.9.1.5}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {9.1.6}$o_{j}$, the scheduling overhead}{46}{subsubsection.0.9.1.6}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {9.2}$i_{j}$, interference from the best-effort core}{46}{subsection.0.9.2}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {10}Schedulability method: resource server}{48}{section.0.10}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {10.1}interval length}{49}{subsection.0.10.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {10.2}\texttt {sbf}}{49}{subsection.0.10.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {10.3}\texttt {dbf}}{51}{subsection.0.10.3}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {11}Experiments}{52}{section.0.11}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {11.1}building blocks}{52}{subsection.0.11.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {11.2}design}{54}{subsection.0.11.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {11.3}zsh wrappers}{54}{subsection.0.11.3}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {12}Contention experiment}{55}{section.0.12}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {12.1}setup}{55}{subsection.0.12.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {12.2}conclusion}{56}{subsection.0.12.2}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {13}Best-effort core memory experiment}{57}{section.0.13}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {13.1}the importance of this experiment: delays and overheads}{57}{subsection.0.13.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {13.2}systems}{58}{subsection.0.13.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {13.2.1}one-scheduler system: \texttt {base-faculty-1}}{58}{subsubsection.0.13.2.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {13.2.2}two-scheduler system: \texttt {base-faculty-2}}{59}{subsubsection.0.13.2.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {13.3}conclusion}{61}{subsection.0.13.3}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {14}\texttt {hs} task systems experiment}{62}{section.0.14}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {14.1}setup}{62}{subsection.0.14.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {14.2}what is a task system?}{62}{subsection.0.14.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {14.3}simulation issues}{63}{subsection.0.14.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {14.4}the result data}{63}{subsection.0.14.4}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {14.5}systems and results}{64}{subsection.0.14.5}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {14.5.1}\texttt {base}}{64}{subsubsection.0.14.5.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {14.5.2}\texttt {long-ticks}}{65}{subsubsection.0.14.5.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {14.5.3}\texttt {long-period}}{66}{subsubsection.0.14.5.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {14.6}conclusion}{67}{subsection.0.14.6}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {15}Linux processes experiment}{68}{section.0.15}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {15.1}advantages}{68}{subsection.0.15.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {15.2}disadvantages}{69}{subsection.0.15.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {15.3}systems and results}{69}{subsection.0.15.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {15.3.1}\texttt {base-p}}{69}{subsubsection.0.15.3.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {15.3.2}\texttt {base-p-no-memory-budget}}{70}{subsubsection.0.15.3.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {15.4}conclusion}{71}{subsection.0.15.4}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {16}Real real-time: audio experiment}{73}{section.0.16}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {16.1}system}{74}{subsection.0.16.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {16.2}execution}{75}{subsection.0.16.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {16.3}ideal fallout}{77}{subsection.0.16.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {16.4}conclusion}{77}{subsection.0.16.4}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {17}Conclusion}{79}{section.0.17}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {18}References}{81}{section.0.18}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {A}Appendix A: Memory experiment fallout}{83}{section.Alph0.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {A.a}\texttt {base-faculty-1}}{84}{subsection.Alph0.1.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {A.b}\texttt {base-faculty-2}}{85}{subsection.Alph0.1.2}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {B}Appendix B: Formulas}{86}{section.Alph0.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {B.a}system}{86}{subsection.Alph0.2.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {B.b}sporadic task model}{86}{subsection.Alph0.2.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {B.c}response time}{86}{subsection.Alph0.2.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {B.d}resource server}{86}{subsection.Alph0.2.4}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {B.d.a}supply}{87}{subsubsection.Alph0.2.4.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsubsection}{\numberline {B.d.b}demand}{87}{subsubsection.Alph0.2.4.2}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {C}Appendix C: \texttt {hs} code}{88}{section.Alph0.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.a}man page for \texttt {hs}}{88}{subsection.Alph0.3.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.b}\texttt {ask}}{92}{subsection.Alph0.3.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.c}\texttt {be}}{92}{subsection.Alph0.3.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.d}\texttt {file\_io}}{94}{subsection.Alph0.3.4}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.e}\texttt {global\_scheduler}}{95}{subsection.Alph0.3.5}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.f}\texttt {llc}}{105}{subsection.Alph0.3.6}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.g}\texttt {log}}{107}{subsection.Alph0.3.7}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.h}\texttt {main}}{109}{subsection.Alph0.3.8}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.i}\texttt {options}}{110}{subsection.Alph0.3.9}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.j}\texttt {program}}{113}{subsection.Alph0.3.10}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.k}\texttt {sporadic\_task}}{114}{subsection.Alph0.3.11}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.l}\texttt {task\_scheduler}}{119}{subsection.Alph0.3.12}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.m}\texttt {tcb}}{126}{subsection.Alph0.3.13}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {C.n}\texttt {time\_io}}{135}{subsection.Alph0.3.14}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {D}Appendix D: experiment code and example data}{136}{section.Alph0.4}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {D.a}example \texttt {hs} system}{136}{subsection.Alph0.4.1}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {D.b}useful zsh commands}{137}{subsection.Alph0.4.2}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {D.c}zsh wrapper to run experiments}{141}{subsection.Alph0.4.3}
\defcounter {refsection}{0}\relax 
\contentsline {subsection}{\numberline {D.d}tick trace cruncher in Elisp}{149}{subsection.Alph0.4.4}
\defcounter {refsection}{0}\relax 
\contentsline {section}{\numberline {$\rightarrow $}Index}{150}{section.Alph0.5}