操作系统—同步与互斥、管程

1.临界资源（互斥访问）

临界资源：一次仅允许一个进程使用的资源

进入区entry：检查可否进入临界区。若能进入，则设置正在访问临界区的标志（“上锁”）
临界区critical：访问临界资源的那段代码（临界段）
退出区exit：将正在访问临界区的标志清除（“解锁”）
剩余区remainder：代码中的其余部分

进入区和退出区：负责实现互斥的代码段

注：非共享的不属于临界资源

2.同步（直接制约关系）

为完成某种任务而建立的两个或多个进程，在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系——”协作完成“

注：对并发进程实现同步的原因：并发进程是异步的

3.互斥（间接制约关系）

当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源

4.同步机制准则

空闲让进
忙则等待
有限等待：对请求访问的进程，保证能在有限时间内进入临界区（保证不会饥饿）
让权等待：不是必须遵循的，如Peterson’s Algorithm

实现临界区互斥

1.软件实现方法

①单标志法 ——违背“空闲让进”

思想：确保每次只允许一个进程进入临界区

turn：用于指示被允许进入临界区的进程编号

turn=0：允许进程P0进入临界区

每个进程进入临界区的权限只能被另一个进程赋予

//P0进程                        //P1进程
while(turn!=0);                 while(turn!=1);      //进入区
critical section;               critical section;    //临界区
turn=1;                         turn=0;               //退出区
remainder section;              remainder section;    //剩余区

②双标志法先检查 ——违背“忙则等待”

思想：在每个进程访问临界区资源之前，先查看临界资源是否正在被访问，若正被访问，该进程需等待

flag[]：布尔型数组。用于指示进程i是否进入临界区

flag[i]=FALSE：Pi 进程未进入临界区

flag[i]=TRUE：Pi 进程进入临界区

优点：不用交替进入，可连续使用
缺点：Pi和Pj可能同时进入临界区

//Pi进程                    //Pj进程
while(flag[j]);   ①        while(flag[i]);   ②    //进入区
flag[i]=TRUE;     ③        flag[j]=TRUE;     ④    //进入区（上锁）
critical section;           critical section;      //临界区
flag[i]=FALSE;              flag[j]=FALSE;         //退出区（解锁）
remainder section;          remainder section;     //剩余区

③双标识法后检查 ——违背“空闲让进”、“有限等待”，导致“饥饿”

思想：先将自己的标志设置为TRUE，再检测对方的状态标志。若对方标志未TRUE，则进程等待

解决了“忙则等待”

//Pi进程                    //Pj进程
flag[i]=TRUE;               flag[j]=TRUE;          //进入区
while(flag[j]);             while(flag[i]);        //进入区
critical section;           critical section;      //临界区
flag[i]=FALSE;              flag[j]=FALSE;         //退出区（解锁）
remainder section;          remainder section;     //剩余区

④Peterson’s Algorithm皮特森算法 ——未遵循“让权等待”，解决“饥饿”

思想：每个进程在先设置自己的标志后再设置turn标志，再同时检测另一个进程状态标志和允许进入标志

turn：为防止两个进程为进入临界区而无限等待
主动争取→主动谦让→检查对方是否也想使用，且最后一次是不是自己谦让的

//Pi进程                    //Pj进程
flag[i]=TRUE;turn=j;        flag[j]=TRUE;turn=i;      //进入区
while(flag[j]&&turn==j);    while(flag[i]&&turn==i);  //进入区
critical section;           critical section;         //临界区
flag[i]=FALSE;              flag[j]=FALSE;            //退出区
remainder section;          remainder section;        //剩余区

2.硬件实现方法 ——不满足“让权等待”，导致饥饿

低级方法、元方法
优点：适用于单处理机、多处理机；简单、容易验证其正确性
缺点：不能实现让权等待，导致饥饿
以下两个指令的功能实现是由硬件逻辑直接实现的，不会被中断

①中断屏蔽方法

优点：简单高效；只适用于OS内核进程

缺点：不适用于多处理机、用户进程

开中断、关中断：运行再内核态，属于特权指令

...
关中断
临界区
开中断
...

②硬件指令方法 ——违背“让权等待”，导致“饥饿”

**TestAndSet指令（TSL）：**原子操作

思想：old记录是否已被上锁，再将lock设为true，检查临界区是否已被上锁（若已上锁，则循环重复前几步）

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞

适用于多处理机环境

old：用于存放lock原来的值，记录是否已被上锁
lock：共享布尔变量，表示资源的两种状态（true-正被占用，初值为false）

//指令
boolean TestAndSet(boolean *lock){boolean old;old=*lock;    //old用于存放lock原来的值*lock=true;return old;   //返回lock原来的值
}
//用该指令实现互斥
while TestAndSet(&lock);    //上锁并检查
进程的临界区代码段;
lock=false;   //解锁
进程的其他代码;

Swap指令（XCHG）：交换两个字（字节）的内容

//指令
Swap(boolean *a,boolean *b){boolean temp;temp=*a;*a=*b;*b=temp;
}
//实现互斥
key=true;
while(key!=false)Swap(&lock,&key);
进程的临界区代码段;
lock=false;
进程的其他代码;

互斥锁 ——违反“让权等待”

互斥锁：解决临界区最简单的工具

