新版操作系统课程设计报告样本.doc

资料内容仅供您学习参考，如有不当之处，请联系改正或者删除。
东莞理工学院
操作系统课程设计报告

学 院: 计算机学院
专 业 班 级: 13软件工程1班
学号
姓名
评价

提交时间: /9/14
指导教师评阅意见:

.

项目名称: 进程与线程管理功能
一、 设计目的
用语言来模拟进程和线程管理系统, 加深对进程和线程的理解, 掌握对进程和线程各种状态和管理的算法原理。
二、 环境条件
系统: WindowsXP、 VMWare、 Ubuntu Linux
语言: C/C++
开发工具: gcc/g++、 Visual C++ 6.0
三、 设计内容
1. 项目背景

计算机的硬件资源有限, 为了提高内存的利用率和系统的吞吐量, 就要根据某种算法来管理进程和线程的状态从而达到目的。
进程与线程管理功能完成基于优先级的抢占式线程调度功能, 完成进程虚拟内存管理功能。
进程与线程管理功能
基本要求: 完成基于优先级的抢占式线程调度功能, 完成进程虚拟内存管理功能。
提高要求: ( 增加1项就予以加分)
(1) 实现多种线程调度算法;
(2)经过”公共信箱”进行通信的机制, 规定每一封信的大小为128字节, 实现两个用户进程之间经过这个”公共信箱”进行通信。
(3) 实现多用户进程并发的虚拟内存管理功能。
(4) 实现用户进程间通信功能, 并用生产者/消费者问题测试进程间通信功能的正确性。
(5) 实现改进型Clock页面置换算法。
(6) 实现Cache功能, 采用FIFO替换算法。
2. 扩展内容
实现多种线程调度算法:时间片轮转调度算法
四、 人员分工
优先级调度算法: 钟德新, 莫友芝
时间片轮转调度算法: 张德华, 袁马龙
设计报告由小组队员共同完成。小组成员设计的代码分工如下:
钟德新编写的代码: void Prinft(){
PCB *p;
system("cls");//清屏
p=run; //运行队列
if(p!=NULL)
{
p->next=NULL;
}
cout<<"当前正在运行的进程: "<<endl;
cout<<"进程名称"<<"\t"<<"优先数"<<"\t"<<"还需要时间"<<"\t"<<"已运行时间"<<"\t"<<"状态:"<<endl;
while(p!=NULL)
{
cout<<p->procname<<"\t\t"<<p->pri<<"\t"<<p->needOftime<<"\t\t"<<p->runtime<<"\t\t"<<p->state<<endl;
p=p->next;
}
cout<<endl<<endl;
cout<<"当前的就绪队列: "<<endl; cout<<"进程名称"<<"\t"<<"优先数"<<"\t"<<"还需要时间"<<"\t"<<"已运行时间"<<"\t"<<"状态:"<<endl;
p=ready; //就绪队列
while(p!=NULL)
{
cout<<p->procname<<"\t\t"<<p->pri<<"\t"<<p->needOftime<<"\t\t"<<p->runtime<<"\t\t"<<p->state<<endl;
p=p->next;
}
cout<<endl<<endl;

cout<<"当前已经完成的进程: "<<endl; //终止队列
cout<<"进程名称"<<"\t"<<"优先数"<<"\t"<<"还需要时间"<<"\t"<<"已运行时间"<<"\t"<<"状态:"<<endl;
p=finish;
while(p!=NULL)
{
cout<<p->procname<<"\t\t"<<p->pri<<"\t"<<p->needOftime<<"\t\t"<<p->runtime<<"\t\t"<<p->state<<endl;
p=p->next;
}
}
这个函数是优先级调度算法程序的界面函数, 主要为程序运行时能够直观的显示结果
void insert(PCB *p)
{
PCB *S1,*S2;
if(ready==NULL) //判断队列是否为空
{
p->next = NULL;
ready = p; //插入就绪队列
}else{
S1 = ready;
S2 = S1;
while(S1!=NULL)
{
if(S1->pri >= p->pri) //判断优先级大小
{
S2 = S1; //置换位置
S1 = S1->next;
}else{
break; //跳出循环
}
}

if(S2->pri >= p->pri)
{
S2->next = p;
p->next = S1;
}else{
p->next = ready;
ready = p;
}
}
}
这是程序优先级排序的函数, 也是优先级调度算法的核心思想函数, 对程序的优先级经过指针进行排序, 再将队首的程序调入运行队列, 经过置换的方法, 将运行队列队首即占用CPU的程序调入就绪队列, 如此循环直至所有程序终止为止。

