MITRA Introduction -- PM-driven Scheduling

Go backward to Multi-Zone Disks
Go up to One Disk Configuration

PM-driven Scheduling

The disk service time required to retrieve N blocks of N active displays might be shorter than a time period. This is because of the concept of a logical zone where: 1) the transfer rate of this zone is assumed to equal the transfer rate of the slowest participating physical zone, and 2) the N blocks reside in the fastest physical zone (by luck) of the logical zone. When this happens, the Scheduler may either (1) busy-wait until the end of the time period or (2) proceed with the retrieval of blocks that should be retrieved during the next time period. With the latter, the Scheduler starts to produces data at a faster rate on behalf of a PM. This motivates an implementation of a PM-driven scheduling paradigm where the Scheduler accepts skip messages from a PM when the PM starts to run out of memory.

With this paradigm, a PM maintains a data buffer with a low and a high water mark. These two water marks are a percentage of the total memory available to the PM. Once the high water mark is reached, the PM generates a skip message to inform the Scheduler that it should not produce data on behalf of this PM for a fixed number of time periods (say Y time periods). Y must be a multiple of the number of logical zones recognized on a disk (otherwise, Y is rounded to (Y)/(m) ). This is due to the round-robin assignment of blocks of each object to the zones where a display cannot simply skip one zone when m > 1. The number of time periods is dependent on the amount of data that falls between the low and high water marks, i.e., the number of blocks cached. It must correspond to at least one sweep of the zones (T_scan) to enable the PM to issue a skip message. During the next Y time periods, the Scheduler produces no data on behalf of the PM while the display consumes data from buffers local to the PM. After Y time periods, the Scheduler starts to produce data for this PM.

The choice of a value for the low and high water marks at the PM are important. The difference between the total available memory and the high water mark should be at least one block. This is because of the race condition that might arise due to networking delays between the PM and the Scheduler. For example, the Scheduler might produce a block for the PM at the same time that the PM is generating the skip message. Similarly, the low water mark should not be zero (its minimum value must be one block). This would eliminate the possibility of the PM running out of data (resulting in hiccups) due to networking delays.

When the Scheduler receives a skip message from a PM, it might employ the idle slot to perform house keeping activities, i.e., migrate sections in support of the bounded list length property. If no such activity is required, the idle slot of a time period might be handled in two possible ways, either (1) busy-wait for the duration of the skipped time slot or (2) proceed with the retrieval of blocks that should be retrieved during the next time period. The second strategy would cause the Scheduler to produce data at a faster rate for the other active PMs, forcing them to generate skip messages. This minimizes the average startup latency of the system as detailed in the Evaluation Section.