一. 单选题（共12题，12分）

1. (单选题, 1分)
两个旅行社甲和乙为旅客到某航空公司订飞机票，形成互斥资源的是（   ）。
A、旅行社
B、航空公司
C、飞机票
D、旅行社和航空公司

解析：正确答案为C。一张飞机片不能售给不同的旅客，因此飞机票是互斥资源，其他因素只是为了完成飞机票订票的中间过程，与互斥资源无关。

2.(单选题, 1分)
下面关于临界区的叙述中，正确的是（   ）。
A、临界区可以允许规定数目的多个进程同时执行
B、临界区只包含一个程序段
C、临界区是必须互斥地执行的程序段
D、临界区的执行不能被中断

解析：对临界区概念的考查。临界区时访问临界资源的、必须互斥地执行的程序段。也就是说，当一个进程在某个临界段中执行时，其他进程不能进入相同临界资源的任何临界段.故本题答案是C。

3.(单选题, 1分)
设与某资源关联的信号量（K）初值为3，当前值为1。若M表示该资源的可用个数，N表示等待该资源的进程数，则当前M、N分别是（   ）。   
A、0、1
B、1、0
C、1、2
D、2、0

解析：正确答案为B。信号量表示相关资源的当前可用数量。当信号量K>0时，表示还有K个相关资源可用，所以该资源的可用个数是1.而当信号量K<0时，表示有K个进程在等待该资源。由于资源有剩余，课件没有其他进程等待使用该资源，因此进程数为0。

4.(单选题, 1分)
有三个进程共享同一个程序段，而每次只允许两个进程进入该程序段，如用PV操作同步机制，则信号量S的取值范围是（   ）。
A、2，1，0，-1
B、3，2，1，0
C、2，1，0，-1，-2
D、1，0，-1，-2

解析：因为每次允许两个进程进入该程序段，信号量最大值取2,。至多有3个进程申请，则信号量最小为-1。所以信号量可取2,1,0,-1，故本题答案为A。

5.(单选题, 1分)
某一时刻某一资源的信号量s=0，它表示（   ）。
A、该时刻该类资源的可用数目为1
B、该时刻该类资源的可用数目为－1
C、该时刻等待该类资源的进程数目为1
D、该时刻等待该类资源的进程数目为0

6.(单选题, 1分)
进程A和B共享同一临界资源，并且进程A正处于对应的临界区执行。下列的描述中（   ）是一条正确的描述。
A 、进程A的执行不能被中断，即临界区的代码具有原子性。
B、进程A的执行被中断，但中断A后，不能将CPU调度给进程B。
C、进程A的执行能被中断，而且只要B进程就绪，就可以将CPU调度给B进程。
D、进程A的执行能被中断，而且只要B进程就绪，就必定将CPU调度给B进程。

7.(单选题, 1分)
有一个资源信号量S：（1）假如若干个进程对S进行了28次P操作和18次V操作之后，信号量S的值为0。（2）假如若干个进程对信号量S进行了15次P操作和2次V操作，请问此时有（   ）个进程等待在信号量S的队列中。
A、2
B、3
C、5
D、7

8.(单选题, 1分)
有两个并发进程P1和P2，x是它们的共享变量。其程序代码如下：

P1()
    {
    x=1;
    y=2;
    printf(z);
}

p2()
    {
    x=-3;
    c=x*x;
    print c;
}

可能打印z的值有（   ），可能打印c的值有（    ）。
A、z=1，-3；c=-1，9
B、z=-1，3；c=1，9
C、z=-1，3，1；c=9
D、z=3；c=1，9

解析：正确答案为B。本体的关键是，输出语句print z， print c读取的x的值不同，由于print z， print c执行有先后问题，使得在执行print z， print c先，x的可能取指有两个，即1，-3；这样，输出z的值可能是1+2=3或（-3）+2=-1；输出c的值可能是11=1或（-3）（-3）=9；

