模拟操作系统的设计与实现

**大学计算机科学与技术学院

——操作系统课程设计

把I告书

课题名模拟操作系统的设计与实现

班..级

姓名

学号

指导教师

日.期

一、实验目的

总体任务：设计一个模拟操作系统，能够完成①处理机管理②死

锁的防止③主存的可变分区管理④虚拟存储器管理⑤磁盘空间

的管理⑥磁盘的驱动调度管理，这6项功能。

①处理机管理〔进程调度管理〕：通过对进程调度算法的模

拟，进一步理解进程的根本概念，加深对进程运行状态和

进程调度过程以及调度算法的理解。

②死锁的防止：模拟进程的资源分配算法，了解死锁的产生

和防止的方法，主要通过银行家算法来进行死锁的防止。

③主存的可变分区管理：通过对可变分区存储管理的模拟，

深入了解可变分区存储管理的原理，加深对如何实现主存

空间的分配和回收的认识。

④虚拟存储器管理：能够实现地址重定位，通过模拟LRU、OPT、

FIFO等缺页调度算法，加深对请求分页管理的理解。

⑤磁盘空间的管理：通过位示图和空白文件目录来实现磁盘

空间的管理，深入了解磁盘空间的管理的方法和原理。

⑥磁盘的驱动调度管理：通过模拟先来先效劳、最短查找时

间优先以及电梯调度算法，来实现磁盘的驱动调度，加深

对于这3种调度算法的理解。

二、设备与环境

1.硬件设备：PC机一台。

2.软件环境：安装Windows操作系统或者Linux操作系统，并

安装相关的程序开发环境，如C\C++\Java等编程语言环境。

三、设计原理

㈠处理机管理〔进程调度管理〕：

1.先来先效劳算法〔FCFS〕

先来先效劳算法按照作业进入系统后备作业队列的先后次序

挑选作业，先进入系统的作业将优先被挑选进入主存，创立用户

进程，分配所需资源，然后移入就绪队列。

2.最短作业优先算法〔SJF〕

最短作业优先算法以进入系统的作业所要求的CPU运行时间

的长短为标准，总是选取预计计算时间最短的作业投入运行。

3.时间片轮转调度算法〔RR〕

循环轮转调度算法的具体原理是：每个进程被分配一个时间

片，即该进程允许运行的时间。就绪的进程都存放在一个就绪链

表中，队首的进程将获得时间片。如果在时间片结束时进程还在

运行，那么CPU将被剥夺并分配给下一个进程。调度程序所要做

的就是维护一张就绪进程列表，当进程用完它的时间片后，它被

移到队列的末尾。

㈡死锁的防止：

1.银行家算法：其思路是先对用户提出的请求进行合法性检

查，即检查请求的是否大于需要的，是否不大于可利用的。假设

请求合法，那么进行试分配。最后对试分配后的状态调用平安性

检查算法进行平安性检查。假设平安，那么分配；否那么，不分

配，恢复原来状态，拒绝申请。

㈢主存的可变分区管理：

1,可变分区存储管理：又称为动态分区模式，按照作业的大

小来划分分区，但划分的时间、大小、位置都是动态的。

㈣虚拟存储器管理：

1.最近最少使用页面替换算法〔LRU〕:

在LRU算法中，被淘汰的页面是在最近一段时间内最久未被

访问的那一页。

2.最正确页面替换算法〔OPT〕：

它是由Belady于1966年提出的一种理论上的算法。其所选

择的被淘汰页面，将是以后永不使用的或者是在最长（未来）时间

内不再被访问的页面。采用最正确置换算法，通常可保证获得最

低的缺页率。

3.先进先出页面替换算法〔FIFO〕:

基于程序总是按线性顺序来访问物理空间这一假设，总是淘

汰最先调入主存的页面，即淘汰在主存中驻留时间最长的页面，

认为驻留时间最长的页不再使用的可能性较大。

㈤磁盘空间的管理：

1.位示图：位示图用假设干个字构成，每一位对应一个z兹盘

块，"1”表示占用，“0”表示空闲。

2.空白文件目录：空白文件目录表用来对整个磁盘的未用空

间进行管理，每个空白文件占用其中的一个表目。

（六）磁盘的驱动调度管理：

1.先来先效劳算法〔FCFS〕:

