Motivation
As an Operating Systems project, we were asked to create a page table with least recently used (LRU) and first in first out (FIFO) replacement policies. I slowly realized the standard containers were not up to this task. The normal use cases for my container needed to be:
Inserting an entry into the page table
Marking an entry as the LRU entry in the page table
Finding the oldest/least recently used entry in the page table
One of my goals while completing this project was to make all operations on the container O(1) since page tables can grow quite large. Take the potential of 128TB virtual address spaces on Redhat systems [1]. Marking an entry as LRU is an O(N) or greater operation using any of the standard library C++ containers. I’ll go through the reasons for each container now. Skip ahead to my solution if you’re not Interested.
vector, array: Ordering requires moving data not just pointer
map: Ordering by key is the wrong idea for a page table
set: No default ordering. I didn’t consider this one but maybe it’s possible to use a set as a page table.
queue, list: Accessing an arbitrary element is O(n)
dequeue, forward_list: Swap is too costly because it switches the contents of the index not the pointer.
Figure 1: (top) The struct at each entry of the queue. (bottom) The data members and methods of the VectorQueue class.
Solution
I created an object containing a vector and a queue. Each element of the vector was a template data-type given to the VectorQueue and each element of the queue was a struct. The struct contains the indices (not pointers) of next and previous entries in the vector. For O(1) push and pops, the head and tail indices are part of the VectorQueue object. An outline of the object is in figure 1.
Methods
I describe using the vector queue object as:
/** * HOW TO USE VECTOR QUEUE: * 1) create the default VectorQueue * 2) size the vector queue using vector’s resize function * 3) set the queue order as desired using the methods: * push(index) – moves an index to the head of the queue * pop(index) – removes the last index from the queue and returns it’s contents **/
There are also getters for most data items. The [] operator accesses the vector elements. The queue is resized to the same size as the vector. The inQueue() function is O(1) and returns whether the vector entry is in the queue.
Future Improvements
I plan to standardize this container so it implements all the methods of Vector and Queue. I also plan to profile the use of this container against a vector which swaps indices at every access. Let me know if there’s anything else you think I should add/remove.
Questions
Why does a dequeue swap the contents of the container instead of the pointers?
Should the [] operater access a struct with both the vector and the queue?
Is there a way to dynamically allocate the Queue while retaining the advantages of the VectorQueue?
References:
[1] https://access.redhat.com/articles/rhel-limits
Comments