multitasking and scheduling ?

[Sam111]

I am wondering about few things

1) say I have a few TSS segments in the gdt . I can use ltr or str to switch/save tasks.
say I have a schedular algorithm (could be round robin ,First In First Out,Priority based scheduling, and many others...etc etc)
When I am in a particular task and have the schedular load a program and execute it.

I am wondering how I can get the control back from the program I have handed the control off to.
For example my loader program/schedular program can take an exe and load it into memory and jmp to the start address for that program.

But once the program that I loaded has control how can I get control back every 40ms or so.

The only thing I can think of is with an interrupt (Either the RTC or the PITS interrupt )
Are those the only ways to interrupt a running process / task to allow/beable to switch tasks or is their other ways ?


2) If I use the PITS or RTC then I am worried about a stack overflow.
Since every time an interrupt is called it pushes the eflags , cs , return address so every 40ms or so the stack would keep growing with no return/iret.

My problem is not in setting up a TSS segment in the GTD or loading/saving/switching a task (controlled by the tr register )
My problem is once the schedular I choose loads a program and hands control off how to get control back from the program that has control.

Thank you for any help with is.

More interested in Preemptive Multitasking instead of tasks that have to execute and finish first before another task an execute

[bluemoon]

The only thing I can think of is with an interrupt (Either the RTC or the PITS interrupt )
Are those the only ways to interrupt a running process / task to allow/be able to switch tasks or is their other ways ?

You have been told that a hundred times, but in case you forgot that I should tell you again:
Check the wiki Multitasking_Systems

There are concept of Cooperative Multitasking and Preemptive Multitasking, which you can do at the same time.
You can preemptive on timer interrupt, and also let the application "Cooperatively" give up cpu time upon blocking or syscall.
You as the OS designer have all the flexibility, use your imagination.

2) If I use the PITS or RTC then I am worried about a stack overflow.
Since every time an interrupt is called it pushes the eflags , cs , return address so every 40ms or so the stack would keep growing with no return/iret.

The easiest way is to have separated kernel stack per process, so the stack will go back upon process resume.
It's a bit more complicated for single kernel stack per processor.

My problem is not in setting up a TSS segment in the GTD or loading/saving/switching a task (controlled by the tr register )
My problem is once the schedular I choose loads a program and hands control off how to get control back from the program that has control.

Does your first question answered it yourself?

[Sam111]

All, I wanted to know is if you must use the RTC or PITS interrupt to switch tasks.
(i.e are those the only ways you can get control back from a program you loaded and allow yourself to switch to run another program)

From your link

Now, the OS has set up a timer interrupt, which causes the OS call a specific interrupt service routine at regular interval. When the timeslot for the current program runs out, the routine will save the current CPU context into a datastructure, select a new program to be run for the next timeslot, and load the CPU registers with the values that were saved in that process's datastructure.

If you still want to figure out, imagine a machine with an accumulator and a stack pointer. You can save the machine state, switch and restore another machine state with

It seems the RTC or PITS are the only ways by the quotes.
Just was wondering if anybody new if their was different ways to get control back to the schedular and if so how they did it. (i.e non-interrupt based ways... or if the only way to have multitask in an OS is thru an IRS/IRQ)

I am still stuck on if I create / enable the PITS interrupt to be triggered every 40ms or so won't every 40ms I get things being pushed on some stack. Regardless of what stack it is it will keep building up an eventually exceed my stack limits.

In the PITS I can call back my schedular function to switch tasks or I could do it right in the PITS interrupt function.
Either way I would just be switching to a different TSS , saving previous tasking registers/state , loading a new TSS with its registers/state, and jmp to the next program or where the program left off.

The schedular is just the way it prioritizes what to execute , and the PITS that allows me to switch the context and tasks/programming being executed. Correct me if I am wrong.


I just had a thought
When a PITS interrupt is triggered should I turn off interrupts to allow me only to work in the PITS interrupt function and after done reenable them sti.
And should ever call back the schedular function I see maybe all the PITS function should do is switch TSS stuff and save states. Then return back to the schedular which then loads the new program... maybe I am wrong

The PITS interrupt and the schedular are a bit confusing on what goes where....they seem one in the same.
My problem when do I call iret if the PITS interrupt goes back to call the schedular ...

