CPU调度算法的模拟实现 页面置换算法的模拟实现 磁盘调度算法的模拟实现.docx

CPU调度算法的模拟实现 页面置换算法的模拟实现 磁盘调度算法的模拟实现.docx

《CPU调度算法的模拟实现 页面置换算法的模拟实现 磁盘调度算法的模拟实现.docx》由会员分享，可在线阅读，更多相关《CPU调度算法的模拟实现 页面置换算法的模拟实现 磁盘调度算法的模拟实现.docx（21页珍藏版）》请在冰点文库上搜索。

CPU调度算法的模拟实现页面置换算法的模拟实现磁盘调度算法的模拟实现

课程设计说明书

设计题目：

操作系统课程设计

班级：

软件工程专业2009-1

学号：

************

******

山东科技大学

2011年12月27日

课程设计任务书

学院信息科学与工程专业软件工程班级09-1姓名于闯英

一、课程设计题目：

操作系统课程设计

二、课程设计主要参考资料

（1）计算机操作系统（第三版）

（2）程序设计基础（基于C语言）

（3）C++面向对象程序设计

三、课程设计应解决的主要问题：

（1）CPU调度算法的模拟实现

（2）页面置换算法的模拟实现

（3）磁盘调度算法的模拟实现

四、课程设计相关附件（如：

图纸、软件等）：

（1）codeblocks8.02编程软件

五、任务发出日期：

2011-11-1课程设计完成日期：

2011-12-27

指导教师签字：

指导教师对课程设计的评语

成绩：

指导教师签字：

年月日

设计1CPU调度算法的模拟实现

一、设计目的

通过CPU调度相关算法的实现，了解CPU调度的相关知识，通过实现CPU调度算法，理解CPU的管理，以及不同的CPU调度算法实现过程。

体会算法的重要性。

二、设计要求

1、编写算法，实现FCFS、非抢占SJF、可抢占优先权调度、RR

2、针对模拟进程，利用CPU调度算法进行调度

3、进行算法评价，计算平均周转时间和平均等待时间

4、调度所需的进程参数由输入产生（手工输入或者随机数产生）

5、输出调度结果

6、输出算法评价指标

三、设计说明

1、采用数组存储进程属性；

course[100][6];

course的行坐标是进程名，course的纵坐标0表示进程到达时间，1表示服务时间，2表示开始服务时间，3表示完成时间，5表示优先级

2、FCFS

先来先服务调度算法是一种最简单的调度算法，当作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个最先进入该队列的作业

3、非抢占SJF

短作业优先调度算法，是指对短作业有限调度算法。

是从后备队列中选择一个估计运行时间最短的作业将他们调入内存。

4、可抢占优先权调度

在这种方式下，系统把处理机分配给优先级最高的进程，使之执行。

但在其执行期间，只要出现另一个其优先权更高的进程，进程调度程序就立即停止当前进程（原优先权最高的进程）的执行，重新将处理及分配给新到的优先权最高的进程。

5、RR

系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首的进程并令其执行一个时间片。

当执行的时间片用完时，有一个计时器发出时钟中断请求。

调度程序便据此信号来停止该进程的执行，并将他送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首过程。

四、运行结果及分析

输入进程的数量。

五、总结

1、刚开始没想好count中该存储几种属性结果多出了一个本来是要存储周转时间的，但是周转时间用完成时间和开始时间可求便没有存储；另外因为在main函数中不需要完成时间和开始时间所以程序中并没有将完成时间和开始时间存到count中；

2、编写程序时本来是跟算法思想来设计程序，但是模拟毕竟与实际不同，比如没有中断请求，没有真正时间观念，所以所设计程序只是将个算法算出结果显现，并非模拟算法过程；

设计2页面置换算法的模拟实现

一、设计目的

通过实现页面置换算法的FIFO和LRU两种算法，理解进程运行时系统是怎样选择换出页面的，对于两种不同的算法各自的优缺点是哪些。

二、设计要求

1、编写算法，实现页面置换算法FIFO、LRU；

2、针对内存地址引用串，运行页面置换算法进行页面置换；

3、算法所需的各种参数由输入产生（手工输入或者随机数产生）；

4、输出内存驻留的页面集合，页错误次数以及页错误率；

三、设计说明

1、采用数组页面的页号

2、FIFO算法，选择在内存中驻留时间最久的页面予以淘汰；

分配n个物理块给进程，运行时先把前n个不同页面一起装入内存，然后再从后面逐一比较，输出页面及页错误数和页错误率。

3、LRU算法，根据页面调入内存后的使用情况进行决策；

同样分配n个物理块给进程，前n个不同页面一起装入内存，后面步骤与前一算法类似。

