一个关于随机数的程序问题，问问大家啊

zdh

一个存储管理的实验，要求如下，我编完以后，编译后运行老出一个错误就是“段错误”，以为是内存溢出，还是其他的问题，然后检查了两天都没有检查出错误，个人认为是随机数产生出了问题，可是就是解决不了，请斑竹，大虾们帮我看看啊，救命！

实验内容
(1) 通过随机数产生一个指令序列，共320条指令，指令地址按下述原则生成
① 50%的指令是顺序执行；
② 25%的指令是均匀分布在前地址部分；
③ 25%的指令是均匀分布在后地址部分；
具体的实施方法是
① 在 [0, 319] 的指令地址之间随机选取一起点m ；
② 顺序执行一条指令，即执行地址为 m+1 的指令；
③ 在前地址[0, m+1] 中随机选取一条指令并执行，该指令的地址是m’ ；
④ 顺序执行一条指令，其地址为m’+1 ；
⑤ 在后地址[m’+2, 319] 中随机选取一条指令并执行；
⑥ 重复上述步骤 ①～⑤，直到执行320次指令。

(2) 将指令序列变为页地址流
设：① 页面大小为1K ；
② 用户页面内存容量为4页到32页；
③ 用户虚存容量为32K 。
在用户虚存中，按每 K 存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条～第9条指令为第0页（对应虚存地址为[0, 9]）；
第10条～第19条指令为第1页（对应虚存地址为[10, 19]）；
……
……
第310条～第319条指令为第31页（对应虚存地址为[310, 319]）；
按以上方式，用户指令可组成32页。

(3) 计算并输出下述各种算法在不同内存容量下的命中率
① First-In-First-out (FIFO) Page Replacement
② Least-Recently-Used (LRU) Page Replacement
③ Optimal Page Replacement
④ Least-Frequently-Used (LFU) Page Replacement
⑤ Not-Used-Recently (NUR) Page Replacement
其中③和④为选择内容

在本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。
[php]
#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;
};
typedef 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],  offset[total_instruction];
void initialize();
void FIFO();
void LRU();
void OPT();
void LFU();
void NUR();

main()
{
  int S,i,j;

  srand(getpid()*10);

  S=(float)(319*rand()/32767+1);
  for(i=0;i<total_instruction;i+=4)
  {
  a=S;
  a[i+1]=a+1;
  a[i+2]=(float)a*rand()/32767;
  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=a/10;
offset=a%10;
}
for(i=4;i<=32;i++)
{
printf("%2d page frames",i);
FIFO(i);
LRU(i);
OPT(i);
LFU(i);
NUR(i);
printf("\n");

}
}

void FIFO(total_pf)
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].pfn==INVALID)
  {diseffect+=1;
  if(freepf_head==NULL)
  {p=busypf_head->next;
   freepf_head=busypf_head;
   freepf_head->next=NULL;
   busypf_head=p;
  }
p=freepf_head->next;
freepf_head->next=NULL;
freepf_head->pn=page;
pl[page].pfn=freepf_head->pfn;
if(busypf_tail->next==NULL)
      busypf_head=busypf_tail=freepf_head;
else
{/*busypf_tail->next=freepf_head; */
  busypf_tail=freepf_head;
}
freepf_head=p;

  }
  }
printf("FIFO:%6.4f",1-(float)diseffect/320);
}

void LRU(total_pf)
  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].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].pfn=freepf_head->pfn;
  pl[page].time=present_time;
  freepf_head=freepf_head->next;
  }
  else
  pl[page].time=present_time;
   present_time++;
  }
  printf("LRU:%6.4f",1-(float)diseffect/320);
  }


void NUR(total_pf)

int total_pf;
{
int i,j,dp,cont_flag,old_dp;
pfc_type *t;

initialize(total_pf);
dp=0;
for(i=0;i<total_instruction;i++)
{
if(pl[page].pfn==INVALID)
{
diseffect++;
if(freepf_head==NULL)
{cont_flag=TRUE;old_dp=dp;
while(cont_flag)
if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)
   cont_flag=FALSE;
else
{dp++;if(dp==total_vp)dp=0;
if(dp==old_dp)
for(j=0;j<total_vp;j++)pl[j].counter=0;
}
freepf_head=&pfc[pl[dp].pfn];
pl[dp].pfn=INVALID;
freepf_head->next=NULL;
}
pl[page].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
else
    pl[page].counter=1;
if(i%clear_period==0)
for(j=0;j<total_vp;j++)
pl[j].counter=0;
}
printf("NUR:%6.4f",1-(float)diseffect/320);
}


void OPT(total_pf)
int total_pf;
{int i,j,max,maxpage,d,dist[total_vp];
pfc_type *t;


initialize(total_pf);
for(i=0;i<total_instruction;i++)
{
if(pl[page].pfn==INVALID)
{diseffect++;
if(freepf_head==NULL)
{for(j=0;j<total_vp;j++)
if(pl[j].pfn!=INVALID)dist[j]=32767;else dist[j]=0;
d=1;
for(j=i+1;j<total_instruction;j++)
{if(pl[page[j]].pfn!=INVALID)
dist[page[j]]=d;
d++;
}
max=-1;
for(j=0;j<total_vp;j++)
if(max<dist[j])
{max=dist[j];maxpage=j;}
freepf_head->next=NULL;
pl[maxpage].pfn=INVALID;
   }
   pl[maxpage].pfn=freepf_head->pfn;
   freepf_head=freepf_head->next;
}
}
printf("OPT:%6.4f",1-(float)diseffect/320);
}


