1. 选择排序

开启n-1轮循环，每次从未排序的元素中选择最小（或最大）的元素，将其与未排序序列的第一个元素交换位置，从而逐步构建有序序列。

选择排序的具体流程如下：

1. 初始状态：将整个序列视为两部分，一部分是已排序序列，另一部分是未排序序列。
2. 选择最小元素：从未排序序列中选择最小的元素，并将其与未排序序列的第一个元素交换位置。
3. 扩大已排序序列：将交换后的元素视为已排序序列的一部分，未排序序列减少一个元素。
4. 重复步骤2和步骤3：直到所有元素都被选择并放置到正确的位置上。

伪代码：

1
2
3
4
5
6
7
8

选择排序(A):
    for i from 0 to length(A)-2:
        minIndex = i
        for j from i+1 to length(A)-1:
            if A[j] < A[minIndex]:
                minIndex = j
        // 将未排序序列中最小元素与第i个元素交换位置
        swap(A[i], A[minIndex])

时间复杂度为O(n^2)

2. 冒泡排序

多次遍历待排序序列，每轮连续比较相邻的元素，如果“左元素 > 右元素”则交换位置，使较大的元素逐步“冒泡”到数组的末端。

冒泡排序的具体流程如下：

1. 比较相邻元素：从数组的第一个元素开始，比较相邻的两个元素，如果前一个元素比后一个元素大，则交换它们的位置，这样较大的元素就会向数组的末端移动。
2. 遍历整个数组：重复步骤1，遍历整个数组，直到所有的元素都已经比较过一次。
3. 缩小范围：每次遍历过程中，都会使得数组末端的一个元素排好序，因此在下一次遍历时，可以将待排序序列的范围缩小一个元素。

伪代码：

1
2
3
4
5
6

冒泡排序(A):
    n = length(A)
    for i from 0 to n-1:
        for j from 0 to n-1-i:
            if A[j] > A[j+1]:
                swap(A[j], A[j+1])

时间复杂度：O(n^2)

3. 插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。其基本思想是将待排序的数据序列分为已排序区间和未排序区间，通过构建有序序列，对未排序的数据逐个进行插入，从而达到排序的目的。

插入排序的具体思路如下：

1. 初始状态：将第一个元素视为已排序序列，剩余的元素为未排序序列。
2. 遍历未排序序列：从第二个元素开始，逐个遍历未排序序列的元素。
3. 将当前元素插入已排序序列：对于每个未排序序列中的元素，将其与已排序序列中的元素逐个比较，找到合适的位置并插入。
4. 移动元素：为了给当前元素腾出位置，需要将已排序序列中比当前元素大的元素依次向后移动。
5. 重复步骤3和步骤4：直到所有元素都被插入到已排序序列中。

伪代码：

1
2
3
4
5
6
7
8

插入排序(A):
    for i from 1 to length(A)-1:
        currentElement = A[i]
        j = i - 1
        while j >= 0 and A[j] > currentElement:
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = currentElement

时间复杂度：O(n^2)

4. 快速排序

快速排序（quick sort）是一种基于分治策略的排序算法。基本思想是选择一个基准元素，将序列分割成两个子序列，其中一个子序列中的所有元素小于基准元素，另一个子序列中的所有元素大于基准元素，然后对这两个子序列分别进行递归排序。

快速排序的具体步骤如下：

1. 选择基准元素：从待排序序列中选择一个元素作为基准元素。通常选择序列的第一个元素、最后一个元素或者中间的元素作为基准元素。
2. 分割序列：根据基准元素，将序列分割成两个子序列，其中一个子序列中的元素小于基准元素，另一个子序列中的元素大于基准元素。通常使用两个指针（左指针和右指针）来实现分割，左指针指向序列的起始位置，右指针指向序列的末尾位置，然后从左右两端向中间移动指针，交换不符合条件的元素，直到左右指针相遇。
3. 递归排序：对两个子序列分别进行递归排序，直到子序列的长度为1或0。
4. 合并结果：将经过排序的子序列合并成最终的有序序列。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

快速排序(A, low, high):
    if low < high:
        pivotIndex = partition(A, low, high)
        快速排序(A, low, pivotIndex - 1)
        快速排序(A, pivotIndex + 1, high)

partition(A, low, high):
    pivot = A[low]  // 选择第一个元素作为基准元素
    left = low + 1
    right = high
    while left <= right:
        while left <= right and A[left] <= pivot:
            left = left + 1
        while left <= right and A[right] > pivot:
            right = right - 1
        if left < right:
            swap(A[left], A[right])
    swap(A[low], A[right])
    return right

快速排序的时间复杂度为 O(n log n)，其中 n 是待排序序列的长度。在平均情况下，快速排序的性能非常好，但是在最坏情况下（例如，当选择的基准元素总是序列中的最大或最小元素时），快速排序的时间复杂度可能会退化为 O(n^2)。

空间复杂度为O(n)：在输入数组完全倒序的情况下，达到最差递归深度 n ，使用 O(n)栈帧空间。若采用尾递归优化，则复杂度为O(log n)。

尾递归优化是一种编译器优化技术，用于优化递归调用的栈空间使用。在尾递归优化中，如果函数的最后一个操作是对自身的递归调用，编译器会将这种递归调用转换为循环，从而避免在调用栈上创建新的帧，节省了栈空间的使用。

5. 归并排序

归并排序（Merge Sort）是一种基于分治思想的排序算法。其基本思路是将待排序序列分成两个子序列，分别对这两个子序列进行递归排序，然后将两个已经排好序的子序列合并成一个有序序列。

具体的算法流程：

1. 分割序列：不断地将待排序序列划分成两个子序列，直到子序列的长度为1或0
2. 递归排序：递归地对分割后的两个子序列进行排序。
3. 合并序列：将两个已经排好序的子序列合并成一个有序序列。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

归并排序(A):
    if length(A) <= 1:
        return A
    else:
        middle = length(A) / 2
        left_half = 归并排序(A[0:middle])  // 递归排序左半部分
        right_half = 归并排序(A[middle:length(A)])  // 递归排序右半部分
        return 合并(left_half, right_half)  // 合并左右两部分并返回合并后的有序序列

合并(left_half, right_half):
    result = []
    while left_half 不为空 and right_half 不为空:
        if left_half[0] <= right_half[0]:
            result.append(left_half[0])
            left_half = left_half[1:]
        else:
            result.append(right_half[0])
            right_half = right_half[1:]
    // 将剩余的元素追加到结果中
    result += left_half
    result += right_half
    return result

归并排序的时间复杂度为 O(n log n)。虽然归并排序的时间复杂度较低，但是需要额外的空间来存储归并过程中产生的临时序列，因此其空间复杂度为 O(n)。

6. 堆排序

堆排序（Heap Sort）是一种基于堆数据结构的排序算法，其基本思想是利用堆的性质实现排序。堆是一个特殊的树形数据结构，具有以下性质：

1. 它是一个完全二叉树，即除了最后一层，其他层都是满的。
2. 在一个小顶堆（Min Heap）中，任意节点的值都小于或等于其子节点的值。
3. 在一个大顶堆（Max Heap）中，任意节点的值都大于或等于其子节点的值。

将待排序的序列构建成一个大顶堆，重复从堆中取出堆顶元素，并重新构建堆，直到堆为空，最终得到即为排序好的序列。

算法的流程：

1. 构建堆：

   ​ 首先需要将待排序的序列构建成一个堆。一种常见的方法是从最后一个非叶子节点开始，依次向前进行调整，保证每个节点都满足堆的性质。

   大顶堆的调整过程：

   • 从最后一个非叶子节点开始（即 n/2-1），向前遍历到根节点。
   • 对于每个节点，如果它的子节点中有比它大的，就将其与最大的子节点进行交换，直到它没有比它大的子节点或者到达叶子节点为止。

2. 排序：

   ​ 构建好堆之后，需要重复从堆中取出最大（或最小）的元素，并重新调整堆，直到堆为空。具体的过程如下：

   • 将堆顶元素（最大或最小值）与堆中的最后一个元素交换位置。
   • 从堆中移除最后一个元素（即最大或最小值）。
   • 对剩余的元素重新调整堆，使其满足堆的性质。

   重复以上步骤，直到堆为空。

