操作系统实验报告

操作系统实验报告

学院: 信息科学与工程学院 班级: 信息0701 姓名: 尹峥伟 学号: 0903070115

2009年11月30日1

目录

实验一: 进程的多级反馈队列调度算法 ------------------2

实验二: 在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收

实验三: 二级目录文件系统 ----------26

总结: ----------36

-----------------15

2

实验一: 进程的多级反馈队列调度算法

实验目的:

通过编写程序模拟操作系统进程的多级反馈队列调度来学习和理解操作系统进程的调度机制.

实验原理:

多级反馈队列调度算法，不必事先知道各进程所需的进程时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下：

1． 设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先权最

高，第二个的次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，??，第I+1个队列的时间片要比第I个队列的时间片长一倍。 2． 一个新进程进入内存后，首先将它放在第一队列的末尾，按FCFS原则排队等待

调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统，如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，??，如此下去，当一个长作业（进程）从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式进行。

3． 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1~（I-1）

队列均空时，才会调度第I队列中为某进程服务时，又有新进程进入优先权较高的队列（第1~（I-1）中的任何一个队列），则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第I队列的末尾，把处理机分配给新到的高优先权进程。

3

流程图：

开始 输入进程的信息量 输入第一队列的时间片 新进程进入第一队列并执行一次操作 是 任务是否完成

否 该 进 入下个队列 程入 本队 列 队 是 是否有新进程 尾 否 按FCFS 执行本队列中的进程

执行中是否 是 有新进程来

否

撤离系统 进程是否完成 是 否 否 下队列是否 为最后队列

是 入该队列且进程按时间片轮转法执行 4

否 是 时间片内是否完成 完成

相关数据结构：

由用户输入的进程结点的信息：

struct data{

int ID; int hour; int minute; int Alltime; }data[SIZE]

就绪队列中的进程结点信息：

typedef struct QNode{ int ID; int Hour; int Minute; int Alltime; struct QNode * next; }QNode,*QueuePtr;

就绪队列的数据结构：

typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue;

源码分析:

对代码中出现的变量做如下的一些说明如下：

5

如该进程任务未完成，则插入本队列队尾

else

