Index: doc/theses/mubeen_zulfiqar_MMath/AllocDS1.fig
===================================================================
--- doc/theses/mubeen_zulfiqar_MMath/AllocDS1.fig	(revision dbfae7bce53b3200450caaf0d2c54c5e9d1ac211)
+++ doc/theses/mubeen_zulfiqar_MMath/AllocDS1.fig	(revision dbfae7bce53b3200450caaf0d2c54c5e9d1ac211)
@@ -0,0 +1,143 @@
+#FIG 3.2  Produced by xfig version 3.2.7b
+Landscape
+Center
+Inches
+Letter
+100.00
+Single
+-2
+1200 2
+6 4950 1275 5250 1425
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 5025 1350 20 20 5025 1350 5045 1350
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 5100 1350 20 20 5100 1350 5120 1350
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 5175 1350 20 20 5175 1350 5195 1350
+-6
+6 5700 1950 6000 2100
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 5775 2025 20 20 5775 2025 5795 2025
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 5850 2025 20 20 5850 2025 5870 2025
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 5925 2025 20 20 5925 2025 5945 2025
+-6
+6 3600 2100 3900 2475
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 3675 2100 3675 2325
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 3600 2325 3900 2325 3900 2475 3600 2475 3600 2325
+-6
+6 5100 2100 5400 2475
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 5175 2100 5175 2325
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 5100 2325 5400 2325 5400 2475 5100 2475 5100 2325
+-6
+6 4350 2100 4575 2775
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 4425 2100 4425 2325
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 4350 2325 4575 2325 4575 2475 4350 2475 4350 2325
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 4350 2625 4575 2625 4575 2775 4350 2775 4350 2625
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 4425 2400 4425 2625
+-6
+6 5700 3225 6000 3375
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 5775 3300 20 20 5775 3300 5795 3300
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 5850 3300 20 20 5850 3300 5870 3300
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 5925 3300 20 20 5925 3300 5945 3300
+-6
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 2700 1950 3900 1950
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 3000 1800 3000 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 3150 1800 3150 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 3300 1800 3300 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 3450 1800 3450 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 3600 1800 3600 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 3750 1800 3750 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 4200 1950 5400 1950
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 4350 1800 4350 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 4500 1800 4500 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 4650 1800 4650 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 4800 1800 4800 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 4950 1800 4950 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5100 1800 5100 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5250 1800 5250 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 4050 1200 4050 1500
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 4350 1200 4350 1500
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 4650 1200 4650 1500
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 3750 1200 5550 1200 5550 1500 3750 1500 3750 1200
+2 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 3975 1350 3375 1800
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 3900 1350 3300 1800
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 4200 1350 4800 1800
+2 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 4125 1350 4725 1800
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 2850 1800 2850 2175
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 2700 1800 3900 1800 3900 2175 2700 2175 2700 1800
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 4200 1800 5400 1800 5400 2175 4200 2175 4200 1800
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 2775 2100 2775 2325
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 2775 2400 2775 2625
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 2700 2625 2850 2625 2850 2775 2700 2775 2700 2625
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 2700 2325 2850 2325 2850 2475 2700 2475 2700 2325
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 3
+	1 1 1.00 45.00 90.00
+	 2700 3375 3450 3375 3450 3150
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 2700 3150 3900 3150 3900 3525 2700 3525 2700 3150
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 3
+	1 1 1.00 45.00 90.00
+	 4200 3375 4950 3375 4950 3150
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 4200 3150 5400 3150 5400 3525 4200 3525 4200 3150
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 3
+	1 1 1.00 45.00 90.00
+	 3900 4350 4950 4350 4950 3900
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 3900 3900 5400 3900 5400 4575 3900 4575 3900 3900
+4 2 0 50 -1 0 12 0.0000 2 135 975 2625 2175 free buckets\001
+4 2 0 50 -1 0 12 0.0000 2 135 435 2625 1950 locks\001
+4 1 0 50 -1 0 12 0.0000 2 135 1365 4650 1125 N thread buckets\001
+4 1 0 50 -1 0 12 0.0000 2 180 390 5175 1725 heap\001
+4 1 0 50 -1 0 12 0.0000 2 180 390 2925 1725 heap\001
+4 1 0 50 -1 0 12 0.0000 2 180 915 3300 3075 bump alloc\001
+4 0 0 50 -1 0 12 0.0000 2 135 360 4275 3325 lock\001
+4 1 0 50 -1 0 12 0.0000 2 180 915 4800 3075 bump alloc\001
+4 0 0 50 -1 0 12 0.0000 2 135 360 3975 4075 lock\001
+4 1 0 50 -1 0 12 0.0000 2 135 345 4725 3825 sbrk\001
+4 0 0 50 -1 0 12 0.0000 2 135 360 2775 3325 lock\001
+4 2 0 50 -1 0 12 0.0000 2 135 675 2625 2625 free lists\001
Index: doc/theses/mubeen_zulfiqar_MMath/AllocDS2.fig
===================================================================
--- doc/theses/mubeen_zulfiqar_MMath/AllocDS2.fig	(revision dbfae7bce53b3200450caaf0d2c54c5e9d1ac211)
+++ doc/theses/mubeen_zulfiqar_MMath/AllocDS2.fig	(revision dbfae7bce53b3200450caaf0d2c54c5e9d1ac211)
@@ -0,0 +1,101 @@
+#FIG 3.2  Produced by xfig version 3.2.7b
+Landscape
+Center
+Inches
+Letter
+100.00
+Single
+-2
+1200 2
+6 2850 2025 3150 2175
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 2925 2100 20 20 2925 2100 2945 2100
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 3000 2100 20 20 3000 2100 3020 2100
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 3075 2100 20 20 3075 2100 3095 2100
+-6
+6 4050 2025 4350 2175
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 4125 2100 20 20 4125 2100 4145 2100
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 4200 2100 20 20 4200 2100 4220 2100
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 4275 2100 20 20 4275 2100 4295 2100
+-6
+6 4650 2025 4950 2175
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 4725 2100 20 20 4725 2100 4745 2100
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 4800 2100 20 20 4800 2100 4820 2100
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 4875 2100 20 20 4875 2100 4895 2100
+-6
+6 3450 2025 3750 2175
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 3525 2100 20 20 3525 2100 3545 2100
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 3600 2100 20 20 3600 2100 3620 2100
+1 3 0 1 0 0 50 -1 20 0.000 1 0.0000 3675 2100 20 20 3675 2100 3695 2100
+-6
+6 3300 2100 3600 2475
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 3375 2100 3375 2325
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 3300 2325 3600 2325 3600 2475 3300 2475 3300 2325
+-6
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 2700 1950 6000 1950
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 3150 1800 3150 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 2850 1800 2850 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 4650 1800 4650 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 4950 1800 4950 2175
+2 1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 4500 1725 4500 2175
+2 1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5100 1725 5100 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 3450 1800 3450 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 3750 1800 3750 2175
+2 1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 3300 1725 3300 2175
+2 1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 3900 1725 3900 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5250 1800 5250 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5400 1800 5400 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5550 1800 5550 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5700 1800 5700 2175
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 5850 1800 5850 2175
+2 1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+	 2700 1725 2700 2175
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 2700 1800 6000 1800 6000 2175 2700 2175 2700 1800
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 2775 2100 2775 2325
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 2775 2400 2775 2625
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 2700 2625 2850 2625 2850 2775 2700 2775 2700 2625
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 2700 2325 2850 2325 2850 2475 2700 2475 2700 2325
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+	1 1 1.00 45.00 90.00
+	 4575 2100 4575 2325
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 4500 2325 5025 2325 5025 2475 4500 2475 4500 2325
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 3
+	1 1 1.00 45.00 90.00
+	 3600 3525 4650 3525 4650 3075
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+	 3600 3075 5100 3075 5100 3750 3600 3750 3600 3075
+4 2 0 50 -1 0 12 0.0000 2 135 975 2625 2175 free buckets\001
+4 2 0 50 -1 0 12 0.0000 2 135 435 2625 1950 locks\001
+4 1 0 50 -1 0 10 0.0000 2 150 1155 3000 1725 N$\\times$S$_1$\001
+4 1 0 50 -1 0 10 0.0000 2 150 1155 3600 1725 N$\\times$S$_2$\001
+4 1 0 50 -1 0 10 0.0000 2 150 1110 4800 1725 N$\\times$S$_t$\001
+4 2 0 50 -1 0 12 0.0000 2 135 675 2625 2625 free lists\001
+4 0 0 50 -1 0 12 0.0000 2 135 360 3675 3250 lock\001
+4 1 0 50 -1 0 12 0.0000 2 135 345 4425 3000 sbrk\001
+4 1 0 50 -1 0 12 0.0000 2 180 390 4425 1500 heap\001
Index: doc/theses/mubeen_zulfiqar_MMath/allocator.tex
===================================================================
--- doc/theses/mubeen_zulfiqar_MMath/allocator.tex	(revision d0e80f6167054028f4628261a2c844ccd7e5668e)
+++ doc/theses/mubeen_zulfiqar_MMath/allocator.tex	(revision dbfae7bce53b3200450caaf0d2c54c5e9d1ac211)
@@ -1,1 +1,32 @@
+
 \chapter{Allocator}
