C++语言的八股文

C++面向对象的特性

• 封装——隐藏对象的属性和实现细节，仅对外公开接口和对象进行交互，将数据和操作数据的方法进行有机结合。
• 继承——允许程序员在保持父类特性的基础上进行扩展，增加功能，这样产生的新类，称为子类；父类和子类存在父子关系，即：
  • 子类拥有父类的所有属性和行为
  • 子类对象可以作为父类对象使用
  • 子类中可以添加父类没有的方法和属性
• 多态——为不同数据类型的实体提供统一的接口。
  • 动态多态（dynamic polymorphism）：通过类继承机制和虚函数机制生效于运行期。可以优雅地处理异质对象集合，只要其共同的基类定义了虚函数的接口。也被称为子类型多态（Subtype polymorphism）或包含多态（inclusion polymorphism）。在面向对象程序设计中，这被直接称为多态。
  • 静态多态（static polymorphism）：模板也允许将不同的特殊行为和单个泛化记号相关联，由于这种关联处理于编译期而非运行期，因此被称为“静态”。可以用来实现类型安全、运行高效的同质对象集合操作。（通过函数重载和模板来实现）

虚函数

• 指被virtual关键字修饰的成员函数。实现多态性，通过指向派生类的基类指针或引用，访问派生类中同名覆盖成员函数。
• 在类对象的头4个字节中，有一个指向这个虚函数表的指针，称为Vptr；（一个类的多个实例共享同一个虚函数表）
• 构造函数不可以有虚函数，析构函数可以有虚函数。（析构函数常常被声明为virtual，这是因为当父类的析构函数未声明为virtual时，如果父类指针指向一个子类的对象，那么当delete该指针时，子类的析构函数不会被调用，从而造成内存泄漏）

虚继承和虚基类

• 为了解决多继承时的命名冲突和冗余数据问题，C++ 提出了虚继承，使得在派生类中只保留一份间接基类的成员。
• 虚继承的目的是让某个类做出声明，承诺愿意共享它的基类。其中，这个被共享的基类就称为虚基类（Virtual Base Class）。在这种机制下，不论虚基类在继承体系中出现了多少次，在派生类中都只包含一份虚基类的成员。

指针和引用

• 引用：引用可以看作是一个指针常量来实现的，引用是一个内存对象的别名。
• 指针：指针指向一个内存对象，保存了这个对象的内存地址。

内置数组和指针

• 内置数组：内置数组是用于储存多个相同类型数据的集合。
• 指针：指针指向一个内存对象，保存了这个对象的内存地址。

• 易混淆点：
  • 指针数组：一个元素对象为指针的数组。
  • 数组指针：指向数组的指针。

static关键字

• 控制可见范围，不用担心重名问题。
• 保持变量内容的持久。
• 默认初始化为0。
• 类成员声明static，static成员为类所拥有，而非实例所拥有。

全局静态变量和局部静态变量的异同

• 不同点：作用域范围不同，全局静态变量具有文件作用域，局部静态变量具有块作用域。
• 相同点：生命周期都是所属模块装载到所属模块卸载。

C++11新特性

• nullptr

• 类型推导（auto和decltype），

  • auto是让编译器通过初始值来推算变量的类型（用来缩写类型和简化声明）；（auto不能传递const特性）
  • decltype在C++中，作为操作符，用于查询表达式的数据类型;主要是为泛型编程而设计，以解决泛型编程中，由于有些类型由模板参数决定，而难以（甚至不可能）表示之的问题。

• 区间迭代

for(auto ch : s){
}

• 构造函数（委托构造，继承构造）
• Lambda表达式
• 新增容器（std::array，std::forward_list，无序容器，std::tuple），
• 服务于string的正则表达式（std::regex，std::regex_match->std::match_results）

 if (std::regex_match ("subject", std::regex("(sub)(.*)") ))
    std::cout << "匹配成功\n";

• 语言级线程支持（std::thread，std::mutex/std::unique_lock，std::condition_variable，std::future/std::packaged_task）

• 右值引用和move语义

• 智能指针（unique_ptr、shared_ptr、weak_ptr）

