面试准备13-操作系统

面试准备之操作系统

常见架构

常用架构：

amd64/x86_64/x64 是 X86 架构的CPU，64位版。amd64 又叫 X86_64。主流的桌面PC，笔记本电脑，服务器（包括虚拟机）都在用X86_64的CPU。
arm64/aarch64 是 ARM 架构的CPU，64位版。苹果新出的电脑在用ARM架构的CPU。有些路由器和嵌入式设备在用arm64的CPU。手机和安卓平板电脑最常用的CPU也是ARM架构的。

Shell和Linux命令

linux命令参考笔记 Linux-常用命令
shell脚本参考笔记 Linux-Shell脚本
以及 Linux | 标签

调度算法

CFS调度器（1）-基本原理
https://www.jianshu.com/p/e97f6555a070

目前 Linux 支持的调度器就有 RT scheduler, Deadline scheduler, CFS scheduler 及 Idle scheduler 等。

调度类

从 Linux 2.6.23 开始，Linux 引入 调度类(scheduling class) 的概念，目的是将调度器模块化。这样提高了扩展性，添加一个新的调度器也变得简单起来。一个系统中还可以共存多个调度器。

调度类	描述	调度策略
dl_sched_class	deadline调度器	SCHED_DEADLINE
rt_sched_class	实时调度器	SCHED_FIFO, SCHED_RR
fair_sched_class	完全公平调度器	SCHED_NORMAL, SCHED_BATCH
idle_sched_class	idle task	SCHED_IDLE

CFS完全公平调度器

CFS(Completely Fair Scheduler) 即完全公平调度器。

CFS 的设计理念是在真实硬件上实现理想的、精确的多任务CPU。CFS 调度器和以往的调度器不同之处在于没有时间片的概念，而是分配 cpu 使用时间的比例。例如：2个相同优先级的进程在一个cpu上运行，那么每个进程都将会分配50%的cpu运行时间。这就是要实现的公平。

各个进程之间按照 权重(weight) 的比例分配 cpu 时间。
例如：2个进程A和B。A的权重是1024，B的权重是2048。
那么A获得cpu的时间比例是 1024/(1024+2048) = 33.3%
B进程获得的cpu时间比例是 2048/(1024+2048)=66.7%
所以，权重越大分配的时间比例越大，相当于优先级越高。在引入权重之后，分配给进程的时间计算公式如下：
分配给进程的时间 = 总的cpu时间 * 进程的权重/就绪队列（runqueue）所有进程权重之和

NICE值与权重

CFS 调度器针对优先级又提出了 nice 值的概念，也就是 ps 结果中的 NI 值。
NI: nice 值，表示进程可被执行的优先级的修正数值。是一个具体的数字，取值范围是 [-20, 19], 数值越小代表优先级越大，同时也意味着权重值越大。
进程真正的优先级等于 pri + nice 所以当 nice 为负值的时候，该程序的pri变小，优先级越高。
这也说明，nice 值越小，这个进程越不 nice, 抢占 cpu 的能力就越强，最终的优先级就越高。nice 值也做静态优先级。
所以，尽管进程的 nice 值不是进程的优先级，但是会影响进程优先级的变化。

nice 值和权重之间可以互相转换。内核提供了一个表格转换 nice 值和权重，是公式 weight = 1024 / 1.25^nice 的计算结果。
公式中的 1.25 取值依据是：进程每降低一个 nice 值，将多获得 10% cpu 的时间。公式中以 1024 权重为基准值计算得来，1024 权重对应 nice 值为0，其权重被称为 NICE_0_LOAD, 默认情况下，大部分进程的权重基本都是 NICE_0_LOAD

调度延迟

调度延迟就是保证每一个可运行进程都至少运行一次的时间间隔。例如，每个进程都运行10ms，系统中总共有2个进程，那么调度延迟就是20ms。如果有5个进程，那么调度延迟就是50ms。

如果现在保证调度延迟不变，固定是6ms，那么系统中如果有2个进程，那么每个进程运行3ms。如果有6个进程，那么每个进程运行1ms。如果有100个进程，那么每个进程分配到的时间就是0.06ms。随着进程的增加，每个进程分配的时间在减少，进程调度过于频繁，上下文切换时间开销就会变大。

因此，CFS调度器的调度延迟时间的设定并不是固定的。当系统处于就绪态的进程少于一个定值（默认值8）的时候，调度延迟也是固定一个值不变（默认值6ms）。当系统就绪态进程个数超过这个值时，我们保证每个进程至少运行一定的时间才让出cpu。这个“至少一定的时间”被称为最小粒度时间。在CFS默认设置中，最小粒度时间是0.75ms。用变量 sysctl_sched_min_granularity 记录。

虚拟时间

CFS 调度器的目标是保证每一个进程的完全公平调度。

例如，调度周期是6ms，系统一共2个相同优先级的进程A和B，那么每个进程都将在6ms周期时间内内各运行3ms。如果进程A和B，他们的权重分别是1024和820（nice值分别是0和1）。进程A获得的运行时间是6x1024/(1024+820)=3.3ms，进程B获得的执行时间是6x820/(1024+820)=2.7ms。进程A的cpu使用比例是3.3/6x100%=55%，进程B的cpu使用比例是2.7/6x100%=45%。计算结果也符合上面说的“进程每降低一个nice值，将多获得10% CPU的时间”。很明显，2个进程的实际执行时间是不相等的，但是CFS想保证每个进程运行时间相等。

因此CFS引入了虚拟时间的概念，也就是说上面的 2.7ms 和 3.3ms 经过一个公式的转换可以得到一样的值，这个转换后的值称作虚拟时间。这样的话，CFS只需要保证每个进程运行的虚拟时间是相等的即可。虚拟时间 vriture_runtime 和实际时间（wall time）转换公式如下：

                                 NICE_0_LOAD
vriture_runtime = wall_time * ----------------
                                    weight

进程A的虚拟时间3.3 * 1024 / 1024 = 3.3ms，我们可以看出nice值为0的进程的虚拟时间和实际时间是相等的。进程B的虚拟时间是2.7 * 1024 / 820 = 3.3ms。我们可以看出尽管A和B进程的权重值不一样，但是计算得到的虚拟时间是一样的。

因此 CFS 主要保证每一个进程获得执行的虚拟时间一致即可。在选择下一个即将运行的进程的时候，只需要找到虚拟时间最小的进程即可。

就绪队列(runqueue)

系统中每个CPU都会有一个全局的就绪队列（cpu runqueue），使用 struct rq 结构体描述，它是 per-cpu 类型，即 每个cpu上都会有一个struct rq结构体。每一个调度类也有属于自己管理的就绪队列。

例如，struct cfs_rq 是 CFS 调度类的就绪队列，管理就绪态的 struct sched_entity 调度实体，后续通过 pick_next_task 接口从就绪队列中选择最适合运行的调度实体（虚拟时间最小的调度实体）。

struct rt_rq 是实时调度器就绪队列。struct dl_rq 是 Deadline 调度器就绪队列。

CFS 维护了一个按照虚拟时间排序的红黑树，所有可运行的调度实体按照 p->se.vruntime 排序插入红黑树。CFS 选择红黑树最左边也就是虚拟时间最小的进程运行。随着系统时间的推移，原来左边运行过的进程慢慢的会移动到红黑树的右边，原来右边的进程也会最终跑到最左边。因此红黑树中的每个进程都有机会运行。

内存

虚拟内存

虚拟内存(Virtual Memory) 是操作系统内核为了对进程地址空间进行管理（process address space management）而精心设计的一个逻辑意义上的内存空间概念。
Linux采用虚拟内存管理技术，每个进程都有独立的进程地址空间。
我们程序中的指针其实都是这个虚拟内存空间中的地址。凡是程序运行过程中可能需要用到的指令或者数据都必须在虚拟内存空间中。

虚拟内存的好处？

1、扩大内存（主要催生虚拟内存原因）
2、安全性提高（不直接访问物理内存）
3、易于开发（每个进程拥有独立的用户空间）

页表(Page Table)

为了能够让程序在物理机器上运行，必须有一套机制可以让这些虚拟内存空间映射到物理内存空间（实实在在的RAM内存条上的空间），这就是操作系统中的 页映射表(page table)

