链表

发表时间: 2016/5/8 22:40:15 作者: 李亚 阅读:721 回复:1 编辑  删除

#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#include <time.h>

#define M 10                  //10个虚页
#define N 20                  //20个页面的访问序列

#define L 10                  //设定实页的最大值

int L_s;                       //实页的实际个数

//定义虚页的结构
typedef struct VirtualPage
{
 int pn;
 int pfn; 
 int time;
 
}VirtualPage;  

//定义实页的结构
typedef struct Page
{
 int pn;
 int pfn; 
 struct Page* next;
 
}Page;  

struct Page pp[L];   //定义一个存放5个实页的数组 ,在底下还要将其串成链表     

struct VirtualPage vp[M];  //  定义存放10个虚页的数组

int queue[N]; //定义一个数组,存放随机生成的20个数,表示访问虚页的次序,里面的数值不能超过9 

int count;  //存放缺页次数, 用来统计缺页率。本算法没有考虑预调页,只要该页不在内存,就认为缺页一次。

int countime; //用于LRU算法中,找出要淘汰的页。每当要访问一个虚页面时,countime的值加1,然后将所要访问的虚页的time项值设置为增值后的当前countime值

int MemoryStatus[L][N]; //记录当访问每一个虚页时,内存中的5个实页的详细信息。

int NotInMemory[N];    //表示每次虚页访问是否在内存

struct Page *Free,*Free_head,*Busy,*Busy_tail,*Busy_head,*temp;  

 

void FIFO()  //先入先出算法的具体实现。
{
    int i,j,k,currentpage;  //一些临时变量
 
 for(i=0;i<N;i++)   //这是主循环,每次处理一个虚页访问。直到把20个虚页处理完为止。
 {
  //当前访问的虚页是哪一页? 由数组queue[i]中的值表示
  currentpage=queue[i];
  
  //判断该虚页是否已经调入内存
  if(vp[currentpage].pfn!=-1)  //表示该页已经在内存中,可以直接访问。同时记录访问该页时对应的实页信息(和前一页相同)
  {
   for(j=0;j<L_s;j++)
            {
    MemoryStatus[j][i]=MemoryStatus[j][i-1];
   }
   NotInMemory[i]=0;
  }
        else  //该页不在内存,需要请求调页
  {
   count=count+1;  //缺页数加1
   
   if(Free!=NULL)  //如果Free链表不为空,表示内存中还有空的实页,故从Free链表中取队首元素,装入该虚页,并修改相关信息。
   {
    temp=Free_head;  //本程序中用Free表示链表的起始地址,Free_head表示链表中的第一个元素地址。实际上两者的值永远相等。
    
    Free_head=Free_head->next;
    Free=Free_head;
    
    //将虚页currentpage装入temp指向的实页,该实页的编号为temp->pfn
    vp[currentpage].pfn=temp->pfn;
    temp->pn=currentpage;
    
    //将temp指向的实页插入Busy链表的末尾
    temp->next=NULL;
    if(Busy==NULL)  //如果是第一次把虚页装入实页,则temp就是Busy链表的第一个元素。
    {
     Busy=temp;
     Busy_head=Busy;
     Busy_tail=Busy;
    }
    else  //如果不是第一次把虚页装入实页,则将temp插入Busy链表的队尾。
    {
     Busy_tail->next=temp;
     Busy_tail=temp;
    }
    //修改内存状态
    
    for(k=0;k<L_s;k++)  //复制访问前一页时的内存状态
    {
     MemoryStatus[k][i]=MemoryStatus[k][i-1];
    }
    MemoryStatus[temp->pfn][i]=currentpage;    //虚页currentpage装入了temp->pfn表示的那个实页里
    
    
   }
   else  //如果Free链表为空,需要置换一页出去。由于采用FIFO算法,故取busy链表的队首元素,将其置换出去,修改信息后插入队尾。
   {
    //将Busy首元素取出,赋给temp
    temp=Busy;
    Busy_head=Busy->next;
    Busy=Busy_head;
    
    //将当前虚页currentpage装入temp指向的实页,修改其信息
    vp[temp->pn].pfn=-1;                //该页被置换出去了,所以其pfn字段要设置成-1,表示其已经不再内存。
    vp[currentpage].pfn=temp->pfn;      //currentpage被装入内存,更新其pfn字段为temp指向的实页。
    temp->pn=currentpage;               //temp指向的实页,装入了currentpage虚页
    
    //将temp指向的实页插入Busy链表的末尾,此时不用再考虑Busy是否为空了。
    temp->next=NULL;
    Busy_tail->next=temp;
    Busy_tail=temp;
    
    //修改内存状态
    for(k=0;k<L_s;k++)  //复制访问前一页时的内存状态
    {
     MemoryStatus[k][i]=MemoryStatus[k][i-1];
    }
    MemoryStatus[temp->pfn][i]=currentpage;    //虚页currentpage装入了temp->pfn表示的那个实页里
    
   }
  }
 }
 
}

 

