Scheduling Algorithm

[distantvoices]

I have some thoughts about weighed round robin for
the Non-Privileged User Processes:

Each process in the round robin ready queue has the field PROCESS_PREFERENCE set to a certain value:

say:
process A has PROCESS_PREFERENCE 50
process B has " " 50
process C has " " 40
process D has " " 20

process a is the running process. It's time to run is over:
PROCESS_PREFERENCE is decremented by 1 and it is added in_to the queue behind process B which experiences the same fate.

At a certain time, when PROCESS_PREFERENCE of A is decremented enough, it is stuffed into the queue after c resp after D, so that these processes gain their chance to run too. When PROCESS_PREFERENCE is exhausted, it will be restored with the original value.

Is it possible with this algorithm to avoid starvation whilst at meantime have f. ex. daemon processes running at lowest priority(PROCESS_PREFERENCE), which then get the processor from time to time?

thanks for feedback.

[Tim]

Sounds like you're describing variable quanta: A and B each have a longer quantum than C and D. That is, once scheduled, A and B will run for equal lengths of time.

This is OK, but probably not that important. Quantum expiry is fairly rare in I/O-bound tasks, which repeatedly have to yield the processor as they wait for hardware devices. Quantum expiry is generally useful when you have two or more CPU-bound tasks which must both run at the same time.

In general, assinging tasks priorities is a better way of making sure that every task gets its turn. For instance, consider a task computing pi to 1 million decimal places and a higher-priority task which manages the mouse pointer. Normally the pi task will have the CPU to itself, since no other task needs to run; the mouse pointer task is blocked, waiting for data from the mouse. When the user does move the mouse, it sends an interrupt, which wakes the pointer task. Since it has a higher priority than the pi task, it pre-empts it, moves the mouse pointer, and sleeps again.

If the mouse pointer task had a lower priority than the pi task, it would have to wait until the pi task's quantum expired before it could move the pointer. If this was the case, you'd see a jumpy mouse pointer. Specifically, it would move once every n seconds, where n is the length of the pi task's quantum.

[distantvoices]

Thanks for Feedback, Tim!

For Device driver tasks and Tasks I consider more important than scheduled ones, I have already one extra queue which is checked prior to the round robin queue.

I just intend to have a kind of NICE mechanism in this scheduling, so that I can tell the kernel to give some processes more often the cpu than others.

[Tim]

I have one queue of runnable threads per priority level (so I have 32 queues). All the scheduler does is:

1. Put the current thread at the back of its queue
2. Look for the first non-empty queue
3. Remove the thread from the front and make it the current thread

So the scheduler is O(1); that is, it takes the same length of time to choose a thread regardless of how many threads are ready to run.

A thread is made ready to run when:

• It is unsuspended (e.g. after it is created)
• It finishes waiting on some object

The finish-waiting scenario most often happens when some device I/O completes (e.g. a thread is reading from a file, and the FS driver signals the event it is waiting on) or when some inter-thread synchronization takes place (e.g. another thread releases a resource that this thread wants to access). This seems to cater for pretty much anything.

I have a limited starvation-avoidance mechanism put in there: every time a thread's quantum expires, its priority gets decremented. So if you have a priority 20 thread and a priority 15 thread, each of which is ready to run, the priority 15 thread will get scheduled after the priority 20 thread has had 5 quanta expired. When this happens, the priority 20 thread gets its priority reset, so it will probably be scheduled after the priority 15 thread has had one quantum expire.

Let me repeat this, because I think it's important, and often overlooked:
Pre-emption hardly ever happens on the timer interrupt. In practice, tasks use co-operative multitasking without realising. Every time a task blocks on something, it's giving up the CPU to some other task. Timer-based multitasking (where a task is pre-empted when its quantum expires) is only to stop a thread that never blocks from taking over the CPU.

[distantvoices]

You say it in right words. most time a task is waiting for input, the hard disk (e.g. the file system notifying him that the requested file is available) - simply it blocks waiting for something. - It is always a mix of co-operative and pre-emptive multitasking.

I consider it important too to have the driver tasks give cpu up under all circumstances: They fetch a message from their post box, execute it, then fetch another one (if there is one) or, if the postbox is empty, block, waiting for a message(from isr or task).

The most important thing I think is to have driver tasks or system threads - e.g. mouse driver, keyboard driver ... execute as soon as they become runnable - moved from blocked queue to their runnable queue. This one f. ex. I call realtime_processes. It is a non scheduled queue, say, the current thread runs until it SUSPENDS. Due to this form of execution, driver tasks or system threads have to execute quickly, come to the end and there comes the next one. Only after this queue is empty, processes from the round robin queue are considered for the cpu. It's nothing high sophisticated, I am just learning to walk *gg*.

stay safe

[Pype.Clicker]

hmm ... what exactly are your process preferences ? you clearly always execute the process with the highest preference, but is your "weighted" algorithm supposed to give twice the CPU time X gets to Y if the weight of Y is twice the one of X ?

Let's say the total of weights in your system is S = Wx + Wy + ...
Let's also say every process must pay 1 to execute on the cpu for one timeslot.

I would say than giving every process i a credit of Wi/S at each timesolt should give a good result:

initially X has $0 just as Y do, and the system is idle
<clock> : X gets $0.33, Y gets $0.66 the system remains idle
<clock> : X has $0.66, Y has $1.33 and buys one slot of CPU time
<clock> : X has $1.00 and buys one slot, Y has $1.00 too
<clock> : X now has $0.33, Y buys 1 and then has $0.66
we're back at the step 2.

thus the CPU will service [- - Y X Y Y X Y Y X ...]
if at step 3, Y was the one to buy CPU time, then at step 4 it
would have only $0.66 and cannot buy anymore while X has $1.33 and can afford one slot of CPU time

A process that keeps asleep for a long time will have a lot of cash and therefore is likely to get CPU as soon as it wakes up.
We could decide to have FIFO order for process that have the same amount of "money". We could also decide that a process could offer more than $1 for 1 slot CPU time, taking over on process that only can afford $1, giving the preference to the longest asleep process in case of multiple process that wake up simultaneously.

[distantvoices]

process_preference: something like the NICE-value of linux - to tell the scheduler, which processes to prefer. High preferred processes are more often given the cpu than less preferred ones.

if every process in the queue has the same process_preference value, it is handled in pure round_robin manner.

[Pype.Clicker]

then i think the "virtual currency" algorithm could be implemented. It must be very close to the "virtual time" of dynamic priorities algorithms, but i never really got what was the explaination of virtual time, so the "currency" approach was the most understandable technique i found to explain it ...
It's much close to "Weighted Fair Queueing" algorithm used in QoS router aswell ...