Paging is a memory management scheme that allows non-contiguous allocation of processes, and which eliminates problems with fragmentation by allocating memory in equal sized blocks known as pages. The basic idea behind paging is to divide physical memory into a number of equal sized blocks called frames, and to divide a programs logical memory space into blocks of the same size called pages. Any page from any process can be placed into any available frame. The page table is used to look up what frame a particular page is stored in at the moment. In the following example, for instance, page 2 of the program’s logical memory is currently stored in frame 3 of physical memory:
A logical address consists of two parts:
- A page number(\(p\) in which the address resides, and
- An offset(\(d\)) from the beginning of that page.
The number of bits in the page number limits how many pages a single process can address. The number of bits in the offset determines the maximum size of each page, and should correspond to the system frame size.
The page table maps the page number to a frame number, to yield a physical address which also has two parts:
- The frame number(\(f\)) and
- The offset(\(d\)) within that frame.
The number of bits in the frame number determines how many frames the system can address, and the number of bits in the offset determines the size of each frame.
Page numbers, frame numbers, and frame sizes are determined by the architecture, but are typically powers of two, allowing addresses to be split at a certain number of bits. For example, if the logical address size is \(2^m\) and the page size is \(2^n\), then the high-order \(m – n\) bits of a logical address designate the page number and the remaining \(n\) bits represent the offset. Note also that the number of bits in the page number and the number of bits in the frame number do not have to be identical. The former determines the address range of the logical address space, and the latter relates to the physical address space.
Consider the following micro example, in which a process has 16 bytes of logical memory, mapped in 4 byte pages into 32 bytes of physical memory. Presumably some other processes would be consuming the remaining 16 bytes of physical memory.
Note that paging is like having a table of relocation registers, one for each page of the logical memory. There is no external fragmentation with paging. All blocks of physical memory are used, and there are no gaps in between and no problems with finding the right sized hole for a particular chunk of memory. There is, however, internal fragmentation. Memory is allocated in chunks the size of a page, and on the average, the last page will only be half full, wasting on the average half a page of memory per process. Possibly more, if processes keep their code and data in separate pages. Larger page sizes waste more memory, but are more efficient in terms of overhead. Modern trends have been to increase page sizes, and some systems even have multiple size pages to try and make the best of both worlds.
When a process requests memory e.g. when its code is loaded in from disk, free frames are allocated from a free-frame list, and inserted into that process’s page table. Processes are blocked from accessing anyone else’s memory because all of their memory requests are mapped through their page table. There is no way for them to generate an address that maps into any other process’s memory space. The operating system must keep track of each individual process’s page table, updating it whenever the process’s pages get moved in and out of memory, and applying the correct page table when processing system calls for a particular process. This all increases the overhead involved when swapping processes in and out of the CPU. The currently active page table must be updated to reflect the process that is currently running.
Hardware Support for Paging
Page lookups must be done for every memory reference, and whenever a process gets swapped in or out of the CPU, its page table must be swapped in and out too, along with the instruction registers, etc. It is therefore appropriate to provide hardware support for this operation, in order to make it as fast as possible and to make process switches as fast as possible also.
One option is to use a set of registers for the page table. For example, the DEC PDP-11 uses 16-bit addressing and 8 KB pages, resulting in only 8 pages per process. It takes 13 bits to address 8 KB of offset, leaving only 3 bits to define a page number.
An alternate option is to store the page table in main memory, and to use a single register called the page-table base register, PTBR to record where in memory the page table is located. Process switching is fast, because only the single register needs to be changed. However memory access just got half as fast, because every memory access now requires two memory accesses – One to fetch the frame number from memory and then another one to access the desired memory location. The solution to this problem is to use a very special high-speed memory device called the translation look-aside buffer, TLB. The benefit of the TLB is that it can search an entire table for a key value in parallel, and if it is found anywhere in the table, then the corresponding lookup value is returned. The TLB is very expensive, however, and therefore very small. Not large enough to hold the entire page table. It is therefore used as a cache device. The percentage of time that the desired information is found in the TLB is termed the hit ratio.
Protection in Paging
The page table can also help to protect processes from accessing memory that they shouldn’t, or their own memory in ways that they shouldn’t. A bit or bits can be added to the page table to classify a page as read-write, read-only, read-write-execute, or some combination of these sorts of things. Then each memory reference can be checked to ensure it is accessing the memory in the appropriate mode. Valid / invalid bits can be added to “mask off” entries in the page table that are not in use by the current process, as shown by example in Figure below.
Note that the valid / invalid bits described above cannot block all illegal memory accesses, due to the internal fragmentation. Areas of memory in the last page that are not entirely filled by the process, and may contain data left over by whoever used that frame last. Many processes do not use all of the page table available to them, particularly in modern systems with very large potential page tables. Rather than waste memory by creating a full-size page table for every process, some systems use a page-table length register, PTLR, to specify the length of the page table.
This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to firstname.lastname@example.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.