SEM of C language_ Tvariable type

    C In language , The data type of semaphore is structure sem_t, It is essentially a long integer number .

     Its prototype is ：　

extern int sem_init __P ((sem_t *__sem, int __pshared, unsigned int __value));

    The header file is ： 

#include <semaphore.h>

__sem Is a pointer to the semaphore structure ;

__pshared Not for 0 This semaphore is shared between processes , Otherwise, it can only be shared by all threads of the current process ;

__value The initial value of the semaphore is given .

     function sem_post( sem_t *sem ) Used to increase the value of a semaphore when a thread is blocked on this semaphore , Calling this function will stop one of the threads from blocking , The selection mechanism is also determined by the thread scheduling strategy .

     function sem_wait( sem_t *sem ) Used to block the current thread until the semaphore sem The value is greater than 0, After unblocking, it will sem Value of minus one , It shows that public resources are reduced after use .

     function sem_trywait ( sem_t *sem ) Is the function sem_wait（） The non blocking version of , It directly converts the semaphore sem Value of minus one .

     function sem_destroy(sem_t *sem) Used to release semaphores sem.

（1） For semaphore sem_init Function created , Here's a description of it ：

#include
int sem_init (sem_t *sem, int pshared, unsigned int value);

    The purpose of this function is to answer the following questions sem The specified semaphore , Set its sharing options , And specify an initial value of integer type .pshared Parameters control the type of semaphore . If pshared The value of is 0, It means that it is a local semaphore of the current process ; otherwise , Other processes can share this semaphore . Only interested in semaphores that are not shared by processes .（ This parameter is affected by the version ）,　Linux Threads generally do not support shared semaphores between processes ,pshared Passing a non-zero will cause the function to return ENOSYS error .

（2） These two functions control the value of the semaphore , Their definitions are as follows ：

#include
int sem_wait(sem_t * sem);
int sem_post(sem_t * sem);

     Both of these functions need to use a function called by sem_init Call the pointer of the initialized semaphore object as a parameter .

    sem_post The semaphore() function adds a to the value of a semaphore “1”, It's a “ Atomic manipulation " That is, add to the same semaphore at the same time “1” The two threads of the operation will not conflict ; And read the same file at the same time 、 The two programs of add and write operations may cause conflicts . The value of the semaphore will always be added correctly “2”－－ Because there are two threads trying to change it .

    sem_wait A function is also an atomic operation , Its function is to subtract one... From the value of the semaphore “1”, But it will always wait for the semaphore to be a non-zero value before starting subtraction . in other words , If you set a value to 2 Semaphore call for sem_wait(), The thread will continue to execute , The value of the semaphore will be reduced to 1. If a value is 0 Semaphore call for sem_wait(), This function will wait until another thread increases this value so that it is no longer 0 until . If there are two threads sem_wait() Wait for the same semaphore to become non-zero , Then when it is added by the third thread “1” when , Only one of the waiting threads can subtract semaphores and continue execution , The other will still be waiting .

     Semaphores are like this “ You can test and set up atomically with just one function ” Its value lies in its ability . There is another semaphore function sem_trywait, It is sem_wait Non blocking partner for .sem_trywait Is an immediate return function , It won't be blocked by anything . Get different information according to its return value . If the return value is 0, It indicates that the semaphore is greater than 0, But it will be automatically subtracted by this function after calling 1, It is not known whether it is zero after the call . If the return value is EAGAIN Description semaphore count is 0.

（3） Get the semaphore sem Value , And save to valp in . The following definition ：

#include
int sem_getvalue(sem_t *sem, int *valp);

（4） the last one Semaphore The function is sem_destroy. This function is used to clean up the semaphore when we run out of semaphores . The following definition ：​​​​​​​

#include
int sem_destroy (sem_t *sem);

