Implementing a binary semaphore ?

A

Anton Erasmus

Guest
Hi,

How would one go about implementing a binary semaphore in verilog ?
I have 2 MCUs that have to share a resource. I want to implement a
semaphore in an EPLD which is connected to both MCUs.
On a read bus cycle from any of the MCUs, the current value of the
semaphore should be read, and simultaneously it should be set.
If it was reset, then the resource is available. After the resource
has been used the MCU should use a write bus cycle to reset the
semaphore. The MCUs uses an Intel type bus. i.e. separate RD and WR
signals.

Regards
Anton Erasmus
 
On Wed, 06 Jul 2005 09:15:11 +0100, Jonathan Bromley
<jonathan.bromley@doulos.com> wrote:

On Tue, 05 Jul 2005 19:27:30 +0200, Anton Erasmus
nobody@spam.prevent.net> wrote:

How would one go about implementing a binary semaphore in verilog ?
I have 2 MCUs that have to share a resource. I want to implement a
semaphore in an EPLD which is connected to both MCUs.

Swapnajit has indicated how you can do a *software* semaphore
in Verilog (answer: with very great difficulty - thanks Verilog!)
but I think you want a *hardware* test-and-set.
Click to expand...
Thanks.

Yes, I wanted a synthysizable version.

Where would one want a "software" semaphore in Verilog ?
Why would the synthysizable version not work as a "software"
semaphore ?

[Snipped]

Regards
Anton Erasmus
 
On Tue, 05 Jul 2005 19:27:30 +0200, Anton Erasmus
<nobody@spam.prevent.net> wrote:

How would one go about implementing a binary semaphore in verilog ?
I have 2 MCUs that have to share a resource. I want to implement a
semaphore in an EPLD which is connected to both MCUs.
Click to expand...
Swapnajit has indicated how you can do a *software* semaphore
in Verilog (answer: with very great difficulty - thanks Verilog!)
but I think you want a *hardware* test-and-set. It's
pretty easy as a piece of synchronous logic: you need just
two flip-flops. Note that it's not a true semaphore but
rather a simple test-and-set operation, so I've called
the register "TAS".

reg TAS, TAS_readout;
always @(posedge clock or posedge reset)
if (reset) begin
TAS<= 1'b0;
TAS_readout <= 1'b0;
end else if (reading_TAS) begin // doing a read cycle
TAS_readout <= TAS;
TAS <= 1'b1;
end else if (writing_TAS) begin
TAS<= 1'b0;
TAS_readout <= 1'b0;
end

Of course, you need to extract the enable signals
"reading_TAS" and "writing_TAS" from the bus strobes,
address decodes and so on. TAS_readout is the value
that you should present to the data bus on read cycles.

You may also wish to be able to write a '1' to the flag
explicitly, to simplify self-test operations. That's
left as a trivial exercise for the reader :)
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
 
On 6 Jul 2005 22:04:48 -0700, "Swapnajit Mittra" <mittra@juno.com>
wrote:

Swapnajit has indicated how you can do a *software* semaphore
in Verilog (answer: with very great difficulty - thanks Verilog!)

Dekker certainly will take offence at that!
Click to expand...
I don't think so. Dekker's algorithm counts as "extreme
difficulty" in my book, given that Verilog is supposed to
be a concurrent language. A concurrent language that
provides arbitrary indeterminate interleaving of runnning
processes, without providing any built-in synchronisation
primitive to manage that, is asking for trouble.

[Dekker's algorithm]
is just about the only *100% Correct All The Time* algorithm
for mutual exclusion of resources between two processes.
Click to expand...
Hmmm... maybe, but I would want some time to convince myself
whether you're right or wrong. Many decades of research
and practical work on concurrency have, I think, provided
more than one useful method :)

There is no such thing as a software semaphore or a hardware
one. Semaphore is a concept whether you implement it in a
software or hardware.
Click to expand...
For sure. I don't think the OP wanted a semaphore, really.
But of course, once you have any robust mutual exclusion
mechanism, you can implement semaphores or any other
synchronisation primitive that takes your fancy.
It's just a shame that dear old Verilog didn't provide
mutual exclusion of some kind as part of the language.

However, Verilog *does* offer a discrete-event model of
computation that can easily be used to implement a
test-and-set, and what's more that model turns out to
be synthesisable. Great news if you're building hardware.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
 
Hi Jonathan,

This is a very nice way of implementing test-and-set in hardware. 'Just
wanted
to point out one obvious "feature" of your method (you've noticed it too, no
doubt!):