• std::move和std::forward

  • std::move(t)用来表示对象t可以被移动，即允许t所占有的资源转移到另一对象上。比较特别使用方式是：用std::move生成一个xvalue（xvalue是定义的右值，有实体，可以被移动。）*表达式来标识它的参数t，等价于通过static_cast转换为右值引用类型（static_cast<typename std::remove_reference<T>::type&&>(t)。
  • std::forward<T>，将左值转换为左值还是右值取决于T的类型；只能将右值转换为右值，不允许右值转换为左值。

• std::bind

  • 函数模板bind为f生成一个转发调用包装器。调用这个包装器相当于调用f，并将其一些参数绑定到args上。

#include <iostream>
#include <functional>

void f(int n1, int n2, int n3, const int& n4, int n5)
{
    std::cout<< n1 << ' ' << n2 << ' ' << n3 << ' ' << n4 << ' ' << n5 << '\n';
}


int main(){
   using namespace std::placeholders;
    std::cout << "1) argument reordering and pass-by-reference: ";
    int n = 7;
    // (_1 and _2 are from std::placeholders, and represent future
    // arguments that will be passed to f1)
    auto f1 = std::bind(f, _2, 42, _1, std::cref(n), n);
    n = 10;
    f1(1, 2, 1001); // 1 is bound by _1, 2 is bound by _2, 1001 is unused
                    // makes a call to f(2, 42, 1, n, 7)

  return 0;
}
//输出为：argument reordering and pass-by-reference: 2 42 1 10 7

为什么使用C++11？

• 更友好的语法规则。（auto、lambda）
• 更强大的容器库。（无序容器）
• 更强大的性能优势。（右值引用，定制模板）
• 内存泄漏。（智能指针）
• 更清晰的代码意图。（override、final和nullptr）
• 编译期错误检查。（static_assert）

智能指针

• 智能指针主要用于管理在堆上分配的内存，它将普通的指针封装为一个栈对象。
• 当栈对象的生存周期结束后，会在析构函数中释放掉申请的内存，从而防止内存泄漏。

shared_ptr如何实现？

• T类型为任意类型
• 需要实现的函数包括：
  • 带T类型传参的构造函数
  • 拷贝构造函数
  • 赋值构造函数
  • 析构函数
  • 解引用运算符
  • ->运算符
• 需要拥有的成员变量：
  • 指向一个整型对象的指针
  • 指向一个T类型对象的指针

template<typename T>

class SharedPtr {

public:

        SharedPtr(T* p) :countPtr(new int(1)), point(p) {}

       SharedPtr(SharedPtr<T>& other) :countPtr(&(++*other.countPtr)), point(other.point) {}

       SharedPtr<T>& operator=(SharedPtr<T>& other) {

              ++* other.countPtr;

              if (this->_ptr && 0 == -- * this->countPtr) {

                     delete countPtr;

                     delete point;

              }

              this->countPtr = other.countPtr;

              this->point = other.point;

              return *this;

       }
       T& operator*() {

              return *point;

       }

       T* operator->() {

              return point;

       }

       ~SharedPtr() {

              if (-- * countPtr == 0) {

                     delete countPtr;

                     delete point;

              }

       }

private:

       int* countPtr;

       T* point;

};

std::make_shared和std::shared_ptr<T>(new T(args...))有啥区别？

参考

• 内存分配次数
  • 内存分配次数不同。（左：1次。右：2次）
• 弱引用
  • 如果任何std::weak_ptr在所有共享所有者的生命周期结束后引用了std::make_shared创建的控制块，T所占用的内存将持续存在，直到所有弱所有者也被销毁，如果(T)的sizeof很大，这可能是不可取的。
• 公共构造函数
  • 如果std::shared_ptr<T>(new T(args…))是在可访问的上下文中执行，可以调用T的非公共构造函数，而std::make_shared要求对所选构造函数进行公共访问。
• 删除器
  • 与std::shared_ptr构造函数不同，std::make_shared不允许自定义删除器。
• 操作符new。
  • std::make_shared使用::new，因此，如果使用类特定的operator new设置了任何特殊行为，它将不同于std::shared_ptr<T>(new T(args…))

RAII

