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
- Question#2: Design and implement a Java program using Abstract Factory and Singleton design patterns. The program displays date and time in one of the following two formats: Format 1: Date: MM/DD/YYYY Time: HH:MM:SS Format 2: Date: DD-MM-YYYY Time: SS,MM,HH The following is how the program works. In the beginning, the program asks the user what display format that she wants. Then the program continuously asks the user to give one of the following commands, and performs the corresponding task. Note that the program gets the current date and time from the system clock (use the appropriate Java date and time operations for this). 'd' display current date 't': display current time 'q': quit the program. • In the program, there should be 2 product hierarchies: "DateObject” and “TimeObject”. Each hierarchy should have format and format2 described above. • Implement the factories as singletons. • Run your code and attach screenshots of the results. • Draw a UML class diagram for the program.arrow_forward#include <linux/module.h> #include <linux/kernel.h> // part 2 #include <linux/sched.h> // part 2 extra #include <linux/hash.h> #include <linux/gcd.h> #include <asm/param.h> #include <linux/jiffies.h> void print_init_PCB(void) { printk(KERN_INFO "init_task pid:%d\n", init_task.pid); printk(KERN_INFO "init_task state:%lu\n", init_task.state); printk(KERN_INFO "init_task flags:%d\n", init_task.flags); printk(KERN_INFO "init_task runtime priority:%d\n", init_task.rt_priority); printk(KERN_INFO "init_task process policy:%d\n", init_task.policy); printk(KERN_INFO "init_task task group id:%d\n", init_task.tgid); } /* This function is called when the module is loaded. */ int simple_init(void) { printk(KERN_INFO "Loading Module\n"); print_init_PCB(); printk(KERN_INFO "Golden Ration Prime = %lu\n", GOLDEN_RATIO_PRIME); printk(KERN_INFO "HZ = %d\n", HZ); printk(KERN_INFO "enter jiffies = %lu\n", jiffies); return 0; } /* This function is called when the…arrow_forwardList at least five Operating Systems you know. What is the difference between the kernel mode and the user mode for the Linux? What is the system-call? Give an example of API in OS that use the system-call. What is cache? Why the CPU has cache? What is the difference between the Static Linking and Dynamic Linking when compiling the code.arrow_forward
- In the GoF book, List interface is defined as follows: interface List { int count(); //return the current number of elements in the list Object get(int index); //return the object at the index in the list Object first(); //return the first object in the list Object last(); //return the last object in the list boolean include(Object obj); //return true is the object in the list void append(Object obj); //append the object to the end of the list void prepend(Object obj); //insert the object to the front of the list void delete(Object obj); //remove the object from the list void deleteLast(); //remove the last element of the list void deleteFirst(); //remove the first element of the list void deleteAll(); //remove all elements of the list (a) Write a class adapter to adapt Java ArrayList to GoF List interface. (b) Write a main program to test your adapters through List interface. (c) Same requirement as (a) and (b), but write an object adapter to adapt Java ArrayList to GoF List…arrow_forwardIn modern packet-switched networks, including the Internet, the source host segments long, application-layer messages (for example, an image or a music file) into smaller packets and sends the packets into the network. The receiver then reassembles the packets back into the original message. We refer to this process as message segmentation. Figure 1.27 (attached) illustrates the end-to-end transport of a message with and without message segmentation. Consider a message that is 106 bits long that is to be sent from source to destination in Figure 1.27. Suppose each link in the figure is 5 Mbps. Ignore propagation, queuing, and processing delays. a. Consider sending the message from source to destination without message segmentation. How long does it take to move the message from the source host to the first packet switch? Keeping in mind that each switch uses store-and-forward packet switching, what is the total time to move the message from source host to destination host? b. Now…arrow_forwardConsider a packet of length L that begins at end system A and travels over three links to a destination end system. These three links are connected by two packet switches. Let di, si, and Ri denote the length, propagation speed, and the transmission rate of link i, for i = 1, 2, 3. The packet switch delays each packet by dproc. Assuming no queuing delays, in terms of di, si, Ri, (i = 1, 2, 3), and L, what is the total end-to-end delay for the packet? Suppose now the packet is 1,500 bytes, the propagation speed on all three links is 2.5 * 10^8 m/s, the transmission rates of all three links are 2.5 Mbps, the packet switch processing delay is 3 msec, the length of the first link is 5,000 km, the length of the second link is 4,000 km, and the length of the last link is 1,000 km. For these values, what is the end-to-end delay?arrow_forward
- how to know the weight to data and data to weight also weight by infomraion gain in rapid miner , between this flow diagram retrieve then selecte attrbuite then set role and split data and decision tree and apply model and peformance ,please show how the operators should be connected:arrow_forwardusing rapid miner how to creat decison trea for all attribute and another one with delete one or more of them also how i know the weight of each attribute and what that mean in impact the resultarrow_forwardQ.1. Architecture performance [10 marks] Answer A certain microprocessor requires either 2, 4, or 6 machine cycles to perform various operations. ⚫ (40+g+f)% require 2 machine cycles, ⚫ (30-g) % require 4 machine cycles, and ⚫ (30-f)% require 6 machine cycles. (a) What is the average number of machine cycles per instruction for this microprocessor? Answer (b) What is the clock rate (machine cycles per second) required for this microprocessor to be a "1000 MIPS" processor? Answer (c) Suppose that 35% of the instructions require retrieving an operand from memory which needs an extra 8 machine cycles. What is the average number of machine cycles per instruction, including the instructions that fetch operands from memory?arrow_forward
- Q.2. Architecture performance [25 marks] Consider two different implementations, M1 and M2, of the same instruction set. M1 has a clock rate of 2 GHz and M2 has a clock rate of 3.3 GHz. There are two classes of instructions with the following CPIs: Class A CPI for M1 CPI for M2 2.f 1.g B 5 3 C 6 4 Note that the dots in 2 fand 1.g indicate decimal points and not multiplication. a) What are the peak MIPS performances for both machines? b) Which implementation is faster, if half the instructions executed in a certain program are from class A, while the rest are divided equally among classes B and C. c) What speedup factor for the execution of class-A instructions would lead to 20% overall speedup? d) What is the maximum possible speedup that can be achieved by only improving the execution of class-A instructions? Explain why. e) What is the clock rate required for microprocessor M1 to be a "1000 MIPS" (not peak MIPS) processor?arrow_forwardPLEASE SOLVE STEP BY STEP WITHOUT ARTIFICIAL INTELLIGENCE OR CHATGPT I don't understand why you use chatgpt, if I wanted to I would do it myself, I need to learn from you, not from being a d amn robot. SOLVE STEP BY STEP I WANT THE DIAGRAM PERFECTLY IN SIMULINKarrow_forwardI need to develop and run a program that prompts the user to enter a positive integer n, and then calculate the value of n factorial n! = multiplication of all integers between 1 and n, and print the value n! on the screen. This is for C*.arrow_forward
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
New Perspectives on HTML5, CSS3, and JavaScriptComputer ScienceISBN:9781305503922Author:Patrick M. CareyPublisher:Cengage Learning
EBK JAVA PROGRAMMINGComputer ScienceISBN:9781337671385Author:FARRELLPublisher:CENGAGE LEARNING - CONSIGNMENT
Systems ArchitectureComputer ScienceISBN:9781305080195Author:Stephen D. BurdPublisher:Cengage Learning
C++ for Engineers and ScientistsComputer ScienceISBN:9781133187844Author:Bronson, Gary J.Publisher:Course Technology Ptr
Programming Logic & Design ComprehensiveComputer ScienceISBN:9781337669405Author:FARRELLPublisher:Cengage