内存管理的伙伴系统和固定分区的区别

固定分区：分区大小和数量一开始就定死了。
伙伴系统：分区是动态切分、动态合并的。

码距是什么 ， 有什么用

概念

码距，也叫汉明距离，是两个等长二进制序列对应位置不同的个数 。
通俗来讲 ， 就是两个合法码字之间“不一样的位数”

比如有两个二进制码字：

1
2
1011001
1001101

逐位比较

1
2
3
1 0 1 1 0 0 1
1 0 0 1 1 0 1
    ↑   ↑

有 2 位不同，所以它们的码距是 2

任意两个合法码字之间都有一个距离。这里面最小的距离就叫最小码距

用处

计算机传输或存储数据时可能出错 ， 码距就是用来判错和纠错的

具体来说 ，

如果一个编码的最小码距是 d_min，那么它最多可以检测出 d_min - 1 位错误

如果一个编码的最小码距是 d_min，那么它最多可以纠正 t 位错误，其中 $2t + 1 ≤ d_min$

其中海明码 d_min 为 3

额外问题

  1. 为什么纠错能力和码距有关?

如果两个合法码字之间距离很近 ， 比如：

1
2
合法码字 A：0000
合法码字 B：0001

即码距为1

那么发送 0000 时 ， 最后一位出错 ， 变成 0001 ， 那么可能接收方会认为数据合法 ， 传输的是数据 B 。 因此码距越小 ， 抗错误能力越小 。

相反如果两个合法码字之间距离很远 ， 比如：

1
2
合法码字 A：0000000
合法码字 B：1111000

那么发送码字 A 时 ， 出现错误 ， 即

1
0000000 → 0010000

接收方会认为接收到的数据离 A 更近 ， 因此会认为这是数据 A 。 因此这个例子就起到了纠错的作用

TCP的三次握手和四次挥手 ， 哪几次不带具体数据的话也会消耗一个序号

SYN 、 FIN 消耗 1 个序号，ACK 不消耗序号

DDR SDRAM 是什么

Double Data Rate Synchronous Dynamic Random Access Memory 双倍数据率同步动态随机存取存储器

DRAM 可以理解成 1 个电容 + 1 个晶体管 , 电容有电表示 1 ， 没电表示 0

SDRAM 中的 S 表示同步 ， 内存操作跟系统时钟同步 ， 也就是CPU 或内存控制器按照时钟节拍发命令：

1
2
3
4
第 1 拍：发地址
第 2 拍：激活行
第 3 拍：读写列
第 4 拍：传数据

DDR 的核心是一个时钟周期传两次数据 。 普通 SDRAM 通常在一个时钟周期中，只在一个边沿传输数据，比如只在上升沿传输：

1
2
时钟：  ↑     ↑     ↑     ↑
数据：  传    传    传    传

而 DDR 在时钟的上升沿和下降沿都传输数据：

1
2
时钟：  ↑  ↓  ↑  ↓  ↑  ↓  ↑  ↓
数据：  传 传 传 传 传 传 传 传

访问数据流程如下：

1
2
3
4
5
6
7
8
9
存储阵列
   ↓ 选中某一行
行缓冲区 / 感应放大器
   ↓ 选中某几列
列选择器 / 列译码器
   ↓
I/O 缓冲区 / 预取缓冲
   ↓
数据总线

硬布线控制器的原理

硬布线控制器从功能上像一大堆写死的 if else，但真实实现是逻辑门电路并行产生控制信号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
第一步：时序发生器产生当前节拍
例如 T0、T1、T2、T3 ...

第二步：指令寄存器 IR 提供当前指令操作码
例如 ADD、LOAD、STORE、JMP ...

第三步：状态寄存器提供条件信息
例如 Z、C、N、中断请求等

第四步：组合逻辑网络综合判断
例如 当前是 LOAD 且处于 T4

第五步：产生控制信号
例如 MemRead、MDRin、RegWrite

第六步：数据通路执行相应微操作
例如 R1 ← M[addr]

第七步：进入下一个时序状态
继续产生下一组控制信号

硬件多线程是什么

概念

核心思想为：在一个 CPU 核心内部，同时保存多个线程的运行现场，当一个线程卡住时，快速切换到另一个线程继续执行，从而提高 CPU 利用率

硬件多线程的“多” ， 其实就是通过多个硬件的方式在一个核心的内部准备多套线程上下文

比如：