9.(单选题, 1分)
进程P1和P2均包含并发执行的线程，部分伪代码如下：
下面选项中，需要互斥执行的操作是（   ）。

P1()
    int x=0;
    Thread1()
    {
      int a;
      a=1;
      x+=1;
    }
    Thread2()
    {
      int a;
      a=2;
      x+=2;
    }
    
 P2()
    int x=0;
    Thread3()
    {
      int a;
      x+=3;
    }
    Thread4()
    {
      int b;
      b=x;
      x+=4;
    }

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

解析：正确答案为B。P1中对a进行赋值，并不影响最终的结果，因此a=1和a=2不需要互斥执行；a=x与b=x执行先后不影响a与b的结果，无须互斥执行；x+=1与x+=2执行先后会影响x的结果，需要互斥执行；P1中的x和P2中的x是不同范围的x，互不影响，不需要互斥执行。

10.(单选题, 1分)
进程P0和P1的共享变量定义和初值为：
boolean  flag[2]; int turn=0;
flag[0]=false;    flag[1]=false;
若进程P0、P1访问临界资源的伪代码如下：

P0()
    {
    while(ture)
     {
       flag[0]=ture;
       turn=1;
       while(flag[1]&&turn==1); 
       临界区；
       flag[0]=flase;
     }
    }
P1()
  {
    while(ture)
    {
        flag[1]=ture;
        turn=0;
        while(flag[0]&&turn==0);
        临界区;
        falg[1]=flase;
    }
}

则并发执行进程P0和P1时产生的情况是（   ）。
A、不能保证进程互斥进入临界区，会出现“饥饿”现象
B、不能保证进程互斥进入临界区，不会出现“饥饿”现象
C、能保证进程互斥进入临界区，会出现“饥饿”现象
D、能保证进程互斥进入临界区，不会出现“饥饿”现象

答：正确答案为D。这是Peterson算法的实际实现，保证进入临界区的进程合理安全。
　　该算法为了防止两个两个进程为进入临界区而无限期等待，设置了变量turn，表示不允许进入临界区的编号，每个进程在先设置自己的标志后再设置turn标志，不允许另一个进程进入。这时，再同时检测另一个进程状态标志和不允许进入表示，就可保证当两个进程要求进入临界区时值允许一个进程进入临界区。保存的是较晚的一次赋值，因此较晚的进程等待，较早的进程进入。先到先入，厚道等待，从而完成临界区访问的要求。
　　其实这里可想象为两个人进门，每个人进门前都会和对方客套一句“你先走”。若进门时没别人，就当和空气说句废话，然后大步登门入室；若两人同时进门，就互相先请，但各自只客套一次，所以先客套的人请完对象，就等着对方请自己，然后光明正大的进门。

11.(单选题, 1分)
若系统中有五个并发进程涉及某个相同的变量A，则变量A的相关临界区最少是由（   ）临界区构成。
A、2个
B、3个
C、4个
D、5个

解析：对临界区概念的考查。故本题答案是D。

12.(单选题, 1分)
有m个进程共享同一临界资源，若使用信号量机制实现对临界资源的互斥访问，则信号量值的变化范围是（   ）。
A、 -(m-1)至 1
B、0至m-1
C、1至m
D、-m至1

二. 填空题（共6题，40分）

13.(填空题, 4分) 在具有N个进程的系统中，允许M个进程(N≥M≥1)同时进入它们的共享区，其信号量S的值的变化范围是   ①    ，处于等待状态的进程数最多是   ②    个。

　　解析：信号量S用于控制进入共享区的进程数，初值为M。极端情况是N个进程都需要进入共享区。故本题答案是（M-N，M），N-M。

14.(填空题, 2分) 有两个用户进程A和B，在运行过程中都要使用系统中的一台打印机输出计算结果，则A、B两进程之间为  ③  制约关系。