莫友芝编写的代码: void priority()
{
run = ready;
ready = ready->next;
run->state = "运行";
while(run!=NULL) /*当运行队列不空时, 有进程正在运行*/
{
Dtime(3);//调用延时函数, 延时3秒
run->runtime=run->runtime+1; //运行时间+1
run->needOftime=run->needOftime-1; //完成需要时间-1
run->pri=run->pri-1; /* //优先级-1每运行一次优先数降低1个单位*/
if(run->needOftime==0) /*如所需时间为0将其插入完成队列*/
{
run->state = "完成";
run->next = finish;
finish = run;
run=NULL; /*运行队列头指针为空*/
if(ready!=NULL) /*如就绪队列不空*/
{
run = ready;
run->state = "运行";
ready = ready->next;
}
}else if( (ready!=NULL)&&(run->pri < ready->pri) ){ //就绪队列不为空, 就绪队列队首优先级大于运行队列队首
run->state="就绪";
insert(run); //运行中的进程重新比较优先级大小
run = ready; //对队列队首的进程调入CPU
run->state = "运行";
ready = ready->next;
}
Prinft(); /*输出进程PCB信息*/
}
}
这是程序运行时的实时程序, 经过循环的方法在程序等候3秒后, 调用德新设计的优先级排序算法, 进行排序。
void CTProcessOfPri()//创立进程
{
PCB * Node;
string c[5]={"P1","P2","P3","P4","P5"}; //模拟设计5条进程
srand((int)time(0)); //设置随机种子
for(int j = 0;j < 5; j++)
{
Node = new PCB;
if(Node==NULL)
{
return;
}else{
Node->procname=c[j]; //为进程名赋值
Node->needOftime=1+(int)(15.0*rand()/(RAND_MAX+1.0));//为进程随机分配占用CPU时间.
Node->runtime = 0; //为运行时间赋值
Node->state ="就绪"; //设置初始状态为”就绪”状态
Node->pri =1+(int)(20.0*rand()/(RAND_MAX+1.0)); //为进程随机分配优先数.
}
insert(Node); //出入就行队列
}
}
随机创立5个模拟程序, 为其赋上初值后, 调用优先级排序函数, 进行第一次排序

张德华编写的程序代码: void insert(PCB *p){ //时间片插入函数
if(start->next==NULL){
PCB *q=start;
if(p->Arrive_time<q->Arrive_time){
start=p;
p->next=q;
q->next=NULL;
end=q;
}else{
q->next=p;
p->next=NULL;
end=p;
}
}else{
PCB *q=start;
PCB *s=start->next;
while(s!=NULL){
if(q->Arrive_time > p->Arrive_time){
p->next=q;
start=p;
return;
}else{
if(s->Arrive_time > p->Arrive_time){
q->next=p;
p->next=s;
return;
}else{
q=q->next;
s=s->next;
}
}
}
s->next=p;
end=p;
}
}
这个是时间片插入函数, 也是轮转调度模拟程序的核心函数, 首先对到达时间进行排序, 将队首调入CPU后, 运行时间片的时间后, 调入就绪队列队尾, 等候下一次的资源.
void firstin(){ //将就绪队列的第一个进程放入运行队列
run=start;
run->State='W'; //改变其状态
start=start->next;
}
模拟占用CPU的函数
void show(PCB *p) //输出函数
{
cout<<"进程名"<<"\t"<<"到达时间"<<"\t"<<"剩余时间"<<"\t"<<"状态\n"; //
if(run!=NULL) //如果运行指针不为空,就输出当前正在运行的进程的PCB
{ cout<<p->name<<"\t"<<p->Arrive_time<<"\t""\t"<<p->Need_time<<"\t""\t"<<p->State<<"\n\n";
}
}
这是一个程序初始值的输出函数, 验证输入的各程序的初始值是否是预期输入

