第3章-进程同步、互斥与信号量（4）

亦凉 2024-03-30 17:14 104阅读 0赞

进程同步、互斥与信号量

### 0 引言 ###

操作系统的并发进程有些是独立的，有些需要相互协作。独立的进程在系统中执行时不受其他进程的影响，而另一些进程需要与其他进程共享数据，来完成共同的任务，这些进程之间具有协作关系。但我们要保证这种协作的时间顺序性，以便于让进程正常运行。  
在单处理机多道程序环境系统中，进程表现出并发的特征，在一段时间内交替的对进程进行切换执行，但由于并发执行的进程之间的相对速度不可预测，即不确定性，取决于其他进程的活动、操作系统的调度策略等。因此我们保证进程同步，让进程的事件存在某种时序关系下运行。

### 1 进程同步与互斥 ###

##### 1.1 进程之间的协作关系（互斥、同步、通信） #####

互斥：多个进程不能同时使用同一资源。  
同步：指多个进程中发生的事件存在着某种时序关系，它们必须按规定时序执行，以共同完成一项任务。  
进程通信：是指多个进程之间要传递一定量的信息。

##### 1.2 临界资源与临界区 #####

临界资源：某段时间内仅允许一个进程使用的资源。  
临界区：每个进程中访问临界资源的那段代码。

例：P1，P2两进程共享变量COUNT（COUNT的初值为5）

P1:{
        
    R1=COUNT;
    R1=R1+1;
    COUNT=R1;}
    
    P2:{
        
    R2=COUNT;
    R2=R2+1;
    COUNT=R2;}

分析：  
1》执行顺序P2→P1  
执行结果：  
P1：COUNT为7，  
P2：COUNT为6。  
2》两个进程交替  
执行顺序：  
P1：\{R1=COUNT\}  
P2：\{R2=COUNT\}  
P1：\{R1=R1+1；COUNT=R1\}  
P2：\{R2=R2=1；COUNT=R2\}  
执行结果  
P1：COUNT为6，  
P2：COUNT为6。  
可以看出两种不同执行顺序的执行结果不同。并且COUNT是一个临界资源，P1和P2的两个程序段是临界区。为了保证进程能够互斥对临界资源进行访问，我们需要在P1和P2的前面判断临界资源是否空闲，以此来判断进程能否进入临界区（即执行访问资源的那段代码）来实现**进程互斥。**

用Bernstein条件考察  
R（P1）=\{R1，COUNT\} W（P1）=\{R1，COUNT\}  
R（P2）=\{R2，COUNT\} W（P2）=\{R2，COUNT\}  
R（P1）∩W（P2）≠\{\}  
P1、P2不符合Bernstein条件，必须对程序的执行顺序施加某种限制。  
![在这里插入图片描述][563ec994cd2b42f098d11ced125231d0.png]

##### 1.3 临界资源进入准则 #####

（1）空闲让进：临界资源空闲时，允许进程进入临界区。  
（2）忙则等待：临界资源被访问时，其他想进入临界区的进程必须等待。  
（3）有限等待：需要访问临界资源的进程，因保证在有效时间内进入，避免进入死等状态。  
（4）让权等待：当进程不能进入临界区时，应当立即释放处理机，避免让其他进程死等。

### 2 进程互斥的实现 ###

##### 2.1 硬件方法 #####

为了解决进程互斥进入临界区的问题，采用硬件实现主要有两种：**禁止中断**和**专用机器指令**。  
禁止中断：通过系统的内核开启、禁止中断来实现。  
**专用机器指令：**  
（1）TS（Test and Set）指令

/TS指令：
    booleanTS(lock);
    booleanlock;
    {
             
    booleantemp;
     temp=lock;
    lock=true;
    returntemp;}
    
    //TS指令的使用
    while(TS(lock)) 
    /*什么也不做*/;
    临界区;
    lock = false;
    剩余区;

Lock有两种状态：1）当lock=false时，表示资源空闲;2）当lock=true时，表示资源正在被使用。为了实现互斥，设布尔变量lock，其初值为false,表示资源空闲。利用TS指令实现互斥。缺点：没有做到：“让权等待”。  
（2）Swap指令  
Swap指令是交换两个字节的内容来实现进程互斥。

//Swap指令
    void Swap(a,b);
    boolean a,b;
    {
             boolean temp;
    temp=a;
    a=b;
    b=temp;
    }
    
    Swap指令的使用
    key=true;
    do{
        
    Swap(lock,key);
    }while(key);
    临界区；
    lock=false;
    剩余区；

利用Swap指令实现进程互斥算法，为每个临界资源设置一个全局布尔变量lock，初始值为false，每个进程设置一个局部变量key，然后进入区利用Swap指令交换lock与key的内容，循环检查key的状态，知道进程进入临界区。

