Paging in Operating System:

Definition and Explanation:

Physical memory is divided into fixed-size blocks called frames. Logical memory is also divided into the same size blocks called pages. A single process may require many pages of memory. When a process is scheduled for execution, its pages are loaded into any available memory frames from the backing store.
The backing store is also divided into blocks. The blocks are of the same size as the frames in main memory. Paging requires additional hardware support in the form of a page table. Every logical address generated by the CPU consists of two parts:
  • A page number (p)
     
  • A page displacement (d)
The page number is used as an index into the page table. The page table contains the base address of each page in physical memory. This base address is combined with the page displacement to determine the physical memory address. It is then sent to the memory management unit. It completes the translation from logical address to physical address.
The page size and frame size are hardware dependent. It is common that both will contain a number of bytes that is a power of 2. The typical values will range from 512 bytes to 16 MB per page. An integral size based upon a power of two is used due to the ease of translation that can occur with such numbers.
Suppose the logical address space consists of 2m bytes and the page/frame size is 2n bytes. The high-order m-n bits of a logical address will designate the page number. The-low order n bits will designate the page displacement as shown below.
Page number p
Page displacement d
m-n bits
n bits

Example:

Suppose a system has a page size of 8 bytes (23 = 8). The physical memory consists of 1024 bytes. It is divided into 128 frames. Suppose that the logical address space consists of 128 bytes (27 = 128). Thus, m = 7 and n = 3 so the page number will require m-n = 7-3 = 4 bits. The displacement within the page will require n = 3 bits.
The 128 byte logical address space will be divided into a total of 16 pages. It requires a total of 16 frames of physical memory. To distinguish uniquely, 16 possible frames will require 4 bits. A total of 8 bytes of code from the process will be located within each frame. It will require a total of 3 bits to uniquely determine which byte within the page/frame is being referenced by the CPU.
Suppose the CPU generates a logical address of 64. The address is at the mid-point of the process requiring 128 bytes of memory. The physical address corresponding to this logical address will be in page number 8 with displacement 0.
PageDisplacement
01234567
001234567
189101112131415
21617181920212223
32425262728293031
43233343536373839
54041424344454647
64849505152535455
75657585960616263
86465666768697071
97273747576777879
108081828384858687
118889909192939495
1296979899100101102103
13104105106107108109110111
14112113114115116117118119
15120121122123124125126127

The page table contains the "mapping" of the logical pages to the physical frames. This is shown graphically in the next diagram.
Page 0 01 0 
Page 1 14 1Page 0
Page 2 22 2 
Page 3 37 3Page 2
Logical memory Page table 4Page 1
     5 
    6 
    7Page 3
    Physical memory
Using the previous diagram as a reference, assume that each page contains 4 bytes. This means that the logical address space consists of 16 bytes. Page 0 contains logical addresses 0,1,2, and 3. Page 1 contains logical addresses 4,5,6, and 7'and so on.
In the physical memory, frame number 0 holds physical address values 0,1, 2, and 3, frame number 1 holds physical addresses 4,5, 6, and 7, and so on.
Logical address 01 FrameAddress
PageDisplacement1400123
01232314567
00123372891011
14567Page table312131415
2891011 416171819
312131415520212223
Logical memory624252627
 728293031
Physical memory
The page table shows that:
  • Logical page 0 is in physical frame 1
     
  • Logical page 1 is in physical frame 4
     
  • Logical page 2 is in physical frame 3
     
  • Logical page 3 is in physical frame 7
To find logical address 10 in the physical memory, we require to find the physical frame that currently holds logical page 2 since logical address 10 is in logical page 2.
The page table currently shows logical page 2 to be in physical frame 3. Logical address 10 is at displacement 2 in page 2. Physical frame 3 and displacement 2 represents physical address 14. This is the address in the physical memory that currently holds logical address 10. The translation of the logical address to the physical address follows the form:
Physical address = (frame# x number bytes/page) + displacement For this example, we have: (3 x 4) + 2 = 14
Similarly, logical address 7 is page 1 displacement 3 [(1,3)]. The page table shows page 1 in frame number 4 currently so: (4x4)+3 = 19.

Leave a Reply

Subscribe to Posts | Subscribe to Comments

Blog Archive

Powered by Blogger.

- Copyright © 2013 Taqi Shah Blogspot -Metrominimalist- Powered by Blogger - Designed by Johanes Djogan -