第四章 进程

4.1 进程概念

进程：在批处理系统中指的是作业，在分时系统中指的是用户程序或者任务，在本篇文章中，使用的名词作业和进程，基本可互换

近代操作系统多为并发执行，具有许多新的特征，引入并发执行的目的是为了提高资源利用率

1、顺序与并发

顺序环境

顺序环境计算机系统只有一个程序在运行，该程序独占系统中所有资源，其执行不受外界影响

顺序执行的特点

顺序性：按照程序结构所指定的次序（可能有分支或循环）

封闭性：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定

可再现性：初始条件相同则结果相同。如：可通过空指令控制时间关系。

并发环境

一定时间内，物理机器上有两个或两个以上的程序同处于开始运行但尚未结束的状态，并且次序不是事先确定的。

并发执行

间断(异步)性：“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系；

失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。

失去可再现性：失去封闭性 －>失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征

顺序与并发总结

顺序:上一个开始执行的任务完成后，当前任务才能开始执行

并发:无论上一个开始执行的任务是否完成，当前任务都可以开始执行

(也就是说，AB顺序执行的话，A一定会比B先完成，而并发执行则不一定。)

串行与并行总结

串行:有一个任务执行单元，从物理上就只能一个任务、一个任务地执行

并行:有多个任务执行单元，从物理上就可以多个任务─起执行

并发的关键是你有处理多个任务的能力，不一定要同时。
并行的关键是你有同时处理多个任务的能力。

2、进程与程序

1️⃣ 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。

2️⃣ 进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。

3️⃣ 进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。

4️⃣ 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序

3、进程的特征

结构特征：进程实体=程序段+相关的数据段+PCB

动态性：进程的实质是进程实体的一次执行过程，因此动态性是进程的最基本的特征。

并发性: 多个进程实体同存在于内存中，且能在一段时间内同时运行。是最重要的特征。

独立性：指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。

异步性: 进程按各自独立的、不可预知的速度向前推进。

4、进程的类型

系统中主要有两大类进程

1、系统进程：系统进程能管理和控制资源

2、用户进程：执行用户程序的进程

区别

1️⃣ 资源的使用：系统进程被分配一个初始的资源集合，这些资源可以为它独占，也能以最高优先权的资格使用。用户进程通过系统服务请求的手段竞争使用系统资源；

2️⃣ I/O操作：用户进程不能直接做I/O操作，而系统进程可以做显式的、直接的I/O操作。

3️⃣ CPU工作状态：系统进程在管态下活动，而用户进程则在用户态（目态）下活动。

5、进程状态

进程在执行的时候会改变状态，每个进程可能处于以下几个状态：

⏳ 五状态模型

新建new：在创建进程

OS 已完成为创建一进程所必要的工作

已构造了进程标识符;
已创建了管理进程所需的表格;

还没有允许执行该进程：因为资源有限

就绪ready：进程等待分配处理器,已经获得了除处理器以外的所有资源

存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到CPU，就立即可以运行（有多个进程处于此状态）

时间片用完处于就绪状态

运行running：指令在执行

当进程由调度/分派程序分派后，得到CPU控制权，它的程序正在运行（在系统中，总只有一个进程处于此状态）

(阻塞)等待waiting：进程等待某些事件发生

进程正在等待某个事件的发生（如等待I/O的完成），而暂停执行

即使给它CPU时间，它也无法执行

终止terminated：进程执行完毕

🏷注意区分就绪状态和阻塞状态：关键在于分配给该进程处理器时，能否立即执行，能的话处于就绪状态；否则处理阻塞状态。
而且执行状态只能由就绪状态转换，而无法从阻塞状态直接转换

状态转换

就绪状态–>执行状态：一个进程被进程调度程序选中

执行状态–>阻塞状态：请求并等待某个事件发生

执行状态–>就绪状态：时间片用完或在抢占式调度中有更高优先级的进程变为就绪状态

阻塞状态–>就绪状态：进程因为等待的某个条件发生而被唤醒

⏳ 七状态模型

引入了挂起:

1️⃣ 终端用户的需要：当终端用户在自己的程序运行期间，发现有可疑问题时，往往希望暂时使自己的进程静止下来,以便研究其执行情况或对程序进行修改;

2️⃣ 父进程的需要：父进程常常希望考察和修改子进程，或者需协调各子进程间的活动，要挂起自己的子进程;

3️⃣ 操作系统的需要：操作系统有时需要挂起某些进程，检查运行中资源的使用情况及进行记帐，以便改善系统的运行性能。

