demand paging - operating systems concept

[Sadaiyappan]

Which of the following programming techniques and structures are ?good? for a demand paged environment (that is, tend to produce fewer page faults)? Which are not good? Explain your answers.
a. Stack
b. Sequential search
c. Binary search
d. Pure code (also called ?reentrant code?)
e. Indirection (that is, accessing objects through pointers)

This problem confuses me. Doesn't it depend on the size of the structure being used? Here is what I guess:

a. Stack
Stack is good.
b. Sequential search
Sequential Search is good.
c. Binary search
Binary search is not good.
d. Pure code (also called ?reentrant code?)
Pure code is not good.
e. Indirection (that is, accessing objects through pointers)
Indirection is not good.

can you explain to me why this is so or link to me something that does (and not wikipedia i went there and it didnt help much)

 

[Cogman]

Search for caching. specifically spacial locality. The two concepts are pretty much the same.

The basic sense is that you want to access elements that are close together and not far apart. The farther apart it is the worse off you are.

 

[DaveSimmons]

> can you explain to me why this is so or link to me something that does

Doesn't your class textbook or lecture notes cover any of this?

For example, stack use is good because it keeps all of the local variables for a function together, and also as close as possible to the local variables of the function that called it. i.e. like Cogman said, locality.

 

[degibson]

Originally posted by: Sadaiyappan
Doesn't it depend on the size of the structure being used? Here is what I guess:

Yes, it does.

There's not much I want to add to Cogman's excellent reply, except:

- You have to be dealing with pretty significant scale before paging is going to happen at all on most commodity systems.

- Even without paging, there is still a good reason to know about locality -- processor caches are much smaller and depend a lot on temporal and spatial locality.

- Reentrant code itself doesn't affect data locality -- it depends on what that code does.

- There are no absolutes, e.g., not all indirection is bad (only unmanaged indirection), not all binary search is bad, sequential search is not always good, etc.

 

[Sadaiyappan]

Ok, my professor wants me to modify an existing virtual memory manager program in C++. He wants me to add Least recently used page replacement algorithm, least frequently used algorithm and an improved least frequently used algorithm that right shifts the bit by 1 every time 5 reference counts for a page. Second chance and FIFO algorithms are already part of the program

I had no problem adding the algorithms -- it was very simple code but he wants me "Test each of your algorithms, and the two algorithms included in the original program, on several sets of data. Try to construct tests that distinguish between the algorithms. Construct a simple table showing the results."

What I want to know is which algorithm is supposed to be the most efficient in which case? The variables he lets us work with and want us to play around with are the upper page number (the value range that is allowed for the pages), reachback (not sure what reachback is), locality (percentage chance that a frame will be reselected from the frames that are in the reachback), and the number of requests and number of frames.

 

[DaveSimmons]

> What I want to know is which algorithm is supposed to be the most efficient in which case?

Isn't that what your tests are supposed to determine? If they aren't, you need to make them.

If you're doing optimization in the real world you usually can't ask someone else what the correct answer is.

 

[Sadaiyappan]

Well that is what the tests are for, but I'm sure the tests have been done before many times and I wanted to know what those results were so I know if my algorithms are working correctly.