[操作系统] 进程 – YHYShiroha的小屋

采用教材：计算机操作系统-汤小丹等编著-西安电子科技大学出版社

进程

进程实体：由程序段、相关的数据段和PCB三部分组成

PCB：进程控制块，系统利用PCB来描述进程的基本情况和活动过程（PCB是进程存在的唯一标志）

进程状态

时间片完：1）避免长期占用CPU；2）高优先级占用

进程的阻塞是主动行为，唤醒是被动行为（被其他进程唤醒）

进程的互斥与同步

临界资源与临界区

临界资源是一次仅允许一个进程使用的共享资源。（硬件：打印机，磁带机等；软件：变量，数组，缓冲区等）

每个进程中访问临界资源的那段代码称为临界区。

int count = 10;

//P1
count += 5; //临界区

//P2
count *= 10; //临界区

//P1 -> P2：count = 150
//P2 -> P1：count = 105

如上代码中，P1和P2都使用了count这个变量，这个变量就是临界资源。可见，P1和P2如果执行顺序不同，是会产生不同的count值的。

竞争：如两进程对同一数据进行改写

进程互斥

多个程序在并发执行时，由于共享系统资源，致使在这些并发执行的程序之间形成相互制约的关系。

进程同步

某些应用程序，为了完成某任务而建立了两个或多个进程。这些进程将为完成同一项任务而相互合作。

同步机制应遵循的规则

1）空闲让进：无进程处于临界区，允许一个请求进入临界区的进程立即进入自己的临界区；

2）忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待；

3）有限等待：对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，避免“死等”；

4）让权等待：当进程不能进入自己的临界区时，应当立即释放处理机，避免“忙等”。

硬件同步机制

TS指令

bool TS(bool *lock) {
	bool old;
	old = *lock;
	*lock = TRUE;
	return old;
}

do {
	...
	while TS(&lock); //lock初值为FALSE
	//critical section;  临界区
	lock = FALSE;
	//remainder section;
}while(TRUE);

Swap指令

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

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

信号量机制

整型信号量

wait(S) {
	while(S <= 0); //S初值为1
	S--;
}
//临界区代码
signal(S) {
	S++;
}

记录型信号量

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

wait(semaphore *S) {
	S -> value--; //S初值为1
	if(S -> value < 0) block(S -> list);
}
//临界区代码
signal(semaphore *S) {
	S -> value++;
	if(S -> value <= 0) wakeup(S -> list);
}

信号量的应用

互斥

//模板
semaphore mutex = 1; //初值

//Pa
Pa() {
	while(1) {
		wait(mutex);
		临界区;
		signal(mutex);
		剩余区;
	}
}

//Pb
Pb() {
	while(1) {
		wait(mutex);
		临界区;
		signal(mutex);
		剩余区;
	}
}

同步

/*
//模板
P1() {
	A;
	V(S);
}

P2() {
	P(S);
	B;
}
*/
p1() {S1; signal(a); signal(b);}
p2() {wait(a); S2; signal(c); signal(d);}
p3() {wait(b); S3; signal(e);}
p4() {wait(c); S4; signal(f);}
p5() {wait(d); S5; signal(g);}
p6() {wait(e); wait(f); wait(g); S6;}
main() {
	semaphore a,b,c,d,e,f,g;
	//初值
	a.value = b.value = c.value = 0;
	d.value = e.value = 0;
	f.value = g.value = 0;
	cobegin
		p1();p2();p3();p4();p5();p6();
	coend
}

经典进程的同步问题

生产者—消费者问题

假定在生产者和消费者之间的公用缓冲池中具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用;利用信号量empty和 full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池;只要缓冲池未空，消费者便可从缓冲池中取走一个消息。

int in=0, out=0;
item buffer[n];
semaphore mutex=1, empty=n, full=0;
void proceducer() {
	do {
	producer 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
}

哲学家进餐问题

由 Dijkstra提出并解决的哲学家进餐问题(The Dinning Philosophers Problem)是典型的同步问题。该问题是描述有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。

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

在以上描述中，当哲学家饥饿时，总是先去拿他左边的筷子，即执行wait(chopstick[i]);成功后，再去拿他右边的筷子，即执行wait(chopstick[(i+1)%5]);又成功后便可进餐。进餐毕，又先放下他左边的筷子，然后再放他右边的筷子。虽然，上述解法可保证不会有两个相邻的哲学家同时进餐，但却有可能引起死锁。假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0;当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。对于这样的死锁问题，可采取以下几种解决方法:

(1)至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。

(2)仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。

(3)规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子;而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子;3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。

视频讲解

https://pan.baidu.com/s/1jV1xUwMp1BOyc1bKbXN7sw?pwd=msh5 提取码: msh5

进程