近期技术面试问题回顾与总结

• 掌握计科五大件：编译原理、计网、计组、操作系统、数据结构和算法，常见面试题.
• 具有一定的代码框架设计能力，熟悉常用设计模式, 有面向对象开发经验。
• 熟练掌握网络编程、熟悉TCP/UDP、HTTP协议及Socket，以及其他以太网通信协议。
• 熟练掌握C++11之后的语言特性，保证代码的可维护性和可扩展性。
• 掌握系统构建、调试、异常分析和性能优化的基本方法。
• 掌握多线程、异步编程等并发编程开发必要方法、框架和组件，掌握性能优化方法。
• 理解并能够应用各种数据序列化和反序列化技术，如JSON, XML, Protocol Buffers等。
• 具备较强的逻辑思维和代码阅读能力；能持续学习，钻研问题，不断提升质量和效率。

编译原理

从源码到可执行文件的过程

点击展开

一个C++程序从源码到执行文件，有四个过程，预编译、编译、汇编、链接。

预处理（Preprocessing）： g++ -E hellp.cpp > hello.i [.cpp → .i]

（1） 清理代码，过滤所有的注释、多行语句合成一个逻辑行，添加行号和文件名标识。
（2） 处理各项预处理指令：

预处理指令	描述
#include	将指定头文件的内容插入到当前位置。
#define	定义宏，宏可以是简单的文本替换，也可以是带参数的宏。
#undef	取消之前的宏定义。
#ifdef、#ifndef、#if、#else、#elif、#endif	根据条件编译指令的真假来决定是否编译某段代码。
#pragma once 或 #ifndef/#define/#endif	防止头文件被重复包含。
#error	编译时产生错误信息。
#line	修改行号。
#pragma	向编译器发出特定的指令。

编译（Compilation）： g++ -S hello.i [.i → .s]

编译器将预处理后的代码转换为汇编语言，包含以下几个步骤：

（1） 词法分析（lexical analysis）：将源代码的字符流分割成一系列的符号流。
（2） 语法分析（syntax analysis）：对符号进行语法分析，产生语法树。
（3） 语义分析（semantic analysis）：检查符号表和语法树的语义，判断表达式是否有意义。
（4） 中间代码生成（intermediate code generation）：通常是低级的或类似汇编语言的中间代码，如三地址码。
（5） 代码优化（code optimization）：对中间代码进行优化，提高代码执行效率。
（6） 目标代码生成（target code generation）：将优化后的中间代码转换为目标机器的汇编代码。

汇编（Assembly）： g++ -c hello.s [.s → .o]

（1） 这个过程主要是将汇编代码转变成机器可以执行的指令。
（2） 每个源文件对应一个目标文件 .o，目标文件是二进制文件，包含机器指令、数据和符号表等信息。

链接（Linking）： g++ hello.o -o hello [.o → bin]

将不同的源文件产生的目标文件和库文件链接形成一个可以执行程序，链接过程主要包括以下几个步骤：

（1）地址和空间分配：链接器会根据目标文件的大小和布局，确定每个模块在最终可执行文件中的位置。
（2）符号决议：链接器会解析每个目标文件中的符号引用，找到符号的定义，并将引用替换为实际地址。
（3）重定位：调整代码和数据中的地址引用，反映它们在最终可执行文件中的实际位置，以便在可执行文件中正确地定位符号。

链接分为静态链接和动态链接。
静态链接：
（1）在链接时将所有需要的库函数和过程嵌入到最终的可执行文件中。
（2）生成的静态链接库在 Windows 下以 .lib 为后缀，在 Linux 下以 .a 为后缀。
（3）静态链接的可执行文件在运行时不依赖外部库，即使删除静态库也不会影响程序的执行。
动态链接：
（1）在链接时只将库函数和过程的引用嵌入到可执行文件中，而不是将整个库函数和过程。
（2）生成的动态链接库在 Windows 下以 .dll 为后缀，在 Linux 下以 .so 为后缀。
（3）动态链接的可执行文件在运行时依赖外部库，需要在运行时加载动态链接库。

拓展阅读：

• 《编译原理》（龙书）
• 《程序员的自我修养：链接、装载与库》
• 中科大 华保健主讲 编译原理

交叉编译与本地编译的区别

点击展开

[TBD]

C++语言特性

匿名函数

点击展开

应用场景

Lambda表达式是C++11引入的一个新特性，它允许定义一个匿名函数并立即使用。以下是一些常见的应用场景：

1. 排序：可以使用lambda表达式定义自定义的排序规则。例如，可以使用lambda表达式对一个vector的元素进行降序排序：

   std::vector<int> nums = {1, 2, 3, 4, 5};
   std::sort(nums.begin(), nums.end(), [](int a, int b) {
       return a > b;
   });

2. 算法：许多C++的STL算法，如std::for_each，std::transform等，都可以接受lambda表达式作为参数。例如，可以使用lambda表达式将一个vector的所有元素都增加1：

   std::vector<int> nums = {1, 2, 3, 4, 5};
   std::for_each(nums.begin(), nums.end(), [](int& n) {
       n++;
   });

3. 线程：可以使用lambda表达式创建新的线程。例如，使用lambda表达式在一个新的线程中打印一条消息：

   std::thread t([]() {
       std::cout << "Hello from a new thread!" << std::endl;
   });
   t.join();

4. 函数对象：可以使用lambda表达式创建函数对象，这对于需要回调函数的场景非常有用。例如，可以使用lambda表达式定义一个函数，该函数接受一个函数对象作为参数，并在函数内部调用这个函数对象：

   auto print = [](const std::string& message) {
       std::cout << message << std::endl;
   };
   print("Hello, world!");

---

优点

由于匿名函数没有名字，可以直接在代码中定义和使用，因此可以更加灵活地组织代码结构、使代码更加简洁清晰、实现更加精细的控制流程。具体来说使用 lambda 表达式有几个主要的优点：

1. 简洁性：lambda 表达式通常比完整的函数定义更简洁，尤其是在函数体很小的情况下。这可以使代码更易于阅读和理解。

2. 局部性：lambda 表达式定义在使用它的地方，这可以增强代码的局部性，使得读者不需要在文件中跳来跳去来查找函数的定义。

3. 闭包：lambda 表达式可以捕获其外部作用域中的变量，这使得它们可以访问和操作这些变量，即使在 lambda 表达式的定义之外。这是普通函数无法做到的。

4. 匿名性：lambda 表达式是匿名的，这意味着你不需要为它们想一个名字。这在你只需要在一个地方使用函数的情况下非常有用。

5. 兼容STL：许多标准模板库（STL）的算法，如 std::sort，std::for_each 等，都接受函数对象作为参数。使用 lambda 表达式可以方便地创建这样的函数对象。

这并不意味着在工作中总是使用 lambda 表达式。在某些情况下，使用普通的函数可能更合适，例如当函数体很大，或者需要在多个地方重用同一个函数时。

---

语法

Lambda表达式一般都是以方括号[]开始，然后是圆括号()，接着是花括号{}，其基本语法如下：

[] (int a, int b) -> int { return a + b; }

其中：

• []：捕获列表，用于捕获外部变量。
• (int a, int b)：参数列表。
• -> int：拖尾返回类型，用于指定lambda表达式的返回类型，也可以省略，让编译器自动推导。
• { return a + b; }：函数体。

---

原理

Lambda表达式的底层实现通常是一个类，该类重载了函数调用运算符operator()，并且包含了捕获的变量。

在编译时，编译器会将lambda表达式转换为一个匿名类，并生成一个函数调用运算符operator()。
在运行时，lambda表达式会创建一个临时对象，然后调用这个临时对象的函数调用运算符operator()，执行lambda表达式的函数体。

例如，以下代码：

int a = 42;
auto lambda = [a](int b) { return a + b; };
std::cout << lambda(10) << std::endl;

在编译时会被转换为类似以下的代码：

class __lambda_1 {
public:
    __lambda_1(int a) : a(a) {}
    int operator()(int b) const { return a + b; }
private:
    int a;
};
int a = 42;
__lambda_1 lambda(a);
std::cout << lambda(10) << std::endl;

这里__lambda_1是一个自动生成的类，它包含了捕获的变量a，并且重载了函数调用运算符operator()，用于执行lambda表达式的函数体。

实际上，上面提到的编译器生成的类__lambda_1是一个闭包类型（closure type），它包含了捕获的变量和函数调用运算符，用于执行lambda表达式的函数体。
闭包的一个强大之处是其可以通过传值或者引用的方式捕捉其封装作用域内的变量，前面的方括号[]就是用来定义捕捉模式以及变量，我们又将其称为 lambda 捕捉块。

常用的几种捕捉方式有：

• []：默认不捕获任何变量；
• [=]：默认以值捕获所有变量，其中包括 this 指针。
• [&]：默认以引用捕获所有变量；
• [x]：仅以值捕获 x，其它变量不捕获；
• [x, y]：仅以值捕获 x 和 y，其它变量不捕获；
• [&x]：仅以引用捕获 x，其它变量不捕获；
• [=, &x]：默认以值捕获所有变量，但是 x 是例外，通过引用捕获；
• [&, x]：默认以引用捕获所有变量，但是 x 是例外，通过值捕获；
• [this]：通过引用捕获当前对象（其实是复制指针）；
• [*this]：通过传值方式捕获当前对象；

---

拓展阅读：

• C++ 中的 Lambda 表达式 - Microsoft Learn
• Lambda expressions (since C++11) - cppreference
• C++ Lambda Expressions and function objects

智能指针

点击展开

概念

智能指针是C++中的一种对象，它像原始指针一样可以指向动态分配的内存，但当它们离开作用域或被显式删除时，它们会自动删除所指向的内存，从而防止内存泄漏。

引用计数就是指某个堆区内存上的对象被多少个智能指针所共享，每个 shared_ptr 有一个关联的计数器，当一个 shared_ptr 的引用计数为 0 时，它会自动释放所管理的对象。

---

类型

C++中有三种类型的智能指针：

1. std::unique_ptr

这是一种独占所有权的智能指针，同一时间只能有一个 unique_ptr 指向给定的对象。
当 unique_ptr 被销毁时，它所指向的对象也会被自动销毁。
由于 unique_ptr 某个时刻只能有一个指针指向某个对象，因此它不允许拷贝构造和赋值。

2. std::shared_ptr

这是一种共享所有权的智能指针，多个 shared_ptr 可以指向同一个对象。
该对象只有在最后一个指向它的 shared_ptr 被销毁时才会被自动销毁。
每个 shared_ptr 对象在内部维护着两个变量：一个指向所管理对象的原始指针，一个指向引用计数的指针。
当一个 shared_ptr 被拷贝或赋值而指向某个动态内存对象时，该对象的引用计数递增。
当一个 shared_pt 被赋予一个新值（指向别的对象）或被销毁（释放）时，该对象的引用计数递减。

3. std::weak_ptr

这是一种不拥有所有权的智能指针。它是为了解决 shared_ptr 可能会引起的循环引用问题而设计的。
weak_ptr 可以从一个 shared_ptr 或者另一个 weak_ptr 中构造，但是它不会增加引用计数。

---

循环引用

循环引用是指两个或更多的对象互相引用，形成一个闭环。在这种情况下，即使没有外部引用，这些对象也无法被垃圾收集器回收，因为它们互相引用，看起来都是“活跃”的。

在C++中，std::shared_ptr可能会导致循环引用。例如，如果你有两个类A和B，它们互相包含对方的 shared_ptr，那么就会形成一个循环引用。即使没有任何其他对象引用这两个对象，它们也不会被销毁，因为它们互相引用。

class B;

class A {
public:
    std::shared_ptr<B> b_ptr;
    ~A() { std::cout << "A deleted\n"; }
};

class B {
public:
    std::shared_ptr<A> a_ptr;
    ~B() { std::cout << "B deleted\n"; }
};

int main() {
    std::shared_ptr<A> a = std::make_shared<A>();
    std::shared_ptr<B> b = std::make_shared<B>();
    a->b_ptr = b;
    b->a_ptr = a;
} // a and b are not deleted here due to circular reference

std::weak_ptr可以帮助解决这个问题。weak_ptr 是一种不控制所指向对象生存期的智能指针，它指向一个由 shared_ptr 管理的对象。
将上述代码中的std::shared_ptr替换为std::weak_ptr，就可以解决循环引用的问题。

class B;

class A {
public:
    std::weak_ptr<B> b_ptr; // change shared_ptr to weak_ptr
    ~A() { std::cout << "A deleted\n"; }
};

class B {
public:
    std::weak_ptr<A> a_ptr; // change shared_ptr to weak_ptr
    ~B() { std::cout << "B deleted\n"; }
};

int main() {
    std::shared_ptr<A> a = std::make_shared<A>();
    std::shared_ptr<B> b = std::make_shared<B>();
    a->b_ptr = b;
    b->a_ptr = a;
} // a and b are deleted here as expected

在上面这个例子中，当a和b离开作用域时，它们会被正确地销毁，因为没有std::shared_ptr指向它们。

---

内存管理

手动管理内存存在的安全隐患有哪些？

• 内存泄漏：忘记使用 delete 释放已分配的内存，导致内存泄漏。
• 重复释放：多次释放同一块内存，导致程序崩溃。
• 内存越界：访问已释放的内存，导致程序崩溃。
• 野指针：释放了内存但没有将指针置为 nullptr，导致野指针。

智能指针帮助管理内存的方式？

智能指针在C++中是一种对象，它们可以像原始指针一样指向动态分配的内存，当智能指针离开作用域或被显式删除时，它们会自动删除所指向的内存。

例如，考虑以下代码：

void foo() {
    int* raw_ptr = new int(42); // Allocate memory with new.
    // ... use raw_ptr ...
} // Memory leak! We didn't delete raw_ptr.

在这上面个例子中，我们在foo函数中使用new分配了一块内存，但是我们忘记了在函数结束时使用delete释放这块内存，所以发生了内存泄漏。如果如下使用智能指针，这个问题将得到结局。

void foo() {
    std::unique_ptr<int> smart_ptr(new int(42)); // Allocate memory with new.
    // ... use smart_ptr ...
} // No memory leak! smart_ptr automatically deletes the memory.

当smart_ptr在foo函数结束时离开作用域，它会自动删除所指向的内存，从而防止内存泄漏。

---

底层原理

C++智能指针的底层实现通常依赖于原始指针和RAII（Resource Acquisition Is Initialization）机制。

std::unique_ptr的底层实现通常是一个包装了原始指针的类，通过重载析构函数来释放资源。

std::shared_ptr的底层实现通常包含一个引用计数器，记录资源被共享的次数，以及一个原始指针指向资源。

std::weak_ptr的底层实现通常包含一个指向资源的原始指针和一个指向引用计数器的弱引用计数器。

---

使用场景

std::unique_ptr：当你需要确保一个对象在任何时候都只有一个所有者时，或者需要在堆上分配一个对象并确保它在不再需要时被删除时，可以使用unique_ptr。

std::shared_ptr：当你需要在多个所有者之间共享一个对象时，可以使用 shared_ptr。

std::weak_ptr：当你需要一个指向对象的指针，但不需要拥有该对象时，可以使用 weak_ptr。这通常用于解决 shared_ptr 的循环引用问题。