内核会为系统中每一个进程维护一份相互独立的页映射表。页映射表的基本原理是将程序运行过程中需要访问的一段虚拟内存空间通过页映射表映射到一段物理内存空间上，这样CPU访问对应虚拟内存地址的时候就可以通过这种查找页映射表的机制访问物理内存上的某个对应的地址。
页(page) 是虚拟内存空间向物理内存空间映射的基本单元。

下图演示了虚拟内存空间和物理内存空间的相互关系，它们通过 Page Table 关联起来。其中虚拟内存空间中着色的部分分别被映射到物理内存空间对应相同着色的部分。而虚拟内存空间中灰色的部分表示在物理内存空间中没有与之对应的部分，也就是说灰色部分没有被映射到物理内存空间中。这么做也是本着“按需映射”的指导思想，因为虚拟内存空间很大，可能其中很多部分在一次程序运行过程中根本不需要访问，所以也就没有必要将虚拟内存空间中的这些部分映射到物理内存空间上。

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

虚拟内存空间大只能表示程序运行过程中可访问的空间比较大，不代表物理内存空间占用也大。

驻留内存

驻留内存(Resident Memory)，顾名思义是指那些被映射到进程虚拟内存空间的物理内存。

上图中，在系统物理内存空间中被着色的部分都是驻留内存。比如，A1、A2、A3和A4是进程A的驻留内存；B1、B2和B3是进程B的驻留内存。进程的驻留内存就是进程实实在在占用的物理内存。一般我们所讲的进程占用了多少内存，其实就是说的占用了多少驻留内存而不是多少虚拟内存。因为虚拟内存大并不意味着占用的物理内存大。

共享内存

上图中，进程 A 虚拟内存空间中的 A4 和进程 B 虚拟内存空间中的 B3 都映射到了物理内存空间的 A4/B3 部分，这部分就是进程 A 和进程 B 的共享内存。

为什么会出现这样的情况呢？
其实我们写的程序会依赖于很多外部的动态库（.so），比如 libc.so, libld.so 等等。这些动态库在内存中仅仅会保存/映射一份，如果某个进程运行时需要这个动态库，那么动态加载器会将这块内存映射到对应进程的虚拟内存空间中。
此外，多个进展之间通过共享内存的方式相互通信也会出现这样的情况。

这么一来，就会出现不同进程的虚拟内存空间会映射到相同的物理内存空间。这部分物理内存空间其实是被多个进程所共享的，所以我们将他们称为共享内存，用 SHR 来表示。某个进程占用的内存除了和别的进程共享的内存之外就是自己的独占内存了。所以要计算进程独占内存的大小只要用RES的值减去SHR值即可。

top命令中的VIRT/RES/SHR

VIRT virtual memory usage 虚拟内存。
进程需要的虚拟内存总量，单位kb。包括进程使用的库、代码、数据等。
VIRT=SWAP+RES
VIRT 包含了在已经映射到物理内存空间的部分和尚未映射到物理内存空间的部分总和。

RES resident memory usage 常驻内存。
进程当前使用的、未被换出的物理内存大小，单位kb。不包括swap out。
RES=CODE+DATA
RES 指进程虚拟内存空间中已经映射到物理内存空间的那部分的大小。
看进程在运行过程中占用了多少内存应该看RES的值而不是VIRT的值。

SHR shared memory 共享内存。共享内存大小，单位kb

理解virt res shr之间的关系 - linux
https://www.orchome.com/298

/proc/pid/maps 文件

/proc/pid/maps 记录进程的虚拟地址空间是如何使用的。
该文件有6列，从左到右分别为：
地址：本段在虚拟内存中的地址范围
权限：本段的权限，r=读，w=写,x=,s=共享,p=私有；
偏移量：偏移地址，即指本段映射地址在文件中的偏移
设备：映像文件的主设备号和次设备号；
节点：映像文件的节点号；
路径: 映像文件的路径
每项都与一个 vm_area_struct 结构成员对应

下面展示一个 Elasticsearch 进程的虚拟内存使用，可以看到大量映射了 Lucene 段数据文件。

# cat /proc/8417/maps 
600000000-7ffb00000 rw-p 00000000 00:00 0
7ffb00000-7ffb76000 rw-p 00c8c000 08:03 334238676         /usr/share/elasticsearch/jdk/lib/server/classes.jsa
7ffb76000-7ffc00000 rw-p 00000000 00:00 0
7ffc00000-7ffc82000 rw-p 00c0a000 08:03 334238676         /usr/share/elasticsearch/jdk/lib/server/classes.jsa
7ffc82000-800000000 rw-p 00000000 00:00 0
800000000-80043b000 rw-p 00001000 08:03 334238676         /usr/share/elasticsearch/jdk/lib/server/classes.jsa
80043b000-800bd1000 r--p 0043c000 08:03 334238676         /usr/share/elasticsearch/jdk/lib/server/classes.jsa
800bd1000-800c00000 ---p 00000000 00:00 0
800c00000-800c40000 rw-p 00000000 00:00 0
5594e84e8000-5594e84e9000 r-xp 00000000 08:03 334238180   /usr/share/elasticsearch/jdk/bin/java
5594e86e9000-5594e86ea000 r--p 00001000 08:03 334238180   /usr/share/elasticsearch/jdk/bin/java
5594e86ea000-5594e86eb000 rw-p 00002000 08:03 334238180   /usr/share/elasticsearch/jdk/bin/java
5594ea3b1000-5594ea3d2000 rw-p 00000000 00:00 0           [heap]
7cc42ef3f000-7cc46ef3f000 r--s c0000000 08:03 170395548   /usr/share/elasticsearch/data/nodes/0/indices/6uNlMASdSAGPNjHUNo9JiA/0/index/_t17.cfs
7cc46ef3f000-7cc4aef3f000 r--s c0000000 08:03 170396357   /usr/share/elasticsearch/data/nodes/0/indices/6uNlMASdSAGPNjHUNo9JiA/1/index/_uym.cfs
7cc4aef3f000-7cc4ece00000 r--s 100000000 08:03 170396409  /usr/share/elasticsearch/data/nodes/0/indices/6uNlMASdSAGPNjHUNo9JiA/0/index/_syt.cfs
7cc4ece00000-7cc52ce00000 r--s c0000000 08:03 170396409   /usr/share/elasticsearch/data/nodes/0/indices/6uNlMASdSAGPNjHUNo9JiA/0/index/_syt.cfs
7f0aa0478000-7f0abb409000 r--s 00000000 08:03 170394844   /usr/share/elasticsearch/data/nodes/0/indices/6uNlMASdSAGPNjHUNo9JiA/1/index/_1dy_Lucene80_0.dvd
7f0abb409000-7f0ad91f5000 r--s 00000000 08:03 170394563   /usr/share/elasticsearch/data/nodes/0/indices/6uNlMASdSAGPNjHUNo9JiA/1/index/_13k_Lucene80_0.dvd
7f0ad91f5000-7f0aef275000 r--s 00000000 08:03 170394757   /usr/share/elasticsearch/data/nodes/0/indices/6uNlMASdSAGPNjHUNo9JiA/1/index/_13k_Lucene84_0.tim
7f0af2174000-7f0b0ca76000 r--s 00000000 08:03 170394502   /usr/share/elasticsearch/data/nodes/0/indices/6uNlMASdSAGPNjHUNo9JiA/0/index/_1k2_Lucene84_0.tim
7f13d110c000-7f13d12e6000 r--s 00000000 08:03 170394538   /usr/share/elasticsearch/data/nodes/0/indices/6uNlMASdSAGPNjHUNo9JiA/1/index/_kf_Lucene84_0.tip
7f13d13b1000-7f13d1526000 r--s 00000000 08:03 170394273   /usr/share/elasticsearch/data/nodes/0/indices/6uNlMASdSAGPNjHUNo9JiA/1/index/_sk_Lucene84_0.tip

/proc/pid/smaps 文件

/proc/pid/smaps 文件是基于 /proc/pid/maps 的扩展，他展示了一个进程的内存消耗，比同一目录下的 maps 文件更为详细。

