↓Skip to main content
  1. Docs/

操作系统笔记

·45 mins· ·
Owl Dawn
Author
Owl Dawn
Table of Contents

大端小端
#

大端存储：字数据的高字节存储在低地址中（和人读的顺序相同）

小端存储：字数据的低字节存储在低地址中

所以在Socket编程中，往往需要将操作系统所用的小端存储的IP地址转换为大端存储，这样才能进行网络传输

小端模式中的存储方式为：

img

大端模式中的存储方式为：

img

判断方法：

方式一：使用强制类型转换-这种法子不错

#include <iostream>
using namespace std;
int main()
{
    int a = 0x1234;
    //由于int和char的长度不同，借助int型转换成char型，只会留下低地址的部分
    char c = (char)(a);
    if (c == 0x12)
        cout << "big endian" << endl;
    else if(c == 0x34)
        cout << "little endian" << endl;
}

方式二：巧用union联合体

#include <iostream>
using namespace std;
//union联合体的重叠式存储，endian联合体占用内存的空间为每个成员字节长度的最大值
union endian
{
    int a;
    char ch;
};
int main()
{
    endian value;
    value.a = 0x1234;
    //a和ch共用4字节的内存空间
    if (value.ch == 0x12)
        cout << "big endian"<<endl;
    else if (value.ch == 0x34)
        cout << "little endian"<<endl;
}

buffer
#

将数据缓冲下来，解决速度慢和快的交接问题；速度快的需要通过缓冲区将数据一点一点传给速度慢的区域

解决的是点操作的慢速问题，本质上就是将点操作转换成批操作

如：内存将数据向硬盘中写入，一般是缓冲到一定大小之后刷入到硬盘中

场景：

  • 向磁盘写数据时，一批一批的刷 比 来点数据就立刻刷要快很多
  • 网络传数据，相同的数据量，大量的小包会很慢

cache
#

实现数据的重复使用。速度慢的设备需要通过缓存将经常要用到的数据缓存起来，缓存下的数据可以提供高速的传输速度给速度快的设备

如：将硬盘中的数据读取出来放在内存的缓存区中，这样以后再次访问同一个资源，速度会快很多

场景：

  • 机械硬盘单词访问时间很长，所以把一些频繁访问的数据缓存在内存中
  • cpu 的计算速度相对内存块，可以将内存中的数据或者指令预读或者缓存在高缓中，充分提高 cpu 的计算效率

缺点：当数据上有更新时，cache 可能带来数据不一致的问题

虚拟地址空间
#

虚拟地址通过页表(Page Table)映射到物理内存，页表由操作系统维护并被处理器引用。在 Linux 中，内核空间是持续存在的，并且在所有进程中都映射到同样的物理内存，内核代码和数据总是可寻址，随时准备处理中断和系统调用。与此相反，用户模式地址空间的映射随进程切换的发生而不断变化，操作系统会为每个进程分配 4G 的虚拟地址空间。

内存
#

虚拟地址空间布局
#

在 32 位模式下它是一个 4GB 的内存地址块，在 Linux 系统中, 内核进程和用户进程所占的虚拟内存比例是 1:3，而 Windows 系统为2:2。实际上，Linux 运行在虚拟地址空间，并负责把系统中实际存在的远小于 4GB 的物理地址空间（物理内存）根据不同需求映射到整个 4GB 的虚拟地址空间中。

虚拟地址通过页表(Page Table)映射到物理内存，页表由操作系统维护并被处理器引用。内核空间在页表中拥有较高特权级，因此用户态程序试图访问这些页时会导致一个页错误(page fault)。在 Linux 中，内核空间是持续存在的，并且在所有进程中都映射到同样的物理内存。内核代码和数据总是可寻址，随时准备处理中断和系统调用。与此相反，用户模式地址空间的映射随进程切换的发生而不断变化。

栈

向低地址扩展，是连续的内存区域

