中北大学软件学院操作系统实验二进程调度算法

实验时间

2024年 4 月13日14时至16时

学时数

1.实验名称

实验二进程调度算法

2.实验目的

(1)加深对进程的概念及进程调度算法的理解；

(2)在了解和掌握进程调度算法的基础上，编制进程调度算法通用程序，将调试结果显示在计算机屏幕上，并检测机算和笔算的一致性。

实验内容

(1)编程实现先来先服务调度算法。

(2)编程实现最短作业优先调度算法。

(3)编程实现最高响应比优先调度算法。

实验原理或流程图

(1)先来先服务(first come first server,FCFS)调度算法是最简单的调度算法，典型调度算法该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它会优先考虑在系统中等待时间最长的作业，而不管该作业执行时间的长短。FCFS调度算法会从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，并为它们分配资源和创建进程；最后，把它们放入就绪队列。当在进程调度中采用FCFS调度算法时，每次调度都是从就绪的进程队列中选择一个最先进入该队列的进程，并为之分配处理机，使之投入运行。在该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才会将处理机分配给其他进程。

(2)由于在实际情况中，短作业(进程)占有很大比例，为了使它们能比长作业优先执行，产生了短作业优先(short job first,SJF)调度算法。SJF调度算法是以作业的长短来计算优先级的，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF调度算法可以分别用于作业调度和进程调度。当把SJF调度算法用于作业调度时，它将从外存的作业后备队列中选择估计运行时间最短的作业，并优先将它调入内存运行。当SJF调度算法用于进程调度时，它将从就绪队列中选择估计运行时间最短的进程，并为之分配CPU运行。

(3)高响应比优先(highest response ratio next,HRRN)调度算法是优先级调度算法的一个特例，通常用于作业调度。在批处理系统中，FCFS调度算法所考虑的只是作业的等待时间，而忽视了作业的运行时间。而SJF调度算法正好相反，其只考虑了作业的运行时间，而忽视了作业的等待时间。HRRN调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间，因此其既照顾了短作业，又不会致使长作业的等待时间过长，从而改善了处理机调度的性能。

实验过程或源代码

(1)C语言编写

#include <iostream>

#include <string.h>

#include <iomanip>

struct job {

char name[10];      //作业的名字

int starttime;      //作业到达系统时间

int needtime;       //作业服务时间

int runtime;        //作业周转时间

int endtime;        //作业结束时间

int flag = 0;         //作业完成标志

char state = 'W'; //作业状态，一开始都默认为就绪

double dqzz_time;    //带权周转时间

};

void fcfs(struct job jobs[50], int n) {

int i = 0, j = 0, sum = 1;

char t_name[10];

int t_time;

for (i = 0; i < n; i++) { //按作业到达系统时间进行排序，最早到达的排在最前面

for (j = i; j < n; j++) { //按作业到达系统时间进行排序，最早到达的排在最前面

if (jobs[j].starttime < jobs[i].starttime) {

//把到达时间早的赋值到t_time

t_time = jobs[j].starttime;

jobs[j].starttime = jobs[i].starttime;

jobs[i].starttime = t_time;

//把到达时间早的赋值到t_time

t_time = jobs[j].needtime;

jobs[j].needtime = jobs[i].needtime;

jobs[i].needtime = t_time;

strcpy(t_name, jobs[j].name);

strcpy(jobs[j].name, jobs[i].name);

strcpy(jobs[i].name, t_name); //在t_name数组中排序

}

}

}

int nowtime = 0; //系统时间

for (i = 0; i < n; i++) {

if (nowtime < jobs[i].starttime) {

nowtime = jobs[i].starttime;

}

jobs[i].state = 'R';

jobs[i].endtime = nowtime + jobs[i].needtime;

jobs[i].runtime = jobs[i].endtime - jobs[i].starttime;

jobs[i].dqzz_time = double(jobs[i].runtime) / jobs[i].needtime;

nowtime = jobs[i].endtime;

jobs[i].state = 'F';

}

}

void print(struct job jobs[50], int n) {

int i;

double avertime;

double dqzz_avertime;

int sum_runtime = 0;

double sum_time = 0.00;

printf("作业名到达时间运行时间完成时间周转时间带权周转时间\n");

for (i = 0; i < n; i++) {

printf("%s       %2d        %2d       %2d        %2d        %.2f\n", jobs[i].name, jobs[i].starttime, jobs[i].needtime,

       jobs[i].endtime, jobs[i].runtime, jobs[i].dqzz_time);

sum_runtime = sum_runtime + jobs[i].runtime;

sum_time = sum_time + jobs[i].dqzz_time;

}

avertime = sum_runtime * 1.0 / n;

dqzz_avertime = sum_time * 1.000 / n;

printf("平均周转时间:%.2f \n", avertime);

printf("平均带权周转时间:%.3f \n", dqzz_avertime);

printf("\n");

}

