Linux多进程4种策略实现哲学家进餐问题

1. 任务简介

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子己在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

本实验要求利用Linux多进程实现哲学家进餐问题。

2. 思路分析

我们分析题目中的同步和互斥关系：

2.1 同步关系

本题中并不存在需要特别关注的同步关系

2.2 互斥关系

系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系

2.3 整体思路

这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。

这里我们提供4种解决方案：

限制位置法：至多只允许有4位哲学家同时去拿左边的筷子，最终能保证至少有1位哲学家能够进餐，并在进餐牛时能释放出他用过的2根筷子，从而使更多的哲学家能够进餐。
奇偶划分法：规定奇数号哲学家先拿他左边的筷子，然后再去拿他右边的筷子；而偶数号哲学家则相反。按此规定，1号、2号哲学家将竞争1号筷子；3号、4号哲学家将克争3号筷子。即5位哲学家都先竞争奇数号筷子，获得后，再去竞争偈数号筷子，圾后总会有一位哲学家能获得两根筷子而进餐。
同时满足法：仅当哲学家的左右两根筷子均可用时，才允许他拿起筷子进餐。
服务生法：设置一个服务生，用于给哲学家服务，当系统存在哲学家所需的资源时，给哲学家分配相应的资源；否者，拒绝哲学家的请求。一个服务生同一时间仅可给一个哲学家服务。

程序具体流程如下图所示：

3. 代码实现 3.1 头文件

首先，我们包含实现问题所需的头文件：

#include 
#include 
#include 
#include 
#include 
#include 
#include

3.2 预定义和数据结构

我们采用共同协商关键字SEMKEY，SHMKEY的方法使得不同进程间可以取得同一个信号量和共享内存
定义了一个结构体Chopstick标记筷子的使用情况（服务生法中将会使用）

#define SEMKEY 123
#define SHMKEY 456
#define PHILNUM 5
#define SEMNUM PHILNUM + 2


#if defined(__GNU_LIBRARY__) && !defined(_SEM_SEMUN_UNDEFINED)
 
#else 
 
union semun
{
	int val;
	struct semid_ds *buf;
	unsigned short *array;
};
#endif

struct Chopstick
{
    int chopstick[PHILNUM];
};

3.3 初始化函数

我们利用协商好的SEMKEY生成一个信号量集，其中第1 - PHILNUM的信号量为筷子，表示剩余筷子的个数；第PHILNUM + 1个信号量为限制数目，表示允许同时吃饭的哲学家最大个数（限制位置法中使用）；第PHILNUM + 2个信号量为server，控制对于服务生的互斥访问（服务生法中将会使用）。
利用协商好的SHMKEY生成一个共享内存集，用于存放结构体Chopstick标记筷子的使用情况（服务生法中将会使用）
我们利用*returnSemId， *returnShmId和**returnShm三个指针来返回初始化的参数

具体实现如下：

void Initialize(int *returnSemId, int *returnShmId, struct Chopstick**returnShm)
{
    int semId = -1, shmId = -1, values[SEMNUM] = {1, 1, 1, 1, 1, PHILNUM - 1, 1};

    

    semId = semget(SEMKEY, SEMNUM, IPC_CREAT | 0666);
    if(semId == -1)
    {
        printf("semaphore creation failed!n");
        exit(EXIT_FAILURE);
    }

    int i = 0;
    union semun semUn;
    for(i = 0; i < SEMNUM; i ++)
    {
        semUn.val = values[i];
        if(semctl(semId, i, SETVAL, semUn) < 0)
        {
            printf("semaphore %d initialization failed!n", i);
            exit(EXIT_FAILURE);
        }
    }

    shmId = shmget(SHMKEY, sizeof(struct Chopstick), IPC_CREAT | 0666);
    if(shmId == -1)
    {
        printf("share memory creation failed!n");
        exit(EXIT_FAILURE);
    }

    void *temp = NULL;
    struct Chopstick *shm = NULL;
    temp = shmat(shmId, 0, 0);
    if(temp == (void *) -1)
    {
        printf("share memory attachment failed!n");
        exit(EXIT_FAILURE);        
    }
    shm = (struct Chopstick *) temp;

    for(i = 0; i < PHILNUM; i++)
    {
        shm -> chopstick[i] = 1;
    }

    *returnSemId = semId;
    *returnShmId = shmId;
    *returnShm = shm;
}

