Key points when thinking about Linux Interrupt handling mechanisms:
- Linux kernel is not a process, but a process manager
- Kernel pages are not swappable, so no page fault can actually happen
- When an interrupt occurs, the time taken by the interrupt handler is accounted in for the process's time slice which was currently in execution
The OS can switch to kernel mode in the following scenarios:
- Exception handling (Page fault/Illegal memory access etc)
- HW Interrupt. This can happen asynchronously as long as interrupts are enabled (Any form of interrupts including timer interrupts even for scheduler, can be taken into account)
- System calls
Kernel control paths:
- System calls - executed in process context
- Exception Handling - Again, caused during process instruction execution, hence again process context
- H/W Interrupt - Can happen asynchronously and can have nothing to do with currently running process, hence runs in its own context - Interrupt context.
Synchronization:
Kernel Pre-emption:
What is kernel pre-emption?
Kernel pre-emption is a mechanism in which a scheduler is allowed to forcibly evict the currently running process and replace it with another process of same or higher priority, even if the current process can still continue to run if allowed to.
In case of kernel pre-emption, if interrupts are enabled, a high priority process can take over the execution over currently executing process. In this way, the first process control path is left unfinished.
In this situation, no other process code, other than that of an interrupt or exception handling can get executed in a uniprocessor system. In case of a multiprocessor system, this is not the case though!
Disabling Interrupts:
Another approach to achieve synchronization while executing in critical region is to disable interrupts. Note that, by disabling interrupts, we are in effect disabling both interrupts as well as scheduling. Only way to execute some other kernel control path can now be only in case of exception handling, which can never be ignored in any case (i.e. for cases like divide by zero kind of operations etc. it becomes a must do operation). Again, even though disabling interrupts can work well for a uniprocessor machine, the same does not hold good while working with a multiprocessor machines, as disabling interrupts on one processor does not stop the critical section of the code from being executed from another cpu.
Semaphores:
Since neither of the above two can effectively protect the critical resources from being accessed improperly, we need a mechanism for a process to lock the execution of the critical section from being simultaneously accessed by other processes (both in a uniprocessor & multiprocessor machines). There are different forms of locks available in the Linux kernel that can serve the locking purpose "ideally" under different situations, one among that being the Semaphore.
Semaphore is just a counter associated with a data structure.
Following attributes can be associated to describe a semaphore:
1. Has a counter
2. Has a list of all the tasks sleeping while waiting on this semaphore
3. Two APIs to handle this "semaphore" lock - up( ) & down( )
Normally a semaphore will have a default count value of 1 initialized when created.
The down( ) API is called whenever a thread that wants to gain access to the data structure to lock the access rights to itself. The down() will decrement the value of the semaphore count by 1 atomically and then check if the count value becomes negative. If not, it gets access to the data structure and continue executing. Mean while if another process comes down to access the same semaphore and calls down(), down API finds that the count value now turns negative, it is placed in the semaphore's wait list and moved to sleep state, while making a call to the scheduler to schedule a new process.
Now, later when the first process finishes its access to the data structure, it will now decide to release the semaphore by calling the up(). This API would increment the count and checks if there are any pending processes in the waiting list and then wake up one of the process in the list and reschedules it for execution.
Spin Locks:
Spin locks are normally used in interrupt handlers and other similar situations where it is not allowed to sleep. In case of a spin lock, if a process tries to gain the spin lock and fails, rather than sleeping, it would enter into a tight loop continuously checking for the spinlock availability. Thus, we can note that this kind of lock can hang an uniprocessor system and hence helpful only for a multi processor system.
A spin lock is preferred over a semaphore under situations where we are not allowed to sleep as well as situations where it is much efficient to just loop continuously waiting for the lock than to bear the overhead of moving process to a list and rescheduling and bringing back in a later situation, as done by the semaphore.
