Non-contiguous memory allocation

Non-contiguous memory allocation

Non-contiguous memory allocation

            In non-contiguous memory allocation, it is allowed to store the processes in non-contiguous memory locations. There are different techniques used to load processes into memory, as follows:

  1. Paging
  2. Segmentation
  3. Virtual memory paging(Demand paging)



Main memory is divided into a number of equal-sized blocks, are called frames. Each process is divided into a number of the equal-size block of the same length as frames, are called Pages. A process is loaded by loading all of its pages into available frames (may not be contiguous).

The process of Translation from logical to physical addresses

  • 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.
  • If the size of logical-address space is 2m and a page size is 2n addressing units (bytes or words), then the high-order (m – n) bits of a logical address designate the page number and then low-order bits designate the page offset. Thus, the logical address is as follows:

Hardware paging

Hardware Support for Paging:

Each operating system has its own methods for storing page tables. Most operating systems allocate a page table for each process. 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.

Implementation of Page Table

  • Generally, Page table is kept in main memory. The Page Table Base Register (PTBR) points to the page table. And Page-table length register (PRLR) indicates the size of the page table.
  • In this scheme, every data/instruction access requires two memory accesses. One for the page table and one for the data/instruction.
  • The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs).

Paging Hardware With TLB

The TLB is an associative and high-speed memory. Each entry in the TLB consists of two parts: a key (or tag) and a value. The TLB is used with page tables in the following way.

  • The 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 (known as a TLB Hit), its frame number is immediately available and is used to access memory. It takes only one memory access.
  • 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. It takes two memory accesses.
  • In addition, it stores the page number and frame number to the TLB, so that they will be found quickly on the next reference.
  • If the TLB is already full of entries, the operating system must select one for replacement by using replacement algorithm.

Paging Hardware With TLB

(Paging hardware with TLB)

The percentage of times that a particular page number is found in the TLB is called the hit ratio. The effective access time (EAT) is obtained as follows:

EAT= HR x (TLBAT + MAT) + MR x (TLBAT + 2 x MAT)

Where HR: Hit Ratio, TLBAT: TLB access time, MAT: Memory access time, MR: Miss Ratio.

Memory protection in Paged Environment:

  • Memory protection in a paged environment is accomplished by protection bits that are associated with each frame. These bits are kept in the page table.
  • One bit can define a page to be read-write or read-only. This protection bit can be checked to verify that no writes are being made to a read-only page. An attempt to write to a read-only page causes a hardware trap to the operating system (or memory-protection violation).
  • One more bit is attached to each entry in the page table: a valid-invalid When this bit is set to “valid,” this value indicates that the associated page is in the process’ logical-address space, and is a legal (or valid) page. If the bit is set to “invalid,” this value indicates that the page is not in the process’ logical-address space.
  • Illegal addresses are trapped by using the valid-invalid bit. The operating system sets this bit for each page to allow or disallow accesses to that page.

(Valid (v) or invalid (i) bit in a page table)


Structure of the Page Table


There are different structures of page table described as follows:

  1. Hierarchical Page table: When the number of pages is very high, then the page table takes a large amount of memory space. In such cases, we use multilevel paging scheme for reducing the size of the page table. A simple technique is a two-level page table. Since the page table is paged, the page number is further divided into parts: page number and page offset. Thus, a logical address is as follows:

Where pi is an index into the outer page table, and p2 is the displacement within the page of the outer page table.

Two-Level Page-Table Scheme:

Address translation scheme for a two-level paging architecture:


  1. Hashed Page Tables: This scheme is applicable for address space larger than 32bits. In this scheme, the virtual page number is hashed into a page table. This page table contains a chain of elements hashing to the same location. Virtual page numbers are compared in this chain searching for a match. If a match is found, the corresponding physical frame is extracted.

  1. Inverted Page Table:
  • One entry for each real page of memory.
  • The entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page.
  • Decreases memory needed to store each page table, but increases the time needed to search the table when a page reference occurs.



A Computer Science Study for IT students and people of IT community