操作系统-面试题汇总

超、凢脫俗 2022-11-19 01:08 127阅读 0赞

**目录**

进程管理

进程和线程有什么区别？

同一进程中的线程可以共享哪些数据？

线程独占哪些资源？

线程的分类

进程间有哪些通信方式？

线程间通信有哪些方式

同步、异步与互斥

并发与并行

调度

进程调度策略？

什么是优先级反转，如何解决？

什么是僵尸进程？

什么是孤儿进程？

进程的异常控制流：陷阱、中断、异常和信号

死锁

什么是死锁？

导致死锁的四个必要条件

死锁处理的基本策略和常用方法

内存管理

分页和分段有什么区别？

页面置换算法

参考

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

# 进程和线程有什么区别？ #

*  **进程**（Process）是**系统**进行**资源分配和调度**的基本单位，**线程**（Thread）是**CPU调度和分派**的基本单位；
 *  线程依赖于进程而存在，**一个进程至少有一个线程**；
 *  **进程**有自己的**独立地址**空间，**线程**共享所属**进程的地址**空间；
 *  进程是拥有系统资源的一个独立单位，而**线程自己基本上不拥有系统资源**，只拥有一点在运行中必不可少的资源(如**程序计数器,一组寄存器和栈**)，和其他线程共享本进程的相关资源如内存、I/O、cpu等；
 *  在进程切换时，涉及到整个当前进程CPU环境的保存，环境的设置以及新被调度运行的CPU环境的设置，而线程切换只需保存和设置少量的**寄存器**的内容，并不涉及存储器管理方面的操作，可见，**进程切换的开销远大于线程切换的开销**；
 *  线程之间的通信更方便，同一进程下的线程**共享全局变量**等数据，而进程之间的通信需要以**进程间通信(IPC)**的方式进行；
 *  多线程程序只要有一个线程崩溃，整个程序就崩溃了，但多进程程序中一个进程崩溃并不会对其它进程造成影响，因为进程有自己的独立地址空间，因此**多进程更加健壮**

## 同一进程中的线程可以共享哪些数据？ ##

*  进程代码段
 *  进程的公有数据（全局变量、静态变量...）
 *  进程打开的文件描述符
 *  进程的当前目录
 *  信号处理器/信号处理函数：对收到的信号的处理方式
 *  进程ID与进程组ID

## 线程独占哪些资源？ ##

*  线程ID
 *  一组寄存器的值
 *  线程自身的栈（堆是共享的）
 *  错误返回码：线程可能会产生不同的错误返回码，一个线程的错误返回码不应该被其它线程修改；
 *  信号掩码/信号屏蔽字(Signal mask)：表示是否屏蔽/阻塞相应的信号（SIGKILL,SIGSTOP除外）

## 线程的分类 ##

*  **用户级线程(user level thread)**：对于这类线程，有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。在应用程序启动后，操作系统分配给该程序一个进程号，以及其对应的内存空间等资源。应用程序通常先在一个线程中运行，该线程被成为**主线程**。在其运行的某个时刻，可以通过调用线程库中的函数创建一个在相同进程中运行的新线程。**用户级线程的好处是非常高效，不需要进入内核空间，但并发效率不高。**
 *  **内核级线程(kernel level thread)**：对于这类线程，有关线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只能调用内核线程的接口。内核维护进程及其内部的每个线程，调度也由内核基于线程架构完成。内核级线程的好处是，**内核可以将不同线程更好地分配到不同的CPU，以实现真正的并行计算。**

**事实上，在现代操作系统中，往往使用组合方式实现多线程，即线程创建完全在用户空间中完成，并且一个应用程序中的多个用户级线程被映射到一些内核级线程上，相当于是一种折中方案。**

## 进程间有哪些通信方式？ ##

*  （无名）管道(Pipe)

管道是一种**半双工**的通信方式，**单向的、先进先出的、无结构的、固定大小的字节流**。数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指**父子进程**关系。

*  命名管道

命名管道也是**半双工**的通信方式，但是它允许**无亲缘关系**进程间的通信。

*  信号(Signal)

信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生

*  消息队列

消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

*  共享内存

共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。**共享内存是最快的 IPC 方式**，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。

*  信号量(Semaphore)

信号量是一个**计数器**，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为**进程间以及同一进程内不同线程之间的同步手段**；课本里面的PV操作就是对信号量的增减。

