进程管理

进程的概念

程序执行的两种方式

顺序执行顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统。
并发执行现代操作系统多为并发执行，引入并发执行的目的是为了提高资源利用率

程序的顺序执行

一个程序独占处理机直至最终结束，它的若干操作必须按照严格的先后次序顺序地执行，这类计算过程就是程序的顺序执行过程。

顺序执行的特征

顺序性：处理机严格按照程序结构所指定的顺序执行。（可能有分支或循环）
封闭性：程序一旦开始运行就独占全部资源，计算机的状态只由该程序的控制逻辑所决定。
可再现性：程序的执行结果与程序运行的速度无关（即与时间无关）。当机器在同一数据集上重复执行同一程序，均可得到相同的结果。

程序的并发执行

指一组在逻辑上相互独立的程序或程序段在执行过程中，其执行时间在客观上相互重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的这种执行方式。

并发执行所带来的影响

失去程序的封闭性和可再现性如果一个程序的执行可以改变另一个程序的变量，那么，后者的输出就可能依赖于各程序执行的相对速度，也就失去了程序的封闭性特点。
程序与计算不再一一对应程序是指令的有序集合，是静态的概念。计算是指令序列在处理机上的执行过程，是动态的概念。在顺序执行时一个程序只能对应唯一的一个计算，而在并发执行时一个程序可以对应多个计算。
并发程序在执行期间可以相互制约例：两个打印程序A和B，程序A打印素数，程序B打印成绩表，这两个彼此独立的程序，在逻辑上没有任何关系，由于并发执行过程中共享打印机资源而出现了相互制约的关系。

为了使并发执行时不出现错误结果，必须采取某些措施来控制并发程序的执行。并且为了控制和协调各程序段执行过程中的软硬件资源的共享和竞争，必须有一个描述各程序段执行过程和共享资源的基本单位。解决方法——引入“进程”。

进程的定义

进程的定义：进程是指一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。

进程有两大类（系统中同时可有多个进程存在）：

系统进程：起着资源管理和控制的作用，或者执行操作系统核心代码的进程。
用户进程：执行用户程序的进程。

系统进程与用户进程的区别：

系统进程被分配一个初始的资源集合，这些资源可以为它独占，也能以最高优先权的资格使用。用户进程通过系统服务请求的手段竞争使用系统资源；
系统进程可以做直接的I/O操作,而用户进程不能直接做I/O操作。
系统进程在核心态（管态）下活动，而用户进程则在用户态（目态）下活动。

进程和程序的区别

进程是动态的，程序是静态的程序本身可以作为软件资源而长期存在；进程是程序的一次执行过程，有一定的生命期。
进程具有并发特征，而程序没有进程是一个能够独立运行的单位，是作为资源申请和调度单位存在的，能与其他进程并发执行；程序不能作为一个独立运行的单位而并发执行。
程序和进程没有一一对应关系通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
各个进程在并发执行过程中会产生相互制约关系因为进程是竞争资源的基本单位，从而其并发性受到系统的制约，而程序却没有。

进程和作业的区别进程——已提交完毕程序的执行过程的描述，是资源分配的基本单位作业——是用户需要计算机完成某项任务时要求计算机所作工作的集合

作业是用户向计算机提交任务的任务实体，进程则是完成用户任务的执行实体用户向计算机提交作业后，进入外存，在作业等待队列中等待执行；进程是系统分配资源的基本单位，任一进程，只要被创建，总有相应的部分存在于内存中。
一个作业可由多个进程组成，且至少必须由一个进程组成，但反过来不成立。
作业的概念主要在批处理系统中，在分时系统中没有作业的概念，而进程的概念则是用在几乎所有的多道系统中。

进程的特征

并发性任何进程都可以同其他进程一起向前推进。
动态性进程对应程序的执行，进程是动态产生，动态消亡的，进程在其生命周期内，在三种基本状态之间转换。
调度性进程是（CPU调度）和资源分配的一个独立单位。
交互性指进程在执行过程中可能与其它进程产生直接或间接的关系。
异步性每个进程都以其相对独立的不可预知的速度向前推进。
结构性进程的组成：程序+数据+PCB

进程的组成

进程通常由程序、数据集合和进程控制块PCB三部分组成。

进程控制块PCB（Process Control Block）

进程控制块：是用来存放进程的管理和控制信息的专门的数据结构（PCB是系统感知进程存在的唯一实体，进程与PCB是一一对应的）。

创建一个进程时，系统首先创建其PCB。然后OS才能根据PCB 中信息对进程实施有效的管理和控制。当一个进程完成其功能之后，系统则释放PCB，进程也随之消亡。

PCB的基本内容

描述信息：进程标识、用户标识、家族关系
控制信息：进程当前状态、优先级、开始地址、通信信息
资源管理信息：I/O设备号、占用内存大小、各种指针
CPU现场保护结构

进程上下文

进程上下文是对进程执行活动全过程的静态描述，包括PCB结构、与执行该进程有关的各种寄存器的值、正文集（程序段在经过编译之后形成的机器指令代码集）、数据集及各种堆栈值。

进程上下文可按一定的执行层次组合

用户级上下文
寄存器级上下文
系统级上下文

进程空间

任何一个进程都有一个自己的地址空间，该空间称为进程空间或虚空间。程序的执行都在进程空间内进行。用户程序、进程的各种控制表格等都按一定的结构排列在进程空间中。

进程空间的大小只与处理机的位数有关。即： $进程空间的大小＝2^n$

UNIX、Linux等操作系统中，进程空间又分为：

用户空间：用户程序执行的空间
系统空间：操作系统的内核程序执行的空间（为了防止用户程序访问系统空间，系统通过程序状态寄存器等设置不同的执行模式（用户模式/系统模式）来进行保护）

进程状态及其转换

进程的基本状态

进程的三种基本状态

就绪状态
运行状态
等待状态（又称阻塞、挂起、睡眠）

就绪状态（Ready)

处于就绪状态的进程已经得到除CPU之外的其他资源，只要由调度得到处理机，便可立即投入执行
可以有多个进程处于就绪状态

运行状态(Running）

进程调度程序从就绪队列中选择一个进程分配给它CPU控制权，该进程所处的状态为运行状态
在单CPU系统中，总只有一个进程处于运行状态

等待状态（阻塞状态：Wait/Blocked)

进程因等待某个事件的发生（如等待I/O的完成），而暂停执行，则称该进程处于等待状态（这时，即使给它CPU时间，它也无法执行）
可以有多个进程处于等待状态

进程状态转换

进程控制

进程控制的手段：由操作系统中的原语来实现。

进程创建
进程撤消
进程阻塞
进程唤醒

原语(Primitive)：是在系统态下执行的完成系统特定功能的程序段。

特点：原语是一个不可分割的基本单位，原语操作具有原子性，既在执行过程中不允许被中断，且不能并发执行。
原语是一种特殊的系统调用，其作用是为了实现进程的控制和通信。

原语与系统调用比较

调用形式（相同点）：均使用访管指令实现
中断性：系统调用在运行中可被中断
并发性：原语不允许并发执行
使用关系：
- 原语→系统进程或系统服务
- 系统调用→系统程序→用户应用程序

常用原语

进程控制：
- 进程创建原语
- 进程撤消原语
- 进程阻塞原语
- 进程唤醒原语
进程同步互斥：
- P原语
- V原语

进程创建

进程创建原语的实现过程进程创建原语的形式：create(name,priority,start-addr)

name 为被创建进程的标识符
priority为进程优先级
start-addr为某程序的开始地址

进程创建原语的功能：创建一个具有指定标识符的进程，建立进程的PCB结构。

进程创建有两种情况： ①批处理中，由操作系统的作业调度程序为用户作业创建相应的进程以完成用户所要求的功能。 ②由父进程创建，在层次结构的系统中，父进程创建子进程以完成并发工作。

