操作系统面试知识点整理

绝地灬酷狼 2022-05-19 04:13 286阅读 0赞

**目录**

1. 内存的页面置换算法

2. 进程调度算法

3. 进程间通信方式

4. 进程线程区别

5. 父子进程、孤儿进程

--------------------

### 1. 内存的页面置换算法 ###

地址映射过程中，如果页面中发现所要访问的页面不在内存中，则产生缺页中断，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出，以便为即将调入的页面让出空间。而**用来选择淘汰哪一页的规则叫做页面置换算法**。

1.  最佳置换算法（OPT）(理想置换算法)：从当前位置看后面的页面引用串，选择最长时间不需要被访问的页面来进行置换。最好是选择以后永远都不需要再使用的页面，这样可以保证最低的缺页率。（OPT算法可以用来评价其他算法）
2.  先进先出置换算法（FIFO）：最简单的页面置换算法。基本思想是，选择驻留内存时间最长的页面进行置换，也就是先进先出。就相当于一个队列，当页面在队列里排满时，将队列头部的页面取出，置换成新的页面，但需要注意的是新的页面将置于队尾的位置。（FIFO算法会出现Belady异常：当所分配的物理块数增大时缺页次数不减反增的异常现象）
3.  最近最久未使用算法（LRU）：基本思想是利用局部性原理，当一个页面在最近的访问历史中最久未被使用时，我们推测它未来使用的可能性也很小，因此将其进行置换。实现原理：将使用的页面放入一个链表，当再次访问某一页面时，将其放置尾部。置换时从头部开始置换，即置换最老的且未被重新访问过的页面。（ LRU 的性能最好，但是需要寄存器和硬件的支持。LRU 是堆栈类的算法，不会出现Belady现象。）
4.  第二次机会算法：将被访问的页面装入一个链表，并设置一个R位，头部为最先进入链表的，当页面被访问时，将其R 位设置为1；在选择置换页面时，当头部的页面R值为0，则被置换；若为1，则将R设置为0，并分析链表下一个页面。新装入的页面，R为0，并放在链表尾部。（其实和LRU的原理一样，但增加了一个R位指标，所以不需要经常更换链表顺序）
5.  时钟（ CLOCK ）置换算法： 使用环形链表将页面链接起来，并使用指针指向最老的页面。

### 2. 进程调度算法 ###

1. 先来先服务（FCFS， first come first served）

**算法原理**：进程按照请求 CPU 的顺序进入队列，先来的进程先执行，执行的过程中不会被其他进程中断。

**算法优点**：易于理解且实现简单，只需要一个队列（FIFO），且相当公平。

**算法缺点**：比较有利于长进程，不利于短进程，有利于CPU繁忙的进程，不利于I/O繁忙的进程。

2. 最短作业优先（SJF， shortest job first），目标是减少平均周转时间

**算法原理**：对预计执行时间短的进程优先分配CPU，通常后来的短进程不抢先正在执行的进程。

**算法优点**：相比于FCFS，改善了平均周转时间，缩短进程的等待时间，提高系统的吞吐量。

**算法缺点**：对长进程非常不利，且有时估计进程准确的执行时间也比较难。

3. 最高响应比优先（HRRN, highest prsponse ratio next），介于FCFS 和 SJF 之间的一种折中算法，既考虑了每个作业等待的时间，也考虑了所需执行的时间。

**算法原理**：响应比 R = （W+T）/ T，其中，W 为等待时间，T 为估计执行时间，系统选择响应比大的作业进行优先处理。

**算法优点**：长作业有机会运行，同一时间内处理的作业数显然少于短作业优先，因此其吞吐量要少于采用短作业优先时的吞吐量。

**算法缺点**：由于每次调度前都要计算响应比，系统开销也要相应增加。

4. 时间片轮转算法（RR， round-robin）

**算法原理**：让就绪进程按FCFS的方式按时间片轮流使用CPU的调度方式，

**算法优点**：简单易行，平均响应时间短

**算法缺点**：不利于处理紧急作业。时间片的大小对系统性能的影响很大，因此时间片大小应选择恰当。

时间片大小的确定方法：1. 系统对响应时间的要求； 2. 就绪队列中进程的数目； 3. 系统的处理能力。

5. 多级反馈队列（Multilevel Feedback Queue），UNIX操作系统采用的就是这种调度算法。