---

代码示例

#include <iostream>
#include <memory>

class Test {
public:
    Test() { std::cout << "Test created\n"; }
    ~Test() { std::cout << "Test deleted\n"; }
    void testFunc() { std::cout << "Test function\n"; }
};

int main() {
    // Using unique_ptr
    std::unique_ptr<Test> uPtr = std::make_unique<Test>();
    uPtr->testFunc();

    // Using shared_ptr
    std::shared_ptr<Test> sPtr = std::make_shared<Test>();
    {
        std::shared_ptr<Test> sPtr1 = sPtr;
        sPtr1->testFunc();
        std::cout << sPtr.use_count() << "\n"; // prints: 2
    }
    std::cout << sPtr.use_count() << "\n"; // prints: 1
    sPtr->testFunc();

    // Using weak_ptr
    std::weak_ptr<Test> wPtr = sPtr;
    {
        auto sPtr2 = wPtr.lock(); // lock() returns a shared_ptr
        if (sPtr2) {
            sPtr2->testFunc();
        }
    }

    if(wPtr.expired()) {
        std::cout << "Object has been deleted\n";
    } else {
        std::cout << "Object still exists\n";
    }

    return 0;
}

---

拓展阅读：

• Smart Pointers - cppreference
• Dynamic memory management - cppreference

并发编程

点击展开

C++11 STL

特性	API
thread	std::thread
mutex	std::mutex、std::lock_guard、std::unique_lock
condition variable	std::condition_variable、std::condition_variable_any
atomic	std::atomic、std::atomic_thread_fence
future	std::future、std::shared_future
interruption	无

---

Concurrency

并发编程是指在程序中同时执行多个任务的编程方式。这些任务可以是同时执行的、交替执行的，或者同时进行的。并发编程的目标是有效地利用计算资源，提高程序的性能、响应速度以及资源利用率。

在并发编程中，可以采用多种方式实现任务的并发执行，包括多线程、异步编程、并行计算等。这些方式可以根据任务的性质、程序的需求以及硬件平台的特性来选择。并发编程通常涉及到线程间的同步与通信、资源共享与竞态条件等问题，需要合理地设计和管理，以确保程序的正确性和性能。

并发编程在现代计算机系统中广泛应用，比如网络服务器、多线程GUI应用程序、并行计算、分布式系统等领域。通过并发编程，可以充分利用多核处理器、提高程序的并发性能，同时也可以满足用户对于快速响应和高吞吐量的需求。

---

Asynchronous

异步编程是一种编程模式，允许程序在执行某些耗时操作时不会被阻塞，而是可以继续执行其他任务。在C++中，异步编程通常通过多线程或异步IO来实现。

一种常见的实现异步编程的方式是使用C++11引入的std::async和std::future。std::async函数允许我们在一个新的线程或者线程池中执行一个函数，并返回一个std::future对象，用于获取函数的执行结果。通过std::future对象，我们可以等待异步操作的完成，也可以获取异步操作的结果。

#include <iostream>
#include <future>
#include <chrono>

// 耗时操作函数，模拟一个耗时操作，比如网络请求或者文件IO
int performTask() {
    std::this_thread::sleep_for(std::chrono::seconds(3));
    return 42; // 返回一个结果
}

int main() {
    // 启动一个异步任务，并获取 future 对象
    std::future<int> futureResult = std::async(std::launch::async, performTask);

    // 执行一些其他任务
    std::cout << "正在执行其他任务..." << std::endl;

    // 等待异步任务完成并获取结果
    int result = futureResult.get();

    // 输出异步任务的结果
    std::cout << "异步任务的结果是: " << result << std::endl;

    return 0;
}

另一种实现异步编程的方式是使用C++标准库中的std::thread和std::condition_variable等多线程工具，或者使用一些第三方库，比如Boost.Asio等，来处理异步IO操作。

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>

// 全局变量，用于存储异步任务的结果
int asyncResult;

// 耗时操作函数
void performTask() {
    // 模拟一个耗时操作，比如网络请求或者文件IO
    std::this_thread::sleep_for(std::chrono::seconds(3));

    // 将结果存储在全局变量中
    asyncResult = 42;
}

int main() {
    // 创建一个互斥量和条件变量
    std::mutex mtx;
    std::condition_variable cv;

    // 启动一个新线程执行异步任务
    std::thread asyncThread([&]() {
        performTask();

        // 异步任务完成后，通知主线程
        cv.notify_one();
    });

    // 执行一些其他任务
    std::cout << "正在执行其他任务..." << std::endl;

    // 等待异步任务完成
    std::unique_lock<std::mutex> lock(mtx);
    cv.wait(lock);

    // 输出异步任务的结果
    std::cout << "异步任务的结果是: " << asyncResult << std::endl;

    // 等待异步线程结束并释放资源
    asyncThread.join();

    return 0;
}

总的来说，异步编程可以提高程序的性能和响应速度，特别是在需要处理大量IO操作或者并发任务的情况下。

---

Multithreading

多线程编程是一种并发编程的方式，通过创建多个线程来同时执行多个任务。在多线程编程中，每个线程都可以独立执行任务，同时共享程序的内存空间。
多线程够何理利用C多核处理器资源，提高程序的性能和响应速度，避免阻塞，降低每个线程的工作量 ，提高程序的并发性能和执行效率。
多线程编程通常涉及到线程的创建、同步、通信和管理等方面的操作，需要注意线程安全性、同步机制等方面的问题，以确保多个线程能够正确地协调工作，避免竞态条件和数据不一致等问题。

ThreadManagement

下面的demo演示了如何用std::thread创建四个线程，分别演示了四种不同的创建方式和参数传递方式。

#include <iostream>
#include <thread>
#include <functional> // 引入 std::ref

// 线程函数，无参数版本
void threadFunctionNoParam() {
    std::cout << "Thread with no parameter." << std::endl;
}

// 线程函数，有参数版本
void threadFunctionWithParam(int value) {
    std::cout << "Thread with parameter: " << value << std::endl;
}

// 线程函数，使用引用类型参数
void threadFunctionWithRef(int& value) {
    // 在线程中修改引用参数
    value += 50;
    std::cout << "Thread with reference parameter: " << value << std::endl;
}

int main() {
    // 创建线程1：无参数版本
    std::thread thread1(threadFunctionNoParam);

    // 创建线程2：有参数版本，传递整数参数
    int param = 42;
    std::thread thread2(threadFunctionWithParam, param);

    // 创建线程3：匿名函数版本
    std::thread thread3([] {
        std::cout << "Thread with anonymous function." << std::endl;
    });

    // 创建线程4：传递引用类型的参数
    int data = 100;
    std::thread thread4([&data] {
        // 在线程中修改引用参数
        data += 50;
        std::cout << "Thread with reference parameter: " << data << std::endl;
    });
    // std::thread thread4(threadFunctionWithRef, std::ref(data)); // 使用 std::ref 来传递引用类型参数

    // 主线程等待线程1执行完成
    thread1.join();

    // 分离线程2，主线程不再等待其执行完成
    thread2.detach();

    // 主线程等待线程3执行完成
    thread3.join();

    // 分离线程4，主线程不再等待其执行完成
    thread4.detach();

    // 输出引用参数被修改后的值
    std::cout << "Modified data in main thread: " << data << std::endl;

    return 0;
}

ThreadPool

线程池是一种有效管理和复用线程的机制，能够减少线程创建和销毁的开销、控制并发线程数量、提高响应速度、平衡系统负载、同时简化线程的管理和调度。

下面的demo演示了如何使用C++的标准库std::thread创建多线程，并利用线程池的概念管理多个线程执行任务的。

#include <iostream>
#include <thread>
#include <vector>
#include <queue>
#include <functional>
#include <mutex>
#include <condition_variable>

class ThreadPool {
public:
    ThreadPool(size_t numThreads) : stop(false) {
        for (size_t i = 0; i < numThreads; ++i) {
            threads.emplace_back([this] {
                while (true) {
                    std::function<void()> task;
                    {
                        std::unique_lock<std::mutex> lock(queueMutex);
                        condition.wait(lock, [this] { return stop || !tasks.empty(); });
                        if (stop && tasks.empty()) return;
                        task = std::move(tasks.front());
                        tasks.pop();
                    }
                    task();
                }
            });
        }
    }

    ~ThreadPool() {
        {
            std::unique_lock<std::mutex> lock(queueMutex);
            stop = true;
        }
        condition.notify_all();
        for (std::thread &thread : threads) {
            thread.join();
        }
    }

    template<class F, class... Args>
    void enqueue(F&& f, Args&&... args) {
        {
            std::unique_lock<std::mutex> lock(queueMutex);
            tasks.emplace(std::bind(std::forward<F>(f), std::forward<Args>(args)...));
        }
        condition.notify_one();
    }

private:
    std::vector<std::thread> threads;
    std::queue<std::function<void()>> tasks;

    std::mutex queueMutex;
    std::condition_variable condition;
    bool stop;
};

// 演示任务函数
void taskFunction(int id) {
    std::cout << "Task " << id << " is being executed." << std::endl;
    // 模拟任务执行时间
    std::this_thread::sleep_for(std::chrono::seconds(1));
    std::cout << "Task " << id << " execution completed." << std::endl;
}

int main() {
    // 创建线程池，包含3个线程
    ThreadPool pool(3);

    // 向线程池添加任务
    for (int i = 0; i < 5; ++i) {
        pool.enqueue(taskFunction, i);
    }

    // 主线程等待任务完成
    std::this_thread::sleep_for(std::chrono::seconds(3));

    return 0;
}

Thread Synchronization

线程同步是一种控制多个线程在共享资源上的访问顺序和时机的机制。在多线程环境中，当多个线程同时访问共享资源时，可能会出现竞态条件（Race Condition）和数据不一致等问题，线程同步就是为了解决这些问题而引入的一种手段。

保证线程同步的方法有多种，其中一些常见的方法包括：

Mutex

互斥锁（Mutex）是一种最常见的线程同步机制，它可以确保在任意时刻只有一个线程能够访问共享资源。线程在访问共享资源之前会先获取互斥锁，访问完成后再释放互斥锁，从而确保了线程的互斥访问。

互斥量的概念可以用一个比喻来理解：假设有一个房间（共享资源），只有拿到房间的钥匙（互斥量的锁）的人才能进入房间（访问共享资源），其他人需要等待拿到钥匙后才能进入。当一个线程拿到了互斥量的锁时，其他线程就无法再拿到该锁，只能等待锁的释放。

用法示例如下：

#include <iostream>
#include <thread>
#include <mutex>

// 共享资源
int sharedData = 0;

// 互斥量
std::mutex mtx;

// 线程函数，向共享资源添加值
void addValue(int value) {
    // 加锁，保护共享资源
    mtx.lock();

    // 访问共享资源
    sharedData += value;
    std::cout << "Thread " << std::this_thread::get_id() << " adds value " << value << ", sharedData is now " << sharedData << std::endl;

    // 解锁，释放互斥量
    mtx.unlock();
}

int main() {
    // 创建两个线程
    std::thread thread1(addValue, 10);
    std::thread thread2(addValue, 20);

    // 等待线程执行完成
    thread1.join();
    thread2.join();

    // 输出最终共享资源的值
    std::cout << "Final sharedData value: " << sharedData << std::endl;

    return 0;
}

按照锁的具体类型来分类：

• 互斥锁（Mutex)：互斥锁是最基本的锁类型，用于保护共享资源的互斥访问。互斥锁适用于对共享资源的长时间操作，因为它会阻塞其他试图获取锁的线程，直到拥有锁的线程释放锁。std::mutex是C++标准库中提供的递归锁类。

• 递归锁（Recursive Mutex）：递归锁是一种特殊的互斥锁，允许同一个线程多次获得锁。递归锁可以在同一线程内对共享资源进行递归调用，避免死锁的问题。std::recursive_mutex是C++标准库提供的递归锁类。

• 自旋锁（Spinlock）：自旋锁是一种特殊类型的互斥锁，当一个线程试图获取一个已经被其他线程持有的自旋锁时，它会在一个循环中不断地尝试获取锁，而不是被阻塞。自旋锁适用于对共享资源的短时间操作，因为它可以避免线程切换的开销。C++标准库中没有提供原生的自旋锁，但可以通过原子操作等机制实现自旋锁的功能。

• 读写锁（Read-Write Lock）：读写锁允许多个线程同时读取共享资源，但在任何时候只允许一个线程写入。读写锁可以提高读取操作的并发性能，适用于读取操作频繁、写入操作较少的场景。C++标准库中没有提供原生的读写锁，但可以通过互斥锁和条件变量等组合实现读写锁的功能。

按照对并发控制的思想进行划分：

• 乐观锁（Optimistic Locking）：乐观锁是一种并发控制的策略，它假设多个线程在访问共享资源时不会发生冲突，因此在访问资源时不会立即加锁，而是在更新资源时才检查是否有冲突。如果发现冲突，就放弃更新，通常配合重试机制使用。乐观锁适用于冲突少的情况。

• 悲观锁（Pessimistic Locking）：悲观锁是一种并发控制的策略，它假设多个线程在访问共享资源时会发生冲突，因此在访问资源时就立即加锁。悲观锁适用于冲突多的情况。

Condition Variable

条件变量（Condition Variable）是一种用于线程间通信和同步的机制，它允许线程在等待某个条件满足时进入阻塞状态，直到其他线程通知条件变量并唤醒它们。条件变量通常与互斥锁一起使用，std::condition_variable用于等待某个条件的发生，而std::mutex用于保护共享资源，确保在访问共享资源时的线程安全性。

最典型的使用场景是生产者和消费者问题：

• 生产者线程负责生成产品，并将产品放入共享队列中。
• 消费者线程负责从共享队列中取出产品，并进行消费。
• 当共享队列为空时，消费者线程需要等待，直到有新的产品放入队列中。
• 当共享队列已满时，生产者线程需要等待，直到有消费者取出产品。

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>

std::queue<int> sharedQueue; // 共享队列
std::mutex mtx; // 互斥量
std::condition_variable cv; // 条件变量

// 生产者函数
void producer() {
    for (int i = 0; i < 10; ++i) {
        std::this_thread::sleep_for(std::chrono::milliseconds(500)); // 模拟生产过程
        {
            std::unique_lock<std::mutex> lock(mtx);
            sharedQueue.push(i); // 将产品放入队列中
            std::cout << "Produced: " << i << std::endl;
        }
        cv.notify_one(); // 通知消费者线程
    }
}

// 消费者函数
void consumer() {
    for (int i = 0; i < 10; ++i) {
        std::unique_lock<std::mutex> lock(mtx);
        cv.wait(lock, []{ return !sharedQueue.empty(); }); // 等待直到队列不为空
        int value = sharedQueue.front(); // 取出产品
        sharedQueue.pop();
        std::cout << "Consumed: " << value << std::endl;
    }
}

int main() {
    // 创建生产者和消费者线程
    std::thread producerThread(producer);
    std::thread consumerThread(consumer);

    // 等待线程执行完成
    producerThread.join();
    consumerThread.join();

    return 0;
}

Semaphore