7. 桶排序

8. 计数排序

9. 基数排序

10. 希尔排序

搜索算法用于在数据结构（例如数组、链表、树或图）中搜索一个或一组满足特定条件的元素。

搜索算法可根据实现思路分为以下两类。

• 通过遍历数据结构来定位目标元素，例如数组、链表、树和图的遍历等。
• 利用数据组织结构或数据包含的先验信息，实现高效元素查找，例如二分查找、哈希查找和二叉搜索树查找等。

1. 暴力搜索

暴力搜索通过遍历数据结构的每个元素来定位目标元素。

1. 线性搜索

• 适用于数组和链表等线性数据结构。
• 顺序地逐个检查数据结构中的每个元素，直到找到目标元素或搜索完整个数据结构。
• 时间复杂度为**O(n)**，其中n是数据结构中的元素数量。

2. 图搜索

• 用于在图/树中查找特定的节点或路径，即深度优先搜索（Depth-First Search，DFS）和广度优先搜索（Breadth-First Search，BFS）
• 广度优先搜索从初始节点开始逐层搜索，由近及远地访问各个节点。
• 深度优先搜索从初始节点开始，沿着一条路径走到头，再回溯并尝试其他路径，直到遍历完整个数据结构。
• 时间复杂度取决于图的结构和算法的实现方式。

2. 自适应搜索

自适应搜索利用数据的特有属性（例如有序性）来优化搜索过程，从而更高效地定位目标元素。

1. 二分搜索

• 仅适用于已排序的数据结构（如有序数组），通过不断将搜索范围减半来定位目标元素。
• 时间复杂度为**O(log n)**。

2. 哈希查找

• 利用哈希表将搜索数据和目标数据建立为键值对映射，从而实现查询操作。
• 时间复杂度通常为**O(1)**，但在冲突较多的情况下可能会降低到O(n)。

3. 树查找

• 通过有序的树结构和特定的查找算法（如递归或迭代）来查找目标元素。
• 包括二叉搜索树（Binary Search Tree，BST）、平衡二叉树（Balanced Binary Tree，如AVL树、红黑树）、B树等。
• 平均情况下的时间复杂度取决于树的高度，**通常为O(log n)**，但在最坏情况下可能为O(n)。

浅拷贝

• 简单的拷贝对象成员变量的值，而不拷贝对象所指向的动态分配的内存。
• 新旧对象的指针成员指向相同内存地址的指针，共享同一块内存。
• 如果其中一个对象销毁了这个指针指向的内存，另一个对象可能会引用已经无效的内存地址。
• 当一个对象发生改变时，由于另一个对象与之共享同一块内存，另一个对象也会受到影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <iostream>
using namespace std;

class ShallowCopy {
private:
    int *data;

public:
    ShallowCopy(int val) {
        data = new int(val);
    }

    ShallowCopy(const ShallowCopy &other) {
        data = other.data; // 进行浅拷贝
        cout<<"shallow copy"<<endl;
    }

    int getData() const {
        return *data;
    }

    void setData(int val) {
        *data = val;
    }

    ~ShallowCopy() {
        delete data;
    }
};

int main() {
    ShallowCopy a1(5);
    ShallowCopy a2 = a1;

    cout << "a1=" << a1.getData() <<" "
         << "a2=" << a2.getData() << endl;

    a1.setData(10);

    cout << "a1=" << a1.getData() <<" "
         << "a2=" << a2.getData() << endl;
    
    return 0;
}

输出结果：

1
2
3

shallow copy
a1=5 a2=5
a1=10 a2=10

深拷贝

• 不仅拷贝对象本身，还拷贝对象所指向的动态分配的内存，以确保拷贝后的对象和原对象指向的内存是独立的。
• 深拷贝会为新的对象分配一块新的内存，并将原对象所指向的内存的内容复制到新分配的内存中，从而使得新旧对象完全独立，互不影响。
• 即使两个对象有相同的值，它们也各自拥有一份独立的内存副本，彼此互不影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <iostream>
using namespace std;

class DeepCopy {
private:
    int *data;

public:
    DeepCopy(int val) {
        data = new int(val);
    }

    DeepCopy(const DeepCopy &other) {
        data = new int;
        *data = *(other.data); // 进行深拷贝
        cout<<"deep copy"<<endl;
    }

    int getData() const {
        return *data;
    }

    void setData(int val) {
        *data = val;
    }

    ~DeepCopy() {
        delete data;
    }
};

int main() {
    DeepCopy b1(5);
    DeepCopy b2(b1);

    cout << "b1=" << b1.getData() <<" "
         << "b2=" << b2.getData() << endl;

    b1.setData(10);

    cout << "b1=" << b1.getData() <<" "
         << "b2=" << b2.getData() << endl;

    return 0;
}

输出结果：

1
2
3

deep copy
b1=5 b2=5
b1=10 b2=5

1. 左值、右值

左值：

• 表达式结束后依然存在的持久性对象或者函数，可以被取地址。
• 左值是可以被标识符引用的表达式，它们代表着内存中的一个位置。例如，变量、数组元素、通过引用或指针访问的对象、具有名称的对象等都是左值。
• 左值在赋值操作符左侧出现，可以接受赋值操作。

右值：

• 表达式结束后就消失的临时对象，通常不能被取地址。
• 右值是不具有持久性的临时对象或者表达式的结果，不能被直接引用。例如，字面常量、临时对象、未命名的临时对象、返回临时对象的函数调用等都是右值。
• 右值通常出现在赋值操作符右侧，用于提供值给赋值操作。

2. 左值引用、右值引用

左值引用

• 左值引用是通过使用 & 符号声明的引用类型。它绑定到左值，并且可以延长左值的生命周期，使得左值可以在函数调用等情况下被修改。
• 左值引用不能绑定到右值。
• 左值引用常用于函数参数传递、函数返回值和操作符重载等场景，可以实现有效的引用语义和避免不必要的拷贝。

1
2
3
4
5

int a = 5;
int &b = a; // b是左值引用
b = 4;
int &c = 10; // error，10无法取地址，无法进行引用
const int &d = 10; // ok，因为是常引用，引用常量数字，这个常量数字会存储在内存中，可以取地址

可以得出结论：对于左值引用，等号右边的值必须可以取地址，如果不能取地址，则会编译失败，或者可以使用const引用形式，但这样就只能通过引用来读取输出，不能修改数组，因为是常量引用。

右值引用

• 右值引用是通过使用 && 符号声明的引用类型。它主要用于绑定到临时对象或者即将销毁的对象，允许移动语义的使用。
• 右值引用可以绑定到右值，但不能绑定到左值。
• 右值引用的引入使得可以实现移动语义，即将资源从一个对象“移动”到另一个对象，而不是进行昂贵的拷贝操作。这在处理临时对象时尤为有用，能够提高性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class A {
public:
    A() {} // 默认构造函数
    A(const A& other) {} // 拷贝构造函数
    A(A&& other) {} // 移动构造函数
};

A createA() {
    return A(); // 返回一个临时对象
}

int main() {
    A a1 = createA(); // 调用移动构造函数，避免了拷贝
    return 0;
}

std::move函数：把一个左值强制转换成一个右值 。

1
2
3

int a = 4;
int &&b = a; // error, a是左值
int &&c = std::move(a); // ok

3. 移动语义

• 利用右值引用允许在对象间转移资源的所有权，而不是传统的拷贝。
• 这种转移资源的操作比拷贝操作更高效，特别是对于动态分配的内存或者其他资源。
• 移动语义的引入是为了解决传统的拷贝操作在处理临时对象时可能造成性能开销的问题。
• 移动语义的核心概念在于，当一个对象被标记为将要被销毁（右值），它的资源可以被安全地“窃取”到另一个对象，而不是简单地复制。这意味着移动操作将对象的资源所有权从一个对象转移到另一个对象，而不会发生资源的复制或者额外的分配。

作用

