\documentstyle[psfig,fancybox]{seminar} \def\printlandscape{\special{landscape}} \slideframe{Oval} \newtheorem{property}{Property} \newcommand{\benq}{\begin{eqnarray}} \newcommand{\eenq}{\end{eqnarray}} \newcommand{\heading}[1]{% \begin{center} \large\bf %% \shadowbox {#1}% \end{center}} \begin{document} \begin{slide} \center{\Large { Earliest Eligible Virtual Deadline First : A Flexible and Accurate Proportional Share Allocation Algorithm}} %\center{\Large Ph.D Proposal} \center{\bf Ion Stoica, Hussein Abdel-Wahab} \center{{\it Department of Computer Science\\ Old Dominion University \\ Norfolk, Virginia, 23529-0162 \\ {\tt e-mail: {stoica, wahab}$@$cs.odu.edu} \\ {\tt URL: http://www.cs.odu.edu/~stoica}}} %\center{\bf Advisor: Hussein-Abdel Wahab} \newslide \heading{\underline {\Large Overview}} \vskip 0.2in \begin{itemize} \item The Problem \item The {\it EEVDF} Algorithm \item Theoretical Results \item Implementation Issues \item Experimental Results \item Conclusions and Future Work \end{itemize} \vskip 0.5in \newslide \heading{\underline {\Large The Problem}} \vskip 0.2in \begin{itemize} \item Consider a set of $n$ clients competing for a time-shared resource $R$, such that each client $i$ is characterized by a weight $w_i$. \\ The {\it Proportional Share Allocation Problem} asks to allocate to each client a share of resource $R$ {\bf proportional} to the client's weight. \end{itemize} \vskip 1.2in \newslide \heading{\underline {\Large Ideal (Fluid-Flow) System}} \begin{figure} \centerline{\psfig{figure=ideal.ps}} \end{figure} \newslide \heading{\underline {\Large Definitions}} \vskip 0.2in \begin{itemize} \item A client is {\it active} while is competing for the resource, and {\it passive} otherwise. \item ${\cal A}(t)$ - set of active clients at time $t$. \item $f_i(t)$ - share of client $i$: \vskip -0.2in \benq f_i(t) = \frac{w_i}{\sum_{j \i {\cal A}(t)} w_j}. \nonumber \eenq \item $S_i(t_1, t_2)$ - service time that client $i$ {\bf should} receive between $t_1$, and $t_2$: \vskip -0.4in \benq S_i(t_1, t_2) = \int_{t_1}^{t_2} f_i(\tau) d\tau.\nonumber \eenq \newslide \heading{\underline {\Large Client's Lag}} \vskip 0.2in \begin{itemize} \item $lag_i(t_1, t_2)$ - difference between service time that client $i$ {\bf should} have received in the ideal system between $t_1$ and $t_2$, and service time it {\bf has} actually received in the real system: \benq lag_i(t_1, t_2) = S_i(t_1, t_2) - s_i(t_1, t_2)\nonumber \eenq \item[] where $s_i(t_1, t_2)$ is the service time that client $i$ has received between $t_1$ and $t_2$. \end{itemize} \vskip 1in \end{itemize} \newslide \heading{\underline {\Large Virtual Time}} \begin{itemize} \item[] \benq S_i(t_1, t_2) = \int_{t_1}^{t_2}\frac{w_i}{\sum_{j \i {\cal A}(t)} w_j} d\tau.\nonumber \eenq \item {\it Virtual time} is defined as: \benq V(t) = \int_{0}^{t}\frac{1}{\sum_{j \i {\cal A}(t)}w_j} d\tau.\nonumber \eenq \item service time $S_i(t_1, t_2)$ can be written as: \benq S_i(t_1, t_2) = w_i (V(t_2) - V(t_1)). \nonumber \eenq \end{itemize} \newslide \heading{\underline {\Large Assumptions}} \vskip 0.2in \begin{itemize} \item {\bf Client Model} \begin{itemize} \item client $i$ becomes {\it active} at time $t_0^i$, when it issues a request to resource $R$, \item after a request is fulfilled, client $i$ either issues a new request, or becomes {\it passive}. \end{itemize} \item {\bf Resource Model} \begin{itemize} \item {\it exclusive}, %\item {non-preemptive}, \item is allocated in time quanta of size at most {\it q} (i.e., a client can use the resource for at most $q$ time units, after which is preempted). \end{itemize} \end{itemize} \vskip 0.6in \newslide \heading{\underline {\Large More Definitions ...}} \vskip 0.2in \begin{itemize} \item[] To each request of client $i$ (having duration $r$) associate: \begin{itemize} \item {\it eligible time (e)} - time by which all previous requests of client $i$ {\bf should} be fulfilled in the ideal system: \benq V(e) = V(t_0^i) + \frac{s_i(t_0^i, t)}{w_i}. \nonumber \eenq \item {\it deadline (d)} - time by which the new request {\bf should} be fulfilled in the ideal system: \benq V(d) = V(e) + \frac{r}{w_i}. \nonumber \eenq \end{itemize} \end{itemize} \newslide \heading{\underline {\Large The EEVDF Algorithm}} \vskip 0.2in \begin{itemize} \item[] A new time quantum is allocated to the client that has the {\bf eligible} request with the {\bf earliest virtual deadline}. \end{itemize} \vskip 1.5in \newslide \heading{\underline {\Large Example}} \vskip 0.2in \begin{figure} \centerline{\psfig{figure=ex.ps}} \end{figure} \begin{itemize} \item Two clients with equal weights, $w_1 = w_2 = 1$. \item client 1 becomes active a time 0, and client 2 at time 1. \end{itemize} \newslide \heading{\underline {\Large Fairness in Dynamic Systems}} \vskip 0.2in \begin{itemize} \item What is the impact on the other clients of a client leaving, joining, or changing its weight ? \item When a client with non-zero lag leaves, what should be its lag when it rejoins the competition ? \end{itemize} \vskip 1in \newslide \heading{\underline {\Large Algorithm Implementation}} \vskip 0.2in \begin{itemize} \item Characteristics of strategies are dictated by answers to: \begin{enumerate} \item Is a client allowed to join/leave competition when it has a non-zero lag ? \item Is a client penalized/receive compensation when it joins/leaves the competition ? \end{enumerate} \item {\bf Strategies} \begin{enumerate} \item ``Yes'' for 1. ``Yes'' for 2. \item ``Yes'' for 1. ``No'' for 2. \item ``No'' for 1. Trivially ``yes'' for 2. \end{enumerate} \end{itemize} \newslide \heading{\underline {\Large Theoretical Results}} \vskip 0.2in \begin{itemize} \item[] {\bf Definition.} A system is {\bf steady} iff all occurring events involve only client having zero lag. \item[] {\bf Theorem.} In a steady system the lag of any client $k$ is bounded: \benq -r_{max} < lag_k(d) < max(r_{max}, q), \nonumber \eenq \noindent where $r_{max}$ is the maximum duration of client's request and $q$ is a time quantum. \item[] {\bf Corollary.} In a steady system in which no request is larger than $q$, for any client $k$: \benq -q < lag_k(d) < q. \nonumber \eenq \end{itemize} \newslide \heading{\underline {\Large Implementation Issues}} \vskip 0.2in \begin{figure} \centerline{\psfig{figure=tree.ps}} \end{figure} \vskip 0.5in \newslide \heading{\underline {\Large Comparison with other Prop.-Share Algorithms}} \vskip 2.5in \newslide \heading{\underline {\Large Experiments}} \vskip 0.2in \begin{itemize} \item[] Prototype implementation: \begin{itemize} \item Simple prototype replacing CPU scheduler of FreeBSD v. 2.0.1 (only for user processes). \item Time quantum (slice) $=$ $100$ $msec.$ \end{itemize} \item[] Platform: \begin{itemize} \item PC compatible, 75 MhZ Pentium processor, 16 MB RAM. \end{itemize} \end{itemize} \vskip 1in \newslide \heading{\underline {\Large Application}} \begin{figure} \centerline{\psfig{figure=experiment.ps}} \end{figure} \newslide \heading{\underline {\Large Experiments}} \vskip 0.2in \begin{itemize} \item {\bf Experiment 1.} Three clients: $w_1 = 3$, $w_2 = 2$, $w_3 = 1$. \item {\bf Experiment 2.} Ten clients: $w_1 = 10$, $w_2 = w_3 = \ldots = w_{10} = 1$. \end{itemize} \begin{itemize} \item NOTE: {\bf compute()} function takes $\sim$ 90 $msec.$ on a ``free'' machine. \end{itemize} \vskip 1in \newslide \heading{\underline {\Large Experiment 1}} \begin{figure} \centerline{\psfig{figure=/home/stoica/sched_project/results/nov26/x1_2_3.ps}} \end{figure} \newslide \heading{\underline {\Large Experiment 1 (cont.)}} \begin{figure} \centerline{\psfig{figure=/home/stoica/sched_project/results/nov26/x1_2_3r10.ps}} \end{figure} \newslide \heading{\underline {\Large Experiment 1 (cont.)}} \begin{figure} \centerline{\psfig{figure=/home/stoica/sched_project/results/nov26/x1_2_3r1.ps}} \end{figure} \newslide \heading{\underline {\Large Experiment 2}} \begin{figure} \centerline{\psfig{figure=/home/stoica/sched_project/results/nov26/x10cl_100.ps}} \end{figure} \newslide \heading{\underline {\Large Experiment 2}} \begin{figure} \centerline{\psfig{figure=/home/stoica/sched_project/results/March8/x12.ps}} \end{figure} \newslide \heading{\underline {\Large Experiment 2 (cont.)}} \begin{figure} \centerline{\psfig{figure=/home/stoica/sched_project/results/nov26/x10cl_5.ps}} \end{figure} \newslide \heading{\underline {\Large Selection Overhead}} \begin{table*} {\small \begin{center} \begin{tabular}{| r | c |} \hline Num. of clients & Time per selection ($\mu$sec) \\\hline 3 & 0.75\\ 7 & 0.85\\ 15 & 1.06\\ 31 & 1.20\\ 63 & 1.47\\ 127 & 1.67\\ 255 & 1.95\\ 511 & 2.01\\ 1023 & 2.2\\ 2047 & 2.7\\ 4095 & 2.8\\ 8191 & 3.1\\ 16385 & 3.2\\ 32767 & 3.6\\ 65353 & 4.8\\ \hline \end{tabular} \end{center} } \end{table*} \newslide \heading{\underline {\Large Conclusions and Future Work}} \begin{itemize} \item {\it EEVDF} - a proportional-share allocation algorithm: \begin{itemize} \item accurate, \item flexible, \item efficient. \end{itemize} \item Potentially, {\it EEVDF} can provide an integrate solution for scheduling batch, interactive, and multimedia applications. \item {\bf Future Work} \begin{itemize} \item Theoretical study of non-steady systems. \item Study and implementation of a fully preemptive scheduler. \item Integration of inferior share bounded services. \item Implementation of a low-level interface that could be use to provide higher level abstractions, e.g., {\it tickets and currencies} (Waldspurger and Weihl), {\it capacity reserves} (Mercer). \end{itemize} \end{itemize} \newslide \heading{\underline {\Large Inferior share bounded services}} \vskip 0.2in \begin{figure} \centerline{\psfig{figure=infbound.ps}} \end{figure} \vskip 0.8in \end{slide} \end{document}