硬件

冯诺依曼结构

运算器
控制器
存储器
输入
输出

现代计算机结构

CPU
位宽 32位 4B/64位 8B
32位CPU 最大只能操作2^32=4GB内存
寄存器
指令寄存器（存当前指令）通用寄存器（存数据）程序寄存器（存下一条指令的内存地址）

控制器
逻辑运算单元

CPU 执行程序的过程

第一步，CPU 读取「程序计数器」的值，这个值是指令的内存地址，然后 CPU 的「控制单元」操作「地址总线」指定需要访问的内存地址，接着通知内存设备准备数据，数据准备好后通过「数据总线」将指令数据传给 CPU，CPU 收到内存传来的数据后，将这个指令数据存入到「指令寄存器」。
第二步，「程序计数器」的值自增，表示指向下一条指令。这个自增的大小，由 CPU 的位宽决定，比如 32 位的 CPU，指令是 4 个字节，需要 4 个内存地址存放，因此「程序计数器」的值会自增 4；
第三步，CPU 分析「指令寄存器」中的指令，确定指令的类型和参数，如果是计算类型的指令，就把指令交给「逻辑运算单元」运算；如果是存储类型的指令，则交由「控制单元」执行；

磁盘

存储器结构

寄存器
CPU Cache
L1 Cache

数据缓存
指令缓存

L2 Cache
L3 Cache
内存
DRAM
SSD/HDD

Cache

Cache数据由内存读取，一块一块地读的。一块数据称为Cache Line

CPU在读数据时，无论数据是否在Cache中，都会先访问Cache。只有当Cache中找不到数据时才访问内存，并且把内存的数据读入Cache。

CPU如何访问Cache？以直接映射Cache为例

Cache与内存的映射关系

通过取模得到。

举个例子，内存共被划分为 32 个内存块，CPU Cache 共有 8 个 CPU Cache Line，假设 CPU 想要访问第 15 号内存块，如果 15 号内存块中的数据已经缓存在 CPU Cache Line 中的话，则是一定映射在 7 号 CPU Cache Line 中，因为 15 % 8 的值是 7

Cache Line中的Tag会标记该CacheLine 对应的内存块位置。

内存访问地址

组标记（TAG)
cache line索引 Index
偏移量 Offset

如果内存中的数据已经在 CPU Cache 中了，那 CPU 访问一个内存地址的时候，会经历这 4 个步骤：

根据内存地址中索引信息，计算在 CPU Cache 中的索引，也就是找出对应的 CPU Cache Line 的地址；
找到对应 CPU Cache Line 后，判断 CPU Cache Line 中的有效位，确认 CPU Cache Line 中数据是否是有效的，如果是无效的，CPU 就会直接访问内存，并重新加载数据，如果数据有效，则往下执行；
对比内存地址中组标记和 CPU Cache Line 中的组标记，确认 CPU Cache Line 中的数据是我们要访问的内存数据，如果不是的话，CPU 就会直接访问内存，并重新加载数据，如果是的话，则往下执行；
根据内存地址中偏移量信息，从 CPU Cache Line 的数据块中，读取对应的字。

Cache提升命中率

数据缓存：按照内存布局顺序访问，将可以有效的利用 CPU Cache 带来的好处

指令缓存：让分支预测器能有效工作。

多核CPU缓存命中率：线程在不同核心来回切换，各个核心的缓存命中率就会受到影响。可以把线程绑定在某一个 CPU 核心上，这样性能可以得到非常可观的提升。

数据一致性

数据写入内存时，如何保证内存数据和Cache一致。

写直达

数据同时写入内存和Cache（如果数据在Cache中的话）中。

简单但是性能不好，浪费写入时间

写回

发生写操作时，新数据如果在Cache中，先写到Cache Block里并标记为脏。数据如果不在Cache中，则定位对应的Cache Block，如果该Block标为脏，则将其中的数据写回内存，然后从内存读取需要写入的内存块到Cache Block中，将数据写到Cache Block中，并标记为脏。

内存

虚拟内存

我们程序所使用的内存地址叫做虚拟内存地址（Virtual Memory Address）
实际存在硬件里面的空间地址叫物理内存地址（Physical Memory Address）。
进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存。

操作系统通过内存分段（早期）或内存分页来管理虚拟地址映射。

内存分段

程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就用分段（Segmentation）的形式把这些段分离出来。

分段=段选择因子（段号+标志位） + 段内偏移量

段选择因子：保存在段寄存器内
段号：段表的索引
段表：段的基地址、段界限、特权级
段偏移量：0到段界限之间

程序被分为四个段
分段的不足之处
内存碎片
虽然分段可以做到内存按需分配，程序内部不会出现内部的内存碎片。但是由于每个段长度不一，当旧程序关闭后，会产生不连续的内存空间，产生外部内存碎片，导致新程序可能无法装载。
频繁内存交换，效率低

