Prerequisite : Partition allocation methods
Worst Fit allocates a process to the partition which is largest sufficient among the freely available partitions available in the main memory. If a large process comes at a later stage, then memory will not have space to accommodate it.
Example:
Input : blockSize[] = {100, 500, 200, 300, 600}; processSize[] = {212, 417, 112, 426}; Output: Process No. Process Size Block no. 1 212 5 2 417 2 3 112 5 4 426 Not Allocated
Implementation: 1- Input memory blocks and processes with sizes. 2- Initialize all memory blocks as free. 3- Start by picking each process and find the maximum block size that can be assigned to current process i.e., find max(bockSize[1], blockSize[2],.....blockSize[n]) > processSize[current], if found then assign it to the current process. 5- If not then leave that process and keep checking the further processes.
Below is implementation of above steps.
C++
// C++ implementation of worst - Fit algorithm #include<bits/stdc++.h> using namespace std; // Function to allocate memory to blocks as per worst fit // algorithm void worstFit( int blockSize[], int m, int processSize[], int n) { // Stores block id of the block allocated to a // process int allocation[n]; // Initially no block is assigned to any process memset (allocation, -1, sizeof (allocation)); // pick each process and find suitable blocks // according to its size ad assign to it for ( int i=0; i<n; i++) { // Find the best fit block for current process int wstIdx = -1; for ( int j=0; j<m; j++) { if (blockSize[j] >= processSize[i]) { if (wstIdx == -1) wstIdx = j; else if (blockSize[wstIdx] < blockSize[j]) wstIdx = j; } } // If we could find a block for current process if (wstIdx != -1) { // allocate block j to p[i] process allocation[i] = wstIdx; // Reduce available memory in this block. blockSize[wstIdx] -= processSize[i]; } } cout << "
Process No. Process Size Block no.
" ; for ( int i = 0; i < n; i++) { cout << " " << i+1 << " " << processSize[i] << " " ; if (allocation[i] != -1) cout << allocation[i] + 1; else cout << "Not Allocated" ; cout << endl; } } // Driver code int main() { int blockSize[] = {100, 500, 200, 300, 600}; int processSize[] = {212, 417, 112, 426}; int m = sizeof (blockSize)/ sizeof (blockSize[0]); int n = sizeof (processSize)/ sizeof (processSize[0]); worstFit(blockSize, m, processSize, n); return 0 ; } |
Java
// Java implementation of worst - Fit algorithm public class GFG { // Method to allocate memory to blocks as per worst fit // algorithm static void worstFit( int blockSize[], int m, int processSize[], int n) { // Stores block id of the block allocated to a // process int allocation[] = new int [n]; // Initially no block is assigned to any process for ( int i = 0 ; i < allocation.length; i++) allocation[i] = - 1 ; // pick each process and find suitable blocks // according to its size ad assign to it for ( int i= 0 ; i<n; i++) { // Find the best fit block for current process int wstIdx = - 1 ; for ( int j= 0 ; j<m; j++) { if (blockSize[j] >= processSize[i]) { if (wstIdx == - 1 ) wstIdx = j; else if (blockSize[wstIdx] < blockSize[j]) wstIdx = j; } } // If we could find a block for current process if (wstIdx != - 1 ) { // allocate block j to p[i] process allocation[i] = wstIdx; // Reduce available memory in this block. blockSize[wstIdx] -= processSize[i]; } } System.out.println( "
Process No. Process Size Block no." ); for ( int i = 0 ; i < n; i++) { System.out.print( " " + (i+ 1 ) + " " + processSize[i] + " " ); if (allocation[i] != - 1 ) System.out.print(allocation[i] + 1 ); else System.out.print( "Not Allocated" ); System.out.println(); } } // Driver Method public static void main(String[] args) { int blockSize[] = { 100 , 500 , 200 , 300 , 600 }; int processSize[] = { 212 , 417 , 112 , 426 }; int m = blockSize.length; int n = processSize.length; worstFit(blockSize, m, processSize, n); } } |
Python3
# Python3 implementation of worst - Fit algorithm # Function to allocate memory to blocks as # per worst fit algorithm def worstFit(blockSize, m, processSize, n): # Stores block id of the block # allocated to a process # Initially no block is assigned # to any process allocation = [ - 1 ] * n # pick each process and find suitable blocks # according to its size ad assign to it for i in range (n): # Find the best fit block for # current process wstIdx = - 1 for j in range (m): if blockSize[j] > = processSize[i]: if wstIdx = = - 1 : wstIdx = j elif blockSize[wstIdx] < blockSize[j]: wstIdx = j # If we could find a block for # current process if wstIdx ! = - 1 : # allocate block j to p[i] process allocation[i] = wstIdx # Reduce available memory in this block. blockSize[wstIdx] - = processSize[i] print ( "Process No. Process Size Block no." ) for i in range (n): print (i + 1 , " " , processSize[i], end = " " ) if allocation[i] ! = - 1 : print (allocation[i] + 1 ) else : print ( "Not Allocated" ) # Driver code if __name__ = = '__main__' : blockSize = [ 100 , 500 , 200 , 300 , 600 ] processSize = [ 212 , 417 , 112 , 426 ] m = len (blockSize) n = len (processSize) worstFit(blockSize, m, processSize, n) # This code is contributed by PranchalK |
Output:
Process No. Process Size Block no. 1 212 5 2 417 2 3 112 5 4 426 Not Allocated
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments