Page size is more complex/nuanced

By: Paul A. Clayton (, May 8, 2021 10:03 am
Room: Moderated Discussions
Some of the comments in this thread seem to reveal misperceptions of the constraints. While I would agree that a linear page table probably makes the most sense for a 32-bit system (with a hierarchical page table being a special case of such where the page table vitual address space is separate from the code/data address space rather than in a hole at the bottom of the code/data address space), there is no fundamental requirement that the block size for the page table needs to be the same as the base page size. Using the same size may modestly simplify the OS (and the conceptualization of the system) and slightly reduce the cost of sharing PDE cache and huge page TLB entries (with different sizes, the indexing would use different bits and the smaller chunk require more tag bits), but those also seem minor costs.

The page size is constrained by sizes supported by the TLB and the page table block size effects a hardware page table walker, but neither prevents the OS from using larger page table blocks or swapping/permission pages. The use of page clustering does complicate the OS (the accessed and dirty bits of all the hardware/TLB pages of the cluster need to be examined when making decisions about paging out) and increases capacity pressure on the TLB (though if such clustering was system-wide, the TLB could treat clusters as pages).

The TLB/architecture can also support multiple page/block sizes, including flattening the page table (for large dense mappings) by mapping an intermediate node to a larger page. Similarly, the page table entry format can support skipping levels (this is used in Mitch Alsup's My 66000).

Another point that seems to have been missed is that, in theory, the OS can load the cache of translation entries as part of a change of address space. I.e., rather than having one software-managed cache entry pointing to the root of the page table, the OS could load multiple "segment" page table roots. (With separate instruction and data TLBs/paging-structure-caches, the OS could even provide a virtual Harvard architecture.) The OS would have to be prepared to manage a TLB/PSC miss on a table walk (which might just be a fatal error if no permitted addresses are outside the defined "segments"; supporting stack growth may justify actually handling this "fault"). Supporting such miss handling (combined with address space IDs) might be desirable to facilitate temporal (across context switches) and spatial (sharing across hardware virtual processors) capacity sharing, though such sharing would introduce some problems.

With such "segmented" address translation, having heap and stack grow away from each other (rather than the more common growth toward each other) might be desirable to allow heap and stack to use the same "segment".

With x86, it would even be possible to use "segment descriptors" to define separate page tables. (This would even allow a small increase in the amount of addressable memory.)

With respect to the cache synonym problem, smaller pages do introduce overhead but they do not force using smaller caches or higher associativity.

OS page size is more constrained to be at least as large as TLB page size. (Providing multiple valid bits in the TLB entry/PTE would allow smaller OS pages with similar tradeoffs to sectors cache blocks.)

4KiB was probably chosen for the attractiveness of having a linear/hierarchical page table for a 32-bit address space have exactly two levels and providing ten metadata bits with a 32-bit physical address space (a single valid bit and three permissions for two modes would leave three bits).

Growing the page size has also been shown to be difficult. The architects for Alpha assumed base page size would grow (and would be used for table node sizes and OS page sizes), but even with systems primarily using in-house OSes the change was much slower than expected. This implies that a page size should be larger than is optimal for initial systems (as long as such does not delay upgrading or push sales to competitors). If paging is not always used and was most important for systems with more memory, memory capacity overheads related to page size might not have been as important.

The architects of the 386 may not have been aware of some of the above mentioned possibilities (x86 did not get ASIDs or paging structure caches for a while), had to cooperate with Microsoft and IBM, and had tighter chip size and complexity constraints than modern systems.
< Previous Post in Thread 
TopicPosted ByDate
4K pages probably used to be too largeYuhong Bao2021/05/01 01:01 PM
  HDD seek time isn't freeMark Roulo2021/05/01 02:12 PM
    HDD seek time isn't freeYuhong Bao2021/05/01 02:21 PM
      HDD seek time isn't freeTim Mc2021/05/01 02:42 PM
        HDD seek time isn't freerwessel2021/05/01 02:57 PM
  4K pages probably used to be too largeBen LaHaise2021/05/02 10:45 AM
    VAX was 512 (in 1977) (NT)anonymous22021/05/02 08:36 PM
      FWIW, S/370 offered a choice of 2K and 4K (NT)rwessel2021/05/03 05:09 AM
      DEC's earliest PDP-11 disks were 512 (in 1971)John Yates2021/05/03 01:53 PM
    4K pages probably used to be too largeanon22021/05/03 01:17 AM
      4K pages probably used to be too largeBen LaHaise2021/05/03 05:36 PM
        Morotola 680x0 series page sizesBen LaHaise2021/05/03 05:51 PM
        4K pages probably used to be too largeanon22021/05/03 06:39 PM
          4K pages probably used to be too largeanon22021/05/03 08:51 PM
        4K pages probably used to be too largeYuhong Bao2021/05/03 10:51 PM
      4K pages probably used to be too largewumpus2021/05/05 09:06 AM
        4K pages probably used to be too largeanon22021/05/05 04:04 PM
          4K pages probably used to be too largeChester2021/05/05 06:45 PM
            4K pages probably used to be too largewumpus2021/05/06 09:06 AM
              Phenom TLB bugHeikki Kultala2021/05/06 12:46 PM
                Phenom TLB bugChester2021/05/06 05:29 PM
        4K pages probably used to be too largeEtienne Lorrain2021/05/06 01:08 AM
          4K pages probably used to be too largeJames2021/05/06 02:36 AM
            4K pages probably used to be too largerwessel2021/05/06 09:32 AM
              Reformatting SCSI disk sector sizeDoug S2021/05/06 11:30 AM
        4K pages probably used to be too largeDavid Hess2021/05/11 08:57 AM
  Page size is more complex/nuancedPaul A. Clayton2021/05/08 10:03 AM
Reply to this Topic
Body: No Text
How do you spell tangerine? 🍊