信号量（Semaphore）是一种计数器，用于控制对共享资源的访问权限。它允许多个线程同时访问共享资源，但可以限制同时访问的线程数量。通过对信号量的增加和减少操作，可以实现对共享资源的访问控制和线程同步。

C++标准库（C++11及更新版本）本身并没有提供信号量的实现，但是在POSIX系统中，可以使用semaphore.h头文件提供的函数来操作信号量。这些函数包括：

• sem_init()： 初始化信号量。

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

• sem_destroy()： 销毁信号量。

  int sem_destroy(sem_t *sem);

• sem_wait()： 等待信号量。

  int sem_wait(sem_t *sem);

• sem_trywait()： 尝试等待信号量，如果无法立即获取则立即返回。

  int sem_trywait(sem_t *sem);

• sem_post()： 发送信号量。

  int sem_post(sem_t *sem);

• sem_getvalue()： 获取信号量的当前值。

  int sem_getvalue(sem_t *sem, int *sval);

以上函数用于创建、销毁、等待和发送信号量，并可以获取当前信号量的值。需要注意的是，这些函数是在POSIX标准中定义的，因此在非POSIX系统上可能不适用，或者需要额外的库支持。

下面是使用信号量解决生产者-消费者问题的例子：

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <chrono>
#include <semaphore.h>

std::queue<int> sharedQueue; // 共享队列
std::mutex mtx; // 互斥量
sem_t empty; // 空闲信号量，表示空闲的缓冲区数量
sem_t full; // 满信号量，表示已填充的缓冲区数量

const int BUFFER_SIZE = 5; // 缓冲区大小

// 生产者函数
void producer() {
    for (int i = 0; i < 10; ++i) {
        std::this_thread::sleep_for(std::chrono::milliseconds(500)); // 模拟生产过程
        sem_wait(&empty); // 等待空闲信号量
        {
            std::unique_lock<std::mutex> lock(mtx);
            sharedQueue.push(i); // 将产品放入队列中
            std::cout << "Produced: " << i << std::endl;
        }
        sem_post(&full); // 发送满信号量
    }
}
义静态变量
// 消费者函数
void consumer() {
    for (int i = 0; i < 10; ++i) {
        sem_wait(&full); // 等待满信号量
        {
            std::unique_lock<std::mutex> lock(mtx);
            int value = sharedQueue.front(); // 取出产品
            sharedQueue.pop();
            std::cout << "Consumed: " << value << std::endl;
        }
        sem_post(&empty); // 发送空闲信号量
    }
}

int main() {
    // 初始化信号量
    sem_init(&empty, 0, BUFFER_SIZE);
    sem_init(&full, 0, 0);

    // 创建生产者和消费者线程
    std::thread producerThread(producer);
    std::thread consumerThread(consumer);

    // 等待线程执行完成
    producerThread.join();
    consumerThread.join();

    // 销毁信号量
    sem_destroy(&empty);
    sem_destroy(&full);

    return 0;
}

Atomic Operation

原子操作（Atomic Operation）是一种不可分割的操作，它要么完全执行，要么完全不执行，不存在中间状态，可以确保在多线程环境中对共享变量的操作是原子性的，不会被其他线程中断。原子操作通常用于实现对共享变量的安全访问和更新，避免了竞态条件和数据不一致等问题。

std::atomic是C++标准库提供的模板类，用于执行原子操作，支持各种数据类型的原子操作，包括整数、指针、布尔值等，同时支持包括增加、读取、设置、交换等原子操作。

以下是std::atomic模板类的一些常见成员函数：

• load()：以原子方式读取std::atomic对象的值。
• store()：以原子方式设置std::atomic对象的值。
• exchange()：以原子方式交换std::atomic对象的值，并返回之前的值。
• compare_exchange_strong()和compare_exchange_weak()：以原子方式比较并交换std::atomic对象的值，可以选择强一致性或者弱一致性。

用法示例如下：

#include <iostream>
#include <atomic>

int main() {
    std::atomic<int> counter(0); // 创建一个原子类型的整数对象，初始值为0

    // 原子操作：增加计数器的值
    counter++;

    // 原子操作：读取计数器的值
    int value = counter.load();

    // 原子操作：设置计数器的值
    counter.store(10);

    // 原子操作：交换计数器的值，并返回之前的值
    int oldValue = counter.exchange(20);

    // 输出结果
    std::cout << "Value: " << value << std::endl;
    std::cout << "Old Value: " << oldValue << std::endl;

    return 0;
}

在这个示例中，我们创建了一个std::atomic对象counter，并进行了一系列原子操作，这些操作都是原子性的，不会被其他线程中断，从而确保了对共享资源的操作是安全的。

Barrier

屏障（Barrier）是一种同步机制，它可以确保所有线程在达到某个指定点之前都必须等待，然后一起继续执行。屏障通常用于多个线程在某个阶段需要等待其他线程都完成某个操作后再继续执行的场景。

C++标准库并没有提供原生的屏障（Barrier）实现。但是可以使用第三方库（如Boost库）提供的屏障来实现线程同步。以下是一个使用Boost库中的屏障的示例：

#include <iostream>
#include <boost/thread.hpp>
#include <boost/thread/barrier.hpp>

const int NUM_THREADS = 3;

boost::barrier bar(NUM_THREADS); // 创建一个屏障，指定线程数量为3

// 线程函数
void threadFunction() {
    std::cout << "Thread " << boost::this_thread::get_id() << " started." << std::endl;
    // 等待所有线程到达屏障
    bar.wait();
    std::cout << "Thread " << boost::this_thread::get_id() << " finished." << std::endl;
}

int main() {
    // 创建线程
    boost::thread_group threads;
    for (int i = 0; i < NUM_THREADS; ++i) {
        threads.create_thread(threadFunction);
    }

    // 等待所有线程完成
    threads.join_all();

    return 0;
}

在这个示例中，首先创建了一个屏障bar，指定了线程数量为3。然后创建了3个线程，并在每个线程中调用bar.wait()等待所有线程到达屏障。当所有线程都到达屏障后，它们才会继续执行后续的操作。

需要注意的是，上述代码使用了Boost库，需要在编译和链接时指定对应的库文件，并且需要安装Boost库。

---

Optimization

在并发编程中，如何确保性能？请介绍一下并发编程中的常见性能优化技巧。

并发编程中确保性能的关键在于合理的设计和优化，并发算法和数据结构，以及有效地利用计算资源和系统资源。以下是一些确保性能的常见方法：

1. 减少锁的使用： 锁是保护共享资源的关键机制，但过多地使用锁会导致线程之间频繁地竞争锁资源，降低程序的并发性能。因此，可以尽量减少锁的使用，尽量使用细粒度的锁或无锁数据结构来减少锁的竞争。

2. 使用非阻塞算法： 非阻塞算法可以避免线程之间的锁竞争，提高并发性能。常见的非阻塞算法包括无锁数据结构（如无锁队列、无锁链表等）和无锁算法（如CAS、原子操作等）。

3. 减少线程间的通信： 线程间的通信会引入额外的开销和延迟，降低程序的性能。因此，可以尽量减少线程间的通信，避免不必要的数据共享和同步操作。

4. 使用线程池： 使用线程池可以减少线程的创建和销毁开销，提高线程的复用性和效率，从而提高程序的并发性能。

5. 并行化任务： 将大型任务分解成多个小任务，并行执行可以充分利用多核处理器的计算能力，提高程序的执行效率和性能。

6. 优化数据访问模式： 合理设计数据结构和访问模式，减少内存访问和数据依赖，优化数据访问性能。

7. 使用高性能并发库： 使用高性能的并发库可以提供优化过的并发算法和数据结构，提高程序的并发性能。

8. 避免资源争用： 避免多个线程之间的资源争用，尽量减少共享资源的访问，优化资源的分配和利用，提高程序的并发性能。

综上所述，确保性能的关键在于合理设计并发算法和数据结构，有效地利用计算资源和系统资源，并尽量减少线程间的通信和资源竞争，从而提高程序的并发性能。

拓展阅读：

• C++并发编程实战
• C++并发
• C++性能优化

多态

点击展开

1. 简述多态实现的原理

   多态可以分为静态多态（编译时多态）和动态多态（运行时多态），可以理解为函数重载 & 模板和函数重写。

   • 静态多态
     • 实现方式：函数重载，由编译器确定的
     • 具体实现：
       • 允许在同一个作用域中声明多个功能类似的同名函数
       • 这些函数的参数列表、参数个数、参数类型、参数顺序不一样
       • 注意不能通过返回值来区别重载
     • 实现原理：
       • 函数名修饰
       • 编译过程
         • 预编译：把头文件中的函数声明拷贝到源文件，避免编译过程中语法分析找不到函数定义
         • 编译：语法分析，同时进行符号汇总（函数名）
         • 汇编：生成函数名和函数地址的映射，方便之后通过函数名找到函数定义的位置，从而执行函数
         • 链接：将多个文件中的符号表汇总合并
       • 通过objdump -t *.o : _ZN+类长度+类名+函数名长度+函数名+E+类型首字母
   • 动态多态
     • 实现方式：虚函数重写，由运行时确定的
     • 具体实现：
       • 在基类的函数名前加上virtual关键字，在派生类中重写该函数
       • 运行时将会根据对象的类型来调用相应的函数
       • 如果对象的类型是基类，则调用基类的函数
       • 如果对象的类型是派生类，这调用派生类的函数
     • 实现原理：
       • 早绑定：编译器编译时已经确定对象调用的函数的地址
       • 晚绑定：若类使用了virtual函数，则编译器会为类生成虚函数表，他是一个一维数组，存放虚函数的地址。
     • virtual关键字用于声明一个函数为虚函数。虚函数主要用于实现多态，即允许在派生类中重写(override)基类中的函数。虚函数表指针在构造函数中初始化。

---

2. 虚函数表和虚函数表指针

   • 虚函数表
     • what：虚函数表是一个存储类的虚函数地址的数组，每个包含虚函数的类或者从这样的类派生的类都有一个虚函数表。
     • how：虚函数表的内容在编译器编译的时候已经生成，当一个类的对象被创建时一个虚函数表也会被创建并与该对象关联。
     • why：虚函数表用于实现动态多态性。动态多态性允许我们通过基类指针调用派生类的函数。
     • where：虚函数表存放在全局数据区中的只读数据段中，每个对象的内存布局中都有一个指向虚函数表的指针。
     • when：有一个基类指针，并且想调用派生类的函数时，需要使用虚函数表。
   • 虚函数表指针：
     • what：虚函数表指针是一个指向虚函数表（vtable）的指针，每个包含虚函数的类或者从这样的类派生的类的对象都有一个虚函数表指针。
     • when：对象构造的时候，在构造函数，将虚函数表的地址赋值给对象vptr。
     • how：继承下虚函数表指针赋值过程：
       • 如果类没有构造函数，则编译器为类生成默认构造函数，从而为类对象初始化vptr。
       • 接着调用子类构造函数的时候，又将子类的虚函数表地址赋值给vptr。

---

3. 构造函数能否声明为虚函数？

   在C++中，构造函数不能声明为虚函数。这是因为虚函数的调用需要通过对象的虚函数表（vtable）来实现，而在对象构造期间，虚函数表尚未建立，因此无法通过虚函数表来调用构造函数。

---

4. 虚析构函数有什么作用？

   虚析构函数主要用于解决通过基类指针删除派生类对象时可能导致的内存泄漏问题。当基类指针指向派生类对象时，如果基类的析构函数不是虚函数，那么只会调用基类的析构函数，而不会调用派生类的析构函数，从而导致派生类对象的资源无法正确释放。

   通过将基类的析构函数声明为虚函数，可以实现在基类指针指向派生类对象时，通过基类指针调用delete操作时，会先调用派生类的析构函数，然后再调用基类的析构函数，从而确保派生类对象的资源能够正确释放。

---

5. 重写和重载的区别？

   • 重载（Overload）：指在同一个作用域内，函数名相同但参数列表不同的函数，可以通过参数的个数、类型、顺序来区分。重载是一种静态多态，由编译器在编译时根据函数的参数列表来确定调用哪个函数。
   • 重写（Override）：指在派生类中重新定义基类中的虚函数，实现多态性。重写是一种动态多态，由运行时根据对象的类型来调用相应的函数。

仿函数

点击展开

在C++中，仿函数（Functor）是一个行为类似函数的对象。它是一个类，该类重载了operator()运算符。因此，我们可以像调用函数一样调用这个类的对象。这就是为什么它被称为仿函数。仿函数可以扩展函数的功能，并且可以保存状态信息，具有很高的灵活性和可复用性。

仿函数在C++中有许多应用场景，以下是一些常见的应用场景：

1. 作为STL算法的参数：STL算法，如sort，transform等，通常接受一个函数或者仿函数作为参数。使用仿函数可以使得代码更加灵活和可重用。

   #include <iostream>
   #include <vector>
   #include <algorithm>
   
   class MyComparator {
   public:
       bool operator()(int a, int b) const {
           return a > b; // 降序排序
       }
   };
   
   class Add {
       int value; // 保存要加的值
   public:
       Add(int val) : value(val) {} // 构造函数，初始化要加的值
   
       int operator()(int x) const { // 重载函数调用运算符
           return x + value; // 返回加法操作的结果
       }
   };
   
   int main() {
       std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
       std::sort(nums.begin(), nums.end(), MyComparator());
       for (int num : nums) {
           std::cout << num << " ";
       }
       std::cout << std::endl; // 输出：9 6 5 4 3 2 1 1
   
   
       std::vector<int> vec = {1, 2, 3, 4, 5};
       std::transform(vec.begin(), vec.end(), vec.begin(), Add(5));
       std::cout << "vec: ";
       for (int num : vec) {
           std::cout << num << " ";
       }
       std::cout << std::endl; // 输出：vec: 6 7 8 9 10
   
       return 0;
   }

2. 作为比较函数：在STL的数据结构，如set，map，priority_queue等，可以接受一个比较函数或者仿函数来自定义元素的排序方式。

   #include <iostream>
   #include <queue>
   #include <vector>
   #include <functional>
   
   struct Compare : public std::binary_function<int, int, bool> {
       bool operator()(const int& a, const int& b) const {
           return a > b;
       }
   };
   
   int main() {
       std::priority_queue<int, std::vector<int>, Compare> pq;
   
       pq.push(3);
       pq.push(1);
       pq.push(4);
       pq.push(1);
       pq.push(5);
   
       std::cout << "Priority Queue: ";
       while (!pq.empty()) {
           std::cout << pq.top() << " ";
           pq.pop();
       }
       std::cout << std::endl; // 输出：Priority Queue: 5 4 3 1 1
   
       return 0;
   }

