#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<stdbool.h>
#define R "RUN" //运行中
#define F "FINISH" //已完成
#define W "WAITE" //等待中
#define T "TAKEN" //未提交
#define MAX 5
#define newblock (PCB *)malloc(sizeof(PCB))
int CurrentTime;//当前时间
int finish;//已完成数量
int visit[MAX]; //标记是否存在队列
typedef struct pcb //进程控制块定义
{
char pname[20];//进程名
float starttime;//开始时间
float runtime;//服务时间
float arrivetime;//到达时间
float finishtime;//完成时间
float zztime;//周转时间：zztime=finishtime-tarttime
float dqzztime;//带权周转时间:dqzztime=zztime/runtime
float st1;//剩余服务时间
int CpuTime;//所用cpu时间
int sc;//sign compeletion标志是否完成
char Status[10];//进程状态
}PCB;
typedef struct Node
{
int data; /*数据域*/
struct Node *next; /*指针域*/
}Node;
typedef struct
{
Node *front;
Node *rear;
}Queue;
void InitQueue(Queue *q)
{
/* 将Q初始化为一个空的链队列 */
q->front=(Node *)malloc(sizeof(Node));
if(q->front!=NULL){
q->rear=q->front;
q->front->next=NULL;
}
}
/*入队操作。*/
void Enqueue(Queue *q,int x)
{
/* 将数据元素x插入到队列Q中 */
Node *NewNode;
NewNode=(Node *)malloc(sizeof(Node));
if(NewNode!=NULL){
NewNode->data=x;
NewNode->next=NULL;
q->rear->next=NewNode;
q->rear=NewNode;
}
}
/*出队操作。*/
int Dequeue(Queue *q)
{
/* 将队列Q的队头元素出队，并存放到x所指的存储空间中 */
Node *p;
int x;
p=q->front->next;
q->front->next=p->next;
if(q->rear==p)
q->rear=q->front;
x=p->data;
free(p);
return x;
}
//进程状态检测与修改
void StatusConfirm(PCB* p){
int i;
for(i=0;i<MAX;i++)//到达时间等于当前时间则状态变为等待中
{
if(CurrentTime>=p[i].arrivetime&&strcmp(p[i].Status,T)==0)
{
strcpy(p[i].Status,W);
}
if(p[i].CpuTime==p[i].runtime&&strcmp(p[i].Status,W)==0)
{
finish++;
strcpy(p[i].Status,F);
p[i].finishtime=CurrentTime;
p[i].zztime=p[i].finishtime-p[i].arrivetime;
p[i].dqzztime=p[i].zztime*1.0/p[i].runtime;
}
}
}
//取就绪队列中运行时间最短的进程下标
int ShortIndex(PCB* p){
int i;
int min;
int temp;
min=100;
temp=-1;
StatusConfirm(p);//更新进程状态
for(i=0;i<MAX;i++)
{
if(strcmp(p[i].Status,W)==0)
{
if(p[i].runtime< min)//有更小的运行时间则更新
{
min=p[i].runtime;
temp=i;
}
}
}
return temp;
}
void append(PCB *p,int n)
{
printf("\n请输入进程名,到达时间和服务时间，以回车结束输入：\n");
for(int i=0;i<n;i++)
{
scanf("%s",&p[i].pname);
scanf("%f",&p[i].arrivetime);
scanf("%f",&p[i].runtime);
p[i].starttime=-1;
p[i].finishtime=-1;
p[i].zztime=0.0;
p[i].dqzztime=0.0;
p[i].CpuTime=0;
strcpy(p[i].Status, T);
}
}
void show(PCB *p,int n)
{
int i;
printf("作业号: \t到达时间: \t服务时间: \t进程状态：");
for(i=0;i<n;i++)
{
printf("\n");
printf(" %3s\t\t\t%d\t\t%d\t\t%s",p[i].pname,(int)p[i].arrivetime,(int)p[i].runtime,p[i].Status);
printf("\n");
}
}
void sort_arrivetime(PCB *p,int n)//用冒泡排序把进程控制块按照最先到达时间排序
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
if(p[j].arrivetime>p[j+1].arrivetime)
{
PCB temp;
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
}
}
void run(PCB *p,int n)
{
int i;
for(i=0;i<n;i++)
{
if(i==0)
{
p[i].starttime=p[i].arrivetime;
p[i].finishtime=p[i].arrivetime+p[i].runtime;
p[i].zztime=p[i].runtime;
p[i].dqzztime=p[i].zztime/p[i].runtime;
}
else
{
p[i].starttime=p[i-1].finishtime;
p[i].finishtime=p[i].starttime+p[i].runtime;
p[i].zztime=p[i].finishtime-p[i].arrivetime;
p[i].dqzztime=p[i].zztime/p[i].runtime;
}
}
}
void sum(PCB *p,int n)
{
int i;
float avgzztime=0,avgdqzztime=0;
for(i=0;i<n;i++)
{
avgzztime+=p[i].zztime;
avgdqzztime+=p[i].dqzztime;
}
printf("\n\n平均周转时间:%.2f",avgzztime/n);
printf("\n平均带权周转时间:%.2f",avgdqzztime/n);
}
void print(PCB *p,int n)
{
int i;
printf("\n\n作业号: \t到达时间: \t服务时间: \t周转时间：\t带权周转时间\n");
for(i=0;i<n;i++)
{
printf("\n\t%3s\t\t%d\t\t%d\t\t%.2f\t\t%.3f",p[i].pname,(int)p[i].arrivetime,(int)p[i].runtime,p[i].zztime,p[i].dqzztime);
}
}
//先来先服务算法
void FCFS(PCB *p,int n)
{
int i;
printf("\n先来先服务算法FCFS：\t");
for(i=0;i<n;i++)
printf("%s ",p[i].pname);
}
//短进程优先调度SJF
void SJF(PCB *p,int n)
{
int i,j,t,k;
PCB temp;//创建一个零时进程，便于后续交换
float end=0.0;//保存cpu已经运行的时间
for(i=0;i<n;i++)//一次排好一个进程
{
k=i;//保存当前进程的下标
while(p[i].arrivetime<=end && i<n)//对从第i个之后的所有进程进行搜索
i++;//找到最后一个等待进程的下标
for(t=k;t<i;t++)//对等待就绪的进程进行按运行时间最短排序
{
for(j=k+1;j<i;j++)
if(p[t].runtime>p[j].runtime)
{
temp=p[t];
p[t]=p[j];
p[j]=temp;
}
}
i=k;//将i的下标还原
end+=p[i].runtime;
}
printf("\n短进程优先调度SJF：\t");
for(i=0;i<n;i++)
printf("%3s ",p[i].pname);
}
//时间片轮转算法
void RR(PCB* p,int n)
{
int t;printf("\n请输入时间片：");scanf("%d",&t);
printf("\n时间片轮转算法RR：\t");
Queue LQ;
InitQueue(&LQ);//创建队列
sort_arrivetime(p,n);//按到达时间排列
int index;
int first;//cpu开始运行时间
int i,j;
first=p[0].arrivetime;
memset(visit,0,sizeof(visit));//标记数组置零
for(index=0,finish=0;finish!=MAX;CurrentTime+=t)//进程调度位currentTime每次加1，直到进程全部被调度完成为止
{
StatusConfirm(p);
if(CurrentTime<first||ShortIndex(p)==-1); //最快到达的进程未到达或就绪队列无进程
else{
if(CurrentTime==first)//针对刚开始运行那一下，即第一次循环，之后的循环不用看
{
Enqueue(&LQ,0);
visit[0]=1;//已存在队列
}
for(i=0,j=index+1;i<MAX;i++,j++)//将提交的进程入队
{
if(j==MAX) j=0;
if(!visit[j]&&strcmp(p[j].Status,W)==0)
{
Enqueue(&LQ,j);
visit[j]=1;//已存在队列
}
}
index=Dequeue(&LQ);//取队头
visit[index]=0;//不存在队列中
strcpy(p[index].Status,R);//进程状态为运行中
printf("%s ",p[index].pname);
p[index].CpuTime+=t;//当前进程所用cpu时间增加
if(p[index].CpuTime==p[index].runtime)//若所用cpu时间已达到所需运行时间
{
strcpy(p[index].Status,F);
p[index].finishtime=CurrentTime+t;// 更新完成时间
p[index].zztime=p[index].finishtime-p[index].arrivetime; //计算周转时间
p[index].dqzztime= p[index].zztime*1.0/p[index].runtime;//计算带权周转时间
finish++;
}
else strcpy(p[index].Status,W);//时间片用完进程重新变为等待状态
}
}
}
void Start(PCB *p)
{
int n,m;
printf("\n***进程调度算法***\n");
printf("\n-------------------------------------------------------------------------------\n\n\n");
printf("请输入进程数目：");scanf("%d",&n);
append(p,n);
printf("\n--------------------------------
评论0