[BUG] - Scheduler isn't always fair

bSchnepp commented 3 years ago

Issue Checklist

[x] A related or similar issue is not already marked as open
[x] The steps to reproduce have been tested, and do produce the issue described
[x] If relevant, graphical issues have a screenshot presented as well. Text-only issues have the text and it's correct version listed within a Markdown code block section
[x] The most recent commit on the master branch the bug is present in, with it's commit hash, is listed in this report

===================================================== Bug Description The scheduler currently relies upon a race to reschedule a process, where there is a different idle thread found first before the it is picked up, as in 4bd7bee28ce9383d5bae906b50a294c1b1a935de. Correct behavior would show that with a given core and thread is run, after the number of ticks has expired, it picks up a different thread rather than the same one. The current setup always ensures there is at least one idle thread at any given time, so this condition should always occur.

To Reproduce Please list the steps to produce the bug below:

Run the software in qemu, using test-nosd.sh
Observe serial output
Note the frequency for the same thread being scheduled

Screenshots If relevant, please provide screenshots here.

Expected behavior The output from kern_idle() should remain fairly similar between all of the threads, with some variance of being within a few thousand.

Additional information Any additional information should be placed here.

bSchnepp commented 3 years ago

This should be addressed with 038d4d82dcb6c7d55a10fdb48d5507c8d41d92e9, but there doesnt seem to be a great way to prove this is fair in an SMP environment.

bSchnepp commented 3 years ago

As of 02d61cf1b63078e6d359f1a474d14bd9925b67f7 with the no SMP environment, it appears fair. Once again however, this is difficult to prove in a multi core environment.

bSchnepp commented 3 years ago

Something to note is that in the non-SMP environment, one of the 3 tasks created appears to never be scheduled.

bSchnepp commented 3 years ago

A possible solution is to rework the threads to be scheduled into a temporary priority queue for each scheduler, and keep attempting to pull threads if possible, and if not, re-add the lowest priority thread. This has the unintended side effect of dragging in threads into non-ideal queues (putting more onto one core when it could be distributed), but would at least solve this issue of skipping a thread.

bSchnepp commented 2 years ago

This patch should address this issue complete now. b3ede6eb09a70af36053db09f130a467939025f3

bSchnepp commented 2 years ago

With ca9a1805a413877745222057bee64ee60223c710, this is all now within master.

bSchnepp / pantheon

[BUG] - Scheduler isn't always fair #16