{ b+=time5;

s->Hour=b/60;s->Minute=b`; s->Alltime-=time5;

printf(\ %d\\t%d:%d\\tQ5\\t%d\\t%d\\t %d\\n\me5,time5,s->Alltime);

CHANGE(Q5,Q5,s);

}//else }//else }//else }//else

else

{ if(s->Alltime-time5<=0) //in the Q5 ,finish

{ b+=s->Alltime;

s->Hour=b/60;s->Minute=b`; printf(\

%d\\t%d:%d\\tQ5\\t%d\\t%d\\t

-\\n\

DeQueue(Q5); }

如该进程任务未完成，则插入本队列队尾

else { b=b+time5;

s->Hour=b/60;s->Minute=b`; s->Alltime-=time5;

printf(\ %d\\t%d:%d\\tQ5\\t%d\\t%d\\t %d\\n\me5,time5,s->Alltime);

CHANGE(Q5,Q5,s);

11

} }

} } }

主要功能模块说明：

在file.cpp文件中：

InitQueue（）——队列的初始化； EnQueue()——入队列操作；

bubble_sort()——对所有进程按到达的时间先后顺序排序； change()——将进程的到达时间转换为分钟；

file()——输入进程的相关信息，并放到一等待队列中； 在tcb.cpp文件中：

CHANGE()——将任务未完成的进程从一个队列入到另一个队列中； DeQueue()——出队列操作；

TIME（）——多级反馈队列的具体算法实现；

调试分析说明：

调试中出现的问题：

1． 因程序的流程未控制好，致使只能完成每一个就绪队列中的第一个进程，而其后的

进程被忽略了；

2． 如果没有进程要求占有处理机，而后面的就绪队列中仍然有进程未完成任务，但此

时程序已停止执行；

3． 未控制程序的执行，致使用户不能看到整个程序的运行结果； 4． 未考虑用户随机输入的进程的先后顺序； 测试数据为：

12

第一组测试数据： 进程的相关信息为： 1 8 00 2 8 20 3 7 58

10

20 50

第一个就绪队列的时间片为： 5

运行结果为：

ID nowtime Queue timer serve left-time 3 8：3 Q1 5 5 1 8：5 Q1 5 5 3 8：15 Q2 10 10 1 8：20 Q2 10 5 2 8：25 Q1 5 5 2 8：35 Q2 10 10 3 8：55 Q3 20 20 2 9：00 Q3 20 5 ID nowtime Queue timer serve 3 9：15 Q4 40 15 所有进程完成任务的序列为： 1 2 3

第二组测试数据 进程的相关信息为： 1 8 5 80 2 9 2 7 5 6 9 2 6 8 2 60 9 3 8 12 第一个就绪队列的时间片为： 2

运行结果为：

ID nowtime Queue timer serve 9 3：10 Q1 2 2 9 3：14 Q2 4 4 9 3：20 Q3 8 6 5 6：11 Q1 2 2 6 8：4 Q1 2 2 6 8：5 Q2 4 1 1 8：7 Q1 2 2 ID nowtime Queue timer serve 6 8：11 Q2 4 4 1 8：15 Q2 4 4 6 8：23 Q3 8 8 45 5 35 — 15 5 15 — left-time — left-time 10 6 — — 58 57 78 left-time 53 74 45

13

1 8：31 Q3 8 8 66 6 8：47 Q4 16 16 29 1 9：2 Q4 16 15 51 2 9：4 Q1 2 2 5 2 9：8 Q2 4 4 1 2 9：9 Q3 8 1 — 1 9：25 Q4 16 16 35 6 9：54 Q5 32 29 — 1 10：26 Q5 32 32 3 1 10：29 Q5 32 所有进程完成任务的序列为： 9 5

2

6

1

3 — 14

实验二: 在可变分区管理方式下采用最先适应

算法实现主存分配和实现主存回收

实验目的

一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实验帮助学生理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。

实验原理

可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。

为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：

第一栏 第二栏 ? ?

起 址 14 K 32 K 其中，起址——指出一个空闲区的主存起始地址。

长度——指出从起始地址开始的一个连续空闲的长度。

状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。

当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。

按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲

15

长 度 12 K 96 K 状 态 未 分 配 未 分 配 空 表 目 空 表 目 ? ?

q->size = q->size + s->size + p->size; }else{

if(s->sPosition + s->size == p->sPosition){ //only bottom is free space; s->size = s->size + p->size;

if((tmp = (free_block * )malloc(sizeof(free_block))) == NULL){ printf(\ }

tmp->size = s->size;

tmp->sPosition = s->sPosition; tmp->next = p->next; q->next = tmp; free(p); }else{

if(q->sPosition + q->size == s->sPosition){ //only top is free space q->size = q->size + s->size;

}else{ //neither bottom or top is free space

if((tmp = (free_block * )malloc(sizeof(free_block))) == NULL){ printf(\ }

tmp->size = s->size;

tmp->sPosition = s->sPosition; tmp->next = p; q->next = tmp; } } }

}else{ //no bottom free space;

if(q->sPosition + q->size == s->sPosition){ //only top is free space q->size = q->size + s->size;

}else{ //neither bottom or top is free space

21

if((tmp = (free_block * )malloc(sizeof(free_block))) == NULL){ printf(\ }

tmp->size = s->size;

tmp->sPosition = s->sPosition; tmp->next = NULL; q->next = tmp; } } }

//释放空间函数 void cfree() {

int pid;

process * p_p,*p_q;

p_p = p_head->next; printf(\

printf(\ scanf(\

//find the process of the specify pid while(p_p->pid != pid && p_p != NULL){

p_q = p_p; //p_p stand for the process ;p_q stand for pre process p_p = p_p->next; }

if(p_p == NULL){

printf(\ }else{

cfree2(p_p); if(p_p == NULL){

22

p_q->next = NULL; }else{

p_q->next = p_p->next; } }

//free space showFreeChain(); showProcessChain(); } //主页面 void prtUsage() {

printf(\\

printf(\ printf(\ printf(\ printf(\

printf(\} int main() { init(); int a; while(1){ prtUsage();

printf(\/2/0 to select\\n\ scanf(\ if(a > 2 || a < 0){

23

printf(\ continue; } switch(a){

case 1:cmalloc();break; case 2:cfree();break; case 0:goto end; default:

printf(\ break; } } end: getchar();

printf(\}

主要功能模块:

void init() 初始化

void showFreeChain() 显示空闲内存信息 void showProcessChain()显示进程信息 void cmalloc()申请空间函数 void cfree()释放空间函数 void prtUsage()主页面

24

运行结果:

主界面

申请内存

释放内存

25

//如果要读的文件已经在uof中 cmRead.readUof(userUof); list::iterator it;

for(it=userUof.begin();it!=userUof.end();++it) { if(it->fileName==s) { //找到了该文件，调用函数读取，并修改uof表 cmRead.readFileN(it->filePoint,n); it->readP+=n;

cmRead.reWriteUof(userUof); return 13;

}

}

//不在uof中 list::iterator iu; int count=0;

for(iu=userUfd.begin();iu!=userUfd.end();++iu) { count++;

if(iu->fileName==s) {

//找到该文件,先打开，更新uof uof ut; //文件属性在disk.txt中的位置

int position=usermfd.ufdLink*514+(count-1)*32+14; char *p=\为打开模式 ut.set(iu->fileName,position,p,n,0,2);

userUof.push_back(ut);//在uof表的最后添加一项 cmRead.readUof(userUof);//uof表重新写入disk

31

}

}

}

cmRead.readFileN(iu->fileFirstBlock,iu->fileLength,n); return 13;

cout<<\无该文件，请检查文件名!\\n\return 13;

int Chmod(string s,int n) {

//如果模式不满足要求0-2

if(n<0||n>2){cout<<\无该模式，模式0-readonly;1-writeonly;2-read/write,请核对输入

\

//否则继续 list::iterator it;

for(it=userUfd.begin();it!=userUfd.end();++it) {

if(it->fileName==s) {

it->fileMode=n+'0'; }

int Command::Create(string s,int n) {

}

}

cmRead.reWriteUfdTotal(userUfd,usermfd.ufdLink); cout<<\修改成功!\\n\return 12;

cout<<\无该文件!\\n\return 12;

//判断文件名是否存在

32

list::iterator it;

for(it=userUfd.begin();it!=userUfd.end();++it) { if(it->fileName==s)

{

cout<<\文件名已存在，不能创建!\\n\ return 11;

}

}

//添加文件到ufd表中 ufd temp;

char *f=\文件存在标志位， char *p;

p=(char*)s.c_str();//文件名,string不能直接赋值给char*，只能通过强制转换char m=n+'0';

int b=cmRead.getNewDataBlock(); cmRead.upDateFat(); temp.set(f,p,m,0,b); userUfd.push_back(temp);

cmRead.reWriteUfdTotal(userUfd,usermfd.ufdLink);

//添加信息到uof表中 uof ut; //文件属性在disk.txt中的位置

int position=usermfd.ufdLink*514+(userUfd.size()-1)*32+14; char *p2=\0为创建模式

ut.set(temp.fileName,position,p2,0,0,2);

userUof.push_back(ut);//在uof表的最后添加一项 cmRead.readUof(userUof);//uof表重新写入disk cout<<\创建成功!\\n\

33

}

return 11;

主要功能模块:

int Read(string s,int n);//读文件 int Open(string s,int n);//打开文件 int Write(string s,string t,int n);//写文件

运行结果:

主界面

Help 指令显示所有命令

34

建立文件

删除文件

35

总结:

尽管这段时间要忙于多门课程的复习,还是认真的做完了以上老师交给的任务. 首先获得的最大收获当然就是对于操作系统的内部原理的认识和学习. 从理论上了解后就开始实际编程实现这些算法, 这其中花了很多时间. 不过有语言和数据结构的基础基本的实现还是没有很大的问题. 但是由于以前写的都是不超过两百行的小型代码, 也没遇到过需要大量数据结构的封装的, 而编写这类程序则不同, 算法不会很难, 但是其中需要各种数据结构以及进行合理有效的连接等. 之前程序规划的不合理导致多次修改代码, 使得效率比较低下. 所以以后编写这类程序一定要事前想好各个数据结构以及模块功能, 然后想好该怎么实现接口等, 这样才能减少错误和提高效率.

36

本文来源：https://www.bwwdw.com/article/khgg.html