并发 竞争与协作 异步产生的错误 同步
并发
- 在内存中同时存在的若干个进程/线程，由操作系统的调度程序采用适当的策略将他(们)调度至CPU(s)上运行，同时维护他们的状态队列。
- 多个并发进程/线程从宏观上是同时在运行；
- 从微观上看，他们的运行过程是走走停停；
-
并发进程之间的关系
独立关系
- 并发进程分别在自己的变量集合上运行
- 例如：chrome和QQ音乐
交互关系
Asynchronous means RANDOM!
- 会引发竞争条件（Race Condition）：一种这样的情况：多个进程并发操作同一个数据导致执行结果依赖于特定的进程执行顺序。
Ti是订票终端，x = 2 代表剩余票数，为所有终端共享，终端逻辑代码如下：
剩余票数最终结果不确定！可能是1，也可能是0.
同步
- 进程同步：进程同步是指一种保持协作进程中共享数据一致性的机制。
- 同步工具包：
1. 临界区（critical section）问题
- 每个并发进程有个一代码段称为临界区，在该区中进程可能改变共同变量、更新一个表或写一个文件。
- 这种系统的重要特征是当一个进程进入临界区，没有其他进程可被允许在临界区内执行，即没有两个进程可同时在临界区内执行。
- 临界资源（Critical resource）每次只能被一个进程访问。而临界区则是能够访问临界资源的代码片段。
- 临界区问题（critical-section problem）是设计一个以便进程协作的协议。每个进程必须请求允许进入其临界区。实现请求的代码段称为进入区（entry section），临界区之后需要归还许可有退出区（exit section），其他代码段成为剩余区（remainder section）。
临界区管理准则
临界区问题的解答必须满足三项要求：
- 互斥（mutual exclusion）： 如果进程Pi在其临界区内执行，那么其他进程都不能在其临界区内执行；
- 前进（progress）：如果没有进程在其临界区内执行且有进程需进入临界区，那么只有那么不在剩余区内执行的进程可参加选择，以确定谁能下一个进入临界区，且这种选择不能无限推迟；
- 有限等待（bounded waiting）：从一个进程做出进入临界区的请求，直到该请求允许为止，其他进程允许进入其临界区内的次数有上限。
有空让进；择一而入；无空等待；有限等待；让权等待
有两种方法用于处理操作系统内的临界区问题：
- 抢占内核（preemptive kernel）：
- 抢占内核允许处于内核模式的进程被抢占。
- 抢占内核更受欢迎，因为抢占内核更适合实时编程，因为它能允许实时进程抢占处于内核模式运行的其他进程。
- 抢占内核模式的响应更快，因为处于内核模式的进程在释放CPU之前不会运行太久
与非抢占内核（nonpreemptive kernel）
Peterson算法是一种经典的基于软件的临界区问题算法，可能现代计算机体系架构基本机器语言有些不同，不能确保正确运行。
Peterson算法适用于两个进程在临界区与剩余区间交替执行,为了方便，当使用Pi时，Pj来标示另一个进程，即j=i−1。Peterson算法需要在两个进程之间共享两个数据项：
int turn;boolean flag[2];
变量turn表示哪个进程可以进入其临界区，即如果turn==i，那么进程Pi允许在其临界区内执行。 数组flag表示哪个进程想要进入临界区，如果flag[i]为true，即Pi想进入其临界区
//进程Pi的Peterson算法 ```java
do{
flag[i]=TRUE; turn=j; while(flag[j]&&turn==j);
临界区
flag[i]=FALSE;
剩余区
}while(TRUE)
可以证明，满足三项要求。- Peterson算法实际上是一种谦让的过程，即：- Pi：我已经准备好了，但是我让这次一次的turn=j，看看Pj是否要运行，如果是的话，我就让Pj先运行。- Pj也是这样的情况。<a name="eUU5Q"></a>## 互斥锁（硬件同步）通过要求临界区用锁来保护，就可以避免竞争条件，即进程在进入临界区之前必须得到锁，而其他退出临界区时释放锁。```javado{请求锁临界区释放锁剩余区}while(TRUE)
忙式等待（BUSY WAITING）
- 忙式等待是指占用CPU执行空循环实现等待（等待时一直空循环）
- 这种类型的互斥锁也被称为“自旋锁”
信号量与PV操作
- 信号量（Semaphore）是一种比互斥锁更加强大的同步工具，它可以提供更高级的方法来同步并发线程。
- 信号量S是个整数变量，除了初始化外，它只能通过两个标准原子操作：wait()和signal()来访问。即P和V。
wait()就是等待资源的过程，定义可表示为：
wait(S){while(S<=0);//no-opS--;}
signal()就是释放资源的过程，定义可表示为：
signal(S){S++;}
在wait()和signal()操作中，对信号量整型值的修改必须不可分地执行。即当一个进程修改信号量值时，不能有其他进程同时修改同一信号量的值。另外，对于wait(S)，对于S的整数值测试(S≤0)和对其可能的修改(S–)，也必须不被中断地执行。
用法
通常操作系统区分计数信号量和二进制信号量（二值信号量）。计数信号量的值域不受限制，而二进制信号量的值只能为0或1,有的系统，将二进制信号量称为互斥锁。
1. 二值信号量
由于二进制信号量是互斥的，因而可以将其应用于处理多进程的临界区问题：这n个进程共享信号量mutex，初始值1。结构如下：do{wait(mutex);//critical sectionsignal(mutex);//remainder section}while(TRUE);
2. 计数信号量
计数信号量可以用来控制访问具有若干个实例的某种资源。该信号量初始化为可用资源的数量。当每个进程需要使用资源时，需要对该信号量执行wait()操作。当进程释放资源时，需要对该信号执行signal()操作。
可以用信号量来解决各种同步问题。如先执行Pi的S1语句，然后再执行Pj的S2语句，可以通向一个信号量，初始化为0。
进程P1中插入语句：S1;signal(synch);
在进程P2中插入语句：
wait(synch);S2;
因为初始化synch为0，P2
只有在P1调用signal(synch)，即(S1)之后，才会执行S2。
3. 实现
信号量的主要缺点是要求忙等待（busy waiting）。即在进入代码段中连续地循环。忙等待浪费了CPU时钟，这种类型的信号量也称为自旋锁（spinlock），这是因为进程在其等待锁的时还在运行(自旋锁有其优点，进程在等待锁时不进行上下文切换，而上下文切换可能需要花费相当长的时间。因此如果锁占用的时间短，那么锁就有用了，自旋锁常用于多处理器系统中，这样一个线程在一个处理器自旋时，另一线程可在另一个处理器上在其临界区内执行).
为克服这一缺点，修改wait()和signal()的定义，信号量值不为正时，不是忙等而是阻塞自己，阻塞操作将一个进程放入到与信号量相关的等待队列中，并将该进程的状态切换成等待状态，接着，控制转到CPU调度程序，以选择另一个进程来执行，从而使CPU占用率变高。
被阻塞在等待信号Ｓ上的进程，可以在其他进程执行signal()的时候操作之后重新被执行，该进程的重新执行是通过wakeup()操作来进行的将进程从等待状态切换到就绪状态。接着进程被放到就绪队列中。
因而将信号量定义为如下：typedef struct{int value; //记录了这个信号量的值struct process *list; //储存正在等待这个信号量的进程（PCB链表指针）}semaphore;
每个信号量都有一个整型值和一个进程链表，当一个进程必须等待信号量时，就加入到进程链表上，操作signal()会从等待进程链表中取一个进程以唤醒。
wait()实现：wait(semaphore *S){S->value--;if(S->value<0) //没有资源{add this process to S->list; //进入等待队列block(); //堵塞}}
signal()实现：
signal(semaphore *S){S->value++;if(S->value<=0){ //上面++后，S仍然还<=0，说明资源供不应求，等待者还有很多，于是唤醒等待队列中的一个remove a process P from S->list;wakeup(P); //切换到就绪状态}}
操作block()挂起调用他的进程。
- 操作wakeup(P)重新启动阻塞进程Ｐ的执行。
- 这两个操作都是由操作系统作为基本系统调用来提供的。
在具有忙等的信号量经典定义下，信号量的值绝对不能为负数，但是本实现可能造成信号量为负值。如果信号量为负值，那么其绝对值就是等待该信号量的进程的个数。
等待进程的链表可以利用进程控制块PCB中的一个链接域来加以轻松实现。即每个信号量包括一个整型值和一个PCB链表的指针。
信号量的关键之处是它们原子的执行。必须确保没有两个进程能同时对一个信号量进行操作，在单处理器情况下，可以在执行wait()和signal()的时候简单的关闭中断，保证只有当前进程进行。
多处理器下，若禁止所有CPU的中断，则会严重影响性能，SMP系统必须提供其他加锁技术（如自旋锁），以确保wait()与signal()可原子地执行。
死锁与饥饿
具有等待队列的信号量的实现可能会导致这样的情况： 两个或多个进程无限地等待一个时间，而该事件只能由这些等待进程之一来产生。这里的事件是signal（）操作的执行。出现这样的状态时，这些进程就成为死锁。
例如，一个由P1
和P2组成的系统，每个都访问共享的信号量Ｓ和Ｑ，Ｓ和Ｑ初值均为１。
P0:
wait(S);wait(Q);//......signal(S);signal(Q);
P1:
wait(Q);wait(S);//......signal(Q);signal(S);
假设，P0执行wait(S)，接着P1执行wait(Q)，P0再执行wait(Q)时，必须等待，直到P1执行signal(Q)，而此时P1也在等待P0执行signal(S)，两个操作都不能进行，P0和P1就死锁了。
与死锁相关的另一个问题是无限期阻塞（indefinite blocking）或饥饿（starvation）：即进程在信号量内无限期等待。
举个例子来理解死锁与饥饿的区别：
死锁(deadlock)
指的是两个或者两个以上的进程相互竞争系统资源，导致进程永久阻塞。
例如：
1、桌子上有慢慢一桌子的美食，但是只有一双筷子。
2、甲拿了一根，然后在找另一根。
3、乙拿了一根，然后也在找另一根。
4、因为他们都掌握了对方必需的资源，导致最后他们俩谁都吃不到美食。
饥饿(starvation)
指的是等待时间已经影响到进程运行，此时成为饥饿现象。如果等待时间过长，导致进程使命已经没有意义时，称之为“饿死”。
例如：
1、小明要告诉妈妈明天开家长会。
2、小明妈妈因为工作太忙，在公司加班，没有回家。
3、于是第二天，小明的妈妈就错过了家长会。（“饿死”）
4、其实小明的妈妈没有出现“死锁”。只是小明的优先级过低，不如工作重要。
总结： 死锁就是无限循环等待，大家都饿着，三个和尚没水喝 饥饿就是单方面长时间等待，hander hansi laoder laosi
经典同步问题
1. 有限缓存问题——生产者消费者问题
假设缓冲池有n个缓冲项，每个缓冲项能存在一个数据项。信号量mutex提供了对缓冲池访问的互斥要求，并初始化为1。信号量empty和full分别用来表示空缓冲项和满缓冲项的个数，信号量empty初始化为n；而信号量full初始化为0
当缓冲池满的时候，生产者必须等待 当缓冲区空的时候，消费者必须等待
生产者进程结构：
do{…//produce an item in next p…wait(empty);wait(mutex);…//add next p to buffer…signal(mutex);signal(full);}while(TRUE);
消费者进程结构：
do{wait(full);wait(mutex);…//remove an item from buffer to next c…signal(mutex);signal(empty);…//consume the item in next c…}while(TRUE);
2. 读者写者问题
只读数据库的进程称为读者；更新（读和写）数据库的称为写者。
第一读者-写者问题：要求没有读者需要保持等待，除非已有一个写者已获得允许以使用共享数据库。换句话说，没有读者会因为一个写者在等待而会等待其他读者的完成。 第二读者-写者问题：要求一旦写者就绪，那么写者会尽可能快得执行其写操作。换句话说，如果一个写者等待访问对象，那么不会有新读者开始读操作。 对于这两个问题的解答可能导致饥饿问题。对第一种情况，写者可能饥饿；对第二种情况，读者可能饥饿。
推广为读写锁。
在获取读写锁时，需要指定锁的模式：读访问，还是写访问。当一个进程只希望读共享数据时，可申请读模式的读写锁；当一个进程希望修改数据时，则必须申请写模式。，多个进程可允许并发获取读模式的读写锁，而只有一个进程可为写操作而获取读写锁。
在以下情况下最为有用：
一是，当可以区分哪些进程只需要读共享数据，哪些进程只需要写共享数据；
二是，当读者进程数比写进程多时。
3. 哲学家进餐问题
拿起与他相近的两只筷子，一个哲学家一次只能拿起一只筷子，同时有两只筷子时，就能吃，吃完，会放下两只筷子。
若有收获，就点个赞吧
0 人点赞
