其他语言

本类阅读TOP10

·基于Solaris 开发环境的整体构思
·使用AutoMake轻松生成Makefile
·BCB数据库图像保存技术
·GNU中的Makefile
·射频芯片nRF401天线设计的分析
·iframe 的自适应高度
·BCB之Socket通信
·软件企业如何实施CMM
·入门系列--OpenGL最简单的入门
·WIN95中日志钩子(JournalRecord Hook)的使用

分类导航
VC语言Delphi
VB语言ASP
PerlJava
Script数据库
其他语言游戏开发
文件格式网站制作
软件工程.NET开发
大三做Minix内核修改实验报告--做Minix上加Semaphore

作者:未知 来源:月光软件站 加入时间:2005-2-28 月光软件站

张超旺 
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_sendmini_rec内真正地向目标进程发送(接收)消息。

 

 

 

二、          Minix 操作系统的库调用过程

 

由于Minix规定进程之间如下通信规则:

a. 用户进程之间不能互发消息。

b. 用户进程只能向MMFS发送、接收消息。

因此用户进程想调用内核的功能时,就必先通过MMFS为媒介或由两者提供。现以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的策略。从信号量的阻塞队列头直接移除被阻塞的用户进程。当然可以通过参数,扩展唤醒策略。

 

 

调用PVCreatSemaphoreDelSemaphore的过程图:

 

 

测试程序:

程序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来共享数据。

 

二〇〇五年二月十一日




相关文章

相关软件