Semi-preemptible IO

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:

• A logical disk block is the smallest unit of data that can be accessed on a disk drive (typically $512$ B). Each logical block resides at a physical disk location, depicted by a physical address (cylinder, track, sector).

• A disk command is a non-preemptible request issued to the disk over the IO bus (e.g., the read, write, seek, and interrogative commands).

• An IO request is a request for read or write access to a sequential set of logical disk blocks.

• The waiting time is the time between the arrival of a higher-priority IO request and the moment the disk starts servicing it.

Figure 1: Timing diagram for a disk read request.

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 $T_{seek}$ time. Then, the disk must wait for a rotational delay, denoted by $T_{rot}$, so that the target disk block comes under the disk arm. The final stage is the data transfer stage, requiring a time of $T_{transfer}$, 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

$$E(T_{waiting}) = \frac{1}{2} (T_{seek}+T_{rot}+T_{transfer}).$$ (1)

Let $V_i$ be the sequence of fine-grained disk commands we use to service an IO request. Let the time required to execute disk-command $V_i$ be $T_i$. Let $T_{idle}$ 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 $i^{th}$ command $V_i$ can be expressed as $p_i = \frac{T_i}{\sum T_i + T_{idle}}$. Finally, the expected waiting time of a higher-priority request in Semi-preemptible IO can be expressed as

$$E(T'_{waiting}) = \frac{1}{2} \sum (p_i T_i) = \frac{1}{2} \frac {\sum T^2_i} {(\sum T_i + T_{idle}) }.$$ (2)

In the remainder of this section, we present 1) chunking, which divides $T_{transfer}$ (Section 3.1); 2) just-in-time seek, which enables $T_{rot}$ preemption (Section 3.2); and 3) seek splitting, which divides $T_{seek}$ (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).