Semaphore between different Processors

[electroRF]

Hi,

Say that there is a specific Variable in Shared Memory, which two Processors read and write.

How do you prevent a situation in which while Processor A writes to it, Processor B reads from it?

Thank you.

 

[tunedwolf]

Tokens. When one has the token, the other has to sulk until it's relinquished

 

[electroRF]

Hi,
Thank you.

I believe there's a problem with that.

Say that now the Token is Available.


Now Both Processors try to take the Token at the same time.

In this case, Both Processor will see that it's available, and will both take the Token.

That is since both will firstly read the Token's value at the same time, and will see that it's available.

 

[alec_t]

Do the two processors have equal priority? If not, the lower priority one can wait for the higher priority one.

 

[tunedwolf]

There are ways to deal with that situation like checking that nobody else has the same token, disabling write access until that is confirmed for example. You will need to set up some form of arbitration protocol to control which processor wins the toss in the event.

 

[electroRF]

Hi,

Could you please suggest on such mechanism for arbitration?


alec_t

yes, they both have the same priority.
How will one wait for the other, i mean, it firstly needs to know it should wait.

 

[be80be]

You have to be using a Arm 7 maybe a ARMv7-R architecture both cores in one of those and do a task at the same time.

 

[alec_t]

How will one wait for the other, i mean, it firstly needs to know it should wait.

If processor A were clocked slightly earlier than processor B (assuming both have the same clock rate) then A could set a flag which B would have to check.
Off the top of my head, if the clocking of A and B were at arbitrary times then perhaps each could check to see if the memory is being accessed, then check again after a set delay which is different for A and B. Only if both checks showed no current access would access be granted.

 

[electroRF]

Hi Alec,

if both Read the Value at the same time, or one slightly after another, then they will both read it's available.

Then, they'll both write that it's Not-Available (it doesn't matter who writes first, because they both read it's Available).

 

[nsaspook]

The first thing you need is shared memory that is coherent across all processors (not cached) then you need the equivalent atomic compare-and-swap instruction on both processors to create a token.
https://en.wikipedia.org/wiki/Compare-and-swap

 

[alec_t]

if both Read the Value at the same time, or one slightly after another, then they will both read it's available.

That's why I suggested a double check using different delays for A and B. On the second check, the processor with the longer delay would find it unavailable.

 

[electroRF]

The first thing you need is shared memory that is coherent across all processors (not cached) then you need the equivalent atomic compare-and-swap instruction on both processors to create a token.
https://en.wikipedia.org/wiki/Compare-and-swap

Hi nsapook.

Thank you very much.

I read about the Compare-and-Swap operation,
However, it deals with different processes running on the same processor.

It's not the same as different processes on different processor.

I mean,
How do you gain the ATOMIC();(see below) between Different Processors?

int compare_and_swap(int* reg, int oldval, int newval)
{
  ATOMIC();
  int old_reg_val = *reg;
  if (old_reg_val == oldval)
     *reg = newval;
  END_ATOMIC();
  return old_reg_val;
}

 

[nsaspook]

Hi nsapook.

Thank you very much.

I read about the Compare-and-Swap operation,
However, it deals with different processes running on the same processor.

It's not the same as different processes on different processor.

It works on multiprocessor systems if they have hardware support (Shared memory and locking primitive instructions). I have no idea about the capabilities of your system.

As of 2013, most multiprocessor architectures support CAS in hardware. As of 2013, the compare-and-swap operation is the most popular synchronization primitive for implementing both lock-based and non-blocking concurrent data structures.[1]

 

[tunedwolf]

Hi,

Could you please suggest on such mechanism for arbitration?


alec_t

yes, they both have the same priority.
How will one wait for the other, i mean, it firstly needs to know it should wait.

Here's one quick and dirt way, but I warn you, I haven't really thought this through, so treat it more as food for thought...

Let's say you have a number generator randomly spitting out values 1-10 which temporarily stores two of those values, making sure that each is different. Each value is assigned to a processor. Whenever a token request is made and both processors want access to the same memory location, each already has a priority assigned, lowest number wins the toss and the other processor has to wait until the token is relinquished. Either way, whenever the token becomes free, the number generator starts allocating numbers again