程序顺序执行与并发执行

吞吐率

衡量一个系统效率的一个指标就是吞吐率，计算公式如下:

$吞吐率=\frac{作业道数}{全部作业时间}$

提高系统的吞吐量应当提高系统资源的利用率

多道程序的缺点

多道下内存和处理机利用率得到显著提高。但是内存存放程序数量并非越多越好

影响系统的响应速度
产生过多的系统开销（系统本身运行的时空耗费）。

多道程序设计提高了系统效率，也带来了系统资源的竞争，因此要协调程序与资源的关系。处理机、存储器和外部设备是计算机系统中重要的硬件资源，因而需要解决处理机资源管理、存储器分配和回收以及外部设备资源管理等问题。

现代操作系统的重要特征

现代操作系统重要特征：并发、资源共享、用户随机使用资源。

程序的顺序执行与并发执行

前驱图

前驱图是一个有向无循环图，记为DAG(Directed Acyclic Graph)，可用于描述进程之间执行的前后关系。

与之相关的概念如下:

结点：一个程序段、进程或一条语句；
有向边：两个结点之间的前趋关系；
重量：结点所含有的程序量或执行时间；
直接前驱、直接后继、开始结点、终止结点

上述DAG图存在的前驱关系如下:

P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9；

前趋图中必须不存在循环。

程序的顺序执行

程序顺序执行具有如下 3 个特点：

顺序性；顺序执行行过程可看作一系列严格按程序规定的状态转移过程。
封闭性；程序执行得到的最终结果由给定的初始条件决定，不受外界因素的影响。
可再现性；只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果。

程序顺序执行的特性为程序员检测和校正程序错误带来很大的方便！

多道的执行环境特点

计算机能够同时处理多个具有独立功能的程序。多道的执行环境具有如下 3 个特点：

独立性；每道程序都是逻辑上独立的。
随机性；多道程序环境下，特别是多用户环境下，程序和数据输入与执行开始时间都是随机的。
资源共享； 资源共享将导致对程序执行速度的制约。外设有限将导致这些设备被共享、内存有限将导致内存被共享等。对单CPU系统更如此。

程序的并发执行

不同程序之间可以并发执行，这是系统的并发性，一个程序内部语句之间在并发环境下依然有并发执行的情况，如下面的情况:

S0：x = a+10；
S1：y = b - a；
S2：z = x+y-10；
S3：print（z）；

程序内部各程序段间是否具备并发执行是由它们之间依赖关系所决定。

并发性是增强计算机系统的处理能力和提高资源利用率所采取的一种技术。程序的并发执行通过前面的分析可分为两种：

多道程序系统的程序执行环境变化所引起的多道程序的并发执行。多道程序并发执行在宏观上是同时进行的，但在微观上仍是顺序执行的。
并发执行是在某道程序的几个程序段中，包含着一部分可以同时执行或顺序颠倒执行的代码。

在时间上来表示，并发执行是一个程序的开始是在另一个程序结束之前。

并发执行的特点

间断性

程序在并发执行时，由于它们共享资源或为完成某一项任务而合作，致使在并发程序之间存在相互制约的关系。

失去封闭性

程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。当处理机资源被其它程序占用时，有条件运行的任何程序都必须等待。

不可再现性

程序在并发执行时，由于失去了封闭性，也导致失去了可再现性。

并发执行的条件

在某些情况下，程序的并发执行使得执行结果不再具有封闭性和可再现性，且可能造成出现错误（执行结果受执行速度影响的结果）。

为了使在并发执行时不出现错误结果，必须采取某些措施来制约、控制各并发程序段执行速度。

1966年Bernstein 提出了相邻语句S1，S2可以并发执行的条件：

语句Si划分为两个变量集合R(Si)和W(Si)；分别为 Si 的读集和写集。

其中，R(Si)={a1，a2，…，am}是语句Si在执行期间对其进行参考的变量；aj(j=1，…，m)。

W(Si)={b1，b2，…，bn}是语句Si在执行期间对其进行访问的变量；bj(j=1，…，n)。