这是一种比拟简单的磁盘调度算法。它根据进程请求访问

磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个

进程的请求都能依次得到处理，不会出现某一进程的请求长期得

不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访

问请求比拟多的情况下，此算法将降低设备效劳的吞吐量，致使

平均寻道时间可能较长，但各进程得到效劳的响应时间的变亿幅

度较小。

2.最短查找时间优先算法〔SSTF〕：

该算法选择这样的进程，其要求访问的磁道与当前磁头所

在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到

比拟好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对

用户的效劳请求的响应时机不是均等的，因而导致响应时间的变

化幅度很大。在效劳请求很多的情况下，对内外边缘磁道的请求

将会无限期的被延迟，有些请求的响应时间将不可预期。

3.电梯调度算法：

每次总是选择沿移动臂的移动方向最近的那个柱面，假设

同一柱面上有多个请求，还需进行旋转优化。如果当前移动方向

上没有访问请求时，就改变移动臂的移动方向，然后处理所遇到

的最近的I/O请求。

四、详细设计

㈠处理机管理〔进程调度管理〕：

1.定义两个结构体worktime和jcb,具体功能分别如下:

structworktime

(

fIoatTb；//作业运行时刻

fIoatTc;〃作业完成时刻

fIoatTi;〃周转时间

fIoatWi;//带权周转时间

)；

structjcb

(

charname[10];〃作业名

fIoatsubtime;〃作业到达时间

fIoatruntime；//作业所需的运行时间

charresource;〃所需资源

floatRp;〃后备作业响应比

charstate;〃作业状态

intworked_time：〃已运行时间

structworktimewt;

intneedtime;//要求运行时间

intflag;〃进程结束标志

structjcb*link;〃链指针

)

2.完整的源程序如下:

#incIude<iostream>

#incIude<stdio.h>

#incIude<stdIib.h>

#incIude<conio.h>

usingnamespacestd;

#definegetpch(type)(type*)maIIoc(sizeof(type))//为进程创立一个空间

structworktime{

fIoatTb;〃作业运行时刻

fIoatTc;〃作业完成时刻

fIoatTi;〃周转时间

fIoatWi;//带权周转时间

)；

structjcb{

charname[10];〃作业名

fIoatsubtime;//作业到达时间

floatruntime;〃作业所需的运行时间

charresource;〃所需资源

floatRp;〃后备作业响应比

charstate;〃作业状态

intworked_time;〃已运行时间

structworktimewt;

intneed_time;//要求运行时间

intflag;〃进程结束标志

structjob*link;//链指针

}*ready=NULL,*p;

typedefstructjcbJCB;

floatT=0;

intN;

JCB*front,*rear;〃时间轮转法变量

voidsort()

JCB*first,*second；

intinsert=0;〃插入数

if((ready-NULL)||((p->subtime)<(ready->subtime)))

{

p->Iink=ready;

ready二p;

T=p->subtime;

p->Rp=1；

1

eIse

{

first=ready:

second=first->link;

while(second!=NULL)

(

if((p->subtime)<(second->subtime))

p->ink=second;

first->Iink=p;

second二NULL；

insert=1;

)

eIse

(

first=first->link;

second=second->Iink;

)

)

if(insert二二0)first->link=p;

)

)

voidSJFget()//最短作业优先算法

(

JCB*front,*mintime,*rear;

intipmove=0;

mintime=ready;

rear=mintime->link;

while(rear!=NULL)

(

if

((rear!=NULL)&&(T>=rear->subtime)&&(mintime->runtime)>(rear->runtime)

)

(

front=mintime;

mintime二rear;

rear=rear>link;

ipmove=1;

)

eIse

rear=rear->link;

)

if(ipmove~1)

(

front->Iink=mintime->link;

mintime->Iink=ready;

)

ready=mintime;

)

voidcreatJCB()//为每个作业创立一个JCB并初始化形成一个循环链队列