4️⃣ 对换的需要：为了缓和内存紧张的情况，将内存中处于阻塞状态的进程换至外存上。

5️⃣ 负荷调节的需要：当实时系统中的工作负荷较重，可能影响到对实时任务的控制时，可由系统把一些不重要或不紧迫的进程挂起，以保证系统仍然能正常运行。

6、进程控制块(PCB)

PCB (Process Control Block):一个专门的数据结构，系统用它来记录进程的外部特征，描述进程的运动变化过程

PCB是进程管理和控制的最重要的数据结构，在创建进程时，建立PCB，并伴随进程运行的全过程，直到进程撤消而撤消。

PCB是系统感知进程存在的唯一标志,进程与PCB是一一对应的

PCB经常被系统访问，如，调度程序、资源分配程序、中断处理程序等，所以PCB应常驻内存。

包含以下信息：

进程状态、程序计数器、CPU寄存器、CPU调度信息、内存管理信息、计账信息、I/O状态信息

为了管理的方便，系统将相同状态的进程组成一个队列，如就绪进程队列，等待进程则要根据等待的事件组成多个等待队列，如等待打印机队列、等待磁盘I/O完成队列等等。

当前队列指针 next:登记与本进程处于同一队列的下一个进程的PCB的地址

PCB通过表来进行组织，PCB表的个数就决定了系统中最多可同时存在的进程个数，成为系统的并发度。组织方式包括：链接方式与索引方式

4.2 进程调度

多道程序设计的目的是无论何时都有进程进行，可以最大化CPU利用率；分时系统的目的是在进程之间快速切换CPU，以便用户在程序运行时能与其交互。为了这些目的，进程调度器选择一个可用进程到CPU中进行

1、调度队列

作业队列 - 在系统中的所有进程的集合

就绪队列 - 在主内存中的，就绪并等待执行的所有进程的集合

设备队列 - 等待某一I/O设备的进程队列

2、调度程序

调度分为三种：长程调度、中程调度与短程调度

长程调度（或作业调度）- 选择可以进入就绪队列的进程(从外存进内存)

速度较慢

长程调度控制了多道程序的“道”

短程调度（或CPU调度）- 选择可被下一个执行并分配CPU的进程

速度较快，切换频率高

中程调度-为了缓和内存紧张的情况，将内存中处于阻塞状态的进程换至外存上（挂起），降低多道程序的度。当这些进程重新具备运行条件时，再从外存上调入内存。这一方案称为交换

3、上下文切换

当CPU切换至另一个进程时，系统必须保存旧进程状态并为新进程调入所保留的状态，上下文切换的时间开销较重；在切换时，系统没有做有用的工作， 时间取决于硬件的支持

具体的操作

当发生上下文切换时，内核CPU会将旧进程的上下文保存在PCB中，并加载计划进行的新进程的上下文

4.3 进程上的操作

1、进程创建process creation

进程何时创建？

作业调度：批处理系统中，作业调度程序调度到某个作业以后，就把这个作业装入内存，并分配必要的资源,创建进程，插入就绪队列。

用户登录：在分时系统中，用户在终端键入登录命令后，若是合法用户，系统建立一个进程，并插入就绪队列。

父进程创建子进程，如此轮流创建下去，构成一个进程树

资源共享

三种方式

1、父进程子进程共享所有的资源

2、子进程共享父进程资源的子集

3、父子进程无共享

当进程创建新进程时，可能有两种执行可能：

父进程与子进程并发执行

父进程等待，直到子进程终止

新进程的地址空间也有两种可能

子进程是父进程的复制品，具有和父进程一样的程序和数据

子进程加载另一个新程序

进程创建的过程

1️⃣ 申请空白的PCB：为新进程分配唯一的数字标识符，并从PCB集合中索取一个空白的PCB。

2️⃣ 为新建立的进程分配资源：为新进程的程序和数据，以及用户栈分配必要的内存空间

3️⃣ 初始化程序控制块

初始化标识符信息。将系统中分配的标识符、父进程标识符填入新PCB中。

初始化处理机状态信息。是程序计数器指向程序的入口地址，栈指针指向栈顶。

初始化处理机控制信息。将进程的状态设置为就绪状态或静止就绪状态。

4️⃣ 将新进程插入就绪队列。

UNIX例子

fork()：系统调用创建新进程

execlp()：系统调用用一个新程序替代进程的内存空间