栈的实时大小并不是固定的，程序在运行时 Linux 内核会根据入栈情况对栈区进行动态增长。它也有最大限制 RLIMIT_STACK (一般为 8M—在32位模式下的进程内存默认布局）在 Linux 中可以通过 ulimit -s 命令查看和设置栈的最大值。当程序使用的栈超过该值时, 发生栈溢出(Stack Overflow)，程序收到一个段错误(Segmentation Fault)。注意，调高栈容量可能会增加内存开销和启动时间。

内存映射段

mmap 其实和堆一样，也是动态分配内存的。

在 Linux 中，若通过 malloc() 请求一大块内存，C运行库将创建一个匿名内存映射（该映射没有对应的文件, 可用于存放程序数据），而不使用堆内存。”大块” 意味着比阈值 MMAP_THRESHOLD 还大，缺省为128KB，可通过 mallopt() 调整。

该区域用于映射可执行文件用到的动态链接库。在Linux 2.4版本中，若可执行文件依赖共享库，则系统会为这些动态库在从0x40000000开始的地址分配相应空间，并在程序装载时将其载入到该空间。在Linux 2.6内核中，共享库的起始地址被往上移动至更靠近栈区的位置。

从进程地址空间的布局可以看到，在有共享库的情况下，留给堆的可用空间还有两处：一处是从.bss段到0x40000000，约不到1GB的空间；另一处是从共享库到栈之间的空间，约不到2GB。这两块空间大小取决于栈、共享库的大小和数量。这样来看，是否应用程序可申请的最大堆空间只有2GB？事实上，这与Linux内核版本有关。在上面给出的进程地址空间经典布局图中，共享库的装载地址为0x40000000，这实际上是Linux kernel 2.6版本之前的情况了，在2.6版本里，共享库的装载地址已经被挪到靠近栈的位置，即位于0xBFxxxxxx附近，因此，此时的堆范围就不会被共享库分割成2个“碎片”，故kernel 2.6的32位Linux系统中，malloc申请的最大内存理论值在2.9GB左右。

堆

向高地址扩展，是不连续的内存区域

分配的堆内存是经过字节对齐的空间，以适合原子操作。堆管理器通过链表管理每个申请的内存，由于堆申请和释放是无序的，最终会产生内存碎片。堆内存一般由应用程序分配释放，回收的内存可供重新使用。若程序员不释放，程序结束时操作系统可能会自动回收。

堆的末端由break指针标识，当堆管理器需要更多内存时，可通过系统调用 brk() 和 sbrk() 来移动break指针以扩张堆，一般由系统自动调用。

使用堆时经常出现两种问题：

  1. 释放或改写仍在使用的内存(“内存破坏”)；
  2. 未释放不再使用的内存(“内存泄漏”)。

当释放次数少于申请次数时，可能已造成内存泄漏。泄漏的内存往往比忘记释放的数据结构更大，因为所分配的内存通常会圆整为下个大于申请数量的2的幂次(如申请212B，会圆整为256B)。

==堆和栈的区别==

  • 管理方式

    栈由编译器自动管理；堆由程序员控制，使用方便，但容易产生内存泄露

  • 生长方向

    栈向低地址方向增长，是连续的内存区域；堆向高地址方向增长，是不连续的内存区域。系统使用链表来存储空闲的内存地址，而且由低地址向高地址遍历

  • 空间大小

    栈顶地址和最大容量由系统预先规定，32位模式下进程默认为8M；堆大小受限于计算机系统中有效虚拟内存，32位 linux 中可达2.9G

  • 存储内容

    栈在函数调用时，首先压入主调函数中下条指令(函数调用语句的下条可执行语句)的地址，然后是函数实参，然后是被调函数的局部变量。本次调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的指令地址，程序由该点继续运行下条可执行语句。

    堆通常在头部用一个字节存放其大小，堆用于存储生存期与函数调用无关的数据，具体内容由程序员安排。

  • 分配方式

    栈可静态分配或动态分配。静态分配由编译器完成，如局部变量分配。动态分配由 alloca 函数在栈上申请空间，用完后自动释放。堆只能动态分配且手动释放。

  • 分配效率

    栈由计算机底层提供支持，分配专门的寄存器存放栈地址，压栈出栈由专门的指令执行，效率较高。堆由函数库提供，效率比栈低得多。

  • 碎片问题

    栈不会存在碎片问题，栈是先进先出的队列，内存弹出栈之前，其上面的栈内容已弹出。而堆的频繁申请释放操作会造成堆内存空间的不连续，造成大量碎片，效率低。

==内存中不同变量布局==

  • 不同的局部变量保存在栈，动态申请的局部变量保存在堆
  • 初始化为非 0 的全局变量 & 静态全局变量 & 静态局部变量保存在 .data 段，未初始化及初始化为 0 的全局变量 & 静态全局变量 & 静态局部变量保存在 .bss 段
  • 全局常量保存在 .rodata 段，而局部常量保存在栈
  • 字符串常量保存在 .rodata 段，但字符串指针保存在栈，字符数组也保存在栈

==.data 段和 .bss 段有什么区别==

bss 段的全局变量只占运行时的内存空间，而不占文件空间，.bss 段不占据 ELF 目标文件的空间，即不占据实际的磁盘空间，只在段表（Section Header Table）中记录起始地址和大小，在符号表（.symtab段）中记录变量符号，仅当 ELF 目标文件加载运行时，才分配空间以及初始化。；而 data 段的全局变量既占文件空间，又占用运行时的内存空间。

==普通局部变量和 static 局部变量的区别==

  • 存储方式

    普通变量保存在栈或堆上，static 局部变量保存在 .data 段

  • 生命周期

    static 局部变量在程序的整个生命周期中存在，也就是说：普通局部变量每次进入函数都要初始化一次，static 局部变量只被初始化一次，即第一次进入函数时初始化，以后每次进入函数都依据上一次的结果值。但是，虽然 static 局部变量在函数调用结束后仍然存在，但其他函数是不能直接引用它的。

==普通函数和 static 函数的区别==

作用域不同，static 函数的作用域是仅本文件有效。一般，对于只在当前源文件中使用的函数，应该在当前源文件中声明和定义为 static 函数，而对于可在当前源文件以外使用的函数，应该在一个头文件中声明，要使用这些函数的源文件中包含此头文件就可以调用此函数。

==const==

常量，保护被修饰的东西。定义常量或引用时必须初始化

定义常量。

定义函数参数

定义函数。函数返回值（即指针）的内容不能被修改，该返回值只能被赋给加 const 修饰的同类型指针

内存碎片
#

  • 内部碎片

    由于采用固定大小的内存分区，当一个进程不能完全使用分给它的固定内存区域时就产生了内部碎片

  • 外部碎片

    由于某些未分配的连续内存区域太小，以至于不能满足任意进程的内存分配请求，从而不能被进程利用的内存区域

现在普遍采用段页式内存分配方式，将进程的内存区域分为不同的段，然后将每一段有多个固定大小的页组成。通过页表机制，使段内的页可以不必连续处于同一内存区域，从而减少了外部碎片。然而同一页内仍然可能存在少量的内部碎片，只是一页的内存空间较小，使内存碎片也较少

段页式
#

将物理内存划分为固定大小的块，成为帧（页框）；将逻辑内存也分为同样大小的块，称为页，当需要执行进程时，该进程的页会被调入到可用的内存帧中

页表起始地址存放在页表基址寄存器(PTBR:Page Table Base Register)中

页表项的组成：

  • 帧号
  • 页表项标志：
    • 存在位(resident bit):对于一个页面是否有物理页与其对应，如果有就为1
    • 修改位(dirty bit)：判断页面 是否被修改过
    • 引用位(clock/reference bit)：页面是否有过对它的引用

页大小是由硬件决定的，通常为 2 的幂。选择页的大小为 2 的幂可以方便地将逻辑地址转换为页号和页偏移。如果逻辑地址空间为 2^m^，且页大小为 2^n^，那么逻辑地址的高 m-n 位表示页号，而低 n 位表示页偏移。

采用分页内存管理有一个不可避免的问题：用户视角的内存和实际物理内存的分离。用户通常更愿意将内存看做是一组不同长度的段的集合，这些段之间并没有一定的顺序。分段就是支持这种用户视角的内容管理方案，逻辑空间由一组段组成，每个段有自己的名称和长度。在段式管理策略中，地址指定了段号和段内偏移，因此用户通过两个量来指定地址：段号+偏移

每个进程通过维护一个段表来管理段式内存，系统也会维护一个内存中的空闲段列表，如上图所示，每个段表必须给出相应的段在内存中的起始地址，还必须指明段的长度，以确保不会使用无效的地址。

对于用户而言，当用户发出一个逻辑地址，用户希望访问到特定程序段的内存空间，而对于计算机而言，则希望用户发出的逻辑可以通过 MMU 转换成页框号和页内偏移量，从而直接去访问真实的内存空间。

为了解决这一问题引入了虚拟内存（就是通过一张段表完成地址映射转换）：简单的说就是用户发出访问程序段的逻辑地址 < 段号，段内偏移量 >，通过对这一逻辑地址的运算将其转换为访问页的虚拟地址 < 页号，页内偏移量 > ，再由 MMU 将其转换为内存的物理地址 < 页框号，页内偏移量 >。通过这种方式，用户访问的就是虚拟内存，经过两次地址映射后，变成真实的物理地址。

**地址越界：**利用段表寄存器中的段表长度与逻辑地址中的段号比较，若段号大于段表长度则产生越界中断；再利用段表项中的段长和逻辑地址中的段内位移进行比较，若段内位移大于段长，也会产生越界中断。

快表
#

快表，又称联想寄存器(TLB)，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，主存中的页表也常称为慢表，配有快表的地址变换机构如图4所示。

CPU 内部有个 TLB，缓存近期访问的页帧转换表项。CPU给出逻辑地址后，由硬件进行地址转换并将页号送入高速缓存寄存器，并将此页号与快表中的所有页号进行比较

  • TLB使用相关存储器(关联内存)实现。
  • 如果TLB命中，物理页号可以被很快获取。只需要一次访存
  • 如果TLB未命中，对应的表项被更新到TLB中。需要两次访存

由局部性原理，一般快表的命中率可以达到90%以上

多级页表
#
  • 因为原来只有一个页表项，即使不存在的映射也会在内存中保留，当我们使用多级页表时，当根据 p1 在一级页表中找不到对应的二级页表的基址时，整个二级页表都不用存在了，这样省空间。

将页表(页表号)分成多级，每一级作为每一级页表的偏移找到下一级页表的起始地址。第一级页表的起始地址写在固定的寄存器 CR3 中，加上第一级页号作为索引找到第二级页表起始地址。再加上第二级页表偏移得到实际页帧号，再加上偏移 offset 得到实际页帧。

虚拟内存
#

将常用的数据和代码放在内存上，不常用的数据和代码放在磁盘上。在有限的容量中，以更小的页粒度为单位装入更多更大的程序。

基本过程：

  • 装入程序时，不必将其全部装入内存，只需要将当前需要执行的部分页面或段装入内存中，就可以让程序开始执行。
  • 程序执行过程中，如果需要执行的指令或访问的数据尚未在内存（发生缺页异常或缺段异常），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序。
  • 操作系统将内存中暂时不用的页面或段调出保存在外存上，从而腾出更多空闲空间存放将要装入的程序以及将要调入的页面或段

页表项中相关位

  • 驻留位：表示该页是在内存还是外存，如果该位等于1，表示该页位于内存中，即该页表项是有效的。如果该位为0，则表示该页还是在外存中。
  • 保护位：表示允许该页做何种类型的访问，如只读、可读写
  • 修改位：表明该页在内存中只是否被修改过
  • 访问位：该页最近是否被访问过，访问过置为1，没访问置为0；页面置换尽量将当前没有被访问过的置换出去。

缺页中断处理
#

  • 当CPU根据逻辑地址的页码访问页表时，发现该页码对应的页表项根本不存在，就是其驻留位为0，然后引发缺页异常中断。
  • 如果此时物理内存中还有空间，则将硬盘中应用程序所需要的这个数据或代码以页的形式读到物理内存，此时修改页表，虚拟地址对应的页表项设置为页码值，然后将驻留位设置为1，重新执行这条指令。
  • 如果此时物理内存中没有空间了，则使用页面置换算法将现有的物理内存置换出去，如果需要置换出去的数据被修改过，那么就要把该数据重新写回到磁盘，如果没有被访问过，则直接将其清空，因为此时物理内存中和磁盘中的数据是一样的。 至于置换哪些地址，则根据访问位有关，如果没有被访问过，则置换出去这些。

页面置换算法
#

作用

缺页中断发生时，需要调入新的页面而内存已满，选择内存当中哪个物理页面被置换。

减少页面的换入换出次数(即缺页中断的次数)

页面锁定(frame locking):用于描述必须常驻内存的操作系统的关键部分或时间关键的应用进程。实现方法是在页表中添加锁定标志位(lock bit)

  • 最优页面置换算法：计算页下一次访问需要等待多久，选择时间最长的（实际系统无法实现）

  • 先进先出：维持链表（队列）。性能较差，可能淘汰经常访问的页面

  • LRU算法（最近最久未使用）需要记录每个页面使用时间的先后顺序

    • 维护一个页面链表，刚使用的页作为链表首，最久未使用为链表尾，每次访问从链表中取出放在链表首，缺页发生时淘汰链表尾
    • 设置一个活动页面栈，访问某页时将页号压入栈，然后考察栈内是否有此页面相同页号，有则抽出，置换时则选择栈底页面

  • 时钟页面置换（CLOCK算法）（最近未用算法 NRU）

    • 需要用到页表项中的访问位，当一个页面被装入内存时，把该位初始化为0。然后如果这个页面被访问(读/写)，则把该位置为1。
    • 把各个页面组织成环形链表(类似时钟表面)，把指针指向最老的页面(最先进来)
    • 当发生一个缺页中断时，考察指针所指向的最老页面，若它的访问位为0，立即淘汰；若访问位为1，则把该位置为0.然后指针往下移动一格，如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格。

  • 二次机会法

    使用 dirty bit 来设定操作系统是否对该地址进行写 如果 dirty bit 没有被置位，则说明内存中该地址和磁盘上存储的信息是一样的，就不需要从内存写到磁盘中了。

  • 最不常用算法（LFU）

    淘汰访问次数最少的页面，对每个页面设置一个访问计数器0

    使用计数器，开销大，链表长的时候查找时间长

    存在某页最开始访问次数多，后面不访问（可定期把次数寄存器右移一位）

全局页面置换算法
#

  • 工作集页置换算法

  • 缺页率页面置换算法

    常驻集大小可变，例如每个进程刚开始运行时，先根据程序大小分配一定数目物理页面，然后再进程运行过程中，动态调整常驻集大小。

    若缺页率较高，则增加工作集分配更多的物理页面，过低则减少工作集，使缺页率保持在一个合理范围

分段
#

分段管理方式的提出则是考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。

每个进程都有一张逻辑空间与内存空间映射的段表，其中每一个段表项对应进程的一个段，段表项记录该段在内存中的起始地址和段的长度。

在配置了段表后，执行中的进程可通过查找段表，找到每个段所对应的内存区。

页式存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享。

异常和中断
#

中断
#

本质上来讲，中断是一种电信号，当设备有某种事件发生时，它就会产生中断，通过总线把电信号发送给中断控制器。如果中断的线是激活的，中断控制器就把电信号发送给处理器的某个特定引脚。处理器于是立即停止自己正在做的事，跳到中断处理程序的入口点，进行中断处理。

  • 同步中断：

    当指令执行时由 cpu 控制单元产生，（之所以成为同步，是因为只有在一条指令终止执行后 cpu 才会发出中断）。也称为异常

  • 异步中断

    有其他硬件设备依照 cpu 时钟信号随机产生

  • 共同点

    如果 cpu 当前不处于核心态，则发起从用户态到核心态的切换，接下来在内核中执行一个专门的例程

异常
#

指 cpu 内部出现的中断，即在 cpu 执行特定指令时出现的非法情况，同时异常也称为同步中断，只有在一条指令执行后在会发出中断，不可能在指令执行期间发生异常

  • trap 陷入（陷阱）。保存的 EIP 指向触发异常的那条指令的下一条指令，异常返回不会再执行那条指令
  • fault 错误。保存的 EIP 指向触发异常的那条指令。异常返回时会重新执行那条指令
  • abort 终止

前两者可恢复，abort 不可恢复

产生原因

  • 程序错误产生（如除数为 0）
  • 内核必须处理的异常条件（缺页）

进程与线程
#

进程
#

进程就是出于执行期的程序以及相关资源的总称。是资源分配的最小单位，一个进程是一个运行着的程序段，一个进程主要包括在内存中申请的空间，代码（加载的程序，包括代码段，数据段，BSS）、堆、栈以及内容提供的内核进程信息结构 task_struct、打开的文件、上下文信息以及挂起的信息等。

task_struct 描述一个正在执行的程序：打开的文件、进程的地址空间、挂起的信号、进程的状态等

写时拷贝
#

在需要写入的时候，数据才会被复制。资源的写入只有在需要写入的时候才进行，在此之前，只是以只读的方式共享。

在页根本不会被写入的情况下（如 fork() 后立即调用 exec()）他们就无需复制了

fork() 的实际开销就是复制父进程的页表以及给子进程创建唯一的进程描述符（task_struct）

父子进程共享 fork 之前打开的文件描述符，并且共享打开文件的读写偏移量。

vfork
#

不拷贝父进程的页表项

子进程作为父进程的一个单独线程在他的地址空间里运行，父进程被阻塞，直到子进程退出或执行exec()。子进程不能向地址空间写入。

现在有了写时拷贝，vfork 的好处仅限于不拷贝父进程的页表项

进程调度
#

Linux 调度器以模块方式提供，模块化结构被称为调度器类，允许多种不同的可动态添加的调度算法并行

进程调度的主要入口点是函数 schedule() ，它找一个最高优先级的调度类，然后问后者谁才是下一个运行的进程。

nice 值映射到绝对时间

相同 nice 值的进程，如果是高 nice 值就会发生频繁的切换，而给定高 nice 值的进程往往是后台进程且多是计算密集型进程。

对于相对 nice 值，比如赋予 18 19 的nice值10ms 和5ms的时间，前者相比后者获得了两倍的处理器时间

CFS 完全公平调度

是一个针对普通进程的调度类

其抢占时机取决于新的运行程序占用了多少处理器的使用比，如果消耗的使用比 比当前进程小，则新进程立刻投入运行，抢占当前进程，否则推迟其运行

每个进程能获得 1/n 的处理器时间，n 为可运行进程的数量。CFS 允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程。nice 值作为进程获得的处理器运行比的权重。

绝对的 nice 值不再影响调度决策，只有相对值才会影响处理器时间的分配比例

目标延迟：每个可运行任务应当运行一次的时间间隔

每个进程由获得的时间片底线，被称为最小粒度

CFS 使用红黑树来组织可运行进程队列，vruntime 变量存放进程的虚拟运行时间（该运行时间的计算是经过了所有可运行进程的标准化（加权）），系统周期性调用 update_curr() ，无论进程处于可运行状态还是不可运行状态，准确地测量给定进程的运行时间。

当 CFS 需要选择下一个运行进程时，挑一个最小的 vruntime 的进程。选择算法可以简单总结为“运行 rbtree 树中最左边叶子节点所代表的进程”。删除动作发生在进程堵塞（变为不可运行）或者终止（结束运行）时。

休眠（被阻塞）进程处于一个特殊的不可执行状态，内核操作：进程把自己标记为休眠状态，从可执行红黑树中移除，放入等待队列（链表实现），然后调用 schedule 选择和执行一个其他进程。唤醒过程：进程被设置为可执行状态，然后再从等待队列中移到红黑树中

上下文切换
#

中断会导致 CPU 从执行当前任务改变到执行内核程序。系统需要保存当前运行在 CPU 上的进程的上下文，以便在处理后能够恢复上下文，即先挂起进程，再恢复进程。

当进行上下文切换时，内核会将旧进程状态保存在其 PCB 中，然后加载经调度而要执行的新进程的上下文。上下文切换的时间是纯粹的开销，因为在切换时系统并没有做任何有用工作。上下文切换的速度因机器不同而有所不同，它依赖于内存速度、必须复制的寄存器数量、是否有特殊指令（如加载或存储所有寄存器的单个指令)。

