Variable size memory pool Vs Fixed size memory pool: Creation

① Difference between variable size memory pool and fixed size memory pool

The variable memory pool is defined with structure T_CMPL which has fields ① size of variable length memory pool ② start address of memory pool area ③ attribute flags such as whether the tasks should be granted memory in the order of FIFO or higher priority.

 

In fixed memory pool, the size of memory pool is not directly defined. Instead, T_CMPF structure has fields of  ① the total number of memory blocks required ② size of each memory block size, are defined. ③ attribute flag is same as variable size memory pool.

 

When considering the implementation, the method to keep track free memory blocks differs for both. In this regard, the initialization differs little.

② Implementation specific differences

In variable memory pool, the free memory blocks are connected through linked list kind of structure as shown in the following figure. Immediately after creation of the memory pool, it will be just one single block of memory as shown in the next figure:

Each block of memory is managed with two fields located at the starting of the memory block itself: ① the next pointer ② length of the memory block including these two fields themselves. For the sake of making the internal implementation easier, the total size of these two fields are made as basic unit size of the memory pool. In other words, the size of memory pool is truncated to the multiple of the basic unit size, any allocation will be done in multiple of the basic unit size and the minimum of memory block will be with basic unit size.

For example, when the word length of the CPU is 4 bytes, the basic unit size will be 8 bytes (2 words). When the user passes the size of memory area as 1028, the maximum memory block size available for the user will be: 1016 bytes.

When the memory pool is allocated into blocks, the usable memory size is reduced further which will be discussed in the next post related to allocation.

Ofcourse, the whole system memory itself is being managed as variable memory pool from where the memory for the variable memory pool and fixed memory pool are allocated. It is kind of recursive!

 ③ ITRON implementation of cre_mpl()

ER cre_mpl(ID mplid, T_CMPL *pk_cmpl)
{
        Check context. If called from ISR,
                return E_CTX;
        Sanity check on arguments
        Enter critical section (Interrupt Disable)
        if (start address of memory pool area is NULL) {
                Allocate the memory from Heap with given memory pool area size
        }
        Keep record of the start address of memory pool area
        Keep record of the total size of memory pool area
        /* Initialize the first and top memory pool header defining the free area */
                Align the memory pool size with alignment requirement from CPU & set as size of free area
                Set next pointer of header as NULL
        Internal structure has one queue to order waiting tasks
        If (tasks are queued in FIFO order)
                Initialize queue as follows:
                ┏━━━━━┯━━━━━━┓
                ┃Ｑｕｅｕｅ　　　│Ｑｕｅｕｅ　　　　　┃
                ┃［０］　　　　　│Ｔａｉｌ　　　　　　　┃
                ┗━━━━━┷━━━━━━┛
        else (tasks are queued as priority based)
                Initialize as follows:
                ┏━━━━━━━━┯━━┯━━━━┯━━━━━━┓
                ┃Ｐｒｉｏｒｉｔｙ０　　　　　　│１　　　│Ｍａｘ　　　│Ｑｕｅｕｅ　　　　┃
                ┃　　　　　　　　　　　　│　　　　│Ｐｒｉ　　　　│Ｔａｉｌ　　　　　　　┃
                ┗━━━━━━━━┷━━┷━━━━┷━━━━━━┛
        Exit critical section (Interrupt Restore)
        return E_OK;
}

④ ITRON implementation of cre_mpf()

