计算机操作系统课程设计-课件

计算机操作系统课程设计1ppt课件计算机操作系统课程设计1ppt课件课程设计内容任务1进程管理演示任务2存储管理系统设计任务3编程序模拟银行家算法任务4磁盘调度算法的实现与分析任务5文件系统演示2ppt课件课程设计内容任务1进程管理演示2ppt课件任务1进程管理演示课程设计内容设计一个允许n个进程并发运行的进程管理模拟系统。运行队列PCBi∧就绪队列PCBjPCBj＋1PCBj＋1∧阻塞队列PCBkPCBk＋1PCBk＋1∧3ppt课件任务1进程管理演示课程设计内容运行队列PCBi就绪队列P接收进程就绪队列1就绪队列2

...就绪队列n超时事件1发生事件2发生等待事件1等事件2...处理机终止进程事件m发生等事件m现代操作系统中进程状态表示方法:4ppt课件接收进程就绪队列1就绪队列2...就绪队列n超时事件1发生PCB进程控制块其中包括参数①进程名name；②要求运行时间runtime；③优先级prior；④状态state；⑤已运行时间runedtime等。为简单起见，只设运行队列，就绪链表，阻塞队列三种数据结构，进程的调度在这两个队列中切换，每个进程运行时间随机产生，为1~20之间的整数。时间片的大小由实验者自己定义，可为3或5，优先级也可以随机产生。各进程之间有一定的同步关系（可选），注意进程状态转换的时机。5ppt课件PCB进程控制块5ppt课件任务2存储管理系统设计实验内容：采用一些常用的存储器分配算法，设计一个请求页式存储管理模拟系统并调试运行。

（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成（可选，也可随机产生）：①

50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分；③

25%的指令是均匀分布在后地址部分；具体的实施方法是：①

在[0，319]的指令地址之间随机选取一起点m；②

顺序执行一条指令，即执行地址为m+1的指令；③

在前地址[0，m+1]中随机选取一条指令并执行，该指令地址为m’；④

顺序执行一条指令，其地址为m’+1;⑤

在后地址[m’+2，319]中随机选取一条指令并执行；⑥

重复上述步骤①~⑤，直到执行320次指令。6ppt课件任务2存储管理系统设计实验内容：采用一些常用的存储器分配算（2）将指令序列变成为页地址流设：①页面大小为1k；

②用户内存容量分别为4页到32页；

③用户虚存容量为32k。在用户虚存中，按每k存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条-第9条指令为第0页（对应虚存地址为[0，9]）；第10条-第19条指令为第1页（对应许存地址为[10，19]）；

…….第310条-第319条指令为第31页（对应许存地址为[310，319]）；按以上方式，用户指令可组成32页。7ppt课件（2）将指令序列变成为页地址流7ppt课件（3）

计算并输出下述各种算法在不同内存容量下的命中率。①

先进先出的算法（FIFO）；

页面失效次数命中率=1-————————

页地址流长度

在本次实验中，页地址长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。

8ppt课件（3）

计算并输出下述各种算法在不同内存容量下的命中率。83．随机数产生办法关于随机数产生法，系统提供函数srand()和rand()，分别进行初始化和产生随机数。例如：

srand()；语句可初始化一个随机数；

a[0]=rand()%320；

a[1]=rand()%a[0]；

S=a[1]+rand()%(a[0]-a[1])……

语句可用来产生a[0]与a[1]中的随机数。

9ppt课件3．随机数产生办法9ppt课件整个算法的思想见下页10ppt课件整个算法的思想见下页10ppt课件

ipnpfn

3131-1

3030-100-1

11-122-1

33-1

44-1

66-1

77-1

55-1

2929-1

2828-1

2727-1…

…

…

pnpfnnext

^0123页表结构空闲物理页框初始状态freefp_headpn表示页号；pfn表示有效位，当页帧不在内存时为－1，否则为指向其内存地址。

66-111ppt课件ipnpfn3131-130

ipnpfn

3131-1

3030-100-1

11-122-1

33-1

44-1

660

77-1

55-1

2929-1

2828-1

2727-1…

…

…

pnpfnnext

^0123页表结构空闲物理页框第一次分配freefp_head

6^Busypf_headBusypf_tail2727-112ppt课件ipnpfn3131-130

ipnpfn

3131-1

3030-100-1

11-122-1

33-1

44-1

660

77-1

55-1

2929-1

2828-1

27271…

…

…

pnpfnnext

^0271^23页表结构空闲物理页框第二次分配freefp_head

6Busypf_headBusypf_tail2828-113ppt课件ipnpfn3131-130

ipnpfn

3131-1

3030-100-1

11-122-1

33-1

44-1

660

77-1

55-1

2929-1

28282

27271…

…

…

pnpfnnext

^0271282^3页表结构空闲物理页框第三次分配freefp_head

6Busypf_headBusypf_tail3030-114ppt课件ipnpfn3131-130

ipnpfn

3131-1

3030300-1

11-122-1

33-1

44-1

660

77-1

55-1

2929-1

28282

27271…

…

…

pnpfnnext

^0271282303^页表结构空闲物理页框第四次分配freefp_head

6Busypf_headBusypf_tail第五次分配

22-115ppt课件ipnpfn3131-130

ipnpfn

3131-1

3030300-1

11-122-1

33-1

44-1

66-1

77-1

55-1

2929-1

28282

27271…

…

…

pnpfnnext

^0271282303^页表结构空闲物理页框第五次,淘汰一页freefp_head

6^Busypf_headBusypf_tail

22-116ppt课件ipnpfn3131-130

ipnpfn

3131-1

3030300-1

11-1220

33-1

44-1

66-1

77-1

55-1

2929-1

28282

27271…

…

…

pnpfnnext

^0271282303页表结构空闲物理页框第五次,分配一页freefp_head

2^Busypf_headBusypf_tail17ppt课件ipnpfn3131-130扩展的银行家算法描述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.r1r2r3224413316223P1P2P3P4任务3编程序模拟银行家算法编制银行家算法程序，并检测所给状态的系统安全性。18ppt课件扩展的银行家算法描述r1r2r322441Allocation(1:n,1:m):资源分配矩阵。Allocation(i,j)=k表示进程i已占有k个j类资源。Need(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类资源。r1r2r3200112115001P1P2P3P4r1r2r3024301201222P1P2P3P419ppt课件Allocation(1:n,1:m):资源分配矩阵。r1资源分配程序的工作过程描述：

基本思想：当进程提出资源申请时，系统首先检查该进程对资源的申请量是否超过其最大需求量，以及系统现有资源能否满足进程需要。若能，则进一步检查：若把资源分给该进程，系统能否处于安全状态？若安全则分配，否则置该进程为等待资源状态。

为简单起见，记Ai为A(i,1),A(i,2),…,A(i,m)，其中A为n×m矩阵。

定义长度为m的向量X，Y间的关系为：

X≤Y当且仅当X(i)≤Y(i)(i=1,2,…,m)20ppt课件资源分配程序的工作过程描述：20ppt课件

1.如果Requesti>Needi则报错返回。

2.如果Requesti>Available,则进程i进入等待资源状态，返回。

3.假设进程i的申请已获准，于是修改系统状态：

Available=Available-Requesti Allocationi=Allocationi+Requesti Needi=Needi-Requesti

4.调用安全状态检查算法。设进程i申请资源，申请资源向量为Requesti，则有如下的资源分配过程：21ppt课件1.如果Requesti>Needi则报错返回。设进（续）

5.若系统处于安全状态，则将进程i申请的资源分配给进程i，返回。

6.若系统处于不安全状态，则进程i进入等待资源状态，并恢复系统状态后返回：

Available=Available+Requesti Allocationi=Allocationi-Requesti Needi=Needi+Requesti22ppt课件（续）22ppt课件安全状态检查算法：设Work(1:m)为临时工作向量。初始时Work=Available.令N={1,2,…,n}1.寻找j∈N使其满足Needj≤Work,若不存在这样的j则转(3);2.Work=Work+Allocationj

N=N-{j},转(1);3.如果N为空则返回系统安全；如果N不为空则返回系统不安全。算法时间复杂度为O(m×n2)，如果每类资源只有一个，则时间复杂度为O(n2)23ppt课件安全状态检查算法：23ppt课件假定系统中有四个进程P1、P2、P3、P4，三种类型的资源R1、R2、R3，数量分别为9、3、6，在T0时刻的资源分配情况如下表所示。举例：资源进程maxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222112P2613511102

P3314211103

P4422002420

24ppt课件假定系统中有四个进程P1、P2、P3、P4，三种类型的资源RT0时刻的安全性利用安全性算法对T0时刻的安全性进行分析，如下表，可知T0时刻存在一个安全序列{P2、P1、P3、P4}，所以系统是安全的。资源

进程WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2112102511623TrueP1623222100723TrueP3723103211934TrueP4934420002936True25ppt课件T0时刻的安全性资源WorkNeedAllocationWo(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向量，资源变化情况如下表。资源进程maxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222011P2613612001

P3314211103

P4422002420

26ppt课件(2)P2请求资源资源maxAllocationNeed4)再利用安全性算法检查此时系统是否安全，如下表。可知存在一个安全序列{P2、P1、P3、P4}，所以系统是安全的，可以立即将P2所申请的资源分配给它。资源

进程WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3P2011001612623TrueP1623222100723TrueP3723103211934TrueP4934420002936True27ppt课件4)再利用安全性算法检查此时系统是否安全，如下表。可知存在(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)系统先假定可为P3分配资源，并修改Available、Allocation3、Need3向量，资源变化情况如表5。28ppt课件(3)P1请求资源(4)P3请求资源28ppt课件表5P3申请资源后的资源分配表资源进程maxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3P1322100222010P2613612001