僵尸进程、孤儿进程
#

僵尸进程：

  • 产生原因

    一个进程使用 fork 创建子进程，如果子进程退出而父进程没有调用 wait() 或者 waitpid() 获取子进程信息，那么子进程的描述符依然保存在系统中

  • 危害：

    僵尸进程已经放弃了几乎所有的内存空间，没有任何可执行代码，不可以被调度，仅仅在进程列表中保留一个位置。除此之外不占有任何内存空间

  • 处理方法

    • kill 父进程，僵尸进程成为孤儿进程，交给 1 号进程 init，init 始终会负责清理僵尸进程（init 会自动 wait 其子进程）
    • ps aux | grep Z kill -s SIGCHLD pid 注意僵尸进程已经死了，无法被杀死
    • 通过 signal(SIGCHLD, SIG_IGN) 通知内核对子进程的结束不关心，由内核回收。表示父进程忽略SIGCHLD信号，该信号是子进程退出的时候向父进程发送的。

孤儿进程：

  • 产生原因：

    如果父进程退出而他的一个或多个子进程还在运行，这些一进城就被成为孤儿进程，最终被 init 进程（pid 为 1）所收养。

  • 没有危害

线程
#

是程序执行的最小单位

是进程中活动的对象，对 linux 来说，线程是一种特殊的进程，把所有的线程都当做进程来实现

