?? 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");
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -