操 作 系 统
课
程
设
计
实
验
报
告
学院：计算机科学与技术学院
班级：计112
学号：1113022032
姓名:
一、实验名称：
用C++实现驱动调度算法、页面替换算法、银行家算法、处理器调度算法
二、实验要求：
书写实验报告，包括的内容有：
（1） 实验题目
（2） 程序中使用的数据结构及主要文字说明
（3） 带有注释的源程序
（4） 执行程序说明，表明各进程控制快的初始状态，以及各算法的运行状态
（5） 通过实验后的收获与体会及对实验的改进意见和见解
二、实验目的：
通过自己编程来实现各类操作系统算法，进一步理解操作系统的概念及含义，提高对操作系统的认识，同时提高自己的动手实践能力。加强我们对各类算法的理解。
三、实验内容：
1、实现页面替换算法
（1）FIFO 先进先出页面替换算法
（2）LRU最近最少使用页面替换算法
（3）LFU最少使用频率页面替换算法
2、银行家算法
3、实现驱动调度算法
（1）先来先服务算法
（2）电梯算法
（3）扫描算法
4、实现处理器调度
（1） 先进先出处理器调度
（2） 时间片轮转法
（3） 优先级调度
四、实验原理：
1、页面替换算法
先进先出页面置换算法：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面加以淘汰。将已调入内存的页面按先后次序链接成一个队列，将最先调入的页面与新页面进行置换
最近最久未使用置换算法：该算法是利用“最近的过去”作为“最近的将来”，将最近最久未使用的页面加以淘汰。将已调入内存的页面按先后顺序链接成一个队列，为每一个页面增加一个访问字段，用来记录一个页面自上次被访问以来所经历的是时间t，当需淘汰一个页面时，选择现有页面中其t值最大，即最近最久未使用的页面加以淘汰
2、银行家算法
先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。
3、驱动调度算法
先进先出算法（FIFO）：总是严格按时间顺序对磁盘请求予以处理。算法实现简单、易于理解并且相对公平，不会发生进程饿死现象。但该算法可能会移动的柱面数较多并且会
经常更换移动方向，效率有待提高
电梯调度算法：总是将一个方向上的请求全部处理完后，才改变方向继续处理其他请求。
扫描算法（scan algorithm）：总是从最外向最内（或最内向最外）进行扫描，然后在从最内向最外（或最外向最内）扫描。该算法与电梯调度算法的区别是电梯调度在没有最外或最内的请求时不会移动到最外或最内柱面。
4、处理器调度算法
先进先出处理器调度：按照作业进入系统后备工作队列的先后次序来挑选作业,
先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后移入就绪队列。
时间片轮转法调度算法：调度次序每次把CPU分配给就绪队列进程/线程使用规
定的时间间隔，就绪队列中每个进程/线程轮流的运行一个时间片，当时间片耗尽时，就强迫当前运行进程/线程让出处理器，转而排列到就绪队列尾部，等候下一轮调度。
优先级调度：根据确定的优先级来选取进程/线程，总是选择就绪队列中的优先
级最高者投入运行，即优先级越高，先被调用。
五、数据结构设计
对操作系统的各类算法设计数据结构如下：
页面替换算法：void FIFO()；void LRU()；void LFU()；
银行家算法：void Init() 初始化算法
void Bank() 银行家算法
bool Safe() 安全性算法
驱动调度算法：
struct MagneticHead//磁头构成
{
int site;
int count;
bool direct;
}；
struct Range//磁盘磁道范围
{
int mStart;
int mEnd;
};
struct RequestList//请求序列
{
int site;
bool state;
};
struct Data//基本数据集合
{
MagneticHead magneticHead;
RequestList *requestList;
int *executeList;
Range range;
int length;
};
处理器调度：
typedef struct pcb//时间片轮转法
{
char pname[N];
int runtime;
int arrivetime;
char state;
struct pcb*next;
}PCB;
typedef struct PCB1//先进先出服务
{
char ID[3];//进程号
char name[10];//进程名
char state;//运行状态
floatarrivetime;//到达时间
floatstarttime;//进程开始时间
floatfinishtime;//进程结束时间
floatservicetime;//服务时间
float turnaroundtime;//周转时间
float weightedturnaroundtime;//带权周转时间
struct PCB1 *next;//指向下个进程
}pcb1;
struct pcb2 {优先级调度
char name[10];
char state;
int super;
int ntime;
int rtime;
struct pcb2* link;
}*ready=NULL,*d;
typedef struct pcb2 PCB2;
六、课程设计总结
在本次课程设计中，就是讲平时所做的实验结合起来，实现操作系统的各类算法，了解操作系统的运行原理以及其基本概念，更好的将操作系统的原理很好的展现出来。同时，在本次实验中遇到了很多问题，需要我们仔细的检查和修改。其次，实验中为了能更好的体现各类算法的运行情况，需要做一个清晰的界面，以能清楚地看出运行结果。
