Neo's Blog

Page Cache 用于缓存文件的页数据，

buffer cache 用于缓存块设备（如磁盘）的块数据。

页是逻辑上的概念，因此 Page Cache 是与文件系统同级的；

块是物理上的概念，因此 buffer cache 是与块设备驱动程序同级的。

Page Cache 与 buffer cache 的共同目的都是加速数据 I/O

写数据时首先写到缓存，将写入的页标记为 dirty，然后向外部存储 flush，也就是缓存写机制中的 write-back（另一种是 write-through，Linux 默认情况下不采用）；

读数据时首先读取缓存，如果未命中，再去外部存储读取，并且将读取来的数据也加入缓存。

操作系统总是积极地将所有空闲内存都用作 Page Cache 和 buffer cache，当内存不够用时也会用 LRU 等算法淘汰缓存页。

在 Linux 2.4 版本的内核之前，Page Cache 与 buffer cache 是完全分离的。但是，块设备大多是磁盘，磁盘上的数据又大多通过文件系统来组织，这种设计导致很多数据被缓存了两次，浪费内存。

所以在 2.4 版本内核之后，两块缓存近似融合在了一起：如果一个文件的页加载到了 Page Cache，那么同时 buffer cache 只需要维护块指向页的指针就可以了。

只有那些没有文件表示的块，或者绕过了文件系统直接操作（如dd命令）的块，才会真正放到 buffer cache 里。

因此，我们现在提起 Page Cache，基本上都同时指 Page Cache 和 buffer cache 两者，本文之后也不再区分，直接统称为 Page Cache。

下图近似地示出 32-bit Linux 系统中可能的一种 Page Cache 结构，其中 block size 大小为 1KB，page size 大小为 4KB。

Page Cache 中的每个文件都是一棵基数树（radix tree，本质上是Trie、多叉搜索树），树的每个节点都是一个页。根据文件内的偏移量就可以快速定位到所在的页，如下图所示。关于基数树的原理可以参见英文维基，这里就不细说了。

TLB：MMU工作的过程就是查询页表的过程。如果把页表放在内存中查询的时候开销太大，因此为了提高查找效率，专门用一小片访问更快的区域存放地址转换条目。（当页表内容有变化的时候，需要清除TLB，以防止地址映射出错。）

Caches：cpu和内存之间的缓存机制，用于提高访问速率，armv8架构的话上图的caches其实是L2 Cache

内存命中率

假设在 n 次内存访问中，出现命中的次数是 m，那么 m / n * 100% 就表示命中率，这是衡量内存管理程序好坏的一个很重要的指标。

如果物理内存不足了，数据会在主存和磁盘之间频繁交换，命中率很低，性能出现急剧下降，我们称这种现象叫内存颠簸。这时你会发现系统的 swap 空间利用率开始增高， CPU 利用率中 iowait 占比开始增高。

大多数情况下，只要物理内存够用，页命中率不会非常低，不会出现内存颠簸的情况。因为大多数程序都有一个特点，就是局部性。

局部性就是说被引用过一次的存储器位置，很可能在后续再被引用多次；而且在该位置附近的其他位置，也很可能会在后续一段时间内被引用。

物理内存管理

对于Page级别的内存分配，通过Buddy系统来管理；TCMalloc 也是通过这种方式来管理span。

对于小对象（例如task_struct、mm_struct等）通过SlabAllcator来进行管理分配。这种思路，Memcache会借鉴。

进程与线程

• 进程线程的区别

线程独享：线程局部存储TLS、errno、寄存器、栈空间

1.进程：一个静态程序的执行过程；

线程：操作系统调度的基本单位；
1.线程ID 每个线程都有自己的线程ID，这个ID在本进程中是唯一的。进程用此来标识线程。

2.寄存器组的值       由于线程间是并发运行的，每个线程有自己不同的运行线索，当从一个线

程切换到另一个线程上时，必须将原有的线程的寄存器集合的状态保存，以便
将来该线程在被重新切换到时能得以恢复。

3.线程的堆栈       堆栈是保证线程独立运行所必须的。       线程函数可以调用函数，而被调用函数中又是可以层层嵌套的，所以线程

必须拥有自己的函数堆栈，使得函数调用可以正常执行，不受其他线程的影
响。
4.错误返回码 由于同一个进程中有很多个线程在同时运行，可能某个线程进行系统调用
后设置了errno值，而在该线程还没有处理这个错误，另外一个线程就在此时
被调度器投入运行，这样错误值就有可能被修改。 所以，不同的线程应该拥有自己的错误返回码变量。
5.线程的信号屏蔽码 由于每个线程所感兴趣的信号不同，所以线程的信号屏蔽码应该由线程自己管理。但所有的线程都共享同样的信号处理器。
6.线程的优先级 由于线程需要像进程那样能够被调度，那么就必须要有可供调度使用的参数，这个参数就是线程的优先级。

