**Problem 2.** An important aspect of any caching system is the question of how a cache entry is chosen for **eviction** from the cache when the cache is full and a new page must be added. (Note that here we do not have any notion of a “slot”—any page can go anywhere in the cache.) There are a wide variety of possible strategies, for example **FIFO**, in which the page that has been in the cache longest is evicted, regardless of how many times it has been accessed. Another is **least recently used**, in which the cache keeps track of when a page was last accessed, and the one that was furthest back in the past is replaced. Suppose a user visits a sequence of pages (named by letters):\[ a, b, c, c, d, a, e, f, c, b, a \]Where the pages take the following amounts of cache space: \[ a: 10\text{MB}, \ b: 5\text{MB}, \ c: 3\text{MB}, \ d: 8\text{MB}, \ e: 7\text{MB}, \ f: 5\text{MB} \] ### Educational Content: Cache Management and Replacement Policies#### Problem Overviewa. **Cache Size for Non-Eviction:** How large must the cache be to ensure that no page is evicted before a page is accessed a second time?b. **Replacement Policy Scenario:** Suppose a browser uses the following replacement policy: when a page is accessed and there is not enough space in the cache, pages are evicted in First-In-First-Out (FIFO) order until there is sufficient space to add the new page. For instance, if the cache size is 10 MB, and the pages in the cache (from oldest to newest) have sizes of 2 MB, 4 MB, and 3 MB, then accessing a new 4 MB page necessitates evicting the two oldest pages (2 MB and 4 MB) to make room. Loading a page from the cache takes 100 microseconds, while loading it over the network takes 100 milliseconds (1,000 times longer), regardless of the page size. Calculate the total time needed to complete the sequence of accesses if the cache size is 20 MB.c. **Exercise with Increased Cache Size:** Repeat the scenario for a cache size of 30 MB.#### Detailed Explanation for Educational Use**Understanding the Problem:**- The goal is to analyze how different cache sizes and management policies affect the efficiency of data retrieval.- The eviction policy here is FIFO, meaning the oldest pages are removed first to make room for new data.**Steps to Approach:**1. **Identify Page Access Sequence:** Determine the sequence and sizes of pages being accessed to understand when evictions occur.2. **Calculate Required Cache Size (a):** To ensure no evictions, the cache must at least hold all accessed pages until they are accessed a second time.3. **Evaluate with Given Cache Sizes (b, c):** - With a 20 MB cache, simulate the FIFO eviction and calculate load times based on whether pages are cached or loaded from the network. - Increase to a 30 MB cache and repeat, noting changes in eviction decisions and load times.**Graphical Representation:**If there were graphs or diagrams, they would typically depict the following:- **Cache Size Utilization Over Time:** Showing how the cache fills and evicts pages as new pages are accessed.- **Access Time Comparison:** A bar graph comparing

We need to find the size of the cache and time to complete the given sequence for the cache…

Problem 2. An important aspect of any caching system is the question of how a cache entry is chosen for eviction from the cache when the cache is full and a new page must be added. (Note that here we do not have any notion of a "slot" any page can go anywhere in the cache.) There are a wide variety of possible strategies, for example FIFO, in which the page that has been in the cache longest is evicted, regardless of how many times it has been accessed. Another is least recently used, in which the cache keeps track of when a page was last accessed, and the one that was furthest back in the past is replaced. Suppose a user visits a sequence of pages (named by letters): a, b,c, c, d, a, e, f,c, b, a Where the pages take the following amounts of cache space: a: 10MB, b: 5MB, c: 3MB, d: 8MB, e: 7MB, f: 5MB.

Problem 2. An important aspect of any caching system is the question of how a cache entry is chosen for eviction from the cache when the cache is full and a new page must be added. (Note that here we do not have any notion of a "slot" any page can go anywhere in the cache.) There are a wide variety of possible strategies, for example FIFO, in which the page that has been in the cache longest is evicted, regardless of how many times it has been accessed. Another is least recently used, in which the cache keeps track of when a page was last accessed, and the one that was furthest back in the past is replaced. Suppose a user visits a sequence of pages (named by letters): a, b,c, c, d, a, e, f,c, b, a Where the pages take the following amounts of cache space: a: 10MB, b: 5MB, c: 3MB, d: 8MB, e: 7MB, f: 5MB.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

