数组

什么是大O

n表示数据规模，则表示运行算法所需要执行的指令数，和成正比。

一个算法有多个步骤，每个步骤规模相同但时间复杂度不同，最终的时间复杂度以最高的那个为准。

对数据规模的概念

如果想要在1s之内解决问题：

• 的算法可以处理大约级别的数据；
• 的算法可以处理大约级别的数据；
• 的算法可以处理大约级别的数据；

这个结论只是执行简单的数据操作，实际还需要再低估一下。

空间复杂度

• 多开一个辅助数组：;
• 多开一个辅助的二维数组：
• 多开常数空间：;

需要注意：递归调用是有空间代价的，递归的深度就是空间复杂度。

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

//计算n以内数据的和

//空间复杂度O(1)
int sum1(int n)
{
    assert(n >= 0);
    int ret = 0;
    for(int i=0;i<=n;i++)
    {
        ret += i;
    }
    return ret;
}

//递归调用：空间复杂度O(n)
int sum2(int n)
{
    assert(n>=0);
    if(n == 0)
        return 0;

    return n + sum2(n-1);
}

简单的时间复杂度分析

O(1)

常数级的算法很简单，没有数据规模的变化

1
2
3
4
5
6
7

// O(1)
void swapTwoInts(int &a , int &b){
    int temp = a;
    a = b;
    b = temp;
    return;
}

O(n)

O(n)的算法典型的特征就是有个循环，并且循环的次数和n相关。

其实正常来说，应该是，其中C是个常数，且不一定大于1

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

// O(n)
int sum(int n){

    assert(n >= 0);

    int ret = 0;
    for( int i = 0 ; i <= n ; i ++ )
        ret += i;
    return ret;
}

//字符串反转，只需要进行1/2次的swap操作即可
void reverse(string &s){

    int n = s.size();
    for(int i = 0 ; i < n/2 ; i ++)
        swap( s[i] , s[n-1-i] );
    return;
}

O(n^2)

见到算法内部有双重循环，每层循环都是n相关基本就八九不离十了。

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

//选择排序算法
void selectionSort(int arr[], int n){

    for(int i = 0 ; i < n ; i ++){
        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }
}

千万要注意两层循环都要和n相关，不要看到双重循环就认为是

1
2
3
4
5
6
7
8
9
10

//第二重循环哪怕循环300w次，这个也是O(n)
void printInformation(int n){

    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= 30 ; j ++ )
            cout << "Class " << i << " - " << "No. " << j << endl;
    return;
}

O(logn)

经典的二分查找法：

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

