You are expected to do your own work on all homework assignments. (See the statement of Academic Dishonesty on the Syllabus.)
Check the Syllabus for the late assignment policy for this course.
Assignments need to be turned in via Laulima. Check the Syllabus for the late assignment policy for the course.
You should turn in single plain text file named README.txt with your answers to the assignment’s questions. Your file must be readable “as is” and points will be removed if the report is not readable.
In this exercise we “reverse-engineer” some code to try to determine how the heap in a C program is managed. Consider the following C program (compiled as an executable called memory):
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
int chunk_sizes[4];
if ((argc != 2) ||
(sscanf(argv[1], "%d,%d,%d,%d", &chunk_sizes[0], &chunk_sizes[1], &chunk_sizes[2], &chunk_sizes[3]) != 4) ||
(chunk_sizes[0] < 0) || (chunk_sizes[1] < 0) || (chunk_sizes[2] < 0) || (chunk_sizes[3] < 0) ) {
fprintf(stderr,"Usage: %s a,b,c,d\n", argv[0]);
fprintf(stderr," where a, b, c, and d above must be >=0 integers (chunk sizes)\n");
exit(1);
}
char *ptrs[9];
unsigned long sizes[9] = {1024, 128, 1024, 128, 1024, 32, 1024, 128, 1024};
for (int i=0; i < 9; i++) {
ptrs[i] = (char *)calloc(sizes[i], sizeof(char));
printf("%ld | ", (unsigned long)(ptrs[i]));
}
printf("\n--------------\n");
free(ptrs[0]); free(ptrs[1]); free(ptrs[3]); free(ptrs[5]); free(ptrs[7]);
for (int i=0; i < 4; i++) {
if (chunk_sizes[i] > 0) { // If the user specified a 0-size chunk, do nothing
char *chunk = (char *)calloc(chunk_sizes[i], sizeof(char));
printf("The %d-byte chunk was allocated at address %ld\n", chunk_sizes[i], (unsigned long)(chunk));
}
}
exit(0);
}
On some system, invoking the program as
./memory 0,0,0,0always produces this output:
0 | 1024 | 1152 | 2176 | 2304 | 3328 | 3360 | 4384 | 4512 |
--------------If invoking the program as
./memory 70,0,0,0produces this output:
0 | 1024 | 1152 | 2176 | 2304 | 3328 | 3360 | 4384 | 4512 |
--------------
The 70-byte chunk was allocated at address 2234would you conclude that the heap allocator allocates new chunks of RAM at the beginning (i.e., lower addresses) or at the end (i.e., higher addresses) of holes in memory? To explain why, use a contraposition argument (e.g., if the heap allocator did X then Y would happen, but instead Z happens).
Whatever the heap allocator does, this is what we assume it does for all subsequent questions. Also, in all subsequent questions, we assume that all considered algorithms go through the list of holes left to right (i.e., from low addresses to high addresse), and when there is a choice, the algorithms always pick the leftmost hole.
If invoking the program as
./memory 80,20,30,10produces this output:
0 | 1024 | 1152 | 2176 | 2304 | 3328 | 3360 | 4384 | 4512 |
--------------
The 80-byte chunk was allocated at address 1072
The 20-byte chunk was allocated at address 1052
The 30-byte chunk was allocated at address 3330
The 10-byte chunk was allocated at address 4502would you say that the heap allocator uses
If invoking the program as
./memory 1100,105,100,20produces this output:
0 | 1024 | 1152 | 2176 | 2304 | 3328 | 3360 | 4384 | 4512 |
--------------
The 1100-byte chunk was allocated at address 52
The 105-byte chunk was allocated at address 2199
The 100-byte chunk was allocated at address 4412
The 20-byte chunk was allocated at address 2179would you say that the heap allocator uses
After looking up some documentation, you find out that the heap allocator uses Best fit! What would the output of the memory program be when invoked as follows:
./memory 500,100,100,20