On May 27, 2005, at 18:31:38, David Nicol wrote:
On 5/26/05, john cooper <[email protected]> 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------
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]