1 什么是并发和并行？

• 并发：一个行为主体同时执行多个任务，在为每个任务分配的时间片间轮流切换

• 并行：多个行为主体同时执行多个任务，每个行为主体只专注于其中的一个任务

2 什么是同步、异步、阻塞和非阻塞？

• 同步：一个任务必须等待另一个任务执行完，才能继续执行

• 异步：一个任务无需等待另一个任务执行完，即可继续执行

• 阻塞：调用一个函数，执行某种操作，在该操作完成之前，函数不返回

• 非阻塞：调用一个函数，启动某种操作，不等操作完成，函数即刻返回

3 什么是进程和线程？

• 进程是可执行程序文件被加载到内存后，由处理器执行其中的代码，操作其中的数据的过程

• 线程是进程内特定的执行序列，它是比进程更小且能独立运行的基本单位，亦称轻量级进程

4 进程和线程有何区别？

• 进程是资源分配的最小单位，而线程是被处理机调度的最小单位

• 进程的创建与销毁往往伴随着资源的分配与释放，系统开销远大于线程

• 不同进程的地址空间是彼此独立的，而同一个进程的不同线程则共享进程的地址空间

• 一个进程的崩溃通常不会影响到系统中的其它进程，而一个线程的崩溃则往往导致整个进程的崩溃

5 既然已经有了进程，为何还要有线程？

• 创建和销毁进程的系统开销通常较大，基于线程的并发具有更低的成本

• 进程间的数据交换需要借助专门的通信机制，而线程之间天然共享数据

• 丰富的线程同步机制，使在宏观异步的背景下实现微观的同步代价极低

6 什么是进程的状态转换？

• 一个进程有三种基本状态：就绪态、运行态和阻塞态

• 进程状态的转换关系如下图所示：

  • 就绪态$\to$$\rightarrow$运行态：处于就绪态的进程被调度器选中，得到处理机，即进入运行态

  • 运行态$\to$$\rightarrow$阻塞态：处于运行态的进程为等待某事件而无法继续运行，即进入阻塞态

  • 阻塞态$\to$$\rightarrow$就绪态：处于阻塞态的进程所等待事件已发生，可继续运行，即进入就绪态

  • 运行态$\to$$\rightarrow$就绪态：处于运行态的进程时间片耗尽或被更高优先级进程抢占，让出处理机，即进入就绪态

7 进程之间共有多少种通信方式？

• 无名管道

  • 半双工，有固定的读端和写端

  • 只能用于父子及兄弟进程间的通信

  • 可以象读写文件一样读写管道，但它并非文件，也不属于任何文件系统，只存在于内存中

• 有名管道

  • 全双工，无固定的读端和写端

  • 可用于任意进程间的通信

  • 参与通信的多个进程通过管道文件会合，管道文件是一种特殊的文件，存在于文件系统中

• 消息队列

  • 由操作系统内核维护的消息链表，以特定的标识符标识

  • 面向记录，每条消息均包括消息类型和消息内容

  • 即使参与通信的进程都终止了，消息队列连同其中的消息也不会被系统自动回收

  • 队列中的消息可以按先进先出的顺序读取，也可以按类型读取

  • 消息队列本身具备同步机制，空队列不可读，满队列不可写，不发则不收

• 共享内存

  • 由操作系统内核维护的公共内存区域，以特定的标识符标识

  • 面向字节流，进程可以象访问本地内存一样访问共享内存中的数据

  • 即使参与通信的进程都终止了，共享内存连同其中的数据也不会被系统自动回收

  • 多个进程通过共享内存通信，所传输数据通过各个进程的虚拟内存被直接映射到同一块物理内存中，这就避免了在不同进程间来回复制数据的开销。因此，基于共享内存的进程间通信，是速度最快的进程间通信

  • 共享内存本身缺乏同步机制，需要编写额外代码建立同步。例如一个进程向共享内存写入数据，在写完之前，其它进程就不能读取该共享内存。为此可能需要借助其它机制，如信号量等，这无疑会增加系统开销