1. Caches are important to providing a high-performance memory hierarchy to processors. Below is a list of 32-bit memory address references, given as word addresses. 42, 137, 66, 50, 38, 225, 173, 22, 19, 88, 51, 43 a. For each of these references, identify the binary address, the tag, and the index given a direct mapped cache with 16 one-word blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty. b. For each of these references, identify the binary address, the tag, and the index given a direct mapped cache with two-word blocks and a total size of 8 blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty. Please explain the process.
Different algorithms are used for scheduling the disk head so that seek time may be reduced. Calculate a total number of heads movement for the following algorithms for the given numbers of disk cylinders. Shortest Seek Time First (SSTF) b) Circular Look (C-Look) Head Start: 71 Queue: 82 , 153 , 14 , 149 , 6 , 189 , 62 , 99 , 121
A computer uses a set-associative cache with 8-blocks per set. How many bits will be used for the counter to apply the (LRU algorithm)? Explain your answer. The following blocks are referenced by the CPU and to be fetched from the RAM to the cache sequentially: (i j k L L j m j n L m j m L k S j P i O k) Assume that the cache set is empty and all the above blocks can be inserted into the set. Use the LRU algorithm to fill in the following table that describes the status of the cache locations for each called block.
8. Consider one disk with 400 cylinders, numbered 0 to 399. Assume the current position of head is at cylinder 130. The request queue is given as follows: 150, 40, 350, 100, 280 For each of the disk-scheduling algorithms given below, show (by plotting in the graphs below) the current position of head based on the disk arm movement to satisfy the above requests, and count the total distance (in cylinders) of the disk arm movement. a. First Come First Served (FCFS) 0 40 100 1.30 150 Total distance (disk am movement) = b. Shortest Seek Time First (SSTF) 40 100 130 150 0 Total distance (disk arm movement) = c. LOOK - in the direction of increasing track number 0 40 100 130 150 Total distance (disk arm movement) = 280 280 280 350 350 350 399 399 399
Could you kindly go through the fundamentals of how a cache hierarchy is set up and how it works?
To what extent does the specified log processing function have access to each field of a log entry? The following code estimates the average number of cache misses per entry while using 64-byte cache blocks and no prefetching.
To what extent does the specified log processing function have access to each field of a log entry? The following code determines the typical number of cache misses per entry while using 64-byte cache blocks and no prefetching.
5. A computer has an L1 and L2 cache, backed up by DRAM which is backed up by virtual memory. The TLB and L1 caches have hit times of .5 ns. The TLB's backup is the page table in DRAM while L1 cache's backup is an L2 cache. The L2 cache has a hit time of 1.5 ns. DRAM has a hit time of 10 ns. Swap space has a hit time of 2,500,000 ns. The hit rates are: TLB: 98.8%, L1: 91.5%, L2: 97.7%, DRAM: 99.9998% and swap space 100%. What is the effective access time?
. Q: In this problem you are to compare reading a file using a single-threaded file server and a multithreaded server. It takes 15 msec to get a request for work, dispatch it, and do the rest of the necessary processing, assuming that the data needed are in a cache in main memory. If a disk operation is needed, as is the case one-third of the time, an additional 75 msec is required, during which time the thread sleeps. How many requests/sec can the server handle if it is single threaded? If it is multithreaded?
. Q: In this problem you are to compare reading a file using a single-threaded file server and a multithreaded server. It takes 15 msec to get a request for work, dispatch it, and do the rest of the necessary processing, assuming that the data needed are in a cache in main memory. If a disk operation is needed, as is the case one-third of the time, an additional 75 msec is required, during which time the thread sleeps. How many requests/sec can the server handle if it is single threaded? If it is multithreaded?
In this chapter, you will learn about the four cache replacement policies that have been discussed.
Consider a 2-block fully associative cache. The following blocks from main memory are accessed which need to be mapped to cache: P, Q, P, R. Which block is replaced from the cache when the last block (block R) is accessed? Assume FIFO replacement policy.