# 并发：同步与互斥

# 1. 并发进程

# 1.1 进程的顺序性

进程的执行是严格按序的，进程内部及进程间也是按序的

# 1.2 顺序程序的设计特点

程序执行的顺序性
程序环境的封闭性
程序执行结果的确定性
计算过程的可再现性

# 1.3 并发程序设计

进程的执行在时间上是重叠的

并发的实质是一个处理器在几个进程间的多路复用

# 1.4 并发问题

并发可能是无关的，也可能是交互的。
无关的并发进程指他们在不同的变量集合上操作
交互的并发进程指他们共享某些变量，之间存在制约关系

# 1.4.1 无关并发进程

Bernstein 条件

$设R(p_i)=\{ a_1,a_2...a_n\},表示程序p_i在执行期间引用的变量 \\ 设W(p_i)=\{b_1,b_2...b_n\},表示程序p_i在执行期间改变的变量 \\ 则程序p_1与p_2满足Bernstein条件：\\ (R(p_1)\cap{W(p_2)})\cup(R(p_2)\cap{W(p_1)})\cup(W(p_1)\cap{W(p_2)}) = \{\}$

# 1.4.2 交互并发进程

进程间相互制约可能会导致时间有关错误

结果不唯一
永远等待

# 1.5 并发进程的好处

有效利用资源，充分发挥机器部件的并行能力

# 1.6 进程的交互

# 1. 竞争

多个进程并不知道彼此的存在
两个控制问题
- 死锁问题
- 饥饿问题
进程互斥是指若干进程因相互争夺独占型资源而产生的竞争制约关系

# 2. 协作

进程间相互知道彼此的存在
进程同步是指为完成共同任务的并发进程基于某个条件来协调其活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系

# 2. 临界区管理

# 2.1 互斥与临界区

并发进程中与共享变量有关的程序段叫临界区，共享变量所代表的资源叫临界资源
一次至多一个进程进入临界区执行
临界区调度原则：互斥使用，有空让进，忙则等待，有限等待，择一而入，算法可行

# 2.2Peterson 方法

1 2	int turn; //表示由哪个进程进入临界区 boolean flag[2]; // //表示进程希望进入临界区的意愿

# 2.3 关中断

while(true)
{
    /* disable interrupts */;
    /* critical section */;
    /* enable interrupts */;
    /* remainder */;
}

关中断使得当前执行的进程不会被打断，从而不会发生进程切换
关中断时间过长会影响系统效率

# 2.4 测试并设置指令

将临界区与一个布尔变量 lock 相关联
lock 代表临界资源的状态，可以看成一把锁，lock 为 true/false 表示临界资源可用 / 不可用
初始值为 true, 如有进程要进入临界区，则对 lock 进行测试和设置指令
如果已有进程在临界区，则 test_and_set 返回 false, 将被阻止进入临界区
如果没有进程在临界区，则 test_and_set 返回 true, 同时将 lock 设为 false, 以阻止其它进程进入临界区

# 2.5 对换指令

为每个临界区设置锁变量 lock，lock 为 false 表示无进程在临界区内
当进程进入临界区时，lock 设置为 true, keyi 变为 false, 因此进程得以通过测试，进入临界区
当另一个进程希望进入临界区时，swap (keyi, lock) 的结果是 keyi=lock=true, 因此，进程被阻止进入临界区

# 3. 信号量与 PV 操作

# 3.1 信号量

信号量表示物理资源的实体，是一个与队列有关的整型变量

typedef struct{
    int value;
    struct process* list;
}semaphore;
//value为一个整型变量，系统初始化时为其赋值；list是等待使用此类资源的进程队列的头指针，初始状态为空队列。
//负数表示等待进程数

如果 value 只能取 0 或 1，则成为了互斥量 (Mutex),0 表示临界区已加锁，1 表示临界区已释放

# 3.2PV 操作 (原子操作不可分割)

void P(semaphore s)
{
     s.value--;
    if(s.value<0)
    {	
        //place this process in the s.list
        //block this process
	}
}
void V(semaphore s)
{
    s.value++;
    if(s.value<=0)
    {
        //remove a process P from s.list
        //place process P on ready list
    }
}

# 3.3 哲学家就餐问题

问题描述：5位哲学家围在一张圆桌旁，桌子中央有一盘通心粉，每人面前有一只空盘子，每两人之间有一只叉子；每位哲学家思考，饥饿，然后吃通心面；为了吃面，哲学家必须获得两把叉子，且每人只能直接从紧邻自己的左边或右边去取叉子

#define THINKING   0
#define HUNGRY     1
#define  EATING     2
#define semaphore
semaphore s[5];  //用于阻塞哲学家的信号量
semaphore mutex=1;//进程解锁
int state[5]; //哲学家的状态
for(int  i=0;i<5;i++){
    state[i]=THINKING;
    s[i] = 0;
}

void philosopher(int i)
{
	while(true)
	{
		think();
		take_fork(i);
		eat();
		put_fork(i);
	}
}

void take_fork(int i)
{
	P(mutex);//进程加锁
	state[i]=HUNGRY;
	check(i);//判断左右叉子状态
	V(mutex);//进程解锁
	P(s[i]);//只有收到通知才能开始吃
}
void put_fork(int i)
{
	P(mutex);//进程加锁
	state[i]=THINKING;
	check((i+1)%5);//判断左手
	check((i+4)%5);//判断右手
	V(mutex);//进程解锁
}

void check(int i)
{
	if(state[i]==HUNGRY&&state[(i+1)%5]!=EATING&&state[(i+4)%5]!=EATING)
	{
		//左右手邻居都不在吃，则同时获得两把叉子
		state[i]=EATING;
		V(s[i]);//进程解锁
	}
}

# 3.4 生产者消费者问题

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}

# 4. 管程

管程是一种软件模块，用于将分散的信号量操作集中起来，能降低编程的复杂度

把分散的临界区集中起来管理，并把共享资源使用数据结构表示出来
管程每次只允许一个进程

# 条件变量

只有在管程才能被访问

cwait (x) 在条件变量 x 上挂起调用进程并释放管程，直到另一个进程在条件变量上执行 csignal (x)
csignal (x)) 如果有其它进程因对条件变量 x 执行 cwait (x) 而被挂起，便释放其中的一个等待进程；如果没有进程在等待，则 csignal () 操作没有任何效果，即 x 变量的状态没有改变

# 5. 进程间通信

# 信号通信 (signal)

信号是一种软中断，通过发送指定信号来通知进程某个异步事件的发生，迫使进程执行信号处理函数

# 管道通信 (pipe)

管道是连接读写进程的一个特殊文件
- 发送进程将管道文件视作输出文件
- 接收进程将管道文件视作输入文件

# 消息传递

1 2	send(destination,message); receive(source,message);

消息传递需要操作系统的参与

# 共享内存

建立一块共享内存区域
进程可以读 / 写共享内存的数据
适用于大量数据传输，速度快
需要应用程序显式地避免冲突

Operating System