Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

primitiveYield (167) interferes with temporal #priority: bumping #677

Open
marceltaeumel opened this issue Mar 28, 2024 · 10 comments
Open
Labels

Comments

@marceltaeumel
Copy link
Contributor

marceltaeumel commented Mar 28, 2024

If a process runs alone at its original priority and bumps it higher temporarily, setting it back and yielding will not schedule processes above its original priority. Only if there are other processes running on that original (lower) priority.

This seems to be an older optimization in primitiveYield.

Here is an example:

| flag p1 p2 |
flag := Semaphore new.
p1 := [
	Processor activeProcess priority: 80.
	Transcript showln: 'P1 started!'.
	flag signal. "activate p2"
	Processor activeProcess priority: 45.
	Processor yield. "fails to schedule p2"
	Transcript showln: 'P1 finished!'.] newProcess.
p1 priority: 45.

p2 := [ 
	Transcript showln: 'P2 started!'.
	flag wait.
	Transcript showln: 'P2 finished!'.
	] newProcess.
p2 priority: 50.

p2 resume.
p1 resume.

Expected transcript output:

P2 started!
P1 started!
P2 finished!
P1 finished!

However, we get:

P2 started!
P1 started!
P1 finished!
P2 finished!

It is only circumstantial that P2 finishes at all because the Timer Interrupt Scheduler (80) will be signaled eventually and then trigger P2 (50) finally. But P1 (45) has finished by then. This is not fair.

We can show that it works as expected once another process works on the original priority (45):

| flag p1 p2 p3 |
flag := Semaphore new.
p1 := [
	p3 resume.
	Processor activeProcess priority: 80.
	Transcript showln: 'P1 started!'.
	flag signal. "activate p2"
	Processor activeProcess priority: 45.
	Processor yield. "fails to schedule p2"
	Transcript showln: 'P1 finished!'.] newProcess.
p1 priority: 45.

p3 := [
	Transcript showln: 'P3 started!'.
	Transcript showln: 'P3 finished!'.
	] newProcess.
p3 priority: 45.

p2 := [ 
	Transcript showln: 'P2 started!'.
	flag wait.
	Transcript showln: 'P2 finished!'.
	] newProcess.
p2 priority: 50.

p2 resume.
p1 resume.

The output is as expected:

P2 started!
P1 started!
P2 finished!
P3 started!
P3 finished!
P1 finished!

By skipping the P3 output, we get the expected order for P1 and P2:

P2 started!
P1 started!
P2 finished!
P1 finished!

The optimization in primitiveYield reads:

(self isEmptyList: processList) ifTrue: [^nil].

And so wakeHighestPriority will not be called in time. But I think we should support temporal priority bumping this way.

@codefrau
Copy link
Contributor

I don't think that's a bug. yield should only yield to processes of the same priority. If there are none then it's a no-op. That primitive is correct.

However, your example should not need to yield at all. Changing a process priority should call wakeHighestPriority, IMHO.

@eliotmiranda
Copy link
Contributor

I agree with Vanessa. We either need a primitive to set a process’s priority rather than relying on assigning to its priority inst var. or we need a primitive which is invoked after a priority change. I’m not sure what the most convenient thing is, but my hunch is that the latter is more useful, but somewhat more difficult to explain ;-)

@OpenSmalltalk-Bot
Copy link

OpenSmalltalk-Bot commented Mar 28, 2024 via email

@codefrau
Copy link
Contributor

codefrau commented Mar 28, 2024

Wonder if any existing prim would do the right thing? Like suspending after setting priority maybe?

@OpenSmalltalk-Bot
Copy link

OpenSmalltalk-Bot commented Mar 28, 2024 via email

@eliotmiranda
Copy link
Contributor

eliotmiranda commented Mar 28, 2024 via email

@codefrau
Copy link
Contributor

That sounds nice and simple. I'll go with that. The primitive can check

for a runnable process simply:

  • the active process has no myList

  • a quiescent process (runnable but not the running one) has as its myList

the list in the quiescentProcesseLists array indexed by its priority.

So if neither of these is true the primitive can fail, and the fall-through

code can set the inst var.

I'd prefer if the primitive would not fail (meaning it should set the var itself), and the fallback code gets executed only on VMs that do not have the prim. It should purely be an optimization, if possible.

This is a pretty infrequent operation for the active process so the fallback code doesn't have to be highly efficient. I'd imagine waiting on an already signaled semaphore would do it? Or is that a no-op?

@OpenSmalltalk-Bot
Copy link

OpenSmalltalk-Bot commented Mar 29, 2024 via email

@marceltaeumel
Copy link
Contributor Author

Aha. So wakeHighestPriority is a rather convenient way (and a case of method re-use) to realize the desired behavior of yield. We assume that "highest priority" is of no concern when calling this method but only to let the next process on the same priority run. This led me to false conclusions about how things are expected to work. Maybe we want to comment the use of wakeHighestPriority in primitiveYield to avoid such confusion in the future.

(Btw: The timestamps of primitiveYield are weird in CoInterpreterPrimitives and InterpreterPrimitives, namely "eem 3/2/-4654 00:12" and "eem 3/2/-4654 00:02".)

Yes, it would be nice to expose wakeHighestPriority (or something similar) as primitive to complement priority changes from within the image. In the meantime, TimingSemaphore signal (see Delay class) could be a feasible workaround as Leon suggested:

Delay class >> wakeHighestPriority
	"Helper to fix scheduling after the active process changed its own priority."
	TimingSemaphore signal.

Process >> priority: anInteger 
	"Set the receiver's priority to anInteger."
	(anInteger >= Processor lowestPriority and:[anInteger <= Processor highestPriority])
		ifTrue: [priority := anInteger. Delay wakeHighestPriority]
		ifFalse: [self error: 'Invalid priority: ', anInteger printString].

Any concerns?

@codefrau
Copy link
Contributor

codefrau commented Apr 3, 2024

This sounds reasonable except the comment in Delay implies it only is used for the active process.

We need to decide on the exact semantics, and enforce them in the priority setter:

  • should it only reschedule if it is the active process?
  • should it only reschedule if it is runnable?
  • should it only reschedule if the priority was increased, rather than decreased?
  • should it reschedule if the prior priority was nil?
  • should preemptionYields affect the behavior?

That's the ones I can think of off the cuff.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

4 participants