• 信号量

  • 信号量的本质是一个计数器，跟踪可用资源的数量，以解决多个用户分享有限资源时的竞争与冲突问题

  • 信号量着意解决进程间的停——等同步而非数据传递，如需交换数据还需借助其它进程间通信机制

  • 信号量基于系统的PV操作，所有针对信号量的访问都是原子化的

  • 每次对信号量的调整不仅限于增减一，也可以增减任意正整数

  • 即使参与通信的进程都终止了，信号量也不会被系统自动回收

  • 支持信号量集

8 进程的调度算法都有哪些？

• 时间片轮转调度算法：将处理机交给位于就绪队列队首的进程，为其分配一个时间片，时间片到期后将该进程排到就绪队列末尾，再从队首调度下一个进程

• 长等候时间优先调度算法：将处理机交给就绪队列中等候时间最长的进程，待其终止或主动放弃处理机后再调度下一个进程

• 短运行时间优先调度算法：将处理机交给就绪队列中预计运行时间最短的进程，待其终止或主动放弃处理机后再调度下一个进程

• 短剩余时间优先调度算法：将处理机交给就绪队列中预计运行时间最短的进程，待其终止或主动放弃处理机后再调度下一个进程，但如果就绪队列中有预计剩余时间更短的进程，则抢占当前进程的处理机，优先执行

• 高响应比优先调度算法：将处理机交给就绪队列中响应比（等候时间与预计运行时间之比）最高的进程，待其终止或主动放弃处理机后再调度下一个进程

• 优先级调度算法：将处理机交给就绪队列中优先级最高的进程，待其终止或主动放弃处理机后再调度下一个进程

9 什么是死锁？

• 死锁系两个或两个以上的进程在运行过程中为了争夺资源，而形成的一种互相等待现象

  • 进程1在得到资源A后试图获取资源B

  • 进程2在得到资源B后试图获取资源A

  • 进程1在等待资源B的过程中不释放已得到的资源A，造成进程2对资源A的无限等待

  • 进程2在等待资源A的过程中不释放已得到的资源B，造成进程1对资源B的无限等待

  • 进程1和进程2分别在对资源B和资源A的无限等待中形成死锁

10 导致死锁的原因是什么？

• 导致死锁的根本原因在于，参与竞争的两个或者更多进程，在请求被其它进程拥有的资源的同时，不肯释放自己已经获得的资源，最终导致无限期的互相等待，整个过程无法推进

11 产生死锁的必要条件都有哪些？

• 独占排它：进程以独占的方式使用其所获得的资源，即在一段时间内不允许其它进程使用该资源。这段时间内，任何试图请求该资源的进程只能在阻塞中等待，直到资源被其拥有者主动释放

• 请求保持：进程已经拥有了至少一个资源，但又试图获取已被其它进程拥有的资源，因此只能在阻塞中等待，同时对自己已经获得的资源坚守不放

• 不可剥夺：进程已经获得的资源，在其未被使用完之前，不可被强制剥夺，而只能由其拥有者主动释放

• 循环等待：进程集合$\{T_0,T_1,T_2,\cdots ,T_n\}$$\{T_0,T_1,T_2,\cdots,T_n\}$中，$T_0$$T_0$等待$T_1$$T_1$拥有的资源，$T_1$$T_1$等待$T_2$$T_2$拥有的资源，······，$T_{n-1}$$T_{n-1}$等待$T_n$$T_n$拥有的资源，$T_n$$T_n$等待$T_0$$T_0$拥有的资源，形成环路

12 解决死锁的基本方法都有哪些？

• 事前预防：通过设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个，以避免死锁的发生。但如果所设置的限制条件过于严苛，则极有可能导致系统资源利用率和吞吐量的下降

• 事中规避：无需事先通过各种限制措施破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，通过某种方法防止系统进入不安全状态，从而避免死锁的发生

• 事后补救：允许系统发生死锁，但可以通过预设的检测机制，及时发现死锁的产生，并精确定位与死锁有关的进程和资源。而后取消或挂起一些进程，回收其资源，再将这部分资源分配给那些于阻塞中等待资源的进程，使之进入就绪状态，继续运行

13 如何预防死锁？

• 破坏独占排它条件：以非独占方式使用资源，避免进程间的资源竞争

• 破坏请求保持条件：不能获得所有资源进程，必须释放已获得的资源

• 破坏不可剥夺条件：进程已获得的资源可被强制剥夺

• 破坏循环等待条件：每个资源对应一个编号，每个进程按编号递增顺序请求资源，按相反顺序释放资源

14 如何解除死锁？

• 取消某些死锁进程，将其拥有的资源分配给其它死锁进程

• 挂起某些死锁进程，将其拥有的资源分配给其它死锁进程

• 令部分进程回退至足以避免死锁的位置，主动释放所拥有的资源，

15 什么是缓冲区溢出？有何危害？

• 缓冲区溢出是指当程序向缓冲区填充数据时，超出了缓冲区的容量限制，溢出部分覆盖了某些合法数据

• 缓冲区溢出的危害包括但不限于以下两种：

  • 导致程序崩溃，拒绝服务

  • 跳转并执行一段恶意代码

16 分段和分页有何区别？

• 段是信息的逻辑单位，根据用户的需要划分，对用户可见；页是信息的物理单位，根据系统的需要划分，对用户透明

• 段的大小不定，与功能有关；页的大小固定，由系统决定

• 使用段的地址空间是二维的；使用页的地址空间是一维的

• 段有助于信息的保护和共享；页与信息的保护和共享无关

17 什么是物理内存和虚拟内存？

• 物理内存是程序运行过程中，用于存放代码和数据的物理介质，不仅包括计算机的主存储器，也包括磁盘上的交换分区或换页文件

• 在系统中运行的每个进程，都拥有各自互独立的，地址连续的存储空间，谓之虚拟内存

• 虚拟内存到物理内存的映射关系，由操作系统内核通过内存映射表动态维护

• 虚拟内存一方面保护了系统的安全，把用户进程与内核进程，用户进程与用户进程，在对内存的访问上完全隔离开，另一方面又借助交换分区或换页文件，允许应用程序以一种完全透明的方式，使用比计算机主存储器大得多的存储空间

18 什么是物理地址和逻辑地址？

• 物理地址是计算机主存储器中以字节为单位的存储单元的编号。程序运行过程中执行的指令和访问的数据，最终都要通过物理地址定位到主存储器的特定存储单元中

• 逻辑地址是虚拟内存中每个字节的编号。该字节并没有真正的存储能力，但它可以与被物理地址标识的物理内存中的特定字节相对应，后者提供实际的存储功能

• 用户程序中使用的地址都是逻辑地址，物理地址只有操作系统内核才能访问

19 换页算法都有哪些？

• 当要在主存储器中保存数据，而主存储器中的空闲空间不够时，就需要将主存储器中的一部分数据暂时转移到交换分区或换页文件中。究竟选择哪部分数据换出更为合理，这就是换页算法需要解决的问题。例如：

  • 先进先出置换算法（FIFO，First In First Out）：将主存储器中最早换入的页面换出

  • 最优置换算法（OPT，Optimal）：将主存储器中预计未来最远使用的页面换出

  • 最近最久未用置换算法（LRU，Least Recently Used）：将主存储器中最近一次使用距离现在最久的页面换出

  • 最少使用置换算法（LFU，Least Frequently Used）：将主存储器中使用次数最少的页面换出

  • 时钟置换算法（NRU，Not Recently Used）：用一个指针轮询主存储器中的每一个页面，每次从该指针的当前位置开始寻找第一个未使用的页面换出，同时令该指针指向被换出页面的下一个页面

20 静态链接库和动态链接库有何区别？

• 静态链接库中的函数代码会被链接器拷贝到调用该函数的可执行程序中

  • 优点：没有加载开销，运行速度快，运行时无需依赖库，库无需发布给用户

  • 缺点：体积大，库一旦修改，所有使用该库的程序都需要重新链接

• 动态链接库中的函数代码不被链接器拷贝到调用该函数的可执行程序中，而是通过插入一系列指令，在运行时由操作系统将动态链接库加载到内存中，执行库中的函数代码

  • 优点：体积小，一个库可被多个程序共享，修改库只要接口不变，使用该库的程序无需重新链接

  • 缺点：加载开销影响前期执行性能，运行时需要依赖库，库必须和使用库的程序一起发布和部署

21 外中断和异常有何区别？

• 外中断：由CPU执行指令以外的事件引发，如I/O完成中断、时钟中断、控制台中断等

