Explain paging in detail. Describe how logical address is converted into physical address?
1 Answer
  • 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

enter image description here

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.

enter image description here

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

enter image description here

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.

enter image description here

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.

enter image description here

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

enter image description here

Please log in to add an answer.