Spread Knowledge

CS604 - Operating Systems - Lecture Handout 32

User Rating:  / 0

Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems


  • MVT
  • Paging
  • Logical to physical address translation

Multiprogramming with Variable Tasks (MVT)

This is the generalization of the fixed partition scheme. It is used primarily in a batch environment. This scheme of memory management was first introduced in IBM OS/MVT (multiprogramming with a varying number of tasks). Here are the main characteristics of MVT.

  • Both the number and size of the partitions change with time.
  • Job still has only one segment (as with MFT) but now can be of any size up to the size of the machine and can change with time.
  • A single ready list.
  • Job can move (might be swapped back in a different place).
  • This is dynamic address translation (during run time).
  • Must perform an addition on every memory reference (i.e. on every address translation) to add the start address of the partition.
  • Eliminates internal fragmentation.
    • Find a region the exact right size (leave a hole for the remainder).
    • Not quite true, can't get a piece with 10A755 bytes. Would get say 10A760.
      But internal fragmentation is much reduced compared to MFT. Indeed, we say that internal fragmentation has been eliminated.
  • Introduces external fragmentation, i.e., holes outside any region.
  • What do you do if no hole is big enough for the request?
    • Can compact memory
      • Transition from bar 3 to bar 4 in diagram below.
      • This is expensive.
      • Not suitable for real time systems.
    • Can swap out one process to bring in another
      • Bars 5-6 and 6-7 in the following diagram

Multiprorgamming with Variable Tasks

External fragmentation

As processes come and go, holes of free space are created in the main memory. External Fragmentation refers to the situation when free memory space exists to load a process in the memory but the space is not contiguous. Compaction eliminates external fragmentation by shuffling memory contents (processes) to place all free memory into one large block. The cost of compaction is slower execution of processes as compaction takes place.


In the memory management techniques discussed so far, two Paging is a memory management scheme that permits the physical address space of a process to be noncontiguous.
It avoids the considerable problem of fitting the various sized memory chunks onto the backing store, from which most of the previous memory-management schemes suffered. When some code fragments or data residing in main memory need to be swapped out, space must be found on the backing store. The fragmentation problems discussed in connection with main memory are also prevalent with backing store, except that access is much slower so compaction is impossible.
Physical memory is broken down into fixed-sized blocks, called frames, and logical memory is divided into blocks of the same size, called pages. The size of a page is a power of 2, the typical page table size lying between 1K and16K. It is important to keep track of all free frames. In order to run a program of size n pages, we find n free frames and load program pages into these frames. In order to keep track of a program’s pages in the main memory a page table is used.

Thus when a process is to be executed, its pages are loaded into any available memory frames from the backing store. The following snapshots show process address space with pages (i.e., logical address space), physical address space with frames, loading of paging into frames, and storing mapping of pages into frames in a page table.


Mapping paging in the logical into the frames in the physical address space and keeping this mapping in the page table

Every logical address generated by the CPU is divided into two parts: a page number (p) and a page offset (d). The page table contains the base address (frame number) of each page in physical memory. The frame number is combined with the page offset to obtain the physical memory address of the memory location that contains the object addressed by the corresponding logical address. Here p is used to index the process page table; page table entry contains the frame number, f, where page p is loaded. The physical address of the location referenced by (p,d) is computed by appending d at the end of f, as shown below:

hardware support

The hardware support needed for this address translation is shown below.

Hardware support for paging

Paging itself is a form of dynamic relocation. When we use a paging scheme, we have no external fragmentation; however we may have internal fragmentation. An important aspect of paging is the clear separation between the user’s view of memory and the actual physical memory. The user views that memory as one single contiguous space, containing only this program. In fact, the user program is scattered throughout the physical memory, which also holds other programs.

Paging Example

  • Page size = 4 bytes
  • Process address space = 4 pages
  • Physical address space = 8 frames
  • Logical address: (1,3) = 0111
  • Physical address: (6,3) = 1011

Paging Example