• 全称为Resource Acquisition Is Initialization，中译为：资源获取就是初始化。C++标准保证任何情况下，已构造的对象最终会销毁，即它的析构函数最终会被调用。

野指针

• 野指针是指针指向的位置是不可知的（随机的、不正确的、没有明确限制的）。
  
  
• 出现野指针的原因：
  • 未初始化
  • 指针所指向的对象已经释放，但未将指针置为nullptr

#pragma once和#ifndef的区别

• #ifndef的方式受C/C++语言标准支持。它不光可以保证同一个文件不会被包含多次，也能保证内容完全相同的两个文件（或者代码片段）不会被不小心同时包含。
• #pragma once一般由编译器提供保证：同一个文件不会被包含多次。——pragma的中文含义是编译指示，在这个语句中指示编译器只编译一次该文件。

new和malloc

内存分区

堆和栈

内存对齐的原因

• 平台原因(移植原因)：不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。
• 性能原因：数据结构(尤其是栈)应该尽可能地在自然边界上对齐。原因在于，为了访问未对齐的内存，处理器需要作两次内存访问；而对齐的内存访问仅需要一次访问。

Cast变换

• C++为了规范C中的类型转换,加强类型转换的可视性，引入了以下四种类型转换。

构造函数有那些？

• 默认构造函数
• 带参数的构造函数
• 委托构造函数
• 拷贝构造函数和拷贝赋值运算符
• 移动构造函数和移动赋值运算符

vector是不是线程安全的？

参考

• vector不是线程安全的，并发读写导致读方的迭代器失效。

• 处理线程安全的方法：

  • 加锁。
  • 固定vector的大小。

shared_ptr是线程安全的吗？

是，为了满足线程安全需求，引用计数器通常使用std::atomic::fetch_add和std::memory_order_relaxed的等价递增(递减需要更强的顺序来安全地销毁控制块)。

std::map和std::unordered_map的实现原理

• std::map：红黑树（一种特殊的平衡二叉树），特性如下：
  • 只有红、黑两种节点。
  • 根节点为黑节点。
  • 叶子节点为黑节点，并且是nil节点。
  • 红节点的子节点都是黑节点。
  • 对于任意结点而言，其可达的叶子节点上的每条路径都包含相同数目的黑结点。
• std:unordered_map：哈希表，哈希冲突的处理方式：
  • 采取链表的形式存储相同哈希值的对象。
  • 根据负载因子来控制是否rehash来调整哈希表的表长。

std::condition_variable::wait为什么需要一个unique_lock<mutex>的变量lck？

• wait函数的实现：
  • 执行lck的unlock()方法（其他线程不再被阻塞）
  • 沉睡等待唤醒
  • 其他线程调用了notify系列方法
  • 沉睡线程被唤醒，执行lck.lock()

源代码到可执行程序过程

• 预处理
  • 宏定义指令（#define）
  • 条件编译指令（#ifdef）
  • 头文件包含指令（#include）
  • 特殊符号（LINE、FILE）
• 编译
  • 语法分析，词法分析，语义分析，符号汇总，然后生成汇编代码文件
• 汇编
  • 把汇编语言代码翻译成目标机器指令
• 链接
  • 将有关的目标文件彼此相连接，也即将在一个文件中引用的符号同该符号在另外一个文件中的定义连接起来，使得所有的这些目标文件成为一个能够被操作系统装入执行的统一整体。

锁的种类有那些？

• 互斥锁（std::mutex）
  • 可以避免多个线程在某一时刻同时操作一个共享资源，标准C++库提供了std::unique_lock类模板，实现了互斥锁的RAII惯用语法：

       std::unique_lock<std::mutex> lk(mtx_sync_);

• 条件锁（std::condition_variable）

  • 条件锁等同于条件变量，某一个线程因为某个条件未满足时可以使用条件变量使该程序处于阻塞状态。一旦条件满足了，即可唤醒该线程(常和互斥锁配合使用)，唤醒后，需要检查变量，避免虚假唤醒。

• 读写锁（std::shared_lock）

  • 也被称作“共享-独占锁”，当读写锁以读模式锁住时，它是以共享模式锁住的；当它以写模式锁住时，它是以独占模式锁住的。

