Allocation of Frames in Operating System

Allocation of Frames in Operating System:

Normally, there are fixed amounts of free memory with various processes at different time in a system. The question is how this fixed amount of free memory is allocated among the different processes.

The simplest case is the single process system. All available memory for user programs can initially be put on the free frame list (pure demand paging). When the user program starts its execution, it will generate a sequence of page faults. The user program would get all free frames from the free frame list. As soon as this list was exhausted, and the more free frames are required, the page replacement algorithm can be used to select one of the in-used pages to be replaced with the next required page and so on. After the program was terminated, all used pages are put on the free frame list again.

The frame allocation procedure is more complicated when there are two of more programs in memory at the same time.

1. Minimum Number of Frames:

We cannot allocate more than the total number of available frames in the system. On the other hand, there is a minimum number of frames which must be allocated. This minimum number is determined by the instruction architecture. It is obvious that we must provide enough frames to hold all the different pages that any single instruction can reference. For example, all memory reference instructions of-a machine have only one memory address. So we need at least one frame for the instruction code and one frame for the memory reference. If one level indirect addressing is allowed, a load instruction on page m can refer to an address on page. It is an indirect reference to page k. We need three pages.

2. Algorithms:

The simplest way is to divide m available frames among n processes to give everyone an equal share, m/n frames. This is called equal allocation. Various processes will need different amounts of memory. If the equal allocation is applied, there can be some frames
wasted. Therefore, other allocation scheme can be used to give available memory to each process according to its size. This is called, proportional allocation. Let the size of the virtual memory for process p_i be s_i, the number of frames allocated to the process p_i be a_i, and define

S = ∑ s_i

If the total number of available frames is m, then a_i can be calculated:

a_i = (s_i/S) * m.

Of course a_i must be adjust to be a integer, greater than the minimum number of frames required by the instruction set with a sum not exceeding m.

In both of theses cases, the number of frames allocated to each process may vary according to the multiprogramming level; say l. If l increases, each process will lose some of the allocated frames to provide memory needed for the new process. Otherwise, the frames allocated to the departed process can be now spread over the remaining processes.

Within these two allocation schemes, a high-priority process is treated the same as low-priority process. By definition, it is desirable to give more memory to high-priority process to speed up its execution.

3. Replacement Scope:

When its necessary to find free page frames, what set of pages should become candidates for replacement?

Local replacement policies replace pages that belong to the process that needs the new frame.
Global policies consider all unlocked frames. Most systems use global replacement because it is easy to implement, has minimal overhead, and performs reasonably well.

	Local Replacement	Global Replacement
Fixed Allocation	Rarely used -A process is given a fixed number of frames. Page faults are satisfied from this set.	This combination isn't possible
Variable Allocation	The process is given a fixed allocation and pages to be replaced are chosen from this set. Periodically, the resident, set size is re-evaluated. Pages can be added or subtracted.	Replacement pages are chosen from any page in memory. Resident set size varies, although by a blind process. This is the most common approach