操作系统课程设计任务书(计算机、软件、网络).docVIP

2016-2017学年第一学期操作系统课程设计任务书依照大纲和课程内容实践特点，结合操作系统、LINUX操作系统和嵌入式程序设计课程主要内容，课设的具体要求及任务如下：一、设计成果的要求课程设计应严格按照要求完成，在系统调试成功后, 需要提供操作系统课程设计报告，具体包括：（1)设计目的 （1)设计内容 （3）设计准备（理论、技术） （4)设计过程（设计思想、代码实现） （5)设计结果并分析 （6）系统的结构、原理框图和模块等的详细说明 （7)用户使用说明书和参考资料 （8）设计体会。注：1.（1）-（7）项可以打印，（8）设计体会必须手写。 2. 报告的封皮、封底，采用给定的模板；报告的内容，在教师的指导下，独立完成，自主排版，不做统一要求。二、设计任务（每名同学选一题，独立完成）题目一：进程与线程Linux进程与线程通讯1. 设计目的深刻理解线程和进程的概念，掌握线程与进程在组成成分上的差别以及与其相适应的通讯方式和应用目标。Linux系统的fork()保持了UNIX的经典语义，被创建的进程具有独立于父进程的地址空间，二者之间的通讯通常可采用pipe机制，clone（）是Linux系统特有的系统调用，可以通过参数确定父子进程之间是否共享存储空间等资源。在地址空间等资源共享的情况下，clone实质相当于创建了一个轻进程或线程，这是clone的通常用法。实际在Linux系统中，fork以及用户级线程pthread都是基于clone实现的。2. 设计内容以Linux系统进程和线程机制为背景，掌握fork()和clone（）系统调用的形式和功能以及与其相适应的高级通讯方式。由fork派生的子进程之间通过pipe通讯，由clone创建的线程之间通过共享内存通讯，对于后者需要考虑互斥问题。以生产者-消费者问题为例，通过实验理解fork（）和clone（）两个系统调用的区别。程序要求能够创建4个进程或线程，其中包括两个生产者和两个消费者，生产者和消费者之间能够传递数据。题目二：处理机调度实时调度算法EDF和RMS1. 设计目的深入理解处理机调度算法，了解硬实时概念，掌握最早截止期优先调度算法EDF(Earliest Deadline First)和速率单调调度算法RMS（Rate Monotonic Scheduling）的可调度条件，并能在可调度情况下给出具体调度结果。2. 设计内容在Linux环境中采用用户级线程模拟实现EDF和RMS两种实时调度算法。给定一组实时任务，按照EDF算法和RMS算法分别判断是否可调度。在可调度的情况下，创建一组用户级线程，分别代表各个实时任务，并按算法所确定的调度次序安排各个线程运行，运行时在终端上画出其Gantt图。为避免图形绘制冲淡算法，Gantt图可用字符表示。题目三：存储管理动态异长存储资源分配算法1. 设计目的理解动态异长存储分区资源管理，掌握所需数据结构和管理程序，了解各种存储分配算法的优点和缺点。2. 设计内容（1）分析UNIX最先适应（First Fit,FF）存储分配算法，即map数据结构、存储分配函数malloc()和存储释放函数mfree()，找出与算法有关的成分。(2) 修改上述与算法有关的成分，使其分别体现BF（Best Fit,最佳适应）分配原则和WF(Worst Fit，最环适应)分配原则。题目四：文件系统Hash结构文件1. 设计目的理解Linux文件系统的内部技术，掌握Linux与文件有关的系统调用命令，并在此基础上建立面向随机检索的Hash结构文件。 Linux系统保持UNIX文件系统的风格，提供流式文件界面，这种结构具有简洁灵活的特点，但并不直接支持记录式文件和关键字检索。本设计在Linux文件系统基础上，设计一组库函数，以提供对随机检索的支持。2. 设计内容 （1）参考教程中Hash文件构造算法，设计一组Hash文件函数，包括Hash文件创建、打开、关闭、读、写等。（2）编写一个测试程序，通过记录保存、查找、删除等操作，检查上述Hash文件是否实现相关功能。题目五：设备管理Linux设备驱动程序安装1. 设计目的认识Linux设备的种类和设备工作方式，理解设备驱动程序的工作原理，掌握设备驱动程序的编写规范，能编写并安装简单的设备驱动程序。2. 设计内容在Linux系统中，编写一个简单的字符型设备驱动程序模块，设备具有独占特性，可执行读和写操作，相关系统调用为open,close,read,write。Open和close分别相当于请求和释放设备，read和write将内容保存在设备模块内的绥冲区中。设备模块可动态注册和卸载，并建立与之对应的特殊文件/dev/mydev。题目六：Bootloader引导程序设计与实现1.设计目的 认识Bootloader的作用，深入理解Bootloader的编程思想。以典型的引导程序vivi为例，对vivi程序的架构，vivi的启动流程，使用vivi完成系统引导程序的设计方法形成深刻的理解和认识。2. 设计内容 在嵌入式操作系统中，Bootloader的作用与PC机上的BIOS类似，通过Bootloader可以完成对系统板上的主要部件如CPU、SDRAM、Flash、串行口等进行初始化。当运行操作系统时，它会在操作系统内核运行之前运行，通过它，可以分配内存空间的映射，从而将系统的软硬件环境带到一个合适的状态，以便为最终调用操作系统准备好正确的环境。 本设计要求同学首先分析老师提供的vivi程序源代码，理清vivi程序的架构分为哪几个模块，然后根据分析vivi程序的执行流程具体分为哪几个阶段，各阶段的主要任务是什么。最后要求同学编写内存映射初始化函数mem_map_init()和内存管理单元初始化函数mmu_init()。题目七：嵌入式linux下键盘驱动程序的设计与实现1.设计目的 通过完成对嵌入式linux下键盘驱动程序的设计和调试，掌握嵌入式linux驱动程序的编写方法，理解驱动程序动态模块的调试方法，掌握驱动程序添加到内核的流程。2. 设计内容 设备驱动程序是操作系统内核和机器硬件之间的接口。设备驱动程序为应用程序屏蔽了硬件的细节，故在应用程序看来，硬件设备只是一个设备文件，应用程序可以像操作普通文件一样对硬件设备进行操作。 本设计要求同学按照标准设备驱动程序的步骤编写驱动程序。由于键盘的设备驱动程序属于字符设备的驱动，因此，应当按照字符设备的规则编写。要求同学编写键盘设备文件file_operations结构，以及以下几个键盘操作函数：键盘控制函数Kbd_Ioctl()、关闭键盘设备函数Kbd_Close()、打开键盘设备函数Kbd_Open()、获取键值函数Kbd_Getkey()、键盘服务子程序Kbd_ISR()、键盘设备的硬件初始化函数Setup_Kbd()、注册键盘设备使用函数KbdInit()和卸载键盘设备函数Kbd_Exit()。题目八：首次适应算法的动态分区分配方式模拟1. 设计目的了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。2. 设计内容1）用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。2）假设初始状态如下，可用的内存空间为640KB，并有下列的请求序列；作业1申请130KB作业2申请60KB作业3申请100KB作业2释放60KB作业4申请200 KB作业3释放100 KB作业1释放130 KB作业5申请140 KB作业6申请60 KB作业7申请50KB作业6释放60 KB请采用首次适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。题目九：循环首次适应算法的动态分区分配方式模拟1.设计目的了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。2.设计内容1）用C语言实现采用循环首次适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。2）假设初始状态如下，可用的内存空间为640KB，并有下列的请求序列；作业1申请130KB作业2申请60KB作业3申请100KB作业2释放60KB作业4申请200 KB作业3释放100 KB作业1释放130 KB作业5申请140 KB作业6申请60 KB作业7申请50KB作业6释放60 KB请采用循环首次适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。题目十：最佳适应算法的动态分区分配方式模拟1设计目的了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。2设计内容1）用C语言分别实现采用最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。2）假设初始状态如下，可用的内存空间为640KB，并有下列的请求序列；作业1申请130KB作业2申请60KB作业3申请100KB作业2释放60KB作业4申请200 KB作业3释放100 KB作业1释放130 KB作业5申请140 KB作业6申请60 KB作业7申请50KB作业6释放60 KB请采用最佳适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。题目十一：最坏适应算法的动态分区分配方式模拟1设计目的了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。2设计内容1）用C语言分别实现采用最坏适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。2）假设初始状态如下，可用的内存空间为640KB，并有下列的请求序列；作业1申请130KB作业2申请60KB作业3申请100KB作业2释放60KB作业4申请200 KB作业3释放100 KB作业1释放130 KB作业5申请140 KB作业6申请60 KB作业7申请50KB作业6释放60 KB请采用最坏适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。 题目十二： 进程调度模拟算法1设计目的通过算法的模拟加深对进程概念和进程调度过程的理解，掌握进程状态之间的切换，同时掌握进程调度算法的实现方法和技巧。2设计内容(1) 用C语言来实现对N个进程采用动态优先权优先算法的进程调度。(2) 每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：l 进程标识数ID；l 进程优先数PRIORITY，并规定优先数越大的进程，其优先权越高；l 进程已占用的CPU时间CPUTIME；l 进程还需占用的CPU时间ALLTIME。当进程运行完毕时，ALLTIME变为0；l 进程的阻塞时间STARTBLOCK，表示当进程再运行STARTBLOCK个时间片后，进程将进入阻塞状态；l 进程被阻塞的时间BLOCKTIME，表示已阻塞的进程再等待BLOCKTIME个时间片后，进程将转换成就绪状态；l 进程状态STATE；l 队列指针NEXT，用来将PCB排成队列。(3) 优先数改变的原则：l 进程在就绪队列中呆一个时间片，优先数增加1；l 进程每运行一个时间片，优先数减3。(4) 假设在调度前，系统中有5个进程，它们的初始状态如下：ID01234PRIORITY93830290CPUTIME00000ALLTIME33634STARTBLOCK2-1-1-1-1BLOCKTIME30000STATEREADYREADYREADYREADYREADY(5) 为了清楚地观察进程的调度过程，程序应将每个时间片内的进程的情况显示出来，参照的具体格式如下：RUNNING PROG: iREADY_QUEUE:-id1-id2BLOCK_QUEUE:-id3-id4=ID01234PRIORITYP0P1P2P3P4CPUTIMEC0C1C2C3C4ALLTIMEA0A1A2A3A4STARTBLOCKT0T1T2T3T4BLOCKTIMEB0B1B2B3B4STATES0S1S2S3S4题目十三：请求调页存储管理方式的模拟11设计目的通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。2设计内容 1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。 2）用c语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。 3）置换算法：采用先进先出（FIFO）置换算法。提示: （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： 50%的指令是顺序执行的； 25%的指令是均匀分布在前地址部分； 25%的指令是均匀分布在后地址部分；具体的实施方法是： 在0，319的指令地址之间随机选取一起点m； 顺序执行一条指令，即执行地址为m+1的指令； 在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m； 顺序执行一条指令，其地址为m+1的指令； 在后地址m+2，319中随机选取一条指令并执行； 重复上述步骤，直到执行320次指令。（2）将指令序列变换为页地址流 设页面大小为1K； 用户内存容量为4页到32页； 用户虚存容里为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令为第0页（对应虚存地址为0，9）；第10条第19条指令为第1页（对应虚存地址为10，19）；第310条第319条指令为第31页（对应虚存地址为310，319）。按以上方式，用户指令可组成32页。（3）计算先进先出（FIFO）算法在不同内存容量下的命中率。其中，命中率=1-页面失效次数/页地址流长度题目十四：请求调页存储管理方式的模拟21设计目的通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。2设计内容 1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。 2）用C语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。 3）置换算法：最近最久未使用（LRU）算法。 提示: （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： 50%的指令是顺序执行的； 25%的指令是均匀分布在前地址部分； 25%的指令是均匀分布在后地址部分；具体的实施方法是： 在0，319的指令地址之间随机选取一起点m； 顺序执行一条指令，即执行地址为m+1的指令； 在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m； 顺序执行一条指令，其地址为m+1的指令； 在后地址m+2，319中随机选取一条指令并执行； 重复上述步骤，直到执行320次指令。（2）将指令序列变换为页地址流 设页面大小为1K； 用户内存容量为4页到32页； 用户虚存容里为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令为第0页（对应虚存地址为0，9）；第10条第19条指令为第1页（对应虚存地址为10，19）；第310条第319条指令为第31页（对应虚存地址为310，319）。按以上方式，用户指令可组成32页。（3）计算最近最少使用（LRU）算法在不同内存容量下的命中率。其中，命中率=1-页面失效次数/页地址流长度题目十五：请求调页存储管理方式的模拟31设计目的通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。2设计内容 1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。 2）用C语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。 3）置换算法：最佳置换（OPT）算法。 提示: （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： 50%的指令是顺序执行的； 25%的指令是均匀分布在前地址部分； 25%的指令是均匀分布在后地址部分；具体的实施方法是： 在0，319的指令地址之间随机选取一起点m； 顺序执行一条指令，即执行地址为m+1的指令； 在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m； 顺序执行一条指令，其地址为m+1的指令； 在后地址m+2，319中随机选取一条指令并执行； 重复上述步骤，直到执行320次指令。（2）将指令序列变换为页地址流 设页面大小为1K； 用户内存容量为4页到32页； 用户虚存容里为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令为第0页（对应虚存地址为0，9）；第10条第19条指令为第1页（对应虚存地址为10，19）；第310条第319条指令为第31页（对应虚存地址为310，319）。按以上方式，用户指令可组成32页。（3）计算最佳置换（OPT）算法在不同内存容量下的命中率。其中，命中率=1-页面失效次数/页地址流长度题目十六：请求调页存储管理方式的模拟41设计目的通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。2设计内容 1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。 2）用C语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。 3）置换算法：最少访问（LFU）算法。 提示: （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： 50%的指令是顺序执行的； 25%的指令是均匀分布在前地址部分； 25%的指令是均匀分布在后地址部分；具体的实施方法是： 在0，319的指令地址之间随机选取一起点m； 顺序执行一条指令，即执行地址为m+1的指令； 在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m； 顺序执行一条指令，其地址为m+1的指令； 在后地址m+2，319中随机选取一条指令并执行； 重复上述步骤，直到执行320次指令。（2）将指令序列变换为页地址流 设页面大小为1K； 用户内存容量为4页到32页； 用户虚存容里为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令为第0页（对应虚存地址为0，9）；第10条第19条指令为第1页（对应虚存地址为10，19）；第310条第319条指令为第31页（对应虚存地址为310，319）。按以上方式，用户指令可组成32页。（3）计算最少访问（LFU）算法在不同内存容量下的命中率。其中，命中率=1-页面失效次数/页地址流长度题目十七：请求调页存储管理方式的模拟51设计目的通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。2设计内容 1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。 2）用C语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。 3）置换算法：最近最不经常使用（NRU）算法。 提示: （1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成： 50%的指令是顺序执行的； 25%的指令是均匀分布在前地址部分； 25%的指令是均匀分布在后地址部分；具体的实施方法是： 在0，319的指令地址之间随机选取一起点m； 顺序执行一条指令，即执行地址为m+1的指令； 在前地址0，m+1中随机选取一条指令并执行，该指令的地址为m； 顺序执行一条指令，其地址为m+1的指令； 在后地址m+2，319中随机选取一条指令并执行； 重复上述步骤，直到执行320次指令。（2）将指令序列变换为页地址流 设页面大小为1K； 用户内存容量为4页到32页； 用户虚存容里为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条第9条指令为第0页（对应虚存地址为0，9）；第10条第19条指令为第1页（对应虚存地址为10，19）；第310条第319条指令为第31页（对应虚存地址为310，319）。按以上方式，用户指令可组成32页。（3）计算最近最不经常使用（NRU）算法在不同内存容量下的命中率。其中，命中率=1-页面失效次数/页地址流长度题目十八： P、V操作及进程同步的实现11设计目的掌握信号量通信方式的一般方法，了解系统实现“阻塞”和“唤醒”功能的方法和技巧。同时掌握进程同步和互斥的概念及实现技术。2设计内容1）用语言编程实现P、V原语并用P、V原语描述如下理发师-顾客问题：有一个理发师，一把理发椅和n把提供给等候理发的顾客座的椅子。如果没有顾客，则理发师便在理发椅子上睡觉；当第一个顾客到来时，必须唤醒该理发师进行理发；如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，他就坐下来等待，如果没有空椅子，他就离开理发店。为理发师和顾客各编一段程序描述他们的行为，要求不能带有竞争条件，试用P、V操作实现。2）实验要求及说明 定义信号量并将P、V操作定义为带参数 以输出字符串的形式表示理发师和顾客的行为。 设计适当的数据结构和函数描述顾客等待队列和“唤醒”理发师理发过程，以及没有顾客时的“阻塞”理发师过程。 编程时需考虑理发师和顾客对应的程序是并发操作的。提示：可利用随机函数模拟并发操作。 理发师和顾客两个进程各自调用一个函数模拟生产及消费的操作。题目十九： P、V操作及进程同步的实现21设计目的掌握信号量通信方式的一般方法，了解系统实现“阻塞”和“唤醒”功能的方法和技巧。同时掌握进程同步和互斥的概念及实现技术。2设计内容用语言编程实现P、V原语并用P、V原语哲学家就餐问题：为每个哲学家各编一段程序描述他们的行为，试用P、V操作实现。题目二十：银行家算法1设计目的1）了解多道程序系统中，多个进程并发执行的资源分配。2）掌握银行家算法，了解资源在进程并发执行中的资源分配情况。3）掌握预防死锁的方法，系统安全状态的基本概念。2设计内容设计一个n个并发进程共享m个系统资源的程序以实现银行家算法。要求：1） 简单的选择界面；2） 能显示当前系统资源的占用和剩余情况。3） 为进程分配资源，如果进程要求的资源大于系统剩余的资源，不与分配并且提示分配不成功；4） 撤销作业，释放资源。编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并采用适当的算法，有效地防止和避免死锁的发生。银行家算法分配资源的原则是：系统掌握每个进程对资源的最大需求量，当进程要求申请资源时，系统就测试该进程尚需资源的最大量，如果系统中现存的资源数大于或等于该进程尚需求资源最大量时，就满足进程的当前申请。这样就可以保证至少有一个进程可能得到全部资源而执行到结束，然后归还它所占有的全部资源供其它进程使用。银行家算法中的数据结构(1)可利用资源向量Available(一维数组)是一个含有m个元素，其中的每一个元素代表一类可利用的资源数目，其初值是系统中所配置的该类全部可用资源数目。如果Availablej=k，表示系统中现有Rj类资源k个。(2)最大需求矩阵Max(二维数组)m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i,j)=k，表示进程i需要Rj类资源的最大数目为k。(3)分配矩阵Allocation(二维数组)m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation(i,j)=k，表示进程i当前已分得Rj类资源k个。(4)需求矩阵Need(二维数组)是一个含有n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need(i,j)=k，表示进程i还需要Rj类资源k个，方能完成其任务。Need(i,j)=Max(i,j)-Allocation(i,j)题目二十一：SPOOLING技术1设计目的设计一个SPOOLING假脱机输出的模拟程序，更好地理解和掌握SPOOLING技术的实现原理。2设计内容SPOOLING技术广泛地应用于各种计算机的I/O。该技术通过预输出和缓输出的方法，使用共享设备的一部分来模拟独占设备。1）设计一个实现SPOOLING技术的进程设计一个SPOOLING输出服务进程、一个SPOOLING输出进程、两个用户请求进程。用户进程请求输出一系列信息，调用输出服务进程，由输出服务进程将该信息送入输出井。等待SPOOLING进程进行输出。SPOOLING输出进程工作时，根据请求块记录的各进程要输出的信息将其输出。2）设计进程调度算法进程调度采用随机算法，两个请求输出的用户进程的调度概率各为45%，SPOOLING输出进程为10%，这由随机数发生器产生的随机数来模拟决定。1） 进程状态2） 进程基本状态有可执行、等待、结束三种。可执行状态就是进程正在运行或等待调度的状态；等待状态又分为等待状态1、等待状态2、等待状态3。状态变化的条件为: 进程执行完成时，置为“结束”态。 服务程序在将输出信息送输出井时，如发现输出井已满，将调用进程置为“等待状态1”。 SPOOLING进程在进行输出时，若输出井空，则进入“等待状态2”。 SPOOLING进程输出一个信息块后，应立即释放该信息块所占的输出井空间，并将正在等待输出的进程置为“可执行状态”。 服务程序在输出信息到输出井并形成输出请求信息块后，若SPOOLING进程处于等待态，则将其置为“可执行态”。 当用户进程申请请求输出块时，若没有可用请求时，调用进程进入“等待状态3”。题目二十二：进程间通信1设计目的Linux系统的进程通信机构（IPC）允许在任意进程间大批量的交换数据。本实验的目的是了解和熟悉Linux支持的通信机制、共享存储区机制及信号量机制。2设计内容（1） 共享存储区的创建，链接和断开（2） 消息的创建，发送和接收（3） 编写程序1，实现利用共享存储区进行进程通信。使用系统调用shmget()，shmat()， shmdt()及shmctl()编制一长度为1k的消息发送和接收程序。（4） 编写程序2，实现利用消息队列进行进程通信。使用系统调用shmget()，shmat()， shmdt()及shmctl()编制一长度为1k的消息发送和接收程序。（1） 为了便于操作和观察结果，用一个程序作为“引子”，先后fork（）两个子进程，SERVER和CLIENT，进行通信。（2） SERVER端建立一个Key为75的共享区，并将第一个字节置为-1，作为数据空的标志，等待其他进程发来的消息。当该字节的值发生变化时，表示收到了消息，进行处理。然后再次把它的值设为-1。如果遇到的值为0，则视为结束信号，取消该队列，并退出SERVER。SERVER每接收到一个消息后显示一句“（server）received”。（3） CLIENT端使用Key为75的共享区，当共享取得第一个字节为-1时，SERVER端空闲，可发送请求。CLIENT随即填入9到0。期间等待SERVER端再次空闲。进行完这些操作后，CLIENT退出。CLIENT每发送一条信息后显示一句“（client）sent”。（4） 父进程在SERVER和CLIENT均退出后结束。题目二十三：进程的管道通信和软中断通信1设计目的加深对进程概念的理解，明确进程和程序的区别。进一步认识并发执行的实质，并了解Linux系统中进程通信的基本原理。2设计内容（1）编制一段程序，实现进程的管道通信。使用系统调用pipe()建立一条管道线，两个子进程P1和P2分别向管道各写一句话：Child 1 is sending a message!Child 2 is sending a message!而父进程则从管道中读出来自两个子进程的信息，显示在屏幕上。要求父进程先接收子进程P1发来的消息，再接收子进程P2发来的消息。（2）编制一段程序，实现进程的软中断通信。使用系统调用fork()创建两个子进程，再用系统调用signal()让父进程捕捉键盘上来的中断信号（即按DEL键）；当捕捉到中断信号后，父进程用系统调用Kill()向两个子进程发出信号，子进程捕捉到信号后分别输出下列信息后终止：Child 1 is killed by parent!Child 2 is killed by parent!父进程等待两个子进程终止后，输出下列信息后终止。Parent is killed!题目二十四：linux进程与线程通讯1设计目的：深刻理解线程和进程的概念，掌握线程和进程在组成成分上的差别以及与其相适应的通信方式和应用目标。2设计内容：以Linux系统进程和线程机制为背景，掌握fork()和clone()系统调用的形式和功能以及与其相适应的高级通信方式。由fork派生的子进程之间通过pipe通信，由clone创建的线程之间通过共享内存通信。以生产者-消费者为例，通过实验理解fork和clone两个系统调用的区别。程序要求能够创建4个进程或线程，其中包括两个生产者和两个消费者，生产者和消费者之间能够传递数据。题目二十五：动态不等长存储资源分配算法1设计目的：理解动态异常存储分区资源管理，掌握所需数据结构和管理程序，了解各种存储分配算法的优缺点。2设计内容：（1）分析Unix最先适应（first fit，ff）存储分配算法。即map数据结构、存储分配函数ma lloc()和存储释放函数mfree()，找出与算法有关的成分。（2）修改上述算法有关成分，使其分别体现BF(best fit，最佳适应)分配原则WF(worst fit，最坏适应)分配原则。题目二十六：编程演示三种存储管理方式的地址换算过程1设计目的：理解页式、段式、段页式的逻辑地址向物理地址的转换过程。理解重定位的含义。要求演示正确、清晰，编程所用工具不限2设计内容：编程实现演示页式、段式、段页式的地址转换过程1、分页方式的地址换算2、分段方式的地址换算3、段页式的地址换算题目二十七：编程模拟多进程共享临界资源1设计目的：理解多进程共享临界资源的原理，并编程实现2设计内容：要求产生3 个进程：（1） 两个进程模拟需要进入临界区的用户进程，当需要进入临界区时，显示：“进程x请求进入临界区”，同时向管理进程提出申请；申请返回，表示进入了临界区。在临界区中等待一段随机时间，并显示：“进程x 正在临界区”；当时间结束，显示：“进程x 退出临界区”,同时向管理进程提出退出申请；当申请返回，显示：“进程x 已退出临界区。”（2）一个进程作为原语的管理进程，接受其他进程的临界区进入请求：如果允许进入，则设置相应变量，然后返回；如果不允许进入，则进入循环等待，直到允许为止；（3）对临界区的访问应遵循空闲让进、忙则等待、有限等待、让权等待的准则。（4）进程间通信可以采用信号、消息传递、管道或网络通信方式。题目二十八：文件系统的设计与实现1设计目的：通过设计一个小型文件系统，进一步掌握文件管理的方法和技术，在实践中去认识文件系统的实现原理，加深对文件系统存储、数据的安全性和一致性理解，使学生初步具有研究、设计、编制和调试操作系统模块的能力。2设计内容：实现一个模拟文件系统，可为该文件系统设计相应的数据结构来管理目录、磁盘空闲空间、已分配空间等。 提供文件的创建、删除、移位、改名等功能。 、提供良好的界面，可以显示磁盘文件系统的状态和空间的使用情况。 提供虚拟磁盘转储功能，可将信息存入磁盘，还可从磁盘读入内存。题目二十九：主存空间的分配与回收1设计目的本设计题目主要让大家熟悉主存的各种分配与回收。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时，将作业或进程所占用的主存空间归还给系统。主存的分配与回收的实现是与主存储器的管理方式有关的。通过本次设计，帮助学生理解在不同的存储管理方式下，如何实现主存空间的分配与回收。使学生初步具有研究、设计、编制和调试操作系统模块的能力。2设计内容采用可变式分区管理，使用首次或最佳适应算法实现主存的分配与回收。可以采用分区说明表或空闲区链来进行。设计多个作业或进程动态请求内存资源的模拟系统，使用首次或最佳适应算法实现内存的分配与回收，实现可变式分区管理；设计相应的内存分配算法，定义相关数据结构，以及输出显示每次请求分配内存的结果和内存的已分配和未分配的状况。题目三十： Windows多线程控制台程序1. 设计目的学习和掌握如何编写Windows多线程控制台程序。通过编写程序，加深对进程和线程关系的理解，掌握多线程程序的执行和编写技巧。 2. 设计内容写一个单进程多线程的Windows控制台程序，该程序在一个进程内建立N个线程来执行指定的任务。N由命令行传递给系统。 Win32控制台程序中，主函数的格式如： Void main(int argc,char *argv)，可以获取命令行参数。 通过VC+“工程/设置”的C/C+属性页设置应用程序为“MTD”多线程。 利用win32 API CreateThread()来生成线程。题目三十一：读者与写者问题（进程同步问题）1设计目的了解进程同步的概念，理解信号量机制的原理，掌握运用信号量解决进程同步问题的方法，进而学会运用进程的同步与互斥。 设计要求：编程模拟读者与写者问题，要求显示结果。 2. 设计内容（1）多个进程共享一个文件，其中只读文件的称之为读者，其余只写文件的称为写者。读者可以同时读，但是写者只能独立写。 （2）对（1）修改，使得它对写者优先，即一旦有写者到，后续的读者都必须等待，而无论是否有读者在读文件。题目三十二：模拟文件管理系统1设计目的深入了解文件管理系统，初步掌握文件管理系统的实现方法。 2. 设计内容编写一程序，模拟一个简单的文件管理系统。树型结构，目录下可以是目录，也可以是文件。 在此文件管理系统，可实现的操作有： 改变目录：格式：cd 显示目录：格式：dir 创建目录：格式：md 删除目录：格式：rd 新建文件：格式：edit 删除文件：格式：del 退出文件系统：exit 实现参考： （1） 文件系统采用二叉树型存储结构，结点结构如下： Struct FileNode Char filenameFILENAME_LEN;/文件名/目录名 Int isdir ;/目录、文件的识别标志 Int i_nlink;/文件链接数 Int adr;/文件的地址 Struct FileNode *parent,*child;/指向父亲的指针和左孩子的指针 Struct FileNode *sibling_prev,*sibling_next;/指向前一个兄弟的指针和后一个兄弟的指针。 （2） 目录名和文件名支持全路径名和相对路径名，路径名各分量间用“/”隔开 （3） 功能具体描述： 改变目录：改变当前工作目录，目录不存在是给出出错信息 显示目录：显示指定目录下或当前目录下所有文件和一级目录（选做：带/s参数的dir命令，显示所有子目录） 创建目录：在指定路径或当前路径下创建指定目录。重名时给出出错信息。 删除目录：删除指定目录下所有文件和子目录。要删目录不空时，要给出提示是否要删除。 创建文件：创建指定名字的文件，只要创建表示文件的节点即可，内容及大小不考虑。 删除文件：删除指定文件，不存在时给出出错信息。 退出文件系统：exit （4） 总体流程： 初始化文件目录 输出提示符，等待接受命令，分析键入的命令； 对合法的命令，执行相应的处理程序，否则输出错误信息，继续等待新命令。直到键入exit退出为止。题目三十三: 内存的申请与释放1.设计目的了解操作系统内存分配的算法。 2.设计内容 （1） 定义一个自由存储块链表，按块地址排序，表中记录块的大小。当请求分配内存时，扫描自由存储块链表，址到找到一个足够大的可供分配的内存块，若找到的块大小正好等于所请求的大小时，就把这一块从自由链表中取下来，返回给申请者。若找到的块太大，即对其分割，并从该块的高地址部分往低地址部分分割，取出大小合适的块返回给申请者，余下的低地址部分留在链表中。若找不到足够大的块，就从操作系统中请求另外一块足够大的内存区域，并把它链接到自由块链表中，然后再继续搜索。 释放存储块也要搜索自由链表，目的是找到适当的位置将要释放的块插进去，如果被释放的块的任何一边与链表中的某一块临接，即对其进行合并操作，直到没有合并的临接块为止，这样可以防止存储空间变得过于零碎。 （