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

news/2024/5/19 10:04:15

实验时间

2024年 4 月13日14时至16时

学时数

2

1.实验名称

实验二进程调度算法

2.实验目的

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

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

  1. 实验内容

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

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

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

  1. 实验原理或流程图

(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. 实验过程或源代码 

(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;

}

  1. 实验结论及心得

结论：截图+手写验证

(1)

。

(2)

(3)

心得：

代码不好写。


http://www.mrgr.cn/p/73804010

相关文章

Python学习1--变量和简单数据类型

Python学习1--变量和简单数据类型

本章练习&#xff1a; Python之禅&#xff1a;
阅读更多...
【实用技巧】JSON格式转换方式

【实用技巧】JSON格式转换方式

1 前言 对接开发中，常遇到的就是报文转换。比如从淘宝或者京东拉取订单，亦或是各个公司内部的WMS、OMS等交互，都涉及到格式转换。而大多的格式基本上都是 JSON 格式，当然也有一些老的 SAP 交互用的是 XML格式的，还有一小部分 webService 接口也是用的 XML 格式。那我们这…
阅读更多...
pwn知识——劫持__malloc_hook（在加入tcache以后）

pwn知识——劫持__malloc_hook（在加入tcache以后）

导论 动调是最好的导师！ malloc_hook函数解析 malloc_hook是malloc的钩子函数，在执行malloc时，会先检测__malloc_hook的值，如果malloc_hook的值存在，则执行该地址（值里边表现为十六进制，可以成为地址），也就是说，如果我们成功劫持malloc_hook以后并修改它的值为one_ga…
阅读更多...
小程序如何优化搜索排名，获取曝光

小程序如何优化搜索排名，获取曝光

在移动互联网时代&#xff0c;小程序以其便捷、轻量级的特点&#xff0c;逐渐成为用户获取服务的重要渠道。然而&#xff0c;小程序数量众多&#xff0c;如何让自己的小程序在搜索中脱颖而出&#xff0c;获取更多的曝光和流量&#xff0c;成为众多开发者关注的焦点。 一、理解…
阅读更多...
实验二——需求分析

实验二——需求分析

一、实验题目 ：需求分析 二、实验目的 1、掌握StarUML软件的安装； 2、掌握利用StarUML工具分析、设计、绘制用例图； 3、掌握利用StarUML工具分析、设计、绘制类图； 4、掌握利用StarUML工具分析、设计、绘制状态图； 5、掌握利用StarUML工具分析、设计、绘制顺序图。 6、掌…
阅读更多...
用户行为分析模型实践（四）—— 留存分析模型

用户行为分析模型实践（四）—— 留存分析模型

作者&#xff1a;vivo 互联网大数据团队- Wu Yonggang、Li Xiong 本文是vivo互联网大数据团队《用户行为分析模型实践》系列文章第4篇 -留存分析模型。 本文详细介绍了留存分析模型的概念及基本原理&#xff0c;并阐述了其在产品中具体实现。针对在实际使用过程问题&#xff0…
阅读更多...
android学习笔记（二）

android学习笔记（二）

1、自定义View。 package com.example.view; import android.content.Context; import android.graphics.Canvas; import android.graphics.Color; import android.graphics.Paint; import android.util.AttributeSet; import android.view.View; //可以在View测量和布局完成后…
阅读更多...
计算机网络：MAC地址 IP地址 ARP协议

计算机网络：MAC地址 IP地址 ARP协议

计算机网络&#xff1a;MAC地址 & IP地址 & ARP协议 MAC地址IP地址ARP协议 MAC地址 如果两台主机通过一条链路通信&#xff0c;它们不需要使用地址就可以通信&#xff0c;因为连接在信道上的主机只有他们两个。换句话说&#xff0c;使用点对点信道的数据链路层不需要使…
阅读更多...
CF1535F String Distance

CF1535F String Distance

\(CF1535F\ \ String\ Distance\) 题意 给 \(n\) 个长度均为 \(len\) 的字符串 \(T_1,T_2,\dots T_n\)，定义 \(f(a,b)\) 为将 \(a,b\) 排序后相等的最小排序次数，若无解则为 \(1337\)(这好像是个黑客用语)。求 \[\sum _{i=1}^{n}\sum _{j=i+1}^{n}f(T_i,T_j) \]其中 \[n\tim…
阅读更多...
连接mysql -- host is not allowed to connect to this mysql server的解决

连接mysql -- host is not allowed to connect to this mysql server的解决

今天通过navicat连接服务器的MySQL，报错：host is not allowed to connect to this mysql server去网上搜了一摞，有些方法不太管用，踩了点坑，在此记录下。版本：MYSQL 8.0.36， CentOS 7mysql -u root -p use mysql; select user, host from user;这时候可以看到：只允许lo…
阅读更多...
单向循环链表的初体验

单向循环链表的初体验

单向循环链表经过小白今天一天的学习，感觉就是在单向链表的尾结点加了一个首结点的地址，不再指向NULL，个人理解就像一群孩子围成了一个圆，头尾相连，同时多少个孩子就是多少个结点，如击鼓传花一般一个个将手上的手绢传递给下一个人，一遍下来就像是单向循环的遍历，想要到…
阅读更多...
Modbus转Profinet网关接称重设备与工控机通讯

Modbus转Profinet网关接称重设备与工控机通讯

Modbus转Profinet网关（XD-MDPN100）是一种能够实现Modbus协议和Profinet协议之间转换的设备。Modbus转Profinet网关可提供单个或多个RS485接口，使得不同设备之间可以顺利进行通信，进一步提升了工业自动化程度。Modbus转Profinet网关接称重设备与工控机通讯Modbus转Profinet网…
阅读更多...
逆向修改app就可以游戏充值到账？

逆向修改app就可以游戏充值到账？

hello ，大家好， 现在市场仍然流行着非常多的传奇类游戏私服或者其他类型的游戏私服，随着私服越来越多（很多并不合法），越来越多的人加入了破解，逆向修改，或者代充的队伍并从中获利。这里我给大家分享一下这些做代充的常规的做法，以及大家作为游戏服务器如何避坑做强校验…
阅读更多...
Linux之安装Nginx

Linux之安装Nginx

目录 传送门前言一、快速安装二、反向代理语法1、基本语法2、location语法1. 基本语法2. 匹配规则3. 修饰符4. 权重5. 嵌套location6. 其他指令7.案例 三、配置反向代理 传送门 SpringMVC的源码解析&#xff08;精品&#xff09; Spring6的源码解析&#xff08;精品&#xff0…
阅读更多...
构建Python中的分布式日志系统：ELK与Fluentd的结合

构建Python中的分布式日志系统：ELK与Fluentd的结合

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 在现代软件开发中&#xff0c;日志系统是至关重要的组成部分。它们不仅用于故障排查和性能监…
阅读更多...
Linux问题集合

Linux问题集合

Linux问题集合 1. Linux下如何定位死锁？ 如果你想排查你的 Java 程序是否死锁，则可以使用 jstack 工具，它是 jdk 自带的线程堆栈分析工具。 在 Linux 下，我们可以使用 pstack + gdb 工具来定位死锁问题。 pstack 命令可以显示每个线程的栈跟踪信息（函数调用过程），它的使…
阅读更多...
2023中国企业敏捷实践白皮书发布，免费下载

2023中国企业敏捷实践白皮书发布，免费下载

在人工智能技术飞速发展，组织面临的复杂性和多变性不断加剧的背景下，《2023中国企业敏捷实践白皮书》通过广泛的调查，洞察剧变之下，谁在逆流而上，如何逆流而上。《2023中国企业敏捷实践白皮书》发布！免费下载在人工智能技术飞速发展，组织面临的复杂性和多变性不断加剧的…
阅读更多...
解决多线程竞争条件——临界区

解决多线程竞争条件——临界区

如图所示，黑色表示没有获得CPU，绿色表示获得CPU，假设为单核两线程程情况。 线程1开始运行，并进入临界区，在出临界区运行过程中到了上下文切换时间。 线程2获得CPU，正常运行一段时间后需要运行至临界区代码，此时，线程1位于临界区。因为不能两个线程同时位于临界区，所以…
阅读更多...
python爬虫—学习笔记-4

python爬虫—学习笔记-4

课堂内容：删除原导出文件的venv，pycham打开此文夹，重新创建本地虚拟编译器。安装依赖库，打开pycham终端输入pip install -r yilaiku.txt,安装依赖库中的库。继续安装bs4、lxml库，命令为：pip install bs4 和 pip install lxml。安装好后，pycham来到spiders目录下，新建Py…
阅读更多...
【Hadoop】-Hive初体验[13]

【Hadoop】-Hive初体验[13]

Hive体验 预先确保已经完成部署Hive&#xff0c;并启动了Metastore服务 可以执行&#xff1a;bin/hive&#xff0c;进入到Hive Shell环境中&#xff0c;可以直接执行SQL语句。 创建表 create table test(id int,name string,gender string); 插入数据 INSERT INTO test val…
阅读更多...
推荐文章

Copyright @ 2022~2023