Posted on 2010-08-17 12:59
Brian 阅读(2196)
评论(1) 编辑 收藏 引用 所属分类:
OS
/*
Title: 时间片轮转法
Author: Brian
Date: 2010/04/09
*/
#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct PNode { // PCB
struct PNode *next; //指向下一个节点的指针
char name[12]; // 进程名
int All_Time; // 总运行时间
int Runed_Time; // 已运行时间
char state; // 进程状态 Ready / End
}* Proc; // 指向该PCB的指针
int ProcNum; // 全局变量，用于用户自己确定进程个数
void InitPCB(Proc &H) { //初始化就绪队列
cout<<"输入总进程个数: ";
cin>>ProcNum; //进程总个数
int Num=ProcNum;
H=(Proc)malloc(sizeof(PNode));
H->next=NULL;
Proc p=H;
cout<<"总进程个数默认为 "<<ProcNum<<" 个,请输入相应信息\n\n";
while (Num--) {
p=p->next=(Proc)malloc(sizeof(PNode));
cout<<"进程名 总运行时间 已运行时间 :";
cin>>p->name>>p->All_Time>>p->Runed_Time;
p->state='R';
p->next=NULL;
}
p->next=H->next; // 构造循环队列
}
void DispInfo(Proc H) { //输出运行中信息
Proc p=H->next;
do {
if (p->state != 'E')
{
cout<<"进程名:"<<p->name<<"\t总运行时间:"<<p->All_Time
<<"\t已运行时间:"<<p->Runed_Time
<<"\t状态:"<<p->state<<endl;
p=p->next;
}
else p=p->next;
} while (p != H->next); // 整个进程链条始终完整，只是状态位有差异
}
void SJP_Simulator(Proc &H) { // 时间片轮转法模拟器
cout<<endl<<"-------------------START--------------------\n";
int flag=ProcNum; // 记录剩余进程数
int round=0; // 记录轮转数
Proc p=H->next;
while (p->All_Time > p->Runed_Time) {
round++;
cout<<endl<<"Round "<<round<<"--正在运行 "<<p->name<<" 进程"<<endl;
p->Runed_Time++;
DispInfo(H);
if (p->All_Time == p->Runed_Time) {
p->state='E';
flag--;
cout<<p->name<<" 进程已运行结束,进程被删除!\n";
}
p=p->next;
while (flag && p->All_Time == p->Runed_Time)
p=p->next; // 这一步非常重要，跳过先前已结束的进程
}
cout<<endl<<"--------------------END---------------------\n";
}
void main() {
Proc H;
InitPCB(H); // 数据初始化
DispInfo(H); // 初始化成功后的进程状态
SJP_Simulator(H); // 模拟时间片轮转法
system("pause");
}
/*
Title: 高响应比优先算法
Author: Brian
Date: 2010/04/11
*/
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef struct PNode { //PCB
struct PNode *next; //指向下一个节点的指针
char name[12]; //进程名
int All_Time; //要求运行时间
int Wait_Time; //等待时间
float Res_Ratio; //响应比
char state; //状态 Ready/End
}* Proc; //指向该PCB的指针
int ProcNum; // 全局变量，用于用户自己确定进程个数
void ComputeRes(Proc &H) //计算响应比
{
Proc p=H->next;
while (p) {
if (p->state == 'R') {
p->Wait_Time++;
p->Res_Ratio=1+(float)(p->Wait_Time)/p->All_Time;
}
else p->Res_Ratio=0.0;
p=p->next;
}
}
void InitProc(Proc &H)
{
cout<<"输入总进程个数: ";
cin>>ProcNum; //进程总个数
int Num=ProcNum;
H=(Proc)malloc(sizeof(PNode));
H->next=NULL;
Proc p=H;
cout<<"总进程个数默认为 "<<ProcNum<<" 个,请输入相应信息\n\n";
while (Num--) {
p=p->next=(Proc)malloc(sizeof(PNode));
cout<<"进程名 总运行时间 等待时间 :";
cin>>p->name>>p->All_Time>>p->Wait_Time;
p->state='R';
p->Res_Ratio=1+(float)(p->Wait_Time)/p->All_Time;
p->next=NULL;
}
}
void DispInfo(Proc H) { //输出运行中信息
Proc p=H->next;
while (p) {
cout<<endl<<"进程名:"<<p->name<<"\t总运行时间:"<<p->All_Time
<<"\t等待时间:"<<p->Wait_Time
<<"\t响应比:"<<p->Res_Ratio<<"\t状态:"<<p->state<<endl;
p=p->next;
}
}
void RelocateMax(Proc &H) // 进程排序 (逆序算法) , 首节点是响应比最高节点
{
if(H->next==NULL || H->next->next==NULL)
return; // 只剩一个节点或没有节点时无需排序
Proc p=H->next,q,r;
if (p) {
r=p->next;
p->next=NULL;
p=r;
while (p) {
r=p->next;
q=H;
while (q->next && q->next->Res_Ratio < p->Res_Ratio)
q=q->next;
p->next=q->next;
q->next=p;
p=r;
}
}
p=H->next;
H->next=NULL;
while (p) {
q=p->next;
p->next=H->next;
H->next=p;
p=q;
}
}
void HRN_Simulator(Proc &H) //高响应比算法模拟器
{
cout<<endl<<"-------------------START--------------------\n";
int flag=ProcNum; // 记录剩余进程数
while (flag)
{
Proc p=H->next;
p->All_Time--;
p->Wait_Time=0;
p->Res_Ratio=1.0;
if (p->All_Time == 0)
{
p->state = 'E';
ComputeRes(H);
DispInfo(H);
if (p->next == NULL)
H->next = NULL;
else H->next = p->next; //将首节点删除
cout<<endl<<p->name<<" 进程已运行结束\n";
flag--;
}
else
{
DispInfo(H);ComputeRes(H);
}
RelocateMax(H);
}
cout<<endl<<"--------------------END---------------------\n\n";
}
void main()
{
Proc H;
InitProc(H); // 数据初始化
DispInfo(H); // 初始化成功后的进程状态
HRN_Simulator(H); // 模拟高响应比优先算法
system("pause");
}