How to administer the paging to minimize m is an important

Assignment Help Computer Engineering

Reference no: EM132104023

In this problem we are concerned with caching or paging. Unlike the RAM or Turing machine models, actual computers have a hierarchy of memory levels.

The basic model for this is that there are two levels, a large but slow-access main memory, and a small but fast-access memory called the cache.

The cache can hold a fixed number k of "pages". The CPU cannot access a page before it is brought into cache. For the purpose of this problem, we treat CPU accesses to the cache as free, and what we are trying to minimize is M = the number of times that a page is brought from main memory into the cache.

(Since k is fixed, when a page is brought in it must evict something else, which is why we normally can't get M to be 0.)

The sequence of pages to be accessed is not known in advance, so deciding on how to administer the paging to minimize M is an important problem in on-line algorithms mdash algorithms that must make decisions "causally" (meaning, depending only on the past).

However, Computer Systems researchers realized it is useful to consider also the clairvoyant or "off-line" version of the problem, in which the entire sequence of CPU page requests, r_1, ..., r_T, is known in advance. (Think of T as very large.)

The off-line optimum gives a lower bound on the performance of on-line algorithms; moreover, one may hope to combine such an algorithm with heuristic predictions and achieve performance that is not too much worse than the lower bound.

Here is the greedy algorithm that people came up with: at time t, if r_t is not in the cache, bring it in and evict the record in the cache whose next request time is furthest in the future.

More formally, if p_1, ...p_k are the pages in cache at time t, the p_i evicted is that which maximizes min{u: [u > t] wedge (p_i = r_u]}. (If the set is empty, the min equals infinity.)

For example, for k = 2 and for the seven requests 1, 2, 3, 2, 3, 1, 2, the time series of cache contents in this algorithm will be: {}, {1}, {1, 2}, {2, 3}, {2, 3}, {2, 3}, {1, 2}, {1, 2}. The cost is M = 4. Show that this algorithm optimizes M.

Reference no: EM132104023

Questions Cloud

A stuntman swings from the end : A stuntman swings from the end of a 4.10 m long rope along the arc of a vertical circle.

Rate of energy lost through windows : How do curtains reduce the rate of energy lost through windows? Is it reducing the amount of thermal energy lost through radiation?

How many lockers will remain open : How many lockers will remain open and how many will remain closed. Solve this problem using array and print the number of open and closed lockers.

Describe a covert channel involving the print queue : Describe a covert channel involving the print queue and estimate the realistic capacity of your covert channel.

How to administer the paging to minimize m is an important : The basic model for this is that there are two levels, a large but slow-access main memory, and a small but fast-access memory called the cache.

Create a web page that contains a table of buttons : Create a web page that contains a table of buttons that should apply various styles to a paragraph according to the specifications listed.

Create a query that prompts for students identification : Create a query that prompts for students' identification numbers and returns their timetables for the current semester.

Build the program after copying the files and placing them : Build the program after copying the files and placing them in your project. You should not be modifying any of the files.

What is the netwrk diameter : How many nodes are there? What is the netwrk diameter? What is bisection bandwidth?

User Account

All Pages