
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
- using r language Obtain a bootstrap t confidence interval estimate for the correlation statistic in Example 8.2 (law data in bootstrap).arrow_forwardusing r language Compute a jackknife estimate of the bias and the standard error of the correlation statistic in Example 8.2.arrow_forwardusing r languagearrow_forward
- using r languagearrow_forwardThe assignment here is to write an app using a database named CIT321 with a collection named students; we will provide a CSV file of the data. You need to use Vue.js to display 2 pages. You should know that this assignment is similar, all too similar in fact, to the cars4sale2 example in the lecture notes for Vue.js 2. You should study that program first. If you figure out cars4sale2, then program 6 will be extremely straightforward. It is not my intent do drop a ton of new material here in the last few days of class. The database contains 51 documents. The first rows of the CSV file look like this: sid last_name 1 Astaire first_name Humphrey CIT major hrs_attempted gpa_points 10 34 2 Bacall Katharine EET 40 128 3 Bergman Bette EET 42 97 4 Bogart Cary CIT 11 33 5 Brando James WEB 59 183 6 Cagney Marlon CIT 13 40 GPA is calculated as gpa_points divided by hrs_attempted. GPA points would have been arrived at by adding 4 points for each credit hour of A, 3 points for each credit hour of…arrow_forwardI need help to solve the following case, thank youarrow_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




