操作系统之进程同异步、互斥

引入

异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。
但是在一定的条件之下，需要进程按照一定的顺序去执行相关进程：
举例说明1：

举例说明2:

读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据＞读数据”的顺序来执行的。所以需要解决这种异步的问题，就是进程同步所讨论的内容。

进程互斥软件实现方法

一、临界区

1、临界资源

2、临界区的控制结构

3、临界区遵循的四个原则

二、进程互斥

1、为什么要进程互斥？

假设进程A在执行程序的时候需要调度打印机的资源，但是调度到一半的时候，操作系统给A分配的时间片用完了，这个时候进程B上处理机，也需要使用打印机，这个时候如果进程不互斥的话，就会将A、B的内容混在一起；因此需要进程互斥；

2、单标记法
两个进程在访问临界区的时候，使用临界区的权限由使用完临界区的进程转交给下一个需要使用临界区的进程；


缺点：只能轮流访问，当进程A访问打印机临界区的时候，时间片使用完毕之后，退出处理机，这时候进程B进入处理机，同时进程B也需要访问打印机，但是这个时候打印机的标记只能给进程A使用，所以进程B只能干等待，等待A下一次进入并且使用完临界区的时候，自己才能进入临界区处理资源， 显然不符合临界区的空闲让进原则；

3、双标志前检查法

使用数组记录想进入临界区的意愿，当进程A进入临界区的时候，需要将自己的意愿数组赋值为TRUE，其他进程进入时候，会判断A进程是否已经进入临界区，如果已经进入则自旋等待，等待A进程执行完毕后，将自己的意愿变为false，这时候其他进程可以进入；

缺点：使用数组表示想进入临界区意愿，若按照 ①⑤②⑥③⑦…的顺序执行，PO 和 P1将会同时访问临界区。因此，双标志先检查法的主要问题是：违反“忙则等待”原则。原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后， “上锁”前可能发生进程切换。

4、双标志后检查法
通过先上锁，后进入的方式

缺点：如果并发执行的话，同时上锁会导致都进不了临界区，违反了空闲让进和有限等待的原则，使得进程长期无法访问资源而产生饥饿现象；

5、Peterson算法
结合双标志方法，如果双方都争着想进入临界区，那可以谦让。

虽然Peterson算法解决了进程互斥，遵循空闲让进，忙则等待，有限等待三个原则，但是未遵循让权等待。

进程互斥硬件实现方法

一、中断屏蔽方法

类似原语，用“开/关中断指令” 实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）

优点：简单、高效
缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中忻指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）

二、TestAndSet指令

简称TS 指令，也有地方称为 TestAndsetlock 指令，或TSL 指令，TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。相当于存在一个全局变量，利用全局变量的值来控制访问临界区，以下是用C语言描述的逻辑

若刚开始lock 是false，则TSL返回的old 值为false，while 循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是true，则执行TLS后old 返回的值为 true， while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行 “解锁”相比软件实现方法，TSL指令把 “上锁”和“检查” 操作用硬件的方式变成了一气呵成的原子操作。
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
缺点：不满足让权等待原则，不满足条件的时候会一直等待；

三、Swap指令

使用的方式TestAndSet一致，只是硬件层面实现不同，都是通过一个全局变量来控制是否能进入临界区；

四、互斥锁

特性：
•需忙等，进程时间片用完才下处理机，违反“让权等待”
•优点：等待期问不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低
•常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
•不太适用于单处理机系统，忙等的过程中不可能解锁

注：如果是多核的时候，一个进程自旋等待只会吃掉一个核，其他核访问完临界区之后，就会释放临界区，等待的进程也能进入临界区操作资源，但是在单核的时候，自旋的进程需要等待自己的时间片用完，并且等待使用临界区的进程上CPU释放临界区的资源才能继续使用临界区；

信号量机制

一、概述
1、由迪杰斯特拉提出信号量机制；
2、信号量是一种变量，表示系统中的一种变量；
3、使用一对原语来对信号量进行操作，wait（s）原语和signal（s）原语，可以把原语比做一个函数，括号里面的s其实就是函数调用的时候传入的一个参数；一般把原语简称为 P,V操作；

二、整型信号量
用一个整数表示系统资源的变量，用来表示系统中某种资源的数量

