3 处理机调度和死锁3 处理机调度和死锁.ppt

(Scheduling and Deadlock) 二、进程调度中的三个基本机制 抢占方式（Preemptive mode） 处理机三级调度图： 3.2.2 选择调度方式和调度算法的若干准则 3.3 调度算法 3.3.2 高优先权优先调度算法 3.3.3 基于时间片的轮转调度算法 ①当时间片很大时，每个进程得到比完成该进程还要多的处理机时间，此时轮转调度模式退化为先来先服务模式。 ②当时间片非常小时，处理器的转换开销就成了决定因素，系统性能降低，大多数时间都消耗在处理机的转换上，只有少许用在用户的计算上。 图：多级反馈队列 Scheduling of a Real-Time Process Five Aperiodic Tasks 作业: 某多道程序系统配有四台磁带机,并有足够大的内存最多可同时处理三道作业,现有一作业序列如下: 一、资源的概念 OS是计算机系统中资源的管理者，而进程是竞争资源的基本单位，故对系统中所有进程的资源分配工作，都由OS完成。 研究资源分配时，我们必须搞清该资源是可以被几个进程同时使用，还是只能为一个进程使用，资源的不同使用性质正是引起系统死锁的原因。 根据资源性质：可剥夺（抢占）和不可剥夺（抢占）资源。 可抢占资源—指资源的占有进程虽然需要使用该资源，但另一个进程却强行把资源从占有者进程处抢来。 不可抢占资源—指只有占用者进程不再需要使用该资源而主动释放资源外，其它进程不得在占有者进程使用资源过程中强行抢占。 二、死锁的定义 死锁Deadlock：是计算机系统中多道程序并发执行时，两个或两个以上的进程由于竞争资源而造成的一种互相等待的现象（僵局），如无外力作用，这些进程将永远不能再向前推进。 陷入死锁状态的进程称为死锁进程，所占用的资源或者需要它们进行某种合作的其它进程就会相继陷入死锁，最终可能导致整个系统处于瘫痪状态。 三、产生死锁的原因 1 竞争资源。当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁； 2 进程推进的顺序不当 。进程在运行过程中，请求和释放资源的顺序不当，导致进程的死锁。 竞争资源 1 竞争非剥夺性资源： 2 竞争临时性资源 生产者—消费者问题 avail－生产者用信号量，记录缓冲区空单元个数 Full—消费者信号量，记录产品个数。 Mutex—互斥信号量。 deposit( data) remove (data) begin begin p(avail) p(full) p(mutex) p(mutex) 送数据入缓冲区某 取缓冲区中某单元 单元 数据 v(full) v(avail) v(mutex) v(mutex) end end 在前述若pv操作使用不当,会引起死锁。把生产者进程两个p操作次序调换一下,先执行P(mutex),后执行P(avail) P (mutex)互斥 P (avail)判断缓冲区满不能送,从消费者执行。 那么当缓存区满且消费者此时不再临界区中,执行到互斥P(mutex)后,消费者进程想进入临界区,但被阻塞在外。 若生产者希望进入临界区,也被阻塞,于是两个进程无限止地相互等待对方来唤醒自己,两个进程陷入死锁。 互斥（ Mutual exclusion ）条件：一个资源一次只能被一个进程所使用，即是排它性使用。 不可抢占（ No preemption ）条件：一个资源仅能被占有它的进程所释放，而不能被别的进程强占。 请求和保持（ Hold-and-wait ）条件：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。 环路等待（ Circular wait ）条件：当每类资源只有一个时，在发生死锁时，必然存在一个进程