Lambda the Ultimate

It sounds like the well-known problem of priority inversion.

I believe priority inversion applies only to cases when the processes compete for the shared resource.
I however meant a case of data dependency, where one (potentially higher priority, or maybe just lucky enough to get some ticks) process needs data from another. If that data is not ready yet, then instead of just wasting the ticks, the blocked (by the need of the data) process can help the producing process by donating some ticks to it - which may mean just executing its continuation for several steps.
So all in all I do not think this situation is priority inversion, or should be avoided.

Perhaps this reference may be of help...

Thanks for the reference, I believe I've skimmed past the paper when it was announced on LtU, now for some reason the link does not work for me. Will place back on my reading list.

I don't see any discussion of tree scheduling in Manticore's "Nested schedulers for heterogeneous parallelism" paper though, so I'm not sure what you mean.

Sections 4 and 5 of The Manticore runtime model do mention a tree of engines and schedulers, correspondingly.

I haven't looked at scheduling much yet, but I plan to, so if you have any good references I'd appreciate it!

My current interest in scheduling comes from two directions - concurrent constraint programming (classical works by Vijay Saraswat, and some modern ones), and the Algorithm = Logic + Control maxim by Robert Kowalski.
I also find Continuations and threads: Expressing machine concurrency directly in advanced languages and Cheap (But Functional) Threads very interesting.
While none of these references is directly about scheduling, I find them forming a useful background.

"Highest" makes sense only in some (quite simple, mostly flat) scheduling schemes. Section 5.2.2 of Using Hierarchical Scheduling to Support Soft Real-Time Applications in General-Purpose Operating Systems gives an overview of (some) more complicated schemes.

Thanks for the pointer. I just meant that the shared process P should not be starved by processes which depend on it, thus preventing progress. The existence of this dependency implies that P is necessarily at least as important as any of its dependents, and any statement or use suggesting otherwise is a safety violation. This is the problem with priority inversion.

If a "higher priority" for P is unjustified, for instance because its output is not critical for the higher priority process R's operation, then promises or asynchronous semantics is justified, where R spawns an agent B to wait on P, while R continues on its merry way. B can then notify R when data is ready.

while in case of priority inversion the conflict has an additional option for resolution by undoing progress of the lower priority process to the point when it acquired the scarce shared resource

I'm not sure I understand. How can progress be undone? I don't see a general way to do this, because processes can have side-effects.

Perhaps we're going about this the wrong way. I see two assumptions in your original write-up that need more analysis first:

1. In what way are tree schedulers insufficient?
2. What problem does 'helping' solve?

You may be right that we are not making progress. Let's preempt this thread with the two you suggested.

In what way are tree schedulers insufficient?

The previously linked dissertation by Regehr has an example to motivate "join" scheduler - a means to generalize hierarchy of schedulers to at least a DAG.

What problem does 'helping' solve?

One of the problems that motivate my interest in scheduling may be found in Compiling Constraint Handling Rules with Lazy and Concurrent Search Techniques. Or just take a look at how we communicate on LtU for a meta-example.
Basically, you may have multiple procedures for finding a solution, and you do not know beforehand, which of them terminates sooner or at all. This requires concurrent execution of them. Also, there may be some data dependencies between procedures (the "lazy" part) - so progress of one procedure (C) may become dependent on the progress of another (P). Helping is a policy (either built into the language, or expressed by the programmer) to delegate ticks of C to P while this dependency lasts. This avoids undeserved leaking ticks of C to other branches of the computation. At least, this aims to find the solution sooner; I never tried to construct a case where this mere optimization becomes a difference between termination and nontermination, though this may be worth a try. On the other hand, one may of course construct a counterexample when helping hurts. It is just a heuristic, and as such is better to be optional (i.e., expressible by the programmer).

The previously linked dissertation by Regehr has an example to motivate "join" scheduler - a means to generalize hierarchy of schedulers to at least a DAG.

Which dissertation? The only one I see in this thread is by Rainey, and 'join' is not mentioned anywhere in there. I am interested in seeing an example where such a generalization is necessary, or at least useful, so I have a good reference when I start looking into scheduling more closely.

Re: helping

By your description, helping seems to be a type of optimization, and not really intended as a solution to a particular problem, is that correct?

My concern with helping is that the additional dynamism of tick donation makes scheduling analysis more difficult. Real-time analyses probably break down in the face of such dynamism for instance.

As for whether the ticks are 'undeserved', I suppose it depends on one's perspective. It sounds like you are concerned with notions of 'fairness', and 'quality of service'. The dataflow dependencies you describe are present in Orc, and Orc' semantics are sufficiently formalized that it has been used to analyze quality of service guarantees. Perhaps those papers would be of interest to you, as it seems related to what you've described, re: policies, stealing ticks, etc. I think they're available from the Orc homepage.

In a sense, the notion of helping/tick donation just doesn't seem natural to me. You can't speed up a hardware process you're waiting on, for instance, so it doesn't generalize to all contexts. I think this impedes the "compositionality", which in turn, impedes the user's ability to reason about his system. That's not a very desirable outcome, so the language would need some way to express that a particular subsystem can or cannot be 'helped'. This adds complexity, but if it is well-motivated, then we've gained some necessary flexibility.

I meant this one, section 5.3.1.2, which introduces "join" and makes a reference to an example in 6.2.1.

It's interesting you mentioned lock-free algorithms, as I remembered them just recently for another reason - extending uniprocessor scheduling of concurrent program to a multiprocessor setting.
Will definitely take a look - it may well be that my use of word "helping" subconsciously derives from recursive helping.