ph.c

哲学家就餐问题的两种算法实现

#include <signal.h>
#include <sys/types.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include "head.h"

#define PHI_NUMBER 100
#define GROUP_SIZE 5                        /* 组大小应大于3 */
#define MAX_GROUP_NUMBER  210               /* 最大组数 */

void sig_usr1(int, siginfo_t*, void*);      /* 令牌信号 或 查询信号 */
void sig_usr2(int, siginfo_t*, void*);      /*  被查询方的回应信号  */
void sig_quit(int, siginfo_t*, void*);
void sig_alarm(int);
void do_eating();
void do_thinking();
void do_finish();
int  do_checking(pid_t);
void is_hungery();
void send_order(pid_t);     /* 传递令牌 */

static volatile sig_atomic_t   sigflag;
static pid_t                   pid, first_pid, next_pid, last_pid, right_pid;
static int                     begin=-1, hungery, eating, can_use, can_check=0, hungery_level;
static int                     count = 1, temp_level, alarm_flag;
static sigset_t                zeromask, oldmask, newmask, fullmask;

int main()
{
    /* 设置SIGUSR1和SIGUSR2的信号处理程序 */
    struct sigaction   sigquit, sigusr1, sigusr2;
    int i;
    pid_t groupptr[MAX_GROUP_NUMBER];

    sigusr1.sa_sigaction  = (void *)sig_usr1;
    sigusr1.sa_flags      = SA_SIGINFO;
    sigusr2.sa_sigaction  = (void *)sig_usr2;
    sigusr2.sa_flags      = SA_SIGINFO;
    sigquit.sa_sigaction  = (void *)sig_quit;
    sigquit.sa_flags      = SA_SIGINFO;

    if (sigaction(SIGUSR1, &sigusr1, NULL) < 0)
	err_quit("sigaction(SIGUSR1) error");
    if (sigaction(SIGUSR2, &sigusr2, NULL) < 0)
	err_quit("sigaction(SIGUSR2) error");
    if (sigaction(SIGQUIT, &sigquit, NULL) < 0)
	err_quit("sigaction(SIGQUIT) error");
    if (signal(SIGALRM, sig_alarm) < 0)
    	err_quit("signal(SIGALRM) error");
	
    sigemptyset(&zeromask);
    sigemptyset(&newmask);
    sigaddset(&newmask, SIGQUIT);
    sigaddset(&newmask, SIGALRM);
    sigprocmask(SIG_BLOCK, &newmask, &oldmask);

    first_pid = getpid();
    can_use = -1;

    for (count=0; ((count < PHI_NUMBER-1) && (pid == 0)) || count == 0; count++){

        if ((count+1)%GROUP_SIZE == 1 && (PHI_NUMBER-count > GROUP_SIZE-2 || PHI_NUMBER <= GROUP_SIZE-2))
	    groupptr[(count+1)/GROUP_SIZE] = getpid();

        if( (pid=fork()) < 0)
	    err_quit("fork error");

        /* 设置右边哲学家的pid */
        if (pid > 0){              /* 不是最后一个哲学家 */
            right_pid = pid;

            /* 如果是分组的最后一个哲学家 */
            if ((count+1)%GROUP_SIZE == 0 && PHI_NUMBER-(count+1) > GROUP_SIZE-2){
	        next_pid = groupptr[count/GROUP_SIZE];   /* next_pid 置为本组第一个哲学家的pid */
                kill (next_pid, SIGQUIT);                /* 通知本组第一个哲学家 */
	    }
            else
	        next_pid = right_pid;
    	    
            kill(pid, SIGQUIT);            /* 通知下一个哲学家可以开始创建了 */
        }
        else{
	    while (sigflag == 0)
		sigsuspend(&zeromask);
	    sigflag = 0;
	}
    }
    begin = 0;	    

    /* 最后一个哲学家 */ 
    if (pid == 0){
        count = PHI_NUMBER;
        right_pid = groupptr[0];          /* right_pid 设置为第一个哲学家的pid */

    /* 设置 next_pid */
    if (PHI_NUMBER <= GROUP_SIZE+3)
            next_pid = right_pid;
        else
	    next_pid = groupptr[(count-1)/GROUP_SIZE];
	    
        kill(next_pid, SIGQUIT);          /* 通知本组第一个哲学家 */

	if (count <= GROUP_SIZE+3)
	    i=1;
	else if (count%GROUP_SIZE >=3 || count%GROUP_SIZE == 0)
	    i=count/GROUP_SIZE;
	else
	    i=count/GROUP_SIZE-1;

	for (; i>0; i--)                  /* 通知每一组的第一个哲学家可以开始了 */
	    kill(groupptr[i-1], SIGQUIT);
    }

    /* 设置左边哲学家的pid */
    if ( groupptr[count/GROUP_SIZE] == getpid() ){    /* 如果是第一个哲学家 */
        begin = 1;

	/* 等待该组最后一个哲学家的信号 */
        while (sigflag == 0)
	    sigsuspend (&zeromask);
        sigflag = 0;
    }
    else                           /* 不是第一个哲学家 */
        last_pid = getppid();

    hungery_level = 0;



    while(1){
        /* 每一组的第一个哲学家先开始行动 */
        if (begin == 1){
            begin=2;
	    while(begin == 2)
	        sigsuspend(&zeromask);
            do_thinking();
	    is_hungery();
	    do_eating();
	    do_finish();
	    continue;
        }

        do_thinking();
	is_hungery();

        while (1){
            /* 左手 */
            /* 根据 hungery_level 控制重试次数，以避免饥饿 */
            for (temp_level=0; temp_level <= hungery_level; temp_level++)
                if( do_checking(last_pid) )
                    break;
                else
                    sleep(0.5);

            /* 若未能拿到筷子，向下传令牌，并将 hungery_level 加一 */
            if (temp_level > hungery_level){
		send_order(next_pid);
                hungery_level++;
		continue;
	    }

            /* 右手 */
            for (temp_level=0; temp_level <= hungery_level; temp_level++)
                if( do_checking(next_pid) )
		    break;
                else
                    sleep(0.5); 

	    if (temp_level > hungery_level){
		send_order(next_pid);
                hungery_level++;
		continue;
	    }
	    break;
	}

	do_eating();
	do_finish();
    }
    return 1;
}


