1.程序的并发

1.1 顺序执行和并发执行

程序有两种执行方式：① 顺序执行 ② 并发执行

顺序执行：一个独立功能的程序独占cpu直到得到最终结果的过程。

并发执行：一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的这种执行方式。

（1）单道程序顺序执行的特点

① 顺序性：严格程序结构规定的次序执行。

② 封闭性：占据了全部资源，最终结果由初始条件决定，不受外界影响。

③ 结果确定性：最终结果由给定的初始条件决定，不受外界因素的影响。

（2）多道程序并发执行特点

① 结果不确定性：执行结果与其执行的相对速度以及并发执行的多道程序之间的相互关系有关，导致并发程序的执行结果是不确定的。

② 资源共享性：硬件和软件资源共享，即执行期间是相互制约的。

1.2 程序并发

（1）基本概念

一组逻辑上相互独立的程序或者程序段在执行时间上是互相重叠的。

① 执行时间相互重叠的意思是一个程序或者说程序段还没执行结束，另一个程序或者程序段就开始了。

② 为了提高计算机资源利用率而设计的。

（2）优缺点

优点：提高资源利用率

缺点：① 资源共享和竞争改变程序的执行速度，同时也会失去原有的时序关系。

           ② 资源共享和竞争导致失去封闭性和确定性，例如程序A写到存储器中的数据可能被                 另程序B修改，导致A被B影响，A的结果是不确定的。

1.3 引入进程的概念

（1）出现的问题

如果随意地执行并发，不做任何约束，将会产生大量的错误结果。不同的执行顺序，得到的结果也是不同的，即不再具有封闭性和结果的确定性。

这是为什么呢？共享公共变量引起的。

（2）如何解决问题

解决公共变量的共享问题，即满足封闭性和确定性。

假定程序 A 和程序 B ，保证满足一下条件：

① 程序 A 的读变量集与程序 B 的写变量集，不能存在交集。

②程序 A 的写变量集与程序 B 的读变量集，也不能存在交集。

③ 程序 A 和 程序 B 的写变量集，更加不能存在交集。

（3）引入进程

由于程序未运行，不知道并发的情况，资源是如何被争夺的等等。因此，“程序” 的静态概念已经不能很确切的反映程序活动的特征，所以“进程” 的动态概念就出现了，用来描述系统以及用户的程序活动。

2.进程的概述

2.1 什么是进程？

进程是程序的一次执行活动，描述了程序动态执行的过程。

① 用户角度： 进程是程序的一次动态执行过程。

② 系统角度： A.进程是操作系统分配资源的基本单位；B.进程是一个具有独立功能的程序对某个数据集在CPU处理器上的执行过程。

2.2 进程和程序的区别

进程和程序的区别

2.3 进程和作业的区别

进程和作业的区别

进程和作业的关系如下：

进程和作业的关系

2.4 进程的特点

① 动态性：进程是对应程序的执行。

    A.进程产生：创建 --> 运行 --> 消亡

    B.进程在在内存三种基本状态（就绪、运行、阻塞）之间转换，可能被挂起到外存。

② 独立性：各进程的地址空间相互独立，可采用进程间通信手段进行通信。

③ 并发性：多个进程可以同时运行。

④ 异步性：每个进程都以其相对独立的不可预知的速度运行。

⑤ 结构化：进程 = 代码段 + 数据段 + PCB（进程控制块）

3.进程的状态

3.1 进程的5种基本状态

5种基本状态的转换

（1）创建状态

创建一个新的进程。

① 批处理环境中，选择一个新作业即将进去内存执行。

② 交互环境中，新用户登录到系统。

③ 操作系统因提供一项服务而创建。

（2）就绪状态

一个进程已经具备了运行的条件，但是暂时还没有CPU调度的状态。

说明：当 CPU 调度的时候，线程可以马上运行。

（3）执行状态

进程占有了包括CPU在内的全部资源，并且在CPU上运行。

（4）等待状态

进程因为等待某件事情的发生而暂时不能运行的状态。

说明：即使CPU空闲，但是这个进程也不能运行。

（5）终止状态

一个进程结束

① 用户结束某应用程序。

② 出现某些错误的时候，例如，I/O失败，无效指令等。

③ 父进程可请求它的某个子进程终止。

④ 父进程终止，系统可能会自动终止其子进程。

3.2 3种关键状态的转换及原因

三种状态的转换

注意：运行状态和就绪状态是可以相互转换的，而阻塞（等待）状态不能直接转换为运行状态，就绪状态也不能直接转换为阻塞（等待）状态。

① 就绪 --> 运行

CPU调用了一个已经准备好的进程（就绪状态），然后就进入了运行状态。

② 运行 --> 就绪

场景1：运行中的进程用完了时间片。

场景2：优先级更高的进程处于就绪状态，所以当前运行进程被迫中断。