• 递归锁（std::recursive_mutex）

  • std::recursive_mutex 允许同一个线程对互斥量多次上锁（即递归上锁）

• 自旋锁（spin_mutex）

  • 自旋锁是一种基础的同步原语，用于保障对共享数据的互斥访问。与互斥锁相比，在获取锁失败的时候不会使得线程阻塞而是一直自旋尝试获取锁。当线程等待自旋锁的时候，CPU不能做其他事情，而是一直处于轮询忙等的状态。自旋锁主要适用于被持有时间短，线程不希望在重新调度上花过多时间的情况。

class spin_mutex {
       std::atomic<bool> flag = ATOMIC_VAR_INIT(false);
public:
       spin_mutex() = default;
       spin_mutex(const spin_mutex&) = delete;
       spin_mutex& operator= (const spin_mutex&) = delete;
       void lock() {
              bool expected = false;
              while (!flag.compare_exchange_strong(expected, true))
                     expected = false;
       }
       void unlock() {
              flag.store(false);
       }
}

C++与Lua的相互调用

Lua和C++ 交互机制的基础在于Lua提供了一个虚拟栈，C++ 和Lua之间的所有类型的数据交换都通过这个栈完成。无论何时C想从Lua中调用一个值，被请求的值将会被压入栈，无论何时C想要传递一个值给Lua，首先将整个值压栈，然后就可以在Lua中调用。

• C++调用Lua：
  • 获取Lua值：调用lua_getlocal获取值->压栈->调用该C API lua_toXXX将栈中元素取出转成相应的C类型的值
  • 调用Lua函数：调用lua_getglobal获取函数->压栈->参数入栈->lua_pcall调用对应函数->返回值入栈
• Lua调用C++：
  • 包装成Lua_CFunction->调用lua_register完成注册->根据注册名调用

生产者和消费者简易实现

参考

条件变量和互斥锁（C++11）

#include <iostream>           
#include <queue>
#include <thread>             
#include <mutex> 
#include <condition_variable> 
using namespace std;

mutex mtx;
condition_variable produce, consume;  // 条件变量是一种同步机制，要和mutex以及lock一起使用

queue<int> q;     // shared value by producers and consumers, which is the critical section
int maxSize = 20;

void consumer()
{
    while (true)
    {
        this_thread::sleep_for(chrono::milliseconds(1000));
        unique_lock<mutex> lck(mtx);
        consume.wait(lck, [] {return q.size() != 0; });     // wait(block) consumer until q.size() != 0 is true

        cout << "consumer " << this_thread::get_id() << ": ";
        q.pop();
        cout << q.size() << '\n';

        produce.notify_all();                               // nodity(wake up) producer when q.size() != maxSize is true
    }
}

void producer(int id)
{
    while (true)
    {
        this_thread::sleep_for(chrono::milliseconds(1000));      // producer is a little faster than consumer  
        unique_lock<mutex> lck(mtx);
         produce.wait(lck, [] {return q.size() != maxSize; });   // wait(block) producer until q.size() != maxSize is true

        cout << "producer " << this_thread::get_id() << ": ";
        q.push(id);
        cout << q.size() << '\n';

        consume.notify_all();                                   // notify(wake up) consumer when q.size() != 0 is true
    }
}

int main()
{
    thread consumers[2], producers[2];

    // spawn 2 consumers and 2 producers:
    for (int i = 0; i < 2; ++i)
    {
        consumers[i] = thread(consumer);
        producers[i] = thread(producer, i + 1);  //thread：第一个参数是task任务，第二个参数是task函数的参数 
    }

    // join them back: (in this program, never join...)
    for (int i = 0; i < 2; ++i)
    {
        producers[i].join();
        consumers[i].join();
    }

    system("pause");
    return 0;
}

信号量（C++20）

#include <iostream>           
#include <queue>
#include <thread>             
#include <semaphore>
using namespace std;

queue<int> q;     // shared value by producers and consumers, which is the critical section
int maxSize = 20;

counting_semaphore semaphore(0);

void consumer()
{
    while (true)
    {
        this_thread::sleep_for(chrono::milliseconds(1000));
        semaphore.acquire();

        cout << "consumer " << this_thread::get_id() << ":";
        q.pop();
        cout << q.size() << '\n';
    }
}

