[SOLVED] CS代考计算机代写 Carnegie Mellon

Carnegie Mellon
Implicit List: Freeing a Block  Simplest implementation:
 Need only clear the “allocated” flag
void free_block(ptr p) { *p = *p & -2 }
 But can lead to “false fragmentation”
4
4
4
2
2
free(p)
malloc(5)
p
4
4
4
2
2
Oops!
There is enough free space, but the allocator won’t be able to find it
1

Carnegie Mellon
Implicit List: Coalescing
 Join (coalesce) with next/previous blocks, if they are free
 Coalescing with next block
4
4
4
2
2
free(p)
p
logically gone
4
4
6
2
2
void free_block(ptr p) {
*p = *p & -2;
// clear allocated flag
// find next block
// add to this block if
//not allocated
}
*p = *p + *next;
next = p + *p;
if ((*next & 1) == 0)
 But how do we coalesce with previous block?
2

Carnegie Mellon
Implicit List: Bidirectional Coalescing
 Boundary tags [Knuth73]
 Replicate size/allocated word at “bottom” (end) of free blocks
 Allows us to traverse the “list” backwards, but requires extra space  Important and general technique!
4
4
4
4
6
6
4
4
Size
a
Payload and padding
Size
a
Header
Format of allocated and free blocks
Boundary tag (footer)
a = 1: Allocated block a = 0: Free block
Size: Total block size
Payload: Application data (allocated blocks only)
3

Carnegie Mellon
Constant Time Coalescing
Case 1 Case 2 Case 3 Case 4
Allocated
Allocated
Allocated
Free
Free
Allocated
Free
Free
Block being freed
4

Carnegie Mellon
Constant Time Coalescing (Case 1)
m1
1
m1
1
n
1
n
1
m2
1
m2
1
m1
1
m1
1
n
0
n
0
m2
1
m2
1
5

Carnegie Mellon
Constant Time Coalescing (Case 2)
m1
1
m1
1
n
1
n
1
m2
0
m2
0
m1
1
m1
1
n+m2
0
n+m2
0
6

Carnegie Mellon
Constant Time Coalescing (Case 3)
m1
0
m1
0
n
1
n
1
m2
1
m2
1
n+m1
0
n+m1
0
m2
1
m2
1
7

Carnegie Mellon
Constant Time Coalescing (Case 4)
m1
0
m1
0
n
1
n
1
m2
0
m2
0
n+m1+m2
0
n+m1+m2
0
8