袁马龙编写的代码: void create() //时间片算法创立进程函数
{
cout<<"请输入所需要运行的进程个数: ";
cin>>N;
PCB *p;
int Time_piece;
start=NULL; //就绪队列头指针
finish=NULL; //完成队列头指针
run=NULL; //运行队列指针
cout<<"请输入时间片长度: ";
cin>>Time_piece;
for(int i=1;i<=N;i++){ //输入进程名字和所需时间,创立进程的PCB
p=(PCB *)malloc(sizeof(PCB));
cout<<"请输入第"<<i<<"个进程的名字:";
cin>>p->name;
cout<<"预计运行的时间:";
cin>>p->Need_time;
cout<<"到达时间:";
cin>>p->Arrive_time;
Cpu_time=0;
p->Count=0; //计数器
p->State='W'; //进程的初始状态设为就绪'W'
p->Time_piece=Time_piece; //时间片的初始值
if(start!=NULL){
insert(p); //若就绪队列不为空,将其插入就绪队列
}else{ //创立就绪队列的第一个PCB
p->next=start;
start=p; //头指针
end=p; //尾指针
}
}
cout<<endl<<endl<<"\t使用时间片轮转算法输出结果: (W为就绪状态, F为终止状态)\n";
cout<<"*********************************************************\n";
run=start; //将就绪队列的第一个进程投入运行
start=start->next;
run->State='W';
}
这是一个设置程序运行初始的条件函数, 如需要运行的程序数目, 程序名称, 运行时间等, 在调用德华设计的排序函数进行排序, 调入队列中
void roundrobin(){ //时间片算法函数
int m=0;
while(run!=NULL){
if(run->Arrive_time>Cpu_time){
Cpu_time=Cpu_time+1; //每运行一次cputime加一
}else{
if(m==0){
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~进程"<<run->name<<"开始 ~~~~~~~~~~~~~~~~~~~~~~~\n\n";
m++;
}
run->Need_time=run->Need_time-1; //每运行一次needtime减一
if(run->Need_time!=0)
show(run);
Cpu_time=Cpu_time+1; //每运行一次cputime加一
run->Count=run->Count+1; //每运行一次计数器count加一
if(run->Need_time==0){ //若运行完后
run->next=finish;
finish=run; //将其插入完成队列头部
run->State='F'; //将其状态改为完成态"F"
show(run);
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~进程"<<run->name<<"结束~~~~~~~~~~~~~~~~~~~~~~~\n\n";
run=NULL; //将运行队列清空
if(start!=NULL) {
firstin(); //若就绪对列不空, 将第一个进程投入运行
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~进程"<<run->name<<"开始 ~~~~~~~~~~~~~~~~~~~~~~~\n\n";
}
}else{
if(run->Count==run->Time_piece){ //如果时间片到
run->Count=0; //计数器置0
if(start!=NULL){ //若就绪队列不空
run->State='W';
insert2(run); //将进程插入到就绪队列中等待轮转
firstin(); //将就绪队列的第一个进程投入运行
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~进程"<<run->name<<"开始~~~~~~~~~~~~~~~~~~~~~~~\n\n";
}
}
}
}
}
cout<<"*********************************************************\n";}
这是一个程序运行结果的输出函数, 输出程序的结果内容, 在什么时间段完成, 什么时间段到达, 以及程序的状态等信息

五、 设计过程
进程是进程实体的运行过程是系统进行资源分配和调度的一个独立单位。另有一种定义方法是”程序在处理器上的执行”。为了模拟的方便, 本设计采用这种定义。简单地说, 进程包括三种状态: 运行状态、 就绪状态、 完成状态
优先级调度算法: 按照进程的优先级大小来调度, 是高优先级进程得到优先的处理的调度策略, 可使用非抢占或可抢占两种策略
用C++模拟设计一个进程模拟类class PCB{
public:
string procname;//进程名
int pri;//进程优先数
string state;//进程状态
int runtime;//进程已运行CPU时间
int needOftime;//还需要时间
PCB *next;//指针
};
来记录进程的基本信息, 如进程名称, 优先级, 进程状态, 进程运行时间, 进程所需时间
再设计模拟进程所需要的各种算法, 运行调试结果

时间片轮转调度算法: 是一种最古老, 最简单, 最公平且使用最广的算法。每个进程被分配一时间段, 称作它的时间片, 即该进程允许运行的时间. 如果在时间片结束时进程还在运行, 则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束, 则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表, 当进程用完它的时间片后, 它被移到队列的末尾.
用C语言模拟设计一个类typedef struct node {
char name[10]; //进程名
int Time_piece; //时间片
int Need_time; //还需要的时间
int Count; //计数器
char State; //进程的状态
struct node *next; //链指针
int Arrive_time; //到达时间
}PCB;
用这个类根据算法的基本思想来设计程序, 模拟算法的运行情况

