操作系统---进程的同步和互斥（易错知识点梳理）

目录

1.S.value()

2.互斥机制要遵循的原则

3.Peterson算法

4.互斥信号量与同步信号量

5.可重入代码

6.P/V操作和管程

7.并发进程的执行

本节对应知识点：

进程的同步与互斥

1.S.value()

S.value()出现在记录型信号量中，用来记录资源的数目：

//记录型信号量

typedef struct{

        int value;

        struct process *L;        //用于链接所有等待该资源的进程

}semaphore;

//wait/P操作

void wait(semaphore){

        S.value--;

        if(S.value<0){

                add.this process to S.L;

                block(S.L);

        }

}

//signal/V操作

void signal(semaphore s){

        S.value++;

        if(S.value<=0){

                remove a process P from S.L;

                wakeup(P);

        }

}

1.对信号量S执行P操作后，使该进程进入资源等待队列的条件是（）

A. S.value<0        B.S.value<=0        C.S.values>0        D. S.value >=0

① S.value>0，表示某类可用资源的数量。每次P操作，意味着请求分配一个单位的资源。

② S.value<=0，表示某类资源已经没有，或者说还有因请求该资源而被阻塞的进程，S.value的绝对值表示等待进程数目。

若S.value=0，表示这类资源已经没有。① 某进程进行P操作后，S.value--，则S.value<0，所以该进程进入等待队列。② 某进程进行P操作前，没有进行S.value--，则S.value<=0，该进程进入等待队列。

答案:A

① 同理，当S.value<0时，表示有进程在等待资源。执行V操作后，S.value++，若此时S.value<=0，表示有进程等待资源，此时就会唤醒S.L队列中的第一个进程（阻塞-->就绪）

2.互斥机制要遵循的原则

实现临界区互斥必须遵循："忙则等待"，“空闲让进”，"有限等待"，不一定需要"让权等待"。若未满足"让权等待"，则会出现"忙等"。

（1）记录型信号量

像上面所说的"记录型信号量"就满足了"让权等待"。当执行S.value--后，S.value<0，表示该资源已经分配完毕，此时会调用block原语进行自我阻塞（运行-->阻塞），主动放弃CPU，并插入该类资源的等待队列。

（2）整型信号量

整型信号量没有遵循"让权等待"：

wait(S){
        while(S<=0);

        S=S-1;

        }
        signal(S){
               S=S+1;

        }

在整型信号量机制中的 wait 操作，只要信号量 S≤0，就会不断循环测试。未遵循“让权等待”的准则，而是使进程处于“忙等”的状态，即一直占用CPU执行while循环。

（3）硬件实现方法

硬件实现方法中的TSL和Swap指令都不能遵循"让权等待”，等待进入临界区的进程会占用CPU执行while循环。

注：TSL指令和swap指令并没有处于阻塞态的进程，等待进入临界区的进程一直停留在执行while循环中，不会主动放弃CPU，一直处在运行态，直到该进程的时间片用完放弃处理机，转为就绪态，此时切换另一个就绪态的进程占用处理机（就绪--->运行）。

（4）软件实现方法

•单标志法：

两个进程必须交替进入临界区，若P0顺利进入临界区并从临界区离开，则此时临界区是空闲的，但P1并没有进入临界区的打算，而turn=1一直成立，就无法再次进入临界区。没有遵循“空闲让进”。

•双标志先检查法：

先检查对方标志，再设置自己的标志，这两个操作无法一气呵成，若“检查对方标志后”和“设置自己标志前”进行进程切换，双方都通过检查，则会同时进入“临界区”，没有遵循“忙则等待”。

•双标志后检查法：
两个进程依次设置自己的标志，并依次检查对方的标志，发现对方也想进入临界区，双方都争着进入临界区，结果谁也进不了，违背“空闲让进”准则，于是因各个进程都长期无法访问临界区而导致“饥饿”现象(违背“有限等待”准则)。

•Peterson算法：

因为等待进入临界区的进程会占用CPU执行while循环，所以没有遵循“让权等待”原则。

3.Peterson算法

为了防止两个进程为进入临界区而无限期等待，设置了变量turn，表示允许进入临界区的编号，每个进程在先设置自己的标志后再设置turn 标志，允许另一个进程进入。这时，再同时检测另一个进程状态标志和允许进入标志，就可保证当两个进程同时要求进入临界区时只一个进程进入临界区。若双方试图同时进入临界区，保存的是较晚的一次turn赋值，虽然前一个turn的赋值也会执行，但是会被后一个turn赋值覆盖。因此较晚的进程等待，较早的进程进入。先到先入，后到等待，从而完成临界区访问的要求。

但他没有遵循“让权等待”原则，上面说了。

Peterson算法能保证进程互斥地进入临界区，不会出现“饥饿”现象。

4.互斥信号量与同步信号量

互斥信号量：

