Paging

Paging

• In paging, operating system divides each incoming programs into pages of equal size. The sections of a disk are called block or sectors. The sections of main memory are called page frames. One sector will hold one page of job instructions and fit into one page frame of memory.

      • In paging, logical address space of a program can be noncontiguous. It solves external fragmentation problem.

      • The relation between virtual addresses and physical memory addresses given by page table.

• Fixed sized blocks are called frames and breaking of logical memory into blocks of same size called pages.

• Memory manager prepares following things before executing a program :

1. Find out the number of pages in the program.

2. Free space in the main memory.

3. Loading of all the programs pages into memory.

• Pages are not loaded continuosly in main memory. Each page can be stored in any available page frame anywhere in main memory. Memory manager keeps the track of pages of program. Paging avoids external fragmentation and need for grint compaction.

• Memory manager uses three tables to keep track of process and memory.

1. Job table: It stores the size of the active job and memory location where its page table is stored.

2. Page map table: It contains vital information about each page. PMT contains apage number and corresponding page frame memory address. It includes only one entry per page. Page numbers are in sequential order.

3. Memory map table: MMT is used to store page frame location and its status. 

• Page size depends upon underlying hardware. Operating system maintains a page table for each process. The page table shows the frame location for each page of a process. Fig. 4.5.1 shows the virtual address format for paging system.

• Processor hardware performs the logical to physical address translation. Logical address contains page number and offset. The physical address contains frame number and offset. Offset is a relative factor. It is used to locate that line within its page frame.

• Fig. 4.5.2 shows address translation.

• Suppose a system uses n-bit for representing both physical and virtual address. The page number is represented by the most significant bit (n - m bits) and the displacement is represented by m bit.

• The table, which holds virtual address to physical address translations is called page table. As displacement is constant, so only translation of virtual page number to physical page is required.

• Fig. 4.5.3 shows paging hardware. CPU generates logical addresses containing page number and an offset. This page number is used to retrieve the frame number from a page table which gives the base address so the physical address is calculated as base + offset.

• Paging implementation requires CPU and operating system support. Page table may itself be resident in main memory.

• Active process is loaded into memory and it occupies number of pages. This set of pages forms its resident set. Hardware defined the page size.

• The processor generates virtual (logical) address and it consists of two parts:

1. Page number

2. Page offset (Displacement)

• Page table contains page number and index frame number. Page number is used as an index into a page table.

• In case of simple partition, a logical address is the location of a word relative to the beginning of the program the processor translates that into a real address.

• But in the paging method the logical to real address translation is still done by processor hardware. The processor must know how to access the page table of the current process.

• The operating system partitions the memory into areas called page frames page frame size is equal. Page size is normally power of 2.

• Fig. 4.5.4 shows a paging model. Operating system maintains the free frame list. During execution of process the memory management unit consults the page table to perform address translation.

• The physical address is the portion of the primary memory allocated to the process. The page frames allocated to the process need not be contiguous.

• The aim of the paging system is to identify the set of pages needed for the process current locality and then to load only those pages into page frames in primary memory.

• The logic of the address translation process in paged system is shown in the following Fig. 4.5.5.

• For example, the virtual address is 03200H. This virtual address is split by dos hardware into the page number and offset within that page. High order 12 bit is used as page number i.e. 003H and lower order 12 bit is used for the offset i.e. (200H).

• Page number is used to index the page table and to obtain the corresponding physical frame number (FFFH). This value is then concatenated with the offset to produce the physical address (FFF200H) which is used to reference the target item in memory.

• The operating system keeps track of the status of each page frame by means of a physical memory map that may be structured as a static table. The logical address space may be the same size as the physical address space or it may be smaller.

• If logical address space is small, it prevents one process from monopolizing all of the memory. If the logical address space is larger than the physical address space, all pages could not be resident in physical memory. Simple paging has no capability for dealing with references to pages that are not in memory.

Protection and Sharing

• Protection bit is used for provide protection to the memory. Page table adds one more column for providing protection bit.

• One bit field define a page to be read only or read-write operation. This field is read at the time of calculating physical address of memory.

• Fig. 4.5.6 shows protection bit with page table.

• When valid bit is set, the required page is in the process logical address space and the page is valid. If invalid bit is set, the page is not in the process logical address space.

Paging with TLB

• Set of registers are used for implementing page table. Registers are suitable only for small page table. If page table size increases then special purpose hardware cache is used for page table.

• Special cache memory called a Translation Lookaside Buffer (TLB) is used with the address translation hardware. The full page table is kept in primary memory.

• TLB is very effective in improving the performance of page frame access. The cache buffer is implemented in a technology which is faster than the primary memory technology.

• Fig. 4.5.7 shows paging with TLB

• The TLB contents may be controlled by the operating system or by hardware, depending on the architecture.

• When a page is first translated to a page frame, the map is read from primary memory into the TLB. The TLB entry contains the page number, page frame's physical address etc.

• The page mapping mechanism first tries to find page number in the TLB. If the TLB contains the page number, then it is called as page hit or TLB hit.

• If the TLB does not contain an entry for page p, then it called as page miss or TLB miss. In case of TLB miss, the operating system locates the page table entry in the primary memory, which increases execution time.

• The TLB is associative, high-speed memory. A translation buffer is used to store a few of the translation table entries. It is very fast, but only for a small number of entries. On each memory reference.

1. First ask TLB if it knows about the page. If so, the reference proceeds fast.

2. If TLB has no information for page, must go through page and segment table to get information. Reference takes a long time, but gives the info for this page to TLB so it will know it for next reference.

• The greatest performance improvement is achieved when the associative memory is significantly faster than the normal page table lookup and the hit ratio is high. The hit ratio is the ratio between accesses that find a match in the associative memory and those that do not.

• Disadvantage of TLB is that: If two pages use the same entry of the memory, only one of them can be remembered at once. If process is referencing both pages at same time, TLB does not work very well.

• Each entry in the TLB must include the page number as well as the complete page table entry. The processor is equipped with hardware that allows it to simultaneously interrogate a number of TLB entries to determine if there is a match on page number. This technique is referred to as associative mapping.

Advantages of Paging

1. Paging eliminates fragmentation.

2. Support higher degree of multiprogramming.

3. Paging increases memory and processor utilization.

4. Compaction overhead required for the relocatable partition scheme is also eliminated.

Disadvantages of Paging

1. Page address mapping hardware usually increases the cost of the computer.

2. Memory must be used to store the various tables like page table, memory map table etc.