任務 
設計一個虛擬存儲區和內存工作區，并使用下述算法計算訪問命中率。

（1）先進先出的算法（FIFO）

（2）最近最少使用算法（LRU）

（3）最佳淘汰算法（OPT）

（4）最少訪問頁面算法（LFU）

（5）最近最不經常使用算法（NUR）

命中率=（1 – 頁面失效次數）/頁地址流長度

2．程序設計本實驗的程序設計基本上按照實驗內容進行。即首先用Srand( )和rand( )函數定義和產生指令序列，然后將指令序列變換成相應的頁地址流，并針對不同的算法計算出相應的命中率。相關定義如下：

 

（1）數據結構

1）頁面類型

typedef struct {

       int  pn, pfn, counter, time;

} pl-type;

其中pn為頁號，pfn為面號，counter為一個周期內訪問該頁面次數，time為訪問時間。

2）頁面控制結構

pfc_struct {

       int  pn, pfn;

struct  pfc_struct  *next;

}

typedef  struct pfc_struct pfc_type;

pfc_type  pfc [total_vp], *freepf_head, *busypf_head;

pfc_type *busypf_tail;

其中pfc[total_vp]定義用戶進程虛頁控制結構，

    *freepf_head為空頁面頭的指針，

    *busypf_head為忙頁面頭的指針，

    *busypf_tail為忙頁面尾的指針。

 

（2）函數定義

1）Void initialize( )：初始化函數，給每個相關的頁面賦值。

2）Void FIFO( )：計算使用FIFO算法時的命中率。

3）Void LRU( )：計算使用LRU算法時的命中率。

4）Void OPT( )：計算使用OPT算法時的命中率。

5）Void LFU( )：計算使用LFU算法時的命中率。

6）Void NUR( )：計算使用NUR算法時的命中率。

 

（3）變量定義

1）int a[tatal_instruction]：指令流數據組。

2）int page[total_instruction]：每條指令所屬頁號。

3）int offset[total_instruction]：每頁裝入10條指令后取模運算頁號偏移值。

4）int total_pf：用戶進程的內存頁面數。

5）int diseffect：頁面失效次數。

 

（4）程序流程圖

（略）

<程序>

# define TRUE 1

# define FALSE 0

# define INVALID – 1

# define null 0

 

# define total_instruction 320                                    / *指令流長 */

*define total_vp 32                                                  / *虛頁長 */

*define clear_period 50                                            / *清零周期 */

 

typedef struct {                                                       / *頁面結構 */

       int pn, pfn, counter, time;

}pl_type;

pl_type pl[total_vp];                                                 / *頁面結構數組 */

struct pfc_struct {                                                  / *頁面控制結構 */

       int pn, pfn;

       struct pfc_struct *next;

};

typdef struct pfc_struct pfc_type;

pfc_type pfc[total_vp], *freepf_head, *busypf_head, *busypf_tail;

 

int diseffect, ︺︺ a [total_instruction];

int page [total_instruction], ︺︺ offser [total_instruction];

 

void initialize ( );

void FIFO ( );

void LRU ( );

void OPT ( );

void LFU ( );

void NUR ( );

 

int main ( void )

{

  int S, i, j;

 

  srand (getpid ( )*10);   /*由于每次運行時進程號不同，故可用來作為初始化隨機數隊列的“種子”*/

  S=(float) 319 *rand ( )/32767+1;

  for (i = 0; i < total_instruction; i+ = 4)  {    / *產生指令隊列 */

    a[i] = S;                                                   / *任選一指令訪問點 */

a[i+1] = a[i]+1;                                         / *順序執行一條指令 */

a[i+2] = (float)a[i]*rand( )/32767                / *執行前地址指令m’ */

a[i+3] = a[i+2]+1;                                     / *執行后地址指令 */

S = (float) rand ( )*(318–a[i+2])/ 32767+a[i+2]+2;

  }

  for (i = 0; i <total_instruction; i++)  {       / *將指令序列變換成頁地址流 */

    page[i] = a[i]/10;

    offser[i] = a[i]%10;

  }

  for (i = 4; i <=32; i++)  {               / *用戶內存工作區從4個頁面到32個頁面 */

    printf (“%2d page frames”, i);

    FIFO (i);

    LRU (i);

    OPT (i);

    LFU (i);

    NUR (i);

    Printf (“\n”);

  }

}

 

void FIFO (total_pf)                                  / *FIFO (First in First Out) ALGORITHM */

int total_pf;                                               / *用戶進程的內存頁面數*/

{   

int i,j;

pfc_type *p, *t;

initialize (total_pf);                              /*初始化相關頁面控制用數據結構 */

busypf_head = busypf _tail = NULL;           /*忙頁面隊列頭，隊列尾鏈接 */

for ( i = 0; i < total_instruction; i++)   {

  if (pl[page[i]], pfn= = INVALID)   {      /*頁面失效 */

diseffect + = 1;                                         /*失效次數 */

  if (freepf_head = = NULL)    {              /*無空閑頁面 */

p = busypf_head–>next;

pl[busypf_head–>pn].pfn = INVALID;

freepf_head = busypf_head;                /*釋放忙頁面隊列中的第一個頁面*/

freepf_head–>next = NULL

busypf_head = p;

}

p = freepf_head–>next;                              /*按FIFO方式調新頁面入內存頁面*/

freepf_head–>next=NULL;

freepf_head–>pn=page[I];

pl[page[i]].pfn=freepf_head–>pfn;

if (busypf_tail= = NULL)

busypf_head=busypf_tail=freepf_head;

else  {

busypf_tail–>next=freepf_head;

busypf_tail = freepf_head;

}

freepf_head = p;

}

}

print (“FIFO: % 6.4f’, 1– (float) diseffect/320”);

}

 

void LRU (total_pf)                            /*LRU (Last Recently Used) ALGORITHM*/

    int total_pf;

{int min, minj, i, j, present_time;

 

initialize (total_pf); present_time = 0;

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

{  if (pl[page[i]]. pfn=INVALID)                      /*頁面失效*/

{diseffect++;

  if (freepf_head=NULL)                                  /*無空閑頁面 */

{min=32767;

for (j=0; j<total_vp; j++)

  if (min>pl[j], time && pl[j]. pfn!=INVALID)

  {min=pl[j].time; minj=j;}

freepf_head = &pfc[pl[minj].pfn];

pl[minj].pfn = INVALID;

pl[minj].time = –1;

freepf_head –>next = NULL;

}

pl[page[i]].pfn = freepf_head–>pfn;

pl[page[i]].time = present_time;

freepf_head = freepf_head–>next;

}

else

pl[page[i]], time = present_time;

present_time ++;

}

printf (“LRU: %6.4f”, 1–(float) diseffect/320);

}