Difference between revisions of "Semaphore"

m (Explorer moved page Binary Semaphore 0B: to Semaphore)
 
(One intermediate revision by the same user not shown)
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 be discussing a Semaphore and its types ie. Binary, Mutex, Counting.<br>
−
Later we will be looking into priority inversion using the LPT,MPT and HPT.<br><br>
+
Later we will see each semaphore in detail with its pros and cons.
 +
Also, we will be looking into priority inversion and priority inheritance.<br><br>
  
 
==Teminologies==
 
==Teminologies==
Line 9: Line 10:
  
  
−
=Prerequisites=
+
=What is a Semaphore?=
−
Please check [[Semaphores|this tutorial]] for detailed explanation on Semaphores.<br> <br>
+
Semaphore is a technique for synchronizing two/more task competing for the same resources. When a task wants to use a resource, it requests for the semaphore and will be allocated if the semaphore is available. If the semaphore is not available then the requesting task will go to blocked state till the semaphore becomes free.
  
−
=API Details=
+
Consider a situation where there are two persons who want to share a bike.
−
Below is the list of the API's used in this tutorial.
+
At one time only one person can use the bike. The one who has the bike key will get the chance to use it. And when this person gives the key to the 2nd person, then the 2nd person can use the bike.
  
−
<b>1.xTaskCreate()</b>: 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 [http://www.freertos.org/a00125.html this link] for more details.<br>
+
Semaphore is just like this <b>Key</b> and the bike is the shared resource.
 +
Whenever a task wants access to the shared resource, it must acquire the semaphore first.
 +
The task should release the semaphore after it is done with the shared resource.  
 +
Until this time all other tasks have to wait if they need access to shared resource as semaphore is not available.
 +
Even if the task trying to acquire the semaphore is of higher priority than the task acquiring the semaphore,
 +
it will be in the wait state until the semaphore is released by the lower priority task.
 +
<br><br>
  
−
<b>2.vTaskDelay()</b>: 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 [http://www.freertos.org/a00127.html this link] for more details.<br>
+
=Types of Semaphores=
 +
There are 3-types of semaphores namely Binary, Counting and Mutex semaphore.
 +
*<b>Binary Semaphore</b>: Binary semaphore is used when there is only one shared resource.
 +
Binary semaphore exists in two states ie.Acquired(Take), Released(Give).
 +
Binary semaphores have no ownership  and can be released by any task or ISR regardless of who performed the last take operation. Because of this binary semaphores are often used to synchronize tasks with external events implemented as ISRs, for example waiting for a packet from a network or waiting for a button is pressed.
  
−
<b>3.vTaskDelete():</b>This function is used to delete as task. We need to pass the taskHandle of the task to be deleted.<br> To delete the own task we should pass NULL as parameter.<br>
+
Because there is no ownership concept a binary semaphore object can be created to be either in the “taken” or “not taken” state initially.
−
Please check [http://www.freertos.org/a00126.html this link] for details. <br>
+
  
−
<b>4.vSemaphoreCreateBinary():</b> This interface is used to create a binary semaphore. We need to pass a handle of type SemaphoreHandle_t to this function.<br>
+
Cons:  
−
Please check [http://www.freertos.org/a00121.html this link] for details. <br>
+
#Priority Inversion : HPT needs to wait for the LPT as LPT is holding the resource required for HPT. In between if MPT task comes then LPT will be in blocked state thereby delaying HPT.
 +
#Does not support recursion : If a task tries to take the semaphore twice then it gets blocked and will not come out of that state till someone releases that semaphore.
 +
#No ownership : Anyone can release or delete the semaphore because of which the dependent tasks will always be in the blocked state.
  
−
<b>5.xSemaphoreTake():</b> 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.<br>
+
*<b>Counting Semaphore</b>: To handle more than one shared resource of the same type, counting semaphore is used. Counting semaphore will be initialized with the count(N) and it will allocate the resource as long as count becomes zero after which the requesting task will enter blocked state.
−
Please check [http://www.freertos.org/a00122.html this link] for details. <br>
+
  
−
<b>6.xSemaphoreGive():</b> This interface is used to release a binary semaphore. We need to pass a semaphore handle to this function.<br>
+
*<b>Mutex Semaphore</b>: Mutex is very much similar to binary semaphore and takes care of priority inversion, ownership, and recursion.
−
Please check [http://www.freertos.org/a00123.html this link] for details. <br>
+
  
−
<b>7.vSemaphoreDelete ():</b> This interface is used to delete a binary semaphore. We need to pass a semaphore handle to this function.<br>
 
−
Please check [http://www.freertos.org/a00113.html#vSemaphoreDelete this link] for details. <br>
 
  
−
 
+
=Priority Inversion=
−
=Example1=
+
This is a scenario where the HPT waits for the LPT as it is using the resource required by HPT.<br>
−
<b> Normal Priority Inversion:</b>
+
Let's see 3 different scenarios of priority inversion depending on the amount of time HPT waits for the lower priority tasks.
−
In this example, we will be creating an LPT. LPT will acquire a semaphore and creates an HPT.
+
*<b>Normal Priority Inversion:</b> Here an HPT tasks waits for the LPT tasks as it is holding the resource(semaphore).
−
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.
+
−
 
+
−
<html><script src="https://gist.github.com/SaheblalBagwan/5bec8e6039889b7ad4875b4a2321e602.js"></script></html>
+
−
 
+
−
[[File:BinarySemaphorePriorityInversion.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.
Line 54: Line 55:
  
 
In this scenario, the HPT task waits for LPT from 2-4 which is the priority inversion period.
 
In this scenario, the HPT task waits for LPT from 2-4 which is the priority inversion period.
 +
[[File:PriorityInversion.png]] <br><br>
  
−
=Example2=
+
*<b>Extended Priority Inversion:</b>Here an HPT tasks waits for the LPT tasks 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.  
−
<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.
 
#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.
Line 72: Line 68:
  
 
In this scenario, the HPT task waits for LPT and Idle task from 2-5 which is the extended priority inversion period.
 
In this scenario, the HPT task waits for LPT and Idle task from 2-5 which is the extended priority inversion period.
 +
[[File:ExtendedPriorityInversion.png]]<br><br>
  
−
=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]]
 
  
 +
*<b>Worst Case Priority Inversion:</b>Here an HPT tasks waits for the LPT tasks 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.
 
#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.
Line 90: Line 82:
  
 
In this scenario, the HPT task waits for LPT and MPT from 2-6 which is the extended priority inversion period.
 
In this scenario, the HPT task waits for LPT and MPT from 2-6 which is the extended priority inversion period.
 +
[[File:0WorstCasePriorityInversion.png]]<br><br>
 +
 +
=Priority Inheritance=
 +
As discussed in the above scenarios, the HPT has to wait for the LPT and also MPT. The scenario of HPT waiting for LPT is justified. But MPT is coming in between and blocking both LPT and HPT. MPT is not at all sharing the same resources and making the HPT wait unnecessarily.
 +
 +
Above problem can be resolved using the mutex semaphore. As soon as the HPT makes a request to semaphore which is allocated to an LPT then, the priority of LPT is temporarily increased to that of HPT. Once the LPT releases the semaphore, its priority will be restored. Because of this, the MPT is never allowed to interfere during the priority inversion(between LPT&HPT). MPT is only allowed to run once HPT is done with its job.
 +
 +
In the below scenario:
 +
#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 and LPT's priority is temporarily raised to that of HPT.
 +
#LPT starts executing again and creates an MPT tasks. It keeps running as its priority is currently higher than MPT. It releases the semaphore and its priority is restored back to lower value.
 +
#Immediately the HPT comes out of the blocked state and starts executing.
 +
#HPT releases the semaphore and runs for some time and deletes itself.
 +
#Now scheduler is left with LPT,MPT, and IDLE task. MPT starts running and deletes itself after completing its job.
 +
#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 only waits for LPT as long as it has the semaphore. As soon as LPT releases the semaphore, HPT takes the control. Also, MPT is never allowed to interfere during the priority inversion(between LPT&HPT). MPT is only allowed to run once HPT is done with its job.
 +
[[File:PriorityInheritance.png]]
 +
<br><br>
  
 
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}}

Latest revision as of 17:55, 14 July 2016

In this tutorial, we will be discussing a Semaphore and its types ie. Binary, Mutex, Counting.
Later we will see each semaphore in detail with its pros and cons. Also, we will be looking into priority inversion and priority inheritance.

Teminologies

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


What is a Semaphore?

Semaphore is a technique for synchronizing two/more task competing for the same resources. When a task wants to use a resource, it requests for the semaphore and will be allocated if the semaphore is available. If the semaphore is not available then the requesting task will go to blocked state till the semaphore becomes free.

Consider a situation where there are two persons who want to share a bike. At one time only one person can use the bike. The one who has the bike key will get the chance to use it. And when this person gives the key to the 2nd person, then the 2nd person can use the bike.

Semaphore is just like this Key and the bike is the shared resource. Whenever a task wants access to the shared resource, it must acquire the semaphore first. The task should release the semaphore after it is done with the shared resource. Until this time all other tasks have to wait if they need access to shared resource as semaphore is not available. Even if the task trying to acquire the semaphore is of higher priority than the task acquiring the semaphore, it will be in the wait state until the semaphore is released by the lower priority task.

Types of Semaphores

There are 3-types of semaphores namely Binary, Counting and Mutex semaphore.

  • Binary Semaphore: Binary semaphore is used when there is only one shared resource.

Binary semaphore exists in two states ie.Acquired(Take), Released(Give). Binary semaphores have no ownership and can be released by any task or ISR regardless of who performed the last take operation. Because of this binary semaphores are often used to synchronize tasks with external events implemented as ISRs, for example waiting for a packet from a network or waiting for a button is pressed.

Because there is no ownership concept a binary semaphore object can be created to be either in the “taken” or “not taken” state initially.

Cons:

  1. Priority Inversion : HPT needs to wait for the LPT as LPT is holding the resource required for HPT. In between if MPT task comes then LPT will be in blocked state thereby delaying HPT.
  2. Does not support recursion : If a task tries to take the semaphore twice then it gets blocked and will not come out of that state till someone releases that semaphore.
  3. No ownership : Anyone can release or delete the semaphore because of which the dependent tasks will always be in the blocked state.
  • Counting Semaphore: To handle more than one shared resource of the same type, counting semaphore is used. Counting semaphore will be initialized with the count(N) and it will allocate the resource as long as count becomes zero after which the requesting task will enter blocked state.
  • Mutex Semaphore: Mutex is very much similar to binary semaphore and takes care of priority inversion, ownership, and recursion.


Priority Inversion

This is a scenario where the HPT waits for the LPT as it is using the resource required by HPT.
Let's see 3 different scenarios of priority inversion depending on the amount of time HPT waits for the lower priority tasks.

  • Normal Priority Inversion: Here an HPT tasks waits for the LPT tasks as it is holding the resource(semaphore).
  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 releases the semaphore.
  4. Immediately the HPT comes out of the blocked state and starts executing.
  5. It releases the semaphore and runs for some time and deletes itself.
  6. Now control goes back to LPT which completes its job and deletes itself.
  7. 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. PriorityInversion.png

  • Extended Priority Inversion:Here an HPT tasks waits for the LPT tasks 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.
  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 waits for an event(packet to be received).
  4. Now the Idle task starts running. Now the HPT is starved because of LPT and Idle task.
  5. LPT comes out of blocked state as the event(wait time/packet is received) has occurred. Now it releases the semaphore.
  6. Immediately the HPT comes out of the blocked state and starts executing. It releases the semaphore and runs for some time and deletes itself.
  7. Now control goes back to LPT which completes its job and deletes itself.
  8. 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. ExtendedPriorityInversion.png


  • Worst Case Priority Inversion:Here an HPT tasks waits for the LPT tasks 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.
  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 creates an MPT tasks.
  4. 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.
  5. LPT comes out of blocked state and releases the semaphore.
  6. Immediately the HPT comes out of the blocked state and starts executing. It releases the semaphore and runs for some time and deletes itself.
  7. Now control goes back to LPT which completes its job and deletes itself.
  8. 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. 0WorstCasePriorityInversion.png

Priority Inheritance

As discussed in the above scenarios, the HPT has to wait for the LPT and also MPT. The scenario of HPT waiting for LPT is justified. But MPT is coming in between and blocking both LPT and HPT. MPT is not at all sharing the same resources and making the HPT wait unnecessarily.

Above problem can be resolved using the mutex semaphore. As soon as the HPT makes a request to semaphore which is allocated to an LPT then, the priority of LPT is temporarily increased to that of HPT. Once the LPT releases the semaphore, its priority will be restored. Because of this, the MPT is never allowed to interfere during the priority inversion(between LPT&HPT). MPT is only allowed to run once HPT is done with its job.

In the below scenario:

  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 and LPT's priority is temporarily raised to that of HPT.
  3. LPT starts executing again and creates an MPT tasks. It keeps running as its priority is currently higher than MPT. It releases the semaphore and its priority is restored back to lower value.
  4. Immediately the HPT comes out of the blocked state and starts executing.
  5. HPT releases the semaphore and runs for some time and deletes itself.
  6. Now scheduler is left with LPT,MPT, and IDLE task. MPT starts running and deletes itself after completing its job.
  7. Now control goes back to LPT which completes its job and deletes itself.
  8. Finally the scheduler is left out with the idle task and it keeps running.

In this scenario, the HPT only waits for LPT as long as it has the semaphore. As soon as LPT releases the semaphore, HPT takes the control. Also, MPT is never allowed to interfere during the priority inversion(between LPT&HPT). MPT is only allowed to run once HPT is done with its job. PriorityInheritance.png

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

Retrieved from "https://exploreembedded.com/wiki/index.php?title=Semaphore&oldid=9650"