/ 0
Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems
Summary
- Addressing and logical to physical address translation
- Examples: Intel P4 and PDP-11
- Page table implementation
- Performance of paging
Addressing in Paging
The page size is defined by the CPU hardware. If the size of logical address space is 2m and a page size is 2n addressing units (bytes or words) , then the high-order m-n bits of a logical address designate the page number and the n low order bits designate offset within the page. Thus, the logical address is as follows:
Example:
Assume a logical address space of 16 pages of 1024 words, each mapped into a physical memory of 32 frames. Here is how you calculate the various parameters related to paging.
No. of bits needed for p = ceiling [log2 16] bits = 4 bits
No. of bits neede for f = ceiling [log2 32] bits = 5 bits
No. of bits needed for d = ceiling [log2 2048] bits = 11 bits
Logical address size = |p| + |d| = 4+11 bits = 15 bits
Physical address size = |f| + |d| = 5+11 bits = 16 bits
Page Table Size
Page table size = NP * PTES , where NP is the number of pages in the process address space and PTES is the page table entry size (equal to |f| based on our discussion so far).
Page table size = 16 * 5 bits (for the above example; assuming a byte size page table entry)
Paging in Intel P4
32-bit linear address
4K page size
Maximum pages in a process address space = 232 / 4K
Number of bits needed for d = log2 4K bits = 12 bits
Number of bits needed for p = 32 – 12 bits =20
Paging in PDP-11
16-bit logical address
8K page size
Maximum pages in a process address space = 216 / 8K = 8
|d| = log2 8K = 13 bits
|p| = 16 – 13 = 3 bits
Another Example
Logical address = 32-bit
Implementation of Page table
- In the CPU registers
This is OK for small process address spaces and large page sizes. It has the advantage of having effective memory access time (Teffective) about the same as memory access time (Tmem). An example of this implementation is in PDP-11. - In the main memory
A page table base register (PTBR) is needed to point to the page table. With page table in main memory, the effective memory access time, Teffective, is 2Tmem , which is not acceptable because it would slow down program execution by a factor of two. - In the translation look-aside buffer (TLB)
A solution to this problem is to use special, small, fast lookup hardware, called translation look-aside buffer (TLB), which typically has 64–1024 entries. Each entry is (key, value). The key is searched for in parallel; on a hit, value is returned. The (key,value) pair is (p,f) for paging. For a logical address, (p,d), TLB is searched for p. If an entry with a key p is found, we have a hit and f is used to form the physical address.
Else, page table in the main memory is searched.
The TLB is loaded with the (p,f) pair so that future references to p are found in the TLB, resulting in improved hit ratio. On a context switch, the TLB is flushed and is loaded with values for the scheduled process. Here is the hardware support needed for paging with part of the page table stored in TLB.
Performance of Paging
We discuss performance of paging in this section. The performance measure is the effective memory access time. With part of the page table in the TLB and the rest in the main memory, the effective memory access time on a hit is Tmem + TTLB and on a miss is 2Tmem + TTLB.
If HR is hit ratio and MR is miss ratio, the effective access time is given by the following equation
Teffective = HR (TTLB + Tmem) + MR (TTLB + 2Tmem)
We give a few examples to help you better understand this equation.
Example 1
Tmem = 100 nsec
TTLB = 20 nsec
Hit ratio is 80%
Teffective = 0.8 (20 + 100) + 0.2 (20 + 2*100) nanoseconds = 140 nanoseconds
This means that with 80% chances of finding a page table entry in the TLB, the effective access time becomes 40% worse than memory access time without paging.
Example 2
Tmem = 100 nsec
TTLB = 20 nsec
Hit ratio is 98%
Teffective = 0.98 (20 + 100) + 0.02 (20 + 2*100) nanoseconds = 122 nanoseconds
This means that with 98% chances of finding a page table entry in the TLB, the effective access time becomes 22% worse than memory access time without paging. This means that with a small cache and good hit ratio, we can maintain most of the page table in the main memory and get much better performance than keeping the page table in the main memory and not using any cache.
Google +