Java中wait()方法为什么要放在同步块中？(lost wake-up 问题)
问：Java 多线程中 wait() 方法为什么要放在同步块中？
答：为了避免「lost wake up 问题」：，即无法唤醒问题。
临界资源
系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源 或互斥资源或共享变量，在共享临界资源是，应采用互斥方式。
临界区：
每个进程中访问临界资源的那段代码称为临界区（criticalsection），每次只允许一个进程进入临界区，进入后，不允许其他进程进入。不论是硬件临界资源还是软件临界资源，多个进程必须互斥的对它进行访问。多个进程涉及到同一个临界资源的的临界区称为相关临界区。使用临界区时，一般不允许其运行时间过长，只要运行在临界区的线程还没有离开，其他所有进入此临界区的线程都会被挂起而进入等待状态，并在一定程度上影响程序的运行性能。
进入区、临界区、退出区、剩余区
如果此刻临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志
如果此刻该临界资源正被某进程访问，则本进程不能进入临界区
进入区：在临界区前面增加一段用于进行上述代码的检查
退出区：在临界区后面加上一段代码，用于将临界区正被访问的标志恢复为未被访问的标志。
剩余区：进程中除进入区、临界区及退出区之外的其他部分代码
进程进出临界区协议
临界区管理准则
1）择一而入：
- mutex的体现，互斥是相对于临界资源的进程排斥关系，一个进程在使用临界资源时，另一进程需等待，当前占用临界资源进程退出使用后，才能访问使用临界资源； 临界区空间，允许一个进程进入；
2）空闲让进：
- 当无进程在临界区，表明临界资源处于空闲状态，任何有权使用互斥区的进程可进入
3）忙则等待：
- 当已有进程进入临界区时表明临界资源正在被访问，其他必须等待，只能一个使用
4）有限等待：
- 进入临界区的进程应在有限时间内退出，以便让等待队列中的一个进程进入
- 对要求访问临界资源的进程应保证在有限时间内能进入自己的临界区，避免死等状态。
- 比如p4在临界区， p1、p2、p3一定是有限次的等待，p4 不可能无限制的停留在临界区中
5）让权等待，进程不进入临界区，释放处理去，防止“忙等”进程；针对while循环等待；
- 当进程不能进入临界区，立即释放处理机，避免进程陷入忙等状态
喂金鱼案例：
DAY1 喂金鱼：金鱼撑死了
临界区的划分：因为： no feed 读公共变量，操作公共数据 ，feed fish 也是在写公共变量 ，操作公共数据
交替执行：alice、tom并发执行，鱼被喂死了
第一天喂金鱼，没有对临界区进行任何的管理，比如说互斥操作违反择一而入管理准则
DAY2: 金鱼撑死了
进入区：
if（no note）{
leave a note；
临界区：
if（no feed）{
feed fish；
}
退出区：
remove note；
鱼还是撑死了，违反了择一而入的原则
DAY3：金鱼饿死了
违反了process的前进规则 ，临界区的有空让进问题
进入区： leave noteAlice if（no noteTom）
临界区： if（no noteTom） {feed fish}
退出去： remove noteAlice
DAY4： 鱼终于活下来了 。
协议发生变化。alice和tom执行的代码不一样，
alice中做了等待的动作，越来越解决了临界区管理的准则：
DAY5: 喂鱼成功
自旋锁:自旋时间短的话我们选择自旋
这边可以不看：
我们来了解一下O
锁的基本操作：
os阻塞与唤醒
oS中经典的生产者-消费者问题 （有时也称作有界缓冲区问题)
操作系统提供了一些原语，sleep 和 wakeup。
内核提供给核外调用的过程或者函数成为原语（primitive），原语在执行过程中不允许中断。
sleep 是一个将调用进程阻塞的系统调用，直到另外一个进程调用 wakeup 方法，将被阻塞的进程作为参数，将其唤醒。
阻塞与忙等待最大的区别在于，进程被阻塞后CPU将不会分配时间片给它，而忙等待则是一直在空转，消耗 CPU 的时间片。
OS中经典的生产者-消费者问题 （有时也称作有界缓冲区问题）
两个进程共享一个公共的固定大小的缓冲区。生产者，将信息放入缓冲区；消费者，从缓冲区中取出信息。（也可以把这个问题一般化为m个生产者和n个消费者问题，但是我们只讨论一个生产者和一个消费者的情况，这样可以简化解决方案。）
问题在于：
-
当缓冲区已满，而此时生产者还想向其中放入一个新的数据项时让生产者睡眠，待消费者从缓冲区中取出一个或多个数据项时再唤醒生产者。
-
同样地，当消费者试图从缓冲区中取数据而发现缓冲区为空时，消费者就睡眠，直到生产者向其中放入一些数据时再将其消费者唤醒。
为了避免忙等待，我们使用了sleep 和 wakeup原语
代码编写：
定义缓存区的大小，可容纳N件商品 ， 当前缓冲区商品的count，初始化=0；
生产者程序 ：生产一件商品，检查当前缓存区的商品数：
- 如果缓存区满了，就执行sleep进入阻塞状态，等待消费者来缓存区取数据，使得缓冲区count<N ,消费者唤醒生产者
- 否则将商品放入缓存区，将count加1.
- 判断count是否为1 ， 如果是，生产者就认为在自己生产之前，缓冲区的count为0 ，有消费者是睡在这个count=0 这个条件下面。 然后发起唤醒信号给消费者
消费者程序运行如下：
- 检查count是否为0，若是，则睡眠；
- 否则从缓冲区中取走一个并递减count的值。
- 最后判断count是否等于N-1
- 如果是，说明拿这件商品之前缓冲区为N.，有可能存在生产者来见到满缓存区而去睡觉。因此需要发送叫醒信号给生产者
含有严重竞争条件的生产者-消费者问题
#define N 100 /*缓冲区中的槽数目*/
int count = 0; /*缓冲区中的数据项数目*/
//producer
void producer(void)
{
int item;
while(TRUE){ /*无限循环*/
item = produce_item(); /*产生下一新数据项*/
if(count == N) sleep(); /*如果缓冲区满了，就进入休眠状态*/
insert_item(item); /*将（新）数据项放入缓冲区中*/
count = count + 1; /*将缓冲区的数据项计数器增1*/
if(count == 1) wakeup(consumer); /*缓冲区空吗？*/
}
}
//consumer
void consumer(void)
{
while(TRUE){ /*无限循环*/
if(count == 0) sleep(); /*如果缓冲区空，则进入休眠状态*/
item = remove_item(); /*从缓冲区中取出一个数据项*/
count = count - 1; /*将缓冲区的数据项计数器减1*/
if(count == N-1) wakeup(producer); /*缓冲区慢吗？*/
consume_item(item); /*打印数据项*/
}
}
这样的程序会有下面的问题：
问题1：生产者消费者 无效的发起wakeUp信号
问题2：临界资源竞争问题
这里有可能会出现竞争条件，其原因是对count的访问未加限制。
问题3：lost wake up 造成死锁问题 
有可能出现以下情况：缓冲区为空，消费者刚刚读取count的值发现它为0。
此时调度程序决定暂停消费者并启动运行生产者。生产者向缓冲区中加入一个数据项，count加1。现在count的值变成了1。它推断认为由于count刚才为0，所以消费者此时一定在睡眠，于是生产者调用wakeup来唤醒消费者。
但是，消费者此时在逻辑上并未睡眠，所以wakeup信号丢失。当消费者下次运行时，它将测试先前读到的count值，发现它为0，于是睡眠。生产者迟早会填满整个缓冲区，然后睡眠。这样一来，两个进程都将永远睡眠下去。
问题的实质在于发给一个（尚）未睡眠进程的wakeup信号丢失了。如果它没有丢失，则一切都很正常。
问题4： 加锁也会导致死锁
信号量与pv操作
信号量是Dijkstra在1965年提出的一种方法，它使用一个整型变量来累计唤醒次数，供以后使用。在他的建议中引入了一个新的变量类型，称作信号量（semaphore）。一个信号量的取值可以为0（表示没有保存下来的唤醒操作）或者正值（表示有一个或多个唤醒操作）。
Dijkstra建议设立两种操作：
down和up（分别为一般化后的sleep和wakeup）。 down 就是p 操作，up就是v操作
对一个信号量执行down操作（p）：
1》0 ---- -1 阻塞
(p可理解为pass,获得一个资源)
-
（1） sem减 1 ；
（2） 若sem减 1 后仍大于等于零，则请求的进程继续执行；
（3） 若sem减 1 后小于零，则进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。
检查数值、修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成。保证一旦一个信号量操作开始，则在该操作完成或阻塞之前，其他进程均不允许访问该信号量。
这种原子性对于解决同步问题和避免竞争条件是绝对必要的。所谓原子操作，是指一组相关联的操作要么都不间断地执行，要么不执行。
总而言之： 就是保证了，在同一个信号量的sleep 操作发生在 awake之前
-1 + 1 =0 唤醒
up操作对信号量的值增1。（v）
V原语操作的动作是：
(V可理解为Release,释放一个资源)
（1） sem*加 1 ；
（2） 若相加结果大于零，则请求的进程继续执行；【图中画错了】 条件应该是> 0
（3） 若相加结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后再返回原进程继续执行或转进程调度。
PV操作对于每一个进程来说，都只能进行一次，而且必须成对使用，在PV原语执行期间不允许有中断的发生。
如果一个或多个进程在该信号量上睡眠，无法完成一个先前的down操作，则由系统选择其中的一个进程（如随机挑选）并允许该进程完成它的down操作。
于是，对一个有进程在其上睡眠的信号量执行一次up操作后，该信号量的值仍旧是0，但在其上睡眠的进程却少了一个。信号量的值增加1和唤醒一个进程同样也是不可分割的
互斥信号量
down就是获取锁。up就是释放锁
1.mutex 二元变量，防止生产者和消费者同时对缓存区进行操作。保证了临界区的互斥。
-
mutex=1时 ，消费者首先获取cpu的执行权，执行p操作。p（mutex）之后mutex=0 ， 消费者准备执行消费操作时，如果此时消费者突然失去了时间片，即cpu调度生产者，生产者执行p操作mutex=-1 ，所以阻塞在mutex=-1的条件上，只有消费者执行v操作，把mutex信号量的值更新为0，此时消费者去唤醒生产者线程。
此时生产者被唤醒重新回到就绪状态等待被cpu选中，执行。。此时生产者一定会执行完v操作， 生产者执行v操作之前，
如果此时有消费者获取到cpu的执行权，不用怕。消费者执行p（mutex）=-1 还是会阻塞在mutex=-1 上面，阻塞的消费者继续等待生产者完成v操作唤醒消费者 。。。 如此。。。 简单就是说**p获取锁，v就是释放锁 ** ，
生产者消费者信号量代码
-
当缓冲区的大小为N时候，实际表示生产者可以生产N个，假设N=5时候，用变量full = 5
即：
生产者 ： 每进行一次p(empty）操作，insert_item 都会对full+1
p（empty）=》
empty： 4、3、2、1、0 ，
full : 0、1、2、3、4
消费者：
p（full） =》
full： 4、3、2、1、0
empty：0、1、2、3、4
full跟empty的关系就像是跷跷板, full=0 与 empty=0 的时候才会使得生产者消费者同时阻塞，这种情况不会出现。。。
消费者：
down（mutex） ---》上锁
down（full）--> down(0) --->阻塞在full=-1 下
生产者
down（empty）--》 当full=-1 表示需要生产者生产商品。所以empty 不可能等于0
即down（empty） 不阻塞向下 执行
此时 down（mutex）--》 mutex=-1 =》 所以阻塞在 mutex ，
此时生产者消费者都阻塞了，造成死锁
不会造成死锁，只是在临界区的代码多了一点。影响性能而已
管程：
重点： monitor 就是锁+条件变量
锁用来互斥
条件变量用来同步
比如说monitor中的活跃线程可能会释放等待线程的singnal ，这是什么意思呢？
就是monitor中因为条件不足而wait的线程被唤醒了，此时被唤醒线程的状态为就绪状态，
释放等待线程+ 被唤醒的线程 =2 monitor里面就有2个活跃的线程。但是释放等待线程 已经做完了对临界资源访问（读、写）的动作
即释放等待的线程 下一步操作以及在管程之外了
sleep、wakeup原语会导致信号丢失
我们知道Java的synchroinzed的实现方式是通过monitor管程，而之前介绍的sleep、wakeup因为无锁导致
消费者线程在判断是否睡觉和真的睡觉的两个操作存在空档，从而让生产者在此时切入执行，释放了 wakeup信号区唤醒消费者。
此时生产者释放的wakeup信号是无效的，因为消费者并没有真的睡觉，只是正准备睡觉，等到消费者真的睡觉了，生产者却没有信号唤
醒消费者了。。。 而缓冲区总有一天会被生产者放满，然后生产者也睡在缓存区满的条件上，
生产者也睡了，消费者也睡了，死锁产生！！！
Java中wait()方法为什么要放在同步块中
wait（）方法放到同步块中，是为了让该线程有锁，保证判断睡觉的操作跟真的睡觉的操作 具有原子性。
如果我们的wait（）方法没有放在同步块中，那就代表没有锁，那么就不能保证判断睡觉和真的睡觉的操作能一起完成。判断睡觉和真的睡觉中间会存在空档从而导致唤醒的信号量丢失，而且wait本身的原语就是释放锁， 如果没有在同步代码块中就没有锁，没有锁而却要释放锁是不是很搞笑！！！。。。。
那么 我们自己使用sleep&Wakeup+ mutex lock 来保证互斥会有什么问题吗？
#define N 100 /*缓冲区中的槽数目*/
int count = 0; /*缓冲区中的数据项数目*/
//producer
void producer(void)
{
int item;
while(TRUE){ /*无限循环*/
item = produce_item(); /*产生下一新数据项*/
lock();//2
if(count == N) sleep(); /*如果缓冲区满了，就进入休眠状态*/
unlock();
insert_item(item); /*将（新）数据项放入缓冲区中*/
count = count + 1; /*将缓冲区的数据项计数器增1*/
if(count == 1) wakeup(consumer); //3 /*缓冲区空吗？*/
}
}
//consumer
void consumer(void)
{
while(TRUE){ /*无限循环*/
lock();
if(count == 0) sleep();// 1 /*如果缓冲区空，则进入休眠状态*/
unlock();
item = remove_item(); /*从缓冲区中取出一个数据项*/
count = count - 1; /*将缓冲区的数据项计数器减1*/
if(count == N-1) wakeup(producer); /*缓冲区慢吗？*/
consume_item(item); /*打印数据项*/
}
}
这边有几个点需要大家知道：
首先生产者和消费者必须是上同一把锁，因为他们是争夺同一个临界资源。如果生产者和消费者使用不同的两把锁，肯定是违背了临界区管理准则。。。
并且 sleep 在睡眠的时候并没有释放锁的功能，那就是说
消费者在count==0 上面 阻塞，阻塞在代码段1上，此时消费者持有lock并没有释放lock,生产者根本就获取不到lock ，生产者也会阻塞在lock锁上，也就是代码段2 。。。
因为生产者阻塞它也就不能够执行代码3 唤醒消费者 。。。 哈哈 生产者第一步就把自己干懵逼了。。
问题：如果不使用信号量、不使用管程，使用互斥锁改变生成者消费者问题， 跟使用管程有什么区别呢？？？
区别在于wait的阻塞能够释放锁，但是sleep不能释放锁！！！后面再补充，这边只是我想的。。。。。。
lock跟wait一起用的场景能不能使用？？？ 我也要好好想一下 先到这里啦