操作系统--进程管理

1、进程的概述

1.1 进程的定义

​ 进程使进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

 进程实体由程序段、数据段、PCB（进程控制块）组成

1.2 进程的组成

（1）程序段：存放要执行的代码

（2）数据段：存放程序执行过程中处理的各种数据

（3）PCB（进程控制块）

• 进程描述信息
  • 进程标识符PID
  • 用户标识符UID
• 进程控制和管理信息
  • 进程当前状态
  • 进程优先级
• 资源分配清单
  • 程序段指针
  • 数据段指针
  • 分配的各种硬件资源
• 处理机相关信息
  • 各种寄存器的值

1.3 进程的组织方式

（1）链接方式：按照进程状态将PCB分为多个队列

（2）索引方式：根据进程状态的不同建立几张索引表

1.4 进程的特征

• 动态性:进程是动态的产生,变化和消亡的,只是一次执行过程.
• 并发性:内存中有多个进行实体,可并发执行
• 独立性:进程是能独立运行,独立获得资源,独立接受调度的基本单位
• 异步性:各个进程之间的执行不需要等待
• 结构性:每个进程的结构都是一致的,都是PCB+程序段+数据段

2、进程的转换

3、进程控制

​  进程控制就是实现进程状态的转换.

​  进程控制是通过原语实现的.原语则是采用关中断和开中断两个指令实现的。

 进程控制相关的原语都做了3件事情:

• 更新PCB中的信息
  • 修改进程状态标志
  • 保存运行环境或者从PCB恢复运行环境
• 将PCB插入到相应的状态队列
• 分配/回收资源

4、进程通信

​  进程通信就是进程时间的信息交换.但进程之间的内存空间是相互独立的.进程间通信保证了进程间的安全通信.

(1) 共享存储

​  操作系统为两个进程分配一片可以共享访问的内存空间,两个进程可以使用这个共享空间进行信息交换.

​  两个进程对共享空间的访问必须是互斥的.

1). 基于数据结构的共享

​  速度较慢,是一种低级的通信方式

2). 基于存储区的共享

​  由两个进程决定共享空间中的数据格式,相比之下这种方式速度更快,是一种更高级的通信方式.

(2) 管道通信

​  在两个进程中开辟一个管道,用于信息的传输.

​  管道只能由一个进程填满,再由一个进程全部取出.一个管道不能双向通信(半双工)

​  各个进程对管道的访问互斥

(3) 消息传递

​  进程之间以格式化消息传递信息,进程使用消息的发送和接收原语进行数据交换

1). 直接通信方式

​  发送进程直接将消息挂到接收进程的消息缓冲队列上

2). 间接通信方式

​  消息先发送到中间实体中,消息头中包含了消息的接收进程等等信息.

​  接收进程会主动在中间实体中查阅信息.

5、线程

5.1 线程的概念

​  线程是一个基本的CPU执行单元,也是程序执行流的最小单位

​  线程是CPU调度的单位，进程是资源分配的单位

​  线程间的并发不需要切换进程环境,系统开销小

线程的特性:

• 线程是处理机调度的单位
• 多核CPU可以同时运行不同的多个线程
• 线程有线程ID,线程控制块TCB
• 线程也有就绪,阻塞,运行三态
• 线程不占有系统资源
• 同一个进程的线程共享进程的内存空间

5.2 线程的实现方式

​  用户级线程:由应用程序通过线程库实现.用户级线程的线程切换可以再用户态下完成,无需操作系统的干预

​  内核级线程:线程的管理工作由操作系统内核完成,所以线程的切换都需要在核心态下完成（内核级线程才是处理机分配的单位）

5.2 多线程模型

• 多对一模型:一个进程的多个用户级线程映射到一个内核级线程
  • 优点:用户级线程的切换不需要CPU切换到核心态
  • 缺点:用户级线程一旦被阻塞,整个进程都会被阻塞
• 一对一模型:每一个用户级线程都对应一个内核级线程
  • 优点:一个线程被阻塞后,别的线程还可以继续执行,并发能力强
  • 缺点:管理成本高
• 多对多模型:n个用户级线程映射到m和内核级线程(n >= m)
  • 克服了多对一模型并发度不高的确定,也克服了一对一模型中进程管理开销太大的缺点

6、处理机调度

6.1 概念

 按某种算法选择一个进程将处理机分配给它

6.2 三个层次的调度

