Semaphore concept

A semaphore is essentially a counter ( Global variables are not set because processes are independent of each other , And it doesn't have to be able to see , Seeing it doesn't guarantee ++ The reference count is an atomic operation ), It is used to read shared data objects by multiple processes , It's different from pipes , It's not primarily for the purpose of transmitting data , It's mainly used to protect shared resources ( Semaphores are also critical resources ), It makes the resource only available to one process at a time .

Semaphore classification

For a variety of reasons ,Linux There are a variety of semaphore implementation mechanisms , It can be used in different situations , The classification is as follows :

[ picture .png]

User semaphores mainly run in user mode , For example, a file must be accessed between processes , Then only the process that gets the semaphore can open the file , Other processes go to sleep , We can also look at the value of the current semaphore , To determine whether to enter the critical zone .

Kernel semaphores mainly run on Linux kernel , It mainly implements the mutual exclusion of kernel critical resources , For example, a device can only be opened by a process , Failure to open a routine on the device will cause the user space process to sleep .

POSIX Famous semaphore

Mainly applied to threads .

 sem_t *sem_open(const char *name, int oflag, mode_t mode, int val);int sem_wait(sem_t *sem);int sem_trywait(sem_t *sem);int sem_post(sem_t *sem);int sem_close(sem_t *sem);int sem_unlink(const char *name);

Every open We need to be in all positions close and unlink, But only in the end unlink take effect

POSIX Unknown semaphore

Mainly applied to threads .

#include<semaphore.h>sem_t sem;int sem_init(sem_t *sem, int pshared, unsigned int val); //pshared by 0 Then shared between threads ,pshared by 1 Then the parent-child process shares int sem_wait(sem_t *sem); // Blocking int sem_trywait(sem_t *sem); // Non blocking int sem_post(sem_t *sem);int sem_destroy(sem_t *sem); Sharing between processes is sem Must be placed in shared memory area (mmap, shm_open, shmget), Global variables of the parent process 、 Pile up 、 Stack storage doesn't work 

Kernel semaphore :

#include<asm/semaphore.h>void sema_init(struct semaphore *sem, int val);void down(struct semaphore *sem); // Can sleep int down_interruptible(struct semaphore *sem); // interruptible int down_trylock(struct semaphore *sem); //m Non blocking void up(struct semaphore *sem);

In addition, there is another way to classify semaphores

Binary semaphore (binary semaphore) And counting semaphores (counting semaphore).
Binary semaphore :
seeing the name of a thing one thinks of its function , There are only two values 0 or 1, Equivalent to mutex , The duty of 1 Resources are available ; And on duty is 0 when , Resources are locked in , The process is blocked and cannot continue .
Count the semaphore :
Its value is in the 0 The semaphore between a limit value and a limit value .

How semaphores work

Semaphores can only do two kinds of operations, waiting and sending signals , Semaphore operations sum up , Its core is PV operation ,P(sv) and V(sv), Their behavior is like this :

(1)P(sv):
If sv The value of is greater than zero , Just subtract it 1; If its value is zero , Suspend the execution of the process

(2)V(sv):
If there are other processes waiting sv And is suspended , Just let it go back to work , If there is no process due to waiting sv And suspend , Just add 1.

In the semaphore PV All operations are atomic operations ( Because it needs to protect critical resources )

notes : Atomic manipulation : The operation of a single instruction is called atomic , The execution of a single instruction is not interrupted

System V IPC

Explain System V Before semaphore , First understand what is System V IPC.

System V IPC There are three types of IPC Collectively known as System V IPC:

  1. System V Semaphore
  2. System V Message queue
  3. System V Shared memory

System V IPC There are some similarities in accessing their functions and the information the kernel maintains for them , It mainly includes :

  1. IPC Key sum ftok function
  2. ipc_perm structure
  3. User access rights specified when creating or opening
  4. ipcs and ipcrm command

The following table summarizes all System V IPC function .


Semaphore Message queue Shared memory
The header file sys/sem.h sys/msg.h sys/shm.h
Create or open IPC Function of semget msgget shmget
control IPC Function of operation semctl msgctl shmctl
IPC Operation function semop msgsnd msgrcv shmat shmdt

