The Tick List

Since its initial release, µC/OS-III iterated through several methods of managing task delays and timeouts. V3.04.00 introduced the concept of a delta-list, which reduced the overhead involved in checking for timeouts and expired delays; however, that initial implementation maintained two separate lists for tracking timeouts and delays. V3.07.00 merged the two lists into one, called OSTickList, in order reduce memory consumption and simplify some of the internals details involved with maintaining multiple tick lists.

Figure - Empty Tick List

(1) This list contains all the tasks (OS_TCBs) that are waiting for time to expire or are pending on an object with a timeout.

(2) The .NbrEntries field in each list contains the current number of entries in the list and is thus updated each time an OS_TCB is either inserted or removed from the list. This field is useful when debugging and serves no other purpose otherwise. This field is only present when OS_CFG_DBG_EN is set to 1 in os_cfg.h.

(3) The .NbrUpdated field in each list contains the number of OS_TCBs updated whenever a tick ISR occurs. This field is useful when debugging and serves no other purpose otherwise. This field is only present when OS_CFG_DBG_EN is set to 1 in os_cfg.h.

(4) The .TCB_List field contains a pointer to a doubly linked list of OS_TCBs that are placed in the list.

(5) OSTickCtr simply keeps track of the number of ticks processed by the OS since startup. The points at which ticks are processed will differ based on the tick mode selected. OSTickCtr may be changed by calling OSTimeSet(), though this is usually best avoided, especially in Dynamic Tick Mode.


Tasks are automatically inserted into the tick list when the application programmer calls an OSTimeDly???() function, or when an OS???Pend() call is made with a non-zero timeout value. A task is usually removed from the tick list by the tick ISR once its delay or timeout has expired. It may also be removed if the time delay is resumed or the pend with timeout is aborted.

Example

Using an example to illustrate the process of inserting a task in the delayed tick list. Here, we assume that the OSTickListDly list is completely empty as shown in the figure above. A task is placed in the tick list when OSTimeDly() is called and let’s assume OSTimeDly() is called as follows:


              :
              OSTimeDly(10, OS_OPT_TIME_DLY, &err);
              :


Referring to the µC-OS-III API Reference Manual, we know that this action indicates that µC/OS-III has to delay the current task for 10 ticks. Since this is the first task inserted in the tick list, the .TickNextPtr and .TickPrevPtr of the task’s OS_TCB both point to NULL.

Figure - Inserting a task into the tick list


OSTimeDly() takes care of a few other details. Specifically, the task is removed from µC/OS-III’s ready list (described in The Ready List) since the task is no longer eligible to run (because it is waiting for time to expire). Also, the scheduler is called because µC/OS-III will need to run the next most important ready-to-run task.

If the next task to run also happens to call OSTimeDly() “before” the next tick arrives and calls OSTimeDly() as follows:


              :    
              OSTimeDly(7, OS_OPT_TIME_DLY, &err);
              :


µC/OS-III will place this new task at the head of the list and replace the "remaining" counts for the first task to 3. In other words, the timeout for the first task is the sum of the two values (7+3).

Figure - Inserting a second task in the delayed tasks tick list


When the tick ISR executes, it increments OSTickCtr and, if the tick list is not empty, decrements only the .TickRemain of the OS_TCB at the head of the list. When .TickRemain reaches zero, the OS_TCB is removed from the list and placed in the ready-list. Then, the .TickRemain field of the next OS_TCB is examined and if the .TickRemain field for that task is also zero, that task is also placed in the ready list. µC/OS-III continues like this until the .TickRemain of an OS_TCB has a non-zero value or, it reaches the end of the list.

The .NbrUpdated field of the tick list contains the number of OS_TCBs removed from the list whenever a tick occurs. Of course, if .TickRemain is non-zero, .NbrUpdated would also be zero because on that specific tick, no task would be made ready-to-run.