/*
Title: 首次適應(yīng)算法
Author: Brian
Date: 2010/05/31
*/
#include <iostream>
#include <cstdlib> // system()
using namespace std;
typedef struct SNode { // Space Node
int start,end; // 起始，結(jié)束
int length; // 長(zhǎng)度大小
struct SNode *next; // 指向下一結(jié)點(diǎn)的指針
}* SP;
SP space=(SP)malloc(sizeof(SNode)); // 全局變量，內(nèi)存空間頭結(jié)點(diǎn)
void DispSpace() { // 顯示內(nèi)存空間分配情況
SP p=space;
cout<<"\n 空閑區(qū)說(shuō)明表 \n"
<<"---地址--長(zhǎng)度---\n";
while (p->next)
{
cout<<" "<<p->next->start
<<" "<<p->next->length<<endl;
p=p->next;
}
cout<<"----------------\n";
}
void Initial() { // 初始化說(shuō)明表
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; // 指導(dǎo)書(shū)上的作業(yè)分配
space->next=p; // 與頭結(jié)點(diǎn)連接
p->next=q;
q->next=NULL;
DispSpace();
}
void Allocation(int len) { // 分配內(nèi)存給新作業(yè)
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) { // 回收內(nèi)存
SP p=space,q=p->next,r; // 開(kāi)始地址和長(zhǎng)度
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)) { // 上鄰區(qū)
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ū)相接
q->start=sta;
q->length=q->end-sta;
return;
}
else if ((p->end == sta) && (q->start < en)) { // 下鄰區(qū)
p->end=en;
p->length=en-p->start;
return;
}
else if (p->end==sta && q->start==en) { // 鄰區(qū)相接
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<<"現(xiàn)在分配大小為 6K 的作業(yè) 4 申請(qǐng)裝入主存: ";
Allocation(6); // 分配時(shí)參數(shù)只有長(zhǎng)度
//--------指導(dǎo)書(shū)測(cè)試數(shù)據(jù)演示----------
cout<<"現(xiàn)回收作業(yè) 3 (起址10,長(zhǎng)度4)\n";
CallBack(10,4);
DispSpace();
cout<<"現(xiàn)回收作業(yè) 2 (起址26,長(zhǎng)度6)\n";
CallBack(26,6);
DispSpace();
//---------------演示結(jié)束-------------
system("pause");
}
/*
Title: 位示圖法
Author: Brian
Date: 2010/05/25
*/
#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct PNode { // 進(jìn)程PCB
struct PNode *next; // 后向指針
char name[12]; // 進(jìn)程名
int *PT; // 頁(yè)表
int size; // 進(jìn)程所需要的空間
}* Proc;
Proc H=(Proc)malloc(sizeof(PNode)); // 進(jìn)程頭結(jié)點(diǎn)
Proc CurrJob; // 當(dāng)前進(jìn)程指針
int BG_DEF[8][8] = { // 指導(dǎo)書(shū)上的初始條件
{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; // 指導(dǎo)書(shū)上初始條件的空閑塊數(shù)
int BG[8][8]={0}; // 用戶(hù)自定義位示圖
int FREE=64; // 用戶(hù)自定義空閑塊數(shù)
void DispBG(int flag) // 顯示當(dāng)前位示圖 F
{
cout<<"\n字節(jié)號(hào)\\位數(shù)\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() // 用戶(hù)選取坐標(biāo)初始化內(nèi)存塊
{
DispBG(1);
cout<<"\n請(qǐng)輸入您想要分配的塊號(hào)坐標(biāo),以 -1 -1 結(jié)束:\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) //內(nèi)存分配
{
int i,j,k,kflag=1; // 進(jìn)程個(gè)數(shù)
Proc s=H;
s=s->next=(Proc)malloc(sizeof(PNode));
cout<<"請(qǐng)輸入進(jìn)程名和內(nèi)存大小: ";
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) // 用戶(hù)自定義位示圖
{
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 // 實(shí)驗(yàn)指導(dǎo)書(shū)位示圖
{
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) //內(nèi)存回收
{
char name[12];
cout<<"請(qǐng)輸入需要回收的進(jìn)程名: ";
cin>>name;
Proc p=H->next,q=H;
while (p)
{
if (strcmp(name,p->name)==0) // 刪除進(jìn)程,回收內(nèi)存
{
for(int i=0; i<p->size; i++) // 修改該進(jìn)程位示圖
{
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; // 刪除進(jìn)程結(jié)點(diǎn)
free(q);
cout<<"回收成功!\n";
return;
}
p=p->next;
q=q->next;
}
cout<<"無(wú)此進(jìn)程,回收內(nèi)存失敗!\n";
}
void DispPT()
{
char name[12];
cout<<"請(qǐng)輸入要打印頁(yè)表的進(jìn)程名: ";
cin>>name;
Proc p=H->next;
while (p)
{
if (strcmp(name,p->name) == 0)
{
cout<<" 塊號(hào)\n"
<<"--------\n";
for (int i=0; i<p->size; i++)
cout<<" "<<p->PT[i]<<endl;
cout<<"--------\n";
return;
}
p=p->next;
}
cout<<"該進(jìn)程不存在!\n";
}
void Welcome()
{
cout<<"----------位示圖法---------\n"
<<" 1. 新進(jìn)程內(nèi)存分配\n"
<<" 2. 舊進(jìn)程內(nèi)存回收\(chéng)n"
<<" 3. 打印進(jìn)程頁(yè)表\n"
<<" 4. 打印位示圖\n"
<<" 5. 退出系統(tǒng)\n"
<<"-----------------------------------\n";
}
void main()
{
H->next=NULL;
int flag;
cout<<"內(nèi)存初始化方式: 1.自定義 2.指導(dǎo)書(shū)\n"
<<"請(qǐng)選擇: ";
cin>>flag;
if (flag==1) Initial(); // 用戶(hù)選取坐標(biāo)初始化內(nèi)存塊
int choice;
while (1)
{
Welcome();
cin>>choice;
switch (choice)
{
case 1: Allocation(flag); break; // 進(jìn)行一次分配內(nèi)存工作
case 2: CallBack(flag); break; // 回收用戶(hù)指定進(jìn)程的內(nèi)存
case 3: DispPT(); break; // 打印用戶(hù)指定進(jìn)程的頁(yè)表
case 4: DispBG(flag); break; // 打印用戶(hù)指定位示圖
case 5: cout<<"\n退出成功!\n"; system("pause"); exit(1);
}
}
}