# Response time of a fixed-head disk to transfers of variable length

Erol Gelenbe, Jacques Lenfant, Alexandre Brandwajn, Dominique Potier

► To cite this version:

Erol Gelenbe, Jacques Lenfant, Alexandre Brandwajn, Dominique Potier. Response time of a fixed-head disk to transfers of variable length. [Research Report] IRIA-RR-038, IRIA. 1973, pp.20. hal-04715929

HAL Id: hal-04715929

https://inria.hal.science/hal-04715929v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

laboratoire de recherche
en informatique
et automatique

response time of a fixed-
head disk to transfers
of variable length

A.Brandwanj, D.Potier

E.Gelenbe, J.Lenfant

ZoP

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n° 38

novembre 1973
RESPONSE TIME OF A FIXED-HEAD DISK
TO TRANSFERS OF VARIABLE LENGTH

E. Gelenbe, J. Lenfant, A. Brandwajn, D. Potier

ABSTRACT

Due to the practical complexity of addressing variable length records placed in arbitrary locations of a fixed-head disk (or drum), and because of the difficulty of managing secondary memory space in such cases, variable length records are often stored with their first address at a fixed location of the magnetic support. We present a queueing model of such a scheme, assuming a Poisson arrival stream and arbitrarily distributed record lengths. The stationary probability distribution of the number of transfer requests in queue and the expected response time is obtained. Numerical examples illustrating the results are presented.

TEMPS DE REPONSE D'UN DISQUE A TETES FIXES
POUR DES ENREGISTREMENTS DE LONGUEUR VARIABLE

RESUME

A cause de la complexité pratique de l'adressage des enregistrements de longueur variable situés à des emplacements quelconques d'un disque à têtes fixes, et aussi parce qu'il est dans ce cas difficile de gérer l'espace de mémoire secondaire, ou stocke souvent les enregistrements de longueur variable à des emplacements fixes sur le support magnétique. Nous présentons un modèle à files d'attente d'une telle organisation en supposant que les arrivées des requêtes au disque constituent un processus de Poisson et que les longueurs des enregistrements suivent une loi quelconque. Une chaine de Markov incluse dans le processus stochastique qui caractérise le modèle est obtenue par un choix convenable de variables supplémentaires. La distribution stationnaire de probabilité du nombre de demandes de transfert en attente et l'espérance mathématique du temps de réponse sont obtenus. Les exemples numériques présentés permettent de comparer ce système avec un modèle dans lequel une politique d'emplacements arbitraires est appliquée.
RESPONSE TIME OF A FIXED-HEAD
DISK TO VARIABLE-LENGTH TRANSFERS

E. GELENBE, J. LENFANT, A. BRANDWAJN, D. POTIER

# I - INTRODUCTION

Even though the trend in modern computer systems is to replace rotating secondary memory devices by core or semiconductor memories, drums and more particularly fixed head disks remain in wide usage while assuring important input-output functions in newer systems. The analysis of their performance remains of interest also because newer "rotating" memory devices such as magnetic bubble memories retain some of their information accessing and transfer characteristics.

The purpose of this paper is to analyze the response time of fixed-head (as opposed to moveable arm) rotating secondary memory devices when the length of the records to be transferred obeys some arbitrary distribution function and when the records are transferred in FCFS order. The method of analysis of such devices, and the results obtained, will depend to a large extent on the scheduling algorithm used as well as on the nature of the transfers. Thus Coffman (1) has examined the behaviour of a drum whose circumference is divided into equal sized sectors each containing a page, and for which page transfers are requested singly (as opposed to batched requests). In his model, the drum (or fixed-head disk) is scheduled using the Eschenbach scheme (2) with one queue per sector. In (3), an algorithm for optimally scheduling variable length transfers for a drum has been given, and it has been shown that it is a solution of a special case of the travelling salesman problem. A comparison of the algorithm in (3) with the classical SLTF (short-test-latency-time-first) algorithm has been presented by STONE and FULLER (5).
In this paper, in addition to our assumption of arbitrarily distributed length of records to be transferred, we also suppose that the starting address on the drum is at a fixed angular position on the circumference for all records. This is a realistic assumption in many cases. Many computer operating systems adopt this policy because of the great ease and simplicity it implies. The records to be transferred in such a system might be segments, file records or groups of pages belonging to the same program or system module for which "pre-paging" is used.

