第三章处理机的调度和死锁

第三章处理机的调度和死锁内容摘要：

a 非抢占轮转调度 当前进程 实时进程 实时进程要求调度 当前进程运行完成 b 非抢占优先权调度 调度时间 c 基于时钟中断抢占的优先权抢占调度 当前进程 实时进程 实时进程要求调度 抢占时刻（其它中断） b 立即抢占优先权调度 当前进程 实时进程 实时进程要求调度 时钟中断到达时 调度时间 调度时间 处理机调度与死锁  EDF（ earliest deadline first)算法 ٭ 根据任务的截止时间来确定任务的优先级 ٭ 截止时间越早，优先级越高 ٭ 可以是抢占式或非抢占式 处理机调度与死锁 最早截止时间优先 EDF例 1 3 4 2 1 3 4 2 1 2 3 4 t 开始截止时间 任务到达 任务执行 图 3－ 7 EDF算法用于非抢占调度方式 处理机调度与死锁 2. 最低松弛度优先 LLF算法 松弛度： ٭ 若 A进程需在 200ms时完成，其本身运行需要 100ms，当前时刻是 10ms，则 A的松弛度为： 200－ 100－ 10＝ 90 ٭ 主要用于可抢占的调度方式中 ٭ 例： A1 A2 A3 A4 A5 A6 A7 A8 B1 B2 B3 0 20 40 60 80 100 120 140 160 t 图 3－ 8 A/B任务每次必须完成的时间 处理机调度与死锁 最低松弛度优先 LLF算法 (2) A1(10) A2(10) A3(10) A4(10) t 0 10 20 30 40 50 60 70 80 t1=0 B1(20) B1(5) B2(15) B2(10) t1 t2 t3 t4 t5 t6 t7 t8 处理机调度与死锁  MPS和松弛耦合 MPS ٭ 紧密耦合 ▪ 共享 RAM和 I/O ▪ 高速总线和交叉开关连接 ٭ 松弛耦合 ▪ 独立 RAM和 I/O ▪ 通道和通信线路连接  ٭ 处理器是否结构相同 处理机调度与死锁  ٭ 静态分配 ٭ 动态分配 ▪ 可防止系统中多个处理器忙闲不均  SMP中进程分配方式 ٭ 进程调度在主处理器上执行 ٭ 有潜在的不可靠性 处理机调度与死锁 （线程）调度方式  ٭ 各个处理机自行在就绪队列中取任务。 ٭ 特点；简单，分布式调度，调度算法可采用前述方法，多个 CPU利用率都不错（不会闲） ٭ 但： ▪ 瓶颈问题，（单队列） ▪ 低效性；（需拷贝现场） ▪ 线程切换频繁（当线程合作时 ,各线程并行的条件不容易满足） 处理机调度与死锁 优点： （ 1）对相互合作的进（线）程组调度，可以减小切换，减小系统开销。 （ 2）每次分配一组 CPU，减少了调度频率。 分配时间 （ 1）面向程序 （ 2）面向线程：使处理机利用率更高。 处理机调度与死锁 应用程序A 应用程序 B Cpu1 线程 1 线程 1 Cpu2 线程 2 空闲 Cpu3 线程 3 空闲 Cpu4 线程 4 空闲 时间 1/2 1/2 浪费 % 应用程序A 应用程序 B Cpu1 线程 1 线程 1 Cpu2 线程 2 空闲 Cpu3 线程 3 空闲 Cpu4 线程 4 空闲 时间 4/5 1/5 浪费 15% 处理机调度与死锁 引入：多处理机系统，每个处理已不再属宝贵资源。 特点：每个进（线）程专用处理机，使其切换小，提高效率。 主要用于大型计算，实时系统 处理机调度与死锁 。 一、竞争资源引起死锁。 ٭ 1．可剥夺（ CPU、内存，）和非剥夺性（打印机，磁带机）资源 ٭ 2．竞争非剥夺性资源 —— 可造成死锁 p1 p2 R1 R2。