① Acquiring lock or resource
------------------------------------
Mutex needs to be associated with Task. So, it cannot be locked from task independent contexts such as ISR, timer Handler, cyclic handler, alarm handler. Also, it cannot be locked from dispatch disabled or CPU locked state. Mutex can avoid priority inversion since it implements Priority Inheritence or Priority Ceiling protocols.
------------------------------------
Mutex needs to be associated with Task. So, it cannot be locked from task independent contexts such as ISR, timer Handler, cyclic handler, alarm handler. Also, it cannot be locked from dispatch disabled or CPU locked state. Mutex can avoid priority inversion since it implements Priority Inheritence or Priority Ceiling protocols.
Semaphore is not like that. Semaphore resources can be acquired or released from even task independent contexts. But, in case of waiting for semaphore resource,it will return E_CTX in task independent contexts. Semaphores are vulnerable to priority inversion scenarios. So, when replacing mutex with binary semaphore, please be aware of this.
Mutex checks for nested call. But, semaphore does not. For example, in the folloing case, in case of binary semaphore, deadlock occurs. But, Mutex returns E_ILUSE;
ID SemID; /* Binary Semaphore ID */
void FunctionA()
{
wai_sem(SemID);
FunctionSub();
sig_sem(SemID);
}
void FunctionSub()
{
wai_sem(SemID);
:
sig_sem(SemID);
}
So, Mutex can avoid priority inversion and recursive locks!
Note that when the task is locking the mutex, the mutex ID is recorded in TCB (Task Control Block) structure. That means, the locked mutex is associated with the locking task and considered as a resource currently occupied by the specific task. So, the task is liable to release the mutex at one point. Other tasks cannot do anything till the locking task releases the mutex. It is like occupying a room locking inside. If any other person trying to occupy the room kept waiting at the entrance till the person inside comes out by unlocking the room.
But, semaphore is NOT considered as resource but just a counter which can be incremented and decremented atomically by any anonymous task. Neither the semaphore nor the task does not remember which particular task increment or decrement which semaphore. But, (unluckily) some programmers associate the semaphore with some resources to manage the access of the resources. For example, number of balls in a basket are maintained using two buttons one is read and other is blue. Whenever you take a ball, you should press red button. When you return the ball, you should press the blue button. There are chances of confusion here when somebody forget to press the red button when taking the ball or when somebody just pressed the blue button without actually returning the ball. In this scenario, ball is considered as actual resource maintained by a semaphore. Pressing the red button is similar to incrementing the count. Pressing the blue button is similar to decrementing the count.
② ITRON implementation to acquire semaphore
-----------------------------------------------------------
ER wai_sem(ID semid)
{
Sanity check on arguments
If (remaining number of semaphore resrouces is zero) {
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 Semaphore, Check for Timeout'
} else (Wait forever) {
Set TCB flags that 'Waiting forever for Semaphore'
}
Set Semaphore ID in TCB
Select Queue according to queueing order
If (Tasks should be granted in FIFO order)
Select Semaphore->Queue[0] as Queue
Else (Should be granted in Priority order)
Select Semaphore->Queue[Current Tasks Priority]
Change the task from ReadyQueue to the Semaphore 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)
}
Reduce Semaphore resource count by one
Exit critical secion
Return E_OK;
}
③ ITRON implementation to lock mutex
--------------------------------------------------
ER loc_mtx(ID mtxid)
{
Sanity check on arguments
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;
Enter critical section (Interrupt Disable)
If (same task has locked this mutex already)
Return E_ILUSE;
If (Ceiling protocol has been selected) and
(this task has high base priority than the ceiling priority)
Return E_ILUSE;
If (this mutext has NOT been locked already (by any other task)) {
Record this task ID as locking task in mutex structure
(Refer from TCB & Record the previous mutex ID locked by the same task)
(Update this mutex ID as previous mutex ID in TCB structure)
If (Ceiling protocol) and
(this tasks's (running) priority* is less than ceiling priority) {
Change the task's priority to ceiling priority
Schedule the tasks, since the priority has been changed
(If any higher priority task exists, that will be executed and control returns here later)
Return value from scheduler(Scheduler directly set return value before return here)
}
} else { /* Has been locked. If not polling mode, process queuing */
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 Mutex, Check for Timeout'
} else (Wait forever) {
Set TCB flags that 'Waiting forever for Mutex'
}
Set MutexID in TCB
Select Queue according to queueing order
If (Tasks should be granted in FIFO order)
Select mutex->Queue[0] as Queue
Else (Should be granted in Priority order)
Select mutex->Queue[Current Tasks Priority]
Change the task from ReadyQueue to the Mutex Queue
If (Priority Inheritence protocol selected) and
(this task has high priority than locked task)
Raise the priority of the locked task
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)
}
Exit critical section and return E_OK;
}
* running priority - Specifies the priority changed inside the kernel. For example, priority raised through priority inheritence or priority ceiiling protocol.
Base priority is the one set by user program. For example, the priority set during creation or chg_pri() system call.
The Queue is maitained as follows. When chaning a queue, entry is deleted from existing queue (Ready Queue) and added to the new Queue.
{
Take the task (say A) currently locking the mutex
Take the base priority of the task A
Parse through all the mutex locked by A {
Fix the maximum (say P) between
the maximum priority of all waiting tasks over mutex of INHERIT and
the maximum of celing priority of mutex with CEILING
And, for all the INHERIT mutexes, the priority of locking task has
to be reset with the maximum priority of all waiting tasks. If no
waitint task, then the priority is reset with minimum system priority.
}
If the priority P is not equal to the running priority of locking task{
Assign the P as running priority of locking task
}
}
No comments:
Post a Comment