• 异常：由CPU执行指令的内部事件引发，如非法操作码、无效内存访问、算术溢出等

22 一个程序从源代码到可运行需要经历怎样的过程？

• 预编译（编译预处理）：执行编译前的准备工作

  • 处理“#include”指令

  • 处理“#pragma”指令

  • 处理条件编译

  • 宏替换

  • 过滤注释

  • 添加行号和文件标识

• 编译：将高级语言代码编译为汇编语言代码

  • 词法分析：扫描源代码，生成单词序列

  • 语法分析：分析单词序列，生成语法树

  • 语义分析：分析语法树中表达式的静态语义

  • 源码级优化：高级语言级别的优化

  • 生成汇编代码：将中间代码转换为用汇编语言表示的指令序列

  • 汇编级优化：优化汇编指令，如选择最佳寻址方式、用移位代替乘除法、删除冗余指令等

• 汇编：将汇编语言代码汇编为机器语言代码

  • 逐条翻译汇编指令，得到二进制形式的机器码文件，亦称目标文件

• 链接：将一或多个目标文件连同所依赖的各种库链接成可执行程序或动态库

  • 静态链接：将静态链接库中被用到的函数代码拷贝到可执行程序或动态库中

  • 动态链接：动态链接库中被用到的函数代码并不被拷贝到可执行程序或动态库中，相反只是插入一系列指令，在运行时由操作系统将动态链接库加载到内存中，执行库中的函数代码

23 典型的锁都有哪些？

• 自旋锁

  • 如果进程无法取得锁，并不会放弃处理机，而是一直循环尝试获取锁，直到取得为止

  • 如果其它进程长期占有锁，试图加锁的进程会消耗大量的处理机时间

  • 自旋锁只在加锁时间很短的场合，表现出较高的执行效率

• 互斥锁

  • 任何时候只能有一个进程取得锁，其它进程放弃处理机而进入睡眠，直到锁状态改变时再被唤醒

  • 从将锁交给操作系统管理并进入睡眠，到因锁状态改变而被操作系统唤醒，其间涉及因上下文切换而导致的性能开销

  • 互斥锁更适合用在加锁时间较长的场合，因上下文切换导致的性能开销所占比重可以忽略不计

  • 某些实现上的等锁过程，会先自旋一段时间，超过一定阈值后再进入睡眠，性能不亚于自旋锁

• 读写锁

  • 在互斥锁的基础上区分读写操作，强调读共享写独占的加锁原则

    • 已加读锁，可以再加读锁，但不能再加写锁

    • 已加写锁，既不能再加读锁，也不能再加写锁

  • 同时存在等读锁和等写锁的进程，等写锁的进程会被优先唤醒

• 条件变量

  • 条件变量在锁定、非锁定两种状态的基础上，又增加了一种可被唤醒的睡眠同时释放已取得锁的状态

    • 当一个进程继续运行的条件不满足时，可以在条件变量中睡眠，同时释放所持有的锁

    • 其它获得锁的进程一旦执行了令条件满足的操作，即可唤醒在条件变量中睡眠的进程

    • 被唤醒的进程在重新取得锁以后，继续之前的执行过程

  • 条件变量通常和互斥锁一起使用，以避免因竞态而死锁

24 什么是用户态和内核态？

• 用户态和内核态是指在程序运行过程中CPU的两种工作状态

  • 处于用户态的CPU访问内存的能力受到限制，不能访问外围设备，也不能被正在运行的程序独占

  • 处于内核态的CPU访问内存的能力不受限制，可以访问任何设备，也可以被正在运行的程序独占

• 将CPU的工作状态分为用户态和内核态，主要是出于安全性的考虑。诸如设置时钟、清理内存之类的敏感操作，都必须在内核态完成，如果将这些操作放到用户态，系统很可能因频繁崩溃而变得极不稳定

25 用户态和内核态是如何切换的？

• 当一个程序处于用户态时，它的能力是受限的。一些比较重要的操作，如读写磁盘数据等，只有进入内核态才能执行。因此，程序经常需要在用户态和内核态之间来回切换

