进程管理

https://www.cnblogs.com/Anker/p/3269106.html

在多道程序环境下，处理器的分配和运行都是以**进程（或线程）**为基本单位，因而对处理器的管理可以归结为对进程的管理。并发是指在计算机内同时运行多个进程，因此进程何时创建、何时撤销、如何管理、如何避免冲突、合理共享就是进程管理的主要任务。

进程管理的主要功能包括：进程控制、进程同步、进程通信、死锁处理、处理器调度等

基本概念

**进程是进程实体的运行过程，是操作系统进行资源调度和分配的基本单位。**从结构上来看进程实体由程序段、数据段和进程控制块（PCB）三部分组成。PCB是进程存在的唯一标志。

PCB所包含的信息主要有四大类：进程标志信息、进程控制信息、进程资源信息和CPU现场信息。

单处理及系统（不包含多核的情况），同一时刻只能有一个进程占用处理机，因此进程之间不能并行执行。每一时刻最多只有一个进程处于运行态。

进程的通信

进程与程序

进程是暂时的，程序是永久的；进程是动态的，程序时静态的；进程至少由代码、数据和PCB组成，程序仅需代码和数据；程序代码经过多次创建可对应不同的进程，而同一个系统的进程（或线程）可以由系统调用的方法被不同的进程（或线程多次使用）。

进程通信机制

**每个进程都有自己独立的地址空间。**在操作系统和硬件的地址保护机制下，进程无法访问其他进程的地址空间，所以必须借助操作系统的系统调用函数实现进程通信。

常见的高级通信机制包括共享存储 、消息通信和管道通信三大类。其他还有文件映射和套接字等。

共享存储

共享存储分为两种：基于数据结构的低级方式共享；基于存储区的高级方式共享。

消息通信

管道通信

管道是用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又称为pipe文件。管道通信只能采用半双工通信。

允许多个进程向管道写入数据，允许多个进程向管道读出数据，操作系统负责保证数据的一致性。

管道是半双工的，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道；

只能用于父子进程或者兄弟进程之间（具有亲缘关系的进程）；

单独构成一 种独立的文件系统；管道对于管道两端的进程而言，就是一个文件，但不是一个普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，存在于内存之中；

数据的读出和写入：一个进程向管道中写的内容被管道另一端的进程读出。写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据。

线程

进程是资源分配的最小单位，线程是CPU调度的最小单位。

线程中的实体基本上不拥有 系统资源，只是有一点必不可少的、能保证独立 运行的资源，比如，在每个线程中都应具有一个用于控制线程运行的 线程控制块 TCB，用于指示被执行指令序列的 程序计数器、保留 局部变量、少数状态参数和 返回地址等的一组 寄存器和 堆栈。

进程可以创建进程和线程，线程也可以创建线程，但线程不可以创建进程。

线程实现

线程的实现可分为两种：用户级线程（User-Level Thread， ULT）和内核级线程（Kernel-Level Thread， KLT）。

用户级线程中，有关线程的管理（线程的创建、撤销和切换等）的所有工作都由应用程序完成，内核意识不到线程的存在。

内核级线程中，线程的管理的所有工作都由内核完成。

进程上下文

进程的上下文：用户级上下文、寄存器上下文以及系统级上下文。

• 用户级上下文: 正文、数据、用户堆栈以及共享存储区；
• 寄存器上下文: 通用寄存器、程序寄存器(EIP)、处理器状态寄存器(EFLAGS)、栈指针(ESP)；
• 系统级上下文: 进程控制块task_struct、内存管理信息(mm_struct、vm_area_struct、pgd、pte)、内核栈。

进程切换需要切换(1)(2)(3)；用户态和内核态的切换只需要(2)；线程的切换也只需要(2)

处理器调度

处理器的三级调度：高级调度（作业调度）、中级调度、低级调度（进程调度）。

三级调度的联系和区别

作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程就送入就绪队列。进程调度从就绪队列中选出一个进程，并将其状态改为运行态，将CPU分配给它。中级调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。当内存空间宽松时，通过中级调度选择具备运行条件的进程，将其唤醒。

作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间。

