操作系统之进程同步

进程同步

线程同步的概念大家都比较清楚,线程是共享内存的,因此对共享内存中的数据并发访问可能会导致数据不一致,那么进程同步是要解决什么呢,因为进程之间可以相互协作,因此也会共享内存,所以也要有同步机制,接下来我们先用经典的生产者和消费者来具体说明进程间的协作可能带来的共享数据不一致的情况

生产者和消费者

操作系统之进程中我们提到了进程间通信的一种方式:管道(这里指匿名管道),管道其实就在内存中的一块共享区域,建立管道的两个进程之间可以通过这个共享区域进行数据的共享,共享方式为:数据的产生者,也就是我们的生产者将数据从管道的一端写入,然后消费者从管道的另一端取数据,生产者消费者第一个实现:用一个数组表示我们的共享缓存区,用一个指针in表示生产者放入的位置,另一个指针out表示消费者读的位置,初始时,两个指针指向同一个位置,消费者通过out等于in知道现在缓存为空,不能取数据,生产者用(in + 1) % n (n为缓存去大小,可以循环写入)不等于out知道现在缓存区还没有满,可以继续写入,但是这里会浪费一个缓存的单元,因为生产者和消费者不能同时通过判断in是非等于out来确定缓存是满或者空,必须浪费一个单元。这是第一版的生产者和消费者实现,有一个不足,那就是浪费了一个单元,我们应该进行优化。于是增加一个变量,用来记录缓冲区还有多少个空的数据单元,然后根据生产者和消费者的操作进行增减,这个时候会出现一个新的问题,因为生产者和消费者属于两个不同的进程,由于增加该变量的操作非原子操作,会造成这个变量的数值错误:

由于并发和非原子操作的原因,可能会造成共享数据的错误,这就是同步问题中的一类同步问题

临界区问题

上面的这个问题称为临界区问题,临界区问题有以下条件:

  • 有n个进程竞相访问共享数据的
  • 进程中有一段代码,这段代码就是访问共享数据的代码,代码对数据的操作是非原子性的
  • 如果n个进程中,有1个以上进程存在对同一个数据的临界区

如果有以上条件,就可能造成临界区问题,显而易见,解决临界区问题的办法就是,如果有一个进程正在自己的临界区执行,不允许其他进程在它的临界区执行,临界区问题解决的三个条件:

  • 互斥:如果进程i正在临界区执行,那么其他任何进程不允许在它的临界区中
  • 空闲让进:没有进程在临界区,从申请进入临界区的进程中选举一个进程进入,不在临界区的不参加选举
  • 有限等待:某一个进程申请进入临界区和进入临界区的时间是有限时间(这之间可以有其他申请临界区进程进入,但是其他进入的次数必须在某一个上界以内)

注意,上面的临界区都是说的对某一个同样的共享数据的临界区

面包房算法

  1. 每当进程进入临界区,分配一个数
  2. 进程分配的数小的进入,如果该数相同,则进程id小的进入

但是在操作系统中,这个方法没有被采用,因为如果每个程序都需要自己在自己的每一个临界区应用程序来做这些编程判断,成本很高,我们需要用一种方案,程序不需要做什么,或者做很少的操作,将主要的工作交给操作系统来完成,于是有了信号量

信号量

一个信号量是一个对象,对象中有一个值和一个队列,另外提供两个方法,两个方法都保证是原子操作,如果某一个进程想进入通过区,就调其中一个方法wait(S)(S表示信号量):

这个方法将信号量的变量减1,然后如果减1后小于零了,则该PCB堵塞,交出CPU并且进入等待队列,如果不小于它可以继续执行。如果可以继续执行,执行完毕后退出临界区后调signal(S):

这个方法把变量加1,如果变量值小于或等于零,则将队列中一个PCB唤醒让它进入就绪队列,于是对于某一个进程,它在进入临界区和离开临界区分别会调用这两个方法:

信号量解决生产者和消费者问题

定义三个信号量,一个m为初始为1,一个empty初始为缓存的长度,一个full初始为0。于是生产者:

wait(empty)
wait(m)
    // 写操作
singal(m)
singal(empty)

消费者:

wait(full)
wait(m)
    // 读操作
singal(m)
singal(full)

读者-写者问题

读者写者问题和生产者和消费者问题比较类似,但是读者写者问题特殊于读者和写者都是多个,同时读者和读者之间可以并行,而某一个写者和任何一个写者/读者都必须互斥。读者写者存在两个问题,第一类读者写者问题是:写者不断的进入临界区(互斥进入),而造成读者的饥饿。第二类读者写者问题是,如果读者之间不互斥,持续的读者不断的进入临界区(不互斥的进入),就会造成写者饥饿。第一类问题的解决,用两个信号量和一个变量,其中一种信号量用来同步那个变量,就是有多少的读者,每次一个读者进入临界区,就对变量加一,离开临界区就对变量减一,另一个信号量来同步读者和写者,当变量值大于1时,读者直接进临界区,当变量为0的时候,才释放读写的信号量:

第二类的读者写者问题,我们可以在增加一个信号量,这个信号量是专门用来标识写者,如果该信号量小于0,则读者不能进入临界区,主要是通过增加写者的优先级来防止第二类问题的产生:

semaphore fmutex=1, rdcntmutex=1, wtcntmutex=1, queue=1;

int readcount = 0, writecount = 0;

void writer(){
    while(1){
        wait(wtcntmutex);
        wait(queue);
        writecount = writecount + 1;
        signal(wtcntmutex);
        wait(fmutex);
        //Do write operation ...
        signal(fmutex);
        wait(wtcntmutex);
        writecount = writecount - 1;
        if(0 == writecount) signal(queue);
        signal(wtcntmutex);
    }
}

void reader(){
    while(1){
        wait(queue);
        wait(rdcntmutex);
        if(0 == readcount) wait(fmutex);
        readcount = readcount + 1;
        signal(rdcntmutex);
        signal(queue);
        //Do read operation ...
        wait(rdcntmutex);
        readcount = readcount - 1;
        if(0 == readcount) signal(fmutex);
        signal(rdcntmutex);
    }
}

哲学家吃饭问题

有5个哲学家,每一个哲学家之间只有一只筷子,一个哲学家要吃饭,必须身边的两根筷子都在桌子上才能吃饭,能够想到的就是给每一根筷子用一个信号量,然后某一个哲学家使用时,操作它要用的筷子对应的两个信号量,但是这个方案有缺陷,会造成死锁:拿起其中一个筷子时,另一筷子被拿走了,因为拿起两个筷子不是原子操作。哲学家吃饭问题有很多解决方案:

  1. 只能四个人吃饭:增加一个信号量初始值为4
  2. 不对称解:相邻哲学家拿筷子的手一致
  3. 所有哲学家都先拿奇数号筷子,再拿偶数号筷子

以下只给出第一个解决的详细过程

Semaphore chopstick[5]={1,1,1,1,1}; //分别表示5支筷子
Semaphore footman=4; //初始值为4最多允许4个哲学家进程同时进行
Philosopher(init)
{
    while(true)
    {
        wait(footman);
        wait(chopstick[i]);//申请左筷子
           wait(chopstick[(i+1)%5]);//申请右筷子
        eat();
        signal(chopstick[i]);//释放左筷子
        aignal(chopstick[(i+1)%5]);//释放右筷子
        aignal(footman);
    }
}
坚持原创分享,您的支持将鼓励我不断前行!