Counting memory blocks

Question

This is a homework question from compiler design course. I just need an explanation of certain parts of the question.

It is claimed that returning blocks to the standard memory manager would require much administration. Why is it not enough to have a single counter per block, which holds the number of busy records for that block, and to return the block when it reaches 0?

The context in which it refers to speaks about linked lists.

The answer from the answer sheet states:

How do you find this counter starting from the pointer to the record and how do you get the pointer by which to return the block?

Coming from a C based background. Could someone explain to me what:

1. block is?
2. the counter does?
3. a busy record is?

A reference to documents that provide a walk-through of what happens during this counting phase. Diagrams would be helpful.

Thanks.

Answer 1

A "block" most likely is a basic block.

I'm not familiar with the term "busy record"; most likely, it refers to some data flow analysis result for variables (i.e. variables might be considered "busy"). Several definitions seem plausible:

1. a variable may be considered "busy" if it holds a value (i.e. has been "written") which also will be "read" (meaning that you can't eliminate the variable easily)
2. a variable may be considered "busy" if it is used "often" (more often than other variables), meaning that you should try to allocate it to a register.

However, you should really find out how the term was defined in your course.

Then, the counter would count, per basic block, the number of variables that are busy. Why that counter may become 0 after some processing is unclear - most likely, "busy" has yet another meaning in your course.

Answer 2

I think it may help if I change some terms, to better explain what I am guessing is going on.

If you have a page of memory, we can say a page is 8k in size. This is the minimum size that is allocated by the memory manager.

You have 10 requests of 100 bytes each, so 1000 bytes are in various places on the page.

The counter would be 10, but, how do you know what is actually freed, or has already been allocated, as the 10 requests may not be contiguous, as there may have been other requests that have already been freed.

So, we have 10 busy records.

Now, you would need to come up with your own answers to the question in the answer sheet, but, hopefully by looking at an example it may be simpler.

Answer 3

1. block is? the manager had divided the memory space into blocks. one or more blocks compose of a memory area unit which is usable for accessing continuously by the user. if require more memory, the manager will add extra block(s) to that memory area. while the manager is always trying to give continuous blocks to the user.

2. the counter does? for a specific block, it may be used by different users, that is, the memory area is shared by multiple users.

3. a busy record is? the counter value which is stored in above "counter".

for example:

struct block {
    struct block *next;
    long counter; //@< the busy record
};

EDIT: changing "area" to "user"
struct user {
    struct block *head;
    ...
};

EDIT: answer the question "why is a counter not enough for a block?" Needs more information when move a block from a "free block list" to a "allocated block list" or vice versa, e.g. order used to locate a position in a list quickly. while i just guess per this point.