All of lore.kernel.org
 help / color / mirror / Atom feed
From: Jaco Kroon <jaco@kroon.co.za>
To: kernel-janitors@vger.kernel.org
Subject: Re: [KJ] question about race condition
Date: Thu, 18 Jan 2007 20:07:15 +0000	[thread overview]
Message-ID: <45AFD373.9000604@kroon.co.za> (raw)
In-Reply-To: <200701181927.l0IJR6TA004900@bingnet2.cc.binghamton.edu>


[-- 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

  reply	other threads:[~2007-01-18 20:07 UTC|newest]

Thread overview: 3+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2007-01-18 19:27 [KJ] question about race condition Shaobo Liu
2007-01-18 20:07 ` Jaco Kroon [this message]
2007-01-18 20:16 ` Alexey Dobriyan

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=45AFD373.9000604@kroon.co.za \
    --to=jaco@kroon.co.za \
    --cc=kernel-janitors@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
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.