Help on multilevel Feedback queue Scheduling

[ashishkumar4]

With reference to the same on Wikipedia by MollenOS, I have implemented 'almost' most of the Multilevel Feedback queuing and it works as expected. I got 10 queues with highest queue getting smallest timeslice. The scheduler starts always from the top of the highest level queue and goes on searching and coming down until it gets a task in some queue. the the task is assigned the cpu and put at the last of the lower queue if it didn't completed in its timeslice. This is done until it reaches the last queue(base) where it just prempts in round robin fashion until its blocked for some io operation at which it jumps to higher queues thus getting immediate attention of the processor. A new task always arrives at the last of the highest queue and sinks down to the base then. This all works incredibly well with my new context switch algorithm which is less time consuming and simpler with less bugs.

Now the help I need is that as I said I have implemented MOST OF IT, I still haven't done much about this step in the algorithm:
"4.If the process voluntarily relinquishes control of the CPU, it leaves the queuing network, and when the process becomes ready again it is inserted at the tail of the same queue which it relinquished earlier."

I don't understand what it means? Please help me with it

Also in my algorithm, a separate timer keeps on incrementing a variable associated with every task in the BASE queue until it reaches a threshold upon which its put in a higher queue (which happens when the task was in lower priority for too long).
But here is a prob: I need atleast 2 independent timers (one for scheduler, one for this thing). I am currently on single processor systems, and had thought to use PIT as well as APIC separately. But my friend said, its not possible. Then what to do? Here are a few my ideas :generate 2 interrupts separately from a single timer at different points in time. But how? or some other solution?

Thanks

[~]

Now the help I need is that as I said I have implemented MOST OF IT, I still haven't done much about this step in the algorithm:
"4.If the process voluntarily relinquishes control of the CPU, it leaves the queuing network, and when the process becomes ready again it is inserted at the tail of the same queue which it relinquished earlier."

I don't understand what it means? Please help me with it

The following is a general idea of how to implement this algorithm, it's a very flexible consideration and managing to implement it in a clean and stable way would require some rigurosity of the mathematical kind, maybe not numerically apart from paging, etc., but in the unambiguity of this multitasking system subcomponent.


It seems that it means that the process can be preempted (interrupted) by the CPU and put in a wait process queue to run another process/program. It also means that the process can interrupt itself by sending the OS a request to do so and then another process/program is started.

In the past, even Windows relied on the process to interrupt itself. If it didn't do that, it would be the only main process to run and all other open programs would freeze due to lack of cooperation to share the CPU time slices.

Now, in addition to a process' capability of voluntarily interrupt itself and pass control to the kernel and then to another existing process, we have the capability from the kernel to interrupt the process automatically after some time, typically determined by its priority level.

Here we are talking about having the process voluntarily signal that it's releasing the CPU control, and when it returns from the queue or group of idle processes, it is put by the algorithm at the end (the tail) of the process queue it was in from the several queues there are. Or it is just marked as "not running" when it releases the CPU, and then it is marked again as "running" and put at the end (or tail, probably implementing some sort of task or circular buffer approach) of the process queue or processes circular buffer from several of them (presumably for being able to have a tiny initial circular buffer and create further ones later as an expansion without reserving too much memory for process structures that will probably never run).

It could probably also be a good idea to have a private buffer for the multiple threads of a process, and being able to resize and/or shrink that buffer according to the threads that are created or destroyed. It could also be good to have nesting or a pointer to a child process/application if it's opened from the current program, for being able to track, close and manipulate other processeses, and for interprocess communication.

[Brendan]

Hi,

With reference to the same on Wikipedia by MollenOS, I have implemented 'almost' most of the Multilevel Feedback queuing and it works as expected. I got 10 queues with highest queue getting smallest timeslice. The scheduler starts always from the top of the highest level queue and goes on searching and coming down until it gets a task in some queue. the the task is assigned the cpu and put at the last of the lower queue if it didn't completed in its timeslice. This is done until it reaches the last queue(base) where it just prempts in round robin fashion until its blocked for some io operation at which it jumps to higher queues thus getting immediate attention of the processor. A new task always arrives at the last of the highest queue and sinks down to the base then. This all works incredibly well with my new context switch algorithm which is less time consuming and simpler with less bugs.