• 使一个程序进入内核态的唯一方法就是执行系统调用。在系统调用执行期间，程序处于内核态。随着系统调用的返回，程序又回到用户态。程序在用户态和内核态间切换过程如下：

  • 用户代码调用某个系统调用函数。该函数将系统调用标识保存在EAX寄存器中，将调用者提供的参数压入栈中，同时触发80H中断

  • 系统内核针对80H中断的中断处理函数被执行。该函数将触发中断的程序从用户态切换至内核态，从栈中弹出之前压入的参数，从EAX寄存器中获取之前保存的系统调用标识，并从系统内核维护的系统调用表中查找与该标识相对应的内核函数入口地址，调用该函数，传入参数，并获得返回值，最后再将触发中断的程序从内核态切换回用户态

  • 用户代码继续中断触发前的执行过程，从系统调用函数中返回

26 进程的终止方式都有哪些？

• 正常终止

  • 从main函数中返回0

  • 以0为参数调用exit、_exit或_Exit函数

• 异常终止

  • 从main函数中返回非0

  • 以非0值为参数调用exit、_exit或_Exit函数

  • 在主线程中调用pthread_cancel函数

  • 调用abort函数

• 被系统杀死

  • 当进程执行了某些在系统看来具有危险性的操作，或系统本身发生了某种故障或意外，内核会向相关进程发送特定的信号

  • 如果进程无意针对所收到的信号采取补救或预防措施，那么内核将按缺省方式将进程杀死，并视情形生成核心转储文件（core文件）以备事后分析，俗称吐核

• 被其它进程杀死

  • 通过键盘、kill命令或其它程序向目标进程发送特定的信号

  • 收到信号的进程，或按缺省方式，或按自定义方式，退出运行

27 什么是僵尸进程、孤儿进程和守护进程？

• 僵尸进程：如果子进程先于父进程终止，但父进程由于某种原因，没有回收子进程的退出状态，子进程即成为僵尸进程。僵尸进程虽然已经不再活动，但其终止状态仍然保留，也会占用系统资源，直至被回收才得以释放

• 孤儿进程：如果父进程先于子进程终止，子进程即成为孤儿进程，同时被init进程收养，即成为init进程的子进程，因此init进程又被称为孤儿院进程

• 守护进程：特殊的孤儿进程，在系统后台持续运行，周期性地执行某种任务

  • 独立于创建者进程的会话、进程组和控制终端

  • 不能打开任何终端

  • 不持有多余的文件描述符

  • 权限掩码为0

  • 以系统的根目录为当前工作目录

28 如何避免僵尸进程？

• 方法一：显式忽略（SIG_IGN）子进程终止信号（SIGCHLD），由系统内核自动回收子进程

• 方法二：在父进程中调用wait或waitpid函数，等待子进程终止并回收之

• 方法三：在父进程中捕获子进程终止信号（SIGCHLD），在信号处理函数中通过wait或waitpid回收子进程

• 方法四：先fork一个儿子进程，再在儿子进程中fork一个孙子进程，儿子进程随即终止并被其父进程回收，孙子进程成为孤儿进程，由init进程负责回收

29 常见的与内存有关的编程错误都有哪些？

• 直接使用未经确认有效的内存

  • 在任何以指针作为输入参数的函数中，先检查其指针参数是否为空指针

  • 调用malloc、calloc、realloc、alloca等函数分配内存，注意检查其返回的指针是否为空指针

  • 通过new操作符分配内存或创建对象，注意捕获bad_alloc异常

• 直接使用未经初始化的内存

  • 一段内存的默认初值并没有统一的标准，不能假定其一定是零值

• 超过有效内存的边界

  • 任何时候，对有效内存边界以外区域的访问，结果都是未定义的

  • 小心地使用数组下标，和指针与整数的加减运算

• 未释放动态分配的内存，形成内存泄漏

  • malloc/calloc/realloc和free必须成对出现

  • new和delete/delete[]必须成对出现

  • 在因错误发生而不得不提前返回或抛出异常时，注意检查之前分配成功的内存有没有释放干净

• 继续使用或重复释放已被释放的内存

  • 释放内存后，及时将指针置空，使用或释放前先检查其是否为空

  • 不要从函数中返回指向栈内存的指针或引用，因为栈内存会随着函数的返回而被自动释放

  • 当存在多个对象共享同一块内存时，注意该内存的生命周期管理，小心悬空指针和重析构