进程撤销

进程撤消原语的实现过程进程撤消原语的形式：kill (或exit)。该命令没有参数，其执行结果也无返回信息。

进程撤消原语的功能：撤消当前运行的进程，将该进程的PCB结构归还给PCB资源池，所占用的资源归还给父进程，从总链队列中摘除它，然后转进程调度程序。

进程撤消有三种情况： ①该进程已完成所要求的功能而正常终止。 ②由于某种错误导致非正常终止。 ③祖先进程要求撤销某个子进程。撤销原语一般由其父进程或祖先进程发出，不会自己撤销自己。

进程阻塞（挂起、等待）

进程阻塞原语的实现过程进程阻塞原语的形式（UNIX系统）：sleep(chan,pri) 其中：chan 进程挂起（睡眠）的原因；pri 进程的优先级。

一般调用形式：susp(chan) 其中：chan 进程等待的原因

进程阻塞原语的功能：中止调用进程的执行，并加入到等待chan的等待队列中；最后使控制转向进程调度。

进程唤醒

进程唤醒原语的实现过程进程唤醒原语的形式：wakeup(chan) 其中：chan 唤醒进程阻塞的原因。

进程唤醒原语的功能：当进程等待的事件发生时，唤醒等待该事件的所有进程或等待该事件的首进程。

进程的相互作用

进程间的制约关系有两个：

间接制约：资源共享——独占分配到的部分或全部共享资源，“互斥”问题
直接制约：进程合作——等待来自其他进程的信息，“同步”问题

进程互斥

临界资源（Critical Resource）：一次仅允许一个进程使用的资源称为临界资源。临界区（ Critical Section）：每个进程中访问临界资源的那段程序段称为临界区（临界段），简称CS区。

互斥的定义：不允许两个或两个以上的共享临界资源的并发进程同时进入临界区称为互斥。

进入临界区的准则： (1)每次至多有一个进程处于临界区；（忙则等待） (2)对要去进入临界区的进程，应在有限时间内使之进入，以免陷入“死等”。（有限等待） (3)若进程不能进入自己的临界区时，则应让出CPU，避免进程出现“忙等”现象。（让权等待） (4)当无进程处于临界区时，必须让一个要求进入临界区的进程立即进入，以有效地利用临界资源。（空闲让进）

互斥的加锁实现解决进程互斥的最简单的办法是加锁。在系统中为每个临界资源设置一个锁位：

0 /true：表示资源可用（锁打开）
1 /false：表示资源不可用（锁关闭）

这样当一个进程使用某个临界资源必须完成下列操作： (1)考察锁位的值：若原来的值是为“0”，将锁位置为“1”（占用该资源）；若原来值是为“1”，(该资源已被别人占用)，则转到1。 (2)执行临界区； (3)开锁：当进程使用完资源后，将锁位置为“0“，称为开锁操作，退出临界区。

关锁、开锁操作算法

信号量和P,V原语

尽管用加锁的方法可以实现进程之间的互斥，但这种方法仍然存在一些影响系统可靠性和执行效率的问题。 OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。信号量代表可用资源实体的数量。

信号量(也叫信号灯)的定义：信号灯是一个确定的二元组（s,q），s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。 S代表资源的实体，在实际应用中应准确地说明s的意义和初值，每个信号灯都有一个队列，其初始状态为空。

信号量只能通过初始化和两个标准的原语来访问——作为OS核心代码执行，不受进程调度的打断
初始化指定一个非负整数值，表示空闲资源总数。
信号量的物理含义：
- S>0表示有S个资源可用；
- S=0表示无资源可用；
- S<0则|S|表示S等待队列中的进程个数；信号量的初值应该大于等于0。

信号量的数值仅能有P,V原语操作改变

对信号量S的P操作记为P(S)，P操作是一个不可分割的原子操作。
对信号量S的V操作记为V(S), V操作是一个不可分割的原子操作。
在具体实施时，应注意P、V操作都应该作为一个整体实施，不允许只有P操作，而无V操作。

