第3章处理机调度和死锁详解.ppt

1.剥夺资源 法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程 2.撤销进程 ：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源 * 前两种算法主要用于宏观调度，说明怎样选择一个进程或作业开始运行，开始运行后的做法都相同，即运行到结束或阻塞，阻塞结束时等待当前进程放弃CPU?。本算法主要用于微观调度，说明怎样并发运行，即切换的方式；设计目标是提高CPU利用率。 其基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率； 主要使用于分时系统 * 系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，停止该进程的执行并将其送往就绪队列的末尾。这样就可以保证就绪队列中所有进程在一定时间内均能获得一时间片的处理机执行时间，也就是说系统能在给定的时间内响应所有用户的请求。具体步骤如下： * 前面介绍的各种进程调度的算法都有一定的局限性。这里介绍一种目前被公认为较好的进程调度算法——多级反馈队列调度算法。 多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合和发展 * （2）当一个新进程进入内存后，首先将它放入第一个队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……如此下去，当一个长作业（进程）从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。 （3）仅当第一队列空闲时，调度程序才调度第二队列中的进程运行，仅当第1~（i-1）队列均空时，才会调度第i 队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列（第1~（i-1）中的任何一个队列），则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。 * 大多属于较小的交互性作业，只要能使作业在第一队列的时间片内完成，便可令用户满意。 周转时间仍然较短，至多在第二到三队列即可完成。 将依次在1~n级队列中轮转执行，不必担心作业长期得不到处理。 * * * 由于在实时系统中都存在着若干个实时进程或任务，它们用来反应或控制某个（些）外部事件，往往带有某种程度的紧迫性，因而对实时系统中的调度提出了某些特殊要求，前面所介绍的多种调度算法，并不能很好的满足实时系统对调度的要求，为此，需要引入一种新的调度，即实时调度。 在实时系统中，时间起着至关重要的作用，即对每一个实时任务，都有一个时间约束要求，如在何时之前必须开始处理或在何时之前必须处理完毕。在一个实时系统中，可能有多个实时任务，每个实时任务都有其时间约束。实时调度的目标就是合理地安排这些任务的执行次序，使之满足各个实时任务的时间约束条件。 * 在实时系统中，硬实时任务和软实时任务都联系着一个截止时间。为保证系统能正常工作，实时调度必须满足实时任务对截止时间的要求，为此，实现实时调度应具备下列条件： * 为了实现实时调度，系统应向调度程序提供有关任务的下述信息： * 在实时系统中，通常都有多个任务，若处理机的能力不够强，则可能会出现某些实时任务不能得到及时处理导致发生难以预料的后果。 * 当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样可满足该硬实时任务对截止时间的要求。但此种机制较复杂。 小的实时系统: 如能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和对任务调度时所花费的系统开销。 （1）基于时钟中断的抢占式优先调度——在某实时任务到达后，如果它的优先级高于当前任务的优先级，这时并不立即抢占当前任务的处理机而是等到时钟中断发生时，才剥夺当前任务的执行， （2）立即抢占式——一旦出现外部中断，只要 当前任务未处于临界区，便能立即剥夺当前任务的执行。 * * 为保证要求较高的硬实时任务能及时运行，在实时系统中还应具有快速切换机制，以保证任务的快速切换。需要以下两种能力： 对外部中断的快速响应能力。要求系统具有快速硬件中断机构，便可在紧迫的外部事件请求中及时响应。 快速的任务分派能力。在完成任务调度后，便应进行任务切换，为提高速度，应使系统中的运行功能单位适当的小。 * 目前有许多实时调度算法，在常用的算法中简单介绍两种实时调度算法： * 该算法是根据任务紧急（或松弛）的程度，来确定任务的优先级。任务的紧急程度越高，为之赋予的优先级就越高。 * 在多