操作系统高频面试题梳理

0.题目汇总

线程和进程的区别？
进程之间的通信方式
说一说进程的状态
说说僵尸进程和孤儿进程。
死锁的必要条件
周转时间和带权周转时间的计算
页面置换算法

1.线程和进程的区别？

1、根本区别： 进程是操作系统资源分配和独立运行的最小单位；线程是任务调度和系统执行的最小单位。
2、地址空间区别：每个进程都有独立的地址空间，一个进程崩溃不影响其它进程；一个进程中的多个线程共享该进程的地址空间，一个线程的非法操作会使整个进程崩溃。
3、上下文切换开销区别：每个进程有独立的代码和数据空间，进程之间上下文切换开销较大；线程组共享代码和数据空间，线程之间切换的开销较小。

2.进程之间的通信方式

每个进程的用户地址空间都是独立的，一般而言是不能互相访问的，但内核空间是每个进程都共享的，所以进程之间要通信必须通过内核。

管道(内核中的缓冲区)

管道本质上就是内核中的一个缓冲区,程序通过对缓存进行读写完成通信

匿名管道：在内核中申请一块固定大小的缓冲区，程序拥有写入和读取的权利。

// 创建匿名管道，并返回了两个描述符，一个是管道的读取端描述符 fd[0]，另一个是管道的写入端描述符 fd[1]
int fd[2];
if(pipe(fd)==-1)
    ERR_EXIT("pipe error");

看到这，你可能会有疑问了，这两个描述符都是在一个进程里面，并没有起到进程间通信的作用，怎么样才能使得管道是跨过两个进程的呢？

可以使用 fork 创建子进程，创建的子进程会复制父进程的文件描述符，这样就做到了两个进程各有两个「 fd[0] 与 fd[1]」，两个进程就可以通过各自的 fd 写入和读取同一个管道文件实现跨进程通信了。

可以使用 fork 创建的两个子进程之间也可以使用匿名管道实现通信。

命名管道：在内核中申请一块固定大小的缓冲区，程序拥有写入和读取的权利，没有血缘关系的进程也可以进程间通信。

mkfifo("tp",0644);
int infd;
infd = open("abc",o_RDONLY);
if (infd ==-1)ERR_EXIT("open");
int outfd;
outfd = open ("tp",O_WRONLY);

优点

实现简单，自带同步互斥机制

缺点

每个消息的最大长度是有上限的（MSGMAX）
效率低下，不适合进程间频繁的交换数据
半双工通信，同一时刻只有一个进程可以进行读写。(可以用两个管道实现双向通信)

消息队列(内核中的队列)

在内核中创建一队列，不同的进程可以通过句柄去访问这个队列，队列中每个元素是一个数据报。

优点

消息队列可实现双向通信。
消息队列允许一个或多个进程写入或者读取消息。

缺点

每个消息的最大长度是有上限的（MSGMAX）
消息队列的总数也有⼀个上限（MSGMNI）
存在用户态和内核态之间的数据拷贝问题。进程往消息队列写入数据时，会发送用户态拷贝数据到内核态的过程，同理读取数据时会发生从内核态到用户态拷贝数据的过程。

共享内存

将同一块物理内存一块映射到不同的进程的虚拟地址空间中，实现不同进程间对同一资源的共享。这样一个进程写入的东西，另一个进程马上就能够看到，不需要进行拷贝。

优点

速度快：不需要陷入内核态或者系统调用，大大提高了通信的速度，享有最快的进程间通信方式之名

缺点

多进程竞争同个共享资源会造成数据的错乱：如果有多个进程同时往共享内存写入数据，有可能先写的进程的内容会被其他进程覆盖。

信号量(内核中的信号量集合)

在内核中创建一个信号量集合（本质是个数组），数组的元素（信号量）都是1，使用P操作进行-1，使用V操作+1，主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据。

P(sv)：如果sv的值⼤大于零，就给它减1；如果它的值为零，就挂起该进程的执⾏。
V(sv)：如果有其他进程因等待sv而被挂起，就让它恢复运⾏，如果没有进程因等待sv⽽挂起，就给它加1。

信号

上面说的进程间通信，都是常规状态下的工作模式。对于异常情况下的工作模式，就需要用「信号」的方式来通知进程。信号是进程间通信机制中唯一的异步通信机制。

在Linux中，为了响应各种事件，提供了几十种信号，可以通过kill -l命令查看。

$ kill -l
 1) SIGHUP       2) SIGINT       3) SIGQUIT      4) SIGILL       5) SIGTRAP
 6) SIGABRT      7) SIGBUS       8) SIGFPE       9) SIGKILL     10) SIGUSR1
11) SIGSEGV     12) SIGUSR2     13) SIGPIPE     14) SIGALRM     15) SIGTERM
16) SIGSTKFLT   17) SIGCHLD     18) SIGCONT     19) SIGSTOP     20) SIGTSTP
21) SIGTTIN     22) SIGTTOU     23) SIGURG      24) SIGXCPU     25) SIGXFSZ
26) SIGVTALRM   27) SIGPROF     28) SIGWINCH    29) SIGIO       30) SIGPWR
31) SIGSYS      34) SIGRTMIN    35) SIGRTMIN+1  36) SIGRTMIN+2  37) SIGRTMIN+3
38) SIGRTMIN+4  39) SIGRTMIN+5  40) SIGRTMIN+6  41) SIGRTMIN+7  42) SIGRTMIN+8
43) SIGRTMIN+9  44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13
48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12
53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9  56) SIGRTMAX-8  57) SIGRTMAX-7
58) SIGRTMAX-6  59) SIGRTMAX-5  60) SIGRTMAX-4  61) SIGRTMAX-3  62) SIGRTMAX-2
63) SIGRTMAX-1  64) SIGRTMAX

运行在 shell 终端的进程，我们可以通过键盘输入某些组合键的时候，给进程发送信号。例如

Ctrl+C 产生 SIGINT 信号，表示终止该进程；
Ctrl+Z 产生 SIGTSTP 信号，表示停止该进程，但还未结束；

如果进程在后台运行，可以通过 kill 命令的方式给进程发送信号，但前提需要知道运行中的进程 PID 号，例如：

kill -9 1050 ，表示给 PID 为 1050 的进程发送 SIGKILL 信号，用来立即结束该进程；

Socket

前面提到的管道、消息队列、共享内存、信号量和信号都是在同一台主机上进行进程间通信，那要想跨网络与不同主机上的进程之间通信，就需要 Socket 通信了。

实际上，Socket 通信不仅可以跨网络与不同主机的进程间通信，还可以在同主机上进程间通信。

针对 TCP 协议通信的 socket 编程模型

针对 UDP 协议通信的 socket 编程模型

3.说一说进程的状态

创建状态：进程在创建时需要申请一个空白PCB，向其中填写控制和管理进程的信息，完成资源分配。如果创建工作无法完成，比如资源无法满足，就无法被调度运行，把此时进程所处状态称为创建状态

就绪状态：进程已经准备好，已分配到所需资源，只要分配到CPU就能够立即运行

执行状态：进程处于就绪状态被调度后，进程进入执行状态

阻塞状态：正在执行的进程由于某些事件（I/O请求，申请缓存区失败）而暂时无法运行，进程受到阻塞。在满足请求时进入就绪状态等待系统调用

终止状态：进程结束，或出现错误，或被系统终止，进入终止状态。无法再执行

4.说说僵尸进程和孤儿进程。

我们知道在unix/linux中，正常情况下，子进程是通过父进程创建的，子进程在创建新的进程。子进程的结束和父进程的运行是一个异步过程,即父进程永远无法预测子进程到底什么时候结束。当一个进程完成它的工作终止之后，它的父进程需要调用wait()或者waitpid()系统调用取得子进程的终止状态。
孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵尸进程。

5.死锁的必要条件

互斥条件：一个资源每次只能被一个进程使用；　

请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放；

不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺；

循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系；

6.周转时间和带权周转时间的计算

$$ 周转时间=作业完成时刻-作业到达时刻\\ 带权周转时间=\frac{周转时间}{服务时间}\\ 平均周转时间=\frac{作业周转总时间}{作业个数}\\ 平均带权周转时间=\frac{带权周转总时间}{作业个数}\\ $$

7.页面置换算法

在进程运行的过程当中，进程所要访问的页面不在内存中，我们就需要把这个不存在的页面调入内存，但内存已经没有空闲空间了，这时候就要求系统从内存中调出一个页面，将其移入磁盘的对换区中。将哪个页面调出来，就要通过算法来确定。我们把选择换出页面的算法就叫做页面置换算法。

先进先出置换算法FIFO

思想：先进先出算法总是淘汰最先进入内存的页面。出发点是近期调入的页面被再次访问的概率要大于早期调入页面的概率。

例题：考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。
当内存块数量分别为3时，试问先进先出置换算法（FIFO）的缺页次数是多少？

最近最少使用页面置换算法LRU

思想：每次选择内存中离当前时刻最久未使用过的页面淘汰,依据的原理是局部性原理

例题：考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。
当内存块数量分别为3时，试问最近最少使用页面置换算法（LRU）的缺页次数是多少？

最佳置换算法OPT

思想：选择的被淘汰页面是以后用不使用的，或者是在未来最长一段时间内不再被访问的页面。

例题：考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。
当内存块数量分别为3时，试问最佳置换法（OPT）的缺页次数是多少？

Clock置换算法

略