《操作系统教程》第2章 处理器.ppt

* 3.O(1)调度算法(1) * O(1)调度算法(2) task_t *prev,*next; runqueue *rq; prio_array_t *array; int idx; prev = current; //保存当前进程 rq = this_rq( ); //当前运行队列 array = rq－＞active; if (unlikely(!array－＞nr_active)) { //运行队列active变成空 rq－＞active = rq－＞expired; //活跃、过期数组切换 rq－＞expired = array; array = rq－＞active; rq－＞expired_timestamp = 0; //进程耗完时间片事件的时间清0 rq－＞best_expired_prio = MAX_PRIO; //修改过期队列最高优先级 } else idx = sched_find_first_bit(array－＞bitmap); //从active队列选择进程 queue = array－＞queue + idx; next = list_entry(queue－＞next,task_t,run_list); … //任务切换 * O(1)调度算法(3) 新调度程序减少对循环的依赖，活跃数组内的可执行队列上的进程都还有时间片剩余；过期数组内的可执行队列上的进程都耗尽时间片。 当某进程的时间片用完时，重新计算它的时间片，并被移至过期数组。 数组是通过指针进行访问的，活跃和过期数组之间来回切换所用的时间就是交换指针需要的时间。 * 4. 负载平衡(1) load_balance（）函数 找最繁忙的可运行队列，该队列中就绪进程数目最多，如果没有哪个可运行队列中就绪进程数目比当前可运行队列中的就绪进程数目多25％或以上，就结束平衡负载处理。 找最繁忙的可运行队列，从中选择一个优先级数组以便抽取就绪进程，最好是过期数组，因为那里面的就绪进程已经有相对较长时间没有运行，很可能不在处理器的高速缓存中。如果过期数组为空，那就只能选活跃数组。 * 负载平衡(2) 找到含有进程且优先级最高的链表，把优先级高的就绪进程平均分散开来。 分析找到的所有优先级相同的就绪进程，选择一个不是正在执行，也不会因为处理器相关性而不可移动，且不在高速缓存中的进程。如果有进程满足这些条件，便将其从最繁忙的队列中抽取到当前队列。 只要可运行队列之间仍然不均衡，重复上面步骤，继续从繁忙队列中抽取进程到当前队列，最终会消除不平衡局面。 * 5.用户抢占和内核抢占 Linux2.6完整地支持内核抢占，只要重新调度是安全的，内核就可在任何时间抢占正在运行的任务。 为了支持内核抢占所作的第一处修改是为进程引入preempt_count计数器，其初值为0，每当使用锁的时候数值加1，释放锁的时候数值减1，当数值为0时，内核就可执行抢占。 内核抢占代码使用自旋锁作为非抢占区域的标记，如果一个自旋锁被持有，内核便不能抢占。 内核代码需要允许或禁止内核抢占，可通过preempt_disable( )和preempt_enable( )实现。 * 2.10 Windows 2003调度算法 处理器调度的对象是线程，也称线程调度。 实现了基于优先级抢先式的多处理器调度系统，系统总是运行优先级最高的就绪线程。 线程可在任何可用处理器上运行，但可限制某线程只能在某处理器上运行，亲合处理器集合允许用户线程通过Win32调度函数选择它偏好的处理器。 * 时间配额 线程被调度运行时，可运行一个被称为时间配额（quantum）的时间。 时间配额是允许线程连续运行的最大时间长度，随后系统会中断线程运行，判断是否需要降低该线程的优先级，查找是否有其他高优先级或相同优先级的线程等待运行。 由于抢先式调度特征，一个线程的一次调度执行可能并没有用完它的时间配额就被抢先。 * 线程调度时机 线程调度出现在DPC/线程调度中断优先级，线程调度触发事件有四种： 1）一个线程进入就绪状态，如一个刚创建的新线程或一个刚结束等待状态的线程。 2）一个线程由于时间配额用完而从运行状态转入退出状态或等待状态。 3）一个线程由于调用系统服务而改变优先级或被系统本身改变其优先级。 4）一个正在运行的线程改变了它的亲合处理器集合。 * 线程优先级 使用32个线程优先级，范围从0到31，分成三部分： 实时优先级（优先数31-16）：用于通信任务和实时任务。实时优先数线程的优先数不可变，一旦就绪线程的实时优先数比运行线程高，它将抢占处理器运行。 可