进程调度&调度算法

初识调度

在学校时，只要讲到操作系统时我就见到周公了。所以我非常不喜欢所谓的模型，对计算机的理解也习惯从生活中来到生活中去，现在对于原理有了一些浅显的理解，那么我就抛砖引玉，希望得到大佬的指正。
在了解进程调度时，先了解两个小故事

齐国使者到大梁来，孙膑以刑徒的身份秘密拜见，劝说齐国使者。齐国使者觉得此人是个奇人，就偷偷地把他载回齐国。齐国将军田忌非常赏识他，并且待如上宾。田忌经常与齐国众公子赛马，设重金赌注。孙膑发现他们的马脚力都差不多，马分为上、中、下三等，于是对田忌说：“您只管下大赌注，我能让您取胜。”田忌相信并答应了他，与齐王和各位公子用千金来赌注。比赛即将开始，孙膑说：“现在用您的下等马对付他们的上等马，用您的上等马对付他们的中等马，用您的中等马对付他们的下等马。”三场比赛结束后，田忌一场败而两场胜，最终赢得齐王的千金赌注。因此田忌把孙膑推荐给齐威王。齐威王向他请教了兵法，封他为军师。 ————《史记》卷六十五：《孙子吴起列传第五》

第二个小故事离我们没有那么遥远，就是时间行者，空间刺客罗某，具体事情可以百度

计算机的进程调度，实际上没有那么复杂(咱得战略上藐视它)，简单的讲就是通过调整运行程序来实现操作系统的最优化。

程序执行的模式

一般而言，同一时间CPU只有一个只能执行一个程序(多进程并发暂不讨论)。
现行条件下，程序的执行大概有两种

• CPU导向/计算密集型程序
  CPU导向(bound)也叫计算密集型，它系统的硬盘、内存性能相对CPU要好很多，此时，系统运作大部分的状况是CPU Loading 100%，CPU要读/写I/O(硬盘/内存)，I/O在很短的时间就可以完成，而CPU还有许多运算要处理，CPU Loading很高。
  在多重程序系统中，大部份时间用来做计算、逻辑判断等CPU动作的程序称之CPU bound。例如一个计算圆周率至小数点一千位以下的程序，在执行的过程当中绝大部份时间用在三角函数和开根号的计算，便是属于CPU bound的程序。
  CPU bound的程序一般而言CPU占用率相当高。这是因为任务本身不太需要访问I/O设备，当然也可能是因为程序是多线程实现因此屏蔽掉了等待I/O的时间。
  就像去高档餐厅吃饭，只要有人来吃，几乎不用排队，但是也要过段时间才能吃饭，毕竟它做菜的时间长
  

  
  



• I/O导向/交互密集型程序
  IO密集型指的系统CPU性能相对硬盘、内存要好很多，此时，系统运作，大部分的状况是CPU在等I/O (硬盘/内存) 的读/写操作，此时CPU负载并不高。
  I/O bound的程序一般在达到性能极限时，CPU占用率仍然较低。这可能是因为任务本身需要大量I/O操作，而调度做得不是很好，没有充分利用处理器能力。
  这种程序大部分的时间用在I/O，I/O后在CPU上进行短暂的CPU运算，然后进行下一次的I/O，这样循环往复...游戏就是一种I/O导向程序，在我们按下qwer后，cpu进行短暂的运算，就又等着下一次I/O
  而十一黄金周到某著名小吃店则不一样，虽然到吃上也要花很久，它菜做的很快，只不过大部分的时间都用在排队上
  

  
  

先来先服务调度算法FCFS(First Come First Serve)

字面意思，先来后到。这个算法也不知道是谁想出来的—，或许就是计算机界约定俗成的吧。
这种算法，看似公允，实则非常反人类。例如：在政务大厅排队处理违章，你只需要三分钟，签个字就行；但是排你前面的人却要搞两钟头，这样实际上你需要的时间就是两钟头零三分钟......

时间片轮转调度算法RR（Round-Robin）

时间片轮转其实就是对FCFS的一种优化，目的就是为了改善短程序排在长程序后面也能快速执行，其方法是在一定的时间内(时间片)将进程轮换。
例如：
现在有两个程序

如果用FCFS方法先来后到，A要100秒，B就得耗时101秒。两个程序平均耗时100.5秒
用RR的方法，假设每一秒轮换一次。A先来执行一秒，然后轮换给B执行一秒，B就执行完了，A接着执行第99秒。这样实际上A就要花101秒，B花2秒(A执行第一秒时B在等待)。两个程序平均花51.5秒。
每10秒轮换一次，平均时间为65秒（A10s+B等A10s+B10s+A等B10s+A90s）其中B实际上在第二波的时间片里的第一秒就完成了，但是余下的九秒也得算在里面,A也得完完整整的等待10秒；
每20秒轮换一次，平均时间为80秒
每30秒轮换一次，平均时间为95秒
每50秒轮转一次，平均时间为125秒
显然如果时间片选择的过大，RR就会完全退化成为FCFS，甚至还不如FCFS。请注意当时间片为三十秒时虽然平均用时还是比FCFS的100.5小，但是CPU在同一时刻只能做一件事，那么切换时间片本身就要耗费时间所以，我们上面的算法其实是不严谨的的。应该是：
51.5+两次切换时间片的时间；65+两次切换时间片的时间........
但是时间片选择的过小，切换时间片的次数太多本身就会成为cpu的负担,而且切换时间片本身也要时间.....

优先级调度算法

特殊优先级“短任务调度算法”SJF(shortest job first)

SJF算法以进程的运行时间长度作为优先级，进程运行时间越短，优先级越高。也就是谁运行的最快谁先上，运行的慢就不要占前排。
是不是有一点像上学时，谁成绩好谁就坐前排，成绩差就不要占着前面的位置，所以嘛！现行计算机就是一种伪科学，来源于生活，是一种人造技术。

SJF算法的缺点
必须预知进程的运行时间。即使是程序员也很难准确估计进程运行时间。如果估计过低，系统就可能按估计的时间终止进程的运行，但此时进程并未完成，故一般都会偏长估计
对长进程不利。长进程的周转时间会明显地增长。可怕的是，SJF算法完全忽视进程等待时间，可能使进程等待时间过长，出现饥饿现象。
人机无法实现交互。
完全未考虑进程的紧迫程度。不能保证紧迫性进程得到及时处理。
(未完待续)

混合调度算法

保证调度算法

彩票调度算法

用户公平调度算法

进程调度&调度算法