- Alternate meanings: See paging (telecommunications). Bank switching is also sometimes referred to as paging.
In computer operating systems, paging memory allocation (also called memory address translation) algorithms divide computer memory into small partitions, and allocates memory using a page as the smallest building block.
|
Contents
- 1 Advantages
- 2 Disadvantages
- 3 How it works
- 4 Paging and virtual memory
- 5 See also
|
Advantages
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 external 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.
Paging also provides a powerful mechanism for memory protection. A process that attempts to address space outside of its page range will generate a fault.
Disadvantages
One disadvantage of paging is the relatively complicated nature of the code required to handle it, especially if virtual memory is to be implemented. There is also a need for a memory management unit (MMU), which means that paging cannot be implemented on some older or smaller processors. It is also possible for internal fragmentation to occur, when, for example, a little more memory is required to store some data than the size of a page. In this case, a whole new page must be allocated to that data, while only a small fraction of the potential storage space within that page is being used. This kind of fragmentation also occurs when less memory is required to save some data than the size of a page.
The greatest disadvantage in paging lies in its effect upon shared memory Inter-Process Communication (IPC). Where one process shares an address-space with another, it isn't possible to point at code or data held by the other process. This is of great utility to memory protection as it prevents accidental (and much intentional) data corruption and data spying. However, it becomes necessary to communicate by the somewhat slower message passing mechanisms that generally involve context-switches and one or more memory-space copies of the message (e.g. copy to kernel-space, then copy to the remote process), plus potential costs for marshalling the message prior to delivery and unmarshalling it upon receipt. This has a significant effect on kernel design, and is among the fundamental reasons that microkernels (which must do much IPC) are generally slower than monolithic kernels. It also has the effect of discouraging arbitrary IPC between user-space processes (though whether that should be considered an advantage or disadvantage is questionable).
It is possible to overcome this IPC disadvantage somewhat by mapping some fragment of the virtual address space to the same physical locations for two or more processes. Memory mapped thusly is effectively shared between the processes, and will effectively retain internal pointer references within that space. Further, its use by any given process will be intentional, rather than accidental. However, marshalling (especially of structures with pointers) and copying of data to this shared space is still necessary.
How it works
The memory access part of paging is done at the hardware level via page tables, and is handled by the memory management unit. As mentioned earlier, physical memory is divided into small blocks called pages (typically 4 kibibytes 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 former). Whatever the case, when a program makes a request 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.
The table below is an example page allocation list which could result if the following allocations happened in this order:
- 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
| Frame Number |
Page 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 |
Consequently, Program A's page tables would contain the following mapping (Program's Page #=>OS Page #): (0=>0, 1=>1, 2=>2); Program B's : (0=>3,1=>4,2=>7); and Program D's : (0=>5, 1=>6).
Now let's consider what happens when a program wants to access its own memory. Let's say Program A contains a statement "LOAD memory at 20FE". What happens? Let's take a look at it now.
20FE is 0010000011111110 in binary notation (in a 16-bit system), and we have pages of 4K in size. So when a request for memory at 20FE is made, the MMU looks at it in this way :
0010000011111110 = 20FE
|__||__________|
| |
| v
v Relative memory address in page (00FE)
Page Number (2)
Because we have pages 4096 bytes 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 a smaller page size means 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 second page of Program A maps to the second OS page. Then, it looks for the physical mapping of the OS page. The second OS page maps to the physical memory address 1000:2000, and the relative memory address that the program wants is 00FE, so the MMU will return memory at the physical address 1000:20FE.
This is a general description. Modern computer architectures use various means to speed up paging. For example on the Intel i386 architecture used in personal computers, among others, the CPU employs a special cache called Translation Lookaside Buffer which contains the mapping between a virtual memory address and the physical address it is backed by. Thus between the first time this mapping is obtained by page table lookups until the physical page is evicted or swapped out, the computationally expensive page table lookups need not be repeated, since the result is cached in the TLB. It is the job of the operating system to delete a particular entry from the TLB when this mapping becomes invalid. But as long as the entry is valid it can save thousands or millions of page table references.
Paging and virtual memory
When paging is used alongside with virtual memory, the operating system has to keep track of pages in use and pages which will not be used or have not been used for some time. Then, when the operating system deems fit, or when a program requests a page that has been swapped out, the operating system swaps out a page to disk, and brings another page into memory. (See Page replacement algorithms for more details as to how the operating system decides which page to swap in and out.) In this way, you can use more memory than your computer physically has.
See also
- Demand paging
- Page replacement algorithm
Categories: Virtual memory | Memory management
