08-18-2009, 06:45 PM
11-27-2010, 05:38 AM
(08-18-2009 06:45 PM)lingu Wrote: [ -> ]Experience with Processes and Monitors in Mesa Butler Lampson
本文主要描述了有关进程和管程在Mesa语言里的应用。Mesa是一种专门用于编写大型并发系统的语言，而涉及到并发、同步等的问题时，就需要考虑如何处理共享数据的问题。Mesa处理共享数据时采用的技术就是管程（注：管程的适用范围是：单核系统或多核系统）。而管程的最重要特性为：在任何时候，管程内只能有一个活动进程。这就保证在任何时刻共享数据在临界区里只能被一个进程访问。而这个过程是这样实现的：
1、由编译器实现管程入口互斥（使用2值信号量），保证任何时候在管程里只有一个活动进程。
2、添加条件变量，实现：
（1）对不能继续运行的进程阻塞（WAIT）
（2）唤醒正在等待的进程（SIGNAL）
对于1，这需要编译器支持管程，意思是需要像Mesa这样的支持管程的程序语言，或者是该种语言有支持管程的扩展库。我查了一下资料，支持管程的编译器不多，只有少数几个，这是应用管程的一个不足之处。
对于2的，Mesa使用的方式如下：
until (条件）
do wait
这个有别于Hoare的定义，Hoare的定义如下：
if not (条件）
do wait
在Hoare的定义里SIGNAL是一个专用命令，用于唤醒等待进程。这个命令是要涉及到进程切换的，会有着不少的系统开销，会延迟进程的执行（考虑到系统开销，Mesa将SIGNAL的语义更改，使它不再代表一个专用命令，而作为一个提示使用，收到该提示的正在等待的进程将会进入就绪表）。由于进程不是立即运行，因此在该进程被唤醒时还要检查条件是否成立，这就需要一个循环去完成。在这里，Mesa的做法是更稳妥的。
此外，对管程的使用一定要小心，它很容易导致死锁。另，除非很小心，否则按优先级顺序排列进程的实际执行数序会被管程打乱，原因是条件等待。在进程方面，Mesa使用FORK/JOIN的方式实现进程的创建。
在管程和进程的实现方面，主要有以下3方面：
1）编译器（静态）分析大量的语法结构和生成合适的代码，包括内置支持模块的调用。
2）运行时实现较少的操作，例如进程的生成和销毁。
3）操作系统实现最复杂的部分，如调度器和管程入口/出口等。
任何时刻，一个进程状态是存在于一个队列中。共有4个这样的队列：
就绪队列（1个）：只得一个，所有准备运行的进程都在这里
管程锁队列（多个）：当一个进程试图进入一个已锁了管程，它就会被从就绪队列放入相应的管程锁队列
条件变量队列（多个）：当一个进程执行了一个WAIT，它将从就绪队列被移到相应的条件变量队列
出错队列：所有不能运行的进程都会从就绪队列移到这个队列。
栈帧是由微处理器在堆中分配的，我认为这个最好还是在栈中分配，因为函数/过程的调用是相当频繁的。如果使用堆，会涉及空闲块的搜寻及释放等操作，会是不少的系统开销。
在一个固定时间里，CPU会扫描进程状态表和向每一个超时的等待进程发送通知。这个通知是有技巧的，因为CPU根本不知道正在等待的进程它的条件变量的位置，因此不能更新队列元素。这个问题的解决是通过使队列元素过期，令使队列元素在下一次正常使用时知道自己的状况和正确的更新自己。
总结：
应用管程的思想可以很好的管理临界区数据的共享问题，保证了任何时刻只有一个活动进程访问临界区里的数据，对于不能运行的进程也实现了阻塞。而且Mesa在实现管程的某些方面考虑的更为完善（与Hoaer的定义相比），如条件的循环检测等。但另一方面，管程也很容易导致死锁或优先级高的程序不能先运行等的问题。除此之外，可以看到支持管程的语言并不是很多，至少在类UNIX系统里是这样。
因此，如果一定要用管程的思想去实现单核系统或多核系统内的数据共享，则需要使用支持管程的语言去实现，例如Mesa，且该语言要与操作系统实现接口共享（即如果使用Mesa，则Mesa可以直接调用系统内的API），那基本上就是要实现该操作系统也是由Mesa编写的（如：Pilot）。但目前类似Mesa这类支持管程的语言应用的并不是很广泛，因此如果还是采用类UNIX的系统作为操作系统的话，建议采用自旋锁或互斥锁替代管程实现数据共享（自旋锁和互斥锁可以通过C或汇编实现）。