stay Linux There are a lot of critical resources in the system that need to be protected , How to make each task access these resources in an orderly way , This involves Linux Concurrent access protection mechanism design related knowledge . These mechanisms will be described in detail later .

( According to reliable information , The realization of lock often appears in the written examination . We can examine the interviewer's understanding of the principle of lock , You can also examine the interviewer's programming skills ).

notes : Part of the code is based on ARM64 Architecture assembly code translated into C The language has been simplified ( for example :spin lock、read-write lock). Some of the code implementation is written to present the principles behind the design , Not streamlining Linux The code implemented in ( for example mutex).

spinlocks (spin lock)

Spin lock is Linux Locks that are used very frequently in , The principle of simple .

When there is a resource access conflict in the kernel , There are two lock solutions available :

  • One is waiting in place
  • One is to suspend the current process , Schedule other processes to execute ( sleep )

Spinlock It's a common locking mechanism provided by the kernel , Spin lock is “ Wait in place ” How to solve resource conflicts , namely , After a thread acquires a spin lock , Another thread expects to acquire the spin lock , Can't get , We can only stay where we are “ Spin ”( Busy waiting ). Because of the busy waiting property of spin lock , It's doomed to the limitations of its use scenarios —— Spin locks should not be held for a long time ( Consume CPU resources ), Generally used in interrupt context .

principle

Let's take going to the bank to do business as an example to explain .

  1. There are usually several windows in the business hall of a bank . Unfortunately today , There is only one window to serve . Now the banking service is to use the number queuing , The way of station to station service .
  2. When you go to the bank for business , First of all, I will go to the number machine to get the ticket , It says what's your row number . Then you can wait in line . There's usually a screen , There's a number on it ( for example :“ please xxx Number to 1 Window No ”), The queue number that represents the current customer that can be served . Every time you finish a customer's business , The numbers on the display will increase 1. Waiting customers will compare whether the number written on their hands is consistent with the number on the display screen , If it's the same , You can go to the front desk for business .
  3. It just opened in the morning , customer A It's the first customer of the day , Go to pick up the number machine 0 Number (next Count ) Small ticket , And then you see on the screen 0(owner Count ), customer A I know it's my turn to do business .
  4. customer A Go to the front desk for business ( Hold lock ) in , customer B coming . Again , customer B Go to the number machine and get it 1 Number (next Count ) Small ticket . Then sit by and wait . customer A Still in business , At this point, the customer C Here we are . customer C Go to the number machine and get it 2 Number (next Count ) Small ticket . customer C Also obediently find a seat to continue to wait .
  5. finally , customer A Our business is done ( Release the lock ). then , The display shows 1(owner Count ). customer B and C Compare the number on the screen with the number of your ticket . customer B Finally, we can handle business ( Hold lock ). customer C Still waiting .
  6. customer B Our business is done ( Release the lock ). then , The display shows 2(owner Count ). customer C At last, business began ( Hold lock ). customer C Our business is done ( Release the lock ).
  7. 3 All the customers finished their business and left . Just a bank clerk .
  8. Final , The display shows 3(owner Count ). The next queue number of the number machine is also 3 Number (next Count ). Nobody's doing business ( The lock is released ).

Linux For every one of them spin lock There will be two counts . Namely next and owner( The initial value is 0). process A When applying for a lock , Will judge next and owner Is the value of equal . If it is equal, it means that the lock can be applied successfully , Otherwise, spin in place . until owner and next The spin will exit only when the value of is equal . Hypothetical process A Lock application successful , And then next Add 1. here owner The value is 0,next The value is 1. process B Also apply for lock , preservation next Get the value to the local variable temp(temp = 1) in . because next and owner Value inequality , So spin read in place owner Value , Judge owner and temp Whether it is equal or not , Until you exit the spin state . Of course next The value of is still plus 1, become 2. process A Release the lock , At this point owner The value of the add 1, So at this time B Process owner and temp The values are all 1, therefore B Process gets lock . When B After the process releases the lock , Will also owner The value of the add 1. Last owner and next All equal to 2, Represents that no process holds a lock .next It's a record of the number of lock applications , and owner Is the count of lock holding processes .

The actual scene

One 、 Consider the following scenario ( Kernel preemption scenario ):

