Allocation Algorithm – Virtual Memory

Allocation Algorithm

There are two different methods of  allocating frames to different process. These are:

1. Equal allocation
2. Proportional allocation

1. Equal allocation

This allocation method divides the available page frames equally among all the processes. i.e. if we have m frames and n processes then we can divide m frames among the n processes.

For example, there are 93 frame and five processes, we can divide 18 frames to each of the five processes. The remaining 3 frames are used as free frame buffer pool. This scheme will create a problem if a process does not require the given amount of frames and hence it leads to wastage of frames.

2. Proportional Allocation Algorithm

This scheme can be used to overcome the problem of equal allocation. Proportional allocation divides the frame in proportion to the sizes of the process i.e. memory is allocated to each process according to its size.

If the size of virtual memory for process pi is si, we can define :

S= Σsi

If the total number of frames is m, we allocate bi frames to process pi, then bi can written as :

bi = si/S *m

We have to set an integer value bi that must be greater than the minimum number of frames, which are required by an instruction set. Their sum must not be greater than m.

Global versus local allocation algorithm

The important factor that plays main role in deciding the allocation of frames is page replacement. In case of multiple processes, page replacement algorithms are classified into two categories :

• Global replacement
• Local replacement

In this algorithm, the replacement frame selected by a process can be any frame from the set of all frames.

1. Global replacement

In global replacement a process can select even that frames which currently allocated to some other process. Thus, in this strategy, one process can take a frame from another process. In global replacement, the number of frames allocated to a process may increase. One problem with this method is that a process cannot control its own page fault rate. The main advantage is that it results in greater system throughput.

2. Local replacement

In this allocation algorithm, the replacement frame selected by a process can only from the set of frames which allocated to it. The process cannot select the frame which currently allocated to other process. Thus, one process cannot take a frame from another process in local replacement. In local replacement, the number of frames allocated to a process does not change.