2
$\begingroup$

I'm studying Real Time Systems, and in the textbook most of the focus is on scheduling algorithms. (Textbook: Real-Time Systems by Jane W. S. Liu)

In the algorithms that involve priorities, it is said that smaller integer represents higher priority (e.g. a process with priority 1 has more priority than one with 3). Then, in the subsequent discussions, there are terms involved like: "Let Pi be a process with a higher priority..." On such occurrences, I get confused whether higher priority means actually higher priority or larger integer. In most of the cases it means the former, however sometimes I've to guess that from the context, which is a bit time consuming.

As far as I know, all algorithms will work well with slight modifications if larger integers represented higher priority, and that would avoid confusion. So my question is: Is there any reason, apart from conventional / historical one, for using smaller integer for denoting higher priority? If not, why not amend it and avoid confusion?

$\endgroup$
3
$\begingroup$

This has always troubled me too. The problem is with the origins of the English word and the difference between ordinal numbers ("first", "second", "third", ...) and cardinal numbers (the numbers you use to count things).

In schedulers we use the word priority in the sense of:

the right to take precedence or to proceed before others[1]

It came into English from Norman French after the Norman conquest of England in 1066. It came into Norman French from the Latin word prior, which (in English) means

existing or coming before in time, order, or importance[1]

I added the emphasis on the word order to emphasize that we are using the word in the sense that requires we use ordinal numbers. So you should think of it in terms of a medieval court hierarchy. The king is seated at the dinner table first because he has the highest rank. The prince (etymology: via Norman French from Latin princeps, which means "first citizen"[2]) is seated second because he has the next highest rank. Then the dukes are seated third because they have the next highest rank. And so on. The knights are seated last because they have the lowest rank. (The common folk with no title don't get seated at all because they have no rank at all.)

[1] This is from the definition from Google. I think they may have gotten it from Oxford English Dictionary. [2]http://en.wikipedia.org/wiki/Royal_and_noble_ranks

$\endgroup$
  • $\begingroup$ Typically, the king, having the highest rank, is seated last. The lower ranks arrive first and wait for him; the king waits for no-one. $\endgroup$ – David Richerby Nov 7 '14 at 1:27
  • $\begingroup$ @DavidRicherby I'm just a simple North American, your sophisticated old-world ways frighten and confuse me. Would it work better if I said the king gets served his dinner first (after he is seated)? $\endgroup$ – Wandering Logic Nov 7 '14 at 22:01
  • $\begingroup$ That would work, yes. :-) $\endgroup$ – David Richerby Nov 7 '14 at 23:03
  • $\begingroup$ That's a good explanation. But then, in CS we're using numbers, whose default interpretation is cardinal, which causes the confusion. Can't we all decide to use higher numbers for higher priority? That'll make lives of many people a lot simpler, I guess. $\endgroup$ – taninamdar Nov 9 '14 at 11:27
1
$\begingroup$

I've always assumed it was related to time. Most people agree that time travels in one direction, and assign larger numbers as it continues.

This works whether you are referring to "which task has the earliest deadline" or "which task was inserted into the priority queue first" (which is often phrased as "which task has been waiting longer", but it doesn't make sense to constantly increment a counter for that, it is derived from the current time and the start time).

Even in the presence of more complex scheduling algorithms, it still makes sense to have all the numbers pointing the same way.

$\endgroup$
1
$\begingroup$

There is no general agreement on whether 1 is the highest or lowest priority.Some systems use low numbers to represent low priority ; others use low numbers for high priority.

Operating System Concepts, by Abraham Silberschatz and James Peterson

$\endgroup$
  • $\begingroup$ Welcome to Computer Science Stack Exchange! Is your answer a quote from the book you mention? If so, please edit it to make this clear: add > before the quote to indent it, and give the full title of the book. Thanks! $\endgroup$ – David Richerby Nov 6 '14 at 9:49
  • $\begingroup$ But what is the reason behind such disagreement? Why would anyone want to use low numbers to represent high priority? That is my question. $\endgroup$ – taninamdar Nov 6 '14 at 10:55
  • $\begingroup$ 1=> First . This means , while making Gantt Chart or giving CPU time slice , the Process with priority->1(First),should be given time slice First. $\endgroup$ – user3271050 Nov 6 '14 at 11:44
  • $\begingroup$ Fun fact: Linux uses both. In userland -20 is the most priority and 19 is the least priority, but in kernelland they get mapped to 40 for most priority and 1 for least priority. See getpriority(2) $\endgroup$ – o11c Nov 7 '14 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.