| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1725 人关注过本帖
标题:哲学家就餐
只看楼主 加入收藏
tdcgoodluck
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2007-5-9
收藏
 问题点数:0 回复次数:1 
哲学家就餐

操作系统期中作业
问题描述:
一个房间内有5个哲学家,他们的生活就是思考和进食。哲学家思考后,过一定的时间就会饥饿,饥饿之后就想吃饭,吃饭后再思考。房间里有一张圆桌,桌子周围放有五把椅子,分别属于五位哲学家每两位哲学家之间有一把叉子,哲学家进食时必须同时使用左右两把叉子。

问题:
1、 写出哲学家进餐的伪码。
2、 用C程序实现哲学家进餐。(注:可以使用共享变量的方式,也可以使用信号量的方式来实现)

图片附件: 游客没有浏览图片的权限,请 登录注册

搜索更多相关主题的帖子: 哲学家 操作系统 叉子 就餐 变量 
2007-05-21 22:39
guoxiang991
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2007-6-8
收藏
得分:0 
小弟找了下,弄到了个代码
解法1,应用CRITICAL_SECTION 变量解决数据共享问题~
这是CSDN上的网友写的,
(原文见http://dev.
感觉有些粗糙,有些变量声明了后面都没用过,
效率比较低,肯定不能保证最大的并发数,
而且我在测试这段代码的时候曾出现过相邻的哲学家同时进餐的状况,这显然是不合逻辑的,
所以这个算法应该有毛病,但是作为一种思路,先记下来慢慢研究~



#include "stdafx.h"
#include "Philosopher.h"
#include < process.h >
#include < time.h >
#include < fstream >
#include < string >
#include < iostream >
#include < assert.h >

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
CWinApp theApp;
using namespace std;
HANDLE hThread;
ofstream out("out.txt");
BOOL b[6];//共享数据,用于表示 5 双筷子的使用情况,FALSE代表被占用
CRITICAL_SECTION cs;
class philosopher
{
private:
 int m_num;    //编号
 int m_index;  //标识状态,0-------waiting   1-----eating    2-----thinking
public:
 philosopher(int num=0) { m_num=num; m_index=2; m_lhand=TRUE; m_rhand = FALSE ;}
 int GetNum() const { return m_num; }
 int GetStatus() const { return m_index ; }
 void ChangeStatus() ;   
};

void philosopher::ChangeStatus()
{
 EnterCriticalSection (&cs) ;
 if(m_index==1)  //eating----->thinking
 {
  assert(!b[m_num]);
  b[m_num]=TRUE;
  if( m_num==1)
  {
   assert(!b[5]);
   b[5]= TRUE;
  }
  else
   b[m_num-1]=TRUE;
  m_index=2;   // change to thinking
  srand(time(NULL)*10000);
  Sleep(rand()%10);
 }
 else if( m_index==2)    //thinking
 {
  m_index=0;   //change to waiting
 }
 else if( m_index==0)    // waiting
 {
  if(m_num==1)
  {
   if(b[1]&&b[5])
   {
    b[1]=FALSE;
    b[5]=FALSE;
    m_index=1;
    srand(time(NULL)*10000);
    Sleep(rand()%10);
   }
  }
  else
  {
   if(b[m_num]&&b[m_num-1])
   {
    b[m_num]= FALSE;
    b[m_num-1]= FALSE;
    m_index=1;
    srand(time(NULL)*10000);
    Sleep(rand()%10);
   }
  }
 }
 LeaveCriticalSection (&cs) ;
}
string PrintStatus(philosopher *pPh)
{
 pPh->ChangeStatus();
 int i=pPh->GetStatus();
 string str;
 if(i==0)
  str="Waiting";
 else if(i==1)
  str="eating";
 else str="thinking";
 return str;
}
void ThreadFunc1(PVOID param)
{
 while(1)
 {
  philosopher *pPh;
  pPh=( philosopher *) param;
  pPh->ChangeStatus();
 }
}
void ThreadFunc2(PVOID param)
{
 while(1)
 {
  philosopher *pPh;
  pPh=( philosopher *) param;
  pPh->ChangeStatus();
 }
}
void ThreadFunc3(PVOID param)
{
 while(1)
 {
  philosopher *pPh;
  pPh=( philosopher *) param;
  pPh->ChangeStatus();
 }
}
void ThreadFunc4(PVOID param)
{
 while(1)
 {
  philosopher *pPh;
  pPh=( philosopher *) param;
  pPh->ChangeStatus();
 }
}
void ThreadFunc5(PVOID param)
{
 while(1)
 {
  philosopher *pPh;
  pPh=( philosopher *) param;
  pPh->ChangeStatus();
 }
}

int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
 for(int j=1;j<=5;j++) b[j]=TRUE;
  out<<b[1]<<b[2]<<b[3]<<b[4]<<b[5];
 philosopher ph1(1),ph2(2),ph3(3),ph4(4),ph5(5);
 InitializeCriticalSection (&cs) ;

 _beginthread(ThreadFunc1,0,&ph1);
 _beginthread(ThreadFunc2,0,&ph2);
 _beginthread(ThreadFunc3,0,&ph3);
 _beginthread(ThreadFunc4,0,&ph4);
 _beginthread(ThreadFunc5,0,&ph5);
 cout<<"press ctrl+C to exit";
 while(1)
 {
  cout<<endl<<b[1]<<b[2]<<b[3]<<b[4]<<b[5]<<endl;   // use  to test
  cout<<"The status at :"<<clock()<<" ms "<<endl;
  cout<<"哲学家"<<ph1.GetNum() <<"状态:"<<ph1.GetNum()<<"--"<<PrintStatus(&ph1)<<endl;
  cout<<"哲学家"<<ph2.GetNum() <<"状态:"<<ph2.GetNum()<<"--"<<PrintStatus(&ph2)<<endl;
  cout<<"哲学家"<<ph3.GetNum() <<"状态:"<<ph3.GetNum()<<"--"<<PrintStatus(&ph3)<<endl;
  cout<<"哲学家"<<ph4.GetNum() <<"状态:"<<ph4.GetNum()<<"--"<<PrintStatus(&ph4)<<endl;
  cout<<"哲学家"<<ph5.GetNum() <<"状态:"<<ph5.GetNum()<<"--"<<PrintStatus(&ph5)<<endl;
  Sleep(2000);
 }
 DeleteCriticalSection (&cs) ;
 return 0;
}