1. 避免不必要的拷贝操作
2. 实现资源管理的高效转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Resource {
public:
    Resource() {}
    // 移动构造函数
    Resource(Resource&& other) {
        // 窃取资源
        this->data = other.data;
        other.data = nullptr; // 将原始对象置为空，避免资源重复释放
    }

private:
    int* data;
};

int main() {
    Resource res1;
    Resource res2 = std::move(res1); // 调用移动构造函数
    return 0;
}

4. 完美转发

• 允许将参数传递到另一个函数，并保留原始参数的值类别（左值或右值）和const修饰符。
• 目标是在保留参数类型的同时，将参数转发给其他函数，实现通用性更强的函数包装或者委托。
• 完美转发的关键是使用了右值引用和模板参数推导。通过使用 std::forward 函数模板，可以在传递参数时保留参数的值类别，确保参数被按原样传递。这种机制在实现泛型编程时尤为有用，可以减少代码的重复和增加可读性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

template<typename T>
void wrapper(T&& arg) {
    // arg 是右值引用或者左值引用，依据传递的实参类型决定
    // 将参数 arg 转发给另一个函数 foo()
    foo(std::forward<T>(arg)); // 完美转发
}

void foo(int& x) { 
	cout << "left value" <<endl;
}
void foo(int&& x) { 
	cout << "right value" <<endl;
}

int main() {
    int x = 42;
    wrapper(x); // 传递左值
    wrapper(42); // 传递右值
    return 0;
}

wrapper 函数模板通过 std::forward 将参数 arg 完美转发给 foo 函数。无论 arg 是左值还是右值，都可以在 foo 中保持其原始的属性，并且正确地调用对应的 foo 函数重载。

运行结果：

1
2

42: left value
42: right value

一、区别

1.1 定义

（1）指针是一个变量，其值为另一个变量的地址，指向内存的一个存储单元。是一个对象实体

（2）而引用的本质是给变量起别名，允许通过这个别名去直接操纵和修改对象本身的属性。引用跟原来的变量实质上是同一个东西。

1
2
3
4
5

int a = 5;
//指针
int* p = &a;
//引用
int& b = a;

1.2 空指针与无效引用

（1）指针可以为空，表示它不指向任何有效的内存地址。在指针没有被初始化时，它的值通常是未定义的，为了避免错误，可以将其初始化为 nullptr 或 NULL。

（2）引用不能为空，它必须在声明时被初始化，并且始终指向某个对象。试图将引用声明为 null 或者空值会导致编译错误。

1.3 初始化

（1）指针需要进行初始化，可以使用取地址符号 & 来获取一个变量的地址，也可以将另一个指针赋值给它。

（2）引用在声明时必须初始化，而且一旦初始化后，不能被重新绑定到其他变量。

4. 运算符

（1）指针可以通过解引用 * 运算符来访问所指向的对象，也可以使用箭头 -> 运算符来访问成员，例如：p->member。

（2）引用则不需要解引用操作符，因为它们在使用时就是被解引用的。例如：b.member。

二、指针常量、常量指针、引用

1. 指针常量：表示这个指针是一个常量，指针的值不可修改。

   如 int* const p，表示一个指向整数类型的指针常量。

• int*：表示指向整数类型的指针。这意味着 p 是一个指针，可以存储整数类型变量的地址。
• const：表示常量，这里用于修饰指针。const 关键字使得指针变量成为一个常量，即指针的值（地址）不能被修改，但是可以通过 p 修改它所指向的整数值。

2. 常量指针：表示该指针指向的值是一个常量，不可修改。

   如 const int* p，表示一个指向整数常量的指针。

• const：表示常量，这里用于修饰整数类型。const 关键字使得指针所指向的整数值为常量，即不能通过 p 修改它所指向的整数值。
• int*：表示指向整数类型的指针。这意味着 p 是一个指针，可以更改指针的指向，让其指向其他值。

1
2
3
4
5
6
7
8
9
10
11

int x = 10;
int y = 20;

int* const p1 = &x;  // p 是一个指向整数类型的指针常量，指向 x 的地址
*p1 = 15;            // 合法，修改了 p 指向的整数变量 x 的值
// p1 = &y;         // 不合法，试图修改 p 的值（地址），但 p 是一个常量，其值不能修改

const int z = 20;
const int* p2 = &x;  // p 是一个指向常量整数类型的指针，指向 x 的地址
// *p2 = 15;         // 不合法，试图通过 p 修改其所指向的整数值，但整数值是常量，不能修改
p2 = &z;             // 合法，修改 p 指向的地址，但是 p 仍然指向一个整数类型的常量

3. 引用的本质在c++内部实现是一个指针常量. 即可以通过引用修改原变量值，但引用不能更改绑定其他变量。

1
2
3
4

int a = 10;
int& b = a;
//等价于
int* const b = &a;

三、区分下列指针类型

1

int *p[10]

表示指针数组，是一个大小为10的数组，数组元素为int *类型的指针。

1

int (*p)[10]

表示一个数组指针，该指针指向一个大小为10，元素类型为int的数组首地址。

1

int *p(int)

表示一个函数声明，函数返回值类型为int*，函数名为p，传入参数类型为int

1

int (*p)(int)

表示一个函数指针，即p是一个指向函数的指针，该函数接受一个int类型的参数，且返回值为int

进程有自己的独立地址空间，因此进程之间重点关注通信。而对于线程来说，除了线程栈外其他数据都是共享的，如果同时读写数据可能造成数据不一致甚至程序崩溃的后果，因此线程之间重点关注同步。

线程同步是指在多线程编程中控制多个线程之间的执行顺序或共享资源访问的过程。在多线程环境中，由于线程的并发执行，可能会导致数据竞争、资源冲突等问题。

1. 竞争条件

在多线程编程中，竞争（Race condition）是指两个或多个线程对共享资源的访问产生的不确定性行为。竞争条件通常发生在多个线程同时访问共享资源时，其中至少一个线程试图修改这些资源的值。在多线程并发场景下指令执行的先后顺序由内核决定，同一个线程内部指令按照先后顺序执行，但不同线程之间的指令执行先后顺序是不一定的。如果执行结果依赖于不同线程执行的先后顺序，那么就会形成“竞争条件”，产生非预期的计算结果，导致程序崩溃等问题。

最常见的解决竞争条件的方式是原子操作，其次便是线程同步。

原子操作是指不可被中断的操作，在执行过程中不会被其他线程或进程干扰，要么全部执行成功，要么全部不执行，不会出现部分执行的情况。原子操作通常是基本的、不可分割的操作单元。

原子操作通常由硬件或者操作系统提供支持，C++11引入了std::atomic模板类来支持原子操作。

2. 线程同步

常见的线程同步的方式有四种：互斥锁、读写锁、条件变量和信号量

2.1 互斥锁

互斥锁（又名互斥量）强调的是资源之间的访问互斥：每个线程在对共享资源操作前都会尝试先加锁，加锁成功才能操作，操作结束之后解锁。

某个线程对互斥量加锁后，其他线程必须等待该线程释放锁才能继续访问共享资源。如果释放互斥锁时有多个线程阻塞，所有在该互斥锁上的阻塞线程都会变成可运行状态。第一个变成运行状态的线程可以对互斥量加锁，其余线程将会看到互斥量依然被锁住，只能回去再次等待它重新变为可用。

mutex是睡眠等待（sleep waiting）类型的锁，当线程抢互斥锁失败的时候，线程会陷入休眠。优点就是节省CPU资源，缺点就是休眠唤醒会消耗一点时间。

互斥锁的接口通常包括 mutex_init()、mutex_lock()、mutex_unlock() 和 mutex_destroy()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <pthread.h>

// 初始化互斥锁
pthread_mutex_t mutex;
pthread_mutex_init(&mutex, NULL);

// 加锁
pthread_mutex_lock(&mutex);

// 解锁
pthread_mutex_unlock(&mutex);

// 销毁互斥锁
pthread_mutex_destroy(&mutex);

2.2 读写锁

读写锁和互斥量类似，是另一种实现线程同步的方式，但是它将操作分为读、写两种方式，可以多个线程同时占用读模式，但只允许一个线程写入。

