1、计算机操作系统课程设计计算机操作系统课程设计文志强计算机与通信学院课程设计内容n任务任务1 进程管理演示进程管理演示n任务任务2 存储管理系统设计存储管理系统设计 n任务任务3 编程序模拟银行家算法编程序模拟银行家算法 n任务任务4 磁盘调度算法的实现与分析磁盘调度算法的实现与分析 n任务任务5 文件系统演示文件系统演示 任务1 进程管理演示 n课程设计内容课程设计内容设计一个允许设计一个允许n个进程并发运行的进程管理模拟系统。个进程并发运行的进程管理模拟系统。运行队列运行队列PCBi就绪队列就绪队列PCBjPCBj1PCBj1阻塞队列阻塞队列PCBkPCBk1PCBk1接收进程接收进程就绪队
2、列就绪队列1 1就绪队列就绪队列2 2 .就绪队列就绪队列n超时超时事件事件1 1发生发生事件事件2 2发生发生等待事件等待事件1 1等事件等事件2 2.处理机处理机终止进程终止进程事件事件m发生发生等事件等事件m m现代操作系统中进程状态表示方法: PCB进程控制块进程控制块 其中包括参数其中包括参数进程名进程名name；要求运行时间要求运行时间 runtime；优先级优先级 prior；状态状态 state；已运行时间已运行时间runedtime等。等。 为简单起见，只设运行队列，就绪链表，阻塞队列三种数据结为简单起见，只设运行队列，就绪链表，阻塞队列三种数据结构，进程的调度在这两个队列中
3、切换，构，进程的调度在这两个队列中切换， 每个进程运行时间随机产生，为每个进程运行时间随机产生，为120之间的整数。之间的整数。 时间片的大小由实验者自己定义，可为时间片的大小由实验者自己定义，可为3或或5，优先级也可以随，优先级也可以随机产生。机产生。 各进程之间有一定的同步关系（可选），注意进程状态转换的各进程之间有一定的同步关系（可选），注意进程状态转换的时机。时机。任务2 存储管理系统设计实验内容：采用一些常用的存储器分配算法，设计一个实验内容：采用一些常用的存储器分配算法，设计一个请求页式存储管理模拟系统并调试运行。请求页式存储管理模拟系统并调试运行。 （1 1）通过随机数产生一个指
4、令序列，共通过随机数产生一个指令序列，共320条指令。指令的地址按条指令。指令的地址按下述原则生成（可选，也可随机产生）：下述原则生成（可选，也可随机产生）： 50%的指令是顺序执行的；的指令是顺序执行的； 25%的指令是均匀分布在前地址部分；的指令是均匀分布在前地址部分； 25%的指令是均匀分布在后地址部分；的指令是均匀分布在后地址部分；具体的实施方法是：具体的实施方法是： 在在0，319的指令地址之间随机选取一起点的指令地址之间随机选取一起点m； 顺序执行一条指令，即执行地址为顺序执行一条指令，即执行地址为m+1的指令；的指令； 在前地址在前地址0，m+1中随机选取一条指令并执行，该指令地
5、址为中随机选取一条指令并执行，该指令地址为m； 顺序执行一条指令，其地址为顺序执行一条指令，其地址为m+1; 在后地址在后地址m+2，319中随机选取一条指令并执行；中随机选取一条指令并执行； 重复上述步骤重复上述步骤，直到执行，直到执行320次指令。次指令。（2 2） 将指令序列变成为页地址流将指令序列变成为页地址流设：设： 页面大小为页面大小为1k1k； 用户内存容量分别为用户内存容量分别为4 4页到页到3232页；页； 用户虚存容量为用户虚存容量为32k32k。在用户虚存中，按每在用户虚存中，按每k k存放存放1010条指令排列虚存地址，即条指令排列虚存地址，即320320条指令在虚条指
6、令在虚存中的存放方式为：存中的存放方式为：第第0 0条条- -第第9 9条指令为第条指令为第0 0页（对应虚存地址为页（对应虚存地址为00，99）；）；第第1010条条- -第第1919条指令为第条指令为第1 1页（对应许存地址为页（对应许存地址为1010，1919）；）； . .第第310310条条- -第第319319条指令为第条指令为第3131页（对应许存地址为页（对应许存地址为310310，319319）；）；按以上方式，用户指令可组成按以上方式，用户指令可组成3232页。页。（3 3） 计算并输出下述各种算法在不同内存容量下的命中率计算并输出下述各种算法在不同内存容量下的命中率 。
7、先进先出的算法（先进先出的算法（FIFOFIFO）；）； 页面失效次数页面失效次数 命中率命中率= 1- = 1- 页地址流长度页地址流长度 在本次实验中，页地址长度为在本次实验中，页地址长度为320320，页面失效次数为每次访，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。问相应指令时，该指令所对应的页不在内存的次数。 3 3随机数产生办法随机数产生办法 关于随机数产生法，系统提供函数关于随机数产生法，系统提供函数srand()和和rand()，分别进行初始化和产生随机数。例如：，分别进行初始化和产生随机数。例如： srand()；语句可初始化一个随机数；语句可初始化一个
8、随机数； a0=rand()%320； a1=rand()%a0； S= a1+ rand()%(a0- a1) 语句可用来产生语句可用来产生a0与与a1中的随机数。中的随机数。 整个算法的思想整个算法的思想见下页见下页 i pn pfn 31 31 -1 30 30 -10 0 -1 1 1 -12 2 -1 3 3 -1 4 4 -1 6 6 -1 7 7 -1 5 5 -1 29 29 -1 28 28 -1 27 27 -1 pn pfn nextpn pfn next 0123页页表表结结构构空闲物理页框空闲物理页框初始状态初始状态freefp_headfreefp_headpnpn
9、表示页号；表示页号；pfnpfn表示有效位，当页帧不表示有效位，当页帧不在内存时为在内存时为1 1，否则为指，否则为指向其内存地址。向其内存地址。 6 6 -1 i pn pfn 31 31 -1 30 30 -10 0 -1 1 1 -12 2 -1 3 3 -1 4 4 -1 6 6 0 7 7 -1 5 5 -1 29 29 -1 28 28 -1 27 27 -1 pn pfn nextpn pfn next 0123页页表表结结构构空闲物理页框空闲物理页框第一次分配第一次分配freefp_headfreefp_head 6 6 Busypf_headBusypf_headBusypf
10、_tailBusypf_tail27 27 -1 i pn pfn 31 31 -1 30 30 -10 0 -1 1 1 -12 2 -1 3 3 -1 4 4 -1 6 6 0 7 7 -1 5 5 -1 29 29 -1 28 28 -1 27 27 1 pn pfn nextpn pfn next 027 1 23页页表表结结构构空闲物理页框空闲物理页框第二次分配第二次分配freefp_headfreefp_head 6 6Busypf_headBusypf_headBusypf_tailBusypf_tail28 28 -1 i pn pfn 31 31 -1 30 30 -10 0
11、 -1 1 1 -12 2 -1 3 3 -1 4 4 -1 6 6 0 7 7 -1 5 5 -1 29 29 -1 28 28 2 27 27 1 pn pfn nextpn pfn next 027 128 2 3页页表表结结构构空闲物理页框空闲物理页框第三次分配第三次分配freefp_headfreefp_head 6 6Busypf_headBusypf_headBusypf_tailBusypf_tail30 30 -1 i pn pfn 31 31 -1 30 30 30 0 -1 1 1 -12 2 -1 3 3 -1 4 4 -1 6 6 0 7 7 -1 5 5 -1 29
12、 29 -1 28 28 2 27 27 1 pn pfn nextpn pfn next 027 128 230 3 页页表表结结构构空闲物理页框空闲物理页框第四次分配第四次分配freefp_headfreefp_head 6 6Busypf_headBusypf_headBusypf_tailBusypf_tail第五次分配第五次分配 2 2 -1 i pn pfn 31 31 -1 30 30 30 0 -1 1 1 -12 2 -1 3 3 -1 4 4 -1 6 6 -1 7 7 -1 5 5 -1 29 29 -1 28 28 2 27 27 1 pn pfn nextpn pfn
13、 next 027 128 230 3 页页表表结结构构空闲物理页框空闲物理页框第五次第五次,淘汰一页淘汰一页freefp_headfreefp_head 6 6 Busypf_headBusypf_headBusypf_tailBusypf_tail 2 2 -1 i pn pfn 31 31 -1 30 30 30 0 -1 1 1 -12 2 0 3 3 -1 4 4 -1 6 6 -1 7 7 -1 5 5 -1 29 29 -1 28 28 2 27 27 1 pn pfn nextpn pfn next 027 128 230 3 页页表表结结构构空闲物理页框空闲物理页框第五次第五
14、次,分配一页分配一页freefp_headfreefp_head 2 2 Busypf_headBusypf_headBusypf_tailBusypf_tail扩展的银行家算法描述扩展的银行家算法描述n为系统中的进程个数。为系统中的进程个数。m为系统中的资源类型数。为系统中的资源类型数。Available(j)=k表示有表示有k个未分配的个未分配的j类类资源。资源。如：如： Available(9,3,6)。Max(i,j)=k表示第表示第i个进程对第个进程对第j类资源的最大申请量为类资源的最大申请量为k.r1 r2 r3 224413316223P1P2P3P4任务3 编程序模拟银行家算法
15、 n编制银行家算法程序，并检测所给状态的系统安全性。编制银行家算法程序，并检测所给状态的系统安全性。 。Allocation(i,j)=k表示进程表示进程i已占有已占有k个个j类资源。类资源。Need(i,j)=k表示第表示第i个进程以个进程以后还需要后还需要k个第个第j类资源。显类资源。显然然Need=Max-Allocation。Request(i,j)=k表表示进程示进程i申请申请k个第个第j类资源。类资源。r1 r2 r3 200112115001P1P2P3P4r1 r2 r3 024301201222P1P2P3P4资源分配程序的工作过程描述：资源分配程序的工作过程描述： 基本思想
16、：基本思想：当进程提出资源申请时，系统当进程提出资源申请时，系统首先检查该进程对资源的申请量是否超过首先检查该进程对资源的申请量是否超过其最大需求量，以及系统现有资源能否满其最大需求量，以及系统现有资源能否满足进程需要。若能，则进一步检查：若把足进程需要。若能，则进一步检查：若把资源分给该进程，系统能否处于安全状态？资源分给该进程，系统能否处于安全状态？若安全则分配，否则置该进程为等待资源若安全则分配，否则置该进程为等待资源状态。状态。 为简单起见，记为简单起见，记Ai为为A(i,1),A(i,2),A(i,m)，其，其中中A为为nm矩阵。矩阵。 定义长度为定义长度为m的向量的向量X，Y间的关
17、系为：间的关系为： XY当且仅当当且仅当X(i)Y(i)(i=1,2,m) 1.1.如果如果RequestRequesti iNeedNeedi i则报错返回。则报错返回。 2.2.如果如果RequestRequesti iAvailable,Available,则进程则进程i i进入等待进入等待资源状态，返回。资源状态，返回。 3.3.假设进程假设进程i i的申请已获准，于是修改系统状的申请已获准，于是修改系统状态：态：Available =Available - RequestAvailable =Available - Requesti i AllocationAllocationi i
18、= Allocation= Allocationi i + Request + Requesti i Need Needi i = Need = Needi i - Request - Requesti i 4. 4.调用安全状态检查算法。调用安全状态检查算法。设进程设进程i i申请资源，申请资源向量为申请资源，申请资源向量为RequestRequesti i，则有如下的资源分配过程：，则有如下的资源分配过程：（续）（续） 5.5.若系统处于安全状态，则将进程若系统处于安全状态，则将进程i i申请的申请的资源分配给进程资源分配给进程i i，返回。，返回。 6.6.若系统处于不安全状态，则进程若
19、系统处于不安全状态，则进程i i进入等进入等待资源状态，并恢复系统状态后返回：待资源状态，并恢复系统状态后返回： Available =Available+ RequestAvailable =Available+ Requesti i AllocationAllocationi i = Allocation = Allocationi i - Request - Requesti i NeedNeedi i = Need = Needi i + Request + Requesti i安全状态检查算法：安全状态检查算法： 设设Work(1:m)Work(1:m)为临时工作向量。初始时为临时工
20、作向量。初始时Work=Available.Work=Available.令令N N=1,2,=1,2, ,n n 1. 1.寻找寻找j jN N 使其满足使其满足NeedNeedj jWork,Work,若不若不存在这样的存在这样的j j 则转则转(3);(3); 2.Work =Work+Allocation 2.Work =Work+Allocationj j N N = =N N-j j ,转转(1);(1); 3. 3.如果如果N N 为空则返回系统安全；如果为空则返回系统安全；如果N N不为空不为空则返回系统不安全。则返回系统不安全。n 算法时间复杂度为算法时间复杂度为O(mn2)
21、，如果每类，如果每类资源只有一个，则时间复杂度为资源只有一个，则时间复杂度为O(n2)假定系统中有四个进程假定系统中有四个进程P1P1、P2P2、P3P3、P4P4，三种类型的资，三种类型的资源源R1R1、R2R2、R3R3，数量分别为，数量分别为9 9、3 3、6 6，在，在T0T0时刻的资源时刻的资源分配情况如下表所示。分配情况如下表所示。举例：举例：资源资源进程进程maxmaxAllocationAllocationNeedNeedAvailableAvailableR1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3R1 R2
22、 R3P1P13 2 23 2 21 0 01 0 02 2 22 2 21 1 21 1 2P2P26 1 36 1 35 1 15 1 11 0 21 0 2 P3P33 1 43 1 42 1 12 1 11 0 31 0 3 P4P44 2 24 2 20 0 20 0 24 2 04 2 0 (1)(1)T0T0时刻的安全性时刻的安全性 利用安全性算法对利用安全性算法对T0T0时刻的安全性进行分析，如下表，时刻的安全性进行分析，如下表，可知可知T0T0时刻存在一个安全序列时刻存在一个安全序列P2P2、P1P1、P3P3、P4P4，所以系，所以系统是安全的。统是安全的。资源资源 进程进
23、程WorkWorkNeedNeedAllocationAllocationWork Work +Allocation+AllocationFinishFinishR1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3P2P21 1 21 1 21 0 21 0 25 1 15 1 16 2 36 2 3TrueTrueP1P16 2 36 2 32 2 22 2 21 0 01 0 07 2 37 2 3TrueTrueP3P37 2 37 2 31 0 31 0 32 1 12 1 19 3 49 3 4TrueTru
24、eP4P49 3 49 3 44 2 04 2 00 0 20 0 29 3 69 3 6TrueTrue(2) P2(2) P2请求资源请求资源P2P2发出请求向量发出请求向量RequestRequest2 2(1,0,1),(1,0,1),系统按银行家算法进行检查：系统按银行家算法进行检查：1)1) RequestRequest2 2(1,0,1) = Need(1,0,1) = Need2 2(1,0,2)(1,0,2)2)2) RequestRequest2 2(1,0,1)= Available(1,1,2)(1,0,1)= Available(1,1,2)3) 3) 系统先假定可为
25、系统先假定可为P2P2分配资源，并修改分配资源，并修改AvailableAvailable、 AllocationAllocation2 2、 NeedNeed2 2向量，资源变化情况如下表。向量，资源变化情况如下表。资资 源源进进 程程maxAllocationNeedAvailableR1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3P13 2 21 0 02 2 20 1 1P26 1 36 1 20 0 1 P33 1 42 1 11 0 3 P44 2 20 0 24 2 0 4) 4) 再利用安全性算法检查此时系统是否安全，如下表。可知再利用安全性算法检查此时系统是否
26、安全，如下表。可知存在一个安全序列存在一个安全序列P2P2、P1P1、P3P3、P4P4，所以系统是安全的，所以系统是安全的，可以立即将可以立即将P2P2所申请的资源分配给它。所申请的资源分配给它。资资 源源 进进 程程WorkNeedAllocationWork +AllocationFinishR1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3P20 1 10 0 16 1 26 2 3TrueP16 2 32 2 21 0 07 2 3TrueP37 2 31 0 32 1 19 3 4TrueP49 3 44 2 00 0 29 3 6True(3) P1(3) P1请求
27、资源请求资源P1P1发出请求向量发出请求向量RequestRequest1 1(1,0,1),(1,0,1),系统按银行家算法系统按银行家算法进行检查：进行检查：1)1) RequestRequest1 1(1,0,1) = Need(1,0,1) = Need1 1(2,2,2)(2,2,2)2)2) RequestRequest1 1(1,0,1) Available(0,1,1)(1,0,1) Available(0,1,1)，让，让P1P1等等待待(4) P3(4) P3请求资源请求资源P3P3发出请求向量发出请求向量RequestRequest3 3(0,0,1),(0,0,1),系
28、统按银行家算法系统按银行家算法进行检查：进行检查：1)1) RequestRequest3 3(0,0,1) = Need(0,0,1) = Need3 3(1,0,3)(1,0,3)2)2) RequestRequest3 3(0,0,1)= Available(0,1,1)(0,0,1)= Available(0,1,1)3) 3) 系统先假定可为系统先假定可为P3P3分配资源，并修改分配资源，并修改AvailableAvailable、 AllocationAllocation3 3、 NeedNeed3 3向量，资源变化情况如表向量，资源变化情况如表5 5。表表5 P35 P3申请资源
29、后的资源分配表申请资源后的资源分配表资资 源源进进 程程maxAllocationNeedAvailableR1 R2 R3R1 R2 R3R1 R2 R3R1 R2 R3P13 2 21 0 02 2 20 1 0P26 1 36 1 20 0 1 P33 1 42 1 21 0 2 P44 2 20 0 24 2 0 4) 4) 再利用安全性算法检查此时系统是否安全，从上表可看出，再利用安全性算法检查此时系统是否安全，从上表可看出，可用资源可用资源Available(0,1,0)Available(0,1,0)已不能满足任何进程的需要，已不能满足任何进程的需要，故系统进入不安全状态，此时系
30、统不分配资源给故系统进入不安全状态，此时系统不分配资源给P3P3。任务4 磁盘调度算法的实现与分析 n编程序实现下述磁盘调度算法，并求出每种算法的平编程序实现下述磁盘调度算法，并求出每种算法的平均移动磁道数，并分析结果：均移动磁道数，并分析结果：先来先服务算法（先来先服务算法（FCFS）最短寻道时间优先算法（最短寻道时间优先算法（SSTF）扫描算法（扫描算法（SCAN）循环扫描算法（循环扫描算法（C-SCAN）1 、先来先服务、先来先服务FCFS (First Come First Server) ：这是最简单的这是最简单的磁盘调度策略，它根据进程请求访问磁盘的时间顺序进行调度。磁盘调度策略，
31、它根据进程请求访问磁盘的时间顺序进行调度。2 、最短寻道时间优先、最短寻道时间优先SSFT (Shortest Seek Time First) ：它是它是根据磁头当前的位置，选择请求队列中距离磁头最短的请求响应。根据磁头当前的位置，选择请求队列中距离磁头最短的请求响应。3 、SCAN ：也称电梯策略，要求磁头臂仅仅沿一个方向移动，并也称电梯策略，要求磁头臂仅仅沿一个方向移动，并在途中满足所有未完成的请求，直到它到达这个方向的最后一个磁在途中满足所有未完成的请求，直到它到达这个方向的最后一个磁道，或这个方向没有别的请求为止，然后倒转服务方向，同样按顺道，或这个方向没有别的请求为止，然后倒转服务
32、方向，同样按顺序完成的有请求。序完成的有请求。4 、CSCAN ：是循环扫描法，当到达最后一个磁道时，磁头臂是循环扫描法，当到达最后一个磁道时，磁头臂返回到磁头的另一端，并再次开始扫描。返回到磁头的另一端，并再次开始扫描。假设磁盘有假设磁盘有200个磁道，磁盘请求队列中是一些随个磁道，磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为：机请求。被请求的磁道按接收顺序分别为：55、58、39、18、90、160、150、38、184，当前，当前磁头在磁头在100磁道处磁道处FCFS策略磁头臂的移动轨迹如下：策略磁头臂的移动轨迹如下：18 3839555890150 160184100假设
33、磁盘有假设磁盘有200个磁道，磁盘请求队列中是一个磁道，磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为：些随机请求。被请求的磁道按接收顺序分别为：55、58、39、18、90、160、150、38、184，当前磁头在，当前磁头在100磁道处磁道处SSTF策略磁头臂的移动轨迹如下：策略磁头臂的移动轨迹如下：18 3839555890150 160184100假设磁盘有假设磁盘有200个磁道，磁盘请求队列中是一些个磁道，磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为：随机请求。被请求的磁道按接收顺序分别为：55、58、39、18、90、160、150、38、184，当，当前
34、磁头在前磁头在100磁道处磁道处SCAN策略磁头臂的移动轨迹如下：策略磁头臂的移动轨迹如下：183839555890150160184100200假设磁盘有假设磁盘有200个磁道，磁盘请求队列中是一个磁道，磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为：些随机请求。被请求的磁道按接收顺序分别为：55、58、39、18、90、160、150、38、184，当前磁头在，当前磁头在100磁道处磁道处C-SCAN策略磁头臂的移动轨迹如下策略磁头臂的移动轨迹如下：183839555890150160184100200（a）FCFS（b）SSTF（c）SCAN（d）C-SCAN下一个被访下一个
35、被访问的磁道问的磁道横跨的横跨的磁道数磁道数下一个被下一个被访问的磁访问的磁道道横跨的横跨的磁道数磁道数下一个被访下一个被访问的磁道问的磁道横跨的横跨的磁道数磁道数下一个被访下一个被访问的磁道问的磁道横跨的横跨的磁道数磁道数554590101505015050583583216010160103919553184241842418213916909418166907238158323820160701820553391150101501323916551638112160103815831841461842418209032平均寻平均寻道长度道长度55.3平均寻平均寻道长度道长度27.5平均寻
36、平均寻道长度道长度27.8平均寻平均寻道长度道长度27.5任务5 文件系统演示 n课程设计内容设计一个简单的多用户文件系统。即设计一个简单的多用户文件系统。即在系统中用一个文件来模拟一个磁盘；在系统中用一个文件来模拟一个磁盘；此系统至少有：此系统至少有：Create、delete、open、close、read、write等和部分文件属性的功能等和部分文件属性的功能实现这个文件系统。实现这个文件系统。 能实际演示这个文件系统。能实际演示这个文件系统。基本上是进入一个界面（此界面就是该文件系统基本上是进入一个界面（此界面就是该文件系统的界面）后，可以实现设计的操作要求。的界面）后，可以实现设计的操作要求。 wzq MFDUFDcattest文件系统总体数据结构图文件系统总体数据结构图 注意：注意：对于物理块对于物理块的访问（包括访问的访问（包括访问指针，空闲位）需指针，空闲位）需要经过输入输出，要经过输入输出，相当于通过定位对相当于通过定位对文件进行读写。打文件进行读写。打开文件目录（开文件目录（AFD）是在内存中，由打是在内存中，由打开文件时创建。开文件时创建。
