gonzui

    1: /*
    2:  *----------------------------------------------------------------------
    3:  *    T-Kernel 2.0 Software Package
    4:  *
    5:  *    Copyright 2011 by Ken Sakamura.
    6:  *    This software is distributed under the latest version of T-License 2.x.
    7:  *----------------------------------------------------------------------
    8:  *
    9:  *    Released by T-Engine Forum(http://www.t-engine.org/) at 2011/05/17.
   10:  *    Modified by T-Engine Forum at 2014/09/10.
   11:  *    Modified by TRON Forum(http://www.tron.org/) at 2015/06/01.
   12:  *
   13:  *----------------------------------------------------------------------
   14:  */
   15: 
   16: /*
   17:  *      ready_queue.h (T-Kernel/OS)
   18:  *      Ready Queue Operation Routine
   19:  */
   20: 
   21: #ifndef _READY_QUEUE_
   22: #define _READY_QUEUE_
   23: 
   24: #include <libstr.h>
   25: #include <sys/bitop.h>
   26: 
   27: /*
   28:  * Definition of ready queue structure
   29:  *      In the ready queue, the task queue 'tskque' is provided per priority.
   30:  *      The task TCB is registered onto queue with the applicable priority.
   31:  *      For effective ready queue search, the bitmap area 'bitmap' is provided
   32:  *      to indicate whether there are tasks in task queue per priority.
   33:  *      
   34:  *      Also, to search a task at the highest priority in the ready queue
   35:  *      effectively, put the highest task priority in the 'top_priority' field.
   36:  *      If the ready queue is empty, set the value in this field to NUM_PRI.
   37:  *      In this case, to return '0' with refering 'tskque[top_priority]',
   38:  *      there is 'null' field which is always '0'.
   39:  *
   40:  *      Multiple READY tasks with kernel lock do not exist at the same time.
   41:  */
   42: 
   43: #define BITMAPSZ        ( sizeof(UW) * 8 )
   44: #define NUM_BITMAP      ( (NUM_PRI + BITMAPSZ - 1) / BITMAPSZ )
   45: 
   46: typedef struct ready_queue {
   47:         INT    top_priority;              /* Highest priority in ready queue */
   48:         QUEUE  tskque[NUM_PRI]; /* Task queue per priority */
   49:         TCB    *null;                     /* When the ready queue is empty, */
   50:         UW     bitmap[NUM_BITMAP]; /* Bitmap area per priority */
   51:         TCB    *klocktsk;         /* READY task with kernel lock */
   52: } RDYQUE;
   53: 
   54: IMPORT RDYQUE   ready_queue;
   55: 
   56: /*
   57:  * Ready queue initialization
   58:  */
   59: Inline void ready_queue_initialize( RDYQUE *rq )
   60: {
   61:         INT    i;
   62: 
   63:         rq->top_priority = NUM_PRI;
   64:         for ( i = 0; i < NUM_PRI; i++ ) {
   65:                 QueInit(&rq->tskque[i]);
   66:         }
   67:         rq->null = NULL;
   68:         rq->klocktsk = NULL;
   69:         MEMSET(rq->bitmap, 0, sizeof(rq->bitmap));
   70: }
   71: 
   72: /*
   73:  * Return the highest priority task in ready queue
   74:  */
   75: Inline TCB* ready_queue_top( RDYQUE *rq )
   76: {
   77:         /* If there is a task at kernel lock, that is the highest priority task */
   78:         if ( rq->klocktsk != NULL ) {
   79:                 return rq->klocktsk;
   80:         }
   81: 
   82:         return (TCB*)rq->tskque[rq->top_priority].next;
   83: }
   84: 
   85: /*
   86:  * Return the priority of the highest priority task in the ready queue
   87:  */
   88: Inline INT ready_queue_top_priority( const RDYQUE *rq )
   89: {
   90:         return rq->top_priority;
   91: }
   92: 
   93: /*
   94:  * Insert task in ready queue
   95:  *      Insert it at the end of the same priority tasks with task priority
   96:  *      indicated with 'tcb'. Set the applicable bit in the bitmap area and
   97:  *      update 'top_priority' if necessary. When updating 'top_priority,'
   98:  *      return TRUE, otherwise FALSE.
   99:  */
  100: Inline BOOL ready_queue_insert( RDYQUE *rq, TCB *tcb )
  101: {
  102:         INT    priority = tcb->priority;
  103: 
  104:         tcb->slicecnt = 0;
  105: 
  106:         QueInsert(&tcb->tskque, &rq->tskque[priority]);
  107:         BitSet(rq->bitmap, priority);
  108: 
  109:         if ( tcb->klocked ) {
  110:                 rq->klocktsk = tcb;
  111:         }
  112: 
  113:         if ( priority < rq->top_priority ) {
  114:                 rq->top_priority = priority;
  115:                 return TRUE;
  116:         }
  117:         return FALSE;
  118: }
  119: 
  120: /*
  121:  * Insert task at head in ready queue
  122:  */
  123: Inline void ready_queue_insert_top( RDYQUE *rq, TCB *tcb )
  124: {
  125:         INT    priority = tcb->priority;
  126: 
  127:         QueInsert(&tcb->tskque, rq->tskque[priority].next);
  128:         BitSet(rq->bitmap, priority);
  129: 
  130:         if ( tcb->klocked ) {
  131:                 rq->klocktsk = tcb;
  132:         }
  133: 
  134:         if ( priority < rq->top_priority ) {
  135:                 rq->top_priority = priority;
  136:         }
  137: }
  138: 
  139: /*
  140:  * Delete task from ready queue
  141:  *      Take out TCB from the applicable priority task queue, and if the task
  142:  *      queue becomes empty, clear the applicable bit from the bitmap area.
  143:  *      In addition, update 'top_priority' if the deleted task had the highest
  144:  *      priority. In such case, use the bitmap area to search the second
  145:  *      highest priority task.
  146:  */
  147: Inline void ready_queue_delete( RDYQUE *rq, TCB *tcb )
  148: {
  149:         INT    priority = tcb->priority;
  150:         INT    i;
  151: 
  152:         if ( rq->klocktsk == tcb ) {
  153:                 rq->klocktsk = NULL;
  154:         }
  155: 
  156:         QueRemove(&tcb->tskque);
  157:         if ( tcb->klockwait ) {
  158:                 /* Delete from kernel lock wait queue */
  159:                 tcb->klockwait = FALSE;
  160:                 return;
  161:         }
  162:         if ( !isQueEmpty(&rq->tskque[priority]) ) {
  163:                 return;
  164:         }
  165: 
  166:         BitClr(rq->bitmap, priority);
  167:         if ( priority != rq->top_priority ) {
  168:                 return;
  169:         }
  170: 
  171:         i = BitSearch1_w(rq->bitmap, priority, NUM_PRI - priority);
  172:         if ( i >= 0 ) {
  173:                 rq->top_priority = priority + i;
  174:         } else {
  175:                 rq->top_priority = NUM_PRI;
  176:         }
  177: }
  178: 
  179: /*
  180:  * Move the task, whose ready queue priority is 'priority', at head of
  181:  * queue to the end of queue. Do nothing, if the queue is empty.
  182:  */
  183: Inline void ready_queue_rotate( RDYQUE *rq, INT priority )
  184: {
  185:         QUEUE  *tskque = &rq->tskque[priority];
  186:         TCB    *tcb;
  187: 
  188:         tcb = (TCB*)QueRemoveNext(tskque);
  189:         if ( tcb != NULL ) {
  190:                 QueInsert((QUEUE*)tcb, tskque);
  191: 
  192:                 tcb->slicecnt = 0;
  193:         }
  194: }
  195: 
  196: /*
  197:  * Put 'tcb' to the end of ready queue.
  198:  */
  199: Inline TCB* ready_queue_move_last( RDYQUE *rq, TCB *tcb )
  200: {
  201:         QUEUE  *tskque = &rq->tskque[tcb->priority];
  202: 
  203:         QueRemove(&tcb->tskque);
  204:         QueInsert(&tcb->tskque, tskque);
  205: 
  206:         tcb->slicecnt = 0;
  207: 
  208:         return (TCB*)tskque->next;     /* New task at head of queue */
  209: }
  210: 
  211: #endif /* _READY_QUEUE_ */