OSDev.org

Hi,

I am quite new to o/s development but I do have experience from many other programming contexts. Anyway, working on my kernel and am in beginning phases of multitasking (single CPU) and interrupt handling. However, now I have a deadlock and want to know what is the way this is usually resolved.

So I have now implemented a semaphore including wait list and connection to scheduler etc. So I wanted to use this new shiny semaphore. So I have created a semaphore for the text console. So I have a syscall handler (that can handle calls from userspace) that can print a string. So of course I wait for the semaphore when printing the string and release it afterwards. However, I also have an interrupt handler for the keyboard which prints something everytime there's a keyboard interrupt. This of course also waits for the semaphore and releases it after printing.

But now the failing case is this: A process calls the print system call. The print system calls grabs the semaphore. However, while inside the function that actually updates the video memory, a keyboard interrupt occurs. The keyboard interrupt handler also tries to grab the semaphore. But since the semaphore has already been acquired, the process is added to the wait list and put to sleep. However, this means that the code that was interrupted (the actual printing, triggered by the process itself, which holds the lock) will now never finish up and actually release the lock! This is because there's no way we can "switch out" of the interrupt handler and back to the system call.

So how is this usually addressed in more general terms (more general than just saying "don't print from the interrupt handlers!" because I guess this conflict could occur over other resources)?

Thank you in advance!

In general, any scheduling primitive inside an interrupt is usually no-go. In about all contemporary operating systems, any type of scheduling is prohibited inside the actual interrupt. This is usually solved by the code that processes the interrupt is done in an bottom-half or in a user process depending on the OS architecture.

Though this nominally makes sense for interrupts in general, is this methodology traditionally followed for the mutlitask/scheduling system? As I near developing mutlitasking in my own OS I was beginning to consider how this might be implemented. I have yet to drill down into the specifics of scheduling in Linux or Minix, but I always thought the scheduler would be called from the systick handler. This would simplify things in that it need only return into a new task. I suppose a background/idle kernel task could periodically check if the current task has been running sufficiently long and stage a flag that forces a task switch on the next systick.

While moving to x86 development after beginning in low-capability embedded devices has given me appropriate perspective and experience to understand why too much processing in an interrupt context is bad, I assumed this would be one of the exceptions. Of course, I have not yet begun implementing multitasking. Perhaps my thoughts on this will change. It would seem that a simpler scheduler (e.g. Round Robin) could be called from within interrupt context if your systick is sufficiently slow. This alone could be reason enough not to do it, though.

No it's the other way around in most operating systems out there. Scheduling most often occurs NOT because of the systick handler. Actually the systick is an obsolete design today and about all operating systems now move towards a "systickless design". About all scheduling operations are triggered by that a thread was stared, blocked (semaphore for example) or exited. An operating system can go very far by not allowing time slice preemption. Once I disabled the OS timer and forgot about it and I didn't notice that several hours later because the OS ran ok without it.

Not many OSes have a periodic timer these days because they prevent power saving and they just waste processor time as most of the time they do nothing.

Hi,



Kernels also tend to use spinlocks (especially for things like the scheduler's data structures); where if the lock can't be acquired the CPU waits and doesn't do a task switch. In general; most locks within the kernel are only held for a very short amount of time and therefore it's usually faster to wait/spin than it is to do two (relatively expensive) task switches.



Potentially excluding "early debugging hacks"; a keyboard driver shouldn't write anything to any (real or virtual) terminal, display or anything else. Typically keyboard IRQ handler sends something to the rest of the keyboard driver, and the rest of the keyboard driver does some processing and sends something to user-space (e.g. to a terminal emulator, to a GUI, ...).

For "early debugging hacks" typically it's enough to do atomic writes directly to the framebuffer without any need for locks; especially if the OS is using text mode.



For these situations typically the kernel has 2 kinds of locks, where one disables IRQs and the other doesn't. If data (that needs a lock) is used by an IRQ handler then that data needs to use an "IRQ disabling lock" (and if the data isn't used by an IRQ handler then it uses a cheaper lock that doesn't disable IRQs). Of course this only works for spinlocks, but IRQ handlers shouldn't be doing anything that takes so long that a mutex or semaphore makes sense.


Cheers,

Brendan

Hi thanks for your advise - for future reference, I have restructed everything so that the screen output is not controlled by a proper semaphore but just saving-disabling/restoring interrupts (which is OK since it is only a single-core kernel at the moment) and then avoid taking semaphores from interrupt handlers at all. So that was the fundamental architectural problem - blocking in interrupt handlers. Fortunately I hadn't done that anywhere else.

This is interesting to me. My knowledge of using the systick as a trigger event for the scheduler came from a Linux kernel book that discussed release 2.6. I can see executing scheduler code on events like you mention as being a reasonable approach, but how do you prevent threads from never yielding the CPU if you are not preempting them after counting timeslices in the systick handler?

You cannot do that; however in practice almost all interactive programs (except for games) intentionally yield the CPU at some point. However, you'll have problems running CPU intensive (e.g. HPC) tasks.

The next step is to preempt lower priority tasks when a higher priority task unblocks. A task doing lengthy processing that never yields would use a low priority and therefore would be preempted as soon as any of the higher priority tasks unblock. Note that (for "higher priority tasks preempt lower priority tasks") when the user presses a key the (higher priority) GUI and/or application typically get CPU time (to handle the key press) "immediately", which is significantly better than "after some low priority task finishes its time slice"; and this is partly why (especially on single-CPU systems under load) some operating systems (Windows, BeOS, ...) feel "fast" (respond to the user very quickly) while other operating systems (Linux) feel "sluggish" (take many extra milliseconds to respond to the user).

Also note that for "CPU bound" tasks it can be better to not bother with time slices at all. To understand this imagine a painter that needs to paint 10 houses. He could do 1 hour of painting on one house, then pack up his gear and switch to a different house and paint the other house for an hour, and so on; and at the end of the week he'll have zero houses that have been finished (and 10 houses that have been started). Alternatively, he could paint a house until its finished (and only switch to the next house when he finishes the previous house) and at the end of the week he might have 2 houses that have been finished (and 8 houses that haven't been started). Even if you ignore the switching costs; the second approach has a much better "average time it takes to finish a job".


Cheers,

Brendan

Sure, no time slices would slightly improve the overall running times of CPU bound tasks. However, in HPC applications at least, context switches have absolutely no measurable overhead. Applications run for hours, days or weeks and are only interrupted a few times per second. On the other hand, no time slices will seriously impact the usability of the machine while the HPC application is running. The negligible benefit of no time slices is heavily offset by the fact that all debugging, logging, monitoring and tracing becomes much harder. You cannot just give every monitoring tool elevated priority to justify no preemption.