• 进程间通信方式

• 线程的状态

• 介绍死锁和如何避免

线程安全

（1）synchronized 方法 + 代码块

（2）互斥锁lock

（3） 线程局部存储

（4）乐观锁

进程调度算法

多级反馈队列调度算法

设置多个就绪队列。在系统中设置多个就绪队列，并为每个队列赋予不同的优先。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。该算法为不同列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片愈小。

　　　　每个队列都采用FCFS算法。当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度;如果它在第二队列中运行个时间片后仍未完成， 再依次将它放入第三队列…依此类推。当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。

　　　　按队列优先级调度。调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行;仅当第1到(i-1)所有队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程。

summary:
多级反馈队列调度算法，“多级”在于有多个不同优先级的队列，“反馈”在于如果有进程加入优先级高的队列时立即停止当前任务，转去执行优先级高的队列中进程，上述过程循环调度就形成多级反馈队列调度算法。

例子：
上图是一个调度的示例，进程有A(4)，B(3)，C(4)，D(2)，E(4)，括号内是需要服务的时间。设第一队列时间片q=1，因为该算法中时间片的规则为：后一个时间片长度为前一个的2倍，所以第二队列时间片q=2，第三队列时间片q=4。

若不能执行完，则放到下一个队列尾部（橙色部分）

到最后一个队列的时候，则执行轮转调度（RR）算法，也就是每次执行一个时间片长度的服务，直到循环执行完所有的进程。

分离thread

非分离线程在终止后，必须要有一个线程用 join 来等待它。否则，不会释放该线程的资源以供新线程使用，而这通常会导致内存泄漏。因此，如果不希望线程被等待，请将该线程作为分离线程来创建。

hash

hlist_head hlist_node 散列表拉链

根据PID定位task：PID哈希表

双向链表

list_head 双向链表

提高调度程序运行速度：建立多个可运行程序链表

等待队列（双向链表）：用自旋锁加保护的等待队列头、等待队列链表的元素

等待队列中睡眠进程的唤醒：互斥进程，非互斥进程

链表维护节点；节点包括管理区【硬件限制，ZONE_DMA, ZONE_NORMAL, ZONE_HIGHMEM】+ page数组

动态定时器的链表组（将同一时间段内即将到时的定时器归入一组）

bitmap

pid分配管理：bitmap pidmap_array

inode、磁盘文件数据块

并发与同步

每CPU变量

不需要同步的内核数组，为每个cpu分配数组一元素

自旋锁

基数树

RCU机制

RCU(读取-拷贝-更新)：只保护被动态分配并通过指针引用的数据结构

何时释放旧副本？ CPU经过静止状态后，定期检测！！

https://blog.csdn.net/qq_52911516/article/details/136878352

原子变量

其他

thread 与 thread_info 紧密挨着；根据esp 屏蔽 低13位 可以最快的获取thread_info;
同时进程描述符指针在thread_info中的偏移为0!

也就是将： OS将task_struct指针存放到了栈上（可以通过esp做简单的AND操作即可）

jiffies:子系统启动的节拍总数

基本原理

e经典的操作系统书籍OperatingSystems:Three Easy Pieces从三个方面讲述了操作系统的基本原理，第一部分即是虚拟化思想，其他两部分是并行和持久化。

最简单的虚拟机是进程，这种虚拟机太过于普通，以至于很多人都没有意识到它们是虚拟机。

模拟器是另一种形式的虚拟机。进程的指令都是可以直接运行在硬件CPU上的，模拟器则不同，它可以使为一种硬件指令集（InstructionSet Architecture，ISA）编译的程序运行在另一种硬件指令集上。应用程序在源ISA（如ARM）上被编译出来，在模拟器的帮助下，运行在不同的目标ISA（比如x86）上。模拟器可以通过解释来实现，即对程序的源ISA指令一条一条进行分析，然后执行相应的ISA指令上的操作。模拟器也可以通过二进制翻译实现，即首先将程序中所有的源ISA指令翻译成目标ISA上具有同样功能的指令，然后在目标ISA指令机器上执行。模拟器的基本原理如图1-2所示。典型的模拟器有QEMU（Quick Emulator）的用户态程序模拟、Bochs模拟器等。