• 写独占：写锁占用时，其他线程加读锁或者写锁时都会阻塞（并非失败）
• 读共享：读锁占用时，其他线程加写锁时会阻塞，加读锁会成功

读写锁有两种策略：

• 强读同步：读锁优先，只要写锁没有占用那么就可以加读锁
• 强写同步：写锁优先，只能等到所有正在等待或者执行的写锁执行完成后才能加读锁

大部分读写锁的实现都采用的是“强写同步”策略，对尝试加锁的操作进行排队，如果前面已经有尝试加写被锁阻塞住的话，后续加读锁也都会被阻塞住（尽管当前时刻是读锁占用的状态）。这样做的目的主要是为了避免“写饥饿”，在“多读少写”的情况下防止数据修改延迟过高。

读写锁的接口通常包括 rwlock_init()、rwlock_rdlock()、rwlock_wrlock()、rwlock_unlock() 和 rwlock_destroy()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <pthread.h>

// 初始化读写锁
pthread_rwlock_t rwlock;
pthread_rwlock_init(&rwlock, NULL);

// 读取加锁
pthread_rwlock_rdlock(&rwlock);

// 写入加锁
pthread_rwlock_wrlock(&rwlock);

// 解锁
pthread_rwlock_unlock(&rwlock);

// 销毁读写锁
pthread_rwlock_destroy(&rwlock);

2.3 条件变量

严格意义上来说，条件变量的主要作用不是处理线程同步, 而是进行线程的阻塞。如果在多线程程序中只使用条件变量无法实现线程的同步, 必须要配合互斥锁来使用。

线程可以等待某个条件变量的发生，如果条件不满足，则线程会阻塞等待，并在条件满足时被唤醒。

条件变量的接口通常包括 cond_init()、cond_wait()、cond_signal() 和 cond_broadcast()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <pthread.h>

// 初始化条件变量和关联的互斥锁
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

// 等待条件满足
pthread_mutex_lock(&mutex);
pthread_cond_wait(&cond, &mutex);
pthread_mutex_unlock(&mutex);

// 发送信号通知条件满足
pthread_cond_signal(&cond);

// 广播通知条件满足
pthread_cond_broadcast(&cond);

2.4 信号量

信号量是一种更为通用的同步原语，用来控制多个线程对共享资源的访问。

信号量本质上是一个非负的整数计数器，表示可用资源的数量。当资源被占用时，计数器减少；当资源释放时，计数器增加。

信号量通常分为两种类型：二进制信号量和计数信号量。

1. 二进制信号量（Binary Semaphore）：
   • 二进制信号量只能取两个值，通常是0和1，分别表示资源的可用和不可用状态。
   • 二进制信号量常用于实现互斥锁（Mutex），用于保护对临界区（Critical Section）的访问，确保同一时间只有一个线程可以访问共享资源。
2. 计数信号量（Counting Semaphore）：
   • 计数信号量可以取多个值，通常是一个非负整数，表示资源的可用数量。
   • 计数信号量常用于限制对资源的访问数量，例如线程池中限制并发执行的线程数量。

信号量提供了两种操作：P操作（等待信号量）和V操作（释放信号量），用于控制资源的访问和释放，也被称为PV原子操作：

• P操作：即信号量sem减一，若sem小于等于0则P操作被阻塞，直到sem变量大于0为止
• V操作：即信号量sem加一

信号量的接口通常包括 sem_init()、sem_wait()、sem_post() 和 sem_destroy()。

1. **sem_init()**：用于初始化一个信号量。

   1	cCopy codeint sem_init(sem_t *sem, int pshared, unsigned int value);

   • sem：指向要初始化的信号量的指针。
   • pshared：指定信号量是进程共享的还是线程共享的。可以传入 0 表示信号量是线程共享的，非零值表示信号量是进程共享的。
   • value：指定信号量的初始值。

2. **sem_destroy()**：用于销毁一个信号量。

   1	cCopy codeint sem_destroy(sem_t *sem);

   • sem：指向要销毁的信号量的指针。

3. **sem_wait()**：用于等待（阻塞）一个信号量。

   1	cCopy codeint sem_wait(sem_t *sem);

   • sem：指向要等待的信号量的指针。

4. **sem_post()**：用于释放一个信号量。

   1	cCopy codeint sem_post(sem_t *sem);

   • sem：指向要释放的信号量的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

#define NUM_THREADS 5

sem_t semaphore;

void *thread_func(void *arg) {
    int id = *((int *)arg);
    sem_wait(&semaphore);
    printf("Thread %d is printing.\n", id);
    sem_post(&semaphore);
    pthread_exit(NULL);
}

int main() {
    pthread_t threads[NUM_THREADS];
    int thread_args[NUM_THREADS];

    // 初始化信号量，初始值为1
    sem_init(&semaphore, 0, 1);

    // 创建多个线程
    for (int i = 0; i < NUM_THREADS; ++i) {
        thread_args[i] = i;
        pthread_create(&threads[i], NULL, thread_func, (void *)&thread_args[i]);
    }

    // 等待所有线程结束
    for (int i = 0; i < NUM_THREADS; ++i) {
        pthread_join(threads[i], NULL);
    }

    // 销毁信号量
    sem_destroy(&semaphore);

    return 0;
}

3. C++示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

#include <iostream>
#include <thread>
#include <mutex>
#include <shared_mutex>
#include <condition_variable>
#include <semaphore.h>
#include <unistd.h> // 用于 sleep 函数

using namespace std;

// 共享资源
int shared_data = 0;

// 互斥锁
mutex mtx;

// 读写锁
shared_mutex rw_mtx;

// 条件变量
condition_variable cond_var;
bool ready = false;

// 信号量
sem_t semaphore;

// 互斥锁示例
void mutex_example(int id) {
    mtx.lock();
    cout << "Thread " << id << " is accessing shared resource with mutex. Shared data: " << shared_data << endl;
    shared_data++;
    mtx.unlock();
}

// 读写锁示例
void rw_lock_example(int id) {
    if (id % 2 == 0) {
        // 读操作
        shared_lock<shared_mutex> lock(rw_mtx);
        cout << "Thread " << id << " is reading shared resource with read-write lock. Shared data: " << shared_data << endl;
    } else {
        // 写操作
        unique_lock<shared_mutex> lock(rw_mtx);
        cout << "Thread " << id << " is writing shared resource with read-write lock. Shared data: " << shared_data << endl;
        shared_data++;
    }
}

// 条件变量示例
void cond_var_example(int id) {
    unique_lock<mutex> lock(mtx);
    cond_var.wait(lock, []{ return ready; });
    cout << "Thread " << id << " is accessing shared resource with condition variable. Shared data: " << shared_data << endl;
    shared_data++;
}

// 信号量示例
void semaphore_example(int id) {
    sem_wait(&semaphore);
    cout << "Thread " << id << " is accessing shared resource with semaphore. Shared data: " << shared_data << endl;
    shared_data++;
    sem_post(&semaphore);
}

int main() {
    // 初始化信号量
    sem_init(&semaphore, 0, 1);

    // 创建线程
    thread t1(mutex_example, 1);
    thread t2(mutex_example, 2);
    thread t3(rw_lock_example, 3);
    thread t4(rw_lock_example, 4);
    thread t5(cond_var_example, 5);
    thread t6(cond_var_example, 6);
    thread t7(semaphore_example, 7);
    thread t8(semaphore_example, 8);

    // 通知条件变量
    sleep(1);
    {
        lock_guard<mutex> lock(mtx);
        ready = true;
    }
    cond_var.notify_all();

    // 等待线程结束
    t1.join();
    t2.join();
    t3.join();
    t4.join();
    t5.join();
    t6.join();
    t7.join();
    t8.join();

    // 销毁信号量
    sem_destroy(&semaphore);

    return 0;
}

4. 死锁

死锁（Deadlock）是指两个或多个进程(线程)在互相等待对方持有的资源而无法继续执行的情况。在死锁状态下，每个进程都在等待某个资源被释放，而该资源被其他进程所持有，导致所有进程都无法继续执行。

死锁发生的主要原因通常是由于多个进程同时持有某些资源，并且每个进程都在等待其他进程释放它所需要的资源。

