Modern operating systems have three characteristics : Interrupt handling 、 Multitasking and multiprocessors . These features lead to when multiple processes 、 Thread or CPU When accessing a resource at the same time , There may be an error , These errors are not allowed by the operating system . In the operating system , The kernel needs to provide concurrency control mechanism , Protect shared resources .

In the operating system , Concurrency refers to a period of time in which several programs have been started to run between the end of the run , And these programs are all running on the same processor , But there is only one program running on the processor at any time . Concurrency can easily lead to competition . Competition is when two or more processes access a resource at the same time , At the same time, it causes resource errors . There are several concurrency control mechanisms :

1. Atomic variable operations :
Atomic variable operations ( It is divided into atomic integer operation and atomic bit operation ) That is, it will never be interrupted by any other task or time before the completion of execution , Not half of it , To execute other code . Atomic operations require hardware support , So it's architecture related , Its API And the definition of atomic type is in include/asm/atomic.h in , Use assembly language to realize .
stay linux in , The definition of atomic variables is as follows :

    typedef struct {
        volatile int counter;
    } atomic_t;

keyword volatile Used to suggest GCC Don't do data optimization for this type , So for this variable counte All of the access is memory based , Don't buffer it into registers . Stored in a register , It may cause the data in memory to change , And the data stored in it has not changed .

(1) Atomic integer operations :
1) Definition atomic_t Variable : 

#define ATOMIC_INIT(i) ( (atomic_t) { (i) } )

atomic_t v = ATOMIC_INIT(0);    // Defining atomic variables v And initialize to 0

2) Set the value of the atomic variable :

#define atomic_set(v,i) ((v)->counter = (i))
void atomic_set(atomic_t *v, int i);// Set the value of the atomic variable to i

3) Get the value of the atomic variable :

#define atomic_read(v) ((v)->counter + 0)
atomic_read(atomic_t *v);// Returns the value of an atomic variable 

4) Atomic variables plus / reduce :

static __inline__ void atomic_add(int i, atomic_t * v); // Atomic variables increase i 
static __inline__ void atomic_sub(int i, atomic_t * v); // Atomic variables decrease i

5) Automatic increment of atomic variable / Self reduction :

#define atomic_inc(v) atomic_add(1, v); // Atomic variables plus 1 
#define atomic_dec(v) atomic_sub(1, v); // Atomic variables minus 1

6) Operate and test :

// These operations autoincrement atomic variables , Self reduction , After minus operation, test whether it is 0, Is to return true, Otherwise return to false 
#define atomic_inc_and_test(v) (atomic_add_return(1, (v)) == 0)
static inline int atomic_add_return(int i, atomic_t *v)


(2) Atomic bit operation ( Operate individually according to each bit of data ):


static inline void set_bit(nr, void *addr); // Set up addr Address No nr position , The so-called set bit is to write the bit as 1 
static inline void clear_bit(nr,void *addr); // eliminate addr Address No nr position , The so-called clear bit is to write the bit as 0 
static inline void change_bit(nr,void *addr); 
static inline void test_bit(nr, void *addr); 
static inline int test_and_set_bit(nr, void *addr); 
static inline int test_and_clear_bit(nr, void *addr); 
static inline int test_and_change_bit(nr, void *addr);


The advantage of atomic manipulation is that it's easy to write ; The disadvantage is that the function is too simple , Can only do counting operation , Too little protection .

2. spinlocks
Spin lock is designed for Prevent multiprocessor concurrency And the introduction of a lock , It is applied to interrupt processing and other parts . For a single processor , To prevent concurrency in interrupt processing, we can simply turn off the interrupt , You don't need a spin lock .
spinlocks It can only be held by one kernel task at most , If a kernel task is trying to request one that has been contested ( Has been held ) The spin lock of , Then the task will be busy all the time —— rotate —— Wait for the lock to be available again . If it's not disputed , The kernel task that requests it can immediately get it and continue . Spin locking can prevent more than one kernel task from entering the critical region at any time , Therefore, this kind of lock can effectively avoid kernel tasks running concurrently on multiprocessors competing for shared resources .
(1) The use of spinlocks :

spinlock_t spin; // Define spin lock
spin_lock_init(lock); // Initialize spin lock
spin_lock(lock); // Successful spin lock, return immediately , Otherwise the spin is there until the holder of the spin lock releases
      spin_trylock(lock); // Successful spin lock return to true immediately , Otherwise return false , Not like the last one " Turn around in the same place "
spin_unlock(lock);// Release the spin lock 

Use the code :

spinlock_t lock; 
spin_lock (&lock); 
....// Critical resource areas  

(2) matters needing attention :
1) Spin lock is a kind of busy waiting . It is a lightweight locking mechanism suitable for short time locking .
2) Spin lock cannot be used recursively . Spin locks are designed to synchronize between different threads or functions . This is because , If a thread already holds a spin lock , It's in a busy waiting state , You have no chance to release the lock you hold . If you call yourself at this time , Then spin lock will never be executed .

3. Semaphore
linux in , Two kinds of semaphores are provided : One is used in kernel programs , One for applications . I'm only talking about the former .
Semaphore and spin lock are used in the same way . Compared with spin lock , Semaphore can only enter the critical area when the process or thread that gets semaphore , Execute critical code . The biggest difference between a semaphore and a spin lock is : When a process tries to get a semaphore that has been locked , Processes don't wait like spin locks in the distance .
A semaphore is a sleep lock . If there is a task trying to get a semaphore that has been held , The semaphore pushes it into the waiting queue , And let it sleep . At this point, the processor is free to execute other code . When the process holding the semaphore releases the semaphore , A task in the waiting queue will be woken up , So you can get this semaphore .