3. 在回调函数中：仿函数是类对象，可以包含成员变量，因此可以保存状态信息。这使得仿函数在执行函数调用时可以考虑到之前的状态，实现更复杂的功能。

   #include <iostream>
   #include <vector>
   #include <algorithm>
   
   // 定义一个仿函数 AddWithState
   class AddWithState {
   private:
       int state; // 保存状态信息
   public:
       // 构造函数，初始化状态信息
       AddWithState(int initialState) : state(initialState) {}
   
       // 重载函数调用运算符，将输入值与状态信息相加并返回
       int operator()(int x) {
           int result = x + state;
           state = result; // 更新状态信息
           return result;
       }
   };
   
   int main() {
       std::vector<int> vec = {1, 2, 3, 4, 5};
       int initialState = 0; // 初始状态信息为 0
   
       // 创建 AddWithState 对象，将初始状态信息传入构造函数
       AddWithState adder(initialState);
   
       // 使用仿函数进行加法操作，并将结果保存到 vec 中
       std::transform(vec.begin(), vec.end(), vec.begin(), adder);
   
       // 输出每次加法操作的结果
       std::cout << "Resulting vector: ";
       for (int num : vec) {
           std::cout << num << " ";
       }
       std::cout << std::endl;
   
       return 0;
   }

4. 作为函数对象适配器的参数： 仿函数可以与函数对象适配器一起使用，实现更复杂的功能。例如，std::bind、std::function等可以与仿函数一起使用，实现函数的组合、筛选等操作。

   #include <iostream>
   #include <functional>
   
   class MyPredicate {
   public:
       bool operator()(int x) const {
           return x % 2 == 0; // 判断是否为偶数
       }
   };
   
   int main() {
       MyPredicate predicate;
       std::function<bool(int)> isEven = std::bind(predicate, std::placeholders::_1);
   
       std::cout << isEven(3) << std::endl; // 输出 0
       std::cout << isEven(4) << std::endl; // 输出 1
       return 0;
   }

关键字

点击展开

static

static 关键字在C++中具有多种用途，用于定义静态变量、静态函数和静态常量，实现了在程序运行期间共享状态信息、提高函数的调用效率等功能。

• 修饰普通变量，修改变量的存储区域和生命周期，使变量存储在静态区，在 main 函数运行前就分配了空间，如果有初始值就用初始值初始化它，如果没有初始值系统用默认值初始化它。
• 修饰普通函数，表明函数的作用范围，仅在定义该函数的文件内才能使用。在多人开发项目时，为了防止与他人命名空间里的函数重名，可以将函数定位为 static。
• 修饰成员变量，修饰成员变量使所有的对象只保存一个该变量，而且不需要生成对象就可以访问该成员。
• 修饰成员函数，修饰成员函数使得不需要生成对象就可以访问该函数，但是在 static 函数内不能访问非静态成员。

---

this

this 是一个指向当前对象的指针，它是每个非静态成员函数的隐含参数。它指向调用该成员函数的那个对象。

• 当对一个对象调用成员函数时，编译程序先将对象的地址赋给 this 指针，然后调用成员函数，每次成员函数存取数据成员时，都隐式使用 this 指针。
• 当一个成员函数被调用时，自动向它传递一个隐含的参数，该参数是一个指向这个成员函数所在的对象的指针。

注意：

• this 并不是一个常规变量，而是个右值，所以不能取得 this 的地址（不能 &this）。
• 在以下场景中，经常需要显式引用 this 指针：
  • 为实现对象的链式引用
  • 为避免对同一对象进行赋值操作
  • 在实现一些数据结构时，如 list

---

volatile

volatile 是一个类型修饰符，用于指示编译器一个变量可能会被程序之外的因素（操作系统、硬件、其它线程等）更改。
它是来解决变量在“共享”环境下容易出现读取错误的问题，使用 volatile 关键字可以防止编译器对变量的一些优化，确保每次读取变量都是从内存中读取，而不是从寄存器中读取。

使用场景：

• 多线程环境下，一个变量在多个线程之间共享时，一个线程修改了变量的值，另一个线程需要读取这个变量的最新值。
• 硬件寄存器，如中断服务程序中会使用 volatile 修饰的变量，因为这些变量的值可能会在程序的控制之外被修改。

示例：

点击展开

#include<iostream>
using namespace std;
int main() {
    const int j = 5;
    int * p;
    void *t = (void *)(&j);
    p = (int*)t;
    (*p)++;
    cout << *p << endl;
    cout << j << endl;
    return 0;
}

输出的结果是：
6
5
输出5的原因是：编译器对其做了优化，直接将j替换为文字常量5。

#include<iostream>
using namespace std;
int main() {
    volatile const int j = 5;
    int * p;
    void *t = (void *)(&j);
    p = (int*)t;
    (*p)++;
    cout << *p << endl;
    cout << j << endl;
    return 0;
}

输出：
6
6
因为有volatile修饰变量，则在输出时，编译器不会对其优化，直接从地址中读取内容。

---

const

const 是一个类型修饰符，用它声明的类型变量表示该变量的值不能被改变。

• 修饰变量，说明该变量不可以被改变；
• 修饰指针，分为指向常量的指针（pointer to const）和自身是常量的指针（常量指针，const pointer）；
• 修饰引用，指向常量的引用（reference to const），用于形参类型，即避免了拷贝，又避免了函数对值的修改；
• 修饰成员函数，说明该成员函数内不能修改成员变量。

new

• new是操作符，而malloc是函数。
• new在调用的时候先分配内存，在调用构造函数，释放的时候调用析构函数；而malloc没有构造函数和析构函数。
• malloc需要给定申请内存的大小，返回的指针需要强转；new会调用构造函数，不用指定内存的大小，返回指针不用强转。
• new可以被重载；malloc不行
• new分配内存更直接和安全。
• new发生错误抛出异常，malloc返回null

malloc底层实现：当开辟的空间小于 128K 时，调用 brk（）函数；当开辟的空间大于 128K 时，调用mmap（）。malloc采用的是内存池的管理方式，以减少内存碎片。先申请大块内存作为堆区，然后将堆区分为多个内存块。当用户申请内存时，直接从堆区分配一块合适的空闲快。采用隐式链表将所有空闲块，每一个空闲块记录了一个未分配的、连续的内存地址。

new底层实现：关键字new在调用构造函数的时候实际上进行了如下的几个步骤：

• 创建一个新的对象
• 将构造函数的作用域赋值给这个新的对象（因此this指向了这个新的对象）
• 执行构造函数中的代码（为这个新对象添加属性）
• 返回新对象

右值引用

点击展开

概念

在C++中，左值引用（lvalue reference）和右值引用（rvalue reference）是与变量或表达式的生命周期和使用方式相关联的两种引用类型。

1. 左值引用（lvalue reference）： 左值引用绑定到具有名称的对象（即左值），并且可以延长其生命周期。左值引用通常用于传递可修改的对象，也可以用于函数重载和模板推断等场景。

int x = 5;                // x 是左值
int& ref_x = x;           // ref_x 是左值引用，绑定到 x
int& ref_x = 5;           // 编译失败，左值引用指向了右值, 引用是变量的别名，由于右值没有地址，没法被修改，所以左值引用无法指向右值
const int& ref_x = 5;     // 编译通过，const修饰了左值引用，不会修改指向值，因此可以指向右值

ref_x = 10;                               // 修改 x 的值
std::cout << "x = " << x << std::endl;    // 输出：x = 10

2. 右值引用（rvalue reference）： 右值引用绑定到临时对象或表达式（即右值），并且可以延长其生命周期。右值引用通常用于移动语义、完美转发和实现移动构造函数和移动赋值运算符等场景。

#include <iostream>

class MyClass {
public:
    MyClass() { std::cout << "Constructor" << std::endl; }
    ~MyClass() { std::cout << "Destructor" << std::endl; }
    MyClass(const MyClass&) { std::cout << "Copy constructor" << std::endl; }
    MyClass(MyClass&&) { std::cout << "Move constructor" << std::endl; }
};

MyClass createObject() {
    return MyClass(); // 返回临时对象，是右值
}

int main() {
    MyClass&& rref = createObject(); // rref 是右值引用，绑定到临时对象
    return 0;
}

在这个示例中，createObject() 函数返回一个临时对象，因此返回值是一个右值。在 main() 函数中，我们使用右值引用 MyClass&& rref 来绑定这个临时对象，延长了它的生命周期，从而使得对象在 main() 函数作用域内仍然有效。

右值引用的绑定延长了对象的生命周期，可以用于实现移动语义，避免了临时对象的不必要拷贝。

右值引用的标志是&&，右值引用专门为右值而生，可以指向右值，不能指向左值:

int &&ref_a_right = 5;   // ok

int a = 5;
int &&ref_a_left = a;   // 编译不过，右值引用不可以指向左值

ref_a_right = 6;       // 右值引用的用途：可以指向并修改右值

---

如何区分

左值引用和右值引用在语义上有很大的差异，左值引用通常用于可修改的对象，右值引用则通常用于临时对象或表达式，并且可以延长其生命周期以实现移动语义。区分左值引用和右值引用的关键在于理解它们绑定到的对象的生命周期和可修改性。

• 左值引用（lvalue reference）绑定到具有名称的对象（即左值），例如变量或对象的名称。
• 右值引用（rvalue reference）绑定到临时对象或表达式（即右值），例如临时对象、函数返回值、字面量等。

int x = 5; // x 是左值
int& lref = x; // lref 是左值引用，绑定到 x
int&& rref = 10; // rref 是右值引用，绑定到临时对象

简而言之，可以从下面的角度判断：左值可以取地址、位于等号左边；而右值没法取地址，位于等号右边。

---

使用场景

• 移动语义：右值引用常用于实现移动构造函数和移动赋值运算符，从而避免了不必要的深拷贝，提高效率。
• 完美转发：即将参数以原样传递给其他函数，无需进行多余的拷贝或移动操作。
• 临时对象的延长生命周期：通过右值引用可以延长临时对象的生命周期，使其在函数调用结束后仍然有效。

下面是一些右值引用的更多使用场景和示例：

#include <iostream>
#include <vector>
#include <utility>

// 移动语义示例：移动构造函数
class MyVector {
private:
    std::vector<int> data;
public:
    MyVector(std::vector<int>&& other) : data(std::move(other)) {
        std::cout << "Move constructor called." << std::endl;
    }
};

// 完美转发示例：使用右值引用进行完美转发
template<typename T, typename U>
void forward(T&& t, U&& u) {
    process(std::forward<T>(t), std::forward<U>(u));
}

void process(int&& x, int&& y) {
    std::cout << "Processing: " << x << ", " << y << std::endl;
}

int main() {
    // 移动语义示例：移动构造函数
    std::vector<int> temp = {1, 2, 3};
    MyVector mv(std::move(temp)); // 调用移动构造函数

    // 完美转发示例：使用右值引用进行完美转发
    int a = 1;
    int b = 2;
    forward(std::move(a), std::move(b)); // 调用 process 函数并进行完美转发

    return 0;
}

---

拓展阅读：

• Understanding Modern C++：rvalue reference
• Effective Modern C++ Item 24: Distinguish universal references from rvalue references
• 一文读懂C++右值引用和std::move

内联函数

点击展开

为什么要使用内联函数

函数调用，尤其是频繁的函数调用是有一定代价的，常伴随着参数的传递，代码的入栈，堆栈平衡等，在声明为内联函数之后：

（1）相当于把内联函数里面的内容写在调用内联函数处。
（2）相当于不用执行进入函数的步骤，直接执行函数体。
（3）相当于宏，却比宏多了类型检查，真正具有函数特性。
（4）编译器一般不内联包含循环、递归、switch 等复杂操作的内联函数。
（5）在类声明中定义的函数，除了虚函数的其他函数都会自动隐式地当成内联函数。

在代码编译的时候，编译器会将调用内联函数的地方展开，将内联函数的代码嵌入到调用内联函数的地方，而对于其他的函数，都是在运行时候才被替代。

内联函数的优点和缺点

优点：
（1）内联函数同宏函数一样将在被调用处进行代码展开，省去了参数压栈、栈帧开辟与回收，结果返回等，从而提高程序运行速度。
（2）内联函数相比宏函数来说，在代码展开时，会做安全检查或自动类型转换（同普通函数），而宏定义则不会。
（3）在类中声明同时定义的成员函数，自动转化为内联函数，因此内联函数可以访问类的成员变量，宏定义则不能。
（4）内联函数在运行时可调试，而宏定义不可以。

缺点：
（1）内联函数的代码会被复制到每一个调用它的地方，如果内联函数代码过长，会导致代码体积增大，影响程序的性能。
（2）内联函数不能进行递归调用，因为内联函数的展开是在编译时进行的，递归调用会导致无限展开，造成编译错误。
（3）是否内联不可控，内联函数只是对编译器的建议，编译器会根据函数的复杂度和调用频率等因素来决定是否内联。

如何定义内联函数？

（1）如果想把一个函数定义为内联函数，在函数名前面放置关键字 inline 即可。
（2）内联函数的定义必须在调用之前，因为编译器在调用一个函数时，需要知道函数的定义。

// 声明1（加 inline，建议使用）
inline int functionName(int first, int second,...);

// 声明2（不加 inline）
int functionName(int first, int second,...);

// 定义
inline int functionName(int first, int second,...) {/****/};

// 类内定义，隐式内联
class A {
    int doA() { return 0; }         // 隐式内联
}

// 类外定义，需要显式内联
class A {
    int doA();
}
inline int A::doA() { return 0; }   // 需要显式内联

编译器对内联函数的处理步骤：

（1）将 inline 函数的定义体复制到每一个调用内联函数的地方。
（2）为所用 inline 函数中的局部变量分配内存空间。
（3）将 inline 函数的的输入参数和返回值映射到调用方法的局部变量空间中。
（4）如果 inline 函数有多个返回点，将其转变为 inline 函数代码块末尾的分支（使用 GOTO）。

示例

#include <bits/stdc++.h>

inline bool EndsWith(const std::string &value, const std::string &ending) {
    if (ending.size() > value.size()) {
        return false;
    }
    return std::equal(ending.rbegin(), ending.rend(), value.rbegin());
}

int main() {
    std::string filename = "example.txt";
    if (EndsWith(filename, ".txt")) {
        std::cout << "The file is a text file." << std::endl;
    } else {
        std::cout << "The file is not a text file." << std::endl;
    }
    return 0;
}

指针和引用

点击展开

指针和引用的区别

相同点：引用和指针都可以作为参数传递给函数，用于更改函数作用域外的变量；也可以作为函数的参数，在传递大对象时避免复制，提升效率。

特性	指针（*）	引用（&）
定义	指针是一个变量，存储一个地址，指向内存的一个存储单元	引用是原变量的一个别名，与对象绑定后，就不可改变
空值	可以为空，可以声明为void	不能为空，不能声明为void
初始化	可以在定义后再赋值	定义的时候必须初始化
大小	sizeof 是指针大小	sizeof 是所引用的对象大小
嵌套	可以有多级指针，指向指针的指针，指向指针的指针的指针……	引用不能有引用，引用本身就是一个别名，不能再有别名了，只能有一级引用

参考链接：

• References in C++
• 值传递、指针传递、引用传递的区别

模板

点击展开

什么是模板？

模板是一种通用的编程工具，它允许程序员编写独立于数据类型的代码。在 C++ 中，模板是一种用于创建通用类或函数的机制，可以在编译时生成特定类型的类或函数。

[TBD]

迭代器

点击展开

