2024-01-19 10:18 已编辑门头沟学院后端

关注

操作系统（计组）＋计网八股

操作系统

1. 锁

加锁的目的是为了保证共享资源在同一时间只能有一个线程访问。

以C++ STL库中的API的角度看一下各种该类型的锁：

1. mutex（mutual exclusive）

std::mutex mtx;
mtx.lock();
mtx.unlock();

mutex即互斥量（互斥体），也便是常说的互斥锁。尽管名称不含lock，但是实际上是用锁来实现的，具体是睡眠等待（sleep waiting）类型的锁。

归根到底，mutex是加锁原语，是为了互斥性地访问共享数据，而非等待原语，在使用mutex时，我们希望加锁不要阻塞，总是能立刻拿到锁。访问完数据后，希望尽快解锁，这样才不影响并发性。

睡眠锁有两个优势（具体实现见https://zhuanlan.zhihu.com/p/647151488）：

当线程acquire互斥锁失败的时候，线程会陷入休眠；
获取了互斥锁的线程可以出让CPU（比如锁住文件同时等待硬盘的情况）；

2. conditional variable

条件变量不是锁，它是一种线程间的通讯机制，并且几乎总是和互斥量一起使用的。所以条件变量一般是和互斥量成套出现的。

条件变量是为了等待某个条件成立，即一个或多个线程等待某个条件（布尔表达式）成立（等待别的线程“唤醒”它）。

C++11中也有条件变量的API： std::condition_variable。条件变量的具体实现参https://zhuanlan.zhihu.com/p/647151488?中的 sleep&wakeup 章节。

条件变量的用法相对固定：

必须与mutex一起使用，该布尔表达式的读（消费者检验）写（生产者更新）收到此mutex的保护；
mutex上锁时才能调用wait()；
布尔表达式的判断和wait()都要放到while循环里；

std::mutex mtx;
std::condition_variable cv;

void print_id (int id) {
  std::unique_lock<std::mutex> lck(mtx);
  while (!ready) {
    cv.wait(lck);
  }
  // ...
  std::cout << "thread " << id << '\n';
}

void go() {
  std::unique_lock<std::mutex> lck(mtx);
  ready = true;
  cv.notify_all();
}

3. read-write lock（读写锁）

C++中并没有实现读写锁，但是C++17提供了std::shared_mutex。

In contrast to other mutex types which facilitate exclusive access, a shared_mutex has two levels of access:

several threads can share ownership of the same mutex.
only one thread can own the mutex.

#include <shared_mutex>

class ThreadSafeCounter
{
public:
    ThreadSafeCounter() = default;
 
    // Multiple threads/readers can read the counter's value at the same time.
    unsigned int get() const
    {
        std::shared_lock lock(mutex_);
        return value_;
    }
 
    // Only one thread/writer can increment/write the counter's value.
    void increment()
    {
        std::unique_lock lock(mutex_);
        ++value_;
    }
 
    // Only one thread/writer can reset/write the counter's value.
    void reset()
    {
        std::unique_lock lock(mutex_);
        value_ = 0;
    }
 
private:
    mutable std::shared_mutex mutex_;
    unsigned int value_{};
};

4. spinlock（自旋锁）

自旋锁更为通俗的一个名字是『忙等待锁』（busy-waiting lock）。自旋锁在acquire阶段会一直循环，不会主动出让CPU，获取了自旋锁的进程或关闭中断，当前CPU无法切换其他进程。

C++似乎并未提供自旋锁，只能用底层接口 __sync_lock_test_and_set实现，该接口会使用在一个时钟周期内读取+写入。

2. 进程、线程和协程

进程是资源（包括内存、打开的文件等）分配的单位：

操作系统中最重要的两个概念之一（另一个是文件）；
可以将进程比做人，每个人有自己的记忆（memory），人与人之间通过谈话（消息传递）来交流，谈话可以是面对面谈话（同一台服务器），也可以是通过电话交流（不同的服务器，网络通信），