ER cre_mpf(ID mpfid, T_CMPF *pk_cmpf)
{
        Check context. If called from ISR,
                return E_CTX;
        Sanity check on arguments
        Align the block size with alignment requirement from CPU
        if size of block is less than size of a pointer, set block size to size of pointer
        Calculate the total size of memory area from number of blocks and block size
        Enter critical section (Interrupt Disable)
        if (start address of memory pool area is NULL) {
                Allocate the memory from Heap with given memory pool area size
        }
        Keep record of the start address of memory pool area
        Keep record of the total size of memory pool area
        Keep record of the total number of memory blocks
        Initialize the memory pool as follows:
                The first word of each block points to the start of next block

 

        Internal structure has one queue to order waiting tasks
        If (tasks are queued in FIFO order)
                Initialize queue as follows:
                ┏━━━━━┯━━━━━━┓
                ┃Ｑｕｅｕｅ　　　│Ｑｕｅｕｅ　　　　　┃
                ┃［０］　　　　　│Ｔａｉｌ　　　　　　　┃
                ┗━━━━━┷━━━━━━┛
        else (tasks are queued as priority based)
                Initialize as follows:
                ┏━━━━━━━━┯━━┯━━━━┯━━━━━━┓
                ┃Ｐｒｉｏｒｉｔｙ０　　　　　　│１　　　│Ｍａｘ　　　│Ｑｕｅｕｅ　　　　┃
                ┃　　　　　　　　　　　　│　　　　│Ｐｒｉ　　　　│Ｔａｉｌ　　　　　　　┃
                ┗━━━━━━━━┷━━┷━━━━┷━━━━━━┛
        Exit critical section (Interrupt Restore)
        return E_OK;
}

Hope to follow up in next posts under RTOS label.

μITRON based RTOS Questions and Answers

①When there is a case where anyone of Semaphore or Event flag can be used, which one will you use?

I will use Semaphore. Because, it is lightweight and the processing speed is faster than event flags.

②Why Semaphore is faster than the event flags?

Reason ①: Semaphore maintains the homogeneous resources. So, it is just based on incrementing and decrementing count of resources. But, in event flags, each task has different waiting conditions. So, it's internal processing needs to check current bit pattern and whether it satisfies the requested bit pattern and it is little more complex than the semaphore.

 

Reason ②: The number of arguments in event flag APIs are more than that of semaphore APIs. This will have performance penalty and the event flag implementation needs to save all the arguments in the task context in case of the task going to wait for the event. So, it's processing is time consuming and consumes more memory than the semaphore.

Post your questions if you have. Let's try to find answeres!

Event Flag Vs Semaphore: Refer Status/Deletion/Clear Event Flag

①Event Flags: Clear/Refer/Delete event flags

As, these functions are not holding much share of programming, let me put all these in one post. And, these functions are exactly same as of Semaphore, though Semaphore does not have a function equivalent to clr_flg().

② uITRON implementation to clear event flag

ER clr_flg(ID flgid, FLGPTN clrptn)
{
        Sanity check on arguments
        Enter critical section (Interrupt Disable)
        existing flag pattern &= clrptn;
        Exit critical section (Interrupt Restore)
        return E_OK;
}

③ uITRON implementation to refer event flag information

ER ref_flg(ID flgid, T_RFLG *pk_rflg)
{
        Sanity check on arguments
        Enter critical section (Interrupt Disable)
        Store event flag's current bit pattern
        Store ID number of task which is at the head of flag's wait queue
        Exit critical section (Interrupt Restore)
        return E_OK;
}

④ uITRON implementation to delete flag

ER del_mtx(ID mtxid)
{
        Check context. If called from ISR,
                return E_CTX;
        Sanity check on arguments
        Enter critical section (Interrupt Disable)
        For each task waiting on the event flag's queue {
                Set E_DLT at the error code register of task's context
                If task is waiting for timeout {
                        Delete task from timer queue
                }
                Set task's status as Ready
                If task is not in suspended state {
                        Change the task from event flag's queue to ready queue
                        If executing task's priority is lower than the waiting,
                           set to execute scheduler when quitting this function
                }
                else {
                        Delete the task from the event flag queue
                }
        }
        Release resources allocated when creating event flag(Release event flag's queue)
        If scheduler has to be executed {
                Call scheduler
                Return the error code in the context's error code register
        }
        Exit critical section (Interrupt Restore)
        return E_OK;
}
Please visit other posts under RTOS label.

Event flag Vs Semaphore: Setting flag/Signalling semaphore

① Difference between setting event flag and signalling semaphore

