算法
红黑树
操作系统
进程和线程
对于有线程系统：
- 进程是资源分配的独立单位
- 线程是资源调度的独立单位
对于无线程系统：
进程是资源调度、分配的独立单位
这个还是看面经好了
线程安全
- 如果有多个线程在同时运行，而这些线程可能会同时运行这段代码。程序每次运行结果和单线程运行的结果是一样的，而且其他的变量的值也和预期的是一样的，就是线程安全的。
cpu调度算法(进程调度)
- 先来先服务
- 最短作业
- 最短剩余时间
- 时间片轮转
- 优先级调度
- 多级反馈队列
线程，进程，为什么进程切换消耗比较大，有多个协成是不是可以同步进行？
进程线程区别
*Ⅰ 拥有资源
- 进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。
- Ⅱ 调度
- 线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
- Ⅲ 系统开销
- 由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
- Ⅳ 通信方面
- 线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。
协程
协程 Coroutines 是一种比线程更加轻量级的微线程。类比一个进程可以拥有多个线程，一个线程也可以拥有多个协程，因此协程又称微线程和纤程。
线程是被内核所调度，线程被调度切换到另一个线程上下文的时候，需要保存一个用户线程的状态到内存，恢复另一个线程状态到寄存器，然后更新调度器的数据结构，这几步操作设计用户态到内核态转换，开销比较多。
协程的调度完全由用户控制，协程拥有自己的寄存器上下文和栈，协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操作用户空间栈，完全没有内核切换的开销。
虚拟内存、物理内存
物理内存（内存条）：当打开程序时，系统会将这些程序加载到物理内存上。
虚拟内存（硬盘）：虚拟的不是物理内存，而是代替物理内存行使存储的功能，物理内存的运行程序的功能是无法用虚拟内存来完成的。
物理内存与虚拟内存的关系：当运行程序过多，物理内存不够用时，系统会将一部分硬盘空间当内存使用，这部分空间就是虚拟内存。
虚拟地址空间（用户空间、内核空间）
C / C++系列 （3）：heap vs. stack & new vs. malloc
C / C++系列 （4）：malloc内存分配 & linux虚拟地址空间布局
- 虚拟地址空间（作用：解决物理内存稀缺问题）：系统为每个进程所分配的4GB虚拟地址空间（32位系统），用来存放进程的虚拟地址，再通过MMU（内存管理单元）将虚拟地址映射到物理内存地址。
- 虚拟地址通过页表(Page Table)映射到物理内存，页表由操作系统维护并被处理器引用。
- 内核空间在页表中拥有较高特权级，因此用户态程序试图访问这些页时会导致一个页错误(page fault)
- 在Linux中，内核空间是持续存在的，并且在所有进程中都映射到同样的物理内存。内核代码和数据总是可寻址，随时准备处理中断和系统调用。与此相反，用户模式地址空间的映射随进程切换的发生而不断变化。
变量内存的分配方式
- 静态存储区
- 全局变量 ，static变量
- 栈
- 局部变量
- 堆（动态内存分配）
- 程序在运行的时候用malloc 或new 申请任意多少的内存，程序员自己负责在何时用free或delete释放内存。
- malloc接触的内存空间是虚拟内存
用户空间
栈空间
- 局部变量存放的位置，函数调用会在占空间生成栈帧,由系统控制
栈又称堆栈，由编译器自动分配释放，行为类似数据结构中的栈(先进后出)。堆栈主要有三个用途：
- 为函数内部声明的非静态局部变量(C语言中称“自动变量”)提供存储空间。
- 记录函数调用过程相关的维护性信息，称为栈帧(Stack Frame)或过程活动记录(Procedure Activation Record)。它包括函数返回地址，不适合装入寄存器的函数参数及一些寄存器值的保存。除递归调用外，堆栈并非必需。因为编译时可获知局部变量，参数和返回地址所需空间，并将其分配于BSS段。
- 临时存储区，用于暂存长算术表达式部分计算结果或alloca()函数分配的栈内内存。
注意点：
- 持续地重用栈空间有助于使活跃的栈内存保持在CPU缓存中，从而加速访问。进程中的每个线程都有属于自己的栈。向栈中不断压入数据时，若超出其容量就会耗尽栈对应的内存区域，从而触发一个页错误。此时若栈的大小低于堆栈最大值RLIMIT_STACK(通常是8M)，则栈会动态增长，程序继续运行。映射的栈区扩展到所需大小后，不再收缩。
- Linux中ulimit -s命令可查看和设置堆栈最大值，当程序使用的堆栈超过该值时, 发生栈溢出(Stack Overflow)，程序收到一个段错误(Segmentation Fault)。注意，调高堆栈容量可能会增加内存开销和启动时间。
- 堆栈既可向下增长(向内存低地址)也可向上增长, 这依赖于具体的实现。本文所述堆栈向下增长。
- 堆栈的大小在运行时由内核动态调整。
共享库区域（内存映射段）
- 内核用于将硬盘文件的内容直接映射到内存,内存映射是一种方便高效的文件I/O方式， 因而被用于装载动态共享库
堆空间
- 动态分配的内存,由用户控制
堆用于存放进程运行时动态分配的内存段，可动态扩张或缩减。堆中内容是匿名的，不能按名字直接访问，只能通过指针间接访问。
分配的堆内存是经过字节对齐的空间，以适合原子操作。
堆管理器通过链表管理每个申请的内存，由于堆申请和释放是无序的，最终会产生内存碎片。堆内存一般由应用程序分配释放，回收的内存可供重新使用。若程序员不释放，程序结束时操作系统可能会自动回收。
可读可写段
BSS段
- BSS段和数据段的区别
- BSS段不占用物理文件尺寸，但占用内存空间；数据段占用物理文件，也占用内存空间
- 对于大型数组如int ar0[10000] = {1, 2, 3, …}和int ar1[10000]，ar1放在BSS段，只记录共有10000*4个字节需要初始化为0，而不是像ar0那样记录每个数据1、2、3…，此时BSS为目标文件所节省的磁盘空间相当可观。
- 当程序读取数据段的数据时，系统会出发缺页故障，从而分配相应的物理内存；当程序读取BSS段的数据时，内核会将其转到一个全零页面，不会发生缺页故障，也不会为其分配相应的物理内存。
- BSS段不占用物理文件尺寸，但占用内存空间；数据段占用物理文件，也占用内存空间
只读代码段
- 可执行代码、字符串字面值、只读变量
- 代码段也称正文段或文本段
- 通常用于存放程序执行代码(即CPU执行的机器指令)。
- 代码段是可共享的，因此频繁执行的程序只需要在内存中拥有一份拷贝即可。
保留区
- 位于虚拟地址空间的最低部分，未赋予物理地址。任何对它的引用都是非法的，用于捕捉使用空指针和小整型值指针引用内存的异常情况。
内核空间
- 包括内核数据和内核栈等
- 用来存放操作系统内核代码和数据等
- 内核代码和数据区在每个进程的地址空间中都相同
- 用户态不能访问内核区
- 内核栈就是用来纪录进程内核态的执行状态的， 进程的内核栈清空了还怎么进程switch呢.进程的切换都是内核态的工作，进程切换基本就是内核栈的切换