Before introducing the concept of Semi-preemptible IO, we first define some terms which we will use throughout the rest of this paper. Then, we propose an abstraction for disk IO, which enables preemption of IO requests. Finally, we present our disk profiler and the disk parameters required for the implementation of Semi-preemptible IO.
Definitions:
In order to understand the magnitude of the waiting time, let us
consider a typical read IO request, depicted in Figure 1.
The disk first performs a seek to the destination
cylinder requiring time. Then, the disk must wait for a
rotational delay, denoted by
, so that the
target disk block comes under the disk arm. The final stage
is the data transfer stage, requiring a time of
, when
the data is read from the disk media to the disk buffer. This data is
simultaneously transferred over the IO bus to the system memory.
For a typical commodity system, once a disk command is issued on the IO bus, it cannot be stopped. Traditionally, an IO request is serviced using a single disk command. Consequently, the operating system must wait until the ongoing IO is completed before it can service the next IO request on the same disk. Let us assume that a higher-priority request may arrive at any time during the execution of an ongoing IO request with equal probability. The waiting time for the higher-priority request can be as long as the duration of the ongoing IO. The expected waiting time of a higher-priority IO request can then be expressed in terms of seek time, rotational delay, and data transfer time required for ongoing IO request as
Let be the sequence of fine-grained disk commands we use
to service an IO request. Let the time required to execute
disk-command
be
. Let
be the duration of time
during the servicing of the IO request, when the disk is idle (i.e.,
no disk command is issued).
Using the above assumption that the higher-priority request
can arrive at any time with equal probability, the probability that it
will arrive during the execution of the
command
can
be expressed as
.
Finally, the expected waiting time of a higher-priority
request in Semi-preemptible IO can be expressed as
In the remainder of this section, we present 1) chunking,
which divides
(Section 3.1);
2) just-in-time seek, which enables
preemption
(Section 3.2); and
3) seek splitting, which divides
(Section 3.3).
In addition, we present our disk profiler, Diskbench,
and summarize all the disk parameters required for the
implementation of Semi-preemptible IO (Section 3.4).