短作业优先调度算法

一、实验目的

了解并掌握作业调度的功能，熟悉并掌握各种作业调度算法。

---

二、实验内容

模拟实现SJF调度。

设置作业体：作业名，作业的到达时间，服务时间，作业状态（W——等待,R——运行,F——完成），作业间的链接指针；

作业初始化：由用户输入作业名、服务时间、到达时间进行初始化，同时，初始化作业的状态为W。

显示函数：在作业调度前、调度中和调度后进行显示。

排序函数：对等待状态的作业按照调度算法排序（不同的调度算法排序方式不同），注意考虑到达时间。

调度函数：每次从等待队列队首调度已到达的适合的作业执行，状态变化。当服务结束时，状态变为F。

删除函数：撤销状态为F的作业。

---

三、实验代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_JOBS 100
#define NAME_LEN 20typedef struct Job {char name[NAME_LEN];int arrival_time;int service_time;char status;struct Job *next;int completion_time;
} Job;Job *waiting_queue = NULL;
Job *completed_jobs = NULL;
int current_time = 0;void init_job(Job *job, const char *name, int arrival_time, int service_time) {strncpy(job->name, name, NAME_LEN);job->arrival_time = arrival_time;job->service_time = service_time;job->status = 'W';job->next = NULL;job->completion_time = 0;
}void add_job(const char *name, int arrival_time, int service_time) {Job *new_job = (Job *)malloc(sizeof(Job));init_job(new_job, name, arrival_time, service_time);if (waiting_queue == NULL || waiting_queue->arrival_time >= new_job->arrival_time) {new_job->next = waiting_queue;waiting_queue = new_job;} else {Job *temp = waiting_queue;while (temp->next != NULL && temp->next->arrival_time < new_job->arrival_time) {temp = temp->next;}new_job->next = temp->next;temp->next = new_job;}
}void display_jobs() {Job *temp = waiting_queue;printf("当前时间:%d\n", current_time);while (temp != NULL) {printf("Job:%s, 状态:%c\n", temp->name, temp->status);temp = temp->next;}printf("\n");
}void schedule() {while (waiting_queue != NULL) {Job *min_job = NULL;Job *prev_min_job = NULL;Job *temp = waiting_queue;Job *prev_temp = NULL;while (temp != NULL) {if (temp->arrival_time <= current_time) {if (min_job == NULL || temp->service_time < min_job->service_time) {min_job = temp;prev_min_job = prev_temp;}}prev_temp = temp;temp = temp->next;}if (min_job == NULL) {if (waiting_queue != NULL) {current_time = waiting_queue->arrival_time;}continue;}min_job->status = 'R';printf("Job:%s在%d时刻开始\n", min_job->name, current_time);display_jobs();current_time += min_job->service_time;min_job->completion_time = current_time;min_job->status = 'F';printf("Job:%s在%d时刻结束\n", min_job->name, current_time);display_jobs();if (min_job == waiting_queue) {waiting_queue = waiting_queue->next;} else {if (prev_min_job != NULL) {prev_min_job->next = min_job->next;}}min_job->next = completed_jobs;completed_jobs = min_job;}
}void display_turnaround_times() {Job *temp = completed_jobs;printf("\n作业周转时间和带权周转时间:\n");while (temp != NULL) {int turnaround_time = temp->completion_time - temp->arrival_time;float weighted_turnaround_time = (float)turnaround_time / temp->service_time;printf("Job:%s, 完成时间:%d, 周转时间:%d, 带权周转时间:%.2f\n",temp->name, temp->completion_time, turnaround_time, weighted_turnaround_time);temp = temp->next;}
}int main() {int n, arrival_time, service_time;char name[NAME_LEN];printf("输入Job数量: ");scanf("%d", &n);for (int i = 0; i < n; i++) {printf("输入Job%d名称, 到达时间, 服务时间: ", i + 1);scanf("%s %d %d", name, &arrival_time, &service_time);add_job(name, arrival_time, service_time);}printf("\n初始运行队列:\n");display_jobs();printf("\nSJF调度开始运行...\n");schedule();printf("\n所有作业全部完成.\n");display_turnaround_times();return 0;
}

---

四、实验结果