通过分析 /proc/pid/maps 文件，我们可以知道：
进程的虚拟内存空间的分布情况，比如heap占用了多少空间、文件映射（mmap）占用了多少空间、stack占用了多少空间？
进程是否有被交换到swap空间的内存，如果有，被交换出去的大小？
mmap方式打开的数据文件有多少页在内存中是脏页（dirty page）没有被写回到磁盘的？
mmap方式打开的数据文件当前有多少页面已经在内存中，有多少页面还在磁盘中没有加载到page cahe中？

在smaps文件中，每一条记录表示进程虚拟内存空间中一块连续的区域，叫做VMA（虚拟内存区域，即一个 vm_area_struct 结构指向的内存区域）

一、第一行，基础信息。第一行的信息完全同于在maps文件中输出的信息。
e3400000-e5130000 该虚拟内存段的开始和结束位置
rw-p 内存段的权限，分别是可读、可写、可运行、私有或共享，最后一位p代表私有，s代表共享
00000000 该虚拟内存段起始地址在对应的映射文件中以页为单位的偏移量，对匿名映射，它等于0或者vm_start/PAGE_SIZE
ca:01 文件的主设备号和次设备号。对匿名映射来说，因为没有文件在磁盘上，所以没有设备号，始终为00:00。对文件映射来说，是映射的文件所在设备的设备号。
96541664 被映射到虚拟内存的文件的索引节点号，通过该节点可以找到对应的文件，对匿名映射来说，因为没有文件在磁盘上，所以没有节点号，始终为0
/app.jar 被映射到虚拟内存的文件名称。后面带(deleted)的是内存数据，可以被销毁。对文件映射来说，是映射的文件名。对匿名映射来说，是此段虚拟内存在进程中的角色。[stack]表示在进程中作为栈使用，[heap]表示堆。其余情况则无显示。

二、详细信息
Size 虚拟内存空间大小。但是这个内存值不一定是物理内存实际分配的大小，因为在用户态上，虚拟内存总是延迟分配的。这个值计算也非常简单，就是该VMA的开始位置减结束位置。
延迟分配就是当进程申请内存的时候，Linux会给他先分配页，但是并不会区建立页与页框的映射关系，意思就是说并不会分配物理内存，而当真正使用的时候，就会产生一个缺页异常，硬件跳转page fault处理程序执行，在其中分配物理内存，然后修改页表(创建页表项)。异常处理完毕，返回程序用户态，继续执行。

Rss 是实际分配的内存，这部分物理内存已经分配，不需要缺页中断就可以使用的。表示该映射区域当前在物理内存中占用了多少空间。
Rss=Shared_Clean+Shared_Dirty+Private_Clean+Private_Dirty
　　　
Shared_Clean 和其他进程共享的未被改写的page的大小
Shared_Dirty 和其他进程共享的被改写的page的大小
Private_Clean 未被改写的私有页面的大小。
Private_Dirty 已被改写的私有页面的大小。
share/private：该页面是共享还是私有。
dirty/clean：该页面是否被修改过，如果修改过（dirty），在页面被淘汰的时候，就会把该脏页面回写到交换分区（换出，swap out）。有一个标志位用于表示页面是否dirty。
share/private_dirty/clean 计算逻辑：
查看该page的引用数，如果引用>1，则归为shared，如果是1，则归为private，同时也查看该page的flag，是否标记为_PAGE_DIRTY，如果不是，则认为干净的。

Swap 表示非mmap内存（也叫anonymous memory，比如malloc动态分配出来的内存）由于物理内存不足被swap到交换空间的大小。

Pss proportional set size, 该虚拟内存区域平摊计算后使用的物理内存大小(有些内存会和其他进程共享，例如mmap进来的)。比如该区域所映射的物理内存部分同时也被另一个进程映射了，且该部分物理内存的大小为1000KB，那么该进程分摊其中一半的内存，即Pss=500KB。

Referenced 当前页面被标记为已引用或者包含匿名映射（The amount of memory currently marked as referenced or a mapping associated with a file may contain anonymous pages）。
当某个页面被访问后，Referenced标志被设置，如果该标志设置了，就不能将该页移出。

Anonymous 匿名映射的物理内存，这部分内存不来自于文件的内存大小。

KernelPageSize 内核一页的大小
MMUPageSize MMU页大小，大多数情况下，和 KernelPageSize 大小一样。
Locked 常驻物理内存的大小，这些页不会被换出。
VmFlags 表示与特定虚拟内存区域关联的内核标志。

rd  - readable
wr  - writeable
ex  - executable
sh  - shared
mr  - may read
mw  - may write
me  - may execute
ms  - may share
gd  - stack segment growns down
pf  - pure PFN range
dw  - disabled write to the mapped file
lo  - pages are locked in memory
io  - memory mapped I/O area
sr  - sequential read advise provided
rr  - random read advise provided
dc  - do not copy area on fork
de  - do not expand area on remapping
ac  - area is accountable
nr  - swap space is not reserved for the area
ht  - area uses huge tlb pages
ar  - architecture specific flag
dd  - do not include area into core dump
sd  - soft-dirty flag
mm  - mixed map area
hg  - huge page advise flag
nh  - no-huge page advise flag
mg  - mergable advise flag

smaps 文件部分示例

$ sudo cat /proc/13697/smaps
e3400000-e5130000 rw-p 00000000 00:00 0
Size:              29888 kB
Rss:               24288 kB
Pss:               24288 kB
Shared_Clean:          0 kB
Shared_Dirty:          0 kB
Private_Clean:         0 kB
Private_Dirty:     24288 kB
Referenced:        20200 kB
Anonymous:         24288 kB
AnonHugePages:         0 kB
Swap:                708 kB
KernelPageSize:        4 kB
MMUPageSize:           4 kB
Locked:                0 kB
VmFlags: rd wr mr mp me ac sd
561859ea9000-56185e1ad000 rw-p 00000000 00:00 0                          [heap]
Size:              68624 kB
Rss:               16812 kB
Pss:               16812 kB
Shared_Clean:          0 kB
Shared_Dirty:          0 kB
Private_Clean:      8272 kB
Private_Dirty:      8540 kB
Referenced:         6432 kB
Anonymous:         16812 kB
AnonHugePages:         0 kB
Swap:              37432 kB
KernelPageSize:        4 kB
MMUPageSize:           4 kB
Locked:                0 kB
VmFlags: rd wr mr mp me ac sd
7ffca3025000-7ffca3046000 rw-p 00000000 00:00 0                          [stack]
Size:                132 kB
Rss:                   4 kB
Pss:                   4 kB
Shared_Clean:          0 kB
Shared_Dirty:          0 kB
Private_Clean:         4 kB
Private_Dirty:         0 kB
Referenced:            4 kB
Anonymous:             4 kB
AnonHugePages:         0 kB
Swap:                 20 kB
KernelPageSize:        4 kB
MMUPageSize:           4 kB
Locked:                0 kB
VmFlags: rd wr mr mp me gd ac
7fa27e6bc000-7fa27e6bd000 rw-p 00013000 ca:01 96541664                   /usr/lib/jvm/java-1.8-openjdk/jre/lib/amd64/libnio.so
Size:                  4 kB
Rss:                   4 kB
Pss:                   4 kB
Shared_Clean:          0 kB
Shared_Dirty:          0 kB
Private_Clean:         0 kB
Private_Dirty:         4 kB
Referenced:            4 kB
Anonymous:             4 kB
AnonHugePages:         0 kB
Swap:                  0 kB
KernelPageSize:        4 kB
MMUPageSize:           4 kB
Locked:                0 kB
VmFlags: rd wr mr mp me ac sd
7fa27e6f6000-7fa27e6fd000 r--s 04cb0000 ca:01 67155858                   /app.jar
Size:                 28 kB
Rss:                   0 kB
Pss:                   0 kB
Shared_Clean:          0 kB
Shared_Dirty:          0 kB
Private_Clean:         0 kB
Private_Dirty:         0 kB
Referenced:            0 kB
Anonymous:             0 kB
AnonHugePages:         0 kB
Swap:                  0 kB
KernelPageSize:        4 kB
MMUPageSize:           4 kB
Locked:                0 kB
VmFlags: rd mr me ms sd
7fa27ef58000-7fa27f128000 r--s 01f56000 ca:01 92694934                   /usr/lib/jvm/java-1.8-openjdk/jre/lib/rt.jar
Size:               1856 kB
Rss:                   0 kB
Pss:                   0 kB
Shared_Clean:          0 kB
Shared_Dirty:          0 kB
Private_Clean:         0 kB
Private_Dirty:         0 kB
Referenced:            0 kB
Anonymous:             0 kB
AnonHugePages:         0 kB
Swap:                  0 kB
KernelPageSize:        4 kB
MMUPageSize:           4 kB
Locked:                0 kB
VmFlags: rd mr me ms sd

