OSDev.org

The Place to Start for Operating System Developers
It is currently Tue Jan 16, 2018 9:20 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 5 posts ] 
Author Message
 Post subject: Kernel locking strategy - best practices
PostPosted: Thu Jan 11, 2018 12:28 pm 
Offline

Joined: Thu Jan 11, 2018 12:20 pm
Posts: 1
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!


Top
 Profile  
 
 Post subject: Re: Kernel locking strategy - best practices
PostPosted: Thu Jan 11, 2018 1:55 pm 
Offline
Member
Member

Joined: Mon Jul 05, 2010 4:15 pm
Posts: 504
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.


Top
 Profile  
 
 Post subject: Re: Kernel locking strategy - best practices
PostPosted: Thu Jan 11, 2018 4:12 pm 
Offline

Joined: Tue Jul 04, 2017 12:45 am
Posts: 6
OSwhatever wrote:
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.


Top
 Profile  
 
 Post subject: Re: Kernel locking strategy - best practices
PostPosted: Thu Jan 11, 2018 4:59 pm 
Offline
Member
Member

Joined: Mon Jul 05, 2010 4:15 pm
Posts: 504
pragmatic wrote:
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.


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.


Top
 Profile  
 
 Post subject: Re: Kernel locking strategy - best practices
PostPosted: Thu Jan 11, 2018 7:27 pm 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8197
Location: At his keyboard!
Hi,

kenz wrote:
So I have now implemented a semaphore including wait list and connection to scheduler etc. So I wanted to use this new shiny semaphore.


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.

kenz wrote:
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.


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.

kenz wrote:
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)?


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

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: Google [Bot] and 17 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group