##### 2.2 软件方法 #####

**（1）单标志算法**

//进程P0
    while (turn!=0) 
    //什么都不做;
    临界区;
    turn =1;
    剩余区;
    
    //进程P1
    while (turn!=1) 
    //什么都不做‘;
    临界区;
    turn =0;
    剩余区;

设置公共整型变量turn，用于指示进入临界区的进程编号i(i=0,1)。当turn=0时，进程P0跳出while循环，进入临界区，在退出区将turn该为1，则进程P1跳出循环，进入临界区，循环往返使P0、P1轮流访问临界资源。缺点：强制性轮流进入临界区，不能保证“空闲让进”。  
**（2）双标志、先检查算法**

//进程P0
    while (flag[1])
    //什么都不做;
    flag[0]=true;
    临界区;
    flag[0] =false;
    剩余区;
    
    //进程P1
    while ( flag[0]) 
    //什么都不做;
    flag[1]=true;
    临界区;
    flag[1] =false;
    剩余区;

设置数组flag，初始时设每个元素为false,表示所有进程都未进入临界区。若flag\[i\]=true,表示进程进入临界区执行。在每个进程进入临界区时，先查看临界资源是否被使用，若正在使用，该进程等待，否则才可进入。解决了“空闲让进”问题。缺点：可能同时进入临界区，不能保证“忙则等待”（**如果先执行while (flag\[1\])，跳过进程P0的循环，然后再执行while ( flag\[0\]) ，跳过进程P1的循环，使两个进程同时进入临界区**），主要问题先检查后修改导致的。  
**（3）双标志、先修改后检查算法**

//进程P0
    flag[0]=true;
    while (flag[1])
    //什么也不做;
    临界区;
    flag[0] =false;
    剩余区;
    
    //进程P1
    flag[1]=true;
    while (flag[0])
    //什么也不做;
    临界区;
    flag[1] =false ;
    剩余区;

两进程先后同时作flag\[i\]=true;  
缺点：保证了不同时进入临界区，但又可能都进不去。不能保证“有空让进”。（**如果先执行flag\[0\]=true;，使得P1进入循环状态，然后再执行flag\[1\]=true;，使得P0进入循环状态，最终两个进程都进不去临界区**）  
**（4）先修改、后检查、后修改算法**

//进程P0
    flag[0]=true;
    turn=1;
    while (flag[1]) && (turn==1)
    //什么也不做;
    临界区;
    flag[0] =false ;
    剩余区;
    
    //进程P1
    flag[1]=true;
    turn=0;
    while (flag[0]) && (turn==0)
    //什么也不做;
    临界区;
    flag[1] =false ;
    剩余区;

保证了“有空让进”和“忙则等待”。

### 3 信号量和PV操作 ###

##### 3.1 信号量的定义 #####

1965年，荷兰学者Dijkstra提出了信号灯机制，卓有成效地解决了进程同步问题。  
**记录型信号灯的定义:**

(1)定义记录型信号量数据结构。
    struct semaphore{
        
    	int value;  //定义资源数的标识
    	struct PCB*queue; //等待队列
    } 
    
    (2)wait 原语：请求一个资源（P 操作）
    void wait(semaphore s){
           
    	s.value = s.value -1;  占用一个资源
    	if(s.value < 0)
    		block(s.queue); 
     /* 将进程阻塞，并将其投入等待队列s.queue */
     }
     
    (3)signal 原语：释放一个资源（V 操作）
    void signal(semaphore s){
          
    	s.value = s.value + 1;//释放一个资源
    	if(s.value <= 0)
      		wackup(s.queue);      
      /* 唤醒阻塞进程，将其从等待队列s.queue 取出，投入就绪队列*/
      }
      
    //s.value的初值表示系统中某种资源数目。
    //wait(s)表示要申请一个资源。
    //signal(s)表示要释放一个资源。
    //s.value <0时，|s.value|表示等待队列的进程数。

##### 3.2 用信号灯（信号量）解决互斥问题 #####

semaphoremutex=1;
    P1:
    	while (1){
        
    		P(mutex);
    		临界区;
    		V(mutex);
    		剩余区;
    	};
    
    P2:
    	while (1){
        
    		P(mutex);
    		临界区;
    		V(mutex);
    		剩余区;
    	};

##### 3.3 用信号灯解决同步问题 #####

semaphore a,b=0,0;
    {
        s1;V(a); V(b)}
    {
        P(a);s2
    {
        P(b);s3}

![在这里插入图片描述][2c5b157b113d400cba682b32eee0c1bd.png]  
因此，信号灯可以解决互斥问题和同步问题。

[563ec994cd2b42f098d11ced125231d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c43288249457473b89d38c2ce488d645.png
[2c5b157b113d400cba682b32eee0c1bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2fd729aa914b41538a85e40b209fcfc1.png