/*
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);
}
}
}