OSDev.org

The Place to Start for Operating System Developers
It is currently Mon Oct 22, 2018 7:55 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 35 posts ]  Go to page 1, 2, 3  Next
Author Message
 Post subject: Round Robin Priority Implementation
PostPosted: Sun Jul 29, 2018 11:20 am 
Offline
Member
Member
User avatar

Joined: Fri Aug 07, 2015 6:13 am
Posts: 986
Hello again, I've recently implemented some basic multitasking and I am wondering on how to expand it.
I want to add priorities nothing complicated just idle, normal, medium and high.
Currently I only have 1 list that circles around in a loop.
Wiki only shows some generic information but that is not enough for an actual implementation.
I've never worked with this stuff before so please excuse my unfamiliarity with the topic.
I just need some general guidelines, again I am a total noob when it comes to this.
Also my kernel is monolithic and I don't care about other CPU's (cores) at the moment.

_________________
OS: Basic OS
About: 32 Bit Monolithic Kernel Written in C++ and Assembly, Custom FAT 32 Bootloader


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Sun Jul 29, 2018 12:25 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
Hi,

Octacone wrote:
I want to add priorities nothing complicated just idle, normal, medium and high.
Currently I only have 1 list that circles around in a loop.


Why not have 4 lists (one for idle, one for normal, ...) where each list circles around in a loop?

When you're looking for a task to give CPU time to; you'd just grab the next task in the "high" list, and if there's no tasks in the "high" list you'd just grab the next task in the "medium" list, and if there's no tasks in that list either then..


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Sun Jul 29, 2018 12:38 pm 
Offline
Member
Member
User avatar

Joined: Fri Aug 07, 2015 6:13 am
Posts: 986
Brendan wrote:
Hi,

Octacone wrote:
I want to add priorities nothing complicated just idle, normal, medium and high.
Currently I only have 1 list that circles around in a loop.


Why not have 4 lists (one for idle, one for normal, ...) where each list circles around in a loop?

When you're looking for a task to give CPU time to; you'd just grab the next task in the "high" list, and if there's no tasks in the "high" list you'd just grab the next task in the "medium" list, and if there's no tasks in that list either then..


Cheers,

Brendan


So basically I have:
idle_list
normal_list
medium_list
high_list

Let's say that each one of them has 1 entry,
Scheduler gets called, picks high_list executes the task and then moves onto medium_list etc...
But doesn't that mean that all of them will get the same exact amount of CPU time?
So I need to make sure that the entire list has been executed before moving onto the next (lower priority) one?

_________________
OS: Basic OS
About: 32 Bit Monolithic Kernel Written in C++ and Assembly, Custom FAT 32 Bootloader


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Sun Jul 29, 2018 1:03 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
Hi,

Octacone wrote:
Brendan wrote:
Why not have 4 lists (one for idle, one for normal, ...) where each list circles around in a loop?

When you're looking for a task to give CPU time to; you'd just grab the next task in the "high" list, and if there's no tasks in the "high" list you'd just grab the next task in the "medium" list, and if there's no tasks in that list either then..


So basically I have:
idle_list
normal_list
medium_list
high_list

Let's say that each one of them has 1 entry,
Scheduler gets called, picks high_list executes the task and then moves onto medium_list etc...


No; scheduler would always run the task from the high list (until that task has to wait for something and there's no tasks on the high list anymore).

Note that typically "high priority" would be used for things that spend most of their time blocked/waiting to make sure that they can respond quickly when whatever they're waiting for actually happens (e.g. maybe a GUI that spends most of its time waiting for a keyboard/mouse event, where you want the GUI to respond to the keyboard/mouse very quickly even when there's 1234 "normal priority" tasks pounding the daylights out of the CPU).


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Sun Jul 29, 2018 1:52 pm 
Offline
Member
Member

Joined: Wed Jul 25, 2018 2:47 pm
Posts: 36
Location: Pizzaland, Southern Europe
For anyone interested, I think this is called "multilevel feedback queue" in literature


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Sun Jul 29, 2018 2:45 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
Hi,

frabert wrote:
For anyone interested, I think this is called "multilevel feedback queue" in literature


Mostly, it's an easy first step towards something more complex.

If you added the "feedback" part it could become "multilevel feedback queue" (but that's relatively broken - in general it's better for programmers to explicitly say what they need than it is for the scheduler to auto-magically get all the priorities wrong because the programmer said nothing).