一个程序只有一个进程，但可以拥有至少一个线程（主线程），这些线程共同拥有进程的地址空间。

C++11通过std::thread进行多线程编程

1. 构造函数

应用通常需要在多个文件描述符上阻塞：在键盘输入（stdin）、进程间通信以及很多文件之间协调I/O 。

在传统的IO模型中，每个IO操作都需要创建一个新的线程或进程来处理。因为单个进程无法同时在多个文件描述符上阻塞。

I/O多路复用支持一个线程同时监测多个文件描述符并且这个过程是阻塞的，当有IO操作可以进行时才唤醒线程进行处理，避免了频繁的线程创建和切换，提高了系统的效率。

多线程/多进程并发和IO多路复用的并发处理流程进行对比（服务器端）：

• 多线程/多进程并发

  • 主线程/父进程：调用 accept()监测客户端连接请求，如果没有新的客户端的连接请求，当前线程/进程会阻塞；如果有新的客户端连接请求解除阻塞，建立连接
  • 子线程/子进程：和建立连接的客户端通信。
    • 调用 read() / recv() 接收客户端发送的通信数据，如果没有通信数据，当前线程/进程会阻塞，数据到达之后阻塞自动解除
    • 调用 write() / send() 给客户端发送数据，如果写缓冲区已满，当前线程/进程会阻塞，否则将待发送数据写入写缓冲区中

• IO多路复用并发

  • 使用IO多路复用函数委托内核检测服务器端所有的文件描述符（通信和监听两类），检测过程会导致进程/线程的阻塞，如果检测到已就绪的文件描述符阻塞解除，并将这些已就绪的文件描述符传出

  • 根据类型对传出的所有已就绪文件描述符进行判断，并做出不同的处理

    • 监听的文件描述符：和客户端建立连接，此时调用accept()不会导致程序阻塞，因为监听的文件描述符是已就绪的（有新请求）

    • 通信的文件描述符：调用通信函数和已建立连接的客户端通信，调用 read() / recv() 不会阻塞程序，因为通信的文件描述符是就绪的，读缓冲区内已有数据；调用 write() / send() 不会阻塞程序，因为通信的文件描述符是就绪的，写缓冲区不满，可以往里面写数据

  • 对这些文件描述符继续进行下一轮的检测

Linux提供了三种I/O多路复用方案：select、poll和epoll

select

1

int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);

• nfds：待检测的文件描述符的数量，即监视的文件描述符集合中最大的文件描述符加1。
• readfds：指向一个集合，包含了希望监视其读操作的文件描述符。
• writefds：指向一个集合，包含了希望监视其写操作的文件描述符。
• exceptfds：指向一个集合，包含了希望监视错误异常的文件描述符。
• timeout：指定超时时间，即 select() 函数最多等待的时间。如果设置为 NULL，则表示一直等待，直到有事件发生；如果设置为 0，则表示立即返回。

返回值：

• 大于0：成功，返回集合中已就绪的IO总个数
• 等于-1：调用失败
• 等于0：没有就绪的IO

fd_set本质是一个数组，为了方便我们操作该数组，操作系统提供了以下函数：

1
2
3
4
5
6
7
8
9
10
11

/ 将文件描述符fd从set集合中删除 
void FD_CLR(int fd, fd_set *set); 

// 判断文件描述符fd是否在set集合中 
int  FD_ISSET(int fd, fd_set *set); 

// 将文件描述符fd添加到set集合中 
void FD_SET(int fd, fd_set *set); 

// 将set集合中, 所有文件描述符对应的标志位设置为0
void FD_ZERO(fd_set *set);

select() 函数的基本工作原理：

1. 当用户process调用select的时候，select会将需要监控的readfds集合拷贝到内核空间（假设监控的仅仅是socket可读），
2. 然后遍历自己监控的skb(SocketBuffer)，挨个调用skb的poll逻辑以便检查该socket是否有可读事件，
3. 遍历完所有的skb后，如果没有任何一个socket可读，那么select会调用schedule_timeout进入schedule循环，使得process进入睡眠。
4. 如果在timeout时间内某个socket上有数据可读了，或者等待timeout了，则调用select的process会被唤醒，接下来select就是遍历监控的集合，挨个收集可读事件并返回给用户了

需要注意的是，select() 函数有一些局限性，其中最主要的是：

• nfds 参数需要指定为待监视文件描述符的最大值加1，这意味着它的性能可能受到文件描述符数量的限制。
• select() 的效率可能会随着待监视的文件描述符数量的增加而下降。
• select() 函数的时间复杂度为 O(n)，因此在大规模文件描述符的情况下可能效率较低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>

int main() {
    fd_set readfds;
    struct timeval timeout;
    int fds[NUM_FDS] = {0}; // 存储文件描述符
    int maxfd = 0; // 最大文件描述符
    int retval, i;

    // 创建5个文件描述符（示例中使用stdin和stdout）
    for (i = 0; i < 5; ++i) {
        fds[i] = i < 3 ? STDIN_FILENO : STDOUT_FILENO; // 前三个是 stdin，后两个是 stdout
        if (fds[i] > maxfd) {
            maxfd = fds[i];
        }
    }

    // 清空文件描述符集合
    FD_ZERO(&readfds);

    // 将所有文件描述符加入读集合
    for (i = 0; i < 5; ++i) {
        FD_SET(fds[i], &readfds);
    }

    // 设置超时时间为5秒
    timeout.tv_sec = 5;
    timeout.tv_usec = 0;

    // 使用select()函数进行监听
    retval = select(maxfd + 1, &readfds, NULL, NULL, &timeout);

    if (retval == -1) {
        perror("select()");
        exit(EXIT_FAILURE);
    } else if (retval == 0) {
        printf("No data within 5 seconds.\n");
    } else {
        // 检查就绪的文件描述符
        for (i = 0; i < 5; ++i) {
            if (FD_ISSET(fds[i], &readfds)) {
                printf("Data is available from fd %d.\n", fds[i]);
            }
        }
    }

    return 0;
}

poll

poll的实现和select非常相似，只是描述fd集合的方式不同。poll使用pollfd结构而不是select的fd_set结构，这就解决了select中fds集合大小1024限制问题。但poll和select同样存在一个性能缺点就是包含大量文件描述符的数组被整体复制于用户态和内核的地址空间之间，而不论这些文件描述符是否就绪，它的开销随着文件描述符数量的增加而线性增大。

1
2
3
4
5
6
7

int poll(struct pollfd *fds, nfds_t nfds, int timeout);

struct pollfd {
    int fd;         // 文件描述符
    short events;   // 要监视的事件（可通过常量定义）
    short revents;  // 监视的事件中满足条件返回的事件（由内核填充）
};

• fds：一个指向 struct pollfd 结构体数组的指针，其中每个元素描述了一个要监视的文件描述符及其所关注的事件。struct pollfd有三个成员：
  • fd：委托内核检测的文件描述符
  • events：委托内核检测的fd事件（输入、输出、错误），它可以是以下几种事件的组合：
    • POLLIN：文件描述符可读。
    • POLLOUT：文件描述符可写。
    • POLLERR：发生错误。
    • POLLHUP：对端挂起。
  • revents：这是一个传出参数，数据由内核写入，存储内核检测之后的结果
• nfds：要监视的文件描述符的数量，类型实际是unsigned long
• timeout：指定超时时间，单位是毫秒。如果设置为负值，poll() 将会无限期等待，直到有事件发生；如果设置为 0，则 poll() 将立即返回，不管是否有事件发生。

返回值：

• -1：失败
• 大于0：表示检测的集合中已就绪的文件描述符的总个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <stdio.h>
#include <stdlib.h>
#include <poll.h>
#include <unistd.h>

#define NUM_FDS 5

