0001 % -*- Mode: LaTeX; TeX-PDF-mode: t -*-
0002 \documentclass[twocolumn,10pt]{article}
0003 \usepackage{amsmath,proof,amsthm,listings,algorithm}
0004 \usepackage[noend]{algorithmic}
0005 \renewcommand\algorithmiccomment[1]{ {\tt /*} #1 {\tt */}}
0006 \newcommand\paren[1]{\left( {#1} \right)}
0007 \newcommand\set[1]{\left\{ {#1} \right\}}
0008 \newcommand\len[1]{\left| {#1} \right|}
0009 % \newcommand\sched{\overset{s}{\mapsto}}
0010 % \newcommand\wake[1]{\overset{w_{#1}}{\mapsto}}
0011 \newcommand\sched{\xrightarrow{s}}
0012 \newcommand\msched{\sched^{\!{\raisebox{-1.5ex}{*}}}}
0013 \newcommand\wake[1]{\xrightarrow{w_{#1}}}
0014 \newcommand\vcpu[1]{\paren{#1}}
0015 \newcommand\pcpu[1]{\paren{#1}}
0016 \newcommand\running[1]{\ensuremath{{running}\paren{#1}}}
0017 \newcommand\runnable[1]{\ensuremath{{runnable}\paren{#1}}}
0018 \newtheorem{thm}{Theorem}
0019 \newtheorem{lma}{Lemma}
0020 \newtheorem{prop}{Property}
0021 % \numberwithin{equation}{subsection}
0022 % \renewcommand{\theequation}{\thesubsection\arabic{equation}}
0023 \lstset{language=C}
0024
0025 \begin{document}
0026
0027 \paragraph{Terminology} $\tau$ denotes a task, $Q$ denotes the quantum
0028 (in time units), $n$ denotes remaining time, $\sched$ denotes {\tt
0029 schedule}, and $\wake{\tau}$ denotes {\tt wakeup} on task $\tau$.
0030 VCPUs are represented as a tuple $\vcpu{\tau, n, \tau, \ldots}$
0031 containing the current task, the remaining quantum, and the tasks in
0032 the runqueue. For convenience, assume that the runqueue entries are
0033 filled with the idle task $\tau_0$ whenever needed. VCPUs are denoted
0034 with $V$. $V_{\tau}$ is the VCPU associated with task $\tau$. $0$
0035 denotes idle or empty activity. PCPUs are represented as a tuple
0036 $\pcpu{V, V', \ldots}$ where $V$ is the current VCPU and $V',\ldots$
0037 are in the VCPU queue.
0038
0039 \section{Round-Robin/Round-Robin Scheduling}
0040
0041 \subsection{First level scheduling}
0042
0043 \begin{subequations}
0044 \begin{equation}
0045 \label{pcpu:s1}
0046 \infer{\pcpu{V,V',\ldots}\sched\pcpu{V'',\ldots}}{
0047 V'\sched V'' & V''=(\tau, n, 0)
0048 }
0049 \end{equation}
0050 \begin{equation}
0051 \label{pcpu:s2}
0052 \infer{\pcpu{V,V',\ldots}\sched\pcpu{V'',V'',\ldots}}{
0053 V'\sched V'' & V''=(\tau, n, \tau', \ldots)
0054 }
0055 \end{equation}
0056 \begin{equation}
0057 \label{pcpu:s3}
0058 \infer{\pcpu{V,0}\sched\pcpu{0,0}}{}
0059 \end{equation}
0060 \begin{equation}
0061 \label{pcpu:w1}
0062 \infer{\pcpu{V,\ldots}\wake{\tau}\pcpu{V,\ldots,V'_{\tau}}}{
0063 V_{\tau}\wake{\tau}V'_{\tau} & V_{\tau} \not\in \set{\ldots}
0064 }
0065 \end{equation}
0066 \begin{equation}
0067 \label{pcpu:w2}
0068 \infer{\pcpu{V,\ldots,V_{\tau},\ldots}\wake{\tau}\pcpu{V,\ldots,V'_{\tau},\ldots}}{
0069 V_{\tau}\wake{\tau}V'_{\tau} &
0070 }
0071 \end{equation}
0072 \end{subequations}
0073 Rule~\ref{pcpu:s1} takes a VCPU $V'$ off the queue, transitions it to
0074 $V''$ (with an empty runqueue) and then makes it the current VCPU.
0075 Rule~\ref{pcpu:s2} applies when the VCPU has a non-empty runqueue.
0076 Rule~\ref{pcpu:s3} handles the empty queue case. Rule~\ref{pcpu:w1}
0077 shows that both the task and the VCPU are placed on their respective
0078 queues during wakeup, and rule~\ref{pcpu:w2} indicates idempotency of
0079 VCPU {\tt wakeup}.
0080
0081 \subsection{Second level scheduling}
0082
0083 \begin{subequations}
0084 \begin{flalign}
0085 \vcpu{\tau, 0, \tau', \ldots} &\sched \vcpu{\tau', Q, \ldots} \label{vcpu:s1}\\
0086 \vcpu{\tau, n, \ldots, \tau, \ldots} &\sched \vcpu{\tau, n, \ldots}\quad\text{where }n > 0 \label{vcpu:s2}\\
0087 \vcpu{\tau, n, \tau', \ldots} &\sched \vcpu{\tau', n, \ldots}\quad\text{where }n > 0, \tau\neq\tau' \label{vcpu:s3}\\
0088 \vcpu{\tau, n, \ldots} &\wake{\tau'} \vcpu{\tau, n, \ldots, \tau'}\quad\text{where }\tau'\not\in\set{\ldots}\label{vcpu:w1} \\
0089 \vcpu{\tau, n, \ldots, \tau', \ldots} &\wake{\tau'} \vcpu{\tau,
0090 n, \ldots, \tau', \ldots} \label{vcpu:w2}
0091 \end{flalign}
0092 \end{subequations}
0093
0094 Transition~\ref{vcpu:s1} occurs when the quantum expires.
0095 Transition~\ref{vcpu:s2} occurs when the quantum has not expired and
0096 the current task also appears on the runqueue.
0097 Transition~\ref{vcpu:s3} is the remaining case for when the quantum
0098 has not expired but the task is not runnable.
0099 Transition~\ref{vcpu:w1} shows how tasks are added to the runqueue.
0100 Transition~\ref{vcpu:w2} indicates idempotency of task {\tt wakeup}.
0101
0102 \section{Properties}
0103
0104 \begin{prop}
0105 \begin{subequations}
0106 \begin{equation}
0107 \label{eq:runningP}
0108 \infer{\running{\tau,(V,\ldots)}}{\running{\tau,V}}
0109 \end{equation}
0110 \begin{equation}
0111 \label{eq:runningV}
0112 \infer{\running{\tau,(\tau',n,\ldots)}}{\tau=\tau'}
0113 \end{equation}
0114 \end{subequations}
0115 \end{prop}
0116 \begin{prop}
0117 \begin{subequations}
0118 \begin{equation}
0119 \label{eq:runnableP}
0120 \infer{\runnable{\tau,(V,V_1,V_2,\ldots,V_m)}}{
0121 \exists_{j\in\set{1,\ldots,m}}\runnable{\tau,V_j}
0122 }
0123 \end{equation}
0124 \begin{equation}
0125 \label{eq:runnableV}
0126 \infer{\runnable{\tau,(\tau',n,\ldots,\tau'',\ldots)}}{\tau=\tau''}
0127 \end{equation}
0128 \end{subequations}
0129 \end{prop}
0130
0131 \begin{prop}[Multiple step {\tt schedule}]
0132 \begin{subequations}
0133 \begin{equation}
0134 \label{msched:refl}
0135 \infer{P\msched P}{}
0136 \end{equation}
0137 \begin{equation}
0138 \label{msched:trans}
0139 \infer{P\msched P''}{P\sched P' & P'\msched P''}
0140 \end{equation}
0141 \end{subequations}
0142 \end{prop}
0143
0144 \begin{lma}\label{lma:wakerun}
0145 If $P\wake{\tau} P'$ then \runnable{\tau,P'}.
0146 \end{lma}
0147 \begin{proof}
0148 Inversion on rules (\ref{pcpu:w1}) or (\ref{pcpu:w2}) gives
0149 $V_{\tau}\wake{\tau}V'_{\tau}$ and
0150 $P'=\pcpu{V,\ldots,V'_{\tau},\ldots}$. Inversion on
0151 $V_{\tau}\wake{\tau}V'_{\tau}$ by (\ref{vcpu:w1}) or (\ref{vcpu:w2})
0152 says that $V'_{\tau}=\vcpu{\tau',n,\ldots,\tau,\ldots}$. Therefore,
0153 \[
0154 \infer{\runnable{\tau, P'}}{
0155 \infer{\runnable{\tau,\pcpu{V,\ldots,V'_{\tau},\ldots}}}{
0156 \infer{\runnable{\tau,V'_{\tau}}}{
0157 \infer{\runnable{\tau,(\tau',n,\ldots,\tau,\ldots)}}{\tau=\tau}
0158 }
0159 }
0160 }
0161 \]
0162 \end{proof}
0163
0164 \begin{lma}\label{lma:preservV}
0165 If \runnable{\tau,V} and $V\sched V'$ then either \runnable{\tau,V'}
0166 or \running {\tau,V'}.
0167 \end{lma}
0168 \begin{proof}
0169 In the case of rule~(\ref{vcpu:s1}) or rule~(\ref{vcpu:s3}), if
0170 $\tau$ is first on queue then it will start running. If $\tau$ is
0171 not first in queue, then it remains runnable.
0172
0173 In the case of rule~(\ref{vcpu:s2}), if $\tau$ is currently running
0174 then it will continue running. If $\tau$ is on queue but not
0175 running, it will remain runnable.
0176 \end{proof}
0177
0178 \begin{thm}[Preservation]\label{thm:preserv}
0179 If \runnable{\tau,P} and $P\sched P'$ then either \runnable{\tau,P'}
0180 or \running{\tau, P'}.
0181 \end{thm}
0182 \begin{proof}
0183 Consider the case of rule~(\ref{pcpu:s1})
0184 \begin{equation*}
0185 \infer{\pcpu{V,V',\ldots}\sched\pcpu{V'',\ldots}}{
0186 V'\sched V'' & V''=(\tau, n, 0)
0187 }
0188 \end{equation*}
0189 If $V_{\tau}\neq V'$ then it is still on queue and still runnable.
0190 Suppose instead that $V_{\tau}=V'$, then by lemma~\ref{lma:preservV}
0191 we know that either \runnable{\tau,V''} or \running{\tau,V''}. But
0192 since $V''=\vcpu{\tau,n,0}$ we know $V''$ has an empty runqueue,
0193 therefore it must be the case that we have $\running{\tau,V''}$
0194 which implies $\running{\tau,P'}$.
0195
0196 The other possible case is rule~(\ref{pcpu:s2})
0197 \begin{equation*}
0198 \infer{\pcpu{V,V',\ldots}\sched\pcpu{V'',V'',\ldots}}{
0199 V'\sched V'' & V''=(\tau, n, \tau', \ldots)
0200 }
0201 \end{equation*}
0202 This case is similar to the previous one except that $V''$ does not
0203 have an empty runqueue. Therefore we must consider the subcase when
0204 $\runnable{\tau,V''}$. Since $V''$ appears on the queue of $P'$,
0205 property~(\ref{eq:runnableP}) applies and \runnable{\tau,P'} can be derived.
0206 \end{proof}
0207
0208 \newcommand\metric[1]{\ensuremath{\text{metric}\paren{#1}}}
0209 \renewcommand\bar\overline
0210 \begin{prop}[Induction Metric]
0211 The size of a VCPU is the length of its queue.
0212 \begin{equation}
0213 \label{eq:metric}
0214 \metric{(\tau,n,\bar\tau)}={\len{\bar\tau}}
0215 \end{equation}
0216 The size of a PCPU is double the number of VCPUs in the queue, plus
0217 the active VPCU if any.
0218 \begin{equation}
0219 \label{eq:metricV}
0220 \metric{(V,\bar V)}=2\sum_{v\in\bar V}{\metric{v}}+\len V
0221 \end{equation}
0222 The metric on a PCPU is the sum of the metrics on each queued VCPU,
0223 plus one if the PCPU is not idle. Notably,
0224 $\metric{(0,0)}=0$, in other words, the idle PCPU is the lowest
0225 metric.
0226 \end{prop}
0227
0228 \begin{lma}\label{lma:nonzerometricV}
0229 If $V\wake{\tau'}V'$ then $\metric {V'}>0$.
0230 \end{lma}
0231 \begin{proof}
0232 In the case of rule~(\ref{vcpu:w1}) the VCPU transition is
0233 $\vcpu{\tau,n,\ldots}\wake{\tau'}\vcpu{\tau,n,\ldots,\tau'}$,
0234 therefore the number of queued tasks is non-zero. In the case of
0235 rule~(\ref{vcpu:w2}) the transition is
0236 $\vcpu{\tau,n,\ldots,\tau',\ldots}\wake{\tau'}\vcpu{\tau,n,\ldots,\tau',\ldots}$
0237 and the task is already queued, therefore the metric is unchanged,
0238 and cannot be zero.
0239 \end{proof}
0240
0241 \begin{lma}\label{lma:nonzerometric}
0242 If a VCPU is on a PCPU queue then it has non-zero metric.
0243 \end{lma}
0244 \begin{proof}
0245 The only way a VCPU can arrive on a PCPU queue is through
0246 rules~(\ref{pcpu:w1}) or (\ref{pcpu:w2}), both of which require a
0247 derivation of $V\wake{\tau'}V'$, and by
0248 lemma~\ref{lma:nonzerometricV} this means $\metric{V'}>0$.
0249 \end{proof}
0250
0251 \begin{lma}
0252 \label{lma:indstepV}
0253 If $V\sched V'$ then $\metric{V'}<\metric{V}$.
0254 \end{lma}
0255 \begin{proof}
0256 In all three rules (\ref{vcpu:s1}), (\ref{vcpu:s2}), and
0257 (\ref{vcpu:s3}), the length of the queue is reduced by one,
0258 therefore, $\metric{V'}<\metric{V}$.
0259 \end{proof}
0260
0261 \begin{lma}\label{lma:indstep}
0262 If $P\sched P'$ then $\metric{P'}<\metric{P}$.
0263 \end{lma}
0264 \begin{proof}
0265 First consider rule~(\ref{pcpu:s1}) where
0266 $\pcpu{V,V',\ldots}\sched\pcpu{V'',\ldots}$. Working backwards,
0267 \begin{flalign*}
0268 \metric{\pcpu{V'',\ldots}} &< \metric{\pcpu{V,V',\ldots}} \\
0269 2\paren{\cdots} + 1 &< 2\paren{\metric{V'}+\cdots}+\len V \\
0270 1 &< 2\cdot\metric{V'} + \len V
0271 \end{flalign*}
0272 since by lemma~\ref{lma:nonzerometric}, $\metric{V'}>0$, this
0273 inequality is true regardless of $\len V$.
0274
0275 The next rule is (\ref{pcpu:s2}) where
0276 $\pcpu{V,V',\ldots}\sched\pcpu{V'',V'',\ldots}$. By inversion we
0277 find that $V'\sched V''$ and $V''=\vcpu{\tau,n,\tau',\ldots}$.
0278 Using lemma~\ref{lma:indstepV} we know that $\metric{V''}<\metric{V'}$.
0279 Working backwards,
0280 \begin{flalign*}
0281 \metric{\pcpu{V'',V'',\ldots}} &< \metric{\pcpu{V,V',\ldots}} \\
0282 2\paren{\metric{V''}+\cdots} + 1 &< 2\paren{\metric{V'}+\cdots}+\len V \\
0283 2\cdot\metric{V''} + 1 &< 2\cdot\metric{V'} + \len V
0284 \end{flalign*}
0285 Since $\metric{V''}<\metric{V'}$, this inequality is always true even
0286 if $\len V=0$.
0287
0288 Finally, rule~(\ref{pcpu:s3}) where $\pcpu{V,0}\sched\pcpu{0,0}$
0289 leads to $\metric{\pcpu{0,0}}<\metric{\pcpu{V,0}}$ which unfolds
0290 into $0<1$.
0291 \end{proof}
0292
0293 \begin{thm}[Exhaustion]\label{thm:exhaust}
0294 $P\msched (0,0)$
0295 \end{thm}
0296 \begin{proof}[Proof by induction on \metric{P}]
0297 The base case where $\metric{P}=0$ implies $P=(0,0)$ and by
0298 property~(\ref{msched:refl}) you have $(0,0)\msched (0,0)$. The
0299 interesting property is (\ref{msched:trans}). By inversion,
0300 $P\sched P'$ and $P'\msched P''$. By lemma~\ref{lma:indstep},
0301 $\metric{P'}<\metric{P}$. Therefore, by induction, $P'\msched
0302 (0,0)$. Using property~(\ref{msched:trans}) and $P\sched P'$, we
0303 arrive at $P\msched (0,0)$.
0304 \end{proof}
0305
0306 \newpage
0307 \section{VCPU}
0308 \newcommand\algorithmsize\small
0309 \paragraph{Notation.} A Sporadic Server Main VCPU $V$, for the purposes
0310 of these algorithms, consists of budget $V_b$, initial capacity $V_C$,
0311 period $V_T$, queue of replenishments $V_R$ ordered by time, and
0312 current usage $V_u$. I/O VCPUs have $V_b, V_u$ along with eligibility
0313 time $V_e$, utilization $V_U$, a single replenishment $V_r$, and
0314 boolean status of ``budgeted''. $C_{max}$ is defined as $V_T\cdot
0315 V_U$ for a given I/O VCPU. A replenishment $r$ is a pair consisting
0316 of a time $r_t$ and some amount of budget $r_b$.
0317
0318 The scheduler relies on four VCPU-specific functions: {\tt
0319 end-of-timeslice}, {\tt update-budget}, {\tt next-event}, and {\tt
0320 unblock}. The first three are used by Algorithm~\ref{alg:schedule}.
0321 The wakeup routine invokes {\tt unblock}.
0322
0323 \begin{algorithm}[!htb]
0324 \caption{\tt schedule}\label{alg:schedule}
0325 \begin{algorithmic}[1]\algorithmsize
0326 \REQUIRE $V$ is current VCPU.
0327 \REQUIRE $\bar V$ is set of runnable VCPUs.
0328 \REQUIRE $t_{cur}$ is current time.
0329 \REQUIRE $t_{prev}$ is previous time of scheduling.
0330
0331 \STATE Let $\Delta t=t_{cur}-t_{prev}$ and let $T_{prev}=V_T$.
0332 \STATE Invoke {\tt end-of-timeslice} on $V$ with $\Delta t$.
0333
0334 \STATE Find $V_{next}\in\bar V$ with highest priority and
0335 non-zero budget. Invoke {\tt update-budget} on each candidate VCPU
0336 before checking its budget.
0337
0338 \IF{there is no satisfactory $V_{next}$}
0339 \STATE Enter idle mode and go to step~\ref{sched:repltimer}.
0340 \ENDIF
0341
0342 \STATE Let $T_{next}$ be the period of $V_{next}$.
0343
0344 \STATE Select next thread for $V_{next}$.
0345 \IF{$V_{next}$ has empty runqueue}
0346 \STATE Let $\bar V'=\bar V\setminus\{V_{next}\}$
0347 \STATE $V_{next}$ is no longer runnable.
0348 \ELSE
0349 \STATE Let $\bar V'=\bar V$.
0350 \ENDIF
0351
0352 \STATE Initially let $\Delta t'$ be equal to the budget of $V_{next}$.
0353 \FOR{\label{sched:repltimer}each VCPU $v\in\bar V$ with higher priority than $V_{next}$}
0354 \STATE Let $t_e$ be the result of {\tt next-event} on $v$.
0355 \IF{$t_e$ is valid \AND $t_e-t_{cur}<\Delta t'$}\STATE Set $\Delta t':=t_e-t_{cur}$.\ENDIF
0356 \ENDFOR
0357 \STATE Set timer to go off after $\Delta t'$ has elapsed.
0358 \STATE Set $t_{prev}:=t_{cur}$ for next time.
0359 \STATE $V$ is no longer running. $V_{next}$, if valid, is now running.
0360 \STATE Switch to $V_{next}$ or idle.
0361 \ENSURE $\bar V'$ is now the set of runnable VCPUs.
0362 \end{algorithmic}
0363 \end{algorithm}
0364
0365 Algorithm~\ref{alg:schedule} is the entry point into the scheduler
0366 architecture. It performs the general work of informing the current
0367 VCPU about its usage, finding the next VCPU to run, and arranging the
0368 system timer to interrupt when the next important event occurs. The
0369 VCPU-specific functionality is delegated into the hooks {\tt
0370 end-of-timeslice}, {\tt update-budget}, and {\tt next-event}.
0371
0372 \begin{algorithm}[!htb]
0373 \caption {\tt wakeup}\label{alg:wakeup}
0374 \begin{algorithmic}[1]\algorithmsize
0375 \REQUIRE Task $\tau$.
0376 \REQUIRE $CUR$ is currently running VCPU.
0377 \REQUIRE $V$ is VCPU associated with task $\tau$.
0378 \STATE Place $\tau$ on runqueue inside $V$.
0379 \STATE Place $V$ on runqueue.
0380 \STATE Invoke {\tt unblock} on $V$.
0381 \STATE Invoke {\tt update-budget} on $V$.
0382 \IF{$V_b>0$ \AND ($CUR$ is idle \OR $CUR_T>V_T$)}
0383 \STATE Preempt and invoke scheduler.
0384 \ENDIF
0385 \end{algorithmic}
0386 \end{algorithm}
0387
0388 To cause a task and its associated VCPU to become runnable, use
0389 Algorithm~\ref{alg:wakeup}. This takes care of putting the task and
0390 VCPU on their corresponding runqueue, and then invokes any
0391 VCPU-specific functionality in hooks {\tt unblock} and {\tt
0392 update-budget}. Finally, it can preempt the running VCPU if the
0393 newly woken one is higher priority.
0394
0395 \begin{algorithm}[!htb]
0396 \caption{\tt MAIN-VCPU-end-of-timeslice}\label{alg:vcpu_eot}
0397 \begin{algorithmic}[1]\algorithmsize
0398 \REQUIRE VCPU $V$
0399 \REQUIRE Time interval consumed $\Delta t$
0400 \STATE Set $V_u:=V_u+\Delta t$.
0401 \STATE Invoke {\tt budget-check} on $V$.
0402 \IF[Blocked or preempted]{$capacity(V)>0$}
0403 \IF[Blocked]{$V$ is \NOT runnable}
0404 \STATE Invoke {\tt split-check} on $V$.
0405 \ENDIF
0406 \STATE Set $V_b:=capacity(V)$.
0407 \ELSE
0408 \STATE Set $V_b:=0$.
0409 \ENDIF
0410 \end{algorithmic}
0411 \end{algorithm}
0412
0413 \begin{algorithm}[!htb]
0414 \caption{\tt MAIN-VCPU-update-budget}\label{alg:vcpu_upbudg}
0415 \begin{algorithmic}[1]\algorithmsize
0416 \REQUIRE VCPU $V$
0417 \REQUIRE Current time $t_{cur}$
0418 \STATE Set $V_b:=max\{capacity(V), 0\}$.
0419 \end{algorithmic}
0420 \end{algorithm}
0421
0422 \begin{algorithm}[!htb]
0423 \caption{\tt MAIN-VCPU-next-event}\label{alg:vcpu_nextevent}
0424 \begin{algorithmic}[1]\algorithmsize
0425 \REQUIRE VCPU $V$
0426 \REQUIRE Current time $t_{cur}$
0427 \RETURN $\min\{r_t \mid r\in V_R\wedge t_{cur}<r_t\}$ \OR ``No event.''
0428 \end{algorithmic}
0429 \end{algorithm}
0430
0431 \begin{algorithm}[!htb]
0432 \caption{\tt MAIN-VCPU-init}
0433 \begin{algorithmic}[1]\algorithmsize
0434 \STATE $add(V_R,V_C,t_{cur})$.
0435 \end{algorithmic}
0436 \label{alg:vcpu_init}
0437 \end{algorithm}
0438
0439 The Sporadic Server policy for Main VPUs is based on that described by
0440 Stanovich et al~\cite{stanovich10}. In Algorithm~\ref{alg:vcpu_eot}
0441 the VCPU has reached the end of a timeslice, so the usage counter is
0442 updated and {\tt budget-check} is invoked to update the replenishment
0443 queue. If the VCPU has been blocked, then a partially used
0444 replenishment may need to be split into two pieces. The $capacity(V)$
0445 formula determines the amount of running time a VCPU can obtain at the
0446 current moment. This formula is defined as
0447 \begin{flalign*}
0448 head(V)&=\min_{r_t} \{r\in V_R\}\\
0449 second(V)&=\min_{r_t} \{r\in V_R \mid r \neq head(V)\}\\
0450 capacity(V)&=
0451 \begin{cases}
0452 0 & \text{if }head_t(V) > t_{cur} \\
0453 head_b(V) - V_u & \text{otherwise}
0454 \end{cases}
0455 \end{flalign*}
0456 where $head(V)$ is the earliest replenishment, and $second(V)$ is the
0457 one that follows. In Algorithm~\ref{alg:vcpu_upbudg} the capacity is
0458 integrated into the VCPU framework by writing the current value into
0459 $V_b$. For a non-running VCPU, the next possible time to run is
0460 determined by finding the next replenishment in the queue that has yet
0461 to occur, this is expressed in Algorithm~\ref{alg:vcpu_nextevent}.
0462 When a Main VCPU unblocks, it invokes {\tt unblock-check} which
0463 updates the earliest replenishment time to the present and performs
0464 any merges that become possible. Note that when Main VCPUs are
0465 created the initial replenishment must be set to the current time for
0466 the amount $V_C$ (Algorithm~\ref{alg:vcpu_init}).
0467
0468 \begin{algorithm}[!htb]
0469 \caption{\tt IO-VCPU-end-of-timeslice}\label{alg:iovcpu_eot}
0470 \begin{algorithmic}[1]\algorithmsize
0471 \REQUIRE I/O VCPU $V$
0472 \REQUIRE Time interval consumed $\Delta t$
0473 \STATE Set $V_b:=\max\{0,V_b-\Delta t\}$.
0474 \STATE Set $V_u:=V_u+\Delta t$.
0475 \IF[Blocked or budget exhausted]{$V$ is \NOT runnable \OR $V_b=0$}
0476 \STATE Set $V_e:=V_e+V_u/V_U$.
0477 \IF{$V_r$ is unused}
0478 \STATE Set $V_r:=r$ where $r_t=V_e$ and $r_b=C_{max}$.
0479 \ELSE
0480 \STATE Set $V_{r_t}:=V_e$.
0481 \ENDIF
0482 \STATE Set $V_u:=0$.
0483 \STATE Set $V_b:=0$.
0484 \IF[Blocked]{$V$ is \NOT runnable}
0485 \STATE Set $V$ as \NOT ``budgeted.''
0486 \ENDIF
0487 \ENDIF
0488 \end{algorithmic}
0489 \end{algorithm}
0490
0491 \begin{algorithm}[!htb]
0492 \caption{\tt IO-VCPU-update-budget}\label{alg:iovcpu_upbudg}
0493 \begin{algorithmic}[1]\algorithmsize
0494 \REQUIRE I/O VCPU $V$
0495 \REQUIRE Current time $t_{cur}$
0496 \IF{$V_r$ is valid \AND $V_{r_t}\leq t_{cur}$}
0497 \STATE Set $V_b:=V_{r_b}$.
0498 \STATE Invalidate $V_r$.
0499 \ENDIF
0500 \ENSURE $0\leq V_b\leq C_{max}$
0501 \end{algorithmic}
0502 \end{algorithm}
0503
0504 \begin{algorithm}[!htb]
0505 \caption{\tt IO-VCPU-next-event}\label{alg:iovcpu_nextevent}
0506 \begin{algorithmic}[1]\algorithmsize
0507 \REQUIRE I/O VCPU $V$
0508 \REQUIRE Current time $t_{cur}$
0509 \IF{$V_r$ is valid \AND $t_{cur}<V_{r_t}$}
0510 \RETURN $V_{r_t}$.
0511 \ELSE
0512 \RETURN No event.
0513 \ENDIF
0514 \end{algorithmic}
0515 \end{algorithm}
0516
0517 \begin{algorithm}[!htb]
0518 \caption{\tt IO-VCPU-unblock}\label{alg:iovcpu_unblock}
0519 \begin{algorithmic}[1]\algorithmsize
0520 \REQUIRE I/O VCPU $V$ associated with I/O task.
0521 \REQUIRE Main VCPU $M$ waiting for result of I/O task.
0522 \REQUIRE $t_{cur}$ is current time.
0523 \IF{$M_T<V_T$ \OR \NOT ($V$ is running \OR $V$ is runnable)}
0524 \STATE Set $V_T:=M_T$.
0525 \ENDIF
0526 \IF{$V$ is \NOT running \AND $V_e<t_{cur}$}
0527 \STATE Set $V_e:=t_{cur}$.\COMMENT{I/O VCPU was inactive}
0528 \ENDIF
0529 \IF{$V_r$ is invalid}
0530 \IF{$V$ is \NOT ``budgeted''}
0531 \STATE Set $V_r$ to replenish for $C_{max}$ budget at time $V_e$.
0532 \ENDIF
0533 \ELSE
0534 \STATE Set $V_{r_b}:=C_{max}$.
0535 \ENDIF
0536 \STATE Set $V$ as ``budgeted.''
0537 \end{algorithmic}
0538 \end{algorithm}
0539
0540 The I/O VCPU algorithm is known as Priority Inheritance
0541 Bandwidth-Preserving Server (PIBS). It is expressed here as a set of
0542 hooks into the VCPU scheduling framework. When an I/O VCPU finishes a
0543 timeslice, it updates its budget and usage amounts as shown in
0544 Algorithm~\ref{alg:iovcpu_eot}. Then if it was blocked or out of
0545 budget, the eligibility time is advanced and a replenishment is set
0546 for that time. Since there is only a single replenishment for an I/O
0547 VCPU, the budget can be updated easily in
0548 Algorithm~\ref{alg:iovcpu_upbudg} by checking the time. Similarly,
0549 the only possible event for a non-running I/O VCPU comes from its
0550 single replenishment, in Algorithm~\ref{alg:iovcpu_nextevent}.
0551
0552 When an I/O VCPU unblocks that means a Main VCPU requires some I/O
0553 task performed on its behalf. Therefore, the I/O VCPU adjusts its
0554 priority according to the period of that Main VCPU. This is performed
0555 with a simple comparison of priorities in
0556 Algorithm~\ref{alg:iovcpu_unblock}. Though this method could result
0557 in the I/O VCPU maintaining a higher priority than it deserves over
0558 some periods of time, if the jobs are short then that effect should be
0559 minimized. A stricter approach would track the precise moment when a
0560 higher priority VCPU was satisfied and would lower the I/O VCPU to the
0561 level of the next highest VCPU waiting. However, this requires early
0562 de-multiplexing in order to figure out when the I/O VCPU task has
0563 finished processing all I/O for a given Main VCPU, and introduces a
0564 loop into an algorithm that is otherwise constant-bounded. In order
0565 to prevent the I/O VCPU eligibility time from falling behind
0566 real-time, it is updated to the current time if the I/O VCPU is not
0567 running. Then a replenishment is posted for the I/O VCPU of $C_{max}$
0568 budget at the eligibility time. The purpose of the ``budgeted'' state
0569 is to prevent repeated job requests from replenishing the I/O VCPU
0570 beyond $C_{max}$ in budget. The ``budgeted'' state is only reset when
0571 the I/O VCPU blocks, therefore, the replenishment can only be posted
0572 in this way once per eligibility period.
0573
0574 \begin{algorithm}[!htb]
0575 \caption{\tt budget-check}
0576 \begin{algorithmic}[1]\algorithmsize
0577 \REQUIRE VCPU $V$.
0578 \IF{$capacity(V) \leq 0$}
0579 \WHILE[Exhaust and reschedule replenishments]{$head_b(V) \leq V_u$}
0580 \STATE Set $V_u:=V_u-head_b(V)$.
0581 \STATE Let $r=head(V)$.
0582 \STATE $pop(V_R)$.
0583 \STATE Set $r_t:=r_t+V_T$.
0584 \STATE $add(V_R,r)$.
0585 \ENDWHILE
0586 \IF[$V_u$ is overrun]{$V_u>0$}
0587 \STATE Set $head_t(V) := head_t(V) + V_u$.
0588 \IF[Merge]{$head_t(V)+head_b(V) \geq second_t(V)$}
0589 \STATE Let $b=head_b(V)$ and $t=head_t(V)$.
0590 \STATE $pop(V_R)$.
0591 \STATE Set $head_b(V):=head_b(V)+b$
0592 \STATE Set $head_t(V):=t$.
0593 \ENDIF
0594 \ENDIF
0595 \IF{$capacity(V)=0$}
0596 \STATE Put $V$ in background mode.
0597 \IF{$V$ is runnable}
0598 \STATE $V$ will go into foreground mode at time $head_t(V)$.
0599 \ENDIF
0600 \ENDIF
0601 \ENDIF
0602 \end{algorithmic}
0603 \label{alg:budget_check}
0604 \end{algorithm}
0605
0606 \begin{algorithm}[!htb]
0607 \caption{\tt split-check}
0608 \begin{algorithmic}[1]\algorithmsize
0609 \REQUIRE VCPU $V$.
0610 \REQUIRE Current time $t_{cur}$.
0611 \IF{$V_u>0$ \AND $head_t(V)\leq t_{cur}$}
0612 \STATE Let $remnant=head_b(V)-V_u$.
0613 \ENSURE $capacity(V)=remnant$.
0614 \IF[Push remnant into next]{$V_R$ is full}
0615 \STATE $pop(V_R)$.
0616 \STATE Set $head_b(V):=head_b(V)+remnant$.
0617 \ELSE
0618 \STATE Set $head_b(V):=remnant$.
0619 \ENSURE $capacity(V)=capacity(V)-V_u$.
0620 \ENDIF
0621 \STATE $add(V_r, V_u, head_t(V)+V_T)$.
0622 \STATE Set $V_u:=0$.
0623 \ENSURE $capacity(V)=capacity(V)$.
0624 \ENDIF
0625 \end{algorithmic}
0626 \label{alg:split_check}
0627 \end{algorithm}
0628
0629 \begin{algorithm}[!htb]
0630 \caption{\tt unblock-check}
0631 \begin{algorithmic}[1]\algorithmsize
0632 \REQUIRE VCPU $V$.
0633 \REQUIRE Current time $t_{cur}$.
0634 \IF{$capacity(V) > 0$}
0635 \STATE $V$ should be in foreground mode.
0636 \STATE Set $head_t(V):=t_{cur}$.
0637 \COMMENT{Advance earliest replenishment to now.}
0638 \WHILE{$\left|V_R\right|>1$}
0639 \STATE Let $b:=head_b(V)$.
0640 \IF[Merge]{$second_t(V)\leq t_{cur}+b-V_u$}
0641 \STATE $pop(V_R)$.
0642 \STATE Set $head_b(V):=head_b(V)+b$ and set $head_t(V):=t_{cur}$.
0643 \ELSE
0644 \RETURN
0645 \ENDIF
0646 \ENDWHILE
0647 \ELSE
0648 \STATE $V$ will go into foreground mode at time $head_t(V)$.
0649 \ENDIF
0650 \end{algorithmic}
0651 \label{alg:unblock_check}
0652 \end{algorithm}
0653
0654 Algorithms~\ref{alg:budget_check}, \ref{alg:split_check}, and
0655 \ref{alg:unblock_check} are based on Stanovich et
0656 al~\cite{stanovich10}. These listings include fixes to minor errors
0657 we discovered in the original description.
0658
0659 \end{document}