将已使用的段交换到硬盘中。然后再将这部分的数据存入连续的段中，拼凑内存碎片空间。
硬盘读写速度慢，因此内存交换费时。
好处
能产生连续的内存空间，

内存分页

解决分段的内存碎片多，内存交换的效率低的问题。

将内存分为一段段的固定大小，即是页。Linux中一页大小为4KB。

通过页表映射虚拟地址和物理地址。

页表是存储在内存里的，内存管理单元 （MMU）将虚拟内存地址转换成物理地址。

而当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行。

分页如何解决分段的缺陷

分页机制使得内存可以按固定大小划分，因此页之间是紧密排列的，不会出现外部缺陷。但是如果程序不足一页的大小，也得分配一个页给它。会存在页内的内部内存碎片。

内存空间不够时，操作系统可以把最近没被使用的内存页面换出（写入硬盘中），一次性写入磁盘的也只有少数的页，时间开销少。

甚至可以只有在程序运行中，需要用到对应虚拟内存页里面的指令和数据时，再加载到物理内存里面去。

分页机制如何将虚拟地址映射到物理地址

虚拟地址=页号+偏移量
页表：维护虚拟页号对应的物理页所在内存的基址

考虑32位环境下，虚拟地址空间有4GB，即是2^32个B。一个页大小为4KB（2^12B），则需要用2^20的页表项。一个页表项有4B，则需要一个2^22 = 4MB的空间用于维护页表。

100个进程就需要400MB。开销很大。

多级页表

上述情况下，将4MB的单级页表再次分页，一级页表分为1024个二级页表（10b），二级页表包含1024个页表项（10b）。一页有4KB，需要4K地址，需要12b维护。

一共32bit。

一级页表可以覆盖所有的虚拟地址空间，需要4B*1024 = 4KB大小，二级页表则可以在需要时再创建。

级数越多，页表占用空间越少。

TLB:Translation Lookaside Buffer 页表缓存

段页式内存管理

先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制；
接着再把每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页；
段号、段内页号和页内位移
段表（段号->页表）页表（页号->物理页号）

Linux内存管理

进程在用户态时，只能访问用户空间内存；
只有进入内核态后，才可以访问内核空间的内存；

用户空间内存

代码段，包括二进制可执行代码；
数据段，包括已初始化的静态常量和全局变量；
BSS 段，包括未初始化的静态变量和全局变量；
堆段，包括动态分配的内存，从低地址开始向上增长；
文件映射段，包括动态库、共享内存等，从低地址开始向上增长（跟硬件和内核版本有关(opens new window)）；
栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是 8 MB。当然系统也提供了参数，以便我们自定义大小；
保留区：不可访问的内存保留区，防止程序因为出现 bug，导致读或写了一些小内存地址的数据，而使得程序跑飞。

进程管理

线程与进程的比较

进程是资源（包括内存、打开的文件等）分配的单位，线程是 CPU 调度的单位；
进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
线程同样具有就绪、阻塞、执行三种基本状态，同样具有状态之间的转换关系；
线程能减少并发执行的时间和空间开销；

对于线程相比进程能减少开销，体现在：

线程的创建时间比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；
线程的终止时间比进程快，因为线程释放的资源相比进程少很多；
同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；
由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；

进程通信

1. 管道

匿名管道
管道是单向的，因此父子之间的进程双向通信需要建立两个管道
命名管道
可以在不相关的进程之间通信

2. 消息队列

数据单元为消息体，是用户自定义的数据类型大小固定
缺点

通信不及时
大小有限制，不适合大数据的传输
通信过程中存在用户态和内核态之间的数据拷贝开销

3. 共享内存

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。

4. 信号量

信号量其实是一个整型的计数器，主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据。
信号初始化为 1，就代表着是互斥信号量
信号初始化为 0，就代表着是同步信号量，它可以保证进程 A 应在进程 B 之前执行。

5. 信号

信号是进程间通信机制中唯一的异步通信机制，因为可以在任何时候发送信号给某一进程，一旦有信号产生，我们就有下面这几种，用户进程对信号的处理方式。

1.执行默认操作。Linux 对每种信号都规定了默认操作，例如，上面列表中的 SIGTERM 信号，就是终止进程的意思。
2.捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。
3.忽略信号。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，它们用于在任何时候中断或结束某一进程。

线程同步

线程互斥

使用互斥来让线程避免对临界资源的竞争

线程同步

并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步。

使用锁或者信号量实现线程互斥和线程同步

锁

自旋锁，即是忙等待锁

当获取不到锁时，线程就会一直 while 循环，不做任何事情。会忙等待

