Paging is one of the memory management schemes by which a computer stores and retrieves data from the secondary storage for use in main memory.
In the paging memory-management scheme, the operating system retrieves data from secondary storage in same-size blocks called pages.
Paging allows the physical address space of the process to be non contiguous
Paging is to deal with external fragmentation problem. This is to allow the logical address space of a process to be non-contiguous, which makes the process to be allocated physical memory.
Logical address space of a process can be non-contiguous; process is allocated physical memory.
Whenever the latter is available.
Divide physical memory into fixed-sized blocks called frames (size is power of 2, between 512 bytes and 8192 bytes).
Divide logical memory into blocks of same size called pages.
Keep track of all free frames.
To run a program of size n pages, need to find n free frames and load program.
Set up a page table to translate logical to physical addresses.
Internal fragmentation-allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used
The logical memory of the process is contiguous, but pages need not be allocated contiguously in memory.
By dividing memory into fixed size pages, we can eliminate external fragmentation.
Paging does not eliminate internal fragmentation
Address generated by CPU is divided into:
1. Page number (p) – used as an index into a page table which contains base address of each page in physical memory.
2. Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit.
Implementation of page table:
Page table is kept in main memory.
Page-table base register (PTBR) points to the page table.
Page-table length register (PTLR) indicates size of the page table.
In this scheme every data/instruction access requires two memory accesses. One for the page table and one for the data/instruction.
The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative registers or translation look-aside buffers (TLBs).
Associative registers - parallel search
Address translation (A', A'')
If A' in associative register, get frame number out.
Otherwise get frame number from page table in memory.
Hit ratio - percentage of times that a page number is found in the associative registers; ratio related to number of associative registers.
Effective Access Time (EAT)
associative lookup = e time units
memory cycle time = m time units
hit ratio = a
EAT = (m + e) a+ (2m + e) (1 - a) = 2m + e - ma
Memory protection implemented by associating protection bits with each frame.
Valid-invalid bit attached to each entry in the page table:
``valid'' indicates that the associated page is in the process' logical address space, and is thus a legal page.
``invalid'' indicates that the page is not in the process' logical address space.
Write bit attached to each entry in the page table.
Pages which have not been written may be shared between processes
Do not need to be swapped - can be reloaded.
Conversion of logical address to physical address
The concept of a logical address space that is bound to a separate physical address space is central to proper memory management.
Logical address - generated by the CPU; also referred to as virtual address.
Physical address - address seen by the memory unit.
Logical and physical addresses are the same in compile-time and load-time address-binding schemes; logical (virtual) and physical addresses differ in execution-time address-binding scheme.
There are three steps to translate logical address to physical address
Step1: Find the index field from the segment selector and use the index field to locate the segment descriptor for the segment in global descriptor table (GDT)
Step 2: Test the access and limit the field of descriptor to make sure that the segment is accessible and the offset is within the limit of the segment
Step3: The base address of the segment will be obtained from the segment descriptor. Then the base address of the segment will be added to the offset to determine a linear address