内核同步原语 操作系统课程设计

青岛理工大学

操作系统课程设计报告

院（系）： 计算机工程学院

专业： 计算机科学与技术 班级： 计算131

学生姓名： 钟晓俊 学号： 201307020

魏正迪 201307025

题目： 设计内核同步原语

起迄日期: ＿ 2016.06.27-2016.07.08＿＿＿

设计地点: 现代教育中心303 指 导 教 师: 熊晓云

2015—2016年度 第 2 学期 完成日期: 2016 年 7 月 13 日

一、 课程设计目的

通过本次课设，掌握操作系统中信号量signal（）与wait（）的工作原理，和在Linux内核中增加系统调用函数的方法，了解对Linux内核重新进行编译、连接的过程。另编写一个用户测试程序，调用新添加的的系统调用。在此期间，可以进一步熟悉Linux系统操作，初步接触到嵌入式系统。同时，通过模拟实现的方式来体现操作系统的管理原理与算法，进而深刻理解操作系统的运行机制和数据结构。可以提高运用操作系统知识解决实际问题的能力；锻炼实际的编程能力、创新能力及团队组织、协作开发软件的能力；还能提高调查研究、查阅技术文献、资料以及编写软件设计文档的能力。 二、 课程设计内容

1、设计要求：

1)要求设计三个原语实现操作系统中信号量signal（）与wait（）功能： Request（）、Release（）和Broadcast（）。

Request（）类似wait（）操作，该原语允许多个进程因一个事件而阻塞，每次产生阻塞时均会发出一个消息，“有多少个进程处于阻塞状态。”

Release（）类似signal（）操作，当一个进程产生这个事件的信号时，该原语会唤醒处于阻塞队列中的第一个进程，并发出一个消息“进程XX解除了阻塞状态，尚有XX个进程处于阻塞状态。”；如果在信号产生时，没有进程因为这个事件阻塞，那么这个信号无效，不产生任何消息。

Broadcast（）是类似一个广播操作，当一个进程产生这个事件的信号时，该原语会唤醒处于阻塞队列中的所有进程，并发出一个消息“广播，所有进程解除了阻塞状态。”；如果在信号产生时，没有进程因为这个事件阻塞，那么这个信号无效，不产生任何消息。 2)编写一个测试程序，验证原语的正确性。

3)要求在实验报告中列出Linux内核的版本与编译过程。 2、小组成员分工如下：

钟晓俊负责课程设计报告的编写及协助魏正迪查找资料；

魏正迪负责内核的配置并在其Linux内核中添加系统调用，进行程序测试等。

三、 系统分析与设计

1、系统分析

操作系统对进程的控制是依据用户命令和系统状态来决定的。进程控制的功能是创建和撤消进程，完成进程状态的转换。进程控制程序属于操作系统的内核程序。

一条原语由若干条机器指令组成，是机器指令的延伸，能完成一个特定的功能，是一种特殊的系统调用命令。它的特点是执行时不可中断，且不允许原语并发执行，即原子性。

对系统中所有进程的生命历程进行控制的原语称为进程控制原语，与进程控制有关的操作原语有：创建原语（create）、停止原语（halt）、挂起原语（suspend）、激活原语（active）、阻塞原语（block）、唤醒原语（wakeup）等基本原语。

内核是系统的控制和协调的中心，在管态下运行。 功能需求如下：

1)Linux内核的编译安装过程并添加系统调用。

2)设计三个原语（Request、Release、Broadcast）实现操作系统中信号量 signal（）与wait（）功能。

注：Request原语实现某进程请求一个资源的功能；

Release原语实现某进程释放一个资源的功能；

Broadcast原语实现广播唤醒所有进程并释放它们的功能。

3)编写一个用户测试程序，验证设计原语的正确性。 数据需求的数据流图如图1所示：

资源数 可用资源数 释放一个事件 事件资源数 事件队列 操作员 建立事件 资源数 事件资源数 资源数 资源数 阻塞事件 操作员 资源数 释放所有事件 总资源数 资源数 图1 数据需求的数据流图

重要数据结构的说明，以及在关键算法中的作用如下：

（1）进程阻塞需要一个等待队列，所有等待同一事件号的进程都挂接到该队列。所以我们需要定义一个结构体myevevt_t，包含事件号eventnum，资源数目value以及等待队列的指针等数据