P操作：当将信号量的值减1后，若结果为大于或等于零，则进程可以继续执行，否则调用P(S)的进程被阻塞，并插入到该信号量的等待队列中，然后转进程调度程序。（1）s值减1；（2）若相减结果大于等于0，则进程继续执行；（3）若结果小于0，则该进程挂起。

V操作：当将信号量的值加1后，若结果大于零，进程继续执行，否则要唤醒在信号量等待队列上的一个进程，然后再返回原进程继续执行或转进程调度。（1）s值加1；（2）若相加结果大于0，进程继续执行；（3）否则，唤醒一个（或多个）等待该信号灯的进程，然后本进程继续执行或转进程调度。

进程同步

同步的定义：所谓同步就是并发进程在一些关键点上可能需要相互等待与互通消息，这样的相互制约关系称为进程同步。

生产者-消费者问题

问题描述：一组生产者向一组消费者提供消息，它们共享一个有界缓冲区n，生产者向其中投放消息，消费者从中取得消息。规则：

对于生产者进程：产生一个数据，当要送入缓冲区时，要检查缓冲区是否已满，若未满，则可将数据送入缓冲区，并通知消费者进程；否则，等待；
对于消费者进程：当它去取数据时，要看缓冲区中是否有数据可取，若有则取走一个数据，并通知生产者进程，否则，等待。
缓冲区是个临界资源，因此，诸进程对缓冲区的操作程序是一个共享临界区，所以，还有个互斥的问题。

full：缓冲区产品数目，初值为0；
empty：缓冲区可存放产品的空位，初值为n；
mutex：对缓冲区互斥信号灯，初值为1；

main(){
	int full=0,empty=n,mutex=1;
	cobegin
		producer();
		consumer();
	coend
}

producer(){
	while(生产未完成){
		...;
		生产一个产品;
		p(empty);
		p(mutex);
		将产品放入缓冲区;
		v(mutex);
		v(full);
	}
}

consumer(){
	while(还要继续消费){
		p(full);
		p(mutex);
		从缓冲区中取出一个产品;
		v(mutex);
		v(empty);
		消费一个产品;
		...;
	}
}

每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥——否则可能死锁。

读者-写者问题

问题描述：有两组并发进程:读者和写者,共享一组数据区，进行读写操作，要求任一时刻“写者”最多只允许一个，而“读者”则允许多个。

规则：

允许多个读者同时执行读操作；
不允许读者、写者同时操作；
不允许多个写者同时操作。

读者和写者的相互关系：

“读－写”互斥
“写－写”互斥
"读－读"允许

采用信号量机制：

Wmutex表示“允许写或允许读”，初值：Wmutex =1；即Wmutex表示写者与其它写者或读者互斥。
公共变量Rcount表示“正在读”的进程数，初值：Rcount =0；
Rmutex：表示对Rcount的互斥操作，初值：Rmutex=1。

main(){
	int Wmutex=1,Rmutex=1,Rcount=0;
	cobegin
		read1();
		...
		readi();
		write1();
		...
		writej();
	coend
}

读者进程：
readn(){
	P(Rmutex);
	Rcount++;
	if(Rcount==1) P(Wmutex);
	V(Rmutex);
	读
	P(Rmutex);
	Rcount--;
	if(Rcount==0) V(Wmutex);
	V(Rmutex);
}

写者进程：
writem(){
	P(Wmutex);
	写
	V(Wmutex);
}

其中n=1,2,...,i；m=1,2,...,j。

哲学家就餐问题

问题描述：有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子，即共5只筷子。每个哲学家的行为是思考和进餐。为了进餐，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。思考时则同时将两支筷子放回原处。规则：

只有拿到两只筷子时，哲学家才能吃饭；
如果筷子已经在他人手上，则该哲学家必须等到他人吃完之后才能拿到筷子；
任何一个哲学家在自己没有拿到两只筷子吃饭之前，决不放下自己手中的筷子。