**算法原理**：设置多个队列，每个队列有不同的优先级和时间片，每个队列中的作业都按照时间片轮转顺序完成，若某一作业经过了N个时间片后还未完成，则自动降到下一个优先级的队列等待；只有高优先级的队列为空时，才能调用低优先级队列中的作业；在低优先级队列中的作业正在运行时，又有新的作业（优先级高）到达，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。

###    3. 进程间通信方式 ###

进程间通信（IPC，InterProcess Communication）是指在不同进程之间传播或交换信息。

IPC 的方式通常有管道（无名管道和命名管道）、消息队列、信号量、共享内存、Socket、Streams等。其中Socket和Streams支持不同主机上的两个进程IPC。

1. 管道，通常指无名管道，是UNIX系统IPC最古老的形式。

特点：1. 它是半双工的，即数据只能在一个方向上流动，具有固定的读端和写端； 2. 它只能用于具有亲缘关系的进程之间的通信（父子进程或兄弟进程之间）； 3. 它可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存于内存中。

2. FIFO，也称为命名管道，它是一种文件类型。

特点：1. FIFO 可以在无关的进程之间交换数据，与无名管道不同； 2. FIFO 有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。

3. 消息队列，是消息的链表，存放在内核中。一个消息队列由一个标识符来标识。

特点：1. 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级；2. 消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除；3. 消息队列可以实现消息的随即查询，消息不一定要以先进先出的次序读取，也可以按消息的类型读取。

4. 信号量，它是一个计数器，用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。

特点：1. 信号量用于进程间同步，若要在进程间传递数据需要结合共享内存； 2. 信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作； 3. 每次对信号量对 PV 操作不仅限于对信号量值加 1 减 1 ，而且可以加减任意正整数； 4. 支持信号量组。

5. 共享内存，指两个或多个进程共享一个给定的存储区。

特点：1. 共享内存是最快的一种IPC，因为进程是直接对内存进行存取； 2. 因为多个进程可以同时操作，所以需要进行同步； 3. 信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。

***总结：***

1.  管道：速度慢，容量有限，只有父子进程能通讯
2.  FIFO：任何进程间都能通讯，但速度慢
3.  消息队列：容量受到系统的限制，而且要注意在第一次读的时候，要考虑上次没读完数据的问题
4.  信号量：不能传递复杂消息，只能用来同步
5.  共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的过程中，里一个进程要注意读写问题，相当于线程中的线程安全问题，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存。

### 4. 进程线程区别 ###

*  进程：进程是资源（CPU、内存等）分配的基本单位，它是程序执行时的一个实例。程序运行时系统就会创建一个进程，并为它分配资源，然后把该进程放入进程就绪队列，进程调度器选中它的时候就会为它分配CPU时间，程序开始真正运行。
 *  线程：线程是程序执行时的最小单位，它是进程的一个执行流，是CPU调度和分派的基本单位，一个进程可以有很多个线程组成，线程间共享进程的所有资源，每个线程有自己的堆栈和局部变量。线程由CPU独立调度执行，在多CPU环境下就允许多个线程同时运行。同样多线程也可以实现并发操作，每个请求分配一个线程来处理。

**区别：**

*  进程是资源分配的基本单位，线程是程序执行的最小单位。
 *  进程有自己的独立地址空间，每启动一个进程，系统就会为它分配地址空间，建立数据表来维护代码段、堆栈段和数据段，这种操作非常昂贵。而线程是共享进程中的数据的，使用相同的地址空间，因此CPU切换一个线程的花费远比进程要小很多，同时创建一个线程的开销也比进程要小很多。
 *  线程之间的通信更方便，同一进程下的线程共享全局变量，静态变量等数据，而进程之间的通信需要以IPC的方式进行。
 *  但是多进程程序更健壮，多线程程序只要有一个线程死掉，整个进程也死掉了；而一个进程死掉并不会影响另一个进程，因为进程有自己独立的地址空间。

### 5. 父子进程、孤儿进程 ###

某进程调用 fork() 产生子进程，两个进程互为父子进程。

*  孤儿进程：若父进程先退出，子进程还没退出，那么子进程变为孤儿进程，并将其父进程变为init进程（1进程）；任何一个进程都必须有父进程；
 *  僵尸进程：若子进程先退出，父进程还没退出，那么子进程必须等到父进程捕获到了子进程的退出状态才真正结束，否则这个时候的子进程就称为僵尸进程。