优先级抢占式调度算法: ( 过程图)

时间片轮转调度算法:( 过程图)

六、 运行结果
优先级抢占式:

时间片轮转调度算法:

七、 结果分析
程序的结果很好体现的进程运行的优先级处理, 对于优先级高的程序, 采用抢占式, 分配程序CPU使用, 优先级较低的进入就绪队列等待CPU资源
而时间片轮转调度算法也很好的实行预期情况, 程序进入CPU运行时间片长度的时间后, 调入就绪队列队尾, 完成则进入完成队列。队首调入CPU, 占用资源, 循环直到所有程序都进入就绪队列.
八、 设计总结
1.设计基本实现了我们小组想要的功能和预测情况, 虽然中间关于指针的使用我们做了许多的调试, 可是我们还是做出来了。
2.然后就是进程算法的调用过程和知识, 发现自己对知识的遗忘程度有点大, 边做边补, 实验结束的会后发现自己的知识巩固了不少。对操作系统的了解也更加深入了。
3.和队友合作然后团队意识有一定的提高
附录:
优先级抢占式调度算法:

///////////////////////////优先级抢占式线程调度算法/////////////////////////

#include "stdlib.h"
#include <iostream>
#include <time.h>
#include <string>

using namespace std;

int n;

class PCB
{
public:
string procname;//进程名
int pri;//进程优先数
string state;//进程状态
int runtime;//进程已运行CPU时间
int needOftime;//还需要时间
PCB *next;//指针
};

PCB *run = NULL; //运行队列头指针
PCB *ready = NULL;//就绪队列头指针
PCB *finish = NULL;//完成队列头指针

/////////////////////////////////延时函数, 模拟CPU占用时间/////////////////////////////
void Dtime(int t){ //此代码块参考网上资料
time_t current_time;
time_t start_time;
time(&start_time);
do{
time(& current_time);
}while((current_time-start_time)<t);
}

//////////////////////////////输出函数, 调整输出界面//////////////////////////////////////
void Prinft(){
PCB *p;
system("cls");//清屏
p=run; //运行队列

if(p!=NULL)
{
p->next=NULL;
}
cout<<"当前正在运行的进程: "<<endl;
cout<<"进程名称"<<"\t"<<"优先数"<<"\t"<<"还需要时间"<<"\t"<<"已运行时间"<<"\t"<<"状态:"<<endl;

while(p!=NULL)
{
cout<<p->procname<<"\t\t"<<p->pri<<"\t"<<p->needOftime<<"\t\t"<<p->runtime<<"\t\t"<<p->state<<endl;
p=p->next;
}
cout<<endl<<endl;

cout<<"当前的就绪队列: "<<endl; cout<<"进程名称"<<"\t"<<"优先数"<<"\t"<<"还需要时间"<<"\t"<<"已运行时间"<<"\t"<<"状态:"<<endl;
p=ready; //就绪队列

while(p!=NULL)
{
cout<<p->procname<<"\t\t"<<p->pri<<"\t"<<p->needOftime<<"\t\t"<<p->runtime<<"\t\t"<<p->state<<endl;
p=p->next;
}
cout<<endl<<endl;

cout<<"当前已经完成的进程: "<<endl; //终止队列
cout<<"进程名称"<<"\t"<<"优先数"<<"\t"<<"还需要时间"<<"\t"<<"已运行时间"<<"\t"<<"状态:"<<endl;
p=finish;

while(p!=NULL)
{
cout<<p->procname<<"\t\t"<<p->pri<<"\t"<<p->needOftime<<"\t\t"<<p->runtime<<"\t\t"<<p->state<<endl;
p=p->next;
}
}

//////////////////////////////////////////按优先级大小插入就绪队列
void insert(PCB *p)
{
PCB *S1,*S2;
if(ready==NULL) //判断队列是否为空
{
p->next = NULL;
ready = p; //插入就绪队列
}else{
S1 = ready;
S2 = S1;
while(S1!=NULL)
{
if(S1->pri >= p->pri) //判断优先级大小
{
S2 = S1; //置换位置
S1 = S1->next;
}else{
break; //跳出循环
}
}

if(S2->pri >= p->pri)
{
S2->next = p;
p->next = S1;
}else{
p->next = ready;
ready = p;
}
}
}