作业调度次数较少，中级调度次数略多，进程调度频率最高。

进程调度是最基本的，不可或缺。

调度的基本准则

$$ 周转时间 = 作业完成时间 - 作业提交时间 \ 带权周转时间 = 作业周全时间 /作业实际运行时间 $$

平均周转时间是指n个作业周转时间的平均值。

平均带权周转时间是指n个作业带权周转时间的平均值。

进程调度方式

进程调度的方式通常有**抢占式（剥夺式）和非抢占式（非剥夺式）**两种方式。

进程调度算法

先来先服务调度算法（FCFS）

先来先服务调度算法（FCFS）是一种简单的调度算法，可以用于作业调度与进程调度。

其基本思想是按照进程进入就绪队列的先后次序来分配处理器，采用非抢占的调度方式

对长作业有利，对短作业不利；有利于CPU繁忙型，不利于I/O繁忙型；

短作业优先调度算法（SJF）

短作业优先调度算法（SJF）用于进程调度时被称为短进程优先调度算法（SPF）。改算法既可以用于作业调度，也可以用于进程调度。

其基本思想就是把处理器分配给最快完成的作业（或进程）

导致长作业“饥饿”

平均等待时间、平均周转时间最少。

最短剩余时间优先调度算法（SRTN）

抢占式的短作业优先调度算法又称为最短剩余时间优先调度算法（SRTN）。每当有进程加入，就绪队列改变时，就需要调度。如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。

优先级调度算法

优先级调度算法是一种常用的进程调度算法，既可以用于作业调度，也可以用于进程调度。其基本思想是把处理器分配给优先级最高的进程。

根据进程创建后的优先级是否可以改变，进程的优先级可以分为两种：静态优先级和动态优先级。静态优先级是进程创建时确定，运行期间保持不变。动态优先级可以根据情况动态调整优先级大小。

一般优先级设置：系统进程大于用户进程、交互进程大于非交互进程、I/O进程大于计算型进程。

高响应比优先调度算法

高响应比优先调度算法综合了先来先服务和短作业优先两种调度算法的特点，即考虑了作业的等待时间和作业的运行时间两个因素，弥补了之前两种调度算法只考虑其中一个因素的不足。

**高响应比优先调度算法主要用于作业调度。**其基本思想是每次进行作业调度时，先计算就绪队列中的每个作业的响应比，挑选响应比最高的作业投入运行。

响应比的计算公式为 $$ 响应比 = (作业等待时间 + 估计运行时间) / 估计运行时间 $$

时间片轮转调度算法（RR）

时间片轮转调度算法主要适用于分时操作系统，在这种算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，即先来先服务原则，但仅能运行一个时间片，如100ms。在使用完一个时间片后，即进程并未完成其运行，他也必须释放出（被剥夺）处理机给下一个就绪进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等待下一次再运行。

时间片太大就会退化为先来先服务。

多级反馈队列调度算法

进程同步

临界资源和临界区

临界资源：一次仅允许一个进程使用的资源称为临界资源。

许多物理设备都属于临界资源，如打印机等；许多变量、数据等都可以被若干进程共享，也属于临界资源。

临界区：进程中访问临界资源的那段代码，又称临界段。

两种形式的制约关系

同步，也称为直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而等待、传递消息所产生的制约关系。进程间的直接制约关系源于他们之间的相互合作。

互斥，也称为间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许去访问临界资源。

**区分同步和互斥只需要记住：只要是同类进程即为互斥关系，不同类进程即为同步关系。**例如消费者与消费者就是互斥关系，消费者和生产者就是同步关系。

为禁止两个进程同时进入临界区，同步机制应遵循以下准则：

空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。

忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。

有限等待。对请求访问的进程，应保证能在有限时间内进入临界区。

让权等待。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

临界区调度的原则

1. 一次至多只有一个进程进入临界区执行

2. 如果已有进程在临界区中，试图进入此临界区的其他进程应等待

3. 进入临界区内的进程应在有限时间内退出，以便让等待队列中的一个进程进入

临界区互斥的基本方法

软件实现方法：单标志法、双标志法先检查、双标志法后检查、Peterson's Algorithm。