3.4 PV操作

给定信号量集的semId以及待操作的信号量下标semNum，其P操作和V如下所示：

void SemWait(int semId, int semNum)
{
    struct sembuf semBuf;
    semBuf.sem_num = semNum;
    semBuf.sem_op = -1;
    semBuf.sem_flg = SEM_UNDO;
    if(semop(semId, &semBuf, 1) == -1)
    {
        printf("semaphore P operation failed!n");
        exit(EXIT_FAILURE);
    }
}

void SemSignal(int semId, int semNum)
{
    struct sembuf semBuf;
    semBuf.sem_num = semNum;
    semBuf.sem_op = 1;
    semBuf.sem_flg = SEM_UNDO;
    if(semop(semId, &semBuf, 1) == -1)
    {
        printf("semaphore V operation failed!n");
        exit(EXIT_FAILURE);
    }
}

3.5 AND信号量

在同时满足法中，我们需要实现AND型信号量，同时完成对于左右两边筷子的操作，具体实现如下：

void SSemWait(int semId, int semNum)
{
    int i = 0;
    struct sembuf semBuf[2];
    for(i = 0; i < 2; i ++)
    {
        semBuf[i].sem_num = (semNum + i) % PHILNUM;
        semBuf[i].sem_op = -1;
        semBuf[i].sem_flg = SEM_UNDO;
    }

    if(semop(semId, semBuf, 2) == -1)
    {
        printf("semaphore SP operation failed!n");
        exit(EXIT_FAILURE);
    }
}

void SSemSignal(int semId, int semNum)
{
    int i = 0;
    struct sembuf semBuf[2];
    for(i = 0; i < 2; i ++)
    {
        semBuf[i].sem_num = (semNum + i) % PHILNUM;
        semBuf[i].sem_op =  1;
        semBuf[i].sem_flg = SEM_UNDO;
    }

    if(semop(semId, semBuf, 2) == -1)
    {
        printf("semaphore SV operation failed!n");
        exit(EXIT_FAILURE);
    }
}

3.6 限制位置法

利用第PHILNUM + 1个信号量，限制同时吃饭的哲学家最大个数，至多只允许有4位哲学家同时去拿左边的筷子，具体实现如下：

void Philosopher1(int semId, int id)
{
    
    do{

        Think(id);

        // wait candidacy
        SemWait(semId, PHILNUM);
        // wait left chopsticks
        SemWait(semId, id);
        // wait right chopsticks
        SemWait(semId, (id + 1) % PHILNUM);

        Eat(id);

        // signal right chopsticks
        SemSignal(semId, (id + 1) % PHILNUM);
        // singal left chopsticks
        SemSignal(semId, id);
        // signal candidacy
        SemSignal(semId, PHILNUM);

    }while(1);
}

3.7 奇偶划分法

规定奇数号哲学家先拿他左边的筷子，然后再去拿他右边的筷子；而偶数号哲学家则相反。具体实现如下：

void Philosopher2(int semId, int id)
{   
    
    do{

        Think(id);

        if(id % 2 == 0)
        {
            // wait left chopsticks
            SemWait(semId, id);
            // wait right chopsticks
            SemWait(semId, (id + 1) % PHILNUM);

            Eat(id);
            
            // signal right chopsticks
            SemSignal(semId, (id + 1) % PHILNUM);
            // singal left chopsticks
            SemSignal(semId, id);
        }
        else
        {
            // wait right chopsticks
            SemWait(semId, (id + 1) % PHILNUM);
            // wait left chopsticks
            SemWait(semId, id);

            Eat(id);


            // singal left chopsticks
            SemSignal(semId, id);
            // signal right chopsticks            
            SemSignal(semId, (id + 1) % PHILNUM);
        }

    }while(1);
}

