目录

一. 页面置换算法

1.最优页面置换算法（OPT）

2.先进先出算法（First-In-First-Out，FIFO）

3.最近最久未使用算法（Least Recently Used，LRU）

4.改进的时钟（Clock）页面置换算法

5.页面缓冲算法（PBA）

二. 进程与线程

【问题】进程与程序的区别

【问题】进程与线程的区别

【问题】进程的通信方式

【问题】线程的通信方式

【问题】进程死锁的四个条件

三. Linux进程调度算法

1.先来先服务（FCFS）

2.短作业优先算法（SJF/SPN）

3.高响应比优先（High Response Rotio Next，HRRN）

4.时间片轮转（Round Robin，RR）

5.多级反馈队列（MLFQ）

四. 虚拟内存

【问题】虚拟内存解决了什么？

【问题】用户态和内核态的区别

【问题】用户态如何切换到内核态？

一. 页面置换算法

        当缺页中断发生时，需要调入新的页面而内存已满时，此时就需要用到页面置换算法选择出一个合适的页面（不再使用的或短期内不会被使用的页面）进行置换，来尽可能的减少页面的换进换出次数。

1.最优页面置换算法（OPT）

        当一个缺页中断发生时，对于保存在内存中的每一个逻辑页面，计算在它的下一次访问之前，还需等待多长时间，从中选择时间最长的那个，作为被置换的页面。

        这只是一个理想状况，在实际系统中方是无法实现的，因为操作系统无从知道一个页面要等多长时间后才会再次被访问。

        可用作其他算法的性能评价依据（在一个模拟器上运行某个程序，并记录每一次的页面访问情况，在第二遍运行时即可采用最优算法）。

2.先进先出算法（First-In-First-Out，FIFO）

        选择内存中驻留时间最长的页面并淘汰之。具体说，系统维护者一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短，当发生一个缺页中断时，将链首页面淘汰出局，并把新的页面添加到链表的末尾。

       但性能较差，调出的页面可能是经常访问的页面，因此FIFO很少单独使用。

3.最近最久未使用算法（Least Recently Used，LRU）

当发生一个缺页中断时，选择最久未被使用的页面，淘汰之。

4.改进的时钟（Clock）页面置换算法

与LRU近似，是对FIFO的一种改进，基本思路是：

需要用到页表中的访问位（读位和写位），将一个页面装入内存时，把读位和写位初始化为0。然后如果这个页面被读或写时，则把对应位置为1；

把各个页面组织成环形链表（类似于钟表面），把指针指向最老的页面（最先进来）；

当发生一个缺页中断时，考察指针所指向的页面，若读写位均为0，立即淘汰；若没有，则找读位为1，写位为0的将其淘汰；若读写位均为1，则将读写位更新为0，指针往下移动一格。如此下去，直到找到淘汰的页面，然后把指针移动到它的下一格。

5.页面缓冲算法（PBA）

        设立空闲页面链表和已修改页面链表。采用可变分配和基于先进先出的局部置换策略，并规定被淘汰页先不做物理移动，而是依据是否修改，分别挂到空闲页面链表或已修改页面链表的末尾；空闲页面链表同时用于物理块分配。当已修改页面链表达到一定长度如Z个页面时，一起将所有已修改页面写回磁盘，故可显著减少磁盘I/O操作次数

PS：以上图片均来自于陈渝老师的操作系统原理

二. 进程与线程

        进程（Process）是一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程，是系统进行资源分配和调度的基本单位。一个程序至少有一个进程。

       线程（Thread）是进程中的一条执行流程，是比进程更小的能独立运行的基本单位。一个进程至少有一个线程

【问题】进程与程序的区别

1.进程是动态的，程序是静态的；程序是有序代码的集合；进程是程序的执行，进程有核心态/用户态

2.进程是暂时的，程序是永久的；进程是一个状态变化的过程，程序可以长久保存

3.进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）

借用陈渝老师一个很经典的栗子：

