OS Chapter 3 Inter-Process Communication ~ Codeless

Race Condition 竞争条件/竞态

竞态

定义：

两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件（race condition）
two or more processes are reading or writing some shared data and the final result depends on who runs precisely
临界区
需要互斥（mutual exclusion）
临界区：对共享内存进行访问的程序片段称为临界区域（critical region/critical section）
临界资源（Critical Resource）：文件，内存、信号量

避免竞态的条件

任何两个进程不能同时处于其临界区
不应对CPU的速度和数量做任何假设
临界区外运行的进程不得阻塞其他进程
不得使进程无限期等待进入临界区

Mutual Exclusion 进程互斥

当进程在临界区中更新共享内存时，其他进程将不会进入临界区

屏蔽中断（硬件/物理解决方式）

每个进程刚进入临界区后就立即屏蔽所有中断，并在离开之前打开中断。
CPU只有发生时钟中断或者其他中断才会切换进程，这样一来就不会进行进程切换了。
所以，进程屏蔽中断之后，他就可以检查和修改共享内存，而不必担心其他进程介入
缺点：把屏蔽中断的权利交给用户程序是不明智的，因为一旦不再打开中断，就会造成严重的后果。
屏蔽中断对于操作系统本身而言是一项很有用的技术，但对于用户进程则不是一种合适的通用互斥机制。

锁变量（软件解决方式）

设定一个信号量，锁定变量，初始位0，当程序进入临界区，如果0就可以进入，然后把值设置为1。如果是1，就等待直到值变为0。
0表示临界区没有进程，1表示已经有某个进程进入临界区
缺点：也会出现假脱机类似的问题，即A读出0，并在将其设定为1之前，程序B读出信号量也是0，就出现问题了。

严格轮换法

设定整型变量turn，初始值0，a执行进入临界区后turn设定为1，b执行进入临界区后turn设定为0，在一个等待循环中不断测试turn，直到某个值出现，称为忙等待（busy waiting），浪费CPU时间，通常避免。
仅在确定等待时间非常短的情况下才使用忙等待，忙等待的锁称为自旋锁（spin lock）
严格要求两个进程轮流进入临界区，违反了条件3（A进入后，不管B有没有进入，都得等B进入一次后才能再次进入）。

Peterson Solution

各进程用其进程号（0/1）作为参数调用enter_region，调用后将turn这是为进程号，然后直到等另一个进程（other）的interested[other]变为FALSE之后，才进入进程。

TSL指令（硬件方案）

TSL RX，LOCK
测试并加锁（Test and Set Lock），将内存字lock读入寄存器RX，然后后在该地址存非零值，保证读字和写字操作不可分割。
（与屏蔽中断不同，屏蔽中断并不能解决多核心问题，因为对于CPU1屏蔽，CPU2没有任何影响，让CPU2远离内存的唯一方法就是锁住总线，就需要硬件）

还有一个XCHG指令，原子性的交换了讲个位置的内容，如一个寄存器与一个存储器字

会出现优先级反转问题（priority inversion problem），高优先级的程序被低优先级的程序抢占。

生产者-消费者问题（Producer-Consumer Problem）//互斥操作要放在同步操作之后

有界缓冲区问题（bounded-buffer）
两进程共享公共固定缓冲区，一个生产者，一个消费者。
添加唤醒等待位，解决wakeup信号丢失的问题，如果一个唤醒等待为

信号量 Semaphore

down：对信号量操作，检查是否大于0，如果大于0，则减一，如果为0，则进程睡眠。
up：对信号量增1，如果处于睡眠，无法down，则系统选择一个程序允许弯沉down。如果up后仍然是0，但其仍处于睡眠状态，则睡眠少一个。

二元信号量（binary semaphore）：供两个或多个进程使用的信号量，其初值为1，保证同时只有一个进程可以进入临界区，称作二元信号量

互斥量 mutex

信号量的简化版，处于两态之一的变量：解锁、加锁。0表示解锁，其他所有值表示加锁。
线程/进程访问临界区时，调用mutex_lock，如果临界区可用，则调用成功，线程进入临界区。如果临界区不可用，则等待，直到临界区中的线程调用mutex_unlock，如果有多个等待，则随机选择一个，允许获得锁。
enter_region进入临界区失败会忙等待，而mutex_lock失败会调用thread_yield将CPU放弃给另一个线程。当该线程再次运行时候，则再进行一次锁测试。
上锁调用mutex_trylock，可以选择成功操作，或者失败了采取什么操作。