（2）另外我们需要定义两个全局的指针变量来为实现事件的队列操作：分别是链头指针myevent_t * lpmyevent_head 和链尾指针myevent_t * lpmyevent_end 。

这里着重说明信号量机制的实现；增加了变量资源数value，每次进行wait（）操作的时候，判断资源数是否足够，如果资源数足够，则将资源数减1，否则将进程放到一个等待队列中去；每次进行signal（）操作时候，，本系统中只需要判断等待队列上是否有进程在等待，如果没有，说明现在的资源数是充足的，没有进程出现等待的现象，需要将资源数加1；如果等待队列上已经有进程在等待，需要将队列头部的进程唤醒。其中最重要的是对资源数的同步实现，对于资源计数，本系统使用了原子变量。

（3）①在进程添加到队列的时候，使用了独占等待的方法，使用了add_to_queue_exclusive,该函数将进程放到指定的队列尾部，而且置上exclusive标记。 ②在阻塞时，Request中使用一个函数来使相应进程阻塞。

③在唤醒时，Release中使用wakeup()将指定队列上的进程唤醒，Broadcast使用一定的函数唤醒所有进程。 2、系统设计：

设计的内核同步原语要求具有以下功能：能够使多个进程阻塞在某一特定的事件上,直到另一进程完成这一事件释放相关资源,给内核发送特定消息然后由内核唤醒这些被阻塞的进程。如果没有进程阻塞在这个事件上,则消息被忽略。

为了实现这些功能，可以编写 4 个系统调用来实现这些功能要求:

1)新建一个事件的系统调用函数:int sys_Create(int eventNum,int value);生成

一个事件,返回该事件的 ID,如果参数为 0,表示是一个新的事件,否则就是一个已经存在的事件。

2)将进程阻塞到一个事件的系统调用函数:int sys_Request(int eventNum);进程阻塞到 eventNum 事件,直到该事件完成才被唤醒。

3)唤醒一个阻塞进程的系统调用函数:int sys_Release(int eventNum);唤醒一个等待eventNum 事件的进程,如果队列为空,则忽略。

4)撤销所有阻塞进程的系统调用函数:int sys_Broadcast(int eventNum);唤醒所有等待eventNum事件的进程，如果信号产生时，队列为空，则无效。 然后我们需要把代码集成到内核中，然后进行测试，主要工作如下： 设计事件的数据结构和系统调用函数。 1)说明一个事件查找函数。

2)建立或查找事件的系统调用，它返回建立的信事件的编号。 3)等待事件的系统调用。

4)唤醒等待事件进程的系统调用。 5)撤销某个事件的系统调用。

6)重新编译内核，用新内核重启系统。 7)测试设计的同步机制。 3、模块设计：

程序模块图如图2所示：

内核同步原语 查找事件scheventNum() 创建事件Create() 阻塞事件Request () 唤醒事件Release() 撤销事件Broadcast()

图2 程序模块图

建立事件的系统调用函数流程图如图3所示：

开始 运行函数Create() N 事件数不为零 Y 遍历已存 在的事件 创建新事件 N 事件是否 定位到位？ Y return 0 返回事件号 结束

图3 建立事件Create()的系统调用函数流程图

阻塞事件Request()的系统调用函数流程图如图4所示：

开始 遍历存在事件 Y N 是否定位到 事件？ Y 获取事件的资源数 N 资源数>0? Y 资源数减1 阻塞，等待被唤醒然后 资源数value减1 return 0 返回事件号 结束

图4 阻塞事件Request()的系统调用函数流程图

唤醒一个阻塞事件Release()的系统调用函数流程图如图5所示：

开始 遍历存在的事件 Y N 是否定位到 事件？ Y 获取事件的资源数 N value>0? Y 资源数value减1 阻塞，等待被唤醒然后 资源数value减1 return 0 返回事件号 结束

图5 唤醒一个阻塞事件Release()的系统调用函数流程图

唤醒所有阻塞进程Broadcast()的系统调用函数流程图如图6所示：

开始 遍历已存在事件 Y N 是否定位到 事件？ Y 调用wake_up_all(), 唤醒多有阻塞进程 kfree(releaseItem)， 释放事件结点 return 0 返回事件号 结束

图6 唤醒所有阻塞进程Broadcast()的系统调用函数流程图