扩展1：CPU 采用时间片轮转调度算法。基本思想是将CPU的处理时间划分成一个个时间片，就绪队列FIFO中依次出队进程轮流运行一个时间片。当时间片结束时，就强迫运行状态的进程让出CPU，该进程入队就绪队列FIFO，等待下一次调度。同时，进程调度又去选择就绪队列中的一个进程，分配给它一个时间片，以投入运行。

扩展2：时间片大小的确认。时间片设得太短会导致过多的进程切换，降低了CPU效率，而设得太长又可能引起对短的交互请求的响应变差。

③ 运行 --> 阻塞

当一个进程等待某一件事情发生的场景，例如：请求系统服务、没有新的工作可以做、等待某一进程提供输入（IPC）、初始化 I/O 且必须等待结果。

3种关键状态之间的互相转换的联系，例如：

（运行 --> 就绪）发生，则 （就绪 --> 运行）必然发生

当一个进程从运行转到就绪状态后，CPU 自然空闲了，如果就绪状态下仍然有别的进程，那么这个进程就会被 CPU 调用，同样如果就绪状态下没有别的进程了，那么这个刚从运行转到就绪状态的进程就会马上被 CPU 重新调用。

（运行 --> 阻塞）发生，则 （就绪 --> 运行）必然发生

当运行中的某个进程，进入阻塞状态后，那么 CPU 同样也空闲了下来，所以会调用已经在就绪状态的进程，即执行（就绪 --> 运行）的操作

CPU 空闲且无就绪进程的时候，（阻塞 --> 运行）发生则会引起 （运行 --> 阻塞）

4.进程的控制块（PCB）

4.1 基本介绍

① 进程控制块PCB：记录进程相关信息和管理进程，由 OS 维护的一个特定的数据结构，包含进程的描述信息、控制信息、资源信息以及现场保护区。

② PCB 是进程动态特性的集中反映。系统通过 PCB 感知进程的存在，通过 PCB 中所包含的各项变量的变化，掌握进程的状态以达到控制进程活动的目的。

③ PCB 结构的全部或部分常驻内存。

④ PCB 随进程的创建而产生，随进程的撤消而释放。

⑤ 系统利用 PCB 来控制和管理进程，故 PCB 是系统感知进程存在的唯一标志。

⑥ 进程与 PCB 是一一对应的。

4.2 包含的内容

（1）描述信息

① 进程标识号，唯一，通常是是一个整数。

② 进程名，通常是可执行文件名。

③ 用户名或者用户标识号。

④ 进程组关系。

（2）进程控制信息

① 进程状态：初始状态、就绪状态、执行状态、等待状态、终止状态。

② 进程优先级：选取进程占有处理机的重要依据。

③ 占有CPU时间

④ 进程优先级偏移

⑤ 占据内存时间

⑥ 程序开始地址

⑦ 各种计时信息

⑧ 通信信息

（3）资源管理信息

① 占用内存大小及其管理用数据结构指针

② 共享程序段大小及起始地址

③ 对换或覆盖用的有关信息，如对换程序段长度，对换外存地址等

④ 指向文件系统的指针及有关标识等

⑤ 输入输出设备的设备号，传送的数据长度、缓冲区地址、缓冲区长度及所用设备的有关数据结构指针等

（4）CPU线程保护信息

① 存储退出执行时的进程现场数据（进程上下文）

② 寄存器值（通用、程序计数器 PC、状态 PSW，地址包括栈指针）

说明：进程的上下文是对进程执行活动全过程的静态描述。

进程上下文的组成：进程的用户地址空间内容、硬件寄存器内容及与该进程相关的核心数据结构组成（正文段、数据集、堆栈）。

进程的上下文

5.进程的调度

5.1 先到先服务调度算法（FCFS）

非抢占式的调度算法，按照请求的顺序进行调度。

从就绪队列FIFO中出队一个进程（最早入队的进程），并为其分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU。

应用场景：有利于长作业，但不利于短作业。因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，导致短作业等待时间过长。

5.2 短作业优先的调度算法（SLF）

非抢占式的调度算法，按照估计运行时间最短的顺序进行调度。

从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU。

应用场景：长作业可能一直无法执行，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

5.3 时间片轮转调度算法

抢占式的调度算法，进程根据请求顺序依次执行，且每个进程只能在被允许的时间内运行。

时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称 RR(Round robin)调度。将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

应用场景：有大量用户交互操作的系统，其目标是快速响应。

时间片轮转算法的性能取决于时间片的大小：

因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。如果时间片过长，那么实时性就不能得到保证。

例子1：假设 CPU 使用4ms的时间片。有一组进程在时间 0 到达，其 CPU 执行的单位是 ms，进程 P1 的执行时间是24ms，进程 P2 的执行时间是3ms，进程 P3 的执行时间是3ms。 

