非抢占式的静态优先权优先调度算法

来自计算思维百科
跳转至: 导航搜索
非抢占式的静态优先权优先调度算法1.png

在完成很多任务时,有的任务很紧急,需要马上处理,这种任务我们一般都说它的优先级最高。最高优先权优先调度算法就是为了照顾紧迫型作业,使之在进入系统后便获得优先处理。最高优先权优先调度算法中的一种算法就是非抢占式的静态优先权优先调度算法。这种调度算法常用于批处理系统中,也可用于某些对实时性要求不严的实时系统中。

基本概念

非抢占式,是指系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成;或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程。

静态优先权,是指在创建进程时确定的,且在进程的整个运行期间保持不变。

非抢占式的静态优先权优先调度算法,就是在创建进程时确定好进程的优先级数,并且在进程整个运行过程中保持不变,而进程需等到处理机空闲时才使用至完成进程的调度算法。

确定进程优先权的依据有3个方面,进程类型、进程对资源的需求和用户要求。

应用范围

非抢占式的静态优先权优先调度算可应用于需要提前设定优先次序的情况处理,例如十字路口交通灯的亮灯顺序控制,银行VIP客户和普通客户服务顺序的安排等

使用方法及步骤

0. 判断所要解决的事件是否符合本算法的问题情况,若符合,执行下一步;

1. 根据事件类型、事件对资源的需求、用户要求设置事件或人员的优先级数;

2. 判断当前资源的空闲情况:若全部没有,则让进程等待;若事件所需的所有资源均空闲,则把资源分配给优先级数最高的进程,事件进行至完成,释放资源;

3. 重复2直至事件队列为空或外部强制停止。

应用案例

应用1-普通十字路口人行道和车道红绿灯设计

案例:十字路口常常面对着超高的人流量和车流量,有时候可能出现人和车正好要往交叉的方向通行,车流量往往比人流量高。应该如何设计人行道红绿灯和车道红绿灯的亮灯顺序?

非抢占式的静态优先权优先调度算法2.png

解决步骤:

  1. 不同日子,一天当中的不同时间对车流量和人流量进行统计并记录
  2. 根据统计的结果,对于车流量和人流量的不同高峰期,设定绿灯时间应该长一点,红灯时间短一点
  3. 对于车和人同时往交叉方向通行的情况,根据统计的结果,让需要通行数量多的一方的绿灯时间长一点
  4. 对于道路流量较少的时间段,设定绿灯的时间可以短一点
  5. 通行流量常常较高的通道绿灯时间应该长一点,但该方向通行后,必须让交叉方向道路通行,即绿灯亮起,

在这个解决方案中,绿灯的时间相当于系统处理的时间,人和车通过路口就是任务,而这个任务的优先级就由车流量和人流量决定。流量大,优先级就高,绿灯时间长就可以优先处理。

可以体现的计算思维

非抢占式的静态优先权优先调度算法根据任务需要设定不同的时间段来执行任务,使得不同的任务都及时得到处理,体现了计算思维的调度特点,提高了整体任务执行效率。