Operating System – Page I

The memory-management scheme that permits the physical-address space of a process to be noncontiguous. Paging avoids the considerable problem of fitting the varying-sized memory chunks onto the backing store.

The paging in its various forms is commonly used in most operating systems.

  • Frames Vs. Paging
    • Frame
      Physical memory is broken into fixed-sized blocks called frame
    • Pages
      Logical memory is broken into blocks of the same size called pages

    When a process is to executed, it’s pages are loaded into any available memory frames from the blocking store. The backing store is divided into fixed-sized blocks that are of the same size as the memory frames.

    Paging itself is a form of dynamic relocation. 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) register, one for each frame of memory.

  • Page Table
    Every address generated by the CPU is divided into two parts: a page number p and a page offset d
    • page number

      The page number is used as an index into a page table.

      page table contains the base address of each page in physical memory. The base address is combined with the page offset to define the physical memory address that is sent to the memory unit.

    • page size

      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.The high-order m-n bits of a logical address designed the page number, and the n low-order bits designed the page offset.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 4KB and 8KB, and some systems support even larger page size.

      Each page-table entry is usually 4 bytes long, but that size can vary as well.

      overhead: Work or information that provides support – possible critical support – for a computing process but is not an intrinsic part of the operation or data. Overhead often adds to processing time but is generally necessary.

  • Advantage and disadvantage
    no external fragmentation
    When we use a paging scheme, we have no external fragmentation:
    Any free frame can be allocated to a process that needs it.

    have internal fragmentation
    We may have some internal fragmentation. Notice that frames are allocated as units. If the memory requirements of a process do not happen to fall on page boundaries, the last frame allocated may not be completely full.
    In the worst case, a process would need n pages plus one byte. It would be allocated n+1 frames, resulting in an internal fragmentation of almost an entire frame ( extra need a frame, only add the 1 byte)

  • The produce from the page to frame

    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 require n pages, at least n frames must be available in memory. If n frames are available, they are allocated to this arriving process.The fist 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

  • User aspect and operating system aspect

    User aspect
    The user program views that memory as one single contiguous space, containing only this one program.

    System aspect
    System view the actual physical memory. In fact, the user program is scattered throughout physical memory, which also holds other programs.

    The difference between the user’s view of memory and the actual physical memory is reconciled by the address-translation hardware. The logical addresses are translated into physical address.
    This mapping is hidden from the user and is controlled by the operating system.

    The user process by definition is unable to access memory it does not own. It has no way of addressing memory outside of its page table, and the table includes only those pages that the process owns.

  • The things managed by operating system
    • 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.
    • Operation of the user process in user space
      If a user makes a system call (to do I/O, for example) and provides an address as a parameter(a buffer for instance), that address must be mapped to produce the correct physical address.The operating system maintains a copy of the page table for each process, just as it maintains a copy of the instruction counter and register contents. This copy is used to translate logical address to physical addresses whenever the operating system must map a logical address to a physical address manually. It is also used by the CPU dispatcher to define the hardware page table when a process is to be allocated the CPU. Paging therefore increases the context-switch time.
  • The hardware support in paging

    Each operating system has its own methods for storing page tables.

    A pointer to the page table is stored with the other register values (like the instruction counter) in the process control block. When the dispatcher is told to start a process, it must reload the user registers and define the correct hardware page-table values from the stored user page table.

    • The different way storing the page-table

      A set of dedicated register
      A the simplest case, the page table is implemented as a set of dedicated registers.
      These registers should be built with very high-speed logic to make the paging-address translation efficient. Every access to memory must go through the paging map, so efficiency is a major consideration.
      The CPU dispatcher reload these registers, just as it reloads the other registers. Instructions to load or modify the page-table register are, of course, privileged, so that only the operating system can change the memory map.

      This scheme only satisfy the the page table is small. When the page table to be very large (for example 1 million entries), the use of fast registers to implement the page table is not feasible.

      A page-table base register (PTBR)
      The page table is kept in main memory, and a page-table base register (PTBR) points to the page table. Changing page table requires changing only this one register, substantially reducing context-switch time.

      The problem with this approach is the time required to access a user memory location.
      First, finding the page-table with PTBR need to access a user memory location
      Second, accessing the desired place in memory also need to access a user memory locations

      Translation look-aside buffer (TLB)
      To use a special, small, fast-lookup hardware cache, called translation look-aside buffer (TLB).
      The TLB is associative, high-speed memory.
      Each entry in the TLB consists of two parts: a key( or tag) and a value.
      When the associative memory is presented with an item, it is compared with all keys simultaneously.

      • If the item is found:
        The corresponding value field is returned. The search is fast; the hardware, however, is expensive

      Typically, the number of entries in a TLB is small, often numbering between 64 and 1,024

    • The mechanism of the TLBThe TLB contains only a few of the page-table entries.
      When a logical address is generated by the CPU, its page number is presented to the TLB.

      If the page number is found
      its frame number is immediately available and is used to access memory. The whole task is very fast.

      If the page number is not in the TLB
      known as a TLB miss
      A memory reference to the page table must be made. When the frame number is obtained, we can use it to access memory. In addition, we add the page number and frame number to the TLB, so that they will be found quickly on the next reference.

      If the TL is already full of entries
      The operating system must select one for replacement.
      Replacement policies ranger from leat recently used (LRU) to random.
      Furthermore, some TLBs allow entries to be wired down, meaning that they cannot be removed from the TLB, TLB entries for kernel code are often wired down.

    • The protection method of the TLB

      support address-space identifiers (ASIDs)
      Some TLBs store address-space identifiers (ASIDs) in each entry of the TLB. An ASID uniquely identifies each process and is used to provide address space protection for that process.
      When the TLB attempts to resolve virtual page numbers, it ensures the ASID for the currently running process matches the ASID associated with the virtual page.
      If the ASIDs do not match, they are treated as a TLB miss.
      In addition to providing address-space protection, an ASID allows the TLB to contain entries for several different processes simultaneously.
      not support ASIDs
      every time a new page table is selected (for instace, each context switch), the TLB must be flushed (or erased) to ensure that the next executing process does not use the wrong translation information.
      Otherwise, there could be old entries in the TLB that contain vaild virtual addresses but have incorrect or invalid physical addresses left over from the previous process.

      The percentage of times that a particular page number is found in the TLB is called the hit ratio.