进程与线程

进程是资源分配的基本单位，也是独立运行的基本单位。进程是资源分配的基本单位，这是与线程的主要区别。

程序的顺序执行具有如下特征：

顺序性；处理器的操作严格按照程序所规定的顺序执行。封闭性：程序一旦开始运行，其执行结果不受外界因素影响。可再现性：只要执行时的初始条件与执行环境形同，当程序重复执行时，都将得到相同的结果。

程序的并发执行是指若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的。

程序的并发执行的特征：

间断性：有共享资源而产生的程序间的间接制约关系导致并发程序具有“执行-暂停-执行”这种间断性的活动规律。失去封闭性：多个程序共享系统中的各种资源，因而这些资源的状态有多个程序来改变，致使程序的运行失去封闭性。不可再现性：由于失去了封闭性 ，导致程序失去其运行结果的可再现性。

程序并发执行的条件（Bernstein条件）：

，表示程序在执行期间所需引用的所有变量的集合，成为读集。

，表示程序在执行期间要改变的所有变量的集合，称为写集。

若两个程序满足下述的三个条件（又称为Bernstein条件）,它们便可以并发执行，且其结果据哦于可再现性。

.

进程

进程：进程是可以并发执行的计算部分。

进程的特征：

动态性、并发性、独立性、异步性、结构特征。

结构特征：每个进程都由程序段、数据段和一个进程控制块（PCB）组成。

进程和程序的关系

进程是动态的，程序是静止的。进程是程序的执行，程序是有序代码的集合，无执行含义。进程是暂时的，程序是永久的。进程是一个状态变化的过程，程序可以长久保存。进程与程序的组成不同。通过多次执行，一个程序可以产生多个不同的进程；通过调用关系，一个进程可以执行多个程序。进程可创建其他进程，程序不能形成新的程序。进程具有并行特性（独立性、异步性），程序没有。

进程映像（不重要）

由程序段、相关数据段、PCB三部分构成了进程映像，也叫进程实体。进程映像是静态的，进程是动态的，进程是进程实体的运行过程。

作业的定义见此处

进程和作业的区别

作业是用户需要计算机完成某项任务而要求计算机所做的工作的集合；进程是已提交完毕的作业的执行过程，是资源分配的基本单位。

两者主要区别如下：

作业时用户向计算机提交任务的任务实体，进程则是完成用户任务的执行实体。一个任务可以由一个或多个进程组成，但进程不能构成多个作业。作业的概念主要用于批处理系统中，进程的概念几乎都有雨多道程序系统中。

进程的组成

进程控制块（PCB）：每个进程均有一个PCB，它是一个即能标识进程的存在、又能刻画执行瞬间特征的数据结构。

程序段：程序段是进程中能被进程调度程序调度到CPU上执行的程序代码段，能实现相应的特定功能。

数据段：一个进程的数据段可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间结果或结果数据。

通常PCB都包括以下内容：

进程标识符（PID）

进程当前状态

进程队列指针：用于记录PCB队列中下一个PCB的地址。

程序和数据地址

CPU现场保护区 ：当进程因某种原因释放处理器时，CPU现场信息（如指令计数器、状态寄存器、通用寄存器等）被保证在PCB的该区域中，以便该进程重新获得处理器后 能继续执行。

通信信息

家族联系

占有资源清单

PCB的作用

保证程序的并发执行。创建进程，实质上是创建进程的PCB；撤销进程则是撤销进程的PCB。

为什么PCB是进程的存在的唯一标志

系统总是通过PCB对进程进行控制的。

进程的状态与转换

创建状态：进程在创建时需要申请一个空白PCB，向其中填写控制和管理进程的信息，完成资源分配。如果创建工作无法完成，比如资源无法满足，就无法被调度运行，把此时进程所处状态称为创建状态

就绪状态：进程已经准备好，已分配到所需资源，只要分配到CPU就能够立即运行

执行状态：进程处于就绪状态被调度后，进程进入执行状态

阻塞状态：正在执行的进程由于某些事件（I/O请求，申请缓存区失败）而暂时无法运行，进程受到阻塞。在满足请求时进入就绪状态等待系统调用

终止状态：进程结束，或出现错误，或被系统终止，进入终止状态。无法再执行

进程状态的相互转换，省略了创建和删除。

进程的控制

包括进程的创建、进程的撤销、进程阻塞和唤醒、进程的切换等。

