Posted on 2010-08-17 12:59
Brian 閱讀(2239)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
OS
/*
Title: 時(shí)間片輪轉(zhuǎn)法
Author: Brian
Date: 2010/04/09
*/
#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct PNode { // PCB
struct PNode *next; //指向下一個(gè)節(jié)點(diǎn)的指針
char name[12]; // 進(jìn)程名
int All_Time; // 總運(yùn)行時(shí)間
int Runed_Time; // 已運(yùn)行時(shí)間
char state; // 進(jìn)程狀態(tài) Ready / End
}* Proc; // 指向該P(yáng)CB的指針
int ProcNum; // 全局變量，用于用戶自己確定進(jìn)程個(gè)數(shù)
void InitPCB(Proc &H) { //初始化就緒隊(duì)列
cout<<"輸入總進(jìn)程個(gè)數(shù): ";
cin>>ProcNum; //進(jìn)程總個(gè)數(shù)
int Num=ProcNum;
H=(Proc)malloc(sizeof(PNode));
H->next=NULL;
Proc p=H;
cout<<"總進(jìn)程個(gè)數(shù)默認(rèn)為 "<<ProcNum<<" 個(gè),請(qǐng)輸入相應(yīng)信息\n\n";
while (Num--) {
p=p->next=(Proc)malloc(sizeof(PNode));
cout<<"進(jìn)程名 總運(yùn)行時(shí)間 已運(yùn)行時(shí)間 :";
cin>>p->name>>p->All_Time>>p->Runed_Time;
p->state='R';
p->next=NULL;
}
p->next=H->next; // 構(gòu)造循環(huán)隊(duì)列
}
void DispInfo(Proc H) { //輸出運(yùn)行中信息
Proc p=H->next;
do {
if (p->state != 'E')
{
cout<<"進(jìn)程名:"<<p->name<<"\t總運(yùn)行時(shí)間:"<<p->All_Time
<<"\t已運(yùn)行時(shí)間:"<<p->Runed_Time
<<"\t狀態(tài):"<<p->state<<endl;
p=p->next;
}
else p=p->next;
} while (p != H->next); // 整個(gè)進(jìn)程鏈條始終完整，只是狀態(tài)位有差異
}
void SJP_Simulator(Proc &H) { // 時(shí)間片輪轉(zhuǎn)法模擬器
cout<<endl<<"-------------------START--------------------\n";
int flag=ProcNum; // 記錄剩余進(jìn)程數(shù)
int round=0; // 記錄輪轉(zhuǎn)數(shù)
Proc p=H->next;
while (p->All_Time > p->Runed_Time) {
round++;
cout<<endl<<"Round "<<round<<"--正在運(yùn)行 "<<p->name<<" 進(jìn)程"<<endl;
p->Runed_Time++;
DispInfo(H);
if (p->All_Time == p->Runed_Time) {
p->state='E';
flag--;
cout<<p->name<<" 進(jìn)程已運(yùn)行結(jié)束,進(jìn)程被刪除!\n";
}
p=p->next;
while (flag && p->All_Time == p->Runed_Time)
p=p->next; // 這一步非常重要，跳過(guò)先前已結(jié)束的進(jìn)程
}
cout<<endl<<"--------------------END---------------------\n";
}
void main() {
Proc H;
InitPCB(H); // 數(shù)據(jù)初始化
DispInfo(H); // 初始化成功后的進(jìn)程狀態(tài)
SJP_Simulator(H); // 模擬時(shí)間片輪轉(zhuǎn)法
system("pause");
}
/*
Title: 高響應(yīng)比優(yōu)先算法
Author: Brian
Date: 2010/04/11
*/
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef struct PNode { //PCB
struct PNode *next; //指向下一個(gè)節(jié)點(diǎn)的指針
char name[12]; //進(jìn)程名
int All_Time; //要求運(yùn)行時(shí)間
int Wait_Time; //等待時(shí)間
float Res_Ratio; //響應(yīng)比
char state; //狀態(tài) Ready/End
}* Proc; //指向該P(yáng)CB的指針
int ProcNum; // 全局變量，用于用戶自己確定進(jìn)程個(gè)數(shù)
void ComputeRes(Proc &H) //計(jì)算響應(yīng)比
{
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<<"輸入總進(jìn)程個(gè)數(shù): ";
cin>>ProcNum; //進(jìn)程總個(gè)數(shù)
int Num=ProcNum;
H=(Proc)malloc(sizeof(PNode));
H->next=NULL;
Proc p=H;
cout<<"總進(jìn)程個(gè)數(shù)默認(rèn)為 "<<ProcNum<<" 個(gè),請(qǐng)輸入相應(yīng)信息\n\n";
while (Num--) {
p=p->next=(Proc)malloc(sizeof(PNode));
cout<<"進(jìn)程名 總運(yùn)行時(shí)間 等待時(shí)間 :";
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) { //輸出運(yùn)行中信息
Proc p=H->next;
while (p) {
cout<<endl<<"進(jìn)程名:"<<p->name<<"\t總運(yùn)行時(shí)間:"<<p->All_Time
<<"\t等待時(shí)間:"<<p->Wait_Time
<<"\t響應(yīng)比:"<<p->Res_Ratio<<"\t狀態(tài):"<<p->state<<endl;
p=p->next;
}
}
void RelocateMax(Proc &H) // 進(jìn)程排序 (逆序算法) , 首節(jié)點(diǎn)是響應(yīng)比最高節(jié)點(diǎn)
{
if(H->next==NULL || H->next->next==NULL)
return; // 只剩一個(gè)節(jié)點(diǎn)或沒(méi)有節(jié)點(diǎn)時(shí)無(wú)需排序
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) //高響應(yīng)比算法模擬器
{
cout<<endl<<"-------------------START--------------------\n";
int flag=ProcNum; // 記錄剩余進(jìn)程數(shù)
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; //將首節(jié)點(diǎn)刪除
cout<<endl<<p->name<<" 進(jìn)程已運(yùn)行結(jié)束\n";
flag--;
}
else
{
DispInfo(H);ComputeRes(H);
}
RelocateMax(H);
}
cout<<endl<<"--------------------END---------------------\n\n";
}
void main()
{
Proc H;
InitProc(H); // 數(shù)據(jù)初始化
DispInfo(H); // 初始化成功后的進(jìn)程狀態(tài)
HRN_Simulator(H); // 模擬高響應(yīng)比優(yōu)先算法
system("pause");
}