重学操作系统之进程管理

未命名文件 (1).png

一、前言

进程管理作为操作系统的模块之一，其作用目的是协调资源分配并且能够独立运行。

二、进程的基本概念

在未配置OS的系统中，程序的执行方式是顺序执行，即必须在一个程序执行完成后，才允许另外一个程序执行；在多道程序环境下，则允许多个程序并发执行。也正是程序的并发执行，才导致引入进程。

2.1 程序的顺序执行

通常可以把一个应用程序分成若干个程序段，在各程序段之间，必须按照某种先后次序顺序执行，仅当前一操作（程序段）执行完后，才能执行后继操作。

程序顺序执行时的特征如下

顺序性，处理机的操作严格按照程序锁规定的顺序执行，即每一操作必须在上一个操作结束之后开始。
封闭性，程序是在封闭的环境下执行的，即程序运行时独占全机资源，资源的状态（除初始状态外）只有本程序才能改变它，程序一旦开始执行，其执行结果不受外界因素影响。
可再现性，只要程序执行时的环境和初始条件相同，当程序重复执行时，无论它是从头到尾不停顿地执行，还是走走停停地执行，都将获得相同的结果。

在程序顺序执行时的特征，为程序员检测和校正程序的错误带来了很大的方便。

2.2 程序的并发执行

程序的并发执行是指两个或两个以上的程序或程序段可在同一时间间隔内同时执行。

多个程序可以并发执行，并发执行可以提高CPU的效率和系统吞吐率。其特征如下

间断性，程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系。如计算操作必须在输入操作之后。
失去封闭性，程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，只是程序的运行失去了封闭性，这样，某程序在运行时，必然会收到其他程序的影响。如当某个程序占用了处理机资源后，另外一个程序必须等待。
不可再现性，程序在并发执行时，由于失去了封闭性，也将导致其再失去可再现性。可能由于不同的操作顺序产生不同的结果。

2.3 进程的定义与特征

由于程序并发执行时，它们失去了封闭性，间断性和不可再现性，这决定了一般的程序是不能参与并发执行的，因为程序执行的结果是不可再现的。这样，程序的运行也就失去了意义，为了能够是程序能够正确的并发，引入了进程的概念。

程序段、数据段、PCB三部分组成了进程的实体，一般情况下我们把进程实体就简称为进程。

从不同的角度，进程可以有不同的定义，比较传统典型的定义有：

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

进程的组成：

进程具有如下的特征：

进程是进程实体的运行过程，是系统进行资源分配和调度（在线程未出现之前）的一个独立单位。

2.4 进程的状态

进程执行时的间断性决定了进程可能具有多种状态。进程的三种基本状态如下。

进程另外两种状态：

进程的状态切换：

2.5 进程控制块

为了描述和控制进程的运行，系统为每个进程定义了一个数据结构，进程控制块PCB，它是进程实体的一部分，是操作系统中最重要的记录型数据结构，PCB中记录了操作系统所需的，用于描述进程当前情况以及控制进程运行的全部信息。

进程控制块的作用是使一个在多道程序环境下能独立运行的程序，成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。PCB是进程存在的唯一标识。

当创建一个进程时，就为它创建一个PCB，进程结束时又回收其PCB，进程于是随之消亡，PCB可以被操作系统中的多个模块读或修改，如被调度程序、资源分配程序、中断处理程序及监督分析程序等读或修改，因为PCB是经常被系统访问，尤其是被运行频率很高的进程及分派程序访问，故PCB应常驻内存。系统将所有的PCB组织成若干个链表（或队列），存放在操作系统中专门开辟的PCB区内。

进程控制块组成 进程控制块PCB主要包含如下信息。

进程标识符，用于唯一地标识一个进程，有内部标识符（由系统赋予的唯一一个数字，通常为进程的序号，为方便系统使用）和外部标识符（由创建者提供，可描述进程的家族关系）。
处理机的状态，当处理机被中断时，其寄存器的信息都必须保存在进程的PCB中，以便该进程重新执行时，能从断点继续执行。
进程调度信息，包括进程状态（指明进程的当前状态，作为进程调度和对换时的依据），进程优先级（用于描述进程使用处理机的优先级别，优先级高的进程应该优先获取处理机），进程调度所需的其他信息（与进程调度算法有关，如进程已等待CPU的时间总和，进程已执行的时间总和等），事件（进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因）。
进程控制信息，包括程序和数据的地址（进程的程序和数据所在的内存或外存首址，以便在调度该进程时，能从PCB中找到其程序和数据），进程同步和通信机制（实现进程同步和进程通信时必需的机制，如消息队列指针，信号量等），资源清单（除CPU以外的进程所需的全部资源以及已经分配到该进程的资源的清单），链接地址（本进程PCB所在队列中的下一个进程的PCB的首地址）。