/* 查询对方状态 */
int do_checking(pid_t pid)
{
    /* 等待令牌 */
    while(can_check == 0)
        can_check=can_check;

    /* 发出查询信号 */
    kill(pid, SIGUSR2);

    while(can_use == -1)
	can_use = can_use;
    
    if (can_use == 1){
        can_use = -1;
        return 1;
    }
    else if(can_use == 0){
	can_use = -1;
        return 0;
    }
    else{
	printf("检查时出错\n");
	return -1;
    }
}

void do_finish()
{
    eating = 0;
    printf("Finish  --- %d\n", count);
    return;
}

/* 传递令牌 */
void send_order(pid_t pid)
{
    can_check = 0;
    kill(pid, SIGUSR1);
    return;
}

void do_thinking()
{    
    printf("Think   --- %d\n", count);
    alarm(1);
    while (alarm_flag == 0)
        sigsuspend(&zeromask);
    alarm_flag = 0;
    return;
}

void is_hungery()
{
    hungery = 1;
    printf("Hungery --- %d\n", count);
    return;
}

void do_eating()
{
    eating = 1;
    hungery_level = 0;
    hungery = 0;
    can_check = 0;
    printf("Eat     --- %d\n", count);
    send_order(next_pid);
    alarm(1);
    while (alarm_flag == 0)
        sigsuspend(&zeromask);
    alarm_flag = 0;
    return;
}

void sig_alarm(int signo)
{
    alarm_flag = 1;
    return;
}

/* 令牌信号，肯定回答 */
void sig_usr1(int signo, siginfo_t* sig_info, void* no_use)
{
    /* 收到令牌信号 */
    if (can_check == 0){
        if (hungery == 1){
            can_check = 1;
        }
        else
	    send_order(next_pid);
    }
    /* 收到肯定回答 */
    else{
        if (sig_info->si_pid == right_pid && sig_info->si_pid != next_pid)
            can_use = 0;
        else
  	    can_use = 1;
    }

    return;
}

void sig_usr2(int signo, siginfo_t* sig_info, void* no_use)   /* 查询信号，否定回答 */
{
    /* 每组的第一个哲学家等待最后一个发pid 
    if (begin == 1){
        sigflag = 1;
	last_pid = sig_info->si_pid;
//	printf("哲学家%d收到该组最后一个(%d)的回复\n", count, sig_info->si_pid);
    }

    if (begin == -1)
	sigflag = 1;
*/
//    if(begin != 1 && begin != -1){    
//        sigflag = 1;
        if (can_check == 0)
    	    if (eating == 1)
	        kill(sig_info->si_pid, SIGUSR2);
	    else
	        kill(sig_info->si_pid, SIGUSR1);
        else
  	        can_use = 0;
    
    return;
}

void sig_quit(int signo, siginfo_t* sig_info, void* no_use)
{
    if (begin == 1){
	sigflag = 1;
	last_pid = sig_info->si_pid;
//	printf("哲学家%d收到该组最后一个(%d)的回复\n", count, sig_info->si_pid);
    }

    else if (begin == -1)
	sigflag = 1;

    else if (begin == 2)
        begin = 0;

    return;
}