==线程仅仅被视为一个与其他进程共享某些资源的进程，每一个线程都拥有唯一隶属于自己的 task_struct==

task_struct 描述一个正在执行的程序：打开的文件、进程的地址空间、挂起的信号、进程的状态等信息

私有资源

  • 线程上下文

    • 线程 ID

    • 优先级

    • 栈区

      线程运行的本质就是函数运行，函数运行时信息是保存在栈帧中的，因此每个线程都有自己独立的、私有的栈区。

    • 寄存区

      函数运行时需要额外的寄存器来保存一些信息，像部分局部变量之类，这些寄存器也是线程私有的，一个线程不可能访问到另一个线程的这类寄存器信息。

    • 线程局部存储TLS

      线程局部存储可以让你使用一个独属于线程的全局变量。也就是说，虽然该变量可以被所有线程访问，但该变量在每个线程中都有一个副本，一个线程对该变量的修改不会影响到其它线程。

    • 信号屏蔽码

      所以线程的信号屏蔽码应该由线程自己管理。但所有的线程都 共享同样的信号处理器。

共享资源

  • 代码区

    编译后可执行的机器指令。这就意味着程序中的任何一个函数都可以放到线程中去执行，不存在某个函数只能被特定线程执行的情况。

  • 数据区

    data 段、bss 段

  • 堆区

  • 栈区

    线程的栈区没有严格的隔离机制来保护，因此如果一个线程能拿到来自另一个线程栈帧上的指针，那么该线程就可以改变另一个线程的栈区

  • 动态链接库

  • 文件

为什么有线程
#

内核线程
#

  • 只运行在内核态，只能由其他内核线程创建，不受用户态上下文拖累
  • 和用户进程一样都有 do_fork() 创建
  • 没有用户空间，

同步和互斥
#

互斥：

指散布在不同任务之间的若干程序片段，当某个任务运行其中一个程序片段时，其他任务就不能运行他们之中的任意程序片段

最基本的场景就是对资源的同时写，为了保持资源的一致性，往往需要进行互斥访问

同步：

散布在不同任务之间的若干程序片段，它们的运行必须按照规定的某种先后次序来运行。

最基本的场景就是任务之间的依赖，比如 A 任务的运行依赖于 B 任务产生的数据

线程同步方式
#

对多线程来说，同步指的是在一定时间内只允许某一个线程访问某个资源，而在此时间内，不允许其他线程访问该资源

临界区

事件

互斥锁

特殊的全局变量，拥有lock和unlock两种状态，unlock的互斥锁可以由某个线程获得，一旦获得，这个互斥锁会锁上变成lock状态，此后只有该线程由权力打开该锁，其他线程想要获得互斥锁，必须得到互斥锁再次被打开之后

在同时需要两个互斥量的时候，总是让他们以相同顺序加锁，可避免死锁

  • 递归

    允许==同一线程==在互斥量解锁之前对该互斥量进行多次加锁，维护锁的计数，解锁次数和加锁次数不相同的情况下不会释放锁

  • 非递归

死锁的产生条件

  • 互斥条件：一个资源只能被一个进程使用
  • 请求与保持条件：一个进程因请求资源等待时，对已获得的资源保持不放
  • 不剥夺条件：进程已获得资源，在未使用完之前，不能强行剥夺
  • 循环等待条件：进程之间形成一种头尾相接的循环等待资源关系

读写锁

可以多个线程同时读，但是不能多个线程同时写

最适用于对数据结构的读操作次数多于写操作次数的场合

  • 强读同步

    总是给读者更高的优先权，只要写者没有进行写操作，读者就可以获得访问权限

  • 强写同步

    总是给写者更高的优先权，读者只能等到所有正在等待或者执行的写者完成后才能进行读

信号量

互斥锁只允许一个线程进入临界区，而信号量允许多个线程进入临界区

条件变量

当线程在等待满足某些条件时使线程进入睡眠状态，一旦条件满足，就换线因等待满足特定条件而睡眠的线程

条件变量通过运行线程阻塞和等待另一个线程发送信号的方法弥补互斥锁的不足，常常和互斥锁一起使用，使用时，条件变量被用来阻塞一个线程，当条件不满足时，线程往往解开响应的互斥锁并等待条件发生变化，一旦其他的某个线程改变了条件变量，它将通知响应的条件变量换线一个或多个正被此条件变量阻塞的线程，这些线程将重新锁定互斥锁并且重新测试条件是否满足

  • 可以一次唤醒所有的等待者（信号量不能）
  • 可能存在唤醒丢失，在等待条件变量之前，条件变量就被唤醒激活（信号量不会）

屏障

允许每个线程等待，直到所有的合作线程都达到某个点，然后从该点继续执行

pthread_join就是一种屏障

pthread_barrier_init();
pthread_barrier_destroy
pthread_barrier_wait
  • 可以通过条件变量来设置屏障，使用一个静态变量，当一个线程到达屏障则减一，让每个线程睡到最后一个线程到为止（信号量不可以）当每个线程到达屏障，检测静态变量是否为0，是则唤醒所有线程

多线程与线程安全
#

线程安全， 是指变量或方法( 这些变量或方法是多线程共享的) 可以在多线程的环境下被安全有效的访问。

对于线程需要弄清以下两点：

  • 线程之间有无先后访问顺序（线程依赖关系）
  • 多个线程共享访问同一变量（同步互斥问题）

进程间通信
#

管道
# 

#include <unistd.h>
int pipe(int fd[2]);  // fd[0]为读而打开， fd[1]为写而打开

只能用于具有亲缘关系的进程之间通信（==父子进程或者兄弟进程==）

通常由一个进程创建，在调用fork后管道就能在父进程和子进程之间使用

是一个单工（半双工）的通信模式，具有固定的读写端

每次使用都需要创建管道对象。

有名管道
# 

#include <sys/stat.h>
int mkfifo(const char* path, mode_t mode);
int mkfifoat(int fd, const char* path, mode_t mode);

可以在互不相关的进程之间实现通信。

严格遵循先进先出的规则，对管道及FIFO的读总是从开始处返回数据，对它们的写则把数据添加到末尾。且不支持如 lseek（）等文件定位操作。

与管道同样为阻塞性读写

信号
#

