Section 1.4.4: Input and Output

Exercise 19. [M28] Special considerations arise when input or output involves short blocks on a rotating device like a magnetic disk. Suppose a program works with $n \geq 2$ consecutive blocks of information in the following way: Block $k$ begins to be input at time $t_k$, where $t_1 = 0$. It is assigned for processing at time $u_k \geq t_k + T$ and released from its buffer at time $v_k = u_k + C$. The disk rotates once every $P$ units of time, and its reading head passes the start of a new block every $L$ units; so we must have $t_k \equiv (k - 1)L \pmod P$. Since the processing is sequential, we must also have $u_k \geq v_{k-1}$ for $1 < k \leq n$. There are $N$ buffers, hence $t_k \geq v_{k-N}$ for $N \leq k < n$.

How large does $N$ have to be so that the finishing time $v_n$ has its minimum possible value, $T + C + (n - 1)\max(L, C)$? Give a general rule for determining the smallest such $N$. Illustrate your rule when $L = 1$, $P = 100$, $T = .5$, $n = 100$, and (a) $C = .5$; (b) $C = 1.0$; (c) $C = 1.01$; (d) $C = 1.5$; (e) $C = 2.0$; (f) $C = 2.5$; (g) $C = 10.0$; (h) $C = 50.0$; (i) $C = 200.0$.

Verified: no
Solve time: -

---

Setup

Let

$$ M=\max(L,C). $$

The minimum possible finishing time is stated to be

$$ v_n=T+C+(n-1)M. \tag{1} $$

To attain (1), the processor must never be idle after block 1 becomes available. Hence the processing times must be

$$ u_k=T+(k-1)M,\qquad v_k=T+C+(k-1)M \tag{2} $$

for $1\le k\le n$.

Indeed, $u_1\ge T$, and every block requires $C$ units of processing. Since successive starting times satisfy

$$ u_k\ge u_{k-1}+C, $$

when $C>M$ they cannot be closer than $C$, and when $L>M$ the blocks themselves cannot become available more frequently than every $L$ units. Thus (2) is the unique schedule realizing the lower bound (1).

The problem is therefore to determine the smallest number of buffers $N$ for which there exist input times $t_k$ satisfying

$$ t_k\equiv (k-1)L \pmod P, \tag{3} $$

$$ t_k+T\le u_k=T+(k-1)M, \tag{4} $$

and

$$ t_k\ge v_{k-N} \qquad (N\le k<n). \tag{5} $$

Equation (4) is equivalent to

$$ t_k\le (k-1)M. \tag{6} $$

For each $k$, among all numbers congruent to $(k-1)L$ modulo $P$, the latest one not exceeding $(k-1)M$ is

$$ t_k=(k-1)L-P,m_k, \tag{7} $$

where

$$ m_k= \left\lceil \frac{(k-1)(L-M)}{P} \right\rceil . \tag{8} $$

These choices maximize every $t_k$ and therefore minimize the required number of buffers.

Solution

A block occupies a buffer from time $t_k$ until time $v_k$. Hence, at time $t_k$, all blocks

$$ j<k $$

with

$$ v_j>t_k $$

are still occupying buffers.

Let

$$ B_k=#{,j<k: v_j>t_k,}. \tag{9} $$

Then exactly $B_k$ buffers are already occupied when block $k$ begins to be read, so the smallest feasible number of buffers is

$$ N = 1+\max_{1\le k\le n} B_k . \tag{10} $$

Using (2),

$$ v_j=T+C+(j-1)M. \tag{11} $$

Therefore

$$ v_j>t_k \iff (j-1)M> \frac{t_k-T-C}{M}. $$

The smallest index $j$ satisfying this inequality is

$$ j_0= \left\lfloor \frac{t_k-T-C}{M} \right\rfloor+2. $$

Hence

$$ B_k = (k-1)-\max(0,j_0-1) = (k-1) - \max!\left( 0, \left\lfloor \frac{t_k-T-C}{M} \right\rfloor+1 \right). \tag{12} $$

Equations (7), (10), and (12) give a complete rule for determining the smallest admissible $N$.

A more transparent form results when $L\le C$, the case of all numerical examples below. Then $M=C$, and (8) becomes

m_k= \left\lceil -\frac{(k-1)(C-L)}{P} \right\rceil = -\left\lfloor \frac{(k-1)(C-L)}{P} \right\rfloor . ] Thus

t_k

(k-1)L

P\left\lfloor

\frac{(k-1)(C-L)}{P}

\right\rfloor .

\tag{13}

$$ Write $$

(k-1)(C-L)=Pq+r,

\qquad 0\le r<P.

$$ Then (13) yields $$

t_k=(k-1)C-r.

]

Substituting into (12),

$$ B_k = \left\lceil \frac{r+T}{C} \right\rceil . \tag{14} $$

