蝎子的养殖技术及市场前景:CPU 调度

CPU调度算法 后备状态 完成状态 就绪 阻塞 执行 I/O完成 I/O请求 时间片完 作业状态间转换

先进先出调度算法 基本原则：按照作业提交或进程进入就绪队列的先后次序来选择。调度方式：不可抢占。缺点：比较有利于长作业，而不利于短作业。 有利于CPU繁忙的作业，而不利于I/O繁忙的作业。应用：不作为主要的调度策略，尤其不能用于分时和实时系统。常结合其他调度策略使用。 可用于作业调度和进程调度

0 4 4 4 7 6 先来先服务（先进先出）： 7 12 10 12 14 11 14 18 14

原则：从就绪队列中挑选所需运行时间最短的进程进入主存运行。调度方式：“非抢占”策略。 应用：不适用于分时系统优点：比FCFS改善平均周转时间和平均带权周转时间，缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业的执行时间，从而影响调度性能。 短进程优先调度算法

0 4 4 1 短作业/短进程优先（SJF/SPF）： 4 6 3 3/2 6 9 8 8/3 9 13 9 9/4 13 18 16 16/5 40/5 2.1

原则：将系统中所有的就绪进程按照FIFO原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。进程可以未使用完一个时间片，就出让CPU（如阻塞）。调度方式：可抢占策略应用：用于进程调度，特别适用于分时系统 时间片轮转算法

A B C D E A B C D E A B C E A C E C 0 1 2 3 4 9 12 15 17 18 15 15/4 11 11/3 16 16/5 6 6/2 13 13/4 12.2 2.12 基于时间片的轮转调度算法

就绪队列1 基于时间片的轮转调度算法 就绪队列2 就绪队列3 就绪队列n 调度方式 按FIFO原则排队等待调度 尚未完成转入第二队列的末尾，按FIFO原则等待调度 采取按时间片轮转的方式运行 因等待而放弃CPU后，进入阻塞队列，一旦等待的事件发生，则回到原来的就绪队列

原则：按照进程的优先级大小来调度，高优先级进程得到优先处理。应用：可用于作业调度和进程调度（主要）用于进程调度时，可分为： “非抢占”的优先级调度法 “可抢占”的优先级调度法：UNIX系统进程调度算法。 优先级调度算法 优先级的确定方式：静态优先级：优先级在进程创建时确定，且在进程整个运行期间保持不变。动态优先级：在创建进程时赋予优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能。 在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行； 进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU。

0 4 4 1 4 8 4 1 8 11 10 10/3 11 16 14 14/5 16 18 15 15/2 9.4 2.93 高优先权优先调度算法 静态优先权，非抢占式（1为高优先权）

多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。优点：为提高系统吞吐量和缩短平均周转时间而照顾短进程为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程不必估计进程的执行时间，动态调节 设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。优先级和时间片相结合：每个队列执行时间片的长度不同，规定优先级越低则时间片越长。按FIFO原则调度；新进程进入内存后，先投入队列1的末尾。动态优先级：若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FIFO算法调度；如此下去，降低到最后的队列，则按"时间片轮转"算法调度直到完成。仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。 基本实现 多级反馈队列算法

仅有进程调度的调度队列模型 进程调度 进程完成 等待事件 交互用户 时间片完

调度队列模型 进程调度 进程完成 时间片完 … … … 与上一模型的主要区别：就绪队列的形式； 设置多个阻塞队列

同时具有三级调度的调度队列模型 进程调度 中级调度 等待事件 进程完成 时间片完 作业调度 交互型作业 批量作业 挂起 事件出现 事件出现

原则：引入动态优先级机制，响应比高者得到优先调度。动态优先数为： 等待时间+要求的服务时间 要求的服务时间调度方式：“非抢占”策略。缺点：调度前，需计算优先数，开销大。 最高响应比优先调度算法 优点：是一种较好的折中算法。如果作业的等待时间相同，则要求的服务时间越短，其优先数越高，因此，有利于短作业。当要求的服务时间相同时，作业的优先数取决于等待时间，因而实现了FIFO。对长作业，当其等待时间越长，其优先数会越高。

最短剩余时间优先算法 短作业优先调度算法的变型。原则：让运行到作业完成时所需运行时间最短的进程优先得到处理，包括新进入系统的进程。调度方式：“可抢占”策略（新进入系统的进程有可能抢占处理机）。优点：降低作业的平均等待时间； 缺点：估计运行时间；系统开销大。应用：可用于分时系统。

所谓调度就是选出待分派的作业或进程。 处理机调度的主要目的就是为了分配处理机。 在不同的操作系统中所采用的调度方式并不完全相同。有的系统中仅采用一级调度，而有的系统采用两级或三级，并且所用的调度算法也完全可能不同。 一般说来，作业从进人系统到最后完成，可能要经历三级调度：高级调度、中级调度和低级调度。 （1）高级调度：又称作业调度。其主要功能是根据一定的算法，从输人的一批作业中选出若干个作业，分配必要的资源，如内存、外设等，为它建立相应的用户作业进程和为其服务的系统进程（如输人、输出进程），最后把它们的程序和数据调人内存，等待进程调度程序对其执行调度，并在作业完成后作善后处理工作。 （2）中级调度：为了使内存中同时存放的进程数目不至于太多，有时就需要把某些进程从内存中移到外存上，以减少多道程序的数目，为此设立了中级调度。特别在采用虚拟存储技术的系统或分时系统中，往往增加中级调度这一级。所以中级调度的功能是在内存使用情况紧张时，将一些暂时不能运行的讲程从内存对换到外存上等待。当以后内存有足够的空闲空间时，再将合适的进程重新换人内存，等待进程调度。引人中级调度的主要目的是为了提高内存的利用率和系统吞吐量。它实际上就是存储器管理中的对换功能。 （3）低级调度：又称进程调度。其主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。执行低级调度功能的程序称做进程调度程序，由它实现CPU在进程间的切换。进程调度的运行频率很高，在分时系统中往往几十毫秒就要运行一次。进程调度是操作系统中最基本的一种调度。在一般类型的操作系统中都必须有进程调度，而且它的策略的优劣直接影响整个系统的计能。