其他篇之操作系统——进程管理

*操作系统之进程管理*

说明：详细内容以面试题问答形式呈现！

一、基本概念

1.冯·诺伊曼体系结构

附-图

（1）输入设备：键盘、鼠标、扫描仪、写板等

（2）中央处理单元CPU：包括运算器和控制器

（3）输出单元：显示器、打印机等

*注：关于冯诺依曼

（1）这里的存储器指的是内存；

（2）不考虑缓存情况，CPU能且只能对内存进行读写，不能访问外设（输入输出设备）；

（3）外设（输入输出设备）要输入或输出数据，也只能写入内存或从内存中读取；

（4）所有设备都只能直接和内存打交道。

2.操作系统（Operator System，简称OS）—通过记录信息并组织信息进行管理

包括：内核（进程管理，内存管理，文件管理，驱动管理），其他程序（例如函数库，shell程序等）

OS定位：在整个计算机软硬件架构中，其定位是一款纯正的“搞管理”的软件，

设计OS的目的：

（1）与硬件交互，管理所有的软硬件资源（对内且对下）

（2）为用户程序（应用程序）提供一个良好的执行环境（对外且对上）

3.时间片

操作系统的任务调度方式之一是采用 “时间片轮转” 的抢占式调度方式，也就是说一个任务执行一小段时间后强制暂停去执行下一个任务，每个任务轮流执行。任务执行的一小段时间叫做“时间片”，任务正在执行时的状态叫做“运行状态”，任务执行一段时间后强制暂停去执行下一个任务，被暂停的任务就处于“就绪状态”，等待下一个属于它的时间片的到来。这样每个任务都能得到执行，由于CPU执行效率非常高，时间片非常短，在各个任务之间快速切换，给人的感觉就是多个任务在同时进行，即所谓的“并发”。

上面的轮转与管理工作，在操作系统中，统一由一个叫做 “调度器” 的内核模块完成。

4.并发与并行

（1）并发：多个进程在一个CPU下采用时间片轮转的方式，在一段时间之内，让多个进程都得以推进，称之为并发；

（2）并行：多个进程在多个CPU下分别同时进行运行，称之为并行。

*如何理解？*

假设张三准备办理转账业务，但当他把所有资料给工作人员之后，工作人员告诉他，你现在办理不了，因为他现在需要填写一张申请表，此时，工作人员将他的资料保存起来，让他去一边填写资料，填写完毕之后，再回来继续办理，同时，张三去填表了，而工作人员继续给别人提供服务。这个过程叫做进程切换。

张三表填完了，继续回到柜台，工作人员拿出他之前的资料，继续给张三办理业务，这叫做进程的上下文保护与恢复（想想，为什么要这麽做？因为进程的运行是在CPU上的，CPU有寄存器，保存的是进程运行的各种临时数据，为了达到切换和便于恢复的目的，就有了将CPU寄存器保存和恢复的做法，归根结底是为了接着上次的位置继续运行）后来，银行出台了规定，每个人在柜台办理任务的时间不能超过10分钟（以防止其他人长时间等待），所以为了更好的服务各个人员，银行工作人员将上面的切换与恢复的思路应用到各种业务中，所以长期来看，即便只有一个工作人员，也能同时服务多个客户，这种机制叫做基于时间片的进程轮转管理机制，而上面的10分钟，就是银行轮转的时间片，只要时间到了，客户酒的下去等待，让其他用户来办理业务，而上面的所有轮转与管理工作，在操作系统中，统一由一个叫做调度器的内核模块完成。对每个人来说，在一段时间之内，可能所有人的业务都得以推进（即便没完成），而不至于大家长时间等待，这种机制就叫做并发如果银行财大气粗，工作人员比客户都多，那就好办了，一人一个工作人员，所有的任务真正同时处理，这种机制叫做并行。

5.内核态与用户态

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

（1）内核态（核心态）：操作系统内核作为直接控制硬件设备的底层软件，权限最高，称为内核态；

（2）用户态：用户程序的权限最低，称为用户态。

*如何理解？*

就好比上面的例子，张三去填表，自己写姓名，电话，邮箱等等，做着自己的事情，这叫做用户态；而张三通过窗口的工作人员，把自己的需求给工作人员，自此，张三在等，银行工作人员在忙，对张三来讲，就叫做陷入内核。那么内核态是什么意思？就是工作人员在帮你办理业务时的状态。

6.进程中的上下文（简单说就是一个环境）

