操作系统-进程

本篇内容：

• 进程与线程（进程管理）
• 进程状态切换
• 进程调度算法
• 进程同步
• 进程通信

（一）进程管理

进程和线程的区别：

• 定义区别：

进程是资源分配的基本单位。进程控制块 (process control block, pcb) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 pcb 的操作。

线程是独立调度的基本单位。一个进程中可以有多个线程，它们共享进程资源。
例如：qq 和浏览器是两个进程，浏览器进程里面有很多线程，例如 http 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 http 请求时，浏览器还可以响应用户的其它事件。

• 拥有资源区别：

进程是资源分配的基本单位，

线程不拥有资源，线程可以访问隶属进程的资源。

• 调度

线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。

• 系统开销区别：

线程开销小，进程开销大

原因：创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、i/o 设备等，所付出的开销远大于创建或撤销线程时的开销。
在进行进程切换时，涉及当前执行进程 cpu 环境的保存及新调度进程 cpu 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小

• 通信区别：

线程间:通过直接读写同一进程中的数据进行通信;
进程通信:借助 ipc。

（二）进程状态

5种状态：

• 创建状态：

进程由创建而产生。多个步骤才能创建：
（1）由进程申请一个空白的进程控制块(pcb)，向pcb中填写控制和管理进程的信；
（2）为该进程分配运行时所必须的资源；
（3）把该进程转入就绪状态并插入到就绪队列中；

• 就绪状态：

进程已经准备好运行的状态;进程已分配到除cpu以外所有的必要资源后，只要再获得cpu，便可立即执行;
即：有执行资格，没有执行权的进程。（妃子随时准备好让皇帝翻牌子的状态）

• 运行状态：

进程已经获取cpu，其进程处于正在执行的状态。
单处理机的系统中，只有一个进程处于执行状态,在多处理机系统中，有多个进程处于执行状态。

• 阻塞状态：

正在执行的进程由于发生某事件（如i/o请求、申请缓冲区失败等）暂时无法继续执行的状态（阻塞状态）；
此时引起进程调度，操作系统把处理机分配给另外一个就绪的进程，而让受阻的进程处于暂停的状态(阻塞态)；

• 终止状态：

进程的终止也要通过两个步骤
（1）等待操作系统进行善后处理，
（2）将其pcb清零，并将pcb空间返还给系统。

状态切换

• 就绪→执行

就绪状态的进程，进程调度程序为之分配了处理机后，进程便由就绪状态转变成**执行状态。

• 执行→就绪

执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机(pcb)，于是进程从执行状态转变成就绪状态。

• 执行→阻塞

正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。

• 阻塞→就绪

处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态

注意：
(1)只有就绪态和运行态可以相互转换，其它的都是单向转换。

就绪状态的进程通过调度算法从而获得 cpu 时间，转为运行状态；
运行状态的进程，在分配给它的 cpu 时间片用完之后就会转为就绪状态，等待下一次调度。

(2)阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 cpu 时间，缺少 cpu 时间会从运行态转换为就绪态。

（三）进程调度算法

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

三种不同系统

批处理系统、交互式系统、实时系统

1.批处理系统

没有太多的用户操作，调度算法目标是保证吞吐量和周转时间

• 先来先服务（fcfs）：非抢占式，按请求顺序调度；利于长作业，不利于短作业；
  （**缺点：**短作业必须等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长）
• 短作业优先：非抢占式，按估计运行时间最短的顺序进行调度（时间最短的最先调度，次短的第二，依次下去。缺点：长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。）
• 最短剩余时间优先：当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

2.交互式系统

有大量的用户交互操作，调度算法的目标是快速地进行响应。

• 时间片轮转
  所有就绪进程按先来先服务原则排队，第一个排队的先执行一个时间片的时间，时间到了后，这个同学就排到队伍最后面去，让第二个人开始也执行一个时间片，时间到了就排到队列末尾去，这样依次执行下去。（类似轮流和cpu玩，每人5分钟这样子）
  效率问题：和时间片的大小有很大关系，时间片太小，进程切换得太频繁，在进程切换上就会花过多时间，时间片太长，实时性得不到保证；
