# source:doc/theses/mubeen_zulfiqar_MMath/allocator.tex@2b910f9

Last change on this file since 2b910f9 was 2b910f9, checked in by m3zulfiq <m3zulfiq@…>, 22 months ago

started chapter allocator

• Property mode set to 100644
File size: 3.9 KB
Line
1\chapter{Allocator}
2
3\noindent
4====================
5
6Writing Points:
7\begin{itemize}
8\item
9Objective of uHeapLmmm.
10\item
11Design philosophy.
12\item
13Background and previous design of uHeapLmmm.
14\item
15Distributed design of uHeapLmmm.
16
17----- SHOULD WE GIVE IMPLEMENTATION DETAILS HERE? -----
18
19\PAB{Maybe. There might be an Implementation chapter.}
20\item
21figure.
22\item
24\end{itemize}
25
26The new features added to uHeapLmmm (incl. @malloc_size@ routine)
27\CFA alloc interface with examples.
28\begin{itemize}
29\item
30Why did we need it?
31\item
33\end{itemize}
34
35
36%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
37%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
38%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% uHeapLmmm Design
39%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
40%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
41
42\section{Objective of uHeapLmmm}
43UHeapLmmm is a lightweight memory allocator. The objective behind uHeapLmmm is to design a minimal concurrent memory allocator that has new features and also fulfills GNU C Library requirements (FIX ME: cite requirements).
44
45\subsection{Design philosophy}
46
47
48%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
49
50\section{Background and previous design of uHeapLmmm}
51
52
53%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54
55\section{Distributed design of uHeapLmmm}
56
57
59
60
61%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
62
64
65
66\subsection{Methods}
67Why did we need it?
69
70
71\subsection{Alloc Interface}
72Why did we need it?
74
75
76%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
77% Following is added by Peter
78
79\noindent
80====================
81
82\newpage
83\paragraph{Design 1: Decentralized}
84Fixed number of heaps: shard the heap into N heaps each with a bump-area allocated from the @sbrk@ area.
85Kernel threads (KT) are assigned to the N heaps.
86When KTs $\le$ N, the heaps are uncontented.
87When KTs $>$ N, the heaps are contented.
88By adjusting N, this approach reduces storage at the cost of speed due to contention.
89In all cases, a thread acquires/releases a lock, contented or uncontented.
90\begin{cquote}
91\centering
92\input{AllocDS1}
93\end{cquote}
94Problems: need to know when a KT is created and destroyed to know when to create/delete the KT's heap.
95On KT deletion, its heap freed-storage needs to be distributed somewhere.
96
97\paragraph{Design 2: Centralized}
98
99One heap, but lower bucket sizes are N-shared across KTs.
100This design leverages the fact that 95\% of allocation requests are less than 512 bytes and there are only 3--5 different request sizes.
101When KTs $\le$ N, the important bucket sizes are uncontented.
102When KTs $>$ N, the free buckets are contented.
103Therefore, threads are only contending for a small number of buckets, which are distributed among them to reduce contention.
104\begin{cquote}
105\centering
106\input{AllocDS2}
107\end{cquote}
108Problems: need to know when a kernel thread (KT) is created and destroyed to know when to assign a shared bucket-number.
109When no thread is assigned a bucket number, its free storage is unavailable.
110It 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.