线程与进程区别

1. 简而言之,一个程序至少有一个进程,一个进程至少有一个线程.

2. 线程的划分尺度小于进程，使得多线程程序的并发性高。

3. 另外，进程在执行过程中拥有独立的内存单元，而多个线程共享内存，从而极大地提高了程序的运行效率。

4. 线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。

5. 从逻辑角度来看，多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理以及资源分配。

内存碎片

内存碎片分为：内部碎片和外部碎片。

内部碎片就是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间；

内部碎片是处于区域内部或页面内部的存储块。占有这些区域或页面的进程并不使用这个存储块。而在进程占有这块存储块时，系统无法利用它。直到进程释放它，或进程结束时，系统才有可能利用这个存储块。

单通道连续分配：内存分为系统区和用户区，系统区在低地址部分，剩余为用户区。仅用于单用户单任务。

多道固定分配：内存划分为多个固定大小的块，每个分区只装一道作业。当有空闲分区，从外存装入适合大小的作业进该分区。

单道连续分配只有内部碎片。多道固定连续分配既有内部碎片，又有外部碎片。

外部碎片指的是还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。

外部碎片是出于任何已分配区域或页面外部的空闲存储块。这些存储块的总和可以满足当前申请的长度要求，但是由于它们的地址不连续或其他原因，使得系统无法满足当前申请。

死锁

条件

（一）互斥条件：一个资源一次只能被一个进程访问。即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占 有。这种独占资源如CD-ROM驱动器，打印机等等，必须在占有该资源的进程主动释放它之后，其它进程才能占有该资源。这是由资源本身的属性所决定的。

（二）请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。

（三）不剥夺条件：进程已经获得的资源，在未使用完之前不能强行剥夺，而只能由该资源的占有者进程自行释放。

（四）循环等待条件：若干资源形成一种头尾相接的循环等待资源关系。

解决

银行家算法

安全序列：是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。

数据结构：
1）可利用资源向量Available
含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。
2）最大需求矩阵Max
一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
3）分配矩阵Allocation
一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的 数目为K。
4）需求矩阵Need
一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

其中有：Need[i,j]=Max[i,j]-Allocation[i,j]

Request(i)是进程Pi的请求量，如果Request(i)[j]=k，则进程Pi需要k个j类资源，当Pi发生请求时

《1》如果Request(i)[j]<=Need[i,j]，转《2》，否则认为出错。
《2》如果Request(i)[j]<=Availbale[i,j]，转3，否则表示资源不够，进程Pi需等待
《3》分配资源并修改对应的值，Availabel[i,j]-=Request(i)[j]，Allocation[i,j]+=Request(i)[j] ,Need[i,j]-=Request(i)[j]

判断安全序列时通过查看Available所能满足的进程Pi的Need[i,…]，若能满足就让Available+Allocation[i,…]，因为当前资源满足进程Pi的需求，可令其执行完毕。再去检查其他进程的Need是否当前Available可满足，满足即加上Allocation，直到当前所有进程都能满足时，这些进程有一个安全序列。

内存页面置换算法（图自知乎）

OPT

理想置换算法，从主存中移除以后不再需要的页面，如果不存在这样的页面，则移除未来最长时间不需要访问的页面。因为未来访问情况无法预测，所以为理想算法。

FIFO

选择内存中驻留最长时间的页面做替换。操作系统维护一个内存页面链表，从链表顺序来看，链表首部驻留时间最长，尾部最短，缺页时置换掉链表首部的页面。

LRU

替换掉从开始到现在最久没被使用过的，操作系统维护一个链表，需要访问链表中的页面时，把该页面移动到链表首部；发生缺页时，移除掉链表尾部页面，新页面加入链表首。

(后续更新)