1
$\begingroup$

What is the term for an algorithm that always requests the same sequence of pages? I recall seeing this concept before but haven't been able to find anything on Google without more specific vocabulary.

One algorithm in this category is a linear scan to (say) find the minimum of a set of data. Each page is accessed in order, regardless of the value of previous accesses.

Most algorithms do not fall into this category. For example, a binary search chooses what page to access based on the values in the page before it.

Improve this question
$\endgroup$
5
  • $\begingroup$ What do you mean by 'the same sequence of pages'? All page replacement algorithms are suppose to speed up search process not slows it down. $\endgroup$
    – Bartosz Przybylski
    Commented Aug 23, 2013 at 16:23
  • $\begingroup$ I mean the algorithm always requests the same pages, in the same order. As I mentioned a linear scan is an example. By "algorithm" I do not mean a page replacement algorithm, I mean the algorithm generating the page requests $\endgroup$
    – SamM
    Commented Aug 23, 2013 at 16:30
  • 1
    $\begingroup$ I don't think that there is any specific name for this case. But question seems to be more about Adversary models. But decisions of adversary might depend on page replacement algorithm. $\endgroup$
    – Bartosz Przybylski
    Commented Aug 23, 2013 at 16:35
  • $\begingroup$ I don't think of an algorithm (for an "application problem") requesting chunks of a level of a memory hierarchy, let alone choose them. Programs and algorithms can conceivably be classified by access pattern(s) on physical or abstract machines. There has been support for cache hinting, page pre-fetch and clever placement on drum memory. $\endgroup$
    – greybeard
    Commented Mar 13, 2015 at 3:58
  • $\begingroup$ I believe the concept I was looking for was Data Oblivious algorithms. (Clearly the description in the question isn't 100% right, but I couldn't remember the details of what I was looking for.) $\endgroup$
    – SamM
    Commented Mar 15, 2015 at 15:47

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.