解释：就是一个进程在执行的时候，CPU的所有寄存器的值、进程的状态以及堆栈上的内容；切换时需要保存当前进程的所有状态，即当前进程的进程上下文，以便再次执行该进程时，能够恢复切换时的状态，继续执行。

二、面试题整理

1.什么是进程？什么是线程？进程和线程的区别？

答：进程是具有一定独立功能的程序在某个数据集合上的一次运行活动，是系统进行资源分配的基本单位，具有动态特性；线程是进程的一个实体，是系统进行任务调度的基本单位，一个进程中可以包含多个线程。二者的区别：

（1）粒度性分析：线程的粒度小于进程；

（2）调度性分析：进程是资源拥有的基本单位；线程是独立调度与独立运行的基本单位，除了寄存器、程序计数器和栈这些运行时必不可少的资源外不拥有其他系统资源；

（3）系统开销分析：由于线程基本不拥有系统资源，所以在进行切换时，线程切换的开销远远小于进程。

2.进程的状态及其转换？

答：

（1）就绪：进程处于可运行状态，只是CPU时间片还未轮到该进程，此时处于就绪状态；

（2）运行：进程处于可运行状态，且CPU时间片轮转到该进程，该进程正在执行代码，此时处于运行状态；

（3）阻塞：进程不具备运行条件，正在等待某个事件的完成，此时处于阻塞状态。

附-图

3.什么是进程同步与互斥？

答：

（1）互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排他性，但互斥无法限制访问者对资源的访问顺序，即互斥是无序的；

（2）同步：是指在互斥的基础上（大多数情况），通过其他机制实现访问者对资源的有序访问，在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的，少数情况是指允许多个访问者同时访问某个资源；

总之，同步体现的是一种协作性，互斥体现的是一种排他性。

延申补充1：进程同步的几种机制

（1）信号量

>>什么是信号量？

信号量的数据结构为一个值（S）和一个指针，指针指向等待该信号量的下一个进程，信号量的值和相应资源的使用情况有关，当S > 0时表示当前可用资源的数量；当 S < 0时其绝对值表示当前正在等待使用该资源的进程个数；一个信号量只能置一次初值，以后都是对他进行P操作或V操作，由此可见，信号量机制必须有公共内存，因此不能用于分布式操作系统。

>>理解P/V操作（不可中断）：

P(S)：执行一次P操作意味着请求分配一个单位资源，因此信号量的值S减1，即S = S - 1；若S >= 0则该进程继续执行，否则该进程置为等待状态，排入等待队列；

V(S)：执行一次V操作意味着释放一个单位资源，因此信号量的值S加1，即S = S 1；若S > 0则该线程继续执行，否则释放队列中第一个等待该资源的进程。

>>利用信号量和PV操作实现进程互斥的一般模型是：

进程P1 进程P2 …… 进程Pn

…… …… ……

P（S）； P（S）； P（S）；

临界区； 临界区； 临界区；

V（S）； V（S）； V（S）；

…… …… …… ……

其中信号量S用于互斥，初值为1。

使用PV操作实现进程互斥时应该注意的是：

A. 每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性；

B. P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环；互斥信号量的初值一般为1。

>>利用信号量和PV操作实现进程同步：

PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来，当信号量的值为0时，表示期望的消息尚未产生；当信号量的值非0时，表示期望的消息已经存在。用PV操作实现进程同步时，调用P操作测试消息是否到达，调用V操作发送消息。

使用PV操作实现进程同步时应该注意的是：

A. 分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量；

B. 信号量的初值与相应资源的数量有关，也与P、V操作在程序代码中出现的位置有关；

C. 同一信号量的P、V操作要成对出现，但它们分别在不同的进程代码中。

（2）自旋锁

自旋锁是为了保护共享资源提出的一种锁机制，调用者申请的资源如果被占用，即自旋锁已经被别的执行单元保持，则调用者一直循环检查该自旋锁的占有者是否已经释放锁，此过程中可能会引起死锁、过多地占用CPU资源等问题。

（3）管程

>>信号量机制功能强大，但使用时对信号量的操作分散，而且难以控制，读写和维护都很困难，因此又提出一种集中式同步进程——管程。其基本思想是将共享变量和对他们的操作集中在一个模块中，操作系统或并发程序就由这样的模块构成，这样模块之间联系清晰，便于维护和修改，易于保证正确性。

>>管程作为一个模块，其类型定义如下：

monitor_name = MONITOR;

