RT-Thread version: 4.0.5
MCU model: STM32F103RCT6 (ARM Cortex-M3 kernel)

1 Synchronization and Mutual Exclusion

First add a few concepts:

• Execution Unit: Determined by the current hardware platform and the operating system it runs. For RT-Thread and STM32, the execution units are threads and interrupts
• Critical Zone: Multiple execution units operate/access the same area at the same time (code)
• Race: A multithreaded situation in which the correctness of a calculation depends on relative chronological order or thread crossover

When multiple execution units (threads, interrupts) execute a critical zone simultaneously, operating on critical resources can result in races, which can be resolved in a synchronous or mutually exclusive manner.

• Synchronization: Running in a predetermined order. (sequential)
  • Thread synchronization: refers to the process by which multiple threads control the order of execution between threads through a specific mechanism.
• Mutual exclusion: that is, multiple execution units are not allowed to operate on critical zones simultaneously (out of order)
  • Threads are mutually exclusive: refers to exclusive access to critical zone resources. When multiple threads are using the critical zone resource, at most one thread is allowed to use it at any time, and other threads using the resource must wait until the resource occupier releases it.

Threads are mutually exclusive and can be viewed as a special type of thread synchronization.

For bare metal, global flag is generally used to achieve synchronization and mutually exclusive access to critical resources. Usually the CPU always polls to see if the flag meets the occupancy criteria. In RTOS, critical zone resources are generally protected by semaphores, mutexes, event sets, etc. For semaphores, when the semaphore instance resource is empty, the thread enters the blocked state and waits for the semaphore to arrive, but when there is a semaphore resource, the thread is immediately awakened, which reduces CPU resource consumption and provides the fastest real-time response speed.

2 Semaphore concept and classification

Semaphore is a lightweight kernel object used to solve the problem of inter-thread synchronization, which can be acquired or released by threads for synchronization or mutually exclusive purposes.
Composition of semaphore objects in RT-Thread:

• Semaphore value: The number of instances (resources) of a semaphore object, indicating how many semaphore instances can be used
• Thread Waiting Queue: Threads that did not successfully acquire semaphores will hang on this queue and wait

Usually a semaphore count value (sem->value) is used to indicate the number of resources that can be occupied. It can only be 0 and a positive integer maximum (65535). Successful release of the semaphore will add 1 to the value, and successful acquisition of the semaphore will subtract 1 from the value. A value of 0 indicates that the resource is empty, and threads that want to acquire the semaphore are blocked and suspended in the thread waiting queue.

The semaphore mutex and synchronization are used differently as follows:

