1.cpp

很好的存储器演示算法,欢迎大家下载使用。谢谢合作

#include <STDIO.H>    
#include <MALLOC.H>    
#include <STDLIB.H>    
#include <STRING.H>    
 
#define P 10//PHYSICS
#define W  500//WORK 
#define  BLOCK_SIZE     500             //初始空闲分区大小    
#define  NULL           0    

#define B 10//PHYSICS
#define D  500//WORK
   
typedef struct Node{   
    int             start_address;      //空闲区首地址    
    int             block_size;         //空闲区大小    
    struct Node*    prior;              //前向指针    
    struct Node*    next;               //后向指针    
    int             state;              //空闲区状态    
}Node,*LinkList;   
   
LinkList    L;                          //指向用户存储区的首地址    
LinkList    Free;                       //空闲分区链表头指针    
LinkList    Assigned;                   //已分配区链表头指针    
   
//--------------------------------------------------------------    
void InitBlock(void) //初始化    
{   
    L = (LinkList)malloc(sizeof(Node));   
       
    L->start_address = 0;   
    L->block_size = BLOCK_SIZE;   
    L->prior = NULL;   
    L->next = NULL;   
    L->state = 0;   
       
    Free = (LinkList)malloc(sizeof(Node));      //建立空闲区链表(含头指针)    
    Assigned = (LinkList)malloc(sizeof(Node));  //建立分配区链表(含头指针)    
   
    Assigned->block_size = Free->block_size = 0;   
    Assigned->start_address = Free->start_address = 0;   
    Assigned->prior = Free->prior = NULL;   
    Assigned->next = Free->next = NULL;   
    Assigned->state = Free->state = 0;   
   
   
    //printf("\n初始化空闲块成功\n");    
}   
//--------------------------------------------------------------    
void Display()      //显示存储区分配情况    
{   
    LinkList p;   
   
    printf("****存储区情况****:\n");   
    printf("已经分配区有:\n");   
    for(p = L;p != NULL;p = p->next)   
    {   
        if(p->block_size == 0)   continue;   
        if(p->state == 1)   
        {          
            printf("(%3d,%3d)\n",p->start_address ,p->start_address+p->block_size);   
        }   
    }   
   
    printf("空闲区有:\n");   
    for(p = L;p != NULL;p = p->next)   
    {   
        if(p->block_size == 0)   continue;   
        if(p->state == 0)   
        {          
            printf("(%3d,%3d)\n",p->start_address ,p->start_address+p->block_size);   
        }   
    }   
}   
//--------------------------------------------------------------    
void Tighten()//紧凑算法    
{   
    int flag;   
    LinkList p,q;   
   
    flag = 0;   
    p = L;      
       
    for(;p != NULL;p = p->next)   
    {   
        if(p->state == 0 && flag == 0)   
        {   
            q = p;   
            if(p->prior != NULL)   
            {   
                p->prior->next = p->next ;   
                p->state = 1;   
            }   
            flag = 1;                   //标记 已找到要移动的空闲区    
            p = p->next ;   
        }   
   
        if(flag == 1)                  
        {   
            for(;p->state == 1 && p != NULL;p = p->next)   
            {   
                p->start_address = p->start_address - q->block_size;   //移动空闲区后的已分配区    
            }   
        }   
   
        if(p->state == 0 && flag == 1)   //找到后面的空闲区,合并    
        {   
            p->start_address = p->start_address - q->block_size ;   
            p->block_size = p->block_size + q->block_size ;   
        }   
    }   
    L->state=1;
    L->block_size = 0;
    printf("紧凑后:\n");   
    Display();   
}   
   
