Difference between revisions of "Binary Semaphore 05: No-Ownership"

Line 1: Line 1:
 
[[category: Free RTOS with Arduino]]
 
[[category: Free RTOS with Arduino]]
−
In this tutorial, we will see how to create and use binary semaphore.<br>
+
In this tutorial, we will see one of the demerits of binary semaphore ie. No-Ownership of semaphores.<br>
−
Later we will be looking into priority inversion using the LPT,MPT and HPT.<br><br>
+
Here we will see what happens if a task releases the semaphore locked by another task.<br><br>
  
 
==Teminologies==
 
==Teminologies==
Line 10: Line 10:
  
 
=Prerequisites=
 
=Prerequisites=
−
Please check [[Semaphores|this tutorial]] for detailed explanation on Semaphores.<br> <br>
+
Please check [[Semaphore|this tutorial]] for detailed explanation on Semaphores.<br> <br>
  
 
=API Details=
 
=API Details=
Line 35: Line 35:
  
  
−
=Example1=
+
=Example=
−
<b> Normal Priority Inversion:</b>
+
 
In this example, we will be creating an LPT. LPT will acquire a semaphore and creates an HPT.
 
In this example, we will be creating an LPT. LPT will acquire a semaphore and creates an HPT.
−
HPT will preempt LPT as starts running. HPT tries to acquire a semaphore used by LPT and goes to blocked state resulting in priority inversion. Now LPT starts running and releases the semaphore and immediately HPT comes out of block state and starts running.
+
HPT will preempt LPT as starts running. HPT tries to acquire a semaphore used by LPT and goes to blocked state resulting in priority inversion. Now LPT starts running and creates MPT, as MPT has higher priority it preempts LPT and starts running.
 +
At this point the semaphore is locked by LPT and HPT is waiting for it. Now MPT releases the semaphore locked by LPT.
  
−
<html><script src="https://gist.github.com/SaheblalBagwan/5bec8e6039889b7ad4875b4a2321e602.js"></script></html>
+
<html><script src="https://gist.github.com/SaheblalBagwan/dbcd698228010f3a95c4927f18c365e8.js"></script></html>
  
−
[[File:BinarySemaphorePriorityInversion.png]]
+
[[File:BinarySemaphoreNonRecursiveLock.png]]
  
−
Here an HPT tasks waits for the LPT tasks as it is holding the resource(semaphore).
 
 
#LPT starts running and acquires the semaphore.
 
#LPT starts running and acquires the semaphore.
 
#Now HPT is created and it preempts LPT and starts running. It makes the request to acquire the semaphore. Since the semaphore is already with LPT, HPT goes to blocked state.
 
#Now HPT is created and it preempts LPT and starts running. It makes the request to acquire the semaphore. Since the semaphore is already with LPT, HPT goes to blocked state.
−
#LPT starts executing again and releases the semaphore.
+
#LPT starts executing again and tries to take the same semaphore. Since the semaphore is not available, it gets blocked.  
−
#Immediately the HPT comes out of the blocked state and starts executing.
+
#Finally the scheduler is left out with the idle task and it keeps running. The LPT and HPT will in blocked state until someone releases the semaphore.
−
#It releases the semaphore and runs for some time and deletes itself.
+
−
#Now control goes back to LPT which completes its job and deletes itself.
+
−
#Finally the scheduler is left out with the idle task and it keeps running.
+
−
 
+
−
In this scenario, the HPT task waits for LPT from 2-4 which is the priority inversion period.
+
−
 
+
−
=Example2=
+
−
<b> Extended Priority Inversion:</b>
+
−
In this example,  HPT waits for the LPT as it is holding the resource(semaphore). Further, the LPT waits for the event/data to be received and the CPU executes the IDLE tasks. This makes the HPT wait for more time.
+
−
<html><script src="https://gist.github.com/SaheblalBagwan/e18934bcd64b11307fabf8b0e0812f32.js"></script></html>
+
−
 
+
−
[[File:BinarySemaphoreExtendedPriorityInversion.png]]
+
−
 
+
−
#LPT starts running and acquires the semaphore.
+
−
#Now HPT is created and it preempts LPT and starts running. It makes the request to acquire the semaphore. Since the semaphore is already with LPT, HPT goes to blocked state.
+
−
#LPT starts executing again and waits for an event(packet to be received).
+
−
#Now the Idle task starts running. Now the HPT is starved because of LPT and Idle task.
+
−
#LPT comes out of blocked state as the event(wait time/packet is received) has occurred. Now it releases the semaphore.
+
−
#Immediately the HPT comes out of the blocked state and starts executing. It releases the semaphore and runs for some time and deletes itself.
+
−
#Now control goes back to LPT which completes its job and deletes itself.
+
−
#Finally the scheduler is left out with the idle task and it keeps running.
+
−
 
+
−
In this scenario, the HPT task waits for LPT and Idle task from 2-5 which is the extended priority inversion period.
+
−
 
+
−
=Example3=
+
−
<b>Worst Case Priority Inversion:</b>
+
−
In this example,  HPT waits for the LPT as it is holding the resource(semaphore). In between an MPT starts executing thereby blocking the LPT and HPT. This makes the HPT wait for MPT and LPT.
+
−
<html><script src="https://gist.github.com/SaheblalBagwan/2e068861803630f0c404d48886c83775.js"></script></html>
+
−
 
+
−
[[File:BinarySemaphoreWorstCasePriorityInversion.png]]
+
−
 
+
−
#LPT starts running and acquires the semaphore.
+
−
#Now HPT is created and it preempts LPT and starts running. It makes the request to acquire the semaphore. Since the semaphore is already with LPT, HPT goes to blocked state.
+
−
#LPT starts executing again and creates an MPT tasks.
+
−
#MPT preempts the LPT and starts running. At this point, the HPT is starved because of LPT and MPT. MPT completes its job and deletes itself.
+
−
#LPT comes out of blocked state and releases the semaphore.
+
−
#Immediately the HPT comes out of the blocked state and starts executing. It releases the semaphore and runs for some time and deletes itself.
+
−
#Now control goes back to LPT which completes its job and deletes itself.
+
−
#Finally the scheduler is left out with the idle task and it keeps running.
+
−
 
+
−
In this scenario, the HPT task waits for LPT and MPT from 2-6 which is the extended priority inversion period.
+
  
  
 
Have an opinion, suggestion , question or feedback about the article let it out here!
 
Have an opinion, suggestion , question or feedback about the article let it out here!
 
{{DISQUS}}
 
{{DISQUS}}

Revision as of 16:54, 15 July 2016

In this tutorial, we will see one of the demerits of binary semaphore ie. No-Ownership of semaphores.
Here we will see what happens if a task releases the semaphore locked by another task.

Teminologies

  1. LPT: Low Priority Task
  2. MPT: Medium Priority Task
  3. HPT: High Priority Task


Prerequisites

Please check this tutorial for detailed explanation on Semaphores.

API Details

Below is the list of the API's used in this tutorial.

1.xTaskCreate(): This interface is used to create a new Task, if the task is successfully created then it returns pdPass(1) or else errCOULD_NOT_ALLOCATE_REQUIRED_MEMORY(-1). Check this link for more details.

2.vTaskDelay(): This function is used to delay/block the task for specified delay time(ticks). INCLUDE_vTaskDelay needs to be set to 1 in FreeRtosConfig.h file for using this function. Check this link for more details.

3.vTaskDelete():This function is used to delete as task. We need to pass the taskHandle of the task to be deleted.
To delete the own task we should pass NULL as parameter.
Please check this link for details.

4.vSemaphoreCreateBinary(): This interface is used to create a binary semaphore. We need to pass a handle of type SemaphoreHandle_t to this function.
Please check this link for details.

5.xSemaphoreTake(): This interface is used to acquire a binary semaphore. We need to pass a semaphore handle and the amount of time to wait for semaphore to become available.
Please check this link for details.

6.xSemaphoreGive(): This interface is used to release a binary semaphore. We need to pass a semaphore handle to this function.
Please check this link for details.

7.vSemaphoreDelete (): This interface is used to delete a binary semaphore. We need to pass a semaphore handle to this function.
Please check this link for details.


Example

In this example, we will be creating an LPT. LPT will acquire a semaphore and creates an HPT. HPT will preempt LPT as starts running. HPT tries to acquire a semaphore used by LPT and goes to blocked state resulting in priority inversion. Now LPT starts running and creates MPT, as MPT has higher priority it preempts LPT and starts running. At this point the semaphore is locked by LPT and HPT is waiting for it. Now MPT releases the semaphore locked by LPT.

BinarySemaphoreNonRecursiveLock.png

  1. LPT starts running and acquires the semaphore.
  2. Now HPT is created and it preempts LPT and starts running. It makes the request to acquire the semaphore. Since the semaphore is already with LPT, HPT goes to blocked state.
  3. LPT starts executing again and tries to take the same semaphore. Since the semaphore is not available, it gets blocked.
  4. Finally the scheduler is left out with the idle task and it keeps running. The LPT and HPT will in blocked state until someone releases the semaphore.


Have an opinion, suggestion , question or feedback about the article let it out here!

Retrieved from "https://exploreembedded.com/wiki/index.php?title=Binary_Semaphore_05:_No-Ownership&oldid=9691"