Interrupting the scheduler...

[Colonel Kernel]

I'm revisiting this and this. I'll try to make my question as brief as possible so as not to retread everything...

I don't want nested interrupts. However, I do want "kernel threads", which means that kernel entries can be nested at most two deep (e.g. -- user-thread makes syscall, transitioning to its kernel-mode stack. Resulting kernel-thread is interrupted by the clock, which could invoke the scheduler, preempting the kernel thread with a higher-priority user-thread). I want "kernel threads" so that long-running kernel operations can be preempted (is there a better way to do this...? I can't think of one...)

The question is this -- Assuming that interrupts are enabled while the scheduler is running (but before it does the final stack switch of course), how can I protect the scheduler from itself? Here are some possible answers -- please let me know how insane they are:

• Use the self-interrupt technique so that the scheduler can only be interrupted by handlers that by definition do not invoke the scheduler. Problem: This is complex to implement, and avoiding it is one of the main reasons I don't want nested h/w interrupts in the first place.
• Use a goofy global var like Minix' k_reenter. Problem: Icky.
• Disable any h/w interrupts that could invoke the scheduler. Problem: This is probably all of them, since interrupt handlers may want to wake up their corresponding driver threads.
• Just disable interrupts while the scheduler runs, stupid!

Perhaps I should have prefaced this question with another question -- does anyone leave interrupts enabled while the scheduler runs? The thing is, I think NT, Minix, and QNX do, but they probably all have the complex/icky mechanisms in place to deal with nested interrupts already. I'm looking for an easy way out when the nesting level is guaranteed to be <= 2.

Once I get this design decision out of my hair, maybe I can actually get something done.

[pini]

If I have correctly understood what your question is, I would say you could use a global variable to store if an interrupt is already running when you get a new one.
The Unix (BSD ?) systems' one is called "set_runrun" or something like that.

I'm planning to use a variable to store whether a interrupt started or not and maybe use it in a spinlock or whatever to avoid the scheduler to be run twice in a single call (is this sentence correct ? I don't know )
So, that's my solution : use a global variable, because it still allows your kernel to be preemptible and is not so difficult to deal with.

I don't think that disabling interrupts (either those that could run the scheduler or all insidethe scheduler itself) is a good idea, since you will lose responsivity (does this word exist ?) and your system will look very low. You could also be waiting for a interrupt at the end of one, and be waiting for another at the end of the second, and so on, and you won't return in user space for a while.

What technique are you all using for this ?

[Brendan]

Hi,

What technique are you all using for this ?

I have 2 different methods for locking re-entrancy locks (which are all spinlocks). The first method locks the re-entrancy lock and prevents thread switches, e.g.:

Code: Select all

%macro LOCK_THREADS 2
   inc dword [gs:CPULISTentryStruct.schedulerLocks]
%ifdef KERNSUPPORT_MP
   lock bts dword %1,%2               ;Try to acquire lock
   jnc %%locked                  ;Continue if lock acquired
%%wait:
   pause
   lock bts dword %1,%2               ;Try to acquire lock
   jc %%wait                  ;Keep trying if still locked
%%locked:
%endif
%endmacro


%macro UNLOCK_THREADS 2
%ifdef KERNSUPPORT_MP
   lock btr dword %1,%2               ;Unlock the lock
%endif
   pushfd
   cli
   sub dword [gs:CPULISTentryStruct.schedulerLocks],1
   ja %%l1
   cmp byte [gs:CPULISTentryStruct.switchThreadsFlag],0
   je %%l1
   mov byte [gs:CPULISTentryStruct.switchThreadsFlag],0
   call switchThreads
%%l1:   popfd
%endmacro

On MP computers this only stops the scheduler for the current CPU. The only reason this is done is to reduce the time between acquiring the lock and releasing it (ie. to prevent thread switches between acquiring and releasing the lock so that the lock is released faster, which reduces lock contention). By itself it does not make it safe to modify the scheduler's data structures (these have thier own locks which must be locked first). If any code attempts to switch threads when one or more locks have been acquired the thread switch will be delayed until all locks have been released.

The second type of lock does the same as the first but in addition prevents IRQ's from being handled:

Code: Select all

%macro LOCK_IRQS 2
   inc dword [gs:CPULISTentryStruct.schedulerLocks]
   inc dword [gs:CPULISTentryStruct.IRQlocks]
%ifdef KERNSUPPORT_MP
   LAPICwrite LAPICtaskPrioriy,0xF0
   lock bts dword %1,%2               ;Try to acquire lock
   jnc %%locked                  ;Continue if lock acquired
%%wait:
   pause
   lock bts dword %1,%2               ;Try to acquire lock
   jc %%wait                  ;Keep trying if still locked
%%locked:
%endif
%endmacro