设信号量chopstick[0]…chopstick [4]分别表示第i号筷子是否被拿，1表示空闲，0表示被拿；初值全为1。

main(){
	int chopstick[0]=1,chopstick[1]=1,chopstick[2]=1,chopstick[3]=1,chopstick[4]=1;
	cobegin
		eat0();
		...
		eat4();
	coend
}

eati(){
	think;
	P(chopstick[i]);
	P(chopstick[(i+1)mod5]);
	eat;
	V(chopstick[i]);
	V(chopstick[(i+1)mod5]);
	think;
}

上述解法可保证不会有两个相邻的哲学家同时进餐，但是可能会引起死锁，假如五个哲学家同时饥饿拿起各自左边的筷子，使五个信号量全为0，当他们再试图去拿右边的筷子时，就会无限等待。解决方法：

至多只允许四个哲学家同时进餐，以保证至少有一个哲学家可以进餐，最终总会释放出他所用过的两只筷子，从而可使更多的哲学家进餐；
规定奇数号哲学家先拿起左边筷子，然后再去拿右边筷子，而偶数号哲学家则相反。

eati(){
	think;
	P(count);
	P(chopstick[i]);
	P(chopstick[(i+1)mod5]);
	eat;
	V(chopstick[i]);
	V(chopstick[(i+1)mod5]);
	V(count);
	think;
}

eati(){
	think;
	if i mod 2==1 then{
		P(chopstick[i]);
		P(chopstick[(i+1)mod5]);
		eat;
		V(chopstick[i]);
		V(chopstick[(i+1)mod5]);
	}
	else{
		P(chopstick[(i+1)mod5]);
		P(chopstick[i]);
		eat;
		V(chopstick[i]);
		V(chopstick[(i+1)mod5]);
	}
	think;
	}
}

进程通信

进程间通信的类型

低级通信和高级通信

低级通信：只传送控制信息，一般只传送一个或几个字节的信息，以达到控制进程执行速度，包括进程互斥和同步所采用的信号量。
- 优点是传送速度快。
- 缺点是：
  - 传送信息量小，效率低：每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。
  - 编程复杂：用户直接实现通信的细节，编程复杂，容易出错。
高级通信：能够传送大批量的数据，目的不是为了控制进程的执行速度，而是为了交换信息。

直接通信和间接通信

直接通信：发送进程发消息时要指定接收进程的名字，反过来，接收时要指明发送进程的名字。信息直接传递给接收方，如管道。
- 在发送时，指定接收方的地址或标识，也可以指定多个接收方或广播式地址；
- 在接收时，允许接收来自任意发送方的消息，并在读出消息的同时获取发送方的地址
- Send(receiver,message)
- Receiver(sender,message)
间接通信：发送进程发消息时不指定接收进程的名字，而是借助于收发双方进程之外的共享数据结构作为通信中转，如信箱。通常收方和发方的数目可以是任意的。
- 发送原语：send(MB,Message)
- 接收原语：receive(MB,Message)

进程间通信的方式

在单机系统中，进程间通信可以分为四种形式：

主从式

主进程可自由地使用从进程的资源或数据；
从进程的动作受主进程的控制；
主进程和从进程的关系是固定的。

会话式通信进程双方可分别称为使用进程和服务进程。其中，使用进程调用服务进程提供的服务。

使用进程在使用服务进程所提供的服务之前，必须得到服务进程的许可；
服务进程根据使用进程的要求提供服务，但对所提供服务的控制由服务进程自身完成。
使用进程和服务进程在进行通信时有固定连接关系。

消息或信箱机制无论接收进程是否已准备好接收消息，发送进程都将把所要发送的消息送入缓冲区或邮箱。

