Operating Systems – CSCI 402
Implementing First Fit: Data Structures
size
link
size
link
size
link
size
link
struct fblock
struct fblock
Free list: a linked list of free blocks sorted according to block addresses
no need to manage allocated blocks use a doubly-linked list
struct fblock
insertion and deletion are fast, i.e., O(1), once you know
where to insert or delete
321 0
struct fblock
1
Copyright ý . of Storage
free(A)
Operating Systems – CSCI 402
(free)
A
(free)
(free)
This is known as coalescing
in order to make coalescing possible, you need to know that size of the blocks above and below the block being freed
you also need to know if they are allocated or free Copyright ý . Cheng
321 0
2
Operating Systems – CSCI 402
Boundary Tags
size
size
size
blink
flink
size
Allocated Block Free Block
This is known as coalescing
in order to make coalescing possible, you need to know that size of the blocks above and below the block being freed
you also need to know if they are allocated or free Copyright ý . Cheng
321 0
3
Operating Systems – CSCI 402
Free block
start
start+8
start+16
start+size-8
In-use block
start
start+8
start+size-8
Detailed Examples
Free list
Free List
in-use = 0
size
prev = 0
next = 0
(Garbage, don¡¯t care)
in-use = 0
size
head
tail
size
in-use = 0
size
prev = 0
next = 0
(Garbage, don¡¯t care)
in-use = 0
size
in-use = 1
size
Return to User! Hands off!
in-use = 1
size
size
4
321 0
Copyright ý . : Heap starts at 0xfedcba98 and size of the heap is 0x0000eca8 (60,584) bytes
the Free List contains one free block and it looks like this:
Free List
Operating Systems – CSCI 402
malloc() Example
head
tail
in-use = 0
0x0000eca8
prev = 0
next = 0
(Garbage, don¡¯t care)
in-use = 0
0x0000eca8
0xfedcba98
0xfedcbaa0
0xfedcbaa8
0xfedda738
5
321 0
Copyright ý . : Heap starts at 0xfedcba98 and size of the heap is 0x0000eca8 (60,584) bytes
the Free List contains one free block and it looks like this:
Free List
Operating Systems – CSCI 402
malloc() Example
head
tail
in-use = 0
0x0000eca8
prev = 0
next = 0
(Garbage, don¡¯t care)
in-use = 0
0x0000eca8
Ex: Request block size is 100
split the block into two
busy block size is 116
remaining free block size is 60584-116 =60468=0xec34
0xfedcba98
0xfedcbaa0
0xfedcbaa8
0xfedda738
6
321 0
Copyright ý . Systems – CSCI 402
Ex: Heap starts at 0xfedcba98 and size of the heap is 0x0000eca8 (60,584) bytes
the Free List contains one free block and it looks like this:
Free List
malloc() Example
head
tail
in-use = 1
0x00000074
Return to user! Hands off!
in-use = 1
0x00000074
in-use = 0
0x0000ec34
prev = 0
next = 0
(Garbage, don¡¯t care)
in-use = 0
0x0000ec34
0xfedcba98
return 0xfedcbaa0
Ex: Request block size is 100
…
0xfedcbb04
0xfedcbb0c
0xfedcbb14
0xfedcbb1c
…
0xfedda738
split the block into two
busy block size is 116
remaining free block size is 60584-116 =60468=0xec34
7
321 0
Copyright ý . Cheng
free() Example
After K blocks of memory have been allocated (and assume that none of them have been deallocated)
in the memory layout, the first K blocks are used block, followed by one free block
K Used Blocks
Free List
Operating Systems – CSCI 402
head
tail
UB1
UB2
…
UBK
FB1
8
321 0
Copyright ý . Systems – CSCI 402
free() Example
After K blocks of memory have been allocated (and assume that none of them have been deallocated)
in the memory layout, the first K blocks are used block, followed by one free block
Free List
head
tail
UB1
UB2
…
UBK
FB1
Memory blocks can be freed in any order
K Used Blocks
when a memory block is freed, we need to
check if the blocks before it and after it are also free
If neither of them are free, we just need to insert the newly freed block into the Free List (at the right place)
need to search the Free List to find insertion point searching through a linear list is “slow”, O(n)
Otherwise, we can merge/coalesce the block in question with neighboring free block(s)
9
321 0
Copyright ý . : free(Y)
Y-16 tells you if
the previous block is free or not Y-8+Z tells you if the next block is free or not
where Z is what¡¯s in Y-4
Coalescing:
need to make sure that everything is consistent
Y-16 Y-8 Y
Y-8+Z
free() Example Y-8-(*(Y-12))
Operating Systems – CSCI 402
in-use=?
size
?
in-use=?
size
in-use=1
size=Z
Return to user! Hands off!
in-use=1
size=Z
in-use=?
size
?
in-use=?
size
10
321 0
Copyright ý . : free(Y) and previous block is free and next block is busy
i.e., Y-16 is 0 and Y-8+Z is 1 where Z is what¡¯s in Y-4 and W is what¡¯s in Y-12
furthermore, Y-8-W is on the Free List
coalesce this block and the previous block
Y-8-W
Y-16 Y-8 Y
Y-16+Z Y-8+Z
free() Example
Operating Systems – CSCI 402
in-use=0
size=W
prev
next
(Garbage, don¡¯t care)
in-use=0
size=W
in-use=1
size=Z
Return to user! Hands off!
in-use=1
size=Z
in-use=1
size
Hands off!
in-use=1
size
11
321 0
Copyright ý . : free(Y) and previous block is free and next block is busy
i.e., Y-16 is 0 and Y-8+Z is 1 where Z is what¡¯s in Y-4 and W is what¡¯s in Y-12
furthermore, Y-8-W is on the Free List
coalesce this block and the previous block
easy!
just change Y-12+Z and Y-4-W to W+Z and Y-16+Z to 0 don¡¯t even need to change prev and next!
Y-8-W
free() Example
Y
Y-16+Z
Y-8+Z
Operating Systems – CSCI 402
in-use=0
size=W+Z
prev
next
(Garbage, don¡¯t care)
in-use=0
size=W+Z
in-use=1
size
Hands off!
in-use=1
size
12
321 0
Copyright ý . : free(Y) and previous block is busy and next block is free
i.e., Y-16 is 1 and Y-8+Z is 0 where Z is what¡¯s in Y-4 and X is what¡¯s in Y-4+Z
furthermore, Y-8+Z is on the Free List
coalesce this block and the next block
Y-8-W
Y-16 Y-8 Y
Y-8+Z
Y-16+Z+X
free() Example
Operating Systems – CSCI 402
in-use=1
size=W
Hands off!
in-use=1
size=W
in-use=1
size=Z
Return to user! Hands off!
in-use=1
size=Z
in-use=0
size=X
prev
next
(Garbage, don¡¯t care)
in-use=0
size=X
13
321 0
Copyright ý . : free(Y) and previous block is busy and next block is free
i.e., Y-16 is 1 and Y-8+Z is 0 where Z is what¡¯s in Y-4 and X is what¡¯s in Y-4+Z
furthermore, Y-8+Z is on the Free List
coalesce this block and the next block
just change Y-4 and Y-12+Z+X toZ+XandY-8to0
move prev and next
pointers
Y-8-W
Y-16 Y-8 Y
free() Example
Operating Systems – CSCI 402
in-use=1
size=W
Hands off!
in-use=1
size=W
in-use=0
size=Z+X
prev
next
(Garbage, don¡¯t care)
in-use=0
size=Z+X
adjust next field in previoius block in Free List adjust prev field in next block in Free List
may need to update where Free List points
Y-16+Z+X
14
321 0
Copyright ý . : free(Y) and previous block is free and next block is also free
i.e., Y-16 is 0 and Y-8+Z is 0 where Z is what¡¯s in Y-4, X is what¡¯s in Y-4+Z, and W is what¡¯s in Y-12
blocks starting at Y-8-W and Y-8+Z are both on the Free List and next to and point at each other coalesce all 3 blocks
Y-8-W
Y-W
Y-16 Y-8 Y
Y-8+Z
Y+Z
free() Example
Operating Systems – CSCI 402
in-use=0
size=W
prev
Y-8+Z
(Garbage, don¡¯t care)
in-use=0
size=W
in-use=1
size=Z
Return to user! Hands off!
in-use=1
size=Z
in-use=0
size=X
Y-8-W
next
(Garbage, don¡¯t care)
in-use=0
size=X
15
321 0
Copyright ý . Cheng
free() Example
Ex: free(Y) and previous block is free and next block is also free
i.e., Y-16 is 0 and Y-8+Z is 0 where Z is what¡¯s in Y-4, X is what¡¯s in Y-4+Z, and W is what¡¯s in Y-12
blocks starting at Y-8-W and Y-8+Z are both on the Free List and next to and point at each other coalesce all 3 blocks
just change Y-4-W and
Y-12+Z+X to W+Z+X
copy next from Y+Z+4 to Y-W+4
adjust prev field in the new next block in Free List to point to Y-8-W
may need to update where Free List points
Y-8-W Y-W
Y-16 Y-8 Y
Y-16+Z+X
Operating Systems – CSCI 402
in-use=0
size=W+Z+X
prev
next
(Garbage, don¡¯t care)
in-use=0
size=W+Z+X
16
321 0
Copyright ý . Systems – CSCI 402
First-fit & Best-fit Algorithms
Memory allocator must run fast
it does not check if the free list is in a consistent state
just like our warmup 1 assignment
One bad bit in any memory allocator data structure can break the memory allocator code
if you write into a boundary tag, your program may die later in malloc() or free()
what would happen if you call free()twice on the same address?
user/application code can corrupt the memory allocation chain easily
the result can lead to segmentation faults
unfortunately, the corruption can stay hidden for a long time and eventually lead to a segmentation fault
memory corruption bugs are very difficult to debug
17
321 0
Copyright ý . Systems – CSCI 402
First-fit Algorithm
Let n be the number of free blocks on the free list in the worst case, malloc() is O(n)
in the worst case, free(ptr) is O(n)
occurs when the blocks around the block containing ptr are both in-use
Such performance in unacceptable in the kernel
it is desirable that the kernel¡¯s worst-case performance has a bound
18
321 0
Copyright ý . Systems – CSCI 402
3.3 Dynamic Storage Allocation
Best-fit & First-fit Algorithms
Buddy System
Slab Allocation
19
321 0
Copyright ý . : malloc(4000)
4K
4K 8K
Buddy Lists
Operating Systems – CSCI 402
8K
blocks get evenly divided into two blocks that are buddies with each other
can only merge with your buddy if your buddy is also free
internal fragmentation
Ex: malloc(4000)
return a 4K block
321 0
Copyright ý . Cheng
32K
16K
16K
20
Operating Systems – CSCI 402
Buddy Systems
Faster memory allocation system (at the cost of more fragmentation, internal fragmentation)
restrict block size to be a power of 2
1) all blocks of size 2 k start at location x where x mod 2 k=0 2) given a block starting at location x such that x mod 2 k=0
BUDDYk(x) =x+2 k if x mod 2 k+1=0 BUDDYk(x) =x-2 k if x mod 2 k+1=2 k Ex: BUDDY2(1010100) =1010000
3) only buddies can be merged
4) try to coalesce buddies when storage is deallocated
k different available block lists, one for each block size
When request a block of size 2 k and none is available:
1) split smallest block 2 j > 2 k into a pair of blocks of size 2 j-1 2) place block on appropriate free list and try again
321 0
21
Copyright ý . Systems – CSCI 402
Buddy Systems
Data Structure
1) doubly-linked list (not circular) FREE list indexed by k
links stored in actual blocks
FREE[k] points to first available block of size 2 k 2) each block contains
in-use bit
size
NEXT and PREV links for FREE list
lots of details
read weenix source code for its “page allocator”
Can get greater variety in block sizes using Fibonacci sequence of block sizes so bj = bj-1+bj-2
ratio of successive block sizes is 2/3 instead of 1/2
22
321 0
Copyright ý . -level Example of Buddy Algorithm
Ex: 16 “pages” (minimum allocation is 1 page) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
k free[k] 0
1
2
3 4
k free[k] 0
1
2
3 4
k free[k] 0
1
2
Operating Systems – CSCI 402
¦¸
¦¸
¦¸
¦¸
0
¦¸
¦¸2
¦¸4
¦¸8
0¦¸
1) allocate a block of size 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2) allocate a block of size 4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
¦¸
¦¸2
¦¸4¦¸
¦¸8
0¦¸
Copyright ý . Cheng
3 4
23
321 0
High-level Example of Buddy Algorithm
Ex: 16 “pages” (minimum allocation is 1 page)
3) allocate a block of size 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4) allocate a block of size 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
k free[k] 0
1
2
3 4
k free[k] 0
1
2
Operating Systems – CSCI 402
¦¸
¦¸ 2 ¦¸
¦¸ 4 ¦¸
¦¸ 8
0 ¦¸
¦¸
¦¸ 2 10
¦¸ 4 12
¦¸8¦¸
0¦¸
3 4
24
321 0
Copyright ý . Systems – CSCI 402
3.3 Dynamic Storage Allocation
Best-fit & First-fit Algorithms Buddy System
Slab Allocation
25
321 0
Copyright ý . Systems – CSCI 402
Slab Allocation
Objects are allocated and freed frequently
allocation involves
finding an appropriate-sized storage initialize it
pointers need to point at the right places
may even need to initialize synchronization data structures
deallocation involves
tearing down the data structures
freeing the storage
lots of “overhead”
Difficulties with dynamic storage allocation
you cannot predict what an application will ask for but it¡¯s not true for the kernel
e.g., can allocate a slab of process control blocks at a time
return one of them from a slab
321 0
26
Copyright ý . Allocation
Operating Systems – CSCI 402
see weenix kernel code! Copyright ý . Cheng
321 0
27
Slab Allocation
Slab Allocation
sets up a separate cache for each type of object to be managed contiguous sets of pages called slabs, allocated to hold objects
we will cover “pages” later, won¡¯t get into too much detail now
Whenever a slab is allocated, a constructor is called to initialize all the objects it hold
this is where you pay for initialization, but it¡¯s done in a batch
As objects are being allocated, they are taken from the set of existing slabs in the cache
objects are considered “preallocated” since they have all been initialized already
As objects are being freed, they are simply marked as free don¡¯t have to free up storage
when appropriate can free up an entire slab
Operating Systems – CSCI 402
28
321 0
Copyright ý . Cheng