void producer(int id)
{
    while (true)
    {
        this_thread::sleep_for(chrono::milliseconds(1000));      // producer is a little faster than consumer  
        
        cout << "producer " << this_thread::get_id() << ":";
        q.push(id);
        cout << q.size() << '\n';
        semaphore.release();
    }
}

int main()
{
    thread consumers[2], producers[2];

    // spawn 2 consumers and 2 producers:
    for (int i = 0; i < 2; ++i)
    {
        consumers[i] = thread(consumer);
        producers[i] = thread(producer, i + 1);  //thread：第一个参数是task任务，第二个参数是task函数的参数 
    }

    // join them back: (in this program, never join...)
    for (int i = 0; i < 2; ++i)
    {
        producers[i].join();
        consumers[i].join();
    }

    system("pause");
    return 0;
}

无锁队列

参考

• 重要思想（CAS）

CAS是英文单词Compare and Swap的缩写，翻译过来就是比较并替换。
CAS机制中使用了3个基本操作数：内存地址V，旧的预期值A，要修改的新值B。
更新一个变量的时候，只有当变量的预期值A和内存地址V当中的实际值相同时，才会将内存地址V对应的值修改为B。

• 通过atomic类来实现

template偏特化

参考

template偏特化是相对于template全特化而言的，即只特化了部分模板参数。

• 类模板偏特化

template <typename T, typename Allocator_T>
class MyVector {
public:
    MyVector() {
        std::cout << "Normal version." << std::endl;
    }
};

template <typename T>
class MyVector<T, DefaultAllocator> {
public:
    MyVector() {
        std::cout << "Partial version." << std::endl;
    }
};

• 函数模板偏特化（C++20）

template <typename A, typename B>
void f(A a, B b) {
    std::cout << "Normal version." << std::endl;
}

template <typename A, typename B>
requires std::integral<B>
void f(A a, B b) {
    std::cout << "Partial version." << std::endl;
}

类的函数后面加一个const

意味着只能修改static或mutable成员。

左值和右值

• glvalue：一个表达式，它的求值决定了一个对象或函数的标识。
• prvalue：求值的表达式。1.计算内置操作符的操作数的值。2.初始化一个对象。
  结果对象可能是一个变量、一个由new创建的对象、临时物化物或者它的一个成员。需注意，非void的丢弃表达式有一个结果对象(物化的临时表达式) ，此外，每个类和数组prvalue都有一个结果对象，除非它是decltype的操作数。
• xvalue：(一个“即将过期”的值)是glvalue的一种，它表示一个对象的资源可以被重用;

左值：是glvalue但不是xvalue。
右值：是prvalue或者xvalue。

可重入

可重入函数主要用于多任务环境中，一个可重入的函数简单来说就是可以被中断的函数，也就是说，可以在这个函数执行的任何时刻中断它，转入OS调度下去执行另外一段代码，而返回控制时不会出现什么错误。

C++17新特性

• 类型擦除（std::any）

计算机网络的八股文

OSI七层模型

• 应用层
  • 网络服务与最终用户的一个接口。
  • 协议有：HTTP FTP TFTP SMTP SNMP DNS TELNET HTTPS POP3 DHCP
  • 数据单元为：消息
• 表示层
  • 数据的表示、安全、压缩。
  • 格式有，JPEG、ASCll、EBCDIC、加密格式等。
  • 数据单元为：消息
• 会话层
  • 建立、管理、终止会话。
  • 对应主机进程，指本地主机与远程主机正在进行的会话。
  • 数据单元为：消息
• 传输层
  • 定义传输数据的协议，端口号，以及流控和差错校验。
  • 协议有：TCP UDP，数据包一旦离开网卡即进入网络传输层。
  • 数据单元为：数据段
• 网络层
  • 进行逻辑地址寻址，实现不同网络之间的路径选择。
  • 协议有：ICMP IGMP IP（IPV4 IPV6）
  • 数据单元为：数据报
• 数据链路层
  • 建立逻辑连接、进行硬件地址寻址、差错校验等功能。（由底层网络定义协议）
  • 将比特组合成字节进而组合成帧，用MAC地址访问介质，错误发现但不能纠正。
  • 数据单元为：帧