When the event flag has the attribute of TA_CLR, it resembles the operation of signalling a binary semaphore. It means it wakes up only one waiting task, clears the bit and returns.

But, when TA_CLR is not specified, it wakes up all tasks waiting for the event. Also it logical ORs the pattern argument with existing pattern. Any further task checking for the event will be returned E_OK, till the event bit is cleared by clr_flg(). This behaviour makes the flags different from Semaphore.

 

Signaling semaphore will wake up at least one waiting task. But, in event flag, it depends on the condition each task is waiting for. If the task is waiting for other bits to be set, then the task would not been waken up.

 

In implementation perspective, Semaphore seems to have less processing than event flags. In event flags, the arguments in the API are more than the semaphore. So, obviously the kernel needs to save all the parameters in the task context of calling the API. Also, since each task has different conditions for waiting, the set_flg API has more processing to check the tasks that meets the condition. In case of semaphore, since it manages homogeneous resources, it does not have much processing compared to flags.
So, in case of selecting between flag and semaphore for an application, semaphore can be preferred.

② ITRON implementation to set flag

ER set_flg(ID flgid, UINT setptn)
{
        Sanity check on arguments
        Enter critical section (Interrupt Disable)
        If (the pattern is already set) {
                /* then No task should be waiting */
                Exit critical section
                return E_OK;
        }
        Check flag queue for any task waiting
        If (there is a waiting task) {
                if (there is only one task can be waiting for the flag (TA_WMUL not set)) {
                        Take the pattern from context for which task is waiting
                        Logical OR the existing pattern in flag and pattern passed in this function
                        if (ORed pattern satisfies waiting pattern according to TA_ORW or TA_ANDW){
                                Store ORed pattern in the pattern pointer saved in the context
                                if (waiting task had TA_CLR attribute in wai_flg) {
                                        Reset the flag's pattern to 0
                                } else {
                                        Store ORed pattern in the flag as existing pattern
                                }
                                if (task is waiting in Timeout) {
                                        Remove from timer queue
                                }
                                Set task status ad Ready
                                if (the task is NOT suspended) {
                                        Change the task to the Ready Queue of corresponding priority
                                        If (the task priority is higher than the current){
                                                call scheduler
                                                return error code from scheduler
                                        } else {
                                                Exit critical section and return the error code from it
                                        }
                                } else {
                                        Just delete the task from the flag queue
                                        Exit critical section and return the error code from it
                                }
                        }
                        Store ORed pattern in the flag as existing pattern
                        Exit critical section and return the error code from it
                }
                else { /* Multiple tasks can be waiting (TA_WMUL) */
                        Logical OR the existing pattern in flag and the pattern passed in this function
                        for (every task in the flag queue) {
                                Take the pattern from context for which the task is waiting
                                if (ORed pattern satisfies waiting pattern according to TA_ORW or TA_ANDW){
                                        Store ORed pattern in the pattern pointer saved in the context
                                        if (task is waiting in Timeout) {
                                                Remove from timer queue
                                        }
                                        Set task status ad Ready
                                        if (the task is NOT suspended) {
                                                If (the task priority is higher than the current)
                                                        Set to call scheduler when quitting this function
                                                Change the task to the Ready Queue of corresponding priority
                                        } else {
                                                Just delete the task from the Flag queue
                                        }
                                        if (waiting task had TA_CLR attribute in wai_flg) {
                                                Reset the flag's pattern to 0
                                                if (set to call scheduler) {
                                                        Call scheduler
                                                        Return error code that is set in scheduler
                                                }
                                                Otherwise, exit critical section and return error code
                                        }
                                }
                        }
                        Store ORed pattern in the flag as existing pattern
                        if (set to call scheduler) {
                                Call scheduler
                                Return error code that is set in scheduler
                        }
                        Otherwise, exit critical section and return error code
                }
        }
        Replace the existing pattern with logical ORed value of it with pattern passed in this function
        Exit critical section
        return E_OK;
}