• 高级调度（作业调度）：将合适的作业调入内存，并为其创建进程
• 中级调度（内存调度）：从挂起队列中选择进程将其数据调回内存
• 低级调度（进程调度）：从就绪队列中选择一个进程为其分配处理机

6.3 三层调度的联系与对比

	作用	发生位置	频率	对进程状态的影响
高级调度（作业调度）	从后备队列的作业中挑选出一个,为它们分配内存等必要资源,并建立响应的进程(建立PCB)	外存—>内存	低	无—>创建态—>就绪态
中级调度（内存调度）	从挂起队列中选择进程将其数据调回内存	外存—>内存	中	挂起态—>就绪态/阻塞态
低级调度（进程调度）	从就绪队列中选择一个进程为其分配处理机	内存—>CPU	高	就绪态—>运行态

6.4 进程的七态模型

 为了减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存从而变为“挂起态”

7、进程调度

7.1 进程调度的时机

• 主动放弃:进程正常终止,发生异常,主动请求阻塞(等待I/O)
• 被动放弃:分配的时间片用完,有更紧急的事情处理(中断),被强占CPU资源

 不能进行进程调度的情况:

• 处理中断的过程中
• 处于内核程序临界区中(普通临界区可以被调度)
• 原子操作过程中(原语)

7.2 进程调度的方式

• 抢占式
  • 只允许进程主动放弃处理机
  • 实现简单,系统开销小
  • 无法及时处理紧急任务,适合早期的批处理程序
• 非抢占式
  • 当一个进程在处理机上运行时,出现了另一个更紧急的进程需要使用处理机,那么此时运行的进程会让出CPU权限.
  • 可以优先处理更紧急的进程,也可实现让各进程按时间片轮流执行的功能
  • 适用于分时操作系统,实时操作系统

7.3 调度算法的评价指标

• CPU利用率 = 忙碌时间/总时间

• 系统吞吐量 = 完成的作业数量/花费时间

• 周转时间 = 作业完成时间-作业提交时间

  • 平均周转时间 = 各作业周转时间之和/作业数
  • 带权周转时间 = 作业周转时间/作业实际运行时间(永远大于1)
  • 平均带权周转时间 = 各作业带权周转时间之和/作业数

• 等待时间：进程等待被服务的时间之和（等待I/O不算）

• 响应时间：从用户提交请求到首次产生响应所用的时间

  eg:
  

7.4 调度算法

（1）先来先服务(FCFS)

​  按照作业到达后背队列的顺序进行执行,不可抢占,不会发生饥饿

​  优点:公平,实现简单

 ​ 缺点:对长作业有利,对短作业不利

（2）短作业优先(SJF)

  每次选择作业时,选择当前所有作业中最短的作业执行.当作业时间一致时,先执行早到达的.会导致饥饿

​  优点:平均等待时间和平均周转时间短

​  缺点:对短作业有利,对长作业不利,会产生饥饿现象

（3）高响应比优先(HRRN)

​  每次选择作业是计算响应比=（等待时间+要求服务时间）/要求服务时间

​  综合考虑等待时间和运行时间,无明显缺点.不会导致饥饿.

eg:

（4）时间片轮转(RR)

​  时间片是将CPU每次分配的时间设置为一样的,公平地为每个进程轮流(根据作业到达的顺序)分配时间片.

​  根据时钟装置发出的时钟中断来进行抢占,所以是抢占式的.

​  不会导致饥饿.

​  优点:公平,响应快,适用与分时操作系统

​  缺点:不区分任务的紧急程度,由于高频度的进程切换会有一定开销.

​  时间片过短会导致开销过大,时间片过长会导致退化成先来先服务.

（5）优先级调度算法

​  按照优先级进行选择

​ 优点:区分任务的紧急成都,适用于实时操作系统

​  缺点:可能导致饥饿.

（6）多级反馈队列

1. 设置多级队列,优先级从高到低,时间片从小到大.
2. 新进程直接进入一级队列
3. 分配完时间片进入下一级队列队尾,如果是被处理机抢占的进程重新回到自己所在的队列尾.
4. 当前一级队列为空时,才会为下一级队列中的进程分配时间片.

​  到最后一级的队列就不会再向下降级了

​  优点:公平,可以灵活调整对进程的偏好程度(不降级的设置)

​  缺点:会造成饥饿

7.5 调度算法区别

