Basic Method

• The basic method for implementing paging involves
  • breaking physical memory into fixed-sized blocks called frames
  • breaking logical memory into blocks of the same size called pages.
• When a process is to be executed, its pages are loaded into any available memory frames from the backing store.
• The backing store is divided into fixed-sized blocks that are of the same size as the memory frames.

  Figure 5: Paging hardware.

  
• The hardware support for paging is illustrated in Fig. 5.
  • Every address generated by the CPU is divided into two parts: a page number ($p$) and a page offset ($d$).
  • The page number is used as an index into a page table.
  • The page table contains the base address of each page in physical memory.
  • This base address is combined with the page offset to define the physical memory address that is sent to the memory unit.
• The paging model of memory is shown in Fig. 6.

  Figure 6: Paging model of logical and physical memory.

  
• The page size (like the frame size) is defined by the hardware. The size of a page is typically a power of 2, varying between 512 bytes and 16 MB per page, depending on the computer architecture.
• Consider the memory in Fig. 7. Using a page size of 4 bytes and a physical memory of 32 bytes (8 pages). It is shown that how the user's view of memory can be mapped into physical memory.
  • Logical address 0 is page O, offset O. Indexing into the page table, we find that page 0 is in frame 5. Thus, logical address 0 maps to physical address 20 (= (5 x 4) + 0).
  • Logical address 3 (page 0, offset 3) maps to physical address 23 (= (5 x 4) + 3).
  • Logical address 4 is page 1, offset 0; according to the page table, page 1 is mapped to frame 6. Thus, logical address 4 maps to physical address 24 (= (6 x 4) + 0).
  • Logical address 13 maps to physical address 9.

  Figure 7: Paging example for a 32-byte memory with 4-byte pages.

  
• Every logical address is bound by the paging hardware to some physical address. Using paging is similar to using a table of base (or relocation) registers, one for each frame of memory.
• When we use a paging scheme, we have no external fragmentation:
  • Any free frame can be allocated to a process that needs it. However, we may have some internal fragmentation.
  • Notice that frames are allocated as units. If the memory requirements of a process do not happen to coincide with page boundaries, the last frame allocated may not be completely full. For example,
    • if page size is 2,048 bytes, a process of 72,766 bytes would need 35 pages plus 1,086 bytes.
    • It would be allocated 36 frames, resulting in an internal fragmentation of 2,048 - 1,086 = 962 bytes.
    • In the worst case, a process would need $n$ pages plus 1 byte. It would be allocated $n + 1$ frames, resulting in an internal fragmentation of almost an entire frame.
• If process size is independent of page size, we expect internal fragmentation to average one-half page per process.
• This consideration suggests that small page sizes are desirable.
• However, overhead is involved in each page-table entry, and this overhead is reduced as the size of the pages increases. Also, disk I/O is more efficient when the number of data being transferred is larger.
• Generally, page sizes have grown over time as processes, data sets, and main memory have become larger.
• Today, pages typically are between 4 KB and 8 KB in size, and some systems support even larger page sizes.
• Usually, each page-table entry is 4 bytes long, but that size can vary as well. A 32-bit entry can point to one of $2^{32}$ physical page frames.
• If frame size is 4 KB, then a system with 4-byte entries can address $2^{44} (4KB*2^{32})$ bytes (or 16 TB) of physical memory.
• When a process arrives in the system to be executed,
  • Its size, expressed in pages, is examined. Each page of the process needs one frame.
  • Thus, if the process requires $n$ pages, at least $n$ frames must be available in memory. If $n$ frames are available, they are allocated to this arriving process.
  • The first page of the process is loaded into one of the allocated frames, and the frame number is put in the page table for this process.
  • The next page is loaded into another frame, and its frame number is put into the page table, and so on (see Fig. 8).

  Figure 8: Free frames (a) before allocation and (b) after allocation.

  
• An important aspect of paging is the clear separation between the user's view of memory and the actual physical memory.
• The user program views memory as one single space, containing only this one program. In fact, the user program is scattered throughout physical memory, which also holds other programs.
• The logical addresses are translated into physical addresses by the address-translation hardware. This mapping is hidden from the user and is controlled by the OS.
• The user process has no way of addressing memory outside of its page table, and the table includes only those pages that the process owns.
• Since the OS is managing physical memory, it must be aware of the allocation details of physical memory-which frames are allocated, which frames are available, how many total frames there are, and so on.
• This information is generally kept in a data structure called a frame table. The frame table has one entry for each physical page frame, indicating whether the latter is free or allocated and, if it is allocated, to which page of which process or processes.