理解virt res shr之间的关系 - linux
https://www.orchome.com/298

Linux内存管理 – /proc/{pid}/smaps讲解
https://www.jianshu.com/p/8203457a11cc

用户空间与内核空间

现在操作系统都是采用虚拟存储器，那么对32位操作系统而言，它的寻址空间（虚拟存储空间）为4G（2的32次方）。
操作系统的核心是内核，独立于普通的应用程序，可以访问受保护的内存空间，也有访问底层硬件设备的所有权限。
为了保证用户进程不能直接操作内核（kernel），保证内核的安全，操心系统将虚拟空间划分为两部分，一部分为内核空间，一部分为用户空间。
针对linux操作系统而言，将最高的1G字节（从虚拟地址0xC0000000到0xFFFFFFFF），供内核使用，称为内核空间，而将较低的3G字节（从虚拟地址0x00000000到0xBFFFFFFF），供各个进程使用，称为用户空间。

内存分页

在基本的分页概念中，我们把程序分成等长的小块。这些小块叫做“页（Page）”，同样内存也被我们分成了和页面同样大小的”页框（Frame）“，一个页可以装到一个页框里。在执行程序的时候我们根据一个页表去查找某个页面在内存的某个页框中，由此完成了逻辑到物理的映射。

为什么要分页？(内存碎片/虚拟内存)

内存的分段和分页管理方式和由此衍生的一堆段页式等都属于内存的不连续分配。什么叫不连续分配？就是把程序分割成一块一块的装入内存，在物理上不用彼此相连，在逻辑上使用段表或者页表将离散分布的这些小块串起来形成逻辑上连续的程序。

（1）解决空间浪费碎片化问题
由于将虚拟内存空间和物理内存空间按照某种规定的大小进行分配，这里我们称之为页（Page），然后按照页进行内存分配，也就克服了外部碎片的问题。

（2）解决程序大小受限问题
程序增长有限是因为一个程序需要全部加载到内存才能运行，因此解决的办法就是使得一个程序无须全部加载就可以运行。使用分页也可以解决这个问题，只需将当前需要的页面放在内存里，其他暂时不用的页面放在磁盘上，这样一个程序同时占用内存和磁盘，其增长空间就大大增加了。而且，分页之后，如果一个程序需要更多的空间，给其分配一个新页即可（而无需将程序倒出倒进从而提高空间增长效率）。

一般一个内存页大小为4KB

在32位操作系统中,一个地址对应32位2进制数,则能寻址到4GB(2^32)的地址.而在linux内存管理中,内存以页为单位进行管理,一般情况下每页4KB大小,4GB内存就有(4GB/4KB=2^20)个页.所以可将一个32位的地址分为20位+12位.前20位可以确定出地址在2^20个页中的哪一页,剩下的12位就可以确定出在这一页中的哪个位置.
反过来,若是知道了页内为12位,那每页大小就肯定为了

二维数组按列遍历缺页率更高

buffer/cache内存

buffer 用于提高磁盘写入效率，也就是写缓存
cache 用于提高磁盘读取效率，也就是读缓存

在服务内存够用的情况下，Linux 内核为了加快对文件的读写效率会将文件放入之 buffer/cache 中以保证读写效率，但其实，尽管当你的应用程序对文件的读写运行结束后，buffer/cache 也不会自动释放该部分内存，而是作为缓冲进行保留，等到你的服务进程在下一次进行相同文件的读写时就可以直接使用，省去了各种重新进行内存初始化的操作；所以这将会导致，当你的应用进程频繁对不同的文件进行读写时，你会发现服务所可以直接使用的free内存将会越来越少的一个重要原因；

难道 buffer/cache 在这样无休止的缓存当中就不会自动释放？
当然不是，当服务器在内存压力较大的情况下时，则将会自动进行内存的回收，作为 free 空间分给其它进程使用，这其中主要回收的一个内存则是 buffer/cache 的缓冲区内存块；

手动 buffer/cache 回收

c/c++中delete/free如何知道释放多少内存？

在使用c或者c++的时候我们经常用到malloc/free和new/delete，在使用malloc申请内存的时候我们给定了需要申请的内存大小，但是在free或者delete的时候并不需要提供这个大小，那么程序是怎么实现准确无误的释放内存的呢？

实际上，在申请内存的时候，申请到的地址会比你实际的地址大一点点，他包含了一个存有申请空间大小的结构体。
比如你申请了20byte的空间，实际上系统申请了48bytes的block
这样在free的时候就不需要提供任何其他的信息，可以正确的释放内存

大多数实现所分配的存储空间比所要求的要稍大一些，额外的空间用来记录管理信息——分配块的长度，指向下一个分配块的指针等等。这就意味着如果写过一个已分配区的尾端，则会改写后一块的管理信息。这种类型的错误是灾难性的，但是因为这种错误不会很快就暴露出来，所以也就很难发现。

malloc()申请的空间实际就是分了两个不同性质的空间。一个就是用来记录管理信息的空间，另外一个就是可用空间了。而用来记录管理信息的实际上是一个结构体。在C语言中，经常用结构来记录信息！下面看看这个结构体的原型：

struct mem_control_block {
 int is_available;    //一般来说应该是一个可用空间的首地址，但这里英文单词却显示出空间是否可用的一个标记
 int size;            //这是实际空间的大小
 };

How does free know how much to free?
https://stackoverflow.com/questions/1518711/how-does-free-know-how-much-to-free

IO

缓冲IO(传统IO)

Linux 中传统的 I/O 操作是一种缓冲 I/O，I/O 过程中产生的数据传输通常需要在缓冲区中进行多次的拷贝操作。

缓存 I/O 又被称作标准 I/O，大多数文件系统的默认 I/O 操作都是缓存 I/O。在 Linux 的缓存 I/O 机制中，操作系统会将 I/O 的数据缓存在文件系统的 页缓存(page cache)中，也就是说，数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。

一般来说，在传输数据的时候，用户应用程序需要分配一块大小合适的缓冲区用来存放需要传输的数据。以应用程序从文件中读取一块数据然后把这块数据通过网络发送到接收端去为例，用户应用程序只是需要调用两个系统调用 read() 和 write() 就可以完成这个数据传输操作，应用程序并不知晓在这个数据传输的过程中操作系统所做的数据拷贝操作。对于 Linux 操作系统来说，基于数据排序或者校验等各方面因素的考虑，操作系统内核会在处理数据传输的过程中进行多次拷贝操作。在某些情况下，这些数据拷贝操作会极大地降低数据传输的性能。

当应用程序访问某块数据时，操作系统首先会检查，是不是最近访问过此文件，文件内容是否缓存在内核缓冲区，如果是，操作系统则直接根据 read 系统调用提供的 buf 地址，将内核缓冲区的内容拷贝到 buf 所指定的用户空间缓冲区中去。如果不是，操作系统则首先将磁盘上的数据拷贝的内核缓冲区，这一步目前主要依靠 DMA 来传输，然后再把内核缓冲区上的内容拷贝到用户缓冲区中。接下来， write 系统调用再把用户缓冲区的内容拷贝到网络堆栈相关的内核缓冲区中，最后 socket 再把内核缓冲区的内容发送到网卡上。

缓冲IO示意图

从上图中可以看出，共产生了四次数据拷贝，即使使用了 DMA 来处理了与硬件的通讯，CPU仍然需要处理两次数据拷贝，与此同时，在用户态与内核态也发生了多次上下文切换，无疑也加重了CPU负担。
在此过程中，我们没有对文件内容做任何修改，那么在内核空间和用户空间来回拷贝数据无疑就是一种浪费，而零拷贝主要就是为了解决这种低效性。