acquire()：获得锁
release()：释放锁
available：布尔变量，表示锁是否可用。若锁可用，调用acquire()会成功，且锁不再可用

当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放

acquire()和release()执行时原子操作，互斥锁通常采用硬件机制来实现
优点：通常用于多处理器系统；等待期间不用切换进程上下文
缺点：忙等待。不太适用单处理机系统
自旋锁：需要连续循环忙等的互斥锁。eg.TSL指令、Swap指令、单标志法

acquire(){while(!available);    //忙等待available=false;    //获得锁
}
release(){available=true;    //释放锁
}

信号量

信号量的值：资源的剩余数量
实现互斥：互斥信号量mutex初值为1
实现同步：同步信号量初值由用户决定
信号量机制：

wait(S)——P操作：减1，检查
signal(S)——V操作：加1

P、V操作是一种低级的进程通信原语（原语通常可由硬件来实现），PV操作是由两个不可被中断的过程组成的

1.整型信号量——未遵循“让权等待”

用于表示资源数目的整型量S

//进入区
wait(S){while(S<=0);    //若资源数不够，就一直循环等待S=S-1;
}
//退出区
signal(S){S=S+1;
}

💟2.记录型信号量——遵循“让权等待”

实现系统资源的“申请”和“释放”，实现进程互斥、进程同步

进程链表L：用于链接所有等待该资源的进程
block原语：进行自我阻塞，放弃处理机，并插入该类资源的等待队列S1。若剩余资源数不够，则调用
wakeup原语：将S.L中的第一个等待进程唤醒，该进程从阻塞态变为就绪态

//记录型信号量描述
typedef struct{int value;   //剩余资源数struct process *L;    //等待队列
}semaphore;
//P操作：相当于申请资源
void wait(semaphore S){S.value--;  //表示进程请求一个该类资源if(S.value<0){   //S.value<0表示该类资源已分配完毕add this process to S.L;block S.L;}
}
//V操作：相当于释放资源
void signal(semaphore S){S.value++;if(S.value<=0){   //若S.value+1后仍<=0，表示S.L中仍有等待该资源的进程被堵塞remove a process P from S.L;wakeup(P);}
}

🪷3.利用信号量实现同步（前V后P）

公共信号量：初值为0

前V后P：在“前操作”之后执行V(S)，在“后操作”之前执行P(S)

semaphore S=0;   //初始化信号量
P1(){x;    //语句xV(S);   //告诉进程P2，语句x已经完成（唤醒wakeup 等待进程P2）...
}
P2(){...P(S);   //检查语句x是否运行完成y;   //检查无误，运行y语句...
}

🪷4.利用信号量实现进程互斥

互斥信号量mutex：初值为1

semaphore mutex=1;    //初始化（记录型）信号量
P1(){...P(mutex);     //准备开始访问临界资源，加锁进程P1的临界区;V(mutex);     //访问结束，解锁...
}
P2(){...P(mutex);     //准备开始访问临界资源，加锁进程P2的临界区;V(mutex);     //访问结束，解锁...
}

5.利用信号量实现前驱关系

设置若干初始值为0的信号量

例如：为保证S1→S2，S1→S3的前驱关系，应分别设置信号量a1，a2

同样，为保证S2→S4，S2→S5，S3→S6，S4→S6，S5→S6

在这里插入图片描述

semaphore a1=a2=b1=b2=c=d=e=0;   //初始化信号量
S1(){...;V(a1);V(a2);   //S1已经运行完成
}
S2(){P(a1);    //检查S1是否运行完成...;V(b1);V(b2);   //S2已经运行完成
}
S3(){P(a2);    //检查S1是否运行完成...;V(c);   //S3已经运行完成
}
S4(){P(b1);    //检查S2是否运行完成...;V(d);   //S4已经运行完成
}
S5(){P(b2);    //检查S2是否运行完成...;V(e);   //S5已经运行完成
}
S6(){P(c);    //检查S3是否运行完成P(d);    //检查S4是否运行完成P(e);    //检查S5是否运行完成...;
}

管程

定义1：高级同步机制 / 进程同步工具，为更方便实现进程互斥和同步
定义2：代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序
特性：保证了进程互斥，降低死锁发生的可能性，提供了条件变量，灵活地实现进程同步
目的：解决信号量机制编程麻烦、易出错的问题
组成：管程的名称、局部与管程内部的共享数据结构说明、对该数据结构进行操作的一组过程（或函数）、对局部于管程内部的共享数据设置初始值的语句

基本特征

局部于管程的数据只能被局部于管程的过程所访问；
一个进程只有通过调用管程内的过程才能进入管程访问共享数据
每次仅允许一个进程在管程内执行某个内部过程

注：①个进程必须互斥访问管程的特性是由 编译器 实现的；

②可在管程中设置条件变量及等待/唤醒操作要解决同步问题

条件变量

定义：当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，如果该进程不释放管程，那么其他进程无法进入管程。为此，将阻塞原因定义为条件变量condition

x.wait：当x对应的条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程——阻塞该进程，并将之插入x的阻塞队列中
x.signal：x对应的条件发生了变化，则调用x.signal，唤醒一个因x条件而阻塞的进程

注：管程的signal操作 ≠ 信号量机制的V操作

∵V操作一定会改变信号量的值