void LFU(total_pf)
int total_pf;
{int i,j,min,minpage;
pfc_type *t;

initialize(total_pf);
for(i=0;i<total_instruction;i++)
{
if(pl[page].pfn==INVALID)
{
diseffect++;
if(freepf_head==NULL)
{
min=32767;
for(j=0;j<total_vp;j++)
{if(min<pl[j].counter&&pl[j].pfn!=INVALID)
{min=pl[j].counter;minpage=j;}

pl[j].counter=0;
}
freepf_head=&pfc[pl[minpage].pfn];
pl[minpage].pfn=INVALID;
freepf_head->next=NULL;
}
pl[page].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
else
pl[page].counter++;
}
printf("LFU:%6.4f",1-(float)diseffect/320);
}


void initialize(total_pf)
   int total_pf;
  {
  int i;
  diseffect=0;
  for(i=0;i<total_vp;i++)
  {
  pl.pn=i;pl.pfn=INVALID;
  pl.counter=0;pl.time=-1;
  }
  for(i=1;i<total_pf;i++)
  {pfc[i-1].next=&pfc;pfc[i-1].pfn=i-1;}
  pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1;
  freepf_head=&pfc[0];
  }
[/php]

kj501

段错误的直接原因出在代码的第72行：

1. 
   
2.         if(pl[page[i]].pfn==INVALID)
   

复制代码

page的值已经越界了。
真正的原因是这句代码：

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

复制代码

你可以自己把它的值打印出来看看。这个值的大小足以让pl[page]的数组下标越界。

zdh

可是我用下面的程序观察随机数,发现产生的随机数不对啊,尽管我觉得实现程序是对

main()
{
int S,i,j,total_instruction=320;
float a[total_instruction];

srand(10*getpid());

S=(float)(319*rand()/32767+1);
printf("%f\n",S);
for(i=0;i<total_instruction;i+=4)

  {

  a=S;

  a[i+1]=S+1;

  a[i+2]=319*rand()/32737;

  a[i+3]=a[i+2]+1;

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

  }
for(i=0;i<320;i++)

  {printf("a[%d]=%f\n",i,a);}

}

zdh

结果是:
[zdh@localhost zdh]$ gcc -o 07 07.c
[zdh@localhost zdh]$ ./07
-1.994926
a[0]=17688.000000
a[1]=17689.000000
a[2]=-65560.000000
a[3]=-65559.000000
a[4]=-2147483648.000000
a[5]=-2147483648.000000
a[6]=21161.000000
a[7]=21162.000000
a[8]=-318613024.000000
a[9]=-318613024.000000
a[10]=-58371.000000
a[11]=-58370.000000
a[12]=-2147483648.000000
a[13]=-2147483648.000000
a[14]=18797.000000
a[15]=18798.000000
       .
       .
       .

fingster

srand(time(0));
result=rand()%range+1;
这样可以显示1到range之间的随机数。srand()调用一次就可以。

zdh

Rf=(X*rand())/(RAND_MAX+1.0)  /*用来产生[0,X-1]中的随机数*/
可是为什么上面程序中产生出来的就不是[0,319]中的随机数呢?

zdh

S=(float)(319*rand()/32767+1);
是要产生[0,319]的随机数啊,还是产生[0,32767]中的随机数呢?现在都弄胡涂了.
而用result=rand()%range+1;实现
不就成了
result=rand()%319+1;

libinary

你既然知道RAND_MAX就应该用它，我的系统里RAND_MAX是：
#define RAND_MAX  2147483647
最好不要用32767这种幻数

kj501

看看rand()的说明, 它产生的是0到RAND_MAX之间的一个随机数.
如果要产生0到319之间的随机数.可以这样:
[php]
#include<stdlib.h>

int main()
{
        int j;
        srand(time(0));
        j=(int) (319.0*rand()/(RAND_MAX+1.0));
        printf("%d\n",j);
}
[/php]

zdh

上面给的例子,我看了,也运行了,完全符合产生[0,319]的随机数,可是当我运用到上面我给你程序里面去后,就会出错了.
07.c:5:1: warning: "NULL" redefined
In file included from /usr/include/stdlib.h:33,
                 from 07.c:1:
/usr/lib/gcc-lib/i386-redhat-linux/3.2.2/include/stddef.h:402:1: warning: this is the location of the previous definition
或是
07.c: In function `main':
07.c:39: warning: integer overflow in expression
斑竹看过我发的程序,觉得如果要求就是[0,319]的,那么程序在不溢出的情况下应该怎么改呢?因为程序在初始化的时候的,都让pl.pfn=INVALID;
所以应该不会在if(pl[page].pfn==INVALID)出错啊,上次你指出来的地方.
谢谢!