分类： 系统运维
2012-01-16 09:51:28
这是我今天偶然想到的一个把monitor程序翻译成semaphore程序的标准步骤，经过三步，monitor程序就可以翻译成semaphore程序，功能一样，虽然可能形式上不是最简的，但是对于有些直接通过semaphore实现很难思考，用semaphore实现很容易产生死锁的问题，我觉得可以尝试先用monitor写，因为monitor简单直观，程序好些，把逻辑搞清楚基本上不会死锁，然后再按我说的三步骤翻译成semahpore程序。我试过了好几个例子，我觉得都是对的。当然这里面不排除我的方法是错的，也可能我的方法是对的，但早就在monitor创始人的论文里解释过了，但是不管咋样，我觉得似乎这个办法非常有意思，而且可行。若需要讨论或需要Java程序测试代码的请与我联系。 (这些代码在我机子上用java程序调试通过，monitor程序是用java的Lock,ReentrantLock, Lock.newCondition模拟实现，Semaphore是用自己实现的类，当然java自身也有Semaphore类，能否用未知，但我相信能用）
（补充，经过我再次尝试一些转换，虽然我仍然相信这个转换是正确的，但是不得不承认转换出来的代码和已有的semaphore代码结构上有区别，所以这个方法仍然不能代替对原有semaphore程序的理解，我个人认为之所以出现这种原因，可能有两点，第一，用semaphore来思考本身就有很多种思路；第二，由于是monitor转换过来的，所以难免有些地方是redundant了，因为我听说过一个说法，虽然semaphore程序难写，难以维护，难以scale，但是一旦写出来了，没废话，效率还是不错）
若没接触过monitor和semaphore程序的可以先阅读wiki上的东西：
另外，如果你想有效的调试、可视化你的多线程Semaphore程序，那么强烈建议使用一个计算机教授Allen B. Downey写的软件swampy中的sync模块，他还有一个讲解这个软件的视频在youtube上。
这是我用他的软件调试我自己写的一个reader-writer problem with reader priority的画面，很有趣，很清晰：
（图中现在的画面展示的是两个Writer被卡住在外层信号量，有一个Writer卡在内层信号量，而Reader都跑得很欢快，清晰展示了读者优先）
接下来详细介绍我想的这三个步骤：
1. 第一步，把monitor程序中所有的"begin:"后面加一个P(mutex)；（注意，这里暂时不需要把所有的end前面加个V(mutex)，这个在第三步讲；注意，begin和end是一个monitor procedure伪代码的开始和结束）；
2. 第二步，所有monitor程序中的shared variable原封不动的加入到semaphore程序，他们的代码也不需要改变；
3. 第三步，对于每一个monitor程序中出现的conditional variable，比如名叫cond的conditional variable，都加一个对应的semaphore，比如cond_sem；然后再加一个名为cond_wait的shared variable到semaphore程序中（cond_wait名字来源于它的意义，它代表有多少人正在等cond_sem）；然后把如下三个东西按一下规则替换：
i)凡monitor程序中用到了cond.queue的，全部翻译成cond_wait。比如if(cond.queue)翻译成if(cond_wait>0)；再比如if(!cond.queue)翻译成if(cond_wait==0)
ii)凡monitor程序中用到了cond.wait()的，全部翻译成{cond_wait++;V(mutex);P(cond_sem);cond_wait--;}
iii)凡monitor程序中用到了cond.signal()的，全部翻译成if(cond_wait>0) V(cond_signal) else V(mutex)
(注意，第三小步这里需要灵活应变，因为有可能cond.signal本身就是放在if里的，比如if(readers==0) cond1.signal()，那么要翻译成if(readers==0) { if(cond1_wait>0) V(cond1_signal) else V(mutex) } else { V(mutex);} 其实可以简写为 if(readers==0&&cond1_wait>0) { V(cond1_signal); } else {V(mutex);}
第三步是其中的关键之处，在第三步的ii)中，{cond_wait++; V(mutex); P(cond_sem); cond_wait--;}之所以这么做，是因为首先我们要释放我们获取的mutex，这一点非常类似于monitor程序中的cond.wait()先释放monitor，然后再等。但是monitor程序中，cond.wait()里一旦被唤醒是自动获取monitor的，但是翻译的代码里为什么不是{cond_wait++; V(mutex); P(cond_sem); P(mutex) ;cond_wait--;}？这就是我个人觉得比较精巧的地方，这个地方也确实能解决实际问题，等下会解释一个例子（其他例子比如producer&consumer我也试过，也是可以的），这里之所以不加入P(mutex)，是因为凡属唤醒它的人自己已经做过P(mutex)了，所以V(cond_sem)后，这个程序还是有mutex在手，继续下去，不会有问题。这样做有两个理由，第一，在monitor程序中，一旦有进程调用cond.signal()，我们必须保证它真的找到了一个进程在等cond.wait()，并且保证它是我释放monitor后第一个执行的，我们通过不放弃mutex做到了这一点；第二，如果我真的加了P(mutex)，那么程序会出现问题，因为这个时候其实出现了断层，本应该在一起的代码分成了两片，中间有可能插入别的改变状态的代码。
接下来看一个例子，我这只举一个例子，这个例子很难，我直接用semaphore思考想了很久没想出来，因为我觉得非常精巧，实在是难以想全，很容易出死锁。但是我可以很方便的写出它的monitor程序，这个例子就是：
Write a monitor-based solution to the reader–writers problem that works as
follows: If readers and writers are both waiting, then it alternates between readers
and writers. Otherwise, it processes them normally, i.e., readers concurrently and
writers serially.
就是读者写者问题，当有读者和写者同时等待时，我们需要交替唤醒他们。其实我可以把这个称之为第四读者写者问题，第负一个读者写者问题（请允许我暂时这样表达），是读读，写写，读写完全互斥，这个最简单，但是不能并行读；第0个读者写者问题，允许并行读；第1个读者写者问题，是读者优先；第2个读者写者问题，是写者优先；第三个读者写者问题，是按照来到的顺序进行调度；第四个读者写者问题，也就是我们马上要讨论的问题，是交替唤醒读写进程。( 这个链接给出了第一，第二，第三读者写者问题的描述和解答，可以看看)
首先给出monitor程序的解答，我个人觉得写monitor程序有个技巧，就是要按照 这个图去思考，先画图，再写程序，感觉顺利多了。
Monitor program for the 4-th reader-writer problem
Condition Variable: r_cond; w_cond
Shared Variable: writing=false; readers=0;
Procedure before_read:
begin:
if(r_cond.queue)
r_cond.wait();
else if (writing == true)
r_cond.wait();
else if (w_cond.queue)
r_cond.wait();
readers++;
if(!w_cond.queue)
r_cond.signal()
end
Procedure after_read:
begin:
readers--;
if(readers==0){
if(w_cond.queue)
w_cond.signal()
}
end
Procedure before_write:
begin:
if(w_cond.queue)
w_cond.wait()
else if(readers>0)
w_cond.wait()
else if (writing == true)
w_cond.wait()
writing = true
end
Procedure after_write:
begin:
writing=false
if(r_cond.queue)
r_cond.signal()
else if (w_cond.queue)
w_cond.signal()
end
按照三个步骤翻译成semaphore程序就是：
Semaphore program for the 4-th reader-writer problem
Int: readers = 0, r_cond_wait = 0, w_cond_wait = 0;
Boolean: writing = false;
Semaphores:
mutex=1 //Guard the critical section
r_cond_sem = 0 //reader queue
w_cond_sem = 0 //writer queue
Reader:
P (mutex)
if(r_cond_wait>0)
{r_cond_wait++;V(mutex);P(r_cond_sem);r_cond_wait--;}
eles if (writing == true)
{r_cond_wait++;V(mutex);P(r_cond_sem);r_cond_wait--;}
else if (w_cond_wait>0)
{r_cond_wait++;V(mutex);P(r_cond_sem);r_cond_wait--;}
readers++;
if(r_cond_wait>0 && w_cond_wait==0)
{ V(r_cond_sem);}
else
{V(mutex);}
P(mutex);
readers--;
if(readers==0){
if(w_cond_wait>0)
V(w_cond_sem);
}
else { V(mutex);}
Writer:
P(mutex);
if(w_cond_wait>0)
{w_cond_wait++;V(mutex);P(w_cond_sem);w_cond_wait--;}
else if (readers>0)
{w_cond_wait++;V(mutex);P(w_cond_sem);w_cond_wait--;}
else if (writing==true)
{w_cond_wait++;V(mutex);P(w_cond_sem);w_cond_wait--;}
writing = true;
V(mutex);
P(mutex);
writing =false;
if(r_cond_wait > 0)
V(r_cond_sem)
else if (w_cond_wait>0)
V(w_cond_sem)
else
V(mutex)
以上便是我今天偶然想到的一个方法，我觉得比较兴奋，当然我并不觉得这个有多神奇，因为我真的记得在monitor创始人的paper中就提到过monitor是可用Semaphore来实现的。当然这个由我自己想出来，觉得还是非常有趣的。
1/19/2012 更正：
仔细阅读了一下monitor的文章（~dwilkins/Seminar/S05/Monitors.pdf）后，觉得我的方法不是完全正确的，换句话说，我的方法只是这个论文的第三页的方法的一个特例。还是文章作者想得全面，想得深刻。
我的以上方法有个假设，就是每一个condition variable的signal操作都在monitor procedure的最后，这个signal操作之后就没有别的操作了，眼看就要离开procedure了。我们可以从论文第三页右边column的第四点明确看到这一点，当这个特殊情况成立时，我们不需要urgent和urgentcount了。
论文第三页左边column其实本质上就是怎么用semahore来实现monitor，其实按照它的思路来，任何一个monitor程序都可以换成semaphore来实现，也就是我整个文章要说的事情了。论文的方法更加全面，正确。加入了一个urgent semaphore，这个确实更加正确，特别对于signal操作之后还有statement的情况。在此佩服作者全面的见解，也惭愧自己没看全面，便不再这里瞎说一通，有兴趣的还是仔细读论文吧，看一周都不为过。
