操作系统-进程通信

刺骨的言语ヽ痛彻心扉 2022-08-14 05:45 288阅读 0赞

进程通信中的难点是对临界区的互斥访问，下面我们来看一下

### 忙等待的互斥 ###

**锁变量**

其实我们很容易想到的解决方案就是加锁，

int lock,cnt;
    void solve_fork()
    {
        while(lock==1);
        lock = 1;
        cnt++;  
        printf("%d 进入了临界区\n",getpid());
        lock = 0;
    }

同时我们也很容易发现这样是有问题的，两个进程同时判断lock，然后都加锁，然后同时进入临界区，其实用上面代码测试的话发现，基本上很多时候都是会同时访问临界区的。当然解决方案很简单，就是让判断和加锁变成一个原子操作，比如后面要说的信号量或者是用硬件加锁，硬件加锁类似于我们用的开关，可以用寄存器来实现，完全可行。

**严格轮换法（自旋锁）**  
这个其实是对加锁的一个上述问题的一个改进，其原理就是每次两个进程去等待一个不同的值。

int lock,cnt;
    void solve_fork1()
    {
        while(lock==1) {}
        cnt++;
        printf("%d 进入了临界区\n",getpid());
        lock = 1;
    }
    void solve_fork2()
    {
        while(lock == 0) {}
        cnt++;
        printf("%d 进入了临界区\n",getpid());
        lock = 0;
    }

上面这样就实现了互斥访问不会出错，但是同样也是有问题的，首先他是通过忙等来解决问题的，其次，他这能解决两个进程竞争的情况。

**Peterson解法**  
解法结果类似于上面的情况，但是思想不一样。可以研究一下

const int N = 2;
    int lock;
    int inter[N];
    
    void enter_region(int pro) // 传入参数0/1
    {
        int other;
        other = 1 - pro;
        inter[pro] = 1;
        lock = pro;
        while(lock == pro && inter[other] == 1);
    }
    void leave_region(int pro)
    {
        inter[pro] = 0;
    }

### 非忙等待互斥 ###

**信号量**

这个应该算是最常见的了，其原理上面锁变量说过了，这是把他变成了一个原子操作，但是怎么变成一个原子操作呢，操作系统内部是怎么实现这个原子操作呢？  
其实上面介绍的方法都是可用的， 只是要解决忙等的情况，这里说一种操作系统实现的情况，对于多核的来说，操作系统使用TSL指令来实现原子操作，指令为 `TSL RX LOCK`,即把lock的值copy到RX寄存器中，同时执行TSL的指令的CPU将锁住内存总线。防止其他CPU在这个指令结束之前访问。其实就是理解成上面说的开关。  
这里还有一个问题就是忙等，这个可以用sleep和wakeup原语来解决。当另一个访问结束之后用wakeup原语激活当前进程。  
当然除了信号量还有互斥信号量的概念，就是不用计数，只为0或1的信号量

**管道程序**

这个Linux用过的话应该不难理解，就是Linux上面的’ | ‘符号，可以理解成一个管道，我们把一个进程产生的数据作为另一个经常需要输入的数据，然后通过一个管道传递给第二个进程，Linux上面的实现是开一个管道，一边关闭读，另一边关闭写，然后进行通信就ok。

**共享存储**

其实就是给两个进程开一块能够同时访问的共享存储空间，然后到时候交替访问就可以实现，开启共享的系统调用时，分别用于开启和关闭共享存储空间  
`shmget(key_t key, size_t size, int flag)`  
`shmdt(void *addr)`

**消息队列**  
把要通信的字段写入消息队列，然后另一个要用的进程去消息队列中取

### 经典IPC问题 ###

