计算机专业保研面试复习笔记：
计算机专业保研面试复习笔记——数据结构中的重要算法
计算机专业保研面试复习笔记——数据库
计算机专业保研面试复习笔记——操作系统
计算机专业保研面试复习笔记——计算机网络

---

---

死锁

定义

多个进程因循环等待资源而造成无法执行的现象

原因

进程互相申请对方占有的资源

条件

• 互斥：至少有一个资源必须处于非共享模式，即一次只有一个进程可使用。如果另一进程申请该资源，那么申请进程应等到该资源释放为止。

• 持有并等待：一个进程应占有至少一个资源，并等待另一个资源，而该资源为其它进程所占有。

• 非抢占：资源不能被抢占，即资源只能被进程在完成任务后自愿释放。

• 循环等待：进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

处理方法

死锁预防

通过限制申请资源来避免死锁

• 通过破坏“互斥”条件：

  • 部分锁是“只读”的，即不是互斥的。

• 通过破坏“持有并等待”条件：

  • 每个进程执行前申请并获得所有资源。
  • 进程仅在没有资源时才可申请资源。

• 通过破坏“无抢占”条件：

  • 如果一个进程持有资源并申请另一个不能立即分配的资源，那么它现在分配的资源可以被抢占。

• 通过破坏“循环等待”条件：

  • 为资源设定顺序，必须先申请到顺序靠前的资源，才能申请顺序靠后的资源。

死锁避免

针对每次申请要求，系统在做决定时考虑现有可用资源、现已分配给每个进程的资源和每个进程将来申请与释放资源。

死锁检测

检测系统中是否有死锁。

死锁恢复

通过终止进程/抢占资源来恢复死锁。

银行家算法

用于资源分配，防止出现死锁的情况。

需要如下数据结构协助完成算法：

• n为系统进程的数量，m为资源类型的种类。

• available 长度为m的向量，表示每种资源的可用实例数量。

• max n*m矩阵，定义每个进程的最大需求。

• allocation n*m矩阵，定义每个进程现在分配的每种资源类型的实例数量。

• need n*m矩阵，表示每个进程还需要的剩余资源。

利用每次每个进程的请求资源数量和剩余资源、可用资源做比较，确定新的资源分配是否安全。

---

进程

概念

操作系统执行一个程序的过程，不止是程序代码，还包括当前活动，如程序计数器的值和处理寄存器的内容等。

特点

第一，进程是一个实体。每一个进程都有它自己的地址空间，一般情况下，包括文本区域（text region）、数据区域（data region）和堆栈（stack region）。

文本区域存储处理器执行的代码；

数据区域存储变量和进程执行期间使用的动态分配的内存；

堆栈区域存储着活动过程调用的指令和本地变量。

第二，进程是一个“执行中的程序”。程序是一个没有生命的实体，只有处理器赋予程序生命时，它才能成为一个活动的实体，我们称其为进程。

基本状态

• 等待态：等待发生某个事件
• 就绪态：等待分配处理器
• 运行态：正在占用处理器

状态转换

运行态->等待态： 等待外设、等待主存等资源分配或等待人工干预

等待态->就绪态： 等待条件已经满足，分配到处理器就可以运行了

就绪态->运行态： 系统按某种策略选中就绪队列中的一个进程占用处理器，占用后就变成了运行态

运行态->就绪态： 不是由于自身原因，是因为外界原因使运行状态的进程让出处理器，变成了就绪态。

进程与程序的区别

• 程序作为一个静态文件存储在计算机系统的硬盘等存储空间中
• 进程是处于动态条件下由操作系统维护的系统资源管理实体

进程控制块（PCB）

包含许多与某个特定进程相关的信息，相当于这些信息的仓库：

• 进程状态：包括就绪、运行、停止、等待等。
• 程序计数器：计数器表示进程将要执行的下一个指令的地址。
• CPU寄存器：包括堆栈指针、通用寄存器等。
• CPU调度信息：包括进程优先级，调度队列的指针等。
• 内存管理信息：基地址、界限寄存器的值、页表或段表。
• 记账信息：包括CPU时间、实际使用时间等。
• I/O状态信息：包括分配给进程的I/O设备列表、打开文件表。

进程调度

FIFO/FCFS 先进先出：调度顺序是人物到达就绪队列的顺序。

SJF（Shortest Job First）：最短的作业(CPU区间长度最小)最先调度。SJF可以保证最小的平均等待时间。

