操作系统5:进程管理

正文索引 [隐藏]

1. 进程

进程:程序的一次执行过程,是资源分配和调度的一个基本单位

引入背景:多道程序设计的环境下,程序并发执行,破坏程序的封闭性和可再现性,程序、计算不再一一对应,程序这个概念已经不能如是反应程序活动的特征,因此用进程来描述

进程的特点:动态性(有生命周期)、并发性、独立性、异步性、结构性

进程 vs 程序

  1. 进程是程序的一次执行,是一个动态的概念;而程序是一组有序的指令, 是一种静态的概念。即进程是程序执行的动态过程,而程序则是进程运行的静态文本。
  2. 一个进程可以执行一个或几个程序,同一个程序也可能由几个进程同时执行。
  3. 程序可长期保存,而进程是有生命周期的。
  4. 进程是并发实体, 而程序则不是。

I. PCB 表

记录 OS 所需的、用于描述进程当前情况以及控制进程运行的全部信息,是进程存在的唯一标志,常驻内存

image-20191215151645283

  • process state

    image-20191215152151801

  • process number:进程号,唯一标明一个进程

  • program counter:指向该进程需要执行的下一条指令的地址

  • register:中断发生时的需要保存的寄存器值

  • memory limits:指明进程所在的内存范围,避免溢出

II. 进程控制

image-20191215170829716

一个进程如何从磁盘的程序启动?一共要经历两个过程:

  • long-term scheduler(job scheduler):就是将磁盘上的程序经过内存分配算法读入内存,多个进程在内存中形成等待队列,等待队列中进程的状态为 readyimage-20191215154511566
  • short-term scheduler(CPU scheduler):从内存中选择合适的进程分配 CPU,开始执行进程

另外,程序在运行到一半的时候也有可能被挂起,这时候需要的是 medium-term scheduler:将正在执行的程序挂起,放回等待序列

image-20191215154906130

2. CPU 调度

I. 调度方式

抢占方式

Preemptive scheduling:抢占式调度,调度时进程可以将其他正在运行的进程 “挤出 CPU”

Nonpreemptive scheduling:非抢占式调度,进程一旦进入 CPU 就稳了,不会被其他进程强行挂起

队列方式

Multilevel Queue Scheduling:好多进程队列,不同队列采用不同调度算法

image-20191215160538285

Multilevel Feedback Queue Scheduling:如果一个进程占用过多的CPU时间,移到较低优先级的队列,因此,I / O绑定和交互过程具有更高的优先级

image-20191215160711874

II. 调度算法

FCFS

先来先得

image-20191215155948595
image-20191215160016474

SJF

谁用时少谁先用

image-20191215160113083
image-20191215160121744

Priority Scheduling

谁优先级高谁先来

image-20191215160216825
image-20191215160232969

Round-Robing Scheduling

一人用一会儿

image-20191215160316575
image-20191215160329256

III. 评价指标

Throughput:单位时间内完成的进程数

Turnaround Time: 周转时间 = 结束时间 - 提交时间

Waiting Time:进程在等待队列中等待的总时间

Response Time:响应时间 = 等待时间 + 运行时间

在批处理系统中,当产生第一次响应时,就是作业完成了,此时周转时间 = 响应时间;

而在分时系统中,时间片结束后,就认为产生了第一个响应,此时周转时间 > 响应时间

IV. 实时调度

有些进程需要进行实时响应,其优先级非常高:

  • Soft real-time systems: 只保证进程优先级,但是不保证啥时候能分配处理器
  • Hard real-time systems: 保证在 ddl 之前分配处理器,超出 ddl 这个进程也就不用被响应了

评价指标

  • Interrupt latency:从中断到达CPU到开始处理该中断的时间间隔
  • Dispatch latency:停止一个进程、开始另一个进程的延迟

V. 多处理器调度

非对称调度: 系统进程被分配一个特定处理器

对称调度:所有进程随机分配处理器

Processor Affinity:特定进程放置在特定处理器中运行

负载均衡

如果一个 CPU 忙碌而另外一个 CPU 闲着,就要把一些进程分配过去

image-20191215163356298

3. 进程间关系

I. 进程通信

IPC, Inter Process Communication

image-20191215153020485

  • 消息传递式:另外开辟一段 message queue 的空间,所有共享信息通过 send-receive 指令送入/取出
  • 共享内存式:直接将内存共享,访问共享内存资源的时候通过 生产者-消费者 模型进行同步

