page 1  (128 pages)
2to next section

Destage Algorithms for Disk Arrays with Non-Volatile Caches

Anujan Varma and Quinn Jacobson

Computer Engineering Department

University of California

Santa Cruz, CA 95064

Abstract

In a disk array with a nonvolatile write cache, destages

from the cache to the disk are performed in the background

asynchronously while read requests from the host system

are serviced in the foreground. In this 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 disks based on the instantaneous occupancy

of the write cache. The performance of the algorithm is

compared with that of a number of alternative 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 re-

quests from the host, disk utilization, and their ability to

tolerate bursts in the workload without causing an overflow

of the write cache. Our results show that linear threshold

scheduling provides the best read performance of all the al-

gorithms compared, while still maintaining a high degree

of burst tolerance. An approximate implementation of the