Now the help I need is that as I said I have implemented MOST OF IT, I still haven't done much about this step in the algorithm:
"4.If the process voluntarily relinquishes control of the CPU, it leaves the queuing network, and when the process becomes ready again it is inserted at the tail of the same queue which it relinquished earlier."

I don't understand what it means? Please help me with it

It means, if/when the process voluntarily gives up control of the CPU by doing "yield()" or "sleep(0)", or by blocking for any reason; it is removed from whichever queue it is on (so that the queue/s only contain threads that are read to run); and then inserted at the tail of that queue, either immediately (in the "yield()" or "sleep(0)" case) or much later on (when a blocked thread is unblocked again).

Also in my algorithm, a separate timer keeps on incrementing a variable associated with every task in the BASE queue until it reaches a threshold upon which its put in a higher queue (which happens when the task was in lower priority for too long).
But here is a prob: I need atleast 2 independent timers (one for scheduler, one for this thing). I am currently on single processor systems, and had thought to use PIT as well as APIC separately. But my friend said, its not possible. Then what to do? Here are a few my ideas :generate 2 interrupts separately from a single timer at different points in time. But how? or some other solution?

Imagine you have a single timer operating in "one shot" mode (note: "one shot mode" is very important for this, and most timers do provide it). If you set the timer to generate an IRQ for the shortest period you will get an IRQ when the shortest period expires, and you can set the timer to generate an IRQ for the "next shortest" period during the IRQ handler.

Now imagine you have a list of "timer events" where each "timer event" has a type and an expiry time; and where the list is kept sorted in chronological order of expiry. When the timer's IRQ occurs you can use the type of the soonest event to determine what to do for that IRQ, and then set the timer up for the "next shortest" period.

For a simple example:

Code: Select all

void timer_IRQ_handler(void) {
    switch(soonest.type) {
        case END_OF_TIME_SLICE:
            handle_end_of_time_slice();
            break;
        case WAKE_SLEEPING_TASKS:
            wake_sleeping_tasks();
            break;
        case INCREASE_PRIORITY_OF_TASKS_THAT_HAVE_BEEN_WAITING_TOO_LONG:
            increase_priority_of_tasks_that_have_been_waiting_too_long();
            break;
    }
    soonest = soonest->next;            // Get "next soonest"
    set_timer_expiry( soonest.time );
}

void handle_end_of_time_slice(void) {
    switch_tasks();
    create_new_timer_event(END_OF_TIME_SLICE, now() + TIME_SLICE_LENGTH );
}

void wake_sleeping_tasks(void) {
    while( (head_of_sleeping_task_list != NULL) && ( head_of_sleeping_task_list->wakeTime <= now() ) ) {
        unblock_task( head_of_sleeping_task_list->taskID );
        head_of_sleeping_task_list = head_of_sleeping_task_list->next;
    }
    if( head_of_sleeping_task_list != NULL) {
        create_new_timer_event(WAKE_SLEEPING_TASKS, head_of_sleeping_task_list->wakeTime );
    }
}

void increase_priority_of_tasks_that_have_been_waiting_too_long(void) {
    for something {
        do stuff;
    }
    create_new_timer_event(INCREASE_PRIORITY_OF_TASKS_THAT_HAVE_BEEN_WAITING_TOO_LONG, now() + whatever );
}

Essentially, you only need one timer for the entire computer, and that single timer can be used for an "unlimited" number of things (scheduler time slices, networking time-outs, "sleep()" and/or "nanodelay()", etc). Of course "need" isn't the same as "want"; and for performance/scalability you really want one timer per CPU.


Cheers,

Brendan

[~]