有一个计算机科学家，想亲手给女儿做一个生日蛋糕。所以他就找了一本有关做蛋糕的食谱，买了一些原料，面粉、鸡蛋、香料等，然后边看边学边做。

其中食谱=程序；科学家=CPU；原料=数据；做蛋糕=进程

这时小儿子哭着跑进来，说手被蜜蜂蛰了。科学家只好把蛋糕先放一边。他在食谱上做了个标记，把状态信息记录了起来。

然后又去找了一本医疗手册，查到了相关的内容，按照上面的指令一步步地执行。当伤口处理完之后，又回到厨房继续做蛋糕。

这里说明了CPU可以从一个进程（做蛋糕）切换到另一个进程（处理儿子的伤口）。

【问题】进程与线程的区别

1.进程是资源分配单位，线程是CPU调度单位

2.进程拥有一个完整的资源平台（虚拟空间），而线程只独享必不可少的资源，如寄存器和栈

3.一个进程中的各个线程共享内存和文件资源，因此线程切换代价比进程低

4.一个线程可以创建和撤销另一个线程，同一个进程中的多个线程之间可以并发执行

5.一旦进程中的一个线程瘫痪，会导致其所属进程的所有线程崩溃

【问题】进程的通信方式

1.信号量：一个计数器，实现进程间的互斥与同步，而不是用于存储进程间通信数据。主要作为进程间以及同一进程内不同线程之间的同步手段

2.管道：匿名管道用于具有亲缘关系的进程之间的通信，数据只能在一个方向上流动；命名管道可以在无关的进程之间交换数据

3.消息队列：消息的链接表。只有有足够权限的进程可以向队列中添加信息，被赋予读权限的进程则可以读走队列中的消息；消息队列克服了管道信息量少的缺点

4.共享内存：使得多个进程可以访问同一块内存空间；针对其他通信方式运行效率较低而设计的，往往与其他通信方式如信号量结合使用，到达进程间的同步于互斥

4.套接口（socket）：用于不同机器之间的进程间通信

【问题】线程的通信方式

1.锁机制：互斥锁、条件变量、读写锁

互斥锁提供了以排他方式防止数据结构被并发修改的方法。

条件变量可以以原子的方式进行阻塞进程，知道某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。

读写锁允许多个线程同时读共享数据，而对写操作是互斥的。

2.信号量机制：无名线程信号量、命名线程信号量

3.信号机制：类似进程间的信号处理

线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制。

【问题】进程死锁的四个条件

1.互斥条件：资源是独占的且排他使用，进程互斥使用资源，即任意时刻一个资源只能给一个进程使用，其他进程若申请一个资源，而该资源被另一进程占有时，则申请者等待直到资源被占有者释放。

2.不可剥夺条件：进程所获得的资源在未使用完毕之前，不被其他进程强行剥夺，而只能由获得该资源的进程资源释放。

3.请求和保持条件：进程获得一定的资源之后，又对其他资源发出请求，但是该资源可能被其他进程占有，此事请求阻塞，但又对自己获得的资源保持不放。

4.循环等待条件：在发生死锁时必然存在一个进程等待队列{P1,P2,…,Pn},其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路，环路中每一个进程所占有的资源同时被另一个申请，也就是前一个进程占有后一个进程所深情地资源。

三. Linux进程调度算法

       进程调度也称为低级调度（CPU调度），是按照某种调度算法（或原则）从就绪队列中选取进程分配CPU,主要是协调对CPU的争夺使用。

       在操作系统中，由于进程综述多于处理机，它们必然竞争处理机，为了充分利用计算机系统中的CPU资源，让计算机系统能够多快好省地完成我们让它做的各种任务，所以需要进程调度。

1.先来先服务（FCFS）

