张超旺
rickycheung@21cn.com
01级计算机科学与技术系
实验报告
－－在MINIX+2.0中实现信号量通信机构
本实验报告由三部分组成，其中第一、二部分主要为对Minix 操作系统的分析，而第三部分则为对Minix 操作系统添加信号量（Semaphore）的实验探索过程。
一、 Minix 操作系统的消息机制分析
Minix 操作系统是微内核结构。它的内部结构是以内核为中心，再由一组服务器的进程的集合为辅。如下表所示：
用户进程 1
用户进程 2
用户进程 3
用户进程 4
…
用户进程
MM
内存管理器
FS
文件系统
…
服务器进程
磁盘任务
终端任务
时钟任务
系统任务
…
I/O任务
进程管理
表1说明：其中最低两层，进程管理和I/O任务这两层构成内核。
Minix 操作系统的进程之间，以及与用户进程之间是使用消息传递的通信机制。那么Minix 操作系统是如何实现消息传递机制？以下是本人对源代码的跟踪。
图 1. 消息传递过程
从根本上说，Minix 操作系统传递消息是靠调用中断门为33(SYSVEC)的中断，再陷入至内核实现的。
在Minix 初化时，会同时初化中断门(src/kernel/protect.c的 prot_init()) 为33 (SYSVEC)，并装入该中断服务例程(src/kernel/mpx386.s的 _s_call)。
当进程需要发送(接收)消息时，先调用由src/lib/i386/rts/_sendrec.s 提供的send (receive)，而src/lib/i386/rts/_sendrec.s 的send (receive) 由调用中断33 (SYSVEC)服务例程 _s_call。_s_call又通过调用sys_call (在src/kernel/proc.c)，陷入Minix的内核。而sys_call利用 mini_send和mini_rec内真正地向目标进程发送(接收)消息。
二、 Minix 操作系统的库调用过程
由于Minix规定进程之间如下通信规则：
a. 用户进程之间不能互发消息。
b. 用户进程只能向MM和FS发送、接收消息。
因此用户进程想调用内核的功能时，就必先通过MM、FS为媒介或由两者提供。现以fork()系统调用为例。
当用户调用fork()时，利用src/lib/syscall/fork.s转跳至src/lib/posix/_fork.c。而_fork.c利用sys_call陷入至MM，当MM完成了对fork在内存初始化的必要操作后，再调用task_call再一次陷入至内核。其流程以下图所示：
图 2. fork调用过程
三、 Minix信号量的实现
在了解了Minix的消息机制和库调用过程的基础上，开始对Minix 信号量的实现进行构思。
首先，因为用户进程之间不能互通消息，所以用户进程想通过信号量唤醒或阻塞其它用户进程时，必然要通过系统调用陷入至MM或内核实现。故可以明确的是，信号量应以库调用形式提供给用户进程使用。
其次，要确定信号量的具体实现形式。在实现初期，我想到有两个方案：
方案一：
在MM层上直接利用消息机制，唤醒或阻塞其它用户进程。
比如，当用户进程A进行P操作时，若信号量小于0，则MM通过不发reply给用户进程A而对其实现阻塞。而当另一用户进程B进行V操作时，若信号量的值不大于0，则MM会查找该信号量阻塞进程队列，然后send一个reply给被阻塞的用户进程。
方案二：
在内核层，通过对进程队列的直接操作，唤醒或阻塞其它用户进程。
当用户进程进行信号量操作时，以MM层为中介，首先陷入MM层，然后从MM层调用自定义的_taskcall(SYSTASK, SYS_SEM, &m)再一次陷入内核。而内核以do_sem响应该消息。
最后在内核层，直接对用户进程队列实现唤醒和阻塞的操作。
方案优劣比较：
方案一实现简洁，只要在MM消息循环简单地控制dont_reply变量，便可实现。但方案一缺乏健壮性(robust)，首先由于控制用户进程简单由reply来决定，若存在其它非使用某信号量的用户进程企图发消息给被P操作阻塞的用户进程时，那么被阻塞的用户进程会被唤醒，但该唤醒不非因由信号量的V操作引起，这便会出现逻辑上谬误。
方案二尽管实现较复杂，要通过两层中断陷入，但实现健壮性(robust)得到提高。在proc.h的进程struct添加标识变量p_sem_wait，唤醒用户进程与否不是由是否发送消息回应决定，而是由V操作时，改变p_sem_wait且利用ready函数唤醒用户进程。
通过上述比较我决定采用方案二。以下是实现细节：
主要利用数据结构：
阻塞进程队列：具体实现是在proc添加struct proc *p_next_block_proc 建立链接关系，semaphore结构内添加阻塞进程队列头和尾指针。
主要利用算法：
对信号量唤醒被阻塞的进程，采用了FCFS的策略。从信号量的阻塞队列头直接移除被阻塞的用户进程。当然可以通过参数，扩展唤醒策略。
调用P、V、CreatSemaphore、DelSemaphore的过程图：
测试程序：
程序1读者和写者问题：
#include <lib.h>
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <fcntl.h>
#define N 10
void enter_item()
{
char buff;
int num;
int fd;
fd=open("item",O_RDWR);
lseek(fd,1,SEEK_SET);
read(fd,&buff,1);
buff++;
num=(int)buff;
printf("\nenter item:%d\n",num);
lseek(fd,1,SEEK_SET);
write(fd,&buff,1);
close(fd);
}
void remove_item()
{
char buff;
int num;
int fd;
fd=open("item",O_RDWR);
lseek(fd,1,SEEK_SET);
read(fd,&buff,1);
buff--;
num=(int)buff;
printf("\nremove item:%d\n",num);
lseek(fd,1,SEEK_SET);
write(fd,&buff,1);
close(fd);
}
void main()
{
int empty=creatsem(N);
int full=creatsem(0);
int mutex=creatsem(1);
int fd=creat("item",0751);
char buff=0;
lseek(fd,1,SEEK_SET);
write(fd,&buff,1);
close(fd);
if(fork()!=0){
while(1){
p(empty);
p(mutex);
enter_item();
v(mutex);
v(full);
}
}else{
while(1){
sleep(2);
p(full);
p(mutex);
remove_item();
v(mutex);
v(empty);
}
}
}
说明：参考了管道(pipe)，进程之间使用文件item来共享数据。
二〇〇五年二月十一日
