操作系统实验C语言模拟操作系统运行课程设计

二：进程调度算法模拟

1 设计目的

（1）要求学生设计并实现模拟进程调度的算法：时间片轮转及先来先服务。 （2）理解进程控制块的结构。 （3）理解进程运行的并发性。 （4）掌握进程调度算法。 2 设计要求

在多道程序运行环境下，进程数目一般多于处理机数目，使得进程要通过竞争来使用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之运行，分配处理机的任务是由进程调度程序完成的。一个进程被创建后，系统为了便于对进程进行管理，将系统中的所有进程按其状态，将其组织成不同的进程队列。于是系统中有运行进程队列、就绪队列和各种事件的进程等待队列。进程调度的功能就是从就绪队列中挑选一个进程到处理机上运行。进程调度的算法有多种，常用的有优先级调度算法、先来先服务算法、时间片轮转算法。

进程是程序在处理机上的执行过程。进程存在的标识是进程控制块（PCB），进程控制块结构如下：

typedef struct node {

char name[10]; /* 进程标识符 */ int prio; /* 进程优先数 */

int round; /* 进程时间轮转时间片 */ int cputime; /* 进程占用 CPU 时间*/ int needtime; /* 进程到完成还需要的时间*/ int count; /* 计数器*/ char state; /* 进程的状态*/ struct node *next /*链指针*/ }PCB;

系统创建一个进程，就是由系统为某个程序设置一个PCB，用于对该进程进行控制和管理，进程任务完成，由系统收回其PCB，该进程便消亡。每个进程可以有三个状态：运行状态、就绪状态和完成状态。

用C语言、C++或者Java语言编写一个程序实现进程调度的算法，模拟进程调度的过程，加深对进程控制块概念和进程调度算法的理解。

本任务要求完成时间片轮转及先来先服务两个算法。

3.时间片轮转算法完成进程的调度

3.1设计要求：

（1）进程的调度采用时间片轮转算法。

（2）设计三个链队列，分别用来表示运行队列、就绪队列和完成队列。 （3）用户输入进程标识符以及进程所需的时间，申请空间存放进程 PCB信息。 （4）输出的格式和上面的运行结果分析中的格式相同。

时间片轮转调度，具体做法是调度程序每次把 CPU 分配给就绪队列首进程使用一个时间片。当这个时间片结束时，就强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。实现这种调度要使用一个间隔时钟。当一个进程开始运行时，就将时间片的值置入间隔时钟内，当发生间隔时钟中断时，就表明该进程连续运行的时间已超过一个规定的时间片。此时，中断处理程序就通知处理器调度进行处理器的切换工作。

3.2.时间片轮转算法主要思想：

在计算机中系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后再把处理机分配给就绪队列中给定的时间内均能获得一时间片的处理机执行时间。 3.3算法的实现

1.数据结构及变量说明

typedef struct pcb

{

char name[10]; //进程标识符

int pArriveTime; //到达时间

int pRunTime; //估计运行时间 int round; //进程时间轮转时间片 int cputime;

//进程占用CPU时间

int needtime; //进程到完成还要的时间 int count; //计数器 char state; //进程的状态 struct pcb *next; //链指针 }PCB;

PCB *finish,*ready,*tail,*run; //队列指针 PCB head_input; int N; //进程数

2.完成功能的主要函数

void roundrun()//时间片轮转法 {}函数

3.时间片轮转的主要算法功能及注释：

void insert2(PCB *p2)//轮转法插入函数 {

tail->next=p2; //将新的PCB插入在当前就绪队列的尾

2

tail=p2;

p2->next=NULL; }

void create2()//轮转法创建进程PCB {

PCB *p; int i,time,n; char na[10]; ready=NULL; finish=NULL; run=NULL;