如果对于语句 S1 和 S2，有

① R(S1)∩ W(S2)=Ø，即S1读变量不是S2 修改的变量。

② W(S1)∩ R(S2)=Ø，即S2读变量不是S1 修改的变量。

③ W(S1)∩ W(S2)=Ø，即双方都不修改相同的变量。

如果并发执行的各程序段中语句或指令满足上述Bernstein 的三个条件（同时成立），则认为并发执行不会对执行结果的封闭性和可再现性产生影响（证明略）。

但在一般情况下，这个条件对于软件设计（模块化）过于苛刻，系统要判定并发执行的各程序段是否满足Bernstein条件是相当困难的。从而，如果并发执行的程序段不按照特定的规则和方法进行资源共享和竞争，则其执行结果将不可避免地失去封闭性和可再现性。

进程

进程的提出

根据Bernstein 条件，我们不能通过限制程序的编写方式和内容来获得系统的可再现性，因此解决此问题可能需要依靠控制程序的执行过程来解决。因为操作系统用户随机性与各道程序逻辑独立的特点将使得每个用户程序所使用的软、硬件资源都受到其他并发程序的共享和竞争，从而得到非预料的或不正确的结果。为了控制和协调各程序执行过程中的软、硬件资源的共享和竞争，显然，需要有一个能描述程序的执行过程且能用来共享资源的基本单位。这个基本单位被称为进程（或任务）。

进程是可并发执行的程序在一个数据集合上的运行过程。

进程是指进程实体的运行过程。

进程和程序的比较

程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念。程序是静态的，进程是动态的
程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的；
进程更能真实地描述并发，而程序不能；
进程是由程序和数据、进程控制块、PCB、三部分组成的；
进程具有创建其他进程的功能，而程序没有
同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程

进程的特征

结构性：由进程段、数据段、进程控制块三部分组成；
动态性：进程是程序的执行过程；
并发性：多个进程可同存于内存中，能在一段时间内同时运行；
独立性：独立运行的基本单位，独立获得资源和调度的基本单位；
异步性：各进程按各自独立的不可预知的速度向前推进

进程的状态转换

进程的三个基本状态

进程在生命消亡前处于且仅处于三种基本状态之一。（就绪，运行，阻塞)

就绪状态(Ready)

存在于处理机调度队列中的所有进程，它们已经准备就绪，一旦得到CPU，就立即可以运行。这些进程所处的状态为就绪状态。

就绪队列：处于就绪状态的进程按一定的策略排队，同一时刻可有多个就绪队列。

运行状态(Running)

正在运行的进程所处的状态为运行状态。

单处理机系统只有一个进程处于该状态。

多处理机系统有多个进程处于运行状态。

等待/睡眠/阻塞状态(Wait/Blocked)

若一进程正在等待某一事件发生（如等待输入输出工作完成），这时，即使给它CPU，它也无法运行，称该进程处于等待状态（阻塞、睡眠、封锁状态）。

阻塞队列：根据阻塞原因可以设置多个队列。

新建状态、完成/终止/结束状态

运行、就绪、阻塞是进程的三个基本状态，而操作系统的规模和设计目的不同，在有些系统中，还增加了两个基本状态，新建状态、完成状态/终止状态/结束状态，这两个状态对进程管理是非常有用的。

新建状态

对应于刚刚定义的进程，还未进入就绪队列的状态，此时系统未将进程全部工作完成（如内存尚待分配等）。如果一个新用户试图登陆到分时系统，新的批处理作业被选中准备投入内存；只有进程代码和数据进入内存，才进入就绪队列。

完成状态

指进程正常，或非正常结束而终止的状态。处于该状态的进程还未从系统中消失，可能由于一些善后工作尚未完成（如记帐，未完成的输出等）。但处于完成状态的进程以后不再被调度执行。

五状态的进程状态关系转换

含有五个状态的进程状态转换关系如下：

空→新建

通常有四个事件可能导致创建一个新进程：

接着，”就绪”和”进程优先数”会被写入。

新建→就绪

操作系统接纳一个进程时，将新建状态修改为就绪状态。

就绪→运行

从就绪队列选择一个进程占用处理机,将就绪态改为运行态

运行→就绪

通常原因是正在运行进程时间片到，从运行态进入就绪态

运行→阻塞

若当前进程所请求事件，或条件未能得到满足，则进入阻塞态。由运行进入阻塞态原因可能很多

阻塞→就绪

系统内发生事件时，根据事件原因查找阻塞队列中的进程，查到，将阻塞态转换为就绪态。

运行→完成

任务执行完成，或由于其它原因无法继续运行，系统将当前进程从运行态转变为完成状态。

系统设置多少状态与系统对进程管理方式有关，也与系统资源利用有关，但要注意，系统中设置过多状态会造成系统参数和状态转换过程增加。

进程在生存期间，可以多次地从一个状态转换到另一个状态，即多次地处于运行状态、就绪状态、阻塞状态，反映了并发程序“走走停停”的运行轨迹。进程不断地从一个状态转换到另一个状态是有条件，或原因的。这些状态随着进程的执行和外界条件发生变化而转换。事实上，进程的状态转换是一个非常复杂的过程。从一个状态到另一个状态的转换除了不同的控制过程，有时还要借助于硬件才能完成。

进程的挂起状态

三个基本状态提供了构造进程活动和模型的系统方法，并指导操作系统设计与实现。但这种系统不充分；

一方面，处理机、内存等系统硬件资源的利用率得不到充分发挥。

另一方面，处在活动空间进程可能由于某原因暂时静止下来，不处于活动，但也不从系统中彻底退出，这就导致三种状态模型扩充，引入挂起状态。

挂起状态是为了解决内存不够的问题，进程被挂起后，就转移到了外存中，挂起是一种被动的行为。

新建→静止就绪

创建一个新进程可以进入静止就绪队列。系统初始执行期间，操作系统倾向建立更多就绪进程维护大量未被阻塞进程。这样使以后新进程由于主存空间不足而无法进入，这时就使用新建 →静止就绪。

静止就绪→活动就绪

若主存中没有就绪进程，一般操作系统需要调入一个进程。而当处于静止就绪状态的进程的优先级高于就绪进程的优先级时，操作系统则往往将处于静止就绪进程通过激活而将其转换为就绪状态。

活动就绪→静止就绪

通常，操作系统倾向挂起阻塞态进程。但有两种情况需要这种转换；一是得到主存更大空间唯一方法是挂起一个就绪进程；二是如果能够确定处于高优先级阻塞状态进程可以很快进入就绪状态。

静止阻塞→静止就绪

同基本状态转换一样，如果等待的事件发生了，则将处于静止阻塞的进程修改为静止就绪状态。

活动阻塞→静止阻塞

若当前系统中没有就绪态进程，就将处于阻塞态进程至少挂起一个，而进入静止阻塞状态，为没有被阻塞的进程让出主存空间。

若操作系统确定当前正在运行进程，或就绪态进程为维护基本性能要求而需要更大内存空间，则既使存在可运行状态就绪进程也可能出现这样状态转换而被挂起进入静止阻塞。

静止阻塞→活动阻塞

这种情况较少发生。如果一个进程处于阻塞，又不在主存,调入它进入主存似乎意义不大。但运行进程执行完，发现静止阻塞队列存在优先级较高者时.

各种状态→完成

在正常情况下，一个运行进程正常，或非正常结束，都进入完成状态。但如表5.2所列出进程终止事件，如果父进程终止，或被创建它的进程终止，则一个进程可以在任何状态下终止而进入完成状态。

进程控制块(Process Control Block)

•为了描述一个进程和其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，采用了一个与进程相联系的数据结构，称为进程控制块（**PCB）。**

•PCB**是OS中最重要的记录型数据结构。**

PCB 作用

作用是将一个不能独立运行的程序变成一个可以独立运行的基本单位，一个能与其他进程并发执行的进程。
OS利用PCB来对并发执行的进程进行控制和管理，PCB是OS感知进程存在的唯一标志。
进程与PCB是一一对应的。
PCB随进程创建而建立，随进程结束而回收。
PCB应常驻内存。

PCB的内容

有下列信息

进程描述信息
- 进程标识符(process ID),唯一，通常是一个整数。
- 进程名:通常基于可执行文件名(不唯一)
- 用户标识符(user ID):进程组关系
进程控制信息
- 当前状态
- 优先级(priority)
- 代码的执行入口地址
- 程序的外存地址
- 运行统计信息(执行时间、页面调度)
- 进程间同步和通信；阻塞原因
- 进程的队列指针
- 进程的消息队列指针
所拥有的资源和使用情况
- 虚拟地址空间的现状
- 打开文件列表
CPU 现场保护信息
- 寄存器值（通用、程序计数器PC、状态字PSW、地址包括栈指针）
- 指向赋予该进程的段/页表的指针。

进程控制

进程控制指对系统中的所有进程实施管理。

如：

创建一个新进程；
终止一个已完成的进程；
终止一个因出现某事件而使其无法运行下去的进程；
进程运行中状态的转换

进程控制一般由OS的内核来实现。

OS的内核

通常将OS中一些与硬件紧密相关的模块（如：中断处理程序；各种常用设备的驱动程序）以及运行频率较高的模块（时钟管理、进程调度以及许多模块公用的一些基本操作）都安排在紧靠硬件的软件层次中，并使它们常驻内存，以提高OS的运行效率，并对它们加以特殊的保护。这部分就是OS的内核。

原语

原语：由多条指令组成，是一种特殊的系统功能调用，它可以完成一个特定的功能。

原语的特点：

执行时不可中断
不可并发
在管态下执行，常驻内存

常用的进程控制原语
- 创建原语 Create
- 终止原语Destory
- 阻塞原语Block，唤醒原语Wakeup
- 挂起原语Suspend、激活原语Active

进程创建

1.申请空白PCB

2.为新进程分配资源如内存

3.初始化进程控制块

4.将新进程插入就绪队列

void Create(n,S0,P0,M0,R0,acc) {     
    i=getinternal_name(n);   
    id(i)=n;
    priority(i)=P0;    
    cpupstate(i)=S0; 
    main_store(i)=M0;  
    resources(i)=R0; 
    status(i)=“readys”;  
    sdata(i)=RL; 
    parent(i)=*;  
    progeny(i)=NULL; 
    insert(progeny(*),i); 
    set accounting data;  
    insert(RL,i);    
}

进程终止

根据被终止进程的标识符，从PCB集合中检索出该进程的PCB；
若被终止进程处于执行状态，应立即终止执行，并置调度标志为真，调度其他进程；
结束该进程所有子孙进程的执行，以防止成为不可控进程；

将进程所拥有的资源交给父进程或系统进程；释放PCB 。

void destroy(n) { 
    sched=false;
    i=getinternal name(n);
    kill(i);
    if sched then scheduler;
}

Void kill(i){
    if status(i)=“executing” then{
        stop(i);   sched=true;
    }
   remove(sdata(i),i);
   for all s∈progeny(i)
       do kill(s);
   for all r∈(main store(i)∪resources(i)) do     //资源归还给父进程
       if owned(r) then insert(avail(semaphore(r)),data(r));
   for all r∈created resources(i) do             //资源归还给系统
       remove resource descriptor(r);
   remove PCB(i);}

进程的阻塞

阻塞：当一个进程所期待的某一事件尚未出现时，该进程调用阻塞原语将自己阻塞。

进程阻塞是进程自身的一种主动行为。

步骤如下：

1.停止运行
2.转变状态
3.插入相应事件队列

4.重新调度

void block(n)
{   i=getinternal name(n);
     stop(i);
     status(i)=“blockeda”;
     insert(WL(r),i);
     scheduler;
}

进程的唤醒

唤醒：处于阻塞状态的进程是绝不可能叫醒它自己的，必须由它的合作进程用唤醒原语唤醒它。