20191320-2021-2022-1-diocs learning notes 5

Chapter 4 concurrent programming

4.1 ~ 4.2 parallel concept

Parallel: parallel computing is a computing solution that attempts to solve problems more quickly using multiple processors executing parallel algorithms.

Sequential and parallel algorithms, concurrency

Difference between sequential algorithm and parallel algorithm:
The sequential algorithm is executed in one step according to all steps.
The parallel algorithm performs independent tasks according to the specified parallel algorithm.

Under rational circumstances, all tasks in parallel algorithms should run in real time at the same time. However, in real parallel execution, it can only be implemented in multi-core or multiprocessor systems. In single CPU systems, it can only be executed concurrently, that is, logically parallel execution.


Thread is defined under the process. The process is an independent execution unit. In kernel mode, it is executed in a unique address space. Thread is an independent execution unit in a process's unified address space. The main thread can create other threads, and each thread can create more threads.
All threads of a process execute in the same address space of the process, but each thread is an independent execution unit.
Threads seem to be relatively lightweight compared to processes. Threads also have the following advantages:

  1. Faster thread creation and switching: to create a thread in a process, the operating system does not have to allocate memory and create a page table for the new thread, because the thread shares the same address space with the process. Therefore, creating a thread is faster than creating a process.
  2. Threads respond faster: a process has only one execution path. When a process is suspended, both processes will stop executing. Conversely, when a thread is suspended, other threads in the same process can continue to execute.
  3. Threads are more suitable for well row Computing: the goal of parallel computing is to use multiple execution paths to solve inter problems faster. Algorithms based on divide and conquer principles (such as binary tree search and quick sorting) often show a high degree of parallelism, which can improve the computing speed by using parallel or concurrent execution.
    However, threads also have problems, need clear synchronization information, and have security problems. On the CPU, processing multithreaded programs requires each thread to switch back and forth, which increases the overhead and reduces the speed.

4.3 ~ 4.5 thread operation and program examples

Thread API provided by Pthread Library under Linux:

pthread_create(thread, attr, function, arg): create thread 
pthread_exit(status): terminate thread 
pthread_cancel(thread) : cancel thread 
pthread_attr_init(attr) : initialize thread attributes 
pthread_attr_destroy(attr): destroy thread attribute 

Creating a thread: using pthread_create() to create a thread.
Terminate thread: after the thread function ends, the thread will terminate automatically. You can also call the function int pthraad_exit {void *status) completes the terminated operation.
Thread connection: a thread can wait for the termination of another thread through: int pthread_join (pthread_t thread, void * * status_ptr). The exit status of the terminated thread is returned by status_ptr.

4.6 thread synchronization

Because threads run in the process's unified address space, all threads in the same process share all global variables and data structures. Competition will occur when multiple threads need to modify the same variable or data structure. To prevent such problems, thread synchronization is required.
The simplest way is to add a lock. A lock is called a mutex. It can be used

  1. Static method to define the mutex m.
  2. Dynamic method, use pthread_mutex_init() function to set mutually exclusive attributes.
    Or the method of using conditional variables. It is also divided into static and dynamic methods.

Producer consumer issues

A series of producer and consumer processes share a limited number of buffers. Each buffer has a specific item at a time. It is also called limited buffer problem. The main role of the producer is to generate a certain amount of data into the buffer, and then repeat the process. At the same time, consumers also consume this data in the buffer.


In the operating system, we have learned about semaphores. Semaphores represent the availability of a resource and are the general mechanism of process synchronization. There are P primitives and V primitives, both of which are atomic operations or basic operations.

Practice content process and problem solving process

Thread program test

The test is carried out according to the example given in the textbook. The test content is to use threads for quick sorting. The principle is: the main thread runs first, and then the main thread calls qsort (& ARG) to let the qsort() function execute and realize a quick sorting of N integers. In qsort(), the thread will select a benchmark element and then perform the operation of quick sorting.
The code is as follows:

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
typedef struct{
	int upperbound;
	int lowerbound;
#define N 10
int a[N]={5,1,6,4,7,2,9,8,0,3};// unsorted data
int print(){//print current a[] contents
	int i;
		printf("%d ",a[i]);
void *Qsort(void *aptr){
	PARM *ap, aleft, aright;
	int pivot, pivotIndex,left, right,temp;
	int upperbound,lowerbound;
	pthread_t me,leftThread,rightThread;
	me = pthread_self();
	ap =(PARM *)aptr;
	upperbound = ap->upperbound;
	lowerbound = ap->lowerbound;
	pivot = a[upperbound];//pick low pivot value
	left = lowerbound - 1;//scan index from left side
	right = upperbound;//scan index from right side
	if(lowerbound >= upperbound)
		pthread_exit (NULL);
	while(left < right){//partition loop
		do{left++;} while (a[left] < pivot);
		if (left < right ) {
			temp = a[left];a[left]=a[right];a[right] = temp;
	pivotIndex = left;//put pivot back
	temp = a[pivotIndex] ;
	a[pivotIndex] = pivot;
	a[upperbound] = temp;
	//start the "recursive threads"
	aleft.upperbound = pivotIndex - 1;
	aleft.lowerbound = lowerbound;
	aright.upperbound = upperbound;
	aright.lowerbound = pivotIndex + 1;
	printf("%lu: create left and right threadsln", me) ;
	pthread_create(&leftThread,NULL,Qsort,(void * )&aleft);
	pthread_create(&rightThread,NULL,Qsort,(void *)&aright);
	//wait for left and right threads to finish
	pthread_join(rightThread, NULL);
	printf("%lu: joined with left & right threads\n",me);
	int main(int argc, char *argv[]){
	PARM arg;
	int i, *array;
	pthread_t me,thread;
	me = pthread_self( );
	printf("main %lu: unsorted array = ", me);
	print( ) ;
	arg.upperbound = N-1;
	arg. lowerbound = 0 ;
	printf("main %lu create a thread to do QS\n" , me);
	pthread_create(&thread,NULL,Qsort,(void * ) &arg);//wait for Qs thread to finish
	printf ("main %lu sorted array = ", me);
	print () ;

Problems and Solutions

When compiling using conventional methods, it is found that the compilation cannot be performed, and it is prompted that pthread related functions are not defined:

After consulting the data and reading carefully, it is found that the compilation operation can be completed only by adding the - pthread parameter to the gcc command, such as gcc thread.c -pthread.

test result

Test in openEuler:

Finally, the program test is successful.

Code link

The code includes some previous codes in the code cloud. Link: https://gitee.com/Ressurection20191320/code/tree/master/IS

Added by willchoong on Sat, 30 Oct 2021 10:26:56 +0300