​​​​​​​     This function also uses a semaphore pointer as an argument , Give back all the resources you own . If there are threads waiting for semaphores to be cleaned up , The user will receive an error .

     However, in linux In the thread of , In fact, there are no resources associated with the semaphore object that need to be released , So in linux in , The function of destroying the semaphore object is only to test whether there is a thread because the semaphore is waiting . If the function returns 0 No explanation , Normal logout semaphore , If you return EBUSY, It indicates that another thread is waiting for the signal of the semaphore .

     Like other functions , These functions return... On success “0”.

Use steps ：

1. Declare semaphores sem_t sem1;

2. Initialize semaphores sem_init(&sem1,0,1);

3.sem_post and sem_wait Function to achieve thread synchronization

4. Release semaphore int sem_destroy (&sem1);

Example ：

LeetCode 1114. Print... In order

Here's a class for you ：​​​​​​

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

Three different threads A、B、C Will share one Foo example .

Threads A Will call first() Method

Threads B Will call second() Method

Threads C Will call third() Method

Please design a modification program , In order to ensure that second() Method in first() Method is then executed ,third() Method in second() Method is then executed .

Tips ：

Although the numbers in the input seem to imply order , But we don't guarantee the scheduling order of threads in the operating system .

The input format you see is mainly to ensure the comprehensiveness of the test .

Example 1：​​​​​​​

 Input ：nums = [1,2,3]
 Output ："firstsecondthird"

explain ：

There are three threads that will be started asynchronously . Input [1,2,3] Represents a thread A Will call first() Method , Threads B Will call second() Method , Threads C Will call third() Method . The correct output is "firstsecondthird".

Example 2：​​​​​​​

 Input ：nums = [1,3,2] 
 Output ："firstsecondthird"

explain ：

Input [1,3,2] Represents a thread A Will call first() Method , Threads B Will call third() Method , Threads C Will call second() Method . The correct output is "firstsecondthird".

Explain   answer

Use synchronization

Ideas ：

     The topic requires the implementation of three methods in sequence , And each method runs in a separate thread . To ensure the execution order of threads , You can create some dependencies between methods , That is, the second method must be executed after the first method , The third method must be executed after the second method .

     The dependencies between method pairs form a specific order of execution for all methods . for example A < B, B < C, Then the execution order of all methods is A < B < C.

     Dependencies can be implemented through concurrency . Use a shared variable firstJobDone Coordinate the execution sequence of the first method and the second method , Use another shared variable secondJobDone Coordinate the execution sequence of the second method and the third method .

Algorithm ：

     First initialize the shared variables firstJobDone and secondJobDone, The initial value indicates that all methods are not executed .

     Method first() No dependency , Can be executed directly . Update variables at the end of the method firstJobDone Indicates that the method execution is complete .

     Method second() in , Check firstJobDone The state of . If it is not updated, it will enter the waiting state , Otherwise, the execution method second(). At the end of the method , Update variables secondJobDone Representation second() Execution completed .

     Method third() in , Check secondJobDone The state of . With the method second() similar , perform third() Before , You need to wait secondJobDone The state of .

 

Realization ：

     The implementation of the above algorithm depends largely on the programming language chosen . Although in Java,C++ and Python There are mutexes and semaphores in , But different languages have different implementations of concurrency mechanism .

C++ Code ：​​​​​​​

#include <semaphore.h> 
class Foo { 
protected: 
    sem_t firstJobDone; 
    sem_t secondJobDone; 
public: 

    Foo() { 
        sem_init(&firstJobDone, 0, 0); 
        sem_init(&secondJobDone, 0, 0); 
    } 

    void first(function<void()> printFirst) { 
        // printFirst() outputs "first". 
        printFirst(); 
        sem_post(&firstJobDone); 
    } 

    void second(function<void()> printSecond) { 
        sem_wait(&firstJobDone); 
        // printSecond() outputs "second". 
        printSecond(); 
        sem_post(&secondJobDone); 

    } 

    void third(function<void()> printThird) { 
        sem_wait(&secondJobDone); 
        // printThird() outputs "third". 
        printThird(); 
    }
};