01.txt

设计一个虚拟存储区和内存工作区

任务 
设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。

（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);

}