In "Introduction to Algorithms" there is the following exercise:

Consider implementing a stack in a computer that has a relatively small amount of fast primary memory and a relatively large amount of slower disk storage. The operations PUSH and POP work on single-word values. The stack we wish to support can grow to be much larger than can fit in memory, and thus most of it must be stored on disk. ...

... A simple, but inefficient, stack implementation keeps the entire stack on disk. Because disk operations are relatively expensive, now consider a stack implementation in which we keep one page of the stack in memory. (We also maintain a small amount of memory to keep track of which page is currently in memory.) We can perform a stack operation only if the relevant disk page resides in memory. If necessary, we can write the page currently in memory to the disk and read in the new page from the disk to memory. If the relevant disk page is already in memory, then no disk accesses are required. ...

I want to implement this in actual code in C or C . I know how to use mmap() and I can use memory-mapped disk files for this, but I don't know how to implement "a stack implementation in which we keep one page of the stack in memory". Is there a way to manage memory as C/C pointers on a page-by-page basis?

CodePudding user response：

You DON'T.

You write the code with the mmapped stack and count the number of times you change page in simulation and let the OS cache as much as it wants. The best way to track page changes is in the push() and pop() functions. Cast the pointer to an integer, use a mask to get rid of the low bits and compare to previous and see if it changed or not.

When you reach the end of your simulated run, you output how many times you had to swap pages in RAM.

You don't actually force it to disk every time. That's totally unnecessary for the learning environment.

CodePudding user response：

Working with 2 pages makes a lot more sense because otherwise you get into some really bad worse cases where every stack access means a disk access.

So you allocate 2 pages and set your stack pointer to the start and you set the counter for how many pages are on disk to 0.

On push() if the stack is full you increment the counter, save the older page to disk, move everything down a page and adjust the stack pointer. Then push the data to the stack.

On pop() if the stack is empty and counter > 0 you decrement counter, load a page back from disk and adjust the stack pointer. Then pop the data from the stack.

Note: you can use the 2 pages as a ring buffer so on read/write of a page you don't have to move data.