开始的时候 P1 会执行4ms，因为 P1 还需要 20ms，所以在第一个时间片之后它会被抢占。接着 P2 获取到 CPU 时间片 4ms，因为 P2 的执行时间3ms少于4ms，所以在其时间片用完之前就会退出。接着 P3 获取到 CPU 时间片 4ms，同上P2。接着 P1 获取到 CPU 时间片 4ms，由于没有就绪进程，P1 可以获取时间片 4ms，反复该操作。因此，平均等待时间为 17/3 = 5.66ms。RR 调度结果如下：

RR调度算法

计算该调度的平均等待时间：P1 等待 10-4 = 6ms，P2 等待 4ms，而 P3 等待 7ms 。

RR 算法的性能很大程度取决于时间片的大小。在一种极端情况下，如果时间片很大，那么 RR 算法与 FCFS 算法一样。相反，如果时间片很小（如 1ms），那么 RR 算法可以导致大量的上下文切换。

例子2：假设有一个需要 10 个时间单元的进程。如果时间片为 12 个时间单元，那么进程在一个时间片不到就能完成，而且没有额外开销。如果时间片为 6 个时间单元，那么进程需要 2 个时间片，并且还有一个上下文切换。如果时间片为 1 个时间单元，那么就会有 9 个上下文切换，相应地使进程执行更慢。

上下文切换例子

5.4 优先级调度算法

为每个流程分配优先级，首先执行具有最高优先级的进程，依此类推。相同优先级的进程以 FCFS 方式执行。

可以根据内存要求、时间要求或任何其他资源要求来确定优先级。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

5.5 多级反馈队列调度算法

既能使高优先级的作业得到响应又能使短作业迅速完成。目前被公认的一种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。

前面介绍的几种进程调度的算法都有一定的局限性。例如，先到先服务算法不利于短作业、短作业优先算法忽略了长进程 、当时间片大小不合适的时候时间片轮转算法存在大量进程切换等。

多级反馈队列算法是抢占式的调度算法，可以解决需要执行多次时间片进程的场景，采用多个队列，每个队列时间片大小都不一样，例如1、2、4、8、...。当进程在第一个队列没有执行完，就会被移动到下一个队列。每个队列优先权也不同，最上面的优先级最高，最后一层的优先级最低（采用时间片轮转调度算法）。因此只有上一个队列没有进程在排队。多级反馈队列算法是优先级调度算法和时间片轮转调度算法的结合。

抢占式的调度算法

例子1：进程 A 需要执行 100ms，如果采用时间片轮转调度算法，CPU 时间片为1ms，那么进程需要切换 100 次。如果采用多级反馈队列调度算法，依次队列对应的时间片是1、2、4、8、16、32、64、...等。因此，进程 A 只需要交换7次。

例子2：一个多级反馈队列的调度程序有三个队列，从 1 到 3（如上图所示）。调度程序首先执行队列 1 内的所有进程。只有当队列 1 为空时，它才能执行队列 2 内的进程。类似地，只有队列 1 和 2 都为空时，队列 3 的进程才能执行。到达队列 1 的进程会抢占队列 2 的进程，同理到达队列 2 的进程会抢占队列 3 的进程。每个进程在进入就绪队列后，就被添加到队列 1 内。队列 1 内的每个进程都有 1ms 的时间片。如果一个进程不能在这一时间片内完成，那么它就被移到队列 2 的尾部。如果队列 1 为空，队列 2 头部的进程会得到一个 2ms 的时间片。如果它不能完成，那么将被抢占，并添加到队列 3。只有当队列 1 和 2 为空时，队列 3 内的进程才按照RR算法 运行。

6.线程

6.1 为什么引入线程的概念

进程的创建、删除和切换过程中时空代价大，限制了系统中的进程数目和并发活动的程度。因此，现代操作系统中，进程作为资源的拥有者，调度和运行的属性赋予新的实体——线程。

进程模型在处理“基于同数据区的同时多请求”时的效率局限性，例：售票系统：数据库服务器软件需同时处理来自多个用户进程的读盘请求，这些请求都是针对同一个盘，可以有如下几种方式：

① 进程：一个进程来顺序处理。

② 多个相互独立的进程：每个进程负责处理一个请求。

③ 用一个进程来并行处理所有请求。

分析：第一种方法没有并发，第二种方法切换的代价比较大。采用第三种方法效率更高，实现一个进程有多个子任务并发执行（线程）。

6.2 线程和进程的区别

线程和进程的区别

① 拥有资源

进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

② 调度

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

③ 系统开销

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

④ 通信方面

线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

6.3 线程的特点

① 进程可以提高线程数来提高并发程度。

② 线程切换的代价比进程切换的少，因为进程设计虚拟地址空间的切换。

③  由于线程间共享进程的代码、数据、内存和文件资源，可直接进行不通过内核进行通信；进程间的通信需要通过内核进行。