Seqlock:
A seqlock is a special locking mechanism used in Linux for supporting fast writes of shared variables between two parallel operating system routines.
It is a reader-writer consistent mechanism which avoids the problem of writer starvation.
A seqlock consists of storage for saving a sequence number in addition to a lock.
The lock is to support synchronization between two writers and the counter is for indicating consistency in readers.
Whenever writer updates the shared data, it increments the sequence number, both after acquiring the lock and before releasing the lock. Reader will read the sequence number before and after reading the shared data. If the sequence number is odd on either occasion, it means the lock is acquired by the writer while the reader was reading data and data may have changed. And if the sequence numbers are different, a writer has changed the data while it was being read. In either case readers retry, until they read the same even sequence number before and after.
The reader never blocks, but it may have to retry if a write is in progress; this speeds up the readers in the case where the data was not modified, since they do not have to acquire the lock as they would with a traditional read-write lock.
Also, writers do not wait for readers, whereas with traditional read-write locks they do, leading to potential resource starvation in a situation where there are a number of readers (because the writer must wait for there to be no readers).
Because of these two factors, seqlocks are more efficient than traditional read-write locks for the situation where there are many readers and few writers.
The drawback is that if there is too much write activity or the reader is too slow, they might livelock (and the readers may starve).
It should also be noted that the technique will not work for data that contains pointers, because any writer could invalidate a pointer that a reader has already followed. In this case, using read-copy-update synchronization is preferred.
RCU (Read Copy Update):
RCU Locks allows reads to occur concurrently with updates. Let us have a pointer ptr pointing to the shared data. Reader works by reading the data pointed by the ptr and Update is done by first allocating data and then setting the value of ptr to the newly allocated data.
As you can see, setting value of a location in memory is an atomic operation so, no locks are required. But there are other concerns. At any time more than one readers could be reading the data pointed by the same pointer, in that case freeing this data would give some unexpected results. So, RCU ensures that data are not freed up until all pre-existing read-side critical sections complete.
RCU is made up of three fundamental mechanisms:
Publish Subscripe Mechanism (for insertion)
Wait for Pre-Existing RCU readers to complete (for deletion)
Maintain multiple versions of recently update objects (to allow readers to tolerate concurrent insertions and deletions)
With RCU, you can concurrently update data containing pointers but in SeqLock you cannot. Because, it may happen the reader has dereferenced the pointer and reading data pointed by it but in the middle of this process writer just invalidate it.
It may seem to you that in Seqlock and in RCU both readers and writers can work concurrently?
Well, no. In Seqlock whenever a reading is working and a writer steps in then according to the protocol reader has to retry because data may have been changed by the writer in that time. So, both reader and writer can concurrently run but cannot work concurrently.
In contrast, RCU readers can perform useful work even in presence of concurrent RCU updaters.
Although, in Seqlock writers requires locking but in RCU both readers and writers can altogether avoid it. Both of them works best when there are few writers but more readers.
How can the updater tell when a grace period has completed if the RCU readers give no indication when they are done?
Just as with spinlocks, RCU readers are not permitted to block, switch to user-mode execution, or enter the idle loop. herefore, as soon as a CPU is seen passing through any of these three states, we know that that CPU has exited any previous RCU read-side critical sections. So, if we remove an item from a linked list, and then wait until all CPUs have switched context, executed in user mode, or executed in the idle loop, we can safely free up that item.
Reference :
1) https://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/x490.html
2) https://www.kernel.org/doc/Documentation/RCU/rcu.txt
3)https://www.kernel.org/doc/Documentation/RCU/listRCU.txt
4)http://www.rdrop.com/users/paulmck/RCU/
A seqlock is a special locking mechanism used in Linux for supporting fast writes of shared variables between two parallel operating system routines.
It is a reader-writer consistent mechanism which avoids the problem of writer starvation.
A seqlock consists of storage for saving a sequence number in addition to a lock.
The lock is to support synchronization between two writers and the counter is for indicating consistency in readers.
Whenever writer updates the shared data, it increments the sequence number, both after acquiring the lock and before releasing the lock. Reader will read the sequence number before and after reading the shared data. If the sequence number is odd on either occasion, it means the lock is acquired by the writer while the reader was reading data and data may have changed. And if the sequence numbers are different, a writer has changed the data while it was being read. In either case readers retry, until they read the same even sequence number before and after.
The reader never blocks, but it may have to retry if a write is in progress; this speeds up the readers in the case where the data was not modified, since they do not have to acquire the lock as they would with a traditional read-write lock.
Also, writers do not wait for readers, whereas with traditional read-write locks they do, leading to potential resource starvation in a situation where there are a number of readers (because the writer must wait for there to be no readers).
Because of these two factors, seqlocks are more efficient than traditional read-write locks for the situation where there are many readers and few writers.
The drawback is that if there is too much write activity or the reader is too slow, they might livelock (and the readers may starve).
It should also be noted that the technique will not work for data that contains pointers, because any writer could invalidate a pointer that a reader has already followed. In this case, using read-copy-update synchronization is preferred.
RCU (Read Copy Update):
RCU Locks allows reads to occur concurrently with updates. Let us have a pointer ptr pointing to the shared data. Reader works by reading the data pointed by the ptr and Update is done by first allocating data and then setting the value of ptr to the newly allocated data.
As you can see, setting value of a location in memory is an atomic operation so, no locks are required. But there are other concerns. At any time more than one readers could be reading the data pointed by the same pointer, in that case freeing this data would give some unexpected results. So, RCU ensures that data are not freed up until all pre-existing read-side critical sections complete.
RCU is made up of three fundamental mechanisms:
Publish Subscripe Mechanism (for insertion)
Wait for Pre-Existing RCU readers to complete (for deletion)
Maintain multiple versions of recently update objects (to allow readers to tolerate concurrent insertions and deletions)
With RCU, you can concurrently update data containing pointers but in SeqLock you cannot. Because, it may happen the reader has dereferenced the pointer and reading data pointed by it but in the middle of this process writer just invalidate it.
It may seem to you that in Seqlock and in RCU both readers and writers can work concurrently?
Well, no. In Seqlock whenever a reading is working and a writer steps in then according to the protocol reader has to retry because data may have been changed by the writer in that time. So, both reader and writer can concurrently run but cannot work concurrently.
In contrast, RCU readers can perform useful work even in presence of concurrent RCU updaters.
Although, in Seqlock writers requires locking but in RCU both readers and writers can altogether avoid it. Both of them works best when there are few writers but more readers.
How can the updater tell when a grace period has completed if the RCU readers give no indication when they are done?
Just as with spinlocks, RCU readers are not permitted to block, switch to user-mode execution, or enter the idle loop. herefore, as soon as a CPU is seen passing through any of these three states, we know that that CPU has exited any previous RCU read-side critical sections. So, if we remove an item from a linked list, and then wait until all CPUs have switched context, executed in user mode, or executed in the idle loop, we can safely free up that item.
Reference :
1) https://www.kernel.org/pub/linux/kernel/people/rusty/kernel-locking/x490.html
2) https://www.kernel.org/doc/Documentation/RCU/rcu.txt
3)https://www.kernel.org/doc/Documentation/RCU/listRCU.txt
4)http://www.rdrop.com/users/paulmck/RCU/
No comments:
Post a Comment