新版操作系统专业课程设计方案报告.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() //时间片算法创立进程函数
{
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<<"个进程名字:"