并发与并行

一组在逻辑上互相独立的程序或程序段在执行过程中执行时间在客观时间上的重叠。
并行执行是指一组程序按独立的，异步的速度执行、并发执行不等于时间上的重叠。
（并行是指同一时刻可以做多件事情，并发是指同一时间间隔内做多件事情）

进程的概念

经典定义：
1.进程是可以并发执行的计算部分

2. 进程是一个独立的、可以调度的活动
3. 进程是一个抽象实体，当它执行某个任务时，将需要分配和释放各种资源
4. 一个进程是一个逐一执行的操作

进程与程序区别
进程是动态的，程序是静态的
进程有一定的生命周期，程序是指令的集合
一个程序可以对应多个进程，一个进程只能对应一个程序
程序可以作为一种软件资源长期保存着，而进程是一次执行过程，是暂时的

进程的五个特性
1.动态性：创建时产生，由调度而执行，得不到资源而暂停执行，有撤销而消亡
2.并发性：多个进程实体同存于主存中
（引入进程的目的，程序是不能并发执行的）
3.独立性：进程实体是一个能独立运行的基本单位，也是系统中获得资源和独立调度的基本单位
4.异步性：进程按各自独立的，不可预知的速度向前推进（导致程序执行的不可再现性）
5.结构特征：进程实体是由程序段、数据段、进程控制块三部分构成，又称进程映像/进程上下文（context）


进程的基本状态

进程的状态转换图

有些还存在两个额外状态：新状态和终止状态

进程状态转换图

进程控制块PCB
1.概念：是操作系统用于记录和刻画进程状态及有关信息的数据结构，也是操作系统控制和管理进程的主要依据。

进程控制块

进程的控制（创建、撤销、阻塞与唤醒）

进程控制原语

原语：一组系统命令
要么全部执行，要么不执行，不存在中间状态

进程的创建（调用创建原语来实现）

$$进程创建
\begin{cases}
& \text{系统生成时，会创建一些系统进程（用来分配系统资源和管理工作）}\
& \text{用户作业，由操作系统的作业调度程序为之创建相应的进程}
\end{cases}$$

进程的撤销

1.既可撤销具有指定标识符的过程，又可撤销一个优先级中的所有进程
2.一个进程被撤销时，必须从系统队列中移出，释放并归还所有系统资源，同时也有审查是否有子孙进程，如果有子孙进程也有一起予以撤销

进程的阻塞和唤醒

1.当一个进程出现等待事件时，该进程调用阻塞原语将自己阻塞

阻塞原语执行过程

唤醒原语执行过程

进程的调度

1.必要性：解决多个进程争夺少数CPU资源的问题
2.功能：
（1）记录系统中所有进程的执行情况
（2）选择占有CPU的进程
（3）CPU分配给进程，即进行进程上下文切换
（4）回收CPU
3.进程调度算法
先来先服务/FCFS
按照进程进入就绪队列的先后次序选择占用处理器的进程

注意
运行时间较长的进程先进入可能会影响到后面进程的等待时间
例：
A（3ms），B（3ms），C（24ms）
输入顺序1：{A，B，C}
调入顺序2：{C，A，B}
问：两次调入顺序不同三个进程的平均等待时间？
（1）A等待0ms，B等待3ms，C等待3+3ms，所有进程得到响应的总共时间是9ms，三个进程的平均等待时间是9/3=3ms
（2）C等待0ms，A等待24ms，B等待24+3ms，所有进程得到响应的总共时间是0+24+27=51ms，所有进程的平均等待是51/3=17ms

优先数调度算法
为每个进程确定一个优先数，进程调度总是让具有最高优先数的进程先使用处理器（若优先数相同则采用FCFS）

优先数的确定
1.静态法：进程执行前就确定优先数
2.动态法：随着进程的执行，优先数不断变化

提高经常使用外围设备的进程的优先数（有利于并行能力）
提高较长时间未使用处理器的就绪进程的优先数（缩短等待处理器的平均时间）

调度
1.非抢占式：优先数高的进程占用了处理器，等其主动让出处理器或由于自身原因主动让出处理器，才重新按优先数选择另一个进程占用处理器
2.可抢占式：某个进程在处理器上运行时，一旦有一个具有更高优先数的进程进入就绪队列，就把处理器让给更高优先数的进程先使用
**优先数的确定
系统进程的优先数＞用户进程的优先数
重要计算问题的进程优先数＞一般计算问题的进程优先数
交互式作业进程的优先数＞批处理作业进程的优先数