//二分查找法
int binarySearch(int arr[], int n, int target){

    int l = 0, r = n-1;
    while( l <= r ){
        int mid = l + (r-l)/2;
        if(arr[mid] == target) return mid;
        if(arr[mid] > target) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

将数字整形转化为字符串：

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

string intToString(int num){

    string s = "";
    string sign = "+";
    if(num < 0){
        num = -num;
        sign = "-";
    }

    while(num){
        s += '0' + num % 10;
        num /= 10;
    }

    if(s == "")
        s = "0";

    reverse(s);
    if(sign == "-")
        return sign + s;
    else
        return s;
}

分析算法思想，核心在" num /= 10"步中，就是n经过几次“除以10”操作后等于0，那么就是;

虽然上面两个例子，一个是以2为底，一个是以10为底，但都是，这个可以通过对数函数的换底公式来理解：有换底公式，可见和之间只相差一个常数，在时间复杂度下可以直接理解为

还需要注意，双重循环也可能出现logN的复杂度，需要注意量增长的规模：

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

//复杂度:O(nlogn)
void hello(int n){

    for( int sz = 1 ; sz < n ; sz += sz )
        for( int i = 1 ; i < n ; i ++ )
            cout << "Hello, Algorithm!" << endl;
}

//外层循环每次增长可以理解为sz*2
//其实就可以理解为n经过几次“除以2”的操作后等于1，外层循环复杂度O(logn)
//内层循环复杂度是O(n)
//合起来是O(nlogn)



//判断是否为素数
// O(sqrt(n))
bool isPrime(int num){

    if( num <= 1 ) return false;
    if( num == 2 ) return true;
    if( num % 2 == 0 ) return false;

    for(int x = 3 ; x * x <= num ; x += 2)
        if( num%x == 0 )
            return false;

    return true;
}

//

递归算法的复杂度分析

面对递归算法需要具体问题具体分析。

递归中只会进行一次递归调用

如果递归函数中只进行一次递归调用，递归深度为depth，在每个递归函数中的时间复杂度为T，则总体的时间复杂度为，既只需关注递归的深度

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

//递归调用的二分查找法
int binarySearch(int arr[], int l, int r, int target){

    if(l > r)
        return -1;

    int mid = l + (r - l) / 2;
    if(arr[mid] == target)
        return mid;
    else if(arr[mid] > target)
        return binarySearch(arr, l, mid - 1, target);
    else
        return binarySearch(arr, mid + 1, r, target);

}

  二分查找法很容易用递归实现，上述代码每次调用时，内部要么直接返回，要么数组左半边调用递归，要么数组右半边调用递归，只会调用一次，所以分析时间复杂度只有看递归的深度即可。

  每次调用数组减少一半，是典型的logn情况，所以复杂度为

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

// sum,O(n)
int sum(int n){

    assert(n >= 0);

    if(n == 0)
        return 0;
    return n + sum(n - 1);
}

// 求x的n次方：O(logn)
double pow(double x, int n){

    assert(n >= 0);

    if(n == 0)
        return 1.0;

    double t = pow(x, n / 2); //每次减半，logn
    if(n % 2)
        return x * t * t;

    return t * t;
}

递归中进行多次递归调用

当递归中有多次递归调用时，就需要关注递归调用的次数了。如果递归中只调用一次，深度就是次数，但如果调用了多次，那么深度和次数就是两个概念了。

1
2
3
4
5
6
7
8
9
10
11

//O(2^n)
//这个是指数级的算法，是个非常慢的算法
int f(int n)
{
    assert(n >= 0);

    if(n == 0)
        return 1;

    return f(n-1) + f(n-1);
}

均摊复杂度分析

  有时候会遇到这种情况：解决某个问题时运用了一系列算法，某个算法的复杂度很高，但这个算法可以降低其他算法的复杂度，这时候就需要计算分摊复杂度。

  均摊复杂度的经典问题就是动态数组vector。

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

template <typename T>
class MyVector{

private:
    T* data;
    int size;       // 存储数组中的元素个数
    int capacity;   // 存储数组中可以容纳的最大的元素个数

    // 复杂度为 O(n)
    void resize(int newCapacity){

        assert(newCapacity >= size);
        T *newData = new T[newCapacity];
        for( int i = 0 ; i < size ; i ++ )
            newData[i] = data[i];
        delete[] data;

        data = newData;
        capacity = newCapacity;
    }

public:
    MyVector(){

        data = new T[100];
        size = 0;
        capacity = 100;
    }

    ~MyVector(){

        delete[] data;
    }

    // 平均复杂度为 O(1)
    void push_back(T e){
        //当元素到达容量上限时，需要调用resize扩大空间
        if(size == capacity)
            resize(2 * capacity);

        data[size++] = e;
    }

    // 平均复杂度为 O(1)
    T pop_back(){

        assert(size > 0);
        size --;

        return data[size];
    }

};

  上面的代码只在push操作时resize了空间，但是没有在pop操作时resize空间。我们当然可以参考push操作，在pop到capacity一半时resize容量，但这里涉及一个问题，就是要防止复杂度震荡。

  考虑这个问题：当push到临界点时resize一倍空间，然后立即pop，此时又resize为一半，然后立即push，这种极端场景下时间复杂度无法均摊，会退化为。

  如果想避免这种场景，可以不再临界点处resize，当pop操作到达capacity的1/4处时，resize为1/2

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

// 平均复杂度为 O(1)
T pop_back(){

    assert(size > 0);
    T ret = data[size-1]; //这里一定要提前拿出来，resize操作会修改data
    size --;

    // 在size达到静态数组最大容量的1/4时才进行resize
    // resize的容量是当前最大容量的1/2
    // 防止复杂度的震荡
    if(size == capacity / 4)
        resize(capacity / 2);

    return ret;
}

VSCode的下载和安装

• 下载VSCode：vscode官网

  安装时有选项，推荐选择“添加到PATH”、“通过Code打开”、“添加到右键菜单”；

  安装完成后是英文版本，可以安装汉化插件。点击左侧扩展按钮，搜索安装[Chinese(Simplified)]，安装完成后右下角弹窗，点击重启后即可生效。

C++环境配置

  VSCode本质上就是一个轻量级文本编辑器，是不能够直接运行代码的，还需要额外进行配置。

方案一：安装MinGW

1. 下载MinGW-w64:MinGW;
2. 点击Toolchains targetting Win64--Personal Builds--mingw-builds--8.1.0--threads-posix--seh，单击下载里面的压缩包文件。
3. 解压到一个目录后，我们需要配置环境变量，在系统的环境变量中编辑Path，把“X:\mingw64\bin”的路径添加进去。

  上述操作完成后，我们的环境就配置完成了，VSCode会自动识别g++编译器。

方案二：复用Visual Studio的MSVC编译器

如果熟悉Visual Studio的话，可以直接复用MSVC编译器。

1、找到MSVC编译器路径，通常在

C:FilesVisual Studio\2022\14.x.x

2、配置VSCode使用MSVC：在VSCode中按Ctrl+Shift+P，输入“Edit Configurations”。在生成的c_cpp_properties.json中配置：

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

{
    "configurations": [
        {
            "name": "Win32",
            "includePath": [
                "${workspaceFolder}/**",
                "C:/Program Files/Microsoft Visual Studio/2022/Community/VC/Tools/MSVC/14.x.x/include/**"
            ],
            "defines": ["_DEBUG", "UNICODE", "_UNICODE"],
            "windowsSdkVersion": "10.0.22000.0",
            "compilerPath": "C:/Program Files/Microsoft Visual Studio/2022/Community/VC/Tools/MSVC/14.x.x/bin/Hostx64/x64/cl.exe",
            "cStandard": "c17",
            "cppStandard": "c++17",
            "intelliSenseMode": "windows-msvc-x64"
        }
    ],
    "version": 4
}

配置编译环境

需要安装如下的扩展：

• C/C++：提供语法高亮、智能感知、调试支持；
• C++ Themes：优化C++语法高亮；
• CMake Tools：如果使用CMake的话，需要安装这个；
• Code Runner：一键运行代码片段；

推荐安装以下扩展：

• GitLens：增强Git功能；
• Bracket Pair Colorizer：彩虹括号；
• Todo Tree：管理TODO注释；

创建和编译C++程序

• 在本地资源管理器中新建一个文件夹用来存放代码，然后用VSCode打开这个文件夹；
• 左边工作区中点击新建文件，新建一个C语言文件，例如“test.c”；
• 编写我们的程序，如hello world。
• 点击Ctrl+Shift+P，搜索“C/C++”，选择编辑配置(UI)。可以看到其中【编译器配置】中默认的是"cl.exe"，我们需要修改为之前安装的mingw64里的gcc.exe；同时【IntelliSense】模式需要修改为"Windows-gcc-x64"；
• 在代码页点击菜单栏的终端、配置任务，选择“C/c++:gcc.exe生成活动文件”，会生成一个"task.json"文件，此时就可以生成我们的代码了；
• 在代码页点击菜单栏终端、运行生成任务，使用gcc.exe生成活动文件。
• 我们可以在终端中运行，在菜单栏点击终端、新建终端，在窗口中输出".\test.exe"，回车后就可以运行了。

github使用

注册

Github官网上注册账号(Sign up)。注册时需要使用邮箱，本地配置时也需要邮箱账户，后续的git信息就会通过邮箱发送给用户。

配置公私钥

  git常常使用ssh协议进行传输，需要配置公钥和私钥。

文件的逻辑结构

文件类型

文件的逻辑结构根据文件类型可以分为两类：

1. 有结构文件：常见的有文本文件、文档、媒体文件等
2. 无结构文件：常见的有二进制文件、链接库等

  有结构文件的文件内容由定长记录和可变长记录两部分组成。定长记录存储文件的格式、编码、文件描述等结构化数据项；可变长记录存储文件的具体内容。

  无结构文件也称为流式文件，文件内容长度以字节为单位。exe、dll、so文件都是无结构文件。

顺序文件

  顺序文件是指按顺序存放在存储介质中的文件。磁带就是典型的顺序文件存储介质，只能按顺序读取和写入文件。顺序文件是所有逻辑文件当中存储效率最高的。

  但由于顺序文件只能顺序读写，所以假如我们想要对文件内容进行增、删等操作，效率极其低下。

索引文件

  可变长文件不适合适使用顺序文件格式存储，所以为了解决这个问题发明了索引文件。索引文件需要配合索引表完成存储的操作。

辅存(磁盘)的存储空间分配

分配方式

连续分配

  如果一个文件存取的时候需要连续的扇区，就会把内存中连续的扇区分配给文件。

  连续分配只要求我们顺序的读取文件即可，所以读取操作非常容易，速度很快。但是对存储要求很高，要求满足容量的连续存储空间。

链接分配

  链接分配可以将文件存储在离散的盘块中，不再需要大块连续的存储空间，但需要额外的存储空间存储文件的盘块链接顺序。根据这个额外存储空间的不同，分为隐式链接和显式链接。

  隐式链接的方法中，隐式分配的下一个链接存储在当前盘块内，就像链表结点中的next指针。隐式链接很适合顺序访问，我们只要知道起始的盘块就可以依次遍历所有的盘块，但是隐式链接的随机访问效率很低，必须从头开始寻找。并且隐式链接的可靠性差，任何一个链接出问题都将影响整个文件。

  显式链接就不在当前盘块中指定下一个盘块的位置了，而是单独有一张表，存储物理盘块以及下一个盘块的地址数据。这张表叫FAT(File Allocation Table)，也就是我们平时说的FAT文件系统，显式链接就是FAT系统的工作原理。FAT也存在一些缺点：它不支持高效的直接存储，因为FAT的记录项非常多，磁盘越大FAT记录越大，存储时需要检索FAT表找到空闲位置。而且检索FAT表时需要将整个FAT加载到内存中，占用较大的存储空间。

索引分配

  把文件的所有盘块集中存储，存储盘块的位置称为索引。每个文件都拥有一个索引块，记录当前文件所有盘块信息，当我们读取某个文件时，只需要读取索引即可，不需要把整张表都加载到内存中。通过索引分配我们可以直接找到文件对应的盘块。文件较大时，索引分配具有明显的优势。

存储空间管理

空闲表

  空闲表可以表示某个空闲的盘块号内有多少个空闲盘块数。空闲盘曲的分配与内存的分配类似，也具有首次适应算法、循环适应算法等；回收过程也和内存回收类似。

空闲链表

  空闲链表把所有空闲盘曲组成一个空闲链表，每个链表节点存储空闲盘块和空闲的数目。存储的信息和空闲表一样，操作方式也和内存的空闲链表方式类似。

位示图

  位示图横向的是盘块，纵向的是磁道，每一个具体的盘块都有0或1的标记，0表示未使用，1表示已经被使用了。位示图优点很多，首先维护成本很低，只需要维护一张表即可；其次位示图可以非常容易的找到空闲盘块；位示图内部使用0/1比特位，占用的空间很小。

目录管理

  目录系统是树形结构存储，使得任何文件或目录都只有唯一路径

内存的分配与回收

  早期的计算机编程并不需要过多的存储管理，但随着计算机和程序越来越复杂，存储管理成为必要。存储管理需要确保计算机有足够的内存处理数据、确保程序可以从内存中获取一部分内存使用，并可以归还使用后的内存以供其他程序使用。

内存分配

• 单一连续分配：

  单一连续分配是最简单的内存分配方式，只能在单用户、单进程的操作系统使用。它把系统内存分为系统区和用户区，系统区内的内存只能够被操作系统使用，用户区内的内存只能被用户程序使用。这个分配方式已经过时不再使用了。

• 固定分区分配：

  固定分区分配是支持多道程序的最简单存储分配方式。内存被划分为若干固定大小的区域，每个分区只提供给一个程序使用，互不干扰。

• 动态分区分配：

  这是操作系统中比较常用的方法。根据进程实际需要，动态地分配内存空间。要支持这种分配方法，就需要相关的数据结构和分配算法:

  数据结构：

  假设主存中有若干分区，有些分区已经被使用，有些分区空闲。动态分区空闲表这个数据结构就可以记录分区的使用情况。

  还有动态分区空闲链数据结构，用一个双向链表的结构存储来存储当前系统中的空闲区域。

  算法：

  首次适应算法(FF)：主要使用空闲链的数据结构，每次进行内存分配的时候从链表头开始顺序查找适合的内存区域。遍历结束后发现没有合适的空闲区，则该次分配失败；如果找到了合适的空闲区，则把这块内存分配给进程使用。首次使用算法有个很大的问题：由于每次都是从头部开始遍历，使得头部的地址空间不断的被划分，导致头部地址可能出现大量碎片。对于这个问题，可以优化为循环适应算法，每次遍历结束后记录位置，下次遍历从这个位置开始，而不需要每次从头开始遍历。

  最佳适应算法：空闲链表按照容量大小进行排序，每次遍历空闲区链表时可以找到最佳的合适空闲区。这种算法可以有效避免大材小用的情况。

  快速适应算法：快速适应算法要求有多个空闲区链表，每个空闲区链表存储一种容量大小的空闲区。这样当我们需要某个大小的空闲区域时，就可以快速找到对应的链表取内存。

内存回收

  内存回收的场景可能会遇到下面四种场景：

  第一种场景是需要回收的区域和空闲区连在一起且正好在空闲区后面，这个场景非常简单，不需要新建空闲链表节点，只需要把空闲区的容量增大即可，把回收区的容量包括进去。

  第二种情况是需要回收的区域和空闲区连在一起，但在空闲区前面。这个场景也是将回收区和空闲区合并，合并而成的新的空闲区使用回收区的地址。

  第三种情况回收区恰好在两个空闲区之间，回收需要将空闲区1、空闲区2和回收区一起合并，然后新的空闲区地址使用空闲区1的地址。

  最后的场景就是单一的回收区，没有连接任何的空闲区，这种情况要为回收区创建新的空闲节点，然后把回收区插入到相应的空闲区链表中去。

段页式存储管理

  每个进程都有独立的进程空间，操作系统管理进程空间有三种管理方式：

页式存储管理

  计算机组成原理中有字和字块的概念，字和字块是相对内存条等物理设备的定义，而操作系统内存管理中的页面则是相对逻辑空间的定义。字块和页面都是指大小一样的一块内存。

  页式管理是将进程的逻辑空间划分成若干大小相同的页面，把相应的物理内存空间分成与页面大小相同的物理块。以进程为单位把进程空间装进物理内存中分散的物理块中。

  页式管理系统中需要了解内存碎片的概念。如下图所示，空闲链表中存有大小不同的空闲节点，如果需要申请一个页面大小的内存，节点1不够，只能使用节点2-3的一部分，这样就造成了内存碎片。所以页式存储管理的页面大小应该适中，过大的话难以分配，过小的话又会造成内存碎片多。一般情况下，页面大小为512B~8K。

  为了知道某个页面被分配到哪个字块，还需要了解页表的概念。页表记录进程逻辑空间和物理空间的映射关系。

  在现在计算机系统中，可以支持非常大的逻辑地址空间(~)，这样页表就会变得非常大，要占用非常大的内存空间。假设具有32位逻辑地址空间(寻址空间为即4G)的分页系统，规定页面大小为4KB，则每个进程页表中的页表项可达1M(4G/4KB=)个，如果每个页表项占用1Byte，每个进程仅仅页表就要占用1MB的内存空间。为应对这种情况，有了多级页表的设计.

  单纯的页式存储管理可能遇到的问题是，假如有一段连续的逻辑分布在多个页面中，将大大降低执行的效率。

段式存储管理

  段式存储管理将进程的逻辑空间划分成若干段，这种划分是非等分的。每一段的长度由进程内连续的逻辑长度决定，比如针对MAIN函数、子程序段X、子函数Y等，根据不同的长度分配不同的内存空间。

  我们也需要一个数据结构来保存逻辑空间到物理空间的映射，段式存储结构中的数据结构叫段表，由于段长度不同，所以相比页式存储管理，段表内多了一个段长。

  页式存储管理和段式存储管理相同点在于，都离散的管理了进程的逻辑空间，它们之间的不同点在于：

1. 页是物理单位，段是逻辑单位；
2. 分页是为了合理利用空间、分段是为了满足用户需求；
3. 页的大小由硬件固定，段的长度可动态变化
4. 页表信息是一维的，段表信息是二维的(需要记录段长度)

段页式存储管理

  结合了页式存储管理和段式存储管理，产生了段页式的存储管理。分页的优点在于虽然存在页内碎片，但相比分段来说提高了内存的利用率；分段的优点在于可以更好的满足用户需求。

  段页式存储管理首先将逻辑空间按照段式管理分成若干段，再把段内空间按页式管理分成若干页。页式管理的页地址由页号和业内偏移组成，段式管理的段地址由段号和段内偏移组成，段页式结合两者，段页地址由段号、段内页号、页内地址三者组成。

虚拟内存

  有些进程实际需要的内存很大，超过了物理内存的容量，而伴随着多道程序设计的出现，使得每个进程可用的物理内存更加稀缺。但由于现实的原因，不可能无限增加物理内存，物理内存总有不够用的时候，所以诞生了虚拟内存技术。虚拟内存是操作系统内存管理的关键技术，使得多道程序运行和大程序运行成为现实。虚拟内存技术把程序使用的内存进行划分，将暂时不使用的内存放置在辅存中。

程序的局部性原理

  局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。

  局部性原理是虚拟内存可以实现的原因之一。程序加载的时候，不需要把进程所有的逻辑空间都加载到内存中，只装载部分即可。如果需要访问页时发现页面不在内存中，则发出缺页中断，发起页面置换，置换后程序就可以继续运行下去。从用户层面看，程序仿佛拥有很大的空间，即是虚拟内存。虚拟内存实际上是对物理内存的补充，速度接近于内存，成本接近于辅存。

虚拟内存置换算法

• 先进先出算法(FIFO)
• 最不经常使用算法(LFU)
• 最近最少使用算法(LRU)

进程调度

  进程调度是指计算机通过决策决定哪个就绪进程可以获得CPU使用权。前提是多道程序设计。

  进程调度有两个步骤：

1. 保留旧进程的运行信息，请出旧进程；
2. 选择新进程，准备运行环境并分配CPU；

  操作系统提供了三个机制来负责进程调度：

• 就绪队列的排队机制：

  为了提高进程调度的效率，操作系统事先将就绪进程按照一定的方式排成队列，以便调度程序可以最快找到就绪进程。

• 选择运行进程的委派机制：

  调度程序以一定的策略选择就绪进程，将CPU资源分配给它。

• 新老进程的上下文切换机制：

  保存当前进程的上下文信息，装入被委派执行进程的运行上下文。

  如果进程调度触发时，老进程还没有执行完毕的场景怎么办？为此有两种进程调度的方式：

• 非抢占式的调度：

  处理器一旦分配给某个进程，就让该进程一直使用下去，调度程序不以任何原因抢占正在被使用的处理器。直到进程完成工作或因为IO阻塞才会让出处理器。

• 抢占式的调度：

  允许调度程序以一定的策略暂停当前运行的进程，保存好旧进程的上下文信息，分配处理器给新进程。

进程调度算法

• 先来先服务算法：

  这个算法比较简单，在就绪队列中按照先来先服务的原则，优先取出队列最前面的就绪进程来调度，之后依次执行。

• 短进程优先调度算法：

  调度程序优先选择就绪队列中估计运行时间最短的进程。短进程优先调度算法不利于长作业进程的执行。

• 高优先权优先调度算法：

  进程附带优先权，调度程序优先选择权重高的进程。这个算法使得紧迫的任务可以优先处理。

  系统中分为前台进程和后台进程，一般来说前台进程的优先级都比后台进程大，因为前台进程需要和用户交互，要保证用户使用时不会卡顿。

• 时间片轮转调度算法：

  按照先来先服务的原则排列就绪队列，然后每次从队列头部取出待执行的进程，分配一个时间片执行，每个进程分配的时间片都是一样的。这是相对公平的调度算法，但是不能保证及时响应用户操作。

死锁

  死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞现象。若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

死锁的产生

  第一个死锁产生的原因是资源竞争。当共享资源数量不满足各个进程需求时，各个进程之间就会因为共享资源的竞争而导致死锁。每个进程都在等待请求的资源被释放，但自身占用的资源又不会主动释放。如果此时增加多余的系统资源，死锁就会解开。

  第二个原因是进程调度顺序不当。如下图，进程1和进程2都要申请打印机和传真机资源。如果调度的顺序是A->B->C->D，那么就会发生死锁。如果适当的改变调度顺序，改为A->D->B->C，那么就可以正常调度。

  死锁产生的必要条件有四个，必须同时满足：

1. 互斥条件：进程对资源的使用是排他性的使用。某个资源只能由一个进程使用，其他进程需要使用只能等待。
2. 请求保持条件：进程至少保持一个资源，同时又提出新的资源请求。此时新资源被占用，请求被阻塞，但被阻塞的进程不释放自己保持的资源。
3. 不可剥夺条件：进程获得的资源在未完成使用前不能被剥夺，获得的资源只能由进程自身释放。
4. 环路等待条件：发生死锁时，必然存在“进程-资源”的环形等待链。

死锁的处理

预防死锁的方法

  死锁产生的必要条件有四个，我们只需要破坏其中一个或多个即可预防死锁产生。互斥条件我们不能破坏，其余三个我们都有方法破坏：

1. 摒弃请求保持条件：系统规定进程运行之前，一次性申请所有需要的资源。这样在进程运行期间不会再提出资源请求。
2. 摒弃不可剥夺条件：当一个进程请求新的资源得不到满足时，必须释放占有的资源。
3. 破坏环路等待条件：可用资源按照线性排列，申请必须按照需要递增申请，线性申请就不再形成环路。

银行家算法

  以银行借贷系统分配策略为基础的算法，是一个可操作的著名的避免死锁的算法。客户申请的贷款是有限的，每次申请需声明最大资金量。银行在能够满足贷款时，都应该给用户贷款；客户在使用贷款后，能够及时归还贷款。

  银行家算法需要有三个数据结构：已分配资源表、所需资源表、可分配资源表。如下图，表格中A、B、C、D四列表示可申请的四个共享资源，P1、P2、P3、P4是四个进程，第一张表内部的数字表示当前进程拥有的资源数量，第二张表内部的数字表示当前进程还需要资源的数量，第三张表内部数字表示当前系统还剩的资源数量。

  当我们把所需资源表减去已分配资源表，就可以得到一张还需要分配的资源表:

  此时我们把还需分配资源表中每个进程依次和可分配资源表比较，如果有一个进程当前满足运行条件，则直接把资源分配给它。等进程运行完毕归还资源后，重新再比较。

预处理器

C预处理器处理程序的源代码，在编译器运行之前运行，通常以符号"#"开头。

C预言的预处理主要有三个方面的内容：

1. 宏定义与宏替换
2. 文件包含
3. 条件编译

宏定义与宏替换

  “宏”是借用汇编预言中的概念，为的是在C语言程序中方便的做一些定义和扩展。这些语句以“#define”开头，分为两种：符号常量的宏定义和带参数的宏定义

• 符号常量的宏定义和宏替换

1

#define 标识符 字符串

  其中标识符就是宏名称，注意宏定义末尾不加分号.

  由于预处理是在编译之前的处理，而编译工作的任务之一就是语法检查，所以预处理是不做语法检查的。且宏定义不分配内存，变量定义才分配内存。

• 带有参数的宏定义及其替换

  对带有参数的宏定义进行宏替换时，不仅对宏标识符作字符串替换，还必须作参数的替换。有时为了避免发生错误，需要在宏参数上加括号。

1
2
3
4
5
6

#define 标识符(参数列表) 字符串


#define FUN(x) (x*x)  //FUN(a+b)将被替换为a+B*a+B

#define FUN(x) ((x)*(x))  //FUN(a+b)将被替换为(a+B)*(a+B)

  宏替换的本质就是文本替换，需要注意：

1. 宏名一般用大写，宏名和参数的括号间不能有空格，宏定义末尾不加分号；
2. 宏替换只做替换，不做语法检查、不做计算、不做表达式求解；
3. 宏替换在编译前进行，不分配内存；函数调用在编译后的程序运行时进行，且分配内存；
4. 函数只有一个返回值，利用宏则可以设法得到多个值；
5. 宏替换会使源程序变长，函数调用不会；
6. 宏替换不占用运行时间，只占用编译时间；函数调用占用运行时间(内存分配、保留现场、值传递、返回值)

  实际工程中应尽量少用宏替换。C++中宏替换实现的符号常量功能由const、enum代替，带参数的宏替换可由模板内联函数代替。

文件包含

1
2

#include <func.h>
#include "func.h"

  如果头文件名在尖括号<>中，那么认为该头文件是标准头文件。编译器将会在预定义的位置集合中查找该头文件，这些预定义的位置可以通过设置查找路径和环境变量或者修改命令行选项来修改；

  如果头文件在一对引号中，则认为它是非系统头文件，非系统头文件的查找通常开始于源文件所在的路径中；

条件编译

  提供条件编译措施使得同一源程序可以根据不同编译条件(参数)选择不同的目标代码，其作用在于便于调试和移植。

1
2
3
4

#if/ifdef/ifndef
#elif
#else
#endif

全局变量和局部变量

  全局变量也称为外部变量，在函数的外部定义。它属于一个源程序文件，作用域是整个源程序。

  在不同的文件中引用一个已经定义过的全局变量，可以用头文件引用的方式，也可以用extern关键字。假设变量写错了，如果使用头文件包含的方式，那么编译期间会报错；如果使用extern关键字，编译期间不会报错，链接期间报错。

1
2
3
4
5
6

//file_1.cpp
int counter;

//file_2.cpp
extern int counter;  //使用file_1中的counter
++counter;

  局部变量指在程序中，只在特定过程或函数中可以访问的变量，是相对全局变量而言的。在面向过程的语言中，局部变量可以和全局变量重名，但局部变量会屏蔽全局变量。

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

int count = 3;  //语句1

int main()
{
    int i, sum, count = 2;  //语句2
    for(i = 0;i < count; i+=2, count++)     //判断条件count是语句2的count
    {
        static int, count = 4;  //语句3
        count++;    //用的是语句3的count
        if(i % 2 == 0)
        {
            extern int count;
            count++;    //因为用了extern，这里的count是语句1的count
            sum += count;   //因为用了extern，这里的count是语句1的count
        }
        sum += count;   //语句3的count
    }

    printf("%d %d\n", count, sum);  //语句2的count
    return 0;
}

static

普通的static

普通的static作用有三个：

1. 隐藏：当我们同时编译多个文件时，所有未加static的全局变量和函数都具有全局可见性，其他的源文件也可以访问。如果加了static前缀，则全局变量和函数对其他源文件隐藏，只在当前文件生效。
2. 默认初始化为0，包括未初始化的全局静态变量和局部静态变量。全局未初始化的变量本身也具备这个属性，未初始化的全局变量和未初始化的静态变量都在BSS段内，所有的字节默认为0x00;
3. 保持局部变量内容的持久。函数内的普通的局部变量退出作用域就消失了，但静态的局部变量退出函数后仍然存在，生存周期为整个源程序的周期。static的局部变量特点是只进行一次初始化且具有“记忆性”。不过虽然生存周期是整个程序，但作用域仍然和普通局部变量相同，出了函数虽然还存在，但不能使用。

类中的static

  C++重用了static关键字，并赋予了不同的含义：类中的static表示属于一个类但不属于此类的任何特定对象的变量和函数。static的成员变量和成员函数都独立于类对象存在。

• 静态数据成员：

  普通数据成员存在于该类的每个对象中，但static数据成员独立于该类的任意对象存在：static数据成员是与类关联的对象，二不与该类的对象相关联。当某个类的实例修改了该静态成员变量，修改后的值被该类的所有实例所见。

  静态数据成员和普通数据成员一样，也遵从public、protected、private的访问规则。

  静态数据成员也存储在全局(静态)存储区。静态数据成员定义时要分配空间，所以不能在类声明中定义，必须在类定义体的外部定义。

1
2
3
4
5
6
7
8
9
10
11

class Account
{
public:
    void apply();
    static double rate() {return interestRate;}
private:
    std::string owner;
    static double interestRate;
};

double Account::interestRate = 10; //类外定义

使用static成员变量而不是全局变量有三个优点：

1. static成员的名字还在类的作用域中，可以避免全局冲突；
2. static成员可以声明为私有的，实施封装；
3. 阅读方便，可以明确看出static成员与类是关联的

• 静态成员函数：

  和静态成员变量一样，静态成员函数是类的内部实现，属于类定义的一部分，为类服务而不是为类的具体对象服务。

  普通成员函数服务于具体的对象，所以普通的成员函数都隐含了一个this指针指向类的对象本身；静态成员函数不与对象关联，所以不具有this指针。所以静态成员函数无法访问属于类对象的非静态数据成员，也无法访问非静态成员函数，只能调用类其余的静态成员函数与访问静态数据成员。不过非静态的成员函数可以任意访问静态的成员函数和变量。由于没有this的开销，静态成员函数相比普通的成员函数速度上有少许增长。

  static成员变量可以被声明为const，但static成员函数不可以。const成员函数的意思是承诺不修改该函数所属的对象，但static成员函数不属于任何对象。

  static成员函数也不能被声明为虚函数、volatile。

const

常量

  C++中const限定符把一个对象转换为常量，常量定义后不允许修改，所以定义时必须初始化。

1

const int bufSize = 512; //必须初始化

  全局变量在整个程序中都可以访问，但全局的const变量是定义该变量的文件的局部变量。如果想被其他文件访问，需要声明extern。

  C和C++中的const有区别。常量引进是在早期的C++版本中，当时标准C规范正在制定。C中的const意思是“一个不能被改变的普通变量”，在C中总是占用存储，C编译器不能把const视为一个编译器的常量：

1
2
3

//以下写法在C中是错误的，C++中是允许的
const bufSize = 100;
int buf[bufSize];

  C默认const是外部连接的，C++默认const是内部连接的，如果想在C+中完成于C同样的事情，需要加extern变成外部连接：

1
2
3
4
5

//C语言可以这么写，C编译器只把他当作声明，C++编译器必须初始化，不能这么写
const int size;

//C++必须加extern
extern const bufSize; //只声明

  const最初的动机是取代#define的值替换功能，使用const取代#define的优点如下：

1. const常量有数据类型，宏常量没有数据类型，所以编译器可以对const常量进行类型安全检查；
2. 预处理会盲目的将宏常量进行代码替换，可能导致代码中多出很多个备份，所以使用const常量可能比使用#define产生更小的目标代码；
3. const可以执行常量折叠：常量折叠是编译期间简化常量表达式的过程，简单说就是将常量表达式计算求值，并用求得的值替换表达式放入常量表。

指针和const

  需要区分指向const的指针和const指针：

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

//指向const的指针：
const double *cptr;
// cptr是个指针，它指向一个const double
// cptr可以指向任何东西，所以不需要初始化，但是它所指的东西不能改变


//const指针
//使指针成为const，要把const标明的部分放在*右边
double d = 1.0;
double* const cptr = &d;
// cptr是个指针，这个指针是指向double的const指针
// 指针本身是const，所以必须初始化
// 在指针寿命期间内，指向的地址不可以改变，但地址里的内容可以变更

const修饰函数参数和返回值

  在一个函数声明式内，const可以和函数返回值、各参数、类成员函数函数自身产生关联：

• const修饰返回值：

  若返回值是值类型，则对于内部数据类型来说，返回值是否是常量并没有关系，const修饰返回值通常用于处理用户定义的类型；除了值类型，还可以返回指针。正常的函数不能返回指向局部变量的指针，因为函数返回后指针就无效了，栈也被情理了，但如果返回的指针是指向堆中分配的存储空间的指针或者是指向静态存储区的指针，在返回后仍然有效。

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

//错误！！
// p是数组在栈上，返回的是指向栈内存的指针，
//返回的地址不是NULL，但内容已经被清除了
char* GetMemory()
{
    char p[] = "hello world";
    return p;
}


//正确
//数组在静态存储区，可以通过函数返回
char* GetMemory()
{
    static char p[] = "hello world";
    return p;
}



//正确
//p指向全局静态存储区，可以通过函数返回
//因为p指向常量，这里最好加上const修饰
//如果不加const，函数外面如果对返回的字符串做修改就崩溃了
const char* GetMemory()
{
    char p* = "hello world";
    return p;
}


//不太好的写法
//p指向堆内存的地址，可以通过函数返回
//但是需要外部来delete[]释放内存
char* GetMemory()
{
    char* p = (char*)malloc(12);
    if(p == NULL){
        return NULL;
    }
    else{
        p = "hello world";
    }
    return p;
}

• const修饰函数参数：

  参数加上const可以明确告知编译器参数在函数体内部不会也无法改变。如果是值传递，加const意义不大，但如果是传递地址，那么都应该尽可能的用const修饰。

const与类

• const成员函数：

1
2
3
4

class base{
    void func1();
    void func2() const;
}

  被const修饰的类成员函数改变了隐含的this形参的类型，使得this形参指向的对象为const类型。this本身的类型是base* const，被const修饰后变成了const base* const。const成员函数不能修改调用该函数的对象。

  const成员函数的目的是为了确保该成员函数可以作用于const对象身上。const对象、指向const对象的指针或引用只能调用其const成员函数；非const对象可以调用所有成员函数。显然，若不存在const成员函数，那么const对象的操作就变的极为困难，无法调用任何成员函数了。

  要注意，如果类成员函数只是常量性质不同，其余都一样，是可以被重载的：

1
2
3
4

class base{
    void func1();
    void func1() const;
}

• const数据成员：

  如果一个类的数据成员声明为const，那么必须在构造函数的初始化列表中进行初始化，且必须具有构造函数。不过如果数据成员同时具有static和const属性，那么也可以使用外部初始化。const数据成员也不可以在类定义处初始化，因为const数据成员只是在某个对象的生存周期内是常量，对于整个类而言是可变的，不同的对象可以有不同的值，如果在类声明中初始化const数据成员，因为类对象还没有创建，编译器不知道const数据成员的值是什么。

1
2
3
4
5
6

class Thing{
public:
    Thing():valueB(1){}
private:
    const int valueB;
}

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

class Test
{
public:
    Test():a(0){}
    enum {
        size1 = 100,
        size2 = 200
    };

private:
    const int a;    //只能在构造函数初始化列表中初始化
    static int b;   //在类外定义并初始化
    const static int c;
    //也可以写作static const int c;
    //c这里是整型，所以也可以在这里初始化，但仍需要在类外进行定义
    //如果c不是整形(char、short、int、long)，就不允许在这里初始化
};

int Test::b = 0;    //static成员变量不允许在类内初始化，不属于某个对象
const int Test::c = 0;  //给const static成员变量赋值时可以不加static，但必须加const

内存管理与释放

  C/C++程序，用户主要使用的内存主要分为：栈区、堆区、全局(静态)存储区、文字常量区、代码区。

  堆区和栈区的区别：

• 栈区：由编译器自动分配和释放，存放函数的参数值、局部变量的值等。操作方式类似于数据结构中的栈，速度较快；
• 堆区：一般由程序员分配释放，若程序员不释放，程序结束时由操作系统回收。要注意和数据结构中的堆是两回事，它的分配方式类似链表。一般速度比较慢，而且容易产生内存碎片，不过用起来方便。

1
2
3
4
5
6
7

//C语言
char* p1 = (char*)malloc(10);

//C++
char* p2 = new char[10];

//要注意p1和p2本身是栈上的变量，只是指向堆上分配的内存

  每一个程序执行时都占用一块可用的内存空间，用于存放动态分配的对象，这个内存空间就是堆。C语言使用标准库函数malloc和free在堆区分配存储空间，C++语言使用new和delete表达式实现。

动态创建对象的初始化

  通常，动态创建的对象如果不提供显式的初始化，那么对于类对象，用该类的默认构造函数初始化，当然也可以使用显式初始化；而内置类型的对象则无初始化；

  对于提供了默认构造函数的类的类型，没有必要对其对象进行显式初始化，操作结果一样；但如果是内置类型或者是没有默认构造函数的类型，不同的初始化方式有显著的差别：

1
2
3
4
5
6
7
8
9

//std::string类有默认构造函数
//无论是隐式的还是显式的，结果都是调用默认构造
string* ps = new string;    //调用默认构造函数初始化
string* ps = new string();  //调用默认构造函数初始化


//int是内置类型的，隐式的和显式的有区别
int* pi = new int;  //隐式的，无初始化
int* pi = new int();    //显式的，pi指向一个初始化为0的int值

  动态创建的对象用完后，程序员必须显式的将该对象占用的内存释放，否则就会内存泄漏，C语言提供了free函数，C++使用delete表达式。回收用new分配的单个对象的内存空间用delete，回收用new[]分配的一组对象的内存空间时用delete[];

1
2
3

char* p = new char[64];
delete[] p;
p = nullptr;

const对象的动态分配和回收

1

const int* pci = new const int(1024);

  C++允许动态创建const对象。与其他常量一样，动态创建的const对象必须在创建时初始化，且一经初始化其值不可再修改。

  对于一个类的const动态对象，如果该类提供了默认的构造函数，则此对象可以隐式初始化；内置类型对象或者未提供默认构造函数的类对象必须显式初始化：

1
2
3
4

//std::string有默认的构造函数
//new表达式没有显式的初始化pcs所指的对象
//而是隐式的将pcs所指的对象初始化为空string
const string *pcs = new const string;

  尽管程序员不能改变const对象的值，但是可以撤销对象本身。如同其他对象一样，const动态对象也可以使用指针释放：

1
2

const string *pcs = new const string;
delete pci;

new/delete和malloc/free比较

相同点：都可以用于申请动态内存和释放内存

不同点：

1. malloc和free是C/C++语言的标准库函数，new/delete是C++的运算符；
2. new自动计算需要分配的空间，而malloc需要手工计算字节数；
3. new是类型安全的，malloc不是；
4. new和delete可以调用相关对象的构造和析构，malloc和free不行；
5. malloc和free需要库文件支持，new和delete不需要

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

malloc和free由于是库函数，不在编译器控制权限之内，所以无法执行类的构造函数和析构函数；



new的执行过程：
1.用operator new的标准库函数(operator new对应malloc)，分配足够大的原始的未类型化的内存，以保存指定类型的一个对象；
2.运行该类的一个构造函数，用指定初始化式构造对象
3.返回指向新分配并构造的对象的指针；

delete的执行过程：
1.首先对指针指向的对象运行适当的析构函数；
2.调用operator delete的标准库函数释放该对象用的内存(operator delete对应free)；



malloc的函数原型如下：
void* malloc(size_t size);
用malloc申请一块长度为length的整数类型的内容程序如下：
int* p = (int*)malloc(sizeof(int) * length);
可见malloc返回值的类型是void*，所以在调用malloc时一定要显式类型转换；
且malloc函数本身并不识别要申请的内存类型，只关心总字节数

free函数的原型如下：
void free(void* memblock);
用free(p)来释放内存，如果p是NULL，那么free(p)操作多少次也不会出问题；
但如果p不是NULL，那么连续free(p)两次就会导致程序运行错误



new内置了sizeof、类型转换和类型安全检查功能，所以使用简单
int* p2 = new int[length];

内存池

  通常我们直接使用new、malloc等申请内存，这样做有个缺点：由于所申请的内存块大小不定，当频繁使用时会造成大量的内存碎片降低性能。

  内存池是一种内存分配方式，在真正使用内存之前，先申请分配一定数量的、大小相等(一般情况下)的内存块留作备用。当有新的内存需求时，就从内存池中分出一部分内存块，若内存块不够再继续申请新的内存。

进程

进程概念

  在没有操作系统之前，计算机只能运行一个程序，全部的资源都属于当前运行的程序。配置了操作系统后，引入了多道程序设计的概念，进程可以合理的隔离资源和运行环境、提升资源利用率。

• 进程是系统进行资源分配和调度的基本单位；
• 进程作为程序独立运行的载体保障程序正常执行；
• 进程的存在使得操作系统资源的利用率大幅提升；

进程实体

  主存中的进程是一个连续的存储空间，称为进程控制块(PCB)。进程控制块是用于描述和控制进程运行的通用数据结构。进程控制块中存有进程状态、优先级、程序计数器、内存指针、上下文数据、IO状态信息、记账信息等多个进程当前状态和控制进程的信息：

• 标识符：唯一标记一个进程，用于区别其他进程；
• 状态：标记进程的运行状态
• 程序计数器：指向进程即将被执行的下一条指令的地址；
• 内存指针：程序代码、进程数据相关的指针；
• 上下文数据：存储进程执行时处理器中的数据；
• IO状态信息：被进程IO操作所占用的文件列表；
• 记账信息：存储进程使用处理器的时间、时钟数总和等信息；

  除了上面的内容，进程还有一些其他信息。所有信息可以分为四大类：进程标识符、处理机状态、进程调度信息、进程控制信息。进程控制块使得进程是能够独立运行的基本单位，操作系统通过进程控制块信息来调度和控制进程。进程控制块是常驻内存的，存放在系统专门开辟的PCB区域内。

进程与线程

  进程(Process)和线程(Thread)是一对多的关系，一个进程内可以有一个或多个线程。

  进程是系统进行资源分配和调度的基本单位，而线程是操作系统进行运行调度的最小单位。线程包含在进程之中，是进程中实际运行工作的单位。一个进程可以并发多个线程，每个线程执行不同的任务。

  进程拥有资源，而线程不拥有资源，进程内部的线程共享进程资源。

五状态模型

• 就绪状态：

  当进程被分配到除CPU以外的所有必要资源后，就处于就绪状态。只要再获得CPU的使用权，就可以立即运行。在一个系统中多个处于就绪状态的进程通常排成一个队列，称为就绪队列。

• 执行状态：

  进程获得CPU，其程序开始执行，这个状态为执行状态。在单处理机中，某个时刻只能有一个进程是处于执行状态。

• 阻塞状态：

  进程因为某种原因，比如其他设备未就绪而无法执行，从而放弃CPU的状态称为阻塞状态。和就绪队列一样，操作系统也有阻塞队列，存放所有阻塞的进程。

• 创建状态：

  进程创建分为两步，第一步分配PCB，第二步插入就绪队列。创建进程时拥有PCB但其他资源尚未就绪的状态称为创建状态。无论是系统创建的进程还是用户创建的进程都是一样的，操作系统提供fork接口创建进程。

• 终止状态：

  进程终止也分为两步：首先进行系统清理，然后进行PCB归还。进程结束由系统清理或者归还PCB的状态称为终止状态。

进程同步

生产者-消费者模型

  有一群生产者进程在生产产品，并将这些产品提供给消费者进程进行消费。生产者进程和消费者进程可以并发执行，在两者之间设置了一个具有n个可缓冲区的缓冲池，生产者进程需要将所生产的产品放到其中一个缓冲区中，消费者进程可以从缓冲区中取走产品进行消费。

  生产者消费者模型在宏观上是没有问题的，当生产一个产品时缓冲区+1，当消费一个产品时缓冲区-1。但是计算机系统中是有问题的。计算机中的缓冲区位于高速缓存Cache上，生产者或消费者如果要操作缓冲区需要三个步骤：

1. 把缓冲区中的信息取出来放入寄存器：register = count
2. 如果生产register+1；如果消费register-1
3. 把寄存器信息放回缓冲区里：count = register

  这三个步骤但从生产者或消费者程序看没有问题，但两者并发执行时就会出差错:

哲学家进餐问题

  有五个哲学家，他们的生活方式是交替的进行思考和进餐。哲学家们共同使用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子。平时哲学家们只进行思考，饥饿时则试图取靠近他们的左、右两支筷子，只有两支筷子都被拿到时才能进餐，进餐完毕后分别放下左、右的筷子继续思考。

  通常的情况下，假设一个哲学家饿了，首先拿起左边的筷子，如果发现右边的筷子被拿走，则需要等待右边的筷子释放，释放后才能拿起筷子吃饭。但有一种极端情况：五个哲学家同时拿起左边的筷子，此时发现他们右边的筷子都被拿走，所以五个哲学家都需要等待右边筷子释放，最终的结果就是五个哲学家被饿死。

进程同步

  上面两个问题是操作系统中的经典问题，问题的根源在于：彼此之间没有通信。如果生产者通知消费者已经完成了一件生产，或者哲学家向旁边的哲学家说我要进餐了，就可以避免这些问题。

  进程的同步用于解决这种对竞争资源在多进程间进行使用次序的协调，使得并发的多个进程之间可以有效使用资源和相互合作。

进程同步原则

  临界资源指的是一些虽然作为共享资源却无法同时被多个线程共同访问的共享资源。当有进程在使用临界资源时，其他进程必须依据操作系统的同步机制等待占用进程释放该共享资源才可重新竞争使用共享资源。为了对临界资源进行约束，提出了进程同步的四个原则：

1. 空闲让进：资源无占用时允许进程使用；
2. 忙则等待：资源有占用，其他请求进程需要等待；
3. 有限等待：保证有限等待时间能够使用资源；
4. 让权等待：进程等待时，需要让出CPU；

线程同步

  和进程同步一样，一个进程内有多个线程并发使用，也会产生生产者-消费者问题和哲学家进餐问题，所以进程内的多线程也需要同步。

Linux的进程管理

进程类型

  Linux下进程分为三种类型：前台进程、后台进程、守护进程。

• 前台进程：

  Linux下有一个重要概念，就是终端Shell，我们使用命令行来使用Linux时就是通过终端Shell来实现。前台进程就是具有终端Shell，可以和用户交互的进程。前台进程占用终端Shell但不一定有输出。

• 后台进程：

  和前台进程相对，没有占用终端的就是后台进程。后台进程基本上不和用户交互，优先级比前台进程低。Linux下将需要执行的命令以“&”符号结束来启动后台进程。

• 守护进程：

  守护(daemon)进程是特殊的后台进程。很多守护进程在系统引导的时候启动，一直运行到系统关闭。Linux下进程名字以d结尾的进程一般都是守护进程，比如定时任务守护进程crond、http服务守护进程httpd、ssh登录的守护进程sshd、数据库守护进程mysqld。

进程标记

• 进程ID：

  进程的唯一标识符，每个进程拥有不同的ID。进程ID表现为一个非负整数，最大值由操作系统限定。

  操作系统提供fork接口创建进程，进程可以多层创建，这些进程是父子进程的关系。进程父子关系可以用pstree命令查看。

  需要记住几个特殊的进程：ID为0的进程为idle进程，是系统创建的第一个进程；ID为1的进程为init进程，是0号进程的子进程，完成系统的初始化。init进程也是所有用户进程的祖先进程；

• 进程标记：

  和Windows系统类似，Linux下的进程也有不同的进程状态，我们可以通过man ps命令来查看进程状态的所有标记，Linux进程状态很多，常见的有以下几种：

Linux操作进程命令

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

+ ps命令：用于显示进程信息的常用命令，常用选项如下：
  + -e：显示所有进程，包括系统进程
  + -f：显示完整进程信息，包括进程的详细信息
  + -l：显示更多的列，包括进程的状态、CPU使用情况等
  + -u：显示指定用户的进程信息
  + -aux：结合-a和-u选项，显示所有用户的所有进程，并显示详细信息
  + -p：显示指定进程号PID的进程信息
  + -k --sort：按指定的列排序进程信息，常见的排序屁啊包括%cpu(CPU使用率)、%mem(内存使用率)等
  + -c：根据命令行显示进程信息
  + -o：自定义输出格式，可以指定要显示的列
  + --forest：以树状结构显示进程间的父子关系

ps命令可以和其他命令结合：
ps -aux | grep '进程名'：查找指定进程的信息

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

+ top命令：系统监视工具，查看进程状态，常用选项如下：
  + -d：秒数，指定top命令每个几秒更新
  + -b：使用批处理模式输出，一般和"-n"选项合用，用于把top命令重定向到文件中
  + -n：次数，指定top命令执行的次数，和"-"选项合用
  + -p：仅查看指定PID的进程
  + -s：使top命令在安全模式中运行，避免在交互模式中出现错误
  + -u：用户名，只监听某个用户的进程

在top命令的显示窗口中，还可以使用如下按键进行交互操作：
+ ?或h：显示交互模式的帮助
+ c：按照CPU的使用率排序，这个是默认的
+ M：按照内存使用率排序
+ N：按照PID排序
+ T：按照CPU的累积运算时间排序
+ k：按照PID给予某个进程一个信号，一般用于终止某个进程
+ r：按照PID给某个进程重设优先级
+ q：退出top命令


使用top命令后展示的进程信息关键字含义如下：
+ PID：进程标识符
+ USER：运行进程的用户名
+ PR：进程的优先级
+ NI：进程的优先级调整值
+ VIRT：进程使用的虚拟内存大小
+ RES：进程实际使用的物理内存大小
+ SHR：进程的共享内存大小
+ %CPU：进程占用CPU的使用率
+ %MEM：进程占用内存的使用率
+ TIME+：进程的累计CPU时间
+ COMMAND：进程命令行

1
2
3
4
5
6

kill命令：给进程发送信号时使用

kill -l：查看操作系统支持的所有信号
//只有SIGKILL 9信号可以无条件终止进程，其他信号进程有权忽略

eg：kill -9 PID :给指定PID进程发送9信号，用于强制退出进程

进程同步方法

• 消息队列
• 共享存储
• 信号量

线程同步的方法：

1. 互斥量
2. 读写锁
3. 自旋锁
4. 条件变量

操作系统发展历程

  多道程序设计是个很重要的概念。早期的批处理系统一次只能处理一个任务，多道程序设计使得批处理系统可以一次处理多个任务，大大提升系统运行效率。多道程序设计是指在计算机内存中同时存放多个程序，程序之间相互不干扰，在计算机的管理程序之下相互穿插运行。对多道程序的管理是操作系统的重要功能。

  操作系统对多道程序和系统资源的管理，可以分为五大功能：进程管理、存储管理、作业管理、文件管理、设备管理。

操作系统概述

  操作系统是管理计算机硬件和软件资源的计算机程序，本质是个软件程序。操作系统管理配置内存、决定资源供需顺序、控制输入输出设备等；操作系统也提供让用户和系统交互的操作界面。操作系统的种类是多样的，不局限于计算机，从手机到超级计算机，操作系统可简单也可复杂，在不同设备上，操作系统可向用户呈现多种操作手段。

操作系统基本功能

  计算机系统中有几大资源：处理器资源、存储器资源、IO设备资源、文件资源。操作系统第一个基本功能是统一管理计算机资源。

  操作系统的第二个功能是实现了对计算机资源的抽象，用户无需面向硬件接口编程：如IO设备管理软件提供读写接口、文件管理软件提供文件操作接口。

  操作系统的第三个基本功能是提供了用户与计算机之间的接口。有三种接口形式：图形窗口形式(比如Windows界面)、命令形式(shell终端敲入命令)、系统调用形式(程序调用的接口)。

操作系统特性

并发性

  并发性是后面三种特性的前提，只有理解了并发性，才能理解其他特性。

  并发需要和并行区分理解：并行是指两个或多个事件可以在同一时刻发生；并发是指两个或多个事件可以在同一时间间隔内发生。

  多道程序设计是并行和并发的基础。在单处理器的系统中只存在并发的概念，同一时刻只有一个程序占用CPU，多个程序交替执行；多处理器系统中，单个处理器并发执行，所有处理器并行执行。

共享性

  共享性表现为操作系统中的资源可供多个并发程序共同使用，这种共同使用的形式称之为资源共享。

  资源共享根据属性可以分为互斥共享形式和同时访问形式：

• 互斥共享：当资源被程序A占用时，其他想使用资源的话只能等待A使用完，比如打印机资源；
• 同时访问：某种资源在一段时间内并发的被多个程序访问，这种“同时”是宏观的，从宏观看资源可以被同时访问，比如硬盘资源；

虚拟性

  虚拟性表现为把一个物理实体转变为若干个逻辑实体，物理实体是真实存在的，逻辑实体是虚拟的。虚拟技术主要有时分复用技术和空分复用技术。

• 时分复用：资源在时间上进行复用，不同程序并发使用，多道程序分时使用计算机的硬件资源，时分复用可以提高资源利用率；
• 空分复用：用来实现虚拟磁盘、虚拟内存等，提高资源的利用率，提升编程效率；

异步性

  异步性表现为在多道程序的环境下，允许多个进程并发执行。由于进程在使用资源时可能需要等待或放弃，所以进程的执行并不是一气呵成的，而是以走走停停的形式推进。