• 物理层
  • 建立、维护、断开物理连接。（由底层网络定义协议）
  • 数据单元为：比特

http和https的区别

https 主要由两部分组成：http + ssl / tls，也就是在 http 上又加了一层处理加密信息的模块。服务端和客户端的信息传输都会通过 tls 进行加密，所以传输的数据都是加密后的数据。

• https协议需要到CA申请证书，一般免费证书较少，因而需要一定费用。
• http是超文本传输协议，信息是明文传输，https则是具有安全性的ssl/tls加密传输协议，所以https相对安全。
• 连接方式和端口不同：
  • http：连接是无状态的，端口是80。
  • https：连接也是无状态的，不过存在身份验证环节，并且传递数据存在加密解密环节，端口是443。

https加密算法

参考

• 对称加密算法：
   需要对加密和解密使用相同密钥的加密算法。所谓对称，就是采用这种加密方法的双方使用方式用同样的密钥进行加密和解密。密钥是控制加密及解密过程的指令。算法是一组规则，规定如何进行加密和解密。

• 非对称加密算法：
   非对称加密算法需要两个密钥：公开密钥（publickey:简称公钥）和私有密钥（privatekey:简称私钥）。公钥与私钥是一对，如果用公钥对数据进行加密，只有用对应的私钥才能解密。如果用公钥对数据进行加密，只有用对应的私钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。

• 散列/哈希算法：
   指把数据通过某种公开的算法变成固定长度的hash值，这个过程可以使用密钥也可以不使用，这种加密算法是不可逆的，也就是说不能从加密后的hash值解密还原成明文，因此，这种算法通常用于验证数据是否被篡改和数据是否一致。因为同样的明文加密后得到是相同的hash值。典型的算法有MD5，SHA，Base64等

  TCP和UDP对比

TCP如何保证可靠性

• 检验和
• 序列号/确认应答
• 超时重传
• 最大消息长度
• 滑动窗口控制
• 拥塞控制
• 等等

TCP三次握手和四次挥手

• 三次握手：建立连接

  
  
  image.png

• 四次挥手：断开连接

  
  
  image.png

如何实现tcp拥塞控制？

参考

• 慢开始算法
  • 拥塞窗口由初始大小为1，指数式增大到慢开始门限（ssthresh）或出现拥塞为止。若增大到慢开始门限（ssthresh），便开始采取拥塞避免算法；若出现拥塞，将慢开始门限（ssthresh）减半，并将拥塞窗口置为1，然后再采取慢开始算法。
• 拥塞避免算法
  • 发送数据每得到接收方确认，拥塞窗口大小增1。
• 快重传算法
  • 数据传输时(数据被分成报文，每个报文都有个序号)，中间的一部分丢失接收方没收到，接收方连续接到后面的数据，则发回对丢失前的数据的重复确认，这样发送方就知道有部分数据丢失了，于是从丢失处重传数据。
• 快恢复算法
  • 快恢复是与快重传配合的算法，在发生数据丢失时，发送方收到接收方发回的三个重复确认信息时，就把每次传输的数据量减为原来的一半，拥塞窗口也修改为这个值,然后又开始采取拥塞避免算法策略。

什么是tcp粘包？如何处理？

• tcp粘包就是指发送方发送的若干包数据到达接收方时粘成了一包，从接收缓冲区来看，后一包数据的头紧接着前一包数据的尾。
• 处理方法：
  • 发送方关闭Nagle算法（用于自动连接许多的小缓冲器消息）。
  • 接收方应用层格式化数据或显示声明数据长度。

网址输入会发生什么？

• DNS解析->基于TCP连接的HTTP请求->服务器处理请求->浏览器解析响应数据后渲染页面->关闭TCP连接

什么是DNS协议？

• 全称为Domain Name System，中译为域名系统，端口为53。DNS一种可以将域名和IP地址相互映射的层次结构的分布式数据库系统。

Protobuf Union

参考

Protobuf没有提供union类型，如果希望使用union类型，可以采用enum和optional属性定义的方式。

为什么采用Protobuf？

