残酷八股文群学习汇总-2月

残酷八股文项目地址

什么是五级流水线，数据冒险是什么

指令

指令的定义

计算机指令就是指挥机器工作的指示和命令，程序就是一系列按一定顺序排列的指令，执行程序的过程就是计算机的工作过程百度百科。

指令的结构

指令包含了操作码和操作数. 操作码决定该条指令的作用（运算类(add、mul、sub)、控制跳转(JA、JE)、取值(lea)）; 操作数指定了参与指令操作的具体数据, 操作数可以是立即数(如add eax, 10, 其中10为立即数), 可以来自寄存器(如mov eax, esp), 也可以来自内存(如mov eax, 某内存地址(逻辑地址)).

根据操作数的多少, 指令可以分为无操作数指令(ret)、一操作数指令JE, INC、二操作指令(mov)和三操作数指令(add)等等。

五级流水线

cpu流水线技术是一种将指令分解为多步，并让不同指令的各步操作重叠，从而实现几条指令并行处理，以加速程序运行过程的技术百度百科。

MIPS五级流水线分为五个模块: 取址 -> 译码 -> 执行 -> 访存 -> 写回

1. 取址: 控制单元根据PC中存放的指令地址, 从存储器中取出下一条即将执行的指令放入指令寄存器.
2. 译码: 根据指令编码的规则去对指令进行译码. 即翻译指令, 看看指令具体是什么操作, 需要几个操作数, 操作数是立即数还是在寄存器或内存里, 并给出操作数的地址以及结果的保存地址等.
3. 执行: 有了操作码和操作数, 就根据操作码对操作数进行操作, 即执行指令.
4. 访存: 访存是load \ store, 即读内存或写内存. 内存操作数需要读内存, 有些结果的保存需要写入内存. (读写内存远远慢于读写寄存器, 可以利用cache加速, 但可能还会遇到缺页中断的问题).
5. 写回: 将指令执行的结果写入寄存器中或内存中.

数据冒险

流水线技术通过并行处理来加速程序的执行过程, 但有些情况下这种并行会导致使用数据存在冒险: 当前指令需要需要使用之前指令的运算结果, 但是其结果没有写回.

如图, add指令需要t0作为操作数参与运算, 但其被上一条指令sub操作, 而且其结果还未写回. 此时存在数据冒险.

解决方法

1. 插入nop指令. (软件解决方法, 不足在下面参考博客中)
2. 流水线停顿, 增加气泡.
   
3. 数据前递.
   t0在EX阶段(执行)就被计算出，所以可将它送到下一条指令ALU的输入，而不需要添加气泡。
   

   参考

数据冒险讲解博客

Python: 什么是鸭子类型

定义

鸭子类型（duck typing）是动态类型的一种风格。在这种风格中，一个对象有效的语义，不是由继承自特定的类或实现特定的接口，而是由”当前方法和属性的集合”决定。

含义

鸭子类型关注对象的方法和属性而不是对象自身的类型. 如下getLen函数可以接受任意类型的参数, 它关注的是该参数是否支持len方法. 如重写了__getitem__的Nums类支持切片操作. 其只有在运行时才能确定参数的正确与否, 如果错误将会引起运行时错误.

class Nums():
    def __init__(self, length):
        self.nums = [_ for _ in range(length)]

    def __len__(self):
        return len(self.nums)

    def __getitem__(self, idx):
        return self.nums[idx]


def getLen(a):
    return len(a)

def printNum(a):
    for x in a:
        print(x, end=',')
    print()

nums = [_ for _ in range(5)]
obj = Nums(5)


print(f"length of nums = {getLen(nums)}\t length of obj = {getLen(obj)}")

print("print nums:")

printNum(nums[:-1])

print("print obj:")

printNum(obj[:-1])

# 输出
# length of nums = 5       length of obj = 5
# print nums:
# 0,1,2,3,
# print obj:
# 0,1,2,3,

优缺点

1. 优点: 主要是动态语言的特性, 其无需关注具体的类型, 极大放松了编程的限制.
2. 缺点: debug和维护的成本高昂, 需依赖清晰的文档和规范才能在多人协作的情况下提高开发效率.

cpp: volatile 和 atomic 的区别

volatile

volatile是cpp中的关键字, 其可以修饰变量用作类型修饰. 如volatile int a = 5;