2.6 进程的组织

在一个系统中，通常有十、数百乃至数千个PCB。为了能对它们进行有效的管理，应该用适当的方式把这些PCB组织起来。常用的组织方式如下：

链接方式，把具有同一状态的PCB，链接成一个队列，这样可以形成若干就绪队列、阻塞队列和空白队列等，优先级高的进程的PCB排在前面。

索引方式，系统根据所有进程的状态建立几张索引表，如就绪索引表，阻塞索引表等，并把各索引表在内存的首地址记录在内存的一些专用单元中，在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址。

三、进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

3.1 进程的创建

一个进程可以创建一个子进程，子进程会继承父进程所拥有的资源，如继承父进程打开的文件、分配到的缓冲区等，当子进程被撤销时，应该讲其从父进程哪里获得的资源归还给父进程，此外，撤销父进程时，也必须同时撤销其所有的子进程。

3.2 进程的终止

3.3 进程的阻塞与唤醒

3.4 进程的切换

3.5 进程控制的实现

四、进程同步

4.1 进程同步基本概念

进程同步主要是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效共享资源和相互合作，而从使程序的执行具有可再现性。在多道程序环境下，当程序并发执行时，由于资源共享和进程合作，使处于一个系统中的诸进程之间可能存在着以下两种形式的制约关系。

间接相互制约关系，同处于一个系统中的进程，通常都共享着某种系统资源，如共享CPU、I/O设备等，间接相互制约即源于这种资源共享。

2. 直接相互制约关系，这种制约主要源于进程间的合作，如A进程通过缓冲向B进程提供数据，当缓冲为空时，B阻塞，待A输入数据后，B被唤醒，缓冲满时，A阻塞，待B取出数据后，A被唤醒。

4.2 临界资源和临界区

许多硬件资源如打印机，磁带机等，都属于临界资源，诸进程应该采取互斥方式，实现对这种资源的共享。人们把在每个进程中访问临界资源的那段代码成为临界区，显然，若能保证诸进程互斥（或称间接相互制约关系）地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。

4.3 同步机制遵循的原则

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

4.4 硬件同步机制

4.4.1 中断屏蔽方法

利用开/关中断指令实现。

优点：简单、高效。
缺点：不适用于多处理机；只适合用于操作系统内核进程，不适用用户进程。（因为开/关中断指令只能运行在内核态，指令能被用户随意使用将会很危险）

4.4.2 TestAndSet 指令

TestAndSet 指令简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令，TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成，以下使用C语言描述的逻辑：

若刚开始lock是false，则TSL返回的old值为false，while 循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是true，则执行TLS后old返回的值为true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁” 相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气响成的原子操作。

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞，适用于多处理机环境。
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行 TSL指令，从而导致忙等。 4.4.3 Swap 指令

有的地方也叫Exchange指令，或简称XCHG指令。 Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑：

逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁(记录在old变量上)，再将上锁标记lock设置为true，最后检查old，如果 ld为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

优点：实现简单，无需像软件实现方法那样严格检查是否会有辑漏洞;适用于多处理机环境。
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

4.5 信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。

一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数。wait、signal原语常简称为P、V操作（来自荷兰语proberen和verhogen）。因此，做题的时候常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)。

整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。Eg：某计算机系统中有一台打印机…

记录型信号量

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

4.6 信号量的应用

信号量的值=这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）

P( S ) ——申请一个资源S，如果资源不够就阻塞等待。
V( S ) ——释放一个资源S，如果有进程在等待该资源，则唤醒一个进程。

实现进程互斥

划定临界区（如：对临界资源打印机的访问就应放在临界区）
设置互斥信号量mutex，初值为1
在进入区P(mutex)——申请资源
在退出区V(mutex)——释放资源

