1. 单道程序系统与多道程序系统

1.1单道程序系统

单道程序系统在内存中每次仅存在一个程序，该程序运行时独占整个系统的资源，实际上它只会顺序的使用其中的一部分。因此在某一时刻，系统的各个部分只有一部分在工作，这造成了资源浪费从而利用率低。

1.1.1程序顺序执行的特征：

• 顺序性： 由图可知，在程序内部I、C、P操作的顺序是不可颠倒的，各程序之间的顺序也不可以颠倒，需严格按照程序所规定的顺序执行。
• 封闭性：程序在运行时，独占全部系统资源，只有程序本身才能改变系统资源的状态。
• 可再现性： 由于程序不受外部影响，只要初始条件相同，运行的结果就一定相同。

1.2多道程序系统

为了减少单道程序系统的利用率低的情况，引入了多道程序设计技术。多道程序设计指允许多道程序同时进入内存，并允许它们共享资源、并发执行的程序设计技术。采用这一技术的系统称为多道程序系统。 多道程序系统是现代操作系统所采用的最基本、最重要的技术。
在多道程序系统中，程序是并发执行的。

由图可见，各程序的内部操作I、C、P操作未颠倒，但程序之间不再是严格的串行次序。如，当程序1在进行运算操作时，很明显程序2的输入操作不会影响程序之间的关系。因此I、C、P操作在时间上可以重叠。 显然，并发执行的程序失去了封闭性和可再现性。 举个例子，I1与I2都取的同一地址的数值，本意是想让I2是取的程序1运行结束后的。而当C1正在进行运算时还未来得及将运算结果写回，I2却已将还未处理的数据取出进行计算造成了结果的错误。

1.2.1程序并发执行的条件

假设有以下几条语句

如果两个程序P1,P2满足Bernstein条件，它们便能并发执行，否则不能：
（ R ( p 1 ) ∩ W ( p 2 ) ） ∪ （ R ( p 2 ) ∩ W ( p 1 ) ） ∪ （ W ( p 1 ) ∩ W ( p 2 ) ） = { } （R(p1) /cap W(p2)） /cup （R(p2) /cap W(p1) ）/cup （W(p1) /cap W(p2)） = /{/} （R(p1)∩W(p2)）∪（R(p2)∩W(p1)）∪（W(p1)∩W(p2)）={}
即当两个程序的 读写集的交 与 写写集的交 都为空集时，它们可以并发执行，否则不行。

1.2.2程序并发执行的特征

• 间断性：多个程序在并发执行时，会因为共享资源的关系，或直接或间接的相互彼此制约。
• 无封闭性：程序在并发执行时，多个程序共享系统的各种资源，因此这些资源的状态也可以由多个程序来改变，使其失去了封闭性。
• 不可再现性：因为程序并发执行无封闭性，这也导致了程序并发执行结果不可再现。

2.进程

2.1进程的定义

进程目前还没有一个统一的定义，以下是许多学者从不同的角度对进程的不同解释

1. 进程是程序的一次执行。
2. 进程是可以和其他计算并发执行的计算。
3. 进程是一个程序及其数据在处理机上顺序执行时发生的活动。
4. 进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。
5. 进程是进程实体的一次活动。

2.2 进程的五个特性

• （1）动态性： 进程具有生命周期。它由系统“创建”而诞生，被“调度”而执行，因得不到资源而暂停，最后因被“撤销”而消亡。
• （2）并发性：不同进程的动作在时间上可以重叠，即系统内的多个进程是可以并发执行的。
• （3)独立性：进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调动的基本单位。在今天既有进程又有线程的操作系统中，进程仍是一个拥有资源的独立单位，但不再是一个可执行的实体，系统独立运行的基本单位变成线程了。
• （4）异步性：进程按各自独立的、不可预知的速度向前推进。不可预知的原因是并发执行。
• （5）结构特性： 从结构上看，每个进程都由程序段、数据段和一个PCB三部分组成。

2.3 进程与程序的区别

