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

Carnegie Mellon
Method 1: Implicit List
 For each block we need both size and allocation status
 Could store this information in two words: wasteful!
 Standard trick
 If blocks are aligned, some low-order address bits are always 0
 Instead of storing an always-0 bit, use it as a allocated/free flag  When reading size word, must mask out this bit
1 word
Size
a
Payload
Optional padding
Format of allocated and free blocks
a = 1: Allocated block a = 0: Free block
Size: block size
Payload: application data (allocated blocks only)
1

Carnegie Mellon
Header Example
 Size = 16, allocation status = 1
 16 = 00010000
size
0
0
0
1
0
0
0
1
 Need to “zero out” the LSB to get the size  -2 = 11111110
 Least significant bit is 0
 Bitwise AND with -2 sets LSB to 0
allocation
2

Carnegie Mellon
Start of
Detailed Implicit Free List Example
Unused
heap
8/0
16/1
32/0
16/1
Double-word aligned
Allocated blocks: shaded
Free blocks: unshaded
Headers: labeled with size in bytes/allocated bit
3