操作系统复习-进程同步
|
348
|
0
|
未分类

2049 字
|
8 分钟

进程同步

进程同步的基本概念

进程同步概念的引入

异步环境下的一组并发进程因直接制约而相互发送消息、相互合作、相互等待，使得各进程按一定的速度执行的过程。

两种形式的制约关系

  1. 间接相互制约关系（互斥关系）：临界资源中
  2. 直接相互制约关系（同步关系）

临界资源

使用的时候需要采用互斥的方式访问的资源。

临界区问题

人们把在每个进程中访问临界资源的那段代码称为临界区。组成如下：

  1. 进入区：临界区前用于检查互斥的代码
  2. 临界区
  3. 退出区：临界区之后释放资源
  4. 剩余区：前三部分之外的代码

代码示意如下：

 while(TRUE) {
    进入区
    临界区
    退出区
    剩余区
}

同步机制应该遵守以下四个准则：

 

  1. 空闲让进
  2. 忙则等待
  3. 有限等待
  4. 让权等待（原则上遵守，非必须）：程序不能进入自己的临界区的时候，应该释放处理机资源

信号量机制

信号量机制介绍

整型信号量

用于表示资源数量的整形数据S。仅可以通过两个原子操作进行访问：wait(S)、singal(S)。这两个信号量可以描述为：

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

signal(S) {
    S++;
}

因为S <= 0的时候一直在测试，所以不满足让权等待。

记录型信号量

有一个表示资源数目的整形变量value，一个进程链表指针list。其代码描述为：

typedef struct {
    int value;  // 初值为拥有的资源数
    struct rocess_control_block *list;   // 进程等待序列，以PCB的方式存储
} semaphore;

其wait和signal操作可以描述为：

wait(semaphore *S) {
    S -> value--;
    if(S -> value < 0) block(S -> list);  // 自行阻塞
}
signal(semaphore *S) {
    S -> value++; 
    if(S -> value <= 0) wakeup(S -> list);  // 唤醒队列中的进程
    // S <= 0的原因：等待队列中有阻塞的进程
}

其中，value的值为1的话，表示为互斥信号量。

AND型信号量

将进程在整个运行的过程中，一次性的分配给进程，使用完后再一起释放。比如：

process A:wait(S1);wait(S2);process B:wait(S2);wait(S1);

信号量集

当所申请的资源低于某一个下限值的时候，不给予分配。对此，改进AND信号量，一次的wait或者signal就对所有资源进行操作，例如：

Swait(S1, t1, d1;...Sn, tn, dn)
Signal(S1, d1; ... Sn, dn)

每次不是对1进行测试，而是对下限值tn进行测试。

信号量集有三种特殊情况：

  1. Swait(S, d, d)
  2. Swait(S, 1, 1)：退化为一般的记录型信号量（S>1）或互斥信号量
  3. Swait(S, 1, 0)：可控开关，当S>=1的时候允许多个进程进入临界区，S=0时不允许任何进程进入。

信号量的应用

信号量实现进程互斥

设置一个互斥信号量mutex=1，对mutex进行wait和signal即可。

信号量实现进程同步

假设P1和P2中有两段代码C1和C2.如果要强制C1先于C2执行，可以写如下代码：

 semaphore S = 0;

P1:
while(TRUE) {
    C1;
    signal(S);
    ....
}   

P2:
while(TRUE) {
    wait(S);
    C2;
    ....
}

经典的进程同步问题

生产者-消费者问题

某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题。

（1）用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。

（2）根据所定义的信号量，利用PV操作写出能正确并发执行的进程。

(1) 定义一个信号量为S，初始值为20。含义如下：
S > 0 表示售票厅可以继续进入
S = 0 表示售票厅满
S < 0 表示需要在外面等待
(2) PV操作如下：
process n (n = 1, 2, 3 ...)
while(TRUE) {
    wait(S);
    购票;
    signal(S);
}

有两个生产者a、b不断向仓库存放产品，由销售者c取走仓库中产品（仓库初态为空，仓库容量为无限大）。请写出通过P、V操作实现3个进程间的同步和互斥的框图或伪程序，并写出信号量的初值和意义。

(1) mutex = 1：互斥信号量给a和b和c
production = 0：表示仓库内的产品
(2) PV操作如下：
process a/b:
while(TRUE) {
    wait(mutex);
    放入产品;
    signal(production);
    signal(mutex);
}
process c:
while(TRUE) {
    wait(production);
    wait(mutex);
    取走产品;
    signal(mutex);
}

有三个并发进程R、W1和W2，共享两个各可存放一个数的缓冲区B1、B2。进程R每次从输入设备读入一个数，若读入的是奇数，则将它存入B1中，若读入的是偶数，将它存入B2中；当B1中有数，由进程W1将其打印输出；当B2中有数，进程W2将其打印输出。试编写保证三者正确工作的程序。