P3314212102

P4422002420

4)再利用安全性算法检查此时系统是否安全，从上表可看出，可用资源Available(0,1,0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源给P3。29ppt课件表5P3申请资源后的资源分配表资源maxAllocat任务4磁盘调度算法的实现与分析

编程序实现下述磁盘调度算法，并求出每种算法的平均移动磁道数，并分析结果：①先来先服务算法（FCFS）②最短寻道时间优先算法（SSTF）③扫描算法（SCAN）④循环扫描算法（C-SCAN）30ppt课件任务4磁盘调度算法的实现与分析编程序实现下述磁盘调度算法磁盘调度策略1、先来先服务FCFS(FirstComeFirstServer)：这是最简单的磁盘调度策略，它根据进程请求访问磁盘的时间顺序进行调度。2、最短寻道时间优先SSFT(ShortestSeekTimeFirst)：它是根据磁头当前的位置，选择请求队列中距离磁头最短的请求响应。3、SCAN：也称电梯策略，要求磁头臂仅仅沿一个方向移动，并在途中满足所有未完成的请求，直到它到达这个方向的最后一个磁道，或这个方向没有别的请求为止，然后倒转服务方向，同样按顺序完成的有请求。4、C－SCAN：是循环扫描法，当到达最后一个磁道时，磁头臂返回到磁头的另一端，并再次开始扫描。31ppt课件磁盘调度策略1、先来先服务FCFS(FirstCome假设磁盘有200个磁道，磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为：55、58、39、18、90、160、150、38、184，当前磁头在100磁道处

FCFS策略磁头臂的移动轨迹如下：

18383955589015016018410032ppt课件假设磁盘有200个磁道，磁盘请求队列中是一些随机请求。被请求假设磁盘有200个磁道，磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为：55、58、39、18、90、160、150、38、184，当前磁头在100磁道处

SSTF策略磁头臂的移动轨迹如下：

18383955589015016018410033ppt课件假设磁盘有200个磁道，磁盘请求队列中是一些随机请求。被请求假设磁盘有200个磁道，磁盘请求队列中是一些随机请求。被请求的磁道按接收顺序分别为：55、58、39、18、90、160、150、38、184，当前磁头在100磁道处

SCAN策略磁头臂的移动轨迹如下：

1838395558901501601841002