共享变量说明;

define 本管程内部定义、外部可调用的函数名表;

use 本管程外部定义、内部可调用的函数名表;

内部定义的函数声明（以“;”结尾）和函数体{...}

{

共享变量初始化语句;

}

>>从语言的角度看，管程主要有以下特性：

A. 模块化：管程是一个基本程序单位，可以单独编译；

B. 抽象数据类型：管程中不仅有数据，而且有对数据的操作；

C. 信息掩蔽：管程外可以调用管程内部定义的一些函数，但函数的具体实现外部不可见，对于管程中定义的共享变量的操作都局限在管程中，外部只能通过调用管程的某些函数来间接访问，体现了一定的封装性。

>>其他：

为了保证共享变量的数据一致性，管程应互斥使用，管程是用于管理资源的，因此管程中有进程等待队列以及相应的等待和唤醒操作。在管程入口有一个等待队列，称为入口等待队列，当一个已进入管程的进程等待时，就释放管程的互斥使用权；当已进入管程的一个进程唤醒另一个进程时，两者必须有一个退出或停止使用管程。在管程内部，可能存在多个等待进程（等待使用管程），称为紧急等待队列，其优先级高于入口等待队列。一个进程进入管程之前要先申请，一般由管程提供enter过程，离开时释放使用权，一般也由管程提供外部过程leave。

>>管程内部有自己的等待机制，有一种特殊的条件型变量：var c : condition;本质上是一个指针，指向等待该条件的PCB队列，对条件型变量可以执行wait()和signal()操作：

wait(c)：若紧急等待队列不空，唤醒第一个等待进程，释放管程使用权，执行该操作的进程进入c队列尾部；

signal(c)：若c队列为空，继续执行原进程，否则唤醒紧急等待队列中的第一个等待进程，自己进入紧急等待队列尾部。

>>信号量/管程同步的示例

https://blog.csdn.net/qq_38211852/article/details/80211169

（4）会合

进程之间直接进行相互作用。

（5）分布式系统

由于分布式系统中没有公共内存，因此参数全为值参，且不可为指针。

延申补充2：进程同步机制的四大基本准则

（1）空闲让进：当无进程处于临界区时，可允许一个请求进入临界区的进程立即进入自己的临界区；

（2）忙则等待：当已有进程进入自己的临界区，所有试图进入临界区的进程必须等待；

（3）有限等待：对要求访问临界资源的进程，应保证其在有限时间内能够进入自己的临界区；

（4）让权等待：当进程不能进入自己的临界区时，应该释放处理机，以免陷入忙等状态。

延申补充3：线程的同步机制

（1）临界区（Critical Section）

通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问，在任意时刻只允许一个线程访问公共资源，如果有多个线程同时试图访问，那么在一个线程临界区后，其他试图访问公共资源的线程将被挂起，直到进入临界区的线程离开，其他线程才可以继续抢占进入临界区。

（2）互斥对象（Mutex）

互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，由此保证公共资源不会同时被多个线程访问。

（3）信号量（Semaphore）

这种同步方式和前面的有所不同，它允许多个线程同时访问同一资源，但是需要限制同一时刻访问此资源的最大线程数目，与操作系统进程同步机制中的PV操作（详情见进程同步机制）相同。

（4）事件对象（Event）

通过通知操作的方式来实现线程的同步，还可以方便实现对多个线程的优先级比较的操作。

>>四种同步机制的比较

4.进程间的通信方式有哪些？

答：

（1）管道（pipe）

管道是一种半双工的通信方式，又称匿名管道，数据只能单向流动，而且只能在具有亲缘关系的进程之间使用，进程的亲缘关系通常指父子进程关系，它把一个进程的标准输出和另一个进程的标准输入连接在一起，写进程在管道的尾部写入数据，读进程在管道的头部读出数据，数据读出后将从管道中移走，其它读进程都不能再读到这些数据。

（2）有名管道（named pipe）

有名管道（即FIFO，先进先出）也是一种半双工的通信方式，但是其支持无亲缘关系的进程之间的通信。有名管道不仅可以在本机上实现两个进程的通信，还可以跨网络实现两个进程间的通信。

（3）信号量（semaphore）

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

（4）消息队列（message queue）

消息队列是以消息链表的形式，存放在内核中并且由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。消息队列是用于两个进程间的通信，首先一个进程创建一个消息队列，然后在消息队列中写数据，而另一个进程则从消息队列中读取数据，需要注意的是，消息队列是用创建文件的方式创建的。