高级语言虚拟机在模拟器的基础上更进一步，将源ISA和目标ISA完全分离开。在高级语言虚拟机中，通常会设计一种全新的虚拟ISA，并在其中定义新的指令集、数据操作、寄存器的使用等类似于物理ISA中的规范。不同于普通程序和模拟器运行的程序，高级语言虚拟机的程序中没有任何具体物理ISA指令字节，而是自己定义虚拟的指令字节，这些指令字节通常叫作字节码。任何想要运行这种虚拟ISA指令的物理 ISA平台都需要实现一个虚拟机，该虚拟机能够执行虚拟机ISA指令到物理ISA指令的转换。程序员通过使用高级语言编写程序，不需要考虑其具体的运行平台，即可非常方便地实现程序的跨平台分发。高级语言虚拟机如图1-3所示。典型的高级语言虚拟机有JVM虚拟机、Python虚拟机等。

操作系统智慧

懒人哲学：越简单、越傻瓜、用户使用的学习成本越低越好

让困于人：当我们遇到困难时，搞不定的或者我们自己搞成本很大的，交给别人来搞(一般让操作系统来搞，其实操作系统也是别人完成的软件系统)

留有余地: 可扩展性，让系统有可扩展性

足够智能：一个系统最好能解决所有的问题，给人的感觉是一个万能的解决方案，也就是操作系统的魔术师的角色

时空转换：在一个维度遇到的瓶颈，那就改变方案把瓶颈移到另外一个维度 【内存页表太大，占用内存资源；那就页表分级，不活跃的放到磁盘】

策机分离和权利分离：一个系统或者平台在主要指定规则、提供通用化的插件即可

简单与美：苛求于简，归于永恒

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <windows.h>
#include <intrin.h>

class Benaphore
{
private:
    LONG m_counter;
    HANDLE m_semaphore;

public:
    Benaphore()
    {
        m_counter = 0;
        m_semaphore = CreateSemaphore(NULL, 0, 1, NULL);
    }

    ~Benaphore()
    {
        CloseHandle(m_semaphore);
    }

    void Lock()
    {
        if (_InterlockedIncrement(&m_counter) > 1) // x86/64 guarantees acquire semantics
        {
            WaitForSingleObject(m_semaphore, INFINITE);
        }
    }

    void Unlock()
    {
        if (_InterlockedDecrement(&m_counter) > 0) // x86/64 guarantees release semantics
        {
            ReleaseSemaphore(m_semaphore, 1, NULL);
        }
    }
};

If you port this code to another CPU architecture, such as that in the Xbox 360 or a multicore iOS device, you’ll have to replace the _InterlockedIncrement macro with something which explicitly guarantees acquire and release semantics.

支持递归的互斥锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

// Define this to {} in a retail build:
#define LIGHT_ASSERT(x) { if (!(x)) DebugBreak(); }
 
class RecursiveBenaphore
{
private:
    LONG m_counter;
    DWORD m_owner;
    DWORD m_recursion;
    HANDLE m_semaphore;
 
public:
    RecursiveBenaphore::RecursiveBenaphore()
    {
        m_counter = 0;
        m_owner = 0;            // an invalid thread ID
        m_recursion = 0;
        m_semaphore = CreateSemaphore(NULL, 0, 1, NULL);
    }
 
    RecursiveBenaphore::~RecursiveBenaphore()
    {
        CloseHandle(m_semaphore);
    }
 
    void Lock()
    {
        DWORD tid = GetCurrentThreadId();
        if (_InterlockedIncrement(&m_counter) > 1) // x86/64 guarantees acquire semantics
        // x86 和 x64 上，_InterlockedIncrement调用会生成一条lock xadd指令，该指令充当完整的内存屏障，保证获取和释放语义
        //此属性是 x86/64 独有的
        {
            if (tid != m_owner)
                WaitForSingleObject(m_semaphore, INFINITE);
        }
        //--- We are now inside the Lock ---
        m_owner = tid;
        m_recursion++;
    }
 
    void Unlock()
    {
        DWORD tid = GetCurrentThreadId();
        LIGHT_ASSERT(tid == m_owner);
        DWORD recur = --m_recursion;
        if (recur == 0)
            m_owner = 0; //先设置为0，再去_InterlockedDecrement
        DWORD result = _InterlockedDecrement(&m_counter); // x86/64 guarantees release semantics
        if (result > 0)
        {
            if (recur == 0)
                ReleaseSemaphore(m_semaphore, 1, NULL);
        }
        //--- We are now outside the Lock ---
    }