I have create a recording for the previous code snippet so it is easier to follow and for trying to see better the logical dependencies that are interwined in the code. Writing it with a minimum of thinking took 11 minutes, so we can see that this topic (task scheduling) will require equally meditation and taking time to really understand:

timer_tasks_snippet__0000.html


The most important part of the previous post was the fact to move the stopped processes immediately and taking them to a queue of suspended tasks (probably a counterpart queue for the queue it belongs to).

It must also be remembered to stop all threads, mark them as stopped and move them in block for multithreading.

[ashishkumar4]

that html link dosent seems to works. any ways Thanks Brenden and Unnamed for helping. I have made such a thing called taskSleep() which just makes the task 'sleep' from which it was invoked, indefinitely until some I/o operation for it arrives. Like for example, I do this:
My func()
{
print some thing.
lock the keyboard input (MUTEX and iolock (a thing I made) )
sleep()
///**** from here the task ends for indefinite time, and other tasks are processed as the task gots removed from the queue***///
getline(something)
print it
}

as soon as I press a key, the interrupt Manager (for keyboard for example) puts the task which locked it to highest priority so as the task gets executed Immediately. Thus a Task like GUI app or something of high priority is removed from the queue until input arrives from the user if it required it, and wakes up almost instantly after the interrupt handling of the input interrupt (int 1 for keyboard, which writes to an input buffer)

Is everything right? it seems to work fine on qemu because :/
Thanks

[~]

timer_tasks_snippet__0000.html

that html link dosent seems to works. any ways Thanks Brenden and Unnamed for helping.

You just need to click or middle-click the link (to open in a new window) and press the Play button you see, and watch how the code was written as if it was a text-based movie for the source code. It is hosted on the Archive.org website so it should not be down.

I have made such a thing called taskSleep() which just makes the task 'sleep' from which it was invoked, indefinitely until some I/o operation for it arrives. Like for example, I do this:
My func()
{
print some thing.
lock the keyboard input (MUTEX and iolock (a thing I made) )
sleep()
///**** from here the task ends for indefinite time, and other tasks are processed as the task gots removed from the queue***///
getline(something)
print it
}

as soon as I press a key, the interrupt Manager (for keyboard for example) puts the task which locked it to highest priority so as the task gets executed Immediately. Thus a Task like GUI app or something of high priority is removed from the queue until input arrives from the user if it required it, and wakes up almost instantly after the interrupt handling of the input interrupt (int 1 for keyboard, which writes to an input buffer)

Is everything right? it seems to work fine on qemu because :/
Thanks

There are several ways to decide to which application to send the data and you should consider them. One is to send user events to the process to which window or text console (in case of pure text-mode windows) is focused and is in the foreground at the top of the stack of windows on screen.

The other is send them to the process that requested data.

The other is have the kernel send data or messages to an application for some reason.

The other is that an application queries the kernel for the list of existing processes and have it select a process ID and a handle for inter-process communication.

In each case, you must know who sends the data (another application, kernel, which device, scheduler, subsystem, etc...) and by which process it must be received.

You could have a message queue for the process and a protocol and an implementation criteria of how to send the messages. Usually for the keyboard, the messages go to the currently selected text console, and for the mouse they go to the application the mouse is moving over taking into account the 2D window or object area. For task scheduling you could reserve more CPU time slices to the currently selected window or console and also for background processes that have higher priority than the others. For devices you would have interrupts and DMA signal completion or requests to give or receive more data. You could accompany every command with a structure that indicates the ID of the process and the thread that initiated it so that you know where to send/receive the data (which application) and also whether to wake it and which one.

So you should have different input/output buffers depending on the services and APIs each application uses. The default buffers would be for keyboard, mouse, disk and network data, as well as some form of structure for storing or sending data from/to multimedia devices, and of course a virtual screen or a handle to the raw video memory. You would need to have all those structures for each process.

[ashishkumar4]

Yeah, thanks. Will see to it but after my final board exams.