-
2019-06-15 22:09:05
操作系统算法模拟实例之单处理机系统进程调度
1.实验目的
在多道程序或多任务系统中,系统回时处于就绪态的进程有若干个,为使系统中
的各进程能有条不素地运行,必须选择某种调度策略,以选择一进程占用处理机。
要求学生设计一个模拟单处理机调度算法,以巩固和加探对进念和进程调度算法的理解。2.实验内容
编写程序完成单处理机系统中的进程调度,要求采用最高优先级优先调度算法。具体内容包括
- 确定进程控制块的内容和组织方式;
- 完成进程创建原语和进调度原语:
- 编写主函数井对所做的工作进行测试
3.实验指导
进程调度算法:
采用最高优先级优先调度算法(即把处理机分配给优先级最高的进程)和先来先服务调度算法,每个进程用一个进程控制块(PCB)表示,进程控制块可以包含以下信息:进程名、优先数、到达时间、需要运行时间、已用CPU时间,进程状态等。进程的优先数(表示优先级别)及需要的运行时间可以事先人为描定(也可以随机数产生),进程的到达时间为进程输入的时间。进程的运行时间以时间片为单位。
每个进程的状态可以是就绪W(Wait),运行R(Run)或完成F( Finish)三种状态之就绪进程获得CPU后都只能运行一个时间片,用已占用CPU时间加1来表示,如果运行一个时间片后,进程的已占用CPU时间已达到所需要的运行时间,则激销该进程,如果运行一个时间片后进程的已占用CPU时间还未达到所需要的运行时间,也就是进程还需要继续运行,此时应将进程的优先数减1(即降低一级),然后把它插入就绪队列等待CPU。
每进行一次,调度程序都打印一次运行进程,就绪队列以及各个进程的PCB,以假进
行检查。重复以上过程,直到所有进程都完成为止。4.程序实例
#include"stdio.h" #include <stdlib.h> #include <conio.h> #define getpch(type)(type *)malloc(sizeof(type)) struct pcb //定义进程控制块 { char name[10]; char state; int super; int ntime; int rtime; struct pcb* link; }*ready=NULL,*p; typedef struct pcb PCB; int sort() //建立对进程进行优先级排列的函数 { PCB *first,*second; int insert = 0; //优先级最大者,插入队首 if((ready==NULL)||((p->super )>(ready->super ))) { p->link =ready; ready=p; } else //进程比较优先级,插入适当的位置中 { first = ready; second = first->link ; while(second != NULL) { //插入进程比当前进程优先数大、插到当前进程前面 if((p->super )>(second->super )) { p->link =second; first->link = p ; second = NULL; insert = 1; } else //插入进程优先级数最低,则插入到队尾 { first=first->link ; second=second->link ; } } if(insert==0) first->link=p; } } /* 说明:上述程序首先定义进程控制块结构,然后对每个进程的优先级赋初值,完成 优先级的排序过程,把优先级大的进程插入就绪队首,等待cup调度,该实验完成了 优先级大者优先调度的原则,从而对进程调度过程加深理解和掌握 */ int input() //建立进程控制块函数 { int i,num; system("cls"); //清屏 printf("\n请输入进程个数?"); scanf("%d",&num); for(i = 0; i < num; i++) { printf("\n进程号 No.%d:\n",i); p = getpch(PCB); printf("\n输入进程名:"); scanf("%s",p->name ); printf("\n 输入进程优先数:"); scanf("%d",&p->super ); printf("\n 输入进程运行时间:"); scanf("%d",&p->ntime ); printf("\n"); p->rtime = 0; p->state = 'w'; p->link = NULL; sort(); } } int space() { int l = 0; PCB *pr = ready; while(pr!=NULL) { l++; pr = pr->link; } return(l); } int disp(PCB *pr) { printf("\n qname\t state\t super \t ndtime \t runtime \n"); printf("|%s\t",pr->name); printf("|%c\t",pr->state); printf("|%d\t",pr->super); printf("|%d\t",pr->ntime); printf("|%d\t",pr->rtime); printf("\n"); } int check() //进程查看函数 { PCB *pr; printf("\n****当前正在运行的程序是:%s",p->name ); //显示当前运行进程 disp(p); pr=ready; printf("\n****当前就绪队列状态为:\n"); //显示就绪队列状态 while (pr!=NULL) { disp(pr); pr=pr->link; } } int destroy() //建立进程撤销函数(进程运行结束,撤销进程) { printf("\n进程{%s}已完成.\n",p->name ); free(p); } int running() //建立进程就绪函数(进程运行时间到,置就绪状态) { (p->rtime )++; if(p->rtime ==p->ntime ) destroy(); else { (p->super )--; p->state ='w'; sort(); } } int main() { int len,h = 0; char ch; input(); len = space(); while((len!=0)&&(ready != NULL)) { ch=getchar(); h++; printf("\n The execute number:%d\n",h); p=ready; ready=p->link ; p->link =NULL; p->state ='R'; check(); running(); printf("\n 按任意键继续...."); ch=getchar(); } printf("\n\n进程已经完成.\n"); ch=getchar(); }
更多相关内容 -
实现单处理机下的进程调度程序
2015-12-16 09:20:01编写一个单处理机下的进程调度程序,模拟操作系统对进程的调度。 要求: 能够创建指定数量的进程,每个进程由一个进程控制块表示。 实现先来先服务调度算法:进程到达时间可由进程创建时间表示。 实现短作业... -
计算机操作系统-进程调度-实验报告
2018-06-30 11:13:16多道程序设计中,经常是若干个进程同时处于就绪状态,必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题,加深对进程调度的理解。主要是优先权法、时间... -
操作系统 进程调度实验报告
2020-06-19 09:25:07多道程序设计中,经常是若干个进程同时处于就绪状态,必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题,加深对进程调度的理解。 二、 实验内容 1. ...题目要求
一、 实验目的
多道程序设计中,经常是若干个进程同时处于就绪状态,必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题,加深对进程调度的理解。
二、 实验内容
1. 优先权法、轮转法
简化假设
1) 进程为计算型的(无I/O)
2) 进程状态:ready、running、finish
3) 进程需要的CPU时间以时间片为单位确定
2. 算法描述
1) 优先权法——动态优先权
当前运行进程用完时间片后,其优先权减去一个常数。
2) 轮转法
三、 流程图
四、实验要求
1. 产生的各种随机数的取值范围加以限制,如所需的CPU时间限制在1~20之间。
2. 进程数n不要太大通常取4~8个
3. 使用动态数据结构
4. 独立编程
5. 两种调度算法实验报告
1.实验目的
多道程序设计中,经常是若干个进程同时处于就绪状态,必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题,加深对进程调度的理解。
2.实验内容与要求
①实验内容
1. 优先权法、轮转法
简化假设
1) 进程为计算型的(无I/O)
2) 进程状态:ready、running、finish
3) 进程需要的CPU时间以时间片为单位确定
2. 算法描述
1) 优先权法——动态优先权
当前运行进程用完时间片后,其优先权减去一个常数。
2) 轮转法②实验要求
1. 产生的各种随机数的取值范围加以限制,如所需的CPU时间限制在1~20之间。
2. 进程数n不要太大通常取4~8个
3. 使用动态数据结构
4. 独立编程
5. 两种调度算法3.流程图与模块调用
4.实验分析
想要完成操作系统算法,首先要弄清楚操作系统相关的专业术语。弄清各个算法的流程和目的要求。才能模拟出相关算法的过程。
在我的理解中,
优先权算法:
①所有线程的先后序列核心是围绕优先权的权值大小。并且该优先权的大小会动态的变化,即每随着进程被调用了一次,权值减3。所以用队列(First In First Out)这种数据结构非常好。能够有效的节省空间,算法复杂度。
②优先权算法中某个线程的结束标识是还需要的时间needTime是否变为了0。所以在随机选取线程的时候要判断该线程还需不需要资源,即needTime是否为0。
③至于状态还有一点很重要的是要即使转换。当进行下一个操作要即使转换上一个线程的状态和下一个线程的状态防止状态混淆。
轮转法
①轮转法强调先进先出的拉链式顺序,而不以其他的权值作为开始/调度的先后顺序,所以普通先进先出的普通队列是解决该算法的最好方法。
②轮转法和优先权法不一样的是优先权法每次只进一个线程只执行一次。而轮转法是进一个可以执行最多是该线程可轮转的次数/轮转值(可能在中间就完成线程的释放),所以在写程序的时候每次都要判断是否已经轮转。并且到最后还要判断还是否需要调度。如果需要,再抛入队尾。5.运行情况
①优先权算法:
②轮转法:
6.实验体会
通过本次实验,我深刻的理解了操作系统中线程资源的分配方式和进程的调度方式。操作系统实验重在理解每一个算法的意图和目的,那么就选择适当的数据结构模拟过程就可以完成相关算法了。
本次实验采用python完成,IDE是pycharm,python的queue库文件很好的支持了我在优先权算法中对队列的相关操作,python的operator库文件,很好的提供了基于类的属性按值排序的功能,这些在算法的编写过程中否起到了很大的作用。【附】实验代码
import operator import random import queue Q = queue.Queue() # 定义队列 class PCB: def __init__(self, id, status, weight, needTime, rotelTimes): self.id = id # 进程的id self.status = status # 进程状态 self.weight = weight # 进程状态优先权重 self.needTime = needTime # 进程需要的时间片 self.rotelTimes = rotelTimes # 轮转次数 def emptyQueue(Q): # 辅助函数-清空队列 while not Q.empty(): Q.get() def priority(): # 优先权算法 emptyQueue(Q) weight = operator.attrgetter('weight') arr_pcb.sort(key=weight, reverse=True) # 按照状态优先权重的值降序排列 for index,item in enumerate(arr_pcb): if item.needTime > 0: Q.put(item) # 压入队列 if index>0: if item.status!='finish': item.status='ready' node = Q.get() node.needTime -= 1 node.weight -= 3 if node.needTime>0: node.status='running' elif node.needTime==0: node.status = 'finish' print('**********时间片到达**********') for i in arr_pcb: print(i.id, i.status, i.weight, i.needTime) def rotel(): for a,item in enumerate(arr_pcb): if item.needTime>0: item.status='running' for b,item2 in enumerate(arr_pcb): if a!=b : if item2.status=='running': item2.status = 'ready' for j in range(0,item.rotelTimes): if item.needTime > 0: item.needTime-=1 if item.needTime==0: item.status='finish' print('**********开始轮转**********') for i in arr_pcb: print(i.id, i.status, i.rotelTimes, i.needTime) N = int(input('请输入需要创建的进程数目(4-8个):')) arr_pcb = [] for i in range(0, N): status = random.randint(1, 10) # 随机生成状态优先权重 needTime = random.randint(1, 4) # 随机生成需要的时间片 rotelTimes = random.randint(1, 3) # 轮转次数 arr_pcb.append(PCB(i, 'ready', status, needTime, rotelTimes)) # 创建进程 key = input('是否采用优先权?Y/N') if key == 'Y': print('**********进程初始化**********') for i in arr_pcb: print('进程:', i.id, i.status, '状态优先权重:', i.weight, '需要时间片数:', i.needTime) priority() while not Q.empty(): priority() elif key =='N': print('**********进程初始化**********') for i in arr_pcb: print('进程:', i.id, i.status, '轮转次数:', i.rotelTimes, '需要时间片数:', i.needTime) flag=0 for item in arr_pcb: if item.needTime>0: flag=1 while flag: rotel()
-
操作系统3——处理机调度(作业调度+进程调度)
2020-02-02 15:18:25操作系统3——处理机调度(作业调度+进程调度) 目录 操作系统3——处理机调度(作业调度+进程调度) 1、处理机的调度层次和目标 2、作业调度——先来先服务调度算法(FCFS) 3、作业调度——短作业优先调度...操作系统3——处理机调度(作业调度+进程调度)
目录
3、作业调度——短作业优先调度算法(SJF)short job first
3、作业调度——优先级调度算法(PSA)priority-scheduling algorithm first
5、进程调度——时间片轮转调度算法(RR—Round Robin)
1、处理机的调度层次和目标
(1)什么是处理及调度?
在多道程序环境下,进程数目通常多于处理机的数目,系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程。
(2)什么是作业?
作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合,包括用户程序、所需的数据及命令等,作业是用户提交给系统的一项相对独立的工作。
(3)什么是作业步?
每个作业会配置一个作业说明书,作业的每个步骤称为一个作业步。每个作业设置一个JCB(作业控制块)是作业唯一的符号标识,包含作业标识,用户名称,用户账号,作业类型,作业状态,调度信息等。
(4)作业状态间转换:
处理机调度的层次:
处理机调度层次
高级调度
也称作业调度或长程调度,调度对象是作业,吧后备状态的作业调入到内存
中级调度
也称中程调度,调度对象是暂时不能运行的进程,调至外存
低级调度
也称进程调度或短程调度,调度对象是进程
(5)处理机调度算法的目标:
对于处理机调度算法目标
资源利用率高(CPU利用率);
公平性;
平衡性
批处理系统目标
平均周转时间;
平均带权周转时间短;(周转时间/服务时间)
吞吐量;
处理机利用率
分时系统的目标
响应时间快;
均衡性;
实时系统目标
截止时间保证;
可预测性;
(6)进程的调度方式分类:
进程调度的任务:保存处理机的现场信息;按照某种算法选取进程;分配处理机给进程。
调度方式:
1.抢占式:当某一进程正在处理机上执行时,即使有某个更为重要或紧迫的进程进入就绪队列,该进程仍继续执行,直到其完成或发生某种事件而进入完成或阻塞状态时。
2.非抢占式:当某一进程正在处理机上执行时,若有某个更为重要或紧迫的进程进入就绪队列,则立即暂停正在执行的进程。
2、作业调度——先来先服务调度算法(FCFS)
(1)算法思想:按照作业/进程进入系统的先后次序进行调度,先进入系统者先调度,
(2)优缺点:
- 有利于长作业(进程),而不利于短作业(进程)
- 有利于CPU繁忙型作业(进程) ,而不利于I/O繁忙型作业(进程)
- 用于批处理系统
- 可用于作业调度,也可用于进程调度
(3)调度算法的评价标准
周转时间:从作业被提交给系统开始,到作业完成为止的这段时间间隔。
平均周转时间:
带权周转时间:进程(或作业)的周转时间T与系统为它提供服务的时间TS之比,即W=T/TS
(4)FCFS算法实例
3、作业调度——短作业优先调度算法(SJF)short job first
(1)算法思想:从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行。
(2)优缺点:
- 降低作业的平均等待时间,提高系统吞吐量;
- 对长作业不利,长作业长期不被调度——饥饿;
- 必须预知作业的运行时间;
- 完全未考虑作业的紧迫程度;
- 人机无法交互;
(3)SJF算法实例
3、作业调度——优先级调度算法(PSA)priority-scheduling algorithm first
算法思想:基于作业的紧迫程度,外部赋予作业优先级,调度算法根据优先级调度。
4、作业调度——高响应比优先调度算法(HRRF)
(1)算法思想:HRRF是FCFS和SJF的结合,克服了两种算法的缺点,设置响应比最高的作业优先启动。等待时间+服务时间=该作业的响应时间。
(2)调度策略
响应比最高的作业优先启动:
因等待时间+服务时间=该作业的响应时间,故该优先级又相当于响应比RP。据此,又可表示为:
(3)HRRF的小结:
- 等待时间相同的作业,则要求服务的时间愈短,其优先级愈高;
- 要求服务的时间相同的作业,则等待时间愈长,其优先级愈高;
- 是FCFS和SJF的结合,克服了两种算法的缺点;
- 长作业,优先级随等待时间的增加而提高,其等待时间足够长时,其优先级便可升到很高, 从而也可获得处理机;
- 缺点:要进行响应比计算,增加了系统开销;
5、进程调度——时间片轮转调度算法(RR—Round Robin)
进程调度的任务:是控制、协调进程对CPU的竞争
- (1)保存处理机的现场信息
- (2)按算法调度进程
- (3)处理机分配给进程
(1)时间片轮转调度算法的原理:系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片。当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便停止该进程的执行,并将其放就绪队列尾;然后,再把处理机分配给就绪队列中新的队首。
(2)时间片大小的确定:与时间片大小有关的因素:系统响应时间;就绪进程个数;CPU能力
(3)算法的特点:
- 采用比FCFS更加公平的处理机分配方式,每个进程大约获得1/n的处理及时间 ;
- 进程上下文切换,增加系统开销;
- 没有考虑到进程的紧急程度;
- 既可以是抢占式的,也可以是非抢占式的;
- 缺点:紧迫任务响应慢。
6、进程调度——优先级调度算法
(1)抢占式优先级调度算法
把处理机分配给优先级最高的进程,但在执行期间,只要出现另一个优先级更高的进程,则进程调度程序就立即停止当前进程的执行,并将处理机分配给新到的优先级最高的进程。只要系统中出现一个新的就绪进程,就进行优先级比较
(2)非抢占式优先级调度算法
系统一旦把处理机分配给就绪队列中优先级最高的进程后,该进程便一直执行下去,直至完成。
(3)静态优先级调度算法
静态优先级在创建进程时确定,且在进程的整个运行期间保持不变。
(4)动态优先级调度算法
优先级随进程的推进或随其等待时间的增加而改变,以获得更好的调度性能。
7、进程调度——多队列调度算法
原理:设置多个就绪队列,并为各个队列赋予不同的优先级。
第一个队列的优先级最高,第二个队列次之,其余各队列的优先级逐个降低。
各个队列中时间片的大小也各不相同,队列优先级愈高,时间片就愈小。
队列的转换:
(1)仅当第一队列空闲时,调度程序才调度第二队列中的进程运行;
(2)仅当第1~(i-1) 队列均空时,才会调度第i队列中的进程运行
(3)如果处理机正在第i队列中为某进程服务时,又有新进程进入优先级较高的队列(第1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回到第i队列的末尾,把处理机分配给新到的高优先级进程
-
【操作系统】_7种进程调度算法
2022-04-26 23:43:41书中一共描述了七种进程调度算法,为了学到这几种调度算法,后边做了几道练习题。 1. 先来先服务(FCFS)调度算法 先来先服务调度算法是最简单的调度方法。其基本原则是,按照进程进入就绪队列的先后次序进行选择。...书中一共描述了七种进程调度算法,为了学到这几种调度算法,后边做了几道练习题。
1. 先来先服务(FCFS)调度算法
先来先服务调度算法是最简单的调度方法。其基本原则是,按照进程进入就绪队列的先后次序进行选择。对于进程调度来说,一旦一个进程得到处理机,它就一直运行下去,直到该进程完成任务或者因等待某事件而不能继续运行,才会让出处理机。先来先服务调度算法属于非剥夺方式。
从表面上看,这个方法对于所有进程都是公平的,并且一个进程的等待时间是可以预先估计的。但是从另一方面来说,这个方法并非公平,因为当一个大进程先到达就绪状态时,就会使许多小进程等待很长时间,增加了进程的平均周转时间,会引起许多小进程用户的不满。
今天,先来先服务调度算法已很少用作主要的调度算法,尤其是分时和实时系统中。但它常被结合在其他的调度算法中使用。例如,在使用优先级作为调度依据的系统中,往往对许多具有相同优先级的进程使用先来先服务的原则。2. 优先级调度算法
按照进程的优先级高低来进行调度,使高优先级进程优先得到处理机的调度算法称为优先级调度算法。进程的优先级可以由操作系统按一定原则赋予,也可以在操作系统外部安非,甚至可由用户支付高额费用来购买。
但在许多采用优先级调度算法的系统中,通常使用动态优先级。一个进程的优先级不是固定的,可能会随许多因素的变化而变化,例如,进程的等待时间、已使用的处理机时间或其他资源的使用情况。
优先级调度算法又可分为下述两种:
①非剥夺的优先级调度算法。一旦某个高优先级的进程得到处理机,就一直运行下去,直到由于其自身的原因(任务完成或等待事件)而主动让出处理机,才让另一个高优先级进程运行。
②可剥夺的优先级调度算法。任何时刻都严格按照优先级高的进程在处理机上运行的原则进行调度,或者说,在处理机上运行的进程永远是就绪进程队列中优先级最高的进程。在进程运行过程中,一旦有另一个优先级更高的进程出现(如一个高优先级的等待状态进程因事件的到来而成为就绪状态),进程调度程序就迫使原运行进程让出处理机给更高优先级的进程使用,或称为抢占处理机。在UNIX系结中,其讲程调度算法属于“可剥夺的优先级调度算法”。每个进程的优先级都是动态优先级,由系统为各进程每隔一个时间间隔计算一次优先级。3. 时间片轮转调度算法
时间片轮转调度算法也多用于进程调度。采用此算法的系统,其进程就绪队列往往按进程到达的时间来排序。进程调度程序总是选择就绪队列中的第一个进程,也就是说,按照先来先服务原则进行调度,但进程仅占用处理机一个时间片。在使用完一个时间片后,即使进程还没有完成其运行,它也必须让出(被剥夺)处理机给下一个就绪的进程。而被剥夺的进程返回就绪队列的末尾重新排队,等候再次运行。时间片轮转调度算法特别适合分时系统使用。当多个进程驻留主存时,在进程间转接的开销一般不是很大。
由于时间片值对计算机系统的有效操作影响很大,所以在设计此算法时,应考虑下列问题:时间片值如何选择?它是固定值还是可变值?它对所有用户都相同还是随不同用户而不同?显然,如果时间片值很大,大到一个进程足以完成其全部任务所需的时间,那么此时间片轮转调度算法就退化为先来先服务调度算法了。如果时间片值很小,那么处理机在进程间的切换工作过于频繁,使处理机的开销变得很大,而处理机真正用于运行用户程序的时间将会减少。通常,最佳的时间片值应能使分时用户得到好的响应时间,因此时间片值应大于大多数分时用户的询间时间,即当一个交互进程正在执行时,给它的时间片值相对来说略大些,使它足以产生一个IO请求:或者时间片值略大于大多数进程从计算到IO请求之间的间隔时间。这样可使用户进程工作在最高速度上,并且也减少了进程间切换的不必要的开销,提高了处理机和I/O设备的利用率,同时也能提供较好的响应时间。
各系统的最佳时间片值是不同的,而且随着系统负荷不同而有所变化。关于时间片值的更进一步考虑和时间片轮转调度算法参阅“多级反馈队列调度算法”。
特别要注意的是,时间片是否用完的判定程序是由时钟中断处理程序激活的,因此时间片值必须大于时钟中断间隔。4. 短进程优先(SPF)调度算法
短进程优先调度算法从进程的就绪队列中挑选那些运行时间(估计时间)最短的进程进入主存运行。这是一个非剥夺算法。它一旦选中某个短进程,就应该保证该进程尽可能快地完成运行并退出系统。这样减少了在就绪队列中等待的进程数,同时也缩短了进程的平均等待时间,提高了系统的吞吐量。但从另一方面来说,各进程的等待时间的变化范围较大,并且进程(尤其是大进程)的等待时间难以预先估计。也就是说,用户对他的进程什么时候完成心里没底。这样,当后续短进程过多时,大进程可能没有机会运行,导致“饿死”。而在先来先服务调度算法中,进程的等待和完成时间是可以预期的。
短进程优先调度算法要求事先能正确地了解一道作业或进程将运行多长时间。但通常一个进程没有这方面可供使用的信息,只能估计。在生产环境中,对于一道类似的作业可以提供大致合理的估计;而在程序开发环境中,用户难以知道他的程序大致将运行多长时间。
正因为此算法明显偏向短进程,而且进程的运行时间是估计的,所以用户可能把他的进程运行时间估计得过短,从而争取优先运行。为此,当一个进程的运行时间超过所估计的时间时,系统将停止这个进程,或对超时部分加价收费。
短进程优先调度算法和先来先服务调度算法都是非剥夺算法,因此均不适用于分时系统,因为不能保证对用户及时响应。5. 最短剩余时间优先调度算法
最短剩余时间优先调度算法是将短进程优先调度算法用于分时环境的变形。其基本思想是,让“运行到任务完成时所需的运行时间最短”的进程优先得到处理,包括新进入系统的进程。在最短进程优先调度算法中,一个进程一旦得到处理机,就一直运行到任务完成(或等待事件)而不能被剥夺(除非主动让出处理机)。而最短剩余时间优先调度算法允许被一个新进入系统的且其运行时间短于当前运行进程的剩余运行时间的进程所抢占。
该算法的优点是,可以用于分时系统,保证及时响应用户要求。缺点是,系统开销增加。首先,要保存进程的运行情况记录,以比较其剩余时间长短:其次,剥夺本身也要消耗处理机时间。毫无疑问,这个算法使短进程一进入系统就能立即得到服务,从而缩短进程的平均等待时间。6. 最高响应比优先调度算法
Hansen针对短进程优先调度算法的缺点提出了最高响应比优先调度算法。这是一个非剥夺的算法。按照此算法,每个进程都有一个动态优先数,该优先数不但是要求的服务时间的函数,而且是该进程得到服务所花费的等待时间的函数。进程的动态优先数计算公式如下:
优先数=(等待时间+要求的服务时间)/要求的服务时间
要求的服务时间是分母,所以对短进程是有利的,因为区的优先数高,可优先运行。另外,因为等待时间是分子,所以长进程由于其等待了较长时间,从而提高了其优先致,终于得到了处理机。进程一旦得到处理机,它就一直运行到进程完成任务(或因等待事件而主动让出处理机),中间不被抢占。
可以看出,“等待时间+要求的服务时间”是系统对作业的响应时间,所以在优先数公式中,优先数的值实际上也是响应时间与服务时间的比值,称为响应比。响应比高者得到优先调度。7. 多级反馈队列调度算法
短进程优先调度算法或最短剩余时间优先调度算法均是在估计的进程运行时间基础上进行调度的,但在程序开发环境或其他情况下,往往难以估计进程的运行时间。这里所研究的算法是时间片轮转调度算法的发展,不必估计进程运行时间。但是本算法仍然基于以下考虑:
①为提高系统吞吐量和缩短进程的平均等待时间而照顺短进程。
②为得到较好的I/O设备利用率和对交互用户的及时响应而照顾I/O型进程。
③在进程运行过程中,按进程运行情况动态地考虑进程的性质(I/O型进程还是处理机型
进程),并且要尽可能快地决定进程当时的运行性质(以I/O为主还是以计算为主),同时进行相应的调度。
具体来说,多级反馈队列的概念如下图所示。系统中有多个进程就绪队列,每个就绪队列对应一个调度级别。第1级队列的优先级最高,以下各级队列的优先级逐次降低。调度时,选择高优先级队列中的第1个就绪进程。
各级队列中的进程具有不同的时间片值。优先级最高的第1级队列中的进程的时间片值最少;题看队列级别的增高,其进程的优先级降低了,但时间片值却增大了。通常,下放一级,其时间片值增大1倍。各级队列均按先来先服务原则排序。
调度方法:当一个新进程进入系统后,它被放入第1级队列的末尾。该队列中的进程按先来先服务原则得到处理机,并使用一个相应于该队列的时间片。假如进程在这个时间片内完成了其全部任务,或因等待事件或/O而主动放弃了处理机,该进程就撤离系统(任务完成)或进入相应的等待队列,从而离开就绪队列。若进程使用完了整个时间片后,其运行任务并未完成(也没有产生V/O请求),仍然要求运行,则该进程被剥夺处理机,同时它被放入下一级队列的末是,当第1级队列为空后,调度程序才去调度第2级队列中的进程。其调度方法同前。当第1、2爱队列全部为空后,才去调度第3级队列中的进程……当前面各级队列全部为空后,才去调度最后第n级队列中的进程。第n级(最低优先级)队列中的进程采用时间片轮转调度算法进行调度。当比运行进程更高级别的队列中到来一个新的进程时,它将抢占处理机,而被抢占的进程回到原队列的末尾。
多级反馈队列的调度操作如上所述,它根据进程运行情况的反馈信息而对队列进行组织并调度进程。但对此调度算法需要说明如下。
①照顾I/O型进程的目的在于充分利用外部设备,以及对终端交互用户及时地予以响应。
为此,通常L/O型进程会进入最高优先级队列,从而能很快得到处理机。另一方面,第1级队列
中进程的时间片值也应大于大多数I/O型进程产生一个I/O请求所需的运行时间。这样,既能
使I/O型进程得到及时处理,也避免了不必要的过多的在进程间转接处理机的操作,以减少系统开销。
②处理机型(计算型)进程由于总是用尽时间片(有些计算型进程一直运行几小时也不会产生一个IO请求),而由最高优先级队列逐次进入低优先级队列。虽然运行优先级降低了,等待时间也较长,但终究会得到较大的时间片值来运行,直至在最低一级队列中轮转。
③在有些分时系统中,一个进程由于IO操作完成而要求重新进入就绪队列,并不是将它
放入最高优先级队列,而是让它进入因I/O请求而离开的原来那一级队列。这就需要对进程所在的队列序号进行记录。这样做的好处是,有些计算型进程偶然产生一次I/O请求,I/O操作完成后仍然需要很长的处理机运行时间,为减少进程的调度次数和系统开销,就不要让它们从最高级队列逐次下移,而是直接放入原来所在队列。
但在一个大的程序中,不同的程序段有不同的运行特点。有时计算多,有时I/O操作多。
也就是说,一个计算型进程有时也可以看成IO型进程,为此在有些系统中,当进程每次由于I/0操作完成而重新进入就绪队列时,就将它放入比原来高一级的就绪队列,这样就能体现出进程由计算型向I/O型变化的状态。一道练习题
解析:
在“可抢占的最高优先级”调度中,任何时刻内核都将处理机分配给当前最高优先级的就绪进程。也就是说,只有当高优先级进程主动放弃CPU时,低优先级进程才有机会运行,并且,一旦高优先级进程需要CPU时,内核就会剥夺低优先级进程的CPU,分配给它使用。在本例中,由于进程P1和P2在开始执行时,需要进行IO,因此最低优先级的P3得到处理机。但是P3运行了20ms之后被P2(IO已完成)抢占了,P2运行了10S后(还剩10s)被P1抢占了CPU;
P1 P2 P3 从开始到结束所用的时间分别为:90ms 110ms 80ms,总共完成需要110ms。
CPU的使用率:(30 + 20 +10 + 10 )/ 110 = 63.6%
IO1的利用率:(20 + 30 + 40) / 110 = 81.8%
IO2的利用率:(30 + 20 + 10 )/ 110 = 54.5 -
处理机调度和进程调度
2020-06-25 12:01:03调度处理机调度高级调度中级调度低级调度进程调度进程调度的时机进程调度的方式进程的切换与过程调度算法FCFS 先来先服务SJF 短作业优先HRRN 高响应比优先总结交互式调度算法时间片轮转 RR优先级调度算法多级反馈... -
操作系统模拟实验:单处理机系统的进程调度(实验要求、代码及实验报告)
2009-12-07 17:17:33自己写的代码和实验报告,模拟了在单处理机系统下的进程调度。适于操作系统初学者理解操作系统中的进程调度原理。(希望朋友们先根据要求自己实现代码,然后再参考我的代码。) -
操作系统进程调度算法 c语言实现
2011-04-07 08:59:30进程调度算法:采用最高优先数优先的调度算法(即把处理机分配给优先数最高的进程)和先来先服务算法。 每个进程有一个进程控制块( PCB)表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行... -
【操作系统】多处理机系统中的进程调度和Unix的进程调度
2016-12-05 18:52:50多处理器系统进程分配多处理器系统 (MPS) 的类型 紧密耦合型:共享内存和 I/O,通过高速总线连接。 松弛耦合型:独立内存和 I/O,通信线路或通道连接。 对称多处理器系统 (SMPS) 和非对称多处理器系统非对称多处理器... -
操作系统实验-单处理机系统的进程调度
2018-12-17 17:43:56实验项目一:单处理机系统的进程调度 4学时 (一)实验目的要求 通过模拟进程控制方法和单处理机系统下的进程调度,了解进程的结构、进程的创建与撤销,进程的组织及进程的状态及其转换,掌握进程调度策略。 (二... -
操作系统实验--模拟实现单处理机下的进程调度程序
2011-11-21 23:16:10操作系统实验 模拟实现单处理机下的进程调度程序 包括先来先服务 短作业优先 时间片轮转 动态优先级 并有详细注释 -
Linux的进程调度算法简介
2021-07-16 09:28:57进程调度的研究是整个操作系统理论的核心,在多进程的操作系统中,进程调度是一个全局性的、关键性的问题,它对系统的总体设计、系统的实现、功能设置以及各方面的性能都有着决定性的影响。进程运行需要各种各样... -
操作系统-java实现进程调度
2020-10-30 20:23:45Java实现操作系统进程调度问题 进程调度方式 (1)非抢占式 一旦处理机分配给某进程后,不管它运行多久让他一直运行下去,不会因为时钟中断等原因而抢占正在运行的处理机。直到该进程完成,自愿放弃处理机,或阻塞... -
操作系统进程调度算法(c语言实现)
2019-12-03 17:15:00进程调度算法 一、先来先服务(FCFS) 基本思想:先到达的进程先进入就绪队列,先进行调度的原则。非抢占方式。 二、短作业优先(SJF) 基本思想:根据进程中的执行时间,选取执行时间最短的作业优先调度;可有抢占... -
单处理机系统的进程调度
2019-09-19 11:10:28了解并掌握进程、进程调度的概念及进程调度算法。 二、实验内容 假设某单处理机系统采用“基于动态优先权的时间片轮转”调度算法,系统允许进程的最大个数为10。进程队列采用单向链表组织进程控制块。请编程实现该... -
操作系统进程调度 FCFS,SJF,RR算法(Java实现)
2022-03-25 13:24:36假定系统的内存共364K,初始状态为操作系统本身占用64K。在t1时间之后,有作业A、B、C、D分别请求8K、16K、64K、124K的内存空间:在t2时间之后,作业C完成;在t3时间之后,作业E请求5K的内存空间;在t4时间之后,作业D完成。... -
操作系统实验-单处理机系统的进程调度c++版
2019-12-12 08:59:17通过模拟进程控制方法和单处理机系统下的进程调度,了解进程的结构、进程的创建与撤销,进程的组织及进程的状态及其转换,掌握进程调度策略。 (二)实验材料和仪器设备 Windows操作系统环境下的个人微机。 (三)... -
操作系统实验之单处理机系统的进程调度
2019-10-10 17:23:42操作系统实验之单处理机系统的进程调度 假设某单处理机系统采用“基于动态优先权的时间片轮转”调度算法。进程队列采用单向链表组织进程控制块。 过程:假设进入的进程有3个,轮转时间片为5 运行逻辑如下: ... -
中断处理与进程调度的区别
2020-12-19 21:36:23中断处理与进程调度的区别 对于中断处理和进程调度的抢占方式(处理机调度),因为二者都有打断的性质,都是抢占了CPU,所以容易混淆。 首先,中断处理是外设打断进程,比如一个进程在使用cpu,它的某条指令到达了... -
操作系统实验报告一 进程调度
2021-05-09 20:17:07实验一 进程调度 任务一 一、实验名称 进程调度-代码阅读并调试实验 二、实验目的 1、阅读下面源代码,完善程序中填空处内容。 2、阅读代码,写出调度算法、算法流程图和程序功能。 3、解释数据结构PCB的定义和... -
操作系统中的进程调度策略有哪几种
2018-09-22 09:00:39先来先服务调度算法:先来先服务(FCFS)调度算法是一种最简单的调度算法,...在进程调度中采用FCFS算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到... -
【Linux 内核】Linux 内核体系架构 ( 进程调度 | 内存管理 | 中断管理 | 设备管理 | 文件系统 )
2022-03-21 23:43:21一、进程调度、 二、内存管理、 三、中断管理、 四、设备管理、 五、文件系统、 -
操作系统(OS)进程与调度
2021-10-13 17:12:054、进程:进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位 5、PCB与进程的关系:PCB是进程存在的唯一标志。创建进程即创建进程实体中的PCB;撤销进程即撤销进程实体中的PCB 1.2 进程的组成 1、... -
操作系统课程设计——处理机和进程调度算法及内存分配回收机制
2021-12-02 19:37:19本程序模拟实现处理机调度和内存分配及回收机制,并通过可视化界面观察进程的运行流程与情况。为了实现算法与界面的解耦合,以及绘制更加优美的界面,本实验设计了前后端分离的架构,在后端使用Python的Flask框架... -
Linux系统进程调度——调度架构详细分析
2019-04-14 16:54:25Linux进程调度架构 1 调度器 1.1 概述 现代的操作系统是多任务的操作系统,硬件的处理器核心和各种资源越来越多,CPU也是一个资源。为了保证进程合理的使用CPU资源,则需要一个管理单元,负责... -
操作系统进程调度模拟算法(C实现)
2020-07-03 16:44:04对各进程按照到达时间进行排序,挑选最先到达的进程一次性执行完毕,判断是否所有进程都被调度,若是则结束,否则返回挑选最先到达的进程一次性执行完毕步骤,继续执行后续程序。按照进程进入的先后次序来分配处理器... -
操作系统:七种进程调度算法
2020-12-07 15:36:32对于七种进程调度算法进行了相关的介绍! -
os 作业调度与进程调度算法
2022-01-18 14:07:35os 作业调度算法与进程调度算法 -
操作系统——进程调度算法(C++)
2020-11-14 14:07:29多道系统中,当就绪进程数大于处理机数时,须按照某种策略决定哪些进程优先占用处理机,本实验模拟实现处理机调度,以加深了解处理机调度的工作 2. 实验内容: 选择一个调度算法,实现处理机调度。 FCFS(先到先服务...