# Changeset a953c2e3

Ignore:
Timestamp:
Jul 8, 2021, 4:09:34 PM (19 months ago)
Branches:
enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
6ff08d8
Parents:
b1a2c4a
Message:

Added allocator design objectives

File:
1 edited

Unmodified
Added
Removed
• ## doc/theses/mubeen_zulfiqar_MMath/allocator.tex

 rb1a2c4a \subsection{Design philosophy} The objective of uHeapLmmm's new design was to fulfill following requirements: \begin{itemize} \item It should be concurrent to be used in multi-threaded programs. \item It should avoid global locks, on resources shared across all threads, as much as possible. \item It's performance (FIX ME: cite performance benchmarks) should be comparable to the commonly used allocators (FIX ME: cite common allocators). \item It should be a lightweight memory allocator. \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Background and previous design of uHeapLmmm} uHeapLmmm was originally designed by X in X (FIX ME: add original author after confirming with Peter). (FIX ME: make and add figure of previous design with description) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Distributed design of uHeapLmmm} uHeapLmmm's design was reviewed and changed to fulfill new requirements (FIX ME: cite allocator philosophy). For this purpose, following two designs of uHeapLmm were proposed: \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 assign/un-assign a heap to the KT. \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. All KTs will be contended for one lock on sbrk for their initial allocations (before free-lists gets populated). Out of the two designs, Design 1 was chosen because it's concurrency is better across all bucket-sizes as design-2 shards a few buckets of selected sizes while design-1 shards all the buckets. Design-2 shards the whole heap which has all the buckets with the addition of sharding sbrk area. \subsection{Advantages of distributed design} The distributed design of uHeapLmmm is concurrent to work in multi-threaded applications. Some key benefits of the distributed design of uHeapLmmm are as follows: \begin{itemize} \item The bump allocation is concurrent as memory taken from sbrk is sharded across all heaps as bump allocation reserve. The lock on bump allocation (on memory taken from sbrk) will only be contended if KTs > N. The contention on sbrk area is less likely as it will only happen in the case if heaps assigned to two KTs get short of bump allocation reserve simultanously. \item N heaps are created at the start of the program and destroyed at the end of program. When a KT is created, we only assign it to one of the heaps. When a KT is destroyed, we only dissociate it from the assigned heap but we do not destroy that heap. That heap will go back to our pool-of-heaps, ready to be used by some new KT. And if that heap was shared among multiple KTs (like the case of KTs > N) then, on deletion of one KT, that heap will be still in-use of the other KTs. This will prevent creation and deletion of heaps during run-time as heaps are re-usable which helps in keeping low-memory footprint. \item It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty. \item Distributed design avoids unnecassry locks on resources shared across all KTs. \end{itemize} FIX ME: Cite performance comparison of the two heap designs if required %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Why did we need it? The added benefits. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Following is added by Peter \noindent ==================== \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.
Note: See TracChangeset for help on using the changeset viewer.