线程是 CPU 调度的单位：

1993年之后逐渐流行起来的概念；
线程间共享地址空间，可以高效共享数据；
多线程的价值在于更好的发挥多核处理器的功能，对于单核处理器，以状态机的角度编程要优于多线程；

协程是用户级的轻量级线程，由用户控制而非内核。

3. 进程间通信

1. Pipe

本质：内核空间的一段缓存，用读写指针管理形成循环队列。

限制：匿名管道在存在父子关系的进程间才能使用；只能先进先出，无法lseek；生命周期随进程；内核态-用户态拷贝开销；

命名管道可以在不相关的进程间进行通信（其实就是读写文件了）。

2. 消息队列

本质：保存在内核中的消息链表。

限制：最大长度受限；内核态-用户态拷贝开销；

消息队列生命周期随内核。

3. 共享内存

本质：两个进程的页表映射同一块物理空间。

限制：需要同步机制。信号量初始化为1代表互斥信号量，初始化为0代表同步信号量。

4. 信号

本质：软件中断，用于通知异常状态（进程间唯一的异步通信机制）。

5. Socket

可以本地通信，也可以跨主机。

4. 虚拟地址空间

堆和栈之间有共享库区。

5. 内存体系

1. 主存&缓存

主存（main memory）：由DRAM（动态存储器）实现

用电容保存电荷的方式来存储数据，电容会不断漏电，所以需要定时刷新充电，才能保持数据不丢失；
刷新也就是把数据读出来再写进去；

缓存（cache）：由SRAM（静态存储器）实现

只要处在通电状态，里面的数据就可以保持存在；
每个CPU有自己独有的L1和L2 cahce，L1在cpu内部（通常分成指令缓存和数据缓存，分开存放 CPU 使用的指令和数据），L2通常不在CPU内部，L3为多个核心共享；
L1缓存读取时间4个时钟周期，L2 11个，L3 39个；

2. 缓存原理

将内存地址分为三部分：TIO

Index + Offset决定了cache的大小，Index决定行数，Offset决定列数（Block的大小）；

TAG被储存在cache中，cache里每一行包含了valid bit + dirty bit + TAG + data；

缓存映射关系：

直接映射（Direct Mapped）；全索引（Fully Associative）；组索引（Set-Associative）;

6. IO

IO的阻塞、非阻塞，同步、异步

IO可以分为两个阶段：数据准备和数据读写。以ssize_t recv(int sockfd, void *buf, size_t len, int flag)为例

阻塞、非阻塞：是内核态的系统调用是否直接返回，是在数据准备状态

阻塞：内核改变当前进程的状态，直到有可读数据才唤醒该进程；
非阻塞：不改变进程状态

同步IO、异步IO：是数据读写阶段

同步IO接口：A操作等待B操作完成后，得到返回值，继续处理
数据由进程自己（请求方）从TCP缓存中复制到buf，占用的是IO调用的时间；
异步IO接口：A操作告知B操作它感兴趣的事件以及通知方式，A操作继续执行自己的业务逻辑，B操作监听到相应事件发生后，通知A
数据由内核复制，复制完成后通过sigio或回调来通知进程；效率更高，入aio_read(), aio_write

在处理IO的时候，阻塞和非阻塞都是同步IO，只有使用了特殊的API才是异步IO。（异步没有阻塞）

Linux IO模型

阻塞（Blocking）
非阻塞（N on-blocking）
IO复用（IO Multiplexing）
相比于阻塞/非阻塞，一个进程可以监听多个fd；
进程阻塞于select/poll/epoll等待套接字变为可读；
select/poll/epoll返回可读fd；
可以设置timeout参数变为非阻塞
信号驱动（Signal-driving）
数据准备阶段（第一阶段）是异步的，相比于非阻塞，信号驱动提供了消息通知机制，不需要不断轮询，减少了系统API调用次数
异步（Asynchronous）
aio_read，aio_write

