操作系统

进程和线程的区别

• 进程是具有一定功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源调度和分配的一个独立单位。
• 线程是进程的实体，是CPU调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。
• 一个进程可以有多个线程，多个线程也可以并发执行

线程同步

互斥量：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。

信号量：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。

事件（信号）：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。

进程通信

主要分为：管道、系统IPC（包括消息队列、信号量、共享存储）、SOCKET

管道主要分为：普通管道PIPE 、流管道（s_pipe）、命名管道（name_pipe）

• 管道是一种半双工的通信方式，数据只能单项流动，并且只能在具有亲缘关系的进程间流动，进程的亲缘关系通常是父子进程
• 命名管道也是半双工的通信方式，它允许无亲缘关系的进程间进行通信
• 信号量是一个计数器，用来控制多个进程对资源的访问，它通常作为一种锁机制。
• 消息队列是消息的链表，存放在内核中并由消息队列标识符标识。
• 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
• 共享内存就是映射一段能被其它进程访问的内存，这段共享内存由一个进程创建，但是多个进程可以访问。

缓冲区溢出

计算机向缓冲区填充数据时超出了缓冲区本身的容量

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

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

死锁产生的条件

两个或多个进程无限期的阻塞、相互等待的一种状态。

死锁产生的四个条件（有一个条件不成立，则不会产生死锁）

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

死锁的处理基本策略

预防死锁：（严重地损害系统性能）
资源一次性分配：（破坏请求和保持条件）
可剥夺资源：即当某进程新的资源未满足时，释放已占有的资源（破坏不可剥夺条件）
资源有序分配法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反（破坏环路等待条件）

避免死锁：
由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。

检测死锁：
首先为每个进程和每个资源指定一个唯一的号码；
然后建立资源分配表和进程等待表

进程状态

• 就绪状态：进程已获得除处理机以外的所需资源，等待分配处理机资源
• 运行状态：占用处理机资源运行，处于此状态的进程数小于等于CPU数
• 阻塞状态： 进程等待某种条件，在条件满足之前无法执行

进程调度

FIFO或First Come, First Served (FCFS)先来先服务

• 调度的顺序就是任务到达就绪队列的顺序。
• 公平、简单(FIFO队列)、非抢占、不适合交互式。
• 未考虑任务特性，平均等待时间可以缩短。

Shortest Job First (SJF)

• 最短的作业(CPU区间长度最小)最先调度。
• SJF可以保证最小的平均等待时间。

Shortest Remaining Job First (SRJF)

• SJF的可抢占版本，比SJF更有优势。
• SJF(SRJF): 如何知道下一CPU区间大小？根据历史进行预测: 指数平均法。

优先权调度

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

时间片轮转

• 设置一个时间片，按时间片来轮转调度（“轮叫”算法）
• 优点: 定时有响应，等待时间较短；缺点: 上下文切换次数较多；
• 时间片太大，响应时间太长；吞吐量变小，周转时间变长；当时间片过长时，退化为FCFS。

多级队列调度

• 按照一定的规则建立多个进程队列
• 不同的队列有固定的优先级（高优先级有抢占权）
• 不同的队列可以给不同的时间片和采用不同的调度方法
• 存在问题1：没法区分I/O bound和CPU bound；
• 存在问题2：也存在一定程度的“饥饿”现象；

多级反馈队列调

• 进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
• 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
• 对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
• 在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。

进程同步

原子操作、信号量机制、自旋锁管程、会合、分布式系统

分页和分段的区别

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

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

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

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

虚拟内存

先将部分程序导入内存，执行完成后导入下一部分程序，给我们的感觉是内存变大了，实际上物理内存的大小并未发生变化。

虚拟内存的优点：将逻辑内存和物理内存分开。虚拟内存允许文件和内存通过共享页而为两个或多个进程所共享。

最佳置换算法（OPT）

这是一种理想情况下的页面置换算法，但实际上是不可能实现的。该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可 [1] 以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。 [1]

先进先出置换算法（FIFO）

最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。

这种算法只是在按线性顺序访问地址空间 [1] 时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。

FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。

最近最久未使用（LRU）算法

FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。

LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。