（5）共享内存（shared memory）

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

（6）信号（signal）

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

（7）套接字（socket）

套接字通信并不为Linux所专有，在所有提供了TCP/IP协议栈的操作系统中几乎都提供了socket，而所有这样的操作系统，对套接字的编程方法几乎也是完全一样的，它可用于不同机器间的通信。

补充：几种通信方式的比较

>管道：速度慢、容量有限、只支持父子进程间的通信；

>FIFO：所有进程间都可以通信，但速度慢；

>消息队列：容量受系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题；

>信号量：不能传递复杂消息，只能用来同步；

>共享内存区：很容易控制容量、速度快，但要保证同步。

5.作业（或进程）的调度算法有哪些？

答：

（1）先来先服务（FCFS,First-Come-First-Served）

此算法的原则是按作业到达后备作业队列（或进程进入就绪队列）的先后顺序来选择作业（或进程）。

（2）短作业优先（SJF,Short-Job-First）

这种调度算法主要用于作业调度，其基本原则是从后备作业队列中选择所需运行时间（估计值）最短的作业进入主存运行。

（3）时间片轮转调度算法（RR,Round-Robin）

当某个进程执行的时间片用完时，调度程序便停止该进程的执行，并将它送到就绪队列的尾部，等待分配下一时间片再继续执行，然后把处理机分配给就绪队列的队首进程，同时也让它执行一个时间片，这样就能保证就绪队列中的所有进程，在一定的时间内都能得以运行推进。

（4）最高响应比优先（HRRN,Highest-Response-Ratio-Next）

所谓响应比指的是【（已等待时间 要求运行时间） / 要求运行时间】，该调度算法基本原则是在每次选择作业投入运行时，先计算此时后备作业队列中每个作业的响应比RR然后选择值最大的作业投入运行。

（5）优先权(Priority)调度算法

其基本原则是按照进程的优先权高低来调度，先调度优先权高的进程，需要注意的是优先数越多，优先权越低。

（6）多级队列调度算法

其基本原则是根据进程（或作业）的性质和类型的不同，将就绪队列（或后备作业队列）再分为若干个子队列，所有的进程（或作业）按其性质排入相应的子队列中，而不同的就绪队列可分配不同的时间片和采用不同的调度算法，在队列之间，通常采用固定优先权的抢占调度方式。

（7）多级反馈队列调度

其基本原则是在多级队列调度的基础上，任务可以根据运行需要的CPU时间在队列之间移动。对于优先级最低的队列来说，里面是遵循时间片轮转法，也就是说，队列QN中有M个作业，它们的运行时间是通过QN这个队列所设定的时间片来确定的；对于其他队列，遵循的是先来先服务算法，每一进程分配一定的时间片，若时间片运行完时进程未结束，则进入下一优先级队列的末尾。

补充：各种调度算法的性能比较

>先来先服务：公平、简单（FIFO队列就可）、非抢占式调度，但不适合交互式运行，同时也未考虑任务的特性；

>短作业优先：可能出现“饥饿”现象，即所需运行时间较长的作业可能会一直得不到运行机会；

>时间片轮转调度算法：优点是定时有响应、等待时间较短；缺点是上下文切换次数较多，另外时间片太大时响应时间过长；

>最高响应比优先：这是介于先来先服务算法与短作业优先算法之间的折中算法，既考虑作业等待时间又考虑作业运行时间，但由于要做响应比计算故增加了系统开销；

>优先权调度算法：也可能出现“饥饿”现象，即优先权太低的任务一直就绪，得不到运行；

>多级队列调度算法：这种调度算法可针对不同用户进程的需求，提供不同的调度策略；

>多级反馈队列调度：该算法既能使高优先级的作业得到响应又能使短作业（或进程）迅速完成，是最通用的一种调度算法，大部分OS采用这种调度算法或其变形，例如UNIX，Windows等。

6.什么是死锁？死锁产生的原因？

答：死锁是指多个进程在运行过程中由于竞争资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，这些进程都将无法再向前推进。产生死锁的原因如下：

（1）进程之间竞争资源（不可剥夺资源、临时资源）；

（2）进程推进顺序不当。

7.死锁产生的必要条件？

答：

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

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

（3）请求和保持条件：进程已经占有了至少一个资源，同时又提出新的资源请求，而该资源被其他进程占有，此时请求进程阻塞，但对已经获得的资源保持不放；

