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.
| Page | Displacement | |||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 2 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 3 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
| 4 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 |
| 5 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
| 6 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 |
| 7 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 |
| 8 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 |
| 9 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 |
| 10 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 |
| 11 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 |
| 12 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 |
| 13 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 |
| 14 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 |
| 15 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 |
The page table contains the "mapping" of the logical pages to the physical frames. This is shown graphically in the next diagram.
| Page 0 | 0 | 1 | 0 | |||
| Page 1 | 1 | 4 | 1 | Page 0 | ||
| Page 2 | 2 | 2 | 2 | |||
| Page 3 | 3 | 7 | 3 | Page 2 | ||
| Logical memory | Page table | 4 | Page 1 | |||
| 5 | ||||||
| 6 | ||||||
| 7 | Page 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 | 0 | 1 | Frame | Address | |||||||||
| Page | Displacement | 1 | 4 | 0 | 0 | 1 | 2 | 3 | |||||
| 0 | 1 | 2 | 3 | 2 | 3 | 1 | 4 | 5 | 6 | 7 | |||
| 0 | 0 | 1 | 2 | 3 | 3 | 7 | 2 | 8 | 9 | 10 | 11 | ||
| 1 | 4 | 5 | 6 | 7 | Page table | 3 | 12 | 13 | 14 | 15 | |||
| 2 | 8 | 9 | 10 | 11 | 4 | 16 | 17 | 18 | 19 | ||||
| 3 | 12 | 13 | 14 | 15 | 5 | 20 | 21 | 22 | 23 | ||||
| Logical memory | 6 | 24 | 25 | 26 | 27 | ||||||||
| 7 | 28 | 29 | 30 | 31 | |||||||||
| 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.
