进程管理_3
目录进程同步、进程互斥
什么是进程同步
进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。
读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据→读数据”的顺序来执行的。
如何解决这种异步问题，就是“进程同步”所讨论的内容。同步也称作直接制约关系，他是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而产生的制约关系。进程间的直接制约关系就是源于他们之间的相互合作。
什么是进程互斥
进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源（eg：内存，打印机、摄像头这样的I/O设备）
两种资源共享方式：
- 互斥共享方式：一个时间段内只允许一个进程访问该资源。
- 同时共享方式：允许一个时间段内由多个进程“同时”对他们进行访问。（同时指的是宏观上）
临界资源：一个时间段内只允许一个进程使用的资源称为临界资源。
许多物理设备：（比如摄像头、打印机）都属于临界资源，此外还有许多变量、数据、内存缓冲区等都属于临界资源。
对于临界资源的访问，必须互斥的进行。
互斥，也称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。
为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：
- 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区：
- 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
- 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
- 让权等待。当进程不能进入临界区时，应当立即释放处理机，防止进程忙等待。
进程互斥的软件实现方法
- 理解各个算法的思想、原理
- 结合上小节学习的“实现互斥的四个逻辑部分”，理解各个算法在进入区、退出区都做了什么？
- 分析各算法存在的缺陷（结合“实现互斥要遵循的四个原则”进行分析）。
单标志法(严格轮转法)
- 算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。
原理：
int turn = 0;//turn 表示允许进入临界区的进程号
//p0进程
while （turn ！= 0）；
critical section;
turn = 1;
remainder section;
//p1进程
while （turn ！= 1）；
critical section;
turn = 0;
remainder section;
缺点：只能按P0→P1→P0→P1→…这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是P0,而P0一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问。因此，单标志法存在的主要问题是：违背“空闲让进”原则。
双标志先检查
算法思想：设置一个布尔型数组flag[],数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0]=ture”意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[]设为true,之后开始访问临界区。
bool flag [2];
//表示进入临界区意愿的数组
flag[0]=false;
flag[1]=false;
//刚开始设置为两个进程都不想进入临界区
//P0进程： P1进程：
while (flag[1]);① while (flag [0]);⑤
//如果此时P0想进入临界区，P1就一直循环等待
flag[0]=true;② flag[1]=true;⑥
//标记为P1进程想要进入临界区
critical section;③ critical section;⑦
//访问临界区
flag[0]=false;④ flag[1]=false;⑧
//访问完临界区，修改标记为P1不想使用临界区
remainder section; remainder section;
若按照152637的顺序执行的话，P0和P1会同时访问临界区。
主要问题是：违反了“忙则等待”原则。
原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。
双标志后检查
1526的顺序执行的话，P0和P1将都无法进入临界区
因此，双标志后检查法虽然解决了“忙则等特”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。
Peterson算法
算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。
背后的含义：“表达意愿”
bool flag[2];//表示进入临界区意愿的数组，初始值都是false
int turn= 0;//turn表示优先让哪个进程进入临界区表达“谦让”
//P0进程：
//进入区
flag[0]=true;①
turn=1;②
while (flag[1]&turn==1);③
critical section;④
flag[0]=false;⑤
remainder section;
P2进程：
flag[1]=true;⑥
//表示自己想进入临界区
turn= 0;⑦//可以优先让对方进入临界区
while (flag[0]&turn==0);⑧//对方想进，且最后一次是自己“让梨”，那自己就循环等待
critical section;⑨
flag[1]=false;//访问完临界区，表示自己已经不想访问临界区了
remainder section;
Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。Peterson算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。
进程互斥的硬件实现方法
中断屏蔽方法
利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)。
- 优点： 简单高效
- 缺点：不适用于多处理机：只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险。）
TestAndSet指令
简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令。
TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑。
- 相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞：适用于多处理机环境。 - 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
Swap指令
逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否己经被上锁（记录在old变量上)，再将上锁标记lock设置为true,最后检查old,如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。
- 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境.
- 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
互斥锁
解决临界区最简单的工具就是互斥锁(mutex lock)。一个进程在进入临界区时应获得锁：
在退出临界区时释放锁。函数acquire()获得锁，而函数release()释放锁。
每个互斥锁有一个布尔变量available,表示锁是否可用。如果锁是可用的，调用acqiure（）会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。acquire(或release(O的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。
互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用acquire()。当多个进程共享同一CPU时，就浪费了CPO周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。
需要连续循环忙等的互斥锁，都可称为自旋锁(spin lock),如TSL指令、swap指令、单标志法。
特性：
- 需忙等，进程时间片用完才下处理机，违反“让权等待”
- 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低
- 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
- 不太适用于单处理机系统，忙等的过程中不可能解锁
信号量机制
问题：
1.在双标志先检查法中，进入区的“检查”、“上锁”操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题：
2.所有的解决方案都无法实现“让权等待”。Dijkstra提出了信号量机制。
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。
原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
一对原语：wait(S)原语和signal((S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal,,括号里的信号量S其实就是函数调用时传入的一个参数。
wait、signal原语常简称为P、V操作（来自荷兰语proberen和verhogen)。因此，做题的时候常把wait(S以、signal(S)两个操作分别写为P(S)、V(S)
整型信号量
用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。
- 存在的问题：不满足“让权等待”原则，会发生“忙等”
记录型信号量
整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。
对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此需要执行S.value-,表示资源数减1，当S.vaue<0时表示该类资源已分配完毕，因此进程应调用bock原语进行自我阻塞（当前运行的进程从运行态→阻塞态)，主动放弃处理机，并插入该类资源的等待队列SL中。可见，该机制遵循了“让权等待”原则，
不会出现“忙等”现象。对信号量S的一次V操作意味着进程释放一个单位的该类资源，因此需要执行S.value++,表示资源数加1，若加1后仍是S.value<=0,表示依然有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态→就绪态）
用信号量实现进程互斥、同步
互斥：
- 分析问题，确定临界区
- 设置互斥信号量，初值为1
- 临界区之前对信号量执行P操作
- 临界区之后对信号量执行V操作。
同步：
- 分析问题，找出哪里需要实现“一前一后”的同步关系。
- 设置同步信号量，初始值为0
- 在前操作之后执行V操作。
- 在后操作之前执行P操作。
生产者-消费者问题
系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）
生产者、消费者共享一个初始为空、大小为的缓冲区。
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
只有缓冲区不空时，消费者才形从中取出严品，合则必须等待。
缓冲区是临界资源，各进程必须互斥地访问。
- 能否改变相邻的P,V操作的顺序？
不能颠倒，实现互斥的P操作一定要在实现同步的P操作之后，V操作不会导致进程阻塞，因此两个V操作顺序可以颠倒。
- 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
- 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
- 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为1,同步信号量的初始值要看对应资源的初始值是多少)
多生产者-多消费者问题
解决：
总结：在生产者-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。
建议：在考试中如果来不及仔细分析，可以加上互斥信号量，保证各进程一定会互斥地访问缓冲区。但需要注意的是，实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”。
重要：
比如，如果从单个进程行为的角度来考虑的话，我们会有以下结论：
如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果
这么看是否就意味着要设置四个同步信号量分别实现这四个“一前一后”的关系了？
正确的分析方法应该从“事件”的角度来考虑，我们可以把上述四对“进程行为的前后关系”抽象为一对“事件的前后关系”
盘子变空事件→放入水果事件。“盘子变空事件”既可由儿子引发，也可由女儿引发；“放水果事件”既可能是父亲执行，也可能是母亲执行。这样的话，就可以用一个同步信号量解决问题了。
从事件的角度出发去考虑问题
吸烟者问题
问题：
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟)。
本质上这题也属于“生产者-消费者”问题，更详细的说应该是“可生产多种产品的单生产者-多消费者”。
分析：
实现：
