Cache Management Algorithms for Flexible Filesystems?

Silvano Maffeis

[email protected]

Computer Science Department University of Zurich

Winterthurerstr. 190, CH-8057 Zurich, Switzerland

IFI TR 93:03y

Abstract

Cache management in flexible filesystems deals with the problem of determining a cached file to be replaced when the local cachespace is exhausted. In analogy to virtual memory management, several different algorithms exist for managing cached files. In this paper we simulate the behavior of First-In-First-Out (FIFO), Least Recently Used (LRU), Least Frequently Used (LFU) and a variation of LFU we call the File Length Algorithm (LEN) from the viewpoint of file access times, cache hit ratios and availability. The results of several simulation runs are presented and interpreted.

Keywords: Cache Management, File Access, Flexible Filesystems, Replication

1 Introduction

For virtual storage management, Denning [4] developed a view of program paging activity called the workingset model. The workingset model is based on the assumption of locality of reference. The idea is to examine the most recent ? page-references of a process P. The set of pages accessed by the most recent ? page-references is the workingset WP of process P.

In this paper we simulate and analyze some well known page replacement algorithms [1] and the workingset model from the viewpoint of a flexible filesystem (FFS) [13]. In this context, we will use the term FFS cache replacement algorithm (FFS-CRA). In FFS, client workstations are attached to several file servers from which they obtain replicas of the needed files. We will assume that clients always obtain a full replica and not only a part of a file. This in analogy to filesystems like Andrew [12] or Coda [5] where only entire files are cached. In FFS problems similar to those encountered in virtual memory management arise, since the decision must be made which locally cached copy of a file to discard when the cache is full and an uncached file is referenced.

Replacement strategies and the workingset model are two well known research areas in the field of virtual memory management and have extensively been studied for many years. In conjunction with cache management in FFS, following novel aspects must be considered by a FFS-CRA:

Coarse granularity: Objects referenced in FFS may encompass few kilobytes to several megabytes of data. In contrast, virtual memory management systems handle much smaller objects, usually memory pages

?This work was supported by Siemens AG, ZFE, Germany and Schweizer Bundesamt fur Konjunkturfragen, Grant No. 2255:1
yto appear in ACM SIGMETRICS Performance Evaluation Review, Vol. 21, No. 3