AFAIK the lowest priority has the highest number in scheduling and in my system all priorities must be different. But isn’t other policies thinkable? For instance, how about a policy where priorities are not numbers but say that a task’s priority would be defined only in term of another task’s priority, and that other task would be the closest in priority to the task whose priority we are setting. Then we would never use actual numbers for priorities, but we would keep a data structure sorting the tasks in priorities and when a task comes as new or is getting a different priority assigned, then this structure is rebalanced. Would this priority mechanism be feasible or do you not agree that it’s a working idea?
2
In principle, the idea is good, and it solves a real problem: what do you do when the developers of two other programs have chosen priorities 12 and 11 for their processes and you need yours to be in between those two?
However, there’s two problems:
-
You need to do a topological sort of the priority graph every time a new process is created or its priority is changed. The best known algorithm for doing an online topological sort has an amortized worst-case time complexity of something like
O(√#edges). That means creating a process will get slower the more processes there are in your system. This is unacceptable, especially on systems like Unix and its cousins or Erlang, where a process is the basic unit of program decomposition, and you have thousands (Unix) or even tens of millions (Erlang) processes on a typical system. -
You will only get a partial ordering. What do you do when there are two processes which could be scheduled but they don’t have an ordering defined between them? Which one do you run first? In a totally different field, the Fortress programming language has a similar problem: Fortress doesn’t have an operator precedence table, instead operator precedence is defined relative to other operators (e.g.
+has same precedence as-,*has higher precedence than+) etc. In Fortress, mixing two operators which don’t have a defined ordering is simply a compile error. But you can’t really do that with two processes, simply refuse to start one.
On a “closed” system where the total set of potentially running processes is fully known before runtime at development time, you could do all of the work of making sure the ordering is total, detecting cycles in your graph, and topologically sorting at development time. And in fact, that’s what’s typically done when developing hard-realtime systems.
1
Why is it needed? There’s nothing from stopping you from designing a super-flexible priority system but, unless it’s actually solving a real problem, adding the additional complexity to something as performance critical as the scheduler is going to be a hard sell.
A simpler solution would be to put a daemon in userspace that can periodically tell the kernel to update the priorities of running processes as new relationships get put in place. This would keep the kernel-space scheduling code simple & efficient while allowing you all the flexibility you need.