- 技术
- 操作系统实验——作业调度算法模拟
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXJOB 50
typedef struct node
{
int number
;
int reach_time
;
int need_time
;
int privilege
;
float excellent
;
int start_time
;
int wait_time
;
int visited
;
}job
;
job jobs
[MAXJOB
];
int quantity
;
void initial_jobs()
{
int i
;
for (i
= 0; i
< MAXJOB
; i
++)
{
jobs
[i
].number
= 0;
jobs
[i
].reach_time
= 0;
jobs
[i
].privilege
= 0;
jobs
[i
].excellent
= 0;
jobs
[i
].start_time
= 0;
jobs
[i
].wait_time
= 0;
jobs
[i
].visited
= 0;
}
quantity
= 0;
}
void readJobdata()
{
FILE
*fp
;
char fname
[20];
int i
;
printf("please input job data file name\n");
scanf("%s", fname
);
if ((fp
= fopen(fname
, "r")) == NULL)
{
printf("error, open file failed, please check filename:\n");
}
else
{
while (!feof(fp
))
{
if (fscanf(fp
, "%d %d %d %d", &jobs
[quantity
].number
, &jobs
[quantity
].reach_time
, &jobs
[quantity
].need_time
, &jobs
[quantity
].privilege
) == 4)
quantity
++;
}
printf("output the origin job data\n");
printf("---------------------------------------------------------------------\n");
printf("\tjobID\treachtime\tneedtime\tprivilege\n");
for (i
= 0; i
< quantity
; i
++)
{
printf("\t%-8d\t%-8d\t%-8d\t%-8d\n", jobs
[i
].number
, jobs
[i
].reach_time
, jobs
[i
].need_time
, jobs
[i
].privilege
);
}
}
}
void reset_jinfo()
{
int i
;
for (i
= 0; i
< MAXJOB
; i
++)
{
jobs
[i
].start_time
= 0;
jobs
[i
].wait_time
= 0;
jobs
[i
].visited
= 0;
}
}
int findrearlyjob(job jobs
[], int count
)
{
int rearlyloc
= -1;
int rearlyjob
= -1;
for (int i
= 0; i
< count
; i
++)
{
if (rearlyloc
== -1)
{
if (jobs
[i
].visited
== 0)
{
rearlyloc
= i
;
rearlyjob
= jobs
[i
].reach_time
;
}
}
else if (rearlyjob
> jobs
[i
].reach_time
&&jobs
[i
].visited
== 0)
{
rearlyjob
= jobs
[i
].reach_time
;
rearlyloc
= i
;
}
}
return rearlyloc
;
}
int findminjob(job jobs
[], int count
, int current_time
)
{
int minjob
= -1;
int minloc
= -1;
for (int i
= 0; i
< count
; i
++)
{
if (minloc
== -1)
{
if (jobs
[i
].reach_time
<= current_time
&& jobs
[i
].visited
== 0)
{
minjob
= jobs
[i
].need_time
;
minloc
= i
;
}
}
else if (minjob
> jobs
[i
].need_time
&&jobs
[i
].visited
== 0 && jobs
[i
].reach_time
<= current_time
)
{
minjob
= jobs
[i
].need_time
;
minloc
= i
;
}
else if (minjob
== jobs
[i
].need_time
&&jobs
[i
].visited
== 0 && jobs
[i
].reach_time
<= current_time
&& jobs
[minloc
].reach_time
> jobs
[i
].reach_time
)
{
minloc
= i
;
}
}
if (minloc
== -1)
minloc
= findrearlyjob(jobs
, quantity
);
return minloc
;
}
int findhighprivilegejob(job jobs
[], int count
, int current_time
)
{
int t
;
int privilegejob
= -1;
int privilegeloc
= -1;
int privilege
= -1;
for (int i
= 0; i
< count
; i
++)
{
if (privilegeloc
== -1)
{
if (jobs
[i
].reach_time
<= current_time
&& jobs
[i
].visited
== 0)
{
privilege
= jobs
[i
].privilege
;
privilegejob
= jobs
[i
].need_time
;
privilegeloc
= i
;
}
}
else if (privilege
< jobs
[i
].privilege
&&jobs
[i
].visited
== 0 && jobs
[i
].reach_time
<= current_time
)
{
privilege
= jobs
[i
].privilege
;
privilegejob
= jobs
[i
].need_time
;
privilegeloc
= i
;
}
else if (privilege
== jobs
[i
].privilege
&&jobs
[i
].visited
== 0 && jobs
[i
].reach_time
<= current_time
&& privilegejob
> jobs
[i
].need_time
)
{
privilegejob
= jobs
[i
].need_time
;
privilegeloc
= i
;
}
}
if (privilegeloc
== -1)
privilegeloc
= findrearlyjob(jobs
, quantity
);
return privilegeloc
;
}
int findhrrfjob(job jobs
[], int count
, int current_time
)
{
int hrrfjob
= -1;
int hrrfloc
= -1;
float responsejob
= -1.0;
for (int i
= 0; i
< count
; i
++)
{
if (hrrfloc
== -1)
{
if (jobs
[i
].reach_time
<= current_time
&& jobs
[i
].visited
== 0)
{
hrrfjob
= jobs
[i
].need_time
;
responsejob
= (float)(current_time
- jobs
[i
].reach_time
+ jobs
[i
].need_time
) / jobs
[i
].need_time
;
hrrfloc
= i
;
}
}
else if (responsejob
< ((float)(current_time
- jobs
[i
].reach_time
+ jobs
[i
].need_time
) / jobs
[i
].need_time
)&&jobs
[i
].visited
== 0 && jobs
[i
].reach_time
<= current_time
)
{
responsejob
= (float)(current_time
- jobs
[i
].reach_time
+ jobs
[i
].need_time
) / jobs
[i
].need_time
;
hrrfjob
= jobs
[i
].need_time
;
hrrfloc
= i
;
}
else if (responsejob
== ((float)(current_time
- jobs
[i
].reach_time
+ jobs
[i
].need_time
) / jobs
[i
].need_time
) &&jobs
[i
].visited
== 0 && jobs
[i
].reach_time
<= current_time
&& hrrfjob
> jobs
[i
].need_time
)
{
hrrfjob
= jobs
[i
].need_time
;
hrrfloc
= i
;
}
}
if (hrrfloc
== -1)
hrrfloc
= findrearlyjob(jobs
, quantity
);
return hrrfloc
;
}
void FCFS()
{
int i
;
int current_time
= 0;
int loc
;
int total_waitime
= 0;
int total_roundtime
= 0;
loc
= findrearlyjob(jobs
, quantity
);
printf("\n\nFCFS算法作业流\n");
printf("------------------------------------------------------------------------\n");
printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
current_time
= jobs
[loc
].reach_time
;
for (i
= 0; i
< quantity
; i
++)
{
if (jobs
[loc
].reach_time
> current_time
)
{
jobs
[loc
].start_time
= jobs
[loc
].reach_time
;
current_time
= jobs
[loc
].reach_time
;
}
else
{
jobs
[loc
].start_time
= current_time
;
}
jobs
[loc
].wait_time
= current_time
- jobs
[loc
].reach_time
;
printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n", loc
+ 1, jobs
[loc
].reach_time
, jobs
[loc
].start_time
, jobs
[loc
].wait_time
,
jobs
[loc
].wait_time
+ jobs
[loc
].need_time
);
jobs
[loc
].visited
= 1;
current_time
+= jobs
[loc
].need_time
;
total_waitime
+= jobs
[loc
].wait_time
;
total_roundtime
= total_roundtime
+ jobs
[loc
].wait_time
+ jobs
[loc
].need_time
;
loc
= findrearlyjob(jobs
, quantity
);
}
printf("总等待时间:%-8d 总周转时间:%-8d\n", total_waitime
, total_roundtime
);
printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n", (float)total_waitime
/ (quantity
), (float)total_roundtime
/ (quantity
));
}
void SFJschdulejob(job jobs
[], int count
)
{
int i
;
int current_time
= 0;
int loc
;
int total_waitime
= 0;
int total_roundtime
= 0;
loc
= findrearlyjob(jobs
, quantity
);
printf("\n\nSFJ算法作业流\n");
printf("------------------------------------------------------------------------\n");
printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
current_time
= jobs
[loc
].reach_time
;
jobs
[loc
].start_time
= jobs
[loc
].reach_time
;
jobs
[loc
].wait_time
= 0;
printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n", loc
+ 1, jobs
[loc
].reach_time
, jobs
[loc
].start_time
, jobs
[loc
].wait_time
,jobs
[loc
].wait_time
+ jobs
[loc
].need_time
);
jobs
[loc
].visited
= 1;
current_time
+= jobs
[loc
].need_time
;
total_waitime
= 0;
total_roundtime
= jobs
[loc
].need_time
;
loc
= findminjob(jobs
, quantity
, current_time
);
for (i
= 1; i
< quantity
; i
++)
{
if (jobs
[loc
].reach_time
> current_time
)
{
jobs
[loc
].start_time
= jobs
[loc
].reach_time
;
current_time
= jobs
[loc
].reach_time
;
}
else
{
jobs
[loc
].start_time
= current_time
;
}
jobs
[loc
].wait_time
= current_time
- jobs
[loc
].reach_time
;
printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n", loc
+ 1, jobs
[loc
].reach_time
, jobs
[loc
].start_time
, jobs
[loc
].wait_time
,
jobs
[loc
].wait_time
+ jobs
[loc
].need_time
);
jobs
[loc
].visited
= 1;
current_time
+= jobs
[loc
].need_time
;
total_waitime
+= jobs
[loc
].wait_time
;
total_roundtime
= total_roundtime
+ jobs
[loc
].wait_time
+ jobs
[loc
].need_time
;
loc
= findminjob(jobs
, quantity
, current_time
);
}
printf("总等待时间:%-8d 总周转时间:%-8d\n", total_waitime
, total_roundtime
);
printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n", (float)total_waitime
/ (quantity
), (float)total_roundtime
/ (quantity
));
}
void HPF(job jobs
[], int count
)
{
int i
;
int current_time
= 0;
int loc
;
int total_waitime
= 0;
int total_roundtime
= 0;
loc
= findrearlyjob(jobs
, quantity
);
printf("\n\nHPF算法作业流\n");
printf("------------------------------------------------------------------------\n");
printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
current_time
= jobs
[loc
].reach_time
;
jobs
[loc
].start_time
= jobs
[loc
].reach_time
;
jobs
[loc
].wait_time
= 0;
printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n", loc
+ 1, jobs
[loc
].reach_time
, jobs
[loc
].start_time
, jobs
[loc
].wait_time
, jobs
[loc
].wait_time
+ jobs
[loc
].need_time
);
jobs
[loc
].visited
= 1;
current_time
+= jobs
[loc
].need_time
;
total_waitime
= 0;
total_roundtime
= jobs
[loc
].need_time
;
loc
= findhighprivilegejob(jobs
, quantity
, current_time
);
for (i
= 1; i
< quantity
; i
++)
{
if (jobs
[loc
].reach_time
> current_time
)
{
jobs
[loc
].start_time
= jobs
[loc
].reach_time
;
current_time
= jobs
[loc
].reach_time
;
}
else
{
jobs
[loc
].start_time
= current_time
;
}
jobs
[loc
].wait_time
= current_time
- jobs
[loc
].reach_time
;
printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n", loc
+ 1, jobs
[loc
].reach_time
, jobs
[loc
].start_time
, jobs
[loc
].wait_time
,
jobs
[loc
].wait_time
+ jobs
[loc
].need_time
);
jobs
[loc
].visited
= 1;
current_time
+= jobs
[loc
].need_time
;
total_waitime
+= jobs
[loc
].wait_time
;
total_roundtime
= total_roundtime
+ jobs
[loc
].wait_time
+ jobs
[loc
].need_time
;
loc
= findhighprivilegejob(jobs
, quantity
, current_time
);
}
printf("总等待时间:%-8d 总周转时间:%-8d\n", total_waitime
, total_roundtime
);
printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n", (float)total_waitime
/ (quantity
), (float)total_roundtime
/ (quantity
));
}
void HRRF(job jobs
[], int count
)
{
int i
;
int current_time
= 0;
int loc
;
int total_waitime
= 0;
int total_roundtime
= 0;
loc
= findrearlyjob(jobs
, quantity
);
printf("\n\nHRRF算法作业流\n");
printf("------------------------------------------------------------------------\n");
printf("\tjobID\treachtime\tstarttime\twaittime\troundtime\n");
current_time
= jobs
[loc
].reach_time
;
jobs
[loc
].start_time
= jobs
[loc
].reach_time
;
jobs
[loc
].wait_time
= 0;
printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n", loc
+ 1, jobs
[loc
].reach_time
, jobs
[loc
].start_time
, jobs
[loc
].wait_time
, jobs
[loc
].wait_time
+ jobs
[loc
].need_time
);
jobs
[loc
].visited
= 1;
current_time
+= jobs
[loc
].need_time
;
total_waitime
= 0;
total_roundtime
= jobs
[loc
].need_time
;
loc
= findhrrfjob(jobs
, quantity
, current_time
);
for (i
= 1; i
< quantity
; i
++)
{
if (jobs
[loc
].reach_time
> current_time
)
{
jobs
[loc
].start_time
= jobs
[loc
].reach_time
;
current_time
= jobs
[loc
].reach_time
;
}
else
{
jobs
[loc
].start_time
= current_time
;
}
jobs
[loc
].wait_time
= current_time
- jobs
[loc
].reach_time
;
printf("\t%-8d\t%-8d\t%-8d\t%-8d\t%-8d\n", loc
+ 1, jobs
[loc
].reach_time
, jobs
[loc
].start_time
, jobs
[loc
].wait_time
,
jobs
[loc
].wait_time
+ jobs
[loc
].need_time
);
jobs
[loc
].visited
= 1;
current_time
+= jobs
[loc
].need_time
;
total_waitime
+= jobs
[loc
].wait_time
;
total_roundtime
= total_roundtime
+ jobs
[loc
].wait_time
+ jobs
[loc
].need_time
;
loc
= findhrrfjob(jobs
, quantity
, current_time
);
}
printf("总等待时间:%-8d 总周转时间:%-8d\n", total_waitime
, total_roundtime
);
printf("平均等待时间: %4.2f 平均周转时间: %4.2f\n", (float)total_waitime
/ (quantity
), (float)total_roundtime
/ (quantity
));
}
int main()
{
initial_jobs();
readJobdata();
FCFS();
reset_jinfo();
SFJschdulejob(jobs
, quantity
);
reset_jinfo();
HRRF(jobs
, quantity
);
reset_jinfo();
HPF(jobs
, quantity
);
system("pause");
return 0;
}
Processed:
0.033, SQL:
9
