• 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