(1) process A A shared resource was accessed during a system call R
(2) process B Shared resources are also accessed during a system call R
Will there be conflict ? Suppose that A Access shared resources R There was an interruption in the process of , The interruption awakens the sleeping , Higher priority B, When the interruption returns to the scene , A process switch occurs ,B Start execution , And through the system call access to R, If there is no lock protection , There will be two thread Enter the critical area , Causes the program to execute incorrectly .OK, We add spin lock See how :A Before entering the critical zone, we got spin lock, alike , stay A Access shared resources R There was an interruption in the process of , The interruption awakens the sleeping , Higher priority B,B You still try to get... Before you visit the critical area spin lock, At this time, due to A Processes hold spin lock And lead to B The process has entered a permanent spin…… How to deal with it ?linux Of kernel It's simple , stay A Process get spin lock When , Ban this CPU Preemption on the Internet ( The permanence above spin It's only in this CPU The process of seizing this CPU In a scenario like the current process of ). If A and B Run in different CPU On , Then the situation will be simpler :A Although the process holds spin lock And lead to B The process enters spin state , But because it's running on different CPU On ,A The process will continue to execute and will be released soon spin lock, relieve B Process spin state

Two 、 Consider the following scenario ( Interrupt context scenarios ):

(1) Running on the CPU0 Progress on A A shared resource was accessed during a system call R
(2) Running on the CPU1 Progress on B Shared resources are also accessed during a system call R
(3) peripherals P The interrupt handler Shared resources are also accessed in R
In such a scenario , Use spin lock Can protect access to shared resources R The critical region of the earth ? We assume that CPU0 Progress on A hold spin lock Enter the critical area , Now , peripherals P There was an interruption , And it's scheduled to CPU1 On the implementation , It doesn't seem to be a problem , Execute on CPU1 Upper handler I'll wait a little bit CPU0 Progress on A, As soon as it does, the critical zone will be released spin lock Of , however , If the peripherals P The interrupt event for is scheduled to CPU0 What's going to happen with the execution on the Internet ?CPU0 Progress on A In the hold spin lock Is preempted by the interrupt context , And grab it CPU0 Upper handler You're still trying to get... Before you go into the critical zone spin lock, Tragedy struck ,CPU0 Upper P Interruption of peripherals handler Enter forever spin state , Now ,CPU1 Progress on B And inevitably trying to hold spin lock When you fail, you get into spin state . To solve such problems ,linux kernel Such an approach was adopted : If it's about interrupt context access ,spin lock Need and ban this CPU Interrupt Union on .

3、 ... and 、 Consider the following scenario ( The bottom half of the scene )

linux kernel Provides a wealth of bottom half The mechanism of , Although they belong to the same interrupt context , But it's a little different . We can simply modify the above scene : peripherals P It's not a break handler Access shared resources in R, It's about bottom half Medium visit . Use spin lock+ Forbidding local interruption can achieve the effect of protecting shared resources , But it's a bit of a fuss to use a bull's knife to kill chickens , Now disable bottom half Just OK 了

Four 、 Interrupt context competition

The same interrupt handler Between uni core and multi core It's not going to run in parallel , This is a linux kernel Characteristics of .
If different interrupt handler Need to use spin lock Protect shared resources , For the new kernel ( Indistinguishes fast handler and slow handler), all handler It's all off and off , Therefore use spin lock No need to turn off interrupt coordination .
bottom half And is divided into softirq and tasklet, The same softirq Will be in a different CPU Concurrent execution on , So if one of the drivers softirq Of handler A global variable is accessed in , For this global variable, you need to use spin lock The protection of , No need to cooperate disable CPU Interrupt or bottom half.
tasklet It's simpler , Because the same tasklet Not many CPU Concurrent on .

Realization

We first define the structure that describes the spin lock arch_spinlock_t.

typedef struct {
   union { unsigned int slock; struct __raw_tickets {   unsigned short owner;         
               unsigned short next;   } tickets;
  }; } arch_spinlock_t;

As described above , We need two counts , Namely owner and next.slock The occupied memory area covers owner and next( It is said that C You can understand a language well ). The following implementation of the application lock operation arch_spin_lock.

static inline void arch_spin_lock(arch_spinlock_t *lock) {arch_spinlock_t old_lock;old_lock.slock = lock->slock;                                 /* 1 */ 
        lock->tickets.next++;                                         /* 2 */           while (old_lock.tickets.next != old_lock.tickets.owner) {     /* 3 */old_lock.tickets.owner = lock->tickets.owner;            /* 4 */        } }

  1. Continue with the example above . Customers get the queue number from the number machine .
  2. The number machine updates the next customer's queue number .
  3. Take a look at the display , Judge if it's your turn .
  4. Keep staring at the screen to see if it's your turn .