• 从定义上看，进程是程序处理数据的过程，而程序是一组指令的有序集合。
• 进程具有动态性、并发性、独立性和异步性等，而程序不具有这些特性。
• 从进程结构特性上看，它包含程序（以及数据和PCB）
• 进程和程序并非一 一 对应。

2.4 进程的基本状态与转换

• 就绪状态（Ready）：当进程已分配到除CPU以外的所有需要的资源，只要能获得处理机（CPU）的资源，便可立即执行。

有的系统为了暂时缓和内存的紧张状态，或为了调节系统负荷引入了挂起状态。即暂时将一部分进程，将他们临时从内存中换出至外存，使他们暂时和系统脱离联系。这样进程的就绪状态可以细分为：活动就绪状态（未被挂起）、静止就绪状态（被挂起）；阻塞状态细分为：活动阻塞状态（未被挂起）、静止阻塞状态（被挂起）

• 执行状态（Running）：当进程已获得处理机资源，其程序正在处理机上执行。
• 阻塞状态（Blocked）或等待状态：正在执行的进程，由于等待某件事件发生而无法执行时，便放弃处理机资源而处于暂停的状态。

在不少系统中，增加了两种基本状态：（1）新状态：进程刚被创建，并分配资源时；（2）终止状态：在进程结束后不会立即撤销进程，相应的进程会暂时留在系统中，以便收集进程的相关信息。

2.5 进程控制块PCB

2.5.1 PCB的定义

• PCB（Process Control Block）是系统为了描述和控制进程的运行而为进程定义的一种数据结构。
• 它是进程实体的一部分，是进程存在的唯一标志，也是操作系统中最重要的结构体类型的数据结构。
• PCB中存放着操作系统所需的用于描述进程当前情况以及控制进程运行的全部信息。

2.5.2 PCB的作用

• （1）标识进程的存在：系统创建进程时，就为之创建一个PCB；进程结束时，系统回收其PCB，进程随之消亡。操作系统靠PCB感知进程的存在。
• （2）为系统提供可并发执行的独立条件：PCB使一个在多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位，即一个能与其他进程并发执行的进程。没有为之建立PCB的程序是不能并发执行的。换而言之，操作系统是根据PCB来对并发执行的进程进行控制和管理的。
• （3）为系统控制和管理进程提供所需的一切信息。

2.5.3 PCB中的主要信息（因系统而异）

• 进程标识符： 系统内部用于标识一个进程的唯一编号，称为进程的内部名。
• 进程的现行状态： 标明进程当前所处的状态，作为进程调度程序分配处理机的依据。
• 处理机的现场保留区： 保存进程由执行状态转变为其他状态时的CPU现场信息，以便当该进程再次被调度运行时恢复处理机现场信息，以使该进程能继续正常进行。
• 进程相应的程序和数据地址： 根据内存管理方式给出该进程相应的程序和数据所在的位置信息。
• 进程资源清单: 列出进程拥有的除了CPU之外的资源记录。
• 进程优先级：表示进程使用处理机的优先级别的整数。
• 进程同步与通信机制： 用于实现进程间的同步、互斥和通信所需的信号量、信箱和消息队列的指针等。
• 进程所在PCB的链接字： 许多操作系统根据进程的状态，把相应的PCB加入到不同的队列中。这样，PCB中就有个链接字，指出该进程所在队列中的下一个进程PCB的首地址。
• 与进程有关的其他信息： 这些信息主要与进程的家族信息有关，如进程的父、子进程的PCB指针等。

2.6 进程的队列

• 进程队列指的是把具有相同状态的进程按照某种原则链接在一起组成的队列，它其实是PCB的一种组织形式，也称PCB链。
• 因为PCB是系统中最重要也是被频繁访问的数据结构，故系统中专门开辟了PCB区。PCB 常驻 内存的系统开辟的PCB区内，一般都是以 数组形式连续存放，形成PCB表或进程表。
• 显然，PCB表的长度是有限的。为了提高对PCB的访问效率，许多操作系统都在PCB中设立链接字，把具有同一状态的PCB用链接字连接成一个或多个队列。这样就形成了一PCB队列。如下图所示

（其等价直观的看法如下图所示）

2.7 进程的互斥