缓存 I/O 的缺点：
数据在传输过程中需要在应用程序地址空间和内核进行多次数据拷贝操作，这些数据拷贝操作所带来的 CPU 以及内存开销是非常大的。

其他IO和网络技术

kernel-bypass

应用绕过 kernel，直接将磁盘拷贝到网卡。
听起来类似零拷贝

RDMA 远程内存访问

在数据中心领域，远程直接内存访问（英语：remote direct memory access，RDMA）是一种绕过远程主机操作系统内核访问其内存中数据的技术

EC编码(纠删码)

纠删码(Erasure Coding, EC)
基于纠偏码，将3备份降低为1.x备份

fast-pass/slow-pass

网关服务器只做握手，控制报文处理。
真正开始数据转发后，回包直接由后台服务器发送给请求方。

零拷贝技术

零拷贝就是一种避免 CPU 将数据从一块存储拷贝到另外一块存储的技术。

mmap() 跳过用户空间

mmap() 让数据传输不需要经过user space

减少拷贝次数的一种方法是调用mmap()来代替read调用：

buf = mmap(diskfd, len);
write(sockfd, buf, len);

应用程序调用 mmap()，磁盘上的数据会通过DMA被拷贝到内核缓冲区，接着操作系统会把这段内核缓冲区与应用程序共享，这样就不需要把内核缓冲区的内容往用户空间拷贝。
应用程序再调用 write() , 操作系统直接将内核缓冲区的内容拷贝到socket缓冲区中，这一切都发生在内核态，最后，socket缓冲区再把数据发到网卡去。

sendfile() 文件到socket零拷贝

从2.1版内核开始，Linux引入了 sendfile() 来简化操作:

#include<sys/sendfile.h>
ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);

系统调用 sendfile() 在代表输入文件的描述符 in_fd 和代表输出文件的描述符 out_fd 之间传送文件内容（字节）。
描述符 out_fd 必须指向一个套接字，而 in_fd 指向的文件必须是可以 mmap 的。
这些局限限制了 sendfile 的使用，使 sendfile 只能将数据从文件传递到套接字上，反之则不行。
使用 sendfile 不仅减少了数据拷贝的次数，还减少了上下文切换，数据传送始终只发生在kernel space。

sendfile()示意图

splice() 任意文件描述符间零拷贝

sendfile() 只适用于将数据从文件拷贝到套接字上，限定了它的使用范围。
Linux在2.6.17版本引入 splice() 系统调用，用于在两个文件描述符中移动数据：

#define _GNU_SOURCE         /* See feature_test_macros(7) */
#include <fcntl.h>
ssize_t splice(int fd_in, loff_t *off_in, int fd_out, loff_t *off_out, size_t len, unsigned int flags);

splice调用在两个文件描述符之间移动数据，而不需要数据在内核空间和用户空间来回拷贝。
他从fd_in拷贝len长度的数据到fd_out，但是有一方必须是管道设备，这也是目前splice的一些局限性。

写时复制(Copy On Write,COW)

写时复制是计算机编程中的一种优化策略，它的基本思想是这样的：如果有多个应用程序需要同时访问同一块数据，那么可以为这些应用程序分配指向这块数据的指针，在每一个应用程序看来，它们都拥有这块数据的一份数据拷贝，当其中一个应用程序需要对自己的这份数据拷贝进行修改的时候，就需要将数据真正地拷贝到该应用程序的地址空间中去，也就是说，该应用程序拥有了一份真正的私有数据拷贝，这样做是为了避免该应用程序对这块数据做的更改被其他应用程序看到。这个过程对于应用程序来说是透明的，如果应用程序永远不会对所访问的这块数据进行任何更改，那么就永远不需要将数据拷贝到应用程序自己的地址空间中去。这也是写时复制的最主要的优点。

浅析Linux中的零拷贝技术（讲的非常透彻，比IMB的文章还清晰易懂）
https://www.jianshu.com/p/fad3339e3448

Linux 中的零拷贝技术，第 1 部分
https://www.ibm.com/developerworks/cn/linux/l-cn-zerocopy1/index.html

Linux 中的零拷贝技术，第 2 部分
https://www.ibm.com/developerworks/cn/linux/l-cn-zerocopy2/index.html

面试被问到“零拷贝”！你真的理解吗？
https://mp.weixin.qq.com/s/UejA6zQFwIatWRp2uTEatg

5种IO模型

对于一次IO访问（以read举例），数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。
所以说，当一个read操作发生时，它会经历两个阶段：

等待数据准备 (Waiting for the data to be ready)
将数据从内核拷贝到进程中 (Copying the data from the kernel to the process)

正式因为这两个阶段，linux系统产生了5种IO模型
在《Unix网络编程》一书中提到了五种IO模型，分别是：

阻塞IO
非阻塞IO
多路复用IO
信号驱动IO
异步IO。

阻塞IO(blocking IO)

阻塞IO(blocking IO) 是最传统的一种IO模型，即在读写数据过程中用户线程会发生阻塞现象并交出CPU。
在linux中，默认情况下所有的socket都是blocking
典型的阻塞IO系统调用有 read(), write(), send(), recv(), sendto(), recvfrom()

当用户进程调用了 recvfrom 这个系统调用，kernel就开始了IO的第一个阶段：准备数据（对于网络IO来说，很多时候数据在一开始还没有到达。比如，还没有收到一个完整的UDP包。这个时候kernel就要等待足够的数据到来）。这个过程需要等待，也就是说数据被拷贝到操作系统内核的缓冲区中是需要一个过程的。而在用户进程这边，整个进程会被阻塞（当然，是进程自己选择的阻塞）。当kernel一直等到数据准备好了，它就会将数据从kernel中拷贝到用户内存，然后kernel返回结果，用户进程才解除block的状态，重新运行起来。
所以，blocking IO的特点就是在IO执行的两个阶段都被block了。

非阻塞IO(nonblocking IO)

当用户线程发起一个read操作后，并不需要等待，而是马上就得到了一个结果。如果结果是一个error时，它就知道数据还没有准备好，于是它可以再次发送read操作。一旦内核中的数据准备好了，并且又再次收到了用户线程的请求，那么它马上就将数据拷贝到了用户线程，然后返回。
在非阻塞IO模型中，用户线程需要不断地询问内核数据是否就绪，也就说非阻塞IO不会交出CPU，而会一直占用CPU。

当用户进程发出read操作时，如果kernel中的数据还没有准备好，那么它并不会block用户进程，而是立刻返回一个error。从用户进程角度讲，它发起一个read操作后，并不需要等待，而是马上就得到了一个结果。用户进程判断结果是一个error时，它就知道数据还没有准备好，于是它可以再次发送read操作。一旦kernel中的数据准备好了，并且又再次收到了用户进程的system call，那么它马上就将数据拷贝到了用户内存，然后返回。
所以，nonblocking IO的特点是用户进程需要不断的主动询问kernel数据好了没有。

多路复用IO(IO multiplexing)

多路复用IO模型是目前使用得比较多的模型。Java NIO实际上就是多路复用IO。
在多路复用IO模型中，会有一个线程不断去轮询多个socket的状态，只有当socket真正有读写事件时，才真正调用实际的IO读写操作。因为在多路复用IO模型中，只需要使用一个线程就可以管理多个socket，系统不需要建立新的进程或者线程，也不必维护这些线程和进程，并且只有在真正有socket读写事件进行时，才会使用IO资源，所以它大大减少了资源占用。

在Java NIO中，是通过 selector.select() 去查询每个通道是否有到达事件，如果没有事件，则一直阻塞在那里，因此这种方式会导致用户线程的阻塞。

IO multiplexing 就是我们说的 select, poll, epoll，有些地方也称这种IO方式为event driven IO。select/epoll的好处就在于单个process就可以同时处理多个网络连接的IO。它的基本原理就是select，poll，epoll这个function会不断的轮询所负责的所有socket，当某个socket有数据到达了，就通知用户进程。

当用户进程调用了select，那么整个进程会被block，而同时，kernel会“监视”所有select负责的socket，当任何一个socket中的数据准备好了，select就会返回。这个时候用户进程再调用read操作，将数据从kernel拷贝到用户进程。
所以，I/O 多路复用的特点是通过一种机制一个进程能同时等待多个文件描述符，而这些文件描述符（套接字描述符）其中的任意一个进入读就绪状态，select()函数就可以返回。

