In the third issue, we introduced semaphores as a function for exclusion control between tasks when using shared resources, and T-Kernel provides not only semaphores but also mutexes.
However, the T-Kernel provides not only semaphores but also mutexes. The mutex provides a function for exclusion control between tasks as well as semaphores, and it supports a mechanism to prevent unbounded priority inversion that occurs with exclusion control.
目次
Temporary execution order reversal in exclusion control
In T-Kernel, each task is given a priority level, and the task with the highest priority is executed first. The process of determining the next task to be executed in this way is called priority-based scheduling.
In priority-based scheduling, the high-priority task always has priority in execution, but when exclusive control of shared resources is performed between tasks, the high-priority task is temporarily placed in a waiting state, so the priority of the task and the order of task execution may not match.
Listing 1 shows an example program in which the execution order of a high-priority task and a low-priority task are reversed.
High-priority Task A executes a process that takes 5 seconds once every 10 seconds. After processing, the program enters a state of waiting for waking up in 5 seconds. A low-priority task C repeatedly executes a process that takes 5 seconds without transitioning to the wakeup call state. Since Task A and Task C share resources (loop variables in Listing 1), we need to use exclusion control (*1). This is achieved using semaphores.
(*1) There is no special meaning of sharing a loop variable in Listing 1. It is implemented in this way as an example to make it easier to understand that sharing some resources will not work properly without exclusion control.
【List 1】
#include <basic.h>
#include <tk/tkernel.h>
#include <tm/tmonitor.h>
IMPORT void doWorkA( void );
IMPORT void doWorkC( void );
INT i; /* Shared by Task A and Task C */
ID semid; /* semaphore ID */
void taskA( INT stacd, VP exinf )
{
while(1){
tm_putstring( (UB*)"A enters critical section!¥n" );
tk_wai_sem(semid, 1, TMO_FEVR);
doWorkA(); /* Processing for Task A */
tm_putstring( (UB*)"A exits critical section!¥n" );
tk_sig_sem(semid, 1);
tk_dly_tsk(5000);
}
tk_ext_tsk();
}
void taskC( INT stacd, VP exinf )
{
while(1){
tm_putstring( (UB*)"C enters critical section!¥n" );
tk_wai_sem(semid, 1, TMO_FEVR);
doWorkC(); /* Processing for Task C */
tm_putstring( (UB*)"C exits critical section!¥n" );
tk_sig_sem(semid, 1);
}
tk_ext_tsk();
}
EXPORT INT usermain( void ) /* Functions called by the initial task */
{
T_CSEM csem = { NULL, TA_TFIFO|TA_FIRST, 1, 1 };
T_CTSK ctskA = { NULL, TA_HLNG|TA_RNG0, taskA, 1, 4*1024 };
T_CTSK ctskC = { NULL, TA_HLNG|TA_RNG0, taskC, 3, 4*1024 };
ID tskIdA; /* Task A Identifier */
ID tskIdC; /* Task C Identifier */
tk_chg_pri(TSK_SELF,1);
semid = tk_cre_sem( &csem ); /* Generate semaphores */
tskIdA = tk_cre_tsk( &ctskA ); /* Generate Task A */
tk_sta_tsk( tskIdA, 0 ); /* Start executing Task A. */
tskIdC = tk_cre_tsk( &ctskC ); /* Generate Task C */
tk_sta_tsk( tskIdC, 0 ); /* Start execution of Task C. */
tk_slp_tsk(TMO_FEVR); /* Transitioning to a wake-up call. */
return 0;
}
void doWorkA( void )
{
for (i = 0; i < 50; i++) {
tm_putstring( (UB*)"A is working!¥n" );
WaitUsec(100000); /* 100 ms busy loop (*2) */
}
}
void doWorkC( void )
{
for (i = 0; i < 50; i++) {
tm_putstring( (UB*)"C is working!¥n" );
WaitUsec(100000); /* A busy loop of 100 ms */
}
}
(*2)WaitUsec () is an API that performs a micro-waiting for the specified amount of time (microseconds). It is used to wait for a short period of time (microseconds). This wait is usually implemented as a busy loop, so the task remains in the running state. In lists 1 to 3 in this paper, it is used to indicate that the task is a constant-time process (not including the kernel wait).
Figure 1 shows the change in task state when task C gets a semaphore before task A, causing task A to wait on task C and reversing the order of execution.
【Figure 1: Example of reversed task execution order】
In the example shown in Figure 1, the reversal of the execution order of Task A and Task C continues until Task C releases the semaphore. This is not a problem because this is a temporary reversal caused by the occurrence of a wait state associated with exclusive control and is within the designer’s intent.
Unbounded priority inversion
Listing 2 shows a program that has a medium priority task B added to the program shown in Listing 1.
Task B executes a process that takes 23 seconds once every 28 seconds. After processing, the program enters a state of waiting for waking up for 5 seconds. However, Task B does not use the resources shared by Task A and Task C, so no exclusive control is used.
【List 2】
#include <basic.h>
#include <tk/tkernel.h>
#include <tm/tmonitor.h>
IMPORT void doWorkA( void );
IMPORT void doWorkB( void );
IMPORT void doWorkC( void );
INT i; /* Shared by Task A and Task C */
ID semid; /* semaphore ID */
void taskA( INT stacd, VP exinf )
{
while(1){
tm_putstring( (UB*)"A enters critical section!¥n" );
tk_wai_sem(semid, 1, TMO_FEVR);
doWorkA(); /* Processing for Task A */
tm_putstring( (UB*)"A exits critical section!¥n" );
tk_sig_sem(semid, 1);
tk_dly_tsk(5000);
}
tk_ext_tsk();
}
void taskB( INT stacd, VP exinf )
{
while(1){
doWorkB(); /* Processing for Task B */
tk_dly_tsk(5000);
}
tk_ext_tsk();
}
void taskC( INT stacd, VP exinf )
{
while(1){
tm_putstring( (UB*)"C enters critical section!¥n" );
tk_wai_sem(semid, 1, TMO_FEVR);
doWorkC(); /* Processing for Task C */
tm_putstring( (UB*)"C exits critical section!¥n" );
tk_sig_sem(semid, 1);
}
tk_ext_tsk();
}
EXPORT INT usermain( void ) /* Functions called by the initial task */
{
T_CSEM csem = { NULL, TA_TFIFO|TA_FIRST, 1, 1 };
T_CTSK ctskA = { NULL, TA_HLNG|TA_RNG0, taskA, 1, 4*1024 };
T_CTSK ctskB = { NULL, TA_HLNG|TA_RNG0, taskB, 2, 4*1024 };
T_CTSK ctskC = { NULL, TA_HLNG|TA_RNG0, taskC, 3, 4*1024 };
ID tskIdA; /* Task A Identifier */
ID tskIdB; /* Task B Identifier */
ID tskIdC; /* Task C Identifier */
tk_chg_pri(TSK_SELF,1);
semid = tk_cre_sem( &csem ); /* Generate semaphores */
tskIdA = tk_cre_tsk( &ctskA ); /* Generate Task A */
tk_sta_tsk( tskIdA, 0 ); /* Start executing Task A. */
tskIdB = tk_cre_tsk( &ctskB ); /* Generate Task B */
tk_sta_tsk( tskIdB, 0 ); /* Start execution of Task B. */
tskIdC = tk_cre_tsk( &ctskC ); /* Generate Task C */
tk_sta_tsk( tskIdC, 0 ); /* Start execution of Task C. */
tk_slp_tsk(TMO_FEVR); /* Transitioning to a wake-up call. */
return 0;
}
void doWorkA( void )
{
for (i = 0; i < 50; i++) {
tm_putstring( (UB*)"A is working!¥n" );
WaitUsec(100000); /* A busy loop of 100 ms */
}
}
void doWorkB( void )
{
INT j;
for (j = 0; j < 230; j++) {
tm_putstring( (UB*)"B is working!¥n" );
WaitUsec(100000); /* A busy loop of 100 ms */
}
}
void doWorkC( void )
{
for (i = 0; i < 50; i++) {
tm_putstring( (UB*)"C is working!¥n" );
WaitUsec(100000); /* A busy loop of 100 ms */
}
}
As in the task execution example shown in Figure 1, if task C acquires a semaphore before task A, task A enters the state of waiting until task C releases the semaphore. When task B starts processing in this state, task C stops processing because task C with a low priority is brought out of the execution state to an executable state, and task A waiting for the semaphore release of task C also has to wait until task B completes its processing. Figure 2 shows the change in the task state at this time.
【Figure 2: An example of uncapped priority inversion】
This phenomenon is called “unbounded priority inversion”.
In Listing 2, Task B is implemented to complete in a certain amount of time. However, in the case of more complex programs, it is not always clear when the wait by Task B is completed, and the system may be in a serious condition.
For example, the Mars Pathfinder control program, which landed on Mars in 1997, famously experienced an unchecked priority inversion that caused the system to reboot.
Use of Mutex
Listing 3 is a program consisting of the same tasks as Listing 2, but it uses mutex to achieve exclusive control of tasks A and C.
【List 3】
#include <basic.h>
#include <tk/tkernel.h>
#include <tm/tmonitor.h>
IMPORT void doWorkA( void );
IMPORT void doWorkB( void );
IMPORT void doWorkC( void );
INT i; /* Shared by Task A and Task C */
ID mtxid; /* mutex ID */
void taskA( INT stacd, VP exinf )
{
while(1){
tm_putstring( (UB*)"A enters critical section!¥n" );
tk_loc_mtx(mtxid, TMO_FEVR);
doWorkA(); /* Processing for Task A */
tm_putstring( (UB*)"A exits critical section!¥n" );
tk_unl_mtx(mtxid);
tk_dly_tsk(5000);
}
tk_ext_tsk();
}
void taskB( INT stacd, VP exinf )
{
while(1){
doWorkB(); /* Processing for Task B */
tk_dly_tsk(5000);
}
tk_ext_tsk();
}
void taskC( INT stacd, VP exinf )
{
while(1){
tm_putstring( (UB*)"C enters critical section!¥n" );
tk_loc_mtx(mtxid, TMO_FEVR);
doWorkC(); /* Processing for Task C */
tm_putstring( (UB*)"C exits critical section!¥n" );
tk_unl_mtx(mtxid);
}
tk_ext_tsk();
}
EXPORT INT usermain( void ) /* Functions called by the initial task */
{
T_CMTX cmtx = { NULL, TA_INHERIT, 1 };
T_CTSK ctskA = { NULL, TA_HLNG|TA_RNG0, taskA, 1, 4*1024 };
T_CTSK ctskB = { NULL, TA_HLNG|TA_RNG0, taskB, 2, 4*1024 };
T_CTSK ctskC = { NULL, TA_HLNG|TA_RNG0, taskC, 3, 4*1024 };
ID tskIdA; /* Task A Identifier */
ID tskIdB; /* Task B Identifier */
ID tskIdC; /* Task C Identifier */
tk_chg_pri(TSK_SELF,1);
mtxid = tk_cre_mtx( &cmtx ); /* Generate a mutex. */
tskIdA = tk_cre_tsk( &ctskA ); /* Generate Task A */
tk_sta_tsk( tskIdA, 0 ); /* Start executing Task A. */
tskIdB = tk_cre_tsk( &ctskB ); /* Generate Task B */
tk_sta_tsk( tskIdB, 0 ); /* Start execution of Task B. */
tskIdC = tk_cre_tsk( &ctskC ); /* Generate Task C */
tk_sta_tsk( tskIdC, 0 ); /* Start execution of Task C. */
tk_slp_tsk(TMO_FEVR); /* Transitioning to a wake-up call. */
return 0;
}
void doWorkA( void )
{
for (i = 0; i < 50; i++) {
tm_putstring( (UB*)"A is working!¥n" );
WaitUsec(100000); /* A busy loop of 100 ms */
}
}
void doWorkB( void )
{
INT j;
for (j = 0; j < 230; j++) {
tm_putstring( (UB*)"B is working!¥n" );
WaitUsec(100000); /* A busy loop of 100 ms */
}
}
void doWorkC( void )
{
for (i = 0; i < 50; i++) {
tm_putstring( (UB*)"C is working!¥n" );
WaitUsec(100000); /* A busy loop of 100 ms */
}
}
With the use of the mutex, when Task A attempts to lock the mutex, Task C’s priority is raised to the same value as Task A’s priority, which means that Task C will have priority over Task B to execute the process. This means that Task C will have priority over Task B (as long as the mutex is locked) and this will prevent Task A from being forced to wait for Task B as a result.
The change in the task state at this time is shown in Figure 3.
【Figure 3: Operation with Mutex】
The difference between the semaphore and the semaphore
A mutex and a semaphore are both data structures that provide exclusive control between tasks. A mutex is equivalent to a semaphore (binary semaphore) with a resource count of 1, except that a mechanism can be used to prevent priority inversion, but it should be noted that there are also the following differences
- a. The mutex cannot be unlocked except for locked tasks.
- b. When the task is finished with the mutex locked, the lock is automatically released.
Although you can achieve exclusion control by using semaphores, the uncapped priority inversion described in this article may occur, for example, when you split up a team or add a new task to an existing system. The mutex is a very effective exclusion control function to avoid priority inversions that can lead to fatal flaws, so we encourage you to use it.
“もっと見る” カテゴリーなし
Mbed TLS overview and features
In this article, I'd like to discuss Mbed TLS, which I've touched on a few times in the past, Transport …
What is an “IoT device development platform”?
I started using Mbed because I wanted a microcontroller board that could connect natively to the Internet. At that time, …
Mbed OS overview and features
In this article, I would like to write about one of the components of Arm Mbed, and probably the most …