Several basic knowledge points of thread scheduling

When multiple threads are executed concurrently, many students do not understand what problems the randomness of scheduling will cause. You should know that if you access critical resources without locking, some unexpected situations will occur and even deadlocks will occur.

There are a few basic things to know about thread scheduling:

  1. The smallest units of scheduling are lightweight processes (for example, the simplest C program we write in Hello World executes as a lightweight process) or threads;
  2. Each thread is allocated a time slice, and when the time slice is up, the next thread is executed.
  3. The scheduling of threads has certain randomness, and it is impossible to determine when the scheduling will occur.
  4. In the same process, all threads created except the local resources created within the thread, other resources created by the process are shared by all threads; For example, both main and child threads can access global variables, open file descriptors, and so on.

The instance

No number of theories can be as straightforward as a graphic example.

Expected code timing

Suppose we want to implement a multithreaded instance, and expect the execution timing to be as follows:

Looking forward to the sequential

Expected feature timing:

  1. The main process creates a child thread. The child thread function ();
  2. The main thread count is self-added and assigned to value1 and value2 respectively.
  3. When the time slice is up, switch to the child thread. The child thread determines whether the values of value1 and value2 are the same. If they are different, it will print the values of value1,value2 and count. So value1,value2 should always be the same, so you shouldn’t print anything;
  4. Repeat steps 2 and 3.

Code 1

Ok, now let’s write the following code in this sequence:

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #include <pthread.h>
  5 #include <unistd.h>
 6  7 unsigned int value1,value2, count=0;  8 void *function(void *arg);  9 int main(int argc, char *argv[])  10 {  11 pthread_t a_thread;  12  13 if (pthread_create(&a_thread, NULL, function, NULL) < 0)  14 {  15 perror("fail to pthread_create");  16 exit(- 1);  17 }  18 while ( 1 )  19 {  20 count++;  21 value1 = count;  22 value2 = count;  23 }  24 return 0;  25 }  26  27 void *function(void *arg)  28 {  29 while ( 1 )  30 {  31 if(value1 ! = value2) 32 {  33 printf("count=%d , value1=%d, value2=%d\n", count, value1, value2);  34 usleep(100000);  35 }  36 }  37 return NULL;  38 } Copy the code

At first glance, the program should satisfy our needs and should run without printing anything, but the actual results were surprising.

Compile and run:

gcc test.c -o run -lpthread
./run
Copy the code

The result of code 1

Execution result:You can see that the subroutine randomly prints out some information, so why this execution? The reason is simple. As we mentioned at the beginning of this article, thread scheduling is 䘺 random, and we cannot dictate when the kernel should schedule a thread. There is a printout, so this means that value1 and value2 are different values at this time, which also means that when the subthread is scheduled, it is scheduled between value1 and Value2 on the main thread.

Actual timing of the execution of code 1

The actual execution timing of the code is as follows:

As shown in the figure above, at some point when the program goes to **value2 = count; When the kernel schedules the thread at **, the child process determines the values of value1 and value2, and finds that the values of the two variables are different.

Chances are good that the program will schedule between the following two lines of code.

value1 = count; 
value2 = count;
Copy the code

The solution

How to solve the problem that concurrency causes programs not to perform as expected? For threads, common methods include POSIX semaphores, mutex, condition variables, and so on. Let’s take mutex as an example to explain how to avoid the problem of code 1.

To define and initialize a mutex:

pthread_mutex_t  mutex;
pthread_mutex_init(&mutex, NULL)
Copy the code

To apply for lock release:

pthread_mutex_lock(&mutex);
pthread_mutex_unlock(&mutex);
Copy the code

Principle: Before entering a critical section, you apply for a lock. If you can obtain the lock, you continue to execute. If you cannot obtain the lock, you sleep until another thread releases the lock.

Code 2

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #include <pthread.h>
  5 #include <unistd.h>
 6 #define _LOCK_  7 unsigned int value1,value2, count=0;  8 pthread_mutex_t mutex;  9 void *function(void *arg);  10  11 int main(int argc, char *argv[])  12 {  13 pthread_t a_thread;  14  15 if (pthread_mutex_init(&mutex, NULL) < 0)  16 {  17 perror("fail to mutex_init");  18 exit(- 1);  19 }  20  21 if (pthread_create(&a_thread, NULL, function, NULL) < 0)  22 {  23 perror("fail to pthread_create");  24 exit(- 1);  25 }  26 while ( 1 )  27 {  28 count++;  29 #ifdef _LOCK_  30 pthread_mutex_lock(&mutex);  31 #endif  32 value1 = count;  33 value2 = count;  34 #ifdef _LOCK_  35 pthread_mutex_unlock(&mutex);  36 #endif  37 }  38 return 0;  39 } 40  41 void *function(void *arg)  42 {  43 while ( 1 )  44 {  45 #ifdef _LOCK_  46 pthread_mutex_lock(&mutex);  47 #endif   48  49 if(value1 ! = value2) 50 {  51 printf("count=%d , value1=%d, value2=%d\n", count, value1, value2);  52 usleep(100000);  53 }  54 #ifdef _LOCK_  55 pthread_mutex_unlock(&mutex);  56 #endif  57 }  58 return NULL;  59 } Copy the code

To access the critical resources value1 and Value2, both the main thread and the child thread must apply for a lock. After obtaining the lock, they can access the critical resources, and then release the mutex. After this code executes, no information is printed. Let’s look at the sequence diagram of the program if it produces a schedule between the following codes.

value1 = count; 
value2 = count;
Copy the code

The sequence diagram is as follows:

As the picture above shows:

  1. At time n, the main thread acquires mutex and enters the critical section;
  2. At time n+1, the time slice is up, switch to the child thread;
  3. At n+2, the child thread cannot apply for a mutex lock.
  4. At n+3, the main thread releases mutex, leaves the critical section, and wakes up the child thread that is blocked in mutex. The child thread applies to mutex and enters the critical section.
  5. At n+4, the child thread leaves the critical section and releases the Mutex.

As you can see, after locking, even if the main thread is value2 =count; We have a schedule, the child thread will go to sleep because it can’t get the mutex, only when the main thread is out of the critical section, the child thread can get the mutex, access value1 and Value2, never print the information, so we achieve the expected code timing.

conclusion

In a real project, the concurrency of possible programs can be more complicated, such as between tasks running on multiple cpus, between tasks running on cpus and interrupts, and between interrupts.

Although the probability of some scheduling is small, it does not mean that it does not occur, and because of the mutual exclusion of resources synchronization problems, it is difficult to repeat, throughout the Linux kernel code, all critical resources will correspond to lock.

Read more Linux kernel source code, learn to learn from god, and god. Is the so-called code read a hundred times, its meaning from see! Read tens of millions of lines of code, will not write to copy!

For more information on how kernel and application synchronization are mutually exclusive, check out your other articles.

For more Linux dry goods, please pay attention to a mouthful of Linux

This article was typeset using MDNICE