Thrashing control and avoidance for concurrent mergesorts using parallel prefetching

Abstract

Prefetching pages in parallel via multiple disks can be attractive in reducing the response times for concurrent mergesorts. However, due to imbalances between the rates of reads and writes, severe buffer thrashing may develop; i.e., prefetched pages in the buffer can be replaced before referenced. In this paper, we study various runtime thrashing control and avoidance policies for concurrent merges using parallel prefetching, where initial sorted runs of a merge job are stored on multiple disks and the final sorted run is written back to another dedicated disk. We evaluate through detailed simulations two thrashing control and one thrashing avoidance policies. For the thrashing control policies, if the number of nonreplaceable buffer pages reaches a predefined threshold, two different actions can be taken: (a) disabling prefetching and (b) forcing synchronous writes. Thrashing can be reduced by the two thrashing control policies, but it is completely eliminated by the thrashing avoidance policy. Instead of a predefined threshold, the thrashing avoidance policy forces synchronous writes if the sum of dirty buffer pages and those that are needed for prefetching is about to reach the buffer capacity. The results show that (1) buffer thrashing can severely degrade the system response time; (2) depending on the workload and threshold values, the two thrashing control policies may not improve the system response time even though they can reduce thrashing; and (3) the thrashing avoidance policy is most effective in both eliminating thrashing and improving the system response time.