nagging questions virtual memory - Minix

This is a discussion on nagging questions virtual memory - Minix ; Hi page 394 of osdi 3rd edition says (at the bottom): "The normal way to process a TLB miss, whether in hardware or in software, is to go to the page table and perform the indexing operations to locate the ...

+ Reply to Thread
Results 1 to 4 of 4

Thread: nagging questions virtual memory

  1. nagging questions virtual memory

    Hi
    page 394 of osdi 3rd edition says (at the bottom):

    "The normal way to process a TLB miss, whether in hardware or in
    software, is to go to the page table and perform the indexing
    operations to locate the page referenced. The problem with doing this
    search in software is that the pages holding the page table may not be
    in the TLB, which will cause additional TLB faults during the
    processing."

    What? Why is that related to whether I'm doing this in hardware or
    software? If I do the search in hardware, the problem could arise just
    as well, right?

    Then it goes on:

    "These faults can be reduced by maintaining a large (e.g., 4-KB or
    larger) software cache of TLB entries in a fixed location whose page
    is always kept in the TLB. By first checking the software cache, the
    operating system can substantially reduce the number of TLB misses."

    My question: Instead of having this TLB cache in memory and making
    sure its page frame number is always in the TLB, why not just make
    sure the page table's frame is always in the TLB???


  2. Re: nagging questions virtual memory

    In article <1174821956.522892.305310@n59g2000hsh.googlegroups. com>,
    "sancho1980" wrote:

    > Hi
    > page 394 of osdi 3rd edition says (at the bottom):
    >
    > "The normal way to process a TLB miss, whether in hardware or in
    > software, is to go to the page table and perform the indexing
    > operations to locate the page referenced. The problem with doing this
    > search in software is that the pages holding the page table may not be
    > in the TLB, which will cause additional TLB faults during the
    > processing."
    >
    > What? Why is that related to whether I'm doing this in hardware or
    > software? If I do the search in hardware, the problem could arise just
    > as well, right?


    If you do it in hardware, the hardware page table walker can ignore the
    TLB if there are any secondary misses. If you do it in software, you may
    have to have a reentrant miss handler (i.e., attempting to access a part
    of the page table not in the TLB will result in the miss handler being
    invoked before it's finished). Not impossible to do but another detail
    to get right.

    > Then it goes on:
    >
    > "These faults can be reduced by maintaining a large (e.g., 4-KB or
    > larger) software cache of TLB entries in a fixed location whose page
    > is always kept in the TLB. By first checking the software cache, the
    > operating system can substantially reduce the number of TLB misses."
    >
    > My question: Instead of having this TLB cache in memory and making
    > sure its page frame number is always in the TLB, why not just make
    > sure the page table's frame is always in the TLB???


    A page table has to cover the whole address space. In practice, parts of
    it may never be used. There are likely to be big gaps e.g. between the
    stack and heap. The page table in total is a lot smaller than all the
    pages in the system but it still may not be practical to represent fully
    in memory.

    --
    Philip Machanick

  3. Re: nagging questions virtual memory

    > If you do it in hardware, the hardware page table walker can ignore the
    > TLB if there are any secondary misses. If you do it in software, you may
    > have to have a reentrant miss handler (i.e., attempting to access a part
    > of the page table not in the TLB will result in the miss handler being
    > invoked before it's finished). Not impossible to do but another detail
    > to get right.


    Ok, so the hardware handler wouldn't even bother to look up the page
    table frame in the TLB and thus doesn't risk getting yet another miss?
    Is that the performance advantage? Well, it (the page table frame)
    could also very well be in the TLB, in which case ignoring the TLB
    from start would actually slow things down; so I don't see the
    performance gain in it, sorry!


    > A page table has to cover the whole address space. In practice, parts of
    > it may never be used. There are likely to be big gaps e.g. between the
    > stack and heap. The page table in total is a lot smaller than all the
    > pages in the system but it still may not be practical to represent fully
    > in memory.


    So are you saying that instead of having the page table frames
    constantly in memory, it is better to have just a RANDOM subset of it
    in memory with its frame base in the TLB? I really don't see how this
    could possibly speed up things!

    Not meaning to sound rude, but I still don't get it!

    Thanks,

    Martin


  4. Re: nagging questions virtual memory

    In article <1174912588.119423.193660@l77g2000hsb.googlegroups. com>,
    "sancho1980" wrote:

    > > If you do it in hardware, the hardware page table walker can ignore the
    > > TLB if there are any secondary misses. If you do it in software, you may
    > > have to have a reentrant miss handler (i.e., attempting to access a part
    > > of the page table not in the TLB will result in the miss handler being
    > > invoked before it's finished). Not impossible to do but another detail
    > > to get right.

    >
    > Ok, so the hardware handler wouldn't even bother to look up the page
    > table frame in the TLB and thus doesn't risk getting yet another miss?
    > Is that the performance advantage? Well, it (the page table frame)
    > could also very well be in the TLB, in which case ignoring the TLB
    > from start would actually slow things down; so I don't see the
    > performance gain in it, sorry!


    I didn't exactly say that. The HW can look in the TLB and if the
    secondary entry isn't there, go straight to memory and not try to fix up
    the TLB for the secondary miss. The secondary table (at least the parts
    of it close to the last reference) may meanwhile have found its way to
    the data cache, making a second use of it in the near future faster.

    A HW page table walker will generally also give up and generate an
    interrupt in the more complex cases so it isn't strictly a matter of one
    or the other.

    > > A page table has to cover the whole address space. In practice, parts of
    > > it may never be used. There are likely to be big gaps e.g. between the
    > > stack and heap. The page table in total is a lot smaller than all the
    > > pages in the system but it still may not be practical to represent fully
    > > in memory.

    >
    > So are you saying that instead of having the page table frames
    > constantly in memory, it is better to have just a RANDOM subset of it
    > in memory with its frame base in the TLB? I really don't see how this
    > could possibly speed up things!


    If you have a 2GB address space, and 4KB pages, that means you have over
    1-million page table entries. If each entry is 4B, you need 2MB for the
    entire page table for _every_ process -- unless you can be smart about
    allocating a process a subset of the address space. But in a true VM
    system, all applications can theoretically expand to the limit of the
    address space, even if they leave gaps. If you have 100 processes
    (currently 85 running on my Mac with a single user), that's 200MB.

    So you generally only want to represent the subset of the page table
    that is actually used in memory. The TLB will contain (you hope) the
    frequently accessed entries.

    All of this is somewhat approximate as there are many variations in
    practice in real systems.

    Here's some further reading:
    * http://www.gelato.unsw.edu.au/~ianw/...iew/report.pdf
    * Jacob, B. L. and Mudge, T. N. 1998. A look at several memory
    management units, TLB-refill mechanisms, and page table organizations.
    SIGOPS Oper. Syst. Rev. 32, 5 (Dec. 1998), 295-306. DOI=
    http://doi.acm.org/10.1145/384265.291065

    --
    Philip Machanick

+ Reply to Thread