Unless the flow should be PITS interrupt is triggered every 40ms --> goes to the PITS interrupt function first turning off (cli) interrupts ---> then saving task TSS stuff ---> then iret back to the schedular function ---> the schedular function loads the next priority program and executes where it left off. (may be that is the way it goes)

My problem is not in understanding the instructions or how to do something with code it is in the flow of how a context switch/task switch should go interms of the PITS , and other things.
Curious to know all available ways of going about it before I choose the best fit for my OS.

[Brendan]

Hi,

1) say I have a few TSS segments in the gdt . I can use ltr or str to switch/save tasks.

LTR only tells the CPU where the current (hardware) task's data is, and STR only stores a reference to where the current (hardware) task's data is. They do not save and load the current task's data and aren't useful for task switching. Normally (for hardware task switching) you'd do LTR once during boot, and task switching is done with JMP, CALL and interrupts.

However, nobody uses the hardware task switching any more - it's slower, and it's easier (and faster and more portable) to do the task switching in software.

But once the program that I loaded has control how can I get control back every 40ms or so.

The only thing I can think of is with an interrupt (Either the RTC or the PITS interrupt )
Are those the only ways to interrupt a running process / task to allow/beable to switch tasks or is their other ways ?

There's 3 ways. Any IRQ (not necessarily a timer IRQ) interrupting the program, the program causing an exception (which may or may not mean the program crashed), or the program explicitly calling the kernel's API.

2) If I use the PITS or RTC then I am worried about a stack overflow.
Since every time an interrupt is called it pushes the eflags , cs , return address so every 40ms or so the stack would keep growing with no return/iret.

Normally the timer IRQ occurs, stuff happens, then the kernel returns from the IRQ; and the stack doesn't keep growing because you're returning properly.

The "stuff happens" part can include switching to a different task and doing lots of things before eventually switching back to the original task. Even in this case, eventually the original task still returns via. iret and the original task's stack doesn't keep growing because you're still returning properly.


Cheers,

Brendan

[Sam111]

Brendan,

You made me think of something.

1)

There's 3 ways. Any IRQ (not necessarily a timer IRQ) interrupting the program, the program causing an exception (which may or may not mean the program crashed), or the program explicitly calling the kernel's API.

Ok, but in theory you must use a type of interrupt weather it be an exception , kernel call , ...etc
(i.e correct me if I am wrong you cann't do context switching/mulitasking if the interrupts where disabled with cli and never enabled )
(when I say mulitasking I mean not having to wait for one program to completely complete before the next task can be executed/run.)

2) How else can you get regular controlled 40ms interrupts without the PITS or RTC. Or a timer based interrupt?
(If you do it thru the software interrupts every 40ms I cann't see it being very multitasking since you would have to wait for control to come back to the function that triggered the interrupt )

3)

Normally the timer IRQ occurs, stuff happens, then the kernel returns from the IRQ; and the stack doesn't keep growing because you're returning properly.

The "stuff happens" part can include switching to a different task and doing lots of things before eventually switching back to the original task. Even in this case, eventually the original task still returns via. iret and the original task's stack doesn't keep growing because you're still returning properly.

Ok from this I am think I must have to do an iret once the PITS interrupt is finished and not just call the schedular function from the PITS.
Since if I did that then I would have a stack that keeps growing with no iret. (Correct me if I was wrong I think this is my failure in seeing that the stack would keep growing. Correct me if I am wrong when a PITS interrupt is called I should cli (so no other interrupts are called) do the PITS function code then sti them back on and iret back to the schedular function.

4)
If the above is how it works then I am curious how much goes into the PITS interrupt function and how much task switching stuff should go into the schedular routine function. Should the PITS only set some global variables that the schedular uses to switch tasks and have the schedular do all the other work. Or should the PITS function be responsible for actually saving a Tasks data and have the schedular be responsible for only scheduleing/prioritizing/loading the next task. I guess it is totally up to the designer but was curious typically how major os's do it (like windows,linux,mac,..etc).

[bluemoon]

Ok, but in theory you must use a type of interrupt weather it be an exception , kernel call , ...etc
(i.e correct me if I am wrong you cann't do context switching/mulitasking if the interrupts where disabled with cli and never enabled )

Yes, to interrupt execution of a program you basically need, umm, an interrupt.

2) How else can you get regular controlled 40ms interrupts without the PITS or RTC. Or a timer based interrupt.