void LRU()   //LRU() 算法的具体实现
{

}

 


void print_f()
{
 int i, j;
  //显示依次访问20个虚页时对应的内存状态,即MemoryStatus数组的值。
  for(i=0;i<L_s;i++)
  {
   for(j=0;j<N;j++)
   {
    if(NotInMemory[j]==1)           //当访问的这个虚页不在内存时,显示将其调入内存后的详细内存信息
     printf("|%3d",MemoryStatus[i][j]);
    else
     printf("|%3c",32);           //当访问的这个虚页在内存时,内存状态未发生改变,故无需再显示一遍。本例用空格代替,其中 32 是空格的ASCII码
   }
  }
  
  printf("\n 缺页数为:%3d",count);
}

 

void main()
{
    int i,j,k;
 int choice;
 count=0;
 countime=0;
   
 printf("请输入实页的个数:");
 scanf("%d", &L_s);
 
 //初始化10个虚页
    for(i=0;i<M;i++)
 {
  vp[i].pn=i;
  vp[i].pfn=-1;
  vp[i].time=0;
  
 }
 
 //初始化5个实页,并将其串成链表形式
    for(i=0;i<L_s; i++)
 {
  
  pp[i].pn=-1;
  pp[i].pfn=i;
  pp[i].next=NULL;
  
 }
 
 //将5个实页依次相连,形成Free链表
 
 Free=&pp[0];
 Free->next=&pp[1];
 for(i=1; i<L_s-1; i++)
 {
  pp[i].next= &pp[i+1];
 }

 pp[L_s].next=NULL;

 Free_head=Free; 
 
 
 //初始化Busy链表
 
 Busy=NULL;
 Busy_head=NULL;
 Busy_tail=NULL;
 
 
 //初始化MemoryStatus数组
 
 for(i=0;i<L_s;i++)
  for(j=0;j<N;j++)
  {
   MemoryStatus[i][j]=-1;
  } 
  
  //初始化NotInMemory数组
  for(i=0;i<N;i++)
  {
   NotInMemory[i]=1;
  }
  
  
  // 生成20个介于 0-9 之间的随机数,作为页面访问序列。并将其显示出来
  for(i=0;i<N;i++)

  {
   queue[i]=rand()%10; 
   printf("|%3d",queue[i]);
  }

  printf("\n");
  
  printf("   1:FIFO(先进现出页面置换算法)    2:LRU(最近最久未使用页面置换算法) \n");
  printf("请输入算法选择:");
  scanf("%d", &choice);
  switch(choice)
  {
 
      case 1:
    FIFO();    //运行 FIFO() 算法
    break;
   case 2:
    LRU();      //运行 LRU() 算法
    break;

   default:
    printf("选择有误\a\a\a\\n");
    break;

  }

  print_f();
  
  getch();
}

回复

快速返回

re: 链表

李亚2017/6/5 12:40:22 [ 删除 ]
import java.io.*;
import java.net.*;
public class Client{
 public static void main(String args[]){
  String[] mess={"2010年的世界杯在哪里举行的?" , "巴西进入世界杯了吗?", "中国进入世界杯了吗?"};
  Socket clientSocket;
  DataInputStream in = null;
  DataOutputStream out = null;
  try{
   clientSocket = new Socket("127.0.0.1", 2010);
   in  = new DataInputStream(clientSocket.getInputStream());
   out = new DataOutputStream(clientSocket.getOutputStream());
   for(int i=0; i<mess.length; i++)
   {
    out.writeUTF(mess[i]);
    String s = in.readUTF();
    System.out.println("收到服务器端的回复:"+ s);
    Thread.sleep(5000);
   }
  }catch(Exception e)
  {
   System.out.println("服务器端断开连接"+e);
  }
 }
}
 
 
 
 import java.net.*;
import java.io.*;
public class Server{
 public static void main(String args[])
 {
  String [] answer= {"南非", "进入世界杯了", "哈哈。。。。 这个问题真逗"};
  ServerSocket serverForClient = null;
  Socket serverSocket = null;
  DataInputStream in = null;
  DataOutputStream out = null;
  try{
   serverForClient = new ServerSocket(2010);
  }catch(IOException e)
  {
   System.out.println(e);
  }
  try{
   serverSocket = serverForClient.accept();
   out = new DataOutputStream(serverSocket.getOutputStream());
   in = new DataInputStream(serverSocket.getInputStream());
   for(int i=0; i<answer.length; i++)
   {
    String s  = in.readUTF();
    System.out.println("服务器端收到客户提问:"+s);
    out.writeUTF(answer[i]);
    Thread.sleep(5000);
   }
  }catch(Exception e)
  {
   System.out.println("客户端断开连接"+e);
  }
 }
}
 
 
 
标题 (可以为空)
姓名*  
内容
 
验证码 验证码(看不清楚?请点击刷新验证码)
  登录