第二章、进程管理

文章目录

• 一、进程与线程
• • 1、进程的定义、特征、组成、组织
  • • （1） 进程的定义
    • （2） 进程的特征
    • （3） 进程的组成
    • （4） 进程的组织
  • 2、进程的状态与转换
  • • （1） 总览
    • （2） 原语实现进程控制
  • 3、线程概念与多线程模型
  • • （1） 概述
    • （2） 线程属性
    • （3） 线程的实现方式
    • （4） 多线程模型
  • 4、进程与线程的区别与联系
  • 5、进程间通信
  • • （1） 管道
    • （2） 共享内存
    • （3） 消息队列
    • （4） 信号量
    • （5） Socket
• 二、处理机调度
• • 1、概览
  • 2、调度的基本概念
  • 3、调度的三个层次
  • • （1） 作业调度（高级调度）
    • （2） 内存调度（中级调度）
    • （3） 进程调度（低级调度）
    • （4） 进程的挂起与七状态模型
    • （5） 三层调度的联系与对比
  • 4、进程调度的时机
  • • （1）什么时候需要进程调度
    • （2）什么时候不能进行进程调度
    • （3）OS内核程序临界区与普通临界区的进程调度情况
  • 5、进程调度的方式
  • 6、进程切换过程
  • 7、调度算法评价指标
  • • （1） CPU利用率
    • （2）系统吞吐量
    • （3）周转时间
    • （4）等待时间
    • （5）响应时间
  • 8、调度算法对比
  • • （1）FCFS —— 先到先服务
    • （2）SJF —— 短作业优先
    • （3）HRRN —— 高响应比优先
    • （4）前三种调度算法对比
    • （5）时间片轮转调度算法
    • （6）优先级调度算法
    • （7）多级反馈队列调度算法
    • （8）后三种调度算法对比
• 三、进程同步与互斥
• • 1、概览
  • 2、概念
  • • （1）进程同步
    • （2）进程互斥
  • 3、临界区资源互斥访问的软件实现方法
  • • （1）思维导图
    • （2）单标志法
    • （3）双标志先检查法
    • （4）双标志后检查法
    • （5）Perterson算法
  • 4、临界区资源互斥访问的硬件实现方法
  • • （1）思维导图
    • （2）中断屏蔽方法
    • （3）TestAndSet指令
    • （4）Swap指令
  • 5、信号量机制
  • • （1）思维导图
    • （2）为什么引入
    • （3）什么是信号量机制
    • （4）整形信号量
    • （5）记录型信号量
    • （6）一个例子
    • （7）记录型信号量知识点总结
  • 6、信号量机制实现进程的互斥、同步与前驱关系
  • • （1）思维导图
    • （2）信号量实现进程互斥
    • （3）信号量实现进程同步
    • （4）信号量实现前驱关系
  • 7、管程
  • • （1）思维导图
    • （2）为什么引入管程
    • （3）管程的组成及基本特征
    • （4）管程实现生产着消费者问题
    • （5）Java中类似于管程的机制
• 四、死锁
• • 1、概览
  • 2、什么是死锁
  • 3、死锁、饥饿、死循环之间的区别
  • 4、死锁的产生
  • • （1）死锁产生的必要条件
    • （2）什么时候会发生死锁
  • 5、死锁的处理策略
  • • （1）预防死锁
    • • ① 破坏互斥条件
      • ② 破坏不可剥夺条件
      • ③ 破坏请求和保持条件
      • ④ 破坏循环等待条件
    • （2）避免死锁
    • • ① 什么是安全序列
      • ② 安全序列、安全状态、不安全状态 与 死锁 联系
      • ③ 如何避免进入不安全状态 —— 银行家算法
      • ④ 代码实现
    • （3）死锁的检测
    • （4）死锁的解除

一、进程与线程

1、进程的定义、特征、组成、组织

（1） 进程的定义

• 进程是 一个具有一定独立功能的程序在一个数据集上的一次动态执行的过程，是操作系统进行资源分配和调度的一个独立单位，是应用程序运行的载体。
• 进程曾经是分时系统的基本运作单位； 在面向进程设计的系统（如早期的UNIX）中，进程是程序的基本执行实体； 在面向线程设计的系统（如当代多数操作系统）中，进程本身不是基本运行单位，而是线程的容器。