• 优先级调度：为每个进程分配一个优先级，按优先级进行调度;(防止低优先级的永远等不到调度，可随时间的推移增加等待进程的优先级)
• 多级反馈队列:设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,…。进程在第一个队列没执行完，就会被移到下一个队列。
  

3.实时系统

实时系统要求一个请求在一个确定时间内得到响应
硬实时： 必须满足绝对的截止时间；
软实时： 可以容忍一定的超时；

（四）进程同步

四个概念：临界区、同步和互斥、信息量、管程
1.临界区： 对临界资源进行访问的那段代码称为临界区；

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查；

2.同步与互斥：

• 同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系;
• 互斥：多个进程在同一时刻只有一个进程能进入临界区

3.信息量
信号量（semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 p 和 v 操作。

• down: 信号量 > 0 ，执行 -1 操作；信号量 = 0，进程睡眠，等待信号量大于 0；
• up: 对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作；
  如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

4.管程
概念： 是一个资源管理模块，其中包含了共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程（方法）所组成的资源管理程序。

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

• 重要特性： 在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。
  

（五）经典同步问题

生产者和消费者问题

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；

解析：因为缓冲区属于临界资源，因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。

为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

读者和写者问题

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。

一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count_mutex 用于对 count 加锁，一个互斥量 data_mutex 用于对读写的数据加锁。

哲学家进餐问题

问题描述：五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

错误解法：如果所有哲学家同时拿起左手边的筷子，那么就无法拿起右手边的筷子，造成死锁。

正确解法: 两个约束条件

• 必须同时拿起左右两根筷子;
• 必须在左右两个另邻居都没有进餐的情况下才允许进餐;

（六）进程通信

进程同步和进程通信的区别:

进程通信是为了达到进程同步目的的一种手段。为了让进程同步，进程间必须通信，传输一些进程同步所需要的信息。

五个概念：管道、fifo、消息队列、信号量、共享存储、套接字

1.管道（匿名管道）

定义： 把一个进程连接到另一个进程的一个数据流成为一个"管道"；
用途： 把一个进程的输出通过管道连接到另一个进程的输入；
本质：内核的一块缓存；
创建 ： 通过pipe函数创建，fd(0)用于读，fd(1)用于写。
特点：

• 只支持半双工通信（单向）；
• 只能在父子进程或兄弟进程中使用；
• 管道内部自带同步机制：子进程写一条，父进程读一条；
• 当进程退出之时，管道也随之释放，与文件保持一致；
• 管道的生命周期尾随进程，进程结束管道就没了；

实现原理：

单进程通信原理

父子进程通信原理

2.fifo（命名管道）

概念： 本质上是一个管道文件，可以通过命令创建也可以通过函数创建，用户可以看到；
特点：

• 可以进行不相干进程间的通信;
• 命名管道是一个文件，对于文件的相关操作对其同样适用;

fifo 常用于客户-服务器应用程序中，fifo 用作汇聚点，在客户进程和服务器进程之间传递数据。

3.消息队列

优点（与fifo比较）

• 消息队列可以独立于读写进程存在，避免了 fifo 中同步管道的打开和关闭时可能产生的困难；
• 避免了 fifo 的同步阻塞问题，不需要进程自己提供同步方法；
• 读进程可以根据消息类型有选择地接收消息，而不像 fifo 那样只能默认地接收。

4.信号量

是一个计数器,用于为多个进程提供对共享数据对象的访问.

5.共享存储

允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种 ipc。

需要使用信号量用来同步对共享存储的访问。

多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 xsi 共享内存不是使用文件，而是使用内存的匿名段。

6.套接字

可用于不同机器间的进程通信;

---

---

@声明和致谢

本篇博客为个人学习笔记,大部分内容来自该博主cyc2018,另有部分来自其他一些博客文章,在此表示感谢!