1. 易变性: volatile修饰的变量编译器不会保存到寄存器中, 而是每一次都从内存中读取.避免在多线程编程中的一些问题.
2. 不可优化性: 限制编译器对于变量的优化.
3. 顺序性: 能够保证volatile变量间的顺序性, 编译器不会进行乱序优化.

atomic

atomic是cpp11提供了模板类, 可以用其定义一个原子类型: atomic<int> a;, 且重载了++, –, += , |= 等运算符. 并且可以通过load和store原子性的读取和修改其值.

区别

1. volatile是cpp关键字, 用作类型修饰符, 是编译器级别的语义. atomic是cpp的STL提供的模板类, 是库级别的.
2. volatile保证了顺序关系, 主要语义是防止编译器缓存, 但无法保证原子性. atomic是为了原子性而产生的, 其内置的成员函数load和store以及重载的运算符等防止了多线程编程下的数据竞争.

从内存里读一个byte计算机内部是怎么样实现的

首先计算机需要知道该byte的虚拟地址. 这是通过寻址获取的. 通过寻址获得其逻辑页号和页内偏移, 然后查看TLB(快表)和页表该页是否已经load进物理内存.

• 如果快表或者页表中存在该虚拟页和物理页的映射. 则MMU进行地址译码, 获取其物理地址, 最后通过总线访问内存.
• 如果不存在映射则发生缺页中断, 陷入内核态系统找到对应的中断服务程序进行处理, 具体就是寻找一块物理空闲页然后将逻辑页读入, 并将映射存入快表和页表.(如果物理页满了会利用页面置换算法(LRU, FIFO, OPT)淘汰物理内存页), 完成后重新执行该条指令(因为中断后未完成).

C++: 简述 virtual function

虚函数可以分为纯虚函数和虚函数.

纯虚函数

格式

virtual void func() = 0;

特性

1. 含有纯虚函数的类称为抽象类, 这种类无法实例化. 且继承它的类如果没有实现纯虚函数的话其还是抽象类.
2. 抽象类的语义类似于某些语言中”接口”的语义, 只有继承类全部实现了该抽象类定义的纯虚函数, 即可认为继承类”实现”了抽象类”接口”语义.

虚函数

虚函数是cpp动态多态的关键. cpp的多态分为静态多态和动态多态.

• 静态多态是如函数的重载、泛型模板等, 其发生在编译期.
• 动态多态是动态类型配合虚函数导致的运行时多态.

格式

virtual void func();

特性

1. 含有虚函数的类会产生虚函数表, 其中每个表项都是函数指针, 指向具体的函数. 在构造对象时, 对象会保存虚函数表指针, 其指向虚函数表.
2. 虚函数配合动态类型会产生多态的效果.
3. 虚函数的绑定是推迟到运行时, 但虚函数的参数绑定是在编译期的, 目的是加快执行速度, 因此虚函数带有默认参数的情况应该避免或保证默认参数一致, 否则会出现不符合预期的结果.

#include <iostream>

using namespace std;

class Base {
public:
    void say() {
        cout << "Base" << endl;
    }
    virtual void func(int i = 0) {
        cout << "This is Base Class. i = " << i << endl;   
    }
};

class Derived : public Base {
public:
    virtual void func(int i = 1) {
        cout << "This is Derived Class. i = " << i << endl;   
    }
};


int main() {
    // p的静态类型是Base
    Base* p = nullptr;
    // 静态绑定, 且该函数不调用this, 因此可以正确执行
    p -> say();

    // p的静态类型是Base, 动态类型是Base
    p = new Base;
    p -> func();

    // p的静态类型是Base, 动态类型是Derived
    p = new Derived;
    // 动态类型配合虚函数, 产生运行时动态多态的效果
    p -> func();

    return 0;

/* 输出
Base
This is Base Class. i = 0
This is Derived Class. i = 0
*/
}

a、b两台服务器怎么判断是否能连通, 为什么能用ping和traceroute

ping

ping主要用于确定网络间的连通性以及网络间的连接状况. 其是基于ICMP协议工作的. ping命令会构建一个ICMP请求报文给目标主机, 并等待目标主机返回ICMP应答报文.

源主机工作流程

