Why we need synchronization
a critical section is a piece of code that accesses a shared resource
(data structure or device) that must not be concurrently accessed by more than one thread of execution.
This overlap, where the result depends on the relative timing of multiple tasks, is called a race condition.
How to use synchronization mechanism
A must read bookUnreliable Guide To Locking – Rusty Russell
Protect from interruption by hardware interrupts:
local_irq_disable(int irq) & local_irq_enable(int irq)
Protection from software interrupts:
local_bh_disable(void) & local_bh_enable(void)
Protection from other CPUs:
spin_lock(spinlock_t *) & spin_unlock(spinlock_t *)
Preemption by other user contexts:
preempt_disable(void) & preempt_enable(void)
What is synchronization in computer science
synchronization means be of the same time.
It means “make it synchronous”, something like coexistence.
Process synchronization refers to the idea that multiple processes are
to join up or handshake at a certain point, in order to reach an
agreement or commit to a certain sequence of action.
* Mutual exclusion – only one excution routine in critical section
The Producer-Consumer Problem
Dining philosophers problem
* Prioirty inversion
* Busy waiting
spinlock - unsleepable mutex
Linux 内核的排队自旋锁FIFO Ticket Spinlock
spinlock保护的critical section执行时间短且不睡眠, 副产品就是避免了
context switch, 相对semaphore效率高.
显然对于little critical section 使用semaphore而不是spinlock,将带来性能
Monitor lock before sleep.
RCU – lockless
Check The Journey to RCU for more details
it was implement based on spinlock.
it can have more than one holder at any time (the number decided at initialization time),
although it is most commonly used as a single-holder lock (a mutex).
if you can not get a semaphore, your task will put itself on the wait queue, and be woken
up the semaphore is released.
- When a program runs on a single-CPU machine, the hardware performs the necessary bookkeeping
to ensure that the program executes as if all memory operations were performed in the order
specified by the programmer (program order), so memory barriers are not necessary.
However, when the memory is shared with multiple devices, such as other CPUs in a multiprocessor
system, or memory mapped peripherals, out-of-order access may affect program behavior.
For example, a second CPU may see memory changes made by the first CPU in a sequence which differs from program order.
Compiler and cpu do the same optimization: reorder of instructions
The Linux kernel has a variety of different barriers that act at different
() Compiler barrier.
() CPU memory barriers.
(*) MMIO write barrier.
Does it work cast a variable to volatile?
No, there is no efects on cast a variable to volatile.
Because, access variable is before volatile cast! That means you
still get a register value. What you do is just conversion a temporary
Rationale for International Standard–Programming Languages–C