30 在内存交换的过程中，被换出的内存去了哪里？

• 在内存交换的过程中，被换出的内存数据，保存在诸如硬盘等辅助存储器的，交换分区或换页文件中

• 辅助存储器通常用于存放文件和被换出的内存数据

  • 文件存储，追求的是空间效率，即最大程度地利用存储空间，故采用离散存储的方式

  • 页面交换，追求的是时间效率，即最大程度地缩短存取时间，故采用连续存储的方式

• 面向交换分区或换页文件的换入换出速度，要远快于面向普通文件区域的读取和写入

31 原子操作是如何实现的？

• 非原子操作导致的并发冲突问题（以i++为例）

  • 处理器对内存中的变量i执行自增操作的步骤

    • 第一步：通过地址总线和数据总线，将变量i所在内存区域中的数值，读到处理器内部的缓存中

    • 第二步：对处理器内部缓存中的数值执行加一操作

    • 第三步：通过地址总线和数据总线，将处理器内部缓存中的数值，写到变量i所在的内存区域中

  • 以上三步在非原子条件下，将发生并发冲突

    处理器1	处理器2
    通过总线，将变量i的值0读到缓存中	通过总线，将变量i的值0读到缓存中
    对缓存中的值执行加一操作，0变成1	对缓存中的值执行加一操作，0变成1
    通过总线，将缓存中的1写到变量i中	通过总线，将缓存中的1写到变量i中

  • 两个处理器各执行一次i++，i的值却并不是2而是1，这就是并发冲突

• 处理器借助总线锁和缓存锁保证特定操作的原子性

  • 总线锁

    • 一个处理器在执行第一步前先对总线加锁，其它处理器的总线操作将被阻塞，直到持有锁的处理器在执行完第三步后对总线解锁，其它处理器才能从阻塞中恢复对总线的操作

    • 在总线被锁定期间，其它处理器不仅不能访问变量i所在的内存，对其它内存的访问也会被阻塞。因此，总线锁对并发性的破坏比较显著，开销比较大，性能比较差

  • 缓存锁

    • 一个处理器在执行第一步前先对缓存加锁，其它处理器中对该内存的缓存操作将被阻塞，直到持有锁的处理器在执行完第三步后对缓存解锁，其它处理器才能从阻塞中恢复对该内存的缓存操作

    • 在缓存被锁定期间，其它处理器只是不能操作与变量i所在内存相对应的缓存，对与其它内存相对应缓存的操作不受任何影响。因此，缓存锁对并发性的破坏比较轻微，开销比较小，性能比较好

  • 在以下两种情况下，不能使用缓存锁，只能使用总线锁

    • 无法将被操作数据缓存在处理器内部，或被操作数据需要跨越多个缓存行

    • 某些处理器，如Intel 486和Pentium处理器，不支持缓存锁

32 什么是页面抖动？

• 刚刚换出的内存页马上又要换入，刚刚换入的内存页马上又要换出，这种频繁的页面调度操作称为页面抖动，或页面颠簸

• 产生页面抖动的主要原因是进程频繁访问的页面数高于主存储器中的可用页面数，即分配给进程的主存储器页面数太少

• 分配给进程的主存储器页面数太少，会导致页面抖动，而分配给进程的主存储器页面数太多，又会削弱系统的整体并发性。为此Denning提出了所谓进程工作集的概念

33 用fork产生的子进程能否共享父进程的全局变量？

• 通过fork创建的子进程会复制父进程除代码区以外的全部内存

• 一个全局变量在父子进程间拥有相同的虚拟内存地址，但被分别映射到彼此独立的物理内存区域

• 用fork产生的子进程无法共享父进程的全局变量，父子进程间的数据交换需要借助于专门的进程间通信机制

• 一个进程的所有线程共享其隶属进程的内存空间，因此子线程可以共享父线程的全局变量

34 某磁盘文件中包含4G个long类型的整数，如何从中找出前N个最大的整数？

• 将磁盘文件中的4G个long类型整数一次性读取到内存中，再从中找出前N个最大的整数，是不现实的

• 比较可行的做法，是分多次读取文件，每次只读取少量数据，并在每次读取后找出其中前N个最大的整数

• 最后将每次得到的N个值汇集到一起，从中找出前N个最大的整数