LRU算法總結及其C算法實作

LRU算法總結及其C算法實作

LRU是關于作業系統的記憶體管理，如何節省利用容量不大的記憶體為最多的程序提供資源，一直是研究的重要方向的其中一種算法。在作業系統開發和管理的時候，為了提高記憶體的使用率，提高記憶體的性能，就需要使用某種算法來管理。使用擴充記憶體或者虛拟記憶體能夠極大的友善作業系統對記憶體的管理和提高記憶體的能力，也就是常常我們說的虛拟記憶體了。當程式載入的時候，這個時候作業系統會讀取一部分到記憶體中，一些資訊段會存儲需要調用的記憶體在磁盤上的位址。例如一個程式要讀檔案，在載入時，讀檔案的方法并沒有載入到記憶體中，當需要讀檔案時，作業系統可能才把相應的記憶體給載入到寄存器，這樣雖然提高了記憶體的功能，但是卻加大了互動。是以就想到可以設計算法來減少互動，提高效率。LRU就是為了這個需求設計的算法中的一種。

連結清單法：

作業系統為每個程序維護一條連結清單，連結清單的每個結點記錄一張頁面的位址。調用一次頁面，則把該頁面的結點從鍊中取出，放到鍊尾；要裝入新頁，則把鍊頭的頁面調出，同時生成調入頁面的結點，放到鍊尾。

連結清單法可看作簡單計時/計數法的改良，維護一個連結清單，自然要比維護所有頁面标志要簡單和輕松。可是，這并沒有在數量級上改變算法的時間複雜度，每調用一個頁面，都要在連結清單中搜尋對應結點并放至鍊尾的工作量并不算小。

重要算法解釋

view plaincopy to clipboardprint?

void LRU(page_node *head)   /*LRU算法,用到一個連結清單,表頭為work_head指針指向記憶體中最久未被通路過的頁面,表尾為work_tail指針指向記憶體中最近被通路過的頁面*/ 

{     

    page_node *phead,*work_head=NULL,*work_tail,*prenode;  

    int i,diseffect=0;  

    for(i=0;i<NUM;i++)  

    if(page_id_status[page_id[i]]==0)  /*如果第page_id[i]頁不在記憶體則發生頁面中斷*/ 

    {    

        if(head!=NULL)    /*記憶體空間已全部被占用,要求換出一頁,即從work_head表頭取出一頁換出*/ 

        {    

            phead=head->next;  

            head->next=NULL;  

            head->id=page_id[i];  

            head=phead;  

        }  

    else                 /*記憶體空間還有部分未被使用,可直接将頁面放入,即放在work_head連結清單尾部即work_tail處*/ 

               diseffect++;  

               page_id_status[page_id[i]]=1;  

    }  

    else                  /*如果第page_id[i]頁在記憶體則調整頁面順序,最近被通路的頁面調到連結清單尾部*/ 

        phead=work_head;  

        while(phead->id!=page_id[i])  

        {  

            prenode=phead;  

            phead=phead->next;  

        if(phead==work_head)  

            work_head=work_head->next;  

        else if(phead==work_tail)  

            work_tail=prenode;  

        else 

            prenode->next=phead->next;  

        phead->next=NULL;  

        work_tail->next=phead;  

        work_tail=work_tail->next;  

    printf("LRU: %d",diseffect);  /*輸出頁面中斷次數*/ 

} 

void LRU(page_node *head)   /*LRU算法,用到一個連結清單,表頭為work_head指針指向記憶體中最久未被通路過的頁面,表尾為work_tail指針指向記憶體中最近被通路過的頁面*/

{  

    page_node *phead,*work_head=NULL,*work_tail,*prenode;

 int i,diseffect=0;

 for(i=0;i<NUM;i++)

 if(page_id_status[page_id[i]]==0)  /*如果第page_id[i]頁不在記憶體則發生頁面中斷*/

 { 

  if(head!=NULL)    /*記憶體空間已全部被占用,要求換出一頁,即從work_head表頭取出一頁換出*/

  { 

   phead=head->next;

   head->next=NULL;

   head->id=page_id[i];

   head=phead;

  }

 else                 /*記憶體空間還有部分未被使用,可直接将頁面放入,即放在work_head連結清單尾部即work_tail處*/

      diseffect++;

      page_id_status[page_id[i]]=1;

 }

 else                  /*如果第page_id[i]頁在記憶體則調整頁面順序,最近被通路的頁面調到連結清單尾部*/

  phead=work_head;

  while(phead->id!=page_id[i])

  {

   prenode=phead;

   phead=phead->next;

  if(phead==work_head)

   work_head=work_head->next;

  else if(phead==work_tail)

   work_tail=prenode;

  else

   prenode->next=phead->next;

  phead->next=NULL;

  work_tail->next=phead;

  work_tail=work_tail->next;

 printf("LRU: %d",diseffect);  /*輸出頁面中斷次數*/

}  

編譯後，按提示輸入頁架數與通路序列，回車；運作後，将看到輸出結果即頁面置換與裝入情況。

如此顯然要花費較大的系統開銷(包括時間和空間上的)，這也是實際系統中不直接采用LRU算法作為頁面置換算法的直接原因，但由于其在頁面置換的優越性，實際系統常使用LRU的近似算法。