CS604 - Operating Systems - Lecture Handout 33

User Rating:  / 0
PoorBest 

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:

Addressing in Paging

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

Another Example

Maximum pages

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.

Logical address

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.

Paging Hardware with 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.