gonzui

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