程序的并发执行，会让多个进程之间可能产生同步和互斥的相互制约的关系。若不采取措施，可能会导致结果的错误与不可再现性，影响系统的安全。为此，引入互斥同步机制，以控制并发执行的诸进程能有效的共享资源和合作，同时使得并发程序的执行仍具有可再现性。

2.7.1 互斥的相关概念及定义

• 进程互斥：对某个系统资源。一个进程正在使用它，另外一个想使用这个资源的进程就必须等待，而不能同时使用。即进程必须互斥地（排他性地）访问所共享的临界资源；是多道程序系统中进程间存在的一种源于资源共享的制约关系，也称间接制约关系，主要是被共享资源的使用性质所决定的。
• 临界资源： 限定进程只能互斥（排他）的访问使用的资源。如：表格、打印机等；临界资源在被一个进程使用时，其他需要使用该资源的进程只能等待，直至抢先者用完释放资源后才可访问。在这期间操作系统也不能中途剥夺抢先者的临界资源（在不kill进程的前提下）,因此临界资源是不可剥夺性资源。
• 不可剥夺性资源: 系统将这类资源分配给进程之后，不可强行夺回，只能等待该进程释放资源。如磁带机、打印机等。
• 可剥夺性资源： 系统将这类资源分配给进程后，该资源可被系统强行收回的。如CPU、内存、磁盘等。
• 临界区（临界段）： 进程中访问临界资源的那段 程序代码 称为临界区或临界段。
• 同类临界区（同类临界段）：使用同一临界资源的不同进程中的临界区称为同类临界区或同类临界段。

2.7.2临界区的使用原则☆

临界区的使用原则是“空则让进，忙则等待，多种择一，等则有限，等则让权”

• 空则让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入。
• 忙则等待： 当临界区中已有进程进入时，其他试图进入临界区的进程必须等待，即不允许两个以上的进程同时进入互斥区，以保证互斥地进入临界区。
• 多中择一： 当没有进程在临界区，而同时有多个进程要求进入临界区时，只能让其中之一进入临界区，其他的进程必须等待。
• 等则有限： 任何进入互斥区的要求应该在有限时间内得到满足。
• 等则让权： 当进程不能进入临界区时，应立即释放CPU，避免进程“忙等”。

2.7.3 互斥的实现

软件： （1）加锁（2）信号量（信号灯）（3）管程机制
硬件： 提供“测试并设置”指令

2.7 进程的同步

进程的同步，指的是两个或多个进程为了合作完成同一个任务，在执行速度或某些确定的时序点上必须相互协调，即一个进程的执行完全依赖于另一个进程----其合作伙伴的消息，当一个进程到达了某一确定点而没有得到合作伙伴发来的“已完成某些事件”的信息时，必须等待，直到该消息到达被唤醒后，才能继续向前推进。

2.7.1 进程同步和互斥的关系

• 相似处：进程的互斥实际上是进程同步的一种特殊情况；进程的互斥和同步统称为进程同步。
• 差别：进程互斥是共享资源的使用权，没有固定和必然的联系；而进程的同步涉及到共享资源的并发进程间的一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。

3. 信号量机制

• 信号量机制的基本原理是：两个或多个进程可以利用彼此间收发的简单信号来实现“正确的”并发执行，一个进程在收到另一个指定信号前，会被迫在一个确定的或者需要的地方停下来，从而保持同步或互斥。
• 信号量（信号灯），是表示某类资源实体与进程队列有关的整型变量（一种数据结构）。一般是由两个成员组成，是一个确定的二元组（S,Q）;其中，S是个具有非负初值的整型变量，表示信号量的值，且S的值只能由定义在信号量上的P操作原语和V操作原语来改变；Q是个初始状态为空的队列。

3.1 信号量整型分量S的物理含义☆☆

S的值只能由P、V操作来改变

• 当$S\ge 0$时： 表示某类资源可用资源的数目，或者说表示可以执行P操作而不会被阻塞的进程数目。
• 当$S<0$时： 其绝对值表示信号量S的阻塞队列中的进程数，即系统中 因为请求该类资源而被阻塞的进程的数目。这些进程需要其他进程发出相应的信号灯来唤醒。