int main() {
    struct pollfd fds[NUM_FDS];
    int timeout = 5000; // 5秒超时

    // 创建5个文件描述符（示例中使用 stdin 和 stdout）
    for (i = 0; i < NUM_FDS; ++i) {
        fds[i].fd = i < 3 ? STDIN_FILENO : STDOUT_FILENO; // 前三个是 stdin，后两个是 stdout
        fds[i].events = i < 3 ? POLLIN : POLLOUT; // 前三个监视读事件，后两个监视写事件
    }

    // 使用 poll() 函数进行监听
    int retval = poll(fds, NUM_FDS, timeout);

    if (retval == -1) {
        perror("poll()");
        exit(EXIT_FAILURE);
    } else if (retval == 0) {
        printf("No data within 5 seconds.\n");
    } else {
        // 检查就绪的文件描述符
        for (i = 0; i < NUM_FDS; ++i) {
            if (fds[i].revents & POLLIN) {
                printf("Data is available from fd %d.\n", fds[i].fd);
            }
            if (fds[i].revents & POLLOUT) {
                printf("Ready to write data to fd %d.\n", fds[i].fd);
            }
        }
    }

    return 0;
}

epoll

epoll 是 Linux 中高性能的事件通知机制，它可以监视多个文件描述符的 I/O 事件，并在这些文件描述符上发生事件时通知应用程序。

epoll把用户关心的文件描述符上的事件放在内核里的一个事件表中，从而无须像select和poll那样每次调用都要重复传入文件描述符集或事件集。但epoll需要使用一个额外的文件描述符，来唯一标识内核中的这个事件表 。这个文件描述符通过epoll_create或epoll_create1创建

创建epoll实例

1
2
3

#include ＜sys/epoll.h＞
int epfd = epoll_create(int size);
int epfd = epoll_create1(int flags)	;

size 参数指定了 epoll 实例的大小，通常设置为大于零的值即可。在 Linux 2.6.8 之前的版本中，该参数没有意义，但是现在已经被忽略。

flags 参数是一个位掩码，用于指定一些选项。目前支持的选项只有一个：EPOLL_CLOEXEC，用于在创建 epoll 实例时设置 close-on-exec 标志。如果设置了这个选项，当调用 exec 函数执行其他程序时，内核会自动关闭该 epoll 实例。简单地创建一个 epoll 实例，可以将 flags 参数设置为 0。

当我们调用 epoll_create 函数创建一个 epoll 实例时，实际上是在内核中创建了一个数据结构来表示这个 epoll 实例。epoll 实例用于存储被监听的文件描述符及其相关信息，例如需要监听的事件类型、文件描述符的状态等。每个 epoll 实例都有一个唯一的标识符，通过这个标识符可以在用户空间中操作这个 epoll 实例。

操作内核事件表

• 事件表是 epoll 实例内部的数据结构，用于存储被监听的文件描述符的事件和状态。在 epoll 中，一个文件描述符可以关注多种类型的事件，主要包括可读事件（EPOLLIN）、可写事件（EPOLLOUT）、对端关闭事件（EPOLLRDHUP）等。当文件描述符上发生了关注的事件时，内核会通知用户程序进行相应的处理。 文件描述符的状态通常指的是其当前的就绪状态，即是否有事件发生或准备好进行IO操作。当文件描述符上有事件发生时，它的状态会被标记为就绪，用户程序可以通过 epoll_wait 函数等待并获取就绪的文件描述符列表，进行相应的操作。
• 在注册(EPOLL_CTL_ADD)文件描述符和事件时，这些信息会被存储到事件表中。事件表通常采用高效的数据结构（如红黑树）来组织，以便快速地查询、添加和删除事件。
• 当文件描述符上有事件发生时，内核会在事件表中查找对应的文件描述符，并更新其状态。

1

int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);

参数：

• epfd 是 epoll 实例的文件描述符。
• op 是操作类型，用三个宏来表示：
  • EPOLL_CTL_ADD：注册新的 fd 到 epfd 中；
  • EPOLL_CTL_MOD ：修改已经注册的fd的监听事件；
  • EPOLL_CTL_DEL：从 epfd 中删除一个 fd；
• fd 是需要向内核事件表中添加/修改/删除的文件描述符。
• event 是指向 epoll_event 结构的指针，告诉内核要监听什么事件。定义如下：

1
2
3
4

struct epoll_event {
    uint32_t events;  // 表示事件的类型
    epoll_data_t data; // 与事件相关的数据
};

epoll_event 结构包含两个成员：

1. events：是一个 32 位无符号整数，表示事件的类型。可以是下列宏的组合：
   • EPOLLIN：表示文件描述符上有数据可读。
   • EPOLLOUT：表示文件描述符可以进行写操作。
   • EPOLLRDHUP：表示对端断开连接。
   • EPOLLERR：表示发生错误。
   • EPOLLHUP：表示发生挂起事件。
   • EPOLLET：设置为边缘触发模式。
   • EPOLLONESHOT：设置为单次触发模式。
2. data：表示事件的数据，它是一个联合体 epoll_data_t，可以是一个文件描述符（fd）或者一个指针（ptr）。具体定义如下：

1
2
3
4
5
6

typedef union epoll_data {
    void    *ptr;    // 指针类型
    int      fd;     // 文件描述符类型
    uint32_t u32;    // 32 位无符号整数类型
    uint64_t u64;    // 64 位无符号整数类型
} epoll_data_t;

epoll_data 联合体允许用户在事件中传递一些附加的数据。

• 如果事件类型是 EPOLLIN 或 EPOLLOUT，则通常使用 fd 成员来表示文件描述符；

• 如果需要传递其他类型的数据，可以使用 ptr 成员来存储一个指针，或者使用 u32 或 u64 来存储一个整数值。

返回值：

• 成功时，返回 0。
• 失败时，返回 -1，并设置相应的errno。

示例：添加一个文件描述符到内核事件表中

1
2
3
4
5
6
7
8

struct epoll_event event;
event.events = EPOLLIN; // 指定事件为可读事件
event.data.fd = fd;     // 文件描述符

if (epoll_ctl(epoll_fd, EPOLL_CTL_ADD, fd, &event) == -1) {
    perror("epoll_ctl: add");
    exit(EXIT_FAILURE);
}

等待事件发生

• epoll_wait 调用会阻塞程序直到事件发生或者超时。

• 如果有事件发生，**epoll_wait 将把这些事件复制到 events 数组中**，并返回发生事件的数量。

• events 数组中的每个元素都是一个 epoll_event 结构，其中包含了发生事件的文件描述符及其事件类型。

1

int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);

参数：

• maxevents 是 events 数组的大小，表示最多可以存储多少个事件。
• timeout 是超时时间，以毫秒为单位。传递 -1 将一直阻塞等待事件，传递 0 将立即返回。

返回值：

• 如果没有事件发生，且超时时间到达，则返回 0。
• 如果有事件发生，返回发生事件的数量。

示例：

1
2
3
4
5
6
7
8
9
10
11

struct epoll_event events[MAX_EVENTS];
int nfds = epoll_wait(epoll_fd, events, MAX_EVENTS, -1);
if (nfds == -1) {
    perror("epoll_wait");
    exit(EXIT_FAILURE);
}

// 处理发生的事件
for (int i = 0; i < nfds; ++i) {
    // 处理 events[i].data.fd 对应的文件描述符的事件
}

示例代码

server端：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <arpa/inet.h>
#include <sys/epoll.h>

#define PORT 8080
#define MAX_EVENTS 10
#define BUFFER_SIZE 1024