3.8 同时满足法

利用AND型信号量实现：仅当哲学家的左右两根筷子均可用时，才允许他拿起筷子进餐。具体代码如下：

void Philosopher3(int semId, int id)
{
    
    do{

        Think(id);

        // wait left & right chopsticks
        SSemWait(semId, id);

        Eat(id);

        // singal left & right chopsticks
        SSemSignal(semId, id);

    }while(1);
}

3.9 服务生法

利用第PHILNUM + 2个信号量server，实现服务生。当哲学家左右手都有筷子时，服务生负责给哲学家分配筷子，之后转而给其他哲学家服务；否则，服务生拒绝哲学家的请求，直接转而给其他哲学家服务。哲学家使用完筷子时，需将其归还。具体代码如下：

void Philosopher4(int semId, struct Chopstick * shm, int id)
{
    
    do{

        Think(id);
        
        // wait server
        SemWait(semId, PHILNUM + 1);

        // check the request
        int left = id, right = (id + 1) % PHILNUM;
        if(shm -> chopstick[left] && shm -> chopstick [right])
        {
            // wait left chopsticks
            shm -> chopstick[left] = 0;
            // wait right chopsticks
            shm -> chopstick [right] = 0;

            // signal server
            SemSignal(semId, PHILNUM + 1);

            Eat(id);

            // signal left chopsticks
            shm -> chopstick[left] = 1;
            // signal right chopsticks
            shm -> chopstick [right] = 1;
        }
        else
        {
            // signal server
            SemSignal(semId, PHILNUM + 1);
        }

    }while(1);
}

注意：这里我们并不需要使用信号量集来标记筷子资源，直接通过共享内存访问、操作即可。原因是服务生每次至多给一个哲学家服务，使得服务期间其他哲学家无法争夺系统资源，从而直接保证了互斥性。

3.10 主函数

主函数负责对变量的初始化，产生哲学家进程，以及最后的资源回收。

int main()
{
    int semId = -1, shmId = -1, i=0;
    struct Chopstick *shm = NULL;

    Initialize(&semId, &shmId, &shm);
    for(i = 0; i < PHILNUM; i ++)
    {
        pid_t pid = fork();
        if(pid < 0)
        {
            printf("fork failed!n");
            exit(EXIT_FAILURE);
        }
        else if(pid == 0)
        {
            sleep(2);
            // Philosopher1(semId, i);
            // Philosopher2(semId, i);
            // Philosopher3(semId, i);
            Philosopher4(semId, shm, i);
            return 0;
        }
    }

    getchar();
    Destroy(semId, shmId, shm);
    return 0;
}

注意：getchar（）函数使得父进程接收到一个字符之后，回收系统资源，结束其产生的子进程。

3.11 实验代码

完整实验代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 


#define SEMKEY 123
#define SHMKEY 456
#define PHILNUM 5
#define SEMNUM PHILNUM + 2


#if defined(__GNU_LIBRARY__) && !defined(_SEM_SEMUN_UNDEFINED)
 
#else 
 
union semun
{
	int val;
	struct semid_ds *buf;
	unsigned short *array;
};
#endif

struct Chopstick
{
    int chopstick[PHILNUM];
};