    bool TryLock()
    {
        DWORD tid = GetCurrentThreadId();
        if (m_owner == tid)
        {
            // Already inside the lock
            _InterlockedIncrement(&m_counter);
        }
        else
        {
            LONG result = _InterlockedCompareExchange(&m_counter, 1, 0);
            if (result != 0)
                return false;
            //--- We are now inside the Lock ---
            m_owner = tid;
        }
        m_recursion++;
        return true;
    }
};

HTTP1.0

301: 永久重定向
302: 临时重定向

！默认关闭！
在HTTP 1.0中，服务器始终在发送响应后关闭连接， 除非客户端发送了Connection: keep-alive请求标头，并且服务器发送了一个Connection: keep-alive响应标头。 如果不存在这样的响应报头，则客户端在收到响应后必须关闭连接的结束。

！默认打开！
在HTTP 1.1中，服务器在发送响应之后不关闭连接， 除非客户端发送了Connection: close请求标头，或者服务器发送了Connection: close响应标头。 如果存在这样的响应头，则客户端在收到响应后必须关闭连接的结束。

HTTPS

可以参考：https://blog.csdn.net/xiaoming100001/article/details/81109617

对称加密与非对称加密相结合

通信内容，通过对称加密算法来加解密；其中有一个重要的东西叫：密钥

密钥是通过非对称加密算法来加密传输，客户端使用服务器的public key来加密，服务端通过自己的private key来解密。

服务器的public key，浏览器如何得知呢？ 通过SSL证书。

SSL证书组织是一个树形组织，最上面的几层是hardcode在系统中的。

当需要验证证书有效性时，浏览器会通过根认证组织逐层认证！

证书的制造过程：

（1）证书颁发由CA进行
（2）证书会对证书明文（网站信息）进行hash
（3）然后把hash用自己的私钥进行加密，得到数字签名

浏览器如何得到证书，如何如何验证证书？

（1）当访问网站S的时候，S会把自己的证书发回给浏览器
（2）浏览器看看证书的颁发者是否可信（如果不可信，需要递归进行，一直到Global CA，自验证！）
（3）如果可信的话，则讲证书明文信息进行hash，得到H1；然后用CA公钥对证书中的数字签名进行解密，得到H2；比对H1,H2是否一致；
（4）如果不一致，则说明证书被篡改；
（5）如果证书合法，一般情况下还校验证书明文中的域名与目标域名是否一致【这个检查是为了防止整个证书被某些网站调包！】
（5）至此，证书ok, 取出其中网站S的公钥用作后续通信的基础。

可以参考：https://www.cnblogs.com/hh9515/p/14885078.html

HTTP2.0

服务器推送、头信息压缩、等

二进制分帧

先来理解几个概念：

帧：HTTP/2 数据通信的最小单位消息：指 HTTP/2 中逻辑上的 HTTP 消息。例如请求和响应等，消息由一个或多个帧组成。

流：存在于连接中的一个虚拟通道。流可以承载双向消息，每个流都有一个唯一的整数ID。

HTTP/2 采用二进制格式传输数据，而非 HTTP 1.x 的文本格式，二进制协议解析起来更高效。 HTTP / 1 的请求和响应报文，都是由起始行，首部和实体正文（可选）组成，各部分之间以文本换行符分隔。HTTP/2 将请求和响应数据分割为更小的帧，并且它们采用二进制编码。

HTTP/2 中，同域名下所有通信都在单个连接上完成，该连接可以承载任意数量的双向数据流。每个数据流都以消息的形式发送，而消息又由一个或多个帧组成。多个帧之间可以乱序发送，根据帧首部的流标识可以重新组装。

多路复用

在 HTTP/2 中，有了二进制分帧之后，HTTP /2 不再依赖 TCP 链接去实现多流并行了，在 HTTP/2中：

同域名下所有通信都在单个连接上完成。
单个连接可以承载任意数量的双向数据流。
数据流以消息的形式发送，而消息又由一个或多个帧组成，多个帧之间可以乱序发送，因为根据帧首部的流标识可以重新组装。

服务器推送

服务端可以在发送页面HTML时主动推送其它资源，而不用等到浏览器解析到相应位置，发起请求再响应。例如服务端可以主动把JS和CSS文件推送给客户端，而不需要客户端解析HTML时再发送这些请求。

服务端可以主动推送，客户端也有权利选择是否接收。如果服务端推送的资源已经被浏览器缓存过，浏览器可以通过发送RST_STREAM帧来拒收。主动推送也遵守同源策略，服务器不会随便推送第三方资源给客户端。

头部压缩

