A cache replacement algorithm improves upon a least recently used algorithm by differentiating between cache lines that have been written with those that have not been written. The replacement algorithm attempts to replace cache lines that have been previously written back to memory, and if there are no written cache lines available, then the algorithm attempts to replace cache lines that are currently on page and on bank.