Comp111: Operating Systems
Classroom Exercise 13 Answers
In class we have studied the buddy system
for memory resource management. Let's do some simulation to make sure we
understand it. In your simulations, please assume that:
(This is roughly the implementation of "BSD malloc".)
- no less than 16 bytes can be allocated via malloc.
- the 16-byte block storage descriptor is physically located before the bytes to be used,
so that the usable memory starts at the descriptor address+16.
- the block descriptor has two 8-byte fields:
next pointer for use in the free list.
size integer that is the power of two
that represents the block's total size.
size is 5, then
- total block size is 25 = 32 bytes.
- total usable memory is 25-16 (descriptor) = 16 bytes.
malloc only calls
sbrk in units of 8192 bytes, i.e.,
the call is of the form
sbrk(n*8192) for n a positive integer.
- Exactly how much memory is allocated to me
if I ask for 800 bytes from
Exactly how much memory is added to the heap?
The allocator fits 800 bytes into 2p-16 for the
smallest p. That is p=10, allocating 1024-16=1008 bytes.
A total of 8192 bytes = 1 page is added to the heap (presuming
that this is the first allocation).
- Describe exactly what happens when one calls
int *foo = (int *)malloc(100*sizeof(int));
as the first
malloc of a program. Assume that
sizeof(int) is 8 (e.g., on
First note that this is related to the first problem, because
At the end, there is one element in the free lists for
212, 211, and 210 bytes, respectively.
- First malloc calls sbrk(8192);
- The block of 8192 is subdivided into two 4096-byte blocks.
- One block of 4096 is subdivided into two 2048-byte blocks.
- One block of 2048 is subdivided into two 1024-byte blocks.
- A pointer to the 16th byte of one of these 1024-byte blocks
is returned to the process.
- Describe exactly what happens when one (subsequently) calls
foo points to 16 bytes beyond the descriptor, so a pointer to the descriptor can be recovered via the code
struct descriptor *p=(struct descriptor *)((char *)foo-16);.
p into the free list for 210 (
foo is not changed.
- Describe exactly what happens when one subsequently calls
int *bar = (int *)malloc(10*sizeof(int));
foo's memory reused? Why or why not?
Note that foo's memory is at the head of the 210 list,
and we want 80 bytes, and thus want to allocate a 128-byte block.
Thus a small part
(1/16) of the memory allocated for
- We split
foo's memory in half to get two 512-byte blocks,
- and then split one 512-byte block into two 256-byte blocks,
- and then split one 256-byte block into two 128-byte blocks,
- and then use one of these for
foo gets reused.
A very common programming error is to write something equivalent to:
int *cat = (int *) malloc(sizeof(int));
int *dog = (int *) malloc(sizeof(int));
free(dog); // segmentation fault: core dumped
Assuming that ints are 8 bytes,
why might this cause a segmentation fault when calling
Depending upon how malloc is implemented, memory can look like this:
<cat descriptor> <dog descriptor>
| next | size | cat| cat| next | size | dog| dog|
cat=0 writes over the
size field of the descriptor for
dog (depending upon implementation), which is unused while the memory is in use. This does nothing.
cat=0 causes a segmentation fault when we try to free
dog, because it writes garbage into the
and misdirects the block to the wrong linked list or an invalid location (NULL) for the list element.
But since we are concerned with
free does not check whether the size field is sane!
In other words, "real programmers don't write out of bounds" and those unreal
programmers that do are in for a lot of pain.
Malloc doesn't use the buddy system for things larger than a page (8192 bytes = 213). So why do we allocate
8 bytes to store a number between 5 and 13? It would seem that this number would take a total of 4 bits = 1/2 of a byte.
Remember that in an IA64 architecture, the alignment requirements for malloc are at 16 byte boundaries. Thus,
if we used only 9 bytes for the descriptor, the resulting address of the allocated memory would be misaligned!