nachos系统管理与调度分析课程设计说明书.docVIP

操作系统课程设计基于NachOS的课程设计 1操作系统课程设计目录一、背景知识11、1 Nachos的介绍11、2 Nachos的目录结构21、3 线程基础知识3二、设计要求和目的42、1 Nachos的线程管理模块42、2 Nachos的线程线程调度算法分析42、3 编程语言选择对比52、4 开发环境配置62、5 NachOS 系统和交叉编译器安装62、5、1 NachOS 系统安装62、5、2 交叉编译器环境的安装7三、 设计思路和程序结构83、1 线程的生成和状态转换83、1、1 基于五状态模型83、1、2 线程创建过程83、2 线程调度机制8四、 关键代码分析94、1 扩充线程管理94、2 扩充线程调度机制104、3 扩充线程调度机制改进124、3、1 信号量机制124、3、2 实现用户更改进程优先级13五、 测试135、1 测试NachOS 环境和交叉编译器135、2 测试创建线程145、3 测试线程优先级15六、 总结15信息科学与工程学院 软件工程1一、背景知识1、1 Nachos的介绍Nachos的全称是“Not Another Completely Heuristic Operating System”，是一个可修改和跟踪的操作系统教学软件。它给出了一个支持多线程和虚拟存储的操作系统骨架，可让学生在较短的时间内对操作系统中的基本原理和核心算法有一个全面和完整的了解。NachOS 提供了可重复的调试环境和模拟操作系统及底层硬件。目的是为学习者展示真实的操作系统运行时的环境，这个简单的操作系统软件可以让学习者在较短的时间内理解并能够用自己的想法来完善它。免费的开源开发包可通过网络下载，通常包括以下几部分：1) NachOS 概述2) 简单可运行的操作系统代码3) 模拟器个人电脑或工作站4) 任务样本：任务说明和现代操作系统涉及的所有项，包括线程和并发，多道程序，系统调用，虚拟内存管理，文件系统管理，网络协议，远程过程调用和分布式系统。5) C+ 编程索引（NachOS 是C+ 子集编程，简单易学。这个索引将对C 语言程序员有所帮助）Nachos操作系统本身只提供了一套框架,很多地方的实现都需要我们自己来完善,因此我们可以通过修改其源代码,来丰富和增强Nachos操作系统的功能.更可以在完善这些功能的同时，了解操作系统的内部运行机制.Nachos 模拟了MIPS R2/3000的指令集、主存、中断系统、网络以及磁盘系统等操作系统所必须的硬件系统。用软件模拟硬件的可靠性比真实硬件高得多，不会因为硬件故障而导致系统出错，便于调试。虚拟机可以在运行时报告详尽的出错信息，更重要的是采用虚拟机使Nachos的移植变得非常容易，在不同机器上移植Nachos，只需对虚拟机部分作移植即可。MIPS R2/3000的指令集的优势：RISC指令集，指令书目少，Nachos 模拟其中的63条。编译器：GCC 可直接将C/C+源程序编译成该指令集的目标代码，而不必重写编译器。Nachos 是一个在宿主机上运行的进程，采用双CPU，即一个宿主CPU，一个虚拟机CPU，不确定性是操作系统所必须具有的特征，而Nachos 采用随机因子模拟真实操作系统的不确定性，使系统运行更加真实。Nachos 是一个可扩展的操作系统，可发挥自己的创造性进行扩展。Nachos 限制：只有一级索引结构限制了系统中最大文件的大小。Nachos 可以用面向对象的思想实现，面向对象的方法能清楚的描述操作系统的各个部分的接口，但是又没有全面的运用到面向对象的性质，例如继承性、多态性，这使得代码更易读和理解。Nachos 分五个功能模块：机器模拟、线程管理、文件系统管理、用户程序和虚拟存储以及网络系统。 由于Nachos开发没有针对windows平台的移植，Nachos 需要在虚拟机上实现，所以需要首先实现创建虚拟机，创建linux 虚拟机来实现nachos代码的编译运行。Nachos 运行时更像一个进程，但是它是完全按照操作系统思想开发的操作系统内核，具有完整的操作系统结构。 Nachos 系统结构，作为一个简单的系统编程，网络协议和文件系统只需够用即可，这里主要设计线程管理和虚拟内存，在设计时虚拟内存可以暂时不要考虑。而其他的则可以由现有系统提供，为此，线程管理为主要任务。1、2 Nachos的目录结构copyright 文件 Nachos 的版权信息readme 文件 Nachos 的readme 信息nachos.ps 文件 Nachos 的介绍文档（Postscript 格式）c+example 目录 有关C+介绍和实例doc 目录 Nachos 各个部分介绍和原有的作业要求code 目录 Nachos 各个部分的源代码最主要的Nachos 的源代码部分MakefileMakefile.depNachos 的Makefile 文件，当Nachos 需要移植到其它系统时，可以修改Makefile.dep 中的HOST 参数machine 目录 Nachos 虚拟机模拟部分源代码threads 目录 Nachos 线程管理部分源代码filesys 目录 Nachos 文件系统管理部分源代码userprog 目录 Nachos 用户程序部分源代码network 目录 Nachos 网络管理部分源代码vm 目录 Nachos 虚拟内存管理部分源代码test 目录 一些测试用应用程序bin 目录 包含有用户程序目标码变换的程序1、3 线程基础知识线程基本概念：是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和撤消另一个线程，同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约，致使线程在运行中呈现出间断性。线程状态：就绪、阻塞和运行三种基本状态。 线程是程序中一个单一的顺序控制流程.在单个程序中同时运行多个线程完成不同的工作,称为多线程. 线程和进程的区别在于,子进程和父进程有不同的代码和数据空间,而多个线程则共享数据空间,每个线程有自己的执行堆栈和程序计数器为其执行上下文.多线程主要是为了节约CPU时间,发挥利用,根据具体情况而定. 线程的运行中需要使用计算机的内存资源和CPU线程的周期 新建 就绪 运行 阻塞 死亡线程调度与优先级 有线程进入了就绪状态,需要有线程调度程序来决定何时执行,根据优先级来调度.线程组 每个线程都是一个线程组的一个成员,线程组把多个线程集成一个对象,通过线程组可以同时对其中的多个线程进行操作.在生成线程时必须将线程放在指定的线程组,也可以放在缺省的线程组中,缺省的就是生成该线程的线程所在的线程组.一旦一个线程加入了某个线程组,不能被移出这个组.进程和线程的关系在引入线程机制后，进程不再是单一的动态实体，而是由两部分组成： 各线程活动的环境，包括：统一的地址控件、全局变量、打开文件和计时器等。 若干个线程，它们是进程中的活动部分，也是处理机的调度单位，而进程不再是处理机的最小调度单位。一个进程中的所有线程在同一地址空间中活动，共享该地址空间中的全局变量，共享打开文件和计时器等。它们总是相互协作，各自承担一个作业中的某个部分。与传统的进程相似，线程具有状态的变化。通常，这些状态是：运行、阻塞、就绪或终止。二、设计要求和目的Nachos的运宿主机通过软件模拟了各种硬件系统,包括中断系统、存储系统、磁盘文件行必须借助于、网络等。它的运行是可以跟踪的，因此，我们可以一步一步的观察操作系统是如何运行的.对于线程的管理，主要涉及到线程的扩充、nachos线程的调度机制和线程优先级。2、1 Nachos的线程管理模块Nachos平台所使用的是非抢占式调度，线程一旦占用CPU，就会一直运行到结束或者被阻塞（等待I/O事件）；Nachos平台中的线程数据结构定义非常简单，并无用户ID、线程ID等数据成员，也就是说，无法基于线程的ID来实现通信、同步互斥等机制。Nachos平台中并无全局性的线程管理机制，并未限制线程的数目，也无法了解有多少线程存在。通过修改Nachos系统平台的底层源代码来实现以下目标：1.扩充线程数据结构。增加“用户ID、线程ID”两个数据成员，同时在Nachos现有的线程管理机制中增加对这两个数据成员的维护机制。2.扩展现有的线程状态。Nachos平台中的线程状态只有“初启态”、“就绪态”、“阻塞态”、“运行态”四种情况。请增加“挂起（suspending）”这个状态，所谓“挂起”是指当前的线程映象保存在磁盘文件而不是内存中。“挂起”状态是未来实现“虚拟内存管理”的重要基础。3.修改线程调度算法。将Nachos平台的线程管理机制调整为“抢占式”。具体可选择“时间片轮转”、“优先级调度”、“多级队列”等不同的调度算法。4.增加全局性的线程管理机制。扩充Nachos平台的现有操作命令，例如可以增加一个名为“ThreadView”的命令，执行该命令，可以在屏幕上显示目前所有存在的线程信息，包括“用户ID“、“线程ID”、“当前状态”等。5.实现一个同步与互斥的例子。在完成以上修改后，可编写一个实例程序，来实现某个“同步互斥”经典问题的正确解法。例如可选择“哲学家就餐”问题，实例程序会创建5个哲学家线程，这些线程拥有同样的用户ID，可以遵循“信号量”机制来正确的运行。也可以选择“生产者消费者”问题等其他经典IPC问题。2、2 Nachos的线程线程调度算法分析Nachos平台所使用的是非抢占式调度，线程一旦占用CPU，就会一直运行到结束或者被阻塞（等待I/O事件）；Nachos平台中的线程数据结构定义非常简单，并无用户ID、线程ID等数据成员，也就是说，无法基于线程的ID来实现通信、同步互斥等机制。Nachos平台中并无全局性的线程管理机制，并未限制线程的数目，也无法了解有多少线程存在。Sysdep模块实现机制分析：sysdep.cc sysdep.h屏蔽OS间的系统调用或函数调用在形式和内容上可能有的细微差别中断处理模块实现机制分析：interrupt.cc .h模拟底层中断机制时钟中断、磁盘中断、终端读/写中断、网络接收/发送中断时钟中断模块实现机制分析：timer.cc .h模拟时钟中断，在nachos指定线程随机切换时启动时钟中断，在每次的时钟中断处理的最后加入线程的切换终端设备模块实现机制分析：console.cc .h模拟终端输入和输出，键盘的输入和显示输出，异步，当发出终端的输入输出请求后系统即返回，需要等待中断发生后才是真正完成了整个过程。磁盘设备模块实现机制分析：disk.cc .h模拟物理磁盘，nachos用宿主机种的一个文件模拟单面物理磁盘，异步工具模块：list.cc .h utility.cc .h定义链表结构及操作线程启动和调度模块：switch.s switch.h线程定义模块：thread.cc .h线程调度算法模块：scheduler.cc .hnachos主控模块：main.cc system.cc system.hnachos系统入口，分析nachos命令行参数，根据不同的选项进行不同功能的初始化设置同步磁盘：文件synchdisk.cc .h文件系统模块：filesys.cc .h模拟创建文件、删除文件、打开文件操作文件头模块：文件filehdr.cc .h打开文件结构：文件openfile.cc .h目录模块：directory.cc .hmachine.h：包含了内存的相关定义machine.cc：包含了对内存和页表的初始化translate.h：定义了页表结构translate.cc：包含了地址转换的实现以及读、写内存的操作address.cc：包含了用户程序页表的操作2、3 编程语言选择对比Java编程的优势：1.简单，面向对象，稳定，跨平台，多线程，动态 2.面向对象基于对象的编程更符合人的思维模式，更容易编写程序 3.类运行时动态加载，使得Java 可以在分布式环境下动态的维护程序及类库，当类库升级时也不必重新修改、编译。 缺点：程序速度较慢，不适合做实时性很强的开发C+编程的优势：1.增加了面向对象的思想，但是又兼具面向过程的方法 2兼容C 缺点：指针调用完成后需要手工释放内存，容易造成内存泄露而程序崩溃2、4 开发环境配置开发环境配置：类型标准配置计算机硬件内存 1G ； CPU Core i3 32位软件Windows 7；ubuntu 10.04交叉编译器GCC 2.95.4运行环境配置：类型标准配置计算机硬件内存 1G ； CPU Core i3 32位软件Windows 7；ubuntu 10.04交叉编译器GCC 2.95.42、5 NachOS 系统和交叉编译器安装2、5、1 NachOS 系统安装ubuntu10.04gcc -v Reading specs from /usr/lib/gcc-lib/i486-linux-gnu/2.95.4/specsgcc version 2.95.4 20011002 (Debian prerelease)1、解压NachOS-4.1.tgzrootubuntu:$ tar -zxvf NachOS-4.1.gz2、运行make dependrootubuntu:/桌面/NachOS-4.1/code/build.linux# make depend3、运行makerootubuntu:/桌面/NachOS-4.1/code/build.linux# make4、运行nachosrootubuntu:/桌面/NachOS-4.1/code/build.linux# ./nachostests summary: ok:0Machine halting!Ticks: total 10, idle 0, system 10, user 0Disk I/O: reads 0, writes 0Console I/O: reads 0, writes 0Paging: faults 0Network I/O: packets received 0, sent 02、5、2 交叉编译器环境的安装在编译前直接解压到local根目录下1、编译生成coff2noff工具：运行configre2.运行make生成coff2noff3.编译test目录下文件修改test/Makefile.dep中变量cpp和GCCDIR为正确的交叉编译器路径rootubuntu:/NachOS-4.1/code/test# vim Makefile.dep4.编译test目录中的程序rootubuntu:/NachOS-4.1/code/test# makerootubuntu:/NachOS-4.1/code/test# ls *.noffadd.noff halt.noff open.noff shell.noff write.noffexec.noff matmult.noff read.noff sort.noff5、执行NachOS格式文件rootubuntu:/NachOS-4.1/code/build.linux# ./nachos -x ./test/halt.nofftests summary: ok:0Machine halting!Ticks: total 21, idle 0, system 10, user 11Disk I/O: reads 0, writes 0Console I/O: reads 0, writes 0Paging: faults 0Network I/O: packets received 0, sent 03、 设计思路和程序结构3、1 线程的生成和状态转换3、1、1 基于五状态模型3、1、2 线程创建过程扩充线程管理，使其最多同时存在128个线程，测试创建线程1) 在Thread类中增加静态成员变量threadNum表示当前线程的总数量2) Fork（）创建一个线程时，threadNum加1，当线程总数超过128个线程时，程序终止。并打印终止信息3) 当一个线程终止时threadNum减14) 当系统关闭时，所有线程都结束3、2 线程调度机制当前的NachOS 系统中，线程没有优先级，每次将线程放入到就绪队列时即是将线程放到队尾，因此若要改变系统调用的线程顺序则需要确定各线程的优先级。扩充线程调度机制，测试线程数为3个1） 在Scheduler类中增加一个成员函数，表示线程的优先级，增加静态的优先级调度2） 在Thread类中增加一个函数来对就绪队列中的线程根据优先级进行排序，将优先级最高的放到队首3） 先将线程放入就绪队列，然后排序，最后从中选择下一条要执行的线程4） 具有优先级的线程将不再按照顺序执行而是根据线程的优先级执行4、 关键代码分析4、1 扩充线程管理code/threads/下的thread.cc和thread.h是线程管理部分的文件代码修改：Thread.h定义静态成员变量threadNum表示线程数量Thread.cc SelfTest () 测试创建线程4、2 扩充线程调度机制代码修改：Scheduler类中添加全局静态优先级Thread.hThread.cc4、3 扩充线程调度机制改进4、3、1 信号量机制class Semaphore public:void P();核心操作：/禁止中断，并保存初始中断状态。因为开始时中断也可能处于被禁止/状态，所以操作结束后要恢复到初始状态而不是使能中断。IntStatus oldLevel = interrupt-SetLevel(IntOff);/当信号量为0时，将当前进程放到等待队列里面，并设置为睡眠模式，/参数值为FALSE表示，进程没有正常结束而要被挂起。void V();核心操作：/禁止中断IntStatus oldLevel = interrupt-SetLevel(IntOff);/如果队列不为空说明有当前进程因为要临界资源被别的进程访问而挂/起，所以V操作首先应将当前进程设置为READY状态，以继续运行并/访问临界资源 private:int value; /信号量值 ( =0)List *queue; /线程等待队列;信号量的私有属性有信号量的值，它是一个阀门。线程等待队列中存放所有等待该信号量的线程。信号量有两个操作：P操作和V操作，这两个操作都是原子操作。P操作1. 当value等于0时，1.1. 将当前运行线程放入线程等待队列。1.2. 当前运行线程进入睡眠状态，并切换到其它线程运行。2. 当value大于0时，value-。V操作1. 如果线程等待队列中有等待该信号量的线程，取出其中一个将其设置成就绪态，准备运行。2. value+;4、3、2 实现用户更改进程优先级int SysWrite(char*buffer ,int size,OpenFileId id)；int SysRead(char*buffer ,int size,OpenFileId id)；SpaceId SysExec(char* exec_name)；int SysJoin(SpaceId id)；int SysStrncmp(char*buffer,char *str,int n)除此外添加一个处理异常的类Exception.cc相应的需要修改shell类中的代码，进行测试rootubuntu:/桌面/NachOS-4.1/code/build.linux# ./nachos -x ./test/shell.noff5、 测试5、1 测试NachOS 环境和交叉编译器rootubuntu:/桌面/18新/a测试创建线程/NachOS-4.1/code/build.linux# makeg+ -ftemplate-depth-100 -Wno-deprecated -g -Wall -I./network -I./filesys -I./userprog -I./threads -I./machine -I./lib -DFILESYS_STUB -DRDATA -DSIM_FIX -DTUT -Dx86 -DLINUX -DCHANGED -c ./threads/thread.cc./threads/thread.cc: In member function void Thread:SelfTest():./threads/thread.cc:471: warning: deprecated conversion from string constant to char*g+ bitmap.o debug.o libtest.o sysdep.o interrupt.o stats.o timer.o console.o machine.o mipssim.o translate.o network.o disk.o alarm.o kernel.o main.o scheduler.o synch.o thread.o addrspace.o exception.o synchconsole.o directory.o filehdr.o filesys.o pbitmap.o openfile.o synchdisk.o post.o switch.o -o nachosrootubuntu:/桌面/18新/a测试创建线程/NachOS-4.1/code/build.linux# ./nachosrootubuntu:/桌面/18新/a测试创建线程/NachOS-4.1/code/build.linux# ./nachos -x ./test/halt.noff5、2 测试创建线程rootubuntu:/桌面/18新/a测试创建线程/NachOS-4.1/code/build.linux# ./nachos -K5、3 测试线程优先级rootubuntu:/NachOS-4.1/code/build.linux# ./nachos -K6、 总结通过这次对nachos线程机制的扩充，较深入理解了操作系统的内核中对线程的管理和基本调度，对线程的4种状态 也有了较好的了解和运用。只是这个是线程的基于优先级的抢占式调度是静态的，动态的抢占式线程调度还没有很好的实现。本次课程设计主要围绕nachos线程模块做了分析，觉得nachos虽小但是它是一个完整的基本的操作系统，各个模块的实现虽然简单，但是它们之间相互协作能够形成一个系统，我觉得这就是操作系统的精髓，正如积小流以成江河的道理一样。真正的做一个操作系统，我认为不在于其算法有多优秀，而在于其算法有多适用，算法的适用都是因不同的环境而定的。这次课程设计，我阅读了不少的代码，从实践的角度了解了操作系统，我觉得我的收获很大。操作系统不仅仅是一门理论性很强的课程，我觉得应该更看重它的实用性。有些东西本来是很通俗易懂的，拿到理论的层面上，便变得很枯燥、很难懂。Nachos利用其简单易懂的设计使我们对课本上的概念有了更深刻的理解。在这次作业的过程中遇到一些困难，因为自己的电脑是64位的，而能找到的交叉编译器只有32位的，这对作业的进度造成很大的影响，因为这只能用同学的电脑做，但是尤其同学也有自己的课程设计要做，因此时间上就显得少了，最后只实现了少部分的功能。庆幸的是，Code:blocks 10.05在代码阅读和调试中起到了很大的作用，因为其支持代码的编译，可以测试NachOS 各部分的实现情况，虽然不能将测试结果直接输出，但是间接地给出了各部分是否能实现。这次课程设计应该很大一部分得益于此。对于操作系统的学习，对于我们而言其实是很抽象的，它不像其他课程的学习，虽然在专业学习的过程中，经常与之打交道，但是并不知道它是怎样实现进程的调度的，再有一点是我们对硬件也不是很熟悉它们的构造。尽管在学习电子技术时接触到一些，但是