**优先权调度：**每个任务关联一个优先权，调度优先权最高的任务。注意：优先权太低的任务一直就绪，得不到运行，出现“饥饿”现象。

Round-Robin(RR) 轮转调度：设置一个时间片，每次轮到这个进程时分配不超过一个时间片的CPU。优点: 定时有响应，等待时间较短；缺点: 上下文切换次数较多；

多级队列调度：按照一定的规则建立多个进程队列。不同的队列有固定的优先级（高优先级队列可以抢占低优先级队列）。不同的队列可以给不同的时间片和采用不同的调度方法。

多级反馈队列：在多级队列的基础上，任务可以在队列之间移动，更细致的区分任务。

进程间通信

管道

管道是最基本的进程通信机制。可以想象成一个管道，两端分别连着2个进程，一个进程往里面写，一个进程从里面读。如果读或写管道的时候没有内容可供读或写，进程将被阻塞，直到有内容可供读写为止。

管道分为匿名管道（普通管道）和命名管道。

• **匿名管道（普通管道）**创建后本质上是2个文件描述符，父子进程分别持有就能够使用管道。只允许单向通信。

• 命名管道是根据路径来使用管道，故能够在任意进程间通信。

消息队列

消息队列本质上是开辟了一块内存空间，这块内存是其他进程可以访问到的，在其中使用链表的方式实现了一个队列，进程可以向该队列中发送数据块或者读取数据块，从而达到进程间通信的目的。

信号量

专门用于解决进程同步与互斥问题的一种通信机制，说明可用资源的数量。

P操作

对信号量-1，进程在使用资源之前声明“自己将占有一份资源”。

V操作

对信号量+1，使用完资源后归还时声明“我完成了”。

二值信号量

如果资源只有一份，那么信号量的初始值将是1，最多只能有一个进程使用该资源。这种信号量被称为“二值信号量”。

共享内存

本质是把两个或多个进程的虚拟地址映射到同一块物理内存。这样，一个进程通过对这块内存的读写就能被其他进程访问到，从而实现进程通信的功能。

互斥锁

可以使用互斥锁解决临界区问题。

采用互斥锁保护临界区，一个进程在进入临界区时调用acquire()获得锁，在退出临界区时调用release()释放锁。

当一个进程试图获取不可用的锁时，它会阻塞，连续循环的调用acquire()，这叫做忙等待。这种类型的锁也被称为自旋锁，因为进程不停地旋转，以等待锁变得可用。

---

线程

概念

是系统调度的最小单位。包括线程ID、程序计数器、寄存器组合堆栈。没有独立的系统资源，与同一进程的其他线程共享代码段、数据段和其他操作系统资源。

内核线程

调度器在内核中，内核负责创建和调度。

用户线程

调度器在用户空间。用户线程的创建和调度都是由上层的应用程序使用线程库的方式来完成的，内核并不知道。

轻量级进程（LWP）

Linux使用轻量级进程实现线程这个概念。在linux中，当一个进程与其他进程共享资源时，它就是轻量级进程，如果独享资源，那么它就是进程。

进程和线程的区别

概念

进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动。进程是系统进行资源分配和调度的一个独立单位。

线程是进程的一个实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。

资源

进程独立拥有系统资源。

线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器，一组寄存器和栈），但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。

线程同步

互斥锁

与进程互斥锁相同。

条件变量

使用条件变量控制线程同步时，线程访问共享资源的前提是程序中设置的条件变量得到满足。条件变量不会对共享资源加锁，但也会使线程阻塞。若条件变量规定的条件不满足，线程就会进入阻塞状态直到条件满足。

信号量

与进程信号量相似。

信号

通过通知操作的方式来保持多线程同步。

---

缓冲区溢出

什么是缓冲区溢出？

缓冲区溢出是指当计算机向缓冲区填充数据时超出了缓冲区本身的容量，溢出的数据覆盖在合法数据上。

有什么危害？

• 程序崩溃，导致拒绝服务
• 跳转并且执行一段恶意代码

其原因是什么？

造成缓冲区溢出的主要原因是程序中没有仔细检查用户输入。

分页和分段有什么区别

1、段是信息的逻辑单位，它是根据用户的需要划分的，因此段对用户是可见的 ；页是信息的物理单位，是为了管理主存的方便而划分的，对用户是透明的。

2、段的大小不固定，有它所完成的功能决定；页大大小固定，由系统决定

3、段向用户提供二维地址空间；页向用户提供的是一维地址空间

4、段是信息的逻辑单位，便于存储保护和信息的共享，页的保护和共享受到限制。