信号量
#

可以视为a counter + a mutex + a wait queue

P(sv)：如果sv的值大于零，就给它减1；如果它的值为零，就挂起该进程的执行

V(sv)：如果有其他进程因等待sv而被挂起，就让它恢复运行，如果没有进程因等待sv而挂起，就给它加1.

XSI信号量：

无论何时创建IPC结构（msgget消息队列、semget信号量、shmget共享内存）都应指定一个键（key_t）

#include <sys/ipc.h>
key_t ftok(const char* path, int fd); // 由一个路径名和一个项目id产生一个键

POSIX信号量：

  • 命名
  • 未命名

消息队列
#

共享内存
#

最快的一种IPC，不需要再客户进程和服务器进程中间复制

与内存映射不同的是：没有相关文件，共享存储段是内存的匿名段

#include <sys/shm.h>
int shmget(key_t key, size_t size, int flag);     // 获得一个共享存储标识符，错误返回-1
// size通常向上取为系统页长的整数倍
int shmctl(int shmid, int cmd, struct shmid_ds* buf);  // 成功返回0，失败-1
void* shmat(int shmid, const void* addr, int flag); // addr为0，由内核选择可用地址
int shmdt(const void* addr);    //成功使shmid_ds结构中的计数器-1，并不删除标识符以及数据结构

内存映射
#

将给定的文件映射到一个存储区域中

#include <sys/mman.h>
void* mmap(void* addr, size_t len, int prot, int flag, int fd, off_t off);

addr 指定映射存储区起始地址，为 0 则由系统指定

fd 指定被映射文件，映射前必须先打开文件

prot 指定映射存储区保护要求（可读、可写、可执行、不可访问）

flag MAP_SHARED存储操作相当于对文件的 write MAP_PRIVATE 存储操作导致创建该映射文件的一个私有副本，任何修改只影响文件副本

int msync(void* addr, size_t, len, int flags);  // 将该页冲洗到被映射的文件中
int munmao(void* addr, size_t len); // 解除映射区，进程终止也会自动解除，关闭文件描述符不会解除
// 不影响被映射的对象，对MAP_PRIVATE的修改会被丢弃

套接字
#

何时多线程何时多进程
#

  • 一个进程中的所有线程都必须运行相同的可执行程序（最多能做的是运行相同可执行程序的不同部分）

    而一个子进程可以运行完全不同的可执行程序

  • 同一个进程的多个线程共享同一块虚拟内存和其他资源，因而一个线程出错可能会影响到同一个进程中的其他线程。而多进程环境下，每个进程都拥有自己的独立资源，一个进程出错不会影响其他进程

协程
#

用户态的轻量级线程，线程内部调度的基本单位。一个线程可以拥有多个协程

切换情况：先将寄存器上下文和栈保存，等切换回来在进行恢复，不会陷入内核态

同一时间只能执行一个协程，而其他协程处于休眠状态，适合对任务的分时处理

**开销：**直接操作栈，基本没有内核切换的开销，可以不加锁的访问全局变量，上下文切换非常快

通信方式：共享内存、消息队列

锁
#

自旋锁
#

自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁

自旋锁使用者一般保持锁时间非常短，因此选择自旋而不是睡眠是非常必要的，自旋锁的效率远高于互斥锁。

在单核 CPU 上，需要抢占式的调度器（即通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU

互斥锁
#

与自旋锁区别：互斥锁其实开销高于自旋锁，但是保持临界区的大小不会造成新的开销，自旋锁是死循环检测，其实开销低，但随着持锁时间，开销是线性增长

读写锁
#

  • 当有人拿到写锁的时候，任何人都不能再拿到读锁或写锁

  • 当有人拿到读锁的时候，其他人也可以拿到读锁，但不能有人拿到写锁去修改临界区

  • 已经加了读锁时，如有人尝试拿写锁，需要尽快得到满足，避免写锁饥饿

顺序锁
#

与读写锁类似，写的优先级高于读操作，在读者正在读的时候也允许写操作的运行，写操作不会等待，除非另一个写操作正在进行。如果发生了写操作，正在进行的读操作必须重新开始，保证了数据的完整性

互斥访问的资源不可以是指针，写操作可能导致指针失效，读操作对失效的指针进行操作将发生错误

比读写锁更加高效，但是不能完全替代读写锁

RCU
#

Read-Copy Update，一种同步机制，对读写锁的优化

  • 随时可以拿到读锁，对临界区的读操作随时可以满足
  • 某时刻只能有一个人拿到写锁，多个写锁互斥

寄存器
#

数据寄存器
#

保存操作数和运算结果等信息，节省读取操作数所需占用总线和访问存储器的时间

EAX 累加器，可用于乘除、输入、输出等操作，使用频率很高

EBX 基地址寄存器：作为存储器指针来使用

ECX：计数寄存器：在循环和字符串操作时，控制循环次数；在位操作中，指明移位的位数

EDX：数据寄存器：在乘除运算时，可作为默认的操作数参与运算，也可存放 I/O 的端口地址

变址寄存器
#

ESI、EDI：主要用于存放存储单元在段内的偏移量

指针寄存器
#

EBP：基指针寄存器，可直接存取堆栈中的数据

ESP：栈指针寄存器，只可以访问栈顶

段寄存器
#

根据内存分段的管理模式设置，内存单元的物理地址由段寄存器的值和一个偏移量组合而成，这样可用两个较少位数的值组合成一个可访问较大物理空间的内存地址。

指令指针寄存器
#

EIP：存放下次将要执行的指令在代码段的偏移量

标志寄存器
#

linux
#

程序放在后台
#

在命令后面加上 ./test &

在前台执行的命令，放到后台执行：ctrl+z bg % 1

在退出shell时继续运行：nohup ./test &

查看当前终端所有任务PID，状态 jobs –l

查看当前所有进程：ps –aux

杀死一个进程：前台ctrl+c，后台：kill PID

将后台中的命令调至前台继续运行：fg %xxnumber

ctrl + c 发送 SIGINT 信号，Ctrl + z 发送 SIGSTOP 信号，进程只是被停止，再发送 SIGCONT 信号，进程继续运行

限制进程 cpu 占用率
#

打包和压缩
#

tar
#

tar ctxv[f device]] file-list

  • 选项第一个字母指定要执行的操作，是必需的

    c :Creat创建新磁带，从头开始写，以前存在磁带上的数据被覆盖

    t :Table列表，磁带上的文件名列表，当不指定文件名时，将列出所有文件

    x :eXtract抽取，从磁带中抽取指定的文件。当不指定文件名时，抽取所有文件

  • 除功能字母外的其它选项

    v :Verbose冗长。每处理一个文件，就打印出文件的文件名，并在该名前冠以功能字母

    f :File。指定设备文件名

    z :采用压缩格式(gzip算法)

    j :采用压缩格式(bzip2算法)

tar cvf my.tar *.[ch] makefile
#注意指定文件名(my.tar)不要忘记写！！！

gzip、gunzip
#

bzip
#

查看文件夹大小
#

du 和 df 的区别
#

  • du，disk usage 通过搜索文件来计算每个文件的大小，然后累加，能看到的是当前存在未被删除的。
  • df，disk free 通过文件系统来快速获取空间大小信息。能够看到已经删除但是程序占用还未释放的文件

du -s 文件夹 查看某一文件夹大小

du [-k/m] 文件夹 查看某文件夹以及各子目录大小

du -h 查看当前目录以及各子目录大小

查找文件
#

find
#

按文件名查找

find / -name a.cpp

按特征查找

find / -size -1000k 查找小于 100kb 的文件

三剑客
#

  • grep 更适合单纯的查找或匹配文本
  • sed 更适合编辑匹配到的文本
  • awk 更适合格式化文本，对文本进行较复杂格式处理

sed
#

sed 可依照脚本的指令来处理、编辑文本文件。

Sed 主要用来自动编辑一个或多个文件、简化对文件的反复操作、编写转换程序等。

  • sed ‘命令’ ‘文件名列表’
  • sed -e ‘命令1’ -e ‘命令2’ -e ‘命令3’ ‘文件名列表’
  • sed -f ‘命令文件’ ‘文件名列表’

