Changeset dbfae7b for doc/theses/mubeen_zulfiqar_MMath

Timestamp:

Mar 30, 2021, 8:40:23 AM (4 years ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

a41e87b

Parents:

d0e80f61

Message:

add figures for design possibilities

Location:

doc/theses/mubeen_zulfiqar_MMath

Files:

• AllocDS1.fig (added)
• AllocDS2.fig (added)
• allocator.tex (modified) (1 diff)

doc/theses/mubeen_zulfiqar_MMath/allocator.tex

@@ +1 @@
+
 \chapter{Allocator}
+
+\newpage
+\paragraph{Design 1: Decentralized}
+Fixed number of heaps: shard the heap into N heaps each with a bump-area allocated from the sbrk area.
+Kernel threads (KT) are assigned to the N heaps.
+When KTs $\le$ N, the heaps are uncontented.
+When KTs $>$ N, the heaps are contented.
+By adjusting N, this approach reduces storage at the cost of speed due to contention.
+In all cases, a thread acquires/releases a lock, contented or uncontented.
+\begin{cquote}
+\centering
+\input{AllocDS1}
+\end{cquote}
+Problems: need to know when a KT is created and destroyed to know when to create/delete the KT's heap.
+On KT deletion, its heap freed-storage needs to be distributed somewhere.
+
+\paragraph{Design 2: Centralized}
+
+One heap, but lower bucket sizes are N-shared across KTs.
+This design leverages the fact that 95\% of allocation requests are less than 512 bytes and there are only 3--5 different request sizes.
+When KTs $\le$ N, the important bucket sizes are uncontented.
+When KTs $>$ N, the free buckets are contented.
+Therefore, threads are only contending for a small number of buckets, which are distributed among them to reduce contention.
+\begin{cquote}
+\centering
+\input{AllocDS2}
+\end{cquote}
+Problems: need to know when a kernel thread (KT) is created and destroyed to know when to assign a shared bucket-number.
+When no thread is assigned a bucket number, its free storage is unavailable.
+It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.