Implementation of all Partition Allocation Methods in Memory Management
Prerequisite: Partition Allocation Methods in Memory Management
In Partition Allocation, when there is more than one partition freely available to accommodate a process request, a partition must be selected. To choose a particular partition, a partition allocation method is needed. A partition allocation method is considered better if it avoids internal fragmentation.
Consider the following data for process:
Process No. | Process Size |
---|---|
1 | 88 |
2 | 192 |
3 | 277 |
4 | 365 |
5 | 489 |
Memory Block No. | Memory Block Size |
---|---|
1 | 400 |
2 | 500 |
3 | 300 |
4 | 200 |
5 | 100 |
Below are the various partition allocation schemes with their implementation with respect to the given data above.
1. First Fit
This method keeps the free/busy list of jobs organized by memory location, low-ordered to high-ordered memory. In this method, the first job claims the first available memory with space more than or equal to its size. The operating system doesn’t search for appropriate partition but just allocate the job to the nearest memory partition available with sufficient size.
Below is the implementation of the First Fit Algorithm:
// C++ program for the implementation // of the First Fit algorithm #include <iostream> #include <queue> #include <vector> using namespace std; // Process Class class process { public : // Size & number of process size_t size; pid_t no; }; // Memory Class class memory { public : size_t size; // Number of memory & queue of space // occupied by process pid_t no; queue<process> space_occupied; // Function to push process in a block void push( const process p) { if (p.size <= size) { space_occupied.push(p); size -= p.size; } } // Function to pop and return the // process from the block process pop() { process p; // If space occupied is empty if (!space_occupied.empty()) { p = space_occupied.front(); space_occupied.pop(); size += p.size; return p; } } // Function to check if block is // completely empty bool empty() { return space_occupied.empty(); } }; // Function to get data of processess // allocated using first fit vector<memory> first_fit(vector<memory> memory_blocks, queue<process> processess) { int i = 0; bool done, done1; memory na; na.no = -10; while (!processess.empty()) { done = 0; for (i = 0; i < memory_blocks.size(); i++) { done1 = 0; if (memory_blocks.at(i).size >= processess.front().size) { memory_blocks.at(i).push(processess.front()); done = 1; done1 = 1; break ; } } // If process is done if (done == 0 && done1 == 0) { na.size += processess.front().size; na.push(processess.front()); } // pop the process processess.pop(); } if (!na.space_occupied.empty()) memory_blocks.push_back(na); return memory_blocks; } // Function to display the allocation // of all processess void display(vector<memory> memory_blocks) { int i = 0, temp = 0; process p; cout << "+-------------+--------------+--------------+" << endl; cout << "| Process no. | Process size | Memory block |" << endl; cout << "+-------------+--------------+--------------+" << endl; // Traverse memory blocks size for (i = 0; i < memory_blocks.size(); i++) { // While memory block size is not empty while (!memory_blocks.at(i).empty()) { p = memory_blocks.at(i).pop(); temp = to_string(p.no).length(); cout << "|" << string(7 - temp / 2 - temp % 2, ' ' ) << p.no << string(6 - temp / 2, ' ' ) << "|" ; temp = to_string(p.size).length(); cout << string(7 - temp / 2 - temp % 2, ' ' ) << p.size << string(7 - temp / 2, ' ' ) << "|" ; temp = to_string(memory_blocks.at(i).no).length(); cout << string(7 - temp / 2 - temp % 2, ' ' ); // If memory blocks is assigned if (memory_blocks.at(i).no != -10) { cout << memory_blocks.at(i).no; } // Else memory blocks is assigned else { cout << "N/A" ; } cout << string(7 - temp / 2, ' ' ) << "|" << endl; } } cout << "+-------------+--------------+--------------+" << endl; } // Driver Code int main() { // Declare memory blocks vector<memory> memory_blocks(5); // Declare first fit blocks vector<memory> first_fit_blocks; // Declare queue of all processess queue<process> processess; process temp; // Set sample data memory_blocks[0].no = 1; memory_blocks[0].size = 400; memory_blocks[1].no = 2; memory_blocks[1].size = 500; memory_blocks[2].no = 3; memory_blocks[2].size = 300; memory_blocks[3].no = 4; memory_blocks[3].size = 200; memory_blocks[4].no = 5; memory_blocks[4].size = 100; temp.no = 1; temp.size = 88; // Push the process processess.push(temp); temp.no = 2; temp.size = 192; // Push the process processess.push(temp); temp.no = 3; temp.size = 277; // Push the process processess.push(temp); temp.no = 4; temp.size = 365; // Push the process processess.push(temp); temp.no = 5; temp.size = 489; // Push the process processess.push(temp); // Get the data first_fit_blocks = first_fit(memory_blocks, processess); // Display the data display(first_fit_blocks); memory_blocks.clear(); memory_blocks.shrink_to_fit(); first_fit_blocks.clear(); first_fit_blocks.shrink_to_fit(); return 0; } |
+-------------+--------------+--------------+ | Process no. | Process size | Memory block | +-------------+--------------+--------------+ | 1 | 88 | 1 | | 2 | 192 | 1 | | 3 | 277 | 2 | | 4 | 365 | N/A | | 5 | 489 | N/A | +-------------+--------------+--------------+
2. Next Fit
The next fit is a modified version of ‘first fit’. It begins as the first fit to find a free partition but when called next time it starts searching from where it left off, not from the beginning. This policy makes use of a roving pointer. The pointer moves along the memory chain to search for a next fit. This helps in, to avoid the usage of memory always from the head (beginning) of the free block chain.
Below is the implementation of the Next Fit Algorithm:
// C++ program for the implementation // of the Next Fit algorithm #include <iostream> #include <queue> #include <vector> using namespace std; // Process Class class process { public : // Size & number of process size_t size; pid_t no; }; // Memory Class class memory { public : size_t size; // Number of memory & queue of space // occupied by process pid_t no; queue<process> space_occupied; // Function to push process in a block void push( const process p) { if (p.size <= size) { space_occupied.push(p); size -= p.size; } } // Function to pop and return the // process from the block process pop() { process p; // If space occupied is empty if (!space_occupied.empty()) { p = space_occupied.front(); space_occupied.pop(); size += p.size; return p; } } // Function to check if block is // completely empty bool empty() { return space_occupied.empty(); } }; // Function to get data of processess // allocated using Next Fit vector<memory> next_fit(vector<memory> memory_blocks, queue<process> processess) { int i = 0; bool done, done1; memory na; na.no = -10; // Loop till process is empty while (!processess.empty()) { done1 = 0; // Traverse memory_blocks for (i = 0; i < memory_blocks.size(); i++) { done = 0; // If process is not empty if (!processess.empty() && memory_blocks.at(i).size >= processess.front().size) { memory_blocks.at(i).push(processess.front()); done = 1; done1 = 1; processess.pop(); } } if (!processess.empty() && done == 0 && done1 == 0) { na.size += processess.front().size; na.push(processess.front()); processess.pop(); } } // If space is not occupied push // the memory_blocks na if (!na.space_occupied.empty()) { memory_blocks.push_back(na); } return memory_blocks; } // Function to display the allocation // of all processess void display(vector<memory> memory_blocks) { int i = 0, temp = 0; process p; cout << "+-------------+--------------+--------------+" << endl; cout << "| Process no. | Process size | Memory block |" << endl; cout << "+-------------+--------------+--------------+" << endl; // Traverse memory blocks size for (i = 0; i < memory_blocks.size(); i++) { // While memory block size is not empty while (!memory_blocks.at(i).empty()) { p = memory_blocks.at(i).pop(); temp = to_string(p.no).length(); cout << "|" << string(7 - temp / 2 - temp % 2, ' ' ) << p.no << string(6 - temp / 2, ' ' ) << "|" ; temp = to_string(p.size).length(); cout << string(7 - temp / 2 - temp % 2, ' ' ) << p.size << string(7 - temp / 2, ' ' ) << "|" ; temp = to_string(memory_blocks.at(i).no).length(); cout << string(7 - temp / 2 - temp % 2, ' ' ); // If memory blocks is assigned if (memory_blocks.at(i).no != -10) { cout << memory_blocks.at(i).no; } // Else memory blocks is assigned else { cout << "N/A" ; } cout << string(7 - temp / 2, ' ' ) << "|" << endl; } } cout << "+-------------+--------------+--------------+" << endl; } // Driver Code int main() { // Declare memory blocks vector<memory> memory_blocks(5); // Declare next fit blocks vector<memory> next_fit_blocks; // Declare queue of all processess queue<process> processess; process temp; // Set sample data memory_blocks[0].no = 1; memory_blocks[0].size = 400; memory_blocks[1].no = 2; memory_blocks[1].size = 500; memory_blocks[2].no = 3; memory_blocks[2].size = 300; memory_blocks[3].no = 4; memory_blocks[3].size = 200; memory_blocks[4].no = 5; memory_blocks[4].size = 100; temp.no = 1; temp.size = 88; // Push the process processess.push(temp); temp.no = 2; temp.size = 192; // Push the process processess.push(temp); temp.no = 3; temp.size = 277; // Push the process processess.push(temp); temp.no = 4; temp.size = 365; // Push the process processess.push(temp); temp.no = 5; temp.size = 489; // Push the process processess.push(temp); // Get the data next_fit_blocks = next_fit(memory_blocks, processess); // Display the data display(next_fit_blocks); memory_blocks.clear(); memory_blocks.shrink_to_fit(); next_fit_blocks.clear(); next_fit_blocks.shrink_to_fit(); return 0; } |
+-------------+--------------+--------------+ | Process no. | Process size | Memory block | +-------------+--------------+--------------+ | 1 | 88 | 1 | | 2 | 192 | 2 | | 3 | 277 | 3 | | 4 | 365 | N/A | | 5 | 489 | N/A | +-------------+--------------+--------------+
3. Worst Fit
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.
Below is the implementation of the Worst Fit Algorithm:
// C++ program for the implementation // of the Worst Fit algorithm #include <iostream> #include <queue> #include <vector> using namespace std; // Process Class class process { public : // Size & number of process size_t size; pid_t no; }; // Memory Class class memory { public : size_t size; // Number of memory & queue of space // occupied by process pid_t no; queue<process> space_occupied; // Function to push process in a block void push( const process p) { if (p.size <= size) { space_occupied.push(p); size -= p.size; } } // Function to pop and return the // process from the block process pop() { process p; // If space occupied is empty if (!space_occupied.empty()) { p = space_occupied.front(); space_occupied.pop(); size += p.size; return p; } } // Function to check if block is // completely empty bool empty() { return space_occupied.empty(); } }; // Function to get data of processess // allocated using Worst Fit vector<memory> worst_fit(vector<memory> memory_blocks, queue<process> processess) { int i = 0, index = 0, max; memory na; na.no = -10; // Loop till process queue is not empty while (!processess.empty()) { max = 0; // Traverse the memory_blocks for (i = 0; i < memory_blocks.size(); i++) { if (memory_blocks.at(i).size >= processess.front().size && memory_blocks.at(i).size > max) { max = memory_blocks.at(i).size; index = i; } } if (max != 0) { memory_blocks.at(index).push(processess.front()); } else { na.size += processess.front().size; na.push(processess.front()); } // Pop the current process processess.pop(); } // If space is not occupied if (!na.space_occupied.empty()) { memory_blocks.push_back(na); } // Return the memory return memory_blocks; } // Function to display the allocation // of all processess void display(vector<memory> memory_blocks) { int i = 0, temp = 0; process p; cout << "+-------------+--------------+--------------+" << endl; cout << "| Process no. | Process size | Memory block |" << endl; cout << "+-------------+--------------+--------------+" << endl; // Traverse memory blocks size for (i = 0; i < memory_blocks.size(); i++) { // While memory block size is not empty while (!memory_blocks.at(i).empty()) { p = memory_blocks.at(i).pop(); temp = to_string(p.no).length(); cout << "|" << string(7 - temp / 2 - temp % 2, ' ' ) << p.no << string(6 - temp / 2, ' ' ) << "|" ; temp = to_string(p.size).length(); cout << string(7 - temp / 2 - temp % 2, ' ' ) << p.size << string(7 - temp / 2, ' ' ) << "|" ; temp = to_string(memory_blocks.at(i).no).length(); cout << string(7 - temp / 2 - temp % 2, ' ' ); // If memory blocks is assigned if (memory_blocks.at(i).no != -10) { cout << memory_blocks.at(i).no; } // Else memory blocks is assigned else { cout << "N/A" ; } cout << string(7 - temp / 2, ' ' ) << "|" << endl; } } cout << "+-------------+--------------+--------------+" << endl; } // Driver Code int main() { // Declare memory blocks vector<memory> memory_blocks(5); // Declare worst fit blocks vector<memory> worst_fit_blocks; // Declare queue of all processess queue<process> processess; process temp; // Set sample data memory_blocks[0].no = 1; memory_blocks[0].size = 400; memory_blocks[1].no = 2; memory_blocks[1].size = 500; memory_blocks[2].no = 3; memory_blocks[2].size = 300; memory_blocks[3].no = 4; memory_blocks[3].size = 200; memory_blocks[4].no = 5; memory_blocks[4].size = 100; temp.no = 1; temp.size = 88; // Push the process processess.push(temp); temp.no = 2; temp.size = 192; // Push the process processess.push(temp); temp.no = 3; temp.size = 277; // Push the process processess.push(temp); temp.no = 4; temp.size = 365; // Push the process processess.push(temp); temp.no = 5; temp.size = 489; // Push the process processess.push(temp); // Get the data worst_fit_blocks = worst_fit(memory_blocks, processess); // Display the data display(worst_fit_blocks); memory_blocks.clear(); memory_blocks.shrink_to_fit(); worst_fit_blocks.clear(); worst_fit_blocks.shrink_to_fit(); return 0; } |
+-------------+--------------+--------------+ | Process no. | Process size | Memory block | +-------------+--------------+--------------+ | 3 | 277 | 1 | | 1 | 88 | 2 | | 2 | 192 | 2 | | 4 | 365 | N/A | | 5 | 489 | N/A | +-------------+--------------+--------------+
4. Best Fit
This method keeps the free/busy list in order by size – smallest to largest. In this method, the operating system first searches the whole of the memory according to the size of the given job and allocates it to the closest-fitting free partition in the memory, making it able to use memory efficiently. Here the jobs are in the order from smallest job to the largest job.
Below is the implementation of the Best Fit Algorithm:
// C++ program for the implementation // of the Best Fit algorithm #include <iostream> #include <queue> #include <vector> using namespace std; // Process Class class process { public : // Size & number of process size_t size; pid_t no; }; // Memory Class class memory { public : size_t size; // Number of memory & queue of space // occupied by process pid_t no; queue<process> space_occupied; // Function to push process in a block void push( const process p) { if (p.size <= size) { space_occupied.push(p); size -= p.size; } } // Function to pop and return the // process from the block process pop() { process p; // If space occupied is empty if (!space_occupied.empty()) { p = space_occupied.front(); space_occupied.pop(); size += p.size; return p; } } // Function to check if block is // completely empty bool empty() { return space_occupied.empty(); } }; // Function to get data of processess // allocated using Best Fit vector<memory> best_fit(vector<memory> memory_blocks, queue<process> processess) { int i = 0, min, index = 0; memory na; na.no = -10; // Loop till processe is not empty while (!processess.empty()) { min = 0; // Traverse the memory_blocks for (i = 0; i < memory_blocks.size(); i++) { if (memory_blocks.at(i).size >= processess.front().size && (min == 0 || memory_blocks.at(i).size < min)) { min = memory_blocks.at(i).size; index = i; } } if (min != 0) { memory_blocks.at(index).push(processess.front()); } else { na.size += processess.front().size; na.push(processess.front()); } // Pop the processe processess.pop(); } // If space is no occupied then push // the current memory na if (!na.space_occupied.empty()) { memory_blocks.push_back(na); } // Return the memory_blocks return memory_blocks; } // Function to display the allocation // of all processess void display(vector<memory> memory_blocks) { int i = 0, temp = 0; process p; cout << "+-------------+--------------+--------------+" << endl; cout << "| Process no. | Process size | Memory block |" << endl; cout << "+-------------+--------------+--------------+" << endl; // Traverse memory blocks size for (i = 0; i < memory_blocks.size(); i++) { // While memory block size is not empty while (!memory_blocks.at(i).empty()) { p = memory_blocks.at(i).pop(); temp = to_string(p.no).length(); cout << "|" << string(7 - temp / 2 - temp % 2, ' ' ) << p.no << string(6 - temp / 2, ' ' ) << "|" ; temp = to_string(p.size).length(); cout << string(7 - temp / 2 - temp % 2, ' ' ) << p.size << string(7 - temp / 2, ' ' ) << "|" ; temp = to_string(memory_blocks.at(i).no).length(); cout << string(7 - temp / 2 - temp % 2, ' ' ); // If memory blocks is assigned if (memory_blocks.at(i).no != -10) { cout << memory_blocks.at(i).no; } // Else memory blocks is assigned else { cout << "N/A" ; } cout << string(7 - temp / 2, ' ' ) << "|" << endl; } } cout << "+-------------+--------------+--------------+" << endl; } // Driver Code int main() { // Declare memory blocks vector<memory> memory_blocks(5); // Declare best fit blocks vector<memory> best_fit_blocks; // Declare queue of all processess queue<process> processess; process temp; // Set sample data memory_blocks[0].no = 1; memory_blocks[0].size = 400; memory_blocks[1].no = 2; memory_blocks[1].size = 500; memory_blocks[2].no = 3; memory_blocks[2].size = 300; memory_blocks[3].no = 4; memory_blocks[3].size = 200; memory_blocks[4].no = 5; memory_blocks[4].size = 100; temp.no = 1; temp.size = 88; // Push the processe to queue processess.push(temp); temp.no = 2; temp.size = 192; // Push the processe to queue processess.push(temp); temp.no = 3; temp.size = 277; // Push the processe to queue processess.push(temp); temp.no = 4; temp.size = 365; // Push the processe to queue processess.push(temp); temp.no = 5; temp.size = 489; // Push the processe to queue processess.push(temp); // Get the data best_fit_blocks = best_fit(memory_blocks, processess); // Display the data display(best_fit_blocks); memory_blocks.clear(); memory_blocks.shrink_to_fit(); best_fit_blocks.clear(); best_fit_blocks.shrink_to_fit(); return 0; } |
+-------------+--------------+--------------+ | Process no. | Process size | Memory block | +-------------+--------------+--------------+ | 4 | 365 | 1 | | 5 | 489 | 2 | | 3 | 277 | 3 | | 2 | 192 | 4 | | 1 | 88 | 5 | +-------------+--------------+--------------+
Contact Us