3.2 P、V操作

P代表荷兰语proberen，意为“测试”。国外的文献可能使用Wait、Down代替。
V代表荷兰语verhogen，意为“增加”。或用Signal、Up代替。
原语是操作系统内核中由若干条指令构成用于完成特定功能的一个过程，该过程是不可分割的，具有原子特性，是机器指令的延伸。

1. 定义在信号量S上的P(S)原语操作
   算法描述：
   （1）S减一；
   （2）若$S\ge 0$,则调用P(S)的进程正常返回；
   （3）else，调用者进程调用阻塞原语Block（Q），把自己插入到信号量S的阻塞队列Q中（把相应的PCB连入到该信号量队列的末尾，并放弃CPU，进入等待）。
2. 定义在信号量S上的V(S)原语操作
   算法描述：
   （1）S加一；
   （2）若$S>0$,则调用V(S)的进程正常返回；
   （3）else，调用者进程调用唤醒原语Wakeup（Q），把信号量S的阻塞队列Q中的队首进程移出并唤醒，返回。

3.3 P(S)操作和V(S)操作的物理含义

• P(S)操作，是在测试一个信号是否到达，表示“等信号”。
• V(S)操作，表示“发信号”。在实现同步时，意味着“合作的伙伴已经完成前趋任务了，剩下的该轮到自己继续干了”；在实现互斥时，意味着“有进程释放了临界资源通知了其他进程，现在有空闲可用的临界资源”
• 在互斥问题中，每执行一次P(S)操作的意义可以理解为，进程请求一个单位的S类资源；每执行一次V(S)操作的意义可以理解为，进程释放了一个单位的S类资源。

3.4 使用P、V操作实现几个经典的同步、互斥问题

• 实现互斥的P、V操作都在同一个进程中，是为了维持一次仅允许一个进程进入临界区，其他想进入临界区的进程需要先测试（P一下）看看是否有其他的进程正处于临界区，然后做出相应的回应。
• 实现同步的P、V操作分别在两个进程中，是为了能实现两个进程相互通信的情形。例如做完前趋工作的进程A现在要通知它的合作伙伴进程B告知他前趋工作已做完。这时候进程A只要P一下相应信号量，那边的进程B只需要V一下测试进程A是否通知了自己，就能做出相应的回应。

由于能力和精力等有限，会在下一次专门编写思路过程+代码 （下次一定）

4. 死锁

• 死锁： 是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。称此时系统处于死锁状态 或 系统产生了死锁；称这些永远在互相等待的进程为死锁进程。

4.1 产生死锁的原因

1. 竞争临界资源
2. 进程推进顺序的不当

4.2 产生死锁的必要条件

1. 互斥条件：每一个资源要么被分配给一个进程，或者空闲。
2. 占有并请求条件：已分配到了一些资源的进程可以申请新的资源。
3. 不可剥夺条件：进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。
4. 循环等待条件：链中的每一个进程都在等待相邻进程所占用的资源。

4.3 死锁的解决办法

1. 死锁的预防：（1）静态资源分配法：在每个进程开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。若系统有足够的资源，会把进程想要的资源一次性的分配给它；若系统没有足够的资源，则一个资源也不分配给它。（2）有序资源使用法：系统类的资源按类都被赋予一个唯一的编号，每个进程只能按编号升序的申请资源。 (3) 摒弃“不可剥夺条件”： 一个已经保持了某些资源的进程，当它再提出新资源申请而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。
2. 死锁的避免： （1）系统的安全状态和不安全状态 （2）银行家算法

系统的安全状态和不安全状态：

• 安全状态：若在某一时刻，系统能按某种进程顺序，为每个进程分配其所需的资源，直至最大需求，使得每个进程均可顺利完成，则称此时系统的状态为安全状态，称这个进程顺序为安全序列；安全序列即，当前进程所需的<系统当前空闲的，当这个进程运行结束后，系统空闲的 = 该进程拥有的 + 刚才系统空闲的。然后找出一个顺序使得对于每一个进程都有，当前进程所需的<系统当前空闲的。
• 不安全状态：在某一时刻，系统中不存在一个安全序列，称系统处于不安全状态。

