1、计算机操作系统课程设计,文志强计算机与通信学院,课程设计内容,任务1 进程管理演示任务2 存储管理系统设计 任务3 编程序模拟银行家算法 任务4 磁盘调度算法的实现与分析 任务5 文件系统演示,任务1 进程管理演示,课程设计内容设计一个允许n个进程并发运行的进程管理模拟系统。,接收进程,就绪队列1,就绪队列2,.,就绪队列n,超时,事件1发生,事件2发生,等待事件1,等事件2,.,处理机,终止进程,事件m发生,等事件m,现代操作系统中进程状态表示方法:,PCB进程控制块其中包括参数进程名name;要求运行时间 runtime;优先级 prior;状态 state;已运行时间runedtime等
2、。为简单起见,只设运行队列,就绪链表,阻塞队列三种数据结构,进程的调度在这两个队列中切换, 每个进程运行时间随机产生,为120之间的整数。时间片的大小由实验者自己定义,可为3或5,优先级也可以随机产生。各进程之间有一定的同步关系(可选),注意进程状态转换的时机。,任务2 存储管理系统设计,实验内容:采用一些常用的存储器分配算法,设计一个请求页式存储管理模拟系统并调试运行。 (1)通过随机数产生一个指令序列,共320条指令。指令的地址按下述原则生成(可选,也可随机产生):50%的指令是顺序执行的; 25%的指令是均匀分布在前地址部分;25%的指令是均匀分布在后地址部分;具体的实施方法是: 在0,
3、319的指令地址之间随机选取一起点m;顺序执行一条指令,即执行地址为m+1的指令;在前地址0,m+1中随机选取一条指令并执行,该指令地址为m;顺序执行一条指令,其地址为m+1;在后地址m+2,319中随机选取一条指令并执行;重复上述步骤,直到执行320次指令。,(2) 将指令序列变成为页地址流设: 页面大小为1k; 用户内存容量分别为4页到32页; 用户虚存容量为32k。在用户虚存中,按每k存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为:第0条-第9条指令为第0页(对应虚存地址为0,9);第10条-第19条指令为第1页(对应许存地址为10,19); .第310条-第319条指令
4、为第31页(对应许存地址为310,319);按以上方式,用户指令可组成32页。,(3)计算并输出下述各种算法在不同内存容量下的命中率 。先进先出的算法(FIFO); 页面失效次数 命中率= 1- 页地址流长度 在本次实验中,页地址长度为320,页面失效次数为每次访问相应指令时,该指令所对应的页不在内存的次数。,3随机数产生办法 关于随机数产生法,系统提供函数srand()和rand(),分别进行初始化和产生随机数。例如: srand();语句可初始化一个随机数; a0=rand()%320; a1=rand()%a0; S= a1+ rand()%(a0- a1) 语句可用来产生a0与a1中的
5、随机数。,整个算法的思想,见下页,pn pfn next,0,1,2,3,页表结构,空闲物理页框,初始状态,freefp_head,pn表示页号;pfn表示有效位,当页帧不在内存时为1,否则为指向其内存地址。,6 6 -1,pn pfn next,1,2,3,页表结构,空闲物理页框,第一次分配,6 ,Busypf_head,Busypf_tail,27 27 -1,pn pfn next,27 1 ,2,3,页表结构,空闲物理页框,第二次分配,freefp_head,6,Busypf_head,Busypf_tail,28 28 -1,pn pfn next,27 1,28 2 ,3,页表结构
6、,空闲物理页框,第三次分配,freefp_head,6,Busypf_head,Busypf_tail,30 30 -1,pn pfn next,27 1,28 2,30 3 ,页表结构,空闲物理页框,第四次分配,freefp_head,6,Busypf_head,Busypf_tail,第五次分配,2 2 -1,pn pfn next,27 1,28 2,30 3 ,页表结构,空闲物理页框,第五次,淘汰一页,freefp_head,6 ,Busypf_head,Busypf_tail,2 2 -1,pn pfn next,27 1,28 2,30 3,页表结构,空闲物理页框,第五次,分配一页
7、,freefp_head,2 ,Busypf_head,Busypf_tail,扩展的银行家算法描述n为系统中的进程个数。m为系统中的资源类型数。Available(1:m):现有资源向量。Available(j)=k表示有k个未分配的j类资源。如: Available(9,3,6)Max(1:n,1:m):资源最大申请量矩阵。Max(i,j)=k表示第i个进程对第j类资源的最大申请量为k.,任务3 编程序模拟银行家算法,编制银行家算法程序,并检测所给状态的系统安全性。,Allocation(1:n,1:m):资源分配矩阵。Allocation(i,j)=k表示进程i已占有k个j类资源。Nee
8、d(1:n,1:m):进程以后还需要的资源矩阵。Need(i,j)=k表示第i个进程以后还需要k个第j类资源。显然Need=Max-AllocationRequest(1:n,1:m):进程申请资源矩阵。Request(i,j)=k表示进程i申请k个第j类资源。,资源分配程序的工作过程描述: 基本思想:当进程提出资源申请时,系统首先检查该进程对资源的申请量是否超过其最大需求量,以及系统现有资源能否满足进程需要。若能,则进一步检查:若把资源分给该进程,系统能否处于安全状态?若安全则分配,否则置该进程为等待资源状态。 为简单起见,记Ai为A(i,1),A(i,2),A(i,m),其中A为nm矩阵。
9、 定义长度为m的向量X,Y间的关系为: XY当且仅当X(i)Y(i)(i=1,2,m),1.如果RequestiNeedi则报错返回。 2.如果RequestiAvailable,则进程i进入等待资源状态,返回。 3.假设进程i的申请已获准,于是修改系统状态:Available =Available - Requesti Allocationi= Allocationi + Requesti Needi = Needi - Requesti 4.调用安全状态检查算法。,设进程i申请资源,申请资源向量为Requesti,则有如下的资源分配过程:,(续) 5.若系统处于安全状态,则将进程i申请的资
10、源分配给进程i,返回。 6.若系统处于不安全状态,则进程i进入等待资源状态,并恢复系统状态后返回: Available =Available+ Requesti Allocationi = Allocationi - Requesti Needi = Needi + Requesti,安全状态检查算法: 设Work(1:m)为临时工作向量。初始时Work=Available.令N=1,2,n 1.寻找jN 使其满足NeedjWork,若不存在这样的j 则转(3); 2.Work =Work+Allocationj N =N-j ,转(1); 3.如果N 为空则返回系统安全;如果N不为空则返回系
11、统不安全。 算法时间复杂度为O(mn2),如果每类资源只有一个,则时间复杂度为O(n2),T0时刻的安全性 利用安全性算法对T0时刻的安全性进行分析,如下表,可知T0时刻存在一个安全序列P2、P1、P3、P4,所以系统是安全的。,(2) P2请求资源P2发出请求向量Request2(1,0,1),系统按银行家算法进行检查:Request2(1,0,1) = Need2(1,0,2)Request2(1,0,1)= Available(1,1,2)3) 系统先假定可为P2分配资源,并修改Available、 Allocation2、 Need2向量,资源变化情况如下表。,4) 再利用安全性算法检
12、查此时系统是否安全,如下表。可知存在一个安全序列P2、P1、P3、P4,所以系统是安全的,可以立即将P2所申请的资源分配给它。,(3) P1请求资源P1发出请求向量Request1(1,0,1),系统按银行家算法进行检查:Request1(1,0,1) = Need1(2,2,2)Request1(1,0,1) Available(0,1,1),让P1等待,(4) P3请求资源P3发出请求向量Request3(0,0,1),系统按银行家算法进行检查:Request3(0,0,1) = Need3(1,0,3)Request3(0,0,1)= Available(0,1,1)3) 系统先假定可为
13、P3分配资源,并修改Available、 Allocation3、 Need3向量,资源变化情况如表5。,表5 P3申请资源后的资源分配表,4) 再利用安全性算法检查此时系统是否安全,从上表可看出,可用资源Available(0,1,0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不分配资源给P3。,任务4 磁盘调度算法的实现与分析,编程序实现下述磁盘调度算法,并求出每种算法的平均移动磁道数,并分析结果:先来先服务算法(FCFS)最短寻道时间优先算法(SSTF)扫描算法(SCAN)循环扫描算法(C-SCAN),磁盘调度策略,1 、先来先服务FCFS (First Come Firs
14、t Server) :这是最简单的磁盘调度策略,它根据进程请求访问磁盘的时间顺序进行调度。2 、最短寻道时间优先SSFT (Shortest Seek Time First) :它是根据磁头当前的位置,选择请求队列中距离磁头最短的请求响应。3 、SCAN :也称电梯策略,要求磁头臂仅仅沿一个方向移动,并在途中满足所有未完成的请求,直到它到达这个方向的最后一个磁道,或这个方向没有别的请求为止,然后倒转服务方向,同样按顺序完成的有请求。4 、CSCAN :是循环扫描法,当到达最后一个磁道时,磁头臂返回到磁头的另一端,并再次开始扫描。,假设磁盘有200个磁道,磁盘请求队列中是一些随机请求。被请求的磁
15、道按接收顺序分别为:55、58、39、18、90、160、150、38、184,当前磁头在100磁道处FCFS策略磁头臂的移动轨迹如下:,18,38,39,55,58,90,150,160,184,100,假设磁盘有200个磁道,磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为:55、58、39、18、90、160、150、38、184,当前磁头在100磁道处SSTF策略磁头臂的移动轨迹如下:,18,38,39,55,58,90,150,160,184,100,假设磁盘有200个磁道,磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为:55、58、39、18、90、160、1
16、50、38、184,当前磁头在100磁道处SCAN策略磁头臂的移动轨迹如下:,18,38,39,55,58,90,150,160,184,100,200,假设磁盘有200个磁道,磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为:55、58、39、18、90、160、150、38、184,当前磁头在100磁道处C-SCAN策略磁头臂的移动轨迹如下:,18,38,39,55,58,90,150,160,184,100,200,调度策略的比较,任务5 文件系统演示,课程设计内容设计一个简单的多用户文件系统。即在系统中用一个文件来模拟一个磁盘;此系统至少有:Create、delete、open、close、read、write等和部分文件属性的功能实现这个文件系统。 能实际演示这个文件系统。基本上是进入一个界面(此界面就是该文件系统的界面)后,可以实现设计的操作要求。,文件系统总体数据结构图,注意:对于物理块的访问(包括访问指针,空闲位)需要经过输入输出,相当于通过定位对文件进行读写。打开文件目录(AFD)是在内存中,由打开文件时创建。,
Copyright © 2018-2021 Wenke99.com All rights reserved
工信部备案号:浙ICP备20026746号-2
公安局备案号:浙公网安备33038302330469号
本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。