硬件实现方法：中断屏蔽法、TestAndSet指令、Swap指令。

方法	特性
单标志法	违背空闲让进
双标志法先检查	违背忙则等待
双标志法后检查	导致饥饿
Peterson	实现有限等待，不满足让权等待
硬件方法	不满足让权等待

管程

系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性。代表共享资源的数据结构，以及有对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程。

管程把对共享资源的操作封装起来，每次只允许一个进程进入管程，从而实现互斥。管程利用条件变量可以很容易实现同步与互斥关系。

条件变量

管程中可以定义条件变量用于描述阻塞原因。每个条件变量均可以使用两个操作wait和signal。

x.wait：当条件变量x所对应的资源缺乏时，进入管程的进程调用x.wait将自己插入到x的等待队列中。

x.signal：当条件变量x所对应的资源变得足够时，则调用x.signal，唤醒一个因缺乏x资源而阻塞的进程。

条件变量和信号量的比较：

• 相似点：条件变量的wait/signal操作类似于信号量的P/V操作，可以实现进程的阻塞和唤醒。
• 不同点：条件变量是没有值的，仅实现了“排队器的功能”，资源剩余数用共享数据结构表示；而信号量是有值的，信号量的值反映了资源剩余数。

🔒 死锁

死锁：若系统中存在一组进程，其中每个进程都占用了某种资源，但他们又都在等待其中另一个进程所占有的资源。如果这种等待永远不能结束，则说明系统出现了死锁。

死锁的处理策略有：死锁的预防、死锁的避免、死锁的检测和解除。

死锁定理：当且仅当此状态的进程-资源分配图是不可完全简化的，则说明发生了死锁。这一充分条件称为死锁定理。

具体请看思维导图。

死锁产生的必要条件

互斥条件：临界资源是独占资源，进程应互斥且排他地使用这些资源。

不剥夺条件：又称不可抢占，已获资源只能由进程自愿释放，不允许被其他进程剥夺。

占有和等待条件：进程在请求资源得不到满足而等待时，不释放已占有资源。

循环等待条件：又称环路条件，存在循环等待链，其中每个进程都在等待链中等待下一进程所持有的资源，造成这组进程处于永远等待状态。

死锁的处理策略

死锁的防止：通过限制资源申请和分配方法来使系统不会进入死锁

死锁的避免：对进程资源申请不加限制，但在分配之前会作安全检查，只有安全才进行分配

死锁的检测和解除：对进程资源申请和分配均不加限制，但周期性地运行死锁检测程序，若发现死锁，则采用一定的策略使系统从死锁状态中解除出来。

死锁的检测和解除

死锁的解除方法主要有：

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

撤销进程法。强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程的代价的高低来进行。

进程回退法。让一个或多个进程回退到足以回避死锁的地步，进程回退时资源释放资源而非被剥夺。要求系统保持进程的历史信息，设置还原点。

死锁与饥饿

饥饿并不表示系统一定会死锁，但至少有一个进程的执行被无限期推迟。

• 进入饥饿的状态进程可以只有一个，而两个或两个以上的进程才有可能发生死锁。
• 饥饿状态的进程可以是就绪进程，死锁的全部进程必定是阻塞的。

经典同步问题

1、画图理解题目

2、判断题目类型

生产者消费者模型

特征：有一定大小的容器，有向容器操作的对象

分析：

生产者A -> 所关心的内容；消费者B -> 所关心的内容；

对容器的操作需要用互斥信号量夹紧

读者写者模型

特征：有某种资源（文件），会有占有问题。写者会改变该资源，但读者不会。且读者会呈现团体性，第一个读者需要申请文件，最后一个读者需要释放文件

分析：

写者 -> 文件是否被占有；

读者团： 第一个读者需要关心文件是否被占有，中间读者只是增加count数量，最后一个读者释放文件

因为有并发性、异步性、独立性所以每个变量操作一定要加互斥操作。

3、分析进程数目和填写进程模板

semaphore mutex = 1;

A() {
    while(1) {
        
    }
}

B() {
    while(1) {
        
    }
}

4、补充基本代码

5、补充PV代码

6、调整代码

添加semaphore变量声明