OSDev.org

In my previous os I recreated the scheduling system 3 times, and I still do not understand the concept of preemptive priority based scheduling (like on linux and windows).

- Is preemption the fact that a thread does not run its full time burst because another higher priority thread is ready to run ?
- How to determine a good duration for the thread to be in not-ready state and not overtake other threads time ?
- How should I sort the threads based on their priority ? Should I make a list of thread pointers and for each thread I set the thread on the list x times where x is their priority ?

-Preemption is when a task is prevented from running further. So basically, any system in which a task is forced to give up control of the CPU. Normally this happens because of a timer interrupt. Note that a task can also voluntarily give up its time by calling a blocking kernel function.
-Not quite sure what you're asking. If a thread is not ready to run, then you mustn't schedule it. It's still waiting for something to happen and can't run yet.
-There are entire libraries about this, but a relatively simple system would be round robin with priorities. This works essentially like this: Every task has a static priority and a dynamic priority. The static priority being what the user set up. When a task becomes runnable, you enter it into the run queue and initialize its dynamic priority to be equal to its static priority. Then, each time you run the scheduler, you pick the task with the highest dynamic priority, and you increment the dynamic priority of any runnable task you do not pick. And when you pick a task, you remove it from the runnable queue. If it is still runnable when you preempt it, then you enter it again with the rules as above.

This ensures non-starvation, since any task will have the highest priority at some point (as long as you ensure no overflows happen, of course). If the types and allowed ranges are chosen such that the dynamic priority has a far higher range than the static, then no task can be entered at the top of the queue.

For the most part, these are idle musings, however, since these days you often have more processors than runnable processes. And when a process becomes runnable, it does not remain so for very long. So most of the time, preemption is unnecessary.

Modern scheduling algorithms also try to keep CPU movement to a minimum (although obviously still allowing them in case a particular CPU becomes clogged), and also to boost processes that regularly sleep on their own, and penalize processes that get preempted. The reason for the former is that CPU caches get trashed when a process is moved from one CPU to another, and the reason for the latter is that processes that sleep regularly are likely interactive and require fast reactions after interrupts.

nullplan wrote: -Not quite sure what you're asking. If a thread is not ready to run, then you mustn't schedule it. It's still waiting for something to happen and can't run yet.

You already answered it.

Is preemption the fact that a thread does not run its full time burst because another higher priority thread is ready to run ?

Each thread has a time burst, I asked if the thread has to run its full time burst for e.g. 6 is th0 time burst, so the timer should fire an IRQ after 6 ticks. Or, the timer fires IRQ after each tick and I should check if there is a higher priority thread than the current one, if it is then I should stop the current one from running and run the higher priority one. And the current one would have not completed its time burst.

Thanks.

devc1 wrote:

Is preemption the fact that a thread does not run its full time burst because another higher priority thread is ready to run ?

Each thread has a time burst, I asked if the thread has to run its full time burst for e.g. 6 is th0 time burst, so the timer should fire an IRQ after 6 ticks. Or, the timer fires IRQ after each tick and I should check if there is a higher priority thread than the current one, if it is then I should stop the current one from running and run the higher priority one. And the current one would have not completed its time burst.

Either.

So, a thread will be pre-empted if:

- It has run it's time full time burst.
- It has not yet run its full time burst. But in the mean time, another, higher priority thread has become runnable.

The latter can be in response to any event, not just ticks. A UI thread might be waiting for user input, for example, and a mouse or keyboard event causes an interrupt. The kernel will service the interrupt, which queues an event for the UI thread, which is then woken up possibly at a higher priority than the current thread.

In fact, in this latter case, if your mouse/kbd is USB based, the interrupt will enable the USB thread, which will itself pre-empt the running process, and that USB thread will then trigger further events to wake up the UI thread.

Eventually, once the higher priority threads are done (interactive threads tend to do their stuff rather quickly,) the scheduler will get back to your pre-empted thread, and pick it up again.

Another difference between a thread using its full time burst and a thread that is pre-empted by higher priority thread is how the pre-empted thread is queued for future running.

In the case of a thread using its full time burst, it may be placed on the back of its priority queue, whereas a thread pre-empted by a higher priority thread may be placed onto the front of its priority queue, so it is picked up straight away to finish its time burst when the scheduler next gets to its priority.

The last one was interesting, I will definitely consider it.

That answers my questions, Thanks,

Please guys assure me if this is correct before I start making the scheduler. I don't want to keep remaking schedulers

So the scheduling would go on these steps :

There are different ideas how the scheduler should work, and they are not right-wrong.

My scheduler has 256 priority levels, but only one (level 2) is used by applications. Some kernel threads have higher priority. In my scheduler, priority is static. If a higher priority thread is made active, then a lower priority thread already running will be preempted. If a same priority (or lower priority) thread becomes active, nothing happens. Threads at the same priority level are scheduled with round-robin. If a thread uses up it's time-slice, it will be preempted. A thread can also become blocked or give up it time-slice voluntarily, in which case a new thread needs to be selected.

If you support multicore, then you also need to consider how threads are spread on different processor cores. The scheduler needs to balance load between cores and can move threads between cores to achieve better load distribution. In my design, each processor core has a null-thread at priority level 0. It will run hlt in a loop. Thus, the ready lists never becomes empty.