int S=1;
void wait(int S){ //wait原语，相当于：进入区while(S<=0);  //如果资源数不够，就意志循环等待S=S-1;        //如果资源数够，则占用一个资源
}void signal(int S){//signal原语，相当于“退出区”S=S+1;         //使用完资源后，在退出区释放资源
}

相当于通过一个整形变量上锁，但是如果一个进程占用了临界区的资源，另一个进程需要访问临界区的资源的时候，会等待上一个进程使用完资源，这个时候会一直忙等待；

三、记录型信号量
1、记录型的信号量增加了等待队列，当进程发现临界区的资源已经被别的进程占用的时候，将自己设置为阻塞状态，并且放入新增的等待队列中，等待临界区的释放被唤醒；

//记录型信号量的定义
typedef struct{int value;struct process *L;
} semaphore;
//某进程需要使用资源时，通过wait原语申请
void wait (semaphore S){S.value--;if(S.value<0){block (S.L);//将该进程加入到消息队列中}
}
//进程使用完资源后，通过signal原语释放
void signal (semaphore S){S.value++;if(S.valie<=0){wakeup(S.L);}
}

五、使用信号量机制实现互斥
1、实现进程互斥
设置互斥信号量mutex，初值为1，对不同的临界资源需要设置不同的互斥信号量，PV必须成对出现

2、实现进程同步
保证一前一后的操作顺序，设置同步信号量S，初始为0，在“前操作”之后执行V（S，在“后操作”之后执行（V）

3、实现进程的前驱关系
（1）要为每一对前驱关系各设置一个同步变量
（2）在“前操作”之后对相应的同步变量执行V操作
（3）在“后操作”之前对相应的同步变量执行P操作

前V后P：信号量代表了某种资源，P2执行的时候需要P1来释放这种资源，这样就限制了P1一定在P2的后面执行；

进程同步问题

一、生产者消费者问题
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待，只有缓冲区不空时，消费者才能从中取出产品，否则必须等待，缓冲区是临界资源，各个进程互斥访问，实现互斥的P操作要放在实现同步的P操作之后，不然会发生死锁，V操作不会导致进程发生阻塞的状态，所以可以交换，使用操作不要放在临界区，不然并发度会降低·

重点：生产消费问题为两个互斥同步的综合问题，需要两个信号量来控制；并且实现互斥的P操作一定需要在实现同步的P操作之后；

二、多生产者多消费者问题


三、吸烟者问题
解决“可以让生产多个产品的单生产者”问题提供一个思路；若一个生产者要生产多种产品（或者说会引发多种前驱事件），那么各个V操作应该放在各自对应的“事件”发生之后的位置

四、读者、写者问题

1、允许多个读者同时对文件执行读操作
2、只允许一个写者往文件中写信息
3、任一写者在完成写操作之前不允许其他读者或写者工作
4、写者执行写操作前，应让已有的读者和写者全部退出

1、直接全部加锁，但是不能读进程同步

2、加上count变量，第一个加锁即可


所以需要让对count的操作是互斥的

但是如果一直读进程进入的时候，写进程一直无法执行，导致饿死；所以在新增一个信号量w；用于实现写优先；当有写操作进入的时候，前面的读进程结束后就应该触发写进程了



最终代码逻辑：

semaphore rw=1;//用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count=0;//记录当前有几个读进程在访问文件
semaphore mutex=1;//用于保证对count变量的互斥访问
semaphore w=1; //用于实现“写优先”writer(){while(1){P（w）;P(rw); //写之前“加锁”写文件。。。V（rw);//写之后“解锁”V(w);}
}reader(){while(1){P(w);P(mutex);   //各读进程互斥访问countif(count==0) P(rw);  //第一个读进程的读进程数+1count++;	//访问文件的读进程数+1V(mutex);	V(w);读文件...P(mutex);	//各读进程互斥访问countcount--;	//访问文件的读进程数-1if(count==0)V(rw);	//最后一个读进程负责“解锁”V(mutex);}
}

五、哲学者进餐问题

五个人，必须拿左右的筷子才能吃饭避免死锁发生，解决方案：
1、可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐，这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。
2、要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一只后再等待另一只的情况。
3、仅当一个哲学家左右两只筷子都可用时才允许他抓起筷子

管程

心得：相当于C++的类，管程是数据放在private中，函数放在public中