四、运行结果及分析

自动运行结果。

五、总结

因为对移位不太了解，故用/2和+256来代替右移和最高位加1；

在编码过程中因为把加1和赋值顺序颠倒，导致程序出错；

设计3磁盘调度算法的模拟实现

一、设计目的

通过实现磁盘调度算法，理解磁盘存储器的管理，以及不同的磁盘调度算法实现过程。

二、设计要求

1、编写算法，实现FCFS、SSTF、SCAN、CSAN调度算法

2、针对给定的磁盘访问序列，运行各种调度算法得出调度过程

3、算法所需的各种参数由输入产生（手工输入或者随机数产生）

4、输出调度过程、平均寻道长度

三、设计说明

1、FCFS调度算法：

这是一种最简单的磁盘调度算法，它根据进程请求访问的先后次序进行调度。

2、SSTF调度算法：

该算法要求访问的磁道与当前磁头所在的磁道距离最近，以使每次寻道时间最短。

实现时，先将被访问的磁道号进行从小到大的排序，然后看已排好序的数组最小值是否比用户输入的当前磁道大，若是则按从小到大的顺序输出即为调度过程，若已排好序的数组最大值小于当前磁道，则按从大到小的顺序输出即为调度过程，若两者均不符，则逐一判断k值（数组下标为k的值小于当前磁道，数组下标为k+1的值大于当前磁道），先要判断这两个部分与当前磁道接近的值与当前磁道的距离，先输出距离短的那部分，k值之前的按从大到小输出，k值之后的按从小到大输出。

3、SCAN调度算法：

此算法在考虑到欲访问磁道与当前磁道间的距离基础上，更优先考虑磁头当前的移动方向。

程序中1代表磁道号增加方向，0代表磁道号减小方向，前半部分的数组排序，定位k值都是同于SSTF算法的，只是在此基础上加入磁臂的移动方向。

4、CSCAN调度算法：

为了减少SCAN算法中的延迟，CSCAN算法规定磁头只能单向移动，例如，只是自里向外移动，当磁头移动到最外边时，立即返回到最里的磁道访问，即将最小磁道号紧接着最大磁道号构成循环，代码实现思想同SCAN算法。

四、运行结果及分析

五、总结

完成此算法主要解决排序问题

编码实现

设计1

#include

#include

#include

usingnamespacestd;

voidFCFS（intcou[100][6],intn）{

inti,j;intcourse[n][4];

for（i=0;i

course[0][2]=course[0][0];

course[0][3]=course[0][1]+course[0][2];

for（i=1;i

if（course[i-1][3]>course[i][0]）course[i][2]=course[i-1][3];

elsecourse[i][2]=course[i][0];

course[i][3]=course[i][1]+course[i][2];

}

cout<

<

<

<

for（i=0;i

cout<

<

<

<

<

}

j=0;

for（i=0;i

cout<<"平均周转时间"<

for（i=0;i

cout<<"平均等待时间"<

}

//非抢占

voidSJF（intcou[100][6],intn）{

inta[n],i,j,k,s,p;intcourse[n][4];

for（i=0;i

for（i=1;i

a[0]=0;course[0][2]=course[0][0];course[0][3]=course[0][1]+course[0][2];

s=course[0][3];

for（i=1;i

for（j=1;course[j][0]<=s&&j

{if（a[j]）{p=course[j][1];k=j;break;}}

if（course[j][0]>s&&j

for（;course[j][0]<=s&&j

{if（p>course[j][1]&&a[j]）{p=course[j][1];k=j;break;}}

course[k][2]=s;s+=course[k][1];course[k][3]=s;a[k]=0;

}

cout<

<

<

<

for（i=0;i

cout<

<

<

<

}

j=0;

for（i=0;i

cout<<"平均周转时间"<

for（i=0;i

cout<<"平均等待时间"<

}

voidrob（intcou[100][6],intn）{

inti,j,k=2,l=0,temp;intcourse[n][6];

for（i=0;i

inta[n];//按优先级记录进程

for（i=0;i

intb[200][3];//记录进程顺序

for（i=1;i

for（j=0;j

if（course[a[j]][5]>course[a[j+1]][5]）

{temp=a[j+1];a[j+1]=a[j];a[j]=temp;}

}

}

b[0][0]=-1;b[0][1]=0;b[0][2]=0;b[1][0]=a[0];b[1][1]=course[a[0]][0];

b[1][2]=course[a[0]][0]+course[a[0]][1];

course[a[0]][2]=b[1][1];course[a[0]][3]=b[1][2];

b[2][0]=-1;b[2][1]=10000;b[2][2]=10000;k++;

for（i=1;i

