实验报告说明书
设计名称： 操作系统课程设计
实 验 ： 进程调度设计
学生姓名：
专 业： 网络工程
班 级： 08级一班
学 号：
指导教师：雷晓平 王东 黄营 杨跃武
日 期： 2011年 6月 19日
课程设计任务书
网络工程 专业 08 年级 1 班
一、 具体要求
本课程设计共2周，采取集中方式。
㈠主要设计内容
1、进程调度
2、存储管理
3、文件管理
㈡操作系统分项设计
1、设计一 ：进程管理系统设计
目的与要求：本设计的目的是加深对进程概念及进程管理各部分内容的理解；熟悉进程管理中主要数据结构的设计及进程调度算法、进程控制机构、同步机构及通讯机构的实施。
要求设计一个允许n个进程并发运行的进程管理模拟系统。该系统包括有简单的进程控制、同步与通讯机构，其进程调度算法可任意选择。每个进程用一个PCB表示，其内容根据具体情况设置。各进程之间有一定的同步关系（可选）。系统在运行过程中应能显示或打印各进程的状态及有关参数的变化情况，以便观察诸进程的运行过程及系统的管理过程。
具体详见：设计任务书1--进程调度算法.doc
2、设计二：存贮器管理系统设计
目的与要求：本设计的目的是使学生熟悉存贮器管理系统的设计方法；加深对所学各种存贮器管理方案的了解；要求采用一些常用的存贮器分配算法，设计一个存贮器管理模拟系统并调试运行。模拟环境应尽量接近真实。
具体详见：设计任务书2--内存分区管理模拟.doc
3、设计三：虚拟存储器管理系统设计
本设计的目的是通过设计一个简单的虚拟存储器管理系统来模拟实际的页面调度算法与过程，以掌握这种有用的技术。要求将其输入/输出处理程序编成一个独立的进程模块并与其它请求输入/输出的进程并发运行。并要求加入设备管理子模块。
具体分析为：页面调度算法主要有FIFO、最近最少使用调度算法（LRU）、最近最不常用调度算法（LFU）、最佳算法（OPT）等。题目要求：
① 实现三种算法：1、先进先出；2、OPT；3、LRU
② 页面序列从指定的文本文件（TXT文件）中取出
③ 输出：第一行：每次淘汰的页面号，第二行：显示缺页的总次数
4、设计四：文件管理系统设计
目的与要求：本设计的目的是通过设计和调试一个简单的外部文件系统，主要是模拟文件操作，，使学生对主要文件操作命令的实质和执行过程有比较深入的了解，掌握它们的基本实施方法。
基本要求如下：
实现三种算法： 先来先服务、最短寻道优先、电梯算法
磁道服务顺序从指定的文本文件（TXT文件）中取出
输出：第一行：磁道的服务顺序；第二行：显示移动总道数
5、设计五：多道程序的转换调度系统
题目要求：（作业调度和进程调度结合在一起）
作业流信息是从指定文本文件（TXT文件）中读取
作业信息：
作业号 进入系统时间 估计运行时间 优先级 内存需求量 磁带机需求量 都为整型
作业调度算法：先来先服务、最短作业优先（二者选一）
进程调度算法：先来先服务、基于优先级的算法(静态优先级)(二者选一)
输出格式：作业号 时间间隔
1 800-810 （/* 8：00-8：10 */）
2 810-900
1 900-930
平均周转时间：总的周转时间/作业总数
周转时间就是作业结束时间减去作业进入系统时间
具体详见：多道程序转换.doc
以上设计以20-25人为组，选择一个设计进行。
㈢操作系统整体设计
将第㈡部分中的全部或部分有机地组合起来，构成一个小型的操作系统。
二、 进度安排
1、教师下达设计任务书(半天)
任务书内容包括题目、主要技术指标和要求、给定条件及原始数据、所用仪器设备和参考资料及文献等。教师讲授必要的设计思路和设计方法。
2、学生完成预设计(1天半)
本阶段学生通过查阅资料及文献（主要自学），明确任务，掌握工程设计基本方法，确定设计方案，进行设计分析，完成预设计。
3、实验阶段(7天)
经教师审查通过预设计方案后，即可进行编程调试。实验由学生独立完成，教师定时指导。
4、设计总结阶段(1天)
本阶段学生要认真完成课程设计报告书，整理技术资料，并尽可能写出课程设计的心得体会和改进意见。
三、 完成后应上交的材料
课程设计报告书包括：设计任务及主要技术指标、设计方案及论证结果、系统的原理框图、设计程序、实验结果、实验中主要问题及故障现象的分析及设计结论等。
附实验数据、系统软硬件环境、使用说明及参考资料。
四、 总评成绩
指导教师 签名日期 年 月 日
系 主 任 审核日期 年 月 日
目 录
一、实验目的………………………………………5
二、实验要求………………………………………5
三、具体内容………………………………………5
3.1先来先服务（FCFS）…………………5
3.2作业优先SJF 算法……………………5
3.3多级队列调度算法…………………….5
3.4时间片轮转调度法………………………5
3.5优先级法…………………………………6
3.6多队列反馈法……………………………6
3.7轮转法…………………………………….6
3.8最短周期优先……………………………6
3.9先来先服务…………………………………7
四、实验程序………………………………………7
五、实验总结………………………………………13
设计题目：进程管理系统设计
一、实验目的：
本设计的目的是加深对进程概念及进程管理各部分内容的理解；熟悉进程管理中主要数据结构的设计及进程调度算法、进程控制机构、同步机构及通讯机构的实施。
二、实验要求：
设计一个允许n个进程并发运行的进程管理模拟系统。该系统包括有简单的进程控制、同步与通讯机构，其进程调度算法可任意选择。每个进程用一个PCB表示，其内容根据具体情况设置。各进程之间有一定的同步关系（可选）。系统在运行过程中应能显示或打印各进程的状态及有关参数的变化情况，以便观察诸进程的运行过程及系统的管理过程。
三、具体内容：
调度也称dispatcher，这是内核的主要职责之一。一个良好的任务调度算法应该主要体现在以下几个方面：
公平：保证每个进程得到合理的CPU 时间
高效：使CPU 保持忙碌状态，即总是有进程在CPU 上运行
响应时间：使交互用户的响应时间尽可能短
周转时间：使批处理用户等待输出的时间尽可能短
吞吐量：使单位时间内处理的进程尽可能多
很显然在任何操作系统中这几个目标不可能同时达到所以不同的。
操作系统会在这几个方面中做出相应的取舍从而确定自己的调度算法，常用的处理机调度算法有：先来先服务FCFS、短作业优先SJF、优先级、时间片轮转法、多级队列法、多级反馈队列法。
（1）先来先服务（FCFS）
FCFS 是最简单的CPU 调度算法，即按进程到来的先后次序进行调度，这样在系统中等待时间最长的进程被优先调度，而不管其所需运行时间的长短。
（2）作业优先SJF 算法
是指当CPU 可供使用时SJF 算法把CPU 分给需要运行时间最短的进程。
（3）多级队列调度算法
把就绪队列划分成几个单独的队列一般根据进程的某些特性如内存大小和进程类型永久性地把各个进程分别链入其中某一个队列中，每个队列都有自己的调度算法，此外在各个队列之间也要进行调度。通常采用固定优先级的抢占式调度，例如某系统中有5 个队列，各个队列的优先级自上而下降低，只有当前3 个队列中都为空的时候队列4 中的进程才可以运行，而当队列4 中的进程在运行时，如果队列1 中进入了一个就绪进程，则队列4 中的进程要立刻让出CPU 使用权。多级反馈队列法允许进程在各队列间移动，其基本思想是把具有不同CPU工作时间这一特性的进程区分开来，如果一个进程要使用很长的CPU 时间，则应把它移至较低级的队列中，这种方式把I/O 繁忙型和交互式进程放在较高优先级的队列中同样在低优先级队列中长时间等待的进程可以移到较高优先级队列中UNIX 系统采用的是多级反馈队列轮转法。
（4）时间片轮转调度法
当两个或两个以上任务有同样优先级，内核允许一个任务运行事先确定的一段时间叫做时间额度quantum ，然后切换给另一个任务也叫做时间片调度time slicing ，内核在满足以下条件时把CPU 控制权交给下一个任务就绪态的任务， 当前任务已无事可做，当前任务在时间片还没结束时已经完成了。轮转法主要是为分时系统设计的，其中时间片是一个重要的参数不能取的过大或过小，通常为10 至100ms 数量级，就绪队列可以看成是一个环形队列，CPU 调度程序轮流地把CPU 分给就绪队列中地每个进程，时间长度为一个时间片Linux 操作系统就是采用时间片轮转的调度算法。
（5）优先级法
优先级调度的基本思想是，把当前处于就绪队列中优先级最高的进程投入运行，而不管各进程的下一个CPU周期的长短和其他因素。
优先级通常用0～4095的整数(称为优先数)表示，是数大优先级高还是数小优先级高取决于规定。例如UNIX系统规定优先数越大优先级越低，优先数越小优先级越高。
优先数有静态和动态之分。静态优先数是指在进程开始运行之前便根据某种或某些因素(如估计运行时间、主存需求量、打开文件个数、所付经费多少等)算定，而且该优先数在进程的整个生命周期内一直不变。静态优先数方法虽然简单，但有可能导致某些低优先级的进程无限期地等待。尤其在高优先级的进程不断进入就绪队列的情况下，使等待CPU的低优先级进程更多，等待时间更长。动态优先数方法是按照某种原则使各进程的优先级随着时间而改变。例如随等待时间增大优先级也跟着提高、随着使用CPU时间的增长优先级跟着下降，就是一种较好的策略。等待了较长时间的进程，总会因其优先级不断地提高而被调度运行。
如果把进入就绪队列的次序作为计算进程动态优先数的主要指标，那么优先级法就变成FCFS。如果把下一个CPU周期最短作为计算进程动态优先数的主要指标，那么优先级法变成SBF，此时各进程的优先数p_pri = 1/ ti，其中ti是估算的下一个CPU周期的长度。
优先级调度也允许剥夺方式。现在的许多操作系统，例如UNIX系统V，Windows NT，OS/2等都采用优先级剥夺调度。
（6）多队列反馈法
其基本思想是，把就绪进程按优先级排成多个队列，同队列的进程具有相同的时间片。高优先级队列的时间片比低优先级队列的小。调度时先从高优先级队列中选出某一进程投入运行，当该进程的时间片到期后则转至低一级的就绪队列中。只有高优先级队列为空时才从低一级队列中调度进程。
例如考虑由3个队列组成的多级队列调度。3个队列的编号分别为0, 1, 2，如图所示。调度算法首先调度0号队列中的进程。当0号队列为空时才调度1号队列中的进程；当0号与1号队列都为空时才调度2号队列中的进程。在剥夺方式下，新进入0号队列的进程将剥夺1号或2号队列中正在执行的进程的CPU，而新进入1号队列的进程将剥夺2号队列中正在执行的进程的CPU。
其实，每个队列都可拥有各自的调度算法，也可制定不同的“转队”规则。这样看来，多队列反馈调度算法能有多种变化。
（7）轮转法
轮转法就是按一定时间片(记为q)轮番运行各个进程。如果q是一个定值，则轮转法是一种对各进程机会均等的调度方法。
轮转法本质上是剥夺的，因为一轮内，每个进程不能获得比一个时间片q更长的运行时间。正是由于这一特点，轮转法特别适用于分时操作系统。
轮转法的关键问题是如何确定q的大小。如果时间片太大以致每个进程的CPU周期都能在一个时间片内完成，则轮转法实际上脱化为FCFS。如果q太小以致CPU切换过于频繁，则会增加CPU的额外开销，降低了CPU的有效利用率。这是因为，每次CPU切换涉及到保存原运行进程的现场和恢复新运行进程的现场，这些操作一般需要10ms～100ms的时间。例如，设有一个CPU周期为10单位的进程，在q取12，6，1时的调度次数分别为0，1，9。令时间单位为1ms(1ms=1000ms)，1次调度的开销为100ms，则在q=1时CPU的额外开销和有效开销之比为1:10，这是不容忽视的。
（8）最短周期优先
最短周期优先(SBF: shortest burst first)把当前就绪队列中的下一个CPU周期最短的那个进程调度运行。
（9）先来先服务
如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务(FCFS: first come first service)总是把当前处于就绪队列之首的那个进程调度到运行状态。也就说，它只考虑进程进入就绪队列的先后，而不考虑它的下一个CPU周期的长短及其他因素。FCFS算法简单易行，但性能却不大好。
四、实验程序
#include "iostream.h"
//define pcb
typedef struct pcb
{
char name[10]; //进程名
char state; //状态w(就绪)r(运行)f(结束)
int id; //id号
int super; //优先级
int ntime; //需运行的时间
int rtime; //已运行的时间
struct pcb *next;
}*pcb1;
pcb1 s,w;//define two publiced linknode ,one is s(ready queue),one is w(blocked queue)
//initialize two queues
void init(pcb1 &r)
{
r=NULL;//both queues is the kind of head index
}
//print the information of the ready queue
void print()
{pcb1 p;
cout<<"您现在查看的是就绪队列的信息:" ;
cout<<"进程号 "<<"进程名 "<<"优先级 "<<"状态"<<"已运行时间 "<<"需运行时间"<<endl;
for(p=s;p!=NULL;p=p->next)
{
cout<<p->id<<" "<<p->name<<" "<<p->super<<" "<<p->state<<" "<<p->rtime<<" "<<p->ntime<<endl; }
}
//print the information of the blocked queue
void print1()
{pcb1 p;
cout<<"您现在查看的是阻塞队列的信息";
cout<<"进程号 "<<"进程名 "<<"优先级 "<<"状态 "<<"已运行时间 "<<"需运行时间"<<endl;
for(p=w;p!=NULL;p=p->next)
{
cout<<p->id<<" "<<p->name<<" "<<p->super<<" "<<p->state<<" "<<p->rtime<<" "<<p->ntime<<endl; }
}
//check the queue if empty
int empty(pcb1 &r)
{
if(r==NULL)
return 0;
else
return 1;
}
//check the first process of the ready queue if finshed
int check()
{
pcb1 p;
p=s;
if(p->rtime==p->ntime)
{
p->state='F';//if one process finshed then change ti's state
cout<<"进程"<<p->id<<" 已经结束"<<endl;
return 0;
}
else
return 1;
}
//sort process according to the super of the process and insert to the ready(blocked) queue
void sort(pcb1 &r,pcb1 p)
{
pcb1 p1,p2;
int in=0;
if(r==NULL)//the queue is empty
{
r=p;
}
else
{
if(p->super>=r->super)//the super of the process which wait insert to the queue is highter than the super of the first process of the queue
{
p->next=r;
r=p;
}
else
{
p1=r;
p2=r->next;
if(p2==NULL)//only one process in the queue
{
r->next=p;
}
else
{
while(in==0&&p2!=NULL)//insert to the middle of the queue
{
if(p->super>=p2->super)
{
p->next=p2;
p1->next=p;
in=1;
}
else
{
p1=p1->next;
p2=p2->next;
}
}
}
if(in==0)//link to the last of ready queue
p1->next=p;
}
}
}
//block one process and insert to block queue
void block()
{
if(empty(s))
{
if(s->next==NULL)
{
sort(w,s);
s=s->next;
}
else
{
pcb1 p1;
p1=s;
s=s->next;
p1->next=NULL;
sort(w,p1);
}
}
else
{
cout<<"现在就绪队列已经为空，再没有进程需要阻塞"<<endl; }
}
//wake one process of block queue and insert to ready queue
void wake()
{
if(empty(w))
{
pcb1 p1;
p1=w;
w=w->next;
p1->next=NULL;
sort(s,p1);
}
else
{
cout<<"阻塞队列已经为空，没有进程再需要唤醒"<<endl; }
}
//runing
void runing()
{
if(empty(s))
{
pcb1 p;
p=s;
if(check())//check the first process of the queue if finished
{//no
s=s->next;
p->rtime++;
p->super--;
p->next=NULL;
sort(s,p);
}
else
{//yes
s=s->next;
}
}
else
{
cout<<"就绪队列已经为空"<<endl; }
}
//creat process
void input()
{
pcb1 p2;
p2=new pcb;
cout<<"请输入 进程号、进程名、进程优先级、需要运行时间";
cin>>p2->id>>p2->name>>p2->super>>p2->ntime;
p2->rtime=0;
p2->state='W';
p2->rtime=0;
p2->next=NULL;
sort(s,p2);
}
//main function
void main()
{
char ch;
init(s);
init(w);
cout<<"*****************************进程调度模拟程序开始*******************************"<<endl;
cout<<"----w/唤醒进程-----r/运行进程-----z/阻塞进程----q/退出程序--"<<endl;
cout<<"--------c/创建进程---------s /查看就绪进程---------l/查看阻塞队列----"<<endl;
while(ch!='q')
{
cout<<"请输入一个字符"<<endl;
cin>>ch;
switch(ch)
{
case 'c':input(); break;
case 'r':runing(); break;
case 's':print(); break;
case 'w':wake(); break;
case 'l':print1(); break;
case 'z':block(); break;
}
}
}
程序运行界面如下：
五、实验总结
本次实验，我的任务是设计一个允许n个进程并发运行的进程管理模拟系统。该系统包括有简单的进程控制、同步与通讯机构，系统在运行过程中能显示各进程的状态及有关参数的变化情况，从而观察诸进程的运行过程及系统的管理过程，我是用C++写的，在我的电脑能够运行通过，虽不能尽善尽美，但也基本能实现老师的要求。
两个星期程序设计课程，虽然时间有点短，但我也收获不少，这次试验，加深了我对进程概念及进程管理的理解；比较熟悉进程管理中主要数据结构的设计及进程调度算法、进程控制机构、同步机构及通讯机构的实施。也让我认识到自己的不足，操作系统的有些知识，我知道的还不多，没有掌握好，还需要多多学学，不断提升自己的能力。