Hardware and Software Concepts:Caching and Buffering

Caching and Buffering

In Section 2.3.4, we discussed how computers contain a hierarchy of storage devices that operate at different speeds. To improve performance, most systems perform caching by placing copies of information that processes reference in faster storage. Due to the high cost of fast storage, caches can contain only a small portion of the information contained in slower storage. As a result, cache entries (also called cache lines) must be managed appropriately to minimize the number of times referenced information is not present in cache, an event called a cache miss. When a cache miss occurs, the system must retrieve the referenced information from slower storage. When a referenced item is present in the cache,a cache hit occurs, enabling the system to access data at relatively high speed.33

To realize increased performance from caching, systems must ensure that a significant number of memory references result in cache hits. As we discuss in Section 11.3, Demand Paging, it is difficult to predict with high accuracy the information that processes will soon reference. Therefore, most caches are managed using heuristics—rules of thumb and other approximations—that yield good results with relatively low execution overhead (see the Operating Systems Thinking Feature, Heuristics).

Examples of caches include the L1 and L2 processor caches, which store recently used data to minimize the number of cycles during which the processor is idle. Many operating systems allocate a portion of main memory to cache data from secondary storage such as disks, which typically exhibit latencies several orders of magnitude larger than main memory.

A buffer is storage area that temporarily holds data during transfers between devices or processes that operate at different speeds.34 Buffers improve system performance by allowing software and hardware devices to transmit data and requests asynchronously (i.e., independently of one another). Examples of buffers include hard disk buffers, the keyboard buffer and the printer buffer.35, 36 Because hard disks operate at much slower speeds than main memory, operating systems typically buffer data corresponding to write requests. The buffer holds the data until the hard disk has completed the write operation, enabling the operating system to execute other processes while waiting for the I/O to complete.A keyboard buffer is often used to hold characters typed by users until a process can acknowledge and respond to the corresponding keyboard interrupts.

Spooling (simultaneous peripheral operations online) is a technique in which an intermediate device, such as a disk, is interposed between a process and a low- speed or buffer-limited I/O device. For example, ifa process attempts to print a document but the printer is busy printing another document, the process, instead of waiting for the printer to become available, writes its output to disk. When the printer becomes available, the data on disk is printed. Spooling allows processes to request operations from a peripheral device without requiring that the device be ready to service the request.37 The term “spooling” comes from the notion of winding thread onto a spool from which it can be unwound as needed.

Self Review

1. How does caching improve system performance?

2. Why do buffers generally not improve performance if one device or process produces data significantly faster than it is consumed?

Ans: 1) Caches improve performance by placing in fast storage information that a process is likely to reference soon; processes can reference data and instructions from a cache much faster than from main memory. 2) If the producing entity is much faster than the consuming entity, the buffer would quickly fill, then the relationship would be limited by the relatively

Operating Systems Thinking

Heuristics

A heuristic is a “rule of thumb”— a strategy that sounds reasonable and when employed, typically yields good results. It often does not have a basis in mathematics because the system to which it applies is sufficiently complex to defy easy mathematical analysis. As you leave your home each morning, you may use the heuristic, “If it looks like rain, take my umbrella.” You do this because from your experience, “looks like rain” is a reasonable (although

not perfect) indicator that it will rain. By applying this heuristic in the past, you avoided a few soakings, so you tend to rely on it. As you look at the pile of paperwork on your desk and schedule your work for the day, you may use another heuristic, “Do the shortest tasks first.” This one has the satisfying result that you get a bunch of tasks done quickly; on the downside, it has the unfortunate side effect of postponing (possibly important) lengthier tasks. Worse yet, if a steady stream of new short tasks arrives for you to do, you could indefinitely postpone important longer tasks. We will see operating systems heuristics in many chapters of the book, especially in the chapters that discuss resource management strategies, such as Chapter 8, Processor Scheduling and Chapter 12, Disk Performance Optimization.

slow speed of the consuming entity—the producing entity would have to slow down because it would repeatedly find the buffer full and would have to wait (rather than execute at its nor- mally faster speed) until the consumer eventually freed space in the buffer. Similarly, if the consuming entity were faster, it would repeatedly find the buffer empty and would have to slow down to about the speed of the producing entity.