My preferred next steps would be to add preemption, so that when a task unblocks you check if the list it uses is higher priority that the list that the currently running task came from, and if it is you preempt the currently running task and switch to the unblocked task immediately. That way you get much better latency because you don't need to wait for some low priority task to finish its time slice. Then I'd suggest giving tasks "sub-priorities", and changing the scheduling algorithm used by "idle" to "variable time slice" (similar to round robin, but the time slice length depends on the sub-priority); and changing the scheduling algorithm used for "medium" to "variable frequency" (higher priority tasks get more fixed size time slices); and so on. Essentially, it'd end up being 4 scheduling policies (where each scheduling policy may have a different scheduling algorithm) with priorities within a policy.


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Sun Jul 29, 2018 2:54 pm 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 498
One thing to keep in mind before (or while) you implement priority support in your scheduler is that without a mechanism to avoid priority inversion, priorities might actually decrease responsiveness. YMMV but I found it to be really hard to utilize priorities without priority inheritance in my OS. For example, giving higher priorities to input device drivers actually increased the input latency as it made input drivers steal cycles from the compositor or bus drivers. A naive priority scheme is worse than no priority support at all.


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Sun Jul 29, 2018 2:57 pm 
Offline
Member
Member

Joined: Wed Jul 25, 2018 2:47 pm
Posts: 36
Location: Pizzaland, Southern Europe
Korona wrote:
For example, giving higher priorities to input device drivers actually increased the input latency as it made input drivers steal cycles from the compositor or bus drivers.

I think that that's partially solved by giving higher priority tasks exponentially shorter time quanta, for example top priority tasks might get 1ms, second tier 2ms, third tier 4ms and so on...


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Sun Jul 29, 2018 4:20 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
Hi,

Korona wrote:
One thing to keep in mind before (or while) you implement priority support in your scheduler is that without a mechanism to avoid priority inversion, priorities might actually decrease responsiveness. YMMV but I found it to be really hard to utilize priorities without priority inheritance in my OS. For example, giving higher priorities to input device drivers actually increased the input latency as it made input drivers steal cycles from the compositor or bus drivers. A naive priority scheme is worse than no priority support at all.


That's not priority inversion, that's setting the priorities wrong (e.g. if the compositor was higher priority than then keyboard then the keyboard won't steal time from the compositor, and input latency wouldn't have been improved at the expense of output latency).

True priority inversion typically involves a shared resource - e.g. a high priority task can't acquire a mutex because a low priority task currently has it (and then a medium priority tasks preempts the low priority task and prevents the release of the mutex, so now you've got lots of low priority and medium priority tasks getting CPU time while the high priority task gets none).

frabert wrote:
Korona wrote:
For example, giving higher priorities to input device drivers actually increased the input latency as it made input drivers steal cycles from the compositor or bus drivers.

I think that that's partially solved by giving higher priority tasks exponentially shorter time quanta, for example top priority tasks might get 1ms, second tier 2ms, third tier 4ms and so on...


For a system where the currently running task is always one of the highest priority tasks that can run (like I've suggested as a "first step" for Octacone), there are only 2 cases - either there is only one task that has the highest priority (and therefore there are no time slices at all - that tasks runs until it's preempted by an even higher priority task or blocks/waits or terminates) or there are 2 or more tasks that share the highest priority (and therefore you're switching between tasks with the exact same priority).


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Mon Jul 30, 2018 12:06 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 498
Brendan wrote:
That's not priority inversion, that's setting the priorities wrong (e.g. if the compositor was higher priority than then keyboard then the keyboard won't steal time from the compositor, and input latency wouldn't have been improved at the expense of output latency).

True priority inversion typically involves a shared resource - e.g. a high priority task can't acquire a mutex because a low priority task currently has it (and then a medium priority tasks preempts the low priority task and prevents the release of the mutex, so now you've got lots of low priority and medium priority tasks getting CPU time while the high priority task gets none).

No, that is not correct. Priority inversion does not require a shared resource. It requires a dependency of one thread on another thread, in the sense that one thread needs to block until the other thread completes some operation. But it is true that this was not clear from my post, so let me elaborate on my point:

Assume that we have three threads: (1) a bus driver (e.g. for the USB or PS/2 bus), (2) a HID driver (e.g. for the USB HID protocol or for the AT keyboard protocol) and (3) a compositor. For the sake of this argument, the relative priority of the HID driver and compositor does not matter. We certainly want to give the bus driver a lower priority than the HID driver and the compositor: If we do otherwise, input events and redraws will be preempted by notifications from completely unrelated devices (e.g. HDDs on the USB bus). However, once the HID driver waits for data from the bus driver (e.g. completion of a DMA request), we're in a priority inversion situation: Instead of handling control to the bus driver in order to receive input events ASAP, we might switch to some other low-priority process and hence increase input latency.

This is not a theoretical argument, I've seen exactly this behavior in practice.


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Mon Jul 30, 2018 12:56 am 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 43
One very easy way to implement priorities in a round-robin system is to give each process a static and dynamic priority. Both are numbers. The static priority is set with some system call and inherited to child processes. If you want, you can also implement some permission stuff regarding setting the priority.