　　解析：对两种制约关系的考查。故本题答案是间接（或互斥）。

15.(填空题, 2分) Peterson算法是一种能够正确对两个进程进行互斥的方法。该方法中用了  ④  个标志进行互斥。

　　解析：3。

16.(填空题, 4分) 用P、V操作管理临界区时，任何一个进程在进入临界区之前应调用  ⑤  操作，退出临界区时应调用   ⑥     操作。

　　解析：P；V。

17.(填空题, 12分)
哲学家进餐算法会出现什么问题　　　？限制同时允许哲学家进餐的人数可以避免这种问题出现。请对下面的算法进行补充。

mutex=第二空；
    chopstick[0..4]=1;
Pi(i=0,1...4);
while(true){
    第三空；
    wait(chopstick[i]);
    第四空;
    Eat;
    signal(chopstick[i]);
    第五空；
    第六空；
}

解析：死锁；4；wait（mutex）；wait（chopstick[(i+1)%5]）;signal(chopstick[(i+1)%5]);signal(mutex);

18.(填空题, 16分)
下面用信号量实现读者/写者问题，请在空白处填写正确答案。
设信号量mutex实现读者与写者，写者与写者之间互斥。readernum是统计读者个数的变量。信号量readermutex实现读者之间互斥使用readernum的信号量。

Mutex=第一空;readernum=第二空;
redermutex=1;
Reader()
    {
    第三空;
    if(readernum==0)第四空;
    readernum++;
    第五空;
    读文件;
    第六空;
    第七空;
    if(readernum==0)
    第八空;
      signal(redermutex);
}
Writer()
    {
    Wait(mutex);
    修改文件;
    Signal(mutex);
}

 解析：1;0;wait(readermutex);wait(mutex);signal(readermutex);wait(readermutex);readernum--;signal(mutex)

三. 简答题（共4题，18分）

19.(简答题, 4分) 何谓进程同步？进程之间的制约关系分为几种，都是什么？
答：资源的有限性决定了进程在资源的共享过程中，也存在竞争。资源的共享和竞争使系统中并发执行的进程间形成一种制约关系，称为进程同步。
　　进程之间的制约关系分为2中，直接制约关系和间接制约关系。
　　直接制约关系：也称为同步关系。这种关系一般存在于合作进程之间。指多个进程中发生的时序存在着某种时序关系，必须协同动作，相互配合，以共同完成一个任务。
　　间接制约关系：也称为互斥关系。拥有间接制约关系的进程之间并不存在直接的交互。它们之间的关系是由共享某一公有资源而引起的。

20.(简答题, 3分) 什么是临界资源？对临界资源采用什么方式进行访问？
答：一次仅允许一个进程访问的资源称为临界资源。对临界资源采用互斥方式进行访问。

21.(简答题, 5分) 什么是临界区？进入临界区的准则有哪些？
答：每个进程中访问临界资源的那段代码称为临界区。进入临界区的准则是空闲让进、忙则等待、有限等待、让权等待。
　　空闲让进：当没有进程处于临界区是，也就是说资源未被使用，处于空闲状态时，允许一个进程进入自己的临界区。
　　忙则等待：当进程申请进入临界区时有其他进程正在执行临界区代码，这就意味着，资源正被其他进程使用，处于忙碌状态，这时申请进程必须等待。
　　有限等待：对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。
　　让权等待：当进程不能进入自己的临界区应立即释放处理机，以免进程陷入“忙等”状态。