互斥信号量的初值一般设置为1，表示临界区只允许一个进程进入。P操作成功则将其减1，禁止其他进程进入；V操作成功则将其加1，允许等待队列中的一个进程进入。互斥量的绝对值表示在临界区外等待进入的进程数。

同步信号量：

与互斥信号量初值一般置1不同，用PV操作实现进程同步时，信号量的初值应根据具体情况来确定。若期望的消息尚未产生，则对应的初值应设为0；若期望的消息已存在，则信号量的初值应设为一个非0的正整数。

1.一个系统中共有5个并发进程涉及某个相同的变量 A，变量A的相关临界区是由（）个临界区构成的。

答案：5

临界区是指访问临界资源A的那段代码(临界区的定义)。那么5个并发进程共有5个操作共享变量 A的代码段。

2.若有4个进程共享同一程序段，每次允许3个进程进入该程序段，若用P，V操作作为同步机制，则信号量的取值范围是( )。

A. 4,3,2,1,-1        B. 2,1,0,-1,-2        C. 3,2,1,0,-1        D. 2,1,0,-2,-3

信号量取值：

3：没有进程进入该程序段；2：有1个进程进入；1：有2个进程进入；0：有3个进程进入；-1：有3个进程进入，并有一个进程在等待进入。

答案：C

3.设与某资源关联的后号量初值为 3，当前值为 1。若 M表示该资源的可用个数，N表示等待该资源的进程数，则M,N分别是（）

A.0,1        B.1,0        C.1,2        D.2,0

信号量麦示相关资源的当前可用数量。当信号量K>0时，表示还有个相关资源可用，所以该资源的可用个数是1。而当信号量K<0时，表示有|K|个进程在等待该资源。由于资源有剩余，可见没有其他进程等待使用该资源，因此进程数为0。

答案：B

5.可重入代码

若代码可被多个进程在任意时刻共享，则要求任意一个进程在调用此段代码时都以同样的方式运行；而且进程在运行过程中被中断后再继续执行，其执行结果不受影响。这必然要求代码不能被任何进程修改，否则无法满足共享的要求。这样的代码就是可重入代码，也称纯代码，即允许多个进程同时访问的代码。

共享资源：

① 互斥共享资源就是临界资源，一次可供一个进程使用，如：公用队列，打印机等。

② 不互斥的共享资源，如可重入代码，磁盘等。

非共享资源：

如：私有数据等。

6.P/V操作和管程

P/V操作：

P/V操作时一种低级的进程通信原语，由两个不可被中断的过程组成。

管程：

管程将对共享资源的操作封装起来，管程内的共享数据结构只能被管程内的过程所访问。一个进程只有通过调用管程内的过程才能进入管程访问共享资源。

P/V信号量和管程条件变量的比较：

相似点：条件变量的wait，signal操作类似于信号量的P/V 操作，可以实现进程的阻塞/唤醒。

不同点：条件变量是“没有值”的，仅实现了“排队等待”功能；而信号量是“有值”的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。

例如，信号量机制中的V操作一定会改变信号量的只S=S+1，而管程中的signal操作是针对某个条件变量的，若不存在因该条件变量阻塞的进程，则signal不会产生任何影响。

7.并发进程的执行

1.进程P1和P2均包含开发执行的线程，部分伪代码描述如下所示。

下列选项中，需要互斥执行的操作是（）

A.a=1与a=2        B.a=x与b=x        C.x+=1与x+=2        D.x+=1与x+=3

A：a是线程内部的局部变量，不需要互斥访问。

D：不同进程的线程代码段，不存在互斥访问的问题。

B：对进程内部的共享变量x的读操作，不互斥也不影响执行结果，所以不需要互斥访问。

C：不同线程对同一个进程内部的共享变量的写操作，需要互斥访问(类似于读者-写者问题)。

所以：需要进行互斥的操作是对临界资源的访问，不同线程对同一个进程内部的共享变量的访问才可能需要进行互斥。

2.有两个并发执行的进程P1和进程 P2，共享初值为1的变量x，P1对x加1，P2对x减1，加1和减1操作的执行指令序列如下:

两个操作完成后，x的值：（）

A.可能为-1或3        B.只能为1        C.可能为0，1或2        D.可能为-1，0，1或2

① P1进程最初取到的值可能为1或0（P2进程完成后更新得到的x值0），那么P1进程最终写入x的值为1+1（2）或0+1（1）

② 同理，P2进程最初取到的值可能为1或2（P1进程完成后更新得到的x值2），那么P2进程最终写入x的值为1-1（0）或2-1（1）

最终的x值可能是0、1或2

答案：C

3.属于同一进程的两个线程thread1和 thread2并发执行，共享初值为0的全局变量x。thread1和thread2 实现对全局变量x加1的机器级代码描述如下。

在所有可能的指令执行序列中，使x的值为2的序列个数是（）

A.1        B.2        C.3        D.4

x=2，只可能是先执行线程thread1再执行线程 thread2，或先执行线程thread2再执行线程 thread1这两种可能。

答案：B