1
2
3
4
5
一个 CPU 核心
├── 线程上下文 0：PC0、寄存器组0、状态0
├── 线程上下文 1：PC1、寄存器组1、状态1
├── 线程上下文 2：PC2、寄存器组2、状态2
└── 线程上下文 3：PC3、寄存器组3、状态3

注意 ， 硬件线程和软件线程（OS中讲述的线程）不一样 ， 硬件线程是 CPU 提供的执行槽位

1
2
操作系统线程：软件层面的任务
硬件线程：CPU核心内部能同时维护的执行位置

主要硬件多线程方式

1.粗粒度多线程

平时一直执行一个线程，只有遇到较大的停顿时，才切换到另一个线程

2.细粒度多线程

几乎每个时钟周期都切换线程

3.同时多线程 SMT

在同一个时钟周期内，一个核心可以从多个线程中选择指令，同时送入不同执行单元执行

现代 CPU 通常是超标量处理器，一个周期可以执行多条指令 ， 如一个核心每周期最多可以发射 4 条指令 ， 但单个线程不一定每周期都有 4 条指令能执行 ， SMT 可以让另一个线程使用剩下的CPU执行槽

对于以下的程序 ， 非常适合 SMT 的发挥：

1
2
3
4
5
访存延迟多
缓存未命中多
I/O 或同步等待多
单线程无法充分利用执行单元
有大量独立线程

具体来说就是：

1
2
3
4
5
6
Web 服务器
数据库查询
编译任务
虚拟化场景
多用户服务
高并发网络服务

另外 ， 超线程 Hyper-Threading 是 Intel 对 SMT 技术的一种商业名称

关于共享内存多处理器

日常的电脑都属于共享内存多处理器 ， 即多个处理器共享内存空间 ， 分为UMA（统一内存访问）和NUMA（非统一内存访问） 。 而计算集群就属于非共享内存多处理器 ， 每个服务器都有自己的内存 ， 互相之间通过网络通信

UMA 的架构大致如下：

1
2
3
4
5
6
7
CPU 核心 0 ┐
CPU 核心 1 │
CPU 核心 2 │
CPU 核心 3 ┘
     │
     ▼
   共享内存

NUMA 的架构大致如下：

1
2
3
CPU 0 ─── 本地内存 0
  │
  └────── 互连总线 ────── CPU 1 ─── 本地内存 1
对比项共享内存多处理器不共享内存多处理器
内存地址空间所有处理器共享同一地址空间每个处理器有自己的地址空间
通信方式读写共享变量消息传递 / 显式通信
编程模型多线程、锁、共享变量MPI、发送/接收消息
典型例子多核 CPU、SMP、NUMA 服务器集群、分布式超算
优点编程相对直观扩展性强
缺点缓存一致性复杂，扩展有限编程更复杂，通信开销大

关于 SISD 、 SIMD 、 MIMD

SISD

单指令流，单数据流 ， 一个处理器一次执行一条指令，处理一份数据

SIMD

单指令流，多数据流 ， 一条指令同时作用于多份数据

比如数组相加：

1
2
3
for (int i = 0; i < 4; i++) {
    c[i] = a[i] + b[i];
}

SISD 的方法：

1
2
3
4
a0 + b0
a1 + b1
a2 + b2
a3 + b3

而 SIMD 可以一条指令同时完成：

1
2
[a0 a1 a2 a3] + [b0 b1 b2 b3]
= [c0 c1 c2 c3]

因此适用于向量处理 、 矩阵运算等

MIMD

多指令流，多数据流 ， 多个处理器或多个核心，各自执行不同的指令，处理不同的数据

比如：

1
2
3
4
核心0：处理图像
核心1：处理网络
核心2：处理音频
核心3：处理数据库

第一类虚拟机和第二类虚拟机的区别

Hypervisor 是一个为虚拟机“模拟”或“管理”硬件资源的软件

第一类虚拟机：Hypervisor 直接运行在硬件上
第二类虚拟机：Hypervisor 运行在宿主操作系统上

第一类虚拟机：裸机型虚拟机

结构

1
2
3
4
5
6
7
硬件
 ↓
Hypervisor （负责让多个虚拟机共享硬件资源）
 ↓
虚拟机 1 / 虚拟机 2 / 虚拟机 3
 ↓
客户操作系统

每个虚拟机内部有自己的客户操作系统 ， 因此其实不需要宿主操作系统

应用场景

1
2
3
4
5
数据中心
云服务器
企业虚拟化平台
服务器整合
生产环境部署

