link list-小專題-記憶體管理-first fit allocation

// 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