Allocation of Frames

Allocation of Frames

AU May-19

• In the last section, we discussed local page replacement policy. Now we have considered how to assign pages of a process logical memory to a fixed set of allocated frames. We also need to decide how many frames to allocate to each process. It is also possible to select the victim from a frame currently allocated to another process.

• There are fixed amount 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.

• Let us consider the single process system. All free memory for user programs can initially be put on the free frame list. When the user starts executing his program, it will generate a sequence of page faults. The user program would get all free frames from the free frame list.

• When 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.

Equal Allocation

• Each process needs a certain minimum number of pages

i. Pages for instructions.

ii. Pages for local data.

iii. Pages for global data.

• Allocation may be fixed. Here "m" frames are splits among the "p" number of

• For example, if there are 180 frames and 6 processes, give each process 30 frames.

• High priority jobs have same number of page frames and low priority jobs. Degree of multiprogramming might vary in equal allocation.

• Problem with equal allocation is that, there may be the wastage of free frames. Some process may require less number of free frames than allocated one. To solve this problem, proportional allocation method is used.

• Proportional allocation: Processes that have more logical memory get more frames.

Priority allocation

• In priority allocation, higher priority processes get more frames. System uses a proportional allocation scheme using priorities rather than size.

• If process P_i  generates a page fault, then select for replacement one of its frames or select for replacement a frame from a process with lower priority number.

Global Vs Local Allocation

• If a process needs frames, should pages from other processes be discarded or just pages from the process which wants frames? Local policy means giving each process a share of the physical memory and swapping pages in and out on a per process basis.

• Global allocation: One process can select a replacement frame from the set of all frames. Process may not be able to control its page fault rate.

• Advantages of global allocation :

i. Flexibility of allocation.

ii. Minimize total number of page faults

• Disadvantages of global allocation

1. One memory-intensive process can hog memory, hurt all processes

• Local allocation: Each process can only select from its own set of allocated frames. Process slowed down even if other less used pages of memory are available.

• Per process local replacement

Advantage: No interference across processes.

Disadvantage: Potentially inefficient allocation of memory.

• Per user local replacement: Each user has separate pool of pages Advantage Fair across different users.

Disadvantage: Allocation is inefficient.

• Local page replacement is more predictable; depends on no external factors. A process which uses global page replacement cannot predict the page fault rate; may execute in 0.5 seconds once and 10.3 on another run. Overall, global replacement results in greater system throughput.

Example 4.13.1 Consider a system having 64 frames and with 4 processes. The virtual memory size is as follows:

v(1) = 16, v(2) = 128, v(3) = 64, v(4) = 48. Allocate free page frames by using equal allocation and proportional allocation policy.

Solution :

Proportional allocation :

Sum of all virtual memory size (v) = v(1) + v(2) + v(3) + v(4)

= 16 + 128 +64 + 48 = 256

Then it allocates is following ways:

Process 1 = (16 / 256) * 64 = 4 frames

Process 2 = (128 / 256) * 64 = 32 frames

Process 3 = (64 / 256) * 64 = 16 frames

Process 4 = (48 / 256) * 64 = 12 frames

University Question