迭代器是类模板，表现的像指针，模拟了指针的一些功能，重载了指针的一些操作符，–>、++、–等。迭代器封装了指针，是一个”可遍历STL容器内全部或部分元素”的对象，本质是封装了原生指针，是指针概念的一种提升，提供了比指针更高级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，–等操作。
迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用取值后的值而不能直接输出其自身。

设计模式

常用设计模式

点击展开

单例模式

单例模式是一种创建型设计模式，它保证一个类只有一个实例，并提供一个全局访问点。单例模式的优点包括：

• 控制实例数目：单例模式可以确保一个类只有一个实例，避免了因为多次创建实例而导致的资源浪费。

• 全局访问点：单例模式提供了一个全局访问点，这使得我们可以在任何地方都能访问到这个实例。

• 共享资源：由于单例模式只有一个实例，所以可以方便地用于共享资源，例如配置信息，缓存等。

注意，虽然单例模式有这些优点，但也有一些缺点，例如它可能导致代码的耦合度增加，且在多线程环境下需要特别注意线程安全问题。因此，在使用单例模式时需要根据具体的需求和场景进行权衡。

---

代理模式

代理模式是一种结构型设计模式，它提供了一个对象来代替另一个对象控制对原对象的访问。代理对象可以在客户端和目标对象之间起到中介的作用，并添加额外的功能。

代理模式主要包含以下三种类型：

• 虚拟代理：在需要时创建开销很大的对象。通过它来存储实例化需要很长时间的真实对象的一些信息。

• 保护代理：控制真实对象访问的权限。

• 远程代理：为一个对象在不同的地址空间提供局部代表。

代理模式通常包含以下几个角色：

• 抽象主题（Subject）：定义了 RealSubject 和 Proxy 共用接口，这样在任何使用 RealSubject 的地方都可以使用 Proxy。

• 真实主题（RealSubject）：定义了 Proxy 所代表的真实实体。

• 代理（Proxy）：保存一个引用使得代理可以访问实体，并提供一个与 Subject 的接口相同的接口。

以下是一个简单的 C++ 代理模式的例子：

class Subject {
public:
    virtual void request() = 0;
};

class RealSubject : public Subject {
public:
    void request() override {
        std::cout << "RealSubject: Handling request.\n";
    }
};

class Proxy : public Subject {
    RealSubject* real_subject_;

public:
    Proxy(RealSubject* real_subject) : real_subject_(new RealSubject(*real_subject)) {}

    void request() override {
        if (this->checkAccess()) {
            this->real_subject_->request();
            this->logAccess();
        }
    }

private:
    bool checkAccess() const {
        // Some real checks should go here.
        std::cout << "Proxy: Checking access prior to firing a real request.\n";
        return true;
    }

    void logAccess() const {
        std::cout << "Proxy: Logging the time of request.\n";
    }
};

---

观察者模式

观察者模式是一种行为型设计模式，定义了对象之间的一对多依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都会得到通知并自动更新。

这种设计模式通常用于需要实现复杂的事件处理或消息传递系统时。例如，GUI库、游戏、实时系统、分布式系统等都可能使用观察者模式。

观察者模式有以下优点：

• 解耦：观察者模式可以解耦观察者和被观察者之间的关系，使得它们可以独立变化和复用。

• 广播通信：被观察者会向所有的观察者广播通知，这是一种一对多的关系。

• 动态关系：可以在运行时动态地添加和删除观察者，改变观察者与被观察者之间的关系。

然而，观察者模式也有一些缺点：

• 过度使用或误用：如果过度使用或误用观察者模式，可能会导致程序难以理解和维护。例如，如果一个观察者的更新操作引发了另一个更新操作，可能会导致复杂的链式更新。

• 假设同步通知：观察者模式通常假设观察者在接收到通知后能立即进行更新，但在某些情况下，这可能不是可行的。例如，如果观察者的更新操作需要很长时间，或者需要从网络获取数据，那么这种同步通知的方式可能会导致程序阻塞。

• 可能引发的性能问题：如果有大量的观察者，或者观察者的处理逻辑很复杂，那么通知所有观察者可能会花费很长时间。

---

拓展阅读：

• C++设计模式

如何实现一个线程安全的单例模式？

点击展开

线程安全：在拥有共享数据的多条线程并行执行的程序中，线程安全的代码会通过同步机制保证各个线程都可以正常且正确的执行，不会出现数据污染等意外情况。

单例模式指在整个系统生命周期里，保证一个类只能产生一个实例，确保该类的唯一性。

单例模式可以分为懒汉式和饿汉式，两者之间的区别在于创建实例的时间不同：

懒汉式：指系统运行中，实例并不存在，只有当需要使用该实例时，才会去创建并使用实例。（这种方式要考虑线程安全）
饿汉式：指系统一运行，就初始化创建实例，当需要时，直接调用即可。（本身就线程安全，没有多线程的问题）

如何实现线程安全：

1. 普通的懒汉式单例没有加锁，是线程不安全的，当线程并发时会创建多个实例。

   #include <iostream>
   
   class Singleton {
   private:
       static Singleton* instance;
   
       // 私有构造函数，防止外部创建实例
       Singleton() {}
   
   public:
       // 获取单例对象实例的静态方法
       static Singleton* getInstance() {
           if (instance == nullptr) {
               instance = new Singleton();
           }
           return instance;
       }
   };
   
   Singleton* Singleton::instance = nullptr;
   
   int main() {
       // 在多线程环境下可能会创建多个实例
       Singleton* singleton1 = Singleton::getInstance();
       Singleton* singleton2 = Singleton::getInstance();
   
       std::cout << "Singleton 1 address: " << singleton1 << std::endl;
       std::cout << "Singleton 2 address: " << singleton2 << std::endl;
   
       return 0;
   }

2. 加锁的懒汉式单例，std::unique_lock<std::mutex> lock(m_Mutex); 加了互斥锁的普通懒汉式是线程安全的。

   #include <iostream>
   #include <mutex>
   
   class Singleton {
   private:
       static Singleton* instance;
       static std::mutex mutex;
   
       // 私有构造函数，防止外部创建实例
       Singleton() {}
   
   public:
       // 获取单例对象实例的静态方法
       static Singleton* getInstance() {
           std::unique_lock<std::mutex> lock(mutex);
           if (instance == nullptr) {
               instance = new Singleton();
           }
           return instance;
       }
   };
   
   Singleton* Singleton::instance = nullptr;
   std::mutex Singleton::mutex;
   
   int main() {
       Singleton* singleton1 = Singleton::getInstance();
       Singleton* singleton2 = Singleton::getInstance();
   
       std::cout << "Singleton 1 address: " << singleton1 << std::endl;
       std::cout << "Singleton 2 address: " << singleton2 << std::endl;
   
       return 0;
   }

3. 双重检查锁定的懒汉单例，通过在实例化单例对象时进行双重检查来避免了不必要的加锁，从而提高了一定的性能。

   #include <iostream>
   #include <mutex>
   
   class Singleton {
   private:
       static Singleton* instance;
       static std::mutex mutex;
       
       // 私有构造函数，防止外部创建实例
       Singleton() {}
   
   public:
       // 获取单例对象实例的静态方法
       static Singleton* getInstance() {
           // 第一次检查：判断实例是否已经存在，避免不必要的加锁
           if (instance == nullptr) {
               // 加锁，确保只有一个线程可以创建实例
               std::lock_guard<std::mutex> lock(mutex);
   
               // 第二次检查：在获取锁后再次判断实例是否已经存在
               if (instance == nullptr) {
                   instance = new Singleton();
               }
           }
           return instance;
       }
   
       // 禁止拷贝构造函数和赋值运算符，防止通过拷贝创建新实例
       Singleton(const Singleton&) = delete;
       Singleton& operator=(const Singleton&) = delete;
   };
   
   // 初始化静态成员变量
   Singleton* Singleton::instance = nullptr;
   std::mutex Singleton::mutex;
   
   int main() {
       // 获取单例对象实例
       Singleton* singleton = Singleton::getInstance();
       std::cout << "Singleton address: " << singleton << std::endl;
       
       return 0;
   }

4. 内部静态变量的懒汉单例，利用了局部静态变量的初始化是线程安全的这一特性，因为C++11保证了局部静态变量的初始化在并发情况下只会被执行一次，线程安全，且不需要使用锁，因此性能最好。

   #include <iostream>
   
   class Singleton {
   private:
       // 私有构造函数，防止外部创建实例
       Singleton() {}
   
   public:
       // 获取单例对象实例的静态方法
       static Singleton* getInstance() {
           static Singleton instance;
           return &instance;
       }
   };
   
   int main() {
       Singleton* singleton1 = Singleton::getInstance();
       Singleton* singleton2 = Singleton::getInstance();
   
       std::cout << "Singleton 1 address: " << singleton1 << std::endl;
       std::cout << "Singleton 2 address: " << singleton2 << std::endl;
   
       return 0;
   }

参考链接：

• C++ 线程安全的单例模式总结 - 小林coding - 博客园

操作系统

死锁的「产生」「预防」「避免」「检测」「解除」

点击展开

产生

死锁是在多任务环境中，两个或更多的进程无限期地等待资源，而这些资源又被等待的进程所占有。死锁通常是由于多个进程之间的资源竞争和进程间的不恰当同步造成的。

死锁的产生需要满足四个条件，也被称为死锁的四个必要条件：

• 互斥条件：一个资源每次只能被一个进程使用。
• 占有与等待条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
• 不剥夺条件：进程已获得的资源，在未使用完之前，不能强行剥夺。
• 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

---

预防

预防死锁就是破坏上面四个条件任意一个，但是实现很难：

• 破坏互斥条件：允许某些资源同时被多个进程访问。但是有些资源本身并不具有这种属性，因此这种方案实用性有限。
• 破坏占有并等待条件：实行资源预先分配策略，当一个进程开始运行之前，必须一次性向系统申请它所需要的全部资源，否则不运行；或者只允许进程在没有占用资源的时候才能申请资源（申请资源前先释放占有的资源）缺点是很多时候无法预知一个进程所需的全部资源；同时会降低资源利用率、降低系统的并发性。
• 破坏非抢占条件：允许进程强行抢占被其它进程占有的资源。会降低系统性能。
• 破坏循环等待条件：对所有资源统一编号，所有进程对资源的请求必须按照序号递增的顺序提出，即只有占有了编号较小的资源才能申请编号较大的资源。这样避免了占有大号资源的进程去申请小号资源，各个进程申请资源的顺序都是从小到大，就不会有环了

---

避免

允许系统中同时存在四个必要条件，但是每当进程提出资源申请时，系统要分析满足该资源请求后，系统是否会发生死锁，若不会发生则实施分配，否则拒绝分配。银行家算法实现了这个过程。

---

检测

画出资源分配图，检测是否存在环路。检测环路前要将资源分配图化简，化简的原理是“一个目前占有运行所需的资源的进程，迟早能够执行完成释放资源”。因此，可以从“进程—资源分配图”中找到一个既不阻塞又非孤立的进程，删除所有与该进程相连的有向边，回收资源，使之成为孤立结点，然后将所回收的资源分配给其它进程。循环此过程，直到无法化简。若仍存在环路，则该系统目前处于死锁状态。

检测到死锁后，需要解除死锁。

---

解除

破坏除了“互斥条件”之外的其他三个条件：

• 回退执行：系统定期对各个进程进行检查，将检查点的有关信息写入文件。死锁时，让某占有必要资源的进程回退到取得资源之前的一个检查点，释放的资源分配给一个死锁进程（破坏“占有且等待”）
• 抢占资源：剥夺占有进程的资源，分配给另外某些进程，直至死锁环路被打破（破坏“不可抢占”）
• 杀掉进程：一次终止一个进程，直至消除死锁环路（破坏“循环等待”）

---

拓展阅读：

• 面试题】技术面试题汇总 🔥 死锁的预防检测避免解除

虚拟地址映射到物理地址的过程

点击展开

物理地址和虚拟地址是操作系统内存管理中的两个重要概念。

1. 物理地址： 物理地址是实际存储在计算机内存芯片上的地址，也称为实际地址或真实地址。它是硬件所理解和处理的地址，用于直接访问计算机的内存单元。

2. 虚拟地址： 虚拟地址是由处理器（CPU）生成的地址，用于访问计算机内存中的数据。它是相对于程序而言的一种抽象地址，程序只能看到和使用虚拟地址，而不知道实际的物理内存地址。虚拟地址空间通常比物理内存空间大得多，因为它可以包含操作系统和其他应用程序的地址空间。

---

为什么要将虚拟地址映射到物理地址？

• Why？：将虚拟地址映射到物理地址的主要目的是实现内存管理和地址空间隔离。通过虚拟地址，操作系统可以为每个程序提供独立的地址空间，使得每个程序都认为自己拥有整个内存空间，从而实现了地址空间的隔离和保护。

---

什么时候会发生虚拟地址到物理地址之间的映射？

• When？：虚拟地址到物理地址的映射通常发生在计算机执行程序时进行内存访问时。具体来说，当程序访问内存中的数据时，处理器会生成虚拟地址，并通过硬件中的地址转换单元（MMU）将虚拟地址映射到物理地址。

---

谁来处理虚拟地址到物理地址的映射？

• Who？：虚拟地址到物理地址的映射是由硬件中的地址转换单元（MMU）来处理的。MMU是计算机体系结构中的一个重要组成部分，负责处理内存访问请求，并将虚拟地址映射到物理地址。

---

如何处理虚拟地址到物理地址的映射？

• How？：虚拟地址到物理地址的映射过程通常包括以下几个步骤：
  1. 页表查找： MMU根据虚拟地址的高位页号来查找页表。
  2. 页表项解析： 一旦找到了页表中对应的页表项，MMU会解析该项以获取物理地址页面帧号。
  3. 偏移量添加： MMU将虚拟地址中的偏移量与物理地址页面帧号相结合，得到最终的物理地址。
  4. TLB缓存（可选）： 为了加速地址转换过程，MMU可能会使用一个高速缓存，称为翻译后备缓冲器（TLB）。TLB中存储了最近的一些虚拟地址到物理地址的映射关系，如果TLB中找到了对应的映射，MMU会直接使用它而不必查询页表。
  5. 缺页处理（可选）： 如果在查询页表或TLB时发现对应的页面不在内存中（即缺页），则会触发一个缺页中断。在这种情况下，操作系统会将缺失的页面从磁盘加载到内存中，并更新页表或TLB以反映这个变化。

---

总的来说，虚拟地址到物理地址的映射是由硬件中的MMU处理的，它通过页表查找、解析页表项、偏移量添加等步骤完成映射过程。TLB缓存和缺页处理是在这个过程中的一些优化和异常处理机制。

参考文档：

• 从虚拟内存到物理内存

计算机网络

三次握手和四次挥手的过程

点击展开

TCP/IP协议中的三次握手和四次挥手是建立和关闭TCP连接时的重要过程。

三次握手（Three-Way Handshake）：

1. 客户端向服务器发送连接请求（SYN）： 客户端发送一个带有SYN（同步序列编号）标志的TCP数据包给服务器，说明客户端要建立连接，并选择一个初始序列号。

2. 服务器响应连接请求（SYN + ACK）： 如果服务器同意连接，会发送一个带有SYN和ACK（确认）标志的TCP数据包给客户端，以确认客户端的连接请求，并选择一个初始序列号作为回应。

