2.3. Disk Scheduling for SM Display

2.3.1. Simple Technique

We make the following simplifying assumptions:

To support continuous display of an object X, it is partitioned into n equi-sized blocks: X₀, X₁, …, X_n–1, where n is a function of the block size (B) and the size of X. We assume a block is laid out contiguously on the disk and is the unit of transfer from disk to main memory. The time required to display a block is defined as a time period (T_p):

Equation 2.3

With this technique, when an object X is referenced, the system stages X₀ in memory and initiates its display. Prior to completion of a time period, it initiates the retrieval of X₁ into memory in order to ensure a continuous display. This process is repeated until all blocks of an object have been displayed.

To support simultaneous displays of several objects, a time period is partitioned into fixed-size slots, with each slot corresponding to the retrieval time of a block from the disk drive. The number of slots in a time period defines the number of simultaneous displays that can be supported by a disk drive. Figure 2.6 demonstrates the concept of time period and time slots. Each box represents a block reading time. Assuming that each block is stored contiguously on the surface of the disk, the disk incurs a seek every time it switches from one block of an object to another. We denote this as T_{w_Seek} and assume that it includes the average rotational latency time of the disk drive. We will not discuss rotational latency further because it is a constant added to every seek time.

Since the blocks of different objects are scattered across the disk surface, a simple technique (Simple [137]) should assume the maximum seek time (i.e., Seek(#cyl)^[9]) when multiplexing the bandwidth of the disk among multiple displays. Otherwise, a continuous display of each object cannot be guaranteed. As in Figure 2.6, the following equation should be satisfied to support N_simple simultaneous display.

^[9] We define Seek(#cyl) as a full stroke that is the time to reposition the disk head from the outermost cylinder to the innermost one.

Equation 2.4

Equation 2.5

For a fixed block size, the maximum number of simultaneous displays that a disk can support is:

Equation 2.6

The optimal block size to support N_simple can be obtained when the left side of Eq. 2.5 equals to T_p:

Equation 2.7

When $MB and $DISK denote the price of main memory, $ per MByte, and the price of a single disk drive, respectively, the cost per stream (CPS) of this technique is:

Equation 2.8

The maximum startup latency observed by a request with this technique is:

Equation 2.9

This is because a request might arrive a little too late to employ the empty slot in the current time period. Note that ℓ_simple is the maximum startup latency (the average latency is ) when the number of active users is N_simple – 1. If the number of active displays exceeds N_simple then Eq. 2.9 should be extended with appropriate queuing models.

2.3.2. Disk Bandwidth Utilization and Performance

Seek is a wasteful operation that minimizes the number of simultaneous displays supported by a disk. To retrieve N blocks, the disk performs N seeks during a time period, where T_{w_seek} = Seek(d). Hence, the percentage of time that disk performs wasteful work can be quantified as: , where d is the maximum distance between two blocks retrieved consecutively (d = #cyl with Simple). By substituting T_p from Eq. 2.3, we obtain the percentage of wasted disk bandwidth:

Equation 2.10

By reducing this percentage, the system can support a higher number of simultaneous displays. We can manipulate two factors to reduce this percentage: 1) decrease the distance traversed by a seek, and/or 2) increase the block size. A limitation of increasing the block size is that it results in a higher memory requirement. However, if one can decrease the duration of the seek time, then the same number of simultaneous displays can be supported with smaller block sizes because the size of a block is proportional to Seek(d) for a given N (see Eq. 2.7). This will save some memory. Briefly, for a fixed number of simultaneous displays, as the duration of the worst seek time decreases (increases) the size of the block shrinks (grows) proportionally with no impact on throughput. This impacts the amount of memory required to support N displays. For example assume: Seek(#cyl) = 17 msec, R_D = 68 Mb/s, R_C = 4 Mb/s, and N = 15. From Eq. 2.7, we compute a block size of 1.08 MByte that wastes 12% of the disk bandwidth. If a display technique reduces the worst seek time by a factor of two, then the same throughput can be maintained with a block size of 0.54 MByte, reducing the amount of required memory by a factor of two and maintaining the percentage of wasted disk bandwidth at 12%. Moreover, the startup latency reduces from 2.16 seconds to 1.08 seconds.

2.3.3. SCAN

One approach to reduce the worst seek time is scheduling of the disk bandwidth for multiple block retrievals in a time period. One can apply a SCAN algorithm [168], [131] for the block retrievals during a time period. The system sorts the order of block retrievals during a time period based on the location of blocks in a disk. The movement of the disk head to retrieve the blocks during a time period abides by the SCAN algorithm, in order to reduce the incurred seek times among retrievals. However, a hiccup may happen if the system initiates the display of a block immediately after its retrieval as in Simple. This is because the time elapsed between two consecutive block retrievals can be greater than a time period. In order to prevent hiccups, the displays of all the blocks retrieved during the current time period must start at the beginning of the next time period. Figure 2.7 demonstrates a continuous display with SCAN. The blocks W_i, X_j, …, Z_k are retrieved during the first time period. The displays of these blocks are initiated at the beginning of the next time period.

Eq. 2.5 and 2.7 still hold with SCAN but with a reduce seek time, . Thus, the block size to support N_SCAN simulstaneous displays with SCAN is:

Equation 2.11

SCAN requires two buffers for a display because a block is displayed from one buffer while the next block is being retrieved from the disk into the other buffer. Thus, the cost per stream is:

Equation 2.12

The maximum startup latency happens when a request arrives just after a SCAN begins in the current time period and the retrieval of the first block is scheduled at the end of the next time period. Thus, it is:

Equation 2.13

2.3.4. Grouped Sweeping Scheme (GSS)

A more general scheduling technique is Grouped Sweeping Scheme [182], GSS. GSS groups N active requests of a time period into g groups. This divides a time period into g subcycles, each corresponding to the retrieval of blocks. Across the groups there is no constraint on the disk head movement. To support the SCAN policy within a group, GSS shuffles the order that the blocks are retrieved. For example, assuming X, Y, and Z belong to a single group, the sequence of the block retrieval might be X₁ followed by Y₄ and Z₆ (denoted as X₁ → Y₄ → Z₆) during one time period, while during the next time period it might change to Z₇ → X₂ → Y₅. In this case, the display of (say) X might suffer from hiccups because the time elapsed between the retrievals of X₁ and X₂ is greater than one time period. To eliminate this possibility, [182] suggests the following display mechanism: the displays of all the blocks retrieved during subcycle i start at the beginning of subcycle i + 1. To illustrate, consider Figure 2.8 where g = 2 and N = 4. The blocks X₁ and Y_l are retrieved during the first subcycle. The displays are initiated at the beginning of subcycle 2 and last for two subcycles. Therefore, while it is important to preserve the order of groups across the time periods, it is no longer necessary to maintain the order of block retrievals in a group.

The maximum startup latency observed with this technique is the summation of one time period (if the request arrives when the empty slot is missed) and the duration of a subcycle :

Equation 2.14

By comparing Eq. 2.14 with Eq. 2.9, it may appear that GSS results in a higher latency than Simple. However, this is not necessarily true because the duration of the time period is different with these two techniques due to a choice of different block size. The duration of a time period is a function of the block size.

To compute the block size with GSS, we first compute the total duration of time contributed to seek times during a time period. Assuming blocks retrieved during a subcycle are distributed uniformly across the disk surface, the disk incurs a seek time of Seek (i.e., T_{w_Seek} = Seek between every two consecutive block retrievals. Since N_gss blocks are retrieved during a time period, the system incurs N_gss seek times in addition to N_gss block retrievals during a time period, i.e., T_p = + N_gss × Seek. By substituting T_p from Eq. 2.3 and solving for B_gss, we obtain:

Equation 2.15

By comparing Eq. 2.15 with Eq. 2.7, observe that the bound on the distance between two blocks retrieved consecutively is reduced by a factor of , noting that g ≤ N_gss.

GSS is a generalization of different techniques. Observe that g = N simulates Simple (by substituting g with N in Eq. 2.15, it reduces to Eq. 2.7). And g = 1 simulates SCAN.