DESTAGE ALGORITHMS FOR DISK ARRAYS WITH NONVOLATILE CACHES

In a disk array with a nonvolatile write cache, destages from the cach e to the disk are performed in the background asynchronously while rea d requests from the host system are serviced in the foreground. In thi s paper, we study a number of algorithms for scheduling destages in a RAID-5 system. We introduce a new scheduling algorithm, called linear threshold scheduling, that adaptively varies the rate of destages to d isks based on the instantaneous occupancy of the write cache. The perf ormance of the algorithm is compared with that of a number of alternat ive scheduling approaches, such as least-cost scheduling and high/low mark. The algorithms are evaluated in terms of their effectiveness in making destages transparent to the servicing of read requests from the host, disk utilization, and their ability to tolerate bursts in the w orkload without causing an overflow of the write cache. Our results sh ow that linear threshold scheduling provides the best read performance of all the algorithms compared, while still maintaining a high degree of burst tolerance. An approximate implementation of the linear-thres hold scheduling algorithm is also described. The approximate algorithm can be implemented with much lower overhead, yet its performance is v irtually identical to that of the ideal algorithm.