线程

定义：线程是进程内一个相对独立的、可调度的执行单元。

线程与进程的异同

调度：线程是独立调度的基本单位，进程是拥有资源的基本单位。拥有资源：进程是拥有资源的基本单位，而线程进拥有一点必不可少的资源（如程序计数器、一组寄存器和栈），但线程可以访问其隶属进程的系统资源。并发性：在引入线程的操作系统中，不仅进程间可以并发执行，同一进程内的多个线程也可以并发执行。使操作系统具有更好的并发性，大大提高了系统的吞吐量。系统开销：线程的创建、撤销、切换所需的系统开销都比线程的大得多。

进程通信

进程通信指的使进程之间的信息交换。

高级进程通信方式可以分为3大类：共享存储器系统、消息传递系统、管道通信系统。

处理器调度

处理器的三级调度

调度是操作系统的一个基础功能，几乎所有资源在使用前都需要调度，调度设计均围绕如何高效利用CPU展开。

高级调度（作业调度）：主要任务是按照一定的原则从外存上出于后备状态的作业中选择一个或者多个，给它们分配内存、输入／输出设备等必要资源，别难过建立相应的进程，以使改作业具有竞争处理器的权利。作业调度的运行频率较低，通常为几分钟一次。

中级调度：主要任务使按照给定的原则和策略，将出于外存对换区中具备运行条件的进程调入内存，并将其状态修改为就绪状态，挂在就绪队列上等待；或者将出于内存中在世不饿能运行的进程交换到外存对换区，将此时的进程状态称为挂起状态。主要涉及内存管理和扩充。

低级调度（进程调度）：主要任务使按照某种策略和方法从就绪队列中选取一个进程，将处理器分配给它。进程调度的运行频率很高，一般几十毫秒运行一次。

高级调度与低级调度的区别：

作业调度为进程调度做准备，进程调度使进程被调用。作业调度频率低，进程调度频率高。有的系统可以不设置作业调度，但进程调度必须有。

调度的基本原则

CPU利用率系统吞吐量

标傲世单位时间内CPU完成作业的数量。响应时间周转时间

周转时间：指作业从提交至完成的时间间隔，包括等待时间和执行时间。周转时间用公式表示为

作业i的周转时间=作业i的完成时间-作业i的提交时间

平均周转时间：至多个作业周转时间的平均值。

带权周转时间：指作业周转时间与运行时间的比。作业i的带权周转时间用公式表示为

=作业i的周转时间/作业i的运行时间

平均带权周转时间：与平均周转时间类似，求平均即可。

调度算法

1. 先来先服务调度算法（FCFS）（作业调度、进程调度）

2.短作业优先调度算法（SJF）（作业调度、进程调度）

3.优先级调度算法（作业调度、进程调度）

4.时间片轮转调度算法（进程调度）

系统将所有就绪进程按到达时间的先后次序排成一个队列，进门处调度程序总是选择队列中的第一个进程执行，并规定执行一定时间，称为时间片。当该进程用完这一时间片时（即是进程并未执行结束），系统将他送至就绪队列队尾，在把处理器分配给下一个就绪进程。

时间片的大小通常由以下因素确定：系统相应时间、就绪队列中的进程数目、系统处理能力

5. 高响应比优先调度算法（作业调度）

响应比=作业响应时间/估计运行时间

即

响应比=（作业等待时间+估计运行时间）/估计运行时间

6. 多级队列调度算法（进程调度）

基本思想：根据进程的性质或类型，将就绪队列划分为若干个独立的队列，每个进程固定地分属于一个队列。每个队列采取一种调度算法，不同的队列可以采用不同的调度算法。

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

多级反馈队列调度算法时时间片轮转调度算法和优先级调度算法的综合和发展。通过动态调整进程优先级和时间片大小，可兼顾多方面的系统目标。

同步与互斥

基本概念

两种形式的制约关系

间接相互制约关系（互斥）：若某一进程要求使用某种资源，而该资源正被另一进程使用，并且该资源不允许两个进程同时使用，那么该进程只好等待已占用资源的进程释放资源后在使用。这种制约关系的基本形式是“进程-资源-进程”。

直接相互制约关系（同步）：某一进程若收不到另一进程给他提供的必要信息就不能继续运行下去，这种情况表明了两个进程之间ian在某些点上要交换信息i，相互交流运行情况。这种制约关系的基本形式是“进程-进程”。