*  套接字(Socket)

与其他通信机制不同的是，它可用于**不同机器间**的进程通信。

## 线程间通信有哪些方式 ##

(1)同步  
多个线程通过**synchronized**通讯，类似于共享内存

(2)while轮询  
线程A不断改变条件，线程B不断查看条件是否满足需求（比方说=5），从而实现通讯。  
效率不高，因为B一直在查看，没做别的

(3)wait/notify  
进入阻塞，而不是像轮询一样一直占用CPU资源

(4)管道通信  
通过管道，将一个线程的消息发送个另一个线程

## 同步、异步与互斥 ##

*  同步：多个进程因为合作而使得进程的执行**有一定的先后顺序**。比如某个进程需要另一个进程提供的消息，获得消息之前进入阻塞态；
 *  互斥：多个进程在同一时刻只有一个进程能进入**临界区**；
 *  异步（和同步相比）：同步是顺序执行，异步是在**等待某个资源的时候继续做自己的事**。

## 并发与并行 ##

并发：在一个时间段中同时有多个程序在运行，但其实**任一时刻，只有一个程序在CPU上运行**，宏观上的并发是通过微观的不断**切换**实现的；

多线程：并发运行的一段代码。是实现异步的手段。

并行（和串行相比）：在多CPU系统中，多个程序无论宏观还是微观上都是**同时执行**的。

## 调度 ##

### 进程调度策略？ ###

**批处理系统**

**先来先服务 first-come first-serverd（FCFS）**：先请求CPU的进程先分配到CPU

**最短作业优先 shortest job first（SJF）**：最短的先分配到CPU，平均等待时间最短，但难以知道下一个CPU区间长度

**最短剩余时间优先 shortest remaining time next（SRTN）**：

**最高响应比优先 Highest Response Ratio Next（HRRN）**：

**交互式系统**  
交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

**时间片轮转 Round Robin**：队列中没有进程被分配超过一个时间片的CPU时间，除非它是唯一可运行的进程。如果进程的CPU区间超过了一个时间片，那么该进程就被抢占并放回就绪队列。

**优先级调度算法**：优先级越高越先分配到CPU，相同优先级先到先服务，存在的主要问题是：低优先级进程无穷等待CPU，会导致无穷阻塞或饥饿；

**多级反馈队列调度算法 Multilevel Feedback Queue**：与多级队列调度算法相比，其允许进程在队列之间移动：若进程使用过多CPU时间，那么它会被转移到更低的优先级队列；在较低优先级队列等待时间过长的进程会被转移到更高优先级队列，以防止饥饿发生。

### 什么是优先级反转，如何解决？ ###

高优先级的进程等待被一个低优先级进程占用的资源时，就会出现优先级反转，即优先级较低的进程比优先级较高的进程先执行。

解决方法：

*  优先级天花板(priority ceiling)：当任务申请某资源时，把该任务的优先级提升到可访问这个资源的所有任务中的最高优先级，这个优先级称为该资源的优先级天花板。简单易行。
 *  优先级继承(priority inheritance)：当任务A申请共享资源S时，如果S正在被任务C使用，通过比较任务C与自身的优先级，如发现任务C的优先级小于自身的优先级，则将任务C的优先级提升到自身的优先级，任务C释放资源S后，再恢复任务C的原优先级。

### 什么是僵尸进程？ ###

一个子进程结束后，它的父进程并没有等待它（调用wait或者waitpid），那么这个子进程将成为一个僵尸进程。**僵尸进程是一个已经死亡的进程，但是并没有真正被销毁。**它已经放弃了几乎所有内存空间，没有任何可执行代码，也不能被调度，仅仅在进程表中保留一个位置，记载该进程的进程ID、终止状态以及资源利用信息(CPU时间，内存使用量等等)供父进程收集，除此之外，僵尸进程不再占有任何内存空间。这个僵尸进程可能会一直留在系统中直到系统重启。

危害：占用进程号，而系统所能使用的进程号是有限的；占用内存。

以下情况不会产生僵尸进程：