所以，如果处理的连接数不是很高的话，使用select/epoll的web server不一定比使用multi-threading + blocking IO的web server性能更好，可能延迟还更大。
select/epoll 的优势并不是对于单个连接能处理得更快，而是在于能处理更多的连接。

信号驱动IO(Signal Driven IO/SIGIO)

在信号驱动IO模型中，当用户线程发起一个IO请求操作，会给对应的socket注册一个信号函数，然后用户线程会继续执行，当内核数据就绪时会发送一个信号给用户线程，用户线程接收到信号之后，便在信号函数中调用IO读写操作来进行实际的IO请求操作。

异步IO(asynchronous IO)

异步IO模型才是最理想的IO模型。在异步IO模型中，当用户线程发起read操作之后，立刻就可以开始去做其它的事。而另一方面，从内核的角度，当它收到一个asynchronous read之后，它会立刻返回，说明read请求已经成功发起了，因此不会对用户线程产生任何block。然后，内核会等待数据准备完成，然后将数据拷贝到用户线程，当这一切都完成之后，内核会给用户线程发送一个信号，告诉它read操作完成了。
也就说用户线程完全不需要知道实际的整个IO操作是如何进行的，只需要先发起一个请求，当接收内核返回的成功信号时表示IO操作已经完成，可以直接去使用数据了。
也就说在异步IO模型中，IO操作的两个阶段（IO请求、数据读写）都不会阻塞用户线程，这两个阶段都是由内核自动完成，然后发送一个信号告知用户线程操作已完成。

前面四种IO模型实际上都属于同步IO，只有最后一种是真正的异步IO，因为无论是多路复用IO还是信号驱动模型，IO操作的第2个阶段都会引起用户线程阻塞，也就是内核进行数据拷贝的过程都会让用户线程阻塞。

Linux IO模式及 select、poll、epoll详解
https://segmentfault.com/a/1190000003063859

Nginx为什么比Apache Httpd高效：原理篇
http://www.mamicode.com/info-detail-1156329.html

3种多路复用IO(NIO)模型select/poll/epoll

select, poll, epoll 都是IO多路复用(IO Multiplexing)的机制。
所以，也可以说， select, poll, epoll 是3种 NIO 的实现方式。
I/O 多路复用就是通过一种机制，一个进程可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作。
但 select, pselect, poll, epoll 本质上都是同步 I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的。

select()

int select(
    int nfds, //忽略，一般设为0
    fd_set * readfds, //等待可读性检查的socket队列
    fd_set * writefds, //等待可写性检查的socket队列
    fd_set * exceptfds, //等待错误检查的socket队列
    const struct timeval * timeout  //超时时间，最长等待时间
);

select 函数监视的文件描述符分 3 类，分别是 writefds, readfds, exceptfds, 调用后 select 函数会阻塞，传入的 fd 集合由用户态拷贝到内核态，然后查询每个 fd 对应的设备状态，直到有描述符就绪（有数据可读、可写、或者有 exception），或者超时（ timeout 指定等待时间，如果立即返回设为 null 即可），函数返回。当 select 函数返回后，可以通过遍历 fdset，来找到就绪的描述符。

select 函数会将不符合要求的socket从队列删除，所以 select 函数返回后每个集合中都是就绪的socket
select 函数返回的 int 值是所有fd_set中可用的(符合要求的)socket个数总和。

fd_set 结构

typedef struct fd_set{
    u_int fd_count;  //socket数组大小
    SOCKET fd_array[FD_SETSIZE]; //socket句柄数组
}fd_set;

操作fd_set的几个宏

FD_ZERO(*set)  //将set初始化为空集合
FD_SET(s, *set)  //将套接字s加入集合set
FD_ISSET(s, *set)  //检查s是否set集合的一个成员，如果是返回true
FD_CLR(s, *set)  //从set集合中删除套接字s

select用法说明
例如，我们想要检查一个套接字s是否有数据需要接收，就在第二个参数可读队列中加入套接字s，调用select，
然后检查select返回值，如果非0，说明可读性队列中有值，再检查s是否还在可读队列中，如果在，就是有数据来了，马上recv。
如果s没有数据需要接收，select函数会把该套接字从可读性检查队列中删除掉，
所以我们只要检查该套接字句柄是否还存在于可读性队列中，就可以知道到底有没有数据需要接收了。

select使用流程
1 用FD_ZERO宏初始化一个套接字集合set
2 用FD_SET宏将套接字s加入到set中
3 调用select函数，等待其返回，select会检测并更新所有集合，并返回所有集合中的可用socket个数
4 若select返回值非0，用FD_ISSET宏检查s是否还在set中
5 若s还在set中，对s进行相应的I/O操作

select 目前几乎在所有的平台上支持，其良好跨平台支持也是它的一个优点。
select的一个缺点在于单个进程能够监视的文件描述符的数量存在最大限制，在 Linux 上一般为 1024，可以通过修改宏定义甚至重新编译内核的方式提升这一限制，但是这样也会造成效率的降低。

poll()

int poll (struct pollfd *fds, unsigned int nfds, int timeout);
不同与 select 使用三个位图来表示三个 fdset 的方式，poll 使用一个 pollfd 的指针实现

struct pollfd {
    int fd; /* file descriptor */
    short events; /* requested events to watch */
    short revents; /* returned events witnessed */
};

pollfd 结构包含了要监视的 event 和发生的 event，不再使用 select “参数-值”传递的方式。同时，pollfd并没有最大数量限制（但是数量过大后性能也是会下降）。
poll 本质上和 select 没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个 fd 对应的设备状态。
和 select 函数一样，poll 返回后，需要轮询 pollfd 来获取就绪的描述符。

select 和 poll 都需要在返回后，通过遍历文件描述符来获取已经就绪的 socket。
事实上，同时连接的大量客户端在一时刻可能只有很少的处于就绪状态，因此随着监视的描述符数量的增长，其效率也会线性下降。

epoll()

epoll 是在 2.6 内核中提出的，是之前的 select 和 poll 的增强版本。
相对于 select 和 poll 来说，epoll 更加灵活，没有描述符限制。epoll 使用一个文件描述符管理多个描述符，将用户关心的文件描述符的事件存放到内核的一个事件表中，这样在用户空间和内核空间的 copy 只需一次。

epoll操作过程需要三个接口，分别如下：

int epoll_create(int size); //创建一个epoll的句柄，size用来告诉内核这个监听的数目一共有多大
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);

epoll_create()

int epoll_create(int size);
创建一个 epoll 的句柄，size 用来告诉内核这个监听的数目一共有多大，这个参数不同于 select() 中的第一个参数，给出最大监听的 fd+1 的值，参数 size 并不是限制了 epoll 所能监听的描述符最大个数，只是对内核初始分配内部数据结构的一个建议。
当创建好 epoll 句柄后，它就会占用一个 fd 值，在 linux 下如果查看 /proc/进程id/fd/，是能够看到这个 fd 的，所以在使用完 epoll 后，必须调用 close() 关闭，否则可能导致 fd 被耗尽。

epoll_ctl()

int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
对指定描述符 fd 执行 op 操作。

epfd: 是 epoll_create() 的返回值。
op: 表示操作，用三个宏来表示：添加 EPOLL_CTL_ADD，删除 EPOLL_CTL_DEL，修改 EPOLL_CTL_MOD。分别添加、删除和修改对 fd 的监听事件。
fd: 是需要监听的 fd（文件描述符）
epoll_event: 是告诉内核需要监听什么事

struct epoll_event 结构如下：

struct epoll_event {
  __uint32_t events;  /* Epoll events */
  epoll_data_t data;  /* User data variable */
};

//events可以是以下几个宏的集合：
EPOLLIN ：表示对应的文件描述符可以读（包括对端SOCKET正常关闭）；
EPOLLOUT：表示对应的文件描述符可以写；
EPOLLPRI：表示对应的文件描述符有紧急的数据可读（这里应该表示有带外数据到来）；
EPOLLERR：表示对应的文件描述符发生错误；
EPOLLHUP：表示对应的文件描述符被挂断；
EPOLLET： 将EPOLL设为边缘触发(Edge Triggered)模式，这是相对于水平触发(Level Triggered)来说的。
EPOLLONESHOT：只监听一次事件，当监听完这次事件之后，如果还需要继续监听这个socket的话，需要再次把这个socket加入到EPOLL队列里