#include<stdio.h>
#include<unistd.h>
void main(int argc, char *argv[])
{ int pid;pid = fork(); /*fork another process*/if (pid < 0) {/* error occurred */fprintf(stderr, “Fork Failed”); exit(-1); }else if (pid == 0) { /* child process */execlp(“/bin/ls”,”ls”,NULL);}  else {   /* parent process */   wait(NULL);printf(“Child Complete”);exit(0);}
} 

pid=fork()： 从系统调用fork返回时，CPU在父进程中时，pid值为所创建子进程的进程号大于0，若在子进程中时，pid的值为零。

2、进程终止process termination

进程调用：当进程完成执行最后语句并且通过系统调用exit()请求操作系统删除自身时，进程终止。此时，进程可以返回状态值(通常为整数)到父进程(通过系统调用exit())。所有进程资源会被系统释放

父进程可终止子进程的执行

子进程使用了超过它所分配的资源

赋予子进程的任务不再需要

父进程终止

僵尸进程：当进程已经终止，但是其父进程尚未调用wait()

孤儿进程：父进程没有调用wait()就终止，其子进程成为孤儿进程

3、进程阻塞process blocking

引起进程阻塞和唤醒的事件：

一个处在运行状态的进程，因等待某个事件的发生（如等待打印机、同步事件等）而不能继续运行时，将调用阻塞原语，把进程置为阻塞状态，并转进程调度程序（等于让出处理机）。

调用进程阻塞操作是在进程处于运行状态下执行的。它的执行将引起等待某事件的队列的改变

4、进程唤醒

当进程所等待的事件发生时，该进程将被唤醒(由进程唤醒操作完成)。

唤醒一个进程有两种方法：由系统进程唤醒、由事件发生进程唤醒

4.4 协同进程Cooperating Processes

独立进程不会影响另一个进程的执行或被另一个进程执行影响

协同进程可能影响另一个进程的执行或被另一个进程执行影响

进程协同的优点

Information sharing 信息共享
Computation speed-up 加速运算
Modularity 模块化
Convenience 方便

4.5 进程间通信Interprocess Communication (IPC)

通常有两种方式：共享内存与消息传递

1、共享存储

使用共享存储模型的进程间通信要建立共享存储区，进程通过读写共享存储区来交换信息，由通信进程来确定交换的数据和位置，不受操作系统的控制

2、消息传递

若P与Q需要通信，需要建立通信连接与通过send/receive交换信息。

通信连接的实现有物理的：如共享存储和硬件总线；有逻辑的：如逻辑特性

消息传递有两种方式：直接通信与间接通信

直接通信

进程必须显式的命名

send(P,message)：向进程P发信息

receive(Q,message)：从进程Q收消息

间接通信

消息导向至信箱并从信箱接收（被视作端口port）

每一个信箱有一个唯一的id；仅当共享一个信箱时进程才能通信

Primitives are defined as:

​ send(A, message) – send a message to mailbox A

​ receive(A, message) – receive a message from mailbox A

mailbox A

进程创建的邮箱是私有的，操作系统创建的邮箱是共享的

操作

创建新的信箱

通过信箱发送和接收消息

销毁信箱

邮箱共享时谁得到信息？

解决方案：允许一个连接最多同2个进程相关只允许一个时刻有一个进程执行接受操作；允许系统任意选择接收者。发送者被通知谁是接收者

3、同步Synchronization

消息传递要么是阻塞的，要么是非阻塞的。

阻塞的消息传递是同步的，发送者会等待消息被接收，接收者会等待消息到达可用

非阻塞的消息传递就是异步的发送者会一直发送消息不必等待，接收者同样也可以不必等待

4、缓冲Buffering

不管通信时直接的还是间接的，通信进程交换的信息总是驻留在临时队列中。队列实现有三个方法：

零容忍：发送者必须等待接收者

有限容量：n个消有限长度，若连接满了发送者必须等待

无限容量：无限长度，发送者从不等待

5、消息传递的例子

Match

即使是系统调用也是通过消息传递实现的

在创建一个任务时也创建了两个特殊邮箱：内核邮箱kernel mailbox与通知邮箱notify mailbox。内核通过内核邮箱与任务通信，将事件发生的通知发送到通知邮箱。

消息传递只需要三个系统调用：msg_send(), msg_receive(), msg_rpc()//远程调用

系统调用port_allocate()创建新邮箱，并为消息队列分配空间，最大长度位8个消息

Windows XP

XP 使用两种消息传递技术：

1，对于少量信息：使用端口的消息队列，消息的最大长度为256字节，简单。

2，对于大量信息：使用section object,即建立一块共享内存。