// node structure for memory info
typedef struct MemInfo {
unsigned begin, size;
struct MemInfo *prev, *next;
}MemInfo;
// head node for occupied memory linked list
MemInfo *head_occupy = NULL;
// head node for un-used memory linked list
MemInfo *head_free = NULL;
MemInfo *tail_free = NULL;
// insert data to tail of the linked list
void Mem_info_insert_in_tail(unsigned begin, unsigned size)
{
// create a new node for this data
MemInfo *data = (MemInfo*) malloc(sizeof(MemInfo));
data->begin = begin;
data->size = size;
// if there is no existing data
if (head_free == NULL)
head_free = tail_free = data;
else {
tail_free->next = data;
data->prev = tail_free;
data->next = NULL;
tail_free = data;
}
}
void Mem_info_show_list(void)
{
MemInfo *rush = head_free;
printf("The result is:\n");
while (rush != NULL) {
printf("(%d, %d) ", rush->begin, rush->size);
rush = rush->next;
}
puts("");
}
// allocate a memory in a linked list by first fit
MemInfo *first_fit_mem_alloc(unsigned size)
{
MemInfo *first_fit, *data = NULL;
// assign this from head node for un-used memory
first_fit = head_free;
// find out first_fit node
while (first_fit != NULL && first_fit->size < size)
first_fit = first_fit->next;
// if we could find out one
if (first_fit != NULL) {
// allocate memory for this data
data = (MemInfo*) malloc(sizeof(MemInfo));
data->begin = first_fit->begin;
data->size = size;
// if the size of this first fit is larger than
// allocation, then calculate the new size
if (first_fit->size > size) {
first_fit->begin += size;
first_fit->size -= size;
}
else {
// judge if this is head
if (first_fit == head_free)
head_free = first_fit->next;
else
first_fit->prev->next = first_fit->next;
// if this is not tail
if (first_fit->next != NULL)
first_fit->next->prev = first_fit->prev;
free(first_fit);
}
} // if (first_fit != NULL)
return data;
}
int main()
{
unsigned begin, size;
printf("Mem info linked list:\n");
fin = fopen("mem_info_input", "r");
while (fscanf(fin, "%d %d", &begin, &size) != EOF) {
printf("(%d, %d) ", begin, size);
Mem_info_insert_in_tail(begin, size);
}
Mem_info_show_list();
first_fit_mem_alloc(1000);
Mem_info_show_list();
fclose(fin);
return 0;
}
記憶體的管理，是我們在目前幾乎所有的os都會碰到的課題。因為都是多工的，也就是許多的job都會切成一小段一小段分別/管線/平行的去執行。而多個程式也會因此同時在記憶體之中allocate。但因為切分的關係，每支程式所需要的記憶體都不盡然相同。有的要42K，有的要32M，有的只需小小的0.1K。而正常的程式在執行結束之後，都會free掉記憶體。因此常常會出現中間部分的記憶體是已經free掉了，因此我們需要記錄那塊free掉的記憶體的位置以及資料，這樣才能夠利用。在這使用了linked list來當作實做的工具。這個list會有四筆資料在內。我們用了雙向的linked list於是有兩筆分別指向前(prev)與後(next)的node。然後我們還需要這個node的記憶體起始位置(begin)以及大小(size)：
typedef struct MemInfo {
unsigned begin, size;
struct MemInfo *prev, *next;
}MemInfo;
而我們也使用了兩個串列，一個串列head_free是為了記錄有哪些記憶體是空的，可以使用的。那麼相反的，head_occupy就會是記錄目前使用中的記憶體的串列。而一樣linked list為了方便起見我們也記錄了尾端tail_free為了實做allocation，一樣我們還是需要資料輸入工具，因此邏輯上相同於普通的linked list中的insert_in_tail()，在這邊我們唯一不同的就是輸入兩筆記錄begin和size，因此Mem_info_insert_in_tail()基本上就和insert_in_tail()是一樣的東西，不多加贅述。
而這邊的主軸，就是要在free的串列之中找到第一個比我們要求的size還要大的記憶體node。因此邏輯上是很簡單的，只要從head_free開始去比較大小，然後找到之後在去對這個node處理即可。
首先我們需要一個pointer去四處搜尋我們要的size，我為它取名為first_fit，也就是它的目的是為了尋找出第一個適合的大小的node，而這個function也需要回傳一個node是要標示我們為他allocation的node，取名為data：
MemInfo *first_fit, *data;接著我們便去找出適合的大小：
while (first_fit != NULL &&first_fit->size < size)
first_fit = first_fit->next;
這時候找到之後，first_fit就會是我們要的node(另一個情形就是並沒有找到我們要的大小，因此這邊的first_fit就會是NULL)，因此當我們有找到的狀況下才需要做allocation和後續的處理：
if (first_fit != NULL) {
// allocate memory for this data
data = (MemInfo*) malloc(sizeof(MemInfo));
data->begin = first_fit->begin;
data->size = size;
而所謂的後續的處理呢，有兩種狀況，第一種就是我們尋找到的node的size比我們需求的大，這時候處理方式就會是把我們找到的node的起始位置begin往下移開size大小(因為我們要在這個node的記憶體allocate size大小，所以free的起始位置就會少掉了size大小)，同時這個node的大小便同時會減少了size這麼大：
if (first_fit->size > size) {
first_fit->begin += size;
first_fit->size -= size;
}
另一種狀況就是我們找到的node的大小正巧符合我們要的大小，但我們需要特別注意的就是如果我們找到的node是第一個，也就是head_free，這時候我們需要重新指定head_free為下一個node(第一種狀況不用，因為head_free比size大，並沒有把整個node移掉，不需重新指定)。接下來就是把前面那個node往下一個node接，下一個node往前接，最後在free掉即可：
else {
// judge if this is head
if (first_fit == head_free)
head_free = first_fit->next;
else
first_fit->prev->next = first_fit->next;
// if this is not tail
if (first_fit->next != NULL)
first_fit->next->prev = first_fit->prev;
free(first_fit);
}
最後回傳我們已經allocated的記憶體就大功告成：
return data