If "reading_TAS" is set for more then one clock period, then the original
values of
TAS and TAS_readout get clobbered!

I'd probably implement this semaphore as a small FSM; 'would make me breathe
a
lot easier!

Cheers!
bala

"Jonathan Bromley" <jonathan.bromley@doulos.com> wrote in message
news:774nc110g2hb56vvre3jtnb5lbm013j3hf@4ax.com...
On Tue, 05 Jul 2005 19:27:30 +0200, Anton Erasmus
nobody@spam.prevent.net> wrote:

How would one go about implementing a binary semaphore in verilog ?
I have 2 MCUs that have to share a resource. I want to implement a
semaphore in an EPLD which is connected to both MCUs.

Swapnajit has indicated how you can do a *software* semaphore
in Verilog (answer: with very great difficulty - thanks Verilog!)
but I think you want a *hardware* test-and-set. It's
pretty easy as a piece of synchronous logic: you need just
two flip-flops. Note that it's not a true semaphore but
rather a simple test-and-set operation, so I've called
the register "TAS".

reg TAS, TAS_readout;
always @(posedge clock or posedge reset)
if (reset) begin
TAS<= 1'b0;
TAS_readout <= 1'b0;
end else if (reading_TAS) begin // doing a read cycle
TAS_readout <= TAS;
TAS <= 1'b1;
end else if (writing_TAS) begin
TAS<= 1'b0;
TAS_readout <= 1'b0;
end

Of course, you need to extract the enable signals
"reading_TAS" and "writing_TAS" from the bus strobes,
address decodes and so on. TAS_readout is the value
that you should present to the data bus on read cycles.

You may also wish to be able to write a '1' to the flag
explicitly, to simplify self-test operations. That's
left as a trivial exercise for the reader :)
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
Click to expand...
 
On Mon, 18 Jul 2005 22:03:25 -0700, "Needamangalam Balachander"
<nbbala@hotmail.com> wrote:

Hi Jonathan,
Just wanted to point out one obvious "feature" of your method
(you've noticed it too, no doubt!):
If "reading_TAS" is set for more then one clock period, then the
original values of TAS and TAS_readout get clobbered!
Click to expand...
Indeed you are right; as far as my design is concerned, this
amounts to performing the read operation twice. There is a
complete read operation on each clock cycle for which "reading_TAS"
is asserted.

I'd probably implement this semaphore as a small FSM;
would make me breathe a lot easier!
Click to expand...
It's always nice to find a truly reliable way to make sure
that things happen only once if that's what you want.
Personally I find it's easier to think about if I use the
discipline of "each enabled clock cycle performs the operation",
and then use synchronous edge detection to convert long pulses
into single-cycle pulses wherever necessary. But of course
you are right, it's something that must be given careful
consideration when you have stuff like my read operation
that has side-effects on each cycle.

--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
 
You can use Dekker's algorithm:
<URL:
http://www.csee.wvu.edu/~jdm/classes/cs356/notes/mutex/Dekker.html>

You can also use SystemVerilog that proposes semaphore as a built-in
class.
<URL: http://www.project-veripage.co­­m/ipcs_1.php>

- Swapnajit.
--
SystemVerilog, DPI, Verilog PLI and all other good stuffs.
Project VeriPage: <URL: http://www.project-veripage.co­­m/>
Get information on new articles:
<URL: http://www.project-veripage.co­­m/list/?p=subscribe&id=1>
 
Swapnajit has indicated how you can do a *software* semaphore
in Verilog (answer: with very great difficulty - thanks Verilog!)
Click to expand...
Dekker certainly will take offence at that! His algorithm has been
implemented in hardware by scores (including yours truly [1]).
Moreover, besides being the first, except Peterson's algorithm,
his is just about the only *100% Correct All The Time* algorithm
for mutual exclusion of resources between two processes.

There is no such thing as a software semaphore or a hardware
one. Semaphore is a concept whether you implement it in a
software or hardware. Similarly, mutual exclusion algorithm
proposed by Dekker (AFAIK, invented before computers) can
be implemented in hardware, software or, to give an extreme
example, by two fork lifts removing garbages from the same
dump.

[1] The SPARC Architecture Manual Version 9. Page 316.

- Swapnajit.
--
SystemVerilog, DPI, Verilog PLI and all other good stuffs.
Project VeriPage: <URL: http://www.project-veripage.co­­­m/>
Get information on new articles:
<URL: http://www.project-veripage.co­­­m/list/?p=subscribe&id=1>
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top