Program for Worst Fit algorithm in Memory Management Last Updated : 13 Sep, 2023 Summarize Suggest changes Share Like Article Like Report Prerequisite : Partition allocation methodsWorst 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 << "\nProcess No.\tProcess Size\tBlock no.\n"; for (int i = 0; i < n; i++) { cout << " " << i+1 << "\t\t" << processSize[i] << "\t\t"; 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("\nProcess No.\tProcess Size\tBlock no."); for (int i = 0; i < n; i++) { System.out.print(" " + (i+1) + "\t\t" + processSize[i] + "\t\t"); 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 C# // 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 Size\tBlock no."); for (int i = 0; i < n; i++) { Console.Write(" " + (i+1) + "\t\t\t" + processSize[i] + "\t\t\t"); 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 JavaScript <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("<br>Process No.  " + " Process Size  " + " Block no.<br>"); 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("<br>"); } } // 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> Output Process No. Process Size Block no. 1 212 5 2 417 2 3 112 5 4 426 Not Allocated Time Complexity: O(N*M) where N is processSize length and M is blockSize length. Auxiliary Space: O(N) Advertise with us Next Article Program for Shortest Job First (or SJF) CPU Scheduling | Set 1 (Non- preemptive) S Sahil Chhabra Similar Reads Greedy Algorithms Greedy algorithms are a class of algorithms that make locally optimal choices at each step with the hope of finding a global optimum solution. At every step of the algorithm, we make a choice that looks the best at the moment. To make the choice, we sometimes sort the array so that we can always get 3 min read Greedy Algorithm Tutorial Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Greedy algorithms are used for optimization problems. An optimization problem can be solved using Greedy if the problem has the following pro 9 min read Greedy Algorithms General Structure A greedy algorithm solves problems by making the best choice at each step. Instead of looking at all possible solutions, it focuses on the option that seems best right now.Example of Greedy Algorithm - Fractional KnapsackProblem structure:Most of the problems where greedy algorithms work follow thes 5 min read Difference between Greedy Algorithm and Divide and Conquer Algorithm Greedy algorithm and divide and conquer algorithm are two common algorithmic paradigms used to solve problems. The main difference between them lies in their approach to solving problems. Greedy Algorithm:The greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of m 3 min read Greedy Approach vs Dynamic programming Greedy approach and Dynamic programming are two different algorithmic approaches that can be used to solve optimization problems. Here are the main differences between these two approaches: Greedy Approach:The greedy approach makes the best choice at each step with the hope of finding a global optim 2 min read Comparison among Greedy, Divide and Conquer and Dynamic Programming algorithm Greedy algorithm, divide and conquer algorithm, and dynamic programming algorithm are three common algorithmic paradigms used to solve problems. Here's a comparison among these algorithms:Approach:Greedy algorithm: Makes locally optimal choices at each step with the hope of finding a global optimum. 4 min read Standard Greedy algorithmsActivity Selection Problem | Greedy Algo-1Given n activities with start times in start[] and finish times in finish[], find the maximum number of activities a single person can perform without overlap. A person can only do one activity at a time. Examples: Input: start[] = [1, 3, 0, 5, 8, 5], finish[] = [2, 4, 6, 7, 9, 9]Output: 4Explanatio 13 min read Job Sequencing ProblemGiven two arrays: deadline[] and profit[], where the index of deadline[] represents a job ID, and deadline[i] denotes the deadline for that job and profit[i] represents profit of doing ith job. Each job takes exactly one unit of time to complete, and only one job can be scheduled at a time. A job ea 13 min read Huffman Coding | Greedy Algo-3Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters. The variable-length codes assigned to input characters are Prefix Codes, means the codes ( 12 min read Huffman DecodingWe have discussed Huffman Encoding in a previous post. In this post, decoding is discussed. Examples: Input Data: AAAAAABCCCCCCDDEEEEEFrequencies: A: 6, B: 1, C: 6, D: 2, E: 5 Encoded Data: 0000000000001100101010101011111111010101010 Huffman Tree: '#' is the special character usedfor internal nodes 15 min read Water Connection ProblemYou are given n houses in a colony, numbered from 1 to n, and p pipes connecting these houses. Each house has at most one outgoing pipe and at most one incoming pipe. Your goal is to install tanks and taps efficiently.A tank is installed at a house that has one outgoing pipe but no incoming pipe.A t 8 min read Greedy Algorithm for Egyptian FractionEvery positive fraction can be represented as sum of unique unit fractions. A fraction is unit fraction if numerator is 1 and denominator is a positive integer, for example 1/3 is a unit fraction. Such a representation is called Egyptian Fraction as it was used by ancient Egyptians. Following are a 11 min read Policemen catch thievesGiven an array arr, where each element represents either a policeman (P) or a thief (T). The objective is to determine the maximum number of thieves that can be caught under the following conditions:Each policeman (P) can catch only one thief (T).A policeman can only catch a thief if the distance be 12 min read Fitting Shelves ProblemGiven length of wall w and shelves of two lengths m and n, find the number of each type of shelf to be used and the remaining empty space in the optimal solution so that the empty space is minimum. The larger of the two shelves is cheaper so it is preferred. However cost is secondary and first prior 9 min read Assign Mice to HolesThere are N Mice and N holes are placed in a straight line. Each hole can accommodate only 1 mouse. A mouse can stay at his position, move one step right from x to x + 1, or move one step left from x to x -1. Any of these moves consumes 1 minute. Assign mice to holes so that the time when the last m 8 min read Greedy algorithm on ArrayMinimum product subset of an arrayINTRODUCTION: The minimum product subset of an array refers to a subset of elements from the array such that the product of the elements in the subset is minimized. To find the minimum product subset, various algorithms can be used, such as greedy algorithms, dynamic programming, and branch and boun 13 min read Maximize array sum after K negations using SortingGiven an array of size n and an integer k. We must modify array k number of times. In each modification, we can replace any array element arr[i] by -arr[i]. The task is to perform this operation in such a way that after k operations, the sum of the array is maximum.Examples : Input : arr[] = [-2, 0, 10 min read Minimum sum of product of two arraysFind the minimum sum of Products of two arrays of the same size, given that k modifications are allowed on the first array. In each modification, one array element of the first array can either be increased or decreased by 2.Examples: Input : a[] = {1, 2, -3} b[] = {-2, 3, -5} k = 5 Output : -31 Exp 14 min read Minimum sum of absolute difference of pairs of two arraysGiven two arrays a[] and b[] of equal length n. The task is to pair each element of array a to an element in array b, such that sum S of absolute differences of all the pairs is minimum.Suppose, two elements a[i] and a[j] (i != j) of a are paired with elements b[p] and b[q] of b respectively, then p 7 min read Minimum increment/decrement to make array non-IncreasingGiven an array a, your task is to convert it into a non-increasing form such that we can either increment or decrement the array value by 1 in the minimum changes possible. Examples : Input : a[] = {3, 1, 2, 1}Output : 1Explanation : We can convert the array into 3 1 1 1 by changing 3rd element of a 11 min read Sorting array with reverse around middleConsider the given array arr[], we need to find if we can sort array with the given operation. The operation is We have to select a subarray from the given array such that the middle element(or elements (in case of even number of elements)) of subarray is also the middle element(or elements (in case 6 min read Sum of Areas of Rectangles possible for an arrayGiven an array, the task is to compute the sum of all possible maximum area rectangles which can be formed from the array elements. Also, you can reduce the elements of the array by at most 1. Examples: Input: a = {10, 10, 10, 10, 11, 10, 11, 10} Output: 210 Explanation: We can form two rectangles o 13 min read Largest lexicographic array with at-most K consecutive swapsGiven an array arr[], find the lexicographically largest array that can be obtained by performing at-most k consecutive swaps. Examples : Input : arr[] = {3, 5, 4, 1, 2} k = 3 Output : 5, 4, 3, 2, 1 Explanation : Array given : 3 5 4 1 2 After swap 1 : 5 3 4 1 2 After swap 2 : 5 4 3 1 2 After swap 3 9 min read Partition into two subsets of lengths K and (N - k) such that the difference of sums is maximumGiven an array of non-negative integers of length N and an integer K. Partition the given array into two subsets of length K and N - K so that the difference between the sum of both subsets is maximum. Examples : Input : arr[] = {8, 4, 5, 2, 10} k = 2 Output : 17 Explanation : Here, we can make firs 7 min read Greedy algorithm on Operating SystemProgram for First Fit algorithm in Memory ManagementPrerequisite : Partition Allocation MethodsIn the first fit, the partition is allocated which is first sufficient from the top of Main Memory.Example : Input : blockSize[] = {100, 500, 200, 300, 600}; processSize[] = {212, 417, 112, 426};Output:Process No. Process Size Block no. 1 212 2 2 417 5 3 11 8 min read Program for Best Fit algorithm in Memory ManagementPrerequisite : Partition allocation methodsBest fit allocates the process to a partition which is the smallest sufficient partition among the free available partitions. Example: Input : blockSize[] = {100, 500, 200, 300, 600}; processSize[] = {212, 417, 112, 426}; Output: Process No. Process Size Bl 8 min read Program for Worst Fit algorithm in Memory ManagementPrerequisite : Partition allocation methodsWorst 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 : blo 8 min read Program for Shortest Job First (or SJF) CPU Scheduling | Set 1 (Non- preemptive)The shortest job first (SJF) or shortest job next, is a scheduling policy that selects the waiting process with the smallest execution time to execute next. SJN, also known as Shortest Job Next (SJN), can be preemptive or non-preemptive.  Characteristics of SJF Scheduling: Shortest Job first has th 13 min read Job Scheduling with two jobs allowed at a timeGiven a 2d array jobs[][] of order n * 2, where each element jobs[i], contains two integers, representing the start and end time of the job. Your task is to check if it is possible to complete all the jobs, provided that two jobs can be done simultaneously at a particular moment. Note: If a job star 6 min read Optimal Page Replacement AlgorithmIn operating systems, whenever a new page is referred and not present in memory, page fault occurs, and Operating System replaces one of the existing pages with newly needed page. Different page replacement algorithms suggest different ways to decide which page to replace. The target for all algorit 3 min read Greedy algorithm on GraphPrim’s Algorithm for Minimum Spanning Tree (MST)Prim’s algorithm is a Greedy algorithm like Kruskal's algorithm. This algorithm always starts with a single node and moves through several adjacent nodes, in order to explore all of the connected edges along the way.The algorithm starts with an empty spanning tree. The idea is to maintain two sets o 15+ min read Boruvka's algorithm | Greedy Algo-9We have discussed the following topics on Minimum Spanning Tree.Applications of Minimum Spanning Tree Problem Kruskal’s Minimum Spanning Tree Algorithm Prim’s Minimum Spanning Tree AlgorithmIn this post, Boruvka's algorithm is discussed. Like Prim's and Kruskal's, Boruvka’s algorithm is also a Greed 15+ min read Dial's Algorithm (Optimized Dijkstra for small range weights)Given a weighted Graph and a source vertex, the task is to find the shortest paths from the source node to all other vertices.Example:Input : n = 9, src = 0Output : 0 4 12 19 21 11 9 8 14 We have learned about how to find the shortest path from a given source vertex to all other vertex using Dijkstr 10 min read Minimum cost to connect all citiesThere are n cities and there are roads in between some of the cities. Somehow all the roads are damaged simultaneously. We have to repair the roads to connect the cities again. There is a fixed cost to repair a particular road.Input is in the form of edges {u, v, w} where, u and v are city indices. 7 min read Number of single cycle components in an undirected graphGiven a set of 'n' vertices and 'm' edges of an undirected simple graph (no parallel edges and no self-loop), find the number of single-cycle components present in the graph. A single-cyclic component is a graph of n nodes containing a single cycle through all nodes of the component. Example: Let us 9 min read Article Tags : DSA Like