Concept

Linux The semaphore of kernel is similar to user mode in concept and principle System V Of IPC The mechanism semaphores are the same , But he It can never be used outside the kernel , So he and System V Of IPC Mechanism semaphores have nothing to do with .

If a task wants to get the semaphore that has been occupied , The semaphore puts it in a waiting queue ( It doesn't just stand outside and wait, it writes its name in the task queue ) And let it sleep .

When the process holding the semaphore releases the signal , A task in the waiting queue will be awakened ( Because there may be more than one task in the queue ), And let it get the semaphore . This is different from a spinlock , The processor can execute other code .

Application scenarios

Because the semaphore contention process sleeps while waiting for the lock to become available again , So semaphore is suitable for lock holding for a long time ; contrary , The lock is held for a short time sometimes , It's not appropriate to use semaphores , Because of sleep 、 The cost of maintaining the waiting queue and wake-up can be longer than the full schedule of lock occupancy .

for 2 A life example :

  1. We need to take the train from Nanjing to Xinjiang 2 Time of day , This ’ Mission ’ It's very time consuming , I can only sit on the bus and wait for the bus to arrive at the station , But we don't have to keep our eyes open , Ideally, we'll get in the car and go straight to bed , Wake up and get to the station ( seen 《 alien 》 Readers will have a deep understanding ), In this way, from people ( user ) From the perspective of , Experience is the best , Compared to the process , The program is waiting for a time-consuming event , No, it has to be occupied all the time CPU, You can pause the current task to sleep , When the waiting event occurs, it will be awakened by other tasks , Similar to this scenario, semaphore is more appropriate .

  2. We sometimes wait for the elevator 、 Toilets , The waiting time for this scenario is not very long , 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 kind of scene is often very short , The system cost is even far less than the cost of going to sleep , So spin lock is more suitable for this kind of scene .

About semaphores and spin locks , And deadlocks , We'll talk about it in more detail later .

Usage method

A task wants to access shared resources , First we have to get the semaphore , The get semaphore operation will reduce the semaphore value by 1, If the value of the current semaphore is negative , Indicates that the semaphore cannot be obtained , The task must be suspended in The waiting queue of the semaphore waits for the semaphore to be available ; If the value of the current semaphore is non negative , It means that the signal quantity can be obtained , Thus, the shared resource protected by the semaphore can be accessed immediately .

After the task accesses the shared resources protected by semaphores , The semaphore must be released , To release a semaphore by adding the value of the semaphore to 1 Realization , If the value of the semaphore is not a positive number , Indicates that there is a task waiting for the current semaphore , So he also wakes up all the tasks waiting for that semaphore .

The composition of kernel semaphore

Kernel semaphores are similar to spinlocks , Because when the lock is closed , It does not allow kernel control paths to continue . However , When the kernel control path attempts to get busy resources protected by kernel semaphore lock , The corresponding process is suspended . Only when resources are released , The process becomes runnable again .

Only sleeping functions can get kernel semaphores ; Neither interrupt handlers nor delayable functions can use kernel semaphores .

The kernel semaphore is struct semaphore Object of type , Located in the kernel source code include\linux\semaphore.h file

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

member describe
lock stay 2.6.33 Later versions , The kernel adds raw_spin_lock series , Usage and spin_lock The series is as like as two peas , Just parameters spinlock_t Change into raw_spinlock_t
count The value of the semaphore , 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
wait_list Kernel list , The task that gets the semaphore will register with the member in the waiting list

Semaphore API

initialization

DECLARE_MUTEX(name)

This macro declares a semaphore name And initialize its value to 1, To declare a mutex .

DECLARE_MUTEX_LOCKED(name)

The macro declares a mutex name, But set his initial value to 0, That is, the lock is in the locked state when it is created . So for this kind of lock , It's usually released first and then acquired .

void sema_init (struct semaphore *sem, int val);

This function is used to initialize the initial value of the semaphore , He sets the semaphore sem The value of is val.

Be careful :

val Set to 1 It means that there is only one holder , This kind of semaphore is called binary semaphore or mutually exclusive semaphore .

We also allow semaphores to have multiple holders , This kind of semaphore is called counting semaphore , When initializing, it is necessary to specify the maximum number of holders allowed, and it is also possible to convert the val Initialize to any positive value n, under these circumstances , At most n Processes can access this resource concurrently .

void init_MUTEX (struct semaphore *sem);

This function is used to initialize a mutex , That is, he put the signal quantity sem Is set to 1.

void init_MUTEX_LOCKED (struct semaphore *sem);

This function is also used to initialize a mutex , But he put the semaphore sem Is set to 0, That is, it is locked from the beginning .

PV operation

Acquisition semaphore (P)

void down(struct semaphore * sem);

This function is used to obtain the semaphore sem, It causes the process calling the function to sleep , Therefore, it cannot be in the interrupt context ( Include IRQ Context and softirq Context ) Use this function . This function will put sem The value of the reduction 1, If the semaphore sem Is nonnegative , Go straight back , Otherwise, the caller will be suspended , The semaphore will not continue until another task releases the semaphore .

int down_interruptible(struct semaphore * sem);

The function is similar to down similar , The difference is ,down It won't be signaled (signal) interrupt , but down_interruptible Can be interrupted by signals , Therefore, the function has a return value to distinguish whether it returns normally or is interrupted by a signal , If you return 0, Indicates that the received semaphore returns normally , If it's interrupted by a signal , return -EINTR.

int down_trylock(struct semaphore * sem);

This function tries to get the semaphore sem, If you can get it immediately , He gets the signal and returns 0, otherwise , Can't represent a signal sem, The return value is not 0 value . therefore , It doesn't cause the caller to sleep , Can be used in interrupt context .

int down_killable(struct semaphore *sem);int down_timeout(struct semaphore *sem, long jiffies);int down_timeout_interruptible(struct semaphore *sem, long jiffies);

Release the kernel semaphore (V)

void up(struct semaphore * sem);

This function releases the semaphore sem, Namely the sem The value of the add 1, If sem The value of is non positive , Indicates that there is a task waiting for the semaphore , So wake up those who wait .

Add

int down_interruptible(struct semaphore *sem)

The function is to get the semaphore , If you don't get a semaphore, sleep , There is no signal interruption at this time , So go to sleep . But during sleep it can be interrupted by signals , Interrupt and return to -EINTR, Mainly used for mutual exclusive synchronization between processes .

Here is a comment on the function :

/**
* 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.
*/

A process is calling down_interruptible() after , If sem<0, Then enter the interruptible sleep state and schedule other processes to run , But once the process receives a signal , Then we will down_interruptible Function . And mark the error number as :-EINTR.

A figurative metaphor : The incoming semaphore is 1 It's like dawn , If the current semaphore is 0, Process sleep , until ( The semaphore is 1) I woke up at dawn , But there might be an alarm in the middle ( The signal ) Wake you up .

And so on : Xiaoqiang comes home from school in the afternoon , I'll start eating when I get home , There will be two situations :
Situation 1 : The meal is ready , You can start eating ;
Situation two : When he went to the kitchen, he found that his mother was still doing ,
Mom said to him :“ You go to sleep first , I'll call you later .”
Xiaoqiang promised to go to sleep , But again :“ If Xiao Hong comes to play with me during this period of sleep , You can wake me up .”
Xiaoqiang is down_interruptible, To eat is to get the signal , Sleep corresponds to dormancy here , And Xiao Hong came to me to play is to interrupt sleep .

Using the interruptible semaphore version means , In case it happens semaphore Deadlock of , There's also a chance to use ctrl+c Issue soft interrupt , Let the user mode process waiting for the kernel driver to return exit . Instead of locking up the whole system . During sleep , Can be terminated by interrupt signal , This process can accept interrupt signals !

For example, you type... On the command line # sleep 10000, Press down ctrl + c, Send the process termination signal to the above process . The signal is sent to the user space , And then through the system call , Will send this signal to the driver . Signals can only be sent to user space , Not authorized to send directly to the kernel , that 1G The kernel space of , We can't operate it directly .

Kernel semaphore usage routines

scene 1

In the driver , When multiple threads access the same resource at the same time ( The global variable in the driver is a typical shared resource ), May cause “ Competitive state “, So we have to control the concurrency of shared resources .Linux The kernel

Spin lock and semaphore are the most common methods to solve concurrency control ( Most of the time, it is used as mutex ).

 Insert picture description here

scene 2

Sometimes we want the device to be opened only by one process , When the device is occupied , Other devices have to go to sleep .

Signal processing diagram

 Insert picture description here

Pictured above :

  1. process A First, through open() Open device file , Call to the kernel hello_open(), And call down_interruptible(), Because the semaphore is not occupied at this time , So the process A You can get the semaphore ;

  2. process A After obtaining the semaphore, continue to process the original task , This process B Also through open() Open device file , Also call kernel functions hello_open(), But at this time, the semaphore cannot be obtained , So the process B Blocked ;

  3. process A Task completed , Close device file , And pass up() Release semaphore , So the process B Awakened , And be able to carry on the rest of the mission ,

  4. process B Finish the task , Release device files , adopt up() Release semaphore

The code is as follows :

#include <linux/init.h>#include <linux/module.h>#include <linux/kdev_t.h>#include <linux/fs.h>#include <linux/cdev.h>#include <linux/device.h>#include <linux/semaphore.h>static int major = 250;static int minor = 0;static dev_t devno;static struct cdev cdev;static struct class *cls;static struct device *test_device;static struct semaphore sem;static int hello_open (struct inode *inode, struct file *filep){if(down_interruptible(&sem))//p{return -ERESTARTSYS;}  return 0;}static int hello_release (struct inode *inode, struct file *filep){up(&sem);//vreturn 0;}static struct file_operations hello_ops ={.open = hello_open,.release = hello_release,};static int hello_init(void){int result;int error;    printk("hello_init \n");result = register_chrdev( major, "hello", &hello_ops);if(result < 0){printk("register_chrdev fail \n");return result;}devno = MKDEV(major,minor);cls = class_create(THIS_MODULE,"helloclass");if(IS_ERR(cls)){unregister_chrdev(major,"hello");return result;}test_device = device_create(cls,NULL,devno,NULL,"test");if(IS_ERR(test_device )){class_destroy(cls);unregister_chrdev(major,"hello");return result;}sem_init(&sem,1);return 0;}static void hello_exit(void){printk("hello_exit \n");device_destroy(cls,devno);    class_destroy(cls);unregister_chrdev(major,"hello");return;}module_init(hello_init);module_exit(hello_exit);MODULE_LICENSE("GPL");MODULE_AUTHOR("daniel.peng");


The test program test.c

#include <stdio.h>#include <sys/types.h>#include <sys/stat.h>#include <fcntl.h>main(){int fd;printf("before open\n ");    
    fd = open("/dev/test",O_RDWR);  // Atomic variable   0if(fd<0){perror("open fail \n");return;}printf("open ok ,sleep......\n ");    sleep(20);printf("wake up from sleep!\n ");        close(fd);   // Add as 1}

Compilation steps

1 make Generate hello.ko

2 gcc test.c -o a

3 gcc test.c -o b

testing procedure

  1. Installation driver
insmod hello.ko

  1. Run the process first A, Running process B

See the process A Successfully turned on the device , In the process A sleep The character device will be occupied all the time , process B Because we can't get the semaphore , Into leisure , Combined with the code, we can see , process B Blocked in function open() in .

  1. process A It's over sleep, And release character devices and semaphores , process B Wake up and get the semaphore , And successfully opened the character device .

  1. process B After execution sleep Function and exit , And release character devices and semaphores .

read - Write semaphores

It's like a spin lock , Semaphores are also read differently - Write the semaphore .

If a read-write semaphore is not currently owned by the writer and there is no writer waiting for the reader to release the semaphore , Then any reader can successfully obtain the read-write semaphore ; otherwise , The reader must be suspended until the writer releases the semaphore . If a read-write semaphore is not currently owned by the reader or writer and there is no writer waiting for the semaphore , Then a writer can successfully obtain the read-write semaphore , Otherwise, the writer will be suspended , Until there are no visitors . therefore , The writer is exclusive , Exclusive .

There are two implementations of read-write semaphores , One is universal , Independent of hardware architecture , therefore , Adding a new architecture doesn't need to re implement it , But the disadvantage is low performance , The cost of obtaining and releasing read and write semaphores is high ; The other is architecture related , So high performance , The cost of getting and releasing read and write semaphores is small , But adding new architectures needs to be re implemented . In kernel configuration , You can use options to control which implementation to use .

The correlation between read and write semaphores API:

DECLARE_RWSEM(name)

This macro declares a read-write semaphore name And initialize it .

void init_rwsem(struct rw_semaphore *sem);

This function is used to read and write semaphores sem To initialize .

void down_read(struct rw_semaphore *sem);

The reader calls this function to get the read and write semaphore sem. This function causes the caller to sleep , So it can only be used in the context of a process .

int down_read_trylock(struct rw_semaphore *sem);

This function is similar to down_read, It's just that it doesn't cause the caller to sleep . It tries to get read and write semaphores sem, If you can get it immediately , It gets the read-write semaphore , And back to 1, Otherwise, it means that the semaphore cannot be obtained immediately , return 0. therefore , It can also be used in interrupt context .

void down_write(struct rw_semaphore *sem);

The writer uses this function to get the read and write semaphore sem, It also causes the caller to sleep , So it can only be used in the context of a process .

int down_write_trylock(struct rw_semaphore *sem);

This function is similar to down_write, It's just that it doesn't cause the caller to sleep . This function tries to get the read and write semaphore , If you can get it right away , It gets the read and write semaphore and returns 1, Otherwise it means you can't get it immediately , return 0. It can be used in interrupt context .

void up_read(struct rw_semaphore *sem);

The reader uses this function to release the read and write semaphore sem. It is associated with down_read or down_read_trylock Pairs using .

If down_read_trylock return 0, No call required up_read To release the read-write semaphore , Because there's no semaphore at all .

void up_write(struct rw_semaphore *sem);

The writer calls this function to release the semaphore sem. It is associated with down_write or down_write_trylock Pairs using . If down_write_trylock return 0, No call required up_write, Because back 0 Indicates that the read / write semaphore is not obtained .

void downgrade_write(struct rw_semaphore *sem);

This function is used to demote a writer to a reader , This is sometimes necessary . Because the writer is exclusive , So while the writer keeps the read-write semaphore , No reader or writer will be able to access the shared resource protected by the read-write semaphore , For those writers who do not need write access under current conditions , Demotion to readers will , So that readers waiting to visit can immediately access , This increases the concurrency , Improved efficiency .

Read write semaphore is suitable for reading more and writing less , stay linux The access to the memory image description structure of the process in the kernel is protected by the read-write semaphore .