int main() {
    int server_fd, new_socket, epoll_fd, nfds;
    struct sockaddr_in address;
    struct epoll_event event, events[MAX_EVENTS];
    char buffer[BUFFER_SIZE];

    // Creating socket file descriptor
    if ((server_fd = socket(AF_INET, SOCK_STREAM, 0)) == 0) {
        perror("socket failed");
        exit(EXIT_FAILURE);
    }

    address.sin_family = AF_INET;
    address.sin_addr.s_addr = INADDR_ANY;
    address.sin_port = htons(PORT);

    // Forcefully attaching socket to the port 8080
    if (bind(server_fd, (struct sockaddr *)&address, sizeof(address)) < 0) {
        perror("bind failed");
        exit(EXIT_FAILURE);
    }
    if (listen(server_fd, 5) < 0) {
        perror("listen");
        exit(EXIT_FAILURE);
    }

    epoll_fd = epoll_create1(0);
    if (epoll_fd == -1) {
        perror("epoll_create1");
        exit(EXIT_FAILURE);
    }

    event.events = EPOLLIN;
    event.data.fd = server_fd;
    if (epoll_ctl(epoll_fd, EPOLL_CTL_ADD, server_fd, &event) == -1) {
        perror("epoll_ctl: server_fd");
        exit(EXIT_FAILURE);
    }

    while (1) {
        nfds = epoll_wait(epoll_fd, events, MAX_EVENTS, -1);
        if (nfds == -1) {
            perror("epoll_wait");
            exit(EXIT_FAILURE);
        }

        for (int i = 0; i < nfds; ++i) {
            if (events[i].data.fd == server_fd) {
                new_socket = accept(server_fd, NULL, NULL);
                if (new_socket == -1) {
                    perror("accept");
                    exit(EXIT_FAILURE);
                }

                event.events = EPOLLIN | EPOLLET;
                event.data.fd = new_socket;
                if (epoll_ctl(epoll_fd, EPOLL_CTL_ADD, new_socket, &event) == -1) {
                    perror("epoll_ctl: new_socket");
                    exit(EXIT_FAILURE);
                }
            } else {
                int client_socket = events[i].data.fd;
                int valread = read(client_socket, buffer, BUFFER_SIZE);
                if (valread == 0) {
                    // Client disconnected
                    close(client_socket);
                    epoll_ctl(epoll_fd, EPOLL_CTL_DEL, client_socket, NULL);
                } else {
                    printf("Client: %s\n", buffer);
                    send(client_socket, buffer, valread, 0);
                }
            }
        }
    }

    close(server_fd);
    return 0;
}

1. 首先，服务器创建一个 TCP 套接字 server_fd，并将其绑定到本地的 8080 端口上。然后开始监听连接请求。
2. 创建了一个 epoll 实例 epoll_fd，并将服务器的监听套接字 server_fd 添加到 epoll 实例中，以便监视它上面的事件（主要是可读事件）。
3. 进入一个无限循环，用于等待并处理发生在 epoll 实例中的事件。每次循环开始时，调用 epoll_wait 函数等待事件发生。
4. 当有事件发生时，epoll_wait 返回并填充一个 events 数组，其中包含了发生的事件。
5. 遍历 events 数组，对每一个事件进行处理。如果事件是发生在服务器监听套接字 server_fd 上的可读事件，说明有新的客户端连接请求到达了。
6. 对新的客户端连接请求，服务器调用 accept 函数接受连接，创建一个新的套接字 new_socket 用于与客户端通信，并将新套接字添加到 epoll 实例中。
7. 如果事件不是发生在监听套接字上的，则说明是已连接的客户端套接字上发生了可读事件，这表示客户端发送了数据。
8. 服务器尝试从客户端套接字中读取数据，并进行处理。如果读取到的数据长度为 0，说明客户端已经关闭了连接，服务器关闭客户端套接字，并从 epoll 实例中删除该套接字。
9. 循环继续，等待下一轮事件发生。

信号是一种软件中断，它提供了异步事件的处理机制。信号作为一种进程间通信（IPC）的基本形式，而一个进程可以给另一个进程发送信号。信号本质上是一个整数，不同的信号对应不同的值，由于信号的结构简单所以天生不能携带很大的信息量，但是信号在系统中的优先级是非常高的。

每个信号都有一个以SIG为前缀的符号名称。信号的编号从1开始（通常是SIGHUP）线性增加。总共有大约31个
信号，但是大多数的程序只用到了它们中的一少部分。

信号有三种状态：产生、未决、递达

产生：键盘输入, 函数调用, 执行shell命令, 对硬件进行非法访问都会产生信号

未决：信号产生, 但还没有被处理

递达：信号被处理后

信号相关函数

**signal()**：该函数用于设置信号处理函数，其原型为：

1
2

#include <signal.h>
void (*signal(int signum, void (*func)(int)))(int);

它接受两个参数，signum 表示要捕获的信号类型，func 表示信号处理函数的指针。当收到指定的信号时，系统将调用指定的处理函数。

**kill()**：用于向指定的进程发送信号。其原型为：

1

int kill(pid_t pid, int sig);

pid 参数指定了目标进程的进程ID，sig 参数指定了要发送的信号类型。

**raise()**：用于向当前进程发送信号。其原型为：

1

int raise(int sig);

sig 参数指定了要发送的信号类型。

**abort()**：给当前进程发送一个固定信号 (SIGABRT)，函数原型：

1
2

#include <stdlib.h>
void abort(void);

调用 abort() 函数可以快速终止进程，并进行相应的清理工作

**sigpending()**：用于获取当前进程挂起的信号集。其原型为：

1

int sigpending(sigset_t *set);

它将当前未决的信号放入由 set 参数指向的信号集中

**sigprocmask()**：用于检查或修改当前进程的信号屏蔽字。其原型为：

1

int sigprocmask(int how, const sigset_t *set, sigset_t *oldset);

通过 sigprocmask() 函数可以设置当前进程的信号屏蔽字，从而阻塞或解除阻塞特定的信号。

1. 进程概述

程序：就是磁盘上的可执行文件文件, 并且只占用磁盘上的空间，是一个静态的概念

进程：是处于执行状态的程序以及相关资源的总称。每个运行的进程的都对应一个属于自己的虚拟地址空间，这是一个动态的概念

PCB进程控制块

内核在linux中通过进程控制块（Process Control Block，PCB）来管理进程。PCB实际是内核中名为task_struct的结构体，它包含了进程的所有信息，包括进程的状态、程序计数器、内存分配情况、打开文件列表、调度信息等。如：

• 进程标识符PID：每一个进程都一个唯一的进程ID，类型为 pid_t,，本质是一个int类型。

• 程序计数器PC：存储了进程当前执行的指令地址。当进程被中断或调度器选择该进程执行时，CPU会从程序计数器指向的地址开始执行指令。

• 文件描述符表：存储了进程打开的所有文件对应的文件描述符。

• 进程的状态：描述了进程当前所处的状态，如初始态、就绪态、运行态、阻塞态、终止态。

• 进程工作目录

• umask掩码：创建新文件时，通过这个掩码屏蔽某些用于对文件的操作权限

• 用户id和组id：当前进程所属用户及用户组

2. 进程创建

在Linux系统中，当前进程调用fork()就会创建一个子进程，fork()调用一次会返回两次，一次是向父进程返回子进程的进程ID，一次向子进程返回0。函数原型为：

1
2

#include <unistd.h>
pid_t fork(void);

在调用 fork() 后，操作系统会复制父进程的所有资源（包括内存、文件描述符、堆栈等），并将它们分配给新创建的子进程，子进程接着从 fork() 调用之后的位置继续执行。

通过getpid()能查看当前进程ID，调用getppid查看父进程的ID

1
2
3

#include <unistd.h>
pid_t getpid(void)
pid_t getppid(void)

Linux的fork()使用写时拷贝技术(copy on write–COW)实现，是一种推迟甚至免除复制数据的技术。

父子进程共享同一段内存，只有在其中一个进程试图修改该页的内容时才会执行实际的复制操作。

通过这种方式能够减少内存复制的开销，特别是在多个进程之间共享大块内存时，可以显著减少内存占用和提高性能。

3. exec函数

一般进程在创建完毕后会调用exec()读取一个可执行文件并将其载入地址空间开始运行，此时该进程的代码段、数据段、堆栈等完全替换为新程序，进程ID保持不变。

exec函数共有7中不同的变体，分别是execl、execv、execle、execve、execlp、execvp、fexecve。它们的主要区别在于传递参数的方式以及如何指定环境变量。常用的是execl()和execlp()

1
2
3
4

#include <unistd.h>

int execl(const char *path, const char *arg, ... /* (char  *) NULL */);
int execlp(const char *file, const char *arg, ... /* (char  *) NULL */);

参数:

• path: 要启动的可执行程序的路径, 推荐使用绝对路径
• arg: 启动的进程的名字, 可以随意指定, 一般和要启动的可执行程序名相同
• … : 要执行的命令需要的参数，可以写多个，最后以 NULL 结尾，表示参数指定完了。

