In Computer Operating Systems, What Is a Page Table?

A page table is a special data structure that is placed in the page table area of the system space and stores the correspondence between logical pages and physical page frames. Each process has its own page table, and the PCB table has a pointer to the page table. ^[1]

A page table is a special data structure that is placed in the page table area of the system space and stores the correspondence between logical pages and physical page frames. Each process has its own page table, and the PCB table has a pointer to the page table. ^[1]

Chinese name

Page table

Storage method

Basic paging storage management

Field

operating system

Page table address structure

Logical address: The address generated by the CPU. The logical address generated by the CPU is divided into: p (page number) It contains the base address of each page in physical memory,

Address translation

Used as an index into the page table; d (page offset), combined with the base address, is used to determine the physical memory address sent to the memory device.

Physical address: The address seen by the memory unit. The logical address space is 2 ^ m and the page size is 2 ^ n. Then the upper m-n bits of the logical address represent the page number, and the lower n bits represent the page offset.

Logical address space: A collection of all logical addresses generated by a program.

Physical address space: The set of all physical addresses in memory corresponding to the logical address. The user program cannot see the real physical address.

Note: The user only generates logical addresses and considers the address space of the process to be 0 to max. The physical address ranges from R + 0 to R + max, R is the base address, and address mapping-the process of transforming a logical address used in the program address space into a physical address in memory. This is done by the memory management unit (MMU).

Paging logical address = P (page number) .d (page shift)

Paging physical address = f (page frame number) .d (same as above)

P = linear logical address / page size

d = linear logical address-P * page size ^[1]

Page table role

Address mapping from page number to physical block number.

The process of converting a logical address into a physical address is: use the page number p to retrieve the page table, get the physical block number of the page from the page table, and load it into the physical address register. At the same time, the in-page address d is directly sent into the in-block address field of the physical address register. In this way, the content in the physical address register is the address of the actual memory accessed by the splicing of the two, thereby completing the conversion from the logical address to the physical address.

Page table basic paging storage management

A fixed-size page is used to describe the logical address space, and a page frame of the same size is used to describe the physical memory space. The page mapping from logical pages to physical page frames is implemented by the operating system, and it is responsible for all pages. Management and control of process operations.

Page Table Hierarchical Page Table

A computer system with a 32-bit logical address space, with a page size of 4KB, then the page table has one million entries. Assuming each entry is 4B, you need

Page table entries for secondary page tables

4MB physical address space to store the page table itself. With multi-level page tables, the space occupied by page tables can be reduced.

A logical address (32-bit system, page size 4K) can be divided into: a 20-bit page number + a 12-bit offset. If the page table is repaginated, the page number is broken down into: a 10-digit page number + a 10-digit offset. Therefore, a logical address is expressed as follows: p1 is the index used to access the external page table, and p2 is the page offset of the external page table.

At this time, the address translation mechanism of the two-level 32-bit paging structure is as follows:

Address translation of two-level page tables

TLB Page tables have a TLB (translation lookaside buffer) page table structure

The translation lookaside buffer (TLB) is small, dedicated, and fast

Hardware buffer, including only a small number of entries in the page table. If the page number is in the TLB, get the frame number and access memory; otherwise, get the frame number from the page table in memory, store it in the TLB, and access memory.

Address translation with TLB