顾名思义，如果进程在执行中阻塞，按到达顺序，队列中的下一个进程会得到CPU。

        这个调度算法比较简单，但是平均等待时间波动较大，花费时间少的任务可能排在花费时间长的任务后面，可能导致I/0和CPU之间的重叠处理，CPU密集型进程会导致I/0设备闲置时，I/0密集型进程也在等待，因此引入短作业优先算法。

2.短作业优先算法（SJF/SPN）

按照进程完成时间进行排序

        该算法的平均等待时间最优，但是连续的短作业流会使长作业饥饿，短作业可用时，任何长作业的CPU时间都会增加平均等待时间。

3.高响应比优先（High Response Rotio Next，HRRN）

       在短作业的基础上进行了改进，在队列中选取优先权最高的进程装入内存。进程的优先级用于表示进程的重要性及运行的优先性。R=（W+S）/ S，其中W是等待时间，S是执行时间，此调度算法选择队列中R最大的进程。

4.时间片轮转（Round Robin，RR）

        RR调度算法定义了一个的时间单元，称为时间片（或时间量）。一个时间片通常在1～100 ms之间。当正在运行的进程用完了时间片后，即使此进程并未执行结束，操作系统也不让它继续运行，而是选择队列中的下一个进程运行。在这个过程中短作业的进程可能在一个时间片内就执行结束了，然后让队列中的下一个进程运行。这样就会非常公平让每一个进程都有机会运行。

        但是这个时候就需要选取合适的时间片，因为如果时间片过大的话，下一个进程的等待时间就会变长，严重的话将退化成FCFS算法；如果时间片过小的话，虽然反应迅速，但是会导致吞吐量由于大量的上下文切换开销受到影响。

5.多级反馈队列（MLFQ）

        在时间片轮转算法的基础上进行的改进，将就绪队列分为两个不同的队列：例如前台（交互）和后台（批处理），每个队列选取自己合理的调度算法；并且每个队列的优先级逐渐降低，同时每个队列的执行时间也各不相同，优先级越高的队列，执行时间越短，优先级越低的队列，执行时间越长。

四. 虚拟内存

【问题】虚拟内存解决了什么？

       电脑中所运行的程序均需经过内存执行，若执行的程序占用的内存很大很多，则会导致内存消耗殆尽，为解决该问题，WINDOWS运用了虚拟内存技术，即拿出一部分硬盘空间来充当内存使用，这部分空间即称为虚拟内存。

       虚拟内存让每个进程都拥有了独立的地址空间，虚拟地址空间划分为多个固定大小的虚拟页(Virtual Page, VP)，物理地址空间划分为多个固定大小的物理页(Physical Page, PP), 通常虚拟页大小等于物理页大小，这样简化了虚拟页和物理页的映射。

推荐博客：计算机底层知识拾遗（一）理解虚拟内存机制

【问题】用户态和内核态的区别

       当一个任务（进程）执行系统调用而陷入内核代码中执行时，我们就称进程处于内核运行态（或简称为内核态）。此时处理器处于特权级最高的（0级）内核代码中执行。当进程处于内核态时，执行的内核代码会使用当前进程的内核栈。每个进程都有自己的内核栈。

       当进程在执行用户自己的代码时，则称其处于用户运行态（用户态）。即此时处理器在特权级最低的（3级）用户代码中运行。

       不管对于Linux还是Windows， 他们都具有自己用户空间和内核空间。当一个程序运行时，如果它是在用户空间下执行，我们把此时运行得程序的这种状态成为用户态，而当这段程序执行在内核的空间执行时，这种状态称为内核态。

【问题】用户态如何切换到内核态？

       由于需要限制不同的程序之间的访问能力, 防止他们获取别的程序的内存数据, 或者获取外围设备的数据, 并发送到网络, CPU划分出两个权限等级 – 用户态和内核态。而要从用户态切换到内核态的方式为：

1.系统调用。用户态进程主动要求切换到内核态的一种方式；用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作，比如前例中fork()实际上就是执行了一个创建新进程的系统调用；

2.异常。当CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。

3.外围设备的中断。当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。