算法	规则	抢占	优点	缺点	是否饥饿
先来先服务(FCFS)	按作业到达顺序进行服务	非抢占	公平、简单	对短作业不利	不会
短作业优先(SJF)	最短作业优先服务	都有	最短的平均等待时间、周转时间	对长作业不利	会
高响应比优先(HRRN)	按响应比服务	非抢占	FCFS与SJF的折中算法		不会
时间片轮转(RR)	按到达顺序，轮流执行一个时间片	抢占	公平（适用于分时系统）	频繁切换开销大	会
优先级调度算法	按优先级执行	都有	区分优先级（适用于实时系统）	会导致饥饿	会
多级反馈队列	略	抢占式	平衡

 早期的批处理系统：先来先服务、短作业优先、高响应比优先算法

 交互式系统：时间片轮转、优先级调度算法、多级反馈队列

8、进程互斥

8.1 两种资源共享方法

• 互斥共享方式：一个时间段内只允许一个进程访问该资源
• 同时共享方式：允许一个时间端内由多个进程“同时”对他们进行访问

8.2 进程的同步与互斥

• 进程同步（直接制约关系）：进程之间需要相互配合地完成工作，个进程的工作推进需要遵循一定的先后顺序
• 进程互斥（间接制约关系）：对临界资源的访问，需要互斥的进行，即同一时间端内只能允许一个进程访问该资源

8.3 进程互斥

 对临界资源的互斥访问，可以在逻辑上分为四个部分

• 进入区：检查是否可进入临界区，若可进入，则“上锁”

• 临界区：访问临界区的代码

• 退出区：“解锁”

• 剩余区：其余代码部分

8.4 原则

• 空闲让进：临界区空闲时，应允许一个进程访问

• 忙则等待：临界区正在被访问时，其他试图访问的进程需要等待

• 有限等待：要在有限时间内进入临界区，保证不会饥饿

• 让权等待：进不来临界区的进程，要释放处理机，防止忙等

8.5 进程互斥的软件实现

(1) 单标志法

 思想:在进入区只做"检查",不上锁,在退出区把临界区的使用权交给另一个进程

 问题:不遵循"空闲让进"原则

(2) 双标志先检查

 思想：在进入区先"检查"后"上锁",退出区"解锁"

 问题：不遵循"忙则等待"原则

(3) 双标志后检查

 思想：在进入区先"上锁"后"检查",退出区"解锁"

 问题：不遵循"空闲让进、有限等待"原则

(4) Peterson原则

 思想：在进入区"主动争取-主动谦让-检查对方是否想进、己方是否谦让"

 问题：不遵循“让全等待”原则，会发生忙等

8.6 进程互斥的硬件实现

（1）中断屏蔽方法

​  实现：使用原语（“开/关中断”）指令实现

​  优点：简单高效

​  缺点：只适用于单处理机

（2）TestAndSet指令

​  实现：原子性的进行上锁和检查操作

​  优点：实现简单，适用于多处理机环境

​  缺点：不满足让权等待

（3）Swap指令

​  实现：原子性的交换两个值

9、信号量机制

9.1 信号量概念

• 使用一对原语对信号量进行操作，从而实现进程互斥与同步
• 信号量就是一个变量,可以用来表示系统中的某种资源的数量.
• 使用wait(S)原语减少一个信号量(相当于获取锁),使用signal(S)原语增加一个信号量(解锁)，通常也简称为P(S)、V(S)操作

9.2 信号量类型

(1) 整型信号量

​  符合“有限等待”原则 ,信号量定义为一个整型量，根据初始情况赋相应的值，仅能通过两个原子操作来访问

P操作 wait(S):

while (S <= 0);
S--;

V操作 signal(S):

S++;

(2) 记录型信号量

 整型变量value(代表资源数目)、进程链表L (链接所有等待进程)

  Value>0，表示当前可用资源的数量；
  Value≤0，其绝对值表示等待使用该资源的进程数，即在该信号量队列上排队的PCB的个数

​  wait(S)先设置信号量的值减一,然后判断当前信号量的状态,如果小于零,将当前进程添加到等待队列

​  signal(S)先设置信号量的值加一,然后判断信号量的值小于等于0,从等待队列中唤醒第一个进程

 typedef struct{
 	int value;	//剩余资源数
 	struct process *L;  //等待队列
 }semaphore;

P操作 wait(S):

