操作系统实验报告学生学院计算机学院专业班级计算机科学与技术3班学号********** 学生姓名林虹指导教师丁国芳2015 年12月15 日目录1 实验一进程调度 (1)2 实验二银行家算法 (16)3 实验三动态分区分配方式的模拟 (20)4 实验四仿真各种磁盘调度算法 (26)实验一进程调度1. 实验目的编写并调试一个模拟的进程调度程序，分别采用“短进程优先”、“时间片轮转”、“高响应比优先”调度算法对随机产生的五个进程进行调度，并比较算法的平均周转时间。

以加深对进程的概念及进程调度算法的理解。

2. 实验要求1.每个进程由一个进程控制块（PCB）表示，进程控制块可以包含如下信息：进程名、优先数（响应比）、到达时间、需要运行时间（进程的长度）、已运行时间、进程状态等等（可以根据需要自己设定）。

2.由程序自动生成进程（包括需要的数据，要注意数据的合理范围），第一个进程到达时间从0开始，其余进程到达时间随机产生。

3.采用时间片轮转调度算法时，进程的运行时间以时间片为单位进行计算。

4.每个进程的状态可以是就绪W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。

5.每进行一次调度，程序都要输出一次运行结果：正在运行的进程、就绪队列中的进程、完成的进程以及各个进程的PCB，以便进行检查。

6.最后计算各调度算法的平均周转时间，并进行比较、分析。

3. 实验内容a.算法原理（1）短进程优先调度算法“短进程优先”调度算法的基本思想是把CPU分配给就绪队列中需要时间最短的进程。

（2）时间片轮转算法将系统中所有的就绪进程按照FCFS原则，排成一个队列。

每次调度时将CPU 分派给队首进程，让其执行一个时间片。

时间片的长度从几个ms到几百ms。

在一个时间片结束时，发生时钟中断。

调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。

进程可以未使用完一个时间片，就出让CPU。

（3）高响应比优先算法HRRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。

每个作业完成后要打印该作业的开始运行时刻、完成时刻、周转时间和带权周转时间，这一组作业完成后要计算并打印这组作业的平均周转时间、带权平均周转时间。

b.程序流程图c.重要数据结构d.各程序说明及关系1. void input() 输入进程函数2. void print() 打印进程函数3.int main() 主函数调用4.各函数代码void SJF() 短进程优先函数e运行结果截图void RR() 短进程优先函数运行结果截图void HRRN() 高响应比优先函数程序运行结果4. 结果分析与实验小结作业调度本质与进程调度类似，但是多道的话，就要多考虑空间的容量了。

单道的情况就不作分析了，对于多道调度，要考虑清楚，什么时候能够接纳新的作业进来；对于给定的空间来说，一次能让作业同时执行的数量应该是多少；根据算法，应该按照怎么样的先后顺序选择等待的作业……逐步分析后，对于非抢占的CPU，一旦作业进入了执行状态，它的结束时间也就定了下来，一旦有作业结束，就会释放空间，释放之后就能立即选择新的作业进来。

根据不同算法，对等待队列也有不同的排序结果，无论怎样，都按先后顺序放入队列中，所以每次选择的时候，都要遍历一遍所有等待中的进程，如果这个作业满足空间需求，则放入CPU中执行，同时更新结束时间，否则则跳过这个作业，判断下一个作业，直到询问完所有等待的作业为止。

不断重复上面的步骤，直到所有的作业都执行完所以模拟的时候，分别开了一个运行队列和一个等待队列，运行队列作为判断有哪个作业已经执行结束。

通过这个实验，对操作系统的作业调度已经有了更深一层的理解了，望以后能再接再厉。

实验二银行家算法1.实验目的用银行家算法避免死锁，实现系统合理分配资源，加深对进程同步及死锁理解。

2.实验要求1.假定系统有3类资源A（10个）、B（15个）、C（12个），系有5个进程并发执行，进程调度采用时间片轮转调度算法。

2.每个进程由一个进程控制块（PCB）表示，进程控制块可以包含如下信息：进程名、需要的资源总数、已分配的资源数、进程状态。

3.由程序自动生成进程（包括需要的数据，要注意数据的合理范围）。

4.进程在运行过程中会随机申请资源（随机生成请求的资源数），如果达到最大需求，表示该进程可以完成；如果没有达到最大需求，则运行一个时间片后，调度其它进程运行。

资源分配采用银行家算法来避免死锁。

5.每个进程的状态可以是就绪W（Wait）、运行R（Run）、阻塞B（Block）或完成F（Finish）状态之一。

6.每进行一次调度，程序都要输出一次运行结果：正在运行的进程、就绪队列中的进程、阻塞队列中的进程、完成的进程以及各个进程的PCB，以便进行检查。

3.实验内容a.算法原理操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。

当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。

