You are responsible for all material presented in lecture. You are also responsible for all associated reading assignments and material covered by practice and homework problems in the text.
Note the exam 3 covers only the material since Exam 2. Students are permitted to bring one 8 1/2 x 11 piece of paper to the exam.DO NOT EXPECT to see these specific questions on your exam (but you might).
Please note that code examples in the text are available from the textbook student site for you to copy, compile, edit, and experiment.
Note that textbook reference are for the 2nd edition of the text. If you are using the first edition, please see the Exam Review page for Spring 2010 for section numbers and practice problems.
31 2 1 0 __________________________________ Header | Block Size (bytes) | | | | |___________________________|_|_|_| | | | | | | | | |_________________________________| Footer | Block Size (bytes) | | | | |___________________________|_|_|_|Each memory block, either allocated or free, has a size that is a multiple of eight bytes. Thus, only the 29 higher order bits in the header and footer are needed to record block size, which includes the header and footer. The usage of the remaining 3 lower order bits is as follows: -- bit 0 indicates the use of the current block: 1 for allocated, 0 for free. -- bit 1 indicates the use of the previous adjacent block: 1 for allocated, 0 for free. -- bit 2 is unused and is always set to be 0.
Given the address of a word (4 bytes) in the heap in the left column, and the original contents of the heap in the middle column, show the new contents of the heap in the right column after a call to free(0x400b010) is executed. Your answers should be given as hex values. Note that the address grows from bottom up. Assume that the allocator uses immediate coalescing, that is, adjacent free blocks are merged immediately each time a block is freed.
Address | Current Value | New Value |
---|---|---|
0x400b028 | 0x00000012 | |
0x400b024 | 0x400b611c | 0x400b611c |
0x400b020 | 0x400b512c | 0x400b512c |
0x400b01c | 0x00000012 | |
0x400b018 | 0x00000013 | |
0x400b014 | 0x400b511c | 0x400b511c |
0x400b010 | 0x400b601c | 0x400b601c |
0x400b00c | 0x00000013 | |
0x400b008 | 0x00000013 | |
0x400b004 | 0x400b601c | 0x400b601c |
0x400b000 | 0x400b511c | 0x400b511c |
0x400affc | 0x00000013 |
|--------|--------|--------|--------|--------| | 16a | 32f | | | | |--------|--------|--------|--------|--------|The calls to malloc( ) and free( ) are cumulative, so each call starts from the row above except the first which starts with and empty heap.
A. Perform the series of calls to malloc and free
using first fit to choose a free block for malloc() and immediate
coalescing to merge blocks after free().
B. Perform the series of calls to malloc() and free()
using best fit to choose a free block for malloc() and immediate
coalescing to merge blocks after free().
ptr1 = malloc( 32 ) |--------|--------|--------|--------|--------| | | | | | | |--------|--------|--------|--------|--------| ptr2 = malloc(16); |--------|--------|--------|--------|--------| | | | | | | |--------|--------|--------|--------|--------| ptr3 = malloc(16); |--------|--------|--------|--------|--------| | | | | | | |--------|--------|--------|--------|--------| ptr4 = malloc(40); |--------|--------|--------|--------|--------| | | | | | | |--------|--------|--------|--------|--------| free(ptr3); |--------|--------|--------|--------|--------| | | | | | | |--------|--------|--------|--------|--------| free(ptr1); |--------|--------|--------|--------|--------| | | | | | | |--------|--------|--------|--------|--------| ptr5 = malloc(16); |--------|--------|--------|--------|--------| | | | | | | |--------|--------|--------|--------|--------| free(ptr4); |--------|--------|--------|--------|--------| | | | | | | |--------|--------|--------|--------|--------| ptr6 = malloc(48); |--------|--------|--------|--------|--------| | | | | | | |--------|--------|--------|--------|--------| free(ptr2); |--------|--------|--------|--------|--------| | | | | | | |--------|--------|--------|--------|--------|
________________________ | | | | | KEY | PAYLOAD | FTR | |______|__________|_____| • KEY - Key of the block (4 bytes). • PAYLOAD - Payload of the block (arbitrary size). • FTR - Footer of the block (4 bytes).Bob has decided to store a key in the beginning of each block instead of a header; Bob has a secret way of computing the size of the block’s payload from the key. The size of the KEY field is 4 bytes. Bob has also decided to store the size of a block’s payload in the footer of the block. Since there is an 8-byte alignment requirement, the least significant of the 3 unused bits is used to indicate whether the block is free (0) or allocated (1). Note that Bob is working on a 32-bit machine. You can assume the following:
Write your code for getKey( void * bp ) below.