**哲学家就餐问题**  
5个哲学家要吃饭，一共有五个筷子在一个圆桌上，哲学家大多数时候在思考，饿了会吃饭，然后怎样设计一个方案使得不饥饿且能高效的吃饭。  
首先看看如果每个哲学家饿了自由的去拿筷子吃饭会发生什么情况，假如他们先拿左边的筷子，拿到之后拿右边的，这样加入5个人同时饿了，然后去拿左边的筷子，然后成功，都去拿右边的筷子，都不成功，这样就发生死锁，没有变法进行下去了。  
一个很直观的解决方案是，如果拿了左边筷子之后去拿右边筷子不能拿的话，就放下筷子，去等待一个随机数，然后在去拿，这样首先能够解决不发生死锁，但是由于是一个随机数，结果不可控，所以性能不够好。  
其实更好的方案是，用and信号量，即把拿左边和右边当成是一个原子操作，释放的时候也一样，可优化点，在当前吃完之后，检查左边和右边是不是处于饥饿状态，需要的话就唤醒让吃饭.

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stdint.h>
    #include <stdbool.h>
    #include <errno.h>
    
    #include <unistd.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <sys/ipc.h>
    #include <sys/sem.h>
    #include <sys/wait.h>
    
    #ifdef  _SEM_SEMUN_UNDEFINED
    union semun
    {
        int val;
        struct semid_ds *buf;
        unsigned short *array;
        struct seminfo *__buf;
    };
    #endif
    
    #define ERR_EXIT(m) \
        do { \
            perror(m); \
            exit(EXIT_FAILURE); \
        } while(0)
    
    int
    wait_1fork(int no,int semid)
    {
        //int left = no;
        //int right = (no + 1) % 5;
        struct sembuf sb = {no,-1,0};
        int ret;
        ret = semop(semid,&sb,1);
        if(ret < 0) {
            ERR_EXIT("semop");
        }
        return ret;
    }
    
    int
    free_1fork(int no,int semid)
    {
        struct sembuf sb = {no,1,0};
        int ret;
        ret = semop(semid,&sb,1);
        if(ret < 0) {
            ERR_EXIT("semop");
        }
        return ret;
    }
    
    //这里表明叉子是一个临界资源
    #define DELAY (rand() % 5 + 1)
    //相当于P操作
    void
    wait_for_2fork(int no,int semid)
    {
        //哲学家左边的刀叉号数
        int left = no;
        //右边的刀叉
        int right = (no + 1) % 5;
    
        //刀叉值是两个
        //注意第一个参数是编号
        struct sembuf buf[2] = {
            {left,-1,0},
            {right,-1,0}
        };
        //信号集中有5个信号量，只是对其中的
        //资源sembuf进行操作
        semop(semid,buf,2);
    }
    
    //相当于V操作
    void
    free_2fork(int no,int semid)
    {
        int left = no;
        int right = (no + 1) % 5;
        struct sembuf buf[2] = {
            {left,1,0},
            {right,1,0}
        };
        semop(semid,buf,2);
    }
    
    
    
    void philosophere(int no,int semid)
    {
        srand(getpid());
        for(;;) {
        #if 1
            //这里采取的措施是当两把刀叉都可用的时候
            //哲学家才能吃饭，这样不相邻的哲学家就可
            //吃上饭
            printf("%d is thinking\n",no);
            sleep(DELAY);
            printf("%d is hungry\n",no);
            wait_for_2fork(no,semid);//拿到叉子才能吃饭
            printf("%d is eating\n",no);
            sleep(DELAY);
            free_2fork(no,semid);//释放叉子
        #else
            //这段代码可能会造成死锁
            int left = no;
            int right = (no + 1) % 5;
            printf("%d is thinking\n",no);
            sleep(DELAY);
            printf("%d is hungry\n",no);
            wait_1fork(left,semid);
            sleep(DELAY);
            wait_1fork(right,semid);
            printf("%d is eating\n",no);
            sleep(DELAY);
            free_2fork(no,semid);
        #endif
        }
    }
     :
    int
    main(int argc,char *argv[])
    {
        int semid;
        //创建信号量
        semid = semget(IPC_PRIVATE,5,IPC_CREAT | 0666);
        if(semid < 0) {
            ERR_EXIT("semid");
        }
        union semun su;
        su.val = 1;
        int i;
        for(i = 0;i < 5;++i) {
            //注意第二个参数也是索引
            semctl(semid,i,SETVAL,su);
        }
        //创建4个子进程
        int num = 0;
        pid_t pid;
        for(i = 1;i < 5;++i) {
            pid = fork();
            if(pid < 0) {
                ERR_EXIT("fork");
            }
            if(0 == pid) {
                num = i;
                break;
            }
        }
        //这里就是哲学家要做的事情
        philosophere(num,semid);
        return 0;
    }

**生产者消费者问题**  
此问题关键在于，对缓冲区的访问是互斥的，所以需要一个信号量mutex，其次满了之后生产者不能放入产品，所以需要一个full变量，显示产品出来，空了之后消费者不能取，所以需要一个empty来保存还可以放入的物品数目，每次down的时候后操作mutex，释放的时候先释放mutex，可以尝试写一下代码。