
Sequential fit methods using linked list:
Program plan:
- Define a function named “printList()” that displays elements of linked list.
- Define a function named “insert()” that takes an integer value as argument and insert the value into linked list.
- Declare a function named “first_fit()” that allocates the process with memory based on first fit strategy.
- Define a function named “best_fit()” that allocates the process with memory based on best fit strategy.
- Define the function “worst_fit()” that allocates the process with memory based on worst fit strategy.
- Define the function “next_fit()” that allocates the process with memory based on next fit strategy.

/***********************************************************
* This program creates a linked list of memory nodes *
* and allocates memory to new process arrivals based on *
* first fit, next fit, best fit and worst fit strategies *
***********************************************************/
Explanation of Solution
Program:
//Include header files
#include<iostream>
using namespace std;
//Declare variables
int lcount = 0;
//Declare a node "ltemp" and initialize it to NULL
struct lnode *ltemp = NULL;
/*Define a node of the linked list with data and pointer to next node */
struct lnode
{
//Define data of node
int ldata;
//Define pointer to next node
struct lnode *lnext;
};
//Define a node "lnode" and initialize to null
struct lnode *head = NULL;
//The function "printList()" prints all elements of list
void printList()
{
//Set pointer to head of the linked list
struct lnode *ptr = head;
//Loop until the list reaches NULL
while(ptr != NULL)
{
//Display all elements of list
cout<<ptr->ldata;
cout<<"->";
//Iterate to next element of list
ptr = ptr->lnext;
}
}
/* The function "insert()" pushes the element into the linked list, it takes the element to be inserted as argument */
void insert(int ldata)
{
//Allocate memory for the node
struct lnode *link = (struct lnode*)malloc(sizeof(struct lnode));
//Insert data to the node
link->ldata = ldata;
//Set head as link's next
link->lnext = head;
//Set "link" as "head"
head = link;
}
/*The function "first_fit()" allocates the process with memory based on first fit strategy */
void first_fit()
{
//Declare the variables
int id, size;
//Get process id from user
cout<<"Enter process id" ;
//Store the process id
cin>>id;
//Get process size from user
cout<<"Enter process size";
//Store the process size
cin>>size;
//Set pointer to head of the linked list
struct lnode *ptr = head;
//Loop until the list reaches NULL
while(ptr != NULL)
{
/* If the process can be allocated, that is if size is less than or equal to memory size */
if(size <= ptr->ldata)
{
//Allocate the node and set the memory left
ptr->ldata = ptr->ldata - size;
//Traverse to next node of list
ptr = ptr->lnext;
break;
}
else
{
//Move to next node of list
ptr = ptr->lnext;
}
}
}
/*The function "best_fit()" allocates the process with memory based on first fit strategy*/
void best_fit()
{
//Declare the variables
int id, size,f=0, min =5000;
//Get process id from user
cout<<"Enter the process id" ;
//Store the process id
cin>>id;
//Get process size from user
cout<<"Enter the process size";
//Store the process size
cin>>size;
//Set pointer to head of the linked list
struct lnode *ptr = head;
//Loop until the list reaches NULL
while(ptr!=NULL)
{
//store value in node to "b"
int b = ptr->ldata;
/*Take difference of memory present and memory required */
int diff = ptr->ldata - size;
/* If difference has 0 or positive value and also less than or equal to "min" */
if(diff>=0 && diff<=min)
{
//Assign value of minimum difference
min = diff;
/* Store data of node with value of minimum difference */
f = ptr->ldata;
}
//Move to next node
ptr = ptr->lnext;
}
//Set pointer to head of the linked list
struct lnode *ptr1 = head;
//Loop until the list reaches NULL
while (ptr1!=NULL )
{
//check for the node with minimum difference value
if(ptr1->ldata == f )
{
/*Assign the memory left after allocation to node */
ptr1->ldata = min;
/* If there is no space to allocate a process */
if(ptr1->ldata==5000)
//Display error message
cout<<"Allocation not Possible"<<endl;
//Display value of node
ptr1->ldata = 0;
break;
}
//Move to next node of linked list
ptr1= ptr1->lnext;
}
}
/*The function "worst_fit()" allocates the process with memory based on worst fit strategy*/
void worst_fit()
{
//Declare the variables
int id, size;
//Get process id from user
cout<<"Enter the process id" ;
//Store the process id
cin>>id;
//Get process size from user
cout<<"Enter the process size";
//Store the process size
cin>>size;
//Set pointer to head of the linked list
struct lnode *ptr = head;
//Declare the variables
int max = 0, g=0;
//Loop until the list reaches NULL
while(ptr!=NULL)
{
//store value in node to "b"
int b = ptr->ldata;
/*Take difference of memory present and memory required */
int diff = ptr->ldata - size;
/* If difference has 0 or positive value and also less than or equal to "max" */
if(diff>=0 && diff>=max)
{
//Assign the maximum difference value
max = diff;
/* Store data of node with minimum difference value */
g = ptr->ldata;
}
//Move to next node
ptr = ptr->lnext;
}
//Set pointer to head of the linked list
struct lnode *ptr1 = head;
//Declare variables
int lcount = 0;
//Loop until the list reaches NULL
while (ptr1!=NULL)
{
//check for the node with maximum difference value
if(ptr1->ldata == g)
{
/* Assign the memory left after allocation to node */
ptr1->ldata = max;
break;
}
//Move to next node
ptr1= ptr1->lnext;
}
}
/*The function "next_fit()" allocates the process with memory based on next fit strategy*/
void next_fit(struct lnode *ltemp)
{
//Declare variables
int id, size;
//Get process id from user
cout<<"Enter the process id" ;
//Store the process id
cin>>id;
//Get process size from user
cout<<"Enter the process size";
//Store the process size
cin>>size;
//Set pointer to head of the linked list
struct lnode *ptr = ltemp;
//After first iteration of loop allocate to next node
if(lcount>0)
{
//Move to next node of linked list
ptr = ptr->lnext;
}
//Loop until the list reaches NULL
while(ptr != NULL)
{
/* If the process can be allocated, that is if size is less than or equal to memory size */
if(size <= ptr->ldata )
{
//Allocate the node and set the memory left
ptr->ldata = ptr->ldata - size;
//Move to next node
ltemp = ptr->lnext;
//Increment count to represent loop iteration
lcount++;
break;
}
//If size doesn't matches the memory present
else
{
//Move to next node
ptr = ptr->lnext;
}
}
//If the list reaches NULL
if(ptr == NULL)
{
//Set pointer to head of the linked list
struct lnode* ptr1 = head;
//Loop until the list reaches NULL
while(ptr1 != NULL)
{
/*If the process can be allocated, that is if size is less than or equal to memory size */
if(size <= ptr1->ldata )
{
/*Allocate the node and set the memory left */
ptr1->ldata = ptr1->ldata - size;
//Move to next node
ltemp = ptr1->lnext;
/*Increment count to represent loop iteration */
lcount++;
break;
}
//If size doesn't matches the memory present
else
{
//Move to next node
ptr1 = ptr1->lnext;
}
}
}
}
//Define a main function
int main()
{
//Declare variables
int ch;
int c =0;
//Create a linked list, insert the nodes with values
insert(5);
insert(10);
insert(9);
insert(20);
//Display linked list of memory spaces
cout<<"List showing memory layout is "<<endl;
//Call the function "printList()" to display list
printList();
cout<<endl;
//Loop forever until "Exit" is chosen by user
for(;;)
{
//Display the menu
cout<<"1. First Fit"<<endl;
cout<<"2. Best Fit"<<endl;
cout<<"3. Worst Fit"<<endl;
cout<<"4. Next Fit"<<endl;
cout<<"5. Exit"<<endl;
//Get user input
cout<<"Enter your choice"<<endl;
cin>>ch;
/* Define a switch statement to call appropriate function */
switch(ch)
{
/*Call the function "first_fit()" in case of first choice */
case 1:
first_fit();
//Display the list after allocation
cout<<"List after allocation is"<<endl;
/* Call the function "printList()" to display the list */
printList();
break;
/* Call the function "best_fit()" in case of second choice */
case 2:
best_fit();
//Display the list after allocation
cout<<"List after allocation is"<<endl;
/* Call the function "printList()" to display the list */
printList();
break;
/* Call the function "worst_fit()" in case of third choice */
case 3:
worst_fit();
//Display the list after allocation
cout<<"List after allocation is"<<endl;
/* Call the function "printList()" to display the list */
printList();
break;
/* Call the function "next_fit()" in case of fourth choice */
case 4:
//Set "ltemp" as head of linked list
ltemp = head;
next_fit(ltemp);
//Display the list after allocation
cout<<"List after allocation is"<<endl;
/* Call the function "printList()" to display the list */
printList();
break;
//Define case for exit
case 5:
exit(0);
//Default case in switch statement
default:
//Display error message
cout<<"wrong choice";
}
//Pause the console window
system("pause");
}
return 0;
}
List showing memory layout is
20->9->10->5->
1. First Fit
2. Best Fit
3. Worst Fit
4. Next Fit
5. Exit
Enter your choice
1
Enter process id1
Enter process size9
List after allocation is
11->9->10->5->Press any key to continue . . .
1. First Fit
2. Best Fit
3. Worst Fit
4. Next Fit
5. Exit
Enter your choice
2
Enter the process id2
Enter the process size9
List after allocation is
11->0->10->5->Press any key to continue . . .
1. First Fit
2. Best Fit
3. Worst Fit
4. Next Fit
5. Exit
Enter your choice
3
Enter the process id3
Enter the process size1
List after allocation is
10->0->10->5->Press any key to continue . . .
1. First Fit
2. Best Fit
3. Worst Fit
4. Next Fit
5. Exit
Enter your choice
4
Enter the process id5
Enter the process size3
List after allocation is
7->0->10->5->Press any key to continue . . .
1. First Fit
2. Best Fit
3. Worst Fit
4. Next Fit
5. Exit
Enter your choice
Efficiency Comparison of sequential fit Methods
First fit | Best fit | Worst fit | Next first |
Allocates at first possible space | Allocates at best memory space available | Allocates in the largest memory hole present | Allocates first at possible memory space then moves to next node |
Always starts searching from head of list | Always starts searching from head of list | Always starts searching from head of list | Starts searching from memory space allocated before |
It leads to internal fragmentation | It avoids internal fragmentation by chosing best memory space | It reduces the rate of production of small holes | It also leads to internal fragmentation |
It is the fastest | It is slowest of all as it has to consider the best hole | It is less faster than first fit as it has to allocate the largest available space | It is almost as fast as first fit algorithm as it proceeds to next block after assigning first one |
The unused memory after allocation becomes waste | It fills memory with small holes that are useless | A larger process arriving at a later time could not be processed | It reduces the seek time and starts from the previous left off allocated space |
Want to see more full solutions like this?
Chapter 3 Solutions
EBK DATA STRUCTURES AND ALGORITHMS IN C
- Write a C program using embedded assembler with a function to convert a digit (0 – 15) to the corresponding ASCII character representing the value in hexadecimal. For numbers 0 – 9, the output will be the characters '0' – '9', for numbers 10 – 15 the characters 'A' – 'F'. The entire core of the program must be written in symbolic instruction language; arrays may not be used. You may only use C to print the result. Tip: This piece of C program will do the same thing: character = number < 10 ? number + '0' : number + 55; As a basis, you can use this program again , which increments a variable. Just replace the INC instruction with ADD and add a test (CMP) with some conditional jump.arrow_forwardAnswer the question fully and accurately by providing the required files(Java Code, Two output files and written answers to questions 1-3 in a word document)meaning question 1 to 3 also provide correct answers for those questions.(note: this quetion is not graded).arrow_forward.NET Interactive Solving Sudoku using Grover's Algorithm We will now solve a simple problem using Grover's algorithm, for which we do not necessarily know the solution beforehand. Our problem is a 2x2 binary sudoku, which in our case has two simple rules: •No column may contain the same value twice •No row may contain the same value twice If we assign each square in our sudoku to a variable like so: 1 V V₁ V3 V2 we want our circuit to output a solution to this sudoku. Note that, while this approach of using Grover's algorithm to solve this problem is not practical (you can probably find the solution in your head!), the purpose of this example is to demonstrate the conversion of classical decision problems into oracles for Grover's algorithm. Turning the Problem into a Circuit We want to create an oracle that will help us solve this problem, and we will start by creating a circuit that identifies a correct solution, we simply need to create a classical function on a quantum circuit that…arrow_forward
- .NET Interactive Solving Sudoku using Grover's Algorithm We will now solve a simple problem using Grover's algorithm, for which we do not necessarily know the solution beforehand. Our problem is a 2x2 binary sudoku, which in our case has two simple rules: •No column may contain the same value twice •No row may contain the same value twice If we assign each square in our sudoku to a variable like so: 1 V V₁ V3 V2 we want our circuit to output a solution to this sudoku. Note that, while this approach of using Grover's algorithm to solve this problem is not practical (you can probably find the solution in your head!), the purpose of this example is to demonstrate the conversion of classical decision problems into oracles for Grover's algorithm. Turning the Problem into a Circuit We want to create an oracle that will help us solve this problem, and we will start by creating a circuit that identifies a correct solution, we simply need to create a classical function on a quantum circuit that…arrow_forwardAnswer two JAVA OOP problems.arrow_forwardAnswer two JAVA OOP problems.arrow_forward
- C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage LearningNew Perspectives on HTML5, CSS3, and JavaScriptComputer ScienceISBN:9781305503922Author:Patrick M. CareyPublisher:Cengage LearningEBK JAVA PROGRAMMINGComputer ScienceISBN:9781337671385Author:FARRELLPublisher:CENGAGE LEARNING - CONSIGNMENT
- Systems ArchitectureComputer ScienceISBN:9781305080195Author:Stephen D. BurdPublisher:Cengage LearningC++ for Engineers and ScientistsComputer ScienceISBN:9781133187844Author:Bronson, Gary J.Publisher:Course Technology PtrProgramming Logic & Design ComprehensiveComputer ScienceISBN:9781337669405Author:FARRELLPublisher:Cengage




