Brian Warehouse

Some birds aren`t meant to be caged, their feathers are just too bright... ...
posts - 40, comments - 16, trackbacks - 0, articles - 1

实验二代码 首次适应法 位示图法

Posted on 2010-08-17 13:02 Brian 阅读(1457) 评论(0)  编辑 收藏 引用 所属分类: OS
/*
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);
        }
    }
}

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理