semaphores using C

Go To Last Post
9 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'm trying to implement a semaphore p() and v() function in C and I would like some feedback on my code. Am I on the right track?

typedef char	SemaphoreType;

void 		SemP(SemaphoreType sem)
{
	enter();
	
	while( !(sem > 0) )
	{
		enter();
		Delay();
		exit();
	}
	
	sem--;
	
	exit();
}


void		SemV(SemaphoreType sem)
{
	enter();
	
	sem++;
	
	exit();
}

The enter() function saves the status register to the stack and disables interrupts. The exit() function restores the status register from the stack. (typical enter/exit critical section code, done in assembly instructions) Delay() is a short delay (essentially a few "nop" instructions).

I would like the semaphore to block until the resource becomes available. Are there any contention or timing issues that might arise using the above code?

Cheers.

Sheldon

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
typedef char   SemaphoreType;

1) You probably need to make a pointer to this type, so it's shared.
This could be done in the typedef or the functions.
2) By making this an unsigned type you double its range, in case you
want someday to extend this to a counting semaphore.

      enter();
      Delay();
      exit();

The enter and exit calls look backwards; Presumably you want to
enable, then delay, then disable again.

Quote:
The enter() function saves the status register to the stack

Whose stack? Even if these functions are inline, it's not clear how they can
declare the variable they need to save the state. My suggestion: make it
explicit, e.g.
SREG_type oldstate; oldstate = enter(); exit(oldstate);
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Also: I assume you're building this into some sort of concurrency
mechanism (task scheduler), so Delay will actually cause something
to run. If you're doing this with ISRs, you need to be very careful about
nested interrupts and deadlocks.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you have semaphores that are only waited on from the mainline, and only posted to from inside an ISR, and you're simply waiting for certain events to happen inside the ISR, then it may be a little overkill.

I've only really thought of full-fledged semaphores as useful in the context of a pre-emptive multitasking environment, where you can actually post() and wait() from inside any piece of user code without worry of spinlocks, and with less worries about deadlocks.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

tell me more.....how can you prevent any chance of deadlock.

Task A waiting for resource currently held by task B
Task B waiting for resource currently held by task C
Task C waiting for resource currently held by task A

deadlock! what stratagies could be used to avoid this from happening.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

sparkymark567 wrote:
tell me more.....how can you prevent any chance of deadlock.

I stated less worries about deadlock, not no chance of deadlock. In a non-preempting system, something as simple as the following would lead to deadlock:

Task A waiting for resource currently held by task B.
Task B wants to release its resource, but can't because task A is running.

Well, I guess this is still exclusively the domain of spinlocks. Oh, well.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have a question about semaphores. (not off topic I hope)

As both functions: signal(semaphore) and wait(semaphore) need to be indivisable operaitions...i.e. no possibility of a scheduler call while exectuting either the signal or wait; global interrupts need to be disabled.

But, apparantly the HC12 has a "test, set if clear" instruction (or something similar). i.e. a single instruction which can be used for manipulating semaphores. I'm not sure how this would be implemented (as I thought semaphores live in ram). Can it be done?

Are there any AVR asssmbly tricks which could be used to achieve the same result....i.e. safe use of semaphores with global interrupts always enabled.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Well, what the OP wrote was effectively a spin-lock, so your observations apply.

I have seen one (count 'em: one) system which would detect deadlocks. It's been
many years, and the context was slightly different, but as I recall the mechanism
was built around a transitive closure of the states of all the semaphores in the
system. It was computationally complex (N**2? N**3?) but (a) careful filtering kept
N sorta-not-too-big and (b) it was an educational system so the value was seen to
outweigh the cost.

If a deadlock attempt was detected it would throw an error. This was fine on a multi-
user system, but not so applicable to an MCU where avoidance is really the only choice.

I seem to recall some rules of thumb for avoidance as:
1) Don't hold more than one lock at a time.
2) If you must disobey (1), obtain them in a pre-defined order, and release them in
the reverse order (think in terms of "outer" and "inner" locks).
3) Think about what you're doing. E.g. main() can never interrupt an ISR, no matter
how hard you try.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Can it be done?

I'm not familiar with this particular instruction, but my assumption (based
on the name) is Yes.

There are many variations, but what you need is a mechanism which is
capable of atomically: (a) fetching (in some form) a value from a shared
location (typically RAM) and (b) storing some value in that location. In
AVR terms:

    ldi    Rx,LOCK_VALUE
    cli
    lds   Ry,lock_byte
    sts   lock_byte,Rx
    sei

after which, if Ry has the value LOCK_VALUE, someone else got in
ahead of you, so you (in some form) loop back and try again. From
the looks of it, the HC12 gets Bonus Points for combining some of
these steps so e.g. it takes no registers(?). Others (x86:SWAP,
ARM:XCHG) get Bonus Points for locking the external memory bus
so you can use it for MP locks.

Quote:
Are there any AVR asssmbly tricks

I haven't seen anything obvious in the AVR instruction set which fits
this description. One possibility is that (in a RISC-ish notion) the above
sequence only takes 6 cycles (7 if you need to save/restore SREG),
so it isn't really worthwhile to architect a separate instruction for it.

Edit: It's probably obvious, but I'll just point out that the Unlock operation
has no atomicity concerns:

   ldi   Rx,NOTLOCKED_VALUE
   sts   lock_byte,Rx

The OP needed the enter/exit for this since he was using a non-atomic
operation (++) to update the byte.