自旋锁是最比较简单的一种锁，一直自旋，利用 CPU 周期，直到锁可用。

开销少，在多核系统下一般不会主动产生线程切换，适合异步、协程等在用户态切换请求的编程方式，但如果被锁住的代码执行时间过长，自旋的线程会长时间占用 CPU 资源，所以自旋的时间和被锁住的代码执行的时间是成「正比」的关系，我们需要清楚的知道这一点。

互斥锁

互斥锁加锁失败后，线程会释放 CPU ，给其他线程；
会有两次线程上下文切换（切换线程的私有数据、寄存器等不共享的数据）的成本：

当线程加锁失败时，内核会把线程的状态从「运行」状态设置为「睡眠」状态，然后把 CPU 切换给其他线程运行；
接着，当锁被释放时，之前「睡眠」状态的线程会变为「就绪」状态，然后内核会在合适的时间，把 CPU 切换给该线程运行。
使用场景：能确定被锁住的代码执行时间很短，就不应该用互斥锁，而应该选用自旋锁，否则使用互斥锁。

读写锁

读写锁适用于能明确区分读操作和写操作的场景。

当「写锁」没有被线程持有时，多个线程能够并发地持有读锁，这大大提高了共享资源的访问效率，因为「读锁」是用于读取共享资源的场景，所以多个线程同时持有读锁也不会破坏共享资源的数据。
但是，一旦「写锁」被线程持有后，读线程的获取读锁的操作会被阻塞，而且其他写线程的获取写锁的操作也会被阻塞。

「读优先锁」

「写优先锁」

「公平读写锁」

乐观锁

乐观锁做事比较乐观，它假定冲突的概率很低

工作方式是：

先修改完共享资源，再验证这段时间内有没有发生冲突
如果没有其他线程在修改资源，那么操作完成
如果发现有其他线程已经修改过这个资源，就放弃本次操作。

只有在冲突概率非常低，且加锁成本非常高的场景时，才考虑使用乐观锁。

悲观锁

前面提到的互斥锁、自旋锁、读写锁，都是属于悲观锁。

悲观锁做事比较悲观，它认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁。

信号量

P 操作：将 sem 减 1，相减后，如果 sem < 0，则进程/线程进入阻塞等待，否则继续，表明 P 操作可能会阻塞；
V 操作：将 sem 加 1，相加后，如果 sem <= 0，唤醒一个等待中的进程/线程，表明 V 操作不会阻塞；

死锁避免

死锁只有同时满足以下四个条件才会发生：

互斥条件；
多个线程不能同时使用同一个资源。
持有并等待条件；
持有并等待条件是指，当线程 A 已经持有了资源 1，又想申请资源 2，而资源 2 已经被线程 C 持有了，所以线程 A 就会处于等待状态，但是线程 A 在等待资源 2 的同时并不会释放自己已经持有的资源 1。
不可剥夺条件；
线程已经持有了资源，在自己使用完之前不能被其他线程获取
环路等待条件；
两个线程获取资源的顺序构成了环形链。

利用工具排查死锁

Java jstack

C pstack+gdb

避免方式

最常见的并且可行的就是使用资源有序分配法，来破环环路等待条件。

调度算法

进程调度

FIFO

FCFS 对长作业有利，适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。

短作业优先

显然对长作业不利

高响应比优先

时间片轮转

如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程；
如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换；

时间片长度设置：

如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；
如果设得太长又可能引起对短作业进程的响应时间变长。

最高优先级调度

多用户计算机系统希望调度有优先级。

进程的优先级可以分为，静态优先级或动态优先级：

静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

非抢占式和抢占式：

非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

缺点：导致低优先级的进程永远不会运行。

多级反馈队列

「时间片轮转算法」和「最高优先级算法」的综合和发展。

设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；

内存页面置换算法

缺页中断

与一般中断的主要区别在于：

缺页中断在指令执行「期间」产生和处理中断信号，而一般中断在一条指令执行「完成」后检查和处理中断信号。
缺页中断返回到该指令的开始重新执行「该指令」，而一般中断返回回到该指令的「下一个指令」执行。

状态位：用于表示该页是否有效，也就是说是否在物理内存中，供程序访问时参考。
访问字段：用于记录该页在一段时间被访问的次数，供页面置换算法选择出页面时参考。
修改位：表示该页在调入内存后是否有被修改过，由于内存中的每一页都在磁盘上保留一份副本，因此，如果没有修改，在置换该页时就不需要将该页写回到磁盘上，以减少系统的开销；如果已经被修改，则将该页重写到磁盘上，以保证磁盘中所保留的始终是最新的副本。
硬盘地址：用于指出该页在硬盘上的地址，通常是物理块号，供调入该页时使用。