You get regular interrupt by the timer, and non-regular interrupts by things like disk I/O completion, network event, keyboard/mouse event, IPI, signals from other process, etc.
All these may be considered to wake up waiting processes.

3)

If the above is how it works then I am curious how much goes into the PITS interrupt function and how much task switching stuff should go into the schedular routine function. Should the PITS only set some global variables that the schedular uses to switch tasks and have the schedular do all the other work. Or should the PITS function be responsible for actually saving a Tasks data and have the schedular be responsible for only scheduleing/prioritizing/loading the next task. I guess it is totally up to the designer but was curious typically how major os's do it (like windows,linux,mac,..etc).

Modern OS is far more complex than PIT (no S) and scheduler.
Linux and Darwin are open source, you may dig into their code to see what happens, however I guess very few people has access to windows code to confirm how actually happened in the mess.

IMO a well planed design separate PIT and scheduler and the actual "context switching". PIT may signal the scheduler, the scheduler then acknowledge a process is over time and do context switching and/or do some load balancing.

[Sam111]

You get regular interrupt by the timer, and non-regular interrupts by things like disk I/O completion, network event, keyboard/mouse event, IPI, signals from other process, etc.
All these may be considered to wake up waiting processes.

Yes , but what I was trying to get at is is the only interrupts that you can use for tasking/switching or regular timed interrupts the RTC or PITS?
Because if that was true then the answer is You must use the PITS or RTC to have timed interrupts for task switching/mulitask switching. regardless of what type of schedular you implement (i.e round robin , priority ,...etc)

The only other thing I currently was curious about is how much logic I should put into the PITS interrupt function and how much in the actual schedular function. Should I just use the PITS function as away to set a global variable or structure that the schedular uses to determine what task is next to load in priority , should I disable interrupts temporarially when the PITS interrupt is being called or should I allow other interrupts to beable to still be called even if I am in the PITS function... (i.e like a hardware or keyboard interrupt )
Seems to me I would want to handle the PITS function completely before I enable interrupts again.
Is their any benifit in using the RTC over the PITS or visa-versa?

I have read that a good common switch time should be around 20ms to 40ms. But in theory you can reprogram the PITS or RTC interrupt to be triggered variablely ... (i.e keep reprogramming it based on the way programs are executed along with schedular priority )
Curious to know if anybody has done anything with this and if it would benfit or if the overhead of reprogramming every so often would outway the benifit???
Guess it would depend on how many times you reprogrammed it and the time between reprogramming it.


Anyway I think I got the main idea on how to go about this now.
Curious if people could post in short how their multitasking/schedular functionality works in their OS. (provided they have one)
Curious to know how different people went about it in different ways

[AJ]

Yes , but what I was trying to get at is is the only interrupts that you can use for tasking/switching or regular timed interrupts the RTC or PITS?
Because if that was true then the answer is You must use the PITS or RTC to have timed interrupts for task switching/mulitask switching. regardless of what type of schedular you implement (i.e round robin , priority ,...etc)

You can use anything that generates a timed interrupt. This includes the LAPIC timer, which gives you one interrupt source per core.

I think there are some basics you need to research before you worry about optimising your scheduler functions too much.

Cheers,
Adam

[Sam111]

I am on a old 32bit machine
so I don't think LAPIC timer applies I think I only have the PITS , and RTC to work with here.

But maybe I have other options it is a dell dimension 4600 so if you know of another way curious to hear it.
Think it is PIC 8259A (the most popular one) though I think it has APIC chip features I believe as well.

But their is no multiprocessors or dual cores ,...etc stuff on this old computer so SMP doesn't apply.
The process or is an old pentium 4. So only single core uni-processor (one processor).

essentially I am limited to what I can program the interrupt PIC or APIC based controller to do a timed interrupt down. regardless of if I can switch it to do it on a different pin or IRQ line
so essentially what would be the benifit of useing something other then the standard RTC or PITS.. I don't think access time in a interrupt table entry would contribute to an interrupt latency but maybe I am wrong ( I do know some of them have greater priorities in the table )

[Solar]

