OSDev.org

The Place to Start for Operating System Developers
It is currently Fri Feb 23, 2018 12:43 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 10 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: 8
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: 507
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: 15
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: 507
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: 8246
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  
 
 Post subject: Re: Kernel locking strategy - best practices
PostPosted: Mon Jan 22, 2018 5:59 am 
Offline

Joined: Thu Jan 11, 2018 12:20 pm
Posts: 8
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. :)


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

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


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?


Top
 Profile  
 
 Post subject: Re: Kernel locking strategy - best practices
PostPosted: Sun Jan 28, 2018 4:49 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 445
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.


Top
 Profile  
 
 Post subject: Re: Kernel locking strategy - best practices
PostPosted: Mon Jan 29, 2018 12:58 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8246
Location: At his keyboard!
pragmatic wrote:
OSwhatever wrote:
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.


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?


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

_________________
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  
 
 Post subject: Re: Kernel locking strategy - best practices
PostPosted: Mon Jan 29, 2018 11:18 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 445
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.


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

All times are UTC - 6 hours


Who is online

Users browsing this forum: ShukantPal and 7 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