进程管理(引入)

前趋图(也称为：有向无循环图)

条件：有向，无循环

O(圆圈)：节点，代表指令，程序，进程…

→：有向边，代表前趋/后继关系

程序的执行

顺序执行及特征

特征：顺序性，封闭性，可再现性

顺序→并发(可能性分析图)

例题：

引起不可再现性是因为没有临界资源(每一个缓冲区)没有访问(互斥访问)

进程的相关概念

定义

程序的一次执行过程

结构

进程映像：PCB+程序段+数据段 (中断返回地址存放在PCB中)

动态

由"创建"而产生，由"调度"而执行，由"撤消"而消亡(而程序是静态的)

状态

三态结构(图)

就绪状态：

条件：获得除CPU以外的所有资源

一个就绪队列

执行状态：

条件：已获得CPU，程序正在执行的状态

在单处理机系统中，只有一个进程处于执行状态；而在多处理机系统中，则有多个进程处于执行状态

阻塞状态：

条件：进程的执行受到阻塞

一个阻塞队列

实事上，在较大的系统中，为了减少队列操作的开销，提高系统效率，根据阻塞原因不同，会设置多个阻塞队列。

转换关系

经常发生：4个，就绪→执行，执行→就绪，执行→阻塞，阻塞→执行 绝对不会发生：就绪→阻塞 有可能会发生：阻塞→执行

挂起状态

引入原因

减少内存当中进程的数量(从内存调到外存)

状态分类

静止→活动 被激活(执行激活函数) 话动→静止 被挂起(执行挂起函数)

具有挂起状态的进程状态图(五态结构)

进程控制块(PCB)

作用

进程存在的唯一标志

进程控制块中的信息(图)

标识，处理机状态，进程调度信息，进程控制信息

优先数：一般为整数

PCB的组织

链接

索引

进程控制(三对操作)

创建与终止

阻塞与唤醒

挂起与激活

进程同步

概念

并发进程在执行次序上的协调，以达到有效的资源共享和相互合作，使程序的执行具有可再现性

关系

间接制约：互斥共享资源

直接制约：相互合作

临界资源

一次只允许一个进程访问的资源 引起不可再现性是因为没有临界资源(每一个缓冲区)没有访问(互斥访问)

临界区

定义

进程访问临界资源的那段代码

描述

进入区：检查有无进程进入

临界区：

退出区：将访问标志复位

信号量机制

整型信号量(S)

是一个整型量，通过2个原子操作wait (s)和signal (s)来访问

含义：表示资源，$S_{初始值}≥0$

变化： –1：wait(s) p(s) 表示申请资源

+1：signal(s) v(s) 表示释放资源

注：wait(s)和signal(s)是成对出现

问题：当S≤0，不能分配资源，进程阻塞(队列)

记录型(S)

S.value：代表资源，s.value≥0

S.L：阻塞进程的队列

操作

1. wait(s)

分析 ： S.value=1→(p(s))1-1=0

S.value=0→(p(s))0-1=-1

2. signal(s)

分析 S.value=-1→(v(s))-1+1=0

S.value=-2→(v(s))-2+1=-1 小结：

1. 实现进程关系的描述
2. wait(s)和signal(s)是成对出现

同一个进程或两个进程之间出现

在记录型信号量机制中 S.value初值：表示系统中某类资源的数目

S.value<0：表示信号量链表中已阻塞进程的数目

信号量的应用

利用信号量实现互斥

一个进程执行，另一个进程不执行，则成互斥关系

步骤

1. 共享临界资源(mutex)=1

wait(mutex)

signal(mutex)

2. 设置临界区

进入：wait(mutex)

CS

退出：signal(mutex)

同一个进程当中，成对出现

总结

mutex实现临界区的设置(2个)

mutex实现两个进程的互斥

同步(直接制约)

同步的模型

前趋图

S1(被等待)signal(a)→S2(等待)wait(a)

代码框架描述如下

经典进程的同步问题

生产者–消费者问题

设置信号量

1. 每个缓冲区：mutex(初值为：1)
2. empty:空(初值为：n)
3. full:满(初值为：0)

结论

1. 当有多个信号量时，注意wait的顺序
2. 临界区的设置，主要是实现变量的修改

代码描述如下：

int in=0,out=0;
item buffer[n];
semaphore mutex=1,empty=n;full=0;
void proceducer(){
	do{
		proceducer an item nextp;
		...
		wait(empty);
		wait(mutex);
		buffer[in]=nextp;
		in:=(in+1)%n;
		signal(mutex);
		signal(full);
	}while(TRUE)
}
void consumer(){
	do{
		wait(full);
		wait(mutex);
		nextc=buffer[out];
		out:=(out+1)%n;
		signal(mutex);
		signal(empty);
		consumer the item in nextc;
		...
	}while(TRUE)
}
void main(){
	cobegin
		proceducer();
		consumer();
	coend
}

注意

在每个程序中的多个wait操作顺序不能颠倒。应先执行对信号资源量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起死锁

哲学家进餐问题

经分析可知，放在桌子上的筷子是临界资源，在一段时间只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组，描述如下：

semaphore chopstick[5]={1,1,1,1,1};

所有信号量均被初始化为1，第i位哲学家的活动可描述为：

do{
	wait(chopstick[i]);
	wait(chopstick[(i+1)%5]);
	...
	//eat
	...
	signal(chopstick[i]);
	signal(chopstick[(i+1)%5]);
	...
	//think
	...
}while[TRUE];

解决漏洞

假设五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0；当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期等待。从而出现死锁。

对于这样的死锁问题，可采取以下几种解决办法：

1. 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐
2. 仅当哲学家的左，右两只筷子均可用时，才允许他拿起筷子进餐
3. 规定奇数号哲学家先拿起他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1，2号哲学家竞争1号筷子；3，4号哲学家竞争3号筷子，即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。

读者–写者问题

两者呈互斥关系

特点：读进程可共享同一对象，写进程不可共享同一对象。

为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex.另外再设置一个整型变量Readcount表示正在读的进程数目。又因为Readcount是一个可被多个Reader进程访问的临界资源，因此，也因该为它设置一个互斥信号量rmutex

读者–写着问题可描述如下：

semaphore rmutex=1,wmutex=1;
int readcount=0;
void reader(){
	do{
		wait(rmutex);
		if(readcount==0)
			wait(wmutex);
		readcount++;
		signal(rmutex);
		...
		perform read operation;
		...
		wait(rmutex);
		readcount--;
		if(readcount==0)
			signal(wmutex);
		signal(rmutex);
	}while(TRUE);
}
void writer(){
	do{
		wait(wmutex);
		perform write operation;
		signal(wmutex);
	}while(TRUE);
}
void main(){
	cobegin
		reader();
		writer();
	coend
}

思考题