Linux Kernel Lock / Deffering Mechanismh

tags: OS Deffering Timer Sleep Work Quere Wait Queue Synchronization

本文整理常見(持續補充中)Synchronization、Work Defering機制，主要是將各種方法列出以避免未來使用上的混淆。
至於為什麼把timer、lock、deferring都放在一起整理的話…
因為我自己感覺概念上都是要等一下在執行接下來的函數lol

The kernel sleeping mechanism

Introduce to Process Sleeping:

1. You may relax a processor as soon as your process is waiting for something, and make sure a condition or something will wake it up.

2. The kernel scheduler manages a list of tasks to run, known as a run queue.
   a. Sleeping processes are removed from that run queue. Unless its state changes (that is, it wakes up)

   => 總之linux kernel 有一個叫run queue的列表，用來儲存正在執行的processes，當一個process需要等待某些東西時(可能是block I/O)，可以將那個process丟去sleep (process state也改變為sleep)，然後等待某個特地的條件達成後再將process重新喚醒。

Utilities to use:

1. Wait Queue
2. Completion

Timer

Introduction to Timer

1. There are 2 categories of time:

   • Absolute time: It’s the date and time of the day. (wall time)
   • Relative time: relies on a CPU feature called a timer.

2. There are 2 categories of Timer:

   • Standard timers, or system timers
   • High-resolution timers (HRTs)

3. When it is needed for a period of time in order to let hardware complete its task, the timer can be used to produce the delay for hardware.

=> 總之你只是想等一段時間，然後再執行一段callback function時可以使用。

Jiffies & HZ & Tick

• A jiffy is a kernel unit of time
• HZ is a constant, which is the number of jiffies is incremented in one second.=> jiffies per second
  • Each increment is called a tick.

Tickless Kernel (補充)

• The tickless kernel (=dynamic tick kernel=NOHZ), the ticks are disabled until some tasks needs to be performed.
  • When there are no task to schedule, the scheduler switch to idle thread and disable the periodic tick until the next timer expires (a new task is queued for processing)
  • 當一個cpu進入idle時，代表那顆CPU在下一個timer時間到之後才需要退出idle(或遇到interrupt)。
  • 所以tickless kernel 就是針對這兩種狀況，只要能妥善的處理好jiffies的數值即可。
• 參考
  • Documentation/timers/NO_HZ.txt
  • http://www.ertl.jp/~shinpei/conf/ospert13/slides/FredericWeisbecker.pdf
  • http://abcdxyzk.github.io/blog/2017/07/23/kernel-clock-8/

Utilities

1. setup_timer: ver<=4.13
2. timer_setup: ver>=4.14

Mutext & Spinlock

此為kernel的lock機制，主要是用來保護Critical Section用的，也就是用來避免發生"當多個thread同時操作一個變數時可能會有產生的race condition"。

Lock

1.1. Spinlock:

//declare & init
spinlock_t my_spinlock;
spin_lock_init(my_spinlock);

//usage
spin_lock_irqsave(&my_spinlock, flags);
...Critical Section...
spin_unlock_irqrestore(&my_spinlock, flags);

1.2. Mutex:

//declare & init
struct mutex my_mutex;
mutex_init(&my_mutex);

//usage
mutex_lock(&my_mutex);
...Critical Section...
mutex_unlock(&my_mutex);

1.3. Comparison

Mutex	Spinlock
protects the process’s critical section	protects the IRQ handler’s critical section
mutex put contenders to sleep until the lock is acquired	spinlock infinitely spin in a loop before the lock is acquired.
Mutex can be held for a long time	spinlock should not
	Note: Preemption is disabled only for threads holding spinlocks, not for spinning waiters.

1.4. Read/Write Semaphore

// 靜態初始化
static DECLARE_RWSEM(rwsem_name);

// 動態初始化
static struct rw_semaphore rw_sem；
init_rwsem(&rw_sem);

讀進程獲取信號量保護臨界區數據：
down_read(&rw_sem);
...
up_read(&rw_sem);

寫進程獲取信號量保護臨界區數據：
down_write(&rw_sem);
...
up_write(&rw_sem);

Ref: https://blog.csdn.net/colddown/article/details/38093207

Work Deferring Mechanism

Utilities

1. softirq

   • softirq, or software interrupt is a deferring mechanism used only for very fast processing, since it runs with disabled scheduler.
   • Only:
     • Networks
     • Block device subsystems using softirq.
       • Block devices are characterized by random access to data organized in fixed-size blocks. Examples of such devices are hard drives, CD-ROM drives, RAM disks, etc.

2. ksoftirqd:

   • A ksoftirqd is a per-CPU kernel thread
   • In most cases, softirqs are scheduled in hardware interrupts, which may arrive very quickly, faster than they can be serviced.
   • The unserved softirqs are then queued by the kernel, and ksoftirqds are responsible for late execution.
   • CPU-consuming ksoftirqd may indicate an overloaded system or a system under interrupt storm

3. Tasklet:

   1. Tasklets are an instantiation of softirqs, and will be sufficient in almost every case.
   2. Tasklets are not re-entrant. (softirqs are)
      • Code is called reentrant if it can be interrupted anywhere in the middle of its execution, and then be safely called again.
   3. Tasklet can run on one and only one CPU
      but different tasklets may be run simultaneously on different CPUs. (without needing to worry about races)

4. Work Queue

   1. The work queue is running only in a pre-emptible context. (context switching may happen)
   2. It means that the work queue can sleep in the bottom half of interrupt handler(to process I/O data, hold mutex etc.)
   3. work queues are built on top of kernel thread.

Interrupt Handling

處理interrupt時，會依照 得馬上處理&可以晚點處理將handler分成top half與bottom half，而可以晚點處理這點恰好就很適合使用defering mechanism來實作。

• To grant more CPU time for other task, the concept of halves is introduced

  • Top half: Perform quick and fast operations, schedules the next part. All disabled interrupts must be re-enabled before exiting the bottom half.
  • Bottom half: Process time-consuming stuff, and run with the interrupt re-enabled (To have a chance not to miss an interrupt).

• The bottom halves may run in

  • Interrupt context (can not sleep, atomic)
    • Softirq
    • Tasklet (較容易使用，通常使用這個)
  • Process context (can sleep and can be preempted)
    • Work queue
    • Threaded IRQ
      補充: Threaded IRQ: 通常使用request_irq來註冊一個handler，然後在handler中在自己去想辦法實作bottom half，但新版的API有提供request_threaded_irq，這個函數的參數有兩個handler分別代表top/bottom，他會自動開一個kthread負責bottom的handler，此時就稱為threadedIRQ。