source: doc/theses/mubeen_zulfiqar_MMath/allocator.tex @ 6a8208cb

Last change on this file since 6a8208cb was dbfae7b, checked in by Peter A. Buhr <pabuhr@…>, 15 months ago

add figures for design possibilities

  • Property mode set to 100644
File size: 1.5 KB
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.
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.
19\paragraph{Design 2: Centralized}
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.
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.