红黑客问题分析和总结.docx

这个是我写的版本，请指教

////////////////公用变量/////////////////////////intrc=0; //上船红客计数

intbc=0; //上船黑客计数inti=-1; //数组下标，公用

Semaphoresail=newSempahore(0);//开船信号量Semaphoreempty=newSemaphore(4); //上船名额分配Semaphore[]go=newSemaphore[4]; //上船信号量Semaphoremutex=newmutex(1); //互斥量Semaphore[]land=newSemaphore[4];//登陆信号量Semaphores=newSemaphore(0); //不符合的等待信号量intt=0;//排在s的计数

/////////////////////////船//////////////////////////classBoatextendsPVableThread{publicrun()

{while(true)

{

p(sail);

for(intk=0;k4;k++)v(go[k]);System.out.println(BOATsailing);

for(intk=0;k4;k++)p(land[k]);System.out.println(BOATlanding);

System.out.println(BOATbacking);p(mutex);//re-init

i=-1;

rc=0;bc=0;

for(intk=0;kt;k++) v(s);t=0;

for(intk=0;k4;k++) v(empty);

v(mutex);

}

}

//////////////////////////红客/////////////////classRedextendsPVableThread

{

publicrun()

{

while(true)

{p(mutex);if((rc==0bc==3)││(rc==2bc==1))

{ t++;

v(mutex);

p(s);//releaseittillbacking

}

else

{v(mutex);

break;

}

}

p(empty);//nomore4enter,releaseafterbackingSystem.out.println(REDgetonboard);

p(mutex);rc++;i=i+1;

if(rc+bc==4)v(sail);v(mutex);

p(go);

System.out.println(REDsailing);

System.out.println(REDlanding);p(mutex);

rc--;

v(land);

v(mutex);

}

}

引用DreamPKU上的解法，个人认为如果YAPI的改一下则更好些对同步与互斥的分析：

同步关系：1.满员才能开船；2.红黑客满足一定的组合规则,才能有四人上船互斥关系：红黑客对请求上船的控制

显然，此题难点在对同步关系的解决。

下面给出所写程序的算法思想：

Red():每个红客到来请求上船时执行该程序；1.请求进入临界区；

首先检查本人的到来是否满足上船的组合(即4个红客或2个红客与2个黑客);

如果满足2个红客和2和黑客的组合，则看是否有船可上，有的话该红客上船并通知另外1个红客和2

个黑客上船，然后通知船满员，并退出临界区；

如果满足4个红客的组合，则看是否有船可上，有的话该红客上船并通知另外3个红客上船，然后通知船满员，并退出临界区；

不符合上船的组合，则先退出临界区，然后在信号量S_red上等待，直到当条件满足时，有人通知其上船。

完毕。

Black():每个黑客到来请求上船时执行该程序,其算法与Red()完全一致；Boat():河上的船执行该程序；

等待满员后开船过河；

空船返回，通知可以上船了，转而执行1。