Re: spinaphore conceptual draft (was discussion of RT patch)

Kyle Moffett
2005-05-28T01:04:54Z

On May 27, 2005, at 18:31:38, David Nicol wrote:
> On 5/26/05, john cooper <john.cooper@timesys.com> wrote:
>
>> given design. Clearly we aren't buying anything to trade off
>> a spinlock protecting the update of a single pointer with a
>> blocking lock and associated context switching.
>
> On contention, and only on contention, we are faced with the
> question of what
> to do. Do we wait, or do we go away and come back later? What
> information is
> available to us to base the decision on? We can't gather any more
> information,
> because that would take longer than spin-waiting. If the
> "spinaphore" told us,
> on acquisition failure, how many other threads were asking for it, we
> could implement
> a tunable lock, that surrenders context when there are more than N
> threads waiting for
> the resource, and that otherwise waits its turn, or its chance, as
> a compromise
> and synthesis.

Here is an example naive implementation which could perhaps be
optimized further
for architectures based on memory and synchronization requirements.

A quick summary:
Each time the lock is taken and released, a "hold_time" is updated
which indicates
the average time that the lock is held. During contention, each CPU
checks the
current average hold time and the number of CPUs waiting against a
predefined
"context switch + useful work" time, and goes to sleep if it thinks
it has enough
time to spare.

Problems:
You can't nest these. You also can't take a normal semaphore inside
one. The
only useable locking order for these is:
..., semaphore, semaphore, spinaphore, spinlock, spinlock, ...

Possible Solution:
If you had a reliable way of determining when it is safe to sleep,
you could call
a "cond_resched_if_nonatomic()" function instead of cond_resched()
and allow
nesting of spinaphores within each other and within spinlocks. I
_do_ implement a
spinaphore_lock_atomic which is guaranteed not to sleep and could be
used within
other locks instead.

struct spinaphore {
atomic_t queued;
atomic_t hold_time;
spinlock_t spinlock;
unsigned long acquire_time;
};

void spinaphore_lock (struct spinaphore *sph) {
unsigned long start_time = fast_monotonic_count();
int queue_me = 1;
until (likely(spin_trylock(&sph->spinlock))) {

/* Get the queue count (And ensure we're queued in the
process) */
unsigned int queued = queue_me ?
atomic_inc_return(&sph->queued) :
queued = atomic_get(&sph->queued);
queue_me = 0;

/* Figure out if we should switch away */
if (unlikely(CONFIG_SPINAPHORE_CONTEXT_SWITCH <
( queued*atomic_get(&sph->hold_time) -
fast_monotonic_count() - start_time
))) {
/* Remove ourselves from the wait pool (remember to re-
add later) */
atomic_dec(&sph->queued);
queue_me = 1;

/* Go to sleep */
cond_resched();
}
}

/* Dequeue ourselves and update the acquire time */
atomic_dec(&sph->queued);
sph->acquire_time = fast_monotonic_count();
}

void spinaphore_lock_atomic (struct spinaphore *sph) {
/* Let the other processes know what we're doing */
atomic_inc(&sph->queued);

/* Just get the lock the old fashioned way */
spin_lock(&sph->spinlock);

/* Dequeue ourselves and update the acquire time */
atomic_dec(&sph->queued);
sph->acquire_time = fast_monotonic_count();
}

int spinaphore_trylock (struct spinaphore *sph) {
/* Try to get the lock, and if so, update the acquire time */
if (spin_trylock(&sph->spinlock)) {
sph->acquire_time = fast_monotonic_count();
}

void spinaphore_unlock (struct spinaphore *sph) {
/* Update the running average hold time */
atomic_set(&sph->hold_time, (4*atomic_get(&sph->hold_time) +
(fast_monotonic_count() - sph->acquire_time))/5);

/* Actually unlock the spinlock */
spin_unlock(&sph->spinlock);
}

Cheers,
Kyle Moffett

-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCM/CS/IT/U d- s++: a18 C++++>$ UB/L/X/*++++(+)>$ P+++(++++)>$
L++++(+++) E W++(+) N+++(++) o? K? w--- O? M++ V? PS+() PE+(-) Y+
PGP+++ t+(+++) 5 X R? tv-(--) b++++(++) DI+ D+ G e->++++$ h!*()>++$
r !y?(-)
------END GEEK CODE BLOCK------