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
Sync question
Moderators: hgm, Rebel, chrisw
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Sync question
No such animal. You have two choices;Gerd Isenberg wrote: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
(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.
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Sync question
There's three levels of correctness for what you could do:Gerd Isenberg wrote: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
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;
}
-
- Posts: 88
- Joined: Wed Mar 25, 2009 12:49 pm
Re: Sync question
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.
Of course, there's nothing keeping all the locks from living in the same variable as long as you have less than 65 threads.
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Sync question
You mean a 64-bit int? That's pretty much equivalent to mine, except mine can handle 18 quintillion threads.Teemu Pudas wrote: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.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Sync question
I had something like this in mind, which might end inside a dead lock:bob wrote:No such animal. You have two choices;Gerd Isenberg wrote: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
(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.
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;
}
-
- Posts: 88
- Joined: Wed Mar 25, 2009 12:49 pm
Re: Sync question
640 K threads ought to be enough for anyone.Zach Wegner wrote:You mean a 64-bit int? That's pretty much equivalent to mine, except mine can handle 18 quintillion threads.
-
- Posts: 2250
- Joined: Wed Mar 08, 2006 8:47 pm
- Location: Hattingen, Germany
Re: Sync question
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 headacheZach Wegner wrote: 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; }
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Sync question
Hmm, I saw Teemu point out a bug, but he deleted it? Anyways, correction:
reading:
writing:
reading:
Code: Select all
while (r < 0 || !cmpxchg(lock,r,r+1))
Code: Select all
while (r != 0 || !cmpxchg(lock,0,-1))
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Sync question
Unfortunately that will kill cache performance... Any atomic type operation is a killer.Teemu Pudas wrote: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.