//--------------------------------------------------------------    
void FirstAdapt()//首次适应算法    
{   
    int progress_size;   
    int success;                            //是否分配成功    
    int sum;                                //空闲区总大小    
    char y_n;   
    LinkList  p,q;   
    Display();   
                   
    printf("\n请输入进程需要的存储空间:\n");   
    scanf("%d",&progress_size);   
       
    if(progress_size <= 0)       printf("A wrong number!\n");   
    else    
    {   
        for(p = L;p != NULL;p = p->next)   
        {   
            if(progress_size <= p->block_size && p->state == 0)        //找到可用的空闲区    
            {   
                q = (LinkList)malloc(sizeof(Node));                 // q 分配后剩余的存储块（空闲区）    
   
                q->start_address = p->start_address + progress_size;     
                q->block_size = p->block_size - progress_size;   
                q->prior = p;   
                q->next  = p->next;   
                q->state = 0;   
   
                if(q->block_size != 0)   
                {   
                    p->next = q;   
                }   
                p->block_size = progress_size;               // p 指向已分配的块单元    
                p->state = 1;   
           
                success = 1;   
                break;   
            }   
            else continue;   
        }   
   
        if(success == 1)        //成功分配    
        {   
            Display();   
        }   
        else                    //暂时未能成功分配    
        {   
            sum = 0;   
            for(p = L;p != NULL;p = p->next )   
            {   
                if(p->state == 0)   
                    sum = sum + p->block_size ;          //计算总的空闲区大小    
            }   
            if(sum >= progress_size)   
            {   
                printf("\n存储区大小不足，是否紧凑?(Y/N)\n");   
                getchar();   
                scanf("%c",&y_n);   
                if(y_n == 'Y' || y_n == 'y')   
                    Tighten();  //执行紧凑    
            }   
            else    
                printf("\n存储区大小不足，分配失败\n");   
        }   
    }   
}//FirstAdapt    
//--------------------------------------------------------------    
void swap(LinkList p,LinkList q)//交换节点    
{   
    p->block_size = q->block_size ;   
    p->start_address = q->start_address ;   
    p->state = q->state ;   
}   
   
   
//--------------------------------------------------------------    
void SortFree(LinkList Free)        //空闲区排序(从小到大)    
{   
    LinkList p,q,t;   
   
    t = (LinkList)malloc(sizeof(Node));   
   
    for(p = Free->next;p != NULL;p = p->next )   
    {   
        q = p;   
        for(;q != NULL;q = q->next )   
            if(q->block_size < p->block_size )   
            {   
                swap(t,q);   
                swap(q,p);   
                swap(p,t);   
            }   
    }   
}   
//--------------------------------------------------------------    
void EvaluateLink()   
{   
    LinkList p,q,r,s;   
       
    q = Free;   
    s = Assigned;   
       
    for(p = L;p != NULL;p = p->next)   
    {   
        if(p->state == 0)                        //查找 L 中空闲分区    
        {   
            r = (LinkList)malloc(sizeof(Node));   
   
            r->start_address = p->start_address;   
            r->block_size = p->block_size ;   
            r->state = p->state ;   
            r->next = NULL;   
   
            q->next = r;   
            q->next->prior = q;   
            q = q->next ;   
        }   
   
        else if(p->state == 1)                   //查找 L 中已分配分区    
        {   
            r = (LinkList)malloc(sizeof(Node));   
               
            r->start_address = p->start_address ;   
            r->block_size = p->block_size ;   
            r->state = p->start_address ;   
            r->next = p->next;   
   
            s->next = r;   
            s->next->prior = s;   
            s = s->next;   
        }   
    }   
}   
//-------------------------//最佳适应算法-------------------------------------    
void BestAdapt()        
{   
    int progress_size;  //新增进程所需空间大小    
    int success;        //是否分配成功    
    int sum;            //空闲区总大小    
    char y_n;   
    LinkList p,q,r;   
    LinkList A,F;   
   
    Display();   
   
    EvaluateLink();   
   
    SortFree(Free);     //空闲区链表排序    
   
    printf("\n请输入进程需要的存储空间:\n");   
    scanf("%d",&progress_size);   
   
    A = Assigned;   
    F = Free;   
   
    if(progress_size <= 0) printf("A wrong number\n");   
    else   
    {   
        for(p = Free->next;p != NULL;p = p->next)   
        {   
            if(progress_size <= p->block_size)   
            {   
                q = (LinkList)malloc(sizeof(Node));         // q 分配后剩余的空闲块    
       
                q->start_address = p->start_address + progress_size;     
                q->block_size = p->block_size - progress_size;   
                q->prior = p;   
                q->next  = p->next;   
                q->state = 0;   
       
                p->next = q;   
                p->block_size = progress_size;               // p 指向已分配的块单元    
                p->state = 1;   
       
                p->next = Assigned->next ;   
                A->next = p;   
       
                q->next = Free->next;   
                F->next = q;   
   
                success = 1;   
   
                for(r = L;r != NULL;r = r->next )   
                {   
                    if(r->start_address == p->start_address )   
                    {   
                        r->start_address = p->start_address ;   
                        r->block_size = p->block_size ;   
                        r->state = 1;   
   
                        q->next = r->next ;   
                        r->next = q;   
                    }   
                }   
                break;   
            }   
            else continue;   
        }   
   
        if(success == 1)   
        {   
            Display();   
        }   
        else   
        {   
            sum = 0;   
            for(p = L;p != NULL;p = p->next )   
            {   
                if(p->state == 0)   
                    sum = sum + p->block_size ;          //计算总的空闲区大小    
            }   
            if(sum >= progress_size)   
            {   
                printf("\n存储区大小不足，是否紧凑?(Y/N)\n");   
                getchar();   
                scanf("%c",&y_n);   
                if(y_n == 'Y' || y_n == 'y')   
                    Tighten();  //执行紧凑    
            }   
            else    
                printf("\n存储区大小不足，分配失败\n");   
        }   
    }   
}//BestAdapt    
   
