Changeset dbfae7b for doc


Ignore:
Timestamp:
Mar 30, 2021, 8:40:23 AM (4 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
arm-eh, jacob/cs343-translation, master
Children:
a41e87b
Parents:
d0e80f61
Message:

add figures for design possibilities

Location:
doc/theses/mubeen_zulfiqar_MMath
Files:
2 added
1 edited

Legend:

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

    rd0e80f61 rdbfae7b  
     1
    12\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 TracChangeset for help on using the changeset viewer.