The process list is sorted by dynamic priority. You always pick the process with the highest dynamic priority. It is set to the static priority when the process is put into the queue and increased by 1 every time the process is not picked. If the process is picked, the dynamic priority is reset (more efficient schemes involving a priority queue and some clever mathematics are available)

This means that for each runable process, at some point the dynamic priority has to exceed the dynamic priority of all other processes. Which ensures that, no matter what, no runable process can starve.

Unfortunately, this way you have to pass over the entire (runable) process list each time you reschedule. So this isn't a solution for supercomputers.


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Mon Jul 30, 2018 8:27 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
Hi,

Korona wrote:
Assume that we have three threads: (1) a bus driver (e.g. for the USB or PS/2 bus), (2) a HID driver (e.g. for the USB HID protocol or for the AT keyboard protocol) and (3) a compositor. For the sake of this argument, the relative priority of the HID driver and compositor does not matter. We certainly want to give the bus driver a lower priority than the HID driver and the compositor: If we do otherwise, input events and redraws will be preempted by notifications from completely unrelated devices (e.g. HDDs on the USB bus). However, once the HID driver waits for data from the bus driver (e.g. completion of a DMA request), we're in a priority inversion situation: Instead of handling control to the bus driver in order to receive input events ASAP, we might switch to some other low-priority process and hence increase input latency.


That's just correctly honouring priorities (that are wrong) without inverting the priorities (allowing a lower priority task like the bus driver to steal CPU time from a higher priority task like the HID driver).

As a general rule; if X depends on Y (e.g. HID driver depends on services provided by the bus driver) then the priority of Y needs to be higher than or equal to the priority of X. In other words, "give the bus driver a higher priority than both the HID driver and the compositor".

If priority is inherited when a request is made (e.g. when the HID driver asks the bus driver to do something, the priority of the HID driver is inherited by the bus driver) the system would automatically fix priorities (that shouldn't have been wrong and shouldn't have needed fixing).

For priority inversion; I use the "avoid blocking" solution (asynchronous communication, no shared memory, no shared locks), so there's nothing a low priority task can do to cause a higher priority task to block and priority inversion can't happen. Of course even though it's immune to priority inversion; I can still get the priorities wrong (and end up with a medium priority task stealing CPU time from a task that should've been higher priority but is actually lower priority).


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Mon Jul 30, 2018 11:10 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 498
Yes, the priorities work as intended (I never claimed something different) but the design still introduces inversion and is broken.

Asynchronicity does not change the problem. My OS is a fully asynchronous microkernel-based OS. However, at some point (i.e. when no outstanding asynchronous requests hits a fast path), threads have to block for asynchronous completion notifications. At that point you run into the problem I described.

Yes, giving the bus driver a higher priority would fix this problem but introduce new (and more severe) problems: As I wrote in my last post, (at least in the case of USB, e.g. EHCI and below; for XHCI the situation is slightly better) if the bus driver has a higher priority than the HID driver, requests from other devices (e.g. block devices) can preempt the HID driver. There is no static priority scheme that solves the whole problem!


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Tue Jul 31, 2018 10:24 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
Hi,

Korona wrote:
Yes, the priorities work as intended (I never claimed something different) but the design still introduces inversion and is broken.

Asynchronicity does not change the problem. My OS is a fully asynchronous microkernel-based OS. However, at some point (i.e. when no outstanding asynchronous requests hits a fast path), threads have to block for asynchronous completion notifications. At that point you run into the problem I described.

Yes, giving the bus driver a higher priority would fix this problem but introduce new (and more severe) problems: As I wrote in my last post, (at least in the case of USB, e.g. EHCI and below; for XHCI the situation is slightly better) if the bus driver has a higher priority than the HID driver, requests from other devices (e.g. block devices) can preempt the HID driver. There is no static priority scheme that solves the whole problem!


In practice; the bus driver (USB controller driver) has to be "very high priority" because it needs to be able to handle an "end of frame" IRQ every 1 ms; and you can't allow less important things (like USB device drivers - e.g. HID driver, block device driver, ...) to starve the bus driver of CPU time and miss IRQs. Don't forget that, more than anything else (except maybe "HID device polling rate"), HID latency depends on the USB controller driver's IRQ latency.

Of course the bus driver can be multi-threaded, with one "very high priority" thread for IRQ handling, and one "only high priority" thread for handling requests from USB device drivers (e.g. HID driver, block device driver, ...).


Cheers,

Brendan

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: Round Robin Priority Implementation
PostPosted: Tue Jul 31, 2018 10:28 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 498
There is no need for one IRQ every frame. One IRQ before each frame counter wraparound (i.e. every 1024 ms) is enough. So there is no need for such a high priority - USB drivers cannot starve the bus driver anyway (unless they need more than 1024 ms to process a single packet - in that situation your system is likely doomed anyway).

The rest of your post (multiple threads and so on) makes sense, yes.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 35 posts ]  Go to page 1, 2, 3  Next

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 20 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group