Previously, two assumptions:
- each process occupies a contiguous memory region ❌
- physical memory is large enough to contain one or more processes with complete memory space
Assuming the first assumption is not made, we can use the paging scheme.
General Idea
The
- physical memory is split into regions of fixed size (physical frame)
- logical memory is split into regions of same size (logical page)
At execution time, pages of a process are loaded into any available memory frame:
- logical memory space remains contiguous
- occupied physical memory region can be disjoined
This allows for a lot flexibility, as the occupied physical memory does not have to follow the continuity as intended.
Page Table
In contiguous memory allocation, usage of a process is tracked simply (starting address, size of process).
However, with paging scheme:
- mapping between logical page and physical frame
- a lookup table is needed
Logical Address
Design decisions
- Frame size is a power-of-2
- Physical frame size == Logical frame size
Given
- page/frame size of
bits of logical address,
the formula is as follows:
where
refers to the most significant bits of refers to the remaining bits of the refers to the frame number, which is found from using mapping mechanism (such as page table) on
Step-by-step:
- Find the page size in bytes.
- for example, 4 bytes.
- Find how many bits needed for the offset
. This is - Determine how many pages there are.
- there are 4 logical pages
- Determine
, , which is the number of bits for the page number. - Determine how many frames there are.
- there are 8 physical frames
- Determine
, , which is the number of bits for the page number.
Pros
- No external fragmentation
- Very less internal fragmentation
- generally only last frame
- Clear separation of logical and physical address space
- allows for great flexibility
- simple address translation
Implementation
Pure-Software Solution
OS stores page table information in PCB - thus the page table is the memory context of a process.
Require two memory access for each memory reference
- first reference to get the page table for the process
- second to get the actual offset for that process
Possible fixes for this - caching
Hardware Support
Translation Look-Aside Buffer (TLB)
TLB acts as a cache of a few page table entries.
Logical address translation with TLB
- TLB-Hit: entry is found - frame number retrieved to generate physical address
- TLB-Miss: entry is not found - memory access is needed to access the full page table, and retrieved frame number is used to generate physical address and update TLB
To calculate the impact on memory access time, consider
- time taken for TLB access
- time taken for main memory access
- percentage of page table contained in TLB
The memory access time is thus
When there is a
- the time taken is
to access the frame number and the to access the memory itself.
When there is a
- the time taken is
to access the frame number, and since there is a miss, to access the page table of the process, and again to access the actual memory.
If TLB access takes 1ns, and main memory access takes 50ns, what is the average memory access time if TLB contains 40% of the whole page table?
As TLB is part of the hardware context
- when a context switch occurs, TLB entries are flushed.
- when a process resumes running, many TLB misses will happen to fill TLB
Protection
Access-Right Bits
By adding bits to specify for each page table entry writable, readable, executable, memory access will be checked against the access-right bits.
Valid Bit
A valid bit indicates if the page is valid to access.
- some pages are out of range for particular process
- OS will set valid bits when process is running
- out-of-range access will be caught by the OS
Page sharing
Page tables can allow several processes to share the same physical memory frame
- the same physical frame number in the page table entries
Possible usages
- Shared code pages (shared standard library, system calls)
- Copy-On-Write (share the page, until one changes the value in it)