调度-Scheduling.ppt

例：A,B,C三周期性进程，周期为30/40/50ms，对应优先级33/25/20，每次CPU运行时间15/15/5ms； 例2(p139图)： 0 10 20 30 40 50 60 70 80 90 100 120 130 140 A B C 0 10 20 30 40 50 60 70 80 90 100 120 130 140 A B C A B A B RMS 0 10 20 30 40 50 60 70 80 90 100 120 130 140 A B C A B A B EDF C * 4.8 多处理机调度 4.8.1 与单处理机调度的区别 4.8.2 多处理器系统的类型 4.8.3 多处理器调度方法 返回 * 4.8.1与单处理机调度的区别 注重整体运行效率（而不是个别处理机的利用率） 更多样的调度算法 多处理机访问OS数据结构时的互斥（对于共享内存系统） 调度单位广泛采用线程 * 4.8.2 多处理器系统的类型 1)松散耦合多处理器系统(集群系统) 每台处理器有自己的内存和I/O，及自己的OS 2)主从多处理器系统 Master, Slave, 所有的系统调用由主控机完成； 从机仅执行主控机指派的计算任务； 3)紧密耦合多处理器系统 一组处理器共享内存，在一个OS的集中控制下工作； * 4.8.3 多处理器调度方法 1)给处理器分配进程： 静态分配：开销小，但可能忙闲不均； 动态分配：灵活，但同进程可能在不同处理器上执行，开销增大； 2)单个处理器上是否使用多道程序技术 3)分派进程： 方法越简单，开销越小，效率越高； 采用FCFS或带有静态优先级的FCFS合适。 * 4.8.3 多处理器调度方法 多处理器系统中的线程调度： 1）负载共享： FCFS：顺序排队； 最少线程数优先：最少线程数作业的线程优先级高； 抢占式最少线程数优先：抢占性； 2）成组调度： 一组相关线程同时调到一组处理器上； 3）专用处理器分配: 成组调度的特例，一个线程对应一个处理器； 4) 动态调度 * 4.9 Linux系统进程调度 4.9.1 Linux进程调度 1．调度方式 抢占式优先级 (多级反馈轮转法) * 2．调度策略 三种不同的调度策略 SCHED_FIFO适合于短实时进程。 SCHED_RR对应“时间片轮转法”，适合于每次运行需要较长时间的实时进程（200ms）。 SCHED_OTHER是传统的UNIX调度策略，适合于交互式的分时进程。 系统中规定，实时进程的优先级高于其他类型进程的优先级。另外，时间配额及nice值不影响实时进程的优先级。 4.9.1 Linux进程调度 * 4.9.1 Linux进程调度 3．调度时机 ①当前进程调用系统调用nanosleep( )或pause( )。 ② 进程终止。 ③ 在时钟中断。 ④ 当唤醒一个睡眠进程。 ⑤ 一个进程通过执行系统调用来改变调度策略或者降低自身的优先级。 4．调度算法 4.9.2 shell基本工作原理 它不属于内核部分，而是在核心之外，以用户态方式运行。 图4-17 shell命令基本执行过程 * 本章小结 三级调度 常用调度性能评价指标 常用调度算法，原理、适用范围、优缺点、是否抢占； FCFS、SJF、SRTF、RR、MFQ、HRRF 多处理器调度、实时调度、linux调度 习题-1 1．在所学的调度算法中，对所有进程和作业都是公平合理的调度算法是﹎﹎A﹎﹎；最有利于提高系统吞吐量的作业调度算法是﹎﹎B﹎﹎；能兼顾作业等待时间和作业执行时间调度算法是﹎﹎C﹎﹎；最有利于提高资源的使用率、能使短作业、长作业及交互作业用户都比较满意的调度算法是﹎﹎D﹎﹎；为实现人机交互作用应采用调度算法是﹎﹎E﹎﹎；能对紧急作业进行及时处理的调度算法是﹎﹎F﹎﹎。 A，B，C，D：(1)FCFS调度算法；(2)短作业优先调度算法；(3)时间片轮转法；(4)多级反馈队列调度算法；(5) 高响应比优先算法；(6)基于优先权的剥夺调度算法。1,2,5,4,3,6 * 2.假定在一个处理机上执行以下五个作业， 作 业 号 1 2 3 4 5 到达时间 0 2 4 6 8 运行时间 3 6 4 5 2 当分别采用FCFS、SJF(短作业优先)和HRRF（响应比高者优先）三种调度算法时，试问 : ⑴三种调度算法调度次序为﹎﹎A﹎﹎、﹎﹎B﹎﹎和﹎﹎C﹎﹎； A、B、C： (1)1 2 3 4 5 ; (2)5 1 3 4 2 ; (3)1 5 3 4 2 ; (4)1 2 5 3 4 ; (5)1 2 3 5 4 ; ⑵采用F