IPC Key sum ftok function

Three types of System V IPC All use IPC Key as their logo ,IPC The key is a key_t Type integer , The type in sys/types.h In the definition of .
IPC The bond is usually made up of ftok The function gives , This function takes an existing pathname pathname And a non 0 Integers id Combine into a key_t value , namely IPC key .

#include <sys/ipc.h>// Successfully returns IPC key , Failure to return -1key_t ftok(const char *pathname, int id);

Parameter description :

  • pathname It must be stable during program operation , Can't create and delete repeatedly
  • id Not for 0, It can be positive or negative

ipc_perm structure

The kernel gives each IPC Object maintains an information structure , namely struct ipc_perm structure , The structure and System V IPC The constant value of a function is defined in sys/ipc.h Header file .

struct ipc_perm{uid_t   uid;   //owner's user idgid_t   gid;   //owner's group iduid_t   cuid;  //creator's group idgid_t   cgid;  //creator's group idmode_t  mode;  //read-write permissionsulong_t seq;   //slot usage sequence numberkey_t   key;   //IPC key};

Create and open IPC object

Create or open a IPC Object uses the corresponding xxxget function , They all have two parameters in common :

  • Parameters key,key_t Type of IPC key
  • Parameters oflag, Is used to specify the IPC Object's read and write permissions (ipc_perm.mode), And the choice is to create a new IPC Object or open an existing IPC object

For parameters key, There are two options for applications :

  • call ftok, Pass it on pathname and id
  • Appoint key by IPC_PRIVATE, This will ensure that a new 、 Unique IPC object , But this flag cannot be used to open an existing IPC object , It can only be new

For parameters oflag, As mentioned above , It contains read and write permissions 、 Create or open these two information :

  • You can specify IPC_CREAT sign , Its meaning and Posix IPC Of O_CREAT equally
  • You can also set to the constant value shown in the following table to specify read and write permissions
     Insert picture description here

ipcs and ipcrm command

 because System V IPC The three types of are not identified by file system pathnames , So I can't use ls and rm Command to view and delete them
ipcs and ipcrm Used to view and delete the System V IPC

usage : ipcs -asmq -tclup 
    ipcs [-s -m -q] -i idipcs -h for help.

usage: ipcrm [ [-q msqid] [-m shmid] [-s semid]  [-Q msgkey] [-M shmkey] [-S semkey] ... ]

SYSTEM V Semaphore

SystemV The semaphore is not as good as Posix The semaphore is like that “ To use ”, But it's older than that , however SystemV But it's more widely used ( Especially in old systems ).

System V A semaphore is a set of counting semaphores (set of counting semaphores), Is a collection of one or more semaphores , Each of these is a counting semaphore .( notes :System V A semaphore is a set of counting semaphores ,Posix A semaphore is a single count semaphore .)

All functions share a header file

#include <sys/types.h>#include <sys/ipc.h>#include <sys/sem.h>

Create semaphores

int semget(key_t key,int nsems,int flags)// return : Signal set returned successfully ID, Error return -1

  • (1) The first parameter key It's a long one ( The only non-zero ), System establishment IPC Communications ( Message queue 、 Semaphores and Shared memory ) You must specify a ID value . Usually , The id Value through ftok Function to get , From kernel to identifier , To make two processes see the same signal set , Just set up key If you don't change the value .

  • (2) The second parameter nsem Specifies the number of semaphores required in the semaphore set , Its value is almost always 1.