3. 客户端确认连接（ACK）： 最后，客户端再发送一个带有ACK标志的数据包给服务器，表示连接请求已收到确认。此时，TCP连接已经建立，双方可以开始进行数据传输。

RFC 973 (TCP 规范) 中关于三次握手的描述是 three way handshake，而不是 three times handshake 或 three way handshakes。
可见，三次握手其实是在一次握手的过程中交换了三个报文，而不是进行了三次握手。
这有点像两个人见面进行一次握手时，他们的手上下摇晃三次，但这并不意味着他们进行了三次握手。

---

四次挥手（Four-Way Handshake）：

1. 发起关闭连接请求（FIN）： 当客户端或服务器决定关闭连接时，会发送一个带有FIN（结束）标志的TCP数据包给对方，表示不再向对方发送数据。

2. 对关闭请求进行确认（ACK）： 收到关闭请求的一方会发送一个带有ACK标志的TCP数据包作为确认，表示收到了关闭请求。

3. 关闭连接（FIN）： 接收到关闭请求并确认后，对方也会发送一个带有FIN标志的TCP数据包给发起关闭的一方，表示同意关闭连接。

4. 确认关闭（ACK）： 最后，发起关闭的一方收到对方的确认后，也会发送一个带有ACK标志的TCP数据包给对方，表示确认收到关闭请求。此时，TCP连接彻底关闭，双方不再传输数据。

这些过程确保了在TCP连接的建立和关闭过程中，双方都能够正确地进行通信并进行必要的确认和处理，以保证数据的可靠传输。

参考链接：

• 三次握手和四次挥手以及TCP标志位的详细介绍
• 【计算机网络】TCP 三次握手与四次挥手

TCP 与 UDP 的对比

点击展开

方面	TCP	UDP
连接性	面向连接	无连接
可靠性	提供可靠的数据传输	不提供可靠性保证
传输方式	面向字节流	面向数据报
传输距离	适用于局域网和广域网	适用于局域网
双工性	全双工	可以是全双工、半双工或单工
流量控制/拥塞控制	提供流量控制和拥塞控制	不提供流量控制和拥塞控制
应用场景	网页浏览、文件传输、电子邮件等	音频、视频流媒体、在线游戏等
应用层协议	HTTP、HTTPS、FTP、SMTP等	DNS、DHCP、TFTP、SNMP等

POST和GET的区别

点击展开

方面	POST	GET
数据位置	请求体中发送数据	URL中发送数据
数据长度限制	无限制	有限制（通常受浏览器或服务器限制 2KB）
安全性	更安全，数据不会暴露在URL中	较不安全，数据会暴露在URL中
应用	添加 / 修改服务器的数据	获取服务器的指定数据
历史记录	不可以	可以保存在历史记录中或者收藏为书签
缓存	不可被缓存	可以被缓存
数据类型	可以发送多种类型的数据（二进制、文本等）	仅能发送ASCII字符
请求类型	用于向服务器提交数据，用于创建资源	用于从服务器获取数据，用于读取资源
幂等性	非幂等，会对服务器资源进行改变	幂等（同样的请求发送多次会产生相同的结果）
安全性	需要一定的安全性措施	相对较不需要安全性措施
可见性	数据不会暴露在URL中	数据会暴露在URL中
后退 / 刷新	后退或者刷新的时候，GET是无害的	后退或者刷新的时候，POST会重新提交表单

TCP 的流量控制与拥塞控制

点击展开

[TBD]

一个Web页面请求全过程

点击展开

从浏览器键入URL到显示网页经历的一系列事件

1. 根据域名，进行 DNS 域名解析：
   当用户在浏览器中输入一个 URL（例如 www.google.com）时，浏览器首先需要将域名转换为 IP 地址，这一步骤称为 DNS 解析。浏览器会查询本地缓存、操作系统缓存、路由器缓存，最后查询 DNS 服务器，直到找到对应的 IP 地址。

2. 拿到解析的 IP 地址，建立 TCP 连接：
   一旦 DNS 解析成功并获得 IP 地址，浏览器会使用该 IP 地址与目标服务器建立 TCP 连接。这个过程包括三次握手：(1) 客户端发送 SYN（同步）包到服务器、(2) 服务器回应 SYN-ACK（同步-确认）包、(3) 客户端发送 ACK（确认）包，连接建立。

3. 向 IP 地址，发送 HTTP 请求：
   TCP 连接建立后，浏览器会向服务器发送 HTTP（或 HTTPS）请求。这个请求包含了请求方法（如 GET、POST）、请求头（如 User-Agent、Accept）以及请求的资源路径（如 /index.html）。

4. 服务器处理请求：
   服务器接收到 HTTP 请求后，会根据请求的内容进行处理。服务器可能会查询数据库、执行应用逻辑、读取文件系统等，以生成响应内容。处理完成后，服务器会准备好 HTTP 响应。

5. 返回响应结果：
   服务器将处理结果封装成 HTTP 响应，并通过 TCP 连接发送回客户端。HTTP 响应包含状态码（如 200 OK、404 Not Found）、响应头（如 Content-Type、Content-Length）以及响应体（如 HTML 文档、JSON 数据）。

6. 关闭 TCP 连接：
   在 HTTP/1.0 中，服务器在发送完响应后会关闭 TCP 连接。在 HTTP/1.1 中，默认启用了持久连接（Keep-Alive），允许复用同一个连接进行多次请求-响应对话，但在一定的空闲时间后也会关闭连接。

7. 浏览器解析 HTML：
   浏览器接收到服务器返回的 HTML 文档后，会开始解析 HTML 内容。解析过程中，浏览器会构建 DOM 树，并根据 HTML 标签加载其他资源（如 CSS、JavaScript、图片）。

8. 浏览器布局渲染：
   在解析 HTML 和加载资源的过程中，浏览器会根据 CSS 构建渲染树（Render Tree），计算每个元素的布局（Layout），并将到屏幕上。这个过程包括以下步骤：(1) 构建渲染树：将 DOM 树和 CSSOM 树结合，生成渲染树。(2) 布局：计算每个元素的位置和大小。(3) 绘制：将元素绘制到屏幕上。

数据结构和算法

堆排序「建堆」「调整」和「删除」的过程

点击展开

建堆、调整和删除是堆操作的三个主要步骤。以下是这三个步骤的简要描述：

• 建堆：建堆是将一个无序的数组构建成一个堆的过程。对于一个完全二叉树（堆就是一个完全二叉树），从最后一个非叶子节点开始，对每一个非叶子节点进行下沉操作（即调整操作），直到根节点。这个过程是O(n)的复杂度。

• 调整：调整是保持堆属性的过程。对于大顶堆，如果某个节点的值小于其子节点，那么就需要将这个节点和它的最大的子节点进行交换，然后继续对交换后的子节点进行调整，直到这个节点的值大于其所有子节点的值。对于小顶堆，调整的过程类似，只是比较和交换的条件相反。

• 删除：删除通常是删除堆顶元素。删除堆顶元素后，为了保持堆的属性，通常的做法是将最后一个元素移动到堆顶，然后进行调整。这个过程是O(log n)的复杂度，因为可能需要调整的层数等于堆的高度。

详见LeetCode 215.

class MinHeap {
private:
    vector<int> data;

    void siftUp(int i) {
        while(i > 0 && data[(i - 1) / 2] > data[i]) {
            swap(data[(i - 1) / 2], data[i]);
            i = (i - 1) / 2;
        }
    }

    void siftDown(int i) {
        while(2 * i + 1 < data.size()) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int j = left;
            if(right < data.size() && data[right] < data[left]) {
                j = right;
            }
            if(data[i] <= data[j]) {
                break;
            }
            swap(data[i], data[j]);
            i = j;
        }
    }

public:
    int top() {
        return data[0];
    }

    void push(int val) {
        data.push_back(val);
        siftUp(data.size() - 1);
    }

    void pop() {
        data[0] = data.back();
        data.pop_back();
        siftDown(0);
    }

    int size() {
        return data.size();
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        MinHeap q;
        for(auto num: nums) {
            q.push(num);
            if(q.size() > k) {
                q.pop();
            }
        }
        return q.top();
    }
};

字典序Trie树

点击展开

What（什么）：字典序，也称为词典序或者字母序，是一种排序方法，它按照字母或者数字的顺序进行排序，就像在字典中查找单词一样。

Who（谁）：程序员和数据科学家经常需要使用字典序，例如在处理字符串或者文本数据时，可能会用到字典序。在数据库查询中，也常常需要按照字典序进行排序。

When（何时）：当需要对字符串或者文本数据进行排序，或者需要在数据库中进行查询时，可能会用到字典序。

Where（何地）：字典序可以在任何需要排序或者查询的地方使用，例如在编程语言中处理字符串，或者在数据库中进行查询。

Why（为什么）：字典序可以帮助我们按照一定的顺序组织和查找数据，使得数据更容易被理解和处理。

How（如何）：在大多数编程语言中，都有内置的字符串比较函数，可以直接用来实现字典序。如果需要自定义字典序，可以使用数据结构（例如Trie）或者算法（例如字典序的下一个排列算法）来实现。

实现方式：用前缀树实现字典序

class TrieNode {
public:
    TrieNode* children[26];
    bool isEndOfWord;

    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++)
            children[i] = nullptr;
    }
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children[c - 'a'] == nullptr) {
                node->children[c - 'a'] = new TrieNode();
            }
            node = node->children[c - 'a'];
        }
        node->isEndOfWord = true;
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children[c - 'a'] == nullptr) {
                return false;
            }
            node = node->children[c - 'a'];
        }
        return node != nullptr && node->isEndOfWord;
    }

    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children[c - 'a'] == nullptr) {
                return false;
            }
            node = node->children[c - 'a'];
        }
        return node != nullptr;
    }
};

上面这个Trie实现支持插入、查找和前缀查找操作。每个TrieNode包含一个指向26个子节点的指针数组（对应26个英文字母）和一个标记该节点是否为一个单词的结束的布尔值。插入操作是将一个单词的每个字符按顺序插入到Trie中，查找操作是检查一个单词是否存在于Trie中，前缀查找操作是检查一个前缀是否存在于Trie中。

位运算拾疑

点击展开

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说到底，就是直接对整数在内存中的二进制位进行操作。使用位运算，主要目的是节约内存，使你的程序速度更快，还有就是对内存要求苛刻的地方使用。

位运算在面试中的“初衷”是考察面试者的基本功，但不幸的是，位运算所考察的知识点，大部分属于知道就知道, 不知道不知道的类型。所以有必要先知道一下。

1. 按位与（&）：将两个数的对应位进行与操作，如果两个数的对应位都为1，则结果为1，否则为0。常用于清零特定位、判断某个位是否为1等操作。

2. 按位或（|）：将两个数的对应位进行或操作，如果两个数的对应位中有一个为1，则结果为1，否则为0。常用于将特定位设置为1。

3. 按位异或（^）：将两个数的对应位进行异或操作，如果两个数的对应位不同，则结果为1，否则为0。常用于交换两个数的值、清除特定位等操作。

4. 按位取反（~）：将一个数的所有位取反，即将0变为1，将1变为0。常用于对数的位进行取反操作。

5. 左移（<<）：将一个数的所有位向左移动指定的位数，高位丢弃，低位补0。常用于实现乘以2的n次方。

6. 右移（>>）：将一个数的所有位向右移动指定的位数，低位丢弃，高位根据情况补0或者补符号位。常用于实现除以2的n次方。

奇技淫巧和常见用途：

• 交换两个数的值：使用按位异或（^）运算，即a ^= b; b ^= a; a ^= b;。
• 判断奇偶性：使用按位与（&）运算，奇数的最后一位为1，偶数的最后一位为0。
• 清零特定位：使用按位与（&）运算，将指定位设置为0。
• 设置特定位：使用按位或（|）运算，将指定位设置为1。
• 快速计算2的幂：使用左移（<<）运算，将1左移n位得到2的n次方。
• 判断一个数是否是2的幂：使用按位与（&）运算，2的幂的二进制表示中只有一位为1，其余为0，所以 n & (n - 1) == 0 表示 n 是2的幂。

#include <iostream>

