2. 考研
  3. 一个主修动物行为学、辅修计算机科学的学生参加了一个课题，调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷，横跨峡谷拉了一根绳索(假设为南北方向)，这样猴子就可以攀着绳索越过峡谷。只要它们朝着相同的方向，同一时刻可以有多只猴子通过。但是如果在相反的方向上

一个主修动物行为学、辅修计算机科学的学生参加了一个课题，调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷，横跨峡谷拉了一根绳索(假设为南北方向)，这样猴子就可以攀着绳索越过峡谷。只要它们朝着相同的方向，同一时刻可以有多只猴子通过。但是如果在相反的方向上

admin2018-07-17  51
问题  一个主修动物行为学、辅修计算机科学的学生参加了一个课题，调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷，横跨峡谷拉了一根绳索(假设为南北方向)，这样猴子就可以攀着绳索越过峡谷。只要它们朝着相同的方向，同一时刻可以有多只猴子通过。但是如果在相反的方向上同时有猴子通过则会发生死锁(这些猴子将被卡在绳索中间，假设这些猴子无法在绳索上从另一只猴子身上翻过去)。如果一只猴子想越过峡谷，它必须看当前是否有别的猴子在逆向通过。请用P、V操作来解决该问题。
选项
答案由于不允许两个方向的猴子同时跨越绳索，所以对绳索应该互斥使用。但同一个方向可以允许多只猴子通过，所以临界区可允许多个实例访问。本题的难点在于位于南北方向的猴子具有相同的行为，当一方有猴子在绳索上时，同方向的猴子可继续通过，但此时要防止另一方的猴子跨越绳索。类比经典的读者／写者问题。 信号量设置：对绳索应互斥使用，设置互斥信号量mutex，初值为1。但同一个方向可以允许多只猴子通过，所以定义变量NmonkeyCount和SmonkeyCount分别表示从北向南和从南向北的猴子数量。因为涉及到更新NmonkeyCount和SmonkeyCount，所以需要对其进行保护。更新NmonkeyCount和SmonkeyCount时需要用信号量来保护，所以设置信号量Nmutex和Smutex来保护’NmonkeyCount和SmonkeyCount，初始值都为1。 int SmonkeyCount=0； ／／从南向北攀越绳索的猴子数量 int NmonkeyCount=0； ／／从北向南攀越绳索的猴子数量 semaphore mutex=1； ／／绳索互斥信号量 semaphore Smutex=1； ／／南方向猴子间的互斥信号量 semaphore Nmutex=1； ／／北方向猴子间的互斥信号量 cobegin{ process South_i(i=1，2，3，…){ while(TRUE){ p(Smutex)； ／／瓦斥访问smonkeycount if(smonkeyCount=0) ／／本方第一个猴子需发出绳索使用请求 p(mutex)； SmonkeyCount=SmonkeyCount+1； ／／后续猴子可以进来 v(SmutexH)； Pass the cordage； p(Smutex)； ／／猴子爬过去后需要更新SmonkeyCount，互斥 Smonkeycount=Smonkeycount—1； ／／更新SmonkeyCount。 if(SmonkeyCount==0) ／／若此时后方已无要通过的猴子，最后一只猴子通过后放开绳索 v(mutex)， v(Smutex)， } process North_j(j=1，2，3，…) while(TRUE){ P(Nmutex)， ／／互斥访问NmonkeyCounn if(NmonkeyCount==0) ／／本方第一个猴子需发出绳索使用请求 p(mutex)； Nmonkeycount=Nmonkeycount+1， ／／后续猴子可以进来 v(Nmutex)； Pass the cordage； P(Nmutex); ／／猴子爬过去后需要更新NmonkeyCount，互斥 NmonkeyCount=NmonkeyCount—1； ／／更新NmonkeyCount if(NmonkeyCount==0) ／／若此时后方已无要通过的猴子，最后一只猴子通过后放开绳索 v(mutex)， v(Nmutex)， } } } coend 注意：有的同学注意到了这种算法会导致饥饿，但是题目中只要求实现互斥，并没有对饥饿控制有要求，而且如果还要考虑饥饿，那么必然会导致复杂性大大增加，一般考试是不会出到那么难的。如果实在要考虑可以设一个固定的数值代表一次单项的最大通过量，当一个方向通过那么多猴子以后，看看对方是否要通过，如果有，就让出铁锁，如果没有，就继续让这个方向的猴子通过。
解析
转载请注明原文地址:https://kaotiyun.com/show/WyRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)