Task scheduler infinite loop

[ManyGifts]

Hi, I need your help about my task scheduler

I have main and 2 extra tasks in my kernel - task0 (main), task1, task2.

I use IRQ0 interrupt from timer to switch tasks and my problem is about task switching.

I need task1 and task2 to be tasks with infinite loop inside - so i can't use iretd instruction to back and then restore eip register.

So it looks like that:

Code: Select all

task1:
task1loop:
;the appropriate code of task1 here
jmp task1loop

task2:
task1loop:
;the appropriate code of task1 here
jmp task1loop

And task scheduler, which is based on timer (40Hz), look like that (i removed extra code for sake of simplicity that waits for ticks etc...):

Code: Select all

irq0_interrupt_service:

call 0x30:0x0 ; call task1, selector is 0x30
call 0x38:0x0 ; call task2, selector is 0x38

;send eoi signal (end of interrupt)
mov al, 0x20
out 0x20, al
iretd

And as you may imagine because of task1 loop it won't leave task1 and no EOI signal will be sent and no IRETD instruction executed and task2 won't be also executed.

PIC is configured properly and it's working fine. My problem (in my option) is wrong task switching.
What are other ways to do it ?

Thank you

[BMW]

http://wiki.osdev.org/Multitasking_Systems
http://wiki.osdev.org/User:Mariuszp/Scheduler_Tutorial

[thepowersgang]

1. You're using segmentation in pmode, don't.
2. Task switching shouldn't be bound to the timer. Instead, write a generic 'reschedule' function that can be called by anything (say, in the idle loop of a task) and then once you get all that working, add a timer hook to force a switch if a task is taking too long.

[ManyGifts]

1. You're using segmentation in pmode, don't.

Why ? You mean there is better to use flat memory model like windows/linux other thank tiny memory model (with segmentation) ? It's my first kernel I am learning, soon I am going to write kernel with flat memory model too.

1. You're using segmentation in pmode, don't.
2. Task switching shouldn't be bound to the timer. Instead, write a generic 'reschedule' function that can be called by anything (say, in the idle loop of a task) and then once you get all that working, add a timer hook to force a switch if a task is taking too long.

Can you explain it more specially ?

What "generic reschedule function" would do ? Well it sounds crazy to allow task with user privilege to manipulate task scheduler.

And what do you mean by time hook ? Interrupt IRQ0 is that time hook ?

Please more details, because I didn't understand it, thank you.

[iansjack]

1. You're using segmentation in pmode, don't.
2. Task switching shouldn't be bound to the timer. Instead, write a generic 'reschedule' function that can be called by anything (say, in the idle loop of a task) and then once you get all that working, add a timer hook to force a switch if a task is taking too long.

That sounds rather prescriptive. I think you should at least explain your statements. And many would disagree with 2.

[thepowersgang]

(Sorry, I was kinda churning through what I saw as simple posts during my lunch break)

First off, segmentation in protected mode is just messy. It is unsupported by most modern compilers, so restricts you to assembly code or evil hacks.

As for task switching, my point was that you should separate the concept of pre-emption (interrupting a task and running another due to some event, typically used to refer to its timeslice expiring) and re-scheduling (suspending a task and letting another run).

