北华航天工业学院
《操作系统》
课程设计报告
课设报告题目:进程调度算法、
银行家算法、虚拟内存中的页面置换
磁盘调度算法
作者所在系部:计算机科学与工程系作者所在专业:计算机科学与技术作者所在班级:B09512
作者姓名:丁小玲
指导教师姓名:赵辉
完成时间:2011.12.14
北华航天工业学院教务处制
随着科学技术的发展,计算机在人们的生活领域中占据了重要的地位。计算机中最最关键的就是操作系统,它直接对计算机的硬件就行了管理,为人们提供了人机界面,使人们可以更方便高效的利用电脑。我们应该掌握操作系统中进程调度,内存管理,设备管理以及文件管理中重要的过程,这样有利于我们以后更好的了解操作系统。
进程调度算法主要有三种算法,分别是先来先服务、短进程优先算法和高响应比优先算法;银行家算法主要是针对资源分配后,系统是否安全的判断;虚拟内存中的页面置换主要有三种算法,分别是先进先出算法、最近最久未使用算法和最佳置换算法;磁盘调度算法主要有三种算法,分别是先来先服务算法、最短寻道时间优先算法、扫描算法和循环扫描算法。
关键词:先进先出安全算法循环扫描最短寻道
第一章绪论 (1)
1.1 课程设计的背景和意义 (1)
1.1.1 课程设计的理论研究基础 (1)
1.1.2 课程设计的意义 (1)
1.2 课程设计环境 (2)
第二章需求分析 (3)
2.1 功能要求 (3)
2.1.1 进程调度算法 (3)
2.1.2银行家算法 (3)
2.1.3 虚拟内存中的页面置换 (3)
2.1.4 磁盘调度算法 (3)
2.2 问题的解决方案 (4)
2.2.1 进程调度算法 (4)
2.2.2银行家算法 (4)
2.2.3 虚拟内存中的页面置换 (4)
2.2.4 磁盘调度算法 (5)
第三章系统设计 (6)
3.1 数据设计 (6)
3.1.1 结构体设计 (6)
3.1.2 函数设计 (6)
第四章系统实现 (9)
4.1 结构体实现 (9)
4.1.1 进程调度算法 (9)
4.2 函数实现 (9)
4.2.1进程调度算法 (9)
4.2.2银行家算法 (12)
4.2.3虚拟内存中的页面置换算法 (13)
4.2.4磁盘调度算法 (17)
4.3 主函数实现 (19)
4.3.1 进程调度算法的运行界面 (19)
4.3.2 银行家算法的运行界面 (19)
4.3.3 虚拟内存中的页面置换的运行界面 (20)
4.3.4磁盘调度算法的运行界面 (21)
4.4 系统界面 (21)
4.4.1 进程调度算法的运行界面 (21)
4.4.2 银行家算法的运行界面 (22)
4.4.3 虚拟内存中的页面置换算法的运行界面 (22)
4.4.4 磁盘调度算法的运行界面 (22)
第五章系统测试 (23)
5.1 模块测试 (23)
5.1.1 进程调度算法的模块测试 (23)
5.1.2 银行家算法的模块测试 (23)
5.1.3虚拟内存中的页面置换算法的模块测试 (24)
5.1.4 磁盘调度算法的模块测试 (25)
5.2 课程设计过程中遇到的问题 (26)
总结 (27)
致谢 (28)
参考文献 (29)
附录 (30)
第一章绪论
随着科学技术的发展,计算机在人们的生活领域中占据了重要的地位。计算机中最最关键的就是操作系统,它直接对计算机的硬件就行了管理,为人们提供了人机界面,使人们可以更方便高效的利用电脑。因此我们要掌握操作系统的主要功能,以及这些功能是在计算机中如何实现的,了解以前到现在的操作系统的发展。
1.1 课程设计的背景和意义
1.1.1 课程设计的理论研究基础
进程调度算法使用了先来先服务,短进程优先算法和高响应比优先算法,根据输入进程的个数和提交时刻不同,使用相关的算法模拟进程在系统中的执行次序。先来先服务主要是根据进程的提交时刻来定,短进程优先是根据进程的运行时间来定,高响应比是根据进程运行时间和等待时间共同确定。但是它们的关键都是确定上一个进程的完成时刻和下一个进程的提交时刻进行比较来确定下一个进程的开始时刻。
银行家算法是模拟了系统中五个进程对三种资源的争夺,使这五个进程可以合理共享系统中的有限的三种资源,避免死锁。在每个进程进行申请资源的时候,首先判断申请是否符合实际情况,若不符合,提示错误,若符合,给其分配,然后用安全算法来测试系统此时是否还处于安全状态,要是不安全,不予分配,给出相关提示,反之分配成功。
虚拟内存中的页面置换,由于内存空间有限,所以只是把部分页面调入内存,当所要访问的页面不在内存中的时候,要把此页面与内存中已经存在的页面替换。现在分别使用了先进先出算法,最近最久未使用算法和最佳置换算法来进行页面置换,最佳置换算法只是作为参考,因为在实际中无法实现,其他两种置换算法根据访问页面序列的不同,出现不同的缺页率,从而判定哪种算法更好一些。
磁盘调度算法,由于现在磁盘的传输速率越来越高,因此访问磁盘的时间中,主要是寻道时间,所以磁盘调度的目标是使磁盘的平均寻道时间达到最少。在磁盘调度算法中使用了先来先服务算法,最短寻道时间优先算法,扫描算法和循环扫描算法,然后分别计算出了它们的平均寻道时间,来比较这几种算法的优劣程度。
1.1.2 课程设计的意义
在多道程序系统中,多个进程并发执行时,往往容易产生死锁。银行家算法可以判断每次如果分配给相关进程申请的资源系统是否还处于安全状态,若不安全就不予分配,这
样就避免了死锁的发生。虚拟内存中页面置换可以模拟了内存中给每个进程分配一定的物理块,当这些块中存放的页面没有当前要访问的页面的时候,就发生置换,这样就不必把所有要访问的序列都提前调入内存中,节省了内存的空间,可以实现多个进程的并发执行。磁盘调度算法实现了多访问多个磁道的时候,哪种算法是最好的,因为磁盘寻道时间占据了访问磁盘的主要时间,所以如何减少寻道时间是操作系统在访问磁盘必须考虑的问题。
1.2 课程设计环境
软件环境:Microsoft Visual Studio 2010 Windows 7
硬件环境:Lenovo CPU T6600
第二章需求分析
2.1 功能要求
2.1.1 进程调度算法
编程实现进程调度算法的基本过程,设计要求:
(1)能够选择进程调度算法(先来先服务、短进程优先算法和高响应比优先算法)。
(2)可以输入进程数目(至少4个进程),以及各进程的提交时间和运行时间。
(3)能够显示调度过程及平均周转时间和平均带权周转时间。
2.1.2银行家算法
编写一程序,能够模拟银行家算法和安全算法来避免死锁。假设系统资源有A、B、C 三种,可以运行5个进程。该程序具备的基本功能为:
1、程序可以输入3种资源的数目,5个进程对3种资源的最大需求量、已分配量和需求量。
2、能够判断某一时刻系统是否处于安全状态,如果处于安全状态能够给出安全序列。
3、当某进程提出资源申请时,能够判断是否能把资源分配给申请进程。
2.1.3 虚拟内存中的页面置换
编程实现虚拟内存中的页面置换的基本过程,设计要求:
(1)能够输入进程的页面访问序列和分配的内存块数。
(2)可以选择页面置换算法(先进先出算法、最近最久未使用算法和最佳置换算法)。
(3)能够以下图形式显示页面置换过程。
2.1.4 磁盘调度算法
编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度。设计要求:
(1)能够输入程序要访问的磁道序列和磁头当前所在的磁道数。
(2)可以选择某磁盘调度算法(先来先服务算法、最短寻道时间优先算法、扫描算法和循环扫描算法)。
(3)能够以下图形式显示磁盘调度顺序和平均寻道长度。
2.2 问题的解决方案
2.2.1 进程调度算法
先来先服务算法,按照进程的提交时刻对进程进行执行,当执行下一个进程的时候,注意比较这个进程提交与上个进程的完成时刻,若上一个进程的完成时刻比此进程的提交时刻晚,那么此进程的开始时刻就是上一个进程的完成时刻。
短进程优先算法,首先确定第一个进程的完成时刻,然后找出提交时刻比第一个进程完成时刻早的进程,从它们中挑出一个运行时间最小的进程开始执行,如此循环即可。
高响应比优先算法,首先确定第一个进程的完成时刻,然后找出提交时刻比第一个进程完成时刻早的进程,然后分别计算它们优先权,从它们中挑出一个优先权最高的进程开始执行开始执行,如此循环即可。
2.2.2银行家算法
首先对系统中三种资源的数目进行控制,然后输入五个进程需要的资源数目和系统已经分配给的各类资源数目。然后求出系统中还可以利用的资源,利用安全算法计算是否可以把这五个进程执行完成,若存在这五个进程执行的一个序列,说明系统处于安全状态,不会发生死锁,反正不安全。在银行家算法中,当有的进程在申请资源时,系统假设把资源分配给此进程,然后调用安全算法,看现在的系统是否安全,如果安全,给此进程进行资源分配,反之不分配。
2.2.3 虚拟内存中的页面置换
先进先出算法,当页面要发生置换的时候,把最先进入内存的页面进行置换,所以用了一个数组来记录内存中每个页面是什么时候进入内存的,当要发生置换的时候,挑选出数组中值最小的元素的下标,这个页面就是要被置换的页面。
最近最久未使用算法,当发生页面置换的时候,把最近最久未使用的页面进行置换,所以用了一个数组来记录内存中每个页面是什么时候被使用的,当要发生置换的时候,挑选出数组中值最小的元素的下标,这个页面就是要被置换的页面。
最佳置换算法,当发生页面置换的时候,把在内存中的页面在以后页面序列中最晚出现或者不出现的页面置换,所以用了一个数组来记录内存中每个页面是在以后页面序列中出现的下标,当要发生置换的时候,挑选出数组中值最大的元素的下标,这个页面就是要被置换的页面。
2.2.4 磁盘调度算法
先来先服务算法,按照输入的磁道的输入序列依次开始访问。
最短寻道时间优先算法,从输入的磁道序列中找出离当前磁道最近的磁道进行访问,然后接着以此类推,开始循环,直到要访问的磁道序列结束。
扫描算法,将输入的磁道序列和当前磁道序列进行比较,把磁道序列分成两类,然后由当前磁道从里向外开始访问磁道序列,直到最大,然后再从外向内访问。
循环扫描算法,将输入的磁道序列和当前磁道序列进行比较,把磁道序列分成两类,然后由当前磁道从里向外开始访问磁道序列,直到最大,然后再从最内部的磁道开始访问。
第三章系统设计
3.1 数据设计
3.1.1 结构体设计
1. 进程调度算法的结构体设计
把每个进程定义成了一个结构体,这个结构体有进程的提交时刻commit,开始时刻strat,等待时间wait,完成时刻finish,运行时间run,周转时间turn,带权周转时间powerturn,以及标识进程是否已执行的标志flag和系统中进程的执行次序seq。
2. 银行家算法的设计
用了一些全局变量的数组。source[3]系统中提供给的A,B,C的最大资源数,Max[5][3]五个进程中需要的资源,need[5][3] 五个进程还需要的资源,allocation[5][3] 五个进程已经分配的资源,available[3] 系统中还可以使用的资源,temp[5]代表安全序列。
3. 虚拟内存中页面置换算法的设计
用一个一维数组表示页面访问序列,一个二维数组来模拟内存中的块以及页面置换的过程。
4. 磁盘调度算法的设计
使用了两个一维数组,一个数组用来表示要访问的磁道序列,另一个数组用来表示对应磁道的移动磁道数,然后根据移动的磁道数来计算出平均寻道长度。
3.1.2 函数设计
1. 进程调度算法
void Input(process d[],DataType a[],DataType b[],int n);
输入函数,对输入的进程进行初始化
void Output(process d[],int n);
输出函数,显示进程的调度以及平均周转时间和平均带权周转时间
void Sort(DataType a[],DataType b[],int n);
排序函数,用来给进程的提交时刻等排序
void FCFS(process d[],int n);
先来先服务算法,根据每个进程的提交时刻从小到大排序,然后进行条件选择,只有要执行的进程的提交时刻比上一个进程的完成时刻早才符合执行条件。
void SPF(process d[],int n);
短进程优先算法,首先确定第一个进程的完成时刻,然后找出提交时刻比第一个进程完成时刻早的进程,从它们中挑出一个运行时间最小的进程开始执行,如此循环即可。
void HRF(process d[],int n);
高响应比优先算法,首先确定第一个进程的完成时刻,然后找出提交时刻比第一个进程完成时刻早的进程,然后分别计算它们优先权,从它们中挑出一个优先权最高的进程开始执行开始执行,如此循环即可。
2. 银行家算法
void Assign(int request[],int n,int k);
分配函数,当一个进程进行资源申请的时候,给它分配资源
void Recover(int request[],int n,int k);
回收函数,当一个进程的申请会引起系统不安全的时候,撤销刚刚给其分配的资源int Safe();
安全算法,来判断此时系统是否存在一个安全序列
void Ask();
申请资源函数,当一个进程的申请引起系统不安全的时候,给出相关提示,不给进程分配资源
3. 虚拟内存中的页面置换
void Replace(int A[][Piece],int n);
转换函数,把数组A[n][Piece]转成A[Piece][n]的形式
void FIFO(int d[],int n);
先进先出算法,把最先进入内存的页面进行置换,所以用了一个数组来记录内存中每个页面是什么时候进入内存的,当要发生置换的时候,挑选出数组中值最小的元素的下标,这个页面就是要被置换的页面。
void LRU(int d[],int n);
最近最久未使用算法,当发生页面置换的时候,把最近最久未使用的页面进行置换,所以用了一个数组来记录内存中每个页面是什么时候被使用的,当要发生置换的时候,挑选出数组中值最小的元素的下标,这个页面就是要被置换的页面。
void OPT(int d[],int n);
最佳置换算法,当发生页面置换的时候,把在内存中的页面在以后页面序列中最晚出现或者不出现的页面置换,所以用了一个数组来记录内存中每个页面是在以后页面序列中出现的下标,当要发生置换的时候,挑选出数组中值最大的元素的下标,这个页面就是要被置换的页面。
4. 磁盘调度算法
DataType Fab(DataType x);
求绝对值的函数
void Ouput(DataType R[],DataType R1[],int n,int x);
根据选择的算法来进行输出
void FCFS(DataType R[],DataType R1[],int n);
先来先服务算法,按照输入的磁道的输入序列依次开始访问。
void SSort(DataType R[],int n);
把数组R[n]从小到大进行排序
void NSort(DataType R[],int n);
把数组R[n]从大到小进行排序
void SSTF(DataType R[],DataType R1[],int n,DataType x);
最短寻道时间优先算法,从输入的磁道序列中找出离当前磁道最近的磁道进行访问,然后接着以此类推,开始循环,直到要访问的磁道序列结束。
void SCAN(DataType R[],DataType R1[],int n);
扫描算法,将输入的磁道序列和当前磁道序列进行比较,把磁道序列分成两类,然后由当前磁道从里向外开始访问磁道序列,直到最大,然后再从外向内访问。
void CSCAN(DataType R[],DataType R1[],int n);
循环扫描算法,将输入的磁道序列和当前磁道序列进行比较,把磁道序列分成两类,然后由当前磁道从里向外开始访问磁道序列,直到最大,然后再从最内部的磁道开始访问。
第四章系统实现4.1 结构体实现
4.1.1 进程调度算法
typedef struct{
int seq;//标志执行次序
int flag;//标志是否执行,1表示已执行,0表示未执行
double commit;//提交时刻
double strat;//开始时刻
double wait;//等待时间
double finish;//完成时刻
double run;//运行时间
double turn;//周转时间
double powerturn;//带权周转时间
}process;
4.2 函数实现
4.2.1进程调度算法
void Input(process d[],DataType a[],DataType b[],int n);// 输入函数
{
for(int i=0;i { d[i].commit = a[i]; d[i].run = b[i]; d[i].finish = 0.0; d[i].flag = 0; d[i].powerturn = 0.0; d[i].seq = i+1; d[i].strat = 0.0; d[i].turn = 0.0; d[i].wait = 0.0; } } void Output(process d[],int n);// 输出函数 { DataType avgturn=0; DataType avgpower=0; for(int i=0;i { avgturn = avgturn + d[i].turn; avgpower = avgpower + d[i].powerturn; } avgturn = avgturn/n; avgpower = avgpower/n; cout<<" 执行"<<"提交"<<"开始"<<"等待"<<"完成"<<"运行"<<"周转"<<"带权周"< cout<<" 次序"<<"时刻"<<"时刻"<<"时间"<<"时刻"<<"时间"<<" 时间"<<"转时间"< for(int i=0;i { cout< cout< cout< cout< cout< cout< cout< cout< } cout<<"此调度算法的平均周转时间为:"< cout<<"此调度算法的平均带权周转时间为:"< } void Sort(DataType a[],DataType b[],int n);// 排序函数 { int i,j,swap; DataType x,y; for(i=0;i { swap=0; for(j=0;j { if(a[j]>a[j+1]) { x=a[j]; a[j]=a[j+1]; a[j+1]=x; y=b[j]; b[j]=b[j+1]; b[j+1]=y; swap=1; } } if(swap==0) break; } } void FCFS(process d[],int n);// 先来先服务算法{ for(int i=0;i d[i].seq = i+1; d[0].strat = d[0].commit ; d[0].finish = d[0].strat + d[0].run ; d[0].wait = 0.0; d[0].turn = d[0].run ; d[0].powerturn = 1.0; d[0].flag = 1; for(int i=1;i { if(d[i].commit > d[i-1].finish||d[i].commit == d[i-1].finish) { d[i].strat = d[i].commit ; d[i].wait = 0.0; } else { d[i].strat = d[i-1].finish ; d[i].wait = d[i-1].finish - d[i].commit ; } d[i].flag = 1; d[i].finish = d[i].strat + d[i].run ; d[i].turn = d[i].finish - d[i].commit ; d[i].powerturn = d[i].turn / d[i].run ; } Output(d,n); } void SPF(process d[],int n);// 短进程优先算法 { process a[MAX],b[MAX]; DataType x,y; x=d[0].commit; y=d[0].run; int c[MAX]; int k=0,l=0,h=0; DataType min; for(int i=1;i if(x==d[i].commit&&y>d[i].run) { x=d[i].commit; y=d[i].run; l=i; } d[l].flag = 1; a[h] = d[l]; a[h].strat = a[h].commit ; a[h].finish = a[h].commit + a[h].run ; a[h].wait = a[h].strat - a[h].commit ; a[h].turn = a[h].finish - a[h].commit ; a[h].powerturn = a[h].turn / a[h].run ; h++; for(int j=0;j { k=0;