In the sequel, we shall obtain the long run probability distribution for the number of requests waiting for transfer in the system we have described and use it to compute the expected response time of the disk with the assumptions we have made regarding its operation, the arrival process of requests for transfers is assumed to be Poisson and the length of each transfer obeys an arbitrary distribution with finite first and second moments.
## II - THE MODEL

The system we wish to analyze is shown in Figure 1. A fixed starting address, at a given angular position, is established on the surface of the fixed-head disk (or drum, henceforth called the *disk*) for all records. For the cylindrical drum this address would correspond to a line, along the axis of rotation, on its surface. Concentric circles on the disk correspond to tracks. Even though the physical length of the tracks diminishes as the center of the disk is approached, they all contain the same number of words. A record beginning on one track, may span several of them.

The length of records to be transferred are independent and identically distributed random variables with an arbitrary distribution function $F(x)$ having finite first and second moments. We shall define the probability $r_n$ that a record is transferred in n rotations of the disk, beginning from its starting address :

$$ (1) \qquad \begin{aligned} r_n &= \text{Prob} \left( (n-1) T < x \le nT \right) \\ &= F(Tn) - F(T(n-1)), \quad n=1,2,\dots \end{aligned} $$

where T is the time necessary for one complete disk rotation. We have implicitly assumed that the length x of a record is given in units of time, and that it is equal to the time necessary for the disk heads to move from its starting address to its ending address.

We assume that the interarrival times of transfer requests are independent and identically distributed random variables with distribution function

$$ G(t) = 1 - e^{-\lambda t} $$

so that the probability of k arrivals in time T is

$$ (2) \qquad a_k = e^{-\lambda T} \frac{(\lambda T)^k}{k!}, \quad k=0,1,2,\dots $$
At an instant of time t, let M(t) be the number of requests awaiting transfer (including the record being transferred). The process {M(t)} is not a Markov chain, unless F(x) is an exponential distribution function. Since we cannot compute directly the distribution of M(t), let us adjoin the supplementary variable N(t) to M(t) and consider the process {M(t), N(t)}, where the disk revolution for the record being transferred is the N(t)-th. {M(t), N(t)} is not, in the general case, a Markov chain either. We may consider, however, the Markov chain C imbedded in {M(t), N(t)} at times t, t = qT, q=0,1,..., just after the heads pass over the starting address marker of the disk. For convenience, we say that N(t) is undefined when M(t) = 0.

The state of C takes the following values :

$$0 \quad \text{if} \quad M(qT) = 0$$

(m,n) if M(qT) = m > 0 and the disk revolution starting at qT is the n-th for the record being transferred,

for q = 0,1,2,... and n=1,2,...

That C is a Markov chain is easily verified. Its transition probabilities are obtained as follows :

$$(3) \qquad \mathrm{Pr} (0|0) = a_0$$

$$(4) \qquad \mathrm{Pr} ((m,1)|0) = a_m, \quad m \ge 1$$

where Pr (v|u) is the probability of entering state v of C at time (q+1)T given that the chain is in state u at qT. We also have :

$$(5) \qquad \mathrm{Pr} ((m,n)|(m-j,n-1)) = a_j c_{n-1} \quad \text{for } m \ge 1, n \ge 2, o \le j \le m$$

$$(6) \qquad \mathrm{Pr} ((m,1)|(m-j+1,n)) = a_j (1-c_n) \quad \text{for } m \ge 1, n \ge 1, 0 \le j \le m.$$
$$ (7) \qquad \Pr(0|(1,n)) = a_0(1-c_n) $$

where

$$ (8) \qquad c_n = \Pr \left( x > \underline{T}_n | x > \underline{T}(n-1) \right) \\ = \frac{1-\underline{F}(\underline{T}_n)}{1-\underline{F}(\underline{T}(n-1))} $$

Notice that we also have