第二类虚拟机：宿主型虚拟机

结构

1
2
3
4
5
6
7
8
9
硬件
 ↓
宿主操作系统
 ↓
虚拟机软件
 ↓
虚拟机
 ↓
客户操作系统

优点在于安装方便使用简单 ， 但是性能相对较低 ， 宿主系统出问题会影响虚拟机 ， 另外资源控制和隔离能力较弱

虚拟文件系统 VFS 是什么

核心作用是给上层应用程序提供统一的文件访问接口，屏蔽不同具体文件系统之间的差异 ， 优点在于统一接口 ， 屏蔽差异（不用关心 ext4、FAT32、NFS 的区别） ， 支持挂载（多种文件系统可以组成统一目录树） ，提高扩展性（新文件系统只要实现 VFS 接口即可） ， 支持“一切皆文件”（设备、管道、proc 信息都可以文件化）

没有 VFS 的话 ， 就会出现以下情况：

1
2
3
4
5
6
7
8
9
10
11
如果是 ext4 文件：
    调用 ext4_read()

如果是 FAT32 文件：
    调用 fat32_read()

如果是 NTFS 文件：
    调用 ntfs_read()

如果是 NFS 文件：
    调用 nfs_read()

有了 VFS 之后 ， 应用程序就只需要调用统一的接口：read(fd, buffer, size) ， 流程就变成：

1
2
3
4
5
6
7
8
9
10
11
应用程序
   ↓
系统调用 read()
   ↓
VFS 层
   ↓
判断这个文件属于哪种具体文件系统
   ↓
调用对应文件系统的 read 方法
   ↓
真正读磁盘或网络数据

什么是 SPOOLing 技术

SPOOLing 技术又称假脱机技术，是利用磁盘等高速大容量存储设备作为输入井和输出井，通过后台输入 / 输出进程管理 I/O 作业队列，使慢速独占设备能够被多个进程逻辑共享。典型例子是打印机系统，用户进程把打印内容先送入输出井，然后由后台打印进程按队列逐个输出到打印机，从而提高 CPU 与外设的并行性和设备利用率

通俗来讲 ， 就是

1
2
3
4
5
6
7
8
9
进程要打印
   ↓
先把打印内容写入磁盘上的输出井
   ↓
进程很快返回，继续做别的事
   ↓
后台打印进程慢慢从输出井取任务
   ↓
按顺序送给打印机打印

如何理解频分复用技术 FDM

FDM 就是不同用户占用不同频率范围，同时在同一物理信道上传输

802.11 帧控制字段中的 To AP 和 From AP 为什么要两位

一位不就够了 ？ 比如 0 表示 To AP ， 1 表示 From AP

但其实

To DSFrom DS含义
00不经过 AP 的无线通信，例如 IBSS/ad hoc
10无线站点发给 AP
01AP 发给无线站点
11AP 到 AP，或者无线分布式系统 WDS 场景

主机发送广播帧时，集线器和交换机有什么区别

Hub 是无脑复制电信号；Switch 是识别为广播帧后，在同一广播域内泛洪 ， 不同之处在于：

1
2
3
4
交换机每个端口是独立冲突域
通常全双工
一般不会发生传统共享以太网那种冲突
交换机只在同一 VLAN / 广播域内泛洪广播帧
项目集线器交换机
工作层次物理层数据链路层
是否看 MAC 地址不看看
广播帧处理复制到所有端口泛洪到同一 VLAN 的其他端口
冲突域所有端口一个冲突域每个端口一个冲突域
广播域一个广播域默认一个广播域，VLAN 可划分
效率低高

为什么说 IP 地址是分层式的，MAC 地址是平面式的

IP 地址有网络号和主机号之分 ， 便于路由聚合和跨网络转发 ， 而 MAC 地址像一个设备身份证

多播转发树是什么

多播用于一个发送者把数据发给一组接收者，而不是发给所有人，也不是只发给一个人

而为了让数据只沿着必要路径转发，路由器会构造一棵树 ， 这就是多播转发树 ， 如

1
2
3
4
5
6
7
        源 S
         |
       R1
      /  \
    R2    R3
   /        \
接收者A     接收者B

RIP 中直连网络不可达时，是询问邻居，还是保存邻居距离后更新路由表

每个路由器周期性地从邻居那里收到距离向量，并在本地保存/更新路由信息 。 注意这些邻居距离通常来自之前或当前收到的 RIP 路由更新，而不是 R 发现故障后专门发消息询问邻居