注意：（1）系统在某一时刻的安全状态可能不唯一，但这不影响对系统安全性的判断。 （2）安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅进入死锁状态。其示意图如下

银行家算法：
银行家算法执行有个前提条件，即要求进程预先提出自己的最大资源请求，并且假设系统拥有固定的资源总量。
其所需的数据结构有:

1. 可用资源向量 available：记录系统中各类资源的当前可利用数目。
2. 最大需求矩阵 max：记录每个进程对各类资源的最大需求量。
3. 分配矩阵 allocation: 记录每个进程对各类资源当前的占有量。
4. 需求矩阵 need: 记录每个进程对各类资源还需要的数目 = max - allocation。
5. 请求向量 request: 记录某个进程当前对各类资源的申请量，是银行家算法的入口参数。

算法描述：
设进程P_i向系统发出请求后，

1. 若Request_i > Need_i ，即请求的数目 > 自己记录的需要的数目，则出错。
2. 若Request_i > Available_i ，即请求的数目 > 系统中当前可用的数目， 则P_i阻塞。
3. 系统试探把资源分配给进程P_i ，修改数据结构中的数值：（1）Available_i = Available_i - Request_i; 即当前可用数 = 可用数 - 请求数（2）Allocation_i = Allocation_i + Request_i; 即当前分配数 = 分配数 + 请求数 （3）Need_i = Need_i - Request_i;即当前需求数 = 需求数 - 请求数。
4. 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，正式将资源分配给进程P_i， 完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程P_i 等待。

3. 死锁的检测和恢复：（1）撤销进程法：1.撤销全部死锁进程 2.最小代价撤销法 （2）挂起进程法（剥夺资源）
4. 鸵鸟算法：因为死锁是小概率事件，并且解决死锁的代价太大。因此系统采取忽略它的方法，主权交给用户或管理员，他们可以使用系统提供的命令撤销自己认为可能陷入死锁的进程已解救死锁。

5. 处理机调度

5.1 调度算法

从资源的角度来看，该算法确定了处理机的分配策略，故称为处理机调度算法。（本质）
从资源使用者的角度来看，该算法确定了进程运行的次序，故称为进程调度算法。
处理机的使用方式有：（1）不可抢占方式（2）可抢占方式

• （1）先来先服务调度算法（FCFS，First Come First Severd）
  该算法按照进程进入就绪队列的先后顺序选择最先进入该队列的进程，把处理机资源分配给它。
  这是不可抢占方式的调度算法，实现简单，但是后来的进程等待CPU时间较长.