动作

参数
-a 新增 a 的后面可以接字串，而这些字串会在新的一行出现(目前的下一行)
-c 取代 c 的后面可以接字串，这些字串可以取代 n1,n2 之间的行
-d 删除 后面通常不接任何咚咚
-i 插入 i 的后面可以接字串，而这些字串会在新的一行出现(目前的上一行)
-p 打印 亦即将某个选择的数据印出。通常 p 会与参数 sed -n 一起运行
-s 取代 可以直接进行取代的工作。通常这个 s 的动作可以搭配正规表示法 
#将日期格式“月-日-年”改为“年.月.日”
#如04-21-1997替换为1997.04.21
sed -e 's/\([0-9][0-9]\)-\([0-9][0-9]\)-\([0-9][0-9]*\)/\3.\1.\2/g'

awk
#

awk '{pattern + action}' {filenames}

pattern 表示 awk 在数据中查找的内容，action 是在找到匹配内容时所执行的一系列命令。{} 不需要在程序中始终出现，但他们用于根据特定的模式对一系列指令进行分组

最基本的功能是在文件或者字符串中基于指定规则浏览和抽取信息，awk 抽取信息后才能进行其他文本操作完整的 awk 脚本通常用来格式化文本文件中的信息

通常以文件的一行为处理单位。awk 每接收文件的一行，然后执行相应的命令来处理文本

BEGIN、END

再开始处理输入文件之前执行 BEGIN 模块

处理了输入文件中的所有行之后执行 END 模块。通常 END 块用于执行最终计算或打印应该出现在输出流结尾的摘要信息

参数

参数
-F 指定输入文件折分隔符
-v var=value 赋值一个用户定义变量

循环和数组

提供类似 C 的 if else 语句。类 C 的 do while 语句。类 C 的 for 循环，break，continue

内置变量

正则

makefile
#

详细教程https://github.com/seisman/how-to-write-makefile

目标、依赖、规则命令

写法：
#

目标：依赖

tab键 + 规则命令

clean:
	rm -rf *.o firstText
#执行make clean时会删除所有.o文件和firstText

一行东西过多可用\来分解多行

使用变量：
# 
OBJS = test1.o test2.o  #设置变量格式  varname=content
G = g++
CFLAGS = -Wall -O -g
 
firstTest:$(OBJS)            #引用变量格式：$(varName)
	$(G) $(OBJS) -o firstTest
 
test1.o:test1.cpp test2.h
	$(G) $(CFLAGS) -c test1.cpp
test2.o:test2.cpp test2.h
	$(G) $(CFLAGS) -c test2.cpp
 
clean:
	rm -rf *.o firstTest
使用函数：
# 
C = gcc
G = g++
CFLAGS = -Wall -O -g
TARGET = ./firstTest
 #表示把所有的.c、.cpp文件编译成.o文件
 # $@扩展成当前规则的目标文件名
 # $<扩展成依赖列表中的第一个依赖文件
 # $^扩展成整个依赖的列表（除掉里面所有重复的文件名）
%.o:%.c
	$(C) $(CFLAGS) -c $< -o $@
 
%.o:%.cpp
	$(G) $(CFLAGS) -c $< -o $@
 
SOURCES = $(wildcard *.c *.cpp)		#函数wildcard，产生一个所有以.c .cpp结尾的文件列表，存入变量SOURCE中
 
OBJS = $(patsubst %.c,%.o,$(patsubst %.cpp,%.o,$(SOURCES)))		#函数patsubst，将SOURCE文件列表中所有.cpp变为.o、.c变为.o存入OBJS
 
$(TARGET):$(OBJS)
	$(G) $(OBJS) -o $(TARGET)
	chmod a+x $(TARGET)
 
clean:
	rm -rf *.o firstTest

wildcard函数：产生一个所有以参数结尾的文件列表

patsubst匹配替换，三个参数（需要匹配的样式，目标样式，需要处理的由空格分离的列表）

tcpdump
#

对网络上的数据包进行截获的包分析工具。

shell
#

shell 脚本就是将完成一个任务的所有命令按照执行的先后顺序，自上而下写入到一个文本文件中，然后给予执行权限

# 定义脚本的执行环境
#!/usr/bin/bash
# 或使用解释环境
#!/usr/bin/env bash | python | perl

运行脚本

  • 给执行权限
  • 解释器直接运行，不需要权限

set -e 在文件开头，告诉 bash 如果任何语句的执行结果不是 true 则立刻退出。防止错误像滚雪球一样变大

set -x 在执行每一行 shell 脚本时，把执行的内容输出来。它可以让你看到当前执行的情况，里面涉及的变量也会被替换成实际的值。

特殊符号
~ 家目录
- 上一目录
! 以前执行过的命令 !!执行上一命令
$ 变量中取内容
& 后台执行
* 匹配所有
? 匹配一个
`` 反引号 命令中执行命令 echo "today is : date + %F"
引号 字符串，单引号不解释变量
(()) 双小括号可以做运算

read: -p 打印信息 -t限定时间 -s 不回显 -n 输入字符个数

开发命令
#

nm
#

列出.o .a .so中的符号信息，包括诸如符号的值，符号类型及符号名称等。所谓符号，通常指定义出的函数，全局变量等等

strings
#

打印文件中可打印的字符，可以使文本文件、可执行文件、动静态链接库

strings -f "*.so" | grep "xxxxxx"
# 快速知道某个.c .cpp 文件编译到哪个.so库中

开机启动过程
#

  1. 加载 BIOS

    BIOS 中 包含了 CPU 的相关信息、设备启动顺序信息、硬盘信息、内存信息、时钟信息、PnP 特性等

  2. 读取 MBR

    硬盘上第 0 磁道第一个扇区被称为 MBR（Master Boot Record），即主引导记录，大小 512 字节，存放预启动信息、分区表信息。

    系统找到 BIOS 指定的硬盘的 MBR 后，会将其复制到 0x7c00 地址所在的物理内存中，内容是 Boot Loader，具体到电脑就是 lilo 或 grub

  3. Boot Loader

    即在操作系统内核运行之前运行的一小段程序，通过它可以初始化硬件设备、建立内存空间的映射图，将系统的软硬件环境带到一个合适的状态

    Boot Loader 有若干种，Grub、Lilo 和 spfdisk

    以下按照 grub

  4. 加载内核

    根据 grub 设定的内核映像所在路径，系统读取内存映像，并进行解压缩操作。

    将解压后的内核放置在内存中，并调用 start_kernel() 函数来启动一系列的初始化函数并初始化各种设备，完成 linux 核心环境的建立。至此 linux 内核建立起来，可以正常运行程序

  5. init

    运行 init 程序，即 /sbin/init，读取 /etc/inittab 文件进行初始化

    执行 rc.sysinit 脚本程序，包括设定 PATH、设定网络配置、启动 swap 分区、设定 /proc 等等

    启动内核模块

    执行不同运行级别的脚本程序

    执行 /etc/rc.d/rc.local，即在一切初始化工作后，linux留给用户进行个性化的地方

  6. 执行 /bin/login，进入登录状态

select / poll / epoll
#

select
#

  • 单个进程能监听的文件描述符的数量存在最大限制，通常为 1024，可通过 FD_SETSIZE 设置，由于 select 采用轮询的方式扫描文件描述符，数量越多，性能越差
  • 内核 / 用户空间内存拷贝问题，需要复制大量的句柄数据结构，有大量开销，每次调用都需要将 fd 集合从用户态拷贝到内核态，需要在内核遍历传递进来的所有 fd
  • select 返回的是含有整个句柄的数组，应用程序需要遍历数组才能发现哪些句柄有事件
  • 水平触发
  • 采用位掩码的模型，通过申请

poll
#

  • 相比 select 模型，poll 使用链表保存文件描述符，没有监视文件数量的限制
  • 每次返回文件描述符数组，需要遍历数组找到哪些文件描述符上有 IO 事件