%macro UNLOCK_IRQS 2
%ifdef KERNSUPPORT_MP
   lock btr dword %1,%2               ;Unlock the lock
%endif
   sub dword [gs:CPULISTentryStruct.IRQlocks],1
   ja %%l1
   call retryIRQs
%ifdef KERNSUPPORT_MP
   LAPICwrite LAPICtaskPrioriy,0x00
%endif
%%l1:
   pushfd
   cli
   sub dword [gs:CPULISTentryStruct.schedulerLocks],1
   ja %%l2
   cmp byte [gs:CPULISTentryStruct.switchThreadsFlag],0
   je %%l2
   mov byte [gs:CPULISTentryStruct.switchThreadsFlag],0
   call switchThreads
%%l2:
   popfd
%endmacro

If an IRQ occurs when one or more "IRQ locks" have been acquired, then the IRQ will be put onto a queue. The IRQ queue is handled as soon as all "IRQ locks" have been released.

Either of these methods can be used to lock and unlock any re-entrancy lock (as long as the "unlock" matches the "lock"). In general the first method ("LOCK_THREADS") is used by default, while the second method ("LOCK_IRQS") is only used to protect code that might be used within an IRQ handler.

My OS uses "extremely fine-grained" locking to severely reduce lock contention - the chance of a thread spinning while waiting for a lock to be released (so that it can be acquired by the spinning thread) is very small, even when there's 256 CPUs using all the locks. Currently there's one lock used to prevent threads from being spawned or terminated, up to 513 seperate locks for physical memory management, 4 locks per CPU for scheduler run queues, a seperate lock for each message queue (2 message queues per thread - user & kernel), 2 seperate locks for my "IPI calls", a lock for each process to protect it's part of linear memory, and 3 different locks to protect different areas within the kernels part of the address space (which will increase to about 10 by the time I'm done).

Almost everything outside of the micro-kernel uses messaging to serialize access to data structures, so that no re-entrancy locks are needed. This works because each thread owns part of the address space that no other thread can access. The exception to this rule is data structures that are stored in "process space", which will need some form of re-entrancy locking - I haven't implemented anything for this yet, but when I do it won't be spinlocks (it'll do a thread switch to who-ever has the lock instead of spinning).


Cheers,

Brendan

[Dreamsmith]

I don't want nested interrupts. However, I do want "kernel threads", which means that kernel entries can be nested at most two deep (e.g. -- user-thread makes syscall, transitioning to its kernel-mode stack. Resulting kernel-thread is interrupted by the clock, which could invoke the scheduler, preempting the kernel thread with a higher-priority user-thread). I want "kernel threads" so that long-running kernel operations can be preempted (is there a better way to do this...? I can't think of one...)

Are you sure you aren't making this more complicated in your head than it really is?

First of all, let's clarify some terminology. From the description above, you just want your ordinary program's tasks to be preemptable while they're running in supervisor mode (this is not a seperate task/thread, despite the fact that it may have a seperate stack for security reasons). You just want a "preemptible kernel". People generally use the term "kernel threads" to mean something else entirely.

Making the kernel preemptible isn't fundamentally different from making any program preemptible and "thread safe". You just need to mark out and protect the critical sections.

The question is this -- Assuming that interrupts are enabled while the scheduler is running (but before it does the final stack switch of course), how can I protect the scheduler from itself?

Why do you want interrupts enabled while the scheduler is running? You can easily implement what you said you wanted above (tasks preemptible while in kernel-space) without making the scheduler itself preemptible. The easiest thing to do is just consider the entire scheduler a critical section. Unless your scheduler is extremely complex, you'll actually service interrupts more quickly by doing this than by bolting on a bunch of extra baggage to handle preemption in places where it's not easy to handle.

Perhaps I should have prefaced this question with another question -- does anyone leave interrupts enabled while the scheduler runs?

No. Is your scheduler so complex and slow that you would actually gain any significant benefit by doing so?