  • (3) The third parameter flag It's a set of signs , When you want to create a new semaphore when it doesn't exist , Can be flag Set to IPC_CREAT Do bit by bit or operation with file permissions .
    Set up IPC_CREAT After the sign , Even if given key It's an existing semaphore key, It doesn't make mistakes . and IPC_CREAT | IPC_EXCL You can create a new , The only semaphore , If the semaphore already exists , Return an error . Generally, we will return the previous file permissions

Delete and initialize semaphores

int semctl(int semid, int semnum, int cmd, ...);

function :
Semaphore control operation .
Parameters :
semid The set of semaphores indicating the operation ;semnum Indicates a member of the semaphore set (0,1 etc. , until nsems-1),semnum The value is only used for GETVAL,SETVAL,GETNCNT,GETZCNT,GETPID, Usually the value is 0, That's the first semaphore ;cmd: Specifies various operations on a single semaphore ,IPC_STAT,IPC_GETVAL,IPC_SETVAL,IPC_RMID;arg: Optional parameters , It depends on the third parameter cmd.
Return value :
If successful , according to cmd Different return different values ,IPC_STAT,IPC_SETVAL,IPC_RMID return 0,IPC_GETVAL Returns the current value of the semaphore ; Error return -1.

If necessary, the fourth parameter is usually set to union semnu arg; The definition is as follows

union semun{ 
  int val;  // Value used
  struct semid_ds *buf;  //IPC_STAT、IPC_SET  Cache used
  unsigned short *arry;  //GETALL,、SETALL  The array used
  struct seminfo *__buf; // IPC_INFO(Linux specific )  Cache used };

  • (1)sem_id By semget The returned semaphore identifier
  • (2)semnum Which semaphore of the current semaphore set
  • (3)cmd Usually one of the following two values
    SETVAL: Used to initialize a semaphore to a known value .p This value is determined by union semun Medium val Member settings , Its function is to set the semaphore before it is used for the first time .
    IPC_RMID: Used to delete a semaphore identifier that no longer needs to be used , If you delete it, you don't need the default parameters , Just three parameters .

Structure

 Insert picture description here

because system v Semaphores are generated along with kernel startup , We can find it in the source file sem.c see static struct ipc_ids sem_ids; It is system v The entrance to the semaphore , Therefore, it always exists in the process of system operation . The information it holds is a resource ( stay sem In this case, the semaphore set , It can also be msg,shm) Information about . Such as :

   struct ipc_ids {  int in_use;// Describe the number of resources allocated   int max_id;/ The largest location index in use       unsigned short seq;// Next assigned location serial number   unsigned short seq_max;// The maximum position uses the sequence   struct semaphore sem; // Protect  ipc_ids The amount of signal   struct ipc_id_ary nullentry;// If IPC The resource could not be initialized , be entries Fields point to pseudo data structures   struct ipc_id_ary* entries;// Point to resources ipc_id_ary Pointer to data structure };

Its last element entries Point to struct ipc_id_ary Such a data structure , It has two members :

 struct ipc_id_ary {
 int size;// Save the length value of the array
 struct kern_ipc_perm *p[0];// It's an array of pointers  , Array length is variable , When the kernel is initialized, its value is 128};

As we can see in the picture above ,sem_ids.entries->p Point to sem_array This data structure , Why? ?

Let's look at the semaphore set sem_array This data structure :

/* One sem_array data structure for each set of semaphores in the system. */struct sem_array {
   struct kern_ipc_perm sem_perm; /* permissions .. see ipc.h */
   time_t   sem_otime; /* last semop time */
   time_t   sem_ctime; /* last change time */
   struct sem  *sem_base; /* ptr to first semaphore in array */ Point to the semaphore queue    struct sem_queue *sem_pending; /* pending operations to be processed */ Point to the head of the pending queue    struct sem_queue **sem_pending_last; /* last pending operation */ Points to the end of the suspended queue    struct sem_undo  *undo;  /* undo requests on this array */ On the semaphore set   Cancel the request    unsigned long  sem_nsems; /* no. of semaphores in array */ The number of semaphores in a semaphore set };

such sem_ids.entries It's like a semaphore set sem_array It's connected , But why pass kern_ipc_perm Connection , Why not just sem_ids Point to sem_array Well , This is because the semaphore , Message queue , The mechanism of shared memory implementation is basically the same , So they all go through ipc_id_ary This data structure management , And by kern_ipc_perm, They are associated with their respective data structures . That's clear ! Let's look at kernel functions later sys_semget() How to create a semaphore set , And add it to sem_ids.entries Medium .

Change the value of the semaphore

int semop(int semid, struct sembuf *sops, size_t nops);

function :
Operation semaphore ,P,V operation

Parameters :
semid: Semaphore set identifier ;nops yes opstr The number of elements in the array , Usually the value is 1;opstr Point to an array of structures
nsops: The number of semaphores for operation , namely sops The number of structural variables , Must be greater than or equal to 1. The most common setting is that this value is equal to 1, Complete the operation of only one semaphore
sembuf Is defined as follows :

struct sembuf{ 
 short sem_num;   // Unless you use a set of semaphores , Otherwise it is 0 
 short sem_op; // Semaphore data that needs to be changed in one operation , through    // It's usually two numbers , One is -1, namely P( wait for ) operation , 
  // One is +1, namely V( Sending signal ) operation . 
 short sem_flg; // Usually it is SEM_UNDO, Make the operating system track  
  // Semaphore , And when the process terminates without releasing the semaphore , The operating system releases semaphores  };

Return value :
Semaphore identifier returned successfully , Error return -1

General programming steps :