*  该进程的父进程先结束了。每个进程结束的时候，系统都会扫描是否存在子进程，如果有则用Init进程接管，成为该进程的父进程，并且会调用wait等待其结束。
 *  父进程调用wait或者waitpid等待子进程结束（需要每隔一段时间查询子进程是否结束）。wait系统调用会使父进程暂停执行，直到它的一个子进程结束为止。waitpid则可以加入`WNOHANG`(wait-no-hang)选项，如果没有发现结束的子进程，就会立即返回，不会将调用waitpid的进程阻塞。同时，waitpid还可以选择是等待任一子进程（同wait），还是等待指定pid的子进程，还是等待同一进程组下的任一子进程，还是等待组ID等于pid的任一子进程；
 *  子进程结束时，系统会产生`SIGCHLD`(signal-child)信号，可以注册一个信号处理函数，在该函数中调用waitpid，等待所有结束的子进程（注意：一般都需要循环调用waitpid，因为在信号处理函数开始执行之前，可能已经有多个子进程结束了，而信号处理函数只执行一次，所以要循环调用将所有结束的子进程回收）；
 *  也可以用`signal(SIGCLD, SIG_IGN)`(signal-ignore)通知内核，表示忽略`SIGCHLD`信号，那么子进程结束后，内核会进行回收。

### 什么是孤儿进程？ ###

一个父进程已经结束了，但是它的**子进程还在运行**，那么这些子进程将成为孤儿进程。孤儿进程会被Init（进程ID为1）接管，当这些孤儿进程结束时由Init完成状态收集工作。

### 进程的异常控制流：陷阱、中断、异常和信号 ###

陷阱是**有意**造成的“异常”，是执行一条指令的结果。陷阱是同步的。陷阱的主要作用是实现**系统调用**。比如，进程可以执行 `syscall n` 指令向内核请求服务。当进程执行这条指令后，会中断当前的控制流，**陷入**到内核态，执行相应的系统调用。内核的处理程序在执行结束后，会将结果返回给进程，同时退回到用户态。进程此时继续执行**下一条指令**。

中断由处理器**外部**的**硬件**产生，不是执行某条指令的结果，也无法预测发生时机。由于中断独立于当前执行的程序，因此中断是异步事件。中断包括 I/O 设备发出的 I/O 中断、各种定时器引起的时钟中断、调试程序中设置的断点等引起的调试中断等。

异常是一种错误情况，是执行当前指令的结果，可能被错误处理程序修正，也可能直接终止应用程序。异常是同步的。这里特指因为执行当前指令而产生的**错误情况**，比如除法异常、缺页异常等。有些书上为了区分，也将这类“异常”称为\*\*“故障”\*\*。

信号是一种**更高层的**软件形式的异常，同样会中断进程的控制流，可以由进程进行处理。一个信号代表了一个消息。信号的作用是用来**通知进程**发生了某种系统事件。

## 死锁 ##

## 什么是死锁？ ##

在两个或者多个并发进程中，如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源，在未改变这种状态之前都不能向前推进，称这一组进程产生了死锁。通俗的讲，就是两个或多个进程无限期的阻塞、相互等待的一种状态。

### 导致死锁的四个必要条件 ###

1）**互斥。**一次只有一个进程可以使用一个资源。其他进程不能访问已分配给其他进程的资源。

2）**占有并等待。**当一个进程等待其他进程时，继续占有已经分配的资源。

3）**不可抢占。**不能强行抢占进程已占有的资源。

4）**循环等待。**存在一个封闭的进程链，使得每个进程至少占有此链中下一个进程所需要的一个资源。

## 死锁处理的基本策略和常用方法 ##

解决死锁的基本方法主要有 **预防死锁、避免死锁、检测死锁、解除死锁 、鸵鸟策略** 等。

**死锁预防**  
　　  
       死锁预防的基本思想是 只要确保死锁发生**的四个必要条件中至少有一个不成立**，就能预防死锁的发生，具体方法包括：

**打破互斥条**件：允许进程同时访问某些资源。但是，有些资源是不能被多个进程所共享的，这是由资源本身属性所决定的，因此，这种办法通常并无实用价值。

**打破占有并等待条件**：可以实行资源预先分配策略(进程在运行前，**一次性**向系统申请它所需要的全部资源，若所需全部资源得不到满足，则不分配任何资源，此进程暂不运行；只有当系统能满足当前进程所需的全部资源时，才一次性将所申请资源全部分配给该线程)或者只允许进程在没有占用资源时才可以申请资源（一个进程可申请一些资源并使用它们，但是在当前进程申请更多资源之前，它必须全部释放当前所占有的资源）。