// 信号量机制实现互斥
semapphore mutex = 1 //初始化信号量

P1() {
...
P(mutex)
临界区代码
V(mutex)
...
}

P2() {
...
P(mutex)
临界区代码
V(mutex)
...
}

实现进程同步

必须保证“一前一后”执行的两个操作（或两句代码）
设置同步信号量S,初始为0
在“前操作”之后执行V(S)
在“后操作”之前执行P(S)

// 信号量机制实现同步
semapphore S = 0 //初始化信号量

P1() {
代码1
代码2
V(S)
代码3
}

P2() {
P(S)
代码4
代码5
代码6
}

上面代码保证代码4在代码2进行。

实现前驱关系

进程P1中有句代码S1，P2中有句代码S2，P3中有句代码S3 …… P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行：

要为每一对前驱关系各设置一个同步信号量
在“前操作”之后对相应的同步信号量执行V操作
在“后操作”之前对相应的同步信号量执行P操作

4.7 管程

为什么引入管程

信号量机制存在的问题：编写程序困难、易出错
让程序员写程序时不需要再关注复杂的PV操作

管程是一种特殊的模块，有这些部分成：

软块这组局部于管程的共享数据结构说明；
对该数据结构进行操作的一组过程；
对局部于管程的共享数据设置初始值的语句；
管程有一个名字。管程 Pascal 语言代码示例：

monitor ProducerConsumer
    integer i;
    condition c;

    procedure insert();
    begin
        // ...
    end;

    procedure remove();
    begin
        // ...
    end;
end monitor;

基本特征：局部于管程的数据只能被局部于管程的程所访问，一个进程只有通过调用管程内的过程才能进入管程访问共享数据；

五、进程同步应用

5.1 生产者-消费者问题

“生产者-消费者”问题是最著名的进程同步问题。它描述了一组生产者向一组消费者提供产品，它们共享一个缓冲池（有n个缓冲区），生产者向其中投放产品，消费者从中取得产品。

模型：

代码示例：

5.2 哲学家进餐问题

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

这里五名哲学家就是五个进程，五根筷子是需要获取的资源。可以定义互斥数组用于表示五根筷子的互斥访问，为了防止哲学家个取一根筷子出现死锁，需要添加一定的限制条件。一种方法是限制仅当哲学家左右筷子均可以用时，才拿起筷子，这里需要一个互斥量来限制获取筷子不会出现竞争。

semaphorechopstick[5]={1,1,1,1,1};
semaphoremutex=1;//互斥地取筷子
Pi(){
    //i号哲学家的进程
    while(1){
        P(mutex);
        P(chopstick[i]);//拿左
        P(chopstick[(i+1)%5]);//拿右
        V(mutex);
        吃饭…
        V(chopstick[i]);//放左
        V(chopstick[(i+1)%5]);//放右
        思考…
    }
}

5.3 读者-写者问题

一个数据对象（数据文件或记录）可被多个进程共享。其中，读者（reader）进程要求读，写者（writer）进程要求写或修改。

为了保证读写的正确性和数据对象的一致性，系统要求：当有读者进程读文件时，不允许任何写者进程写，但允许多个读者同时读；当有写者进程写时，不允许任何其它写者进程写，也不允许任何读者进程读。

semaphorerw=1; // 用于实现对共享文件的互斥访问
intcount=0; // 记录当前有几个读进程在访问文件
semaphoremutex=1; // 用于保证对count变量的互斥访问
semaphorew=1; // 用于实现“写优先”

writer(){
    while(1){
        P(w);
        P(rw);
        写文件…
        V(rw);
        V(w);
    }
}

reader(){
    while(1){
        P(w);
        P(mutex);
        if(count==0)
            P(rw);
        count++;
        V(mutex);
        V(w);
        读文件…
        P(mutex);
        count--;
        if(count==0)
            V(rw);
        V(mutex);
   }
}

六、进程通信

进程通信，是指进程之间的信息交换，进程的互斥和同步，由于只能交换很少量的信息而被归结为低级通信，目前的高级通信机制可归结为三大类

6.1 共享存储器系统

相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信，基于此，又可以分为如下两种类型：基于共享数据结构的通信方式，在这种通信中，要求诸进程共用某些数据结构，借此实现进程间的信息交换。基于共享存储区的通信方式，为了传输大量数据，在存储器中划出一块共享存储区，诸进程可通过对共享存储区中的数据的读或写来实现通信。