int main() {

struct job jobs[50];

int n, i; //n个作业

printf("请输入作业个数:");

scanf("%d", &n);

printf("请输入各作业的信息(格式：作业名到达时间服务时间)：\n");

for (i = 0; i < n; i++) {

scanf("%s", jobs[i].name); //作业名

scanf("%d", &jobs[i].starttime); //到达时间

scanf("%d", &jobs[i].needtime); //运行（服务时间）时间

}

printf("\n");

fcfs(jobs, n);

printf("先来先服务(FCFS)调度算法运行结果：\n");

print(jobs, n);

}

(2)

#include <stdio.h>

#include <string.h>

struct job {

int id;

int starttime;//作业到达系统的时间

int needtime;//作业服务的时间

int endtime;//作业的结束时间

int runtime;//作业周转的时间

double dqzztime;//作业的带权周转时间

};

main() {

struct job job[50];

int n, i; //n个作业

printf("输入作业的个数\n");

scanf("%d", &n);

printf("输入每个作业的id，到达时间，服务时间\n");

for (i = 0; i < n; i++) {

scanf("%d%d%d", &job[i].id, &job[i].starttime, &job[i].needtime);

}

printf("\n");

int b = 0;

int temp;

int min;

for (i = 0; i < n - 1; i++) { //按作业到达系统时间进行排序，最早到达的排在最前面

if (job[i].starttime > job[i + 1].starttime) { //把到达时间晚的赋值到min

min = job[i].starttime;

job[i].starttime = job[i + 1].starttime;

job[i + 1].starttime = min;

//把到达时间晚的赋值到min

min = job[i].needtime;

job[i].needtime = job[i + 1].needtime;

job[i + 1].needtime = min;

temp = job[i].id;

job[i].id = job[i + 1].id;

job[i + 1].id = temp; //在temp数组中排序

}

}

job[0].endtime = job[0].starttime + job[0].needtime; //结束时间=到达时间+服务时间

job[0].runtime = job[0].needtime; //周转时间=服务时间

job[0].dqzztime = job[0].runtime * 1.0 / job[0].needtime; //带权周转时间=周转时间/服务时间

for (i = 1; i < n; i++) {

if (job[i].starttime > job[i - 1].endtime) { //第i个进程到达系统时，第i-1个进程已运行完毕

job[i].endtime = job[i].starttime + job[i].needtime;

job[i].runtime = job[i].needtime;

} else {

b = 0; //要排序的作业的个数

if (job[i].starttime < job[i - 1].endtime) {

for (int j = i; j < n; j++) {

if (job[j].starttime < job[i - 1].endtime) {

b = b + 1;

}

}

for (int j = i; j < b - 1 + i; j++) {

int mins = job[j].needtime;

int w = j; //最小的作业时间的标志

for (int z = j; z < b - 1 + i; z++) {

if (mins > job[z + 1].needtime) {

mins = job[z + 1].needtime;

w = z + 1;

}

}

min = job[j].starttime;

job[j].starttime = job[w].starttime;

job[w].starttime = min;

min = job[j].needtime;

job[j].needtime = job[w].needtime;

job[w].needtime = min;

temp = job[j].id; //将第二个参数的值复制给第一个参数，返回第一个参数

job[j].id = job[w].id;

job[w].id = temp;

//按最短运行时间排序

}

}

job[i].endtime = job[i - 1].endtime + job[i].needtime;

job[i].runtime = job[i].endtime - job[i].starttime;

}

job[i].dqzztime = job[i].runtime * 1.0 / job[i].needtime;

}

printf("作业名   到达时间   运行时间   完成时间   周转时间   带权周转时间\n");

for (i = 0; i < n; i++) {

printf(" %d\t     %d\t       %d\t %d\t      %d            %.2f\n",

       job[i].id, job[i].starttime, job[i].needtime, job[i].endtime, job[i].runtime, job[i].dqzztime);

}

}

(3)

#include <stdio.h>

#include <stdlib.h>

//每运行完一次就要计算一次等待时间和响应比=(等待+服务)/服务

//进程结构体