// 交换两个数的值
void swap(int& a, int& b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

// 判断奇偶性
bool isEven(int n) {
    return (n & 1) == 0;
}

// 清零特定位
int clearBit(int num, int pos) {
    return num & ~(1 << pos);
}

// 设置特定位
int setBit(int num, int pos) {
    return num | (1 << pos);
}

// 快速计算2的幂
int powOf2(int n) {
    return 1 << n;
}

// 判断一个数是否是2的幂
bool isPowerOf2(int n) {
    return (n & (n - 1)) == 0;
}

int main() {
    // 交换两个数的值
    int a = 5, b = 10;
    swap(a, b);
    std::cout << "Swap: a = " << a << ", b = " << b << std::endl;

    // 判断奇偶性
    int num = 7;
    std::cout << "Is " << num << " even? " << isEven(num) << std::endl;

    // 清零特定位
    int num1 = 10;
    int pos1 = 2;
    std::cout << "Clear bit at position " << pos1 << " in " << num1 << ": " << clearBit(num1, pos1) << std::endl;

    // 设置特定位
    int num2 = 5;
    int pos2 = 1;
    std::cout << "Set bit at position " << pos2 << " in " << num2 << ": " << setBit(num2, pos2) << std::endl;

    // 快速计算2的幂
    int n = 3;
    std::cout << "2^" << n << " = " << powOf2(n) << std::endl;

    // 判断一个数是否是2的幂
    int num3 = 16;
    std::cout << num3 << " is power of 2? " << isPowerOf2(num3) << std::endl;

    return 0;
}

拓展阅读：

• https://www.bilibili.com/video/BV1YT4y117AH/

业务技能

Protobuf和Json有什么区别，车内通信应用领域有何不同？

点击展开

Protocol Buffers (protobuf) 和 JSON 是两种常用的数据序列化格式，它们都可以用于数据存储和通信。然而，它们在设计理念、性能和使用场景上有一些重要的区别：

• 数据大小和速度：Protobuf 通常比 JSON 更小，更快。Protobuf 是二进制格式，比 JSON 的文本格式更紧凑，因此在网络传输和数据存储上更有效率。同时，Protobuf 的解析和序列化速度也通常比 JSON 更快。

• 类型安全：Protobuf 是静态类型的，需要预先定义数据结构（在 .proto 文件中）。这意味着你可以在编译时获取类型安全性，并且可以利用 Protobuf 编译器生成的代码来读写数据。而 JSON 是动态类型的，数据结构可以在运行时改变，这在某些情况下可能更灵活，但也可能导致更多的运行时错误。

• 可读性和互操作性：JSON 是人类可读的，可以直接在文本编辑器中查看和编辑，而且被广泛支持在几乎所有的编程语言中。而 Protobuf 是二进制格式，不易于直接阅读和编辑，但它提供了工具可以将数据转换为可读的文本格式。Protobuf 的支持也比较广泛，但可能不如 JSON 那么普遍。

• 版本兼容性：Protobuf 设计了一套规则来处理数据结构的变化，使得新旧版本的数据结构可以相互兼容。而在 JSON 中，如果数据结构发生变化，可能需要更多的手动处理来保证兼容性。

总的来说，Protobuf 和 JSON 各有优势，适用于不同的场景。在需要可读性和广泛的语言互操作性的 Web 开发中，JSON 是一个很好的选择，因为 HTTP 请求和响应通常需要在多种不同的平台和语言之间进行交互。

在需要高效性能和强类型的车载网络通信中，Protobuf 是更好的选择，因为因为车载系统通常有严格的性能和资源限制，在车载网络中，带宽和资源通常是有限的，因此需要使用更高效的数据格式。Protobuf 的二进制格式比 JSON 的文本格式更紧凑，因此可以更有效地利用网络带宽。

拓展阅读：

1. Protobuf编码原理
2. 序列化协议Protobuf入门

介绍下DoIP报文的格式。

点击展开

DoIP（Diagnostic over Internet Protocol）是一种在以太网上进行车辆诊断的协议。它是基于TCP/IP和UDP/IP的，允许在车辆网络中进行高速、高效的数据传输。

DoIP报文的基本格式如下：

协议版本：这是一个8位的字段，表示DoIP协议的版本。当前的版本是0x02。

载荷类型：这是一个16位的字段，表示载荷的类型。例如，诊断消息、车辆识别请求等。

载荷长度：这是一个32位的字段，表示载荷的长度（以字节为单位）。

载荷：这是一个可变长度的字段，包含载荷的实际数据。其内容和长度取决于载荷类型。

源地址：这是一个16位的字段，表示发送节点的地址。

目标地址：这是一个16位的字段，表示接收节点的地址。

在实际使用中，DoIP报文通常会被封装在TCP或UDP报文中，然后通过以太网进行传输。具体的传输协议（TCP或UDP）取决于载荷类型和特定的应用需求。

拓展阅读：

• https://www.iso.org/standard/87961.html
• https://github.com/doip/doip
• http://bbs.eeworld.com.cn/thread-1275968-1-1.html

介绍下CAN报文的格式以及在工作中是如何分析CAN报文的。

点击展开

CAN（Controller Area Network）报文主要有两种格式：标准格式（CAN 2.0A）和扩展格式（CAN 2.0B）。其基本格式包括：起始位、仲裁域（包括标识符和远程传输请求位）、控制域（包括数据长度代码）、数据域、CRC域、确认域和结束位。上述两种格式的主要区别在于标识符的长度，标准格式的标识符是11位，而扩展格式的标识符是29位。

以下是CAN报文的基本结构：

• 起始位（Start of frame）：这是一个固定为0的位，表示报文的开始。

• 仲裁域（Arbitration field）：这个域包括标识符和远程传输请求位（RTR）。标识符用于标识报文的类型或目的。RTR位用于区分数据帧（RTR=0）和远程帧（RTR=1）。

• 控制域（Control field）：这个域包括数据长度代码（DLC），表示数据域中的字节数（0到8字节）。

• 数据域（Data field）：这个域包含报文的数据，长度由DLC指定。

• CRC域（CRC field）：这个域包含一个15位的循环冗余校验序列和一个固定为1的分隔位。

• 确认域（ACK field）：这个域包括一个确认位和一个固定为1的分隔位。发送节点将确认位设置为0，接收节点在成功接收报文后将其设置为1。

• 结束位（End of frame）：这是一个固定为1的位，表示报文的结束。

在CAN网络中，所有节点都会监听网络上的所有报文，并根据报文的标识符决定是否处理报文。当多个节点同时发送报文时，标识符较小的报文（即优先级较高的报文）会被优先发送。这是通过CAN协议的仲裁机制实现的。

有一些工具可以帮助在工作中分析CAN报文，例如Wireshark、Vector CANoe等。这些工具可以自动解析CAN报文，并提供一些高级的功能，如报文过滤、触发条件等。

简单介绍下MQTT的消息格式、消息类型、服务质量和连接保活特征。

点击展开

MQTT（Message Queuing Telemetyr Transport 消息队列遥测传输协议）：基于发布/订阅模式的轻量级通讯协议，该协议构建于TCP/IP协议之上。MQTT运行于TCP之上，属于应用层协议。

• 消息格式：
  每条MQTT命令消息的消息头都包含一个固定的报头，有些消息会携带一个可变报文头和一个负荷。消息格式如下：

  固定报文头 | 可变报文头 | 负荷

1. 固定报头：最少有两个字节，第一个字节包含消息的类型（Message Type）和QoS级别等标志位。第二个字节开始是剩余长度字节，该长度是后面的可变报文头加消息负载的总长度，该字段最多允许四个字节。
   剩余长度字段单个字节的最大值为0x7F. 也就是127个字节。MQTT协议规定，单个字节的最高位如果是1，表示后续还有字节存在，第八位起延续位的作用。
   由于MQTT协议最多使用四个字节表示剩余长度，并且最后一个字节的最大值只能是0x7F,而不是0xFF。所以能发送的最大消息长度是256MB，而不是512MB。

2. 可变报头：主要包含协议名，协议版本，连接标志，心跳间隔时间，连接返回码，主题名等。

3. 负荷：实际上可以理解为消息的主体。当MQTT发送的消息类型是CONNECT（连接）、PUBLISH（发布）、SUBSCRIBE（订阅）、SUBACK（订阅确认）、UBSUNSCRIBE（取消订阅）时会带有负荷。

• 消息类型：
  固定报文头中的第一个字节包含连接标志，连接标志用来区分MQTT的消息类型。MQTT协议拥有14中不同的消息类型。如下表，可简单分为连接及终止、发布和订阅、Qos2消息的机制以及各种确认ACK。

类型名称	类型值	报文说明	流动方向
CONNECT	1	客户端请求连接到服务器	客户端到服务器
CONNACK	2	连接确认	服务器到客户端
PUBLISH	3	发布消息	客户端到服务器，服务器到客户端
PUBACK	4	发布确认，针对QoS 1消息	客户端到服务器，服务器到客户端
PUBREC	5	发布收到（保证交付第一步），针对QoS 2消息	客户端到服务器，服务器到客户端
PUBREL	6	发布释放（保证交付第二步），针对QoS 2消息	客户端到服务器，服务器到客户端
PUBCOMP	7	发布完成（保证交付第三步），针对QoS 2消息	客户端到服务器，服务器到客户端
SUBSCRIBE	8	客户端订阅请求	客户端到服务器
SUBACK	9	订阅确认	服务器到客户端
UNSUBSCRIBE	10	取消订阅请求	客户端到服务器
UNSUBACK	11	取消订阅确认	服务器到客户端
PINGREQ	12	PING请求	客户端到服务器
PINGRESP	13	PING响应	服务器到客户端
DISCONNECT	14	客户端断开连接	客户端到服务器

• 服务质量：
  MQTT消息质量有三个等级，QoS 0、Qos 1、Qos 2。

1. Qos 0：最多分发一次，消息的传递完全依赖底层的TCP/IP网络，协议里没有定义应答和重试。消息只会到达服务端一次，要么就没到达。

2. Qos 1：至少分发一次、服务器的消息接收由PUBACK消息进行确认，如果通信链路或设备异常，或指定时间内没有收到确认消息，发送端会重发这条在消息头中设置了Dup位的消息。

3. Qos 2：只分发一次。最高级别的消息传递，消息丢失和重复都是不可接受的，使用这个服务质量等级会有额外的开销。

• 连接保活机制：
  MQTT客户端可以设置一个心跳间隔时间（keep Alive Timer），表示在每个心跳检测时间内发送一条消息。如果在这个时间周期内，没有业务数据相关的消息，客户端会发送一个PINGREQ消息，相应的，服务器会返回一个PINGRESP消息进行确认。

如果服务器在一个半（1.5）个心跳间隔时间周期内没有收到来自客户端的消息，就会断开与客户端的连接。心跳间隔时间最大值可以设置为18个小时，8表示客户端不会断开。

拓展阅读：https://cloud.tencent.com/developer/article/1432369

RESTful 的灵魂是什么？

点击展开

RESTful的灵魂是一种设计理念和风格，其核心思想是将Web应用程序建模为资源，并通过统一的接口（HTTP方法）对资源进行操作。RESTful架构风格强调以下几个关键特征：

1. 资源（Resources）： 将网络上的信息（如文档、图片、视频等）视为资源，并使用URI（统一资源标识符）来唯一标识每个资源。

2. 表现层状态转换（Representational State Transfer）： 客户端和服务器之间的交互通过表现层的转换来实现，客户端通过操作资源的表现形式来操作资源。

3. 无状态（Stateless）： 服务端不保存客户端的状态信息，每个请求都包含足够的信息，使服务器可以理解请求的上下文。

4. 统一接口（Uniform Interface）： 使用统一的接口对资源进行操作，包括标识资源的URI、使用标准的HTTP方法（GET、POST、PUT、DELETE等）进行操作、使用标准的媒体类型（如JSON、XML）来传输资源的表现形式。

5. 客户端-服务器架构（Client-Server）： 将系统划分为客户端和服务器，客户端负责用户界面和用户交互，服务器负责存储和管理资源。

6. 可缓存性（Cacheability）： 服务端必须声明哪些资源是可缓存的，客户端可以使用缓存来提高性能和减少网络延迟。

7. 分层系统（Layered System）： 允许系统在不影响客户端的情况下增加中间层（如代理服务器、负载均衡器等），以提高系统的可伸缩性和性能。

综上所述，RESTful的灵魂在于将Web应用程序建模为资源，并通过统一的接口和无状态的通信方式来实现客户端和服务器之间的交互，以实现系统的松耦合、可伸缩性和可重用性。

AUTOSAR 是做AP还是CP，两者有什么区别，简要介绍下？

点击展开

• 汽车领域的一套标准软件架构
• AUTOSAR的主要内容：
    ○ 完整的基础软件架构：框架，系统有哪些模块，模块间的交互
    ○ 汽车应用接口规范
    ○ 验收测试规范
    ○ 方法论
• CP：基于传统ECU的嵌入式软件平台
• AP：基于高性能智能ECU的软件中间件 [C++11、SOA、Security]
• 功能模块介绍—AP：
    ○ 通信模块（ara::com）：模块和外界交互，SOME/IP、DDS、Signal PDU、IPC
    ○ 执行模块（ara::exec）：模块在系统中如何跑起来，由一个可执行程序变成进程，管理其启动时和运行时的一些进程的行为。
    ○ 持久化模块（ara::per）：进程记录一些数据，读写一些信息，和外界配置信息交互
    ○ 时间同步（ara::tsync）：高精度时间保证。
    ○ 日志追踪（ara::log）：模块运行的记录日志。
    ○ 状态管理（ara::sm）：模块的状态转换。
    ○ 升级管理（ara::ucm）：软件升级
    ○ 诊断管理（ara::diag）

TC397

点击展开

国内L2+大多数方案 MCU:TC397 SoC:TDA4VM

CP AUTOSAR一般运行在8bit、16bit、32bit的微控制器（MCU）中，如英飞凌的TC3xx，瑞萨的RH850等。
AP AUTOSAR可以运行在64bit的高性能处理器（MPU）、CPU等中，如瑞萨的H3，英伟达的Xavier等。除此之外，AP AUTOSAR也可以运行在虚拟硬件上。
CP AUTOSAR OS是基于OSEK标准的。 AP AUTOSAR OS是POSIX OS，且至少应包含PSE51子集。

注：
OSEK/VDX、POSIX和PSE51都是操作系统标准，主要用于嵌入式系统和实时系统。

OSEK/VDX：这是一个为汽车电子控制单元（ECU）开发的开放式标准。它定义了一个实时操作系统（RTOS）的接口，以及一些相关的服务，如网络通信和诊断。OSEK/VDX标准旨在提供一个跨多个硬件平台的统一的软件架构，以简化汽车电子系统的开发和维护。

POSIX：这是一组由IEEE定义的操作系统接口标准，旨在提高软件的可移植性。POSIX标准定义了一组核心的API和服务，包括文件系统操作、进程管理、线程管理、和信号处理等。许多操作系统，包括大多数Unix和Linux变种，以及一些嵌入式操作系统，都提供了对POSIX标准的支持。

PSE51：这是POSIX标准的一个子集，专门为小型嵌入式实时系统设计。PSE51标准定义了一组最小的、对实时系统有用的API和服务，包括线程管理、时间管理、和信号量等。PSE51标准旨在提供一个适合资源受限环境的、可移植的操作系统接口。

FOTA和TBOX的通信怎么做

点击展开

云端和TBOX的通信，一边是上行和下行的通信，下行一般采用MQTT协议，将云端的信息通知给TBOX，上行信息一般较多，如版本信息、安装进度、安装状态等，一般采用HTTPS的POST、GET请求和云端交互，设计到指定的一系列车云REST接口。

MQTT：MQTT 是一种基于发布/订阅模式的轻量级消息协议，特别适合在网络带宽较小、不稳定或高延迟的环境中使用。在车云通信的下行通信中，云端需要将信息（如 FOTA 更新）推送给 TBOX，这种一对多的通信模式非常适合 MQTT。此外，MQTT 还支持持久会话和消息存储，可以确保重要的信息不会丢失。

HTTPS：HTTPS 是 HTTP 的安全版本，它在 HTTP 上添加了 SSL/TLS 协议，可以提供数据的加密传输、身份验证和消息完整性检查。在车云通信的上行通信中，TBOX 需要将信息（如版本信息、安装进度、安装状态等）发送给云端，这种一对一的通信模式非常适合 HTTPS。此外，HTTPS 的 POST 和 GET 请求可以方便地与云端的 REST 接口进行交互。

诊断仪的代码移植

点击展开

1. 理解源代码：首先，需要理解源代码的功能和结构，包括各个模块的作用，以及它们之间的交互方式。

2. 选择目标平台：然后，需要选择一个目标平台，这可能是一个不同的操作系统，或者一个不同的硬件架构。

3. 设置开发环境：根据目标平台，设置相应的开发环境，包括编译器、调试器等工具。

4. 修改代码：根据目标平台的特性，修改源代码。这可能包括修改硬件抽象层（HAL），修改操作系统相关的代码，以及修改编译器特定的代码等。

5. 编译和测试：编译修改后的代码，并在目标平台上进行测试。测试应该包括功能测试，性能测试，以及稳定性测试等。

6. 优化和调试：根据测试结果，进行必要的优化和调试。

代码移植之后怎么做验证

点击展开

1. 单元测试：对每个函数或模块进行独立的测试，使用 EXPECT_EQ 宏来检查响应是否等于预期的响应，以确保它们在新环境中的功能正确。（1.车云接口 2.整车版本 3.网络丢包）

2. 集成测试：在所有模块组合在一起后进行测试，以确保它们能够正确地协同工作。（编译通过）

3. 系统测试：在整个系统级别进行测试，以确保所有组件和服务在一起工作时的行为符合预期。（放到板子上跑）

4. 性能测试：测试系统在高负载或大数据量下的性能和稳定性。（压测）

5. 回归测试：在每次修改代码后，重新运行所有的测试，以确保修改没有引入新的错误。（查缺补漏）

6. 验收测试：最后，进行验收测试，以确保系统满足所有的业务需求和用户需求。（质量部门）

CMake的基础用法

点击展开

https://zhuanlan.zhihu.com/p/662623216

CMake是一个跨平台的自动化构建系统，主要用来管理软件构建的过程，它使用一个名为CMakeLists.txt的配置文件来指导编译和链接的过程。

make_minimum_required(VERSION x.x): 指定项目需要的最低CMake版本。

project(ProjectName): 定义项目的名称和使用的语言。

add_executable(TargetName source1 source2 ...): 添加一个可执行目标，并指定其源文件。

add_library(TargetName type source1 source2 ...): 添加一个库目标，并指定其类型（静态或动态）和源文件。

find_package(PackageName): 查找并加载外部依赖包。

target_link_libraries(TargetName library1 library2 ...): 指定目标链接的库。

诊断刷写的流程

点击展开

诊断刷写通常是指在汽车诊断过程中，通过诊断工具将新的固件刷写到汽车的电子控制单元（ECU）中。以下是一个基本的诊断刷写流程：

软件刷写总体上分为三个步骤：

1. pre-programming
2. programming
3. post-programming

刷写前：

Step 1：切换到拓展模式
（10：会话控制 03：拓展会话）

Step 2：检查刷写前提条件，如条件不满足，则退出刷写。
（31：例程控制 01：启动例程 XXX：例程ID，如车速、电源等）

Step 3：停用故障码存储功能，屏蔽故障
（85：故障码控制设置 02：停止故障码存储）

Step 4：停止发送一切通讯报文，关闭与诊断无关的报文，将节约出来的通信资源用于刷写软件，提升刷写速度。
（28：通信控制 01：停止发送报文和接收报文 01：一般通信报文 XXX结点识别号）

---

Step 1：进入编程模式
（10：会话控制 02：编程会话）

Step 2：使用27服务进行安全访问
（27：安全访问 01：请求种子 02：发送与验证Key）

Step 3：写入指纹信息，即标记写软件人的身份
（2E：DID写入）

Step 4：擦除内存
（31：例程控制 01：启动例程 FF 00：例程ID，擦除存储数据）

Step 5：调用34，36，37服务完成数据的写入。
（34：请求下载 36：传输数据 37：请求传输退出）

Step 6：执行31服务，检查刚刚写入的数据块是否正确，典型的就是执行checksum验证。如果还有数据块要写，则再跳回Step 5，如果没有，则进入Step 7。
（31：例程控制 01：启动例程 02 02：例程ID，检查内存 FF 01： 检查编程依赖）

Step 7：写入所有数据块之后，一个完整的软件也就写好了，此时需要ECU检查一下这个软件是否可用，比如软硬件兼容问题。
（11：ECU复位 01：硬件复位）

---

Step 1：切换到拓展模式
（10：会话控制 03：拓展会话）

Step 2：启用发送一般性通讯报文
（28：通信控制 00：启用发送报文和接收报文 01：一般通信报文 XXX结点识别号）

Step 3：各个ECU回复故障码的检测
（85：故障码控制设置 01：启动故障码存储）

Step 4：ECU回到默认模式
（10：会话模式 01：默认会话）

A/B分区

点击展开

1. 什么是A/B分区系统呢？

答：A分区或者B分区系统独立，两者之间可以相互切换的系统。

2. 为什么需要这样的系统呢？

答：在没有A/B功能之前，车辆控制器的刷写需要车辆停车，满足一定的安全刷写条件后，使用诊断仪或者其他上位机刷写。这一系列的操作，费时费力。为了最大程度的节省刷写时间，给用户更好的升级体验，静默刷写来了。而静默刷写建立的基础就是A/B功能，即：激活的分区，可以在车辆运行的过程中更新非激活分区。

3. 非激活分区完成更新以后，何时切换分区？

非激活分区（A分区或者B分区）完成软件更新以后，需要在下次系统启动（一般需要MCU进行系统级复位）时，进行分区切换。

4. A/B分区均启动失败以后，应该如何处理？

如果A/B分区均启动失败，程序应该进入诊断的编程会话（Programming Session），以便于程序可以被更新，避免控制器成为”板砖”。

为了Aspice做了那些工作

点击展开

ASPICE全称“AutomotiveSoftware ProcessImprovement and CapacityDetermination”，即汽车软件过程改进及能力评定。
它是一个过程模型，由过程和能力度两个维度构成，用于评价汽车行业软件设计开发的能力水平。

ASPICE评估对象是项目，而不是产品或公司体系。ASPICE评估只能证明一个公司某个项目在某个时间段的过程能力情况。

1.编写和维护技术文档，包括系统软件技术规范（SSTS）、开发接口文档等，以确保所有的软件开发活动都有明确的指导和记录。

2.为下一个阶段的工作提供输入。例如，系统需求会为软件需求提供输入，这样可以让工作有章法可循。

3.使用Jira等缺陷跟踪管理系统，明确任务和缺陷。一级需求作为epic，二级需求作为story。在这个过程中，我会与产品经理反复沟通，明确我们的目标和预期结果。

4.进行定期的内部审计和评估，以确保我们的软件开发过程符合ASPICE的要求。

5.提供培训和指导，以确保团队成员理解和遵守ASPICE规范。

6.在软件开发过程中，我会确保所有的变更都经过严格的变更控制过程，包括变更请求的提交、评审、批准和实施。

最后，我会进行持续的过程改进，以提高我们的软件开发能力和成熟度。

进程crash之后的处理

点击展开

Native层Crash处理:

• kernel捕捉到进程的异常信号(SIGABRT,SIGBUS,SIGFPE)时,调用信号处理函数；信号处理函数负责收集Crash进程的错误信息，并将错误信息通过socket发送给debugger守护进程；

• debugger守护进程接收到crash信息后，一方面告知AMS有进程发生Crash，一方面通过tomestone保存完整的现场信息；

• AMS收到Crash信息后，弹出对话框告知用户Crash信息，同时保存该crash进程的相关LOG；

• 出现 Crash 或 ANR，可以从以下几个方面处理：

可以先把墓碑文件导出来

然后再搜索其中的关键字，比如：exception、crash，看看是哪些方法或者异常导致了问题；

根据backtrace初步定位问题原因后，查找代码进行分析修复与验证。

NullPointerException - 空指针引用异常
ClassCastException - 类型强制转换异常
IllegalArgumentException - 传递非法参数异常
ArithmeticException - 算术运算异常
ArrayStoreException - 向数组中存放与声明类型不兼容对象异常
IndexOutOfBoundsException - 下标越界异常
NegativeArraySizeException - 创建一个大小为负数的数组错误异常
NumberFormatException - 数字格式异常
SecurityException - 安全异常
UnsupportedOperationException - 不支持的操作异常

GCC和GDB

点击展开

了解基础：首先要知道gdb是一个强大的UNIX和Linux下的程序调试工具，它支持多种编程语言，包括C、C++等。
基本命令：掌握gdb的启动方式，例如gdb program来直接调试程序。一些基本命令，如run、next、step、continue、break（或b）、print（或p）等，用于启动程序、单步执行、设置断点和查看变量值。
使用帮助：知道如何在gdb中使用help命令来获取帮助信息。

断点和监视点：深入了解不同类型的断点（如条件断点）和监视点（watchpoint）的设置和使用。
堆栈跟踪：学会使用backtrace（或bt）命令来查看函数调用堆栈。
变量查看：掌握如何查看和修改变量的值，包括局部变量和全局变量。
源代码导航：学习如何在gdb中导航源代码，包括设置和跳转到不同的源代码行。

（gdb）help：查看命令帮助，具体命令查询在gdb中输入help + 命令,简写h
（gdb）run：重新开始运行文件（run-text：加载文本文件，run-bin：加载二进制文件）,简写r
（gdb）start：单步执行，运行程序，停在第一执行语句
（gdb）list：查看原代码（list-n,从第n行开始查看代码。list+ 函数名：查看具体函数）,简写l
（gdb）set：设置变量的值
（gdb）next：单步调试（逐过程，函数直接执行）,简写n
（gdb）step：单步调试（逐语句：跳入自定义函数内部执行）,简写s
（gdb）backtrace：查看函数的调用的栈帧和层级关系,简写bt
（gdb）frame：切换函数的栈帧,简写f
（gdb）info：查看函数内部局部变量的数值,简写i
（gdb）finish：结束当前函数，返回到函数调用点
（gdb）continue：继续运行,简写c
（gdb）print：打印值及地址,简写p
（gdb）quit：退出gdb,简写q
（gdb）break+num：在第num行设置断点,简写b
（gdb）info breakpoints：查看当前设置的所有断点
（gdb）delete breakpoints num：删除第num个断点,简写d
（gdb）display：追踪查看具体变量值
（gdb）undisplay：取消追踪观察变量
（gdb）watch：被设置观察点的变量发生修改时，打印显示
（gdb）i watch：显示观察点
（gdb）enable breakpoints：启用断点
（gdb）disable breakpoints：禁用断点
（gdb）x：查看内存x/20xw 显示20个单元，16进制，4字节每单元
（gdb）run argv[1] argv[2]：调试时命令行传参
（gdb）set follow-fork-mode child#Makefile项目管理：选择跟踪父子进程（fork()）

差分升级

点击展开

差分算法需要解决两个主要的问题：

1. 如何高效的在old中寻找尽可能多的可用于构建new的数据流。
2. 如何尽可能缩减描述old → new所需要的字节数。

新老版本切分成定长的数据库，计算各块的hash，通过比对hash来寻找新旧之间相同的数据块。

通过后缀排序算法预处理新旧文件，将预处理的结果以后缀数组和名次数组的形式存为字典目录，基于该字典目录能能够快速查找字典数据集和待编码数据集之间的相同数据段。

HdiffPatch 的差异性比较主要通过以下步骤实现：

1. 使用滑动窗口在旧文件中查找新文件中的数据块。这个过程使用了后缀数组和最长公共前缀数组来加速查找。

2. 对于在旧文件中找到的数据块，生成一个指向旧文件中位置的引用。

3. 对于在旧文件中找不到的数据块，直接将这些数据包含在差分文件中。

4. 将所有的引用和数据块按照在新文件中的顺序组合起来，生成差分文件。

在 HdiffPatch 的源代码中，以下是一些核心的函数和方法：

1. create_compressed_diff：这是创建差分文件的主要函数。它首先调用 search_cover 函数来查找在旧文件中的数据块，然后将找到的数据块和新文件中的其他数据一起压缩，生成差分文件。

2. search_cover：这个函数使用滑动窗口和后缀数组来在旧文件中查找新文件中的数据块。

3. hdiff_private::getChecksum：这个函数用于计算数据块的校验和，用于快速比较数据块。

4. hdiff_private::save_compress：这个函数用于将数据块压缩并保存到差分文件中。

• 使用后缀数组和最长公共前缀数组加速查找：后缀数组是一个数据结构，它包含了一个字符串所有后缀的排序列表。最长公共前缀数组则存储了排序后的相邻后缀之间的最长公共前缀的长度。通过这两个数据结构，HdiffPatch 可以快速找到新文件中的数据块在旧文件中的位置。

• 使用滑动窗口查找数据块：为了减小差分文件的大小，HdiffPatch 使用一个滑动窗口在旧文件中查找数据块。这个窗口的大小是可配置的，通过调整窗口大小，可以在查找速度和差分文件大小之间找到一个平衡。

• 使用压缩算法减小差分文件的大小：HdiffPatch 支持多种压缩算法，包括 zlib，bzip2，lzma 等。通过压缩，可以进一步减小差分文件的大小。

• 使用校验和快速比较数据块：为了加速数据块的比较，HdiffPatch 使用校验和算法计算数据块的校验和。通过比较校验和，可以快速判断两个数据块是否相同。

BSDiff: APK差分升级

1. 将旧文件二进制使用后缀排序或哈希算法形成一个字符串索引。

2. 使用该字符串索引对比新文件，生成差异文件(difference file)和新增文件(extra file)。

3. 将差异文件和新增文件及必要的索引控制信息压缩为差异更新包。

1）控制文件，包含需要添加和插入二进制段的指引信息（”添加指令”指定旧文件中的偏移量和长度，从旧文件读取适当的字节数，并将其添加到差异文件中的相同字节数；”插入指令”只是指定一个长度，指定的字节数是从额外的文件中读取的）；

2）差异文件，包含近似匹配字段的字节差异；

3）新增文件，包含无法近似匹配的完全不同的字段。

这三个文件加一起会比新文件略大，但其中控制文件和差异文件是高度结构化的，意味着其均可被高效压缩，所以可以使用类似bzip2等压缩工具将更新包总文件进行非常有效的压缩。

Binder通讯原理解析

点击展开

• Binder 就是用来Client 端和 Server 端通信的。
• Binder借助了内存映射（mmap）的方法，在内核空间和接收方用户空间的数据缓存区之间做了一层内存映射。从发送方用户空间拷贝到内核空间缓存区的数据，就相当于直接拷贝到了接收方用户空间的数据缓存区，从而减少了一次数据拷贝。
• 内存映射能减少数据拷贝次数，实现用户空间和内核空间的高效互动。两个空间各自的修改能直接反映在映射的内存区域，从而被对方空间及时感知。也正因为如此，内存映射能够提供对进程间通信的支持。
• 一次完整的 Binder IPC 通信过程通常是这样：
  • 1、首先 Binder 驱动在内核空间创建一个 数据接收缓存区 ；
  • 2、接着在内核空间开辟一块内核缓存区，建立 内核缓存区 和 内核中数据接收缓存区 之间的映射关系，以及 内核中数据接收缓存区 和 接收进程用户空间地址 的映射关系；
  • 3、发送方进程通过系统调用 copyfromuser() 将数据 copy 到内核中的内核缓存区，由于内核缓存区和接收进程的用户空间存在内存映射，因此也就相当于把数据发送到了接收进程的用户空间，这样便完成了一次进程间的通信。

Android 添加自定义 native 服务

点击展开

Native服务就是用C++写的系统服务，通过init进程启动，可以实现binder接口供client调用。

1. 编写服务代码：首先，你需要用C++编写你的服务代码。这通常包括实现一个或多个Binder接口，这些接口将被其他进程（客户端）调用。

2. 编写.rc文件：.rc文件是Android的init语言脚本，用于描述应该如何启动你的服务。你需要在这个文件中指定你的服务的名称、执行路径、所需的权限等信息。

3. 编写Android.bp文件：Android.bp文件是Android构建系统的一部分，用于描述如何构建你的服务。你需要在这个文件中指定你的源代码文件、依赖库等信息。

4. 编译和安装：使用Android构建系统（如mm或mmm命令）编译你的服务。编译成功后，.rc文件会被安装到/system/etc/init/目录下，你的服务的可执行文件会被安装到/system/bin/目录下（或其他你在.rc文件中指定的位置）。

5. 配置SELinux策略：为了让你的服务在启动时能够获得必要的权限，你可能需要修改或添加SELinux策略。这通常涉及到编写.te文件和可能的.fc文件。

6. 测试你的服务：重启你的设备，你的服务应该会在启动时自动运行。你可以使用ps命令检查你的服务是否正在运行，使用logcat命令查看你的服务的日志输出。