Link to home
Start Free TrialLog in
Avatar of RandomAccess
RandomAccess

asked on

Please, I urgently need help.

I have to get write this program asap, and have been working on it for over a week and still cannot figure it out. I am new to the language and I don't understand some of it. I know this is worth more than 75 points, but those are all I have to give. I will describe the program.

The program has to be written in C and simulate a best-fit strategy for memory allocation. It is to be done with a linked list, a starting block of 10000 free spaces of memory(0-9999). The program is supposed to use commands to allocate/deallocate blocks of this memory(it is kind of counter intuitive, the blocks represent memory not yet used, so when you allocate something, one of the block will either be made smaller or used up entirely, depending on the size the user inputs.

The data structure for the blocks(nodes) is two int variables, one for the starting address of the block and one for the ending address, and a pointer to the next node.

The allocate command asks for one variable, size, and the deallocate asks for the starting address and the size.

Now, I have been working on this night and day, writing linked list functions like deletenode, addnode, addnode in the right order, count the nodes, etc.. Thinking that I would be able to use them together to carry out this process. But I do not understand the operations that will make them all come together and do this.

My school sucks and getting help from anybody their is like getting blood from a rock. Two assistants to help 400 students. So I am hoping that someone here could help shed some light on how this would work. I have alot of basic functions written for the linked lists(they took me forever). If anyone would be so kind as to show me how to use these kind of functions to perform this process I would be very grateful.
Avatar of imladris
imladris
Flag of Canada image

We cannot, as I think you understand, do you homework for you. To facilitate using this forum as help, which is perfectly legitimate, it is best if you can both show the work you have done, and ask specific questions.

As a basic overview:

you should be managing a linked list that describes the memory (free or used). Each block of memory should be represented on the list. So to start you would have a single node, which is marked free, and has size 10000). When a block allocation is requested, you search through your list to find a free block that is the smallest possible that still fulfills the request (smallest possible for best fit). When you have found one you reduce the existing block size by the allocation amount, create a new block for the allocation amount, mark it as used, and insert it into the list.

Voila, a memory manager is born. You will probably need some reporting functions to show how your simulator is performing.

So, see if that helps. When you get stuck post (some relevant section) of your code, and ask a specific question. I, for one, am willing to go through the process with you (which will undoubtedly involve more than 1 question) for the 75 points, though I can't vouch for the time frame. But there are other experts here too.
Avatar of RandomAccess
RandomAccess

ASKER

Thank you for posting. From what you said, I seem to at least to have been on the right track. I think my real stumbling block is trying to figure out a function that will do the best fit part. I have written a function that can tell if a node is big enough, but how do I decide which node is smallest and fits. I have thought of maybe storing them in a variable, but whenever I do that on paper i end up writing all these nested if statements that are most likely unnecessary and almost w/o question won't work(I am new enough to programming that I still have trouble with most errors.)

Here the node

typedef struct node{
     int startaddress;
     int endaddress;
     struct node *nextptr;
     }STRNODE;


Now I have the program set up so that whe the user begins putting in options, a block from 0-9999 has already been created. Then I haev a bunch of functions that add, order, and delete nodes. I thought by making these i would be able to do this procedure by combining them in some way.

But maybe I should just create a function that does it all at once? The one function I am trying to write would go through all the nodes, and return the one with the smallest size but that was big enough to fit. let me show you how I get stuck, I will write one of my attempts.

int scanlist(STRNODE **hp, int d)   /*d is the size the user entered*/

int nodesize;
STRNODE *curr;
curr=*hp;

while(curr!= NULL){
  nodesize= (curr->endaddress)-(curr->startaddress);
  if(nodesize < d){
   curr=curr->nextptr;
   return;
  }
  else{
   if(nodesize >= d){
     ....

this is where I get stuck. I just have this feeling that I know i'm doing it wrong. Andif this is kind of the way to do this, I am not sure how to keep the values. I basically want to store the node as the one to use if the users size will fit in it. As the while loop goes, if it finds one that is smaller but still fits, it will replace the other as the node to be allocated from.

I understand that you can't do my homework for me, but I am very appreciative that you took the time to help me out. If what I wrote in this comment makes any sense, at least if the problem I am having is clear, could you point me in the right direction. But if you can't, thank you again anyway for taking the time to help me.
ASKER CERTIFIED SOLUTION
Avatar of newmang
newmang

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial