Semaphores, event flags, and ports

Misc topics, here: 1) As far as I can tell, the semaphores really just wind up creating queues – is that correct? If so, if I have a semaphore of 10,000 units, that runs me out of memory quite quickly. Is there any way around this? 2) I’ve worked with ThreadX in the past and they had a great concept of "event flags". That is, it’s a UINT32 that you can block on, with other trigger points – inside or outside an ISR, and it can unblock multiple waiting threads. There doesn’t appear to be any way to do this in FreeRTOS. Anyone interested in getting them added? 3) There are currently APIs that are to be used outside and inside an ISR. Isn’t it possible to make the core routine (e.g. QueueSend/QueueReceive) just know when it’s in an interrupt, especially on an ARM platform? I have a procedure that’s sometimes called from an ISR and sometimes from foreground code, and I need to manaually manage which context I’m in. It would be nice if FreeRTOS did that automatically. 4) I’ve done a port to the Atmel SAM7S256 using the ARM SDT 2.51 – more specifically, an Olimex SAM7P256 board. Is anyone interested in the source code? Thanks!

Semaphores, event flags, and ports

> Misc topics, here: > > 1) As far as I can tell, the semaphores really just wind up creating queues > – is that correct? If so, if I have a semaphore of 10,000 units, that runs me > out of memory quite quickly. Is there any way around this? The semaphore implementation is a set of macros that demonstrate how a binary semaphore can be implemented using the existing queue implementation.  A queue is created that has one space, of zero length.  The length is zero as you never actually post or receive anything from the queue/semaphore, all you are interested in is whether space would be available or not. Using macros to implement binary semaphores over an existing feature in this manner, rather than having a separate semaphore module, maintains the low ROM footprint and minimises source code to facilitate testing.  The binary semaphore implementation is however limited.  If you were wanting to implement a counting semaphore you could write a simple function API that uses the macros.  The function would keep track of the count value, causing calling tasks to block only when the count reached zero.  I think this implementation would then only take a couple more bytes of RAM over that used by the binary semaphore – the extra bytes being used to maintain the count value. > 2) I’ve worked with ThreadX in the past and they had a great concept of "event > flags". That is, it’s a UINT32 that you can block on, with other trigger points > – inside or outside an ISR, and it can unblock multiple waiting threads. There > doesn’t appear to be any way to do this in FreeRTOS. Anyone interested in getting > them added? This is a topic that came up a while back.  Somebody was implementing event flags, but this was some time ago and I have not heard anything since.  Can you explain a little more of their functionality, how you want them to work.  It’s about time we added some more functionality.  Unblocking multiple tasks on an event should not be too much of a problem, but having a single task block on multiple events could be. > 3) There are currently APIs that are to be used outside and inside an ISR. Isn’t > it possible to make the core routine (e.g. QueueSend/QueueReceive) just know > when it’s in an interrupt, especially on an ARM platform? I have a procedure > that’s sometimes called from an ISR and sometimes from foreground code, and > I need to manually manage which context I’m in. It would be nice if FreeRTOS > did that automatically. To do this you would require one of four things (correct me if I’m wrong). 1)  A portable way of detecting when you are in an ISR (something that could be implemented outside of the portable layer). 2) A (non portable) way of detecting when you are inside an ISR for every architecture that FreeRTOS.org executes on, i.e. a call to the port layer would be made by the API functions to determine if you were inside an ISR or not. 3) A function that the user would have to call on entry and exit of every ISR to let the kernel know when it was in an ISR. 4) A much more heavy weight interrupt management scheme for the kernel – this might be nice but would be a problem for maintaining so many different architectures. The abcFromISR() versions of the API functions basically do not cause a context switch automatically, but instead return a value to the caller to indicate whether a context switch should be performed or not.  This allows the caller to control when the context switch occurs, and thus ensure the interrupt is cleared prior to the context switch occurring right at the end of the ISR.  Again, each architecture handles this in a different way. My design goal is to make writing ISR’s as easy and light weight as possible, and where possible allow them to be completely written in C.  This is more successful using some tools than others.  It is a compromise of coarse. Also, to choose whether the context should be saved on entry to every ISR, whether or not a switch actually takes place, or whether to just save the context should a switch be required. > 4) I’ve done a port to the Atmel SAM7S256 using the ARM SDT 2.51 – more specifically, > an Olimex SAM7P256 board. Is anyone interested in the source code? Is this the Keil IDE with the ARM compiler?  I am having a problem with these tools when using the demo version.  The demo is limited to 16K, but it seems to take the RAM image into account when calculating the size – which is a problem when using the heap_1 or heap_2 implementations.  Just setting the configTOTAL_HEAP_SIZE up can cause the ‘object code too large for demo version’ error, whereas it should not alter the object code size at all. It’s very late and my head is fuzzy – so I hope this makes sense. Regards.

Semaphores, event flags, and ports

Hey Richard! Thanks for the response. My responses to your responses: 1) Thanks much for the pointer – Sounds like all of the tools are there to create a typical semaphore, it just would be nice if they were there out of the box. All of the other OSes have them, so I thought I was quite the idiot for not noticing it. 2) Event flags basically work as an OS service that are simply a bitfield, and each thread can block on a bitfield mask. For example, let’s say we’ve created an event flag (which is by this definition 32 bits). For the sake of argument, let’s say we have an event flag with 3 bits. Each of those 3 bits in the event flag indicate that a single thread needs to do something (doesn’t matter what). The worker thread does a EventFlagsWait() with a mask of the events that will wake it up. When some other thread (or an ISR) sets one of the bits that the worker thread is waiting on, three things happen: 1) The "current flags" for the triggered bits get cleared out of the event group 2) The "triggered flags" that got set get passed off to the result of the EventFlagsWait() call 3) Any thread waiting on those flags are set to "ready to run" The question probably is, could all of this be done as a semaphore? Sure. However, there are several instances where you want to purposely wake up a thread and you don’t care how many sources may tell it to wake up, and depending upon the speed of those postings, it may overflow the queue (and cause it to be missed). Am I describing this very well? 3) Whoops… I’ve got to get my head out of "ARM Centric" mode. I’ve been staring at ARM assembly too long and lost a little perspective… 4) The ARM compiler that I’m referring to is ARM Incorporated’s ARM SDT 2.51. It’s as old as the hills. Sorry it’s not the Keil one you’re mentioning – it seems to be a hairy problem. ;-/ I had some serious problems getting the SAM7S256 working because there was a "thumb" bit set down inside one of the routines – all better now! Anyway, my changes are available. Just curious if you wanted them! BTW Richard, I wanted to let you know that I’m sending up FreeRTOS in a high altitude balloon. It’s going to receive GPS, radio telemetry over 2 meter radio, activate a cut-down device, siren, log temperature data, and take photographs. No worries – this is a hobbyist project. It’s very similar to this guy’s page: http://vpizza.org/~jmeehan/balloon/ I didn’t want to use Linux (his description of how difficult it was to get everything working was my primary concern) and what better way to get acquainted with FreeRTOS than with a cool project like this? Thanks again!

Semaphores, event flags, and ports

Hello,     I was really interested to use such an API you’ve described (planned some implementation of drivers .. so I’ve implemented the functionality you’re writing about. Some features with explanation: - events are grouped by event signallers. Maximum number of events handled through one signaller is dependand on the width of portBASE_TYPE and portTickType (smaller of the two) – the implementation could and even should be changed (uses EventList item value stored in TCB, in paraller with queues, so some corrections to queues implementation had to be introduced to coexist with my binary events implementation). - signaller must be initialized before first usage (it uses two lists intern), but it can be static struct. RAM footprint for the struct is 2 * xList + 2 * portBASE_TYPE. To store info about awaited events of tasks the implementation uses EventListItems in TCB. - events signallers holds all the information about the occurance of events, events are distinguished only in the space of event signaller. It is possible to have more than one signaller initialized and used in various tasks of FreeRTOS, single task can write to any numer of signallers but can only await events from one signaller. - the task can wait on signal of event or group of events (in this case any signalled event from group interrupts wait, the information about received signals is returned in Wait() func). - events can be signalled from inside of the interrupt – in this case the funcs XXXXFromISR must be used. - when event is signalled all the tasks awaiting it will be waked and receive the information about signalled events they waited for. - events implementation is based on the queue implementation and similar mechanisms are used to introduce wait and protection of internal structures. Unfortunately all is in its place: the queue implementation introduces horrible possible interrupt latency and event implementation repeats the behaviour. BTW I am quite sure that the queue implementation and now event implementation is not feasible to be used in the systems where exists at least one interrupt source requiring short latency handling – in AT91SAM7S it is possible to use FastForcing feature (and with GCC used as compiler one needs additionally assembler crafted interrupt routines) together with changes in FreeRTOS’ critical section handling, but what about other systems? I have to write something more about it in the next post. The design of queues should be changed – using global interrupt disable flag (through CRITICAL_SECTION) in random code sections without easily predictable amount of time spent with interrupts disabled is not The Solution (TM). Anyone interested in viewing my implementation of binary event handling please send me email to trevor|really common at|pp.org.pl. I can contribute it to FreeRTOS as well. Kind regards, Tadeusz

Semaphores, event flags, and ports

>I was really interested to use such an API you’ve described >(planned some implementation of drivers .. so I’ve implemented >the functionality you’re writing about. Cool – I need to read your post a few time to get my understanding better. >BTW I am quite sure that the queue implementation and now event >implementation is not feasible to be used in the systems where >exists at least one interrupt source requiring short latency >handling – in AT91SAM7S it is possible to use FastForcing >feature (and with GCC used as compiler one needs additionally >assembler crafted interrupt routines) together with changes in >FreeRTOS’ critical section handling, but what about other systems? On sam7 and other arm7 you can have critical section just disable irq, then use fiq for low latency interrupts.  You have to ensure fiq does not access protected areas. >I have to write something more about it in the next post. The >design of queues should be changed – using global interrupt disable >flag (through CRITICAL_SECTION) in random code sections without >easily predictable amount of time spent with interrupts disabled >is not The Solution (TM). Is this not normal? How else you prevent an interrupt accessing same queue variables members as a task? I am interested.

Semaphores, event flags, and ports

>>I have to write something more about it in the next post. The  >>design of queues should be changed – using global interrupt disable  >>flag (through CRITICAL_SECTION) in random code sections without  >>easily predictable amount of time spent with interrupts disabled  >>is not The Solution (TM).  >Is this not normal? How else you prevent an interrupt accessing same queue variables members as a task? This is done somewhat already.  The interrupt is only disabled while the queue is being locked and unlocked.  When locked it is protected from corruption by multiple access. Any more improvements are good.

Semaphores, event flags, and ports

> Cool – I need to read your post a few time to get my understanding better. Cool – maybe I will need to write it once again to get _my_ understanding better ;-). > On sam7 and other arm7 you can have critical section just disable irq, then use fiq for low latency interrupts. You > have to ensure fiq does not access protected areas. Exactly and I’ve written about it. But there are also systems which don’t have extra FIQ flags and are also ARMs which don’t have such an interrupt controller which can re-route interrupts to behave as FIQ. The section most critical (at least which seem to take most of time) > Is this not normal? How else you prevent an interrupt accessing same queue variables members as a task? > I am interested. I am not talking about different way of prevention against accessing the same variables (although in ARM it is easily implementable without disabling interrupts at all) but about shortening the blocks of instructions which must be atomically executed with interrupts disabled not to mess the internal structures of FreeRTOS – I think it is possible. I have just compared the newest implementation of queues in FreeRTOS in version 4.1.2 with that in 4.0.1 and there is improvement in the area (I am using for my project 4.0.1) but there is still place for improvement. Tadeusz

Semaphores, event flags, and ports

I would also like to see VRTX / ThreadX – style counting semaphores and flags.  I may try coding them based on the queue code.  One way to avoid excessive code space is to put the routines in more little files and make it a libarary so only the called functions get included. >>The question probably is, could all of this be done as a semaphore? Sure. However, there are several instances where you want to purposely wake up a thread and you don’t care how many sources may tell it to wake up… Sorry, a bitmask flag is not a semaphore.  The original semaphore concept was binary – locked or unlocked.  Counting semaphores extend that inone dimension – there are multiple resources available.  Flags extend it in a DIFFERENT dimension in two different uses, as either (a) a way to wait for any of multiple things rather than just one, or (b) an attempt to prevent deadlocks by getting multiple semaphores in the same atomic operation.  Using VRTX on an old project, we had processes pending on different flags for various different event masks, but *all* flags included (as the same bits) a "channel stop" and "channel clear" flag so that *all* processes could be signalled at the same time.

Semaphores, event flags, and ports

richardbarry wrote: >This is a topic that came up a while back. Somebody was >implementing event flags, but this was some time ago and >I have not heard anything since. I tried to write Trevor today and my email bounced.  If he is still out there, perhaps he will chime in. >Can you explain a little more of their functionality, how you want them to work. >It’s about time we added some more functionality. Unblocking >multiple tasks on an event should not be too much of a problem, >but having a single task block on multiple events could be. Here is what I envision: 1) First, extend the task control block: typedef struct tskTaskControlBlock {     …     portBASE_TYPE ev_events; /* initialized to 0 on task creation */     portBASE_TYPE ev_mask; /* only matters if task is delayed on events */     … } 2) Either add a new DelayedTaskList for waiting on events, or allow a different type of event in the existing queues.  Events are broadcast to ALL tasks that are waiting for a particular event, meaning when an event is posted you would have to loop through all delayed tasks and see which ones should be woken.  There are efficiency concerns here because events are broadcast and must be communicated to all tasks. 3) I think it’s OK that suspended tasks miss signals.  Tasks that are running or delayed should not miss them. 4) API modifications.  Since these events are application-wide there is no ‘create’ mechanism required.  That leaves us with: xEventPost(portBASE_TYPE newEvent) {     /* notify all live tasks */     foreach( tcb in all non-suspended tcbs in system ) {         tcb->ev_events |= newEvent;         if( task is delayed on events && ( newEvent & tcb->ev_mask != 0) ) {             wake up this task;         }     } } xEventPostFromISR()  {    … } portBASE_TYPE xEventWait(portBASE_TYPE mask, int timeout_ticks) {     portBASE_TYPE ret;     /* not sure if it is really necessary to loop here,      * but it probably isn’t any more expensive      * than a simple conditional, and it might      * give us options in the future, like the      * ability to ‘clear’ events externally.      */     while(myTCB->ev_mask & mask != 0 && timeout_not_expired) {         block here waiting for events;     }     /* clear appropriate event(s) for this task */     ret = myTCB->ev_events & mask;     myTCB->ev_events &= ~mask;     /* notify the user the event bit(s) that caused us to wake up */     return ret; } /***/ This allows for a task to wait on multiple events.  For example: #define EVENT_ENGINE_FAILURE 0x00000001 #define EVENT_TRANSMISSION_FAILURE 0x00000002 #define EVENT_AIRBAG_FAILURE 0x00000004 task() {     …     xWaitEvent(EVENT_ENGINE_FAILURE | EVENT_AIRBAG_FAILURE);     … } Note that I do not understand FreeRTOS well enough to know how to handle the blocking/unblocking, or the timeout.  This is just notional.  I am not really up-to-speed enough on FreeRTOS to write this myself, but I would be happy to help, do code reviews, and test.