• Use as mutex: semaphores should be full after they are created. When a thread needs to use a critical resource, it first gets the semaphore and makes it empty, which allows only one thread to use the resource at any time. However, this can cause problems with thread priority flipping. (We'll talk about the hazards and solutions later).
• For synchronization: The semaphore should be left blank after it is created. Assuming there are threads 1 and 2, the semaphore fetch from thread 1 will be blocked. When thread 2 releases the semaphore under certain conditions, if thread 1 has the highest priority, it will immediately cut to the thread to synchronize between the two threads. Similarly, interrupts and threads can synchronize in this way (in which only semaphores are released, not acquired).

Note: Mutual exclusion between interrupts and threads cannot be semaphore-based, but switch-based.

2.1 Binary Semaphore

A binary semaphore resembles a flag bit, and its resource count value can only be 0 and 1. 0 indicates that the resource is acquired and 1 indicates that it is released.
As mentioned earlier, using global variables as flag CPUs requires constant queries, which wastes CPU resources. A binary semaphore is a good solution to this problem. When the binary semaphore is empty, the thread enters a blocking wait state and wakes up when the semaphore is marked 1. However, using binary semaphores to protect critical resources can cause an unbounded priority flip.

2.2 Count semaphore

Counted semaphores with resource count values ranging from 0 to 65535 allow multiple threads to acquire semaphores to access resources, but limit the maximum number of resources. When this number is reached, other threads attempting to acquire the semaphore will be blocked until a thread releases the semaphore (threads that do not acquire the semaphore can also release the semaphore). Generally used for:

• Event Count: Release semaphores when an event occurs, acquire semaphores when an event is processed, and a value of 0 indicates that all events have been processed
• Resource management: The semaphore value represents the current number of resources available, and a value of 0 indicates that there are no resources (such as parking spaces).

3 semaphore control block

The semaphore control block is a data structure used by the operating system to manage semaphores:

struct rt_ipc_object
{
    struct rt_object parent;                            /**< Inherited from rt_object class */

    rt_list_t        suspend_thread;                    /**< Threads hanging on this resource */
};

struct rt_semaphore
{
    struct rt_ipc_object parent;                        /* Inherited from ipc_object class */

    rt_uint16_t          value;                         /* The value of the semaphore */
    rt_uint16_t          reserved;                      /* Reserved Fields */
};
typedef struct rt_semaphore *rt_sem_t;

Where sem->value is the resource count value, sem->parent. Suspend_ Threads are threads suspended because they failed to acquire the semaphore, which are inserted into the chain table in either thread priority or FIFO order using a two-way circular chain table store.

4 semaphore function interface

4.1 Create/Delete

• Create semaphore

/**
 * @brief    Creating a semaphore object.
 * @param    name Semaphore name
 * @param    Resource Count Value
 *           value If used for sharing resources, this value should be initialized to the number of available resources.
 *           If used to indicate the occurrence of an event, the value should be initialized to zero.
 *
 * @param    flag Indicates how threads waiting to acquire a semaphore when it is unavailable (value==0):
*               RT_IPC_FLAG_PRIO: The queue of waiting threads will be queued according to the thread priority, the higher priority waiting threads will get the signal of waiting first
*               RT_IPC_FLAG_FIFO: The queue of waiting threads will be queued in FIFO mode, the first-in threads will get the signal of waiting first
*
*               NOTE: RT_IPC_FLAG_FIFO This is a non-real-time scheduling method and is generally not recommended unless the application cares a lot about coming first,
 *                    And the user clearly knows that all threads involved in the semaphore will become non-real-time threads.
 *                    Otherwise, RT_is recommended IPC_ FLAG_ PRIO, which ensures that the thread is real-time.
 *
 * @return   Returns a pointer to the semaphore object. Creation failure return value is RT_NULL
 */
rt_sem_t rt_sem_create(const char *name, rt_uint32_t value, rt_uint8_t flag)
{
    rt_sem_t sem;

    RT_DEBUG_NOT_IN_INTERRUPT;
    RT_ASSERT(value < 0x10000U);	// Value must be less than 2^16 (65536)

    /* Assign Kernel Objects */
    sem = (rt_sem_t)rt_object_allocate(RT_Object_Class_Semaphore, name);
    if (sem == RT_NULL)
        return sem;

    /* Initialize semaphore object */
    _ipc_object_init(&(sem->parent));

    /* Set the value of available semaphores */
    sem->value = value; // If a binary semaphore is created, its value range is [0,1], and if it is a count semaphore, its value range is [0,65535]

    /* Set semaphore mode */
    sem->parent.parent.flag = flag;

    return sem;
}
}

• Delete semaphore

rt_err_t rt_sem_delete(rt_sem_t sem)
{
    RT_DEBUG_NOT_IN_INTERRUPT;

    /* Parameter Check */
    RT_ASSERT(sem != RT_NULL); 
    RT_ASSERT(rt_object_get_type(&sem->parent.parent) == RT_Object_Class_Semaphore);
    RT_ASSERT(rt_object_is_systemobject(&sem->parent.parent) == RT_FALSE);

    /* Wake up all threads blocking suspended on this semaphore */
    _ipc_list_resume_all(&(sem->parent.suspend_thread));

    /* Delete semaphore object */
    rt_object_delete(&(sem->parent.parent));

    return RT_EOK;
}

When the function is called, the semaphore is deleted (it must be created dynamically), and if a thread is waiting for the semaphore when it is deleted, the deletion wakes up the thread waiting on the semaphore (the return value for the waiting thread is -RT_ERROR) before releasing the semaphore's memory resources.

4.2 Initialization/Departion

Static initialization and detachment (static objects cannot be deleted) objects are functionally identical to the functions described above and are no longer discussed.

4.3 Acquire/No Wait Acquire

• Get semaphore

rt_err_t rt_sem_take(rt_sem_t sem, rt_int32_t time)
{
    register rt_base_t temp;
    struct rt_thread *thread;

    /* Parameter Check */
    RT_ASSERT(sem != RT_NULL);
    RT_ASSERT(rt_object_get_type(&sem->parent.parent) == RT_Object_Class_Semaphore);

    RT_OBJECT_HOOK_CALL(rt_object_trytake_hook, (&(sem->parent.parent)));

    /* Shutdown Interruption */
    temp = rt_hw_interrupt_disable();

    if (sem->value > 0)
    {
        /* Available semaphores */
        sem->value --;

        /* Open Interrupt */
        rt_hw_interrupt_enable(temp);
    }
    else
    {
        /* No wait, return timeout error */
        if (time == 0)
        {
            rt_hw_interrupt_enable(temp);

            return -RT_ETIMEOUT;
        }
        else
        {
            /* Current Context Check */
            RT_DEBUG_IN_THREAD_CONTEXT;

            /* Semaphore unavailable, suspend current thread */
            /* Get Current Thread */
            thread = rt_thread_self();

            /* Set Thread Error Code */
            thread->error = RT_EOK;

            /* Suspend Threads */
            _ipc_list_suspend(&(sem->parent.suspend_thread),
                                thread,
                                sem->parent.parent.flag);

            /* Start timing when there is waiting time */
            if (time > 0)
            {
                /* Set thread timeout and start timer */
                rt_timer_control(&(thread->thread_timer),
                                 RT_TIMER_CTRL_SET_TIME,
                                 &time);
                rt_timer_start(&(thread->thread_timer));
            }

            /* Open Interrupt */
            rt_hw_interrupt_enable(temp);

            /* Initiate Thread Scheduling */
            rt_schedule();

            if (thread->error != RT_EOK)
            {
                return thread->error;
            }
        }
    }

    RT_OBJECT_HOOK_CALL(rt_object_take_hook, (&(sem->parent.parent)));

    return RT_EOK;
}