Are you really basing the design of your OS on your current (already outdated) hardware?

[OSwhatever]

You can use anything that generates a timed interrupt. This includes the LAPIC timer, which gives you one interrupt source per core.

I think there are some basics you need to research before you worry about optimising your scheduler functions too much.

Cheers,
Adam

Yes, any timer with a free running counter (used as reference time) and a timer that can assert an interrupt after a desired timeout will do. Regardless if it HPET or old legacy hardware.

Mind you, you can get really far by not having preemption. A vast minority of task switches are due to preemption because your process or thread runs out of time slice. If you're early in your project, implement the scheduler first without worry about preemption. Also don't go into the trap designing your system requiring jiffies, which means that there is a OS tick that is updated every xx ms or so. Many are abandoning that and just setup a timer interrupt when the time slice expires.

[Brendan]

I am on a old 32bit machine
so I don't think LAPIC timer applies I think I only have the PITS , and RTC to work with here.

According to the specifications, this is a Pentium 4 with hyper-threading, and therefore definately does have local APICs (and local APIC timers). The Intel 865G chipset also has HPET, which is far better than PIT.

You also don't actually need to use a timer, even for "non-cooperative scheduling". It's possible to use (for example) the performance monitoring interrupt instead, to allow each task to execute for "N instructions" before it is pre-empted. There are reasons (involving power management and its interaction with modern variable speed CPUs) why this approach is superior (fairer) than using a timer; and it's also likely to be far more precise.

But their is no multiprocessors or dual cores ,...etc stuff on this old computer so SMP doesn't apply.
The process or is an old pentium 4. So only single core uni-processor (one processor).

As far as I can tell, it's single-core with hyper-threading. Hyper-threading makes one core look like 2 logical CPUs (which helps to keep the core's "otherwise idle" execution units busy, especially when one logical CPU has to wait for cache misses, etc).

However, hyper-threading in Pentium 4 wasn't as good as it is more recent CPUs (and software was worse back then); so some software (especially badly designed software running on an OS that isn't optimised for hyper-threading) can run slower than it would with hyper-threading disabled. For good software you can expect up to about 15% performance improvement by using hyper-threading (by supporting SMP) on your Pentium 4.

Basically, SMP does apply (although you may need to enable it in the BIOS); and even though you're not going to get 100% performance improvement it's still worth doing because it'll mean you can upgrade your computer (e.g. to a quad-core) some time in the next 10 years without rewriting half your OS to use SMP.

There's 3 ways. Any IRQ (not necessarily a timer IRQ) interrupting the program, the program causing an exception (which may or may not mean the program crashed), or the program explicitly calling the kernel's API.

Ok, but in theory you must use a type of interrupt weather it be an exception , kernel call , ...etc
(i.e correct me if I am wrong you cann't do context switching/mulitasking if the interrupts where disabled with cli and never enabled )
(when I say mulitasking I mean not having to wait for one program to completely complete before the next task can be executed/run.)

The kernel API can use a call gate, SYSENTER or SYSCALL. None of these are a type of interrupt, and all of them are faster than a software interrupt. Note: Your Pentium 4 probably doesn't support SYSCALL, but will support call gates and SYSENTER).

Disabling interrupts (e.g. with "CLI") will not prevent software from using software interrupts, call gates, SYSENTER or SYSCALL, and doesn't prevent software from generating exceptions. It only effects IRQs.

Correct me if I am wrong when a PITS interrupt is called I should cli (so no other interrupts are called) do the PITS function code then sti them back on and iret back to the schedular function.

When an interrupt occurs the CPU looks at the "Interrupt Descriptor Table" to figure out what to do. For interrupts, there's 3 types of descriptors that can be in the IDT - "interrupt gate" (which automatically disables IRQs for you), "trap gate" (which doesn't disable IRQs for you) and "task gates" (which is part of hardware task switching and not something most people bother with).