+
+\newpage
+\paragraph{Design 1: Decentralized}
+Fixed number of heaps: shard the heap into N heaps each with a bump-area allocated from the sbrk area.
+Kernel threads (KT) are assigned to the N heaps.
+When KTs $\le$ N, the heaps are uncontented.
+When KTs $>$ N, the heaps are contented.
+By adjusting N, this approach reduces storage at the cost of speed due to contention.
+In all cases, a thread acquires/releases a lock, contented or uncontented.
+\begin{cquote}
+\centering
+\input{AllocDS1}
+\end{cquote}
+Problems: need to know when a KT is created and destroyed to know when to create/delete the KT's heap.
+On KT deletion, its heap freed-storage needs to be distributed somewhere.
+
+\paragraph{Design 2: Centralized}
+
+One heap, but lower bucket sizes are N-shared across KTs.
+This design leverages the fact that 95\% of allocation requests are less than 512 bytes and there are only 3--5 different request sizes.
+When KTs $\le$ N, the important bucket sizes are uncontented.
+When KTs $>$ N, the free buckets are contented.
+Therefore, threads are only contending for a small number of buckets, which are distributed among them to reduce contention.
+\begin{cquote}
+\centering
+\input{AllocDS2}
+\end{cquote}
+Problems: need to know when a kernel thread (KT) is created and destroyed to know when to assign a shared bucket-number.
+When no thread is assigned a bucket number, its free storage is unavailable.
+It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.