嵌入式操作系统内核原理和开发（实时调度）

    和很多通用的操作系统相比， 实时操作系统有自己的一个特点，那就是实时调度。通用操作系统的线程优先级一般是可以变化的，而实时系统的线程优先级却是不变的。之所以这么设计，是为了保证高优先级的任务在第一时间获得调度，这样才能保证调度的实时性。因为实时系统是严格按照优先级搞定调度的，所以不管什么时候，我们只要寻找到最高优先级的任务即可。

    rawos系统可以支持256个优先级，对任务的创建个数也没有限制，所以就会出现多个任务共享一个优先级的情况。因此系统本身对同优先级的任务分配了定额的时间片，一旦该任务时间片用完，就会被放到优先级的末尾，直到获得下一次的调度机会，下面的代码就说明了这一情况，它是在时钟中断的时候被调度的，

void caculate_time_slice()
 {
    RAW_TASK_OBJ   *task_ptr;
    LIST *head;
    
    RAW_SR_ALLOC();
 
    task_ptr = raw_task_active;
    head = &raw_ready_queue.task_ready_list[task_ptr->priority];
     
    RAW_CRITICAL_ENTER();
                           
    if (is_list_empty(head)) {
 
        RAW_CRITICAL_EXIT();
        return;
    }
 
    /*there is only one task on this ready list, so do not need to caculate time slice*/
    if (head->next->next == head)  {
        
        RAW_CRITICAL_EXIT();
        return;
        
    }
 
    if (task_ptr->time_slice) {
        task_ptr->time_slice--;
    }
 
    /*if current active task has time_slice, just return*/
    if (task_ptr->time_slice) {               
        RAW_CRITICAL_EXIT();
        return;
    }
 
    /*Move current active task to the end of ready list for the same priority*/
    move_to_ready_list_end(&raw_ready_queue, task_ptr);
 
    /*restore the task time slice*/ 
    task_ptr->time_slice = task_ptr->time_total;  
    
    RAW_CRITICAL_EXIT();
 }

    上面说的是一个优先级下面有多个任务的情况，如果优先级本身只有一个任务，那么就很抱歉了，下面还得继续运行这个任务。另外，我们在windows上面编程的时候喜欢暂时释放线程的运行权利，调用sleep（0）即可，那么这在rawos上是怎么实现的呢，

RAW_U16  raw_sleep(RAW_U32  dly) 
 {
  RAW_U16 error_status;
  
  RAW_SR_ALLOC();
 
  #if (RAW_TASK_FUNCTION_CHECK > 0)
  
  if (raw_int_nesting) {
    
    return RAW_NOT_CALLED_BY_ISR;
  }
  #endif    
    
  RAW_CRITICAL_ENTER();
 
  if  (dly) {
 
    /*system is locked so task can not sleep just return immediately*/
    if (raw_sched_lock) {   
      RAW_CRITICAL_EXIT();  
      return RAW_SCHED_DISABLE;
    }
 
    raw_task_active->task_state = RAW_DLY;
 
    tick_list_insert(raw_task_active, dly);
               
    remove_ready_list(&raw_ready_queue, raw_task_active);
  }
  
  else {  
    /*make current task to the end of ready list*/
     move_to_ready_list_end(&raw_ready_queue, raw_task_active);
  }
 
  RAW_CRITICAL_EXIT();
 
  raw_sched();   
 
  if (dly) {
    /*task is timeout after sleep*/
    error_status = block_state_post_process(raw_task_active, 0);
  }
 
  else {
    
    error_status = RAW_SUCCESS;
 
  }
  
  return error_status;
 }

    通过的上面的代码，我们可以看到其实系统啥也没干，只是把任务方法放到优先级的链表末尾了。因为我们的系统需要实时调度，所以即使把使用权出让出来，也不可能让低优先的任务运行，只能让同优先级的其他任务运行了。当然，同优先级没有其他任务的时候，只好它自己继续玩了。说了这么多，我们看看系统是怎么调度的，

void raw_sched()
 {
  RAW_SR_ALLOC();
 
  /*if it is in interrupt or system is locked, just return*/ 
  if (raw_int_nesting || raw_sched_lock) {              
      return;                                             
  }
  
  RAW_CRITICAL_ENTER();
               
  
  get_ready_task(&raw_ready_queue);
 
  /*if highest task is currently task, then no need to do switch and just return*/
  if (high_ready_obj == raw_task_active) {                 
      RAW_CRITICAL_EXIT();                                     
      return;
  }
   
  CONTEXT_SWITCH();                                           
  RAW_CRITICAL_EXIT();
 
 }

    这个函数看上去很长，其实最重要的部分就是get_ready_task这个函数，它的目的就是寻找到当前最高优先级下面的任务，大家看看代码就明白了，