返回值：

• 成功：无返回值；
• 失败：返回 -1

4. 进程终止

进程的常见终止方式：

• main函数中执行return语句
• 调用exit()或_exit()

函数的参数相当于退出码, 如果参数值为 0 程序退出之后的状态码就是0, 如果是100退出的状态码就是100。

1
2

#include <stdlib.h>
void exit(int status)

• exit(0)/return 0表示程序以成功状态结束，并返回给操作系统一个退出码为 0。

• exit(EXIT_FAILURE)/return 1表示程序已失败状态结束，并返回给操作系统一个非0的退出码。

5. 进程控制

5.1 孤儿进程

在一个启动的进程中创建子进程，这时候父子进程同时运行，当父进程结束或者被终止时，而子进程还在继续执行，这种情况下子进程被称为孤儿进程。

这种情况下，操作系统会将该子进程的父进程设置为init进程（在Linux系统中PID为1的init进程）。init进程会接管孤儿进程并负责它的管理。

那么系统为什么要接管这个孤儿进程呢？在子进程退出的时候, 进程中的用户区可以自己释放, 但是进程内核区的PCB资源自己无法释放，必须要由父进程来释放子进程的PCB资源。

5.2 僵尸进程

僵尸进程指已经终止执行的子进程，但是其父进程还未对其进行善后处理（即收回其占用的系统资源和进程表中的条目），僵尸进程仍然在进程表中存在，但是它已经停止了执行，并且释放了大部分系统资源，仅保留一些基本信息，例如进程ID和终止状态。

5.3 进程回收(wait/waitpid)

要解决僵尸进程问题，父进程通常需要调用 wait() 或 waitpid() 等系统调用来等待子进程的终止，并获取其终止状态，然后将其彻底清理掉。

1
2
3
4

#include <sys/wait.h>

pid_t wait(int *status);
pid_t waitpid(pid_t pid, int *status, int options);

调用wait()/waitpid()的进程可能会发生：

• 如果其所有子进程仍在运行，则阻塞
• 如果一个子进程已终止，正等待父进程获取终止状态，则取得该子进程的终止状态立即返回
• 如果没有任何子进程，则立即出错返回

waitpid() 可以看做是 wait() 的升级版，通过该函数可以控制回收子进程资源的方式是阻塞还是非阻塞，另外还可以通过该函数进行精准打击，可以精确指定回收某个或者某一类或者是全部子进程资源。

• pid:

  • -1时，同wait()一样
  • 0时，回收当前进程的所有子进程
  • 大于0时，指定回收ID为pid的子进程

• status: NULL, 和wait的参数是一样的

• options: 控制函数是阻塞还是非阻塞，0表示阻塞， WNOHANG表示非阻塞

6. 进程间通信

Linux支持的进程间通信机制包括管道、命名管道、信号量、消息队列、共享内存、套接字

6.1 管道

管道是一种半双工的通信方式，分为匿名管道pipe和命名管道FIFO两种。匿名管道只存在于内存中，且只能用于具有亲缘关系的进程，通常用于父子进程之间。命名管道（FIFO）则是一种特殊的文件，可以用于不同进程之间的通信。

pipe() 系统调用创建一个管道，返回两个文件描述符，一个用于读取数据，另一个用于写入数据。通常与 fork() 系统调用一起使用，创建一个父子进程，然后使用 dup() 复制文件描述符以便父子进程可以在管道中进行通信，最后使用 close() 关闭不需要的文件描述符。

1
2
3

#include <unistd.h>
// 创建一个匿名的管道, 得到两个可用的文件描述符
int pipe(int pipefd[2]);

参数：

• pipefd[0]: 对应管道读端的文件描述符，通过它可以将数据从管道中读出
• pipefd[1]: 对应管道写端的文件描述符，通过它可以将数据写入到管道中

返回值：成功返回0，失败返回-1

使用 mkfifo() 创建一个命名管道，然后可以使用 open() 打开该命名管道，之后使用 read() 和 write() 进行数据的读写操作，最后使用 close() 关闭文件描述符。

1
2
3

#include <sys/stat.h>
// int open(const char *pathname, int flags, mode_t mode);
int mkfifo(const char *pathname, mode_t mode);

参数:
pathname: 要创建的有名管道的名字
mode: 文件的操作权限, 和open()的第三个参数一个作用，最终权限: (mode & ~umask)
返回值：创建成功返回 0，失败返回 -1

6.2 消息队列

消息队列是一种通过消息传递进行通信的机制，允许一个进程向队列发送消息，其他进程从队列中接收消息。

使用 msgget() 创建或打开一个消息队列，然后使用 msgsnd() 发送消息到队列中，使用 msgrcv() 从队列中接收消息，使用 msgctl() 控制消息队列的属性。

6.3 信号量

信号量是一种用于进程间同步和互斥的机制，通常用于解决共享资源的访问问题

使用 semget() 创建或打开一个信号量集，然后使用 semop() 对信号量进行操作，包括对信号量的增减、等待等操作，最后使用 semctl() 控制信号量集的属性。

6.4 共享内存

共享内存是一种高效的进程间通信方式，允许多个进程直接访问同一块内存区域，从而实现数据共享。在所有进程间通信的方式中共享内存的效率是最高的。

使用 shmget() 创建或打开一个共享内存段，然后使用 shmat() 将共享内存连接到当前进程的地址空间，之后可以直接在内存中进行读写操作，最后使用 shmdt() 断开共享内存的连接，使用 shmctl() 控制共享内存的属性。

6.5 套接字

套接字是一种在网络编程中常用的进程间通信方式，它允许不同主机上的进程进行通信

使用 socket() 创建一个套接字，然后使用 bind() 绑定套接字到特定的地址和端口，使用 listen() 监听连接请求，使用 accept() 接受连接请求并创建新的套接字，然后使用 connect() 连接到远程主机的套接字，之后可以使用 send() 和 recv() 进行数据的发送和接收，最后使用 close() 关闭套接字。

7. 守护进程

守护进程（Daemon Process）是在后台运行的一种特殊类型的进程，它通常在系统启动时启动，并在整个系统运行期间持续执行，独立于控制终端并且周期性地执行某种任务或等待处理某些发生的事件。

如何创建守护进程

1. 调用fork()，创建新的子进程
2. 在父进程中调用exit()。这会确保父进程的父进程（即守护进程的祖父进程）在其子进程结束时会退出，保证了守护进程的父进程不再继续运行，而且守护进程不是首进程。最后一点是成功完成下一步骤的前提
3. 通过调用 setsid() 函数创建一个新的会话，使守护进程成为会话的领头进程，并且摆脱终端的控制。
4. 在子进程中，通过调用 umask() 函数来修改文件掩码，以确保守护进程创建的文件具有合适的权限。
5. 为了确保守护进程不会影响其他进程的工作目录，一般会将工作目录切换到根目录
6. 关闭守护进程继承的文件描述符，以避免其影响其他进程或继承终端。
7. 为了确保守护进程能够正常退出或重新加载配置等，需要注册一些信号处理函数，比如 SIGTERM 和 SIGHUP 信号。
8. 在守护进程初始化完成后，执行它的核心功能，比如提供网络服务、定时任务等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>
#include <signal.h>

void signal_handler(int sig) {
    // 处理信号
}

int main() {
    // 创建子进程
    pid_t pid = fork();

    if (pid < 0) {
        // 创建失败
        exit(EXIT_FAILURE);
    }

    if (pid > 0) {
        // 父进程退出
        exit(EXIT_SUCCESS);
    }

    // 在子进程中执行以下操作
    // 创建一个新会话
    if (setsid() < 0) {
        exit(EXIT_FAILURE);
    }

    // 修改文件掩码
    umask(0);

    // 改变工作目录
    chdir("/");

    // 关闭文件描述符
    close(STDIN_FILENO);
    close(STDOUT_FILENO);
    close(STDERR_FILENO);

    // 注册信号处理函数
    signal(SIGTERM, signal_handler);
    signal(SIGHUP, signal_handler);

    // 执行守护进程的核心功能
    while (1) {
        // Do something
        sleep(1);
    }

    return 0;
}