（2） 进程的特征

（3） 进程的组成

而其中最重要的就是进程控制块PCB（Process Control Block）

• PCB是进程存在的唯一标志。
• PCB通常包含的内容：

• 

（4） 进程的组织

① 链接方式

② 索引方式

2、进程的状态与转换

（1） 总览

（2） 原语实现进程控制

① 总览

② 进程控制大致图解

③ 进程创建原语

④ 进程终止原语

⑤ 进程唤醒和阻塞原语（必须成对出现，成对使用）

⑥ 进程切换原语

3、线程概念与多线程模型

（1） 概述

（2） 线程属性

（3） 线程的实现方式

线程的实现分为两类：用户级线程(User-Level Thread,UTL)和内核级线程(Kernel-Level Thread, KTL)l。内核级线程又称内核支持的线程。

① 用户级线程

② 内核级线程

③ 特殊的组合方式及重点注意

（4） 多线程模型

① 多对一模型

② 一对一模型

③ 多对多模型

此种模型效率是三种模型中最好的

4、进程与线程的区别与联系

（4）区别

5、进程间通信

为什么要引入进程间通信：

• 各进程拥有的地址空间独立
• 为保证安全，一个进程不能访问另一个进程的地址空间
• 进程之间时常需要相互交换数据

进程间通信方式主要有五种：管道、共享内存、消息队列、信号量、Socket

（1） 管道

管道，通常指无名管道，是UNIX系统IPC最古老的方式。管道分为无名管道 和 命名管道 两种 ， 除了建立、打开、删除的方式不同外，这两种管道几乎是一样的。他们都是通过内核缓冲区实现数据传输。

特点：

• 单管道为半双工，要实现双向同时传输可通过建立双管道实现
• 只能用于具有亲缘关系的进程之间的通信
• 管道的实质为内核缓冲区，进程以先进先出的方式从缓冲区存取数据
• 写满才能读，读完才能写
• 一个数据只能被读一次，读出以后便在缓冲区不复存在了

（2） 共享内存

共享内存允许两个或多个进程共享一个给定的存储区，这一段存储区可以被两个或两个以上的进程映射至自身的地址空间中，一个进程写入共享内存的信息，可以被其他使用这个共享内存的进程，通过一个简单的内存读取错做读出，从而实现了进程间的通信。

采用共享内存进行通信的一个主要好处是效率高，因为进程可以直接读写内存，而不需要任何数据的拷贝，对于像管道和消息队里等通信方式，则需要再内核和用户空间进行四次的数据拷贝，而共享内存则只拷贝两次：一次从输入文件到共享内存区，另一次从共享内存到输出文件。

共享内存有两种实现方式：

1、基于数据结构的共享

2、基于存储区的共享

（3） 消息队列

消息队列，就是一个消息的链表，是一系列保存在内核中消息的列表。用户进程可以向消息队列添加消息，也可以向消息队列读取消息。

消息队列与管道通信相比，其优势是对每个消息指定特定的消息类型，接收的时候不需要按照队列次序，而是可以根据自定义条件接收特定类型的消息。

（4） 信号量

信号量（semaphore）与已经介绍过的 IPC 结构不同，它是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。

1、特点

• 信号量用于进程间同步，若要在进程间传递数据需要结合共享内存。
• 信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作。
• 每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。
• 支持信号量组。

2、原型

• 最简单的信号量是只能取 0 和 1 的变量，这也是信号量最常见的一种形式，叫做二值信号量（Binary Semaphore）。而可以取多个正整数的信号量被称为通用信号量。

Linux 下的信号量函数都是在通用的信号量数组上进行操作，而不是在一个单一的二值信号量上进行操作。

（5） Socket

适合同一主机的不同进程间和不同主机的进程间进行全双工网络通信。在所有提供了TCP/IP协议栈的操作系统中几乎都提供了socket，而所有这样操作系统，对套接字的编程方法几乎是完全一样的，即“网络编程”。

二、处理机调度

1、概览

2、调度的基本概念

3、调度的三个层次

（1） 作业调度（高级调度）

（2） 内存调度（中级调度）