epoll_wait()

int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);
等待 epfd 上的 io 事件，最多返回 maxevents 个事件。
参数 events 用来从内核得到事件的集合，maxevents 告之内核这个 events 有多大，这个 maxevents 的值不能大于创建 epoll_create() 时的 size，参数 timeout 是超时时间（毫秒，0会立即返回，-1将不确定，也有说法说是永久阻塞）。该函数返回需要处理的事件数目，如返回0表示已超时。

水平触发(Level Trigger)和边缘触发(Edge Trigger)

epoll 对文件描述符的操作有两种模式：LT（level trigger）和ET（edge trigger）。LT 模式是默认模式，LT模式与ET模式的区别如下：

LT模式：当 epoll_wait 检测到描述符事件发生并将此事件通知应用程序，应用程序可以不立即处理该事件。下次调用epoll_wait时，会再次响应应用程序并通知此事件。
ET模式：当 epoll_wait 检测到描述符事件发生并将此事件通知应用程序，应用程序必须立即处理该事件。如果不处理，下次调用epoll_wait时，不会再次响应应用程序并通知此事件。

LT模式
LT(level triggered)是缺省的工作方式，并且同时支持block和no-block socket.在这种做法中，内核告诉你一个文件描述符是否就绪了，然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作，内核还是会继续通知你的。