$$ (9) \qquad c_n = \frac{\sum_{j=n+1}^{\infty} r_j}{\sum_{j=n}^{\infty} r_j} $$

The transition probabilities are zero for all cases not covered by equations (3) to (7).

If i,j are states of C (i,j ∈ {0} ∪ ({m,n} where m ≥ 1, n ≥ 1), let
Π(i,j,q) be the q-step transition probability of C from i to j.
From (4) we know that

$$ \Pi_j = \lim_{q \to \infty} \Pi(i,j,q) $$

exists and is independent of i if

(a) C is aperiodic and irreducible and

(b) There exist numbers $\Pi_i > 0$ satisfying the equations

$$ \sum_{\text{all } i} \Pi_i = 1 $$

$$ \Pi_j = \sum_{\text{all } i} \Pi_i \Pi(i,j,1), \text{ for each } j $$

That C is aperiodic and irreducible is easily verified : it suffices to
show, using (3) to (7), that there exists an integer k > 0 such that

$$ \Pi(i,j,q) > 0 $$
for all $q \ge k$ (4), for all i,j. If (a) and (b) are satisfied, we say
that C is ergodic.

**Theorem 1**

Denote $\Pi_i$ by $\gamma(m,n)$ if $i=(m,n)$ and by $\gamma(0)$ if $i=0$. If
$E\{n\} \lambda T < 1$, where

$$
E \{ n \} = \sum_{n=1}^{\infty} n r_n
$$

then C is ergodic and

$$
\gamma(0) = 1 - \lambda T \mathbb{E} \{ n \}
$$

Furthermore, $P_n(z)$ the generating function

$$
P_n(z) = \sum_{m=1}^{\infty} \gamma(m,n) z^m
$$

is given by

$$
P_n(z) = (1-F((n-1)T)) P_1(z) (A(z))^{n-1}
$$

for $n \ge 1$, where

$$
A(z) = \sum_{k=0}^{\infty} a_k z^k = e^{-\lambda T} (1-z)
$$

$a_k$ being given by (2). Also

$$
P_1(z) = \gamma(0)z \left[ \frac{A(z)-1}{z-R(A(z))} \right]
$$

where

$$
R(z) = \sum_{n=1}^{\infty} r_n z^n
$$
Theorem 1, as well as the next result we present, will be proved in
later sections.

The result we give above yields the joint probability distribution,
at the stationary state, for the number of records awaiting transfer and
for the index of the current revolution for the record being transferred, at
instants of time right after the disk heads pass over the starting address.
We would also like to have information regarding the number of records awai-
ting transfer at <u>any</u> instant of time. For this purpose, we proceed as follows.

Let $p_m(u)$ be the stationary probability of finding $m$ records
waiting to be transferred at instants of time $qT + uT$, $q=0,1,2,...$, where
$0 \le u < 1$. Let $P(z,u)$ be the generating function

$$
(10) \qquad P(z,u) = \sum_{m=0}^{\infty} p_m(u) z^m
$$

Consider the function P(z) defined as the mean of P(z,u)
over the interval [0,1].

$$
P(z) = \int_{0}^{1} P(z,u) du
$$

The expected number of requests awaiting for transfer (including the
one being transferred) at an arbitrary instant of time is then $E[M]$, given
by

$$E \{ M \} = \lim_{z \to 1} \frac{d}{dz} P(z)$$

**Theorem 2**

If $\lambda T E \{n\} < 1$, then

$$E \{ M \} = \lambda T \left( E \{ \ell \} + \frac{1}{2} \right) + \frac{(\lambda T)^2}{2} \frac{E \{ n^2 \}}{1 - \lambda T E \{ n \}}$$

where, $\ell$ being the length of a transfer, $\ell$ is given by

$$\ell = \frac{x}{T}$$

and

$$E\{n^2\} = \sum_{n=1}^{\infty} n^2 r_n$$

### III - PROOF OF THEOREM 1

We omit the proof that $C$ is aperiodic and irreducible. We shall only show that there exist numbers $\Pi_i > 0$ satisfying the equations

$$\sum_{\text{all } i} \Pi_i = 1$$

and

$$\Pi_j = \sum_{\text{all } i} \Pi_i \Pi(i,j,1)$$

for each $j$ under the conditions stated in Theorem 1. Adopting the notations of Theorem 1, we have

$$(11) \qquad \gamma(0) = a_0 \gamma(0) + \sum_{n=1}^{\infty} a_n (1-c_n) \gamma(1,n)$$

from (3) and (7). (4) and (6) yield for $m \ge 1$

$$(12) \qquad \gamma(m,1) = a_m \gamma(0) + \sum_{j=0}^{m} \sum_{n=1}^{\infty} a_j (1-c_n) \gamma(m-j+1,n)$$
Finally, from (5) we have

$$
(13) \qquad \gamma(m,n) = \sum_{j=0}^{m-1} a_j c_{n-1} \gamma(m-j,n-1)
$$

for m ≥ 1, n > 1.

We now use these equations to compute the generating functions P_n(z) :

$$
P_n(z) = \sum_{m=1}^{\infty} \gamma(m,n) z^m
$$

From (11) and (12) we have

$$
(14) \quad z[\gamma(0) + P_1(z)] = a_0 \gamma(0)z + \sum_{n=1}^{\infty} a_0 z(1-c_n)\gamma(1,n) + \sum_{m=1}^{\infty} z^{m+1}(a_m\gamma(0) + \sum_{j=0}^{m} \sum_{n=1}^{\infty} a_j(1-c_n)\gamma(m-j+1,n)) = z\gamma(0)A(z) + \sum_{n=1}^{\infty} (1-c_n)A(z)P_n(z)
$$

Using (13), we obtain for n > 1

$$
P_n(z) = \sum_{m=1}^{\infty} \sum_{j=0}^{m-1} a_j c_{n-1} \gamma(m-j, n-1) z^m
$$

yielding

$$
P_n(z) = c_{n-1} A(z) P_{n-1}(z), \quad n=2,3,\dots
$$

which when solved gives us for n > 1

$$
(16) \quad P_n(z) = \genfrac{[}{]}{0pt}{}{n-1}{\Pi} c_j P_1(z) (A(z))^{n-1}
$$

Notice that by (8) we have

$$
\sum_{j=1}^{n-1} c_j = 1 - F(T(n-1))
$$

so that P_n(z) is of the form

$$
(17) \quad P_n(z) = (1 - F(T(n-1))) P_1(z) (A(z))^{n-1}
$$

which was to be shown.
From (14) we obtain

$$P_1(z) = A(z) \left( \gamma(0) + \frac{1}{z} \sum_{n=1}^{\infty} (1-c_n) P_n(z) \right) - \gamma(0)$$

and using (17)

$$\sum_{n=1}^{\infty} (1-c_n)P_n(z) = P_1(z) \sum_{n=1}^{\infty} (1-F(T(n-1))) (1-c_n) (A(z))^{n-1}$$

But (1) and (8) yield

$$(1 - F(T(n-1))) (1 - c_n) = r_n$$

and

$$R(A(z)) = \sum_{n=1}^{\infty} r_n (A(z))^n$$

Therefore $P_1(z)$ is of the form

$$(18) \quad P_1(z) = \gamma(0)A(z) + \frac{1}{z} P_1(z)R(A(z)) - \gamma(0)$$

$$= z \gamma(0) \left[ \frac{A(z)-1}{z-R(A(z))} \right]$$

which was to be shown. To obtain $\gamma(0)$ we use the equality

$$\gamma(0) + \lim_{z \to 1} \sum_{n=1}^{\infty} P_n(z) = 1$$

which means that the sum over all states of stationary probabilities is 1.

Using (17) we have

$$\lim_{z \to 1} \sum_{n=1}^{\infty} P_n(z) = P_1(1) \sum_{n=1}^{\infty} (1-F(T(n-1)))$$

$$= P_1(1) \sum_{n=1}^{\infty} \left(1 - \sum_{j=1}^{n-1} r_j\right)$$

$$= P_1(1) \sum_{n=1}^{\infty} \sum_{j=n}^{\infty} r_j$$

$$= P_1(1) \sum_{n=1}^{\infty} n r_n$$
Therefore

$$ \gamma(0) = 1 - E \{n\} P_1(1) $$

We compute $P_1(1)$ from (18) applying l'Hôpital's rule to obtain

$$ P_1(1) = \gamma(0) \frac{\lambda T}{1 - \lambda T E \{n\}} $$

Finally

$$ \gamma(0) = 1 - \lambda T E \{n\} $$

To insure ergodicity we must have $\gamma(0) > 0$, therefore the condition

$$ \lambda T E \{n\} < 1 $$

must be satisfied.

## IV - PROOF OF THEOREM 2

Consider the generating function $P(z,u)$ defined in (10). $p_m(u)$ is given by the following equation, in which $a_j(u)$ is the probability of j arrivals in time $uT$:

$$ (19) \quad p_m(u) = \gamma(0)a_m(u) + \sum_{n=1}^{\infty} \sum_{k=1}^{m} (1-g_n(u))\gamma(k,n)a_{m-k}(u) + \sum_{n=1}^{\infty} \sum_{k=1}^{n} g_n(u)\gamma(k,n)a_{m-k+1}(u) $$

where $g_n(u)$, the probability that a transfer is no longer than $T(n-1+u)$ given that it is longer than $T(n-1)$, is given by

$$ (20) \quad g_n(u) = \frac{F(T(n-1+u)) - F(T(n-1))}{1-F(T(n-1))} $$

Let $A_u(z)$ be the generating function

$$ (21) \quad A_u(z) = \sum_{j=0}^{\infty} a_j(u) z^j = e^{\lambda T u (z-1)} $$

Then $P(z,u)$ is obtained from (19) and (21) as

$$ (22) \quad P(z, w) = \gamma(0)A_u(z) + \sum_{n=1}^{\infty} (1-g_n(u))A_u(z)P_n(z) + \sum_{n=1}^{\infty} g_n(w)A_u(z) \frac{P_n(w)}{z} $$
and

$$ (23) \qquad E \{ M \} = \lim_{z \to 1} \int_{0}^{1} \frac{\partial}{\partial z} P(z, u) du $$

Notice that

$$ \lim_{z \to 1} \frac{d}{dz} A_u(z) = \lambda T u $$

and that

$$ \sum_{n=1}^{\infty} P_n(1) = 1 - \gamma(0) $$

Using these relations, we obtain after some algebra that

$$ E \{ M \} = \frac{\lambda T}{2} + \sum_{n=1}^{\infty} \frac{d}{dz} P_n(z) |_{z=1} - \int_{0}^{1} du \sum_{n=1}^{\infty} g_n(u) P_n(1) $$

Notice from Theorem 1 and (21) that

$$ P_n(1)g_n(u) = (F(T(n-1+u)) - F(T(n-1))) P_1(1) $$

and

$$ \int_{0}^{1} du \, P_{n}(1) g_{n} = P_{1}(1) \int_{n-1}^{n} (F(yT) - F((n-1)T)) dy $$

We also have

$$ \begin{aligned} \sum_{n=1}^{\infty} \int_{0}^{1} du \, P_n(1) g_n(u) &= P_1(1) \left( - \sum_{n=1}^{\infty} \int_{n-1}^{n} (1-F(yT))dy + \sum_{n=1}^{\infty} (1-F((n-1)T))) \right) \\ &= \lambda T \left( - \int_{0}^{\infty} (1-F(yT))dy + \sum_{n=1}^{\infty} n G(n) \right) \end{aligned} $$

