先来先服务调度算法

来自计算思维百科
跳转至: 导航搜索
先来先服务调度算法.png

如果有很多任务需要完成,到底先做哪一个?我们常常采用的一种策略就是先来的任务先做,后来的任务后做。这就是计算机操作系统的先来先服务(FCFS)调度算法,是资源分配策略中一种最简单的调度算法。

基本概念

先来先服务(FCFS)调度算法,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源,创建进程,然后放入就绪队列。

应用范围

该算法常常应用于使用者数量多于资源数量且每个使用者占用资源的时间相对较长的情况,例如与人相关的顺序安排,银行普通客户柜台手续办理等

使用方法及步骤

  1. 无论当前任务数量多少,都需要按照到达时间依次排成一个队列;
  2. 无论所需资源是否空闲,只要有新事件进入队列,则必须排在队列最后一个事件的后面,并且将队列事件数量加1;
  3. 判断所需资源中的一个是否被占用,若被占用,则当前队列中的事件等待;若所需资源全部空闲,则事件进行至完成,队列数量减1;
  4. 循环1、2、3至队列为空或外部强制停止。

应用案例

应用1-银行普通客户柜台手续办理顺序设计

案例:某银行有4个普通柜台,银行规定每天服务的人员数量为200,银行设定的人员工作顺序是窗口1,窗口2,窗口3,窗口4,当前来办理业务的客户有5个,且接下来还会有客户来办理业务,拿到号码的人都不会临时改变办理日期。如何让来办理业务的客户和银行工作人员得到合理的安排呢?

解决步骤:

  1. 设置一个排号器,身份证作为标识ID,用来给客户排号;设置一个叫号器,用于呼叫当前在等待的客户的号码到空闲的窗口
  2. 根据客户到达银行的时间先后顺序给客户编号,因此第一个客户拿到的号码应该为001,第二个客户号码为002,第三个客户号码为003,第四个客户号码为004,第五个客户号码为005。
  3. 4个柜台工作人员的窗口前此时都没有客户来办理业务,叫号器呼叫号码为1的客户到001号窗口,呼叫号码为002的客户到2号窗口,呼叫号码为003的客户到3号窗口,呼叫号码为004的客户到4号窗口,第005个客户则在大厅等待。
  4. 在1号、2号、3号、4号客户办理业务的过程中,有新的客户来到银行,新客户编号为006。
  5. 若4个窗口中有一个窗口已办理好业务,则呼叫器呼叫下一位正在等待的客户到空闲的窗口办理业务。
  6. 重复4、5至排号器号码为200。

应用2-超市柜台结算顺序

案例:大型超市每天都有很多顾客买东西,但柜台通常只有少数几个。为了保证不出现拥挤混乱的场面,通常结算都是按照到达结算柜台的先后顺序排队,先到的先结算,排在前面的先结算,哪个柜台空闲,可以在该柜台排队结算。

可以体现的计算思维

先来先服务算法按照任务到达时间先后顺序给对象排序,操作简单易行,体现了计算思维的调度特点,对短任务尤其有利。