//--------------------------------------------------------------    
void Callback()                     //存储区回收函数    
{   
    int i;   
    int x;   
    LinkList p;   
   
    printf("已经分配区有:\n");   
    for(i = 0,p = L;p != NULL;p = p->next)       //显示已分配区    
    {   
        if(p->state == 1)   
        {          
            printf("%d.\t(%3d,%3d)\n",i+1,p->start_address ,p->start_address+p->block_size);   
            i++;   
        }   
    }   
   
    printf("请输入需要撤消的进程编号:\n");   
    scanf("%d",&x);   
   
    for(i = 0,p = L;p != NULL;p = p->next)   
    {   
        if(p->state == 1) i++;   
        if(i == x)   
        {   
            p->state = 0;                        //回收后状态位置    
            break;   
        }   
    }   
   
    for(p = L;p->next != NULL;)         
    {   
        if(p->state == 0 && p->next->state == 0)   
        {   
            p->block_size = p->block_size + p->next->block_size ;       //改变空闲块大小    
            p->next = p->next->next ;   
            if(p->next != NULL)   
            {   
                p->next->prior = p;   
            }   
        }   
        else    p = p->next ;   
    }   
   
    Display();   
}//回收算法    
  //--------------页面置换算法之最佳置换算法-------------------
int p[P],y[W],c[P]={0};
int m,n,l,n2,hit=0;
int ding=0;

void init()                        //输入物理块，页的信息
{
	int i;
	printf("1.请输入物理块数");
	scanf("%d",&m);
	printf("2.请输入页数");
	scanf("%d",&n);
	printf("输入页号:\n");
	for(i=0;i<n;i++)
		scanf("%d",&y[i]);
}
void  initial_phy()                          //物理块的初始化，先将物理块装满
{
	int i,q=0,sign0;
	p[0]=y[0];
	ding++;
	sign0=0;
	n2=1;
	for(i=1;i<m;i++)
	{
		for(int t=0;t<i;t++)          //判断将要装入的物理块是否与物理块中的内容相同
		{
			if(p[t]==y[n2])
			{
				sign0=1;
				break;
			}
		}
	printf("\n物理块内容：\n");
				for(int j=0;j<i;j++)   //显示当前物理块内容
		{
			
		    printf("%d  ",p[j]);
		}

		if(sign0)                   
		{
			printf("\n命中\n");
			hit++;
			i--;
			n2++;
		}
		else                     //判断与已存在物理块内容不同，进行装入
		{
			p[i]=y[n2];
			ding++;
			n2++;
		}
		sign0=0;
		
      
	}
	printf("\n物理块内容:\n");