若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配b.程序流程图c.重要数据结构d.各函数实现1.void input() 随机生成进程函数2.void print() pcb打印函数3.void Safe() 安全性检查算法4.void Bankalgorithm()5.int main() 主函数e.运行结果截图4.结果分析与小结多个进程同时运行时，系统根据各类系统资源的最大需求和各类系统的剩余资源为进程安排安全序列，使得系统能快速且安全地运行进程，不至发生死锁。

银行家算法是避免死锁的主要方法，其思路在很多方面都非常值得我们来学习借鉴。

实验三动态分区分配方式的模拟1.实验目的了解动态分区分配方式中的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解2.实验要求1.用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程和回收过程。

其中，空闲分区通过空闲分区链（表）来管理；在进行内存分配时，系统优先使用空闲区低端的空间。

2.假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：3.要求每次分配和回收后显示出作业分配情况及空闲内存分区链的情况。

3.实验内容a.算法原理（1）首次适应算法:最先适应算法的基本思想是空闲区表中的空闲区按地址大小递增顺序排列。

当要求分配一个容量S的区域时，在空闲区表中从头开始比较。

直到找到X>=S为止。

如果满足，则从X中分配S，剩余部分保留在空闲区表中原来位置，否则分配失败。

（2）最佳适应算法:最佳适应算法的基本思想是空闲区表中空闲区按其容量以递增次序排列，即X1<=X2<=X3<=.......<=Xn 。

当要求一个空闲区时，由小到大进行查找。

如果要求分配一个容量为S的分区，则从X1开始比较，直至S<=X1；然后从Xi分配S,若有剩余，则作为一个空余区插入适当位置，否则分配失败。

b.程序流图分配回收c.重要数据结构说明d.各程序说明及其关系1. space *New_space (int num, int Size, int adr):动态申请空间函数动态申请方法如下：2.void FF()：首次适应算法函数遍历一次所有的空闲分区，一旦找到则跳出遍历，分配空间，分配后，可能会有Size == 0的分区出现，这时候应该调用remove_zero 函数，将该分区移出链表：3.void BF()：最佳适应算法函数每次分配前都要找一次最小值，如果找不到，则说明分配失败，已经没有可以满足空间要求的分区了，关键代码如下：1.void recycle ()：回收空间函数对于回收的过程，则要分情况处理了，关键代码及其详细说明如下：e.程序设计结果为6个进程依次自动分配空间，分配所有后，再依次释放空间：1.首次适应算法2.最佳适应算法4.结果分析与小结可变分区的分配与回收，关键在于细心。

对于分配来说，根据三个算法来分配，基本用链表来模拟的话，应该没什么问题。

而对于回收来说，要判断的条件就会比较多了，首先要考虑是不是第一个分区，再考虑是不是最后一个，两者都不是的话，就要考虑是否相邻的情况，对于第一个和最后一个，也同样需要考虑是否相邻的情况，所以用链表模拟的话，一定要细心，不然很容易会出现指针越界导致程序崩溃。

实验四仿真各种磁盘调度算法1.实验目的了解磁盘调度的基本算法及性能2.实验要求由系统产生一系列磁盘请求（10个），分别给出先来先服务算法、最短寻道时间优先算法、扫描(SCAN)算法和循环扫描(CSCAN)算法时磁头移动顺序并计算磁头的平均移动磁道数。

（假设磁头刚从80磁道移到100磁道）3.实验内容a.算法原理（1）先来先服务算法即先来的请求先被响应。

FCFS策略看起来似乎是相当"公平"的，但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。

FCFS策略为我们建立起一个随机访问机制的模型，但是假如用这个策略反复响应从里到外的请求，那么将会消耗大量的时间。

为了尽量降低寻道时间，看来我们需要对等待着的请求进行适当的排序，而不是简单的使用FCFS策略。

这个过程就叫做磁盘调度管理。

有时候FCFS也被看作是最简单的磁盘调度算法（2）最短寻道时间优先算法要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。

（3）扫描算法该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。

例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。

这样自里向外的访问，直至再无更外的磁道需要访问时，才将磁道换向自外向里移动。

这时，同样也是每次选择这样的进程来调度，也就是要访问的当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现像（4）循环算法当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该里程就必须等待，为了减少这种延迟，CSCAN算法规定磁头单向移动，而本实验过程中我们所设计的是磁头从里向外移动，而从外向里移动时只须改方向而已，本实验未实现。

但本实验已完全能演示循环扫描的全过程。

b.总程序流图c.重要数据结构d.各算法代码1.double FCFS() 先来先服务算法2.double SSTF() 最短寻道时间优先算法3.double SCAN() 扫描算法4.double CSCAN() 循环算法5.int main() 主函数e.运行结果4.结果分析与小结计算机磁盘是一种很重要也很常用的外部设备，其分配也有一定的分配策略。