标签：复习 signal 死锁 value 信号量互斥临界进程

不同进程之间的关系
- 同步 = 直接制约关系，相互之间协调顺序，进行阻塞等调整。
- 互斥 = 间接制约关系，一个进程进入临界区，另一进程必须等待。

同步

临界区问题

多道程序环境中，进程并发执行，但不同进程之间会有联系和相互制约。
临界资源一次只允许一个进程使用：打印机等
所以需要互斥。

临界资源访问过程
1. 进入区：检查可否进入临界区。能：设置正在访问标志，阻止其他进程访问临界区。
2. 临界区：访问临界资源的代码段
3. 退出区：清除正在访问标志
4. 剩余区：剩余代码部分
临界区问题方案原则：
1. 互斥：只有一个进程在临界区执行。
2. 进步progress：临界区无进程在运行，有进程需要进入临界区-->只有不在剩余区内执行的进程可以参加选择。
3. 有限等待：发出进入临界区请求-->被允许的时间有上限。
  在临界区运行的进程不能被调度或切换。

实现临界区互斥基本方法

软件实现方法

单标志法
双标志法-先检查
双标志法-后检查

4 Peterson's Algorithm

进程共享2个数据：
- int turn;
- boolean falg[2]：进程P_i flag[i]=true表示想进入临界区。
  - 若P_j在临界区，P_i会在while中不进入临界区。

do {
	flag[i] = true;
	turn = j;
	while (flag[j] && turn == j);
		critical section
	flag[i] = false;
	remainder section
} while (true);

硬件实现方法

通过锁来保护临界区。称为低级方法。

缺点：进程等待进入临界区等待耗时，不能让权等待，很多进程一起等的时候，有些进程可能一直选不上-->
单处理器：修改共享变量时禁止中断/关中断即可。
多处理器：这样过于耗时不可行。

2 硬件指令方法

TestAndSet指令：检查lock值。lock=true表示不可中断，临界区执行；
Swap指令：交换两个字的内容

解决临界区问题工具

以下是构建好的软件工具。

1 互斥锁 mutex lock

最简单的同步工具。

缺点：使用忙等待。其他进程在临界区时，其他进程要不断调用acquire()。
不过这里等待锁时没有上下文切换。
bool available：表示锁是否可用；
acquire() 锁可用时获得锁，这个锁不会被其他的进程用了；一个原子操作
release() 一个原子操作

信号量 semaphore

定义两个标准原子操作：

P操作-申请资源：wait(S) 资源-- 减少信号量计数
V操作-释放资源：signal(S) 资源++

1 二进制信号量

二进制信号量-->值0 or 1。
so类似于互斥锁，提供互斥。

2 整型信号量

变量 value
- value > 0 信号量可用资源数
- value = 0 无空闲资源、无空闲进程，正在执行一个进程
- value < 0 calue绝对值代表正在使用该资源的阻塞进程数量
  这里在临界区内忙等

wait(value){
	while(value<=0); /*没有可用资源时忙等*/
	value--; /*有可用资源时减少资源数 表示占用这个资源*/
}
signal(value){
	value++; /*释放资源 可用资源数++*/
}

3 记录型信号量

不存在忙等的机制

变量 value、链表List

typedef struct{
	int value;
	struct process *List;/*连接等待该资源的进程*/
}semaphore; /*一个信号量拥有的数据*/

void wait(semaphore sema){
	sema.value--; /*申请资源时*/
	if(sema.value < 0){/*没有可用资源了*/
		add this process to sema.List;
		block(sema.List);/*自我阻塞 等待唤醒*/
	}
}

void signal(semaphore sema){
	sema.value++; /*释放资源时*/
	if(sema.value <= 0){/*释放前是没有可用资源的*/
		remove a process P from sema.List;
		wakeup(P);/*唤醒其中一个自我阻塞的进程*/
	}
}

4 导致的死锁与饥饿

一个死锁的例子：S、Q资源 进程P0、P1
1. P0：wait(S)  -->  P1：wait(Q)  -->
2. P0：wait(Q) 这里要等P1 signal(Q)之后才能到下一步
/*！！已经开始无线等待了*/
# 死锁！！！死！！！
/* because要等到`5`才释放，同时`4`也在后面，等也等不到 */
3. P1：wait(S) 这里要等P0释放S之后才能到下一步
4. P0：signal(S) 释放S
5. P1：signal(Q) 释放Q
6. P0：signal(Q) 释放Q
7. P1：signal(S) 释放S

5 优先级反转问题

意思是H等M完成才能运行，但是理应当是H先运行嘛。
这是因为临界资源R被L先占用了。

三个进程：L低、M中、H高进程	资源R
0. 进程L正在访问R
1. H请求访问R，H阻塞等待L使用完
2. 这是L被M抢占，M执行，L没办法及时释放资源R
3. 等待M运行完，L运行完，H才运行

解决

给资源R也设置优先级，高于所有进程的优先级，这样不会出现优先级反转的问题。
pintos采用的是进行优先级捐赠。
就是让L临时继承H的优先级，这样M就不会抢占了，等L运行完，释放R之后交还优先级给H，然后H立即执行。最后才到M。

管程

利用ADT 抽象数据类型封装了数据and一系列函数，管程的类型就是ADT类型。(管程很像一个类class)

把对共享资源的操作封装
只有一个进程在管程内处于活动状态。-->实现互斥。

条件变量

条件变量condition...pintos既视感
管程中设置了多个condition条件变量，每个condition保存了一个等待队列，指向因这个condition变量阻塞的所有进程。

对condition条件变量的操作
- x.wait()：当资源不满足，正在管程中的进程调用x.wait()加入这个condition的队列中，释放管程，进程阻塞。然后其他进程可使用管程。
- x.signal()：对应的condition发生了变化，调用x.signal()，唤醒正好一个阻塞的进程
！当执行signal操作但无对应的阻塞线程时，系统会认为signal没有发生过。

对比信号量操作

类似：类似P/V操作，对进唤醒/阻塞
不同：condition没有值，只是一个等待功能。
信号量有一个值体现共享资源数量。

经典同步问题

1 生产者/消费者模型

。。。

2 读者-写者问题

共享一个文件，又读又写

要求：
1. 允许多读者一起读
2. 允许1个写者写入
3. 写入完成前不允许读
4. 写之前所有读者要退出

3 哲学家进餐问题

。。。

嗯当时上课的时候就没怎么明白是怎么回事，欠下来的债终归是躲不掉的。

标签：复习,signal,死锁,value,信号量,互斥,临界,进程
From： https://www.cnblogs.com/sectumsempra/p/17127918.html

期末复习——同步、互斥、死锁

同步