A program to control memory for a task in C

I have got a task to solve, that is a bit cryptic. The task is to make a program in C that handles texts messages, the program should simulate a system with a small amount of memory, the system should only be able to hold X messages with maximum X characters, every character takes 1 byte (ASCII). To manage messages should I make a system that is held in the primary memory (to simulate a system with limited memory). When the program starts the program should allocate ONE memory area for all information for messages.

This is called the metadatastructure in the task:

The memory area used for storage in its entirety to be continuous in memory, but divided in 32 bytes data blocks, the amount of data blocks in the system should be limited to 512.

The tasks also says that i should create X number data blocks , X depends on with value X number messages the system is set to contain.

I believe I need to create a structure like a ring buffer to hold every message (data block?).

This is called the bitmap for data blocks :

To keep track of witch data block that is free and busy I have to implement a bitmap where I have 1 but for each data block. The bit value is 0(busy)/ 1(free). This bitmap should be used to find free data blocks when I want to add a message, the bitmap should be up to date when the systems deletes or creates a data block for a message.

The allocated memory for this system should be divided into 3 blocks /areas , 1 for the metadatastructure, 1 for the bitmap for each data block and 1 for data blocks.

I need help to thing aloud about solutions and how this can be solved in C. Thanks

At the beginning of your program malloc a large block. The return pointer is where it starts and you know how big the block you asked for is so you know where it ends.

That's your memory store.

Write a allocator and de-allocator that use the store (and only the store) and call them from the rest of your program instead of calling malloc and free...

This task can also be done with a whopping big array and using array offsets as pointer equivalents, but that would be silly in c. I only mention it because I used one constructed that way in fortran for years in a major piece of particle physics software called PAW.

concerning the bit map

Your allocator must know at all times which parts of the store are in use and which are not. That's the only way it can reliably give you a currently unused block, right? Maintaining a bitmap is one way to do that.

Why is this good? Imagine that you've been using this memory for a while. Many objects have been allocated in that space and some have been freed. The available space is no long continuous, but instead is rather patchy.

Suddenly you need to allocated a big object.

Where do you find a large chunk of continuous free memory to put it in? Scanning the bitmap will be faster than walking a complicated data structure.

Thank you. But what about the bitmap?

2010-10-10 17:44:50

Thanks. The explanation and idea is great! But how can I take this idea out in practice? Here is what I struggle to understand. To control all messages and to have them organize I need to have a data structure (do not use the memory we allocated at the start of the program), I believe that a ring buffer will do what I take about ?

2010-10-10 18:41:14

The ring buffer will have a variable that points to the data block that is reserved for the message text to the message, sow the message text to a message will not actual be stored in the ring buffer, correct ? The memory that contains the message text is divided into 32 bytes data blocks, sow a message over 32 characters will be spread over several 32 bytes data-blocks.

2010-10-10 18:41:42

Sow when I want to add a message text to an message in my system I have to use an allocator (my own written) to declare an 32 bytes block inside my already allocated memory, how can I allocate two(or more) 32 bytes data-blocks to store a text over 32 bytes/characters ? And how can i write a bitmap to hold control over which data-blocks that is ready and used ?I have never done a C program where I have needed to take care of bites and bytes.

2010-10-10 18:42:20

Sorry. Number of letters limit!!!

2010-10-10 18:43:21

@user: These are all very good questions. Solving them is the point of the exercises. One possible way to makes some progress: find a real world analogy. Imaging that you had a wall full of mail boxes. Design a system for allocating those boxes to people on demand (i.e. when they ask for them) and letting them give up a box when their done with it. What would you keep track of which ones were already assigned? The boxes holes are your blocks. What if you wanted people to be able to ask for several boxes in a row. That equivalent to the "more than one block" allocation problem.

dmckee 2010-10-10 18:56:23

Is the any way to allocate a data block inside a already allocated block? void *memory = malloc(24000); void *memory2 = realloc(memory, 32); This will just shrink memory ?

2010-10-10 21:28:07

@user: There is not. The whole point of this exercise is that *you* will have to keep track of which bits of the store are in use and which are free and figure out how to efficiently fulfill requests. When you have successfully completed this exercise you will know something about how `malloc` and `free` could be implemented (but not necessarily how any particular version *is* implemented because there is more than one way to solve this problem).

dmckee 2010-10-10 21:34:04

Ok. But after allocated a big memory block, how can I then create a object inside the already allocated memory? The bitmap should keep the track for me, do you have any example of a bitmap?

2010-10-10 22:06:23

In words: Creates X numbers of meta data-listings, then a bitmap with X bits, and then X numbers data-blocks where each is 32 bytes (bitmaps X is equal to X numbers data-blocks). This 3 memory ares should will be located consecutively in the computer`s real memory.My theoretical plan: Allocate a big enough memory area to hold all this 3 memory ares(with malloc). Then i am not sure how i can create data-listings without using malloc?t sure how i can create data-listings without using malloc?

2010-10-10 22:52:12

@user: *You* need to write some code which does something very much linke what malloc and free do. You should write something like `block* my_malloc(const int blocks)` which returns a pointer to a piece of the store that was free (and you have to do the bookkeepping to mark as no longer free). Likewise write a `void my_free(block*b)`, which marks that allocation as no longer in use. These functions will do that by maintaining the bitmap and some other data structures (which *you* need to figure out) to insure that they can meet all the requirements you were given.

dmckee 2010-10-11 03:36:04

ansaurus

tags:

views:

answers:

A program to control memory for a task in C

related questions