计算机系统与系统软件课程设计任务书.doc

计算机系统与系统软件课程设计任务书一、 课程设计目的 计算机系统与系统软件课程设计是计算机类专业的集中实践性环节之一，是学习完计算机系统与系统软件课程后进行的一次全面的综合练习。其目的在于加深对操作系统课程的理解，使学生更好地掌握操作系统的基本概念、基本原理、及基本功能，理解操作系统在计算机系统中的作用、地位和特点，具有分析实际操作系统，设计、构造和开发现代操作系统的基本能力，为今后从事的各种实际工作，如设计、分析和改进各种系统软件和应用软件提供必要的软件理论基础。二、 课程设计内容及要求课程设计要求：每位同学从下述设计任务中任选一个任务完成，上机验收运行结果，现场提问，并提交所完成该任务的课程设计报告。实验要求：1） 上机前认真使用C语言编写好程序，采用Visual C+6.0作为编译环境；2） 上机时独立调试程序3） 上机验收运行结果，现场提问4） 根据具体任务要求，提交课程设计实验报告，报告内容包括：课程设计目的、内容、基本原理、模块划分、数据结构、算法设计、程序流程图（包括主程序流程图、模块详细设计流程图等）、以及算法源码（必须有相关注释，以有助于说明问题为宜，不得全盘打印而不加任何注释）、心得体会等。设计内容一 页式虚拟存储管理页面置换算法1目的和要求在熟练掌握计算机虚拟存储技术的原理的基础上，利用一种程序设计语言模拟实现几种置换算法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础 2实验内容阅读教材计算机操作系统第四章，掌握存储器管理相关概念和原理。模拟实现页式虚拟存储管理的三种页面置换算法（OPT、FIFO和LRU），并通过比较性能得出结论。前提：（1）页面分配采用固定分配局部置换。（2）作业的页面走向和分得的物理块数预先指定。可以从键盘输入也可以从文件读入。（3）置换算法的置换过程输出可以在显示器上也可以存放在文件中，但必须清晰可读，便于检验。 3实验环境Windows操作系统、VC+6.0、C语言4实验提示（1）基础知识 存储管理是操作系统进行资源管理的一个重要功能。现代操作系统广泛采用虚拟存储的技术对内存进行扩充。实现虚拟存储的一个主要技术手段就是将辅存和主存统一管理，在二者之间进行对换，从而形成物理上两级而逻辑上一级的存储管理系统。一个置换算法的好坏对这个逻辑上的单级虚存的性能起着极其重要的作用，而且会影响处理机的调度性能。 对于本任务规定的前提：页面分配采用固定分配局部置换，则置换发生的时机是作业已经将操作系统分配的固定数目的物理块全部用完且发生缺页的时候。此时必须要将已经装入内存的部分逻辑页面换出以便将所缺的页面调入内存。置换算法就是一个决定将内存中“哪一个”页面换出的算法。（2）数据结构要模拟实现某一个置换算法，有如下一些对象需要用相关的数据结构来描述：l 作业的页面走向（执行过程中对页面的访问顺序）。可以用数组也可以用字符串。如果用数组，则页面走向的长度受数组长度限制，如果用字符串，则需要将字符串进行解析，将字符串经过解析处理后变成一个页面的排列顺序。考虑最佳置换算法（“向前看”）和其他置换算法（“向后看“）的特点。l 页框（作业分得的物理块）。由于作业分得的物理块数在置换算法执行之前已经确定，可以用一些比较简单的数据结构实现。在综合置换算法的原理，可以灵活采用相应的数据结构，尽可能使程序的时间复杂度最低。如对于FIFO，队列最合适，对于LRU，则数组和堆栈都比较合适，采用不同的数据结构还要配合在数据结构上的相应操作才行。 （2）功能模块划分 大体上可以将整个程序的模块划分成如下几个部分：1）主模块：主要是初始化、界面和模块调用。2）页面走向输入模块。（从键盘读入数据结构或将页面走向写入文件）3）置换算法模块。      * 判断模块。决定换出哪一块。每一种置换算法对应一种判断算法。* 调整模块。根据判断模块的结果，调整作业分得物理块集合中逻辑页面的情况。 * 置换过程输出模块（在显示器上显示或写入文件）。该模块每发生一次置换，由置换算法模块调用一次。*.除此之外，有些反复执行的操作考虑用过程或函数实现。总而言之，整个程序应该结构清晰，界面友好，可读性好，易调试，易扩充，易维护。 设计内容二 虚拟存储管理（请求分页存储管理）1目的和要求存储管理的主要功能之一是合理的分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是：通过编写和调试请求页式存储管理中页面置换算法的模拟程序以加深对存储管理方案的理解，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换方法；通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解。2实验内容阅读教材计算机操作系统第四章，掌握存储器管理相关概念和原理。（1）用C语言实现对分页式存储管理中的硬件的地址转换和产生缺页中断。（2）设计页表。分页式虚拟存储系统是把作业的副本存放在磁盘上，当作业被选中时，可把作业的开始几页先装入主存且启动执行。为此，在为作业建立页表时，应说明哪些页已在主存，哪些页尚未装入主存，页表的格式为：页 号 标 志 主存块号 在磁盘上的位置可根据页面置换算法的不同，页表构的内容可以作适当的增删。 （3）地址计算。作业执行时，指令中的逻辑地址指出了参加运算的操作数存放的页号和单元号，硬件的地址转换机构按页号查页表，若该页对应标志为“1”，则表示该页已在主存，这时根据关系式： 绝对地址=块号*块长+单元号计算出欲访问的主存单元地址。按计算出的绝对地址可以取到操作数，完成一条指令的执行。若访问的页标志为“0”，则表示该页不在主存，这时硬件发“缺页中断”信号，由OS按该页在磁盘上的位置，把该页信息从磁盘读出装入主存后再重新执行这条指令。（4）设计“地址转换”程序模拟硬件的地址转换工作。当访问的页在主存时，则形成绝对地址，但不去模拟指令的执行，而用输出转换后的地址来代替一条指令的执行。当访问的页不在主存时，则输出“*该页页号”，表示产生了一次缺页中断，执行缺页中断程序。该模拟程序的算法如图1.2所示。开始是取一条指令取指令中访问的页号查页表该页标志=1？转缺页中断子程序形成绝对地址输出绝对地址有后继指令？结束取一条指令否是否图 1.2 地址转换模拟流程图(5) 缺页中断模拟。如果访问页不在主存且页表未满，则调入一页并打印页表情况；如果该页不在主存且页表已满，则产生缺页中断，模拟算法如图1.3所示。输出：页号lnumber输出：*lnumber页号为lnumber淘汰页的页号j=phead将页lnumber装入队尾输出：页号j修改页表：第j页存在标志改为“0”第lnumber页存在标记改为“1”第lnumber页修改标记改为“0”第lnumber页主存块号为第j页原主存块号图 1.3 缺页中断算法流程图实验中采用FIFO算法进行页面淘汰。把在主存的页的页号按进入主存的先后次序排成队列，每次总是调出队首页。用数组存放页号的队列。若分配给该作业的物理块数为m，则数组由m个元素组成，p0，p1pm-1，队首指针head，队尾指针tail。当装入新页时，将其页号装入数组。3实验环境Windows操作系统、VC+6.0、C语言4实验主要步骤：1. 启动C语言环境，新建文件。2. 假定主存的每块长度为128个字节；现有一个共七页的作业，其中的第0页至第3页已经装入主存，其余三页未装入主存；该作业的页表为：015011118012219013311021400225002360121如果作业依次执行的指令序列（操作，页号，单元号）为：(+, 0, 070)、(+, 1, 050)、(*, 2, 015) 、(存, 3, 021)、(取, 0, 056)、(, 6, 040)、(移位, 4, 053)、(+, 5, 023)、(存, 1, 037)、(取, 2, 078)、(+, 0, 070)、(+, 4, 001)、(存, 6, 084)。运行设计的地址转换程序，显示或打印运行结果。因仅模拟地址转换，并不模拟指令的执行，故可不考虑上述指令序列中的操作。3. 编写程序运行。设计内容三 模拟实现可变分区存储管理1目的和要求在熟练掌握计算机分区存储管理方式的原理的基础上，利用一种程序设计语言模拟实现操作系统的可变分区存储管理的功能，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。2实验内容设计合理的数据结构来描述存储空间：对于未分配出去的部分，可以用空闲分区队列来描述，对于已经分配出去的部分，由装入内存的作业占据，可以将作业组织成链表或数组。实现分区存储管理的内存分配功能，要求选择至少两种适应算法（如首次适应算法，循环首次适应算法，最佳适应算法，最坏适应算法）。实现分区存储管理的内存回收算法：要求能够正确处理回收分区与空闲分区的四种邻接关系。当碎片产生时，能够进行碎片的拼接。3实验环境Windows操作系统、VC+6.0、C语言4实验提示（1）基础知识 分区存储管理是操作系统进行内存管理的一种方式。现代操作系统广泛采用多道程序设计的技术来提高系统吞吐量和内存的利用率。由于可变分区存储管理将一个连续的作业装入一片大小与作业恰好相等的内存中，因而地址变换的算法简单，需要的硬件支持少，变换效率高。但是最大的缺点是随着作业不断地进出内存，会将内存逐渐分割成一些大小很小而数目较多的小块，而且一块中仅能容纳一道作业，导致内存利用率较低。分区存储管理的另一个缺点是由于必须将整个作业的逻辑地址空间全部装入内存作业才可以开始运行，因而这种存储管理的方式无法实现内存的扩充。（2）数据结构要模拟实现可变分区存储管理，有如下一些对象需要用相关的数据结构来描述：l 内存中没有被存储管理程序分配给作业的部分，属于空闲内存，要求以分区为单位进行统一管理以合理分配。包括对分区的描述（结构体）和对多个分区的组织（表格或链表）。l 对于内存中已经分配给作业的那部分内存，当作业完成后应该将占据的内存归还给系统，以便进行再分配。因此必须对已分配分区进行描述和组织，以便进行内存的回收。（2）功能模块划分 大体上可以将整个程序的模块划分成如下几个部分：1）主模块：主要是初始化（设置物理内存的用户区的大小，选取适应算法）和界面，界面参考如下：初始化，选择内存分配适应算法：1-首次适应算法2-循环首次适应算法3-最佳适应算法4-最坏适应算法5-初始化6-退出选择操作步骤：1-作业进入内存（内存分配）2-作业完成（内存回收）3-显示当前自由分区链4-显示当前内存中的作业占据的分区5-碎片拼接6-退出2）内存分配算法（实现两种适应算法）3）内存回收算法（考虑四种邻接情况，尤其是采用最佳（坏）适应算法时的分区合并）4）碎片拼接算法5）空闲分区队列显示6）作业队列显示除此之外,有些反复执行的操作考虑用过程或函数实现。总而言之，整个程序应该结构清晰，界面友好，可读性好，易调试，易扩充，易维护。设计内容四 模拟实现算法多级反馈队列进程调度算法1目的和要求在熟练掌握计算机处理机调度原理的基础上，利用一种程序设计语言模拟实现多级反馈队列进程调度算法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。2实验内容模拟实现算法多级反馈队列进程调度算法，并分析其调度效果。前提： 调度算法中采用至少4级队列，每级队列的时间片大小预先指定。 由于只是模拟实现，调度的对象进程实际上并不包括程序和数据，而仅仅包括一个PCB数据结构，用PCB来代表一个进程，调度算法调度的对象只包括进程的PCB.处理机的切换通过将PCB在运行指针和就绪队列之间进行移动来实现。又因为进程的组成只有PCB，没有程序和数据，因而进程只有运行和就绪两种状态，没有等待状态。 为避免显示结果超过一屏，调度结果要求写入文件中以方便检验。3实验环境Windows操作系统、VC+6.0、C语言4实验提示（1）基础知识 由于处理机是计算机系统中最宝贵和稀有的资源，因而处理机调度是操作系统进行资源管理的一个重要功能。现代操作系统广泛采用多道程序设计的技术来提高系统吞吐量，提高程序的并发度和资源利用率。特别是进程调度程序，由于其运行频率高，更加要求调度算法简单，高效，系统开销小，进程切换快，可以说，调度算法的好坏直接影响整个计算机系统的性能。多级队列调度算法是一种动态优先数调度算法。对于普通的优先调度算法，如何确定进程优先级以真实地反映进程运行的紧迫程度是一个难题，但在多级队列调度算法中，可以预先规定优先级一样可以获得好的性能。该算法实际上综合了两种调度算法：队列内部是FCFS,队列之间是优先调度。（2）数据结构最核心的数据结构就是进程的逻辑结构。进程中必须包括的内容很多（参见教材PCB部分的定义），为了简化起见，可以略去一些与本模拟调度算法关系不大的一些信息。请同学们自行设计，要求能够实现本调度算法即可。（2）功能模块划分 大体上可以将整个程序的模块划分成如下几个部分：1）主模块：主要是初始化（队列的级数和每级队列的时间片大小）和界面，可参考如下：多级队列调度算法模拟实现1-初始化2-创建进程3-调度4-显示各级就绪队列的进程5-退出2）进程创建3）调度算法实现4）显示多级队列中的就绪进程.除此之外,有些反复执行的操作考虑用过程或函数实现。总而言之，整个程序应该结构清晰，界面友好，可读性好，易调试，易扩充，易维护。设计内容五 模拟实现银行家算法实现死锁避免1目的和要求在熟练掌握死锁发生原理和解决死锁问题的基础上，利用一种程序设计语言模拟实现利用银行家算法实现死锁避免，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。2实验内容模拟实现银行家算法实现死锁避免。要求：初始数据（如系统在T0时刻的资源分配情况、每一种资源的总数量）从文本文件读入，文件中给出最大需求矩阵Max、分配矩阵Allocation，在程序中求得需求矩阵Need和可利用资源向量Available。3实验环境Windows操作系统、VC+6.0C语言4实验提示银行家算法中的数据结构：1.可利用资源向量Available 是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。2.最大需求矩阵Max 是个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi，jk，表示进程i需要Rj类资源的最大数目为k。3.分配矩阵Allocation是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每个进程的资源数。如果Allocationi,jk，表示进程i当前已分得Rj类资源的数目为k。4.需求矩阵Need是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数，如果Needi,j=k，表示进程i还需要Rj类资源k个，方能完成其任务。三矩阵间存在下述关系：Needi,j = Maxi,j- Allocationi,j银行家算法：设Requesti是进程Pi的请求向量。如果Requestijk，表示进程Pi只需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：(1)如果Requestij< Needi,j，则转向步骤2；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果Requesti j< Availablej，则转向步骤3；否则，表示系统中尚无足够的资源，Pi必须等待。(3)系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值： Availablej:= Availablej - Requestij;Allocationi,j := Allocationi,j + Requestij;Needi,j := Needi,j - Requestij;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。安全性算法：(1)设置两个向量、工作向量Work表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，执行安全算法开始时，Work := Available。、Finish表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finishi:=false ；当有足够资源分配给进程时，令Finishi:=true 。(2)从进程集合中找到一个能满足下述条件的进程： Finishi:=false Needi,j<=workj如找到，执行步骤(3)；否则，执行步骤(4)。(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj:= Workj+ Allocationi,j ;Finishi:=true go to step 2；(4)如果所有进程的Finishi=true，则表示系统处于安全状态；否则，系统处于不安全状态。设计内容六 模拟进程调度1目的和要求在熟练掌握进程状态的转变、进程调度的策略、进程调度的过程等原理的基础上，利用一种程序设计语言模拟实现进程调度的过程，进一步体会多道程序并发执行的特点，并分析具体的调度算法的特点，掌握对系统性能的评价方法，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。2实验内容阅读教材计算机操作系统第二章和第三章，掌握进程管理及调度相关概念和原理。编写程序模拟实现进程的两种以上调度算法的调度过程，模拟程序只对PCB进行相应的调度模拟操作，不需要实际进程。假设初始状态为：有n个进程处于就绪状态，有m个进程处于阻塞状态。采用进程调度算法进行调度(调度过程中，假设处于执行状态的进程不会阻塞)，且每过t个时间片系统释放资源，唤醒处于阻塞队列队首的进程。程序要求如下：1）输出系统中进程的调度次序；2）计算CPU利用率。3实验环境Windows操作系统、VC+6.0、C语言4实验提示用C语言实现提示：1） 程序中进程可用PCB表示，其类型描述如下： struct PCB_type int pid ; /进程名int state ; /进程状态 2表示“执行”状态 1表示“就绪”状态 0表示“阻塞”状态 int cpu_time ; /运行需要的CPU时间（需运行的时间片个数） 2） 设置两个队列，将处于“就绪”状态的进程PCB挂在队列ready中；将处于“阻塞”状态的进程PCB挂在队列blocked中。 队列类型描述如下： struct QueueNode struct PCB_type PCB; Struct QueueNode *next;并设全程量：struct QueueNode *ready_head=NULL, /ready队列队首指针*ready_tail=NULL , /ready队列队尾指针*blocked_head=NULL, /blocked队列队首指针*blocked_tail=NULL; /blocked队列队尾指针3)设计子程序： start_state(); /读入假设的数据，设置系统初始状态dispath(); /模拟调度 calculate(); /计算CPU利用率4）测试用数据： n=2 m=3 t=5 ready_head blocked_headunuse_cpu+x+x=tblocked队首进程入ready队列队尾；x=0beginuse_cpu=0x=0unuse_cpu=0ready队列不空或blocked队列不空ready队列不空pß 取ready队首元素p->PCB.state置“运行”输出p->PCB.namep->PCB.cpu_time-use_cpu+p->PCB.cpu_time>0p入ready队列队尾释放pend轮转法调度过程dispath()算法流程图： /*use_cpu中记录CPU 运行时间 /*unuse_cpu中记录CPU空闲时间 否 是是 否 是 否 是 是否是三、课程设计说明书的编写规范写出课程设计说明书。说明书中除了在封面应有题目、班级、姓名、学号和课程设计日期、地点以外，其正文一般应包括：课程设计目的、内容、基本原理、模块划分、数据结构、算法设计、程序流程图（包括主程序流程图、模块详细设计流程图等）、以及部分算法源码（必须有相关注释，以有助于说明问题为宜，不得全盘打印而不加任何注释）、心得体会等。四、成绩评定方法由指导教师根据学生完成任务的情况、课程设计说明书的质量和课程设计过程中的工作态度等综合打分。1. 课程设计报告及平时：50%包括报告内容的全面性、正确性，文字表述的准确性和条理性，以及书写的工整程度等（30%）。平时主要包括考勤和操作练习的实际情况（20%）2. 设计末考核：50%包括上机验收结果和现场提问结果。