时间片轮转调度算法
CPU处理时间分成固定大小的时间片，轮流来，如果时间片用完进程还未结束，也得重新排到就绪队列的末尾等待再次调度

时间片轮转调度

时间片太长$\mapsto$变成FCFS
时间片太短$\mapsto$进程上下文切换次数增加$\mapsto$加重系统开销

时间片q的选择：
q=R/N(R是系统对响应时间的要求；N是进程数)

多级反馈队列调度算法/MLFQ
设置多个就绪队列
各个队列的优先权不同(第一个队列的优先权最高，逐个降低)
各个队列的时间片大小不同（优先权越高的队列时间片越小）
当前队列的某个进程在时间片内没有完成就进入下一个队列的末尾
当某个队列为空时才会调度下一个队列
处理机在第i队为谋进程服务时，如果有新进程进入优先权较高的队列（i之前），则处理机就去处理i之前的那个新进程了，正在运行的进程被放到i队伍的末尾（可怜哈哈哈哈）

多级反馈队列调度算法

优点、
对与分时交互型短作业$\mapsto$周转时间短
长作业$\mapsto$轮转方式运行，不必担心长期得不到处理

4.调度算法的选择
（1）处理器利用率（尽量让CPU处于忙碌状态）
（2）吞吐量
（3）等待时间（尽可能减少）
（4）响应时间（尽可能减少）

进程的同步与互斥

进程的互斥

与时间有关的错误
由于并发进程执行的随机性，由于贡献了资源/变量，在不同时刻或执行速度的不同或外界的影响，交替访问资源/变量的时候可能造成结果不正确
1.临界区：并发进程中与共享变量有关的程序段
相关临界区：多个并发进程中涉及相同共享变量的那些程序段
2.解决方案：
如果有进程在相关临界区执行的时候就不让另一个进程进入相关临界区
任何一个进入临界区执行的进程必须在有限的时间内退出临界区
有进程退出临界区应让一个等待进入临界区的进程进入它的临界区

1.进程互斥：若干个进程要使用一个共享资源，任何时刻只允许一个进程去使用，其他要使用的进程必须等待，直到那个进程使用完后释放资源
2.进程互斥的管理办法：PV操作 管程

PV操作
1.信号量S
S$\geq$0时，代表可供并发进程使用的资源实体数
S＜0时，|S|表示正在等待使用资源实体的进程数。
2.操作原语P V
P操作意味着请求一个资源，V操作意味着释放一个资源
P操作代表阻塞进程操作，V操作代表唤醒被阻塞进程的操作
3.步骤：
$$设互斥信号量S表示临界区\longmapsto
\begin{cases}
无并发进程进入临界区& \text{S=1}\
有一个并发进程进入临界区进程& \text{S=0}\
有一个进入临界区|S|个进程在等待进入& \text{S$\leq$0}
\end{cases}$$

进程同步（异步环境下）

异步环境：互相合作的一组并发进程，由于每个进程执行的速度不同，又相互独立，所以需要解决一个同步的问题

1.进程同步：并发进程之间存在一种制约关系，一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到达时才被唤醒

进程协作

错误
进程A速度＞进程B，可能在B没取走记录时A存入新的，造成记录丢失
进程A速度＜进程B，可能在A没存入新的记录时B又取走，造成记录重复加工
解决方法
互通消息
2.解决进程同步：PV操作

PV操作
1.信号量S
S=0时，代表期望的消息未产生
S$\ne$0时，表示期望的消息已存在
2.操作原语P V
P操作测试消息是否到达，V操作发送消息
3.步骤：
$$设互斥信号量S表示临界区\longmapsto
\begin{cases}
无并发进程进入临界区& \text{S=1}\
有一个并发进程进入临界区进程& \text{S=0}\
有一个进入临界区|S|个进程在等待进入& \text{S$\leq$0}
\end{cases}$$

3.时间上的同步问题

进程通信

$$进程通信
\begin{cases}
低级& \text{PV操作}\
高级 \begin{cases} 共享存储器系统\ 消息传递系统 \管道通信系统 \end{cases}
\end{cases}$$

共享存储器系统

