Paged Memory Management

Basic principles of paged storage management

Discontinuous storage allocation: Paged storage management allows the program's storage space to not be continuous, so that the process can be stored in various memory blocks, avoiding external fragmentation problems and improving memory utilization.
Address structure: The system divides the logical address space into several pages of equal size, each page is numbered. Similarly, the memory is divided into blocks of equal size and each block is numbered. The logical address consists of two parts: page number (P) and page offset address (W). The specific calculation method is:

\[ P = \text{INT}(A / L), \quad W = A \mod L \]

Among them, \(A\) is the logical address, \(L\) is the page size, INT means downward division, and MOD means remainder.

Bitmap management: The allocation of main memory space is managed through a bitmap, which records which blocks are allocated and which blocks are free. Free blocks are found by looking for the "0" bit in the bitmap and memory is allocated to the job. When the job is executed, the memory block is returned and the bitmap is updated.
Block number calculation: When a memory block needs to be allocated or reclaimed, the block number is calculated by the formula based on the position in the bitmap:

\[ \text{block number} = \text{word size} \times \text{word length} + \text{bit number} \]

When the job ends, the operation of returning the block uses the opposite calculation method to update the bitmap and the number of free blocks.

Page table: A page table is maintained for each job, recording the mapping of the logical page number and the physical block number of each page. The page table implements the address mapping from page number to physical block number. Each page in the job has a corresponding entry in the page table.
Hardware-supported address conversion: When the job is executed, the hardware automatically converts the logical address to the physical address through the page table control register. The logical address is divided into two parts: page number and in-page address. The page table is indexed by the page number to obtain the corresponding physical block number, and then the physical address is calculated by adding the in-page address. The calculation formula is:

\[ \text{physical address} = \text{block number} \times \text{block length} + \text{in-page address} \]

Logical address decomposition: The logical address consists of two parts: page number and in-page address. The corresponding physical block number is found in the page table by the page number, and the specific physical address is found by the in-page address.
Page table query: When the page number exists in the page table, the corresponding physical block number can be obtained. If the page number does not exist in the page table, a program interrupt of address error occurs.
Physical address calculation: After obtaining the block number through the page table, the physical address is calculated in combination with the in-page address.