非抢占式的时间片轮转调度算法

来自计算思维百科
跳转至: 导航搜索
非抢占式的时间片轮转调度算法.jpg

我们很多任务需要处理的情况下,为了不使某个任务长时间等待,可以采用时间片轮转的调度算法。这种算法的思想就是让每个任务都执行相同的时间,这个时间不足以完成任务,但是可以使任务部分完成。基于时间片的轮转式进程调度算法是一种非抢占式的调度算法。

基本概念

在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把CPU 分配给队首进程,并令其执行一个时间片。时间片的大小从几ms到几百ms。由于是非抢占式的,必须等执行的时间片用完时,再处理下一个进程,同时也让它执行相同的时间片。

在本算法中,最重要的是时间片的确定。时间片太长,本算法会退化成顺序算法,无法满足交互用户的需求;太短则会增加系统的开销。

应用范围

该算法可用于有不同或相同固定使用时间设定的任务顺序安排,例如大学教室使用的顺序分配,企业会议室的使用顺序安排等

使用方法及步骤

1. 按照先来先服务原则将事件排成队列,标明顺序;

2. 根据事件的大小等因素设定合适的时间片;

3. 让队首事件执行完一个时间片,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并把它送往就绪队列的末尾;然后再把资源分配给就绪队列中心的队首进程,同时也让它执行一个时间片。

4. 重复步骤3直到事件执行完毕或外部强制终止。

应用案例

应用1-大学教室使用分配

解决步骤:

  1. 找出空闲的教室并编号;
  2. 给没有学院楼的学院班级设计课表,设计原则为上课时间长度一样,一旦教室被使用,则该时间段教室不应该分配给其他班级
  3. 每个学生都应该拿到有标注上课时间和教室的课表
  4. 学生按照课表上课

在这个解决方案中,教师就是一种资源,需要教室的课程就是任务,每个课程只能占用固定的时间片段,这就是时间片调度思想。

可以体现的计算思维

非抢占式的时间片轮转调度算法根据需要设定不同的时间段,按照先来先服务原则,使得每一个任务都能较为均衡地得到执行,提高了整体任务的执行效率,体现了计算思维的调度,适合于可设定使用时间段的任务次序安排。