但是这种策略也存在一些缺点：在很多情况下，无法预知一个进程执行前所需的全部资源，因为进程是动态执行的，不可预知的；同时，会降低资源利用率，导致降低了进程的并发性。

**打破非抢占条件**：允许进程**强行从占有者哪里夺取某些资源**。也就是说，但一个进程占有了一部分资源，在其申请新的资源且得不到满足时，它必须释放所有占有的资源以便让其它线程使用。这种预防死锁的方式实现起来困难，会降低系统性能。

**打破循环等待条件**：实行资源有序分配策略。对所有资源排序编号，所有进程对资源的请求必须严格按资源序号递增的顺序提出，即只有占用了小号资源才能申请大号资源，这样就不回产生环路，预防死锁的发生。

**死锁避免**  
　　  
　　死锁避免的基本思想是动态地检测资源分配状态，以确保循环等待条件不成立，从而确保系统处于安全状态。所谓安全状态是指：如果系统能按某个顺序为每个进程分配资源（不超过其最大值），那么系统状态是安全的，换句话说就是，如果存在一个安全序列，那么系统处于安全状态。资源分配图算法和银行家算法是两种经典的死锁避免的算法，其可以确保系统始终处于安全状态。其中，资源分配图算法应用场景为每种资源类型只有一个实例(申请边，分配边，需求边，不形成环才允许分配)，而银行家算法应用于每种资源类型可以有多个实例的场景。

**死锁解除**

死锁解除的常用两种方法为进程终止和资源抢占。所谓进程终止是指简单地终止一个或多个进程以打破循环等待，包括两种方式：终止所有死锁进程和一次只终止一个进程直到取消死锁循环为止；所谓资源抢占是指从一个或多个死锁进程那里抢占一个或多个资源，此时必须考虑三个问题：

(I). 选择一个牺牲品  
　　(II). 回滚：回滚到安全状态  
　　(III). 饥饿（在代价因素中加上回滚次数，回滚的越多则越不可能继续被作为牺牲品，避免一个进程总是被回滚）

# 内存管理 #

## 分页和分段有什么区别？ ##

段式存储管理是一种符合用户视角的内存分配管理方案。在段式存储管理中，将程序的地址空间划分为若干段（segment），如代码段，数据段，堆栈段；这样每个进程有一个二维地址空间，相互独立，互不干扰。段式管理的优点是：**没有内碎片**（因为段大小可变，改变段大小来消除内碎片）。但段换入换出时，会产生外碎片（比如4k的段换5k的段，会产生1k的外碎片）

页式存储管理方案是一种用户视角内存与物理内存相分离的内存分配管理方案。在页式存储管理中，将程序的逻辑地址划分为固定大小的页（page），而物理内存划分为同样大小的帧，程序加载时，可以将任意一页放入内存中任意一个帧，这些帧不必连续，从而实现了**离散分离**。页式存储管理的优点是：**没有外碎片**（因为页的大小固定），但会产生内碎片（一个页可能填充不满）。

两者的不同点：

**目的**不同：**分页**是由于**系统管理的需要**而不是用户的需要，它是信息的物理单位；**分段**的目的是为了能更好地满足**用户的需要**，它是信息的逻辑单位，它含有一组其意义相对完整的信息；

**大小**不同：**页的大小固定**且由系统决定，而**段的长度却不固定**，由其所完成的功能决定；

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

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

**内存碎片**：页式存储管理的优点是没有外碎片（因为页的大小固定），但会产生内碎片（一个页可能填充不满）；而段式管理的优点是没有内碎片（因为段大小可变，改变段大小来消除内碎片）。但段换入换出时，会产生外碎片（比如4k的段换5k的段，会产生1k的外碎片）。

## 页面置换算法 ##

**FIFO先进先出算法**：在操作系统中经常被用到，比如作业调度（主要实现简单，很容易想到）；

**LRU（Least recently use）最近最少使用算法**：根据使用时间到现在的长短来判断；

**LFU（Least frequently use）最少使用次数算法**：根据使用次数来判断；

**OPT（Optimal replacement）最优置换算法**：理论的最优，就是要保证置换出去的是不再被使用的页，或者是在实际内存中最晚使用的算法。

# 参考 #