只要存在空缓冲区或邮箱，发送进程就可以发送消息。
与会话系统不同，发送进程和接收进程之间无直接连接关系，接收进程可能在收到某个发送进程发来的消息之后，又转去接收另一个发送进程发来的消息。
发送进程和接收进程之间存在缓冲区或邮箱用来存放被传送消息。

共享存储区方式共享存储区方式不要求数据移动。两个需要互相交换信息的进程通过对同一共享数据区(shared memory)的操作来达到互相通信的目的。这个共享数据区是每个互相通信进程的一个组成部分。

消息缓冲机制

发送进程先申请一个消息缓冲区，写入消息后把该消息缓冲区送入接收进程的消息队列中，通知接收进程。接收进程从消息队列中摘下一消息缓冲区，取出所需要的信息。

发送原语：发送一个消息给进程 B,发送进程存放的消息内存区的首址在m中：send ( B, m)
接收原语:接收来自A进程的消息n：Receive ( A, n)

消息缓冲机制中所使用的缓冲区为公用缓冲区，使用消息缓冲机制传送数据时，两通信进程必须满足如下条件：

在发送进程把消息写入缓冲区和把缓冲区挂入消息队列时，应禁止其它进程对该缓冲区消息队列的访问。否则，将引起消息队列的混乱。同理，当接收进程正从消息队列中取消息缓冲时，也应禁止其它进程对该队列的访问。
当缓冲区中无消息存在时，接收进程不能接收到任何消息。

邮箱通信

邮箱通信就是由发送进程申请建立一与接收进程链接的邮箱。发送进程把消息送往邮箱，接收进程从邮箱中取出消息，从而完成进程间信息交换。

邮箱由邮箱头和邮箱体组成。其中邮箱头描述邮箱名称、邮箱大小、邮箱方向以及拥有该邮箱的进程名等。邮箱体主要用来存放消息。

进程间的通信要满足如下条件： a.发送进程发送消息时，邮箱中至少要有一个空格存放该消息。 b.接收进程接收消息时，邮箱中至少要有一个消息存在。

死锁问题

死锁的定义

死锁的定义：指两个或多个并发进程彼此相互等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源，而无法继续向前推进的状态。

产生死锁的原因

竞争资源

可剥夺性资源：CPU、RAM等；非剥夺性资源：打印机、磁带机等；临时性资源：通信数据。
系统中配备的非剥夺性资源的数量不能满足诸进程运行的需要时，会使进程因争夺资源而陷入僵局。

进程推进顺序不合理

产生死锁必要条件

只有4个条件都满足时，才会出现死锁 (1)互斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一个进程所占有。（涉及的资源是临界资源） (2)部分分配（请求和保持条件）：进程每次申请它所需要的一部分资源，在等待新资源的同时，继续占有已经分配到的资源。 (3)不剥夺条件：进程已获得的资源，在没有使用完之前，不能被剥夺，只能在使用完时由自己释放。 (4)环路条件：在发生死锁时，必然存在一种进程-资源的循环链，链中每一个进程已获得的资源同时被下一个进程所请求。

死锁的排除方法

预防死锁：采取某种策略，限制并发进程对资源的请求，从而破坏产生死锁的必要条件中的一个或者几个来防止发生死锁。基本思想：打破产生死锁的四个必要条件中的一个或者几个。（排除死锁的静态策略）
避免死锁：系统在分配资源时，根据资源的使用情况提前做出预测，从而避免发生死锁。在资源的动态分配过程中，用某种方法防止系统进入不安全状态。
检测与解除死锁：系统设有专门的机构，当发生死锁时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁中恢复出来。
- 死锁的检测
  - 通过系统的检测机构，及时地检测出死锁的发生，确定与死锁有关的进程和资源。
  - 资源分配图的化简，检查是否存在循环等待。
  - 显然，死锁的频繁检测会大大增加系统开销。
- 死锁的解除
  - 将进程从死锁状态中解脱出来。
  - 最小代价撤销进程法：选择被撤进程代价最小的。
  - 挂起进程：使用挂起与激活机构，缓解资源紧张。