四、系统测试与调试分析

1、系统测试

（1）新建事件Create()的系统调用函数功能测试表 测试说明 测试用例 测试名称 内核同步原语 测试目的 验证添加的系统调用功能是否成功实现 测试技术 单元测试 测试方法 黑盒测试法 测试内容 新建事件Create()的系统调用函数功能 测试数据 申请的资源数：3 预期结果 成功创建一个事件，事件号为:XX资源数为：3 测试结果 成功创建一个事件，事件号为:XX资源数为：3

（2）阻塞事件Request()的系统调用函数功能测试表 测试说明 测试用例 测试说明 测试用例 测试说明 测试用例 测试名称 内核同步原语 测试目的 验证添加的系统调用功能是否成功实现 测试技术 单元测试 测试方法 黑盒测试法 测试内容 阻塞事件Request()的系统调用函数功能 测试数据 事件号：XX 预期结果 已经成功申请一个资源给事件XX 测试结果 已经成功申请一个资源给事件XX 测试名称 内核同步原语 测试目的 验证添加的系统调用功能是否成功实现 测试技术 单元测试 测试方法 黑盒测试法 测试内容 唤醒事件Release()的系统调用函数功能 测试数据 事件号：XX 预期结果 已经释放了事件XX的一个资源 测试结果 已经释放了事件XX的一个资源 测试名称 内核同步原语 测试目的 验证添加的系统调用功能是否成功实现 测试技术 单元测试 测试方法 黑盒测试法 测试内容 唤醒所有事件Broadcast()的系统调用函数功能 测试数据 事件号：XX 预期结果 已经释放了事件XX的全部资源 测试结果 已经释放了事件XX的全部资源 （3）唤醒事件Release()的系统调用函数功能测试表 （4）唤醒所有事件Broadcast()的系统调用函数功能测试表 预期结果如下：

2、调试分析