6.2 消息传递系统

进程间的数据交换是以格式化的消息为单位，程序员直接利用操作系统提供的一组通信命令（原语），不仅能实现大量数据的传递，而且还隐藏了通信的实现细节，使通信过程对用户是透明的，从而大幅减少通信程序编制的复杂性。

6.3. 管道通信

连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件，向管道（共享文件）提供输入的发送进程，以字符流形式将大量的数据送入管道；而接受管道输出的接受进程，则从管道中接受数据，由于发送和接受进程是利用管道进行通信的，因此叫做管道通信。管道通信需要具有三方面的协调能力：互斥（当一个进程正在对pipe执行读/写时，其他进程必须等待），同步（当写进程把一定数量的数据写入pipe，便去睡眠等待，到读进程取走数据后，再把它唤醒，当读进程读一个空pipe时，也应该睡眠等待，直到有数据写入管道，才将其唤醒），确定对方是否存在，只有确定了对方已存在时，才能进行通信。

七. 线程

7.1 线程的引入

可以把线程理解为“轻量级进程”。
线程是一个基本的CPU执行单元，也是程序执行流的最小单位。
引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件）
引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。线程则作为处理机的分配单元。

7.2 线程与进程的比较

线程称为轻型进程或进程元，在引入线程的操作系统，一个进程往往都拥有多个线程，至少有一个线程，下面从不同的方面将线程与进程进行比较。

调度

线程作为调度和分派的基本单位，而进程作为资源拥有的基本单位。同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另外一个进程中的线程时，将会引起进程切换。
并发性

不仅进程间可以并发执行，同一个进程中的多个线程之间亦可并发执行，是的操作系统具有更好的并发性，从而能更加有效地提高系统资源利用率和系统吞吐率。
拥有资源

线程一般不拥有系统资源（除少量必不可少的资源），但它可以访问其隶属的进程的资源，即一个进程的代码段，数据段以及拥有的系统资源，如已打开的文件、I/O设备等。
系统开销

在创建和撤销进程时，系统都要为之创建和回收进程控制块，分配或回收资源，操作系统付出的开销明显大于线程创建或撤销时的开销，在进程切换时，涉及到当前进程CPU环境的保存和新被调度运行进程的CPU环境的设置，而线程的切换则仅需保存和设置少量寄存器内容，不涉及存储器管理方面的操作，所以线程的切换开销远小于进程切换开销，以外，由于一个进程中的多个线程具有相同的地址空间，在同步和通信的实现上也比较容易，在一些操作系统中，线程的切换，同步和通信都无需操作系统内核的干预。

7.3 线程实现方式

用户级线程

用户级线程仅存在于用户空间中。对于线程的创建、撤销、同步和通信等，无需利用系统调用来实现，对于用户级线程的切换，通常发生在一个应用进程的诸多线程之间。线程的任务控制块都是设置在用户空间，线程所执行的操作也无需内核的帮助，因而内核完全不知道用户级线程的存在。设置了用户级线程的系统，仍可以以进程为单位进行调度，而设置的是内核支持线程，则以线程为单位进行调度。

其优点如下

线程切换不需要转换到内核空间，节省了切换开销。
调度算法可以是进程专用的，进程可以选择不同的调度算法对自己的线程进行管理和调度，而与操作系统的低级调度算法无关。
用户级线程的实现与操作系统平台无关，在所有的应用程序中都可以对其进行共享。

其缺点如下

系统调用的阻塞问题，当线程执行一个系统调用时，不仅该线程被阻塞，而且进程内的所有线程都会被阻塞，而在内核支持线程方式中，进程中的其他线程仍可以执行。
在单纯的用户级线程实现方式中，多线程应用不能利用多处理机进行多处理的优点，内核每次分配给一个进程的仅有一个CPU，因此进程中仅有一个线程能执行，在该线程放弃CPU之前，其他线程只能等待。 内核级线程

无论用户进程中的线程，还是系统进程中的线程，它们的创建、撤销和切换等也是依靠内核，在内核空间中实现。内核空间为每个内核支持线程设置了一个线程控制块，内核是根据该控制块而感知某个线程的存在，并对其加以控制。其优点如下