Hence

$$ N = 1+ \max_{0\le r<P} \left\lceil \frac{r+T}{C} \right\rceil . \tag{15} $$

Only those residues $r$ that actually occur as

$$ r\equiv (k-1)(C-L)\pmod P, \qquad 0\le k<n, \tag{16} $$

need be considered.

Now specialize to

$$ L=1,\qquad P=100,\qquad T=.5,\qquad n=100. $$

Since $0\le k-1\le 98$, the residues arising from (16) are computed directly in each case.

(a) $C=.5$

Here $M=L=1$. Taking $t_k=(k-1)$ gives

$$ v_j=.5+.5+(j-1)=j. $$

At time $t_k=k-1$, only block $k-1$ has not yet been released. Thus $B_k=1$ for $k>1$ and

$$ N=2. $$

(b) $C=1.0$

Again $M=1$ and $t_k=k-1$.

Now

$$ v_j=1.5+(j-1). $$

At time $k-1$, only block $k-1$ remains in memory. Therefore

$$ N=2. $$

(c) $C=1.01$

Now $C-L=.01$.

For $0\le k-1\le 98$,

$$ r=.01(k-1), $$

so

$$ 0\le r\le .98. $$

By (14),

$$ B_k= \left\lceil \frac{r+.5}{1.01} \right\rceil . $$

The maximum occurs at $r=.98$:

$$ \left\lceil \frac{1.48}{1.01} \right\rceil = 2. $$

Hence

$$ N=3. $$

(d) $C=1.5$

Now $C-L=.5$.

The residues are

$$ r=.5m,\qquad 0\le m\le 98, $$

reduced modulo $100$; thus the largest occurring residue is $49$.

Equation (14) gives

$$ \max B_k = \left\lceil \frac{49.5}{1.5} \right\rceil = 33. $$

Therefore

$$ N=34. $$

(e) $C=2.0$

Now $C-L=1$.

The residues are

$$ 0,1,\ldots,98. $$

Hence

$$ \max B_k = \left\lceil \frac{98.5}{2} \right\rceil = 50, $$

and

$$ N=51. $$

(f) $C=2.5$

Now $C-L=1.5$.

The residues are

$$ 1.5m\pmod{100}, \qquad 0\le m\le 98. $$

Since $1.5=3/2$, multiplying by $2$ shows that the largest residue attained before $m=99$ is $98.5$.

Therefore

$$ \max B_k = \left\lceil \frac{99}{2.5} \right\rceil = 40, $$

and

$$ N=41. $$

(g) $C=10.0$

Now $C-L=9$.

The residues are

$$ 9m\pmod{100}, \qquad 0\le m\le 98. $$

Since $\gcd(9,100)=1$, every residue modulo $100$ occurs. Thus the largest is $99$.

Hence

$$ \max B_k = \left\lceil \frac{99.5}{10} \right\rceil = 10, $$

and

$$ N=11. $$

(h) $C=50.0$

Now $C-L=49$.

Since $\gcd(49,100)=1$, every residue modulo $100$ occurs.

Therefore

$$ \max B_k = \left\lceil \frac{99.5}{50} \right\rceil = 2, $$

and

$$ N=3. $$

(i) $C=200.0$

Now $M=C=200$.

Because

$$ u_k=T+200(k-1), $$

the processor is the bottleneck. A block occupies a buffer for approximately $200.5$ time units, while successive read requests are separated by $200$ units. Consequently at most one earlier block remains buffered when a new one is read.

Indeed, from (14),

$$ \max B_k = \left\lceil \frac{99.5}{200} \right\rceil = 1. $$

Hence

$$ N=2. $$

Therefore the required numbers of buffers are

$$ \boxed{ \begin{array}{c|c} C & N\ \hline 0.5 & 2\ 1.0 & 2\ 1.01 & 3\ 1.5 & 34\ 2.0 & 51\ 2.5 & 41\ 10.0 & 11\ 50.0 & 3\ 200.0 & 2 \end{array}} $$

Verification

For each case, the value of $N-1$ equals the largest number of previously read blocks whose release times exceed a later admissible reading time. Formula (10) counts exactly those simultaneously occupied buffers. With this $N$, condition (5) is satisfied for every $k$; with any smaller value, some $t_k$ would occur before a required buffer had been released. Therefore the computed $N$ is both sufficient and necessary.

This completes the proof.

∎

Notes

The quantity governing the buffer requirement is not the ratio $C/L$ alone. The arithmetic progression

$$ (k-1)(C-L)\pmod P $$

determines how closely the desired processing schedule can be matched to the disk's rotational opportunities. The large values for $C=1.5$ and $C=2.0$ arise because the residues remain far from $100$, causing many blocks to accumulate before a favorable rotational position recurs.