操作系统进程的同步

操作系统中进程的同步管理机制以及经典同步问题，包含基本概念、硬件同步机制、信号量机制、管程机制等内容。

进程的同步

• 基本概念
  • 引入的原因
    • 进程的异步性(进程的走走停停)。
  • 同步的主要任务
    • 多个进程次序上的协调。按一定规则共享资源、并能相互合作。是程序的执行具有可再现性。
  • 同步机制(3种)
    • 信号量机制硬件同步机制管程机制
  • 进程间存在的两种制约关系
    • 资源共享关系(间接制约的关系)进程能互斥地访问临界资源。资源又由操作系统统一分配。不允许用户进程直接使用。进程通过资源间接制约其它资源相互合作关系(直接制约关系)前趋图的关系。进程执行次序上的协调。
  • 临界资源
    • 在某段时间内只允许一个进程使用的资源。eg:(硬件资源)打印机、磁带机，(软件资源)变量、文件。进程之间互斥访问。实现对临界资源的共享
  • 临界区
    • 每一个进程访问临界资源的那段代码。进程互斥的进入自己的临界区，就可保证互斥访问。
  • 互斥访问的基本思想
    • 访问临界区前先检查临界资源是否被访问未访问，则进入，并设置其为正在访问标识若正访问，则不进入 因此一个多了一个进入区来检查临界资源访问情况多了一个退出区，将访问标志改回去 伪代码：repeat 进入区//进入前的检测(用于对临界资源的访问检查) 临界区 退出区//退出后的指示(将访问标志改为未访问) 剩余区until false；
  • 同步机制的四条准则
    • 空闲让进(空闲时进程可以进)忙则等待(忙碌的时候进程等待)有限等待(有限时间内访问临界资源，以免陷入死锁)让权等待：进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”。
  • 解决互斥问题的软件方案(4)
    • 设置访问编号
      • 设置一个全局变量记录访问临界值的进程。 伪代码：//主程序描述框架unsigned turn = i;//（全局变量）main(){ cobegin//并发开始 pi;//pi与pj并发 pj; coend}//进程pi{ repeat //进入区(进入前的检测) while turn<>i do no_op;//turn不等于i，就没有操作 临界区 //退出区(退出后的指示) turn=j; 剩余区 until false；}//进程pj{ repeat //进入区(进入前的检测) while turn<>j do no_op;//turn不等于i，就没有操作 临界区 //退出区(退出后的指示) turn=i; 剩余区 until false；} 但是以上方法违背了让权等待和空闲让进。因为默认i有优先权，i可以执行，但是i因为其他原因无法执行时，j也不可执行。也就是没有让权等待。操作系统一直空闲，j却依旧不能进，违背了空闲让进。 不可能两边同时执行，不违背忙则等待。也不可能同时等待。至少最初i先开始，可以不用等待。所以不违背有限等待。
    • 设置访问标志
      • 相对于第一种方式。设置两个全局变量flag，表示两个进程是否能访问。初始都为false 伪代码：//主程序描述框架bool flagi=flagj=false;//（全局变量）main(){ cobegin//并发开始 pi;//pi与pj并发 pj; coend}//进程pi{ repeat //进入区(进入前的检测) while flagj do no_op;//flagj=true，就没有操作 flagi=true; 临界区 //退出区(退出后的指示) flagj=false; 剩余区 until false；}//进程pj{ repeat //进入区(进入前的检测) while flagi do no_op;//turn不等于i，就没有操作 flagj=true; 临界区 //退出区(退出后的指示) flagj=false; 剩余区 until false；} 但是这个依旧不能让权，违背了让权等待。而且当两个进程同时判断，同时进入，同时访问，则违背了忙则等待。 因为判断条件变成了对方的访问控制标志。只要对方没有访问，自己就可以访问，不违背空闲让进。也不肯能双方都被迫陷入等待，不违背限时等待。
    • 设置与访问标志
      • 与设置访问标志不同的是，进程进入时在检查访问标识之前都抢先将标志改为自己。也就避免了同时进，实现了忙则等待。 伪代码：//主程序描述框架bool flagi=flagj=false;//（全局变量）main(){ cobegin//并发开始 pi;//pi与pj并发 pj; coend}//进程pi{ repeat //进入区(进入前的检测) flagi=true; while flagj do no_op;//flagj=true，就没有操作 临界区 //退出区(退出后的指示) flagj=false; 剩余区 until false；}//进程pj{ repeat //进入区(进入前的检测) flagj=true; while flagi do no_op;//turn不等于i，就没有操作 临界区 //退出区(退出后的指示) flagj=false; 剩余区 until false；} 违背了让权等待、空闲让进(两边都同时设置为true，都不能进)、有限等待(两边都在等待，进入死锁状态)因为双方不可能同时进入，所以不违背忙则等待。
    • person算法
      • 即为设置访问编号与设置访问标志的结合体。 伪代码：//主程序描述框架bool flagi=flagj=false;unsigned turn;//（全局变量）main(){ cobegin//并发开始 pi;//pi与pj并发 pj; coend}//进程pi{ repeat //进入区(进入前的检测) flagi=true; turn=j; while (flagj && turn==j) do no_op;//flagj=true，就没有操作 临界区 //退出区(退出后的指示) flagj=false; 剩余区 until false；}//进程pj{ repeat //进入区(进入前的检测) flagj=true; turn=i; while (flagi && turn==i) do no_op;//turn不等于i，就没有操作 临界区 //退出区(退出后的指示) flagj=false; 剩余区 until false；} turn用于实现空闲让进(他直接将权让给对方)。当pi执行了第一个赋值语句后，立即执行pj的赋值语句。如没有turn则两边都要等待。但若是turn=j后，pi依旧可以运行，pj等待。如果同时进入的话，因为turn只有一个变量，后面的会覆盖前面的，总有一个让权另一个，所以不可能同时执行，不违背忙则等待也因为总有一个让权给另一个，所有不可能两边都在死等，不违背限时等待违背了让权等待，若一个进程进入了临界区，但是却缺少资源而阻塞，另一个进程也无法在进去。
