Changeset 70df5f3


Ignore:
Timestamp:
Jul 26, 2021, 11:08:22 PM (11 months ago)
Author:
m3zulfiq <m3zulfiq@…>
Branches:
enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr
Children:
04141f8
Parents:
866cad3
Message:

Added intro chapter

File:
1 edited

Legend:

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

    r866cad3 r70df5f3  
    2424\noindent
    2525====================
     26
     27\section{Introduction}
     28Dynamic memory allocation and management is one of the core features of C. It gives programmer the freedom to allocate, free, use, and manage dynamic memory himself. The programmer is not given the complete control of the dynamic memory management instead an interface of memory allocator is given to the progrmmer that can be used to allocate/free dynamic memory for the application's use.
     29
     30Memory allocator is a layer between thr programmer and the system. Allocator gets dynamic memory from the system in heap/mmap area of application storage and manages it for programmer's use.
     31
     32GNU C Library (FIX ME: cite this) provides an interchangeable memory allocator that can be replaced with a custom memory allocator that supports required features and fulfills application's custom needs. It also allows others to innovate in memory allocation and design their own memory allocator. GNU C Library has set guidelines that should be followed when designing a standalone memory allocator. GNU C Library requires new memory allocators to have atlease following set of functions in their allocator's interface:
     33
     34\begin{itemize}
     35\item
     36malloc: it allocates and returns a chunk of dynamic memory of requested size (FIX ME: cite man page).
     37\item
     38calloc: it allocates and returns an array in dynamic memory of requested size (FIX ME: cite man page).
     39\item
     40realloc: it reallocates and returns an already allocated chunk of dynamic memory to a new size (FIX ME: cite man page).
     41\item
     42free: it frees an already allocated piece of dynamic memory (FIX ME: cite man page).
     43\end{itemize}
     44
     45In addition to the above functions, GNU C Library also provides some more functions to increase the usability of the dynamic memory allocator. Most standalone allocators also provide all or some of the above additional functions.
     46
     47\begin{itemize}
     48\item
     49aligned_alloc
     50\item
     51malloc_usable_size
     52\item
     53memalign
     54\item
     55posix_memalign
     56\item
     57pvalloc
     58\item
     59valloc
     60\end{itemize}
     61
     62With the rise of concurrent applications, memory allocators should be able to fulfill dynamic memory requests from multiple threads in parallel without causing contention on shared resources. There needs to be a set of a standard benchmarks that can be used to evaluate an allocator's performance in different scenerios.
     63
     64\section{Background}
     65
     66\subsection{Memory Allocation}
     67With dynamic allocation being an important feature of C, there are many standalone memory allocators that have been designed for different purposes. For this thesis, we chose 7 of the most popular and widely used memory allocators.
     68
     69\paragraph{dlmalloc}
     70dlmalloc (FIX ME: cite allocator) is a thread-safe allocator that is single threaded and single heap. dlmalloc maintains free-lists of different sizes to store freed dynamic memory. (FIX ME: cite wasik)
     71
     72\paragraph{hoard}
     73Hoard (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and using a heap layer framework. It has per-thred heaps that have thread-local free-lists, and a gloabl shared heap. (FIX ME: cite wasik)
     74
     75\paragraph{jemalloc}
     76jemalloc (FIX ME: cite allocator) is a thread-safe allocator that uses multiple arenas. Each thread is assigned an arena. Each arena has chunks that contain contagious memory regions of same size. An arena has multiple chunks that contain regions of multiple sizes.
     77
     78\paragraph{ptmalloc}
     79ptmalloc (FIX ME: cite allocator) is a modification of dlmalloc. It is a thread-safe multi-threaded memory allocator that uses multiple heaps. ptmalloc heap has similar design to dlmalloc's heap.
     80
     81\paragraph{rpmalloc}
     82rpmalloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses per-thread heap. Each heap has multiple size-classes and each size-calss contains memory regions of the relevant size.
     83
     84\paragraph{tbb malloc}
     85tbb malloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses private heap for each thread. Each private-heap has multiple bins of different sizes. Each bin contains free regions of the same size.
     86
     87\paragraph{tc malloc}
     88tcmalloc (FIX ME: cite allocator) is a thread-safe allocator. It uses per-thread cache to store free objects that prevents contention on shared resources in multi-threaded application. A central free-list is used to refill per-thread cache when it gets empty.
     89
     90\subsection{Benchmarks}
     91There are multiple benchmarks that are built individually and evaluate different aspects of a memory allocator. But, there is not standard set of benchamrks that can be used to evaluate multiple aspects of memory allocators.
     92
     93\paragraph{threadtest}
     94(FIX ME: cite benchmark and hoard) Each thread repeatedly allocates and then deallocates 100,000 objects. Runtime of the benchmark evaluates its efficiency.
     95
     96\paragraph{shbench}
     97(FIX ME: cite benchmark and hoard) Each thread allocates and randomly frees a number of random-sized objects. It is a stress test that also uses runtime to determine efficiency of the allocator.
     98
     99\paragraph{larson}
     100(FIX ME: cite benchmark and hoard) Larson simulates a server environment. Multiple threads are created where each thread allocator and free a number of objects within a size range. Some objects are passed from threads to the child threads to free. It caluculates memory operations per second as an indicator of memory allocator's performance.
     101
     102\section{Research Objectives}
     103Our research objective in this thesis is to:
     104
     105\begin{itemize}
     106\item
     107Design a lightweight concurrent memory allocator with added features and usability that are currently not present in the other memory allocators.
     108\item
     109Design a suite of benchmarks to evalute multiple aspects of a memory allocator.
     110\end{itemize}
     111
     112\section{An outline of the thesis}
     113LAST FIX ME: add outline at the end
Note: See TracChangeset for help on using the changeset viewer.