• (2）短作业优先 / 进程最优 调度算法（SJF / SPF，Shortest Job First / ）
  SJF： 该算法总是从后备队列中选取估计运行时间最短的作业，先调入内存运行。
  SPF： 该算法总是从就绪队列中选取估计运行时间最短的作业，先将处理机分配给它，使它立即执行。
  这是不可抢占方式的调度算法，优点是系统吞吐量大、实现简单。最大的缺点是，长作业等待时间可能过长，一直得不到调度。

• （3）最高响应比优先（HRRF， Highest Response Ration First）
  该算法总是选取响应比最高的作业运行。
  主要缺点是每次调度时都需要计算各道作业的响应比，也是一部分时间开销。
  响应比 = （作业等待时间 + 作业估计运行时间）/ 作业估计运行时间
  = 1 + 作业等待时间 / 作业估计运行时间

  可以将响应比看做类似优先级的概念
  易知响应比与作业等待时间呈正相关，即作业等待时间越长，响应比越高
  响应比与作业估计时间呈负相关，即作业估计运行时间越长，响应比越低

• （4）优先级调度算法（Priority）
  该算法总是选择具有最高优先级的进程首先使用处理机。交互式系统常用优先数来表示进程的优先级，而优先数就是一个用来表示进程使用处理机的优先程度的整数，它分为固定值的静态优先数 和 可变值的动态优先数。
  这是一种可抢占方式的调度算法。

  1. 静态优先权： 在创建进程的时候便确定，且在进程的运行期间保持不变。优点是简单易行，系统开销小缺点是优先权低的进程可能长时间不被调度。
     2.动态优先权： 在创建进程时所赋予的优先权，可以随进程的推进而改变，以获得更好的调度性能。

• （5）时间片轮转调度算法（RR， Round Robin）
  该算法把所有的就绪进程按FCFS原则排成一个队列，且规定一个时间片作为进程每次使用处理机的最长时间单位，按时间片把处理机轮流分配给当前位于就绪队列队首的进程使用，当该进程的时间片用完以后，系统产生时钟中断，剥夺该进程的执行，将它送到就绪队列队尾，等待下一轮的调度。同时处理机调度程序又去调度当前就绪队列的队首进程，也让它运行给定的时间片，如此循环往复。
  缺点是，时间片不好确定。因为时间片是固定不变的。

• （6）多级反馈队列（MFQ，Multilevel Feedback Queues）
  该算法的基本思想为：
  1）首先，系统按进程优先级设置了多级就绪进程队列，从第一级队列到最后一级队列，优先级越来越低。
  2）其次，每一级就绪队列对应一个不同的时间片。优先权越高的队列，进程的时间片越小。
  3）再次，当一个新进程进入内存后，首先被放到第一级优先队列的队尾。按照FCFS原则排队等待调度。当轮到该进程执行时，如能在时间片内完成，便可准备撤离系统；如果在时间片内未完成，调度程序将转入第二队列的末尾，再次依照FCFS原则等待调度。
  4）最后，仅当第一级队列为空时，才调度第二级队列中的进程；如此下去，仅当前面的n - 1级队列全部为空时，才去调度最后第n级队列中的进程。如果处理机正在第I队列中为某进程服务，此时又有新的进程进入至第I级之前的队列，则系统抢占正在运行的进程的处理机，由调度程序将刚被抢占的进程放入第I级队列的队尾，重新进行处理机调度。

5.2 调度时机

当发生以下几种情况时，现行进程都要放弃处理机的使用，即将引起系统对进程的重新调度。

1. 在分时系统中，现行进程的时间片用完了；
2. 发生了外部中断
3. 进程因等待某事件或资源而阻塞
4. 现行进程运行结束或出现异常情况。

5.3 调度过程

1. 保存“下降”进程现场
2. 选择将要运行的进程----“上升”进程
3. 恢复“上升”进程的现场

6. 线程

线程是进程中可独立执行的子任务，是进程中的一个实体，是系统独立调度和分派的基本单位。一个进程中至少有一个线程。线程继承所属进程的一切资源，线程自身只拥有运行时所需的很少的一点资源。

6.1 线程和进程的比较

1. 拥有的资源
   进程都是拥有资源的一个独立单位，它可以拥有自己的资源。而线程几乎不拥有系统系统资源，但它可以访问其隶属进程的资源。
2. 可调度性
   以进程为单位进行处理机切换和调度时，处理机切换时间长，资源利用率降低；以线程为单位进行处理机切换和调度时，由于不发生资源变化，特别是地址空间的转化，处理机切换时间较短，从而处理机效率较高。
   在传统的操作系统中。进程既是拥有资源的基本单位，又是能独立调度的基本单位；在引入线程的系统中，进程只是拥有资源的基本单位，而线程是调度与分派的基本单位。
3. 并发性
   在引入线程的操作系统，不仅进程之间可以并发执行，而且线程之间也可以并发执行，因而使操作系统具有更好的并发性，从而能更有效的利用系统资源，提高系统的吞吐量。
4. 系统开销
   系统在创建和撤销进程时，系统要为之分配或回收资源。显然，系统创建进程的开销要远大于线程的开销。类似地，操作系统为进程切换付出的开销也要远大于线程切换的开销。另外，由于同一进程内的多个线程具有相同的地址空间，致使它们之间的同步与互斥的实现，也变得比较容易。
5. 系统感知方面
   进程的调度、同步等由操作系统内核完后，而线程的控制既可以由操作系统内核进行，也可以由用户控制。