struct pcb {

char name[10];   //进程名

int atime;      //到达时间

int rtime;    //运行时间

int stime; //开始时间

int ftime;      //完成时间

int ttime;      //周转时间

double wtime;    //带权周转时间

double rp; //响应比

int state; //执行状态 1表示已经执行

};

//输入模块

void input(struct pcb *p, int n) {

for (int i = 0; i < n; i++) {

scanf("%s", p[i].name, sizeof(p[i]));

}

for (int i = 0; i < n; i++) {

scanf("%d", &p[i].atime);

}

for (int i = 0; i < n; i++) {

scanf("%d", &p[i].rtime);

}

}

//输出模块

void output(struct pcb *p, int n) {

printf("作业名：");

for (int i = 0; i < n; i++) {

if (i == n - 1) {

printf("%s", p[n - 1].name);

printf("\n");

} else {

printf("%s ", p[i].name);

}

}

printf("到达时间：");

for (int i = 0; i < n; i++) {

if (i == n - 1) {

printf("%d", p[n - 1].atime);

printf("\n");

} else {

printf("%d ", p[i].atime);

}

}

printf("服务时间：");

for (int i = 0; i < n; i++) {

if (i == n - 1) { //最后一行要加回车这样做其实不方便

printf("%d", p[n - 1].rtime);

printf("\n");

} else {

printf("%d ", p[i].rtime);

}

}

printf("完成时间：");

for (int i = 0; i < n; i++) {

if (i == n - 1) {

printf("%d", p[n - 1].ftime);

printf("\n");

} else {

printf("%d ", p[i].ftime);

}

}

printf("周转时间：");

for (int i = 0; i < n; i++) {

if (i == n - 1) {

printf("%d", p[n - 1].ttime);

printf("\n");

} else {

printf("%d ", p[i].ttime);

}

}

printf("带权周转时间：");

for (int i = 0; i < n; i++) {

if (i == n - 1) {

printf("%.2f", p[n - 1].wtime);

printf("\n");

} else {

printf("%.2f ", p[i].wtime);

}

}

}

//atime升序

void sort(struct pcb *p, int n) {

for (int i = 0; i < n - 1; i++) {

struct pcb temp;

for (int j = 0; j < n - i - 1; j++) {

if (p[j].atime > p[j + 1].atime) {

temp = p[j];

p[j] = p[j + 1];

p[j + 1] = temp;

}

}

}

}

void hrrf(struct pcb *p, int n) {

int finishedcount = 0;   //记录已经完成的进程数

int unfinishedposition = 0; //记录未完成进程的位置

double nowtime = 0;      //现在时间

for (int i = 0; i < n; i++) {

p[i].state = 0;

}

while (finishedcount < n) {

double max_rp = 0; //中间变量比较响应比

int next = 0;        //记录下一个要运行的位置下标

//扫描找出有max响应比的进程下标

for (int i = unfinishedposition; (i < n && p[i].atime <= nowtime && i != 0); i++) {

if (p[i].state == 1) {

continue;

}

if (p[i].rp > max_rp) { //扫描对比rp

max_rp = p[i].rp;

next = i; //记录下一个要执行进程下标

}

}

if (nowtime < p[unfinishedposition].atime * 1.0) { //考虑到达的进程都运行完了, 有些进程还没到达的情况

nowtime = p[unfinishedposition].atime * 1.0;

next = unfinishedposition;

}

//运行阶段

{

nowtime = nowtime + p[next].rtime; //更新现在时间

p[next].state = 1; //记录运行状态

p[next].ftime = nowtime;       //完成时间=现在时间

p[next].ttime = nowtime - p[next].atime; //周转=现在时间-到达

p[next].wtime = 1.0 * p[next].ttime / p[next].rtime; //带权周转=周转/运行

for (int i = unfinishedposition; i < n; i++) { //指向下一个未运行的进程

if (p[i].state == 0) {

unfinishedposition = i;

break;

}

}

finishedcount++; //运行完成的个数

}

//循环计算rp,响应比=(现在时间+运行时间-到达时间)/运行时间

for (int i = 0; i < n && (p[i].atime <= nowtime); i++) {

if (p[i].state == 1) { //已经完成的就不要算响应比了

continue;

} else {

p[i].rp = (nowtime + p[i].rtime - p[i].atime) / p[i].rtime;

}

}

}

}

int main() {

int n;              //进程数量

scanf("%d", &n);

struct pcb p[333];

input(p, n);

sort(p, n);

hrrf(p, n);

output(p, n);

return 0;

}