The biggest reason for this is because modern systems are very IO driven (even in control situations, you're usually waiting for something to happen, not crunching numbers). If an IO-based thread had to wait to be pre-empted before another thread can run (a thread that it may be waiting on), there would be quite a bit of wasted CPU time, and substantially more lag in input.

Quick anecdote with regards to this - My ARM port runs almost perfectly (with GUI working) with no timer-based pre-emption, everything works cooperatively (of course, you'd want to add a preemption system eventually, just to stop runaway processes from stopping the system).

[Kevin]

To answer the original question: If you really want to use hardware task switching, you need to be sure that you leave the task and get the register state written back to the TSS before you schedule the next task. The way to achieve this might be to have a separate task for the kernel and use task gates for your interrupts.

That said, I would consider this advanced stuff. Doing software task switching is much easier (and unlinke hardware task switching, almost everyone around here knows exactly what the code for it has to look like and can help you with it).

[iansjack]

If an IO-based thread had to wait to be pre-empted before another thread can run (a thread that it may be waiting on), there would be quite a bit of wasted CPU time, and substantially more lag in input.

Does any sane OS implement task switching based only on a timer? All the ones that I know will switch tasks immediately the current one blocks. Why on earth would you not implement that?

[bwat]

Quick anecdote with regards to this - My ARM port runs almost perfectly (with GUI working) with no timer-based pre-emption, everything works cooperatively (of course, you'd want to add a preemption system eventually, just to stop runaway processes from stopping the system).

Timer base preemption* wont guarantee the prevention of runaway processes stopping the system. Feedback based priorities which dynamically lower the priority of the running process based upon running time, and dynamically raise the priority of starved processes, would help.

I personally am not a fan of process quanta. I don't build multi-user systems so defining a fair scheduler is not that useful to me either (I think this is what you're saying). In fact it's just wasting processor cycles. I usually stick I/O bound processes (device driver processes) at priorities higher than application processes (most of which have the same priority). Very long sequences of CPU bound processing can be broken up with yields. Even then I often find that unnecessary. That's just me.


*) I assume this means timesharing with processes each having a scheduling quantum, and doesn't include periodic scheduling of tasks or sleep calls

[thomasloven]

Switching tasks when a process blocks helps in order to avoid bussy waiting and wasting processor time.
However, the best scheduling algorithm in the world won't help against a runaway process if the algorithm doesn't get to run. That's why you _also_ want timer based scheduling (a.k.a. preemption).

[bwat]

I don't think you've fully understood the terms you've used.

Switching tasks when a process blocks helps in order to avoid bussy waiting

No. Switching tasks has nothing to do with avoiding busy waiting.
Busy waiting is when you continuously poll for a change in state. If the process blocks then it performs no work. The process cannot by definition be busy when blocked. So, it is the blocking and not the task switching which avoids busy waiting.

and wasting processor time

Yes, the switching of tasks can keep processor busy doing other things. This part is true.

timer based scheduling (a.k.a. preemption).

No, it's not. Preemption is stopping one process/thread/job/task and starting another. Your timer based scheduler might use preemption but it most definately not correctly "also known as preemption." You'll find plenty of systems that use preemption and have no timer based scheduling (whatever that means).
Some definitions of preemption:

The operation of suspending the running task and inserting it into the ready queue is called preemption.
--- Hard Real-time Computing Systems, Buttazzo.


Preemption of a job or operation means that processing may be interrupted and resumed at a later time, even on another machine. A job may be interrupted several times.
--- Scheduling Algorithms, Brucker.


The strategy of allowing processes that are logically runnable to be temporarily suspended is called preemptive scheduling, and is in contrast to the run to completion method of early batch systems.
--- Modern Operating Systems, Tanenbaum.

[Brendan]

Hi,

Code: Select all

irq0_interrupt_service:

call 0x30:0x0 ; call task1, selector is 0x30
call 0x38:0x0 ; call task2, selector is 0x38

;send eoi signal (end of interrupt)
mov al, 0x20
out 0x20, al
iretd

For hardware task switching, only ever use "call far" when you expect the other task switch tasks back (with "retf"). You need to use "jmp far" because you don't expect the other task to switch back.

You also need to send the EOI *before* you do a task switch, because after the task there's no way to guess what the CPU will be doing.

The IRQ handler needs to choose one task to jump to (you can't just jump to all tasks in the same IRQ).

Finally, if you modify any register in an IRQ handler then you *must* save it and then restore it after. You're using AL but not saving it or restoring it.

For a rough example of all this:

Code: Select all

    section .data
currentTSSfarPointer:
    dd 0                           ;Note: CPU ignores the "offset" part, so there's not much point having it..
currentTSS:
    dw 0x38
    section .text


;Note: IRQ0 *must* be an "interrupt gate" (and can not be a "trap gate")

irq0_interrupt_service:
    push eax

    ;send eoi signal (end of interrupt)
    mov al, 0x20
    out 0x20, al    

    add word [currentTSS],8        ;Get next TSS to switch to
    cmp word [currentTSS],0x38     ;Is it too high?
    jbe .l1                        ; no
    mov word [currentTSS],0x30     ; yes, wrap around to first TSS
.l1:
    jmp far [currentTSSfarPointer] ;WARNING: Task switch and not a JMP (execution continues after the jump)

    pop eax
    iretd

Of course thepowersgang is right - this should be broken up into 3 pieces (IRQ0 handler, a "reschedule", and a "goto task"). For example:

Code: Select all

    section .data
currentTSSfarPointer:
    dd 0                           ;Note: CPU ignores the "offset" part, so there's not much point having it..
currentTSS:
    dw 0x38
    section .text


;Note: IRQ0 *must* be an "interrupt gate" (and can not be a "trap gate")

irq0_interrupt_service:
    push eax

    ;send eoi signal (end of interrupt)
    mov al, 0x20
    out 0x20, al    

    call reschedule

    pop eax
    iretd


;Find task to run and switch to it

reschedule:
    push eax
    movzx eax,[currentTSS]
    add eax,,8                     ;eax = next TSS to switch to
    cmp eax,0x38                   ;Is it too high?
    jbe .l1                        ; no
    mov eax,0x30                   ; yes, wrap around to first TSS
    call gotoTask
    pop eax
    ret


;Switch to a specific task
;
;Input
; ax = TSS for task to switch to

gotoTask:
    cmp [currentTSS],ax             ;Is this task currently running?
    je .done                        ; yes, do *not* attempt to switch (will cause GPF)

    mov [currentTSS],ax
    jmp far [currentTSSfarPointer] ;WARNING: Task switch and not a JMP (execution continues after the jump)

.done:
    ret

Eventually "reschedule" will become something more sane (e.g. maybe using queues or something to choose which task to switch to (instead of doing a "2 hard-coded tasks" thing). Also (later) if a task blocks you can just call "reschedule" without waiting for the timer, and if the currently running task is preempted (e.g. a higher priority task is restarted) you can call "gotoTask" directly to avoid any unnecessary overhead (as you know which task to switch to already in those cases).


Cheers,

Brendan

[ManyGifts]

To answer the original question: If you really want to use hardware task switching, you need to be sure that you leave the task and get the register state written back to the TSS before you schedule the next task. The way to achieve this might be to have a separate task for the kernel and use task gates for your interrupts.

That said, I would consider this advanced stuff. Doing software task switching is much easier (and unlinke hardware task switching, almost everyone around here knows exactly what the code for it has to look like and can help you with it).

Yes, I would like to use hardware task switching as it's my first kernel. After I get known it better I'd like to create more advanced one.

What do you mean by be sure to leave task ? You mean to use iretd instruction inside task and in irq0 after task is done set eip of task for begin ?

[Combuster]

Yes, I would like to use hardware task switching as it's my first kernel.

It's exactly the opposite: you do not want hardware task switching for reasons of simplicity.

[Kevin]

Yes, I would like to use hardware task switching as it's my first kernel. After I get known it better I'd like to create more advanced one.

Hardware task switching is the one that needs more advanced knowledge. Software task switching is the easy one (and in the common case, the better one, too).