2.4. Constrained Data Placement
This study introduces a REgion BasEd bloCk Allocation (REBECA) mechanism that reduces Tw_Seek by: 1) partitioning the disk space into R regions, and 2) forcing the system to retrieve the block of N active requests from a single region. By reducing the worst seek time, some of the disk bandwidth is freed to retrieve additional blocks per time period, providing for a higher number of simultaneous displays (throughput). However, with a fixed amount of memory, the latency increases as the number of regions (R) is increased. Hence, it is crucial to use a planner to determine a value for the configuration parameters of a single disk multimedia server to realize a pre-specified throughput and latency time requirement.
The seek time is a function of the distance that the disk head travels from its current track to the track that contains the referenced block. Hence, the worst possible seek time depends on the longest distance between the two blocks that could potentially be retrieved after each other. For example, assume the jth block of object X (Xj) should be retrieved after the ith block of object W (Wi) as in Figure 2.7. If the blocks of an object are assigned to the available disk space in a random manner then the worst seek time (Tw_Seek) depends on the distance between the first and the last cylinder of the disk (longest_d). However, if the placement of Xj and Wi are controlled such that their distance is at most d, where d < longest_d, then Tw_Seek is reduced. By reducing the seek time (wasteful work), the disk can spend more of its time transferring data (useful work), resulting in a higher throughput.
REBECA increases the throughput using the above observation. Assuming that N blocks of N different objects can be retrieved and displayed in one time period (Tp), its design is as follows. First, REBECA partitions the disk space into R regions. Next, successive blocks of an object X are assigned to the regions in a zigzag manner as shown in Figure 2.9. The zigzag assignments follows the efficient movement of disk head as in the elevator algorithm [169]. To display an object, the disk head moves inward (see Figure 2.10) until it reaches the innermost region and then it moves outward. This procedure repeats itself once the head reaches the out-most region on the disk. This minimizes the movement of the disk head required to simultaneously retrieve N objects because the display of each object abides by the following rules:
The disk head moves in one direction (either inward or outward) at a time.
For a given time period, the disk services those displays that correspond to a single region (termed active region, Ractive).
In the next time period, the disk services requests corresponding to either Ractive + 1 (inward direction) or Ractive – 1 (outward direction). The only exception is when Ractive is either the first or the last region.
In these two cases, Ractive is either incremented or decremented after two time periods because the consecutive blocks of an object reside in the same region. For example, in Figure 2.9, X5 and X6 are both allocated to the last region and Ractive changes its value after two time periods. This scheduling paradigm does not waste disk space (an alternative assignment/schedule that enables Ractive to change its value after every time period would waste 50% of the space managed by the first and the last region). Note that for two regions (i.e., R. = 2) the above scheduling paradigm is not necessary and the blocks should be assigned in a round-robin manner to the regions.
Upon the arrival of a request referencing object X, it is assigned to the region containing X0 (say Rx).
The display of X does not start until the active region reaches X0 (Ractive = Rx) and its direction corresponds to that required by X. For example, X requires an inward direction if X1 is assigned to Rx+1 and outward if RX – 1 contains X1 (assuming that the organization of regions on the disk is per Figure 2.10).
Figure 2.9. REBECA.
Figure 2.10. Disk head movement.
To compute the worst seek time with REBECA, let b denote the number of blocks per region. The worst seek time during one time period is a function of b, because the blocks within a region are at most b blocks apart. However, across the time periods the worst seek time is a function of 2 x b. To observe consider Figure 2.7. The last scheduled object during time period i (Zk in Figure 2.7) can be 2 x b blocks apart from the first scheduled object during time period i + 1 (Wi+1 in Figure 2.7). This is because Zk and Wi+1 reside in two different regions. Hence, the worst seek time across the time periods is the time required for the disk head to skip 2 × b blocks. However, without REBECA, in the worst case the two blocks can be R × b blocks apart, where R × b is the total number of blocks in the disk drive. Note that even for R = 2 the total seek time is reduced. This is because the seek time within a time period is still a function of b for N – 1 requests and 2 × b for the last one.
Introducing regions to reduce the seek time increases the average latency time observed by a request. This is because during each time period the system can initiate the display of only those objects that correspond to the active region and whose assignment direction corresponds to that of the current direction of the arm. To illustrate this, consider Figure 2.11. In Figure 2.11.a, Y is stored starting with R2, while the assignment of both X and Z starts with R0. Assume that the system can support three simultaneous displays (N = 3). Moreover, assume a request arrives at time T1, referencing object X. This causes region R0 to become active. Now, if a request arrives during T1 referencing object Y, it cannot be serviced until the third time period even though sufficient disk bandwidth is available (see Figure 2.11.b). Its display is delayed by two time periods until the disk head moves to the region that contains Y0 (R2).
In the worst case, assume: 1) a request arrives referencing object Z when Ractive = R0, 2) both the first and the second block of object Z (Z0 and Z1) are in region 0 (Rz = R0) and the head is moving inward, and 3) the request arrives when the system has already missed the empty slot in the time period corresponding to R0 to retrieve[10] Z0. Hence, 2 × R + 1 time periods are required before the disk head reaches R0, in order to start servicing the request. This is computed as the summation of: 1) R+ 1 time periods until the disk head moves from R0 to the last region, and 2) R time periods until the disk head moves from the last region back to R0 in the reverse direction. Hence, the maximum latency time (ℓ) is computed as
[10] An intelligent scheduling policy might prevent this scenario.
Equation 2.16
Note that ℓ is the maximum latency time (the average latency is 
) when the number of active users is less than N; otherwise, Eq. 2.16 should be extended with appropriate queuing models.
An interesting observation is that the computed latency time (ℓ in Eq. 2.16) is not observed for recording of live[11] objects. That is, if N sessions of multimedia objects are recorded live, the transfer of each stream from memory to the disk can start immediately. This is because the first block of an object X can be stored starting with any region. Hence, it is possible to start its storage from the active region (i.e. Ractive ← RX).
[11] Recording a live session is similar to taping a live football game. In this case, a video camera or a compression algorithm is the producer and the disk drive is the consumer.
In summary, partitioning the disk space into regions using REBECA is a tradeoff between throughput and latency time.