基于面向对象操作系统开发平台(OSKit)的分析与程序设计(4)

　　作者：汤海京
　　
　　线程分析篇之线程调度
　　
　　本文是《基于面向对象操作系统开发平台(OSKIT)的分析与程序设计》的第四篇，作者将对线程调度进行分析。
　　线程调度是操作系统内核中的主要内容之一，它对整个操作系统的执行效率至关重要。OSKit当然也包括此项内容，而且由于线程的调度更加频繁，所以这部分在OSKit中的所占的比重要比它在UNIX中大许多。
　　
　　4.1 线程调度算法分析
　　
　　4.1.1 线程调度算法的总体描述
　　在分时系统中，内核给每个线程分配一段CPU时间，这段时间称为时间片，当这段时间过去之后，内核将调度另一个线程将其变为执行态。这就是所谓的时间片轮转法。
　　
　　与UNIX中的线程调度十分相似的是，OSKit的调度程序也采用了一种被称为多级反馈循环调度的算法，此种算法属于操作系统调度程序中最常用的一种。其核心思想是：内核给线程分一个时间片，并把该线程反馈回若干优先级队列中的某一个。一个线程在结束它之前，可能需要多次通过多次的"反馈循环"。当内核作上下文切换和恢复的时候，调度程序必须保证该线程从原来挂起的地方继续执行，否则这种调度算法是不能采用的。
　　
　　因此，我认为有必要向大家重申一下线程的上下文切换和恢复。首先，所谓线程的上下文是指由用户地址空间的内容、硬件寄存器的内容以及与该线程有关的内核数据结构组成的。更加严格的讲，线程的上下文是由它的用户级上下文、寄存器上下文以及系统级上下文组成。
　　
　　4.1.2 优先级逆转法
　　OSKit中采用了操作系统设计中比较精彩的优先级逆转算法，即在一个优先级较低的线程占有mutex的同时，另一个优先级较高的线程又来申请此mutex，这样，优先级较高的线程就被比他低的线程阻塞。
　　
　　此时我们引入了优先级逆转算法，也就是说，当上述情况发生的时候，线程调度程序就将优先级较低的线程的优先级提升至与较高优先级线程一样，这样可以使得占有mutex的线程快速执行。
　　
　　如果现在需要调度的线程不止两个的话，该算法允许进行递归，也就是说，那个优先级低的线程执行还需要另外一个mutex，而此mutex被另一个优先级更低的线程占有，所以，调度程序就依次提升优先级低的线程的优先级，这就是递归提升。
　　
　　但是，如过我们支持递归提升优先级的话，就可能出现死锁，所以我们又必须引入一套检验死锁的程序，这大大增加了操作系统核心的大小和系统的开销，但使得操作系统更加完善，并可以处理实时线程。
　　
　　4.2 pthread/pthread_scheduler.c
　　此源码文件包括了一套完整的线程调度机制，OSKit的全部线程调度算法都集中在了这个文件之中，通过阅读下面的函数分析，将使读者了解OSKit到底是用什么函数来具体实现线程调度的，并且能对前面讲述的概念有更深入的理解。
　　
　　4.2.1清空等待调度的线程队列
　　说明：为了能让大家真正从概念上了解此函数的作用，我想有必要先说明一下什么是线程等待队列。由于调度程序在操作系统中也是作为一个线程出现的，并且同一时间，它只能调度一个线程，所以就会造成有许多线程等待调度但无法接受调度的情况，OSKit提供的这个函数正弥补了这个缺陷，他将所有的等待调度的线程用链表的形式链接在一起，这就是所谓的等待调度的线程队列。显然，清空它实际上就是释放链表的指针。
　　static inline int posix_runq_empty ( void )
　　
　　4.2.2得到等待队列中优先级最高的线程的优先级
　　说明：当调度线程完成手头的工作，要对下一个线程进行调度时，就将面临一个问题，到底应该调度哪个等待调度的线程？OSKit提供的这个函数可以返回此时在等待队列中优先级最高的线程，供调度线程调度。
　　static inline int posix_runq_maxprio ( void )return PRIORITY_MAX - ( prio - 1 );
　　
　　4.2.3得到指向下一个要执行线程的指针
　　说明：当某个线程要转执行态的时候，调度程序并不知道这个线程挂起在了什么地方，我们可以通过调用OSKit提供的这个函数来找到指向要执行线程的指针。
　　static inline int posix_runq_onrunq ( pthread_thread_t *pthread )
　　
　　4.2.4在线程的执行队列的队尾追加一个线程
　　说明：将优先级最低的线程，或者是由于其他原因要最后执行的线程添加到线程执行队列的最后。
　　static inline void posix_runq_insert_tail ( pthread_thread_t *pthread )
　　
　　4.2.5在线程的执行队列的队头追加一个线程
　　说明：将优先级最高的线程或者是由于某种原因要现执行的线程添加到线程执行队列的最前面。
　　static inline void posix_runq_insert_head ( pthread_thread_t *pthread )
　　
　　4.2.6将等待队列中优先级最高的线程提出队列执行
　　说明：当操作系统要执行在线程执行队列里等待线程的时候，理所当然应该从头开始，我们考调有此函数来实现线程出对执行的功能。
　　static inline pthread_thread_t * posix_runq_dequeue ( void )
　　注： 返回指向下一个等待线程的指针
　　
　　4.2.7从等待队列中删除独占资源的线程
　　说明：为了使操作系统能够在总体最优化的前提下运行，OSKit规定不允许某一个线程长时间独占系统资源，如果发现此类时间，就可以调用这个函数来将独占资源的线程从执行队列中删除，以保持线程调度的公平合理。
　　static inline void posix_runq_remove ( pthread_thread_t *pthread )
　　
　　4.2.8此时用到的调度算法
　　说明：在前面的章节里，我曾经提到，线程的调度算法仿佛其属性一样，在初始化的时候就赋给了它，但它却是可以更改的，OSKit就是通过调用下面的这个函数来实现在线程创建之后来改变调度算法的。
　　
　　int posix_sched_schedules ( int policy )
　　 if ( policy == SCHED_RR || policy == SCHED_FIFO )
　　 return 1;
　　 return 0;
　　
　　
　　
　　
　　
　　4.2.9将一个线程变为运行态
　　说明：众所周知，线程在系统中一般有三种状态，OSKit通过调用该函数实现线程转执行态的功能。
　　int posix_sched_setrunnable ( pthread_thread_t *pthread )
　　
　　4.2.10终止该线程目前的调度算法
　　说明：这又是在线程创建之后改变其调度算法的一种函数调用，它的功能是中止该线程目前的调度算法。
　　
　　void posix_sched_disassociate ( pthread_thread_t *pthread )
　　{
　　 if (posix_runq_onrunq(pthread)) {
　　 /* * On the scheduler queue, so its not running. */
　　 posix_runq_remove ( pthread );
　　 }
　　}
　　
　　
　　
　　
　　
　　4.2.11为一个新的线程创建调度参数
　　说明：所谓调度参数就是调度程序决定是否执行某个线程的依据。例如，某用户态线程最近使用CPU时间的统计等。
　　
　　void posix_sched_init_schedstate ( pthread_thread_t *pthread,const struct
　　sched_param *param )
　　
　　
　　
　　
　　
　　4.2.12改变线程的调度状态
　　说明：如果其调度参数符合调度条件，调度程序会通过调用OSKit提供这个函数来改变此线程的调度状态，并将它转为准备调度态。此时该线程被锁住，而且要关中断
　　
　　int posix_sched_change_state ( pthread_thread_t *pthread , const struct
　　sched_param *param )
　　
　　
　　
　　
　　
　　4.2.13优先级迁移
　　说明：这是我在上面提到的优先级逆转法的具体实现，OSKit就是通过调用它来完成对线程优先级的动态变更的。
　　int posix_sched_priority_bump ( pthread_thread_t *pthread, int newprio )
　　
　　
　　注意：这只是暂时的，仅仅适用于实时线程
　　4.2.14基于某种原因，线程被送回等待队列
　　说明：当线程在操作系统中执行的时候，完全有可能由于用户的原因造成当线程执行完它的时间片后返回执行队列时，位置改变了。下边是我对OSKit提供的几种改变原因的注解。
　　
　　int posix_sched_dispatch ( resched_flags_t reason, pthread_thread_t
　　*pthread )
　　 switch (reason) {
　　case RESCHED_USERYIELD: posix_runq_insert_tail(pthread);
　　 /* 如果由用户造成线程为空闲态，则插入队尾 */
　　 case RESCHED_YIELD: posix_runq_insert_head(pthread);
　　/* 如果由用户造成线程为空闲态，则插入队尾 */
　　 case RESCHED_PREEMPT:
　　/* 根据线程拥有的优先级和其调度算法来具体分析 */
　　 if (pthread->policy == SCHED_RR) {
　　 if (--pthread->ticks == 0) {
　　 posix_runq_insert_tail(pthread);
　　 /* 如果是时间片轮转发调度且只有一个ticks，则插入队尾 */
　　 pthread->ticks = SCHED_RR_INTERVAL;
　　 }
　　 else
　　 posix_runq_insert_head(pthread);
　　 /* 虽然是时间片轮转法，但拥有的ticks不止一个，则插入对头 */
　　 }
　　else if (pthread->policy == SCHED_FIFO)
　　posix_runq_insert_head(pthread);
　　 /* 如果是先来先处理法，则插入对头 */
　　 case RESCHED_INTERNAL: /* 使线程变为空闲态 */
　　 default:
　　if (pthr