Allocation Algorithms

• The easiest way to split $m$ frames among $n$ processes is to give everyone an equal share, $m/ n$ frames. This scheme is called equal allocation.
  • For instance, if there are 93 frames and five processes, each process will get 18 frames.
  • The leftover three frames can be used as a free-frame buffer pool.
• An alternative is to recognize that various processes will need differing amounts of memory.
  • Consider a system with a 1-KB frame size.
  • If a small student process of 10 KB and an interactive database of 127 KB are the only two processes running in a system with 62 free frames, it does not make much sense to give each process 31 frames.
  • The student process does not need more than 10 frames, so the other 21 are, strictly speaking, wasted.
• To solve this problem, we allocate available memory to each process according to its size (proportional allocation).
• Let the size of the virtual memory for process $p_i$ be $s_i$, and define
  
  $$S=\sum s_i$$
  
  

• Then, if the total number of available frames is $m$, we allocate $a_i$ frames to process $p_i$, where $a_i$ is approximately
  
  $$a_i = \frac{s_i}{S*m}$$
  
  

• For proportional allocation, we would split 62 frames between two processes, one of 10 pages and one of 127 pages, by allocating 4 frames and 57 frames, respectively, since

  10/137 x 62 ~ 4,
  127/137 x 62 ~ 57.
  

• In this way, both processes share the available frames according to their ``needs'', rather than equally.
• In both equal and proportional allocation, of course, the allocation may vary according to the multiprogramming level.
  • If the multiprogramming level is increased, each process will lose some frames to provide the memory needed for the new process.
  • If the multiprogramming level decreases, the frames that were allocated to the departed process can be spread over the remaining processes.