• When the semaphore count value sem->vaule is greater than 0, the thread takes the sem->vaule and subtracts it by 1
• When sem->vaule is 0, the current semaphore resource instance is empty, and the thread requesting the semaphore decides how to invoke it based on the time parameter:
  1. time==0: directly returned with -RT_ETIMEOUT;
  2. Time>0: Suspend the current thread, set the thread timeout callback time if there is a wait time, start the thread's timer, and start thread scheduling.
• No wait to get semaphore

rt_err_t rt_sem_trytake(rt_sem_t sem)
{
    return rt_sem_take(sem, RT_WAITING_NO);
}

RT_ WAITING_ The NO macro value is 0, even if the semaphore is obtained without waiting time.

4.4 Release Signal

rt_err_t rt_sem_release(rt_sem_t sem)
{
    register rt_base_t temp;
    register rt_bool_t need_schedule;

    /* parameter check */
    RT_ASSERT(sem != RT_NULL);
    RT_ASSERT(rt_object_get_type(&sem->parent.parent) == RT_Object_Class_Semaphore);

    RT_OBJECT_HOOK_CALL(rt_object_put_hook, (&(sem->parent.parent)));

    need_schedule = RT_FALSE;

    /* disable interrupt */
    temp = rt_hw_interrupt_disable();


    if (!rt_list_isempty(&sem->parent.suspend_thread))
    {
        /* Resume blocked threads */
        _ipc_list_resume(&(sem->parent.suspend_thread));
        need_schedule = RT_TRUE;
    }
    else
    {
        if(sem->value < RT_SEM_VALUE_MAX)
        {
            sem->value ++; /* value Value increases by 1 */
        }
        else
        {
            rt_hw_interrupt_enable(temp); /* enable interrupt */
            return -RT_EFULL; /* value Value overflow */
        }
    }

    /* enable interrupt */
    rt_hw_interrupt_enable(temp);

    /* Restore the current thread, initiate task scheduling */
    if (need_schedule == RT_TRUE)
        rt_schedule();

    return RT_EOK;
}

• If the semaphore wait queue is empty (that is, no threads are blocked by accessing the semaphore), add sem->value plus 1 directly
• If the semaphore wait queue is not empty, wake up the first thread in the queue (remove the thread from the blocking list and add it to the ready list) to get the semaphore

Note: This function can be called during an interrupt to synchronize the interrupt with the thread (only semaphores can be released during an interrupt, not acquired).

5 Semaphore application example

5.1 Mutually exclusive access to critical resources

/*
 * Date           Author   
 * 2022-02-05     issac wan
 */

#include <rtthread.h>

#define my_printf(fmt, ...)         rt_kprintf(fmt"\n", ##__VA_ARGS__)

#define THREAD_PRIORITY         20
#define THREAD_TIMESLICE        5

static uint16_t num1 = 0, num2 = 0;
static rt_sem_t sem1;

static rt_thread_t send_thread = RT_NULL;
void send_thread_entry(void * param){
    while(1){
        rt_sem_take(sem1, RT_WAITING_FOREVER);
        num1++;
        rt_thread_delay(100);
        num2++;
        rt_sem_release(sem1);
    }
}

ALIGN(RT_ALIGN_SIZE)
static struct rt_thread receive_thread;
static rt_uint8_t receive_thread_stack[512] = {0};
void receive_thread_entry(void * param){
    while(1){
        rt_sem_take(sem1, RT_WAITING_FOREVER);
        if (num1 == num2)
            my_printf("[%u]Successful! num1:[%d], num2:[%d]", rt_tick_get(), num1, num2);
        else
            my_printf("[%u]Fail! num1:[%d], num2:[%d]", rt_tick_get(), num1, num2);
        rt_sem_release(sem1);
        rt_thread_delay(1000);
    }
}

