| Table of contents |
|
2 Advantages 3 Disadvantages 4 How it works 5 Paging and virtual memory |
In computer operating systems, paging is the algorithm that divides computer memory into small partitions, and allocates memory using a page as the basic building block.
A key advantage that this method has over simpler methods such as the buddy memory allocation technique and dynamic allocation techniques is that the memory allocated to a program does not have to be contiguous, and because of that, there is very little internal fragmentation - thus little memory is wasted.
Because programs rarely use all parts of their code and data at one point in time, the concept of virtual memory can be implemented by writing pages to disk, and reading pages from disk when they are needed. This is another advantage of paging over other memory allocation techniques.
The only major disadvantage of paging is the relatively complicated nature of the code required to handle it, especially if virtual memory is to be implemented. Otherwise, there are only minor disadvantages such as the need for a memory management unit, which means that paging cannot be implemented on 286 or lower computers.
The memory access part of paging is done at the hardware level, and is handled by the memory management unit (MMU for short), available only on 386+ computers. As mentioned earlier, physical memory is divided into small blocks (typically 4 kilobytes or less) in size, and each block is assigned a page number. The operating system may keep a list of free pages in its memory, or may choose to probe the memory each time a memory request is made (though most modern operating systems do the latter). Whatever the case, when a program requests for memory, the operating system allocates a number of pages to the program, and keeps a list of allocated pages for that particular program in memory. Now, let us take a look at an example.
Definition
Advantages
Disadvantages
How it works
| Page Number | Program Allocated to | Physical Memory Address |
|---|---|---|
| 0 | Program A.0 | 1000:0000 |
| 1 | Program A.1 | 1000:1000 |
| 2 | Program A.2 | 1000:2000 |
| 3 | Program B.0 | 1000:3000 |
| 4 | Program B.1 | 1000:4000 |
| 5 | Program D.0 | 1000:5000 |
| 6 | Program D.1 | 1000:6000 |
| 7 | Program B.2 | 1000:7000 |
- Program A requests 3 pages of memory
- Program C requests 2 pages of memory
- Program D requests 2 pages of memory
- Program C terminates, leaving 2 empty pages
- Program B requests 3 pages of memory, and it is allocated the 2 empty pages that program C left, plus an additional page after program D
Ok. So far so good. But what happens when a program wants to access its own memory? Let's say Program A contains a statement "LOAD memory at 30FE". What happens? Let's take a look at it now.
30FE is 0011000011111110 in binary notation (in a 16-bit system), and we have pages of 4K in size. So when a request for memory at 30FE is made, the MMU looks at it in this way :
\r\n0011000011111110 = 30FE\r\n|__||__________|\r\n | |\r\n | v\r\n v Relative memory address in page (00FE)\r\nPage Number (3)\r\n
Because we have pages 4096 bytes (4096-1 = 4095 can be represented by 12 bits in binary) in size, the MMU looks at the first 4 bits for the page number, and the next 12 bits for the relative memory address in the page. If our pages were 2048 bytes in size, the MMU would look at the first 5 bits for the page number, and the next 11 bits for the relative memory address. So smaller pages mean more pages.
Thus, when this memory access request is made, the MMU looks at the program's page tables for the mapping to the OS page number. In this case, the first page of Program A maps to the first OS page. Then, it looks for the physical mapping of the OS page. The first OS page maps to the physical memory address 1000:1000, and the relative memory address that the program wants is 00FE, so the MMU will return memory at the physical address 1000:10FE.