void Initialize(int *returnSemId, int *returnShmId, struct Chopstick**returnShm)
{
    int semId = -1, shmId = -1, values[SEMNUM] = {1, 1, 1, 1, 1, PHILNUM - 1, 1};

    

    semId = semget(SEMKEY, SEMNUM, IPC_CREAT | 0666);
    if(semId == -1)
    {
        printf("semaphore creation failed!n");
        exit(EXIT_FAILURE);
    }

    int i = 0;
    union semun semUn;
    for(i = 0; i < SEMNUM; i ++)
    {
        semUn.val = values[i];
        if(semctl(semId, i, SETVAL, semUn) < 0)
        {
            printf("semaphore %d initialization failed!n", i);
            exit(EXIT_FAILURE);
        }
    }

    shmId = shmget(SHMKEY, sizeof(struct Chopstick), IPC_CREAT | 0666);
    if(shmId == -1)
    {
        printf("share memory creation failed!n");
        exit(EXIT_FAILURE);
    }

    void *temp = NULL;
    struct Chopstick *shm = NULL;
    temp = shmat(shmId, 0, 0);
    if(temp == (void *) -1)
    {
        printf("share memory attachment failed!n");
        exit(EXIT_FAILURE);        
    }
    shm = (struct Chopstick *) temp;

    for(i = 0; i < PHILNUM; i++)
    {
        shm -> chopstick[i] = 1;
    }

    *returnSemId = semId;
    *returnShmId = shmId;
    *returnShm = shm;
}

void Think(int id)
{
    printf("philosophy %d is thinkingn", id);
    sleep(random() % 2);
}

void Eat(int id)
{
    printf("philosophy %d is eatingn", id);
    sleep(random() % 2);
}

void ShmDestroy(int semId, struct Chopstick * shm)
{
    if(shmdt(shm) < 0)
    {
        printf("share memory detachment failed!n");
        exit(EXIT_FAILURE);
    } 
    if(shmctl(semId, IPC_RMID, 0) < 0)
    {
        printf("share memory destruction failed!n");
        exit(EXIT_FAILURE);        
    }
}

void SemWait(int semId, int semNum)
{
    struct sembuf semBuf;
    semBuf.sem_num = semNum;
    semBuf.sem_op = -1;
    semBuf.sem_flg = SEM_UNDO;
    if(semop(semId, &semBuf, 1) == -1)
    {
        printf("semaphore P operation failed!n");
        exit(EXIT_FAILURE);
    }
}

void SemSignal(int semId, int semNum)
{
    struct sembuf semBuf;
    semBuf.sem_num = semNum;
    semBuf.sem_op = 1;
    semBuf.sem_flg = SEM_UNDO;
    if(semop(semId, &semBuf, 1) == -1)
    {
        printf("semaphore V operation failed!n");
        exit(EXIT_FAILURE);
    }
}

void SSemWait(int semId, int semNum)
{
    int i = 0;
    struct sembuf semBuf[2];
    for(i = 0; i < 2; i ++)
    {
        semBuf[i].sem_num = (semNum + i) % PHILNUM;
        semBuf[i].sem_op = -1;
        semBuf[i].sem_flg = SEM_UNDO;
    }

    if(semop(semId, semBuf, 2) == -1)
    {
        printf("semaphore SP operation failed!n");
        exit(EXIT_FAILURE);
    }
}

void SSemSignal(int semId, int semNum)
{
    int i = 0;
    struct sembuf semBuf[2];
    for(i = 0; i < 2; i ++)
    {
        semBuf[i].sem_num = (semNum + i) % PHILNUM;
        semBuf[i].sem_op =  1;
        semBuf[i].sem_flg = SEM_UNDO;
    }

    if(semop(semId, semBuf, 2) == -1)
    {
        printf("semaphore SV operation failed!n");
        exit(EXIT_FAILURE);
    }
}

void SemDestroy(int semId)
{
    union semun semUn;
    if(semctl(semId, 0, IPC_RMID, semUn) < 0)
    {
        printf("semaphore destruction failed!n");
        exit(EXIT_FAILURE);
    }
}

void Destroy(int semId, int shmId, struct Chopstick *shm)
{
    SemDestroy(semId);
    ShmDestroy(shmId, shm);
    printf("destruction finished! exitn");
}