where we have used $P_1(1) = \lambda T$ and where

$$ G(n) = F(nT) - F((n-1)T) $$

is the probability that a transfer will be complete during its n-th rotation, and we have used the fact that

$$ 1-F((n-1)T) = \sum_{m=n}^{\infty} G(m) $$
Notice that

$$
\begin{align*}
\int_0^\infty (1-F(yT)) dy &= \int_0^\infty \frac{du}{T} (1-F(u)) \\
&= \left. \frac{u}{T} (1-F(u)) \right|_0^\infty \\
&+ \int_0^\infty \frac{u}{T} dF(u)
\end{align*}
$$

is obtained by a change of variables and an integration by parts. This yields

$$
\int_{0}^{\infty} (1 - F(yT)) \, dy = E\{\ell\}
$$

where x being the length of a transfer, l is given by
l = x/T

We now have

$$
E \{ M \} = \frac{\lambda T}{2} + \lambda T E \{ \ell \} - \lambda T E \{ n \} + \sum_{n=1}^{\infty} \frac{j}{d} z P_{n}(z) \bigg|_{z=1}
$$

The remaining algebra to complete the proof of theorem 2 is straightforward,
and we omit presenting it here.

V - NUMERICAL EXAMPLES AND CONCLUSIONS.

In this paper, we have analyzed the behaviour of a fixed-head disk
or drum used for storing variable length records. The initial address of
each record corresponds to a fixed angular position on the disk surface
(or drum circumference). This placement method has considerable advantages
over "optimal" scheduling methods because it simplifies the addressing
problems of the secondary memory device.

