OSDev.org

I think I'm caught in a paradox

I want to execute processes called by other processes as more as possible
But on the other hand, I need to prevent other processes from starvation

Is there any good scheduling algorithms can meet my requirements?

Round robin is a nice and simple choice for starters. You keep all currently runnable processes in a list. New processes are added at the end of the list, processes that get scheduled in are removed from the front. If a process is scheduled out that is still runnable, it is also added to the back of the list.

That means, any process that becomes runnable will be scheduled once all the processes in front of it in the queue have had their turn. No process can starve.

The algorithm in this form does not admit any priorities, but that is for a later day to solve. Algorithm also does not allow for a preference for any CPU or NUMA node. You may need something more complicated when the time comes and you truly care. But this algorithm should get you started at least.

The choice of scheduling algorithm has little to do with IPC, BTW, since the calling process will be suspended waiting for the answer, and the called process will become runnable if it isn't already. As long as you do not make tasks wait for the end of their time slice to be scheduled out, all is well.

I'm also working on a microkernel and currently I use a very simple round-robin queue with weak references to all threads. Threads that don't have to wake up yet are simply skipped over and any dead threads are removed lazily. This is obviously not efficient but it works well enough for now.

I don't have any concrete plans for a new scheduler yet, but I'll likely split it in two parts: a linked chain for runnable threads only and a priority queue with the "sleep until" time as key.

theflysong wrote: I want to execute processes called by other processes as more as possible
But on the other hand, I need to prevent other processes from starvation

You may want to look into time slice donation: every thread has a limited amount of time to run, but can choose to immediately start running another thread with the remainder of its time slice. This way you can achieve low latency (which I assume is what you're after) yet it won't affect any other threads since they get to keep their time slice.

Demindiro wrote:I'm also working on a microkernel and currently I use a very simple round-robin queue with weak references to all threads. Threads that don't have to wake up yet are simply skipped over and any dead threads are removed lazily. This is obviously not efficient but it works well enough for now.

I don't have any concrete plans for a new scheduler yet, but I'll likely split it in two parts: a linked chain for runnable threads only and a priority queue with the "sleep until" time as key.

theflysong wrote: I want to execute processes called by other processes as more as possible
But on the other hand, I need to prevent other processes from starvation

You may want to look into time slice donation: every thread has a limited amount of time to run, but can choose to immediately start running another thread with the remainder of its time slice. This way you can achieve low latency (which I assume is what you're after) yet it won't affect any other threads since they get to keep their time slice.

The evil process could create hundreds of process and let them donate all the slice to it.so that it can take up lots of time

nullplan wrote:Round robin is a nice and simple choice for starters. You keep all currently runnable processes in a list. New processes are added at the end of the list, processes that get scheduled in are removed from the front. If a process is scheduled out that is still runnable, it is also added to the back of the list.

That means, any process that becomes runnable will be scheduled once all the processes in front of it in the queue have had their turn. No process can starve.

The algorithm in this form does not admit any priorities, but that is for a later day to solve. Algorithm also does not allow for a preference for any CPU or NUMA node. You may need something more complicated when the time comes and you truly care. But this algorithm should get you started at least.

The choice of scheduling algorithm has little to do with IPC, BTW, since the calling process will be suspended waiting for the answer, and the called process will become runnable if it isn't already. As long as you do not make tasks wait for the end of their time slice to be scheduled out, all is well.

Thanks.I have tried the round robin before.So I want to try something else.

theflysong wrote: The evil process could create hundreds of process and let them donate all the slice to it.so that it can take up lots of time

If the process can abuse that it can just as easily just spawn a bunch of threads doing nothing but waste cycles.

If you're worried about fairly distributing execution time you will need process groups (or something similar) and adjustable priorities for each group.

Also, know that it's easy to grind a system to a halt by spawning a couple dozen threads (depending on CPU) and having them do an unaligned `lock cmpxchg` on a page boundary in a loop. (For extra fun, play some music on that same machine).

I'm learning about some fun and exciting new kinds of forkbomb in this thread, but not so much about schedulers! But seriously, I think an evil process getting more than its fair share of time is a security and administration issue - be careful what you install.

I had some ideas about this way back in the past when I knew basically nothing. They involved iterating over the whole process list on every task switch, checking how much time a process has had recently. I guess that's not very efficient? IDK but it seems to be done more simply in real OSs.

This is where prioritized schedulers and dynamic priority computation become important. Of course, this won't stop a fork bomb, but it should stop a greedy process that creates 50 threads to monopolize the CPU. Note that I guess these threads could manipulate the heuristics involved with the computation, but that would be quite tricky to do.

Hi,

Although it is subject to change, we currently use 4 levels of queues where level 0 is FCFS (First Come First Serve), level 1 is PRI (Priority), level 2 is RR (Round Robin) and Level 3 is planned to be SJF (Shortest Job First). The Schedule function just goes through these 4 levels of priority. A thread can be moved from a queue by lowing or raising its priority which in turns changes how it gets scheduled.

neon wrote:Hi,

Although it is subject to change, we currently use 4 levels of queues where level 0 is FCFS (First Come First Serve), level 1 is PRI (Priority), level 2 is RR (Round Robin) and Level 3 is planned to be SJF (Shortest Job First). The Schedule function just goes through these 4 levels of priority. A thread can be moved from a queue by lowing or raising its priority which in turns changes how it gets scheduled.

I think it would be a good scheduling algorithms for me.I will try it.Thanks.