Semaphores, event flags, and ports

I thought of something else perhaps worth considering, though it would complicate things a bit.  We could make broadcasting of signals more efficient with the concept of "process groups", and not bother updating tcb->ev_events on processes not in the same process group.  If this involved another thread of linked lists it probably wouldn’t be worthwhile — just a thought.

Semaphores, event flags, and ports

I am writing this message, because I want people pay attention to the implemetation of semaphores. The today implementation is not so good because it use a lot of RAM as it used the queue implementation. Look at queue structure!!! And if you looked at the semaphore macros you see that we have one element with the size of zero. typedef struct QueueDefinition {     signed portCHAR *pcHead; we do not need because the size is zero        signed portCHAR *pcTail; we do not need because the size is zero        signed portCHAR *pcWriteTo;    we do not need because the size is zero            signed portCHAR *pcReadFrom;    we do not need because the size is zero            xList xTasksWaitingToSend;    we do not need because the do not blocking then giving gave                  xList xTasksWaitingToReceive;    we use this if we take semaphore it is used for store the list of waiting tasks            unsigned portBASE_TYPE uxMessagesWaiting; is 0 or 1           unsigned portBASE_TYPE uxLength; is  always 1             unsigned portBASE_TYPE uxItemSize; is always 1            signed portBASE_TYPE xRxLock;    i do not know exactly i suppose the do not use this             } xQUEUE; I think that all we need is 1. One xLiskWaitingToTake List of tasks                             2. If it is a counting semaphore we need the variable – a counter But!!! The xList has a field xMiniListItem wich is a structure and it plays a role as a the end Item if all List. And all ListItems has xItemValue field which is used for sorting. There it is used to sort in priority order or time order. In xMiniListItem it is always equal to MaxPortTickType. Then the counting semaphore value is not equal to zero the list is empty the can use this variable to count. Then the counting semaphore is equal to zero the must block the taking task. We can made a hook. Internaly in semaphore the can count not from zero till the n. But the can count from -1 till n-1.  

Semaphores, event flags, and ports

I have wrote some implementation of semaphores as I wrote above, but I have not test it yet. And I do not have time to do this now, and I don’t know there to send this sources. Maybe someone help me and watch or test them. This implementation is based on vTaskPlaceOnEventList.I think it is very useful function. I appeal to Richard Barry. I hope he wrote some documentation about this function on his official site FreeRTOS.org May be it will help people to write their own extensions to the FreeRTOS as a event flags fifo and etc.

Semaphores, event flags, and ports

Hi – I would be very interested to take a look at your implementation.  Can you send me the source to r dot barry at freertos.org? The semaphore implementation is written to make use of the existing queue functionality.  It should be noted that the existing semaphore implementation has absolutely zero impact on the executable code size – as macros on top of queues they add no new code at all.  Also the semaphore structures include all the event management details.  Some RTOS’s implement an event management system as a separate module, so creating a semaphore requires both the semaphore and an event control block to be allocated.  In FreeRTOS.org only the semaphore need be allocated. Regards.

Semaphores, event flags, and ports

I understand that if we are using such macros implementation we does not write any code and it dose not use Flash ROM of microcontrollers but look at my Atmega128 it has 128k FLASH ROM and only 4k RAM. And also I want to say that the new code for semaphores is stored only once for all semaphores, but the wasting of RAM is more because the can have many Semaphore structures in RAM.

Semaphores, event flags, and ports

I think this was meant for me (?) >I would be very interested to take a look at your implementation. I don’t have one yet … it was more of an idea.  But I would be willing to work on it to contribute, just might take a while :)