for（j=1;jcourse[a[i]][0]）break;}

for（;j

if（b[j-1][2]<=course[a[i]][0]）{

for（ints=k;s>j;s--）

{b[s][0]=b[s-1][0];b[s][1]=b[s-1][1];b[s][2]=b[s-1][2];}

b[j][0]=a[i];b[j][1]=course[a[i]][0];course[a[i]][2]=b[j][1];

if（b[j+1][1]-course[a[i]][0]>=course[a[i]][1]）{b[j][2]=b[j][1]+course[a[i]][1];k++;course[a[i]][3]=b[j][2];continue;}

else{b[j][2]=b[j+1][1];k++;course[a[i]][1]-=b[j][2]-b[j][1];}

}

course[a[i]][2]=b[j-1][2];

while

（1）{

for（;j

if（b[j][1]-b[j-1][2]>=course[a[i]][1]）{

for（ints=k;s>j;s--）

{b[s][0]=b[s-1][0];b[s][1]=b[s-1][1];b[s][2]=b[s-1][2];}

b[j][0]=a[i];b[j][1]=b[j-1][2];b[j][2]=b[j-1][2]+course[a[i]][1];

k++;break;

}

else{

for（ints=k;s>j;s--）

{b[s][0]=b[s-1][0];b[s][1]=b[s-1][1];b[s][2]=b[s-1][2];}

b[j][0]=a[i];b[j][1]=b[j-1][2];b[j][2]=b[j+1][1];

course[a[i]][1]-=b[j][2]-b[j][1];k++;

}

}

course[a[i]][3]=b[j][2];

}

for（i=0;i

cout<

<

<

<

for（i=0;i

cout<

<

<

<

<

}

j=0;

for（i=0;i

cout<<"平均周转时间"<

for（i=0;i

cout<<"运行过程"<

for（i=1;i

{cout<<"C"<"<

}

//m存储时间片周期

voidRR（intcou[100][6],intn,intm）{

inti,j;intcourse[n][4];

for（i=0;i

intpram[100][2],p=0;intsum=0;//执行时间

for（i=0;i

{if（sum

i=0;

while

（1）{

for（j=0;j

if（course[j][1]==0）continue;

if（course[j][0]>i）break;

if（course[j][1]==cou[j][1]）{course[j][2]=i;}

if（course[j][1]<=m）

{

i+=course[j][1];pram[p][0]=j;pram[p][1]=course[j][1];

p++;course[j][3]=i;course[j][1]=0;

}

else{i+=m;pram[p][0]=j;pram[p][1]=m;p++;course[j][1]-=m;}

}

intk;

for（k=0;k

=0）break;}

if（k==j）{i=course[j][0];}

if（k==n）break;

}

for（i=0;i

cout<<"运行顺序"<

for（i=0;i

cout<

<

<

<

for（i=0;i

cout<

<

<

<

}

j=0;

for（i=0;i

cout<<"平均周转时间"<

for（i=0;i

cout<<"平均等待时间"<

}

intmain（）{

intcourse[100][6];intn;

cout<<"输入进程数量"<>n;

inti,p=0;srand（（int）time（0））;

for（i=0;i

{course[i][0]=p;course[i][1]=rand（）%9+1;course[i][5]=rand（）%9+1;}

course[0][2]=course[0][0];course[0][3]=course[0][1]+course[0][2];

cout<<"FCFS"<

cout<<"SJF"<

cout<<"可抢占优先权调度"<

cout<<"RR"<

}

设计2

#include

usingnamespacestd;

intFIFO（int*num,intorder[100][10],intn,intm）{

order[0][1]=num[0];intsign=2;inti=1;

for（;i

intj=1;

for（;j

if（j==sign）{order[0][sign]=num[i];sign++;}

if（sign>n）break;

}

if（i==m）{order[0][0]=m;return0;}

order[0][0]=i;sign=1;intsignm=1;

for（i++;i

intj=1;

for（;j<=n;j++）{if（order[signm-1][j]==num[i]）break;}

if（j>n）{

for（intk=1;k<=n;k++）{order[signm][k]=order[signm-1][k];}

order[signm][0]=i;order[signm][sign]=num[i];

sign=sign%n+1;signm++;

}

}

returnsignm-1;

}

intLRU（int*num,intorder[100][10],intn,intm）{

order[0][1]=num[0];intsignn[n+1];signn[1]=256;intsign=2;inti=1;

for（;i

intk=0;

for（intj=1;j

{signn[j]/=2;if（order[0][j]==num[i]）{k=1;signn[j]+=256;}}

if（k==0）{order[0][sign]=num[i];signn[sign]=256;sign++;}

if（sig