操作系统--进程状态切换以及cpu调度（转）

进程的状态转换

　　进程在运⾏中不断地改变其运⾏状态。通常，⼀个运⾏进程必须具有以下三种基本状态。

进程状态

执⾏态run：进程正在使⽤CPU

等待态wait：进程正在等待I/O完成，不在使⽤也不能使⽤CPU就绪态ready：进程不在使⽤CPU，但已经纯备好⽤使⽤CPU　　在特定的情况下，这三种状态可以相互转换。

状态转换

　　就绪->执⾏， 当前运⾏进程阻塞，调度程序选⼀个优先权最⾼的进程占有处理机；　　执⾏->就绪， 当前运⾏进程时间⽚⽤完；

　　执⾏->等待，当前运⾏进程等待键盘输⼊，进⼊了睡眠状态。　　等待->就绪，I/O操作完成，被中断处理程序唤醒。

　　刚从其他状态进⼊就绪态的进程需要置⼊调度队列，该队列不⼀定按进⼊队列的时间先后顺序排列。

　　从等待态中出来的进程通常不直接进⼊运⾏态，⽽要进⼊就绪态。如果需要直接进⼊运⾏态，这属于抢先式调度，通过抢先式中断完成。

　　从执⾏态到就绪态的转换发⽣在抢先式终端处理中，例如I/O或分时下的时间⽚。分时是在多个⽤户同时以交互⽅式使⽤计算机时采⽤的⼀种技术。

　　分时技术：每当时钟中断发⽣时且发现当前运⾏进程已连续在CPU上运⾏了⼀定的时间（称为时间⽚，⼀般为

20ms~250ms）时，就强制地发⽣进程切换，使当前进程退出CPU，重新调度，选出另⼀个进程在CPU上运⾏。此时，退出的进程不能变为等待状态，因为它不是因为等待I/O⽽退出的，也不能变为终⽌，因为它尚未结束，因此，它需要转换为就绪态，等待属于它的时间⽚的到来。

　　当正在建⽴⼀个新进程时，计算机上的当前运⾏进程是哪⼀个？　　该新进程的⽗进程。

CPU调度算法

　　同时处于就绪态的进程经常有多个，因此需要⼀个CPU调度算法来君顶那⼀个就绪进程先运⾏。衡量CPU调度算法的标准有：CPU利⽤率、⽤户程序响应时间、系统吞吐量、公平合理性、设备利⽤率等。

　　常见的调度算法有先来先服务FIFO、轮转调度法RR（时间⽚法）、优先级调度法、短作业优先SJF、最短剩余事件优先、最⾼相应⽐优先、多级反馈法、策略驱动法、最晚时间限调度、⼆级调度法。

定义　　

　　FIFO算法：⼀般应⽤于实时性系统中，最先进⼊就绪态的进程最先进⼊运⾏态。

　　轮转调度法：根据系统给与的时间⽚，进⾏进程的轮询访问CPU，若时间⽚结束，该进程还在运⾏，就会被强制撤出。该⽅法通常和FIFO或优先级算法⼀起使⽤。

　　优先级调度法：根据不同进程的重要程度和紧急程度，来赋予每个进程⼀个优先级，带有最⾼优先级的进程最先执⾏。优先级调度算法分为静态优先级和动态优先级两种。动态优先级可以防⽌优先级⾼的进程不停地执⾏。

　　最短作业优先：最先执⾏占⽤CPU时间最短的进程。最短的进程第⼀个执⾏总是产⽣最⼩的平均相应事件。　　最短剩余时间优先：剩余运⾏事件最短的进程最先运⾏。

　　最⾼相应⽐优先：最先执⾏相应⽐最⾼的进程。相应⽐的计算公式为1+等待时间/估计运⾏时间。

　　多级反馈法：是⽬前最常⽤的算法！它结合了FIFO、RR、优先级算法和SJF算法。该算法有多个队列，同⼀队列中的进程优先级相同，不同队列中进程优先级不同，不同队列拥有不同的时间⽚。　　策略驱动法：基于对各个⽤户的承诺。

　　最晚时间限调度：保证在每个进程必须完成的最晚时间限钱运⾏完该进程。

　　⼆级调度算法：在系统负载很重时，不是所有的进程建⽴就⽴即进⼊就绪态，有些进程建⽴起来后，进⼊后备队列。操作系统采⽤⼀个⼆级调度程序来决定进程在后备队列和就绪队列之间的转换。其中⼀级调度是从后备队列中选择进程使其转换为就绪态；另⼀级调度则是在就绪队列中选择⼀个执⾏。