多道批处理的调度算法
typedef struct data
{
int hour;
int minute;
}time; //时间
typedef struct link_node{
char name[5]; //作业名
time inTime; //入井时间
time outTime; //完成时间
time jobTime; //作业调度时间
time processTime; //进程调度时间
int zz;//周转时间
float zzxs;//带权周转时间
int workTime; //运行时间
int needMemory; //需要内存资源数
int needTape; //需要磁带机数
int surplusMemory; //分配之后此时剩余资源数
int surplusTape; //分配之后此时剩余磁带机数
int finished; //标记结束返回内存资源
int flag;//0表示作业处于后备等待队列， 1处于就绪等待队列 ，-1表示已经结束
float hrrf; //响应比
struct link_node *next;
}node;
typedef node linknode;
int process,memory,tape; //进程数，主存大小，磁带机数
time now_time; //记录当前时间
程序框架：
//函数名：print_work 参数：linknode *head
void print_work(linknode *head){
//功能：打印作业表的各项信息（调度前）
}
//函数名：create_node 参数：无
linknode *create_node(void){
//功能：通过malloc函数创建结点并给各个属性赋值
}
//函数名：go_ahead 参数：int n
void go_ahead(int n){
//功能：计算当前时间形式为XX:XX
}
//函数名：work_execute 参数：linknode *head
void work_execute(linknode *head){
//功能：进行作业调度，判断系统资源能否满足此次的作 业调 度请求，若满足则将该作业调入就绪队列。
}
//函数名：process_excute 参数：linknode* head
void process_execute(linknode *head){
//功能：进行进程调度，调度完成后将作业标记为已完成。
}
//函数名：FCFS 参数：无
void FCFS(void){
//功能：实现先来先服务调度算法
}
//函数名：input_FCFS 参数：无
linknode *input_FCFS(void){
//功能：完成FCFS算法的输入过程
}
//函数名：insert_FCFS 参数：linknode *head, linknode *Node
void insert_FCFS(linknode *head,linknode *Node){
//功能：为input_FCFS提供服务，实现将作业结点插入队列尾部
}
//函数名：SJF 参数：无
void SJF(void){
//功能：实现SJF算法
}
//函数名：input_SJF 参数：无
linknode *input_SJF(void){
//功能：完成SJF算法的输入过程
}
//函数名：insert_SJF 参数：linknode *head,linknode *Node
void insert_SJF(linknode *head,linknode *Node){
//功能：为input_SJF提供服务，实现将作业结点按照执行时间由 小到大插入队列当中
}
//函数名：HRRF 参数:无
void HRRF(void){
//功能：实现HRRF算法
}
//函数名：HRRF_execute 参数：linknode *head
void HRRF_execute(linknode *head){
//功能：模拟HRRF中的作业调度过程和进程调度过程
}
//函数名：sort_HRRF 参数：linknode *head
linknode * sort_HRRF(linknode *head){
//功能：实现将从给定的形参指针后的结点按照此时响应比的由大 到小的顺序进行排序完成后返回排序后的未完成作业的首指针
}
int main()
{
int choice;
do{
printf("请输入你要创建的进程数:");
scanf("%d",&process);
printf("请输入主存大小和磁带机总数:");
scanf("%d %d",&memory,&tape);
printf("******************调度算法******************\n");
printf(" * 1.MUL_FCFS * \n");
printf(" * 2.MUL_SJF * \n");
printf(" * 3.MUL_HRRF * \n");
printf(" * 0.EXIT * \n");
printf("请输入你的选择:");
scanf("%d",&choice);
if(choice == 0)
exit(0);
else if(choice == 1)
FCFS();
else if(choice == 2)
SJF();
else if(choice == 3)
HRRF();
else
{
printf("输入出错，请重新输入!\n");
continue;
}
printf("\n");
}while(True);
return 0;
}
测试用例：
5
100 4
1
job1 10:00 40 35 3
job2 10:10 30 70 1
job3 10:15 20 50 3
job4 10:35 10 25 2
job5 10:40 5 20 2
这是一个大致的补充之后的程序
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct data
{
int hour;
int minute;
}time;
typedef struct link_node{
char name[5];
time inTime;
time outTime;
time jobTime;
time processTime;
int zz;
float zzxs;
int workTime;
int needMemory;
int needTape;
int surplusMemory;
int surplusTape;
int finished;
int flag;
float hrrf;
struct link_node *next;
}node;
typedef node linknode;
int process,memory,tape;
time now_time;
void print_work(linknode *head){
printf("作业名 入井时间 运行时间 需要内存 需要磁带机 周转时间 带权周转时间\n");
linknode *p = head->next;
while(p != NULL){
printf("%-5s %02d:%02d %2d %2d %2d %2d %.2f\n",p->name,p->inTime.hour,p->inTime.minute,
p->workTime,p->needMemory,p->needTape,p->zz,p->zzxs);
p = p->next;
}
}
linknode *create_node(void){
linknode *p = (linknode *)malloc(sizeof(linknode));
if(p == NULL){
printf("分配内存失败！\n");
exit(0);
}
printf("请输入作业名、入井时间、运行时间、需要内存、需要磁带机数（中间用空格隔开）：");
scanf("%s %d:%d %d %d %d",p->name,&p->inTime.hour,&p->inTime.minute,&p->workTime,&p->needMemory,&p->needTape);
p->surplusMemory = memory;
p->surplusTape = tape;
p->finished = 0;
p->flag = 0;
p->next = NULL;
return p;
}
void go_ahead(int n){
now_time.minute += n;
if(now_time.minute >= 60){
now_time.hour += now_time.minute / 60;
now_time.minute %= 60;
}
}
void work_execute(linknode *head){
linknode *p = head->next;
while(p != NULL){
if(p->flag == 0 && p->needMemory <= p->surplusMemory && p->needTape <= p->surplusTape){
p->jobTime = now_time;
p->surplusMemory -= p->needMemory;
p->surplusTape -= p->needTape;
p->flag = 1;
}
p = p->next;
}
}
void process_execute(linknode *head){
linknode *p = head->next;
while(p != NULL){
if(p->flag == 1){
if(p->workTime == 0){
p->outTime = now_time;
p->zz = (p->outTime.hour*60+p->outTime.minute) - (p->inTime.hour*60+p->inTime.minute);
p->zzxs = (float)p->zz / p->workTime;
p->surplusMemory += p->needMemory;
p->surplusTape += p->needTape;
p->finished = 1;
p->flag = -1;
}
else{
p->workTime--;
go_ahead(1);
}
}
p = p->next;
}
}
void insert_FCFS(linknode *head,linknode *Node){
linknode *p = head;
while(p->next != NULL)
p = p->next;
p->next = Node;
}
linknode *input_FCFS(void){
int i;
linknode *head = (linknode *)malloc(sizeof(linknode));
head->next = NULL;
for(i = 0; i < process; i++){
linknode *p = create_node();
insert_FCFS(head,p);
}
return head;
}
void FCFS(void){
linknode *head = input_FCFS();
printf("\n调度前的作业表：\n");
print_work(head);
printf("\n调度后的作业表：\n");
while(head->next != NULL){
work_execute(head);
process_execute(head);
linknode *p = head->next;
if(p->flag == -1){
head->next = p->next;
free(p);
}
else{
head = head->next;
}
}print_work(head);
printf("\n作业调度结束！\n");
}
void insert_SJF(linknode *head,linknode *Node){
linknode *p = head;
while(p->next != NULL && Node->workTime > p->next->workTime)
p = p->next;
Node->next = p->next;
p->next = Node;
}
linknode *input_SJF(void){
int i;
linknode *head = (linknode *)malloc(sizeof(linknode));
head->next = NULL;
for(i = 0; i < process; i++){
linknode *p = create_node();
insert_SJF(head,p);
}
return head;
}
void SJF(void){
linknode *head = input_SJF();
printf("\n调度前的作业表：\n");
print_work(head);
printf("\n调度后的作业表：\n");
while(head->next != NULL){
work_execute(head);
process_execute(head);
linknode *p = head->next;
if(p->flag == -1){
head->next = p->next;
free(p);
}
else{
head = head->next;
}
}
printf("\n作业调度结束！\n");
}
linknode * sort_HRRF(linknode *head){
linknode *p = head;
while(p->next != NULL && p->next->flag != 0)
p = p->next;
if(p->next == NULL)
return NULL;
linknode *maxp = p->next;
float maxhrrf = (now_time.hour * 60 + now_time.minute - maxp->inTime.hour * 60 - maxp->inTime.minute + maxp->workTime) / (float)maxp->workTime;
while(p->next != NULL){
if(p->next->flag == 0){
float hrrf = (now_time.hour*60+now_time.minute-p->next->inTime.hour*60-p->next->inTime.minute+p->next->workTime) / (float)p->next->workTime;
if(hrrf > maxhrrf){
maxp = p->next;
maxhrrf = hrrf;
}
}
p = p->next;
}
return maxp;
}
void HRRF_execute(linknode *head){
linknode *p = sort_HRRF(head);
if(p != NULL){
p->jobTime = now_time;
p->surplusMemory -= p->needMemory;
p->surplusTape -= p->needTape;
p->flag = 1;
}
process_execute(head);
}
void HRRF(void){
linknode *head = input_SJF();
printf("\n调度前的作业表：\n");
print_work(head);
printf("\n调度后的作业表：\n");
while(head->next != NULL){
work_execute(head);
HRRF_execute(head);
linknode *p = head->next;
if(p->flag == -1){
head->next = p->next;
free(p);
}
else{
head = head->next;
}
}
printf("\n作业调度结束！\n");
}
int main()
{
int choice;
printf("请输入你要创建的进程数:");
scanf("%d",&process);
printf("请输入主存大小和磁带机总数:");
scanf("%d %d",&memory,&tape);
do{
printf("******************调度算法******************\n");
printf(" * 1.MUL_FCFS * \n");
printf(" * 2.MUL_SJF * \n");
printf(" * 3.MUL_HRRF * \n");
printf(" * 0.EXIT * \n");
printf("请输入你的选择:");
scanf("%d",&choice);
if(choice == 0)
exit(0);
else if(choice == 1)
FCFS();
else if(choice == 2)
SJF();
else if(choice == 3)
HRRF();
else
{
printf("输入出错，请重新输入!\n");
continue;
}
printf("\n");
}while(1);
return 0;
}
- 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7525069
- 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：图的单源最短路径算法
- 除此之外, 这篇博客: 位段的含义与使用方法中的 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
位段是一种与结构体的定义方法相似，与结构体使用方法略有不同的自定义类型。
例：
struct A { int _a:2; int _b:5; int _c:10; int _d:30; };如上图所示，位段的定义分为4个部分，分别是 位段名（A），成员类型（int)，成员名(_a,_b，_c...),各成员使用空间的大小（2，5，10，30）。
2.1 内存开辟方式：
struct S { char a:3; char b:4; char c:5; char d:4; };如图所示，当计算机为位段成员创建空间时，需要根据成员类型和成员所需空间大小来分配相对应的内存空间.
由于成员类型是char类型，因此计算机每次为成员创建1个字节（8bit)空间。
由于a成员需要3个bit空间，b成员需要4个bit空间，因此a与b成员共需要7个bit空间，此时不需要分配新的内存空间（从右向左使用空间的情况）
c成员需要5个bit空间，目前开辟的空间只剩1个bit，因此需要创建新的空间，将c放在新的空间中，之前剩余的1个bit空间不予使用
对于d成员同理
综上，此位段共开辟了3个字节空间。
2.2 使用方法
struct S { char a : 3; char b : 4; char c : 5; char d : 4; }; int main() { //创建位段变量s struct S s = { 0 }; //为位段成员赋值 s.a = 10; s.b = 12; s.c = 3; s.d = 4; printf("%d\n%d\n%d\n%d", s.a,s.b,s.c,s.d); return 0; }2.2.1创建位段变量s
2.2.2为位段成员赋值
由于s.a只能使用3个bit空间，而10的二进制编码是1010，因此存入s.a的值是010，其十进 制数为2。
s.b可以使用4个bit空间，12的二进制编码为1100，存入s.b的值为1100，其最高位1为符号位，因此其十进制数为-4。
s.c可以使用5个bit空间，3的二进制编码为11，存入s.c的值为11，由于s.c占5个bit空间,需要在高位补齐，补齐后为00011，因此其十进制数为3。
s.d可以使用4个bit空间，4的二进制编码为100，存入s.c的值为100，由于s.c占4个bit空间,需要在高位补齐，补齐后为0100，因此其十进制数为4。
运行结果：
- 您还可以看一下 孙玖祥老师的图解数据结构与算法课程中的 红黑树的右旋原理小节, 巩固相关知识点