进程同步和互斥
进程同步
进程具有异步性，异步性指的是各并发执行的进程以各自独立的、不可预知的速度向前推进
进程通信--管道通信
读、写进程并发的运行，由于并发必然导致异步性，因此读、写顺序的两个操作执行的先后顺序不确定，在实际应用中，又必须写数据-----读数据的顺序来执行
同步亦称直接制约关系，它指的是为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而产生的制约关系。进程间的直接制约关系就是源于他们之间的相互合作
进程互斥
互斥共享方式，把一个时间段内只允许一个进程使用的资源称为临界资源，许多物理设备都属于临界资源。此外，还有许多变量、数据、内存缓冲区等都属于临界资源
对临界资源的访问，必须互斥地进行。互斥、亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源后，另一个进程才能去访问临界资源
对临界资源的互斥访问，可以在逻辑上分为四个部分
进入区：负责检查是否可进入临界区，若可以，则应设置正在访问临界资源的标志（可以理解为上锁），以阻止其他进程同时进入临界区
临界区（临界段）：访问临界资源的代码
退出区：负责解除正在访问临界资源的标志（解锁
剩余区：做一些其他处理
为了保持对临界资源的互斥访问，同时保持系统整体性能，需要遵循：
1
空闲让进
临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
2
忙则等待
当已有进程进入临界区，没他试图进入临界区的进程必须等待
3
有限等待
对请求访问的进程，应保证在有限时间内机内临界区（保证不会饥饿）
4
让权等待
当进程不能进入临界区，应立即释放处理，防止进程忙等待
进程互斥的软件实现方法
单标志法
算法思想：
每个进程在访问完临界区后会把使用临界区的权限转给另一个进程。每个进程进入临界区的权限只能被宁另一个进程赋予
同一时刻最多只有一个进程访问临界区
单标志法的主要问题是违背空闲让进原则
双标志先检查法
算法思想:设置一个布尔型数组fagU,数组中各个元素用来标记各进程想进入临界区的意愿,比如
flag[]=ture”意味着0号进程PO现在想要进入临界区。每个进程在进入临界区之前先检查当前有
没有别的进程想进入临界区,如果没有,则把自身对应的标志flag设为true后开始访问临界
主要问题是忙则等待的原则，不符合互斥原则
原因在于进入区的检查和上锁两个处理不是一气呵成的，检查后，上锁前可能发生进程切换
双标志后检查法
是先检查法的改版，前一个是先检查后上锁，但这两个不能一气呵成，导致两个进程同时进入临界区的问题。因此用先上锁后检查的方法
虽然解决了忙则等待，但又违背了空闲让进和有限等待的原则，进程会因为长期无法访问临界资源产生饥饿现象
peterson算法
如果都想进，那就尝试孔融让梨，主动让对方先进入临界区
进程互斥的硬件实现方法
中断屏蔽方法
利用开关中断指令实现（与原语的实现思想相同，即在某个进程开始访问临界区到结束访问为止都不允许被中断，也不能发生进程切换，因为不可能同时发生两个同时访问临界区的情况
关中断即不允许当前进程被中断，也必然不会发生进程切换
直到当前进程访问完临界区，在执行开中断指令，才可能有别的进程上处理机并访问临界区
优点：简单、高效
缺点：不适合多核处理机，只适用于操作系统内核进程，不适用于进程用户（因为开、关中断指令只能运行在内核态，这组指令让用户执行随意起来会很危险）
TestAndSet指令
简称TS，或者TSL指令
是用硬件实现的，执行的过程不允许被中断，只能一气呵成
缺点：不满足让权等待，暂时无法进入临界区的进程会占用cpu并循环执行TSL，从而导致忙等
swap指令
又叫Exchange或者XCHG指令
硬件实现的，执行的过程中不允许被中断，只能一气呵成
和TSL无太大区别
信号量机制
信号量机制有两种
整形信号量、记录型信号量
用户进程通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步
信号量其实就是一个变量(可以是一个整数,也可以是更复杂的记录型变量),可以用一个信号量来表示系统中某种资源的数量,比如:系统中只有一台打印机,就可以设置一个初值为1的信号量。
原语是一种特殊的程序段,其执行只能一气呵成,不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”,因此如果能把进入区、退出区的操作都用“原语”实现,使这些操作能“一气呵成”就能避免问题。
一对原语指的就是wait(S)和signal(S)原语，可以把理解为自己写的函数，括号内的信号量S就是函数调用时传入的一个参数
wait、singal可以简称为PV操作，可以把wait(s)、signal(S)两个操作分别写为P(S)V(S)
整形信号量
用一个整数来表示系统某个资源的数量
与普通整数变量的区别：对信号量的操作只有三种，即初始化、P操作、V操作
记录型信号量
解决整形信号量的缺陷存在的忙等的问题，即用记录型数据结构表示的信号量
某个进程需要使用资源时，通过wait原语申请
用信号量机制实现进程一些关系
信号量机制实现进程互斥
1、先分析并发进程的关键活动，划定临界区(如：对临界资源打印机的访问就在临界区)
2、设置互斥信号量mutex，初始值为1
3、在临界区前执行P(mutex)
4、在临界区后执行V(mutex)
对不同的临界资源需要设置不同的互斥信号量，就像摄像头、打印机是不同的信号量
P 、V必须成对出现，缺少P不能保证临界资源的互斥访问。缺少V会导致资源永不被释放，等待进程永不被唤醒
进程同步：要让各个并发进程按要求有序的推进
分析什么地方要实现同步关系，保证一前一后
设置同步信号量S，初始为0
在前操作之后执行V(S)
在后操作之前执行P(S)
信号量机制实现前驱关系
每一对前驱关系都是一个进程同步问题
1、为每一对前驱关系设置一个同步变量
2.在“前操作”之后对相应的同步变量执行V操作
3.在“后操作”之前对相应的同步变量执行P操作
生产者消费者问题
系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用。(“产品”理解为某种数据)
生产者、消费者共享一个初始为空、大小为n的缓冲区
只有缓冲区没满时，生产者才能把产品放在缓冲区、否则必须等待
只有缓冲区不空时,消费者才能从中取出产品,否则必须等待。
缓冲区属于临界资源、各进程必须互斥的访问
如何实现
顺序颠倒的限制性p(empty)操作再执行p(mutex)会对出现死锁现象，两类进程都无法进行
因此，实现互斥的P操作一定要在实现同步的P操作之后
V操作不会造成进程阻塞，因此两个·V操作顺序可以交换
把使用产品放在临界区，会造成短暂性的进程堵塞时间增长，从而导致进程的并发度降低
多生产者-多消费者
多指的时多类
当缓冲区为一、上不上锁都一样
如果大于1的缓冲区，就必须设置一个互斥信号量mutex互斥访问缓冲区
吸烟者问题
差不多，2333
读者写者问题
①允许多个读者可以同时对文件执行读操作:②只允许一个写者往文件中写信息:;③任一写者在完成写操作之前不允许其他读者或写者工作;④写者执行写操作前,应让已有的读者和写着全部退出，这样不会造成数据出现错误
先分析关系、找之间的互斥和同步
‘两类进程：写进程、读进程
互斥关系：写写进程、读写进程，但读读进程之间不存在互斥问题
整理思路。根据操作确定P、V操作的大致顺序
设置信号量。设置需要的信号量，根据题目确定信号量的初始值
潜在问题：如果一个读者一直在读进程，写进程就要等待，一直等待，就会被饿死
如何修改
重点
其实没那么死板直接就看这个，其他的也行
哲学家问题
造成死锁现象
理解死锁现象就行
管程
信号量机制会造成编写程序困难、易出错
管程是一种高级的同步机制
管程是一种特殊的软件模块，有一些部分组成
1.局部于管程的共享数据结构说明
2.对该数据结构进行操作的一组过程
3.对局部于管程的共享数据设置初始值的语句
4.管程有一个名字
过程就是函数其实
管程的基本特征
局部于管程的数据只能被局部于管程的过程所访问
一个进程只有通过调用管程内的过程才能进入管程访问共享数据
每次仅允许一个进程在管城内执行某个内部过程
引入管程就是方便实现进程的同步和互斥
1.需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
2.需要在管程中定义用于访问这些共享数据的“入口”ーー其实就是一些函数(如生产者消费者问题中,可以定义一个函数用于将产品放入缓冲区,再定义一个函数用于从缓冲区取出产品)
3.只有通过这些特定的“入口”才能访问共享数据
4.管程中有很多“入口”,但是每次只能开放其中一个“入ロ”,并且只能让一个进程或线程进入(如生产者消费者问题中,各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证个时间段内最多只会有一个进程在访问缓冲区。注意:这种互斥特性是由编译器负责实现的,程序员不用关心)
5.可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待(此时,该进程应先释放管程的使用权,也就是让出“入口”):可以通过唤醒操作将待在条件变量上的进程或线程唤醒
程序员可以用某种特殊的语法定义一个管程(比如: monitor Producerconsumer....end monitor;),然后其他人就可以根据入口方便的实现同步和互斥