• Protobuf优点
  • 传输效率快（据说在数据量大的时候，传输效率比xml和json快10-20倍），序列化后体积相比Json和XML很小，支持跨平台多语言，消息格式升级和兼容性还不错，序列化反序列化速度很快。
• Protobuf缺点
  • 使用不太方便。

Protobuf Lua 的序列化和反序列化

• 序列化：SerializeToString
• 反序列化：ParseFromString

计算机操作系统的八股文

进程和线程

• 进程：是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位。程序是指令、数据及其组织形式的描述，进程是程序的实体。
• 线程：CPU调度的最小单位，线程的特点就是在不需要独立资源的情况下就可以运行。

进程间通信方式

• 管道

  • 匿名管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
  • 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。

• 消息队列

  • 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

• 信号

  • 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

• 信号量

  • 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

• 共享内存

  • 共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。

• 套接字

  • 套接字也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同设备及其间的进程通信。

共享内存实例

参考

• Windows实例
  需注意字符集：使用多字节字符集

#include <windows.h>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int main()
{
    string strMapName("ShareMemory");                // 内存映射对象名称
    string strComData("This is common data!");        // 共享内存中的数据
    LPVOID pBuffer;                                    // 共享内存指针

    // 首先试图打开一个命名的内存映射文件对象
    HANDLE hMap = ::OpenFileMapping(FILE_MAP_ALL_ACCESS, 0, strMapName.c_str());
    if (NULL == hMap)
    {    // 打开失败，创建之
        hMap = ::CreateFileMapping(INVALID_HANDLE_VALUE,
                                   NULL,
                                   PAGE_READWRITE,
                                   0,
                                   strComData.length()+1,
                                   strMapName.c_str());
        // 映射对象的一个视图，得到指向共享内存的指针，设置里面的数据
        pBuffer = ::MapViewOfFile(hMap, FILE_MAP_ALL_ACCESS, 0, 0, 0);
        strcpy((char*)pBuffer, strComData.c_str());
        cout << "写入共享内存数据：" << (char *)pBuffer << endl;
    }
    else
    {    // 打开成功，映射对象的一个视图，得到指向共享内存的指针，显示出里面的数据
        pBuffer = ::MapViewOfFile(hMap, FILE_MAP_ALL_ACCESS, 0, 0, 0);
        cout << "读取共享内存数据：" << (char *)pBuffer << endl;
    }

    getchar();            // 注意，进程关闭后，所有句柄自动关闭，所以要在这里暂停

    // 解除文件映射，关闭内存映射文件对象句柄
    ::UnmapViewOfFile(pBuffer);
    ::CloseHandle(hMap);
    system("pause");
    return 0;
}

参考

• Linux实例

#include <iostream>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <vector>
#include <unistd.h>
#include <cstring>

#define KEY_OF_SHM 8888
#define TEXT_SIZE 1024

struct ShmDataStruct {
    int readable_;
    char text_[TEXT_SIZE];
};

using namespace std;

int main(){
    //获取shm_id，在不同进程中这是唯一的，获取和KEY有关
    int shm_id = shmget(KEY_OF_SHM, sizeof(struct ShmDataStruct), 0666 | IPC_CREAT);

    string strComData("This is common data!");        // 共享内存中的数据
    void *addr_to_shm;                                  // 共享内存指针

    struct ShmDataStruct *shm_data;
      //将addr_to_shm连接到系统分配的共享内存，也就是将共享内存（物理地址）挂到当前进程的内存空间（虚拟地址）
    addr_to_shm = shmat(shm_id, (void*)0, 0);

     //将获得的void*类型的转为我们需要的data struct
    shm_data = (struct ShmDataStruct*)addr_to_shm;

    // char buffer[TEXT_SIZE];
    if(shm_data->readable_ == 0){
        shm_data->readable_ = 1;
        strncpy(shm_data->text_, strComData.c_str(), strComData.size());
         cout << "写入共享内存数据：" << (char *)shm_data->text_ << endl;
    }
    else{
        
        cout << "读取共享内存数据：" << (char *)shm_data->text_ << endl;
    }

    shm_data->readable_ = 1;

    getchar();            // 注意，进程关闭后，所有句柄自动关闭，所以要在这里暂停

    //把共享内存从当前进程分离，也就是将其从进程内存空间的页表中除掉
    shmdt(addr_to_shm);

    //删除共享内存
    shmctl(shm_id, IPC_RMID, 0);
    exit(EXIT_SUCCESS);
    return 0;
}

