• Sign In / Register
  • Language
    • English
    • Deutsch
    • Française
    • Español
    • Português
    • Italia
    • Русский
    • 日本語
    • 한국어
    • 简体中文
    • 繁體中文

This article explains the request scheduling algorithm of MEMS storage devices in detail.

  • January 25, 2021
  • 89

MEMS (MicroElectromechanical System, Micro Electromechanical System) memory is a new type of storage device that has the characteristics of high density, low power consumption, non-volatile, multi-probe parallel access, etc., and has obvious advantages over traditional disks. It can fill the performance gap between RAM and disk, and can play multiple roles in computer systems, bringing new ideas and new methods to the research of new high-performance mass storage system structure.

MEMS.png

Request scheduling algorithm for MEMS storage devices

(1) Disk request scheduling algorithm

The first is the simplest and worst-performing first-come, first-served (FCFS): the second algorithm is CLOOKLBN. This algorithm is to serve in ascending LBN order, that is, when all requested LBNs lag behind the currently requested LBN, the service starts from the request involving the smallest LBN: the third is the shortest addressing time first ( sSTF-BN), the main idea is to select the request with the smallest addressing delay, but it is rarely used in practical applications. Because few host operating systems have information for calculating actual addressing distance or predicting addressing time, considering the mapping relationship between disk LBN and physical location, most SSTF algorithms use the most recently accessed LBN and target LBN The distance between is used as an approximation of the access time. This simplification is effective for disks: the fourth is the shortest positioning time priority algorithm (SPTF), which selects the request with the smallest positioning delay. For disks, the SPTF algorithm and other algorithms The significant difference is that it needs to consider seek time and rotation delay.

Four scheduling algorithms are applied to Atalalok, and the response time of Atlas10k under different request arrival frequencies of random loads is calculated. The performance of FCFS is the worst among the four scheduling algorithms. At the same time, the performance of FCFS reaches saturation the fastest as load requests increase. The performance of SSTFesLBN is better than CLOOKLBN, the performance of SPTF is the best, and the speed of SPTF performance reaching saturation is the slowest.

The first three scheduling algorithms ((FCFSCLOOKLBN and SSTFesLBN) can be implemented simply and effectively using the host's software system. Taking into account the mapping relationship between the disk LBN and the physical location, the implementation of these three scheduling algorithms does not require detailed device information, only according to the request LBN number to select the request to be served. The SPTF algorithm is usually implemented in the firmware of the disk drive. The SPTF algorithm requires accurate information about the disk state, mapping information from LBN to physical location, accurate prediction information for addressing time and rotation delay, etc. .

(2) MEMS storage device request scheduling algorithm

In order to conveniently apply MEMS storage devices to computer systems, MEMS storage devices use the same interface as disks. In order to prove that the existing disk request scheduling algorithm is also applicable to MEMS storage devices, the four disk request scheduling algorithms in the previous section are applied to MEMS storage devices. Most request scheduling algorithms, such as SSTFLBN and CLOOKLBN, only need to know the LBN information, and use the distance between LBNs as an estimate of the positioning time. The SPTF algorithm involves addressing time and rotation delay. However, MEMS storage devices only have addressing in the x-axis and Y-axis directions, and there is no rotation delay. Same as the disk, the addressing time is one-dimensional, close to a linear LBN space. Unlike the magnetic disk, the addressing of the MEMS storage device in both directions is done in parallel, and the larger one is chosen as the actual addressing time. Since there is a stable time in the x-axis direction, the addressing time in the x-axis direction is always greater than that in the Y-axis. If the addressing time of the Y axis is relatively large, the performance of SPTF is only slightly better than SSTF. Use Disksim. The scheduling algorithm of the disk is applied to the MEMS storage device, and the average response time under the random load of different request arrival frequencies is calculated.

The four scheduling algorithms have similar performance to disks on MEMS storage devices: FCFS has the worst performance and SPTF has the best performance. However, the gap between FCFS and LBN-based algorithms is smaller than that of disks. Because the addressing time in MEMS storage devices accounts for a large proportion of the entire service time. The performance gap between CLOOKLBN and SSTFLBN is smaller than that of disks.

Three data layout strategy

(1) Small-grained non-sequential access

MEMS storage device data access has similar characteristics to disks, and short-distance addressing is faster than long-distance addressing. Different from the magnetic disk, due to the restoring force of the spring, the effect of the force of the actuator at different positions is different. The influence of spring force on different positions of each TIp's access area. The force of the spring increases with the increase of the sled displacement, but the positioning time is longer for short distances. Therefore, when considering finding small-granularity and commonly used data items, in addition to the addressing distance, the distance between the sled and the center position must also be considered.

(2) Large-granularity sequential access

The streaming rates of MEMS storage devices and disks are similar: Atals10K has a streaming rate of 17,3-25, 2MB/s, and MEMS storage devices have a streaming rate of 75,9MB/s. The positioning time of MEMS storage devices is an order of magnitude lower than that of magnetic disks. For MEMS storage devices, positioning time has little effect on mass data transmission. For example: the service time of a 256KB read request at different positions on the X-axis, the service time difference between different requests of 1250 cylinders is only 10%. At the same time, it reduces the need for locality of large-granularity and sequential data transmission. However, for the disk, the addressing distance is an important factor affecting the addressing time. Similarly, for a 256KB request, the long-distance addressing time can double the entire service time.

(3) Two-way data layout

In order to make full use of the access characteristics of MEMS storage devices, a two-way layout strategy is introduced. The small data is stored in the small area in the middle, and the large, sequential stream data is stored in the small area on the periphery. This strategy can be implemented in a 5X5 grid.

On the assumption that there is no correlation within each request, compare the performance of a bidirectional layout, an "organpipe" layout, and an optimized disk layout. In the "organpipe" layout strategy, the most frequently accessed files are stored on the middle track of the disk, the less frequently used files are stored on both sides of the middle track, and the least frequently used files are stored near the innermost and outermost tracks. On the track. This layout strategy is optimized for disks. The disadvantage is that files need to be moved regularly according to the frequency of use of the files, and some status of the files need to be maintained to record the frequency of use of the files.


Select Your Location