进程的同步与通信

进程间的联系

1. 资源共享关系
2. 相互合作关系

临界资源的含义

采取互斥的方式,实现共享的资源 ，一次只能供一个进程使用

临界资源典型案例

临界区的含义

每个进程中访问临界资源那段程序称为临界区

同步机制遵循原则

为了实现进程互斥，设置同步机制来协调诸进程，但进程必须遵循下述4条准则：

• 空闲让进
• 忙则等待
• 有限等待
• 让权等待

信号量机制

记录型信号量机制

信号量除初始化外，仅能通过两个标准的原子操作wait(s)和signal(s)来访问，也称为P、V操作，这是两个原子操作

P、V操作——执行时不可中断的，同时也是互斥的

P—wait(s)

V—signal(s)

相应的，wait(s)和signal(s)操作可描述如下：

void wait(static semaphore s)//申请资源
{
    s.value--;//表示资源数目
    if(s.value<0)
        block(s,L);//自我阻塞
}
void signal(static semaphore s)//释放资源
{
    s.value++;
    if(s.value<=0)
        wakeup(s,L);//唤醒进程访问临界资源
}

注意：wait()和signal()必须成对出现

缺少wait()导致系统混乱，不能保证对临界资源的互斥访问

缺少signal()将会使临界资源永远不被释放，导致等待该资源的进程不被唤醒

实例

看图写代码

main(){
	semaphore a=b=c=d=e=f=g=0;
    cobegin{
        {T1;signal(a);signal(b);}//T1用完后，释放资源，空闲资源供T2,T3可用
        {wait(a);T2;signal(c);signal(d);}//T2申请资源a，T2用完后，释放资源，空闲资源T4,T5可用
        {wait(b);T3;signal(e);}//T3申请资源b,T3用完后，释放资源e
        {wait(c);T4;signal(f);}//T4申请资源c,T4用完后，释放资源f
        {wait(d);T5;signal(g);}//T5申请资源d,T5用完后，释放资源g
        {wait(e);wait(f);wait(g);T6;}//T6使用资源必须在e,f,g都释放之后才可以使用
    }
}

生产者消费者问题

英文普及

生产者——Producer

消费者——Consumer

代码分析

semaphore mutex=1,empty=n,full=0;
item buffer[n];
int in=out=0;
void producer(int i)
{
    while(1)
    {
		···
        produce an item in nextp;
        ···
        wait(empty);//申请放，请求空的区域，看是否能放
        wait(mutex);//看进程是否可申请到临界资源
        buffer[in]=nextp;
        in=(in+1) mod n;
        signal(mutex);//释放临界资源
        signal(full);//放操作
    }
}
void consumer(int j)
{
    while(1)
    {
		···
        produce an item in nextp;
        ···
        wait(full);//申请取，请求满的区域，看是否能取
        wait(mutex);//看进程是否可申请到临界资源
        nextc=buffer[out];
        out=(out+1) mod n;
        signal(mutex);//释放临界资源
        signal(empty);//取操作
    }
}

生产者-消费者问题中应注意以下几点

• wait(mutex)和signal(mutex)必须成对出现
• 对资源信号量empty和full的wait和signal操作，同样需要成对出现
• 先执行对资源信号量的wait操作，再执行对互斥信号量的wait操作，否则可能引起死锁

若缓冲池全空，消费者无法取，若全满，生产者无法放

死锁定义

多个进程在执行过程中，因争夺被另一个进程占有且永远不会释放的资源的现象称为死锁

死锁的例子

产生死锁的原因

• 竞争资源
  • 竞争可剥夺性资源
    • 进程优先权竞争处理机
  • 竞争非剥夺性资源
    • 进程资源环形链——I/O设备共享时的死锁情况
  • 竞争临时性资源
• 进程推进顺序不当

环路等待情况(竞争非剥夺性资源)

R1分配给P1，R2分配给了P2

P1请求着R2，P2请求着R1(而R1在P1手里，未释放，R2在P2手里，未释放)

因此形成一种环形链，进入死锁状态

产生死锁的必要条件

• 互斥条件
• 请求和保持条件
• 不剥夺条件
• 环路等待条件

解决死锁的基本方法

• 预防死锁
• 避免死锁
  • 银行家算法
• 监测死锁
• 解除死锁

银行家算法

具有代表性的避免死锁的算法是Dijkstra的银行家算法