HTTP 1.1请求的大小变得越来越大，有时甚至会大于TCP窗口的初始大小，因为它们需要等待带着ACK的响应回来以后才能继续被发送。HTTP/2对消息头采用HPACK（专为http/2头部设计的压缩格式）进行压缩传输，能够节省消息头占用的网络的流量。而HTTP/1.x每次请求，都会携带大量冗余头信息，浪费了很多带宽资源。

为了减少这块的资源消耗并提升性能， HTTP/2对这些首部采取了压缩策略：

HTTP/2在客户端和服务器端使用“首部表”来跟踪和存储之前发送的键－值对，对于相同的数据，不再通过每次请求和响应发送；

首部表在HTTP/2的连接存续期内始终存在，由客户端和服务器共同渐进地更新;

每个新的首部键－值对要么被追加到当前表的末尾，要么替换表中之前的值。

HTTP3.0

QUIC（Quick UDP Internet Connections）基于 UDP 实现，是 HTTP/3 中的底层支撑协议，该协议基于 UDP，又取了 TCP 中的精华，实现了即快又可靠的协议

参考：https://blog.51cto.com/u_6315133/3122045

负数

负数用补码来表示，补码等于数的反码 + 1

浮点数

两种表示小数的数据类型，分别是双精度浮点数和单精度浮点数

双精度浮点数类型用64位:符号位（1位） + 阶码（11位） + 尾数（52位）

单精度浮点数类型用32位:符号位（1位） + 阶码（8位） + 尾数（23位）

符号位：正数为0，负数为1；

指数位：阶数+偏移量，阶数是2^(e-1)-1，e为阶码的位数，也就是指数位的位数。偏移量是把小数点移动到整数位只有1时移动的位数，正数表示向左移，负数表示向右移；

小数位：即二进制小数点后面的数。

一个例子

大于零的数，采用除法取余；
小于0的数，采用乘法取余；
递归上面这个过程，直到变为0

把0.1(10)转成的二进制0.00011 0011 0011 …(2)转成浮点数形式的二进制：

（能够精确表示的小数为：0.5，0.25，0.125…等的自由组合）

转化过程见：https://cloud.tencent.com/developer/article/1856972

1、先要把小数点移动到整数位只有1，要向右移动4位，故偏移量为-4，通过指数位的计算公式2^(e-1)-1+偏移量 = 2^(11-1)-1-4 = 1019，把1019转成二进制为1111111011，不够11位要补零，最终得出指数位位01111111011；

2、移位后的小数位为.1 0011 0011 …，因为小数位只能保留52位，第50、51、52位、53位分别为0011，故对第52位进1使第51位为1，使第50、51、52位为010。

注意：此处的精度丢失问题，有很多小数（例如本例中的0.1）在转二进制时会出现无限循环的情况，所以在位数有限的境况下，肯定需要舍弃后面的精度。这一点，就与1/3这种小数是在十进制下无限循环类似。

定点数

只能表示纯小数，例如0.999991212

TLB（Translation Lookaside Buffer）是一块高速缓存。

TLB缓存虚拟地址和其映射的物理地址。

数据cache缓存地址(虚拟地址或者物理地址)和数据。

参考：https://zhuanlan.zhihu.com/p/108425561

存储的分布式化

高效存储的一些考虑：

1. 很长时间没有人访问的老数据，怎么办？
2. 是不是减少副本的同时，还能还原出数据？（例如，RAID）
3. 数据压缩，平成好压缩效果与压缩/解压速度
4. 数据的分层存储：根据数据的冷热来选择不同的存储介质（局部性原理），内存、硬盘（SSD、SATA)
5. 存储与计算分离（底层基础：网络IO不再是瓶颈，而CPU性能、磁盘IO性能跟不上）

分布式存储引擎

主要解决数据如何拆分、数据如何冗余、数据如何定位的问题。

（1）parititioning 方式，即数据在逻辑上怎么切分

（2）localization 方式，即数据在物理上怎么分布

一个系统要想拥有高可用性，有且只有一个办法 — 副本（replication），因为物理故障是无法避免的，只能花钱做备份。

主从和时效性是 replication 要考虑的两个重要问题。

主从主要有单主、多主和无主三种方式。

时效性主要有同步、异步、半同步三种方式。

（3）rebalance 方式，即在节点数变化后，数据在物理上怎么重新分布.

分布式文件系统

按照Block拆分文件，然后通过一个管理员来管理Block到对应及其的映射关系。

新的问题：
如果存储block的机器挂了怎么办？ 如果管理员挂了怎么办？

参考：https://zhuanlan.zhihu.com/p/141775358