# source:doc/theses/mubeen_zulfiqar_MMath/uw-ethesis-frontpgs.tex@fb6691a

Last change on this file since fb6691a was fb6691a, checked in by Peter A. Buhr <pabuhr@…>, 3 months ago

final proofread of Mubeen's MMath thesis

• Property mode set to 100644
File size: 8.4 KB
Line
1% T I T L E   P A G E
2% -------------------
3% Last updated October 23, 2020, by Stephen Carr, IST-Client Services
4% The title page is counted as page i' but we need to suppress the
5% page number. Also, we don't want any headers or footers.
6\pagestyle{empty}
7\pagenumbering{roman}
8
9% The contents of the title page are specified in the "titlepage"
10% environment.
11\begin{titlepage}
12        \begin{center}
13        \vspace*{1.0cm}
14
15        {\Huge\bf High-Performance Concurrent Memory Allocation}
16
17        \vspace*{1.0cm}
18
19        by \\
20
21        \vspace*{1.0cm}
22
23        {\Large Mubeen Zulfiqar} \\
24
25        \vspace*{3.0cm}
26
27        A thesis \\
28        presented to the University of Waterloo \\
29        in fulfillment of the \\
30        thesis requirement for the degree of \\
31        Master of Mathematics \\
32        in \\
33        Computer Science \\
34
35        \vspace*{2.0cm}
36
37        Waterloo, Ontario, Canada, \the\year \\
38
39        \vspace*{1.0cm}
40
41        \copyright{} Mubeen Zulfiqar \the\year \\
42        \end{center}
43\end{titlepage}
44
45% The rest of the front pages should contain no headers and be numbered using
46% Roman numerals starting with ii'.
47\pagestyle{plain}
48\setcounter{page}{2}
49
50\cleardoublepage % Ends the current page and causes all figures and tables
51% that have so far appeared in the input to be printed. In a two-sided
52% printing style, it also makes the next page a right-hand (odd-numbered)
53% page, producing a blank page if necessary.
54
55\begin{comment}
56% E X A M I N I N G   C O M M I T T E E (Required for Ph.D. theses only)
57% Remove or comment out the lines below to remove this page
58\begin{center}\textbf{Examining Committee Membership}\end{center}
59  \noindent
60The following served on the Examining Committee for this thesis.
61The decision of the Examining Committee is by majority vote.
62  \bigskip
63
64  \noindent
65\begin{tabbing}
66Internal-External Member: \=  \kill % using longest text to define tab length
67External Examiner: \>  Bruce Bruce \\
68\> Professor, Dept. of Philosophy of Zoology, University of Wallamaloo \\
69\end{tabbing}
70  \bigskip
71
72  \noindent
73\begin{tabbing}
74Internal-External Member: \=  \kill % using longest text to define tab length
75Supervisor(s): \> Ann Elk \\
76\> Professor, Dept. of Zoology, University of Waterloo \\
77\> Andrea Anaconda \\
78\> Professor Emeritus, Dept. of Zoology, University of Waterloo \\
79\end{tabbing}
80  \bigskip
81
82  \noindent
83  \begin{tabbing}
84Internal-External Member: \=  \kill % using longest text to define tab length
85Internal Member: \> Pamela Python \\
86\> Professor, Dept. of Zoology, University of Waterloo \\
87\end{tabbing}
88  \bigskip
89
90  \noindent
91\begin{tabbing}
92Internal-External Member: \=  \kill % using longest text to define tab length
93Internal-External Member: \> Meta Meta \\
94\> Professor, Dept. of Philosophy, University of Waterloo \\
95\end{tabbing}
96  \bigskip
97
98  \noindent
99\begin{tabbing}
100Internal-External Member: \=  \kill % using longest text to define tab length
101Other Member(s): \> Leeping Fang \\
102\> Professor, Dept. of Fine Art, University of Waterloo \\
103\end{tabbing}
104
105\cleardoublepage
106\end{comment}
107
108% D E C L A R A T I O N   P A G E
109% -------------------------------
110  % The following is a sample Declaration Page as provided by the GSO
111  % December 13th, 2006.  It is designed for an electronic thesis.
112 \begin{center}\textbf{Author's Declaration}\end{center}
113
114 \noindent
115I hereby declare that I am the sole author of this thesis. This is a true copy
116of the thesis, including any required final revisions, as accepted by my
117examiners.
118
119  \bigskip
120
121  \noindent
122I understand that my thesis may be made electronically available to the public.
123
124\cleardoublepage
125
126% A B S T R A C T
127% ---------------
128
129\begin{center}\textbf{Abstract}\end{center}
130
131Memory management takes a sequence of program generated allocation/deallocation requests and attempts to satisfy them within a fixed-sized block of memory while minimizing the total amount of memory used.
132A general-purpose dynamic-allocation algorithm cannot anticipate future allocation requests so its output is rarely optimal.
133However, memory allocators do take advantage of regularities in allocation patterns for typical programs to produce excellent results, both in time and space (similar to LRU paging).
134In general, allocators use a number of similar techniques, each optimizing specific allocation patterns.
135Nevertheless, memory allocators are a series of compromises, occasionally with some static or dynamic tuning parameters to optimize specific program-request patterns.
136
137The goal of this thesis is to build a low-latency memory allocator for both kernel and user multi-threaded systems, which is competitive with the best current memory allocators, while extending the feature set of existing and new allocator routines.
138A new llheap memory-allocator is created that achieves all of these goals, while maintaining and managing sticky allocation properties for zero-filled and aligned allocations without a performance loss.
139Hence, it becomes possible to use @realloc@ frequently as a safe operation, rather than just occasionally, because it preserves sticky properties when enlarging storage requests.
140Furthermore, the ability to query sticky properties and information allows programmers to write safer programs, as it is possible to dynamically match allocation styles from unknown library routines that return allocations.
141The C allocation API is also extended with @resize@, advanced @realloc@, @aalloc@, @amemalign@, and @cmemalign@ so programmers do not make mistakes writing theses useful allocation operations.
142llheap is embedded into the \uC and \CFA runtime systems, both of which have user-level threading.
143The ability to use \CFA's advanced type-system (and possibly \CC's too) to combine advanced memory operations into one allocation routine using named arguments shows how far the allocation API can be pushed, which increases safety and greatly simplifies programmer's use of dynamic allocation.
144
145The llheap allocator also provides comprehensive statistics for all allocation operations, which are invaluable in understanding and debugging a program's dynamic behaviour.
146No other memory allocator examined in the thesis provides such comprehensive statistics gathering.
147As well, llheap provides a debugging mode where allocations are checked with internal pre/post conditions and invariants. It is extremely useful, especially for students.
148While not as powerful as the @valgrind@ interpreter, a large number of allocations mistakes are detected.
149Finally, contention-free statistics gathering and debugging have a low enough cost to be used in production code.
150
151A micro-benchmark test-suite is started for comparing allocators, rather than relying on a suite of arbitrary programs. It has been an interesting challenge.
152These micro-benchmarks have adjustment knobs to simulate allocation patterns hard-coded into arbitrary test programs.
153Existing memory allocators, glibc, dlmalloc, hoard, jemalloc, ptmalloc3, rpmalloc, tbmalloc, and the new allocator llheap are all compared using the new micro-benchmark test-suite.
154\cleardoublepage
155
156% A C K N O W L E D G E M E N T S
157% -------------------------------
158
159\begin{center}
160\textbf{Acknowledgements}
161
162I would like to thank all the people who made this thesis possible.
163
164I would like to acknowledge Peter A. Buhr for his assistance and support throughout the process.
165It would have been impossible without him.
166
167I would like to acknowledge Gregor Richards and Trevor Brown for reading my thesis quickly and giving me great feedback on my work.
168
169Also, I would say thanks to my team members at PLG especially Thierry, Michael, and Andrew for their input.
170\end{center}
171\cleardoublepage
172
173\begin{comment}
174% D E D I C A T I O N
175% -------------------
176
177\begin{center}\textbf{Dedication}\end{center}
178
179This is dedicated to the one I love.
180\cleardoublepage
181\end{comment}
182
183% T A B L E   O F   C O N T E N T S
184% ---------------------------------
186\tableofcontents
187\cleardoublepage
188\phantomsection    % allows hyperref to link to the correct page
189
190% L I S T   O F   F I G U R E S
191% -----------------------------
193\listoffigures
194\cleardoublepage
195\phantomsection         % allows hyperref to link to the correct page
196
197% L I S T   O F   T A B L E S
198% ---------------------------