5

I have need some some help with some thinking around a task.

My task is to create one memory area

void *memory = malloc(320);

and then use pointers to store texts into this storage place: We want to divide this area into data blocks of 32 bytes, sow we can store: 320/32 = 10 data blocks a 32 bytes. Into one data block I can store (1 ASCSII char = 1 bytes) 32 characters.

I have a bitmap that is 10 long where every bit indicates if data block is used(1) or not(0).

But what if I want to store a text that is 60 characters long? Then i need 2 data blocks (2 x 32 bytes). The bitmap shows that data block 2 and 6 are free, 1 and 6 is not side by side. How can I achieve this?

struct  data {
    char * text;
};

typedef struct data d;

d->text = ???
Greg Hewgill
  • 951,095
  • 183
  • 1,149
  • 1,285
user265767
  • 559
  • 3
  • 12
  • 27
  • 8
    If there aren't two adjacent free blocks, then you can't satisfy the request for a 60 byte string. You've just discovered "memory fragmentation": http://en.wikipedia.org/wiki/Memory_fragmentation – Steve Jessop Oct 14 '10 at 21:48
  • So your only options would be to defragment (which requires people to not hold on to pointers), or to allocate more memory. – EboMike Oct 14 '10 at 21:50
  • The fact that your problem description calls for only 60 characters when you can fit 64 characters in two blocks may be a hint that you're supposed to do something with the remaining 4 characters. – Dan Bryant Oct 14 '10 at 22:43

6 Answers6

4

This is called memory fragmentation and is a serious problem. You have to report out of memory even though there is technically enough to support the block.

Managed languages like C# that don't allow pointers (in the normal case - please don't fixate on this) have the freedom to rearrange the underlying memory and fix this problem (though it's not free in terms of performance).

To fix the problem in C:
There's not a lot you can do because those pointers into the memory prevent you from reshuffling everything. Someone else has mentioned the buddy system and there are others but few are simple. A lot are based on having preset 'big chunks' and 'small chunks' and only allowing small requests small chunks etc... but that's all to stop arriving at the problem in the first place, once you're there you either deny the memory request or expand the pool.

Daniel
  • 1,994
  • 15
  • 36
0

As mentioned in other comments and answers, this is a fragmentation problem. You could either defragment the code (which will impose lots of requirements and limitations on how systems are allowed to access the memory), or allocate memory.

There are techniques to minimize fragmentation. One popular one is buddy memory allocation: http://en.wikipedia.org/wiki/Buddy_memory_allocation

EboMike
  • 76,846
  • 14
  • 164
  • 167
0

You would have to add a kind of a memory manager layer that keeps track of what slots a particular entry occupies (in this case a string) and in which order the slots are used - your bit field would not be enough.

AndersK
  • 35,813
  • 6
  • 60
  • 86
0

Your string data structure should be exactly like your block manager except it should track "local" blocks rather than all blocks in the memory pool.

stonemetal
  • 6,111
  • 23
  • 25
0

Some thoughts off the top of my head:

  • Add on to your storage architecture by having all requests to your storage go through a controller/manager that abstracts access to the storage (could be the same one that handles the bitmap). This would allow you to defragment your storage while not worrying about other parts of the app having pointers to the wrong place after defragmentation.

  • You could rewrite the spec for your storage system so that one specific byte of each block is used to store a number identifying the "next" block (thus having only 31 bytes of effective storage per block).

Jeff
  • 21,744
  • 6
  • 51
  • 55
  • Or every block is char a[32], struct message contains a array that points out data_blocks, then I can divide a string into blocks and add the block number to the array ? – user265767 Oct 14 '10 at 22:43
0

You could a byte from the each of the 10 32 byte spaces and used that byte as an index to the continuation of the string. This would actually be a linked list, and you could make it a doubly linked list by having the forward and backward indexes.

nategoose
  • 12,054
  • 27
  • 42