1.基于共享数据结构的通信方式
在这种通信方式中，要求诸进程公用某些数据结构，进程通过它们交换信息。这种通信方式是低效的，只适于传递少量数据。
2.基于共享存储区的通信方式
为了传输大量数据，在存储器中划出了一块共享存储区，诸进程可通过对共享存储区中的数据进行读或写来实现通信。这种通信方式属于高级通信。

消息传递系统

消息传递系统中，进程间的数据交换以消息为单位

$$实现方式\begin{cases} 直接通信方式\ 间接通信方式 \end{cases}$$
直接通信方式
可用send原语和receive原语来实现进程之间的通信，
这两个原语定义如下：
send（P，消息） 把一个消息发送给进程P。
receive（Q，消息） 从进程Q接收一个消息。
间接通信方式
采用间接通信方式时，进程间发送或接收消息通过一个共享的数据结构——信箱来进行，消息可以被理解>成信件，每个信箱有一个唯一的标识符
间接通信方式中的“发送”和“接收”原语的形式如下：
send（A，信件） 把一个信件（消息）发送给信箱A
receive（A，信件） 从信箱A接收一封信件（消息）

管道通信系统

1.管道，是指用于连接一个读进程和一个写进程，以实现它们之间通信的共享文件，又称为pipe文件
2.为了协调双方的通信，管道通信机制必须提供以下三方面的协调能力：（1）互斥；（2）同步；（3）对方是否存在。

线程的概念

1.需要线程的目的：保持系统的并发性
2.为了减少额外开销，系统把进程的资源申请与调度执行分开，线程是调度的基本单位，进程是资源申请与拥有的基本单位
3.概念：线程（Thread）是进程中的一个实体，是可独立参与调度的基本单位
4.属性：
并发
一个线程可以创建另一个
动态性（生命周期）
TCB（进程是PCB）
同一进程内的线程共享同一地址空间
一个进程的线程对另外一个进程是不可见的
线程的通信是基于全局变量进行的
5.状态（与进程类似）

运行
就绪
等待

线程调度

时间片轮转算法
优先权算法

进程与线程的区别（工厂的车间与工人）

1.进程作为资源的申请与拥有单位，线程作为调度的基本单位
2.线程在调度和切换上所花费的开销比进程小得多
3.进程是独立拥有资源的的一个基本单位，线程只拥有一点点运行中必要的资源
4.进程作为独立拥有资源的基本单位，线程是独立参与调度的基本单位

死锁

1.概念：死锁是多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进
2$$产生原因\begin{cases} 竞争资源\ 进程推进顺序非法（请求与释放资源顺序不当） \end{cases}$$

注意
以下两种情况造成进程永远等待不属于我们要讨论的死锁问题：
（1）如果出现某个进程申请系统中不存在的资源或申请的资源数超过了系统拥有的最大资源数。
（2）由于硬件故障或程序性错误引起的循环等待

3.$$产生死锁必要条件 \begin{cases} 互斥条件（进程互斥使用资源） \ 占有且等待条件（得不到需要的资源就不释放占有的资源）\ 不剥夺条件（进程不能从另一进程抢夺资源）\ 循环等待条件（每个进程都在等待另一个进程所持有的资源） \end{cases}$$

4.对策：预防 避免 检测 解除
预防
（1）静态分配策略//破坏第二个必要条件
所谓静态分配是指一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源都得到满足后才开始执行
（2）层次分配策略//破坏第四个必要条件
当一个进程获得了某一层的一个资源后，它想再申请该层中的另一个资源，必须先释放该层中的已占用资源。

避免

银行家算法
先满足请求资源较少的进程，然后通过回收已经完成的进程的资源，将系统可用资源进行积累，以满足请求资源较大的进程。
把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款，操作系统按照银行家制定的规则为进程分配资源。
银行家规则（Dijkstra）：
（1）当一个用户对资金的最大需求量不超过银行家现有的资金时就可接纳该用户；
（2）用户可以分期贷款，但贷款的总数不能超过最大需求量；
（3）当银行家现有的资金不能满足用户的尚需贷款数时，对用户的贷款可推迟支付，但总能使用户在有限的时间里得到贷款；
（4）当用户得到所需的全部资金后，一定能在有限的时间里归还所有的资金。

检测
操作系统中的每一时刻的系统状态都可以用进程—资源分配图来表示，进程—资源分配图是描述进程和资源间申请及分配关系的一种有向图，可用以检测系统是否处于死锁状态。