printf(\输入进程名及所需时间\\n\ for(i=1;i<=N;i++) {

p=(PCB*)malloc(sizeof(PCB)); scanf(\ scanf(\ strcpy(p->name,na); p->cputime=0; p->needtime=time; p->count=0; //计数器 p->state='W'; p->round=3; if(ready!=NULL) insert2(p); else {

p->next=ready; ready=p; tail=p; } }

system(\

printf(\ 轮转法输出\\n\

printf(\ prt(); //输出进程PCB信息

run=ready; //将就绪队列的第一个进程投入运行 ready=ready->next; run->state='R';

3

}

void roundrun()//时间片轮转法 {

while(run!=NULL) {

run->cputime=run->cputime+1; run->needtime=run->needtime-1; run->count=run->count+1;

if(run->needtime==0)//运行完将其变为完成态，插入完成队列 {

run->next=finish; finish=run; run->state='F'; run=NULL; if(ready!=NULL)

firstin(); //就绪对列不空，将第一个进程投入运行 } else

if(run->count==run->round) //如果时间片到 {

run->count=0; //计数器置0 if(ready!=NULL) //如就绪队列不空 {

run->state='W'; //将进程插入到就绪队列中等待轮转 insert2(run);

firstin(); //将就绪对列的第一个进程投入运行 } }

prt(); //输出进程信息 } }

4.时间片算法主要流程图如下：

4

开始 创建PCB进程，输入进程名及时间 就绪队列ready!＝null Y run->cputime=run->cputime+1;run->needtime=run->needtime-1;run->count=run->count+1; N run->needtime==0 Y N run->count==run->round run->next=finish; finish=run; run->state='F'; run=NULL; Y run->count=0;//计数器置0 ready!=NULL ready!=NULL N Y ready!=NULL run=ready; run->state='R'; Y ready=ready->next; tail->next=run; tail=run;run->next=NULL; run->state='W'; run=ready; run->state='R'; ready=ready->next; 输出进程信息 结束 5

5.时间片算法运行结果分析如下：

4.用先来先服务算法完成进程的调度

4.1设计要求：

（1）进程的调度采用先来先服务算法。

（2）设计三个链队列，分别用来表示运行队列、就绪队列和完成队列。 （3）用户输入进程标识符以及进程所需的时间，申请空间存放进程PCB信息。 （4）输出的格式和上面的运行结果分析中的格式相同。

先来先服务：按照进程进入就绪队列的先后次序来分配处理器。先进入就绪队列的进程优先被挑选，运行进程一旦占有处理器将一直运行下去直到运行结束或被阻塞，这是一种非剥夺式调度。

6

4.2先来先服务调度算法主要思想：

此算法既可用于作业调度，也歌词用于进程调度。当作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。 4.3 算法的实现

1.数据结构及变量说明

typedef struct pcb

{

char name[10]; //进程标识符

int pArriveTime; //到达时间

int pRunTime; //估计运行时间 int round; //进程时间轮转时间片 int cputime;

//进程占用CPU时间

int needtime; //进程到完成还要的时间 int count; //计数器 char state; //进程的状态 struct pcb *next; //链指针 }PCB;

PCB *finish,*ready,*tail,*run; //队列指针 PCB head_input; int N; //进程数

2.完成功能的主要函数

void ExecProcessList(){}//先来先服务函数

3.先来先服务的主要算法功能及注释：

void ExecProcessList() {

run=head_input.next; while(run!=NULL) {

run=head_input.next;//run指向对头的下一个进程

printf(\开始运行 正在运行 已经运行时间 剩余时间 等 待 中 的 进程 for (int j=0;j<(run->pRunTime)/1000;j++)//输出每次运行的统计信息 { if (0==j) {

printf(\到达进程开始执行 }

printf(\ %s %d %d\ ready=run->next; //判断此时还有哪些进程在队列里面 while (ready!=NULL)

已结束进程\\n\ 7

{

printf(\ %s \ ready=ready->next; } printf(\ }

run->state='C'; //将进城状态设置为执行完的状态

printf(\ ready=run;//将run指向下一个元素 run=run->next; head_input.next=run;

delete ready;//将此进程从进程队列里面删除 } }

4.先来先服务算法主要流程图如下：

8

开始 run=head_input.next; run!=NULL Y run=head_input.next; run->state='C'; printf(\ ready=run; run=run->next; head_input.next=run; delete ready; j=0 ready=run->next; printf(\ j==0? printf(\ %s \\n\>name);ready!=NULL Y printf(\ ready=ready->next; 结束 5.先来先服务运行结果如下：

9

10

三：主存空间的回收与分配

1 设计目的

主存是中央处理器能直接存取指令和数据的存储器，能否合理地利用主存，在很大程度上将影响到整个计算机系统的性能。主存分配是指在多道作业和多进程环境下，如何共享主存空间。主存回收是指当作业执行完毕或进程运行结束后将主存空间归还给系统。主存分配与回收的实现是与主存储器的管理方式有关。本次设计主要是为了帮助学生深入理解主存空间的分配与回收的几种算法。

（1）掌握最先适应分配算法（2）掌握最优适应分配算法（3）掌握最坏适应分配算法 2 设计要求

用户提出内存空间请求，系统根据申请者要求，按照最先适应分配算法的分配策略分析内存空间的使用情况，找出能满足请求的空闲区，分给申请者，当程序执行完毕时，系统要收回它所占用的内存空间。建立空闲数据文件，空闲区数据文件包括若干行，每行有两个字段：起始地址、内存块大小（均为整数），各字段以逗号隔开。下面是一个空闲区数据文件的示例：

0， 10， 18， 28， 34， 44，

10 08 10 06 10 09

读取空闲区数据文件，建立空闲区表并在屏幕上显示空闲内存状态，空闲区表记录了可供分配的空闲内存的起始地址和大小，用标志位指出该分区是否是未分配的空闲区。

接收用户的内存申请，格式为：作业名、申请空间的大小。

按照内存分配算法中的一种方法选择一个空闲区，分割并分配，修改空闲区表，填写内存已分配区表（起始地址、长度、标志位），其中标志位的一个作用是指出该区域分配给哪个作业。

进程结束后回收内存。本次设计要求完成如下算法： （1）设计一个内存分配回收的程序使用最先适应分配算法 （2）设计一个内存分配回收的程序使用最优适应分配算法 （3）设计一个内存分配回收的程序使用最坏适应分配算法

用户提出内存空间请求，系统根据申请者要求，选择上述算法的一种分配策略分析内存空间的使用情况，找出合适的空闲区，分给申请者，当进程执行完毕时，系统收回它所占用的内存空间。 创建空闲区表：

空闲区表的结构如下：

typedef struct node{ int start;

11

int length; char tag[20]; }job;

3.算法的设计实现

3.1设计实现：

1.数据结构及变量说明

const int MAXJOB=100;//定义表最大记录数 typedef struct node{

int start; int length; char tag[20];

}job;

job frees[MAXJOB];//定义空闲区表 int free_quantity;

job occupys[MAXJOB];//定义已分配区表 int occupy_quantity;

2.完成功能的主要函数

initial() 初始化

readData() 从文本文件读取数据 sortearliest() 最先适应算法排序 earliest() 实现最先适应算法 sortbest() 最佳适应算法排序 bestMethod() 实现最佳适应算法 sortbad() 最坏适应算法排序 BadMethod() 实现最坏适应算法 finished() 实现主存回收 view() 显示

3.2.最先适应算法的功能及注释

//声明变量 char job_name[20]; int job_length; int i,j,flag,t;

//输入进程名和空间大小

cout<<\请输入新申请内存空间的作业名和空间大小:\cin>>job_name; cin>>job_length;

12

flag=0; //标志变量

for(i=0;i

if(frees[i].length>=job_length){//空闲区长度是否大于进程所需空间

flag=1; } }

if(flag==0){ //空闲区长度小于进程所需空间

cout<

else{ //空闲区长度大于进程所需空间，从首地址开始查询，找到大于进程长度的及分配给进程 t=0; i=0; while(t==0){ if(frees[i].length>=job_length){

t=1;

}

i++; } i--;

occupys[occupy_quantity].start=frees[i].start; strcpy(occupys[occupy_quantity].tag,job_name); occupys[occupy_quantity].length=job_length; occupy_quantity++;

if(frees[i].length>job_length){ frees[i].start+=job_length;

frees[i].length-=job_length; } else{ for(j=i;j

frees[j]=frees[j+1]; }

free_quantity--;

最先适应算法的主要流程图如下：

13

开始循环按首地址由小到大排序输入进程名和所需分配内存的大小所需内存是否大于0Y利用循环找到已分配表的末端，插入一个节点N给进程分配内存空间，空闲表做相应的处理结束最先适应算法运行结果如下：

14

3.3.最佳适应算法的实现

//声明变量

char job_name[20]; //名字 int job_length; //长度 int i,j;

int max=0,min=0,maxx; //输入进程名和空间大小

cout<<\请输入新申请内存空间的作业名和空间大小:\ cin>>job_name; cin>>job_length; //查找最合适的空闲区 for(i=0;i

15

if(frees[j].length<=frees[i].length) max=i;elsemax=j;} for(j=0;j

if(frees[j].length>=frees[i].length) min=i;elsemin=j;}

if(frees[min].length<=job_length && frees[max].length>=job_length){ maxx=i; }}

if(frees[maxx].length

cout<

occupys[occupy_quantity].start=frees[maxx].start; strcpy(occupys[occupy_quantity].tag,job_name); occupys[occupy_quantity].length=job_length; occupy_quantity++;

if(frees[maxx].length>job_length){ frees[maxx].start+=job_length; frees[maxx].length-=job_length; } else{

for(j=maxx;j

free_quantity--; 最优流程图：

16

开始空闲分区容量按从小到大进行排序输入进程名和所需分配内存的大小所需内存是否大于0Y利用循环招到第一次能满足要求的空闲区插入节点给进程分配内存空间，空N闲表做相应的处理结束最佳算法运行结果如下：

17

3.4.最坏适应算法的实现

//声明变量

char job_name[20]; //名字 int job_length; //长度 int i,j; int max;

//输入进程名和空间大小

cout<<\请输入新申请内存空间的作业名和空间大小:\ cin>>job_name; cin>>job_length; //找出空闲区最大的 for(i=0;i

18

for(j=0;j

if(frees[j].length

if(frees[max].length

occupys[occupy_quantity].start=frees[max].start; strcpy(occupys[occupy_quantity].tag,job_name); occupys[occupy_quantity].length=job_length; occupy_quantity++;

if(frees[max].length>job_length) { frees[max].start+=job_length; frees[max].length-=job_length;} else{

for(j=max;j

开始分区容量按从大到小排序输入进程名和所需分配内存的大小所需内存是否大于0Y利用循环找到最大的空闲分区插入一个节点给进程分配内存空间，空N闲表做相应的处理结束

最坏算法运行结果如下：

19

3.5.主存回收算法的实现

//声明变量 char job_name[20]; int i,j,flag,p=0; int start; int length;

//输入要回收的进程名

cout<<\请输入要撤消的作业名:\ cin>>job_name; flag=-1; //标志变量 //找到指定进程

20

for(i=0;i

start=occupys[i].start;

length=occupys[i].length; } }

if(flag==-1){

cout<<\没有这个作业名\

else{ //加入空闲表 for(i=0;i

frees[j]=frees[j+1]; }

free_quantity--; p=1; }

else{ frees[i].length+=length;

p=1; } }

if(frees[i].start==(start+length)){ frees[i].start=start; frees[i].length+=length;

p=1; }}

if(p==0){ frees[free_quantity].start=start; frees[free_quantity].length=length;

free_quantity++; }

//删除分配表中的该作业 for(i=flag;i

occupys[i]=occupys[i+1]; }

occupy_quantity--;

主存回收的流程图如下：

21

开始输入要回收的进程名判断是否有此进程Y回收后的空闲区起始地址为进程的起始地址；长度为=进程空间的大小状态为free此进程相邻是否有空闲区NY回收后的空闲区起始地址为前一空闲区起始地址；长度为=空闲区长度+进程空间的大小状态为free此进程是否只与前一个空闲区相邻N此进程是否只与后一个空闲区相邻NNYY回收后的空闲区起始地址为进程的起始地址；长度为=空闲区长度+进程空间的大小状态为free回收后的空闲区起始地址为前一空闲区起始地址；长度为=两空闲区长度之和+进程空间的大小状态为free结束回收算法运行结果如下：

22

四：模拟DOS文件的建立和使用

1 设计目的

磁盘文件是磁盘上存储的重要信息，通过本实验模拟DOS文件的建立和使用情况，理解磁盘文件的物理结构。文件管理是操作系统中重要的内容之一，不同的文件系统提供了不同的物理结构，通过实验，深入理解文件的物理结构与存取方法之间的关系，以便更好的掌握文件系统的概念。 2 设计要求

（1） 模拟设计DOS操作系统中磁盘文件的存储结构

DOS操作系统对磁盘文件的管理采用链接结构，将所有的链接指针集中在一起，存放在文件分配表（FAT）中。连接文件的第一个物理块号登记在文件目录中。其设计思想是：假定磁盘上共有N个物理块可供使用，当要存放文件时，从FAT表中寻找其值为0的项，用其对应的物理块存放文件信息，并把文件占有的各物理块用链接指针登记在FAT表中，再把文件的第一个物理块号登记在文件目录中。

文件目录及FAT表如图所示:

在DOS中FAT表的前两项用来记录磁盘的类型。而从第2项开始记录磁盘的分配情况和文件各物理块的链接情况。在FAT表中第三项的值如果为0，表示对应的第三块空闲。由图还知道文件A的各记录依次存放在第2、第4、第15、第16、第50等六个物理块中。第50块中的指针为FFF，表示文件A的结束。文件B的各记录依次存放在第7、第10、第20等三个物理块中。第20块中的指针为FFF。

23

假定磁盘存储空间共有100个物理块，设计一个文件分配表。为了简单，文件分配表可用一个数组定义，其中每一个元素与一个物理块对应。当第 i 个元素为 0 时，表示第 i 块空闲；当第 i 个元素既不为 0 也不为 FFF 时，其值表示该文件的下一个物理块号。另外，再设一个空闲块总数变量记录系统还有的空闲块数。为了简单，假定一个物理块指存放一个逻辑记录，要求设计一个程序，把文件的逻辑记录结构转换成 DOS 的链接结构。当用户要求将已在主存的文件保存在磁盘上时，给出文件名及文件的记录个数，系统应能在磁盘上正确地保存文件。或当用户要求给指定文件增加记录时，也应正确的实现，并插在指定记录之后。

为了正确地执行模拟程序，可用键盘模拟输入用户的要求。输入格式为： write(文件名，记录个数) 或insert(文件名，逻辑记录号) （2） 模拟设计便于直接存取的索引文件结构

为了便于用户直接存取文件的各个逻辑记录，在 MS-DOS 中通过文件目录，再沿着链查找FAT表，便可直接找到指定逻辑记录对应的物理块。在小型机或更高级的文件系统中，直接存取文件的方法是为每个文件建立一个索引表，指出各逻辑记录与物理块的对应关系。

最简单的形式是一个逻辑记录对应一个物理块。文件目录与索引表的关系如图所示。

通常索引表按照逻辑记录顺序建立，这样既有利于顺序存储，又有利于直接存储。为了标识哪些记录已经建立，哪些记录还没建立，故在索引表中增设一个标志位。写文件或插入一个记录的过程是寻找一个空闲物理块，然后将其填入索引表对应项中。其建立过程同第一题，即 write（文件名，记录号）和 insert（文件名，记录号）。

要求用位示图描绘出磁盘的使用情况，并要求模拟程序执行过程的每一步都能显示文件目录、位示图、索引表。

3模拟算法的实现:

24

1.数据结构及变量名：

const int FDF=-2; const int FFF=-1;

const int N=100;//存储空间(FAT表长度) int filenumber;//文件数量 struct FILEINFO{ char filename[10]; int startaddress; int filelength;

};

2.实现功能的主要函数 Void printfmenu()//打印目录表 Void printfFAT()//打印FAT表 Void search2()//搜索文件

void write(char *tmpname,int tmplength)//写入文件 void insert(char *tmpname,int insertpoint)//插入文件

（1）.模拟设计DOS操作系统中磁盘文件的存储结构的主要算法功能及注释如下：①写入函数算法：

void write(char *tmpname,int tmplength) { int last,i,j;

strcpy(file[filenumber].filename,tmpname);//复制文件名和文件块个数 file[filenumber].filelength=tmplength; for(i=2;i

}

}

for(i=1;i

for(j=2;j

FAT[last]=FFF;

25

break;

}

}

FAT[last]=FFF;//文件末存结束标记

Remainingspace-=tmplength;//改变空闲块个数 filenumber++;

printf(\文件名和长度:%s %d\\n\

}

写入函数的主要流程图如下：

26

开始 intlast,i,j;strcpy(file[filenumber].filename,tmpname);file[filenumber].filelength=tmplength; i=2 N i

27

写入函数运行结果如下：

②插入函数主要算法如下：

void insert(char *tmpname,int insertpoint) {

int i;

int last,brpoint;

for(i=0;i

brpoint=file[last].startaddress; for(i=0;i

for(i=0;i

if(FAT[i]==0) {

brpoint=FAT[brpoint]; //扫描直到找到插入位置

//brpoint记录当前文件扫描到的位置

if(strcmp(file[i].filename,tmpname)==0)//比较插入文件名与已存在文件名是否相同 { }

last=i; break;

28

}

file[last].filelength++; Remainingspace--;

printf(\文件名和长度:%s %d\\n\

//改变空闲块个数与文件长度

}

FAT[i]=FAT[brpoint]; FAT[brpoint]=i; break;

}

插入函数主要流程图：

29

开始 int i;int last,brpoint; i=0 i

插入的运行结果如下：

（2）.模拟设计便于直接存取的索引文件结构的主要算法功能及注释如下： void search(char *tmpname){

int i;

for(i=0;i

{

if(strcmp(file[i].filename,tmpname)==0)//比较插入文件名与已存在文件名是否相同

{

printf(\找到了!\\n\

printf(\文件名 起始块号 文件长度\\n\

printf(\ %s %d %d\\n\

}

void search2(int searchpoint) {

int i=0; int m;

if(FAT[searchpoint]==0) { }

else if(FAT[searchpoint]==-1&&FAT[searchpoint-1]==-2||FAT[searchpoint]==-2&&FAT[searchpoint+1]==-1)

{

printf(\此处为系统空间!\ }

else if(FAT[searchpoint]!=0) {

for(i=0;i

m=searchpoint-file[i].startaddress; printf(\该点空缺,没有文件!\ } }

31

if(m>=0&&m

printf(\找到了!此处的文件名为:%s\ break; } } }

}

1.模拟设计便于直接存取的索引文件结构的主要流程图如下：

32

开始 int i=0; int m; N FAT[searchpoint]==0 Y printf(\该点空缺,没有文件!\ FAT[searchpoint]==1&&FAT[searchpoint-1]==-2||FAT[searchpoint]==-2&&FAT[searchpoint+1]==-1 N Y printf(\此处为系统空间!\ FAT[searchpoint]!=0 Y i=0 i=0&&m

搜索的运行结果如下：

33

34

五：磁盘调度

1.设计目的

（1）要求学生设计一个模拟磁盘调度的程序 （2）理解磁盘调度过程中的三个时间段 （3）理解磁盘调度的三种算法 2.实验原理

共享设备的典型代表为磁盘，磁盘的物理块的地址由柱面号、磁道号、扇区号来指定，完成磁盘某一个物理块的访问要经过三个阶段：寻道时间 Ts、旋转延迟 Tw 和读写时间 Trw。

寻道时间 Ts 是磁头从当前磁道移动到目标磁道所需要的时间；旋转延迟 Tw 是当磁头停留在目标磁道后，目标物理块从当前位置旋转到磁头位置的时间；读写时间 Trw 是目标物理块内容与内存中对应交换的时间。磁盘调度的原则是公平和高吞吐量，衡量指标有访问时间 T 和平均访问时间 Ta：

T=Ts+Tw+Trw Ta=Tsa+Twa+Trwa

寻道时间和旋转延迟成为调度算法的主要考虑因素。减少访问时间就是要减少寻道时间和旋转延迟。 3．设计要求

（1）设计并实现一个函数，完成先来先服务的磁盘调度功能 （2）设计并实现一个函数完成最短寻道时间优先的磁盘调度功能。 （3）设计并实现一个函数完成电梯算法的磁盘调度功能。 4.设计实现： 1.数据结构及变量： 2.实现的主要函数

void FCFS(int array[],int m)// 先来先服务算法 void SSTF(int array[],int m)// 最短寻道时间优先算法 void SCAN(int array[],int m) //电梯算法 3.先来先服的磁盘调度的主要思想如下：

这种算法根据请求访问磁盘的先后顺序进行调度，此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。 4.先来先服务的主要算法功能及注释如下：

void FCFS(int array[],int m)// 先来先服务算法 {

int i,now; float sum=0; float avg;

printf(\先来先服务算法调度后的序列为:\\n\

35

for (i=0;i

printf(\ sum+=abs(array[i+1]-array[i]); }

sum=sum-abs(array[m]-array[m-1]);//减去多加的一次 avg=sum/m;

printf(\平均寻道长度：%f\\n\输出平均寻道长度 printf(\移动的总道数:%f\\n\}

5.先来先服务的主要流程图如下：

开始 int i,now;float sum=0; float avg; i=0 N i

36

7.最短寻道时间优先调度的主要思想如下：

该算法选择这样的进程：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间 最短。但这种算法不能保证平均寻道时间最短。 8.最短寻道时间调度的主要算法功能及注释如下：

void SSTF(int array[],int m)// 最短寻道时间优先算法 {

int temp; int k=1; int now,l,r; int i,j; float sum=0; float avg=0; for (i=0;i

if (array[i]>array[j]) //将磁道号从小到大排序 {

temp=array[i]; array[i]=array[j]; array[j]=temp; } } }

printf(\请输入当前的磁道号：\\n\输入当前磁道号 scanf(\

printf(\最短寻道时间优先算法调度后的序列为:\\n\输出磁盘调度序列 if (array[m-1]<=now) //若被访问的下一最大的磁道号不大于当前的磁道号 {

for (i=m-1;i>=0;i--) {

printf(\输出磁盘调度序列

37

sum+=now-array[i]; now=array[i]; } } else {

if (array[0]>=now) //若被访问的下一最小的磁道号不小于当前的磁道号 {

for (i=0;i

printf(\输出磁盘调度序列 sum+=array[i]-now; now=array[i]; } }

else //当前的磁道号的值在若所有被访问的下的磁道号之间 {

while (array[k]

if ((now-array[l])<=(array[r]-now)) {

while (l>=0) //先向磁道号减小方向访问 {

printf(\输出磁盘调度序列 sum=sum+now-array[l]; now=array[l]; l=l-1; }

now=array[0];

for (j=r;j

printf(\输出磁盘调度序列 sum+=array[j]-now; now=array[j]; }

38

}

else //先向磁道号增加方向访问 {

while (r

printf(\输出磁盘调度序列 sum+=array[r]-now; now=array[r]; r=r+1; }

now=array[m-1];

for (j=l;j>=0;j--) //再向磁道号减小方向访问 {

printf(\ //输出磁盘调度序列 sum+=now-array[j]; now=array[j]; } } } }

avg=sum/(m);

printf(\平均寻道长度：%f\\n\输出平均寻道长度 printf(\移动的总道数:%f\\n\}

9.最短寻道时间调度的主要流程图如下：

39

开始 将磁道号从小到大排序 输入当前磁道号now Y N array[m-1]<=now 输出磁盘调度序列Y (array[0]array[j] >=now N 磁头移动总距离输出磁盘调度确定当前磁道在已sum+=now-array[i] 序列array[j] 排的序列中的位置 目前的位置变为当前磁头移动总距离Y 的位置now=array[i] sum+=now-now-N array[i] array[l])<=(array[r]-now i>=0 目前的位置变为当前的位置now=array[i] 先向磁道号先向磁道号now=array[i] 减小方向访增加方向访N 问，再向磁问，再向磁道号增加方道号减小方向访问 向访问 i

40

11.电梯调度的主要思想如下：

该算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，电梯调度考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外的访问，直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动。这时，同样也是每次选择这样的进程来调度，即要访问的磁道在当前位置内距离最近者，这样，磁头又逐步地从外向里移动直至再无更里面的磁道要访问。 12电梯调度的主要算法如下：

void SCAN(int array[],int m) //扫描算法 {

int temp; int k=1; int now,d,l,r; int i,j; float sum=0; float avg=0; for (i=0;i

if (array[i]>array[j]) //将磁道号从小到大排序 {

temp=array[i]; array[i]=array[j]; array[j]=temp; } }

printf(\请输入当前的磁道号：\\n\输入当前磁道号 scanf(\

printf(\请输入当前移动臂的移动的方向(1 表示向磁道号增加方向,0 表示向磁道号减小方向): \\n\ scanf(\ //先要给出当前磁道号和移动臂的移动方向 printf(\扫描算法(SCAN)调度后的序列为:\\n\

if (array[m-1]<=now) //若被访问的下一最大的磁道号不大于当前的磁道号

41

{

for (i=m-1;i>=0;i--) {

printf(\输出磁盘调度序列 sum=now-array[i]; now=array[i]; } } else {

if (array[0]>=now) //若被访问的下一最小的磁道号不小于当前的磁道号 {

for (i=0;i

printf(\输出磁盘调度序列 sum=array[i]-now; now=array[i]; } }

else //当前的磁道号的值在若所有被访问的下的磁道号之间 {

while (array[k]

case 0: //先向磁道号减小方向访问 {

while (l>=0) {

printf(\输出磁盘调度序列 sum=sum+now-array[l]; now=array[l]; l=l-1; }

now=array[0];

42

for (j=r;j

printf(\输出磁盘调度序列 sum+=array[j]-now; now=array[j]; } break; }

case 1: //先向磁道号增加方向访问 {

while (r

printf(\输出磁盘调度序列 sum+=array[r]-now; now=array[r]; r=r+1; }

now=array[m-1]; for (j=l;j>=0;j--) {

printf(\ //输出磁盘调度序列 sum+=now-array[j]; now=array[j]; } break; } default:

printf(\输入有误\\n\ } } }

avg=sum/(m);

printf(\平均寻道长度：%f\\n\输出平均寻道长度 printf(\移动的总道数:%f\\n\}

13.电梯调度的主要流程图如下：

43

开始 将磁道号从小到大排序 输入当前磁道号now Y N array[m-1]<=now 输出磁盘调度序列Y (array[0]array[j] >=now N 磁头移动总距离输出磁盘调度确定当前磁道在已排的序列中的位置 sum+=now-array[i] 序列array[j] 输入d=0或1 目前的位置变为当前磁头移动总距离的位置now=array[i] sum+=now-N array[i] d=0 d=1 Y Y i>=0 目前的位置变为当前的位置now=array[i] Y now-N now=array[i] array[l])<=(arraN y[r]-now i

44

13．电梯调度的运行结果如下：

45

六．课程设计小结

本次设计，我用两周的时间完成了操作系统课程设计的程序设计和报告编写，获益匪浅，同时也让我看到了自己的不足。通过这次的课程设计使我认识到要掌握一门学问不仅仅要把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好地巩固所学，灵活运用，才能提高自己实践能力.通过这次的设计使我认识到只停留在表面理解问题是很难使问题得到很好的解决的，实践能力与理论知识同样重要。可以说此课程设计的理论难度并不大，但是若要深入发掘其中的东西，并且实际去编程实现，就遇到了相当大的难度。因为要深入理解某种算法才能够编写出来，这需要自己去自学和实践检验。通过学习进程调度算法模拟，实现了时间片轮转及先来先服务算法；通过学习主存空间的分配与回收，实现了最先适应分配算法，最优适应分配算法，最坏适应分配算法；通过学习模拟DOS文件的建立和使用，学习了模拟设计DOS操作系统中磁盘文件的存储结构和模拟设计便于直接存取的索引文件结构；通过模拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法概念的理解。模拟磁盘调度算法(FCFS,SSTF,SCAN,)，实现各种不同调度算法的过程，并计算各算法的平均寻道长度，这次的编程，不仅让我们明白了操作系统中的算法思想，更让我们明白了解决一个问题的方法，让我们懂得了，要想学好一门知道，就必须将理论和实践结合起来！

46

六．课程设计小结

本次设计，我用两周的时间完成了操作系统课程设计的程序设计和报告编写，获益匪浅，同时也让我看到了自己的不足。通过这次的课程设计使我认识到要掌握一门学问不仅仅要把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好地巩固所学，灵活运用，才能提高自己实践能力.通过这次的设计使我认识到只停留在表面理解问题是很难使问题得到很好的解决的，实践能力与理论知识同样重要。可以说此课程设计的理论难度并不大，但是若要深入发掘其中的东西，并且实际去编程实现，就遇到了相当大的难度。因为要深入理解某种算法才能够编写出来，这需要自己去自学和实践检验。通过学习进程调度算法模拟，实现了时间片轮转及先来先服务算法；通过学习主存空间的分配与回收，实现了最先适应分配算法，最优适应分配算法，最坏适应分配算法；通过学习模拟DOS文件的建立和使用，学习了模拟设计DOS操作系统中磁盘文件的存储结构和模拟设计便于直接存取的索引文件结构；通过模拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法概念的理解。模拟磁盘调度算法(FCFS,SSTF,SCAN,)，实现各种不同调度算法的过程，并计算各算法的平均寻道长度，这次的编程，不仅让我们明白了操作系统中的算法思想，更让我们明白了解决一个问题的方法，让我们懂得了，要想学好一门知道，就必须将理论和实践结合起来！

46

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