int semaphore_sample(void){
    rt_err_t receive_thread_ret = 0;
    sem1 = rt_sem_create("sem1", 1, RT_IPC_FLAG_FIFO);
    if (sem1 == RT_NULL)
        return -RT_ERROR;

    send_thread = rt_thread_create("send_th",
                                    send_thread_entry,
                                    RT_NULL,
                                    512,
                                    THREAD_PRIORITY,
                                    THREAD_TIMESLICE);
    if (send_thread == RT_NULL)
        return -RT_ERROR;
    else
        rt_thread_startup(send_thread);


    receive_thread_ret = rt_thread_init(&receive_thread,
                                        "rec_th",
                                        receive_thread_entry,
                                        RT_NULL,
                                        receive_thread_stack,
                                        sizeof(receive_thread_stack),
                                        THREAD_PRIORITY - 1,
                                        THREAD_TIMESLICE);
    if (receive_thread_ret != RT_EOK)
        return receive_thread_ret;
    else
        rt_thread_startup(&receive_thread);

    return RT_EOK;
}
INIT_APP_EXPORT(semaphore_sample);

• Create a binary semaphore with an initial resource count value of 1;
• Create two threads: the sending thread and the receiving thread, both of which acquire threads by waiting indefinitely;
• After successfully obtaining the semaphore in the sending thread, let num1+1 first, then use the delay function to simulate the time occupying the semaphore, and let num2+1 release the semaphore at the end of the delay.
• After the receiving thread successfully acquires the semaphore, if num1==num2, the synchronization succeeds and vice versa, the semaphore is released.

The serial port print information is as follows:

Note: Mutual exclusion can be seen as a special thread synchronization

5.2 Resource Count (simulated parking lot)

/*
 * Date           Author   
 * 2022-02-05     issac wan
 */

#include <rtthread.h>

#define my_printf(fmt, ...)         rt_kprintf("[%u]"fmt"\n", rt_tick_get(), ##__VA_ARGS__)

#define THREAD_PRIORITY         20
#define THREAD_TIMESLICE        5

#define MAX_TRUCK_SPACE (5U)//Max 5 parking spaces

static rt_sem_t sem;
static rt_thread_t park_thread = RT_NULL;
static rt_thread_t pick_thread = RT_NULL;

void park_thread_entry(void* param){
    rt_err_t park_ret = RT_EOK;
    while(1){
        park_ret = rt_sem_trytake(sem);    // No pending acquisition
        if(RT_EOK == park_ret){
            my_printf("Successfully acquired a parking space, There are currently%d Number of empty parking spaces", sem->value);
        }else{
            my_printf("FULL!");
        }

        rt_thread_delay(1000);
    }
}

void pick_thread_entry(void* param){
    while(1){
        if(MAX_TRUCK_SPACE == sem->value){
            my_printf("All parking spaces are empty!");
        }
        else{
            rt_sem_release(sem);
            my_printf("Successfully released a parking space, Currently Common%d Number of empty parking spaces", sem->value);
        }
        rt_thread_delay(3000);
    }
}
int semaphore_sample(void){
    sem = rt_sem_create("sem", MAX_TRUCK_SPACE, RT_IPC_FLAG_PRIO);

    if (sem == RT_NULL)
        return -RT_ERROR;

    park_thread = rt_thread_create("park_th",
                                    park_thread_entry,
                                    RT_NULL,
                                    512,
                                    THREAD_PRIORITY - 1,
                                    THREAD_TIMESLICE);
    if (park_thread == RT_NULL)
        return -RT_ERROR;
    else
        rt_thread_startup(park_thread);

    pick_thread = rt_thread_create("pick_th",
                                    pick_thread_entry,
                                    RT_NULL,
                                    512,
                                    THREAD_PRIORITY,
                                    THREAD_TIMESLICE);
    if (pick_thread == RT_NULL)
        return -RT_ERROR;
    else
        rt_thread_startup(pick_thread);

    return RT_EOK;
}
INIT_APP_EXPORT(semaphore_sample);

• Initialize two threads: parking thread and pick-up thread;
• Initializes a counting semaphore for parking lot vacancy counts up to a maximum of 5.
• The parking thread does not wait for a semaphore to be acquired every second. When the semaphore is empty, the parking fails.
• The pickup thread releases the semaphore every 3 seconds, and the pickup fails when the semaphore count reaches the maximum value set.

The serial port print information is as follows:

6 Summary

• Synchronization allows multiple threads to access critical resources simultaneously in a sequential manner. Mutual exclusion allows only one thread to access critical resources, out of order.
• Semaphores are mainly used to solve the problem of synchronization and mutual exclusion between threads, which are divided into binary semaphores (0-1) and count semaphores (0-65535).
• It is important to note that semaphores can cause priority flipping when protecting critical resources.
• Semaphores synchronize interrupts with threads (allowing only semaphores to be released during interrupts, not semaphores to be acquired), but they do not mutually exclusive (by turning off interrupts).