网络操作系统课程设计计划书

08级网络工程专业《网络操作系统》课程教学计划2010-2011学年第一学期一、实习目的与要求1、掌握操作系统基本理论与管理方式；2、在算法基础上，解决实际的管理功能问题，提高学生实际应用、编程的能力；3、涉及编程题目时，要求详细书写文档内容。二、实习内容项目一、进程机制与并发程序设计（一）linux下生产者与消费者的问题实现1．实验目的（1）掌握基本的同步互斥算法，理解生产者和消费者同步的问题模型。（2）了解linux中多线程的并发执行机制，线程间的同步和互斥。2、实验要求（1）创建生产者和消费者线程在linux环境下，创建一个控制台进程，在此进程中创建n个线程来模拟生产者或者消费者。这些线程的信息由本程序定义的“测试用例文件”中予以指定。该文件的格式和含义如下：31P32P43C414P25C3124第一行说明程序中设置几个临界区，其余每行分别描述了一个生产者或者消费者线程的信息。每一行的各字段间用Tab键隔开。不管是消费者还是生产者，都有一个对应的线程号，即每一行开始字段那个整数。第二个字段用字母P或者C区分是生产者还是消费者。第三个字段表示在进入相应线程后，在进行生产和消费动作前的休眠时间，以秒计时；这样做的目的是可以通过调整这一列参数，控制开始进行生产和消费动作的时间。如果是代表生产者，则该行只有三个字段。如果代表消费者，则该行后边还有若干字段，代表要求消费的产品所对应的生产者的线程号。所以务必确认这些对应的线程号存在并且该线程代表一个生产者。（2）生产和消费的规则在按照上述要求创建线程进行相应的读写操作时，还需要符合以下要求：①共享缓冲区存在空闲空间时，生产者即可使用共享缓冲区。②从上边的测试数据文件例子可以看出，某一生产者生产一个产品后，可能不止一个消费者，或者一个消费者多次地请求消费该产品。此时，只有当所有的消费需求都被满足以后，该产品所在的共享缓冲区才可以被释放，并作为空闲空间允许新的生产者使用。③每个消费者线程的各个消费需求之间存在先后顺序。例如上述测试用例文件包含一行信息“5C3l24”，可知这代表一个消费者线程，该线程请求消费1，2，4号生产者线程生产的产品。而这种消费是有严格顺序的，消费1号线程产品的请求得到满足后才能继续往下请求2号生产者线程的产品。④要求在每个线程发出读写操作申请、开始读写操作和结束读写操作时分别显示提示信息。（3）相关基础知识本实验所使用的生产者和消费者模型具有如下特点：本实验的多个缓冲区不是环形循环的，也不要求按顺序访问。生产者可以把产品放到目前某一个空缓冲区中。消费者只消费指定生产者的产品。在测试用例文件中指定了所有的生产和消费的需求，只有当共享缓冲区的数据满足了所有关于它的消费需求后，此共享缓冲区才可以作为空闲空间允许新的生产者使用。本实验在为生产者分配缓冲区时各生产者间必须互斥，此后各个生产者的具体生产活动可以并发。而消费者之间只有在对同一产品进行消费时才需要互斥，同时它们在消费过程结束时需要判断该消费对象是否已经消费完毕并清除该产品。linux用来实现同步和互斥的实体。在linux中，常见的同步对象有：信号量(Semaphore)、互斥量(Mutex)、临界段(CriticalSection)等。使用这些对象都分为三个步骤，一是创建或者初始化：接着请求该同步对象，随即进入临界区，这一步对应于互斥量的上锁；最后释放该同步对象，这对应于互斥量的解锁。这些同步对象在一个线程中创建，在其他线程中都可以使用，从而实现同步互斥。(二)Linux下读者与写者的问题实现1、设计目的通过实现经典的读者写者问题，巩固对线程及其同步机制的学习效果，加深对相关基本概念的理解，并学习如何将基本原理和实际设计有机的结合。2、设计内容在linux环境下，使用多线程和信号量机制实现经典的读者写者问题，每个线程代表一个读者或一个写者。每个线程按相应测试数据文件的要求，进行读写操作。请用信号量机制分别实现读者优先和写者优先的读者-写者问题。读者-写者问题的读写操作限制：(1)写-写互斥，即不能有两个写者同时进行写操作(2)读-写互斥，即不能同时有一个读者在读，同时却有一个写者在写(3)读-读允许，即可以有二个以上的读者同时读读者优先的附加限制：如果一个读者申请进行读操作时已有另一读者正在进行读操作，则该读者可直接开始读操作。写者优先的附加限制：如果一个读者申请进行读操作时已有另一写者在等待访问共享资源，则该读者必须等到没有写者处于等待状态后才能开始读操作。运行结果显示要求：要求在每个线程创建、发出读写操作申请、开始读写操作和结束读写操作时分别显示一行提示信息，以确信所有处理都遵守相应的读写操作限制。3、测试数据文件格式测试数据文件包括n行测试数据，分别描述创建的n个线程是读者还是写者，以及读写操作的开始时间和持续时间。每行测试数据包括四个字段，各字段间用空格分隔。第一字段为一个正整数，表示线程序号。第二字段表示相应线程角色，R表示读者是，W表示写者。第三字段为一个正数，表示读写操作的开始时间。线程创建后，延时相应时间（单位为秒）后发出对共享资源的读写申请。05k10k14k26k32k128k第四字段为一个正数，表示读写操作的持续时间。当线程读写申请成功后，开始对共享资源的读写操作，该操作持续相应时间后结束，并释放共享资源。下面是一个测试数据文件的例子：1R352W453R524R655W5.13二选一项目二、主存储器空间的分配和回收1、可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：操作系统作业1作业3空闲区作业2空闲区为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：起址长度状态第一栏14K12K未分配第二栏32K96K未分配空表目空表目其中，起址——指出一个空闲区的主存起始地址。长度——指出从起始地址开始的一个连续空闲的长度。状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。上述的这张说明表的登记情况是按提示（1）中的例所装入的三个作业占用的主存区域后填写的。(2)当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。(3)采用最先适应算法（顺序分配算法）分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。由于本实习是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。最先适应分配算法如图4-1。(4)当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示（1）中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图4-2。(5)请按最先适应算法设计主存分配和回收的程序。然后按（1）中假设主存中已装入三个作业，且形成两个空闲区，确定空闲区说明表的初值。现有一个需要主存量为6K的作业4申请装入主存；然后作业3撤离；再作业2撤离。请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。2、分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。(1)分页式存储器把主存分成大小相等的若干块，作业的信息也按块的大小分页，作业装入主存时可把作业的信息按页分散存放在主存的空闲块中，为了说明主存中哪些块已经被占用，哪些块是尚未分配的空闲块，可用一张位示图来指出。位示图可由若干存储单元来构成，其中每一位与一个物理块对应，用0/1表示对应块为空闲/已占用。(2)假设某系统的主存被分成大小相等的64块，则位示图可用8个字节来构成，另用一单元记录当前空闲块数。如果已有第0，1，4，5，6，9，11，13，24，31，共10个主存块被占用了，那么位示图情况如下：字位节数号01234567011001110101010100200000000310000001400000000500000000600000000700000000图1最先适应分配模拟算法图2主存回收算法(3)当要装入一个作业时，根据作业对主存的需要量，先查当前空闲块数是否能满足作业要求，若不能满足则输出分配不成功。若能满足，则查位示图，找出为“0”的一些位，置上占用标志“1”，从“当前空闲块数”中减去本次占用块数。按找到的计算出对应的块号，其计算公式为：块号=j8+i其中，j表示找到的是第n个字节，I表示对应的是第n位。根据分配给作业的块号，为作业建立一张页表，页表格式：页号块号012(4)当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志清成“0”，表示对应的块已成为空闲块。归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：字节号j=[块号/8]（[]表示取整）位数i={块号/8}（{}表示取余）(5)设计实现主存分配和回收的程序。假定位示图的初始状态如（2）所述，现有一信息量为5页的作业要装入，运行你所设计的分配程序，为作业分配主存且建立页表（格式如（3）所述）。然后假定有另一作业执行结束，它占用的块号为第4，5，6和31块，运行你所设计的回收程序，收回作业归还的主存块。要求能显示和打印分配或回收前后的位示图和当前空闲块数，对完成一次分配后还要显示或打印为作业建立的页表。项目三、文件系统设计（图形界面或文本模式）1、单用户多级文件系统设计本文件系统采用类似DOS系统的文件管理方式，每次调用该文件系统时，首先申请一定的内存空间，然后对该内存空间进行分配。将申请到的空间划分为目录区，文件区；采用位示图进行空间管理，盘块的分配使用显示链接（FAT表）的方式。每次调用该文件系统时自动为其分配空间，并将上次操作的结果从硬盘上调入内存；当结束调用时则将操作的结果重新存入硬盘，以便下次调用。（每次使用都会自动搜索文件系统，以此确定是否是第一次使用；若是则格式化生成文件系统，否则读取已存在的文件系统。）设计技术参数（数据结构）：#defineMaxSize100#defineDisk512//每个盘块大小为512bit#defineNumDisk2048//有2048个盘块，既可分配空间为1M/*************目录和文件的结构定义***********************/structDirectoryNode{charname[9];/*目录或文件的名字*/inttype;/*0代表目录，1代表普通文件*/structDirectoryNode*next;/*指向下一个兄弟结点的指针*/structDir