线程间通信方式

参考

• 两个进程间的线程通信等同于进程通信。
• 单个进程间的线程通信：
  • 互斥锁
  • 条件变量
  • 信号量
  • 读写锁shared_lock。

多线程的应用场景？

• 多线程处理后台任务
• 多线程异步处理任务
• 多线程分布式计算

协程

• 类似于子例程，与线程不同的是，从当前协程切换到其他协程由当前协程来控制。

死锁

• 死锁是指集合中的每一个进程都在等待只能由本集合中的其他进程才能引发的事件。

• 产生死锁的四个条件：

  • 互斥
  • 请求和等待
  • 不剥夺
  • 环路等待

• 死锁避免：银行家算法

• 死锁检测：定时检测、效率低时检测、进程等待时检测。

• 死锁解除：撤销或挂起一些进程。

• 开发中如何避免死锁？

  • 采取原子操作
  • 利用局部变量的生命周期（RAII）
  • try_lock

物理地址和逻辑地址

• 物理地址：加载到内存地址寄存器中的地址，内存单元的真正地址。
• 逻辑地址：CPU所生成的地址。

虚拟内存

• 虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

作业调度策略

• FIFO全称为：First Come First Serve，中译为：先来先服务
• SJF全称为：Shortest Job First，中译为：短作业优先
• 时间片轮转
• 多级反馈队列
• 高响应比优先

页面置换算法

• OPT全称为：Optimal Replacement Algorithm，中译为：最佳置换算法
• FIFO全称为：First In First Out，中译为：先进先出置换算法
  • Belady现象：采用FIFO算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。
• LRU全称为：Least Recently Used，中译为：最近最久未使用置换算法

大端和小端

• 大端：字数据的高字节存储在低地址中，字数据的低字节则存放在高地址中。
• 小端：字数据的低字节存储在低地址中，字数据的高字节则存放在高地址中。

孤儿进程和僵尸进程

• 孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
• 僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵尸进程。

进程响应信号有那些方式？

• 忽略
• 执行默认
• 捕获

数据结构与算法的八股文

二叉树的应用场景

• C++ STL中的set、map，数据压缩（哈夫曼编码），海量数据并发查询（平衡二叉树）

用两个小球来判断100层高的楼会被摔坏的最低楼层

参考
参考

• 采用动态规划的思想
• dp(n,2) = max(k,dp(n-k,2)+1)，dp(1,2) = 1 临界点：k == dp(n-k,2)+1
  *当n == 1 + 2 + 3 + ... + k时，dp(n,2) = k。

最短路径算法

• 单源最短路径算法：
  • Dijkstra算法（单源、无负权、有向图、无向图最短路径）
  • Bellman-Ford算法（单源、可有负权、有向图、无向图最短路径）
• 多源最短路径算法：
  • Floyd算法（多源、可有负权、有向图、无向图最短路径）

计算机操作系统的八股文

简述CPU执行一条指令的过程

• 取指令阶段：将一条指令从主存中取到指令寄存器的过程。
• 指令译码阶段：在指令译码阶段，指令译码器按照预定的指令格式，对取回的指令进行拆分和解释，识别区分出不同的指令类别以及各种获取操作数的方法。
• 执行指令阶段：此阶段的任务是完成指令所规定的各种操作，具体实现指令的功能。为此，CPU的不同部分被连接起来，以执行所需的操作。
• 访存取数阶段：根据指令地址码，得到操作数在主存中的地址，并从主存中读取该操作数用于运算。
• 结果写回阶段：把执行指令阶段的运行结果数据“写回”到某种存储形式。

页面分页和分段的不同点

• 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。
  段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好的满足用户的需要。
• 页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。
  段的长度却不固定，决定于用户所编写的程序，通常由编辑程序在对源程序进行编辑时，根据信息的性质来划分。
• 分页的作业地址空间是维一的，即单一的线性空间，程序员只须利用一个记忆符，即可表示一地址。
  分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

未完待续