KernelSync

---

Kernel Synchronization Methods

1 Atomics Operations

• Atomic Interger Operations(operates on integers)
  • ensure that the atomic operations are only used with these special types
  • ensure the compiler does not optimize access to the value
  • hide any arch-specific differences in its implementation (SPARC 24 bits)
  • Table8.1 shows Full Listing of Atomic Integer Operations
• The given function is usually just a macro and inherently atomic.
• Atomic Bitwise Operations(operates on individual bits)
  • bitwise functions operate on generic memory address, bit 0 is the least significant bit of the given address
  • Table 8.2 shows Listing of Atomic Bitwise Operations
  • nonatomic versions of all the bitwise functions are atomic function names prefixed with double underscores.(e.g. __test_bit()). If you are safe from race conditions, nonatomic version might be faster.

2 Spin Locks

• Summary
  • A spin lock is a lock that can be held at most by one thread of execution.
  • The nature of the spin lock: a lightweight single-holder lock that should be held for short durations, so try to hold the lock as short as possible, and code that cannot sleep(interrupt handler, for example)
  • Note: kernel is preemptive, so the duration of locks held is equivalent to the scheduling latency of the system.
  • Note: Spin Locks are NOT recursive, or it will cause deadlock.
  • Spin locks can be used in interrupt handlers, but before obtaining the lock, one should disable local interrupts(on /current/ processor), or it will cause double-acquire deadlock.
  • Because it is increasing hard to ensure that interrupts are always enabled in any given code path, in stead of spin_lock_irqsave(), spin_lock_irq() is NOT recommended.
  • What Do I Lock? Protect the data not the code.
  • Kernel configure option, CONFIG_DEBUG_SPINLOCK, enable debugging checks.
• Other Spin Lock Methods
  • Table 8.3 Listing of Spin Lock Methods
• Spin Locks and Bottom Halves
  • No need to protect data used only within a single type of tasklet, and disable bottom halves.
  • Data shared by softirqs must be protected whether it is the same softirq type or not, but no need to disable bottom halves.
• Reader-Writer Spin Locks
  • Writing demands mutual exclusion, and multiple concurrent readers are safe so long as there are no writers.(e.g task list)
  • If the line between your readers and writers is muddled, it might be an indication that you do NOT use reader-writer locks.
  • If you only have readers in interrupt handlers but no writers, you do not need to disable interrupts, but still need to disable interrupts for write access.
  • favor readers over writer. a sufficient number of readers can starve pending writers.
  • this code will deadlock.

read_lock(&mr_rwlock);
write_lock(&mr_rwlock);

3 Semaphores

• Summary
  • Semaphores in Linux are sleeping locks.
  • When a task attempts to acquire a semaphore that is already held, the semaphore places the task onto a wait queue and puts the task to sleep.
  • Unless the locks that could be held a long time, the overhead of sleeping can outweight the total lock hold time.
  • Semaphores ONLY be obtained in process context, as interrupt context is not schedulable.
  • When holding a semaphore, you can sleep, and won't cause deadlock.
  • Cannot hold a spin lock while you acquire a semaphore, because you might sleep.
  • Semaphores allow for an arbitrary number of simultaneous lock holders.
  • usage count(or simply count) =1 == binary semaphore(or mutex)
  • usage count > 1 == counting semaphore(seldom use in kernel)
  • down(): you /down/ a semaphore to acquire it.
  • up(): release a semaphore

• Using Semaphores
  • down_interruptible() attempts to acquire the given semaphore, if it fails, it sleeps in the TASK_INTERRUPTIBLE state, and can be woken up with a signal.

static DECLARE_MUTEX(mr_sem);
...
if(down_interruptible(&mr_sem))
   /* signal received, semaphore not acquired */
/* critical region... */
up(&mr_sem);

• Reader-Writer Semaphores
  • All reader-writer semaphores are mutexes, and reader-writer locks use uninterruptible sleep.
  • Unique method: downgrade_writer(): atomically converts an acquired write lock to a read lock.
  • What to Use: Spin Locks Versus Semaphores(Ref.P.132 Table8.6)

4 Complteion Variables

• Summary
  • synchronize between two tasks in the kernel, when one task needs to signal to the other that an event has occurred.
  • For example, in kernel/sched.c and kernel/fork.c. Kernel code waiting for the initialization of the data structure calls /wait_for_completion()/. When the initialization is complete, the waiting tasks are awakened via a call to /complete()/.

5 BKL: The Big Kernel Lock

• Summary
  • BKL, a global spin lock, was created to ease the transition from Linux's original SMP to fine-grained locking.
  • You can sleep when you hold the BKL, and will not deadlock. Because the lock is automatically dropped when the task is unscheduled and reacquired when the task is rescheduled, so the share data is NOT safe.
  • BKL disables kernel preemption while it is held.
  • can acquire the lock recursive, but must call /unlock_kernel()/ an equal number to release the lock.
  • Use of BKL is discouraged because the BKL is seemingly associated with code instead of data, and thus hard to replacement. However, understanding the BKL and its interfaces is important, becasue the lock is still fairly well used in parts of the kernel.

6 Seq Locks

• Summary
  • Discuss: can sleep or not?
  • New type of lock introduced in the 2.6 kernel.
  • favor writers over readers.
  • When writing, a lock obtained and a sequence number is incremented.
  • reader check the sequence number prior to and after reading the data, if the values are the same, then a write did NOT begin in the middle of the read. If the values are even( why even? not zero? could there be more than one writers?)

do{
   seq = read_seqbegin(&mr_seq_lock);
   /* read data here... */
}while (read_seqretry(&mr_seq_lock, seq));

• Discuss: what is /read_seqretry()/ doing?

7 Preemption Disabling

• Summary
  • preempt_disable(), preempt_enable() are nestable
  • preempt_count() - useful when debug
  • get_cpu() will disable kernel preemption prior to returning the current processor number. put_cpu() - reenable kernel preemption.

8 Barriers

• Summary
  • It is sometimes a requirement that memory-reads(loads) and memory-writes(stores) issue in the order specified in your program code, but both the compiler and the processor(exclusive x86) can reorder reads and writes for performance issue.
  • This sort of reordering occurs because modern processors dispatch and commit instructions out-of-order, to optimize use of their pipelines.

---

最後修改日期: Wed, 01 Dec 2004 05:02:03

搜尋: