进程

为了提高资源利用率和系统吞吐量，通常采用多道程序技术，将多个程序同时装进内存，并使之并发运行，此时作为资源分配和独立运行的基本单位都是进程。

程序并发执行时的特征

间断性。程序在并发时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使这些并发成执行的程序之间形成了相互制约的关系。相互制约将导致并发程序具有“执行——暂停——执行”这种间断性的活动规律
失去封闭性。
不可再现性

进程的描述

为了使参与并发执行的每个程序(含数据)都能独立地运行，操作系统中必须为止配置一个专门的数据结构，称为进程控制块(Process Control Block, PCB)。系统利用PCB来描述进程的基本情况和活动过程，进而控制和管理进程。

一般情况下，我们把进程实体就简称为进程，例如，所谓创建进程，实质上是创建进程实体中的PCB；而撤销进程，实质上是撤销进程的PCB。

较为典型的进程定义：

进程是程序的一次执行
进程是一个程序及其数据在处理机上顺序执行时所发生的活动
进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

进程的特征

动态性。进程的实质是进程实体的执行过程，因此，动态性是进程的最基本特征。动态性还表现在“它由创建而产生，由调度而执行，由撤销而消亡”，可见进程实体具有一定的生命周期。
并发性。是指多个进程实体同存于内存中，且能在一段时间内同时运行。
独立性。实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行
异步性。是指进程是按异步方式运行的，即按各自独立的、不可预知

进程的基本状态及转换

由于多个进程在并发时共享系统资源，致使它们在运行过程中呈现间断性的运行规律，所以进程在其生命周期内可能具有多种状态。一般而言，每一个进程至少应处以下三种基本状态之一

就绪(Ready)状态。指这些进程已处于准备好运行的状态，即进程已分配除CPU意外的所有必要资源后，只要再获得CPU便可立即执行。
执行(Running)状态。指进程以获得CPU，其程序正在执行的状态。
阻塞(Block)状态。这是指正在执行的进程由于发生某事件(如I/O请求、申请缓冲区失败等)暂时无法继续执行的状态，亦即进程的执行收到阻塞。

三种基本状态转换

创建状态和终止状态

为了满足进程控制块对数据及操作的完整性要求以及增强管理的灵活性，通常在系统中又为进程引入两种常见的状态：创建状态和终止状态。

创建状态
如果因为资源不足等情况，创建该进程的资源不能地到满足，如系统无足够的内存使进程无法装入其中，此时创建工作尚未完成，进程不能被调度运行，于是把此时进程所在的状态称为创建状态
终止状态
进程的终止也要分两个步骤：首先是等待操作系统进行善后处理，最后将其PCB清零，并将PCB空间返还给系统。当一个进程被各种情况终止了，它将进入终止状态。进入终止状态的进程以后不能再执行，但在操作系统中依然保留一个记录，保存状态码和一些计时统计数据，供其他进程收集，一旦其他进程完成了对其信息的提取之后，操作系统将删除该进程，将PCB清零并将该空白的PCB返还给操作系统。

进程五种基本状态及转换

挂起操作和进程状态的转换

除了三种基本状态外，还引入了一个对进程重要的操作——挂起操作。当该操作作用于某个进程时，该进程将被挂起，意味着此时进程处于静止状态。如果进程正在执行，它将暂停执行。若原本处于就绪状态，则该进程此时暂不接受调度。与挂起操作对应的操作时激活操作。

引入原语操作后的三个进程状态的转换

挂起原语(suspend)
激活原语(active)

在上述两个原语操作的作用下，可能发生以下几种状态转换

活动就绪(Readya) –> 静止就绪(Readys)，当处于readya时，进程可以接受调度，但出于readys时，不再被调度执行
活动阻塞(Blockeda) –> 静止阻塞(Blockeds)，处于Blockeds状态的进程在其所期待的事件出现后，从静止阻塞(blockeds)变为静止就绪(readys)状态
静止就绪(readys) –> 活动就绪(readya)，处于readys状态的进程若用激活原语active激活后，该进程转变为readya状态
静止阻塞(blockeds) –> 活动阻塞(blockeda)，处于blockeds状态的进程若用激活原语active激活后，进程将转变为blockeda状态

引入挂起操作后五个进程状态的转换

NULL –> 创建：一个新进程产生时，该进程处于创建状态
活动 –> 活动就绪：当前系统的性能和内存容量均允许的情况下，完成对进程创建的必要操作后，将状态转换为就绪状态
创建 –> 静止就绪：当资源不足以分配给该进程时，主要是主存，系统会将进程状态转为静止就绪状态，被安置在外存，不参与调度，此时进程创建尚未完成
执行 –> 终止：当进程以任意形式终结时，该进程被转换为终止状态。

进程管理中的数据结构

OS管理资源、进程等数据结构一般分为以下四类：内存表、设备表、文件表和用于进程管理的进程表，通常进程表又被称为进程控制块PCB。

进程控制块PCB的作用

为了便于系统描述和管理进程的运行，在OS的核心为每个进程专门定义了一个数据结构——进程控制块PCB(Process Control Block)。PCB作为进程实体的一部分，记录了操作系统所需的，用于描述进程的当前情况以及管理进程运行的全部信息，是操作系统中最重要的记录型数据结构。

PCB具体作用的阐述：

作为独立运行的基本单位的标志。当一个程序(含数据)配置了PCB后，就表示它已是一个能在多道程序环境下独立运行的、合法的基本单位，也就具有取得OS服务的权利。系统是通过PCB感知进程的存在的，事实上，PCB已成为进程存在于系统中的唯一标志
能实现间断性运行方式。在多道程序环境下，程序是采用停停走走间断性的运行方式运行的。在有了PCB之后，系统将CPU现场信息保存在被中断的进程的PCB中，供该进程再次被调度执行时恢复CPU现场时使用。
提供进程管理所需要的信息。当调度程序调度到某进程运行时，该程序所需要的资源信息都需要到PCB中获取。
提供进程调度所需要的信息。PCB提供了进程处于何种状态的信息，调度需要根据该信息进行调度，比如只有处于就绪状态才能被调度。
实现与其他进程同步与通信。进程同步机制是用于实现多个进程的协调运行的，在采用信号量机制时，它要求每个进程中都设置有相应的用于同步的信号量。在PCB中还具有用于实现进程通信的区域或通信队列指针等。

进程控制块PCB的组织方式

线性方式
链接方式
索引方式

进程控制

进程控制一般是由内核中的原语来实现的。

进程的阻塞与唤醒

引起进程阻塞和唤醒的时间

向系统请求共享资源失败
等待某种操作的完成。比如等待某I/O设备完成指定的任务，该进程才能继续执行，则该进程在启动了I/O设备之后就自动进入阻塞状态了。
新数据尚未到达。对于相互合作的进程，如果一个进程需要先获得另一进程提供的数据后才能对该数据进行处理，只要其所需数据尚未到达，进程便只有阻塞。
等待新任务的到达。

进程的阻塞过程
正在执行的进程，如果发生了上述某时间，进程便通过调用阻塞原语block将自己阻塞。可见阻塞是进程自身的一种主动行为。
进入阻塞的过程

调用block –> 将PCB状态改为阻塞 –> 将PCB插入阻塞队列

进程唤醒过程
当被阻塞进程所期待的事情发生时，比如它所启动的I/O操作已完成，或其所期待的数据已经到达，则由有关进程(不如提供数据的进程)调用唤醒原语wakeup，将等待该事件的进程唤醒。
被唤醒的过程

将被阻塞的进程从等待该事件的阻塞队列中移出 –> 将PCB状态改为就绪 –> 将该PCB插入到就绪队列中

进程的挂起与激活

挂起
OS利用挂起原语suspend将指定进程或处于阻塞状态的进程挂起。

激活
利用原语active，将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，将之改为活动就绪。

进程同步

单处理机系统中的进程同步机制——硬件同步机制、信号量机制、管程机制等。

临界区

每个进程中访问临界资源的那段代码称为临界区。若能保证诸进程互斥地进入自己地临界区，便可实现诸进程对临界资源地互斥访问。
为此，每个进程进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问。

在临界区前面增加一段用于进行检查的代码称为进入区(entry section)，相应的，在临界区后面也要加上一段称为退出区(exit section)的代码。

一个访问临界资源的循环过程描述如下：

while(TRUE){
    进入区
    临界区
    退出区
    剩余区
}

所有同步机制应遵循下述四条准则

空闲让进。当无进程处于临界区时，表明资源处于空闲状态，并允许一个请求立即进入临界区。
忙则等待。当临界资源被访问时，其他试图进入临界区的进程必须等待。
有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，避免“死等”状态。
让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以避免陷入“忙等”状态。

硬件同步机制

关中断
进入锁之前关闭中断，那样就确保了只有一个进程在允许，进程无法被调度。有很多缺点：滥用关中断权利可能导致严重后果，关中断时间过长影响系统效率等。
利用Test-and-Set指令实现互斥
这是一种借助一条硬件指令——“测试并建立”指令实现互斥的方法。TS指令一般性描述如下
```
boolean TS(boolean *lock){
    Boolean old;
    old = *lock;
    *lock = TRUE;
    return old;
}
```
这条指令的执行过程是不可分割的，即是一条原语。其中lock有两种状态，当为FALSE时表示该资源空闲，当为TRUE时，表示该资源正在被使用

利用TS指令实现互斥的循环进程结构可描述如下

do {
    // ...
    while TS(&lock); // 进入区
    critical section; // 临界区
    lock := FALSE; // 退出区
    remainder section; // 剩余区
}while(TRUE)

利用swap指令实现进程互斥

对换指令

void swap(boolean *a, boolean *b){
    boolean temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

用对换指令可以简单有效地实现互斥，方法是为每个临界资源设置一个全局的布尔变量lock，其初值为false，在每个进程中再利用一个局部布尔变量key。利用swap指令实现进程互斥的循环进程可描述如下：

do{
    key=TRUE;
    do{
        swap(&lock,&key);
    }while(key!=FALSE);
    // 临界区操作;
    lock=FALSE;
    // ...
} while(TRUE);

信号量机制

整形信号量

整形S仅能通过两个标准的原子操作wait(S)和signal(S)来访问

wait(S){
    while(S<=0);
    S--;
}
signal(S){
    S++;
}

记录型信号量

在整型信号量机制中的wait操作，只要是信号量S<=0,就会不断测试，因此该机制并未遵循“让权等待”的准则，处于“忙等”状态。

记录型信号量机制采取了“让权等待”的策略，会出现多个进程等待访问一个临界资源的情况，为此信号量机制除了用于代表数目的整型变量value外，还应增加一个进程链表指针list，用于链接上述的所有等待进程

typedef struct{
    int value;
    struct process_controller_block *list;
}semaphore;

相应的，wait(S)和signal(S)操作可描述如下:

wait(semaphore *S){
    S->value--;
    if(S->value<0) block(S->list);
}

signal(semaphore *S){
    S->value++;
    if(S->value<=0) wakeup(S->list);
}

S->value的初值表示系统中某类资源的数目，对于每次wait操作意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源减少一个，因此S->value–;当S->value<0时说明该类资源已分配晚比。
因此进程应调用block原语进行自我阻塞，放弃处理机，并进入S->list中。
signal操作表示释放一个单位的资源，将S->value++，并waitup第一个list中阻塞的进程。

AND型信号量
AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。

对若干个临界资源的分配采取原子操作方式：要么把它请求的资源全部分配到进程，要么一个也不分配。

为此，在wait操作中增加一个“AND”条件，称为AND同步，或称为同时wait操作，S(Simultaneous wait)定义如下

Swait(S1,S2,...,Sn){
    while(TRUE){
        if(Si>=1&&...&&Sn>=1){
            for(i=1;i<=n;i++) Si--;
            break;
        }else{
            // 进入等待队列
        }
    }
}

Ssignal(S1,S2,...,Sn){
    while(TRUE){
        for(i=1;i<=n;i++){
            Si++;
            // 将所有在等待队列的Si的进程移除
        }
    }
}

信号量集

对AND信号量机制的扩充，对进所申请的所有资源以及每类资源不同的资源需求量，再一次P、V原语操作中完成申请或释放。进程对信号量Si的测试值不再是1，而是该资源的分配下限指ti，即要求Si>=ti，否则不予分配。进程对该资源的需求值为di，表示资源占用量，进行Si:=Si-di操作。由此形成一般化的“信号量集”机制，对应的Swait、Ssignal格式为：

Si：表示资源总量
ti：分配资源下限值
di：分配多少

Swait(S1,t1,d1,...,Sn,tn,dn);
Ssignal(S1,t1,...,Sn,tn);

一般“信号量集”还有下面几种特殊情况

Swait(S,d,d)，此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源少于d时，不与分配
Swait(S,1,1)，此时信号量退化为一般信号量S(S>1时)或互斥信号量S(S=1)
Swait(S,1,0)，当S>=1时，允许多个进程进入某特定区，当S变为0后，将阻止任何进程进入特定区，相当于一个可控的开关

管程机制

定义
代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块，称之为管程。
管程被请求和释放资源的进程所调用。
管程由四部分组成

管程的名称
局部于管程的共享数据结构说明
对该数据结构进行操作的一组过程
对局部于管程的共享数据设置初始值的语句

管程的语法描述：

// 管程名
Monitor monitor_name {
    // 共享变量说明
    share variable declarations;
    // 条件变量说明
    cond declarations;
    // 能被进程调用的过程
    public:
    // 对数据结构操作的过程
    void P1(...){...}
    void P2(...){...}
    // ....
    // 管程主体
    {
        // 初始化代码
        initialization code;
    }
}

管程包含了面向对象的思想，将表征共享资源的数据结构及其对数据结构操作的一组过程，包括同步机制，都集中并封装在一个对象内部，隐藏了实现袭击。

每次只能由一个进程请求管程的过程，从而实现了进程互斥。

应考虑的一种情况：当一个进程调用了管程，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除，而在此期间，如果该进程不释放管程，则其它进程无法进入管程，被迫长时间等待。

为此引入condition，管程中对每个条件变量都须予以说明，形式为: condition x,y；对条件变量的操作也仅为wait和signal，提供了两个操作,x.wait 和 x.signal

x.wait：当正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x的条件变化。此时其它进程可以使用该管程
x.signal：正在调用管程的进程发现x条件发生了变化，则调用x.signal，重新启动一个因为x条件被挂起或阻塞的进程，如果有多个这样的进程则挑其中一个，如果没有则继续执行原进程。