解法2,用信号量,这个比上面一个好很多了,

#include "stdafx.h"
#include "Philosopher.h"
#include "windows.h"
#include < process.h >
#include < time.h >
#include < stdlib.h >
#include < stdio.h >

#include < iostream >

using namespace std;

const unsigned int PHILOSOPHER_NUM=5;
const char THINKING=1;
const char HUNGRY=2;
const char DINING=3;

// each fork has a semaphore
HANDLE semph[PHILOSOPHER_NUM];

// Mutex for printing
HANDLE mutex;

void philosopherProc(void* param);

int main(int argc, char* argv[])
{
 int i;
 srand(time(0));

 mutex = CreateMutex(NULL, false, NULL);
 for (i=0; i<PHILOSOPHER_NUM; i++)
 {
  semph[i] = CreateSemaphore(NULL, 1, 1, NULL);
  _beginthread(philosopherProc, 0, (void*)&i);
  Sleep(10);
 }

 Sleep(2000);
 return 0;
}

void philosopherProc(void* param)
{
 int myid;
 char idStr[128];
 char stateStr[128];
 char mystate;
 int ret;
 unsigned int leftFork;
 unsigned int rightFork;

 myid = *((int*)(param));
 itoa(myid, idStr, 10);

 //cout << "philosopher " << myid << " begin......" << endl;
 Sleep(10);
 // initial state is THINKING
 mystate = THINKING;
 leftFork = (myid) % PHILOSOPHER_NUM;
 rightFork = (myid + 1) % PHILOSOPHER_NUM;

 while (true)
 {
  switch(mystate)
  {
  case THINKING:
   // changing my state
   mystate = HUNGRY;
   strcpy(stateStr, "HUNGRY");
   break;
  case HUNGRY:
   strcpy(stateStr, "HUNGRY");
   // first test the left fork ...
   ret = WaitForSingleObject(semph[leftFork], 0);
   if (ret == WAIT_OBJECT_0)
   {
    // left fork is ok, take it up !
    // then test the right fork ...
    ret = WaitForSingleObject(semph[rightFork], 0);
    if (ret == WAIT_OBJECT_0)
    {
     // right fork is also ok !
     // changing my state
     mystate = DINING;
     strcpy(stateStr, "DINING");
    }
    else
    {
     // right fork is being used by others, so I must put down
     // the left fork.
     ReleaseSemaphore(semph[leftFork], 1, NULL);
    }
   }
   break;
  case DINING:
   // put down both the left and right fork
   ReleaseSemaphore(semph[leftFork], 1, NULL);
   ReleaseSemaphore(semph[rightFork], 1, NULL);
   // changing my state
   mystate = THINKING;
   strcpy(stateStr, "THINKING");
   break;
  }
  // print my state
  WaitForSingleObject(mutex, INFINITE);
  cout << "philosopher " << myid << " is : " << stateStr << endl;  
  ReleaseMutex(mutex);
  // sleep a random time : between 1 - 5 s
  int sleepTime;
  sleepTime = 1 + (int)(5.0*rand()/(RAND_MAX+1.0));
  Sleep(sleepTime*10);
 }
}


另一 方法
#define   N   5
#define   Left   (i+N-1)%N
#define   Right   (i+1)%N
#define   THINKING   0
#define   HUNGRY   1
#define   EATING   2
typedef   int   semaphore;
int   state(N);
semapore   mutex   =1;
semaphore   s(N);

void   philosopher(int   i){
while(TRUE){
    think();
    take_forks(i);
    eat();
    put_forks(i);
}
}
void   tak_forks(int   i){
down(&mutex);
state(i)=HUNGRY;
test(i);
up(&mutex);
down(&s[i]);
}
void   put_forks(int   i){
down(&mutex);
state(i)=THINK;
test(LEFT);
test(RIGHT);
up(&mutex);
}
void   test(i){
if(state(i)==HUNGRY   &&   state(LEFT)!=EATING   &&   state(RIGHT)!=EATING){
    state(i)=EATING;
    up(&s[i])
}
}
2008-05-13 19:27
快速回复:哲学家就餐
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.044389 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved