复习题

进程同步问题

一个快餐厅有4类职员：

领班：接受顾客点菜
厨师：准备顾客的饭菜
打包工：将饭菜打包
出纳员：收款并提交食物

每位职员可被看做一个进程，试用一种同步机制写出能让4类职员正确并发工作的程序。

设 3 个同步信号量 S2,S3,S4 和 4 个互斥信号量 W1,W2,W3,W4 来协调进程工作。

Semaphore S2, S3, S4; // S为同步信号量，表示4类职员的工作顺序
Semaphore W1, W2, W3, W4; // W为互斥信号量，表示每一类员工一次只能为一个客户服务
S2 = S3 = S4 = 0; 
W1 = W2 = W3 = W4 = 1;
cobegin
   process P1() {
        while(true) {
            有顾客到来;
            P(W1); // W1=W1-1, if  W1<0 block;
            接受顾客点菜;
            V(W1); // W1=W1+1
            V(S2); // S2=S2+1;
        }
    }
    process P2() {
        while(true) { 
            P(S2); // S2=S2-1, if S2<0 block;
            P(W2); // W2=W2-1, if W2<0 block;
            准备顾客的饭菜;
            V(W2); // W2=W2+1
            V(S3); // S3=S3+1
        }
    }
    process P3() {
        while(true) {
            P(S3);
            P(W3); // W3=W3-1, if  W3<0 block;
            将饭菜打包;
            V(W3); // W3=W3+1
            V(S4); // S4=S4+1
        }
    }
    process P4() {
        while(true) {
            P(S4);
            P(W4); // W4=W4-1, if  W4<0 block;
            收款并提交食品;
            V(W4); // W4=W4+1
        }
    }
coend

先 P 再 V，PV 成对出现。

假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行登记，而且每次只允许一人进行登记操作，请用记录型信号量机制实现上述问题的同步。

定义信号量 sum,mutex，初值分别为100，1。则第 i 个读者的活动描述为：Pi

Semaphore sum,mutex;
Sum = 100;
mutex = 0;
cobegein
    procedure Pi()(i = 1, 2, 3……){  
        wait(sum);//sum=sum-1, if sum<0 block
        wait(mutex);//mutex=mutex-1, if mutex<0 block
        登记；
        signal(mutex);//mutex=mutex+1
        进入阅览室；
        阅读;     
        wait(mutex);//mutex=mutex-1, if mutex<0 block
        登记；
        signal(mutex); //mutex=mutex+1
        离开阅览室；
        signal(sum); //sum=sum+1
    }
coend

图给出了四个进程合作完成某一任务的前趋图，试说明这四个进程间的同步关系，并用P、V操作描述它。

Semaphore p1, p2, p3, p4;
p1 = p2 = p3 = p4 = 0;
cobegein
    process s1(){  
        //…
        Signal(p1);
        Signal(p2);
    }
    process s2(){  
        wait(p1);
        // …
        Signal(p3);
    }
    process s3(){  
        wait(p2);
        // …
        Signal(p4);
    }
    process s4(){  
        wait(p3);
        wait(P4);
        // …
    }
coend

请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。

将独木桥的两个方向分别标记为 A 和 B，并用整形变量 countA 和 countB 分别表示 A、B 方向上已在独木桥上的行人数，初值为 0。再设置三个初值都 1 的互斥信号量：SA 用来实现对 countA 的互斥访问，SB 用来实现对 countB 的互斥访问，mutex 用来实现两个方向的行人对独木桥的互斥使用。则具体描述如下：

Semaphore SA, SB, mutex;
int countA, countB;
SA, SB, mutex = 1, 1, 1;
countA, countB = 0, 0;

cobegin 
    process A() { 
        wait(SA); //互斥操作countA变量
        if(countA == 0) then wait(mutex); //A方向第一个上桥的人执行mutex=mutex-1, if mutex<0 block, 否则可以上桥
        countA++;
        signal(SA); //释放SA变量
        过独木桥；
        wait(SA); //互斥操作countS变量
        countA--;
        if (countA == 0) then signal(mutex);//A方向第最后一个下桥的人执行mutex=mutex+1 if mutex<=0 wakeup, 唤醒B进程
        signa(SA);
    }

    process B() { //过程同A
        wait(SB);
        if(countB == 0) then wait(mutex);
        countB++;
        signal(SB);
        过独木桥；
        wait(SB);
        countB--;
        if (countB == 0) then signal(mutex);
        signa(SB);
    }
coend

设公共汽车上，司机和售票员的活动分别是：

司机的活动：启动车辆；正常行车；到站停车；
售票员的活动：关车门；售票；开车门；

请用记录型信号量机制实现上述问题的同步。

Semaphore s1, s2;
s1, s2 = 0, 0; /*s1表示是否允许司机启动汽车，s2表示是否允许售票员开门*/
cobegin 
    process driver() {
        while (true) {
            wait(s1);//s1=s1-1, if s1<0 block，售票员关门后司机才能开车
            启动车辆;
            正常行车;
            到站停车;
            signal(s2); //s2=s2+1，ifs2<=0 wakeup busman司机停车后，售票员才可以开门
        }
    }

    process busman() {
        while (true) {
            关车门;
            signal(s1); //s1=s1+1，ifs1<=0 wakeup driver售票员关门后，司机才可以开车
            售票;
            wait(s2); //s2=s2-1, if s2<0 block，司机停车后售票员才可以开车门
            开车门;
            上下乘客;
        }
    }             
coend

有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。问题：

解释P、V操作的含义。
并用P、V操作来保证文件的正确打印。

(1) P、V 操作是两条原语，定义如下：
P 操作：P操作记为 P(S)，其中 S 为一信号量，它执行时主要完成下述动作：S = S - 1

若S >= 0，则进程继续运行。
若S < 0，则该进程被阻塞，并将它插入该信号量的等待队列中。

V操作：V操作记为 V(S)，其中 S 为一信号量，它执行时主要完成下述动作：
S = S + 1

若 S > 0，则进程继续运行。
若 S <= 0，则从信号量的等待队列中移出队首进程。使其变为就绪状态。

(2) 描述如下：

semaphore empty1, empty2, full1, full2, mutex1, mutex2；
empty1 = empty2 = 1;
full1, full2 = 0, 0;
mutex1 = mutex2 = 1; //empty1,empty2,full1,full2分别表示缓冲区1、2空和满的同步信号量，mutex1,mutex2分别表示互斥使用缓冲区1、2的互斥信号量
cobegin
    process PA() {
        while (true) {
            从磁盘读一个记录;
            P(empty1); //empty1=empty1-1, if empty1<0 block，缓冲区1不为空则阻塞
            P(mutex1); //mutex1=mutex1-1, if mutex<0 block，缓冲区1正在被操作则阻塞
            将记录存入缓冲区1;
            V(mutex1); //mutex1=mutex1+1, if mutex1<=0 wakeup, 如果有等待操作缓冲区1的进程将被唤醒
            V(full1); //full1=full1+1, if full1<=0 wakeup, 缓冲区1放入一个数据，如果PB进程等待取数据则被唤醒
        }
    }

    process PB() {
        while (true) {
            P(full1);
            P(mutex1);
            从缓冲区1取出纪录;
            V(mutex1);
            V(empty1);
            P(empty2);
            P(mutex2);
            将记录存入缓冲区2;
            V(mutex2);
            V(full2);
	    }
	}

    process PC() {
        while (true) {
            P(full2);
            P(mutex2);
            从缓冲区2取出纪录;
            V(mutex2);
            V(empty2);
            打印记录;
        }
    }
coend