数组

什么是大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;
}

基本厨具

• 锅具
  • 炒锅：万能的，煎炒烹炸样样精通；
  • 汤锅：用于煮面条或者烧水；
  • 平底不粘锅：用于煎饼、煎肉；
  • 小奶锅：做快手菜

六大基酒

伏特加

  鸡尾酒中的万金油，突出纯净，就像一张空白画纸，可以填充任意的风味和材料，包括果汁、咖啡和奶茶。不知道喝什么，但就是想喝酒的时候，选择伏特加就不会出错。推荐：斯米诺、SKYY、绝对伏特加；如果想要品质好的伏特加，可以选绝对亦乐、灰雁。

金酒

  金酒又被称作风味伏特加，是在蒸馏烈酒的基础上加以杜松子为首的各种香料和草本来增加风味。所以金酒最大的特点就是有草本气息。不同品牌做出的风味不一样。推荐必富达、添加利、孟买蓝宝石。

朗姆酒

  带有浓浓热带气息的海盗酒，本身的原料是甘蔗糖蜜，所以喝起来有香甜感，做出的鸡尾酒也有热带风情。最常见的就是百加得。进阶的话朗姆酒有细分：金朗姆、黑朗姆、陈年朗姆等，刚刚入门只需要一瓶白朗姆即可。

龙舌兰

  具有异域风情的酒。必须使用墨西哥当地的蓝色龙舌兰草作为原料。派对和夜店常见的喝法是把盐放在虎口上，先舔一口盐，再喝一shooter龙舌兰，最后再咬一瓣超酸青柠。国内性价比高的龙舌兰就是奥美加、培恩。

威士忌

  威士忌种类非常多，调酒的话不推荐用高价的单一麦芽威士忌，这种威士忌是纯喝风味的，调酒不需要太强的风味。推荐百龄坛、波本。

白兰地

  白兰地的分级是按照年份分级，可以在标签上看到VS、VSOP和XO。XO是陈年时间最久的，VS是最轻的。调酒时推荐用VS，口味风格不会特别突出。

家庭吧台中的辅料推荐

利口酒

利口酒可以给烈酒加上特殊的风味。

• 君度橙酒 COINTREAU
• 金巴利 CAMPARI
• 味美思 VERMOUTH,味美思是加烈葡萄酒，分为干性、甜性、半干性。
• 苦精 Bitters。就是浓缩的草药酒。用于鸡尾酒的提香。

非酒类材料

• 柠檬和青柠檬，可以直接用青柠汁。
• 各种苏打水。
• 果汁

一些常见的鸡尾酒配方

金酒篇

GIN & TONIC 金汤力

直调酒，不需要搅拌不需要摇晃。

• 加冰
• 45-60ml金酒
• 90-150ml汤力水
• 少许青柠汁（可选，经典金汤力不加）
• 一瓣青柠做装饰

勺子只做提拉，不要搅拌，否则气泡会散失

GIMLET 螺丝钻

• 60ml金酒
• 15ml青柠汁
• 15ml糖浆
• 摇晃，一瓣青柠做装饰

NEGRONI 尼格罗尼

口感苦涩，但是很好看

• 30ml金酒
• 30ml金巴利
• 30ml甜味美思
• 搅拌，一片橙子皮做装饰

TOM COLLINS 汤姆柯林斯

• 60ml金酒
• 30ml柠檬汁
• 15ml糖浆
• 加满新鲜的苏打水
• 摇晃，一片柠檬皮做装饰

FRENCH 75 法兰西75

• 45ml金酒
• 22.5ml柠檬汁
• 22.5糖浆
• 加满香槟
• 摇晃，长条柠檬皮做装饰

AI编程

  传统的编程模型中，开发程序是一项高度专业化的任务。程序员需要具备深厚的技术背景，掌握至少一门编程语言。并且要对复杂的逻辑和算法有着清晰的理解。然而随着AI人工智能技术飞速发展，编程的方式正在迎来革命性的变化。现在迎来了一个全新的阶段：我们不再需要精通晦涩难懂的编程语法，甚至不需要直接面对复杂的代码编辑器。取而代之的是，我们可以像和朋友聊天一样，用自然、日常的语言，向一个强大的AI大模型描述我们的需求。

  AI编程的核心在于利用强大的AI大模型来辅助甚至主导编程过程。这些AI大模型经过海量数据的训练，具备了理解和生成代码的能力。通过简单的对话聊天，即使是非专业的用户，也能够与AI大模型交互，快速生成所需的程序代码。

主流AI编程IDE对比

Cursor简介

  Curosr是一款基于人工智能的现代化代码编辑器，由Anysphere公司开发。

  Cursor是基于VS Code开发的一款编辑器，它在保留VS Code强大功能和熟悉操作体验的同时，专注于集成AI技术，帮助开发者更高效的编写代码。

  国内阿里与字节页有基于VS Code开发的IDE：

• 阿里Lingma IDE: https://lingma.aliyun.com/
• 字节Trae：https://www.trae.com.cn/

核心特征：

• AI 原生设计：从底层架构就融入了AI能力，而非后期添加的插件；
• 智能代码生成：通过自然语言描述快速生成代码片段；
• 上下文感知：深度理解项目结构和代码关系；
• 实时协助：在编程过程中提供即时的建议和优化；

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是四个进程，第一张表内部的数字表示当前进程拥有的资源数量，第二张表内部的数字表示当前进程还需要资源的数量，第三张表内部数字表示当前系统还剩的资源数量。

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

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