(

JCB

inti=0;

I=(JCB*)maIIoc(sizeof(JCB));

cout«"\n请输入作业的个数："；

scanf("%d",&N);

printf("\n作业号No.%d:\n”,i);

printf("\n请输入作业的名字：“);

scanf("%s",l->name);

printf("\n请输入作业的时间:");

scanf("%d",&l->need_time);

Instate二'r';〃作业初始状态为就绪

|->worked_time=0;

I->Iink=NULL;

l->flag=O;

front=l;

for(i=1;i<N;i++)

{

p=(JCB*)maIIoc(sizeof(JCB));

printf("\n作业号No.%d:\n",i);

printf("\n请输入作业的名字:");

scanf("%s",p->name);

printf("\n请输入作业的时间:");

scanf("%d",&p->need_time);

p->state='r1;

p->worked_time=0;

p->flag=0;

l->link=p；

I=I->Iink;

)

rear=I;rear〉Iink=front;

)

voidoutput()//进程瑜出函数

(

intj;

printf("nameruntimeneedtimestate\n");

for(J=1;j«N;J++)

{printf("%-4s\t%-4d\t%-4d\t%-c\n",front->name,front->worked_time,

front->need_time,front->state);

front=front->Iink;

1

printf("\n");

)

intjudge(JCB*p)〃判断所有进程运行结束

(

intflag=1,i;

for(i=0;i<N;i++)

I

if(p->state'='e")

(

flag=0;

break;)

p=p->Iink;

)

returnflag;

1

voidRRget()//时间片轮转算法

(

JCB*s;

intfIag1=0;

s=(JCB*)malIoc(sizeof(JCB))；

s=front;

printf("\n\n");

output();

printf("请榆人任意一键继续\n”)；

getch();〃按，壬意键继续

s=front;

while(fIag1!=1)

(

if(s->state==,r')

(

s->worked_time++;

s->need_time—;

if(s>need_time==0)

s->state='e';

output0;

printf(-请输入任意一键继续...\n");

getch():

)

if(s->state='e'&&s->fIag=0)

(

printf('进程％s已经运行完成！\n\n",s->name);

s->fIag=1;

)

s=s->link;

flag仁judgefs);

)

printf("\n");

)

voidinput()

(

inti,num;

printf("\n请输入作业的个数：")；

scanf("%d",&num);

for(i=0;i<num;i-+)

{

printf("\n作业号No.%d:\n",i);

p=getpch(JCB)；

printf("\n瑜入作业名：")；

scanf("%s",p->name);

printf("\n瑜入作业到达时刻：")；

scanf("%f",&p->subtime);

printf("\n瑜入作业运行时间：")；

scanf("%f",&p->runtime);

printf("\n");

p->state='w';

p->link=NULL;

sortO;

1

)

intspace()

(

int1=0;JCB*jr=ready;

while(jr!=NULL)

(

I++；

jr=jr->link:

］

return(I);

)

voiddisp(JCB*jr,intseIect)

(

if(seIect==3)printf('An作业到达时间效劳时间响应比

运行时刻完成时刻周转时间带权周转时间\n”)；

eIseprintf("\n作业到达时间效劳时间运行时刻完成时刻

周转时间带权周转时间\n”)；

printf("%s\t",jr->name);

printf("%.2f\t",jr->subtime);

printf("%.2f\tu,jr->runtime);

if(seIect==3&&p==jr)printf("%.2fjr->Rp);

if(p==jr){

printf("%.2f\t",jr->wt.Tb);

printf("%.2f",jr->wt.Tc);

printf("%.2f\t",jr->wt.Ti);

printf("%.2f",jr->wt.Wi);

)

printf("\n");

)

intdestroy()

(

printf("\n作业［%s］已完成.\n",p->name);

free(p);

return(1);

1

voidcheck(intselect)

JCB*jr;

printf("\n****当前正在运行的作业是:%s",p->name);

disp(p,seIect);

jr=ready;

printf("\n****当前就绪队列状态为：\n");

whiIe(Jr!二NULL)

(

jr->Rp=(jr->runtime+T-jr->subtime)/jr->runtime;

disp(jr,seIect);

jr=jr->link:

1

destroy();

}

voidrunning(JCB*jr)

(

if(T>=jr->subtime)jr->wt.Tb=T;

eIsejr->wt.Tb=jr->subtime;

jr->wt.Tc=jr->wt.Tb+jr->runtime;

jr->wt.Ti=jr->wt.Tc-jr->subtime;

jr->wt.Wi=jr->wt.Ti/jr->runtime;

T=jr->wt.Tc;

1

intmain()

intselect=0,Ien,h=0;

fIoatsumTi=0,sumWi=0;

printf("\t**x**************\n"),

printf("请选择作业调度算法的方式:\n");

printf("\t1.先来先效劳2.最短作业优先3.时间片轮转法\n\n");

printf("\t**x**************\n")；

printf(”请输入作业调度算法序号(1-3):”):

scanf("%d",&seIect);

if(select==3)

{creatJCB()；

RRget()；)

eIse

input();

Ien=space();

whiIe((len!=0)&&(ready!=NULL))

h++;

printf("\n执行第％d个作业\n",h);

p=ready;

ready=p->link;

p->link=NULL;

p->state=,R1;

running(p);

sumTi+=p->wt.Ti;

sumWi+=p->wt.Wi;

check(seIect);

if(seIect==2&&h<Ien-1)SJFget();

printf("\n按任意一键继续");

getchar();

getchar();

)

printf("\n\n作业已经完成.\n")；

printf("\t此组作业的平均周转时间：%.2f\n",sumTi/h);

printf("\t此组作业的带权平均周转时间:%.2f\n",sumWi/h);

getchar();)

return0;

)

㈡死锁的防止：

1.定义进程控制块pcb的类，用于存放和处理进程的相关信息,

如下：

cIasspcb

(

pubIic:

intp_pid;

intp_stat;

intp_appIy;

intp_occupy;

boolp_issuc;

intp_require;

pcb(intid,intrequire)

(

p_pid=id;

p_require=require;

p_stat=TASK_RUNNING;

p_occupy=0;

p_issuc=faIse;

p_apply=0;

)

friendostream&operator«(ostream&cout,constpcb&p)

cout«p.p_pid«'\t'«p.p_stat«'\t'«p.p_require«'\t'«p.p_occup

y«endI;

returncout;

）；

2.完整的源程序如下:

#incIude<iostream>

#incIude<vector>

#include<iterator>

#incIude<fstream>

usingnamespacestd;

constintTASK_RUNNING=O;

constintTASKSUCCEEDS;

constintTASK_WAITING=2；

ofstreamff("result.txt");

constintRMAX=10;〃系统拥有的最大资源数

constintPMAX=4;〃系统运行的最大进程数

intRcs_Ieft=RMAX;

cIasspcb

(

pubIic:

intp_pid;

intp_stat;

intp_appIy;

intp_occupy;

booIp_issuc;

intp_require;

pcb(intid,intrequire)

(

p_pid二id;

p_require=require;

p_stat=TASK_RUNNING;

p_occupy=0;

p_issuc=faIse;

p_apply=0;

friendostream&operator«(ostream&cout,constpcb&p)

cout«p.p_pid«'\t'«p.p_stat«'\t'«p.p_require«'\t'«p.p_occup

y«endI;

returncout;

)

)；

voidrand(vector<pcb>&pgrp);

voidbanker(vector<pcb>&pgrp);

〃定义的子函数

voidwakeup(vector<pcb>&pgrp,intavaiIable);

booIisFinished(vector<pcb>&pgrp);

booIisSafeState(vector<pcb>&pgrp,intavaiable);

vector<pcb>::iteratorgetFirstRunningProcess(vector<pcb>&pgrp);

voidreadAppIy(vector<pcb>::iteratorproc);

intmain()

(

vector<pcb>pgrp;

//输入各进程申请的资源总量，以及初始化各个进程

cout«"ENTERTHEMAXNUMBERFORTHEREQUESTEDRESOURCE："«endI;

cout«"processID\tREQUESTED"«endI;

ff«"ENTERTHEMAXNUMBERFORTHEREQUESTEDRESOURCE:"«endI;

ff«"processID\tREQUESTED"«endI;

intqty;

for(inti(1)；i<=PMAX;i++)

(

do

(

cout«"process"«i«"\t";

ff«"process"«i«"\t";

cin»qty;

cout«i«endI;

ff«i«endl;

}while(qty<1||qty>RMAX);

pgrp.insert(pgrp.begin(),pcb(i,qty));

)

〃选择资源分配算法

cout«"PLEASESELECTAALOGRITHM："«endl

«"Random(R)orBanker(B)"«endI

«"ANYOTHERKEYTOQUIT"«endl;

ff«"PLEASESELECTAALGORITHM："«endI

«"Random(R)orBanker(B)"«endI

«"ANYOTHERKEYTOQUIT"«endI«""；

charchoice;

cin»choice;

ff«choice«endI;

if(choice=="R'||choice=='r')

rand(pgrp);

if(choice=='B'||choice==,b')

banker(pgrp);

return(0);

)

voidrand(vector<pcb>&pgrp)

(

vector<pcb>::iteratorcurrent;

cout«"H0WSTARTRANDOMALOGRITHM-"«endl;

ff«"H0WSTARTRANDOMALOGRITHM-"«endl；

for(；；)

(

//seIectaTASK_RUNNIGprocess,maybedifferentfromtheformer

one;

current=getFirstRunningProcess(pgrp);

if(current==NULL)

(

//norunningprocess,end

if(isFinished(pgrp))

(

cout«"SYSTEMRUNNINGSUCCEED!!"«endI;

ff«"SYSTEMRUNNINGSUCCEED!!"«endI;

return;

)

cout«"SYSTEMLOCKED!!!"«endI；

ff«"SYSTEMLOCKED!!!"«endl:

return;

1

)

if(current->p_appIy二二0)

readAppIy(current);

//判断能否满足进程的资源请求

if(current->p_appIy>Rcs_Ieft)

{//appIytoomuch,pIeasewait…

current->p_stat=TASK_WAITING;

cout«endl«"theprocess"«current->p_pid«"iswaitting\n";

ff«endI«"theprocess"«current->p_pid«"iswaitting\n";

continue;

)

〃满足该进程当前的申请

cout«""«current->p_appIy«"resourcesareacceptedfor

process"

«current->p_pid«endI;

ff«""«current->p_appIy«"resourcesareacceptedfor

process"

«current->p_pid«endI;

cout«endI;

ff«endI;

Rcs_left-=current->p_appIy;

current->p_occupy+=current->p_appIy;

current->p_appIy=0;

//看该进程是否已满足最大资源请求

if(current->p_occupy<current->p_require)

(

pcbproc(*current);

pgrp.erase(current);//deIetecurrentandinsertintothe

end

pgrp.insert(pgrp.end(),proc);

continue;

)

//满足最大资源请求，进程成功完成，将其从进程队列删除

cout«endI«"process"«current->p_pid«"\thas

compIeted!!"«endI;

ff«endI«"process"«current->ppid«"hascompIeted!"«endI;

Rcs_left+=current->p_occupy;

current->p_occupy=0;

current->p_stat=TASK_SUCCEED;

pgrp.erase(current);

if(isFinished(pgrp))

(

cout«"SYSTEMRUNNINGSUCCEED!!"«endI;

ff«"SYSTEMRUNNINGSUCCEED!!"«endI;

return;

)

wakeup(pgrp,Rcs_Ieft);

)

)

voidbanker(vector<pcb>&pgrp)

(

vector<pcb>::iteratorcurrent;

intIength;

cout«"N0WSTARTBANKERALOGRITHM"«endl;

ff«"N0WSTARTBANKERALOGRITHM"«endI;

for(;;)

current=getFirstRunningProcess(pgrp);

if(current==NULL)

(

//norunningprocess,end

if(isFinished(pgrp))

(

cout«"SYSTEMRUNNINGSUCCEED!!"«endI;

ff«"SYSTEMRUNNINGSUCCEEDI!"«endI；

return;

)

eIse

(

cout«"SYSTERMLOCKED!!!"«endl;

ff«"SYSTERMLOCKED!!!"«endI；

return;

}

]

if(current->p_appIy==0)

readApply(current);

//判断能否满足进程的当前资源请求

if(current->p_appIy>Rcs_Ieft)

(

current->p_stat=TASK_WAITlNG;

cout«endl;

cout«"process"«current->p_pid«"iswaitting!"«endI;

ff«endl«"process"«current->p_pid«"iswaitting!"«endl;

continue;

1

//假定对申请资源的进程分配资源

pcbbackup(*current);//backupcurrent

length=Rcs_left;

current->p_occupy+=current->p_appIy;

length-=current->p_apply;

if(current->p_require-current->p_occupy>Iength

&&!isSafeState(pgrp,length))

(

〃撤销模拟分配

current->p_occupy=backup.p_occupy;

current->p_stat=TASK_WAITING;

cout«endI«"process"«current->p_pid«"\tis

waitting,"«endI;

ff«endI«"process"«current->p_pid«"\tis

waitting."«endI;

continue;

)

〃分配平安，可对进程进行实际的分配

Rcs_Ieft-=current->p_appIy;

cout«endI«"process"«current->p_pid«"get"«current->p_appIy«"

resource(s)!"«endI;

ff«endI«"process"«current->p_pid«"get"«current->p_appIy«"re

source(s)!"«endI;

current->p_appIy=0;

if(current->p_occupy<current->p_require)

(

pcbproc=*current;

pgrp.erase(current);

pgrp.insert(pgrp.end(),proc);

continue;

]

eIseif(current->p_occupy==current->p_require)

(

current->p_stat=TASK_SUCCEED；

current->p_occupy=0;

cout«endI«"process"«current->p_pid«"has

finished!!!"«endI;

ff«endI«"process"«current->p_pid«"has

finished!!!"«endI;

Rcs_Ieft+=current->p_require;

pgrp.erase(current);

wakeup(pgrp,Rcs_Ieft);

)

//判断是否仔有进程都已结束

if(isFinished(pgrp))

(

cout«endl«"SYSTERMSUCCEED!!"«endI;

ff«endl«"SYSTERMSUCCEED!!"«endI；

return;

1

)

)

vector<pcb>::iteratorgetFirstRunningProcess(vector<pcb>&pgrp)

(

vector<pcb>::iteratorp;

for(p=pgrp.beginO;p!=pgrp.end();p++)

if(p->p_stat==TASK_RUNNING)

(

returnp;

1

)

returnNULL;

)

//

voidreadAppIy(vector<pcb>::iteratorproc)

(

cout«endl«"ENTERTHErequestFORTHE

PROCESS\n"«proc->p_pid«'\t';

ff«"ENTERTHErequestFORTHEPROCESS\n"«proc->p_pid«"

cin»proc->p_appIy;

ff«proc->p_apply«endI;

while(proc->p_appIy>proc->p_require-proc->p_occupy)

(

cout<<endI«"beyondthereaIneed!"<<endI;

ff«"beyondthereaIneed!"«endI;

cout«endl«'RE-ENTERTHEREQUESTFORTHE

PROCESS\n"«proc->p_pid«'\t，;

ff«"RE-ENTERTHEREQUESTFORTHEPROCESS\n,,«proc->p_pid«"

cin»proc->p_appIy;

ff«proc->pappIy«endI;

1

)

//

booIisFinished(vector<pcb>&pgrp)

(

vector<pcb>::iteratorp;

for(p=pgrp.begin();p!=pgrp.end();p++)

if(p->p_stat!=TASK_SUCCEED)

returnfalse;

returntrue;

1

//

voidwakeup(vector<pcb>&pgrp,intavaiIabIe)

(

vector<pcb>::iteratorp;

for(p=pgrp.begin();p!=pgrp.end();p++)

if(p->p_stat==TASK_WAITING)

(

if(p->p_appIy<=availabIe)

p->p_stat=TASK_RUNNING;

1

)

boolisSafeState(vector<pcb>&pgrp,intavaiable)

(

vector<pcb>::iteratorp;

bool_isSafe=true;

for(p=pgrp.begin();p!=pgrp.end();p++)

if(p->p_stat!二TASK_SUCCEED)

p->p_issuc=faIse;

//

for(p=pgrp.begin();p!=pgrp.end();p++)

(

if(p->p_issuc-true)continue;

if((p->p_require-p->p_occupy)>avaiIabIe)continue;

eIse

(

p->p_issuc=true;

avaiIabIe^=p>p_occupy;

p=pgrp.begin();

continue;

1

I

for(p=pgrp.begin();p!=pgrp.end();p++)

(

if(p->p_issuc==true)continue;

eIse

(

_isSafe=faIse;

break；

}

)

return_isSafe;

)

㈢主存的可变分区管理：

1.定义一个名为freearea的结构体，用于存放空闲区的信息,

具体如下：

structfreearea

(

intstartaddress;〃空闲区起始地址

intsize;//空闲区大小

intstate：//空闲区状态：。为空表目，1为可用空闲块

);

2.完整的源程序如下：

#incIude"stdio.h"

#defineN5

structfreearea

(intstartaddress;

intsize;

intstate;

}freeblock[N]={{20,20,1},{80,50,1},{150,100,1},{300,30,0},{600,100,1}

)；

intalIoc(intappIyarea)

(

inti,tag=0;

for(i=0;i<N;i++)

if(freebIock[i].state==1&&freebIock[i].size>appIyarea)

(freebIock[i].startaddress=freebIock[i].startaddress+appIyarea;

freebIock[i].size=freebIock[i].size-appIyarea;

tag=1;

returnfreebIock[i].startaddress-appIyarea;

}eIse

if(freebIock[i].state==1&&freebIock[i].size==appIyarea)

{freebIock[i].state=0;

tag=1;

returnfreebIock[i].startaddress;

}

if(tag==0)

return-1;

)

voidsetfree()

(ints,I,tag1=0,tag2=0,tag3=0,i,j;

printf("inputfreeareastartaddress:\n");

scant("%d",&s);

printf("inputfreeareasize:\n");

scanf("％d"，&l);

for(i=0;i<N；i++)

(

if(freebIock[i].startaddress==s+1&&freebIock[i].state==1)

I=I+freebIock[i].size;

tag1=1;

for(j=0;j<N;j++)

if(freebIock[j].startaddress+freebIock[j].size-s&&freebIock[j].state

==1)

(

freebIock[i].state=0;

freebIock[j].size=freebIock[j].size+l;

tag2=1;

break;

)

if(tag2==0)

(

freeblock[i].startaddress=s;

freeblock[i].size=l;

break；

)

)

)

if(tag1==0)

(for(i=0；i<N；i++)

if(freebIock[i].startaddress+freeblock[i].size-s&&freebIock[i].state

==1)

{freebIock[i].size=freebIock[i].size+l;

tag3=1;

break;

1

if(tag3==0)

for(j=0;j<N;j++)

if(freeblock[j].state-0)

(freeblock[j].startaddress=s;

freeblock[j].size=l;

freebIock[j].state=1;

break;

)

)

1

voidadjust()

(inti,j;

structfreeareamiddata;

for(i=0;i<N；i++)

for(j=0;j<N;j-+)

if(freeblock[j].startaddress>freebIock[j+1].startaddress)

(middata.startaddress=freebIock[j].startaddress;

middata,size=freeblock[j].size;

middata.state=freebIock[j].state;

freeblock[j].startaddress=freebIock[j+1].startaddress;

freebIock[j].size=freebIock[j+1].size;

freeblock[j].state=freebIock[j+1].state;

freeblock[j+r.startaddress=middata.startaddress;

freeblock[j+1'.size=middata.size;

freeblock[j+1^.state=middata.state;

1

for(i=0;i<N;i++)

for(j=0;j<N；j++)

if(freeblock[j].state==0&&freebIock[j+1].state==1)

{middata.startaddress=freebIock[j].startaddress;

middata.size=freeblock[j].size;

middata,state=freebIock[j].state;

freebIock[j].startaddress=freebIock[j+1].startaddress;

freebIock[j].size=freebIock[j+1].size;

freebIock[j].state=freebIock[j+1].state;

freeblock[j+1_.startaddress=middata.startaddress;

freebIock[j+1..size=niiddata.size;

freeblock[j+1_.state=middata.state;

1

1

voidprint()

(inti;

printf("||\n");

printf("|startsizestate|\n");

printf("||\n");

for(i=0;i<N;i十十)

(

printf("|%3d%3d%3d

|\n",freebIock[i].startaddress,freebIock[i_.size,freebIock[i].state);

printf("||\n");

)

)

voidmain()/*主函数*/

(intappIyarea,start,i;

charend;

printf("\nisthereanyjobrequestmemory?yorn;");

while((end=getchar0)=='y')

{printf("atfirstthefreememoryisthis:\n");

adjust();

print();/*打印空闲区表的初始状态*/

printf("inputrequestmemorysize:");

scanf("%d",&applyarea);/*输入作业的申请量*/

start=aIloc(applyarea);

/*调用allocO函数，为作业分配空间，start

为返回的始地址*/

adjust();

printf("afteraIIocation,thefreememoryisthis:\n");

print();/*打印空闲区表*/

if(start==-1)/*alloc()分配不成