LWN: Comments on "Utilization inversion and proxy execution"

Utilization inversion and proxy execution

raistlin — Fri, 22 May 2020 16:55:14 +0000

It is, IMO, very neat. The problem is that it's not trivial to decide what to do, on an SMP systems... And, believe me, we thought about just turning CONFIG_SMP off, but we've been told that wouldn't end up well. :-)

So, imagine that A owns a lock, and that both B and C want it, so they both block on A.

At this point, A can run:
1) in its own timeslice, and
2) in B's timeslice, and
3) in C's timeslice.

Which is cool, because being able to run for sooo long, guarantees that A will be quick with the critical section on the lock! So far so good then, we just have to leave both B and C in the runqueue, and when the scheduler picks A, we ran A (of course) but also when the scheduler pick B, we run A and when it picks C, we run A.

Now, what about we are on a 4 CPUs system and, the scheduler, all at the same time:
- picks A on CPU 0
- picks B on CPU 2
- picks C on CPU 3

There. We obviously can run A on 3 CPUs at the same time (that would be _really_funny_!! :-D )... And hence you have to deal with a bunch of special cases and the "neatness" rapidly sinks. :-(

There are solutions, from a theoretical (as in, academic papers) point of view, but they're not the most beautiful to implement in real-world Linux kernel.

Smart people are looking into solutions, and I'm confident they'll find a way to get around the problems. But yeah, there it is why we're not there yet :-)

Utilization inversion and proxy execution

glenn — Tue, 19 May 2020 18:18:24 +0000

Assigning priority to data would be equivalent to assigning priority to a critical section. Data and critical section can both be viewed as a resource with an assigned priority. The priority ceiling locking protocol (PCP) assigns priorities to mutexes, and hence critical sections. I believe this was the inspiration for the pthread mutex attr PTHREAD_PRIO_PROTECT.

I think a looser coupling of priority from thread of execution makes more sense. Think of each thread of execution being put in a bucket*, and the CPU scheduler schedules buckets instead of threads. By default, a new thread/process is put in a new bucket. When the CPU schedules a bucket, it delegates to the bucket which thread to schedule. I think this scheme can simplify priority inheritance implementation: a thread inherits a priority by being moved to the bucket of the blocked higher-priority task from which it inherits. The CPU scheduler doesn't need to know about inheritance, because it only schedules buckets.**

I believe both MPI/UNC's LitmusRT and CMU's Linux/RK kernels supports these concepts.

* Literature will call these buckets "servers," but I feel like this term has gotten too overloaded over the years. Speaking of renaming classic terms, I think proxy execution is simply "bandwidth inheritance." Is this right?

** Things can get really crazy when you consider deadline-scheduling. A bucket that looses CPU time due to donating its CPU time to a thread of another bucket is reciprocated with lower-priority budget of the inheriting thread in exchange. Because we're talking about deadline-scheduling, this lower-priority budget _may_ become valuable in the future. The availability of this budget may reduce the need for inheritance actions in the future. I'm not aware of any implementations of this budget-exchange system. I think maintaining a ledger of past budget exchanges could be quite complicated. (I can't find a reference to the academic paper that proposed this scheme.)

Utilization inversion and proxy execution

Wol — Mon, 18 May 2020 17:27:39 +0000

> Maybe it's because you just shouldn't be sleeping while holding a lock in the first place :-)

Sounds great, but I guess in practice that's impossible. Especially if it's user space locking resources it needs. Locks are just a nightmare, full stop, but you need them to stop processes trampling over each other.

That's why they have things like the deadlock killer - if I'm holding a lock you want, and then I try and claim a lock you're holding, one of us is going to get killed ... there's just no easy way to manage locks.

Cheers,
Wol

Utilization inversion and proxy execution

dgm — Mon, 18 May 2020 17:11:46 +0000

This all seems to suggest that priority should often be a property of the data, not the process.
I don't know if it has been ever tested (a quick googling didn't turn up anything), but it would be interesting to assign priorities to sockets, files, queues or semaphores in addition to/instead of processses.

Utilization inversion and proxy execution

Sesse — Mon, 18 May 2020 16:40:26 +0000

Wow, so with proxy execution, if A sleeps holding a lock and B needs it, A can be scheduled on B's timeslice? (Can it just context-switch directly to B?) That sounds really neat; so neat that I can't immediately understand why it hasn't been done before. Maybe it's because you just shouldn't be sleeping while holding a lock in the first place :-) I wonder if you one could do similar things for condition variables or the likes.

Utilization inversion and proxy execution

valschneider — Fri, 15 May 2020 20:04:54 +0000

Hey Jon,

Thanks a lot for the write-up! One thing perhaps worth clearing up is that I'm only a newcomer to Proxy Execution - for now it's mostly been Peter and Juri's baby.
Juri talked about it at OPSM19 (https://www.youtube.com/watch?v=mlu9pC5IL2g) and at LPC18 (https://www.linuxplumbersconf.org/event/2/contributions/62/).

Just making sure credit goes where credit is due!