收藏
0有用+1
0

时间片轮转调度

计算机科学概念
时间片的概念,可以用来部分解释本书开始时的一句话:在数据传输领域,你亲眼看见的,都不是真的。在宏观上:我们可以同时打开多个应用程序,每个程序并行不悖,同时运行。但是在微观上:由于只有一个CPU,一次只能处理程序要求的一部分,如何处理公平,一种方法就是引入时间片,每个程序轮流执行。
中文名
时间片轮转调度
行    业
计算机
性    质
名词
采    用
算法系统

概念的引入

播报
编辑
备埋姜说到并行计算,尤其是单台计算机的并行计算章盼主,一定要先建立时间片的概念。
我们现在所用的,不管是Windows还是Linux,一般都称为多任务操作系统,即,系统允许凳霉宙并行运行多局蒸泪盛背兰个应用程序。
操作系统一般是按照一定策略,定期给每个活动的进程执行其内部程序的机会,并且每次只执行一小段时间,然后操作系统利用中断强行退出执行,将当前程序信息压栈,然后开始执行下一个进程的一小段程序。
通过这样不断快速的循环切换,每个程序都获得执行,在用户看来,感觉到很多程序都在平行的执行,这就模拟了并行计算。
当然,新的多核CPU以及超线程CPU,内部就有超过1个的CPU执行体,运行时就不是模拟了,而是真的有两个以上的程序在被执行。
当章洪然在我们程序员看来,只需要理解程序是被操作系统片段执行的,每个片段就是一个时间片,就足够了。
既然是片段执行,程序员就必须理解,在自己的程序运行时不是独一无二的,我们看似很顺畅的工作,其实是由一个个的执行片段构成的,我们眼中相邻的两条语句乌阿牛甚至同一个语句中两个不同的运算符之间,都有可能插入其他线程或进程的戏欠动作。

基本概念

播报
编辑
时间片轮转法(Round-Robin,RR)主要用于分时系统中的进程调度。为了实现轮转调度,系统把所有就绪进程按先入先出的原则排成一个队列。新来的进程加到就绪队列末尾。每当执行进程调度时,进程调度程序总是选出就绪队列的队首进程,让它在CPU上运行一个时间片的时间。时间片是一个小的时间单位,通常为10~100ms数量级。当进程用完分给它的时间片后,系统的计时器发出时钟中断,调度程序便停止该进程的运行,把它放入就绪队列的末尾;然后,把CPU分给就绪队列的队首进程,同样也让它运行一个时间片,如此往复。 [1]

进程调度

播报
编辑
采用此算法的系统,其程序就绪队列往往按进程到达的时间来排序。进程调度程序总是选择就绪队列中的第一个进程,也就是说按照先来先服务原则调度,但一旦进程占用处理机则仅使用一个时间片。在使用先一个时间片后,进程还没有完成其运行,它必须释放出处理机给下一个就绪的进程,而被抢占的进程返回到就绪队列的末尾重新排队等待再次运行。
处理器同一个时间只能处理一个任务。处理器在处理多任务的时候,就要看请求的时间顺序,如果时间一致,就要进行预测。挑到一个任务后,需要若干步骤才能做完,这些步骤中有些需要处理器参与,有些不需要(如磁盘控制器的存储过程)。不需要处理器处理的时候,这部分时间就要分配给其他的进程。原来的进程就要处于等待的时间段上。经过周密分配时间,宏观上就象是多个任务一起运行一样,但微观上是有先后的,就是时间片轮换。

实现思想

播报
编辑
时间片轮转算法的基本思想是,系统将所有的就绪进程按先来先服务算法的原则,排成一个队列,每次调度时,系统把处理机分配给队列首进程,并让其执行一个时间片。当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序根据这个请求停止该进程的运行,将它送到就绪队列的末尾,再把处理机分给就绪队列中新的队列首进程,同时让它也执行一个时间片。