The operation of releasing the lock is very simple . Do you remember the above example of a bank doing business ? The operation of releasing the lock is just the queue number on the display plus 1. We just need to put owner Count plus 1 that will do .arch_spin_unlock The implementation is as follows .

static inline void arch_spin_unlock(arch_spinlock_t *lock) { lock->tickets.owner++; }

Semaphore (semaphore)

Semaphore is also called signal light , It is used to coordinate data objects between different processes , And the main application is shared memory mode of inter process communication . Essentially , A semaphore is a counter , It is used to record information about a resource ( Such as shared memory ) Access status of . It's responsible for coordinating the processes , To make sure they get it right 、 Rational use of public resources . It and spin lock The biggest difference is : Processes that cannot get semaphores can sleep , So it leads to system scheduling . As a general rule , To get shared resources , The process needs to do the following :
(1) Test the semaphore that controls the resource .
(2) If the value of this semaphore is positive , The resource is allowed to be used . The process decrements the semaphore 1.
(3) If this semaphore is 0, The resource is currently unavailable , The process goes to sleep , Until the semaphore value is greater than 0, The process is awakened , Go to step (1).
(4) When a process no longer uses a semaphore controlled resource , Semaphore value plus 1. If a process is sleeping and waiting for this semaphore , Then wake up the process .
What maintains the semaphore state is Linux Kernel operating system, not user process . We can start from scratch /usr/src/linux/include/linux/sem.h See the definitions of the various structures that the kernel uses to maintain semaphore state in . A semaphore is a data set , The user can use each element of this collection alone .

Semaphore (semaphore) It's a mechanism for inter process communication to handle synchronous mutual exclusion . Is a measure used in a multithreaded environment , It's responsible for coordinating the processes , To make sure they get it right 、 Rational use of public resources . It and spin lock The biggest difference is : Processes that cannot get semaphores can sleep , So it leads to system scheduling .

principle

Semaphores can be used to mark the number of available resources .

for 2 A life example :

  1. We are going to take the train from Nanjing to Xinjiang , This ’ Mission ’ It's very time consuming , I have to wait on the bus for the bus to arrive at the station , But we don't have to keep our eyes open waiting for the bus to arrive , The best thing is we get in the car and go straight to bed , Wake up and get to the station , In this way, from people ( user ) From the perspective of , Experience is the best , Compared to the process , While the program is waiting for a time-consuming task , There is no need to occupy CPU, You can pause the current task to sleep , When the waiting event occurs, it will be awakened by other tasks , It's more appropriate to use semaphore in this scenario .
  2. We're waiting for the elevator 、 Waiting for the bathroom , There are not many events to wait for in this scenario , If we have to find a place to sleep , Then wake up when the elevator arrives or the restroom is ready , Well, obviously, it's not necessary , We just need to line up , Just brush and tiktok , Compared to computer programs , For example, the driver enters the interrupt routine , Waiting for a register to be set , The waiting time for this scenario is very short , The system cost is far less than the cost of going to sleep , So spin lock is more suitable for this kind of scene .

Realization

To record the amount of resources available , We definitely need a count Count , Mark the number of resources currently available . Of course, there is also a notebook function like a librarian . It is used to record the students waiting to borrow books . therefore , A two-way linked list is enough . So just one count Count and wait for the chain header of the process . The structure describing the semaphore is as follows .

struct semaphore {unsigned int count;struct list_head wait_list; };

stay Linux in , Every process is like every student who borrows books . Inform a classmate , It's like waking up the process . therefore , We also need a structure to record the current process information (task_struct).

struct semaphore_waiter {struct list_head list;struct task_struct *task; };

struct semaphore_waiter Of list Members are hung when the process is unable to get semaphores semaphore Of wait_list member .task A member is to record the process information that is subsequently awakened .

Assign the current process to task, And use it list Member adds the node of the variable to sem Medium wait_list For the head of a list , Suppose there are multiple processes in sem On the call down_interruptible, be sem Of wait_list The formation of the queue is shown in the figure below :
 Insert picture description here

