Sync question

[Gerd Isenberg]

Let say you have some data, for instance a cacheline, which is frequently probed by several threads (or processes), but very rarely (let say less than 0.01% of the reads) written by the same threads (or processes).

I don't want multiple parallel reads (which might occur quite often) mutual exclusive to block each other aka entering a critical section, but only write mutual exclusive versus reads - any read and write request has to wait until an ongoing write is finished, any write request has to wait until all pending reads (or one write) are finished. Is there any standard pattern to implement such a kind of Mutex or Semaphore?

Thanks,
Gerd

[bob]

Let say you have some data, for instance a cacheline, which is frequently probed by several threads (or processes), but very rarely (let say less than 0.01% of the reads) written by the same threads (or processes).

I don't want multiple parallel reads (which might occur quite often) mutual exclusive to block each other aka entering a critical section, but only write mutual exclusive versus reads - any read and write request has to wait until an ongoing write is finished, any write request has to wait until all pending reads (or one write) are finished. Is there any standard pattern to implement such a kind of Mutex or Semaphore?

Thanks,
Gerd

No such animal. You have two choices;

(1) use mutex locks so that reads can't happen while writes are in progress, and vice-versa. If this is a common action, it will kill performance.

(2) use some other trick such as the "lockless hash" approach used in Crafty so that you can determine that the data has been broken without needing a lock.

You didn't mention how "big" the data item is. If it is a single word, you are in good shape to control things. If it is multiple words, then out-of-order writes can become a killer. You can always separate the things so that they don't fit in the same cache line. Or if you can modify your code so that the write won't wreck things if you read an old and a new value at the same time, you can ignore it. Or you can take action as given in (1) or (2).

You can't do a "write lock" because you can't allow writes to happen while reads are in progress, and you can't do read locks as they will interfere with each other for no good reason and kill performance.

[Zach Wegner]

Let say you have some data, for instance a cacheline, which is frequently probed by several threads (or processes), but very rarely (let say less than 0.01% of the reads) written by the same threads (or processes).

I don't want multiple parallel reads (which might occur quite often) mutual exclusive to block each other aka entering a critical section, but only write mutual exclusive versus reads - any read and write request has to wait until an ongoing write is finished, any write request has to wait until all pending reads (or one write) are finished. Is there any standard pattern to implement such a kind of Mutex or Semaphore?

Thanks,
Gerd

There's three levels of correctness for what you could do:

1. Only lock on writes. If the data is more than a cache line (or word? Bob would know I guess), then it might become corrupted.

2. Lock on reads only if the lock is already held. This will usually help against corruption as it happens in case 1, but there is still a window where a write can slip in after the mutex read.

3. Do a complicated compare-and-swap on a read. Most of the time, the lock isn't held, so you can read freely. But you still have to increment a counter, so that we only write when there are no readers. I suppose it would look something like this:

Code: Select all

read()
{
  // r is how many readers are reading now, or -1 if someone is writing
  r = lock;
  while (r >= 0 && !cmpxchg(lock,r,r+1))
    r = lock;
  
  // do read here
  
  ASSERT(lock>=1);
  r = lock;
  while (!cmpxchg(lock,r,r-1))
    r = lock;
}
write()
{
  // acquire lock
  r = lock;
  while (r == 0 && !cmpxchg(lock,0,-1))
    r = lock;

  // do write here

  ASSERT(lock==-1);
  lock = 0;
}

[Teemu Pudas]

Multiple locks. Each reader only uses one, a writer has to acquire them all.

Of course, there's nothing keeping all the locks from living in the same variable as long as you have less than 65 threads.

[Zach Wegner]

Multiple locks. Each reader only uses one, a writer has to acquire them all.

Of course, there's nothing keeping all the locks from living in the same variable as long as you have less than 65 threads.

You mean a 64-bit int? That's pretty much equivalent to mine, except mine can handle 18 quintillion threads.

[Gerd Isenberg]

Let say you have some data, for instance a cacheline, which is frequently probed by several threads (or processes), but very rarely (let say less than 0.01% of the reads) written by the same threads (or processes).

I don't want multiple parallel reads (which might occur quite often) mutual exclusive to block each other aka entering a critical section, but only write mutual exclusive versus reads - any read and write request has to wait until an ongoing write is finished, any write request has to wait until all pending reads (or one write) are finished. Is there any standard pattern to implement such a kind of Mutex or Semaphore?

Thanks,
Gerd

No such animal. You have two choices;

(1) use mutex locks so that reads can't happen while writes are in progress, and vice-versa. If this is a common action, it will kill performance.

(2) use some other trick such as the "lockless hash" approach used in Crafty so that you can determine that the data has been broken without needing a lock.

You didn't mention how "big" the data item is. If it is a single word, you are in good shape to control things. If it is multiple words, then out-of-order writes can become a killer. You can always separate the things so that they don't fit in the same cache line. Or if you can modify your code so that the write won't wreck things if you read an old and a new value at the same time, you can ignore it. Or you can take action as given in (1) or (2).

You can't do a "write lock" because you can't allow writes to happen while reads are in progress, and you can't do read locks as they will interfere with each other for no good reason and kill performance.

I had something like this in mind, which might end inside a dead lock:

Code: Select all

char CACHE_ALIGN gloabalData[64];

volatile int ReadCount = 0;
volatile bool isWritePending = false;

void read (void *pLocalBuffer) {
   ++ReadCount;
   while (isWritePending); // wait until write finished
   memcpy (pLocalBuffer, gloabalData, 64);
   --ReadCount;
}

void write (void *pLocalBuffer) {
    while (isWritePending || lockexchange (isWritePending, true));
    while ( readCount );  // wait for pending reads 
    memcpy (gloabalData, pLocalBuffer, 64);
    isWritePending = false;
}

[Teemu Pudas]

You mean a 64-bit int? That's pretty much equivalent to mine, except mine can handle 18 quintillion threads.

640 K threads ought to be enough for anyone.

[Gerd Isenberg]

3. Do a complicated compare-and-swap on a read. Most of the time, the lock isn't held, so you can read freely. But you still have to increment a counter, so that we only write when there are no readers. I suppose it would look something like this:

Code: Select all

read()
{
  // r is how many readers are reading now, or -1 if someone is writing
  r = lock;
  while (r >= 0 && !cmpxchg(lock,r,r+1))
    r = lock;
  
  // do read here
  
  ASSERT(lock>=1);
  r = lock;
  while (!cmpxchg(lock,r,r-1))
    r = lock;
}
write()
{
  // acquire lock
  r = lock;
  while (r == 0 && !cmpxchg(lock,0,-1))
    r = lock;

  // do write here

  ASSERT(lock==-1);
  lock = 0;
}

Ok, that is what I wanted. I thought about a distinct boolean as write indicator and a read counter. But one variable as combined read and write indicator is sufficient (like using MSB as boolean write indicator) and avoids headache

[Zach Wegner]

Hmm, I saw Teemu point out a bug, but he deleted it? Anyways, correction:

reading:

Code: Select all

  while &#40;r < 0 || !cmpxchg&#40;lock,r,r+1&#41;)

writing:

Code: Select all

  while (r != 0 || !cmpxchg(lock,0,-1))

[bob]

Multiple locks. Each reader only uses one, a writer has to acquire them all.

Of course, there's nothing keeping all the locks from living in the same variable as long as you have less than 65 threads.

Unfortunately that will kill cache performance... Any atomic type operation is a killer.