Event flag Vs Semaphore: Waiting for event/resource

① Waiting for event flag

In case of event flag, a few more arguments like the flag pattern for waiting, mode for waiting has to be passed. In binary semaphore, it is more simple, only the semaphore id.

 

Event flag can synchronize multiple tasks on a single event. Like single shoot triggers many marathon runners. With binary semaphore, it is not possible. But, with counting semaphore (multiple resource count), it is possible.

 

But implementation, it is almost same as semaphore except that each task context need to save few more arguments passed in wai_flg() function. (The arguments which vary depend on calling task needs to be preserved in task context)

② ITRON implementation to wait for event
ER wai_flg(ID flgid, UINT waiptn, UINT wfmode, UINT *p_flgptn)
{
        Sanity check on arguments
        If (only single task is allowed to wait (TA_WSGL, TA_WMUL flags)
                        and already a task is waiting)
                return E_ILUSE;
        If (the event pattern does not match the waiting pattern) {
                If (this function is called from interrupt context) or
                If (called from task independent state ex: timer handlers) or
                If (called from dispatch disabled state)
                        Return E_CTX;
                If (polling mode)
                        Exit critical section and return E_TMOUT;
                If (Timeout value is specified) {
                        Add task into timer queue;
                        Set TCB flags that 'Waiting for flag, Check for Timeout'
                } else (Wait forever) {
                        Set TCB flags that 'Waiting forever for flag'
                }
                Set event flag ID in TCB
                Also save parameters like waiting mode, waiting pattern,
                        pointer to return bit pattern and even flag attributes
                Select Queue according to queueing order
                If (Tasks should be granted in FIFO order)
                        Select Flag->Queue[0] as Queue
                Else (Should be granted in Priority order)
                        Select Flag->Queue[Current Tasks Priority]
                Change the task from ReadyQueue to the Flag Queue
                Schedule the tasks, since this task is going to sleep
                (Once the task is released, execution will return here)
                Return the value set by scheduler(Scheduler directly set return value before return here)
        }
        Store the pattern into the pointer for returning bit pattern
        If the bit pattern has to be cleared (TA_CLR flag) {
                Clear the flag pattern
        }
        Exit critical secion
        Return E_OK;
}

For other posts, visit posts under RTOS label.

Event Flag Vs Semaphore: Creation

①　Difference between binary semaphore and event flag
In the synchronization context, the event flag resembles the binary semaphore. So, I would like to explore the exact difference between the binary semaphore and event flag.

Instead of 'initial resource count value' in semaphore, event flag has 'initial pattern value'. Otherwise, it is exactly same as creating semaphore.

② ITRON implementation to create event flag

ER cre_flg(ID fkgid, T_CFLG *pk_cflg)
{
        Check context. If called from ISR,
                return E_CTX;
        Sanity check on arguments
        Enter critical section (Interrupt Disable)
        Initialize internal structure with the arguments.
        Internal structure has one queue to order waiting tasks
        If (tasks are queued in FIFO order)
                Initialize queue as follows:
                ┏━━━━━┯━━━━━━┓
                ┃Ｑｕｅｕｅ       │Ｑｕｅｕｅ         　 ┃
                ┃［０］　        　│Ｔａｉｌ　　             ┃
                ┗━━━━━┷━━━━━━┛
        else (tasks are queued as priority based)
                Initialize as follows (Max Pri is taken from configuration):
                ┏━━━━━━━━┯━━┯━━━━┯━━━━━━┓
                ┃Ｐｒｉｏｒｉｔｙ                   │１　    │Ｍａｘ         │Ｑｕｅｕｅ 　        ┃
                ┃　　　　０　　           　│　    　│Ｐｒｉ　          │Ｔａｉｌ　   　         ┃
                ┗━━━━━━━━┷━━┷━━━━┷━━━━━━┛
        Exit critical section (Interrupt Restore)
        return E_OK;
}

The semaphore related implementation has been explained in the previous posts under RTOS label. Please refer to that.