It is also known that SLTF or optimal schedules for variable length
records cannot be implemented efficiently unless special hardware features,
which are often non-existent on commercially available equipment, are
installed. The major disadvantage of the policy we have analyzed seems to
be the wastage in disk space which may be incurred, although it avoids the
complicated placement algorithms one would use if an attempt were made to
minimize wasted space on disk.

As we shall presently see via some numerical examples, there are
cases in which our placement algorithm produces a lower average response
time than that for a "random" placement policy of records on the disk. A
rigorous comparison of the algorithm we analyze with the SLTF or "optimal"
(3) policy remains to be done.

Suppose that records are transferred on a FCFS basis from the disk,
and that they are located at random on the disk surface. The appropriate
model in this case is the M/G/1 queue (4) with a service time which is the
sum of two independent random variables : an access time A uniformly
distributed between 0 and T, and a transfer time x with distribution
function F(x). By a straightforward application of the formula of Pollaczek
and Khintchine we obtain the disk response time as :

$$
(24) \qquad W_R = T \left( E \{ \ell \} + \frac{1}{2} + \lambda T \frac{E \{ \ell \} + \frac{1}{3} + E \{ \ell^2 \}}{2 \left( 1 - \lambda T \left( \frac{1}{2} + E \{ \ell \} \right) \right)} \right)
$$

