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

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

一、实验目的

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

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

⑥磁盘的驱动调度管理，这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.位示图：位示图用若干个字构成，每一位对应一个磁盘块，〃:L"

表示占用，表示空闲。

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

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

因磁盘的驱动调度管理：

1.先来先服务算法（FCFS）:

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

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

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

此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，

此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各

进程得到服务的响应时间的变化幅度较小。

2.最短查找时间优先算法（SSTF）:

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

道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞

吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求

的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务

请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有

些请求的响应时间将不可预期。

3.电梯调度算法：

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

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

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

最近的I/O请求。

四、详细设计

㈠处理机管理（进程调度管理）：

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

structworktime

（

floatTb;〃作业运行时刻

floatTc;〃作业完成时刻

floatTi;〃周转时间

floatWi;〃带权周转时间

）；

structjcb

（

charname[10];〃作业名

floatsubtime;〃作业至（]达时间

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

charresource;〃所需资源

floatRp;〃后备作业响应比

charstate;〃作业状态

intworked_time;〃已运行时间

structworktimewt;

intneed_time;〃要求运行时间

intflag;〃进程结束标志

structjcb*link;〃链指针

）

2.完整的源程序如下：

#include

#include

#include

#include

usingnamespacestd;

#definegetpch(type)(type*)malloc(sizeof(type))〃为进程创

建一个空间

structworktime{

floatTb;〃作业运行时刻

floatTc;〃作业完成时刻

floatTi;〃周转时间

floatWi;〃带权周转时间

)；

structjcb{

charname[10];〃作业名

floatsubtime;〃作业至(]达时间

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

charresource;〃所需资源

floatRp;〃后备作业响应比

charstate;〃作业状态

intworked_time;〃已运行时间

structworktimewt;

intneed_time;〃要求运行时间

intflag;〃进程结束标志

structjcb*link;〃链指针

}*ready=NULL/p;

typedefstructjcbJCB;

floatT=0;

intN;

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

voidsortQ

JCB*first,*second;

intinsert=0;〃插入数

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

(

p->link=ready;

ready=p;

T=p->subtime;

p->Rp=l;

)

else

(

first=ready;

second=first->link;

while(second!=NULL)

(

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

(

p->link=second;

first->link=p;

second=NULL;

insert=l;

)

else

(

first二first-〉link;

second=second->link;

)

)

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->runtim

e)>(rear->runtime)){

front=mintime;

mintime=rear;

rear=rear->link;

ipmove=l;

)

else

rear=rear->link;

)

if(ipmove==l)

(

front->link=mintime->link;

mintime->link=ready;

)

ready=mintime;

)

voidcreatJCBO〃为每个作业创建一个JCB并初始化形成一个循

环链队列{

JCB

inti=0;

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

cout<<”\n请输入作业的个数:“；

scanf("%dn,&N);

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

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

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

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

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

l->state=匕〃作业初始状态为就绪l->worked_time=0;

l->link=NULL;

l->flag=0;

front=l;

for(i=l;i<n;i++)<p="">

(

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

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

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

scanf("%s"zp->name);

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

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

p->state='r';

p->worked_time=0;

p->flag=0;

l->link=p;

l=l->link;

)

rear=l;rear->link=front;

)

voidoutput()〃进程输出函数

intj;

printf("nameruntimeneedtimestate\n");

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

{printf("%-4s\t%-4d\t%-4d\t%-

c\n"zfront->name/ront->workedjimejront->

need_time,front->state);

front=front->link;

)

printf("\n");

)

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

(

intflag=lj;

for(i=0;i<n;i++)<p=,,n>

(

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

(

flag=0;

break;}

p=p->link;

)

returnflag;

)

voidRRget()〃时间片轮转算法

(

JCB*s;

intflagl=0;

s=(JCB*)malloc(sizeof(JCB));

s=front;

printf("\n--------------------------------------------------------\n");

output();

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

getch();//按任意键继续

s=front;

while(flagl!=1)

(

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

(

s->worked_time++；

s->need_time-;

if(s->need_time==0)

s->state='e';

outputQ;

printf("请输入任意一键继续…\n)

getch();

)

if(s->state==>flag==O)

(

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

s->flag=l;

)

s=s->link;

flagl=judge(s);

)

printf("----------------------------------------------------\n");

)

voidinput()

(

inti,num;

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

scanf("%d",&num);

for(i=0;i<num;i++)<p="">

(

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"z&p->runtime);

printf("\nH)；

p->state='w';

p->link=NULL;

sort();

)

)

intspaceO

(

int1=0;JCB*jr=ready;

while(jr!=NULL)

(

I++；

jr=jr->link;

)

return(l);

)

voiddisp(JCB*jrjntselect)

if(select==3)printf("\n作业到达时间服务时间响应比