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

青岛理工大学操作系统课程设计报告院（系）： 计算机工程学院 专业： 计算机科学与技术 班级： 计算131 学生姓名： 钟晓俊 学号： 201307020 魏正迪 201307025 题目： 设计内核同步原语 起迄日期: 2016.06.27-2016.07.08 设计地点: 现代教育中心303 指 导 教 师: 熊晓云 20152016年度 第 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() 事件数不为零Y 遍历已存在的事件N创建新事件事件是否 定位到位？Y返回事件号 结束N return 0图3 建立事件Create()的系统调用函数流程图阻塞事件Request()的系统调用函数流程图如图4所示： 开始遍历存在事件 是否定位到 事件？YN资源数减1返回事件号 结束 资源数0?获取事件的资源数Y 阻塞，等待被唤醒然后 资源数value减1 return 0YN图4 阻塞事件Request()的系统调用函数流程图唤醒一个阻塞事件Release()的系统调用函数流程图如图5所示： 开始遍历存在的事件 是否定位到 事件？YN资源数value减1返回事件号 结束 value0?获取事件的资源数Y 阻塞，等待被唤醒然后 资源数value减1 return 0YN图5 唤醒一个阻塞事件Release()的系统调用函数流程图唤醒所有阻塞进程Broadcast()的系统调用函数流程图如图6所示： 开始遍历已存在事件 是否定位到 事件？YN返回事件号 结束调用wake_up_all(),唤醒多有阻塞进程Y return 0kfree(releaseItem)，释放事件结点图6 唤醒所有阻塞进程Broadcast()的系统调用函数流程图四、系统测试与调试分析1、系统测试（1）新建事件Create()的系统调用函数功能测试表测试说明测试名称内核同步原语测试目的验证添加的系统调用功能是否成功实现测试技术单元测试测试方法黑盒测试法测试用例测试内容新建事件Create()的系统调用函数功能测试数据申请的资源数：3预期结果成功创建一个事件，事件号为:XX资源数为：3测试结果成功创建一个事件，事件号为:XX资源数为：3（2）阻塞事件Request()的系统调用函数功能测试表测试说明测试名称内核同步原语测试目的验证添加的系统调用功能是否成功实现测试技术单元测试测试方法黑盒测试法测试用例测试内容阻塞事件Request()的系统调用函数功能测试数据事件号：XX预期结果已经成功申请一个资源给事件XX测试结果已经成功申请一个资源给事件XX（3）唤醒事件Release()的系统调用函数功能测试表测试说明测试名称内核同步原语测试目的验证添加的系统调用功能是否成功实现测试技术单元测试测试方法黑盒测试法测试用例测试内容唤醒事件Release()的系统调用函数功能测试数据事件号：XX预期结果已经释放了事件XX的一个资源测试结果已经释放了事件XX的一个资源（4）唤醒所有事件Broadcast()的系统调用函数功能测试表测试说明测试名称内核同步原语测试目的验证添加的系统调用功能是否成功实现测试技术单元测试测试方法黑盒测试法测试用例测试内容唤醒所有事件Broadcast()的系统调用函数功能测试数据事件号：XX预期结果已经释放了事件XX的全部资源测试结果已经释放了事件XX的全部资源预期结果如下：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官网/下载纯净的内核源码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-dev4. 清除以前编译的内核信息#make mrproper（第一次编译不需此命令）5. 配置内核#make oldconfig6.编译内核#make -j87.安装模块#make modules_install8. 安装内核#make install9. 创建initrd文件mkinitranfs 3.14.57 -o /boot/initrd.img-3.14.5710. 更新引导项update-grub11. 重启reboot之后启动页面会出现新编译的内核和原有的内核选项进行选择12. 重启之后查看内核已使用新的内核13. 调用新加的系统调用(1).创建后多次申请资源，直到阻塞(2).打开新的终端，释放资源，终端1中的进程自动释放(3).多个程序阻塞时，打开新的终端调用broadcast释放所有的14. 执行dmesg查看系统调用中printk打印输出的信息六、程序清单新加的系统调用函数源码1.yuan.c#include #include #include #include typedef struct _myeventint 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) 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;elsereturn eventNum;asmlinkage int sys_Request(int eventNum)myevent_t *tmp;myevent_t *prev = NULL;if(tmp = scheventNum( eventNum, &prev) != NULL)printk(wait:value is %d,atomic_read(&tmp-value);if (atomic_read(&tmp-value) 0)atomic_dec(&tmp-value);printk(wait:ive dec value to ,atomic_read(&tmp-value);return eventNum;printk(wait:value should be 0 to sleep-value:%dn,atomic_read(&tmp-value);DEFINE_WAIT(wait); /prepare_to_wait(&tmpp,&wait,TASK_INTERRUPTIBLE);set_current_state(TASK_INTERRUPTIBLE);add_wait_queue_exclusive(&tmp-p,&wait); schedule(); finish_wait(&tmp-p,&wait);printk(wait:now im back and value is :%dn,atomic_read(&tmp-value);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(signal:so list is empty and value now is(added):%dn,atomic_read(&tmp-value);return eventNum;printk(signal:so im going to wake up one exclusive processn);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;e