You can have a preemptible kernel, fully capable of being interrupted while performing long tasks, which is what you said you wanted, without having a preemptible scheduler (unless your scheduler is itself one of those long tasks, and I can't imagine why it would be). You don't need a preemptible scheduler if all you want is a preemptible kernel.

[Colonel Kernel]

Are you sure you aren't making this more complicated in your head than it really is?

No, I'm not sure of that at all. I usually don't ask these questions until I've confused myself terribly and need to be smacked with some sensibility from folks like you. Thanks!

First of all, let's clarify some terminology. From the description above, you just want your ordinary program's tasks to be preemptable while they're running in supervisor mode (this is not a seperate task/thread, despite the fact that it may have a seperate stack for security reasons). You just want a "preemptible kernel". People generally use the term "kernel threads" to mean something else entirely.

Exactly. I used the wrong term, but we agree 100% on the concept. Due to my sleep-deprived brain, I shortened "thread running in kernel mode" to "kernel thread". My bad.

Making the kernel preemptible isn't fundamentally different from making any program preemptible and "thread safe". You just need to mark out and protect the critical sections.

It's kinda different in that you have more direct control of the synchronization mechanisms. It's also different in that you're pretty much programming bare hardware, so abstractions such as threads and critical sections aren't just *there* the way they are in application development. At least, not until you implement them -- which I haven't yet.

Why do you want interrupts enabled while the scheduler is running?

See also:

• Just disable interrupts while the scheduler runs, stupid!

You can easily implement what you said you wanted above (tasks preemptible while in kernel-space) without making the scheduler itself preemptible. The easiest thing to do is just consider the entire scheduler a critical section. Unless your scheduler is extremely complex, you'll actually service interrupts more quickly by doing this than by bolting on a bunch of extra baggage to handle preemption in places where it's not easy to handle.

I'm just wondering if it's possible, desirable, and/or easy to do. I have no idea whether I'll need such a thing or not. All I know is that some kernels do it this way, and I want to know why/how.

Perhaps I should have prefaced this question with another question -- does anyone leave interrupts enabled while the scheduler runs?

No. Is your scheduler so complex and slow that you would actually gain any significant benefit by doing so?

I don't have a scheduler yet, so I can't answer that question.

[Colonel Kernel]

...Continued from above...

I should explain my approach to my OS project... Maybe it will help explain where these seemingly bizzare questions are coming from.

My background is in data access software development, which (naturally) is a user-space thing, even though it's pretty close to what could be considered "systems programming". I've worked on parsers, query execution engines/optimizers, server-side infrastructure (database connection pooling, etc.). In a nutshell, I work in a domain where there are many rich abstractions to choose from when designing a system, and where it really pays to think everything through and create a solid design before writing a single line of production code.

I have a pretty strong background in the theory of OS design, since it was a major focus of my studies when I was working on my CS degree. However, I never got the chance to actually implement anything (the OS lab course was canceled the semester before I started). So, I'm making up for it now, but what I lack is primarily knowledge of implementation details, not concepts.

The problems I'm having now may be of my own making... I think it's just a side effect of analyzing the problem domain, perhaps a little too much. I understand the gory details of the x86 architecture pretty well, and I understand the abstractions to be implemented by my kernel equally well (threads, address space management, etc.). What I'm searching for is a set of abstractions to bridge the two worlds, so I don't have to keep my head full of implementation details in order to understand how my kernel is supposed to work. I'm trying to visualize how things are supposed to work so I can actually design it before writing too much code. The risk of forging ahead with coding something I don't fully understand is that the code will be mess, and will just need to be rewritten anyway.

If you have any advice on how to mentally tackle these kinds of design issues, I would appreciate hearing it. So far, what I'm hearing is "kernel development is just like other kinds of concurrent programming". I agree with this at a high level, but like I said, I think there are certain abstractions lacking between "threads" and the processor-specific details of interrupt handling and context switching... In an effort to find out what these abstractions ought to be, I'm looking for patterns in other kernel designs. Hence the broad and strange questions.

Thanks for your help so far.

[Brendan]

Hi,

You can easily implement what you said you wanted above (tasks preemptible while in kernel-space) without making the scheduler itself preemptible. The easiest thing to do is just consider the entire scheduler a critical section. Unless your scheduler is extremely complex, you'll actually service interrupts more quickly by doing this than by bolting on a bunch of extra baggage to handle preemption in places where it's not easy to handle.

I'm just wondering if it's possible, desirable, and/or easy to do. I have no idea whether I'll need such a thing or not. All I know is that some kernels do it this way, and I want to know why/how.

The main consideration (IMHO) is whether the OS supports multiple CPUs (and how well) or if it's single-CPU only. If the OS does support multiple CPUs then disabling interrupts on one CPU won't prevent another CPU from accessing the same data at the same time. In this case you need additional re-entrancy locking, but once this is done you may no longer need to disable interrupts in most of the kernel's code. For the scheduler's code to switch to another thread, disabling interrupts is required (unless you're using hardware task switching) because an IRQ handler shouldn't be called when the CPU doesn't contain consistant state (ie. halfway between threads). Disabling interrupts might be needed for the beginning of some exception handlers (for e.g. page fault if CR2 isn't saved/restored during a thread switch). Apart from these cases it's possible to never disable interrupts, even though it may be more practical and/or beneficial.

For an OS designed for single-CPU only it's easier to disable interrupts around all critical sections. If a critical section is too long for this then I'd suggest redesigning the operation - a more efficient algorithm, splitting the critical section into several small critical sections, etc.


Cheers,

Brendan