struct semaphone B1_Empty, B1_Full, B2_Empty, B2_Full;
B1_Empty.value=1;
B1_Full.value=0;
B2_Empty.value=1;
B2_Full.value=0;
void R( ) {	
    int a;
    While(1) {
	read a number a;
	if(a%2==1) {	
            wait(B1_Empty);
            put a in B1;
            signal(B1_Full);
        } else {	
            wait(B2_Empty);
            put a in B2;
            signal(B2_Full);
	}
    }
}
void W1( ) {	
    while(1) {	
        wait(B1_Full);
	print a number from B1;
	signal(B1_Empty);
    }
}
void W2( ) {	
    while(1) {	
        wait(B2_Full);
        print a number from B2;
	signal(B2_Empty);
    }
}
void main( ) {
    R( );
    W1( );
    W2( );
}
 

读者-写者问题

a、b两点之间是一段东西向的单行道，现要设计一个自动管理系统，管理规则如下：当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一个方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点（b点）的车辆可以进入ab段，但不能从a点和b点同时驶入，当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量为工具，对ab段实现正确的管理以保证行驶安全。

semaphore S1 = 1, S2 = 1, Sab = 1;
int ab = ba = 0;

void Pab() {
    while(1) {
        wait(S1);
        if(ab == 0) wait(Sab);
        ab = ab + 1;
        signal(S1);
        从a开往b;
        wait(S1);
        ab = ab - 1;
        if(ab == 0) signal(Sab);
        signal(S1);
    }
}

void Pab() {
    while(1) {
        wait(S2);
        if(ba == 0) wait(Sba);
        ba = ba + 1;
        signal(S2);
        从b开往a;
        wait(S2);
        ba = ba - 1;
        if(ba == 0) signal(Sba);
        signal(S2);
    }
}

其他问题

有3个并发执行的进程A，B，C，它们在执行时都要读共享文件F。限定：进程A和进程B可同时读文件F，进程B和进程C也可同时读文件F，但不允许进程A和进程C同时读文件F。请回答下列问题：

（1）用PV操作实现管理时应怎样定义信号量及其初值？

（2）写出用PV操作管理3个进程的程序。

semaphore mutex = 1;

process A:
while(1) {
    wait(mutex);
    读文件;
    signal(mutex);
}

process B:
while(1) {
    读文件;
}

process C:
while(1) {
    wait(mutex);
    读文件;
    signal(mutex);
}

设公共汽车上，司机和售票员的活动分别是：司机活动：启动车辆、正常行车、到站停车；售票员活动：关车门、售票、开车门。

要求：当发车时间到，售票员关好车门后，司机才能启动车辆，售票员开始售票；当到站后，司机停车后，售票员才能打开车门，乘客下车，站牌乘客上车。

在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用信号量和P、V操作实现他们的同步。

 semaphore doorMutex = 0, stopMutex = 0;

process driver:
while(1) {
    wait(doorMutex);
    启动车辆;
    正常行驶;
    到站停车;
    signal(stopMutex);
}
    


process waiter:
while(1) {
    关门;
    signal(doorMutex);
    售票;
    wait(stopMutex);
    开车门;
    乘客上下车;
}

公路上有一座桥，该桥一次只允许一辆汽车在桥上行驶。当桥上有汽车时，其它汽车不能上桥。试问：

（1）这是一个同步问题还是互斥问题？

（2）用信号量和P、V操作描述并发过程的活动。

(1) 是一个互斥问题
(2) PV操作如下:
semaphore mutex = 1;
process car_n: (n = 1, 2, 3, ...)
while(1) {
    wait(mutex);
    上桥;
    下桥;
    signal(mutex);
}

在一个盒子里混装了数量相等的围棋白子和黑子,现在要用自动分拣系统把白子和黑子分开，设分拣系统有两个进程P1和P2,其中P1捡白子、P2捡黑子，规定每个进程每次只捡一子，当一个进程正在捡子时不允许另一个进去，当一个进程捡完一子时必须让另一个进程去捡，试写出这两个并发进程能够正确执行的程序。

semaphore white = 1, black = 0;

process A:
while(1) {
    wait(white);
    捡白子;
    signal(black);
}

process B:
while(1) {
    wait(black);
    捡黑子;
    signal(white);
}

假设有一个路口，通行交通规则如下：只要没有机动车在通行，路口行人就可以通过，只有没有行人在通过路口且没有其他机动车在通过路口时该机动车才能通过。请用P、V操作描述行人和机动车通过路口的同步互斥过程。

semaphore road = 1, rmutex = 1;
int count = 0;

process Person:
while(1) {
    wait(rmutex);
    count++;
    if(count == 1) wait(road);
    signal(rmutex);
    通过路口;
    wait(rmutex);
    count--;
    if(count == 0) signal(road);
    sinal(rmutex);
}

process Car:
while(1) {
   wait(road);
   通过路口;
   signal(road);
}
上一篇
下一篇