Conference rusure::math

Maybe I'm being a little dense, but shouldn't the cost be

	        t               
	C(t) = Sum p[k] k S  +  p[t+1] (t S + H) ?
	       k=1

You only do the hibernation once...

    You want the probabilities to sum to 1; and the p[k] are defined
    to be the probability that the spin would be successful on the k-th
    iteration (if the code were to always spin and never give up).

    The probabilities were defined this way so they'd be independent
    of when you decide to give up.

>	        t                                t
>	C(t) = Sum p[k] k S  +  (t S + H) ( 1 - Sum p[k] )
>	       k=1                              k=1

A little arithmetic yields:

	    delta C			    t
C'(t)  =    -------  = C(t+1) - C(t) = S(1-Sum p[k]) - Hp[t+1]
	    delta t			   k=1

Similiarly,
		 2
	    delta C
C''(t) =    -------- = C'(t+1) - C'(t) = -Hp'[t+1] - Sp[t+1]
		   2
	    delta t

We can treat C'(t) as the "derivative" of C(t) (ah, rigor, where is thy sting?)
and claim that if this function has a nice convex shape (C''(t) > 0, C'(0) < 0)
then C'(t) crosses the origin at the minimum value of C(t). The function will
have the desired shape when p'[k] < -p[k]*S/H, meaning p[k] decays more quickly
than exp(-kS/H), and p[1] > S/H; and the minimum will be either at x or x+1,
where x is the largest value of t for which C'(t) < 0.

If C(t) is a local minimum (and t > 1), then

	C(t+1) - C(t) >= 0, and C(t-1) - C(t) >= 0.
So,
	     t                              t-1
	S(1-Sum p[k]) >= Hp[t+1],  and  S(1-Sum p[k]) <= Hp[t]
	    k=1                             k=1

	                                     t 
	    ...                         S(1-Sum p[k]) <= Hp[t] + Sp[t]
	                                    k=1
	                  t
	(H+S)p[t] >= S(1-Sum p[k]) >= Hp[t+1]
	                 k=1

                                                                   t
Working backwards, suppose (H+S)p[t] >= Hp[t+1], and let SS = S(1-Sum p[k]).
                                                                  k=1
	Hp[t+1] = SS + C(t) - C(t+1)
	(H+S)p[t] = SS + C(t-1) - C(t)

	(H+S)p[t] >= Hp[t+1]  =>  SS + C(t-1) - C(t) >= SS + C(t) - C(t+1)
	=>  (C(t+1)+C(t-1))/2 >= C(t)

Which implies C(t) <= C(t+1) or C(t) <= C(t-1), or both; so C(t) may be a
local minimum.  And

	(H+S)p[t] <= Hp[t+1]  =>  C(t) >= (C(t+1)+C(t-1))/2

Which means that C(t) >= C(t+1) or C(t) >= C(t-1), or both (so C(t) is NOT
a local minumum).

All this yields is a way of looking at a local property of the p[k] (i.e.,
(H+S)p[t] vs Hp[t+1] that gives a clue about whether this might be minimum.

Suppose we choose when to give up according to some probability distrubution.
That is, before starting the spin loop, we choose the number of spins we will
try before giving up; we choose 1 spin as our limit with probability q[1],
we choose to stop after 2 spins with probability q[2], ....  Then the expected
cost of this strategy is:

	    inf                   inf
	E = Sum q[t] C(t);   with Sum q[t] = 1.
	    t=1                   t=1

We would like to choose the q[t] to minimize E.

This can be analyzed as a two-player game -- one player chooses the p[k]
values and the other chooses the q[t] values.  It turns out that the
best strategy for choosing the q[t] values is to let q[1] = 1, and all
other q[t] equal zero.  This gives E = Sp[1] + (S+H)(1-p[1]).  Any other
distribution of the q[t] allows the other player to choose the p[k] such
that we get a higher value of E.  For example, p[3H/S] = 1, and all other
p[k] = 0; any strategy that ever spins for more than one iteration will
have an E value higher than Sp[1] + (S+H)(1-p[1]).

Instead of the p[k] given in 864.0, the following may be more useful.
A reasonable assumption is that p[1] >= p[2] >= p[3] ....  But this can't
be immediately analyzed as a game, since the p[k] are not all independent.
Instead we introduce the s[k] distribution:

	       inf                                     inf
	p[k] = Sum s[i]/i;  s[k] = k (p[k] - p[k+1]);  Sum s[k] = 1.
	       i=k                                     k=1

The s[k] are all independent, and they sum to 1.  In terms of the s[k],

	        t               inf
	C(t) = Sum p[k] k S  +  Sum p[k] (t S + H)
	       k=1             k=t+1

	        t                   inf
	     = Sum s[k] S (k+1)/2 + Sum s[k] S t(t+1)/(2k)
	       k=1                 k=t+1
				            inf
				+ (t S + H) Sum s[k] (k-t)/k
				           k=t+1

	        t                   inf
	C(t) = Sum s[k] S (k+1)/2 + Sum s[k] { S t(2k+1-t)/(2k) + H (1-t/k) }
	       k=1                 k=t+1

The s[k] distribution that maximizes the above has s[M] = 1, for some
very large M, so that

	C(t) = S t + H

Thus, we see again that whatever q[t] distribution we choose, the s[k]
values can be chosen so that E >= S + H.  Thus, the best q[k] distribution
has q[1] = 1.  This may be seen more easily by considering the p[k]
distribution: p[1] = p[2] = ... = p[M] = 1/M, p[M+1] = p[M+2] = ... = 0.
We have:

	C(t) = S t(t+1)/(2M) + (t S + H) (1 - t/M),  for t <= M
	     = S (M+1)/2,                            for t >= M

Notes .0, .3 and .4 (I'll get to .5 later) all assume that a minimum 
exists inside the interval 0 < t < inf.  But there are some conditions, 
and perhaps most conditions, under which the optimal choice is either 
t=0 (don't spin at all) or t=inf (spin until the mutex is free).

Make the following assumptions:

	the event which releases the mutex is independent of the event 
		which tries to seize the mutex
	mutexes are held for times which are described by a distribution 
		(this may be a restatement of the above)
	measure time in units such that the time of a spin loop is one, 
		just for convenience
	ignore fractional parts of mutex hold intervals (this is just to 
		simplify the algebra, and can be removed by anyone who 
		is better at algebra than I am).
	the distribution is singular, so all mutex holds intervals have 
		the same length, which I will call n (this assumption 
		will be relaxed shortly)

Because the release event is independent of the lock event, p(t) has the 
simple form

	p(t) = 1/n 	for 1 <= t <= n
	p(t) = 0	otherwise

If we evaluate C(t) in the interval 1 <= t <= n we get 

	C(t) = - t^2 * S/(2*n) + t * ( S/(2*n) + S - H/n ) + H

a quadratic with a negative first coefficient.  So C'(t) = 0 determines a 
maximum, and the minimum must be on an end point.

The end points are 

	C(0) = H			don't spin at all
	C(n) = S * (n+1) / 2		spin until released

These two equations make sense:  If we don't spin, we pay only the cost 
H, if we spin, we will spin (n+1)/2 times, on the average, so we pay the 
cost S that number of times.

So the choice between the two strategies is easy in this case.  If

	2 * H / S < n+1

then don't spin, otherwise spin to release.


But the assumption of a single hold interval length n is not realistic, 
at least if I understand the real problem you are trying to solve.  So 
let's relax this a bit.

Assume that the distribution of hold intervals is given by pn(n), which 
gives the probability that a given interval has length n.  If the 
average length of these intervals is <n>, then the probability that a 
the hold blocking the current seize has length n is given by 

	n * pn(n) / <n>

because longer holds are more likely to block a seize.

We can write p(t) in terms of pn(n) as an expectation

		inf
	p(t) =	Sum n * pn(n) * p(t|n) / <n>
		n=1

	where	p(t|n) = 1/n 	for 1 <= t <= n
		p(t|n) = 0	otherwise

		inf
	p(t) =	Sum pn(n) / <n>
		n=t

Note in passing that p(t) is monotonically decreasing, as assumed in .5. 
I think this is true any time that held intervals are drawn from a 
distribution independent of the seize event.

In principle, we now have the solution: determine from theory or 
experiment the distribution pn(n), plug it into C(t), and search for the 
minimum.  But before I leave this, I'll offer a two simple cases and a 
conjecture, then I'll discuss the game theory approach of .5.

Assume that p(t) is proportional to 1/t^2 for large t.  Then C(t) will 
be dominated by the first term which will not converge.  So the choice 
of spin until release will always have infinite cost unless p(t) 
converges to zero faster than 1/t^2.

Assume that pn(n) is bounded such that almost all the distribution is 
between nl and nh.  Then we should do no spins if 

	2 * H / S < nl + 1

and we should spin until release if p(t) converges faster than 1/2^t and

	2 * H / S > nh + 1


My conjecture is that for unimodal (single-peaked) distributions of 
pn(n), we should do no spins if

	2 * H / S < <n> + 1

and should spin to release if p(t) converges fast enough and 

	2 * H / S > <n> + 1

Note that <n> will depend on the mutex in question, so you might 
partition mutexes into two classes: spin class and hibernate classes.

I can't prove this, but I can offer an argument and a counterexample.  
The artificiality of the counter-example suggests to me that real pn(n) 
will satisfy the above.

Suppose I am making the decision on the spot after each spin.  Because 
of independence, all I can know is the distribution of pn(n) and 
therefore p(t) and therefore C(t).  Suppose I think it over and make 
some computations and conclude that a spin is called for.  I try a spin and 
the mutex is still held.  So I do my computations again, but my 
knowledge base is essentially the same.  I've done one spin, so I am 
probably closer to the release, but in general I don't know any more 
about the hold interval I am facing.  So my decision must be the same, 
and I try the spin again.  Next time, same thing, until the mutex is
released.

Now for the counter example:  Suppose the pn(n) is bimodal:

	pn(1) = .9
	pn(10) = .1
	pn(n) = 0	otherwise

and 2 * H / S = 5.  Now I try for a mutex and find it held.  If the 
length of this interval is 1, then I should spin, and if it is 10, then 
I should not.  But the probabilities of these two are almost equal, so I 
don't know which I am facing.  But I can take one spin and if the mutex 
is released, I am golden.  If it fails, then I know that I am facing an 
interval of 10, so it makes sense to hibernate.

A less extremely bimodal distribution would give a similar result, but 
a unimodal distribution will not.  In the real world, unimodal 
distributions are much more common than bimodal, so I have some 
confidence that my conjecture will apply in the real world.

The game theory approach in .5 leads to a pessimistic result, as usual 
(see _Statistics_, Winkler and Hays, Holt Rinehart and Winston, NY, 
1975, page 558-562).  If you assume an adversary, then of course they 
will arrange things so the intervals are arbitrarily long, so you should 
always choose not to spin, but hibernate immediately.

As the reference above points out (I can't find the right page), the 
game theory approach is correct when 

	you are facing a thinking adversary

		OR

	your knowledge of the distribution indicates that the outcomes 
	a thinking adversary would choose are very likely

		OR

	the costs associated with those outcomes are very high

		OR 

	you are extremely risk averse, and prefer a decision which may 
	be sub-optimal because it avoids the chance of a costly outcome

If any of the above apply in your real problem, the answer is simple: do 
not spin, hibernate immediately.

One final note on reality: I have assumed that the probability of more 
than one task waiting on the same mutex is negligible.  If not, you 
would have to look at the cases where another task is already 
hibernating or spinning, and the cases where another task decides to 
hibernate or spin while you are doing one or the other.  Pretty 
complicated, but it looks like most of them are more arguments for 
hibernating right off.

I assume that we are willing to spend CPU time spinning if this will
shorten the elapsed time until acquiring the mutex and in turn the
total run time, but this is not taken into account in the cost.

Several other bits of information can help decide what action to take
without knowing the probability distribution.

If we know the mean service time holding the mutex relative to the hiber-wake
time and the number waiting, we can better estimate the penalty for hibernating
at the wrong time.  Restating some of .6, this is illustrated by:

The first simple case: the service time holding the mutex is less than
1/max-processes*hiber-wake-service time, it makes sense to only spin.
Even if every process were waiting for the mutex, our mean waiting time
will be less than half the hiber-wake time.

The second simple case: the service time holding the mutex is greater than
the hiber-wake service time, it makes sense in this case to only hiber
if another process is already waiting since we know that we will wait
at least the service time.

This suggests that we would like to know the number waiting.

If we have the arrival rate, then queuing theory will give us the mean number
in the system thru Little's Law, but it is probably easier to simply compute
it in real time.

re: < Note 864.7 by LASSIE::PETTENGILL "mulp" >
                      -< This looks like queuing theory >-

> I assume that we are willing to spend CPU time spinning if this will
> shorten the elapsed time until acquiring the mutex and in turn the
> total run time, but this is not taken into account in the cost.
    
    Yes, I thought of this too on first reading .0, but then decided
    that .0 was taking the point of view of the executive.  The executive's
    goal is to get all these processes in and out as fast as possible,
    while minimizing the cost of servicing them.  So .0 looks at the
    cost in CPU ticks of spinning versus waiting.
    
    Costs from the point of view of the user process are quite different.
    We assume that delay is a cost to a user process, and there may
    be other costs.  To deal with this problem, we would have to define
    those costs and then figure out how to relate them to the executive
    costs.  We would also have to implement some concept of fairness,
    so processes cannot take unfair advantage.
    
    0. takes the easy way out and assumes that executive costs are much
    more important than user costs.  Probably reasonable in this case, 
    since an efficient executive will benefit all users, and the user
    inefficiency will average out.

> The first simple case: the service time holding the mutex is less than
> 1/max-processes*hiber-wake-service time, it makes sense to only spin.
> Even if every process were waiting for the mutex, our mean waiting time
> will be less than half the hiber-wake time.
    
    True in principle but seems unlikely in practice.  The max-processes
    I see are around 100, and I can't believe that mutex hold time is 100 
    times less than hiber wake time.  And see later problem on losing
    a place in line by spinning.

> The second simple case: the service time holding the mutex is greater than
> the hiber-wake service time, it makes sense in this case to only hiber
> if another process is already waiting since we know that we will wait
> at least the service time.
    
    This really depends on the distribution of hold times and the cost
    as a function of waiting time, but it is roughly correct, for
    reasonable assumptions of both.  It still neglects the cost to the
    executive.

> This suggests that we would like to know the number waiting.
    
    I assumed that this is close to zero on average.  If not, we need
    to look at the complications mentioned in .6.  If process A holds
    the mutex, and process B is queued, and process C starts spinning,
    who gets the mutex when A releases it?  Is it a race?  If process
    A holds the mutex and process B starts spinning, and process C queues
    itself, then who gets it?  Did B just lose a place in line by spinning?

I just realized that an implicit assumption in all of the above is that each
process has its own CPU, either in actuality or in practice.

If there is a single CPU available for the holder of the mutex and the process
attempting to acquire the mutex, a spin-lock wait will need to be preempted by
the scheduler at a cost that is likely to be about the same as a hiber-wake.

Many thanks!  The comments have all been very useful (except mine,
which have contained nought but tedious math).

re .7,.8 (accounting for a shortened elapsed time)

	At first I thought .0 could account for this by artificially
	increasing the 'cost' of a hiber/wake.  For example, on a stand-
	alone machine, the cost of a hiber/wake is infinitely larger than
	the cost of a spin.

	However, users pay for CPU time and for connect time, and the
	model doesn't account for the value of completing the work early.

re .6

	"Don't spin at all" isn't quite right, since we need to check the
	bit sometime; we may as well to check it at least once.

	Put another way, suppose we never checked the bit, but instead did
	a hiber, and waited for a wake.  If the mutex is initially unlocked,
	who will ever lock it?  And so who would ever issue the wake?

	BTW, I was surprised to see that sometimes it's best to spin
	until released.

re .9
	This is enlightening.  It might mean that we should never spin
	for more than a quantum (or half a quantum) on a time-sharing
	system.


A couple notes have suggested keeping statistics.  What simple statistics
will suffice without consuming much storage?

>    For example, on a stand- alone machine, the cost of a hiber/wake is
>    infinitely larger than the cost of a spin. 

    No, only about 1000 times larger at most...probably more like 500.
    Expect this differential to narrow as CPU speeds increase relative
    to shared-memory accesses.
    
    This means that you really only need about 1000 p[i] or q[i] entries
    for some simple analyses.  Of course, in a high-contention environment
    this could go up to N * 1000 or so.
    
    I think there are two possible approaches here:
    
    [1] Spin once and hiber if you don't get the mutex.  This is the
    	"simple" strategem.  I believe it is near optimal (gut feel).
    
    [2] Create a simulation model whereby you control all the parameters,
    	(a) mutex-request interarrival distribution, (b) mutex holding
    	time distribution, (c) Number of processes, each with distributions
    	from (a) and (b) above.  Obtain spin-time and hiber/wake time
	by experimentation or perhaps some ballpark figures from me.
    	Run the simulation to determine optimium stopping points for
	various (a), (b), (c) and tabulate the results.
    
    	The idea is to see if there are a small number of ideal results.
    	It may be, for example, that "spin 30 / N times" is a reasonable
	answer for most cases (N = queue length including servee). 
    
    	IF you can summarize results THEN you can formulate an algorithm
    	based upon table lookup techniques, and dynamically adapt to
    	a changing workload;

	We've done this in the past in similar situations, with good results.

      	  John

re: < Note 864.10 by CLT::GILBERT >

>	However, users pay for CPU time and for connect time, and the
>	model doesn't account for the value of completing the work early.
    
    Right.  If you want to do this, then you must make your cost function
    a lot more complex.

>	"Don't spin at all" isn't quite right, since we need to check the
>	bit sometime; we may as well to check it at least once.
>	Put another way, suppose we never checked the bit, but instead did
>	a hiber, and waited for a wake.  If the mutex is initially unlocked,
>	who will ever lock it?  And so who would ever issue the wake?
    
    Well, you're looking at the code, so you know best.  I was assuming
    that you would check the bit first and then decide to spin.  If
    the easiest way to check the bit is to spin once, then yes, a
    reasonable alternative is to spin once.

>	BTW, I was surprised to see that sometimes it's best to spin
>	until released.
    
    Me too, but the more I think about it, the more I think that the
    two best choices are spin once or spin until released.  I wish some
    math heavy would prove the conjecture in .6.

>	This is enlightening.  It might mean that we should never spin
>	for more than a quantum (or half a quantum) on a time-sharing
>	system.
    
    General Rule: in a true applied math problem, you spend 80% of your
    thought on the application and 20% on the math.  And what I know about 
    mutexes is just what is written on 37-41 of Kenah, Goldenberg and
    Bate.  So all I'll say is that .6 addresses the math problem stated 
    in .0.  Someone who understands these things may want to restate
    .0 to be closer to the problem that we really want to solve.  If it 
    turns out that we need to solve a different problem, then .6 may or 
    may not apply.
    
> A couple notes have suggested keeping statistics.  What simple statistics
> will suffice without consuming much storage?
    
    The first thing you want to do is put values to H and S, as defined
    in .0.  I assume that you can calculate these by instruction counts
    or something, but they may depend on processor type.
    
    Then estimate pn(n) and <n>, as defined in .6.  I hope you can get
    these by some kind of monitoring on a running system, but I haven't
    done this since I used to examine the PC and PS from inside the
    clock interrupt routine on a PDP-11.  I expect that pn(n) and <n>
    will depend on the mutex, and probably on the load on the system,
    and maybe on other things.

    The inequalities in .6 may then settle the whole question on the
    spot.  Or the shape of the distribution may indicate whether the
    conjecture in .6 will apply.
    
    If not, then (assuming that the analysis of .6 is not entirely off
    base) you would like to know the n for the delay you are currently
    facing.  This may be knowable, depending on the details of the mutex
    and the executive code and data structures.  If it is knowable,
    then you can plug it into the inequalities and decide to hibernate
    or spin.
    
    If n is not knowable, then knowing pn(n) is the next best thing.
    I am sure that pn(n) depends on the mutex, the overall load on the
    system, the detailed load on the resource involved (for example,
    pn(n) for the logical name mutex ought to depend on the size of
    the logical name tables), and maybe other things.  So write pn(n)
    as
    
    	pn(n) = pn(n; mutex, load, mutex load, other things...)
    
    and use the monitoring above to determine a good parametric form
    for 
    
    	pn(n) = pn(n; mutex, load, mutex load, other things...)
    
    and to evaluate the parameters.  Empirically defining a function
    of many parameters is no fun, but theory, intuition and monitoring
    ought to eliminate many parameters.
    
    Once you have pn(n;...) in terms of the most important parameters,
    you can decide how to monitor the parameters in real time and what
    statistics you need to keep so you can estimate the pn(n) you are 
    facing.  Hmmm... you should probably have looked ahead to the
    statistics problem as you were eliminating parameters from pn(n;...);
    no point in including a parameter you cannot measure in real time.
    
    I think that this is the same thing in different words as the
    simulation/table idea in .11.  Pick the words you like best.

                               t0           t1
C(t1) - C(t0) = (t1-t0) S (1 - Sum p[k]) -  Sum  p[k] ((t1-k)S+H), for t1 > t0.
                               k=1         k=t0+1

                        t
C(t+1) - C(t) = S (1 - Sum p[k]) - p[t+1] H
                       k=1

    I've finally gotten a useful result!  Suppose our strategy is to
    'give up' after t0 spins, and we want to choose t0 so that the
    resulting strategy is not much worse than the optimal strategy:

	C(t ) <= (1 + Z) C(t   )
	   0                opt

    Let R = (cost of hiber+wake)/(cost per spin).  Then if t0 = 0.618 * R,
    we are guaranteed to never be more than 1.618 times worse than the
    optimal strategy.  (yes, the 0.618 above is (sqrt(5)-1)/2).

    

    Re .14:
    
    Nice, Peter.  
    
    I think that this is probably publishable.  Can we expect to see
    it in print soon?
    
    --  Barry

We have

	        t                               t
	C(t) = Sum k p[k] S  +  (t S + H) (1 - Sum p[k])
	       k=1                             k=1

Suppose that the optimal (minimal) C(t) occurs at t = t_opt.  Let H = R S.


Suppose we decide to stop spinning after t_0 spins, and t_0 < t_opt.
Let Z = C(t_0) / C(t_opt).

We use the model that says p[1] >= p[2] >= p[3] >= ....  Then the p[k] that
maximize Z can be tediously shown to be:

	p[k] = b,	for k < t_opt,
	p[k] = 0,	for k > t_opt,
	b >= p[t_opt] > 0, where
	(t_opt-1) b + p[t_opt] = 1.

[ This follows from
	dZ/dp[i] > dZ/dp[j]   for 1 <= i < j <= t_0,
	dZ/dp[i] > dZ/dp[j]   for t_0 < i < j <= t_opt,
	dZ/dp[i] <= 0   for i > t_opt, and
	dZ/dp[t_opt] > dZ/dp[1]   for t_0 < i < j <= t_opt. ]

Here we simplify, and also let p[t_opt] = b.  Then (roughly),

	Z = [ t_0^2 S / (2 t_opt) + (t_0 S + H) (1 - t_0/t_opt) ]
					/ [ t_opt S / 2 ]

	  = [ t_0^2 + 2 (t_0 + R) (t_opt - t_0) ] / t_opt^2

The t_opt value that maximizes this has dZ/dt_opt = 0.

	dZ/dt_opt = { -2 t_0^2 - 4 (t_0 + R) (t_opt - t_0) + 2 t_opt (t_0 + R) }
	                                    / t_opt^3

So, setting this to zero, we have:

	-2 t_0^2 - 4 (t_0 + R) (t_opt - t_0) + 2 t_opt (t_0 + R) = 0

	t_opt = t_0 (t_0 + 2 R) / (t_0 + R)

Letting t_0 = p R,

	t_opt = R p (p+2) / (p+1)

Plugging these back into Z, we have:

	Z = [ p^2 + 2 (p + 1) (p (p+2)/(p+1) - p) ] / [ p (p+2)/(p+1) ]^2
	  = [ p^2 + 2 (p+1) (p (p+2)/(p+1) - p) ] [ (p+1)^2 ] / [ p^2 (p+2)^2 ]
	  = (p+1)^2 / [ p (p+2) ] = 1 + 1/(p(p+2))


On the other hand, suppose we have t_0 = p R (as before), but t_opt < t_0.
Then to maximize Z, the p[k] values are all miniscule, so that

	C(t_opt) = H = R S,
and
	Z = [ t_0 S + H ] / H = (p R S + R S)/(R S) = p + 1.


In either case (t_opt > t_0 or t_opt < t_0), we have:

	Z = C(t_0)/C(t_opt) <= max ( 1+p , 1+1/(p(p+2)) )

We summarize.  Given a value for t_0, the above shows us how to choose
the p[k] to maximize Z, and it shows just how large Z may be.


Now we consider the optimal choice of t_0 = p R.  To minimize the above
expression, we want to choose p so that 1+p = 1+1/(p(p+2)), viz:

	p = 1/(p(p+2)), so that

	p^3 + 2 p^2 - 1 = 0, or

	(p + 1) (p^2 + p - 1) = 0.

So we have the solutions:

	p = -1,  or  p = (-sqrt(5)-1)/2,  or  p = (sqrt(5)-1)/2 = phi.

The third of these is the only meaningful solution, so we have:

	t_0 = phi R = phi H/S,

	Z = C(t_0)/C(t_opt) <= 1 + phi
		(Z is maximized with t_opt = 1 or t_opt = R = H/S),

	where phi = (sqrt(5)-1)/2 = 0.618, the golden ratio.

Thus, if our strategy is to spin until we consume 61.8% of the hiber+wake cost
and then 'give up', our expectation is never more than 61.8% worse than optimal.

A few steps from the previous reply....

    Z = C(t_0) / C(t_1),  t_0 < t_1.

     dZ     (t_1 S + H) C(t_0) - (t_0 S + H) C(t_1) - i S [ C(t_0) - C(t_1) ]
    ----- = ----------------------------------------------------------------- ,
    dp[i]                            C(t_1)^2
                                               for 1 <= i <= t_0.

     dZ     (t_1 S + H) C(t_0) - i S C(t_0)
    ----- = ------------------------------- ,  for t_0 < i <= t_1.
    dp[i]               C(t_1)^2


     dZ
    ----- = 0 ,  for t_1 < i.
    dp[i]

Thus,

     dZ      dZ
    ----- > ----- ,  for 1 <= i < j <= t_0.
    dp[i]   dp[j]

     dZ      dZ
    ----- > ----- > 0 ,  for t_0 < i < j <= t_1.
    dp[i]   dp[j]

      dZ         dZ       C(t_0) S - C(t_1) H
    ------- - --------- = -------------------  < 0  ( assuming Z < R ).
    dp[t_0]   dp[t_0+1]         C(t_1)^2

     dZ       dZ
    ----- < ------- .
    dp[1]   dp[t_1]