Date: Fri, 26 Nov 2004 02:08:41 +0100
From: Ingo Molnar <mingo@elte.hu>
To: Esben Nielsen <simlo@phys.au.dk>
Cc: linux-kernel@vger.kernel.org
Subject: Re: Priority Inheritance Test (Real-Time Preemption)
Message-ID: <20041126010841.GA3563@elte.hu>
References: <20041125165829.GA24121@elte.hu> <Pine.OSF.4.05.10411252305040.25041-100000@da410.ifa.au.dk>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <Pine.OSF.4.05.10411252305040.25041-100000@da410.ifa.au.dk>
User-Agent: Mutt/1.4.1i
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 2465
Lines: 88


* Esben Nielsen <simlo@phys.au.dk> wrote:

> I am running on -31-7 kernel now - it takes quite some time to run with
> the runall.sh script with 100000 samples per point so I don't have full
> data yet. [...]

btw., do you really need 100,000 samples to get statistically stable
results? I've been running with 1000 samples and it was already more
than usable - i'd say 3000-5000 samples ought to be more than enough. 

> But the bounds look like
> depth observed bound  theoretical
>    1        1 ms          1 ms
>    2        3 ms          2 ms      :-(

are you sure the theoretical limit is 2 msec? I think it's 3 msec, for
the following reason:

there are two types of nonprivileged-task lock sequences allowed in the
2-deep case:

	spin_lock(&lock2);
	spin_lock(&lock1);
	... loop for 1 msec ...
	spin_unlock(&lock1);
	spin_unlock(&lock2);

or:
	spin_lock(&lock1);
	... loop for 1 msec ...
	spin_unlock(&lock1);

now, with the above locking, the worst case scenario is the following
one, in chronological order [task A and B are unprivileged, RT is the
highprio task]:

	task-A			task-B			task-RT

	spin_lock(&lock2);
	[ gets lock2 ]
				spin_lock(&lock1);
				[ gets lock1 ]
							spin_lock(&lock2);
							[ boosts task-A ]
							[ waits ]
	[ gets RT prio ]				.
	spin_lock(&lock1);				.
	[ boosts task-B ]				.
	[ waits ]					.
	.			[ gets RT prio ]	.
	.			[ 1 msec loop ]		.
	.			spin_unlock(&lock1);	.
	[ gets lock 1 ]					.
				spin_lock(&lock1);	.
				[ waits ]		.
	[ 1 msec loop ]		.			.
	spin_unlock(&lock1);	.			.
				[ gets lock1 ]		.
	spin_unlock(&lock2);				.
							[ gets lock2 ]
							spin_lock(&lock1);
							[ boosts task-B ]
							[ waits ]
				[ 1 msec loop ]		.
				spin_unlock(&lock1);	.
							[ gets lock1 ]


the additional 1 msec comes in because the RT task might be blocking on
a task that _itself_ has to wait 1 msec to get its second lock. So we
have 3 msec of maximum waiting altogether.

the additional +1 msec comes from the fact that 1-deep lock/unlock of
lock1 is an allowed operation too - 2 msec would be the limit if the
only sequence is the 2-deep one.

so i think the numbers, at least in the 2-deep case, are quite close to
the theoretical boundary.

agreed?

	Ingo
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/