(1) The realization of semaphore :
stay linux in , The definition of semaphore is as follows :

struct semaphore {
    spinlock_t        lock;      // Used to correct count Variables protect .
    unsigned int        count;     //     Greater than 0, Resources are free ; be equal to 0, Resources are busy , But no process is waiting for this protected resource ; Less than 0, Resource not available , And at least one process is waiting for the resource .
    struct list_head    wait_list; // The address where the list of waiting queues is stored , All sleep processes currently waiting for resources will be placed in this list .

(2) Use of semaphores :


1) Defining semaphores :

 struct semaphore sem;


2) Initialize semaphores :

static inline void sema_init(struct semaphore *sem, int val); // Set up sem by val
#define init_MUTEX(sem) sema_init(sem, 1) // Initialize a semaphore that is mutually exclusive to users sem Set to 1
#define init_MUTEX_LOCKED(sem) sema_init(sem, 0) // Initialize a semaphore that is mutually exclusive to users sem Set to 0

Definition and initialization can be done in one step :

DECLARE_MUTEX(name); // This macro defines the semaphore name And initialization 1
DECLARE_MUTEX_LOCKED(name); // This macro defines the semaphore name And initialization 0

  When semaphores are used for mutual exclusion ( That is to avoid multiple processes running in the same critical area ), The value of the semaphore should be initialized to 1. This semaphore can only be owned by a single process or thread at any given time . In this mode of use , A semaphore is also called a “ mutex (mutex)”, It's mutually exclusive (mutual exclusion) For short .Linux Almost all semaphores in the kernel are used for mutex .

Use semaphores , The kernel code must contain <asm/semaphore.h> .


3) obtain ( lock ) Semaphore :

void down(struct semaphore *sem);

// This function causes sleep , So it can't be used in interrupt context ; * * down - acquire the semaphore * @sem: the semaphore to be acquired * * Acquires the semaphore. If no more tasks are allowed to acquire the * semaphore, calling this function will put the task to sleep until the * semaphore is released. * * Use of this function is deprecated, please use down_interruptible() or * down_killable() instead. */

 Copy code

int down_interruptible(struct semaphore *sem);


* When the function goes to sleep , Can be awakened by a signal ;
* down_interruptible - acquire the semaphore unless interrupted
* @sem: the semaphore to be acquired
* Attempts to acquire the semaphore. If no more tasks are allowed to
* acquire the semaphore, calling this function will put the task to sleep.
* If the sleep is interrupted by a signal, this function will return -EINTR.
* If the semaphore is successfully acquired, this function returns 0.


int down_killable(struct semaphore *sem);


 * down_killable - acquire the semaphore unless killed
 * @sem: the semaphore to be acquired
 * Attempts to acquire the semaphore.  If no more tasks are allowed to
 * acquire the semaphore, calling this function will put the task to sleep.
 * If the sleep is interrupted by a fatal signal, this function will return
 * -EINTR.  If the semaphore is successfully acquired, this function returns
 * 0.



4) Release semaphore 

void up(struct semaphore *sem); // Release semaphore sem, Wake up the waiting 


4. Completed quantity
It's used for one execution unit to wait for another to finish something ;

struct completion {
    unsigned int done;    // Greater than 0, A function that represents the amount of completion can be executed immediately , Don't wait ; be equal to 0, Put the thread with the amount of completion in the waiting state .
    wait_queue_head_t wait;

Usage method :

1) Define the amount of completion :

struct completion com;

2) initialization :

init_completion(&com); // If you think these two steps are troublesome , I'll give you another macro to define and initialize DECLARE_COMPLETION(com);

3) Waiting for completion :

void __sched wait_for_completion(struct completion *x); // Waiting for one completion Awakened 



 * wait_for_completion: - waits for completion of a task
 * @x:  holds the state of this particular completion
 * This waits to be signaled for completion of a specific task. It is NOT
 * interruptible and there is no timeout.
 * See also similar routines (i.e. wait_for_completion_timeout()) with timeout
 * and interrupt capability. Also see complete().

int __sched wait_for_completion_interruptible(struct completion *x);// Interruptible wait_for_completion


* wait_for_completion_interruptible: - waits for completion of a task (w/intr)
* @x: holds the state of this particular completion
* This waits for completion of a specific task to be signaled. It is
* interruptible.

unsigned long __sched wait_for_completion_timeout(struct completion *x, unsigned long timeout);// With timeout processing wait_for_completion


* wait_for_completion_timeout: - waits for completion of a task (w/timeout)
* @x: holds the state of this particular completion
* @timeout: timeout value in jiffies
* This waits for either a completion of a specific task to be signaled or for a
* specified timeout to expire. The timeout is in jiffies. It is not
* interruptible.

4) Wake up completion

void complete(struct completion *x); // Wake up only one waiting process or thread .
void complete_all(struct completion *x); // Wake up all processes or threads waiting for this amount of completion .


Postscript : In addition to the above several widely used concurrency control mechanisms , also Interrupt mask Sequential lock (seqlock)、RCU(Read-Copy-Update) wait , Make a simple summary, as shown in the figure below :