（4）环路等待条件：在发生死锁时，必然存在一个“进程-资源”的环形链，即环路中进程P1等待进程P2占有的资源，进程P2等待进程P3占有的资源，...进程Pn等待进程P1占有的资源，由此形成一个进程等待环路。

8.解决死锁问题的基本方法？

答：

（1）预防死锁

我们可以通过破坏死锁产生的4个必要条件来预防死锁，其中资源互斥是资源使用的固有特性无法改变。

A. 破坏“不可剥夺条件”：一个进程获得了部分资源但得不到其他所需资源时便处于等待状态，等待期间该进程已经占有的资源也将被释放重新加入到系统的资源队列中被其他进程使用，等待进程想要继续运行必须重新获取所需的全部资源；

B. 破坏“请求和保持条件”：第一种方法是静态分配即每个进程在开始执行时就申请它所需要的全部资源；第二种方法是动态分配即每个进程在运行过程中申请所需的资源时其本身不占有系统资源；

C. 破坏“环路等待条件”：采用资源有序分配的方法，其基本思想是将系统中的资源顺序编号，每个进程按编号递增的顺序请求资源，按编号递减的顺序释放资源。

（2）避免死锁

预防死锁的几种策略，会严重地损害系统性能。因此在避免死锁时，要施加较弱的限制，从而获得较满意的系统性能。避免死锁的基本思想是系统对进程发出的每一个资源申请进行动态检查，根据检查结果决定是否分配资源，如果分配后系统可能发生死锁则不予分配，否则予以分配，这是一种保证系统不进入死锁状态的动态策略，其中最具代表性的算法是银行家算法。

银行家算法：首先需要定义状态和安全状态的概念，系统的状态是当前给进程分配的资源情况，安全状态是指至少有一个安全序列不会导致死锁【安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和】。

该算法的相关数据结构如下：

A. 可利用资源向量Available：是个含有m个元素的数组，每一个元素代表一类可利用资源的数目，如果Available[j] = K，则表示系统中现有Rj类资源K个；

B. 最大需求矩阵Max：这是一个n * m的矩阵，定义了系统中n个进程中的每一个进程对m类资源的最大需求量，如果Max[i,j] = K，则表示进程i需要Rj类资源的最大数目为K；

C. 分配矩阵Allocation：这是一个n * m的矩阵，定义了系统中每一类资源当前已分配给每一个进程的资源数，如果Allocation[i,j] = K，则表示进程i当前已分得Rj类资源的数目为K；

D. 需求矩阵Need：这是一个n * m的矩阵，定义了每一个进程尚需的各类资源数，如果Need[i,j] = K，则表示进程i还需要Rj类资源K个，方能完成其任务。

（3）检测死锁

见下图所示：https://blog.csdn.net/jgm20475/article/details/81297819

附-图

死锁定理（死锁产生的充分条件）：当且仅当S状态的资源分配图是不可完全简化时，系统的状态则是死锁状态。

（4）解除死锁

A. 资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他死锁进程，但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态；

B. 撤销进程法：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源，从以下几个方面采用最优策略选择“代价最小”的进程来解除死锁状态，包括进程的优先级、进程已运行时间以及运行完成还需要的时间、进程已占用系统资源、进程完成还需要的系统资源、终止进程数目、进程类型（交互式/批处理）等。

C. 进程回退法：让一个或多个进程回退到足以避免死锁的状态，进程回退时自愿释放资源而不是被剥夺，因此要求系统保持进程的历史信息，设置还原点。

9.进程上下文切换？

答：

上下文切换，也称环境切换。在操作系统中，CPU切换到另一个进程需要保存当前进程的状态并恢复要运行进程的状态，当前运行任务转为就绪（或挂起/或删除）状态，另一个被选定的就绪任务成为当前任务。因此，上下文切换包括保存当前任务的运行环境、恢复将要运行任务的运行环境。

进程上下文用进程的PCB（Process-Control-Block，进程控制块或任务控制块）表示，它包括进程状态、CPU寄存器的值等。可能发生上下文切换的情况有中断处理、多任务处理、用户态切换等。

三、参考文章

1.https://wenku.baidu.com/view/fe34281103020740be1e650e52ea551810a6c976.html

2.https://www.cnblogs.com/zeze/p/9711792.html

3.https://www.cnblogs.com/xymqx/p/4442329.html

4.https://blog.csdn.net/youngchang06hpu/article/details/8009947

5.https://blog.csdn.net/hd12370/article/details/82814348