source: doc/theses/mubeen_zulfiqar_MMath/allocator.tex @ dbfae7b

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-expr
Last change on this file since dbfae7b was dbfae7b, checked in by Peter A. Buhr <pabuhr@…>, 14 months ago

add figures for design possibilities

  • Property mode set to 100644
File size: 1.5 KB
Line 
1
2\chapter{Allocator}
3
4\newpage
5\paragraph{Design 1: Decentralized}
6Fixed number of heaps: shard the heap into N heaps each with a bump-area allocated from the sbrk area.
7Kernel threads (KT) are assigned to the N heaps.
8When KTs $\le$ N, the heaps are uncontented.
9When KTs $>$ N, the heaps are contented.
10By adjusting N, this approach reduces storage at the cost of speed due to contention.
11In all cases, a thread acquires/releases a lock, contented or uncontented.
12\begin{cquote}
13\centering
14\input{AllocDS1}
15\end{cquote}
16Problems: need to know when a KT is created and destroyed to know when to create/delete the KT's heap.
17On KT deletion, its heap freed-storage needs to be distributed somewhere.
18
19\paragraph{Design 2: Centralized}
20
21One heap, but lower bucket sizes are N-shared across KTs.
22This design leverages the fact that 95\% of allocation requests are less than 512 bytes and there are only 3--5 different request sizes.
23When KTs $\le$ N, the important bucket sizes are uncontented.
24When KTs $>$ N, the free buckets are contented.
25Therefore, threads are only contending for a small number of buckets, which are distributed among them to reduce contention.
26\begin{cquote}
27\centering
28\input{AllocDS2}
29\end{cquote}
30Problems: need to know when a kernel thread (KT) is created and destroyed to know when to assign a shared bucket-number.
31When no thread is assigned a bucket number, its free storage is unavailable.
32It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.
Note: See TracBrowser for help on using the repository browser.