/*
Title: 首次适应算法
Author: Brian
Date: 2010/05/31
*/
#include <iostream>
#include <cstdlib> // system()
using namespace std;
typedef struct SNode { // Space Node
int start,end; // 起始，结束
int length; // 长度大小
struct SNode *next; // 指向下一结点的指针
}* SP;
SP space=(SP)malloc(sizeof(SNode)); // 全局变量，内存空间头结点
void DispSpace() { // 显示内存空间分配情况
SP p=space;
cout<<"\n 空闲区说明表 \n"
<<"---地址--长度---\n";
while (p->next)
{
cout<<" "<<p->next->start
<<" "<<p->next->length<<endl;
p=p->next;
}
cout<<"----------------\n";
}
void Initial() { // 初始化说明表
SP p,q;
p=(SP)malloc(sizeof(SNode));
q=(SP)malloc(sizeof(SNode));
p->start=14; p->length=12; p->end=26;
q->start=32; q->length=96; q->end=128; // 指导书上的作业分配
space->next=p; // 与头结点连接
p->next=q;
q->next=NULL;
DispSpace();
}
void Allocation(int len) { // 分配内存给新作业
SP p=space,q;
while (p->next) {
if (p->next->length < len)
p=p->next;
else if (p->next->length > len) {
p->next->start=p->next->start+len;
p->next->length=p->next->length-len;
cout<<"分配成功!\n";
DispSpace(); return;
}
else {
q=p->next;
p->next=q->next;
cout<<"分配成功!\n";
DispSpace(); return;
}
}
cout<<"分配失败!\n";
DispSpace(); return;
}
void CallBack(int sta,int len) { // 回收内存
SP p=space,q=p->next,r; // 开始地址和长度
p->end=0;
int en=sta+len;
while (q) {
if (sta == 0) { // 初始地址为0
if (en == q->start) { // 正好回收
q->start=0;
q->length=q->end;
return;
}
else {
r=(SP)malloc(sizeof(SNode));
r->start=sta; r->length=len; r->end=en;
p->next=r;
r->next=q;
return;
}
}
else if ((p->end < sta) && (q->start > en)) { // 上邻区
r=(SP)malloc(sizeof(SNode));
r->start=sta; r->length=len; r->end=en;
p->next=r;
r->next=q;
return;
}
else if ((p->end < sta) && (q->start == en)) { // 邻区相接
q->start=sta;
q->length=q->end-sta;
return;
}
else if ((p->end == sta) && (q->start < en)) { // 下邻区
p->end=en;
p->length=en-p->start;
return;
}
else if (p->end==sta && q->start==en) { // 邻区相接
p->end=q->end;
p->length=p->end-p->start;
p->next=q->next;
return;
}
else {
p=p->next;
q=q->next;
}
}
}
void main() {
Initial();
cout<<"现在分配大小为 6K 的作业 4 申请装入主存: ";
Allocation(6); // 分配时参数只有长度
//--------指导书测试数据演示----------
cout<<"现回收作业 3 (起址10,长度4)\n";
CallBack(10,4);
DispSpace();
cout<<"现回收作业 2 (起址26,长度6)\n";
CallBack(26,6);
DispSpace();
//---------------演示结束-------------
system("pause");
}
/*
Title: 位示图法
Author: Brian
Date: 2010/05/25
*/
#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct PNode { // 进程PCB
struct PNode *next; // 后向指针
char name[12]; // 进程名
int *PT; // 页表
int size; // 进程所需要的空间
}* Proc;
Proc H=(Proc)malloc(sizeof(PNode)); // 进程头结点
Proc CurrJob; // 当前进程指针
int BG_DEF[8][8] = { // 指导书上的初始条件
{1,1,0,0,1,1,1,0},
{0,1,0,1,0,1,0,0},
{0,0,0,0,0,0,0,0},
{1,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0}
};
int FREE_DEF = 54; // 指导书上初始条件的空闲块数
int BG[8][8]={0}; // 用户自定义位示图
int FREE=64; // 用户自定义空闲块数
void DispBG(int flag) // 显示当前位示图 F
{
cout<<"\n字节号\\位数\t0\t1\t2\t3\t4\t5\t6\t7\n";
for(int i=0; i<8; i++)
{
cout<<'\t'<<i;
for(int j=0; j<8; j++)
{
if (flag==1)
cout<<"\t"<<BG[i][j];
else cout<<"\t"<<BG_DEF[i][j];
}
cout<<endl;
}
cout<<endl;
}
void Initial() // 用户选取坐标初始化内存块
{
DispBG(1);
cout<<"\n请输入您想要分配的块号坐标,以 -1 -1 结束:\n";
int i,j;
while (1)
{
cin>>i>>j;
if (i+j==-2) // i==-1 && j==-1
break;
BG[i][j]=1;
FREE--;
}
DispBG(1);
}
void Allocation(int flag) //内存分配
{
int i,j,k,kflag=1; // 进程个数
Proc s=H;
s=s->next=(Proc)malloc(sizeof(PNode));
cout<<"请输入进程名和内存大小: ";
cin>>s->name>>s->size;
if (flag==1)
{
if (s->size > FREE)
{
cout<<"空间不足,分配失败!";
return;
}
FREE-=s->size;
}
else {
if (s->size > FREE_DEF) {
cout<<"空间不足,分配失败!";
return;
}
FREE_DEF-=s->size;
}
s->PT=new int[s->size]; // 新建PT表
k=0;
if (flag==1) // 用户自定义位示图
{
for (i=0; i<8 && kflag; i++)
for (j=0; j<8 && kflag; j++)
{
if (!BG[i][j])
{
BG[i][j]=1;
FREE--;
s->PT[k++]=8*i+j;
if (k==s->size)
{
cout<<"分配完成!\n";
kflag=0;
}
}
}
}
else // 实验指导书位示图
{
for (i=0; i<8 && kflag; i++)
for (j=0; j<8 && kflag; j++)
{
if (!BG_DEF[i][j])
{
BG_DEF[i][j]=1;
FREE_DEF--;
s->PT[k++]=8*i+j;
if (k==s->size)
{
cout<<"分配完成!\n";
kflag=0;
}
}
}
}
s->next=NULL;
}
void CallBack(int flag) //内存回收
{
char name[12];
cout<<"请输入需要回收的进程名: ";
cin>>name;
Proc p=H->next,q=H;
while (p)
{
if (strcmp(name,p->name)==0) // 删除进程,回收内存
{
for(int i=0; i<p->size; i++) // 修改该进程位示图
{
int m=p->PT[i]/8;
int n=p->PT[i]%8;
if (flag==1)
{
BG[m][n]=0;
FREE++;
}
else {
BG_DEF[m][n]=0;
FREE_DEF++;
}
}
q->next=p->next; // 删除进程结点
free(q);
cout<<"回收成功!\n";
return;
}
p=p->next;
q=q->next;
}
cout<<"无此进程,回收内存失败!\n";
}
void DispPT()
{
char name[12];
cout<<"请输入要打印页表的进程名: ";
cin>>name;
Proc p=H->next;
while (p)
{
if (strcmp(name,p->name) == 0)
{
cout<<" 块号\n"
<<"--------\n";
for (int i=0; i<p->size; i++)
cout<<" "<<p->PT[i]<<endl;
cout<<"--------\n";
return;
}
p=p->next;
}
cout<<"该进程不存在!\n";
}
void Welcome()
{
cout<<"----------位示图法---------\n"
<<" 1. 新进程内存分配\n"
<<" 2. 旧进程内存回收\n"
<<" 3. 打印进程页表\n"
<<" 4. 打印位示图\n"
<<" 5. 退出系统\n"
<<"-----------------------------------\n";
}
void main()
{
H->next=NULL;
int flag;
cout<<"内存初始化方式: 1.自定义 2.指导书\n"
<<"请选择: ";
cin>>flag;
if (flag==1) Initial(); // 用户选取坐标初始化内存块
int choice;
while (1)
{
Welcome();
cin>>choice;
switch (choice)
{
case 1: Allocation(flag); break; // 进行一次分配内存工作
case 2: CallBack(flag); break; // 回收用户指定进程的内存
case 3: DispPT(); break; // 打印用户指定进程的页表
case 4: DispBG(flag); break; // 打印用户指定位示图
case 5: cout<<"\n退出成功!\n"; system("pause"); exit(1);
}
}
}