* [KJ] question about race condition
@ 2007-01-18 19:27 Shaobo Liu
2007-01-18 20:07 ` Jaco Kroon
2007-01-18 20:16 ` Alexey Dobriyan
0 siblings, 2 replies; 3+ messages in thread
From: Shaobo Liu @ 2007-01-18 19:27 UTC (permalink / raw)
To: kernel-janitors
[-- Attachment #1.1: Type: text/plain, Size: 1109 bytes --]
I have a question about concurrence confusing me a lot.
As we know, when a resource is shared by multiple processes, we need some
mechanism to protect
shared resource.
For example, process A and process B both share a data structure DS.
Both A and B want write new data into DS.
Usually we use a mutex to protect DS,
here the mutex is defined as:
DECLARE_MUTEX(mut);
for process A
{
.....
down_interruptible(&mut);
A operates on DS;
up(&mut);
.......
}
for process B
{
.....
down_interruptible(&mut);
B operates on DS;
up(&mut);
.......
}
If the above pseudo code is run on a multi-core system, and if one core
tries "down_interruptible(&mut) "
in process A, with another core trying "down_interruptible(&mut);" in
process B exactly at the same time, both A and B
will get the semaphore simultaneously, and then operate on DS.
It seems we have no way to protect the shared resource at all.
The similar logics also fit in with other locking mechanism such as mutex,
spinlock, and atomic variables.
Can you tell me my misunderstaning about above scenario.
Thanks.
[-- Attachment #1.2: Type: text/html, Size: 7526 bytes --]
[-- Attachment #2: Type: text/plain, Size: 168 bytes --]
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [KJ] question about race condition
2007-01-18 19:27 [KJ] question about race condition Shaobo Liu
@ 2007-01-18 20:07 ` Jaco Kroon
2007-01-18 20:16 ` Alexey Dobriyan
1 sibling, 0 replies; 3+ messages in thread
From: Jaco Kroon @ 2007-01-18 20:07 UTC (permalink / raw)
To: kernel-janitors
[-- Attachment #1.1: Type: text/plain, Size: 2782 bytes --]
Shaobo Liu wrote:
> I have a question about concurrence confusing me a lot.
>
> As we know, when a resource is shared by multiple processes, we need some mechanism to protect
> shared resource.
>
> For example, process A and process B both share a data structure DS.
> Both A and B want write new data into DS.
>
>
>
> Usually we use a mutex to protect DS,
> here the mutex is defined as:
>
> DECLARE_MUTEX(mut);
>
> for process A
> {
> .....
> down_interruptible(&mut);
> A operates on DS;
> up(&mut);
> .......
>
> }
>
> for process B
> {
> .....
> down_interruptible(&mut);
> B operates on DS;
> up(&mut);
> .......
>
> }
>
> If the above pseudo code is run on a multi-core system, and if one core tries "down_interruptible(&mut) "
> in process A, with another core trying "down_interruptible(&mut);" in process B exactly at the same time, both A and B
> will get the semaphore simultaneously, and then operate on DS.
>
> It seems we have no way to protect the shared resource at all.
>
> The similar logics also fit in with other locking mechanism such as mutex, spinlock, and atomic variables.
>
> Can you tell me my misunderstaning about above scenario.
You're missing the fact that the attempt to take the lock happens
atomically. I'm not 100 % sure about the kernel implementation, but
basically one way to do this would be to store the value 0 in the memory
location representing the lock, or "available". Now x86 (and x86_64)
has the ability to lock the memory bus (only one of the processors/cores
can access that particular memory location) for the duration of an
instruction. So in terms of assembler an attempt to take the lock would
then look something like (assuming edi has been pre-loaded with the
memory address representing the lock):
mov ax, 1
retry:
lock xchg ax, [esi]
test ax, ax
jz success
jmp retry
success:
; lock is taken
Whether the above is interruptable or not depends on the status of the i
bit in the cpu status flags (cli/sti). Of course, we can also make a
call just before the jmp to retry to attempt scheduling another process
on this core to give whatever process is holding the lock an opportunity
to finish it's job.
Anybody please feel free to correct me. You can also take a look at at
atomic.h (can't remember it's exact location in the sources) to get a
better idea of what I'm talking about (atomic.h abuses the lock command
to achieve some pretty cool stuff - I've used it once to speedup
calculations in userspace that would otherwise have had to be protected
with a mutex).
PS: You're race condition applies equally to a unicore processor if
interrupts are still enabled.
Jaco
[-- Attachment #1.2: S/MIME Cryptographic Signature --]
[-- Type: application/x-pkcs7-signature, Size: 3233 bytes --]
[-- Attachment #2: Type: text/plain, Size: 168 bytes --]
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [KJ] question about race condition
2007-01-18 19:27 [KJ] question about race condition Shaobo Liu
2007-01-18 20:07 ` Jaco Kroon
@ 2007-01-18 20:16 ` Alexey Dobriyan
1 sibling, 0 replies; 3+ messages in thread
From: Alexey Dobriyan @ 2007-01-18 20:16 UTC (permalink / raw)
To: kernel-janitors
On Thu, Jan 18, 2007 at 02:27:05PM -0500, Shaobo Liu wrote:
> If the above pseudo code is run on a multi-core system, and if one core
> tries "down_interruptible(&mut) "
> in process A, with another core trying "down_interruptible(&mut);" in
> process B exactly at the same time, both A and B
> will get the semaphore simultaneously, and then operate on DS.
>
> It seems we have no way to protect the shared resource at all.
> The similar logics also fit in with other locking mechanism such as mutex,
> spinlock, and atomic variables.
>
> Can you tell me my misunderstaning about above scenario.
This scenario is purely theoretical. In real world there is no such
thing as "at the same time". One CPU will be there first.
_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2007-01-18 20:16 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2007-01-18 19:27 [KJ] question about race condition Shaobo Liu
2007-01-18 20:07 ` Jaco Kroon
2007-01-18 20:16 ` Alexey Dobriyan
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.