epoll
#

  • 没有文件描述符数量限制，上限就是最大可以打开文件的数目
  • 每一个 epoll 对象都有一个独立地 eventpoll 结构体，用于存放通过 epoll_ctl 方法向 epoll 对象中添加进来的事件。这些事件挂载在红黑树上，如此，重复添加的事件可通过红黑树高效的识别出来
  • 所有添加到 epoll 中的事件都会与设备(网卡)驱动程序建立回调关系，当相应的事件发生时会调用这个回调方法。这个回调方法在内核中叫 ep_poll_callback，它会将发生的事件添加到 rdlist 双链表中。
  • epoll描述符的事件结构，只需要向内核中拷贝一次，不需要每次都拷贝
  • epoll是一个异步阻塞操作，发起调用，让操作系统进行文件描述符的监控，使用事件回调函数对描述符进行监控，避免了 select 的遍历轮询，性能不会随着文件描述符增多而下降

当某一进程调用 epoll_create 方法时，Linux 内核会创建一个 eventpoll 结构体，这个结构体中有两个成员与 epoll 的使用方式密切相关，一个是红黑树，另一个是双向链表。红黑树中存储着所有添加到 epoll 中的需要监控的事件，双链表中则存放着将要通过 epoll_wait 返回给用户的满足条件的事件。这些事件都会挂载在红黑树中，如此，重复添加的事件就可以通过红黑树而高效的识别出来(红黑树的插 入时间效率是 log(n)，其中 n 为树的高度).而所有添加到 epoll 中的事件都会与设备(网卡)驱动程序建立回调关系，也就是说，当响应的事件发生时会调用这个回调方法.这个回调方法在内核中叫 ep_poll_callback，它会将发生的事件添加到 rdlist 双链表中.通过这种方式大大的提高了效率。

LT 模式下，只要一个句柄上的事件一次没有处理完，会在以后调用 epoll_wait 时次次返回这个句柄，而 ET 模式仅在第一次返回。当 socket 句柄上有事件时，内核会把该句柄插入到准备就绪的 list 链表中，这是调用 epoll_wait，会把准备就绪的 socket 拷贝到用户态内存，然后清空准备就绪 list 链表，最后 epoll_wait 会检查这些 socket，如果不是 ET 模式且 socket 上有未处理的事件，则将该井放回刚刚清空的准备就绪链表。而 ET模式的句柄，除非有新中断到来，即使 socket 上的事件没有处理完，也不会再返回

定位服务器瓶颈
#

  • 系统 CPU 利用率

    监控命令：vmstat、sar、dstat、mpstat、top、ps

  • 内存利用率

    物理内存不够时，会使用 swap 分区，关注 swap 和 mem 的使用情况

    监控命令：vmstat、sar、dstat、free、top、ps

  • 磁盘 I/O 的利用率和延迟

    需要考虑 I/O 的 TPS、平均 I/O 数据、平均队列长度、平均服务时间、平均等待时间、IO 利用率（磁盘 Busy Time%）等指标

    监控命令：sar、iostat、iotop

  • 网络利用率

    监控命令：sar、ifconfig、netstat，以及查看 net 的 dev 速率。

  • 上下文切换

    pidstat -w 1 查看每个进程或线程的上下文使用情况。

    cswch/s 每秒任务主动切换上下文次数，当某一任务处于阻塞时，主动让出 CPU 资源

    nvcswch/s 每秒被动，如时间片用完

    taskset -c 0 ./redis-server· 将 Redis 实例绑定在 0 号核上，减少实例在不同核上被来回调度的开销

    可以把网络中断程序和 Redis 实例绑在同一 CPU Socket 的不同核上，避免跨 Socket 访问内存中的网络数据的开销

    **一个实例对应一个物理核的缺点：**导致子进程、后台线程和主线程竞争 CPU 资源，可能使主线程阻塞

    方案：

    • 一个实例对应一个物理核

      # 0 和 12 表示同一个物理核的两个逻辑核
taskset -c 0,12 ./redis-server

    • 优化源码，让不同线程在不同核上运行。

死锁
#

产生死锁的四个必要条件：

  • 互斥条件：每个资源只能被一个进程使用
  • 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放
  • 不剥夺条件：进程已获得的资源，在未使用之前，不能强行剥夺
  • 循环等待条件：若干进程之间形成一个头尾相接的循环等待关系

避免死锁：

  • 破坏请求和保持条件：

    • 一次性的申请所有的资源，之后不再申请资源，如果不满足条件则得不到资源分配
    • 只获得初期资源运行，之后将运行完的资源释放，请求新的资源

  • 破坏不可抢占：

    当一个进程获得某种不可抢占资源，提出新的资源申请，若不能满足，则释放所有资源，以后需要，再次重新申请

  • 破坏循环等待：

    对资源进程排号，按顺序请求资源，若进程获得序号的资源想要获取序号低的资源，就需要先释放序号高的资源

具体方法：

  • 正确的顺序获取锁

  • 超时放弃

  • 检测获取资源的有向图是否存在环，从一个节点出发进行 dfs，如果访问了已经访问过的节点，则存在环。

    死锁恢复：

    • 资源剥夺法：剥夺陷入死锁的进程所占用的资源，但不撤销此进程，直到死锁解除
    • 进程回退法：根据系统保存的检查点让所有进程回退，直到足已解除死锁。这种措施要求系统建立保存检查点、回退以及重启机制
    • 进程撤销法：
      1. 撤销陷入死锁的所有进程，解除死锁，继续运行
      2. 逐个撤销陷入死锁的进程，回收其资源并重新分配，直到死锁解除。可选择符合下面条件之一的先撤销： 1.CPU消耗时间最少者 2.产生的输出量最小者3.预计剩余执行时间最长者 4.分得的资源数量最少者后优先级最低者

场景设计
#

海量数据
#

海量日志，提取出某日访问百度次数最多的 ip
#

  • 问题

    IP 地址最多有 2^32 = 4G 种取值情况，所以不能完全加载到内存中处理

  • 解决方法

    采用映射的方法，比如模 1000，按后三位把整个大文件映射为 1000 个小文件

    再找出每个小文中出现频率最大的 IP（可以采用 hash_map 进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这 1000 个最大的 IP 中，找出那个频率最大的 IP

统计最热门的10个查询串
#

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为 1-255 字节。 假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

  • 问题

    内存不能超过 1G，一千万条记录，每条记录是 255Byte，很显然要占据 2.375G 内存

  • 方案

    第一步：Query 统计

    • 多路归并排序

      外部排序指的是大文件的排序，当待排序的文件很大时，无法将整个文件的所有记录同时调入内存进行排序，只能将文件存放在外存，这种排称为外部排序。

      多路归并排序，即将原文件分解成多个能够一次性装入内存的部分分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。

      排完序之后我们再对已经有序的 Query 文件进行遍历，统计每个 Query 出现的次数，再次写入文件中。

      复杂度：O(N+NlgN)= O（NlgN）

    • 哈希表

      300万的Query，每个Query255Byte，因此我们可以考虑把他们都放进内存中去，维护一个Key为Query字串，Value为该Query出现次数的HashTable，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内完成了对该海量数据的处理

    第二步：找出TOP10

    • 大根堆

      维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比。最先遍历到的k个数存放到最小堆中，并假设它们就是我们要找的最大的k个数，X1>X2…Xmin(堆顶)，而后遍历后续的N-K个数，与堆顶元素进行比较，如果遍历到的Xi大于堆顶元素Xmin，则把Xi放入堆中，而后更新整个堆，更新的时间复杂度为logK，如果Xi<Xmin，则不更新堆

高频100词
#

有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

  • 分文件（外存中进行）

    顺序读文件中，对于每个词 x，取 hash(x) % 5000，然后按照该值存到 5000 个小文件（记为 x0,x1,…x4999）中。这样每个文件大概是 200k 左右。

  • 文件内排序（内存中）

    对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用 trie 树 / hash_map等），并取出出现频率最大的 100 个词（可以用含 100 个结点的最小堆），并把 100 个词及相应的频率存入文件，这样又得到了5000个文件。

  • 归并

    把这 5000 个文件进行归并（类似与归并排序）