计网

0. Basics

Ethernet Frame（帧）

IP Packet（分组）

TCP Segment（节）

1. HTTP1.0和HTTP2.0的区别？

结论1：从HTTP/1.0到HTTP/2，都是利用TCP作为底层协议进行通信的。
结论2：HTTP/1.1，引进了HTTP长连接(keep-alive)，只要任意一方没有明确提出断开连接则保持TCP连接状态，减少了建立和关闭TCP连接的消耗和延迟。
结论3：HTTP/2，引入了多路复用：连接共享，一个连接上可以有多个request，提高了连接的利用率，降低延迟。

HTTP/1.0

无连接和无状态：HTTP/1.0 每次请求都会建立一个新的TCP连接，请求完成后立即断开连接。
文本协议：HTTP/1.0 是基于文本的协议，易于读取和调试。
请求/响应模型：每次请求对应一个响应。
无内置压缩支持：虽然HTTP/1.0 通过 Content-Encoding 头部可以支持响应体的压缩，但这不是内置的。
队头阻塞问题：多个请求需要按照先进先出（FIFO）的顺序进行，即前一个请求没有完成，后一个请求就不能开始。
简单的头部元信息：HTTP/1.0 中，请求和响应头是比较简单的。
缺乏优先级/依赖性：所有请求都是独立处理的。

HTTP/2.0

多路复用：一个单一的TCP连接可以同时处理多个请求和响应。
二进制协议：HTTP/2 是基于二进制的协议，这使得协议解析变得更快和更高效。
头部压缩：HTTP/2 使用 HPACK 算法来压缩头部，以减少数据传输的大小。
服务器推送：服务器可以主动发送额外的资源，以加速客户端的页面加载。
优先级和依赖性：HTTP/2 可以设置请求之间的优先级和依赖性。
更强的流控制：除了TCP流控制，HTTP/2 还提供了其自己的流控制机制。
更安全（相对而言）：虽然 HTTP/2 自身不是加密协议，但实际应用中，几乎所有的客户端和服务器都要求通过 HTTPS（即 HTTP over TLS）来使用 HTTP/2。

总体而言，HTTP/2 通过多种优化提供了比 HTTP/1.x 更高的性能，包括更低的延迟和更高的吞吐量。这些改进是为了应对现代网页日益增加的复杂性和需求。

2. TCP基础

TCP is a reliable byte stream protocol for the Internet.

1983年4.2BSD发布，第一个广泛应用的TCP实现。

一个比喻：用寄明信片的方式传送一本书（明文，乱序，可能丢）；

To transmit a stream of data, TCP breaks the data stream into segments for transmission through the Internet, and resembles the segments at the receiving side to recreate the data stream.

How to be reliable and sequence-preserving?

Assign every byte in the stream a sequence number (including start(SYN)/end(FIN) of stream);
Cumulative positive acknowledge;
Retransmit when didn't get ACK in time.

TCP is connection-oriented

Connection: certain status infomation that TCPs initialize and maintain for each data stream, including including sockets, sequence numbers, and window sizes.

核心思想

Cumulative positive acknwoledgement with retransmission;
Flow control (sliding window);
Congestion flow;

(2&3 are optional, without sliding window is Single-MSS Stacks)

应用

FTP

HTTP / HTTPS

实现

三分天下：

BSD iOS / maxOS
Linux Android / Chrome OS
Windows PC / Laptop

互联网绝大多数信息都是在这三个实现间流转。

3. TCP流量控制

流量控制（flow control）：to avoid network layer delivers data faster than application layer removes from socket buffer. The receiver controls sender, so sender won't overflow receiver's buffer by transmitting too much, too fast.

接收方通过TCP头部中的rwnd字段控制发送方的发送速率，rwnd即为接收方的空闲buffer长度。