( notes : Block a process , The general process is to put the process in the waiting queue first , Then change the state of the process , Let's set it to TASK_INTERRUPTIBLE, Then we call the scheduling function schedule(), The latter will take the current process from cpu In the running queue of )
(3) Trying to get a semaphore , If not , The function immediately returns 1 Instead of putting the current process to sleep .

Everything is all set. , Now you can implement the semaphore application function .

void down(struct semaphore *sem) { struct semaphore_waiter waiter; if (sem->count > 0) { sem->count--;  /* 1 */ return;                                    
     } waiter.task = current;                          /* 2 */ list_add_tail(&waiter.list, &sem->wait_list);   /* 2 */ schedule();                                     /* 3 */}

  1. If the semaphore marked resource is left , Naturally, the semaphore can be acquired successfully . Just decrement the available resource count .
  2. Since we can't get the semaphore , You need to put the current process on the waiting queue list of semaphores .
  3. schedule() The main function is to trigger task scheduling , Give up voluntarily CPU Right to use . Before giving up , The current process needs to be removed from the run queue .

The implementation of the release signal is also relatively simple . The implementation is as follows .

void up(struct semaphore *sem) {struct semaphore_waiter waiter;if (list_empty(&sem->wait_list)) {   sem->count++;                          /* 1 */   return; }waiter = list_first_entry(&sem->wait_list, struct semaphore_waiter, list); list_del(&waiter->list);                  /* 2 */wake_up_process(waiter->task);            /* 2 */}

  1. If the waiting list has no process , So naturally, we just need to increase the resource count .
  2. Take the first process from the head of the waiting process chain , And remove... From the list . And then wake up the process .

Read-write lock (read-write lock)

No matter spin lock or semaphore, only one process can enter the critical region at the same time . In some cases , We can distinguish between read and write operations . therefore , We hope that the process of read operation can be carried out concurrently . For write operations, only one process enters the critical area . And this synchronization mechanism is read-write lock . Read write locks generally have the following properties .

  1. At the same time, only one write process enters the critical area .
  2. When the write process does not enter the critical area , At the same time, multiple read processes can enter the critical area .
  3. The read process and the write process cannot enter the critical area at the same time .

There are two types of read-write locks , One is the semaphore type , The other is spin lock type . Let's say spin lock Type explanation .

principle

Let's use the toilet model to interpret the lock .

  1. I find that companies usually have cleaning aunts cleaning toilets . If you take the men's room as an example , I think that when a man enters the toilet, it is equivalent to a reader entering the critical area . Because there can be more than one man in the toilet . And cleaning aunt into the men's toilet is equivalent to the writer into the critical area .

  2. hypothesis A The man found that the cleaning aunt was not cleaning the toilet , Just go to the toilet . And then B and C At the same time, it goes into the toilet .

  3. Then the cleaning aunt is going to clean the toilet , I found a man in the toilet , So we have to wait at the door .

  4. ABC They all left the toilet . The cleaning aunt quickly went into the toilet to clean . then D Men go to the bathroom , I found aunt cleaning in it . I came out and waited at the door . Now I realize that the writer ( Aunt cleaning ) Be exclusive , readers ( Man ) It's time to enter the critical zone .

Since we allow multiple readers to enter the critical zone , So we need a count to count the number of readers . meanwhile , Because there is always only one writer who enters the critical zone , So just one bit Mark whether a write process has entered the critical area . therefore , We can combine the two counts into one . It only needs 1 individual unsigned int The type is enough . highest (bit31) It means whether there is a writer in the critical area , low 31 position (0~30bit) Count the number of readers .

 Insert picture description here

Realization

To describe a read-write lock, just 1 It's just a variable , So we can define the structure of read-write lock as follows .

typedef struct {volatile unsigned int lock;} arch_rwlock_t;

Since read and write operations are distinguished , So there must be two application lock functions , They are reading and writing . First , Let's see read_lock Implementation of operations .

static inline void arch_read_lock(arch_rwlock_t *rw){unsigned int tmp;do {tmp = rw->lock;tmp++;                            /* 1 */} while(tmp & (1 << 31));                 /* 2 */rw->lock = tmp;}

  1. Increase the reader count , Finally, it will be updated to rw->lock in .
  2. to update rw->lock The premise is that there is no writer , So it's going to determine if there's a writer in the critical zone ( The way to judge is rw->lock Variable bit 31 Value ). If , Some writers have entered the critical zone , It's here to cycle . Until the writer leaves .

When the read process leaves the critical area, it calls read_unlock Release the lock .read_unlock The implementation is as follows .

static inline void arch_read_unlock(arch_rwlock_t *rw){rw->lock--;}

Just decrease the reader count .

Read operation finished , Let's see how write operations are implemented .arch_write_lock The implementation is as follows .

static inline void arch_write_lock(arch_rwlock_t *rw){unsigned int tmp;do {tmp = rw->lock;} while(tmp);                       /* 1 */rw->lock = 1 << 31;                 /* 2 */}

  1. Because the writer is exclusive ( Neither the reader nor the writer can have ), So there's only rw->lock The value of is 0, Only the current writer can enter the critical area .
  2. Set up rw->lock Of bit31, It means the writer enters the critical area .

Called when the write process leaves the critical area write_unlock Release the lock .write_unlock The implementation is as follows .

static inline void arch_write_unlock(arch_rwlock_t *rw){rw->lock = 0;}

Also because the writer is exclusive , So just put rw->lock Set up 0 that will do . It means that no process has entered the critical zone . After all, it's because only one writer can enter the critical zone at the same time , When the writer leaves the critical zone , It certainly means that no process is in the critical zone right now .

The above code implementation will actually lead to starvation of the writing process . for example ,A、B、C Three processes enter the read critical area ,D The process tries to get a write lock , At this time, we can only wait A、B、C Three processes exit the critical zone . If there were before the launch F、G The process enters the read critical area , Then there will be D The process of starvation .

mutex (mutex)

Mutex implements “ Repel each other ”(mutual exclusion) A simple form of synchronization ( So it's called mutex (mutex)). Mutexes prevent multiple threads from entering protected code at the same time “ A critical region ”(critical section). therefore , At any moment , Only one thread is allowed into such a code protection zone .

Before any thread enters the critical area , Must obtain (acquire) Ownership of the mutex associated with this area . If another thread already has a critical mutex , Other threads can no longer enter it . These threads have to wait , Until the current master thread is released (release) The mutex .

When do I need to use mutexes ?
Mutexes are used to protect shared volatile code , That is to say , Global or static data . Such data must be protected by mutexes , To prevent them from being corrupted when multiple threads are accessing at the same time .

As mentioned earlier semaphore Initializing count When counting , It can be divided into counting semaphores and mutually exclusive semaphores ( Binary semaphore ).mutex And the initialization count is 1 The binary semaphores of are very similar . All of them can be used as resources for mutual exclusion . however mutex But there is a special place : Only the lock holder can unlock . however , Binary semaphores can be acquired in a process , Releasing semaphores in another process . If it is applied in embedded applications RTOS, in the light of mutex The implementation of priority inversion is also considered .

principle

since mutex It's a binary semaphore , So you don't need to be like semaphore You need a count Count . because mutex have “ Only the lock holder can unlock ” Characteristics , So we need a variable owner Record the lock holding process . The lock must be released by the same process . Of course, we also need a chain header , Mainly used to facilitate the process of sleep waiting . The principle and semaphore And similar , So it's also reflected in the code .

Realization

mutex Implementation code and Linux There will be differences in implementation , But it can still show you the principles of design . The following design code is more like a part RTOS The code in .mutex and semaphore equally , We need two similar structures to describe mutex.

struct mutex_waiter {struct list_head   list;struct task_struct *task;};struct mutex {long   owner;struct list_head wait_list;};

struct mutex_waiter Of list A member is hung when the process cannot get the mutex mutex Of wait_list Linked list .

First, implement the function of applying for mutual exclusion .

void mutex_take(struct mutex *mutex){struct mutex_waiter waiter;if (!mutex->owner) {mutex->owner = (long)current;           /* 1 */return;}waiter.task = current;list_add_tail(&waiter.list, &mutex->wait_list); /* 2 */schedule();                                     /* 2 */}

  1. When mutex->owner The value of is 0 When , Represents that no process holds a lock . So you can apply directly . then , Record the current lock application process task_struct.
  2. Since you can't get the mutex , Naturally, we need to sleep and wait , Hang in the waiting list .

The release code implementation of mutex is the same as semaphore There are many similarities .

int mutex_release(struct mutex *mutex){struct mutex_waiter *waiter;if (mutex->owner != (long)current)                         /* 1 */return -1;if (list_empty(&mutex->wait_list)) {mutex->owner = 0;                                  /* 2 */return 0;}waiter = list_first_entry(&mutex->wait_list, struct mutex_waiter, list);list_del(&waiter->list);mutex->owner = (long)waiter->task;                         /* 3 */wake_up_process(waiter->task);                             /* 4 */return 0;}

  1. mutex have “ Only the lock holder can unlock ” The feature of this line of code is that .
  2. If the waiting list has no process , So nature just needs to mutex->owner Set up 0, It means no lock is released .
  3. mutex->owner Change the value of to that of the current lockable process task_struct.
  4. Take the first process from the list of waiting processes , And remove... From the list . And then wake up the process .