区分方法：同类进程即为互斥关系，不同类进程为同步关系。

临界资源与临界区

临界资源：同时仅允许一个进程使用的资源。

临界资源的访问可以分为四个部分：

进入区

临界区。进程中用于访问临界资源的代码。

退出区

剩余区

临界资源与临界区的区别：临界资源是一种系统资源，需要不同进程互斥访问；临界区是每个进程中访问临界资源的一段代码，是属于对应进程的。

互斥的概念与要求

为禁止两个进程同时进入临界区，软件算法或同步机构都应遵循以下准则。

空间让进忙则等待有限等待让权等待

同步的概念与实现机制

可以用信号量实现同步。

互斥实现方法

1.软件方法

算法1：设置一个公用整形变量turn，用来表示允许进入临界区的进程标识。若turn为0，则允许进程P0进入临界区；否则循环检查该变量，直到turn变为本进程标识；在推出去，修改允许进入进程的标识turn为1. 进程P1的算法于此类似，两个进程的程序结构如下：

int turn = 0;P0:{Do{While(turn!=0); //当turn不为0时循环检查，直到为0（进入区）进程P0的临界区代码CS0； //（临界区）turn=1； //退出区进程P0 的其他代码；}While（true） //循环执行这段代码}P1:{Do{While(turn!=1); // 进入区）进程P0的临界区代码CS1； //（临界区）turn=0； //退出区进程P1 的其他代码；}While（true） //循环执行这段代码}

此方法可以保证互斥访问临界资源，但存在的问题是强制两个进程以交替次序进入临界区，很容易造成资源利用不充分。例如，当进程P0退出临界区后将turn设置为1，但此时P1暂时不要求访问该临界资源，而P0又想再次访问临界资源，则它将无法进入临界区。可见，此算法无法保证实现“空闲让进”准则。

算法2：设置标志数组flag[]表示进程是否在临界区中执行，初值均为假。在每个进程访问该临界资源之前，现检查另一个进程是否在临界区中，若不再，则修改本进程的临界区标志为真，并进入临界区，在推出区修改本进程临界区标志为假。两进程的程序结构如下：

enmu boolean{false,true}; //设置数组元素类型boolean flag[2]={false,false}; //设置标志数组P0:{DO{While flag[1]; //flag[1]为真表示P1在访问临界区，P0等待 （进入区）flag[0] = true; //进入区进程P0的临界区代码CS0; //临界区flag[0] = flase; //退出区进程P0的其他代码；}While(true)}P1:{DO{While flag[0]; //flag[0]为真表示P0在访问临界区，P0等待 （进入区）flag[1] = true; //进入区进程P0的临界区代码CS1; //临界区flag[1] = flase; //退出区进程P1的其他代码；}While(true)}

此算法解决了‘空闲让进“的问题，但当两个进程都为进入临界区时，此时各自的访问标志都为false，若此时两个进程同时想进入临界区，并发现对方的标志值为false，于是两个进程同时进入了各自的临界区，违背了临界区的访问规则”忙则等待“。

算法3：仍然设置flag[]，但标志用来表示进程是否希望进入临界区，每个进程在访问临界资源之前，先将自己的标志设置为真，然后检查另一个进程的标志。若另一个进程的标志为真，则进程等待；反之则进入临界区。两进程的程序结构如下：

enmu boolean{false,true}; //设置数组元素类型boolean flag[2]={false,false}; //设置标志数组P0:{DO{flag[0] = true; //进入区While flag[1]; //flag[1]为真表示P1希望访问临界区，P0等待 （进入区）进程P0的临界区代码CS0; //临界区flag[0] = flase; //退出区进程P0的其他代码；}While(true)}P1:{DO{flag[1] = true; //进入区While flag[0]; //flag[0]为真表示P0希望访问临界区，P0等待 （进入区）进程P0的临界区代码CS1; //临界区flag[1] = flase; //退出区进程P1的其他代码；}While(true)}

与算法2类似，同时请求时，两进程标志都为true，都认为对方希望进入临界区，并阻塞自己，造成”死等“现象，违背了”有限等待“准则。

算法4：算法3与1的结合。标志数组flag[]表示进程是否希望进入临界区或是否在临界区中执行。此外，还是只一个turn变量，用于表示允许进入临界区的进程表示。两进程的程序结构如下：

enmu boolean{false,true}; //设置数组元素类型boolean flag[2]={false,false}; //设置标志数组int turn; P0:{DO{flag[0] = true; //进入区turn =1; //此时P0未进入临界区，仍然允许P1进入临界区（进入区）While (flag[1] && turn==1); //flag[1]为真表示P1希望访问临界区，turn为1表示P1可以进入临界区，P0等待 （进入区）进程P0的临界区代码CS0; //临界区flag[0] = flase; //退出区进程P0的其他代码；}While(true)}P1:{DO{flag[1] = true; //进入区turn = 0; //此时P1未进入临界区，仍然允许P0进入临界区（进入区）While (flag[0] && turn == 0); //flag[0]为真表示P0希望访问临界区，turn为0表示P0可以进入临界区，P1等待 （进入区）进程P1的临界区代码CS1; //临界区flag[1] = flase; //退出区进程P1的其他代码；}While(true)}

此算法可以完全正常工作。

2.硬件方法

信号量

信号量是一个确定的二元组（s,q），其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。s表示系统中某类资源的数目，当其值大于0时，表示系统中当前可用资源的数目；当小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。

P操作：先执行s=s-1；若s>=0，则该进程继续运行；若s<0，则阻塞该进程，并将它插入该信号量的等待队列中。相当于申请资源

V操作：先执行s=s+1；若s>0，则该进程继续执行；若s<=0，则从该信号量等待队列中移出第一个进程，使其变为就绪状态并插入就绪队列，然后再返回原进程继续执行难。相当于释放资源。

信号量的应用

1.实现进程同步

假设存在并发进程P1，P2.P1中有一条语句S1，P2中有一条语句S2，要求S1必须在S2之前执行。

semaphore N=0; //设置信号量并设置初始值为0P1(){...S1;V(N)...}P2(){...P(N)S2;...}

2.实现进程互斥

semaphore N=1; //设置信号量并设置初始值为0P1(){...P(N);P1的临界区代码；V(N)...}P2(){...P(N)P2的临界区代码；V(N);...}

经典同步问题

生产者-消费者问题

它描述的是一组生产者向一组消费者提供产品，它们共享要给有界缓冲区，生产者向其中投入产品，消费者从中取走产品。

Semaphore full=0; //满缓冲区数目Semaphore empty=n; //空缓冲区数目Semaphore mutex=1; //对有界缓冲区进行操作的互斥信号量Producer(){while(true){Produce an imtem put in nextp; //nextp为临时缓冲区P(empty);P(mutex);将产品放入缓冲池V(mutex);V(full);}}Consumer(){while(true){P(full); //申请一个满缓冲区P(mutex); //申请使用缓冲区取出产品V(mutex); //缓冲池使用完毕，释放互斥信号量V(empty); //增加一个空缓冲区Consumer the item in nextc; //消费掉产品}}

信号量机制问题的解题步骤

关系分析。只要存在一堆同步关系，往往就需要一种资源信号量。确定临界资源。临界区通用写法为：

P(N) //可有可无，根据题目中的同步互斥关系决定P(mutex)访问临界资源V(mutex)V(N) //可有可无，根据题目中的同步互斥关系决定

整理思路。确定问题中不同角色进程的具体岱庙及其所用到的信号量，完成问题的解答。

管程

管程定义了一个数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。

管程具有以下基本特征

局部于管程的数据只能被局部于管程的过程所访问。一个进程只能通过调用管程内的过程才能进入管程的访问共享数据。每次仅允许一个进程在管程内执行某个内部过程，即进程互斥地通过调用内部过程进入管程。局限于管程并仅能从管程内进行访问的若干条件变量，用于区别各种不同的等待原因。在条件变量上进行操作的两个函数过程wait和signal。

死锁

定义：当多个进程因竞争系统资源或相互通信而出于永久阻塞状态时，若无外力作用，这些进程都将无法向前推进。这些进程中的每一个进程，均无限期地等待词组进程中某个其他进程占有的、自己永远无法得到的资源，这种现象叫死锁。

死锁产生的原因和必要条件

资源分类：可剥夺资源；不可剥夺资源

死锁产生的原因：系统资源不足、进程推进顺序不当。系统资源不足是产生死锁的根本原因，进程推进不当是产生死锁的重要原因。

死锁产生的必要条件：互斥条件、不剥夺条件、请求与保持条件、环路等待条件。要产生死锁，4个条件缺一不可，因此可以通过破话其中一个或几个条件来避免死锁的产生。

处理死锁的基本方法

鸵鸟算法。不理睬死锁。预防死锁。通过设置某些条件，区破坏产生死锁的4个必要条件中的一个或几个。避免死锁。在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁的产生。检测及解除死锁。通过系统的检测机构及时检测出死锁的发生，然后采取某种措施解成死锁。

预防和避免的区别：

死锁的预防方法中，总的来说都施加了较强的限制条件，虽然实现较为简单，却严重损害了系统性能。在避免死锁的办法中，所施加的条件较弱，可以获得较好的系统性能。

死锁的预防（严格）

4个条件的破坏

互斥条件：不大可能破坏。

不剥夺条件：对于一个已经获得了某些资源的进程，若新的资源请求不能立即得到满足，泽它必须释放所有已经获得的资源，以后需要资源时再重新申请。该策略实现比较复杂，且会增加系统开销，降低系统吞吐量。通常不会用于剥夺资源后代价较大的场合，如打阴界。

请求与保持条件：为破坏请求与保持条件，可以采用预先静态分配方法。预先静态分配发要求进程再其运行之前一次性申请所需要的全部资源，再它的资源未满足前不投入运行，一旦投入运行，这些资源就一直归它所有，也不再提出其他资源请求。降低资源利用率，容易导致其他进程残生“饥饿”现象。

环路等待条件：未了破坏环路等待条件，可以采用有序资源分配法。有序资源分配法时将系统中的所有资源都按类型赋予一个编号（如打印机为1，磁带机为2），要求每一个进程均严格按照编号递增的次序请求资源，同类资源一次申请完。造成资源浪费，增加程序复杂性。

死锁的避免（相对宽松）

若在某一时刻，系统能按某种顺序来为每个进程分配其所需的资源，直至最大需求，使每个进程都可顺利完成，则称此时的系统状态为安全状态，称该序列为安全序列。

若某一时刻系统中不存在安全序列，则称此时的系统状态为不安全状态。

PS：1.不安去状态不是指系统中已经产生死锁。处于不安全状态的系统不会必然导致死锁。

银行家算法

简单说就是分为以下步骤：

1，先看进程请求的资源是否小于或等于其所需的，是则进行，否则报错

2.看进程请求的资源是否小于或等于可用的，是则进行，否则报错

3.资源预分配

4.对于修改后的向量，调用安全性算法，安全则执行，否则让进程等待，并恢复第三步中所改变的向量。

懒得打，网上找的

死锁的检测与解除

死锁定理

可以用简化资源分配图的方法来检测系统状态S是否是死锁状态。简化方法如下：

在资源分配图中，找出一个既不阻塞又非孤立的进程结点Pi（即从进程集合中找到一个存在连接的边，且资源申请数量小于系统中已有空闲资源数量的进程）。因进程Pi获得了所需的资源，他能继续运行直到完成，然后释放器占有资源（相当于消去Pi的所有申请边与分配边，使之编程孤立的结点）。在进程Pi释放资源后，可以唤醒因等待这些资源而阻塞的进程，根据第一步的方法，进一步消去边。重复前两步，若能使所有结点编程孤立结点，则称改图是可完全简化的。

系统状态S为死锁的条件是：当且仅当S章台的资源分配图是不可完全简化的，该定理称为死锁定理。

死锁解除

剥夺资源。从其他进程中抢占足够的资源给死锁的进程以解除其死锁状态。

撤销进程。撤销一些进程，直到有足够的资源分配给其他进程，解除死锁状态。

进程回退。让一个或多个进程回退到足以回避死锁的地步，进程回退时资源释放资源。

死锁与饿死

当等待四件给进程推进和响应带来明显影响时，则称此时发生了进程饥饿，当进程饥饿到一定程度，进程所赋予的任务即使完成也不再具有实际意义时，称该进程被饿死。

饿死与死锁的联系：二者都是由于竞争资源而引起的。

区别：

死锁进程都出一等待状态；忙时等待的进程并非处于等待状态，但却可能被饿死。死锁进程等待的时永远不会释放的资源；饿死进程等待的时会被释放但却不会分配给自己的资源，表现为等待时间没有上界。死锁一定发生了循环等待，饿死则不然。死锁一定涉及多个进程，而饥饿或二四的进程可能只有一个。