void get_ready_task(RAW_RUN_QUEUE *rq)
 {
  LIST *node ;
  RAW_S32 highest_pri =  rq->highest_priority;
  /*Highest task must be the first element on the list*/
  node = rq->task_ready_list[highest_pri].next;
 
  high_ready_obj = list_entry(node, RAW_TASK_OBJ, task_list);
  
 }

    所以，实时系统的核心就是寻找到那个最高优先级就可以了。在实时系统上面，我们一般用bitmap表示优先级，如果对应的优先级存在，那么该位置1，反之置0。那么什么情况下，会发生优先级的改变呢？其实就两种情况，一种是需要把任务加入调度队列的时候，还有一种就是把任务清除出调度队列的时候。

void add_ready_list(RAW_RUN_QUEUE *rq, RAW_TASK_OBJ *task_ptr)
 {
  /*if task priority is equal current task priority then add to the end*/
  if (task_ptr->priority == raw_task_active->priority) {
    add_ready_list_end(rq, task_ptr);
  }
  /*if not add to the list front*/
  else {
    add_ready_list_head(rq, task_ptr);
  }
  
 }
 
 
 void remove_ready_list(RAW_RUN_QUEUE *rq, RAW_TASK_OBJ *task_ptr)
 {
 
  RAW_S32   i;
  RAW_S32  priority = task_ptr->priority;
 
  list_delete(&task_ptr->task_list);
 
  /*if the ready list is not empty, we do not need to update the highest priority*/
  if (!is_list_empty(&rq->task_ready_list[priority]) ) {
    return;
  }
 
  bit_clear(rq->task_bit_map, priority);
 
  /*If task priority not equal to the highest priority, then we do not need to update the highest priority*/
  if (priority != rq->highest_priority) {
    return;
  }
  
  i =  bit_search_first_one(rq->task_bit_map, priority,  CONFIG_RAW_PRIO_MAX - priority);
  /*Update the next highest priority task*/
  if (i >= 0) {
    rq->highest_priority = priority + i;
  } 
 
  else {
    
    #if (CONFIG_RAW_ASSERT > 0)
    RAW_ASSERT(0);
    #endif
 
  }
  
 }

    加入调度队列的情况考虑的比较少，我们只需要判断当前的最高优先级和加入任务优先级之间的关系即可。如果新加入的任务优先级高，那么优先级发生了改变；反之什么也不需要做。反之删除任务则比较复杂一些，我们需要判断移除的任务是不是最高优先级，不是还好处理，如果清除出去的任务正好是最高优先级，我们就需要从bitmap中寻找下一个最高优先级了，这个函数就是bit_search_first_one。函数第一个参数是bitmap数组，第二个参数是当前最高优先级，第三个参数是剩下的优先级总数，返回值为次优先级距离当前最高优先级的偏移值。

/*For 32 bit cpu*/
 RAW_S32 bit_search_first_one(RAW_U32 *base, RAW_S32 offset,  RAW_S32 width)
 {
     register RAW_U32 *cp, v;
     register RAW_S32 position;
 
     cp = base;
     cp += offset >> 5;
    
     if (offset & 31) {
 #if (CONFIG_RAW_LITTLE_ENDIAN > 0)
         v = *cp & ~(((RAW_U32)1 << (offset & 31)) - 1);
 #else
      v = *cp & (((RAW_U32)1 << (32 - (offset & 31))) - 1);
 #endif
     } 
    
  else {
         v = *cp;
     }
 
     position = 0;
     while (position < width) {
         if (v) {            /* includes 1 --> search bit of 1 */
             if (!position) position -= (offset & 31);
            
 #if  (CONFIG_RAW_LITTLE_ENDIAN > 0)
 
       if (!(v & 0xffff)) {
                 v >>= 16;
                 position += 16;
             }
             if (!(v & 0xff)) {
                 v >>= 8;
                 position += 8;
             }
             if (!(v & 0xf)) {
                 v >>= 4;
                 position += 4;
             }
             if (!(v & 0x3)) {
                 v >>= 2;
                 position += 2;
             }
             if (!(v & 0x1)) {
                 ++position;
             }
             
 #else
            
      if (!(v & 0xffff0000)) {
        v <<= 16;
        position += 16;
      }
      
      if (!(v & 0xff000000)) {
        v <<= 8;
        position += 8;
      }
      
      if (!(v & 0xf0000000)) {
        v <<= 4;
        position += 4;
      }
      
      if (!(v & 0xc0000000)) {
        v <<= 2;
        position += 2;
      }
      
      if (!(v & 0x80000000)) {
        ++position;
      }
            
 #endif
             if (position < width) {
              
                 return position;
                
             } else {
          
                 return -1;
                
             }
         } else {              /* all bits are 0 --> 1 Word skip */
             if (position) {
                 position += 32;
             } else {
                 position = 32 - (offset & 31);
             }
             v = *++cp;
         }
     }
 
     return -1;
 }

    这个函数其实有两个，其中一个是32位cpu，另一个是为8位cpu准备的。当然，我们这里看到的是前一种情形，这里作者还考虑了大小端的情况，小端就是x86之类的cpu，大端就是powerpc之类的cpu，主要是指字节序不同而已。按照作者的说法，这是目前最快的查找方法，能比ucos查找表的方法快多少，我不太清楚，估计只能按照系统设备性能的平均值来估算了，别的还真不好说。要是本身用户侧的代码写的比较差，那么争取的这点调度性能其实意义也不大。