• 硬件同步机制
  • 关中断
    • 原理：锁测试和上锁期间关中断。进程在临界区时就不会发生线程或进程的切换，保证了互斥。
    • 缺点(3)
      • 滥用关中断权力可能导致严重后果关中断时间长，系统效率降低关中断只能限制一个处理机，多处理机的不适用
  • 利用Test-and-Set指令实现互斥
  • 利用Swap指令实现互斥
• 信号量机制
  • 整型信号量
    • 一个用于表示资源数目的整型量s。仅能通过原子操作wait(s)（申请资源）、signal(s)(释放资源)进行访问。也称为P、V操作。 伪代码：wait(s){//申请资源后资源减少 while(s<=0) do no_op;//无资源无操作 s--;//资源数} signal(s){ s++;} 但是仍旧无法实现让权等待。临界区的一个进程因为资源不够，进入阻塞。但是其它进程无法进入。
  • 记录型信号量
    • 借助一个阻塞链表实现了让权等待 结构体：typedef struct{ int value;//资源数目 struct process_control_block *list;//阻塞链表}semaphore; wait(semaphore s){ s.value--; if(s.value<0){//资源不够就放入阻塞列表 block(s.list); }}/*s.当value<0之后，value的绝对值是阻塞队列中的进程个数*/ signal(semaphore s){ s.value++;//阻塞队列中进程减少 if(s.value<=0){//阻塞队列中还有进程 wakeup(s.list);//这就让一些进程继续执行 }} 因为一旦开始释放，阻塞列表的进程就开始执行，也就实现了让权等待。
  • AND型信号量
    • 缺少那个资源就把他放在哪个资源的阻塞队列中 Swait(semaphore s1,s2,...,sn){ while(TRUE){ if(s1.value>=1 &&...&& sn.value>=1){ for(i=1;i<=n;i++){ si.value--; } break; } else{ /*找到第一个si<1时，重置程序计数器，把这个进程放在si的阻塞队列中*/ } }} signal(semaphore s){ while(TRUE){ for(i=1;i<=n;i++){ si.value++; /*把进程放入就绪队列*/ } }}
    • 引入
      • 当两个进程都拥有一部分资源，但还需要的一些资源被对方占有，双方都无法运行，造成死锁。
  • 信号量集
    • 与AND信号量集的区别是，他多了一个量，所需的每个资源不只一个，即每个资源所需量tn一次需要N个某类临界资源资源数量就有一个下限值t(大于t时才可分配)，进程需要d个 伪代码：semaphore s1,s2,...,sn;Swait(s1,t1,d1,...,sn,tn,dn){ while(TRUE){ if(s1.value>=t1 &&...&& sn.value>=tn){//条件函数不一样 for(i=1;i<=n;i++){ si.value-=di; } break; } else{ /*找到第一个si<t1时，重置程序计数器，把这个进程放在si的阻塞队列中*/ } }} signal(semaphore s1,s2,..,sn){ while(TRUE){ for(i=1;i<=n;i++){ si.value+=di; /*把进程放入就绪队列*/ } }}
  • 信号量的应用
    • 刚好可以解决进程之间存在的两种制约关系
    • 实现互斥
      • 设置一个互斥信号mutex=1。//说明资源只有一个 /*主程序*/int mutex=1;//资源信号量int main(){ cobegin pi; pj; coend}pi/pj:{ repeat//循环 wait(mutex);//mutex就代表临界资源 critical section//进入临界区 signal(mutex); remainder section//剩余区 until false; }
    • 实现前驱关系
      • 进程p1，p2，执行s1、p1执行完s1后p2再执行s2 伪代码：/*主程序*/int s=0;int main(){ cobegin p1; p2; coend;}p1:{ s1; signal(s);//释放s}p2:{ wait(s);//申请s s2;}
• 管程机制
  • 引入原因
    • 信号量虽好，但是大量的同步操作分散在各个进程中，系统的管理会很麻烦
  • 思想
    • 利用共享数据结构抽象表示系统中的共享资源。将共享数据结构实施的操作定义为一组过程
  • 定义
    • 资源管理模块：代表共享资源的数据结构+实施操作的一组过程。
  • 组成
    • 管程名字局部于管程的共享数据结构的说明对该数据结构的一组操作对管程的数据设置初始化语句
• 经典同步问题
  • 生产者与消费者
    • 进程次序
      • 输入时：输入进程时生产者，计算进程时消费者。输出时：计算进程是生产者，输出进程是消费者。
    • 同步措施
      • 在生产者与消费者直接设置有n个缓冲区的缓冲池，——相当于一个循环队列生产的数据放入缓冲池，消费者从缓冲池中拿数据 缓冲区分为：满缓冲区、空缓冲区 缓冲区也是临界资源
    • 互斥
      • 生产者与消费者互斥生产者之间互斥消费者之间互斥
    • 伪代码
      • /*全局变量*/typedef struct{//循环缓冲表 ...} item; item buffer[n];int in=out=0;//in指针,out指针 in=(in+1)%n out=(out+1)%nitem nextp,nextc;//每次要生产、消费的产品semphore mutex=1；//互斥信号量，初始为1semphore empty=n,full=0//资源信号量/*主程序*/void main(){ cobegin producer1;...producerm; consumer1;...consumern; coend}/*生产者*/produceri:{ repeat produce an item in nextp; wait(empty);//空缓冲区减少 wait(mutex); //Swait(empty,mutex); //使用and信号量。多个资源一同申请，防止死锁。不用考虑先后顺序 buffer[in]=nextp; in=(in+1)%n; signal(mutex); signal(full); //生产过后要去通知消费者，满缓冲区增加 //Ssignal(mutex,full); //and信号量释放 until false;}/*消费者*/consumerj:{ repeat wait(full);//满缓冲区减少 wait(mutex); //Swait(full,mutex); //使用and信号量。 nextc=buffer[out]; out=(out+1)%n; signal(mutex); signal(empty); //通知生产者空缓冲区增加 //Ssignal(mutex,empty); //and信号量释放 consumer the item in nextc; until false;} 注意：wait不能互换(不然可能要死锁，获得了metux钥匙，但是缓冲区不为空还是不能生产，消费者没钥匙不能消费)，signal可以互换。
  • 读者与写者
    • 互斥
      • 对某一数据区(可共享)的读取和写入操作。读的过程不可以写，写的过程不可以读。多个读进程可同时读。只有一个写进程只能它一个访问写进程在写的时候，禁止任何读进程写入写进程在写之前让其它进程退出用一个程序计数器来记录读进程的个数
    • 信号量的设计
      • 写互斥信号量：wmutex=1读者进程计数器：readcount=0💣对readcount(为临界资源)的互斥访问：rmutex=1.（只要多个进程对某一数据进行改写，就需要互斥，不然会导致数据的不可再现性）readcount=0时，才能写，才需申请wmutex。读之前需要申请wmutex。读一个readcount+1。
    • 伪代码
      • int readcount=0;semaphore wmutex=1,rmutex=1;main(){ cobegin read1,read2,..... write1,write2.... coend}write{ repeat wait(wmutex); perform write operation; signal(wmutex); until false;}read{ repeat wait(rmutex); if(readcount==0) then wait(wmutex);//如果没有读进程，就申请写信号量，避免写进程执行。加一个条件避免重复申请。 readcount++; signal(rmutex);//可以读了，就释放，便于其它读进程读。 perform read operation; wait(rmutex); readcount--; if(readcount==0) then signal(wmutex);//通知写进程，可以写了 signal(rmutex); until false;}
  • 哲学家进餐
    • 描述
      • 五个哲学家，在一张圆桌上，桌上五支筷子，分别位于哲学家的左右两边。哲学家只有同时拿到两支筷子才能吃。因为拿到两支才能吃，所以左右两支筷子都设一个信号量。
    • 伪代码
      • semaphore chopshick[0,...,4]={1,1,1,1,1};//筷子信号量数组main(){ cobegin philosopy0; philosopy1; philosopy2; philosopy3; philosopy4; coend} philosopyi:{ repeat think; wait(chopstick[i]); //申请左边筷子 wait(chopstick[(i+1)mod5]); //右边 eat; signal(chopstick[i]); signal(chopstick[(i+1)mod5]); until false;} 但是当哲学家都同时拿起左边筷子的时候，就会陷入死锁。
    • 死锁解决办法
      • 当哲学家左右两支筷子均可使用时，才允许拿起筷子规定奇数号哲学家先拿左边筷子，偶数号先拿右边至多允许四个人同时拿起筷子，这样至少一个人可以吃或者使用and信号量解决philosopyi:
{
   repeat think;
  Swait(chopstick[i],chopstick[(i+1)mod5]);
  eat;
  Ssignal(chopstick[i],chopstick[(i+1)mod5]);
   until false;
}