Question

a) Briefly describe each of the following memory allocation algorithms: i. Best fit ii. Next fit b) Given fixed memory partitions of 200 KB, 100 KB, 400 KB, 300 KB, and 400 KB (in order), how would each of the algorithms from (a) place processes in memory if they required 187 KB, 228 KB, 126 KB, 306 KB (in order)? c) A system has five page frames. The time of loading, time of last access, and the Referenced and Modified bit for each page are shown in the following table (with time in clock ticks). Frame Loaded Last referenced Referenced Modified 0 76 115 1 0 1 99 118 1 0 2 68 76 0 1 3 63 78 1 0 4 12 86 0 1 For each of the following algorithms, which page would be the next to be replaced? i. Second chance ii. Clock

Answer 1

1.Best fit memory allocation algorithm


Start
Step 1-> In function void bestfit(int bsize[], int m, int psize[], int n)
Declare int alloc[n]
Call function memset(alloc, -1, sizeof(alloc))
Loop For i=0 and i<n and i++
Declare and Initialize bestIdx = -1
Loop For j=0 and j<m and j++
If bsize[j] >= psize[i] then,
If bestIdx == -1 then,
Set bestIdx = j
Else If bsize[bestIdx] > bsize[j] then,
Set bestIdx = j
If bestIdx != -1 then,
Set alloc[i] = bestIdx
Set bsize[bestIdx] -= psize[i]
Loop For i = 0 and i < n and i++
Print i+1, psize[i]
If alloc[i] != -1
Print alloc[i] + 1
Else
Print "Not Allocated"
Print newline
Step 2->In function int main()
Declare and initialize bsize[] = {100, 500, 200, 300, 400}
Declare and initialize psize[] = {112, 518, 110, 526}
Set m = sizeof(bsize)/sizeof(bsize[0])
Set n = sizeof(psize)/sizeof(psize[0])
Call function bestfit(bsize, m, psize, n)
Stop

2. Next fit memory allocation algorithm

// memory management algorithm

using System;

using System.Linq;

public class GFG {

// Function to allocate memory to blocks as per Next fit

// algorithm

    static void NextFit(int []blockSize, int m,

                            int []processSize, int n) {

        // Stores block id of the block allocated to a

        // process

        int []allocation = new int[n];

        int j = 0;

        // Initially no block is assigned to any process

        Enumerable.Repeat(-1, n).ToArray();

        // pick each process and find suitable blocks

        // according to its size ad assign to it

        for (int i = 0; i < n; i++) {

            // Do not start from beginning

            while (j < m) {

                if (blockSize[j] >= processSize[i]) {

                    // allocate block j to p[i] process

                    allocation[i] = j;

                    // Reduce available memory in this block.

                    blockSize[j] -= processSize[i];

                    break;

                }

                // mod m will help in traversing the blocks from

                // starting block after we reach the end.

                j = (j + 1) % m;

            }

        }

        Console.Write("\nProcess No.\tProcess Size\tBlock no.\n");

        for (int i = 0; i < n; i++) {

            Console.Write( i + 1 + "\t\t" + processSize[i]

                    + "\t\t");

            if (allocation[i] != -1) {

                Console.Write(allocation[i] + 1);

            } else {

                Console.Write("Not Allocated");

            }

            Console.WriteLine("");

        }

    }

// Driver program

    static public void Main() {

        int []blockSize = {5, 10, 20};

        int []processSize = {10, 20, 5};

        int m = blockSize.Length;

        int n = processSize.Length;

        NextFit(blockSize, m, processSize, n);

    }

}