Pré-requisito: Métodos de alocação de partição
Worst Fit aloca um processo para a partição que é maior o suficiente entre as partições disponíveis gratuitamente na memória principal. Se um processo grande ocorrer posteriormente, a memória não terá espaço para acomodá-lo.
Exemplo:
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.
Abaixo está a implementação das etapas acima.
C++// C++ implementation of worst - Fit algorithm #include
// 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('nProcess No.tProcess SizetBlock no.'); for (int i = 0; i < n; i++) { System.out.print(' ' + (i+1) + 'tt' + processSize[i] + 'tt'); 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 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
// C# implementation of worst - Fit algorithm using System; 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]; } } Console.WriteLine('nProcess No.tProcess SizetBlock no.'); for (int i = 0; i < n; i++) { Console.Write(' ' + (i+1) + 'ttt' + processSize[i] + 'ttt'); if (allocation[i] != -1) Console.Write(allocation[i] + 1); else Console.Write('Not Allocated'); Console.WriteLine(); } } // Driver code 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); } } // This code has been contributed by 29AjayKumar
<script> // Javascript implementation of // worst - Fit algorithm // Method to allocate memory to // blocks as per worst fit // algorithm function worstFit(blockSize m processSize n) { // Stores block id of the block allocated // to a process let allocation = new Array(n); // Initially no block is assigned // to any process for(let 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(let i = 0; i < n; i++) { // Find the best fit block // for current process let wstIdx = -1; for(let 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]; } } document.write('
Process No. ' + ' Process Size ' + ' Block no.
'); for(let i = 0; i < n; i++) { document.write(' ' + (i + 1) + ' ' + ' ' + processSize[i] + ' '); if (allocation[i] != -1) document.write(allocation[i] + 1); else document.write('Not Allocated'); document.write('
'); } } // Driver code let blockSize = [ 100 500 200 300 600 ]; let processSize = [ 212 417 112 426 ]; let m = blockSize.length; let n = processSize.length; worstFit(blockSize m processSize n); // This code is contributed by rag2127 </script>
Saída
Process No. Process Size Block no. 1 212 5 2 417 2 3 112 5 4 426 Not Allocated
Complexidade de tempo: O(N*M) onde N é o comprimento do processSize e M é o comprimento do blockSize.
Espaço Auxiliar: SOBRE)