void Philosopher1(int semId, int id)
{
    
    do{

        Think(id);

        // wait candidacy
        SemWait(semId, PHILNUM);
        // wait left chopsticks
        SemWait(semId, id);
        // wait right chopsticks
        SemWait(semId, (id + 1) % PHILNUM);

        Eat(id);

        // signal right chopsticks
        SemSignal(semId, (id + 1) % PHILNUM);
        // singal left chopsticks
        SemSignal(semId, id);
        // signal candidacy
        SemSignal(semId, PHILNUM);

    }while(1);
}

void Philosopher2(int semId, int id)
{   
    
    do{

        Think(id);

        if(id % 2 == 0)
        {
            // wait left chopsticks
            SemWait(semId, id);
            // wait right chopsticks
            SemWait(semId, (id + 1) % PHILNUM);

            Eat(id);
            
            // signal right chopsticks
            SemSignal(semId, (id + 1) % PHILNUM);
            // singal left chopsticks
            SemSignal(semId, id);
        }
        else
        {
            // wait right chopsticks
            SemWait(semId, (id + 1) % PHILNUM);
            // wait left chopsticks
            SemWait(semId, id);

            Eat(id);


            // singal left chopsticks
            SemSignal(semId, id);
            // signal right chopsticks            
            SemSignal(semId, (id + 1) % PHILNUM);
        }

    }while(1);
}

void Philosopher3(int semId, int id)
{
    
    do{

        Think(id);

        // wait left & right chopsticks
        SSemWait(semId, id);

        Eat(id);

        // singal left & right chopsticks
        SSemSignal(semId, id);

    }while(1);
}

void Philosopher4(int semId, struct Chopstick * shm, int id)
{
    
    do{

        Think(id);
        
        // wait server
        SemWait(semId, PHILNUM + 1);

        // check the request
        int left = id, right = (id + 1) % PHILNUM;
        if(shm -> chopstick[left] && shm -> chopstick [right])
        {
            // wait left chopsticks
            shm -> chopstick[left] = 0;
            // wait right chopsticks
            shm -> chopstick [right] = 0;

            // signal server
            SemSignal(semId, PHILNUM + 1);

            Eat(id);

            // signal left chopsticks
            shm -> chopstick[left] = 1;
            // signal right chopsticks
            shm -> chopstick [right] = 1;
        }
        else
        {
            // signal server
            SemSignal(semId, PHILNUM + 1);
        }

    }while(1);
}

int main()
{
    int semId = -1, shmId = -1, i=0;
    struct Chopstick *shm = NULL;

    Initialize(&semId, &shmId, &shm);
    for(i = 0; i < PHILNUM; i ++)
    {
        pid_t pid = fork();
        if(pid < 0)
        {
            printf("fork failed!n");
            exit(EXIT_FAILURE);
        }
        else if(pid == 0)
        {
            sleep(2);
            Philosopher1(semId, i);
            // Philosopher2(semId, i);
            // Philosopher3(semId, i);
            // Philosopher4(semId, shm, i);
            return 0;
        }
    }

    getchar();
    Destroy(semId, shmId, shm);
    return 0;
}

4. 实验结果

我们通过gcc编译器编译源程序philosopher.c，生成目标文件philosopher

我们从控制台输入命令$ ./philosopher，来模拟哲学家进餐情况：

5.1 限制位置法

通过调用Philosopher1(semId, i)实现限制位置法，结果如下：

5.2 奇偶划分法

通过调用Philosopher2(semId, i)实现奇偶划分法，结果如下：

5.3 同时满足法

通过调用Philosopher3(semId, i)实现同时满足法，结果如下：

5.4 服务生法

通过调用Philosopher4(semId, shm, i)实现奇服务生法，结果如下：

我们可以很轻易的通过上图所示的缓冲池可视化结果，验证我们程序的正确性，至此实验部分介绍完毕。

Linux多进程4种策略实现哲学家进餐问题

Linux相关栏目本月热门文章