  1. Create a semaphore or get a semaphore that already exists in the system
    1). call semget().
    2). Different processes use the same semaphore key to get the same semaphore
  2. Initialize semaphores
    1). Use semctl() Functional SETVAL operation
    2). When using two-dimensional semaphores , The semaphore is usually initialized to 1
  3. Carry out semaphores PV operation
    1). call semop() function
    2). Realize the synchronization and mutual exclusion between processes
  4. If the semaphore is not needed , Remove from system
    1). Use semctl() Functional IPC_RMID operation


example

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <sys/types.h>#include <unistd.h>#include <sys/sem.h>#include <sys/ipc.h>#define USE_SYSTEMV_SEM 1#define DELAY_TIME 2union semun {int val;struct semid_ds *buf;unsigned short *array;};//  Put the semaphore sem_id Set to init_valueint init_sem(int sem_id,int init_value) {union semun sem_union;sem_union.val=init_value;if (semctl(sem_id,0,SETVAL,sem_union)==-1) {perror("Sem init");exit(1);}return 0;}//  Delete sem_id Semaphore int del_sem(int sem_id) {union semun sem_union;if (semctl(sem_id,0,IPC_RMID,sem_union)==-1) {perror("Sem delete");exit(1);}return 0;}//  Yes sem_id perform p operation int sem_p(int sem_id) {struct sembuf sem_buf;sem_buf.sem_num=0;// Semaphore number sem_buf.sem_op=-1;//P operation sem_buf.sem_flg=SEM_UNDO;// The semaphore is not released before the system exits , The system releases automatically if (semop(sem_id,&sem_buf,1)==-1) {perror("Sem P operation");exit(1);}return 0;}//  Yes sem_id perform V operation int sem_v(int sem_id) {struct sembuf sem_buf;sem_buf.sem_num=0;sem_buf.sem_op=1;//V operation sem_buf.sem_flg=SEM_UNDO;if (semop(sem_id,&sem_buf,1)==-1) {perror("Sem V operation");exit(1);}return 0;}int main() {pid_t pid;#if USE_SYSTEMV_SEMint sem_id;key_t sem_key;sem_key=ftok(".",'A');printf("sem_key=%x\n",sem_key);// With 0666 And create mode Create a semaphore , Return to sem_idsem_id=semget(sem_key,1,0666|IPC_CREAT);printf("sem_id=%x\n",sem_id);// take sem_id Set to 1init_sem(sem_id,1);#endifif ((pid=fork())<0) {perror("Fork error!\n");exit(1);} else if (pid==0) {#if USE_SYSTEMV_SEMsem_p(sem_id); //    P operation #endifprintf("Child running...\n");sleep(DELAY_TIME);printf("Child %d,returned value:%d.\n",getpid(),pid);#if USE_SYSTEMV_SEMsem_v(sem_id); //    V operation #endifexit(0);} else {#if USE_SYSTEMV_SEMsem_p(sem_id); //    P operation #endifprintf("Parent running!\n");sleep(DELAY_TIME);printf("Parent %d,returned value:%d.\n",getpid(),pid);#if USE_SYSTEMV_SEMsem_v(sem_id); //    V operation waitpid(pid,0,0);del_sem(sem_id);#endifexit(0);}}

The operation results are as follows :

[ picture .png]