We help IT Professionals succeed at work.

Please, I urgently need help.

RandomAccess
RandomAccess asked
on
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.
Comment
Watch Question

Commented:
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.

Author

Commented:
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.
Commented:
RandomAccess

As I understand your post you have an area of 10000 bytes allocated and you have to dole out chunks of this to the users on a best fit basis. Is this correct?

As a first idea could you have a header block for each chunk, both allocated and free, with the following format.

structure contains:
1) integer to indicate whether chunk is used or free.
2) pointer to end of this chunk.

We don't need to store the start address in the header structure as we already know this and we can run through the memory area by using the end pointer in a header to get to the end of the current chunk then advance 1 byte to get to the next chunk header. As each chunk has its own header whether or not it is used or free then we can always find our way around easily.

Initially the memory area would have one header with the used flag set to free and the end pointer pointing to the end of the memory area.

As the user asks for a block of memory you would then run through each chunk with the following logic.

1) Start at the first header and create a variable to hold the size of a chunk of memory (lets call in freeval) and set it to the size of your memory buffer less the size of a header (ie the amount of free memory in your list) and a variable to hold a pointer (lets call it freeptr)

2) If it is marked as used then advance to the end of that chunk (using the pointer in the header) and then advance 1 byte to get to the start of the next header.

OR

If the header shows that the chunk is free then calculate the size of the chunk (by subtracting your current address + the size of the header from the end address in the header). If the size of this chunk is less than the amount of the request then go back to step 2.

We now know that the chunk of memory we are looking at is (a) free and (b) larger then or equal to the amount of the request. So now we compare the size of this chunk with the freeval variable. If this chunk is smaller than the value of freeval we know that this chunk is a better fit than any other free chunk we have looked at previously in the buffer so we update freeval with the size of this chunk and update freeptr with the address of this chunk. We also set a variable to indicate that we have found a valid chunk that is a candidate for use.

3) We continue doing step 2 until we get to the end of the memory area at which stage we either know that there is no chunk bige enough in which case we return an error to the caller OR we know the size and address of the smallest chunk that will fulfill our request. If this is so we go to step 4.

4) Move to the address pointed to by the pointer in freeptr.

5) Store the ending address in the free header found there for use later then write a used header with the used flag set and the end address set to the address of the end of the chunk (ie the current address + the size of a header + the size of the area requested by the user.

6) If the size of the allocation request + the size of a header is equal to the value of freeval then we know that this new chunk fills the previous free space in the chunk exactly so we can return the pointer to this chunk to the caller. If not we go to step 7.

7) We have to create a free chunk header for what is left over after we allocated our new chunk so we move to the address pointed to by the end pointer in our newly created header (ie the end of the newly allocated chunk) and then advance 1 byte to get to the next header location. We then create a new free header and set the end pointer in this header to be the address we saved in step 6.

This logic should work and should be relatively easy to code with no spaghetti code required.

If this idea appeals and you need more help please do not hesitate to ask.

Cheers - Gavin

Explore More ContentExplore courses, solutions, and other research materials related to this topic.