//////////////////////////实时运行函数///////////////////////////////
void priority()
{
run = ready;
ready = ready->next;
run->state = "运行";
while(run!=NULL) /*

当运行队列不空时, 有进程正在运行

*/
{
Dtime(3);//调用延时函数, 延时3秒

run->runtime=run->runtime+1; //运行时间+1
run->needOftime=run->needOftime-1; //完成需要时间-1
run->pri=run->pri-1; /* //优先级-1

每运行一次优先数降低1个单位

*/
if(run->needOftime==0) /*

如所需时间为0将其插入完成队列

*/
{
run->state = "完成";
run->next = finish;
finish = run;
run=NULL; /*

运行队列头指针为空

*/
if(ready!=NULL) /*

如就绪队列不空

*/
{
run = ready;
run->state = "运行";
ready = ready->next;
}
}else if( (ready!=NULL)&&(run->pri < ready->pri) ){ //就绪队列不为空, 就绪队列队首优先级大于运行队列队首
run->state="就绪";

insert(run); //运行中的进程重新比较优先级大小

run = ready; //对队列队首的进程调入CPU
run->state = "运行";
ready = ready->next;
}
Prinft(); /*

输出进程PCB信息

*/
}

}

void CTProcessOfPri()//创立进程
{
PCB * Node;
string c[5]={"P1","P2","P3","P4","P5"}; //模拟设计5条进程
srand((int)time(0)); //设置随机种子
for(int j = 0;j < 5; j++)
{
Node = new PCB;
if(Node==NULL)
{
return;
}else{
Node->procname=c[j]; //为进程名赋值
Node->needOftime=1+(int)(15.0*rand()/(RAND_MAX+1.0)); //为进程随机分配占用CPU时间.
Node->runtime = 0; //为运行时间赋值
Node->state ="就绪"; //设置初始状态为”就绪”状态
Node->pri =1+(int)(20.0*rand()/(RAND_MAX+1.0)); //为进程随机分配优先数.
}
insert(Node); //出入就行队列
}
}

void main()
{
cout<<"*******************************************"<<endl;
cout<<"* 优先数调度算法*"<<endl;
cout<<"*******************************************"<<endl;
cout<<"按任意键开始创立进程??"<<endl;
getchar();
CTProcessOfPri(); //新建进程

Prinft(); //调用界面输出函数
cout<<endl;
cout <<"按任意键开始运行进程模拟调度程序??"<<endl;
getchar();

priority(); //运行模拟进程调度。
}
时间片轮转调度算法:
#include "iostream.h"
#include "string.h"
#include "stdlib.h"

typedef struct node {
char name[10]; //进程名
int Time_piece; //时间片
int Need_time; //还需要的时间
int Count; //计数器
char State; //进程的状态
struct node *next; //链指针
int Arrive_time; //到达时间
}PCB;

//run为当前运行进程指针,start为就绪队列头指针
//end为就绪队列尾指针,finish为完成队列头指针
PCB *run,*start,*end,*finish;

int N; //进程个数
int Cpu_time;//需要的CPU时间

void insert(PCB *p){ //时间片插入函数
if(start->next==NULL){
PCB *q=start;
if(p->Arrive_time<q->Arrive_time){
start=p;
p->next=q;
q->next=NULL;
end=q;
}else{
q->next=p;
p->next=NULL;
end=p;
}
}else{
PCB *q=start;
PCB *s=start->next;
while(s!=NULL){
if(q->Arrive_time > p->Arrive_time){
p->next=q;
start=p;
return;
}else{
if(s->Arrive_time > p->Arrive_time){
q->next=p;
p->next=s;
return;
}else{
q=q->next;
s=s->next;
}
}
}
s->next=p;
end=p;
}
}

void insert2(PCB *p){
end->next=p; //将新的PCB插入在当前就绪队列的尾
end=p;
p->next=NULL;
}

void show(PCB *p) //输出函数
{
cout<<"进程名"<<"\t"<<"到达时间"<<"\t"<<"剩余时间"<<"\t"<<"状态\n"; //
if(run!=NULL) //如果运行指针不为空,就输出当前正在运行的进程的PCB
{
cout<<p->name<<"\t"<<p->Arrive_time<<"\t""\t"<<p->Need_time<<"\t""\t"<<p->State<<"\n\n";
}
}

void create