• In my previous post I had discussed about “Fragmentation” and how it can be solve. In this and later post, I will discuss some of the memory allocation techniques that can be helpful to lower the amount of fragmentation such as Paging and Segmentation. In this post I am going to discuss about the paging technique and Segmentation will be discussed in the next post.
  • External fragmentation can be solved by allocating non-contiguous address space to a process. This can be achieved by implementing paging scheme. Paging avoids the problem of different sized memory blocks to be fit for the process.

Basic Method

  • In paging, a process is divided into different pages of the same size. In the logical view, a process consists of a linear arrangement of pages.
  • Each page of the process has s bytes in it. The value of the s is a power of 2 and it is usually defined in the computer architecture.
  • The computer hardware performs decomposition of the logical address into the form of (pi, bi ).
  • Pi is the page number of the process and bi is an offset in pi (0<=bi<s). The physical view consists of non-adjacent memory areas allocated to pages of the process. These pages are numbered from 0 to max and bytes in a page are numbered from 0 to 1023.
  • The kernel partitions the memory areas into page frames. Size of each page frame is the same as the size of the page. Page frames are also numbered from 0 to max.
  • Page frames are allocated to program pages. Since both page and page frame have the same size, one frame is allocated for each program page. The kernel maintains a free frame list to note the IDs of free page frames.

Paging

  • A page table (PT) is prepared for each process. It contains page numbers and page frames allocated to those pages. The MMU uses page table to perform address translation.
  • The above figure illustrates the arrangement of processes P and R in the system using paging. Suppose that size of the process P is 5500 bytes and the page size is 1K bytes.
  • So the process p is divided into 6 pages which are numbered from 0 to 5 and process R is divided into 3 pages, numbered from 0 to 2. The computer has a memory of 10K bytes. So memory is divided into 10 page frames of the same size i.e. 1K bytes.
  • The kernel checks free frame list and allocates a free page frame to each page of the process. The page tables of the process P and process R contains page frames allocated to their pages. After allocation of page frames to each page we have only one free frame of number 4.
  • The figure illustrates that six page frames are occupied by process P, and three page frames are occupied by process R.
  • The last page of the process P contains only 380 bytes. If a data itemsample has the address 5248, the computer hardware would view its address as the pair (5,128). The logical address (5,128) would be translated into the physical address 8320 using the entry for page 5 in the page table.

Paging Hardware Support

  • Each O/S has its own method for storing page tables. Most allocate a page table for each process.
  • A pointer to the page table is stored with other register’s value in the PBC. The H/W implementation at page table can be done in various ways.
  • In the simplest case, the page table is implemented as a set of dedicated registers. The page tables are very large for this mechanism to store all pages.
  • Rather than storing page table into registers it is kept in main memory.  One register, page table base register (PTBR) points to the page table. Changing page table requires changing the value of only this register. This way there is no limitation for storing large page table as it is stored in memory instead of dedicated registers.

Memory Protection in pages

  • Memory Protection in paged environment is implemented by protection bits that is associated with each frame.
  • Normally these bits are present in a page table.
  • One bit can define a page to be read-write or read only.
  • Every memory reference looks into the page table to find the current page number.
  • At the same time physical address is computed the protection bits are checked to verify that no writes are being made to a read only page.
  • An attempted to write to read only page causes a hard-trap to the operating system. (Memory Protection Violation).
  • One more bit generally attached in page table that is called valid– invalid bits.
  • When this bit is set to valid, it indicates that the associated page is present in logical address space and it is the legal (valid) page.
  • Illegal addresses are finding using other valid and invalid page.
  • Some system provide hardware in the form of a page table length register (PTLR). It indicates size of the page table. This value is checked against every logical address and verifies that address is in valid range.