Im trying to make a priority based preemptive scheduler, is that how it works ?

And btw, I think the idle thread would have the highest priority ? and I will also make its priority controlled by the user or even disable it, to maximize cpu usage when needed. that's my design.

devc1 wrote:Im trying to make a priority based preemptive scheduler, is that how it works ?

This is how one of them works. There are as many schedulers as operating systems, and there are tons of research papers, articles, and even books about them. That particular rabbit hole is very deep.

devc1 wrote:And btw, I think the idle thread would have the highest priority ?

Honestly, the idle thread should probably be a special case. You don't want to run it while there is anything else runnable. If you add it to the normal scheduling structures, it would get scheduled like any other thread, even at lowest priority. But the entire goal of scheduling algorithms is to prevent starvation under all circumstances. So if you don't special case it, it would sometimes run although the CPU could be doing other things.

devc1 wrote:and I will also make its priority controlled by the user or even disable it, to maximize cpu usage when needed. that's my design.

The idle thread is scheduled only if there is nothing else to do. What's the point of having a priority for it, then? And if disabled, what do you do when there is no thread ready to run?

- I think that I will shutdown the cpu if it finds nothing to run, and make it wait for some interrupt from another cpu when a thread is ready.
- So if I have one thread just executing an infinite loop, the cpu will run on 100% and burn the cpu temperature and consume energy (in case of laptops). the idle thread should work a bit to cool the cpu down ?

devc1 wrote:- I think that I will shutdown the cpu if it finds nothing to run, and make it wait for some interrupt from another cpu when a thread is ready.

Code: Select all

Honestly, the idle thread should probably be a special case. You don't want to run it while there is anything else runnable. If you add it to the normal scheduling structures, it would get scheduled like any other thread, even at lowest priority. But the entire goal of scheduling algorithms is to prevent starvation under all circumstances. So if you don't special case it, it would sometimes run although the CPU could be doing other things.

- So if I have one thread just executing an infinite loop, the cpu will run on 100% and burn the cpu temperature and consume energy (in case of laptops). the idle thread should work a bit to cool the cpu down ?

The hlt instruction makes the cpu idle and consume very little energy. I think that is enough unless you want to support advanced power management, which is quite complicated.

Well, but if I now have one thread running an infinite loop, the thread is tecnically always ready so the cpu will be used at 100% which will increase its temp.

So how to determine when the idle thread should run, I was using before a value which indicates at which timer ticks the thread becomes ready to run after each task switch ?

devc1 wrote:Well, but if I now have one thread running an infinite loop, the thread is tecnically always ready so the cpu will be used at 100% which will increase its temp.

So how to determine when the idle thread should run, I was using before a value which indicates at which timer ticks the thread becomes ready to run after each task switch ?

Have a look at xv6, and how it does its idle scheduling:

Video explaining xv6 scheduler, part of a good series explaining xv6.

While xv6 doesn't do priority scheduling, it's basically a single priority round robin scheduler, it is interesting in that the scheduler runs in its own context, the context of the CPU on which it is running.

So, say thread A is going to sleep, and we need to pick a new process to schedule, we first switch context from thread A to the current CPU's scheduler context. That scheduler context will then scan for a ready to run thread, and if it finds one (thread B), it will now switch to thread B's context, and thread B is resumed.

The upshot being that if no new thread is ready to run, this is your idle situation, and your scheduler thread can just go into idle mode, which can be as simple as waiting for the next interrupt using "hlt" then polling for a new thread to run again.

The beauty of this is that this mechanism doesn't depend on HOW you schedule the next thread. It's pure mechanism with little in the way of policy, so the act of choosing the next thread (basically, how you implement your priority scheduling) can be encapsulated in a single function that the scheduler calls, which just returns the next thread to run, and replaced at will easily to change how scheduling works, even at runtime if necessary.

devc1 wrote:- So if I have one thread just executing an infinite loop, the cpu will run on 100% and burn the cpu temperature and consume energy (in case of laptops). the idle thread should work a bit to cool the cpu down ?

No. If a CPU cannot handle running at 100% for extended periods, then it should not be on the market. If you have a task that needs the run time, let it run. Let the user cancel it if it is a mistake, that is not your (the kernel's) choice to make. In general, assume that the work is accomplishing something useful. Throttling a batch process because of perceived power consumption issues is typically not sensible. You are making the task take longer than it has to.

On UNIX-like operating systems, the administrator can set ulimits to prevent evil users from overusing resources, and CPU time is one of the limits that can be set. So that is one way to deal with runaway processes. Note that in this case, the policy choice is the administrator's, not the kernel's.

BTW, energy consumption is also an issue in desktops and servers. We don't want to pay more for power than we have to. Also, did you know that you can just mark the sentence you want to reply to and click the "quote" button top right of the post to only quote that part (when you are in the "Post a reply" dialog)?

devc1 wrote:Well, but if I now have one thread running an infinite loop, the thread is tecnically always ready so the cpu will be used at 100% which will increase its temp.

Let it run. Let it run hot. If the CPU cooling system can't handle a fully loaded CPU, it is inadequate and must be supplemented.

Modern CPUs have ways to change the clock speed to prevent meltdowns. If overheating is an issue, let the thermal throttling handle it.

Thanks