Index: doc/theses/thierry_delisle_PhD/comp_II/comp_II.tex =================================================================== --- doc/theses/thierry_delisle_PhD/comp_II/comp_II.tex (revision 31a6f38ca7d2e1a23150072813a3cdf4f57f44f6) +++ doc/theses/thierry_delisle_PhD/comp_II/comp_II.tex (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -133,5 +133,5 @@ As a hard requirement, the \CFA scheduler must guarantee eventual progress, otherwise the above-mentioned illusion of simultaneous execution is broken and the scheduler becomes much more complex to reason about. \newterm{Predictability} and \newterm{reliability} mean similar workloads achieve similar performance so programmer execution intuition is respected. -For example, a thread that yields aggressively should not run more often than other tasks. +For example, a thread that yields aggressively should not run more often than other threads. While this is intuitive, it does not hold true for many work-stealing or feedback based schedulers. The \CFA scheduler must guarantee eventual progress, should be predictable, and offer reliable performance. @@ -219,5 +219,5 @@ Popping is done by selecting two queues at random and popping from the queue with the oldest timestamp. A higher number of underlying queues leads to less contention on each queue and therefore better performance. -In a loaded system, it is highly likely the queues are non-empty, \ie several tasks are on each of the underlying queues. +In a loaded system, it is highly likely the queues are non-empty, \ie several threads are on each of the underlying queues. For this case, selecting a queue at random to pop from is highly likely to yield a queue with available items. In Figure~\ref{fig:base}, ignoring the ellipsis, the chances of getting an empty queue is 2/7 per pick, meaning two random picks yield an item approximately 9 times out of 10. Index: doc/theses/thierry_delisle_PhD/comp_II/img/system.fig =================================================================== --- doc/theses/thierry_delisle_PhD/comp_II/img/system.fig (revision 31a6f38ca7d2e1a23150072813a3cdf4f57f44f6) +++ doc/theses/thierry_delisle_PhD/comp_II/img/system.fig (revision 7a8011331cd3137af75be1b83777c648932350ce) @@ -1,3 +1,3 @@ -#FIG 3.2 Produced by xfig version 3.2.5c +#FIG 3.2 Produced by xfig version 3.2.7b Landscape Center @@ -36,21 +36,4 @@ 1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4500 3600 15 15 4500 3600 4515 3615 -6 -6 3225 4125 4650 4425 -6 4350 4200 4650 4350 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4425 4275 15 15 4425 4275 4440 4290 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4500 4275 15 15 4500 4275 4515 4290 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 4575 4275 15 15 4575 4275 4590 4290 --6 -1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3450 4275 225 150 3450 4275 3675 4425 -1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4050 4275 225 150 4050 4275 4275 4425 --6 -6 6675 4125 7500 4425 -6 7200 4200 7500 4350 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7275 4275 15 15 7275 4275 7290 4290 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7350 4275 15 15 7350 4275 7365 4290 -1 3 0 1 -1 -1 0 0 20 0.000 1 0.0000 7425 4275 15 15 7425 4275 7440 4290 --6 -1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 6900 4275 225 150 6900 4275 7125 4425 --6 6 6675 3525 8025 3975 2 1 0 1 -1 -1 0 0 -1 0.000 0 0 -1 1 0 2 @@ -79,9 +62,8 @@ 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3975 2850 150 150 3975 2850 4125 2850 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 7200 2775 150 150 7200 2775 7350 2775 -1 3 0 1 0 0 0 0 0 0.000 1 0.0000 2250 4830 30 30 2250 4830 2280 4860 +1 3 0 1 0 0 0 0 0 0.000 1 0.0000 2250 4830 30 30 2250 4830 2280 4830 1 3 0 1 0 0 0 0 0 0.000 1 0.0000 7200 2775 30 30 7200 2775 7230 2805 1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3525 3600 150 150 3525 3600 3675 3600 -1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 3875 4800 100 100 3875 4800 3975 4800 -1 1 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4650 4800 150 75 4650 4800 4800 4875 +1 3 0 1 -1 -1 0 0 -1 0.000 1 0.0000 4625 4838 100 100 4625 4838 4725 4838 2 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5 2400 4200 2400 3750 1950 3750 1950 4200 2400 4200 @@ -153,19 +135,18 @@ 1 1 1.00 45.00 90.00 7875 3750 7875 2325 7200 2325 7200 2550 +2 2 1 1 -1 -1 0 0 -1 3.000 0 0 0 0 0 5 + 6975 4950 6750 4950 6750 4725 6975 4725 6975 4950 2 2 0 1 -1 -1 0 0 -1 0.000 0 0 0 0 0 5 5850 4950 5850 4725 5625 4725 5625 4950 5850 4950 -2 2 1 1 -1 -1 0 0 -1 3.000 0 0 0 0 0 5 - 6975 4950 6750 4950 6750 4725 6975 4725 6975 4950 -4 1 -1 0 0 0 10 0.0000 2 105 720 5550 4425 Processors\001 -4 1 -1 0 0 0 10 0.0000 2 120 1005 4200 3225 Blocked Tasks\001 -4 1 -1 0 0 0 10 0.0000 2 150 870 4200 3975 Ready Tasks\001 -4 1 -1 0 0 0 10 0.0000 2 135 1095 7350 1725 Other Cluster(s)\001 -4 1 -1 0 0 0 10 0.0000 2 105 840 4650 1725 User Cluster\001 -4 1 -1 0 0 0 10 0.0000 2 150 615 2175 3675 Manager\001 -4 1 -1 0 0 0 10 0.0000 2 105 990 2175 3525 Discrete-event\001 -4 1 -1 0 0 0 10 0.0000 2 135 795 2175 4350 preemption\001 -4 0 -1 0 0 0 10 0.0000 2 150 1290 2325 4875 generator/coroutine\001 -4 0 -1 0 0 0 10 0.0000 2 120 270 4050 4875 task\001 -4 0 -1 0 0 0 10 0.0000 2 105 450 7050 4875 cluster\001 -4 0 -1 0 0 0 10 0.0000 2 105 660 5925 4875 processor\001 -4 0 -1 0 0 0 10 0.0000 2 105 555 4875 4875 monitor\001 +4 1 -1 0 0 0 10 0.0000 2 135 900 5550 4425 Processors\001 +4 1 -1 0 0 0 10 0.0000 2 165 1170 4200 3975 Ready Threads\001 +4 1 -1 0 0 0 10 0.0000 2 165 1440 7350 1725 Other Cluster(s)\001 +4 1 -1 0 0 0 10 0.0000 2 135 1080 4650 1725 User Cluster\001 +4 1 -1 0 0 0 10 0.0000 2 165 630 2175 3675 Manager\001 +4 1 -1 0 0 0 10 0.0000 2 135 1260 2175 3525 Discrete-event\001 +4 1 -1 0 0 0 10 0.0000 2 150 900 2175 4350 preemption\001 +4 0 -1 0 0 0 10 0.0000 2 135 630 7050 4875 cluster\001 +4 1 -1 0 0 0 10 0.0000 2 135 1350 4200 3225 Blocked Threads\001 +4 0 -1 0 0 0 10 0.0000 2 135 540 4800 4875 thread\001 +4 0 -1 0 0 0 10 0.0000 2 120 810 5925 4875 processor\001 +4 0 -1 0 0 0 10 0.0000 2 165 1710 2325 4875 generator/coroutine\001