Re: [Geekos-devel] Efficient implementing of semaphores...

[Behrang S. <beh...@ya...>]

The sample code given below is written in O'Reilly's 
Understanding Linux Kernel for the semaphore down
operation.

It only states that the code in line 5 should be
implemented 
with the processor's atomic instructions and thus is
the 
critical region.

It also states that the code between the lines 13 - 16
are 
critical so they are protected by a system-wide
spinlock
called the "semaphore_wait_lock" and by the assistance
of
interrupt disabling:

"In order to do this, it increments the waking field,
which 
is protected by the semaphore_wake_lock spin lock and
by 
interrupt disabling, then invokes wake_up( ) on the
semaphore wait queue."

Wherever I look it seems to me there should be some
interrupt disabling code somewhere in the
implementation
of the semaphore up/down operations? Is that true?

1.  void down(struct semaphore * sem)
2.  {
3.    /* BEGIN CRITICAL SECTION */
4.    --sem->count;
5.    if (sem->count < 0) {
6.    /* END CRITICAL SECTION */
7.      struct wait_queue wait = { current, NULL };
8.      current->state = TASK_UNINTERRUPTIBLE;
9.      add_wait_queue(&sem->wait, &wait);
10.     for (;;) {
11.       unsigned long flags;
12.       spin_lock_irqsave(&semaphore_wake_lock,
flags);
13.       if (sem->waking > 0) {
14.         sem->waking--;
15.         break;
16.       }
17.       spin_unlock_irqrestore(&semaphore_wake_lock,
flags);
18.       schedule( );
19.       current->state = TASK_UNINTERRUPTIBLE;
20.     }
21.  
22.    spin_unlock_irqrestore(&semaphore_wake_lock,
flags);
23.    current->state = TASK_RUNNING;
24.    remove_wait_queue(&sem->wait, &wait);
25.   }
26. }

Thanks in advance,
Behrang S.

--- David Hovemeyer <da...@cs...> wrote:
> On Sun, Feb 02, 2003 at 01:46:18PM -0500, Jaime
> Lafleur-Vetter wrote:
> > Yes, indeed there is.
> >  
> > Most architectures provide at least one atomic
> instruction that would
> > enable you to implement critical sections and
> semaphore without having
> > to resort to disabling interrupts.
> >  
> > Example instructions that the hardware may provide
> atomically are:
> >             Test-and-set: operates on 1 bit of
> memory. Returns the
> > previous value and sets the bit to 1.
> >             Swap: swaps to input values
> >  
> > Since these operations would be atomic, they could
> be used to enforce a
> > critical section.
> 
> The tricky part comes in determining what to do if
> the atomic instruction
> determines that the lock is held (i.e., another
> thread is in the
> critical section).  It could yield the CPU and
> retest the condition
> again when it wakes up.  However, you have to ensure
> that while
> the thread is trying to put itself to sleep, the
> lock isn't released,
> resulting in the thread possibly sleeping forever!
> 
> I think to solve this problem, the scheduler would
> need to be aware
> of threads that had partially completed lock
> operations in progress.
> 
> > In GeekOS disabling of interrupts for atomicity is
> used in many places
> > because the time period where interrupts are
> disabled is so small that
> > it has little or no negative effect. Thus, I
> wouldn't be concerned with
> > disabling of interrupts as long as the period is
> short. 
> 
> I think this is probably true, but allowing GeekOS
> to support a locking
> style where interrupts could remain enabled would be
> nice.
> 
> -Dave


__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com