Linux多进程4种策略实现哲学家进餐问题
1. 任务简介一张圆桌上坐着5名哲学家,每两个哲学家之间的桌上摆一根筷子,桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐,哲学家在思考时,并不影响他人。只有当哲学家饥饿时,才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子己在他人手上,则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐,当进餐完毕后,放下筷子继续思考。本实验要求利用Linux多进程实现哲学家进餐问题。2. 思路
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 <time.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/sem.h>
#include <sys/shm.h>
#include <sys/ipc.h>
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)
/* union semun is defined by including <sys/sem.h> */
#else
/* according to X/OPEN we have to define it ourselves */
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};
/* semSet[0 - PHILNUM-1]: chopsticks, initial value 1
semSet[PHILNUM]: restrict number / candidacy, initial value PHILNUM-1
semSet[PHILNUM + 1]: server, initial value 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)
{
/* restrict numbers */
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)
{
/* left or right */
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)
{
/*simultaneously left and right*/
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)
{
/* server */
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 <time.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/sem.h>
#include <sys/shm.h>
#include <sys/ipc.h>
#define SEMKEY 123
#define SHMKEY 456
#define PHILNUM 5
#define SEMNUM PHILNUM + 2
#if defined(__GNU_LIBRARY__) && !defined(_SEM_SEMUN_UNDEFINED)
/* union semun is defined by including <sys/sem.h> */
#else
/* according to X/OPEN we have to define it ourselves */
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};
/* semSet[0 - PHILNUM-1]: chopsticks, initial value 1
semSet[PHILNUM]: restrict number / candidacy, initial value PHILNUM-1
semSet[PHILNUM + 1]: server, initial value 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 thinking\n", id);
sleep(random() % 2);
}
void Eat(int id)
{
printf("philosophy %d is eating\n", 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! exit\n");
}
void Philosopher1(int semId, int id)
{
/* restrict numbers */
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)
{
/* left or right */
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)
{
/*simultaneously left and right*/
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)
{
/* server */
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)
实现奇服务生法,结果如下:
我们可以很轻易的通过上图所示的缓冲池可视化结果,验证我们程序的正确性,至此实验部分介绍完毕。
更多推荐
所有评论(0)