22.(简答题, 6分) 信号量是被保护的数据结构，除信号量被赋初值外，信号量的值仅能由两个同步原语wait操作和signal操作才能改变。请说明这两个原语的物理意义。
答：wait操作的物理意义其实就是分配资源的过程。执行wait操作时，一般是进程要申请资源，资源量首先减1，代表分配或预分配。之后判断分配或预分配后资源数量是否小于零，如果小于零带包目前系统中午资源，之前为预分配，进程需要进入等待队列等候资源，进程被阻塞。
　　signal操作的物理意义其实就是释放资源的过程，执行signal操作时，一般是今晨要归还资源，资源量首先加1,。如果加1后，资源数目依然小于零，这就意味着仍有今晨在等待资源，这时候调用进程离开临界区之前，需要从等待队列中唤醒一个进程，让该进程进入就绪队列，等待调度获得资源去执行；如果资源数目大于零，表示目前信号量队列中没有等待该资源的进程，则调用进程直接离开临界区即可。

四. 计算题（共3题，30分）

23. (计算题, 10分) 有如下2个进程并发执行，因为共享资源变量X而导致结果不确定。请分别用Peterson算法和信号量机制实现进程A和进程B的互斥。

进程A
    x=1;
y=2;
if x>0 
    y=x*y;
else
    y=x+y;
printf("%d",y);
进程B
    x=-1;
if x<0 
    a=x+2;
else
    a=x-2;
printf("%d",a);

解析1 Peterson算法：

int flag[2]={0,0};
int turn;
进程A
{
　　flag[0]=1;
　　turn=1;
　　while(flag[1]&&turn==1);`
　　x=1;
　　y=2;
　　if x>0
　　　　y=x*y;
　　else
　　　　y=x+y;
　　printf("%d",y);
　　flag[0]=0;
}
进程B
{
　　flag[１]=1;
 　　turn=0;
 　while(falg[0]&&turn==0);
  x=-1;
if x<0
a=x+2;
else
a=x-2;
printf("%d",a);
flag[1]=0;
}

解析２信号量机制

semaphore mutex;
mutex.value=1;
进程A
{
    wait(mutex);
    x=1;
    y=2;
    if X>0
        y=x*y;
    else
        y=x+y;
    printf("%d",y);
    signal(mutex);
}
进程B
{
wait(mutex);
    x=-1;
    if x <0
        a=x+2;
    else
        a=x-2;
    printf("%d",a);
    signal(mutex);
}

24.(计算题, 10分) 某博物馆最多容纳500人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下：
cobegin
Visitor_i （参观者进程i）：
{   …
  进门；
…
  参观；
…
出门；
…
}
coend
请添加必要的信号量和PV操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

解析：出入口一次仅允许一个人通过，设置互斥信号量mutex，初值为1.博物馆最多可同时容纳500人，因此设置信号量empty，初值为500。

mutex=1;
number=500;
cobegin
    Visitor_i(参股者进程i)
    {
    wait(number);
    wait(mutex);
    进门;
    signal(mutex);
    参观;
    wait(mutex);
    出门;
    signal(mutex);
    signal(number);
}

25.(计算题, 10分) 请用信号量对下面2个进程进行互斥访问。

x=0;y=1;
process p0
    {
    int reg1,z;
    reg1=reg1*reg1+10;
    x=reg1;
    printf("%d",x);
    z=y;
    z=z*2021+1024;
    y=z;
    printf("%d",y);
}

process p1
    {
    int reg1,z;
    reg1=reg1*10+30;
    y=reg1;
    printf("%d",y);
    z=x;
    z=z*520+204;
    x=z;
    printf("%d",x);
}

解析：

mutex1=1;mutex2=1;
x=0;y=1;
process p0
    {
    int reg1,z;
    wait(mutex1);
    reg1=reg1*reg1+10;
    x=reg1;
    printf("%d",x);
    signal(mutex1);
    wait(mutex2);
    z=y;
    z=z*2021+1024;
    y=z;
    printf("%d",y);
    signal(mutex2);
}

process p1
    {
    int reg1,z;
    wait(mutex2);
    reg1=reg1*10+30;
    y=reg1;
    printf("%d",y);
    signal(mutex2);
    wait(mutex1);
    z=x;
    z=z*520+204;
    x=z;
    printf("%d",x);
    signal(mutex1);
}