Real‐time integrated prefetching and caching

Real‐time integrated prefetching and caching

0.00 Avg rating0 Votes
Article ID: iaor20131946
Volume: 16
Issue: 1
Start Page Number: 47
End Page Number: 58
Publication Date: Feb 2013
Journal: Journal of Scheduling
Authors: , ,
Keywords: computers: data-structure, combinatorial optimization, heuristics
Abstract:

The high latencies for access to background memory like hard disks or flash memory can be reduced by caching or hidden by prefetching. We consider the problem of scheduling the resulting I/Os when the available fast cache memory is limited and when we have real‐time constraints where for each requested data block we are given a time interval during which this block needs to be in main memory. We give a near linear time algorithm for this problem which produces a feasible schedule whenever one exists. Another algorithm additionally minimizes I/Os and still runs in polynomial‐time. For the online variant of the problem, we give a competitive algorithm that uses lookahead and augmented disk speed. We show a tight relationship between the amount of lookahead and the speed required to get a competitive algorithm.

Reviews

Required fields are marked *. Your email address will not be published.