3i Infotech Papers: Sample Questions 303 - 303 of 1245

Examrace Placement Series prepares you for the toughest placement exams to top companies.

Question number: 303

» Basic CS » Algorithms

Essay Question▾

Describe in Detail

In the context of memory management, what are placement and replacement algorithms?

Explanation

Placement algorithm:

  • Determine where in available real-memory to load a page.

  • Common methods are first-fit, next-fit, best-fit.

    • First-fit:

      • Maintain list of free partitions ordered by addresses.

      • Tendency for small fragments start and large fragments at list end.

    • Next-fit:

      • Tendency to fragment the large free block at the end of memory.

      • Leads to more equal distribution of fragments.

    • Best-fit:

      • Search the entire list and allocate the smallest hole that is big enough.

Replacement algorithm:

  • Determine which page should be be swapped out.

  • Used when memory is full and one process needs to remove page to make room for another page.

    • Page fault forces choice:

      • Which page to remove to make room for incoming page?

    • Modified page is first saved

      • Unmodified overwritten.

    • Better not to choose an often used page

      • Probably need to bring back in soon.

Page replacement algorithms:

First in first out:

  • Oldest page in main memory is selected for replacement.

  • Easy to implement, replaces pages from the tail and add new pages at the head.

Reference String: 0,2, 1,6, 4,0, 1,0, 3,1, 2,1,

Misses: x x x x x x x x x

Page replacement algorithms

Page Replacement Algorithms

Page replacement algorithms

Optimal page algorithm:

  • An optimal page-replacement algorithm has the lowest page-fault rate of all algorithms.

  • Replace the page not be used for largest period of time.

  • Ideal but not possible in real life as it depends on accurately predicting future behaviour of the program

Reference String: 0,2, 1,6, 4,0, 1,0, 3,1, 2,1,

Misses: x x x x x x

Optimal page algorithm

Optimal Page Algorithm

Optimal page algorithm

Least Recently Used (LRU) algorithm

  • Page which has not used for the longest time in main memory is selected for replacement.

  • Easy to implement, keep a list, replace pages by looking back into time.

Reference String: 0,2, 1,6, 4,0, 1,0, 3,1, 2,1,

Misses: x x x x xx x x

Least Recently Used (LRU) algorithm

Least Recently Used (LRU) Algorithm

Least Recently Used (LRU) algorithm