这次遇到的主要问题是内核的编译和向内核中增加新的系统调用。内核的编译对细节要求很高。1>例如：当你新添加的系统调用的函数为无参的函数时void name()这种格式并不正确，正确的格式为void name(void);用第一种形式时，进行内核编译操作(# make install)时会有错误提示。2>由于内核中的文件都是只读文件，并没有修改的权限，所以需要用root权限来对文件进行操作，进行操作的方式有两种：第一种是#gedit 文件路径 然后直接保存；

第二种为#vi 文件路径 这种方式最后退出的时候需要用特定的命令才能保存#w !sudo tee % 通过这种方式进行保存。方式一中会遇到时间超时的提示(自己觉得是文件太多，检索时间过长)，只有用第二种方式。3>调试小技巧：当编译内核成功时，但是系统调用调不出来，卡死或者以杀死时，需要使用printk内核调试函数例如：

最后通过命令dmesg命令查看程序从哪里中断，就在那里解决。提醒内核编译繁琐，容易出错，要耐心。

五、用户手册

.本实验在ununtu14.04系统上操作，原来内核为4.2.2，要编译的内核版本为3.14.57。到linux官网https://www.kernel.org/下载纯净的内核源码linux-3.14.57.tar.gz将下载到的压缩包移动到根目录下/usr/src目录下；通过命令将源码解压tar vxf linux-3.14.57.tar.gz linux-3.14.57 然后进入linux-3.14.57目录下操作(此次操作大部分都在此目录下操作)

1.获取权限并进入内核解压目录

2.修改文件

a.在文件中添加系统调用

b.修改系统调用表的内容

c.写入系统调用处理程序声明

注：声明的顺序必须和调用表的顺序一样 3.安装工具#apt-get install libncurses5-dev

4.清除以前编译的内核信息#make mrproper（第一次编译不需此命令）

5.配置内核#make oldconfig

6.编译内核#make -j8

7.安装模块#make modules_install

8.安装内核#make install

9.创建initrd文件mkinitranfs 3.14.57 -o /boot/initrd.img-3.14.57 10.更新引导项update-grub

11.重启reboot之后启动页面会出现新编译的内核和原有的内核选项进行选择 12.重启之后查看内核已使用新的内核

13.调用新加的系统调用

(1).创建后多次申请资源，直到阻塞

(2).打开新的终端，释放资源，终端1中的进程自动释放

(3).多个程序阻塞时，打开新的终端调用broadcast释放所有的

14.执行dmesg查看系统调用中printk打印输出的信息

六、程序清单

新加的系统调用函数源码 1.yuan.c

#include #include #include #include typedef struct __myevent{ int eventNum; atomic_t value; wait_queue_head_t p; struct __myevent *next; }myevent_t;

myevent_t * lpmyevent_head = NULL ; myevent_t * lpmyevent_end = NULL ;

myevent_t * scheventNum(int eventNum, myevent_t **prev) { myevent_t *tmp = lpmyevent_head; *prev = NULL; while(tmp) { if(tmp->eventNum == eventNum) { return tmp; } *prev = tmp; tmp = tmp->next; } return NULL; }

asmlinkage int sys_Create(int eventNum,int value) { myevent_t *new_event = 0; myevent_t *prev = 0; int result ; if(!scheventNum( eventNum, &prev))

{

} else { return eventNum; } }

asmlinkage int sys_Request(int eventNum) { myevent_t *tmp; myevent_t *prev = NULL; if((tmp = scheventNum( eventNum, &prev)) != NULL) { printk(\is %d\ if (atomic_read(&tmp->value) > 0) { atomic_dec(&tmp->value); printk(\dec value to <%d>\ return eventNum; } printk(\should be 0 to sleep-->value:%d\\n\ DEFINE_WAIT(wait); //prepare_to_wait(&tmp>p,&wait,TASK_INTERRUPTIBLE); set_current_state(TASK_INTERRUPTIBLE);

new_event = (myevent_t *) kmalloc(sizeof(myevent_t),GFP_KERNEL);

init_waitqueue_head(&new_event->p); new_event->next = NULL;

new_event->p.task_list.next = &new_event->p.task_list; new_event->p.task_list.prev = &new_event->p.task_list; if(!lpmyevent_head) {

new_event->eventNum = eventNum; lpmyevent_head =lpmyevent_end= new_event; } else { new_event->eventNum = eventNum; lpmyevent_end->next=new_event; lpmyevent_end=new_event; }

atomic_set(&new_event->value,value); result = new_event->eventNum; return result;

add_wait_queue_exclusive(&tmp->p,&wait); schedule(); finish_wait(&tmp->p,&wait); printk(\i'm back and value is :%d\\n\ return eventNum; } return 0; }

asmlinkage int sys_Release(int eventNum) { myevent_t *tmp = NULL; myevent_t *prev = NULL; if((tmp = scheventNum(eventNum,&prev)) != NULL) { if (list_empty(&(tmp->p.task_list))) { atomic_inc(&tmp->value); printk(\list is empty and value now is(added):%d\\n\tmp->value)); return eventNum; } printk(\i'm going to wake up one exclusive process\\n\ wake_up(&tmp->p); return eventNum; } return 0; }

asmlinkage int sys_Broadcast(int eventNum) { myevent_t *prev=NULL; myevent_t *releaseItem; if((releaseItem = scheventNum(eventNum,&prev)) != NULL) { if( releaseItem == lpmyevent_end) { lpmyevent_end = prev; } else if(releaseItem == lpmyevent_head) { lpmyevent_head = lpmyevent_head->next; } else

}

{ prev->next = releaseItem->next; } wake_up_all(&releaseItem->p); kfree(releaseItem); printk(\%d should have been closed\\n\ return eventNum; }

return 0;

测试程序的源码： 1.create.c

#include #include #include //Create:316 int main() { syscall(316,1,3); return 0 ; }

2.request.c

#include #include #include int main() { syscall(317,1); return 0 ; }

3.release.c

#include #include #include int main() { syscall(318,1); return 0 ; }

4.broadcast.c

#include #include #include int main()

{ }

syscall(319,1); return 0 ;

七、参考文献

[1] 汤子瀛 编著，《计算机操作系统（第四版）》，西安电子科技大学出版社，2014.5 [2] http://blog.csdn.net/linuxzhouying/article/details/7642969 [3] http://www.franksthinktank.com/howto/addsyscall/ [4] http://blog.csdn.net/xuyuefei1988/article/details/8635539 [5] http://blog.csdn.net/rk2900/article/details/8281335

八、课程设计评价

课 程 设 计 评 价 学生 成绩： 教师： 学生 成绩： 年 月 日

本文来源：https://www.bwwdw.com/article/9p75.html