ET模式
ET(edge-triggered)是高速工作方式，只支持no-block socket。在这种模式下，当描述符从未就绪变为就绪时，内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪，并且不会再为那个文件描述符发送更多的就绪通知，直到你做了某些操作导致那个文件描述符不再为就绪状态了(比如，你在发送，接收或者接收请求，或者发送接收的数据少于一定量时导致了一个EWOULDBLOCK 错误）。但是请注意，如果一直不对这个fd作IO操作(从而导致它再次变成未就绪)，内核不会发送更多的通知(only once)

ET模式在很大程度上减少了epoll事件被重复触发的次数，因此效率要比LT模式高。epoll工作在ET模式的时候，必须使用非阻塞套接口，以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。

Linux IO模式及 select、poll、epoll详解
https://segmentfault.com/a/1190000003063859

epoll相对于select/poll有哪些优化

select, poll, epoll 都是IO多路复用(IO Multiplexing)的机制。
I/O 多路复用就通过一种机制，可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作。但 select, poll, epoll本质上都是同步 I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的。

select 缺点：
1、每次调用 select，都需要把 fd 集合从用户态拷贝到内核态，这个开销在 fd 很多时会很大。
2、每次调用 select 都需要在内核遍历传递进来的所有 fd，即采用轮询的方法，效率较低，性能随着监视文件描述符数量的增长而下降。
3、select 最大的缺陷就是单个进程所打开的 FD 是有一定限制的，它由 FD_SETSIZE 设置，默认值是 1024。

epoll 是对 select 的改进，可以避免上述的三个缺点，我们先看一下 epoll 和 select 的调用接口上的不同。
select 只提供了一个函数 select
epoll提供了三个函数：
epoll_create：创建一个epoll句柄
epoll_ctl：注册要监听的事件类型
epoll_wait：等待事件的产生

对于1：epoll 的解决方案在 epoll_ctl 函数中。每次注册新的事件到 epoll 句柄中时（在 epoll_ctl 中指定 EPOLL_CTL_ADD ），会把所有的 fd 拷贝进内核，而不是在 epoll_wait 的时候重复拷贝，epoll 保证了每个fd在整个过程中只会拷贝一次。

对于2：epoll 的解决方案不像 select 那样每次都把 current 轮流加入 fd 对应的设备等待队列中，而只在 epoll_ctl 时把 current 挂一遍（这一遍必不可少）并为每个 fd 指定一个回调函数，当设备就绪，唤醒等待队列上的等待者时，就会调用这个回调函数，而这个回调函数会把就绪的 fd 加入一个就绪链表）。epoll_wait 的工作实际上就是在这个就绪链表中查看有没有就绪的fd（利用 schedule_timeout() 实现睡一会，判断一会的效果，和select实现是类似的）。

对于3：epoll 没有这个限制，它所支持的 FD 上限是最大可以打开文件的数目，这个数字一般远大于2048，举个例子，在1GB内存的机器上大约是10万左右，具体数目可以cat /proc/sys/fs/file-max察看，一般来说这个数目和系统内存关系很大。

epoll 的优点
1、select 只能监听 1024 个文件描述符（poll做了改进，监听的文件描述符个数没有限制）。epoll监视的描述符数量不受限制，它所支持的FD上限是linux最大可以打开文件的数目。
2、select/poll 的性能都会随着监视文件描述符数量的增长而下降，因为他们都是从所有 fd 集合中遍历找出就绪的 fd，也就是时间复杂度是 O(n)
epoll 的 IO 效率不会随着监视 fd 的数量的增长而下降，因为 epoll 不同于 select/poll 轮询的方式，而是通过每个 fd 定义的回调函数来实现的，只有就绪的 fd 才会执行回调函数，也就是只管活跃的连接，和连接总数无关。所以时间复杂度是 O(1)

为什么nginx性能比apache性能好（对比select和epoll）
https://segmentfault.com/q/1010000003885108

nginx性能为啥比Apache性能好（主要讲epoll）
https://blog.csdn.net/resilient/article/details/52584007

reactor 模式

进程/线程/并发

内核本身不区分进程线程

在 linux 系统中，内核本身的调度和管理并不对进程和线程进行区分，只是根据 clone 时传入的参数的不同来从概念上区分进程和线程。
Linux 中无论是进程还是线程，只要是调度单元，都通过 struct task_struct 表示。这也是为什么讲说进程和线程在内核相同的原因。

struct task_struct 有保存有关线程/进程中的一切信息，主要包括有线程/进程状态、与其他线程/进程关系、虚拟内存相关、日志相关、线程/进程限制等。该结构体定义在 include/linux/sched.h 文件中。

struct task_struct 内如何区分进程/线程？
在 struct task_struct 中并没有明确的标识（枚举类型），区分该task是线程还是进程，不过可以通过pid和tgid简单判断当前task是哪种类型。

struct task_struct {
...
    pid_t pid;
    pid_t tgid;
...
    struct *group_leader;
}

pid 用于标识不同进程和线程。
tgid 用于标识线程组id，在同一进程中的所有线程具有同一tgid。tgid值等于进程第一个线程（主线程）的pid值。接着以CLONE_THREAD来调用clone建立的线程，都具有同样的tgid。
group_leader 线程组中的主线程的task_struct指针。

进程和线程的区别

进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位。每个进程都有自己的独立内存空间，不同进程通过进程间通信来通信。由于进程比较重量，占据独立的内存，所以上下文进程间的切换开销（栈、寄存器、虚拟内存、文件句柄等）比较大，但相对比较稳定安全。

线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。线程间通信主要通过共享内存，上下文切换很快，资源开销较少，但相比进程不够稳定容易丢失数据。

进程让操作系统的并发性成为可能，而线程让进程的内部并发成为可能。

但是要注意，一个进程虽然包括多个线程，但是这些线程是共同享有进程占有的资源和地址空间的。

进程是操作系统进行资源分配的基本单位，而线程是操作系统进行调度的基本单位。

由于多个线程是共同占有所属进程的资源和地址空间的，那么就会存在一个问题：
如果多个线程要同时访问某个资源，怎么处理？
这就是线程的同步和并发控制问题。

并行(Parallel)与并发(Concurrent)的区别

并发（concurrency）和并行（parallellism）是：
解释一：并行是指两个或者多个事件在同一时刻发生；而并发是指两个或多个事件在同一时间间隔发生。
解释二：并行是在不同实体上的多个事件，并发是在同一实体上的多个事件。
解释三：并发是在一台处理器上“同时”处理多个任务，并行是在多台处理器上同时处理多个任务。如hadoop分布式集群
所以并发编程的目标是充分的利用处理器的每一个核，以达到最高的处理性能。

并发的关键是你有处理多个任务的能力，不一定要同时。
并行的关键是你有同时处理多个任务的能力。

并发是不是一个线程，并行是多个线程？
答：并发和并行都可以是很多个线程，就看这些线程能不能同时被（多个）cpu执行，如果可以就说明是并行，而并发是多个线程被（一个）cpu 轮流切换着执行。

多线程是否一定比单线程快？

那么可能有朋友会问，现在很多时候都采用多线程编程，那么是不是多线程的性能一定就由于单线程呢？

不一定，要看具体的任务以及计算机的配置。比如说：
对于单核CPU，如果是CPU密集型任务，如解压文件，多线程的性能反而不如单线程性能，因为解压文件需要一直占用CPU资源，如果采用多线程，线程切换导致的开销反而会让性能下降。

但是对于比如交互类型的任务，肯定是需要使用多线程的、

而对于多核CPU，对于解压文件来说，多线程肯定优于单线程，因为多个线程能够更加充分利用每个核的资源。

虽然多线程能够提升程序性能，但是相对于单线程来说，它的编程要复杂地多，要考虑线程安全问题。因此，在实际编程过程中，要根据实际情况具体选择。

Java并发编程：进程和线程之由来 - 海子
http://www.cnblogs.com/dolphin0520/p/3910667.html

进程间通信(IPC)方式

进程间通信(IPC，Inter-Process Communication)
http://blog.csdn.net/laviolette/article/details/39319955

1 管道(PIPE)，一种半双工通信方式，且只能在父子进程间使用
管道：连接一个读进程和一个写进程的共享文件
2 有名管道(FIFO)，可用于任意进程间通信
3 信号(Signal)，用于通知某个进程某事件已发生
4 信号量(Semaphore)，处理进程间同步互斥，低级通信
5 消息队列(Message Queue)，
6 共享内存(Shared Memory)，最快的IPC方式，可以举我项目中捕获进程和处理进程的例子
7 套接字(Socket)，可用于不同主机间的进程通信

本地的进程间通信（IPC）有很多种方式，但可以总结为下面4类：

消息传递（管道、FIFO、消息队列）
同步（互斥量、条件变量、读写锁、文件和写记录锁、信号量）
共享内存（匿名的和具名的）
远程过程调用（RPC 等）

UDS 进程间Socket

Unix Domain Socket 又叫 IPC(inter-process communication 进程间通信) socket，用于实现同一主机上的进程间通信。
socket 原本是为网络通讯设计的，通信双方在同一台机器上时，虽然也可以通过 127.0.0.1 通信，但这样还需要经过网络协议栈绕一圈。
这时，就可以用到 Unix Domain Socket，UDS 不需要经过网络协议栈，不需要打包拆包、计算校验和、维护序号和应答等，只是将应用层数据从一个进程拷贝到另一个进程。

线程间通信方式

1 互斥锁和条件变量
2 共享变量
3 信号量

协程Coroutine

协程就是用户空间下的线程。

协程就是一个不由OS内核抢占调度，而由程序管理在用户态自管理的协作式“线程”，不用线程，就减少了OS的线程数，省去了cpu线程切换的开销。
就是说协程的调度由应用来决定，不需要cpu调度参与，不需要切换上下文，完全由用户程序去控制的调度单位。

go协程

func Add(x, y int) {
    z := x + y
    fmt.Println(z)
}

func main() {
    for i:=0; i<10; i++ {
        go Add(i, i)
    }
}

如上代码，在一个函数调用前加上 go 关键字，这次调用就会在一个新的协程中并发执行。当被调用的函数返回时，这个协程也自动结束。需要注意的是，如果这个函数有返回值，那么这个返回值会被丢弃。

python协程

Python 语言也可以通过 yield/send 的方式实现协程。

死锁的四个必要条件

产生死锁的四个必要条件：
（1）互斥条件：一个资源每次只能被一个进程使用。
（2）请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3）不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。
（4）循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之
一不满足，就不会发生死锁。

守护进程

进程组与会话期

进程组(process group)：一个或多个进程的集合，每个进程都有一个进程组ID，这个ID就是进程组长的进程ID。且该进程组ID不会因组长进程的退出而受到影响。

会话期(session)：会话期是一个或多个进程组的集合。通常，一个会话开始于用户登录，终止于用户退出，在此期间该用户运行的所有进程都属于这个会话期。每个会话有唯一一个会话首进程(session leader)，会话ID为会话首进程ID

控制终端(controlling terminal) ：每一个会话可以有一个单独的控制终端，与控制终端连接的会话首进程就是控制进程(controlling process)。这时候，与当前终端交互的就是前台进程组，其他的都是后台进程组。

setsid()

进程调用 setsid()函数会：

首先请注意：只有当该进程不是一个进程组长时，才会成功创建一个新的会话期。
（1）摆脱原会话的控制。该进程变成新会话期的首进程
（2）摆脱原进程组。成为一个新进程组的组长
（3）摆脱终端控制。如果在调用 setsid() 前，该进程有控制终端，那么与该终端的联系被解除。
如果该进程是一个进程组的组长，此函数返回错误。

Linux如何创建守护进程？

创建守护进程的的一般步骤：

1、fork()创建子进程，父进程exit()退出
这是创建守护进程的第一步。由于守护进程是脱离控制终端的，因此，完成第一步后就会在Shell终端里造成程序已经运行完毕的假象。之后的所有工作都在子进程中完成，而用户在Shell终端里则可以执行其他命令，从而在形式上做到了与控制终端的脱离，在后台工作。

2、在子进程中调用 setsid() 函数创建新的会话
在调用了 fork() 函数后，子进程全盘拷贝了父进程的会话期、进程组、控制终端等，虽然父进程退出了，但会话期、进程组、控制终端等并没有改变，因此，这还不是真正意义上的独立开来，而 setsid() 函数能够使进程完全独立出来。

3、再次 fork() 一个子进程并让父进程退出。
现在，进程已经成为无终端的会话组长，但它可以重新申请打开一个控制终端，可以通过 fork() 一个子进程，该子进程不是会话首进程，该进程将不能重新打开控制终端。退出父进程。

4、在子进程中调用 chdir() 函数，让根目录 ”/” 成为子进程的工作目录
这一步也是必要的步骤。使用fork创建的子进程继承了父进程的当前工作目录。由于在进程运行中，当前目录所在的文件系统（如“/mnt/usb”）是不能卸载的，这对以后的使用会造成诸多的麻烦（比如系统由于某种原因要进入单用户模式）。因此，通常的做法是让”/“作为守护进程的当前工作目录，这样就可以避免上述的问题，当然，如有特殊需要，也可以把当前工作目录换成其他的路径，如/tmp。改变工作目录的常见函数是chdir。

5、在子进程中调用 umask() 函数，设置进程的文件权限掩码为0
文件权限掩码是指屏蔽掉文件权限中的对应位。比如，有个文件权限掩码是050，它就屏蔽了文件组拥有者的可读与可执行权限。由于使用fork函数新建的子进程继承了父进程的文件权限掩码，这就给该子进程使用文件带来了诸多的麻烦。因此，把文件权限掩码设置为0，可以大大增强该守护进程的灵活性。设置文件权限掩码的函数是umask。在这里，通常的使用方法为umask(0)。

6、在子进程中关闭任何不需要的文件描述符
同文件权限码一样，用fork函数新建的子进程会从父进程那里继承一些已经打开了的文件。这些被打开的文件可能永远不会被守护进程读写，但它们一样消耗系统资源，而且可能导致所在的文件系统无法卸下。
在上面的第二步之后，守护进程已经与所属的控制终端失去了联系。因此从终端输入的字符不可能达到守护进程，守护进程中用常规方法（如printf）输出的字符也不可能在终端上显示出来。所以，文件描述符为0、1和2 的3个文件（常说的输入、输出和报错）已经失去了存在的价值，也应被关闭。

7、守护进程退出处理
当用户需要外部停止守护进程运行时，往往会使用 kill 命令停止该守护进程。所以，守护进程中需要编码来实现 kill 发出的signal信号处理，达到进程的正常退出。

【Linux编程】守护进程(daemon)详解与创建
http://blog.csdn.net/woxiaohahaa/article/details/53487602

当前位置 : 首页 » 文章分类 : 开发 » 面试准备13-操作系统