1. ping目标主机后ICMP协议构建ICMP请求报文
2. IP层协议得到ICMP报文以及目标主机IP地址后, 将本机地址作为源地址, 再加上其他的一些控制信息组成IP数据包.
3. 根据本地ARP缓存查找目标IP地址对应的MAC地址(物理地址). 如果没找到就通过ARP协议找. 最后将目标主机的MAC地址和本机的MAC地址交给数据链路层, 构造数据帧.
4. 通过物理层发送给目标主机

目标主机工作流程

1. 物理层收到二进制数据流经过数据链路层, 根据以太网协议解析出数据帧, 判断数据帧中的目标MAC地址是否为本机, 是则接受, 否则抛弃.
2. 经过网络层解析IP数据包, 通过IP包头的协议字段判断出是ICMP报文. 之后ICMP协议处理, 构建并发送一个ICMP应答报文.
3. 将封装好的ICMP应答报文经过网络层、数据链路层、物理层发送回源主机.

Traceroute

traceroute命令不仅可以检测网络间是否联通, 还可以知道从源主机到目标主机经过了哪些路由器. 其可以通过利用ICMP协议定位路径上经过的路由器. 并利用端口不可达错误来确定数据包是否到达目标主机.

工作流程

1. 源主机向目标主机发送一系列的UDP报文. 第一个报文的生存时间TTL = 1, 当其到达路径上第一个路由器时, 该路由器将TTL值减1, 并发现TTL = 0. 因此路由器将其丢弃, 并发送给源主机ICMP不可达的报文.
2. 主机收到ICMP不可达报文后, 接着发送TTL = 2的报文, 这样确定路径上第2个路由器.
3. 这样循环往复, 直到数据报到达目标主机, 由于traceroute发送的是端口号大于30000的UDP报文, 因此目标主机只能发送一个端口不可达的ICMP数据包(无法交付的UDP报文)给源主机.
4. 通过这种方法源主机知道了到目标主机路径上的路由器的IP和目标主机是否联通等信息.

traceroute是怎么traceback, 最终让发出traceroute的客户端得到信息的

1. 源主机向目标主机发送一系列的UDP报文. 第一个报文的生存时间TTL = 1, 当其到达路径上第一个路由器时, 该路由器将TTL值减1, 并发现TTL = 0. 因此路由器将其丢弃, 并发送给源主机ICMP不可达的报文.
2. 源主机收到ICMP不可达报文后, 接着发送TTL = 2的报文, 这样确定路径上第2个路由器.
3. 这样循环往复, 直到数据报到达目标主机, 由于traceroute发送的是端口号大于30000的UDP报文, 因此目标主机只能发送一个端口不可达的ICMP数据包(无法交付的UDP报文)给源主机.
4. 通过这种方法源主机知道了到目标主机路径上的路由器的IP和目标主机是否联通等信息.

C++: 简述 vtable

虚函数表是含有虚函数的类所拥有的. 它配合动态绑定技术, 可以实现运行期多态.

特点

• 每个含有虚函数的类均会有一份类共享的虚函数表.
• 每个对象含有虚函数表指针, 一般会在对象内存地址的开头. 这样的好处是通过父类指针调用子类对象的虚函数时, 能在子类对象的前sizeof(父类)区域中拿到子类的虚函数表指针, 正确的实现多态.
• 虚函数表是指针数组, 其表项为函数指针, 指向类所对应的虚函数.
• 虚函数表的产生是在编译器, 并且编译器会为有虚函数的对象添加虚函数指针.
• 动态绑定是在运行期. 其依赖于虚函数指针和虚函数表.

hashmap和treemap的区别, 除了红黑树还可以怎么实现treemap

hashmap

cpp的unordered_set和unordered_map均为关联哈希容器. 支持查找、增加、修改、删除指针的key. 通过哈希方法实现.

treemap

cpp的set和map均为关联式有序容器. 支持默认比较(如set<pair<int, int>>)或自定义(重载operator <)的方式来指定容器对元素的排序动作. 保证key唯一且有序. 一般通过红黑树实现, 红黑树是一种高度平衡查找二叉树.

区别

• 实现方式不同

• 支持的操作不尽相同. map和set容器自带支持lower_bound和upper_bound函数, 可以按key值大小遍历容器等.

• 常用操作时间复杂度

  容器	添加	删除	修改	查找
  hashmap	$O(1)$	$O(1)$	$O(1)$	$O(1)$
  treemap	$O(logN)$	$O(logN)$	$O(logN)$	$O(logN)$

实现

还可以利用其他AVL树来实现treemap, 如普通AVL树、Treap.