Illustrative Example

Suppose a $500$ kB read-request has to seek $20,000$ cylinders requiring $T_{seek}$ of $14$ ms, must wait for a $T_{rot}$ of $7$ ms, and requires $T_{transfer}$ of $25$ ms at a transfer rate of $20$ MBps. The expected waiting time, $E(T_{waiting})$, for a higher-priority request arriving during the execution of this request, is $23$ ms, while the maximum waiting time is $46$ ms (please refer to Section 3 for equations). Semi-preemptible IO can reduce the waiting time by performing the following operations.

It first predicts both the seek time and rotational delay. Since the predicted seek time is long ( $T_{seek} = 14$ ms), it decides to split the seek operation into two sub-seeks, each of $10,000$ cylinders, requiring $T'_{seek} = 9$ ms each. This seek splitting does not cause extra overhead in this case because the $T_{rot} = 7$ can mask the $4$ ms increased total seek time ( $2 \times T'_{seek} - T_{seek} = 2 \times 9 - 14 = 4$). The rotational delay is now $T'_{rot} = T_{rot} - (2 \times T'_{seek} - T_{seek}) = 3$ ms.

With this knowledge, the disk driver waits for $3$ ms before performing a JIT-seek. This JIT-seek method makes $T'_{rot}$ preemptible, since no disk operation is being performed. The disk then performs the two sub-seek disk commands, and then $25$ successive read commands, each of size $20$ kB, requiring $1$ ms each. A higher-priority IO request could be serviced immediately after each disk-command. Semi-preemptible IO thus enables preemption of an originally non-preemptible read IO request. Now, during the service of this IO, we have two scenarios:

• No higher-priority IO arrives. In this case, the disk does not incur additional overhead for transferring data due to disk prefetching (discussed in Sections 3.1 and 3.4). (If $T_{rot}$ cannot mask seek-splitting, the system can also choose not to perform seek-splitting.)
• A higher-priority IO arrives. In this case, the maximum waiting time for the higher-priority request is now a mere $9$ ms, if it arrives during one of the two seek disk commands. However, if the ongoing request is at the stage of transferring data, the longest stall for the higher-priority request is just $1$ ms. The expected value for waiting time is only $\frac{1}{2}~\frac{2 \times 9^2 + 25 \times 1^2 }{2 \times 9 + 25 \times 1 + 3}= 2.03$ ms, a significant reduction from $23$ ms (refer to Section 3 for details).

This example shows that Semi-preemptible IO substantially reduces the expected waiting time and hence increases the preemptibility of disk access. However, if an IO request is preempted to service a higher-priority request, an extra seek operation may be required to resume service for the preempted IO. The distinction between IO preemptibility and IO preemption is an important one. Preemptibility enables preemption, but incurs little overhead itself. Preemption will always incur overhead, but it will reduce the service time for higher-priority requests. Preemptibility provides the system with the choice of trading throughput for short response time when such a tradeoff is desirable. We explore the effects of IO preemption further, in Section 4.3.