The normal approach is to use an "interrupt gate" for the timer IRQ, so that the CPU automatically disables IRQs for you (and you don't need to do "CLI" yourself). Some people would begin the IRQ handler by setting some sort of "don't pre-empt me" flag, then enabling IRQs for the remainder of the interrupt handler to ensure that more important IRQs aren't postponed. Basically, you should never need to use "CLI" to disable IRQs in an interrupt handler, but you may want to use "STI" to enable IRQs in an interrupt handler.

If the above is how it works then I am curious how much goes into the PITS interrupt function and how much task switching stuff should go into the schedular routine function. Should the PITS only set some global variables that the schedular uses to switch tasks and have the schedular do all the other work. Or should the PITS function be responsible for actually saving a Tasks data and have the schedular be responsible for only scheduleing/prioritizing/loading the next task. I guess it is totally up to the designer but was curious typically how major os's do it (like windows,linux,mac,..etc).

Your scheduler should have a low level "goto_task(task_id)" function, which does a task switch from the currently running task to a different (explicitly requested) task. You scheduler should also have a "do_task_switch(void)" function that determines which task to switch to and then calls the "goto_task(task_id)" function. The timer interrupt handler should only call the scheduler's "do_task_switch(void)" function.

Note: Different tasks block for different reasons (e.g. waiting for disk IO, called "sleep()", etc). When a task blocks for any reason, the kernel needs to find another task to run. Therefore the scheduler's "do_task_switch(void)" function would be called by lots of different parts of the kernel (not just the timer IRQ). When a task unblocks (e.g. it was waiting for disk IO and the disk IO was completed, or it called "sleep()" a while ago and needs to wake up now) the task can be given CPU time again. If the task that was unblocked is a higher priority than the currently running task, then you probably want the unblocked task to pre-empt the currently running task. In this case the scheduler's "goto_task(task_id)" function would be used by any code in the kernel that causes tasks to unblock (e.g. "goto_task(the_higher_priority_task_that_I_just_unblocked)" and not just used by the scheduler's "do_task_switch(void)" function.


Cheers,

Brendan

[OSwhatever]

Your scheduler should have a low level "goto_task(task_id)" function, which does a task switch from the currently running task to a different (explicitly requested) task. You scheduler should also have a "do_task_switch(void)" function that determines which task to switch to and then calls the "goto_task(task_id)" function. The timer interrupt handler should only call the scheduler's "do_task_switch(void)" function.

When you are mentioning "task" here, is this a process or a thread?

[Brendan]

Hi,

Your scheduler should have a low level "goto_task(task_id)" function, which does a task switch from the currently running task to a different (explicitly requested) task. You scheduler should also have a "do_task_switch(void)" function that determines which task to switch to and then calls the "goto_task(task_id)" function. The timer interrupt handler should only call the scheduler's "do_task_switch(void)" function.

When you are mentioning "task" here, is this a process or a thread?

Yes.

I use "task" to mean process or thread or fibre or whatever else a scheduler might be scheduling..


Cheers,

Brendan

[Velko]

Your scheduler should have a low level "goto_task(task_id)" function, which does a task switch from the currently running task to a different (explicitly requested) task. You scheduler should also have a "do_task_switch(void)" function that determines which task to switch to and then calls the "goto_task(task_id)" function. The timer interrupt handler should only call the scheduler's "do_task_switch(void)" function.

Remembering how I got my head spinning, while trying to come up with implementation of something like that, I feel there's something to add.

goto_task(task_id) is actually an easy one. You just save current execution path (say - stack pointer), load a new one and off you go. It requires some thought what and where to be saved, and what will happen when you switch to new task. But nothing too complicated.

do_task_switch(void) IMHO is much tougher. You have to keep several code execution paths in head. First you have to ensure, you're not trying to switch (at least - not repeatedly) to currently executing thread. Then, imagine thread #1 switching to some other thread. What thread #1 should do, when it regains control? Then, what should happen when there's no more runnable threads and CPU should sleep. How scheduler will work after sleeping when some thread becomes runnable again? And I'm almost sure I forgot to mention several other essential things to consider. It's not that easy to come up with working solution.

I'm using slightly alternate approach: running scheduler in it's own in-kernel thread (actually - a thread per logical CPU). Scheduler itself runs a loop like this (pseudocode):

Code: Select all

for (;;) {
    while (have_runnable_tasks()) {
       task = pick_a_task();
       goto_task(task);
    }
    sleep();
}

do_task_switch(void) then essentialy becomes goto_task(SCHEDULER_THREAD_OF_CURRENT_CPU), jumping back into that loop.

There, all complexity removed