（3） 进程调度（低级调度）

（4） 进程的挂起与七状态模型

（5） 三层调度的联系与对比

4、进程调度的时机

（1）什么时候需要进程调度

（2）什么时候不能进行进程调度

（3）OS内核程序临界区与普通临界区的进程调度情况

5、进程调度的方式

• 所谓进程调度方式，是指当某个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要处理，即有优先权更高的进程进入就绪队列，此时应如何分配处理机。

  

6、进程切换过程

7、调度算法评价指标

（1） CPU利用率

（2）系统吞吐量

（3）周转时间

（4）等待时间

（5）响应时间

8、调度算法对比

（1）FCFS —— 先到先服务

（2）SJF —— 短作业优先

• 非抢占式（SJF）

  

• 抢占式（SRTN）

  

  

（3）HRRN —— 高响应比优先

（4）前三种调度算法对比

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

• 时间片为 2 举栗子

  

  

• 时间片为 5 举栗子

  

• 可能出现的问题

  

  

（6）优先级调度算法

• 抢占式例子

  

• 非抢占式例子

  

• 补充

  

（7）多级反馈队列调度算法

• 举个例子

  

（8）后三种调度算法对比

三、进程同步与互斥

1、概览

2、概念

（1）进程同步

• 同步也称为直接制约关系。
• 在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系,如等待、传递信息等，引入了进程同步的概念。进程同步是为了解决进程的异步问题。
• 异步性：进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

一个简单的例子来理解这个概念。

例如，让系统计算1 + 2x3，假设系统产生两个进程: 一个是加法进程，一个是乘法进程。要让计算结果是正确的，一定要让加法进程发生在乘法进程之后,但实际上操作系统具有异步性,若不加以制约，加法进程发生在乘法进程之前是绝对有可能的，因此要制定一定的机制去约束加法进程，让它在乘法进程完成之后才发生。

（2）进程互斥

• 进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

在这里需复习一下临界资源的概念。

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

• 对临界资源的访问，必须互斥地进行。

  

• 为了禁止两个进程同时进入临界区，需遵循以下 准则

  

3、临界区资源互斥访问的软件实现方法

（1）思维导图

• 软件实现方法的思想：在进入区设置并检查一些标志 来标明是否有进程在临界区中,若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

  

（2）单标志法

（3）双标志先检查法

（4）双标志后检查法

（5）Perterson算法

4、临界区资源互斥访问的硬件实现方法

（1）思维导图

（2）中断屏蔽方法

（3）TestAndSet指令

• 执行TSL指令时，它的内部运转逻辑：
  • 假设lock现在为false，代表临界资源A空闲，那么我就可以访问这个资源，同时将lock=true，提醒别的进程，这个临界资源A我正在使用，让他们等等
  • 假设lock为true，代表临界资源正在有人使用，所以我必须等待，并且将lock=true，并不影响什么，所以没关系，只是为了让lock为false时可以上锁，将上锁与检查在一个TSL指令完成。

（4）Swap指令

5、信号量机制

（1）思维导图

（2）为什么引入

• 为了更好地解决进程互斥与同步问题

  

（3）什么是信号量机制

（4）整形信号量

（5）记录型信号量

（6）一个例子

（7）记录型信号量知识点总结

6、信号量机制实现进程的互斥、同步与前驱关系

（1）思维导图

（2）信号量实现进程互斥

（3）信号量实现进程同步

（4）信号量实现前驱关系

7、管程

（1）思维导图

（2）为什么引入管程

（3）管程的组成及基本特征

（4）管程实现生产着消费者问题

（5）Java中类似于管程的机制

四、死锁

1、概览

2、什么是死锁

3、死锁、饥饿、死循环之间的区别

4、死锁的产生

（1）死锁产生的必要条件

（2）什么时候会发生死锁

5、死锁的处理策略

（1）预防死锁

① 破坏互斥条件

② 破坏不可剥夺条件

③ 破坏请求和保持条件

④ 破坏循环等待条件

（2）避免死锁

① 什么是安全序列

② 安全序列、安全状态、不安全状态 与 死锁 联系

③ 如何避免进入不安全状态 —— 银行家算法

④ 代码实现

（3）死锁的检测

（4）死锁的解除