CS 61C Homework 2-1

Background reading

Lecture notes from 6/28 and P&H: Chapters 3.3, 3.5, 3.8

Administrative requirements

Submit your solution online by 8pm on 4th July 2004. Do this by creating a directory named hw2-1 that contains the file hw2-1.txt. From within that directory, type:

submit hw2-1

This is not a partnership assignment; hand in your own work, and don't collaborate with anyone else.

Problem 1

Consider the C program.


     char *set(char c, int i) {
          ___________   /* fill in the blank */
          str[i] = c;
          return str;
     }

     int main() {
          char *output;

          output = set('o', 2);
          output = set('w', 0);
          output = set('r', 1);

	  ... /* some more code, but output is not used within "..." */

          printf("%s", output);

          return 0;
     }

For each of the statements inserted into the blank above (in the function set), what is the output of the program? If the program causes a compilation error, say "compilation error" (compiler warnings do not count). If the program causes a runtime error, say "runtime error". If the program behavior is undefined, say "undefined". Otherwise, say whatever it outputs. EXPLAIN clearly the reason the program behaves this way. An unsupported answer will not receive any credit for this problem.

a. static char str[ ] = "thing";
b. char str[ ] = "thing";
c. char *str = (char *)malloc(6); strcpy(str, "thing");

Some advice: It is recommended that you answer this question without using the compiler to come up with an answer for you--since, on a midterm, you will not be able to use a compiler should a similar question come up ;) So, try to come up with the answer in your head and use then use the compiler afterward to check to see if the answer you came up with was correct.

Problem 2

If the heap is 16 bytes large, determine the behavior of best fit, first fit, next fit, and the buddy system after the following allocation/deallocation scheme. If the memory management algorithm cannot satisfy the requests, indicate which step the algorithm fails. If the memory management algorithm can satisfy the requests, show the state of the heap after step (7).

(1) allocate 5 bytes
(2) allocate 8 bytes
(3) allocate 3 bytes
(4) free memory allocated in (1)
(5) free memory allocated in (3)
(6) allocate 3 bytes
(7) allocate 5 bytes

Some clarification: Assume that "allocate 5 bytes" includes any header information (so you do not need to allocate more than 5 bytes for the next pointer, the size, etc). Also assume that if you need to split a free block that the lower portion of the free block is allocated (and the higher portion remains free).

Problem 3

A machine uses the buddy system for memory management of its heap. Initially it has one block of 256 bytes starting at address 0. Determine whether the following free blocks are buddies, and can therefore be combined to make a larger free block:

a. block 1 (address 64, size 32) and block 2 (address 96, size 32)
b. block 1 (address 128, size 64) and block 2 (address 64, size 64)
c. block 1 (address 96, size 16) and block 2 (address 80, size 16)

Problem 4

Do problems 3.1, 3.2, 3.5, and 3.6 in P&H.