II. 进程同步

资源锁

互斥:进程在运行中争用系统资源,对于独占型资源,只能一个进程使用完,另一个进程才能使用

资源一旦加上锁后就不能被其他进程访问,可以实现资源互斥,通过 Peterson‘s Solution 实现:

image-20191215165849164

信号量

资源锁的进阶版,通过 P-V 操作可实现资源互斥、进程同步

  • P 操作:信号量 --
  • V 操作:信号量 ++

互斥

image-20191215165009976

同步:在异步环境下,互相合作的进程按各自独立的速度向前推进,但在某些确定点上必须协调工作。即当某个进程到达这些点后,等待另一进程发来信息,否则就只能停下来等待其操作的完成,进程间的这种协同关系称为进程同步

image-20191215164845664

管程

管程:锁 +条件变量 + 局部变量 + 进程,同一时间只能有一个进程活跃于管程内(即自由使用管程内的变量)

假设 x 是一个条件变量,则管程中的进程可使用以两种操作完成同步:

  • x.wait():挂起正在活跃的进程,等待 signal
  • x.signal():唤醒之前调用过 x.wait() 的进程

4. 死锁

死锁:死锁是指两个或两个以上的进程在执行过程中,由于系统资源不足进程推进顺序不合适造成的一种阻塞现象,若无外力作用,它们都将无法推进

image-20191215172310065

举例(资源分配图表示)

资源分配图,箭头指向 R 表示等待资源,指向 P 表示分配资源

image-20191215172638129

产生死锁的必要条件

  • 互斥使用
  • 不可抢占
  • 请求保持
  • 环路等待

I. 死锁的静态预防

总体思路是破坏死锁产生的必要条件:

  • 资源静态分配法:进程运行前一次性申请全部资源
  • 资源顺序分配法:系统全部资源编号,只允许按编号顺序递增申请,破坏环路
  • 申请新资源前,释放已有资源

II. 死锁的动态避免

总体思路是每当进程申请资源时,避免进入不安全状态:

  • 安全:当多个进程动态申请资源时,系统按某一顺序依次为每个进程分配所需资源,使每个进程都可以在最终得到最大需求量后依次顺利完成
  • 不安全:当前状态可能死锁

如何检测一个状态是否是安全的呢?使用银行家算法

银行家算法

  • Allocation 表:进程已分配资源
  • Max 表:进程所需总资源
  • Available 表:系统当前剩余资源

image-20191215173410825

  1. 首先算出 Need 表,记录进程还需分配资源

image-20191215173454452

  1. 列出 FINISH 表,表示分配是否完成,先将所有项置为 f:

image-20191215173640888

  1. 接下来找出 need 比 available 小的:

image-20191215173729550

  1. P2 的需求小于能用的,所以配置给他再回收:

image-20191215173841723

  1. 更新 FINISH 表:

image-20191215173859055

  1. 转 3,若最终能全部变为 true,就是安全状态,若出现资源不够的情况,就是不安全状态

III. 死锁的检测与恢复

死锁的检测:检测当前状态,如果已经不安全,就进入了死锁状态

恢复:

  • 删除法:删除死锁进程,将资源分配给其他进程
  • 剥夺法:剥夺某些进程的资源

5. 线程

线程:又称轻型进程,是进程内的一个可调度的实体,是处理机调度的基本单位

进程 vs 线程

image-20191215174954157

  1. 调度方面:线程作为调度分派的基本单位,而进程则是资源分配和调度的一个基本单位;
  2. 并发性方面:进程之间可以并发,一个进程的多线程之间也可并发执行;
  3. 拥有资源方面:进程作为拥有资源的基本单位,而线程只拥有少量必不可少的资源,但它可以访问所属进程的资源
  4. 系统开销方面:进程切换要涉及到进程环境的切换,开销较大,而线程间切换只需保存和设置少量的寄存器内容,开销远小于进程切换开销

用户线程 vs 内核线程

  • 用户线程:存在于用户空间中,其创建、撤消和切换都不需系统支持,用户进程需要内核线程进行支持
  • 内核线程:是依赖于内核的,其创建、撤消和切换都是由内核实现的

image-20191215175041818
image-20191215175053702
image-20191215175120360
image-20191215175135398