DOC

Haotian Liu
George Wheaton

*NOTE: We attempted to pass all extra credit algorithms, and enter the design competition.


P2FL (Power of two free list):

	Each page has a header, and this header has some information about the page. At first it has a pointer that is pointing to the kpage_t ptr, so that we can free it as we want. Then, there is an int numalloc, this keeps a log of the page's number of allocated blocks. Also, there is a free list of sizes, in powers of two, each list pointing to its buffer. And for the buffers in the page, they have a header pointer to the free list it belongs to. Following the header is the data itself. If it is free, the header points to the next free buffer. Particularly, the first page (we call it mainpage), has an additional variable named numpages, which indicates how many pages we have already used. When dealing with a request, we first check the free list, so that we can make full use of the free buffer not getting a new page. If there is no buffer available, we try to search each page's end, checking if there is enough space in a bufer that we can use. If not, we come to the final option-- that is we get a new page. For this implementation, as we should keep it sequential (the blocks need to be contiguous), we don't free the page when there is something still allocated. Also, whenever we free a buffer, we just add it to the very beginning of the free list -- this makes this algorithm less efficient.

Metrics
MEMORY UTILIZATION (pages used in order of traces 1 - 5) -> 3, 66, 1058, 1646, 2876
TIME (real-time process took, time in user mode, time in kernel mode for 3rd, 4th, and 5th) -> 0.31/0.21/0.08, 0.55/0.48/0.04, 9.79/8.54/0.69

BUD (Buddy system):	

	We still use the power of two, but this time it is different. At the very beginning, we take a whole page to store all the information we need (for our implementation of lists). The first page is called mainpage. If it is full, we just alloc a new one and add it to the previous one's end. The mainpage keeps a track of the number of allocs for the entire program, and also has numpages to take account of the used pages which are under control of the mainpage. By control we mean, in the mainpage, there is a structure array that stores each page's kpage_t item and the address and also the numalloc of that page and a bitmap which we will use for finding the buddy. For each data page, there is no header. So we can store up to 8192 bytes. When a request occurs, the kma_bud first check the free list which is almost the same as p2fl. If hit, then alloc, but there is an additional action that we mark the bitmap to indicate that the current block we are talking about is being used. The bitmap has 64 unsigned char, so it has 512 bits (in our implementation every one bit represents a 16 byte block) that can cover the whole 8192 bytes. If free list miss, we try the large free list, if we have, we divide it to two same size blocks, and keep doing this dividing until we get the right size block we need. If none of this works we finally get a new page, and divide it in the same way for the large block to the right size block (we always break it down in this manner). Once we divide blocks, there must also be a combine method. We implemented this by having the block first look up the bitmap, and find its buddy, and try to combine both of them to a large one. And doing the same process before except in reverse until we reach the largest 8192 block size.

Metrics
MEMORY UTILIZATION -> 3, 43, 1374, 1244, 10054
TIME -> 0.11/0.06/0.03, 0.17/0.10/0.05, 0.74/0.56/0.15

RM (Resource map): 

	The resource map is perhaps the most straightforward implementation of our allocator. We simply maintain a doubly linked list of available free blocks and their respective sizes (the data of which is in the free block itself, at the beginning). The header to this list is kept at the beginning of the mainpage. The list is maintained through the functions add, remove, and resolve. Add adds a free block to our list in order of increasing address (to maintain contiguity and allow for more efficient memory utilization). Remove takes a free block and removes it from our list, maintaing list integrity. Resolve is called whenever we have a free command, and it runs through the pages looking for pages with their numalloc (each page keeps track of how many free blocks are in it) set to 0. To do this we start at the end or last page, and work backwards checking each page. If the page has no free blocks, then we don't need it so we free it (making sure to call remove on each free block that is in that page, found through the whichpage member). The resource allocation comes from our findfit method, which searches our free list for a block that is large enough to handle the request. If found we return it, remove it from our free list, and try to add the remainder to our free list so we can preserve memory. If not found, we need to initialize a new page and recursively call findfit again. The major challenge of this implementation was passing test 5, and to do so we needed to change resolve to a better algorithm (the one described above) from the more simple algorithm that we used in our P2FL implementation. Most of the time here is spent in the O(n) add and O(kn) resolve where k is amount of pages and n is amount of resources.

Metrics
MEMORY UTILIZATION -> 3, 40, 696, 1145, 1605
TIME -> 0.40/0.37/0.02, 1.21/1.08/0.04, 41.24/38.66/0.08

LZBUD (Lazy buddy system):	

	This is a furthering of the buddy system. We only change a few things. First, we keep a record of slack for each free list. The slack follows the algorithm talked about in the hand-out. Also we carefully maintain the slack when dividing the block into two small ones. When dealing with the combination, we don't care about the slack, because we are dealing with the globally free blocks, and slack = N-2L-G, so it doesn't make any sense to slack. In addition, we improve the function of adding the free buffer to the free list because now we add it in the order of the address (increasing address) of the buffer. The most difficult part for this algorithm was that when slack is zero, we need to free another buffer and try to combine it as possible. It makes it too conflicted, that they can be in the same page, and in the following page or in the two pages which are not near each other. This has a huge impact for the free page function. So, we separately keep track of these two pages, can try to free it, but not free it twice. Then, change the method to free all pages so that we emulate all the pages from the end to the beginning and check the numalloc so that we can free it.

Metrics
MEMORY UTILIZATION -> 3, 43, 775, 1244, 1021
TIME -> 0.12/0.08/0.03, 0.23/0.18/0.03, 0.79/0.63/0.09

MCK2 (McKusick-Karels):	

	It mainly keeps one page for a fixed size. When finishing all the algorithms above, this one is straightforward. We still use the idea for p2fl, that each page has its own header at the very beginning of that page. When we initialize the page, we divide the entire page to the fixed size buffers and set each buffer pointer to the following one. Then we add the last one and the first one, and then set the first one to point to the following one. So that all the buffers are in the link. And to keep it sequential, we cannot free a page that is in the middle of the page queue, so we mark it empty, so that the next time we try to get a page, we can use it for a different size. To point out that, when we set a page to empty, we set the first buffer within the page to point the one that the last buffer is pointing to, and then unlink the first buffer, so that all the buffers are unlinked. This is promised by the ordering of address when we add the free buffer into the free list.

Metrics
MEMORY UTILIZATION -> 8, 43, 993, 2233, 1379
TIME -> 0.14/0.06/0.06, 0.23/0.19/0.03, 0.91/0.73/0.09

FUN (improvement on Lazy buddy system):	

	This is for the competition. It comes from converting the bud to lzbud, and we improve the function by adding a free buffer to a free list in the order of address. Also, we make a improvement that when we free a 8192 byte block, there is no need to empty the bit map, so just free the page. As the 5.trace has a lot of requests for more than 4096 bytes-size blocks, this indeed improves the quickness. The mainpage can store 91 page info as in 64bit machine. Once we know that the competition is in a 32bit machine, we change it to 105 pages by change the #define NUMPAGES. The improvement from 64bit to 32bit is around 2%.

Metrics
MEMORY UTILIZATION -> 3, 43, 1374, 1244, 10090
TIME -> 0.11/0.07/0.04, 0.17/0.11/0.04, 0.72/0.60/0.06