Outline for Today s Lecture Administrative Objective Focus in on File Buffer Cache Why Are File Caches Effective 1 Locality of reference storage accesses come in clumps spatial locality If a process accesses data in block B it is likely to reference other nearby data soon e g the remainder of block B example reading or writing a file one byte at a time temporal locality Recently accessed data is likely to be used again 2 Read ahead if we can predict what blocks will be needed soon we can prefetch them into the cache most files are accessed sequentially File Buffer Cache Proc Memory File What do we cache want to cache inodes dir nodes whole files disk blocks The answer will determine where in the request path the cache sits V M Virtual memory and File buffer cache will compete for physical memory How What to Cache Locality in File Access Patterns UNIX Workloads Most files are small often fitting into one disk block although most bytes are transferred from longer files Accesses tend to be sequential and 100 Spatial locality What happens when we cache a huge file Most opens are for read mode most bytes transferred are by read operations 1 What to Cache Locality in File Access Patterns Access Patterns Along the Way continued There is significant reuse re opens most opens go to files repeatedly opened quickly Directory nodes and executables also exhibit good temporal locality Proc F S File cache Looks good for caching Use of temp files is significant part of file system activity in UNIX very limited reuse short lifetimes less than a minute Long absolute pathnames are common in file opens Name resolution can dominate performance why Caching File Blocks Proc read fd buf n u m File cache System wide Open file table System wide File descriptor table r w pos mode in memory copy of inode ptr to on disk inode V M Block Process descriptor per process file ptr array read rootdir read inode read foo read inode read bar read inode read fd buf sizeof buf read fd buf sizeof buf read fd buf sizeof buf read rootdir read inode read foo read inode read bar read inode read filedatablock Issues for I O Cache Structure Goal maintain K slots in memory as a cache over a collection of m items on secondary storage K m 1 What happens on the first access to each item Fetch it into some slot of the cache use it and leave it there to speed up access if it is needed again later 2 How to determine if an item is resident in the cache Maintain a directory of items in the cache a hash table Hash on a unique identifier tag for the item fully associative r w pos mode stdin stdout stderr open foo bar file read fd buf sizeof buf read fd buf sizeof buf read fd buf sizeof buf close fd 3 How to find a slot for an item fetched into the cache File data Choose an unused slot or select an item to replace according to some policy and evict it from the cache freeing its slot Byte 2 File Block Buffer Cache HASH vnode logical block Buffers with valid data are retained in free inactive memory in a buffer cache or file cache list head Each item in the cache is a buffer header pointing at a buffer Blocks from different files may be intermingled in the hash chains Handling Updates in the File Cache 1 Blocks may be modified in memory once they have been brought into the cache Modified blocks are dirty and must eventually be written back Write back write through 104 2 Once a block is modified in memory the write back to disk may not be immediate synchronous Delayed writes absorb many small updates with one disk write System data structures hold pointers to buffers only when I O is pending or imminent busy bit instead of refcount free inactive list tail most buffers are free How long should the system hold dirty data in memory Asynchronous writes allow overlapping of computation and disk update activity write behind Do the write call for block n 1 while transfer of block n is in progress Thus file caches also can improve performance for writes 3 Knowing data gets to disk Force it but you can t trust it fsync Access Patterns Along the Way Proc Mechanism for Cache Eviction Replacement Typical approach maintain an ordered free inactive list of slots that are candidates for reuse F S Busy items in active use are not on the list E g some in memory data structure holds a pointer to the item File cache open foo bar file write fd buf sizeof buf write fd buf sizeof buf write fd buf sizeof buf close fd read rootdir read inode read foo read inode read bar read inode write fd buf sizeof buf write fd buf sizeof buf write fd buf sizeof buf E g an I O operation is in progress on the item get rootdir get inode get foo get inode get bar get inode get filedatablock put filedatablock The best candidates are slots that do not contain valid items Initially all slots are free and they may become free again as items are destroyed e g as files are removed Other slots are listed in order of value of the items they contain These slots contain items that are valid but inactive they are held in memory only in the hope that they will be accessed again late r 3 Replacement Policy The effectiveness of a cache is determined largely by the policy for ordering slots items on the free inactive list Defines the replacement policy A typical cache replacement policy is LRU Assume hot items used recently are likely to be used again Move the item to the tail of the free list on every release The item at the front of the list is the coldest inactive item Other alternatives FIFO replace the oldest item MRU LIFO replace the most recently used item Viewing Memory as a Unified I O Cache A key role of the I O system is to manage the page block cache for performance and reliability tracking cache contents and managing page block sharing choreographing movement to from external storage balancing competing uses of memory Modern systems attempt to balance memory usage between the VM system and the file cache Grow the file cache for file intensive workloads Grow the VM page cache for memory intensive workloads Support a consistent view of files across different style of access unified buffer cache Prefetching Intrafile prediction To avoid the access latency of moving the data in for that first cache miss Prediction Guessing what data will be needed in the future How Sequential access suggests prefetching block n 1 when n is requested Upon seek sequentiality is broken It s not for free Consequences of guessing wrong Overhead removal of useful stuff disk bandwidth consumed Stop