多文件排序
#

有10个文件，每个文件1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求你按照 query 的频度排序。

  • 读取文件，重复的合并到一个文件中

    顺序读取10个文件，按照 hash(query) % 10的结果将 query 写入到另外 10 个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设 hash 函数是随机的）。

  • 排序

    找一台内存在 2G 左右的机器，依次对用 hash_map(query, query_count) 来统计每个 query 出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的 query 和对应的 query_count 输出到文件中。这样得到了 10 个排好序的文件

  • 归并

bitmap
#

在2.5亿个整数中找出不重复的整数（内存不足以容纳这2.5亿个整数）

  • 数量统计

    int 有4个字节，32 位bit，最多可表示 2^32^ 个正整数，即 4G 个正整数（1G = 2^30^，1K = 2^10^）

    用 2Bitmap 法，每个正整数用两个bit的标志位，00表示没有出现，01表示出现1次，10表示出现多次。 开辟一个用 2Bitmap 法标志 4G 个正整数的桶数组，则总共需要 4G * 2bit = 1G 内存。

  • 扫描

    然后扫描这 2.5 亿个整数，查看 Bitmap 中相对应位，如果是 00 变 01，01 变 10，10 保持不变。所描完事后，查

    看 bitmap，把对应位是 01 的整数输出即可。

注意：新开数组的所需大小并不取决于数据量的大小，而是取决于某数据值的大小

超大文件取数字交集
#

现有两个各有 20 亿行的文件，每一行都只有一个数字，求这两个文件的交集

使用 bitset 解决，int 最大为 2^32^ - 1 = 4G，用一个二进制下标来表示一个 int 值大约需要 4G 个 bit 位，即 4G / 8 = 512M 的内存，用 int 存的话，2^32^ / 32 = 2^27^ = 128M，则建立 int[128M] 的数组，先 /32 确定数组位置再 %32 确定是哪一位，然后取并集。

若有正负数则每个文件建两个 bitset 来存储正数和负数

长 URL 转短 URL
#

实现必要条件
#

  • 有独立域名系统，用于拼接完整的短链接，以后后续反查长链接地址
  • 有一个 id 发号器（保证数字保持唯一），如数据库的自增序列

实现方案
#

  1. 将长链接字符串插入数据库，使用 sequence 递增序列作为主键，然后返回主键 id

    或者 先从发号器取出一个新 id，插入 id 和长链接字符串（两个字段，且 id 为主键）

  2. 将主键 id 进行 62 进制编码（10 数字 + 26 大写字母 + 26 小写字母，一般 url 用这些表示）

  3. 使用自身域名信息 + 62 进制字符串拼接为完整的 url，返回

解析

客户请求短链接时，时间是寻址短链接域名发送到服务器系统上，然后根据 url 后缀，转换为 10 进制，去数据库查询主键，找出长链接，然后返回客户端，返回码为 301/302（浏览器自动重定向）

优化
#

发号器瓶颈

  • 可多用几个发号器，各自发号不重复

    如 10 个发号器，尾号分别为 0~9

同样的长链接，生成的短链接不一样

  • 一定时间生成短链接不变

    内存存放 LinkedHashMap，key 为长链接，value 为短链接

  • 永久一样

    存入数据库时，除了唯一id和长链接地址外，使用长链接生成 64 位 hashcode，然后一并存入数据库，并且添加索引，下次插入数据库之前，先查询 hashcode 列是否有这个值，有的话则取出比较value是否相等，这里可能是 hash 冲突，实际上不是同一个长链接，但是使用64位 hashcode 的话，冲突概率会小很多，这里使用 hashcode 做索引，而不是直接使用长链接本身，是考虑到长链接比较长，作为索引的话，会导致索引层级加深，需要增加额外的磁盘寻址

分布式
#

分布式锁
#

  • 在分布式系统环境下，一个方法在同一时间只能被一个机器的一个线程执行
  • 高可用的获取锁和释放锁
  • 高性能的获取锁和释放锁
  • 具备可重入特性（重新进入，有多于一个任务并发使用，而不用担心数据错误）
  • 具备锁释放机制，防备死锁
    • 具备非阻塞锁特性，即没有获取到锁就将直接返回锁失败

实现

  • memcached
  • redis：利用 redis 的 setnx 命令，此命令同样是原子性操作，只有在 key 不存在的情况下，才能 set 成功
  • zookeeper
  • chubby

一致性哈希
#

  • 首先求出服务器（节点）的哈希值，并将其配置到 0 - 2^32^ 的圆上
  • 同样方法求出存储数据的键的哈希值，并将其映射到相同的圆上
  • 从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上， 如果超过 2^32^仍然找不到服务器，则保存到第一个服务器上。

优点：

服务器的数量如果发生改变，并不是所有缓存都会失效，而是只有部分缓存会失效，前端的缓存仍然能分担整个系统的压力，而不至于所有压力都在同一时间集中到后端服务器上。

哈希环倾斜

服务器节点分布不均

引入虚拟节点机制，每台机器映射的虚拟节点越多，则分布的越均匀

高并发
#

客户端
#

  • 尽可能减少请求数，例如：依靠客户端本身的缓存或处理能力。

  • 尽量减少对服务器资源的不必要消耗。例如，重复使用某些资源。例如，连接池客户端处理的基本原则是不访问服务器就不访问。

客户端发出请求的常用方法有:

  • 尽量使用浏览器的缓存功能来减少访问服务器，如 js、css、图片等。

  • 可考虑使用压缩传输功能，减少网络流量，提高传输速度。

  • 考虑异步请求，分批获取数据。

服务端
#

  • 增加资源供应，如更大的网络带宽、更高配置的服务器、高性能的网络服务器和高性能的数据库。
  • 请求分流，如使用集群和分布式系统架构。
  • 应用程序优化，例如：使用更高效的程序设计语言，优化处理业务逻辑的算法，优化访问数据库的 SQL

前端接收客户端请求的常用方法

  • 动静分离，部分静态资源可直接从 Nginx 返回。

  • 根据需要，分发到不同的后端进行处理，例如：负载平衡，业务拆分访问等等。

  • 前面加一层做多个 Nginx 的负载平衡，比如 LVS，F5。

  • CDN 服务也可 DN 服务。

  • 也可以缓存动态内容，尽量减少访问后端服务。

静态资源： 可以理解为前端的固定页面，包含 HTML、CSS、JS、图片等，不需要查数据库也不需要程序处理，直接就能够显示的页面，如果想修改内容则必须修改页面，访问效率高

**动态资源：**需要程序处理或者从数据库中读数据，能根据不同的条件在页面显示不同数据，内容更新不需要修改页面，但是访问速度不及静态页面。

  • 应用数据与静态资源分离 将静态资源（图片，视频，js，css等）单独保存到专门的静态资源服务器中，在客户端访问的时候从静态资源服务器中返回静态资源，从主服务器中返回应用数据。
  • 客户端缓存 因为效率最高，消耗资源最小的就是纯静态的 html 页面，所以可以把网站上的页面尽可能用静态的来实现，在页面过期或者有数据更新之后再将页面重新缓存。或者先生成静态页面，然后用 ajax 异步请求获取动态数据。
  • 集群和分布式 （集群是所有的服务器都有相同的功能，请求哪台都可以，主要起分流作用） （分布式是将不同的业务放到不同的服务器中，处理一个请求可能需要使用到多台服务器，起到加快请求处理的速度。） 可以使用服务器集群和分布式架构，使得原本属于一个服务器的计算压力分散到多个服务器上。同时加快请求处理的速度。
  • 反向代理 在访问服务器的时候，服务器通过别的服务器获取资源或结果返回给客户端。

Related

MySQL 笔记
·25 mins
C/CPP 笔记
·30 mins
Matlab笔记
·8 mins
Redis 笔记
·9 mins
算法笔记
·5 mins
计算机网络笔记
·37 mins