Using Little's formula and Theorem 2 we obtain the expected response time
for the algorithm we have analyzed :

$$
(25) \quad W_F = T \left( E \{ \ell \} + \frac{1}{2} + \lambda T \frac{E \{ n^2 \}}{2(1 - \lambda T E \{ n \})} \right)
$$

In figure 3 we plot W<sub>F</sub> and W<sub>R</sub> versus λ for the record lengths distributed
according to the density function given in Figure 2. In this case W<sub>F</sub> is appre-
ciably better than W<sub>R</sub>. It would be interesting to characterize the class
of probability distributions F(x) for which W<sub>F</sub> ≤ W<sub>R</sub>.
<figure><img src="image_2.png" /><figcaption>a) FIXED-HEAD DISK</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Figure 1</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>Figure 2</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 3</figcaption></figure>
REFERENCES

(1) E.G. COFFMAN, Analysis of a Drum Input/Output Queue under Scheduled Operation in a Paged Computer System, J. ACM, vol. 16, n°1 (1969), pp. 73-90.

(2) A. WEINGARTEN, The Eschenbach Drum Scheme, Comm. ACM, vol. 9, n°7 (1966), pp. 509-512.

(3) S. FULLER, An optimal Drum Scheduling Algorithm, IEEE Transactions on Computers, vol. C-21, n°11 (1972), pp. 1153-1165.

(4) W. FELLER, An Introduction to Probability Theory and its Applications, vol. 1, 3rd ed., John Wiley, New York (1968).

(5) H.S. STONE and S.H. FULLER, On the Near-Optimality of the Shortest-Latency-Time-First Drum Scheduling Discipline, Comm. ACM, vol.16, n°6 (1973), pp. 352-353.