1
$\begingroup$

I'm currently dealing with inverted page tables and how they work. If I understood correctly, an IPT is a table that maps a frame number to a PID and page number. The way this works is by having a hash function map a tuple (PID, page_number) to (frame_number). If the entry of the table given by the frame number contains (PID, page), then we have a hit. Because a hash function can map multiple inputs to one output, we have to keep a chain of pages for each frame (according to my lecture notes).

Why does an inverted page table keep a linked list of pages per frame? Only one page can be loaded into a single frame at a time, how does this make sense? To me this seems more an issue similar to that of direct-mapped caching, where you have to throw out the previous block to make place for a new block.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Hash functions can have collisions, and you need to resolve the collisions. If two (PID, page_number) pairs map to the same row, only one can be stored there, and you need to have a mechanism to find the other one.

You can use page tables to map multiple virtual addresses (pages) to the same physical address (frame). For instance, this may be used to support shared memory, copy-on-write, on-demand zeroing for memory allocation, and more.

Improve this answer
$\endgroup$
5
  • $\begingroup$ By "a mechanism to find the other one", what exactly do you mean? An IPT is a map from frame_number -> (PID, page_number). In my lecture notes, it describes an IPT with a linkedlist of (PID, page_number) as value of the map, instead of a single (PID, page_number). I understand that collisions can happen, but how does it make sense to use a linked list if a frame number can only be occupied by a single page? When a hash collision happens, shouldn't we throw the currently occupying page out of memory and load the new page, instead of "locating the other one"? $\endgroup$
    – Tim V
    Nov 23, 2020 at 13:35
  • $\begingroup$ @TimV, In the second paragraph, I'm saying that the function (PID, page_number) -> frame_number is not bijective; it might map multiple (PID, page_number) values to the same frame_number. Consequently, given a frame_number, there might be multiple (PID, page_number) associated with it. You need a way to find the one you're looking for. You call it a map frame_number -> (PID, page_number), but strictly speaking there might be no such function, due to this effect. $\endgroup$
    – D.W. ♦
    Nov 23, 2020 at 20:14
  • $\begingroup$ @TimV, In paragraph 1, I'm saying that the hash function can create additional collisions, so the function (PID, page_number) -> row is not bijective; it might map multiple (PID, page_number) values to the same row, due to a collision in the hash function. If we want to look up the mapping for a specific (PID, page_number), it's not enough to look in the first row it hashes to, because it might be elsewhere. Every hash table has to deal with this, and there are multiple solutions; IPT's use separate chaining. $\endgroup$
    – D.W. ♦
    Nov 23, 2020 at 20:18
  • $\begingroup$ Thank you for your answer! Can we summarize this by saying that IPTs use separate chaining and when an IPT contains such a chain with multiple elements, it is not the IPTs job to throw out virtual pages in page frames? $\endgroup$
    – Tim V
    Nov 24, 2020 at 9:55
  • $\begingroup$ @TimV, sounds reasonable to me. $\endgroup$
    – D.W. ♦
    Nov 24, 2020 at 16:08

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.