S.value--;
if(S.value<0) block(S.L);	//如果小于零,将当前进程添加到等待队列

V操作 signal(S):

S.value++;
if(S.value<=0) wakeup(S.L);  //如果小于等于0,从等待队列中唤醒第一个进程

9.3 实现进程的同步与互斥

• 进程互斥：设置互斥信号量初值为1，临界区前P后V操作
• 进程同步：设置同步信号量初值为0，临界区前V后P操作
• 前驱关系：为每对前驱关系设置同步信号量初值为0，（每个都）前V后P操作

9.4 进程同步/互斥经典问题

10、死锁

10.1 概念

​  各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进。

​  发生死锁：对不可剥夺资源的不合理分配，可能会导致死锁

10.2 死锁的必要条件

• 互斥条件：即在一段时间内某资源只由一个进程占用。如果其它进程请求该资源则只能等待。
• 请求和保持条件：指进程已经保持了至少一个资源，又请求新资源而被阻塞，但又对自己已获得的其它资源保持不放。
• 不可剥夺条件：已获得资源不能被抢占，只能进程自己释放
• 循环等待条件：即存在一个进程——资源的环形链。

10.3 死锁的处理策略

• 预防死锁：破坏死锁产生的四个必要条件
• 避免死锁：避免系统进入不安全状态（银行家算法）
• 死锁的检查和解除：允许死锁发生，系统负责检测出死锁并解除

10.4 预防死锁

（1）破环互斥条件

​  实现：将临界资源改造为可共享使用的资源（如SPOOLing技术）

​  缺点：可行性不高，一般认为互斥条件是无法改变的

（2）破坏不可剥夺条件

​  方案一：申请的资源得不到满足时，立即释放所拥有的所有资源

​  方案二：申请的资源被其他进程占用时，由操作系统协助剥夺

​  缺点：实现复杂，剥夺资源可能导致部分工作失效，且开销大

（3）破坏请求和保持条件

​  实现：运行前分配好所有的需要的资源，之后一直保持

​  缺点：资源利用率第，可能导致饥饿

（4）破坏循环等待条件

​  实现：给资源编号，必须按编号从小到大的顺序申请资源

​  缺点：不方便增加新设备，会导致资源浪费

10.5 避免死锁

​  避免死锁的实质：系统在进行资源分配时，如何使系统不进入不安全状态

​  系统的安全状态：系统在进行资源分配之前，应先计算此次资源分配的安全性。所谓安全状态，是指系统能按某种进程顺序(P1，P2，…，Pn)每个进程 Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称(P1，P2，…，Pn)为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

银行家算法

（1）数据结构

• 可利用资源向量 Available：表示还有多少可用资源，一维数组（长度m）

• 最大需求矩阵 Max：表示各进程对资源的最大需求，二维数组（n*m）

• 分配矩阵 Allocation：表示已经给各进程分配的资源，二维数组（n*m）

• 需求矩阵 Need：表示各进程最多还需要多少资源（Max-Allocation=Need）

• 申请数组 Request：表示进程此次申请的各种资源数，一维数组（长度m）

eg:

（2）银行家算法步骤

1. 检查此次申请是否超过了之前声明的最大需求数
2. 检查此时系统剩余的可用资源是否还能满足此次请求
3. 试探分配，更改各数据结构
4. 用安全性算法检查此次分配是否会导致系统进入不安全状态

（3）安全性算法步骤

1. 检查当前的剩余可用资源是否能满足某个进程的最大需求
2. 如果可以就把该进程加入安全序列，并把该进程持有的资源全部收回
3. 重复上述步骤，看最终是否能让所有进程都加入安全序列

10.6 死锁的检测

​ （1）资源分配图（数据结构）

​  进程结点（对应一个进程）

​  资源结点（对应一类资源）

​  进程结点—>资源结点（表示进程想要申请几个资源）

​  资源结点—>进程结点（表示已经为进程分配了几个资源）

（2）死锁检测算法

​  根据某种算法，利用上述数据结构，如果最终能消除所有边则不会发生死锁。如果不能，则最终还连着边的进程则进入死锁状态

（3）死锁定理

​  弱资源分配图时不可完全简化的，说明发生了死锁

10.7 死锁的解除

• 资源剥夺法：挂起某些死锁进程，并抢占它的资源分配给其他的死锁进程
• 撤销进程法：强制撤销部分死锁进程并剥夺资源
• 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步