For the class of replacement algorithms known as stack algorithms, existing analysis techniques permit the computation of memory miss ratios for all memory sizes simultaneously in one pass over a memory reference string. We extend the class of computations possible by this methodology in two ways. First, we show how to compute the effects of copy-backs in write-back caches. The key observation here is that a given block is clean for all memory sizes less than or equal to C blocks and is dirty for all larger memory sizes. Our technique permits efficient computations for algorithms or systems using periodic write-back and/or block deletion. The second extension permits stack analysis simulation for sector (or subblock) caches in which a sector (associated with an address tag) consists of subsectors (or subblocks) that can be loaded independently. The key observation here is that a subsector is present only in caches of size C or greater. Load forward prefetching in a sector cache is shown to be a stack algorithm and is easily simulated using our technique. Running times for our methods are only slightly higher than for a simulation of a single memory size using nonstack techniques.

Article Free Access Share on A trace-driven analysis of the UNIX 4.2 BSD file system Authors: John K. Ousterhout Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CA Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CAView Profile , Hervé Da Costa Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CA Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CAView Profile , David Harrison Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CA Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CAView Profile , John A. Kunze Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CA Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CAView Profile , Mike Kupfer Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CA Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CAView Profile , James G. Thompson Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CA Computer Science Division, Electrical Engineering and Computer Sciences, University of California, Berkeley, CAView Profile Authors Info & Claims SOSP '85: Proceedings of the tenth ACM symposium on Operating systems principlesDecember 1985 Pages 15–24https://doi.org/10.1145/323647.323631Published:01 December 1985Publication History 390citation1,640DownloadsMetricsTotal Citations390Total Downloads1,640Last 12 Months127Last 6 weeks18 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF