11级网络工程专业《网络操作系统》课程设计
教学计划
20##-2014学年第一学期
一、实习目的与要求
1、掌握操作系统基本理论与管理方式；
2、在算法基础上，解决实际的管理功能问题，提高学生实际应用、编程的能力；
3、涉及编程题目时，要求详细书写文档内容。
二、实习内容
项目一、进程机制与并发程序设计
（一） linux下生产者与消费者的问题实现
1、实验目的
（1）掌握基本的同步互斥算法，理解生产者和消费者同步的问题模型。
（2）了解linux中多线程的并发执行机制，线程间的同步和互斥。
2、实验要求
（1）创建生产者和消费者线程
在linux环境下，创建一个控制台进程，在此进程中创建n个线程来模拟生产者或者消费者。这些线程的信息由本程序定义的“测试用例文件”中予以指定。
该文件的格式和含义如下：
3
1 P 3
2 P 4
3 C 4 1
4 P 2
5 C 3 1 2 4
第一行说明程序中设置几个临界区，其余每行分别描述了一个生产者或者消费者线程的信息。每一行的各字段间用Tab键隔开。不管是消费者还是生产者，都有一个对应的线程号，即每一行开始字段那个整数。第二个字段用字母P或者C区分是生产者还是消费者。第三个字段表示在进入相应线程后，在进行生产和消费动作前的休眠时间，以秒计时；这样做的目的是可以通过调整这一列参数，控制开始进行生产和消费动作的时间。如果是代表生产者，则该行只有三个字段。如果代表消费者，则该行后边还有若干字段，代表要求消费的产品所对应的生产者的线程号。所以务必确认这些对应的线程号存在并且该线程代表一个生产者。
（2）生产和消费的规则
在按照上述要求创建线程进行相应的读写操作时，还需要符合以下要求：
①共享缓冲区存在空闲空间时，生产者即可使用共享缓冲区。
②从上边的测试数据文件例子可以看出，某一生产者生产一个产品后，可能不止一个消费者，或者一个消费者多次地请求消费该产品。此时，只有当所有的消费需求都被满足以后，该产品所在的共享缓冲区才可以被释放，并作为空闲空间允许新的生产者使用。
③每个消费者线程的各个消费需求之间存在先后顺序。例如上述测试用例文件包含一行信息“5 C 3 l 2 4”，可知这代表一个消费者线程，该线程请求消费1，2，4号生产者线程生产的产品。而这种消费是有严格顺序的，消费1号线程产品的请求得到满足后才能继续往下请求2号生产者线程的产品。
④要求在每个线程发出读写操作申请、开始读写操作和结束读写操作时分别显示提示信息。
（3）相关基础知识
本实验所使用的生产者和消费者模型具有如下特点：
本实验的多个缓冲区不是环形循环的，也不要求按顺序访问。生产者可以把产品放到目前某一个空缓冲区中。
消费者只消费指定生产者的产品。
在测试用例文件中指定了所有的生产和消费的需求，只有当共享缓冲区的数据满足了所有关于它的消费需求后，此共享缓冲区才可以作为空闲空间允许新的生产者使用。
本实验在为生产者分配缓冲区时各生产者间必须互斥，此后各个生产者的具体生产活动可以并发。而消费者之间只有在对同一产品进行消费时才需要互斥，同时它们在消费过程结束时需要判断该消费对象是否已经消费完毕并清除该产品。
linux用来实现同步和互斥的实体。在linux中，常见的同步对象有：信号量(Semaphore)、互斥量(Mutex)、临界段(CriticalSection)等。使用这些对象都分为三个步骤，一是创建或者初始化：接着请求该同步对象，随即进入临界区，这一步对应于互斥量的上锁；最后释放该同步对象，这对应于互斥量的解锁。这些同步对象在一个线程中创建，在其他线程中都可以使用，从而实现同步互斥。
(二)Linux下读者与写者的问题实现
1、设计目的
通过实现经典的读者写者问题，巩固对线程及其同步机制的学习效果，加深对相关基本概念的理解，并学习如何将基本原理和实际设计有机的结合。
2 、设计内容
在linux环境下，使用多线程和信号量机制实现经典的读者写者问题，每个线程代表一个读者或一个写者。
每个线程按相应测试数据文件的要求，进行读写操作。请用信号量机制分别实现读者优先和写者优先的读者-写者问题。
读者-写者问题的读写操作限制：
(1)写-写互斥，即不能有两个写者同时进行写操作
(2)读-写互斥，即不能同时有一个读者在读，同时却有一个写者在写
(3)读-读允许，即可以有二个以上的读者同时读
读者优先的附加限制：如果一个读者申请进行读操作时已有另一读者正在进行读操作，则该读者可直接开始读操作。
写者优先的附加限制：如果一个读者申请进行读操作时已有另一写者在等待访问共享资源，则该读者必须等到没有写者处于等待状态后才能开始读操作。
运行结果显示要求：要求在每个线程创建、发出读写操作申请、开始读写操作和结束读写操作时分别显示一行提示信息，以确信所有处理都遵守相应的读写操作限制。
3 、测试数据文件格式
测试数据文件包括n 行测试数据，分别描述创建的n 个线程是读者还是写者，以及读写操作的开始时间和持续时间。每行测试数据包括四个字段，各字段间用空格分隔。第一字段为一个正整数，表示线程序号。第二字段表示相应线程角色，R 表示读者是，W 表示写者。第三字段为一个正数，表示读写操作的开始时间。线程创建后，延时相应时间（单位为秒）后发出对共享资源的读写申请。第四字段为一个正数，表示读写操作的持续时间。当线程读写申请成功后，开始对共享资源的读写操作，该操作持续相应时间后结束，并释放共享资源。下面是一个测试数据文件的例子：
1 R 3 5
2 W 4 5
3 R 5 2
4 R 6 5
5 W 5.1 3
项目二、主存储器空间的分配和回收
1、 可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。
可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：
为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：
其中，起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。
上述的这张说明表的登记情况是按提示（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个主存块被占用了，那么位示图情况如下：
图1 最先适应分配模拟算法
图2 主存回收算法
(3) 当要装入一个作业时，根据作业对主存的需要量，先查当前空闲块数是否能满足作业要求，若不能满足则输出分配不成功。若能满足，则查位示图，找出为“0”的一些位，置上占用标志“1”，从“当前空闲块数”中减去本次占用块数。
按找到的计算出对应的块号，其计算公式为：
块号= j´8+i
其中，j表示找到的是第n个字节，I表示对应的是第n位。
根据分配给作业的块号，为作业建立一张页表，页表格式：
(4) 当一个作业执行结束，归还主存时，根据该作业的页表可以知道应归还的块号，由块号可计算出在位示图中的对应位置，把对应位的占用标志清成“0”，表示对应的块已成为空闲块。归还的块数加入到当前空闲块数中。由块号计算在位示图中的位置的公式如下：
字节号 j=[块号/8] （[ ]表示取整）
位数 i={块号/8} （{ }表示取余）
(5) 设计实现主存分配和回收的程序。假定位示图的初始状态如（2）所述，现有一信息量为5页的作业要装入，运行你所设计的分配程序，为作业分配主存且建立页表（格式如（3）所述）。然后假定有另一作业执行结束，它占用的块号为第4，5，6和31块，运行你所设计的回收程序，收回作业归还的主存块。
要求能显示和打印分配或回收前后的位示图和当前空闲块数，对完成一次分配后还要显示或打印为作业建立的页表。
项目三、文件系统设计
1、 单用户多级文件系统设计
本文件系统采用类似DOS系统的文件管理方式，每次调用该文件系统时，首先申请一定的内存空间，然后对该内存空间进行分配。将申请到的空间划分为目录区，文件区；采用位示图进行空间管理，盘块的分配使用显示链接（FAT表）的方式。每次调用该文件系统时自动为其分配空间，并将上次操作的结果从硬盘上调入内存；当结束调用时则将操作的结果重新存入硬盘，以便下次调用。（每次使用都会自动搜索文件系统，以此确定是否是第一次使用；若是则格式化生成文件系统，否则读取已存在的文件系统。）
设计技术参数（数据结构）：
#define MaxSize 100
#define Disk 512 //每个盘块大小为512bit
#define NumDisk 20## //有2048个盘块，既可分配空间为 1M
/*************目录和文件的结构定义***********************/
struct DirectoryNode {
char name[9]; /*目录或文件的名字*/
int type; /*0代表目录，1代表普通文件*/
struct DirectoryNode *next; /*指向下一个兄弟结点的指针*/
struct DirectoryNode *preDirFile; /*指向父结点的指针*/
struct DirectoryNode *subFile; /*指向第一个子结点的指针*/
int size; /*如果是文件则表示文件的大小*/
int first; /*起始盘块号*/
int last; /*末尾盘块号*/
int order; /*备用*/
};
//连续分配
struct FileSys {
int VacTable[NumDisk]; //空闲表,0为空闲，1为被用
struct DirectoryNode root; //根目录
struct DirectoryNode Directory[NumDisk];
} *filesys;
typedef struct {
struct DirectoryNode *DirFile;
char name[9];
}DataType; //包含一个指向目录的指针和名字
typedef struct { //队列结构的实现
DataType data[MaxSize];
int front,rear; //分别表示队列的头结点和尾结点
}Tp;
void InitQueue(Tp *sq) //队列初始化
int EnAddQueue(Tp *sq,DataType data) //在队列中增加元素
DataType EnDelQueue(Tp *sq) //从队列中删除一个元素
int Empty(Tp *sq) //判断队列是否为空，返回0表示队列为空
①．Dir:显示目录内容命令，显示当前目录下的文件和子目录。
②．Md:创建目录操作。
③．Create:创建文件，在当前目录下创建一个文件。
④. all:显示从根目录开始的所有目录和文件及其层次结点。
⑤．Cd:改变目录。
⑥．Del:删除文件操作。
⑦. Rd:删除目录操作，删除当前目录下的子目录。
⑧. Ren:重命名函数
⑨. Exit:退出命令
2.多用户文件系统设计
（1）．在内存中开辟一个虚拟磁盘空间作为文件存储器，在其上实现一个多用户多目录的文件系统。
（2）．文件物理结构可采用显式链接或其他方法。
（3）．磁盘空闲空间的管理可选择位示图或其他方法。如果采用位示图来管理文件存储空间，并采用显式链接分配方式，则可以将位示图合并到FAT中。
（4）．文件目录结构采用多用户多级目录结构，每个目录项包含文件名、物理地址、长度等信息，还可以通过目录项实现对文件的读和写的保护。
（5）．设计一个较实用的用户界面，方便用户使用。要求提供以下相关文件操作：①具有login (用户登录) ②系统初始化（建文件卷、提供登录模块）③文件的创建： create④文件的打开：open⑤文件的读：read⑥文件的写：write⑦文件关闭：close⑧.删除文件：delete ⑨.创建目录（建立子目录）：mkdir⑩改变当前目录：cd（11）列出文件目录：dir（12）退出：logout
项目四、进程调度算法的设计
设计要求：
①设计进程控制块PCB表结构，适用于多级队列反馈调度算法。
②建立进程就绪队列，编制入链子程序。
③编制多级队列反馈调度算法
设计技术参数:
①本程序用多级队列反馈调度算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。
②为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。
③在优先数算法中，优先数的值为50与运行时间的差值，即P_TIME-process->needtime。进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。
④对于遇到优先数一致的情况，采用FIFO策略解决。
项目五、linux下消息传递通信方式的分析与设计
设计要求：
①分析linux系统下几种消息传递通信方式。
②消息传递通信方式有消息缓冲通信、信箱通信和基于消息传递的网络通信等方式，选择一种通信方式，分析通信的关键技术并给出详细实例。
③设计时采用c/s模式。
项目六、页面置换算法的模拟实现
1．假设分给一作业的内存块数为4，每个页面中可存放10条指令。
2．用C语言设计一个程序，模拟一作业的执行过程。设该作业共有320条指令，即它的地址空间为32页，目前它的所有页面都还未调入内存。在模拟过程中，如果所访问的指令已经在内存，则显示其物理地址，并转下一条指令。如果所访问的指令尚未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业的虚页面，则需进行页面置换。最后显示其物理地址，并转下一条指令。在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
3．置换算法：请分别考虑OPT、FIFO和LRU算法。
4．作业中指令的访问次序要求按下述原则生成：
? 50%的指令是顺序执行的。
? 25%的指令是均匀分布在前地址（即低地址）部分。
? 25%的指令是均匀分布在后地址（即高地址）部分。
具体的实施办法是：
① 在[0，319]之间随机选取一条起始执行指令，其序号为m；
② 顺序执行下一条指令，即序号为m+1的指令；
③ 通过随机数，跳转到前地址部分[0，m-1]中的某条指令处，其序号为m1；
④ 顺序执行下一条指令，即序号为m1+1的指令；
⑤ 通过随机数，跳转到后地址部分[m1+2，319]中的某条指令处，其序号为m2；
⑥ 顺序执行下一条指令，即序号为m2+1的指令；
⑦ 重复“跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行”的过程，直至执行完全部320条指令。
5. 随机数产生办法，Linux或UNIX系统提供函数strand()和rand(),分别进行初始化和产生随机数。例如： strand (); 语句可初始化一个随机数； a[0]=10*rand()/65535*319+1; a[1]=10*rand()/65535*a[0]; 语句可用来产生a[0]与a[1]中的随机数。
项目七、linux shell程序设计
设计要求：
1.熟练掌握shell的使用，会编写简单的shell程序。
2.Linux环境下利用 shell设计和实现机房的辅助管理系统
3.利用Linux shell进行程序脚本设计，实现两大功能：编辑生成上机课表并自动生成上机用户，进行用户课前和课后管理。
4.主要技术关键的分析
（1） 定义起始登陆界面
①能显示三种信息：能根据登录用户显示欢迎对象、根据系统时间显示欢迎内容个性化的欢迎信息；有系统初始化、系统管理和退出三个菜单项操作提示菜单；
②能显示当前上课的具体时间（教学第几周、星期几第几节）和系统状态提示信息。
（2）系统初始化
①生成本机房的上机安排表：上机安排表至少包含十条记录，每条记录应有课程 、班级、起至周、上课节等内容，能对安排表进行显示、添加、删除、修改,复制。
②生成本机房的上机用户：根据上机安排表自动生成对应的上机用户，一个用户对应于安排表的一条记录，且账号= 班级+课程；密码=班级+课程号
（3）课前准备
①为用户创建一个工作环境：工作空间和用户资料。
②校正系统时间；在用户目录下创建工作目录，挂载U盘；查找所需文件；拷贝所需文件；若有压缩包则需打开压缩包；设置文件和目录属性，开放使用权限。
（4）课后整理：
①释放用户空间，进行资料收集。
②更改文件和目录属性，关闭使用权限，对发生改变和新生成文档要进行打包压缩；移动包到U盘，卸载U盘，删除在用户目录下创建工作目录。
项目八、linux中samba服务器的配置
设计要求：
① 理解samba服务器的功能。
② 列出在shell终端下安装samba服务的方法。
③ 列出在shell终端下创建用户的方法。
④ 详细列出基于共享模式的samba服务器的配置过程并给出测试结果。
⑤ 详细列出基于用户模式的samba服务器的配置过程并给出测试结果。
项目九、linux模块加载或内核编译
设计要求：
①掌握linux模块加载的方法，比如linux中驱动程序模块的加载、系统安全模块的加载等。
②掌握在Linux上进行内核编译的方法。
三、实习时间
20##年12月26日到20##年1月2日（分散进行）
具体安排：一、12月26日下午5、6、7、8节进行分组，下发课程设计题目，各小组回去查阅资料。
二、12月27日上午1、2、3、4节各小组确定题目，讨论设计方案。
三、12月28日-12月29日，各小组进行算法设计并调试。
四、12月30日下午5、6、7、8节，检查各小组进展情况。
五、12月31日上午各小组测试实验结果并演示。
六、1月1日各小组整理课程设计报告并打印。
七、1月2日下午5.6.7.8节，收课程设计报告并进行答辩。
四、实习地点
经计楼611（网络工程实验室）
五、分组情况
每1-2位同学完成一个题目。
实习指导教师： 陈卫
六、实习考核
学生完成设计内容以后交实验报告和电子文档：
实验报告内容包括：
1、封面
2、设计任务书
3、成绩评定表
4、目录
5、正文
电子文档包括以下内容：
1．源程序
2．可执行程序
3．课程设计论文电子版
七、注意事项
设计前应复习设计中所涉及的理论知识和算法，针对设计要求完成基本代码编写并完成预习报告、设计中认真调试所编代码并进行必要的测试、记录并分析设计结果，设计后认真书写符合规范格式的设计报告，并要求用正规的课程设计报告纸和封面装订整齐，按时上交。
八、附则（实践报告模板和实践学生名单附后）
《网络操作系统》
课程设计报告
题 目
姓 名 _______________ 学 号 ________________
同 组 者 _______________ 专 业
指导教师 成 绩
网络工程系
年 月 日
设计题目
论文题目应简明扼要，应避免过宽、过大、过空，应反映出研究的范围、层次和深度，一般不超过20个汉字。可以根据需要使用副标题，用以补充说明论文中的特定内容。论文题目要准确反映论文的实质性主题内容，所用词语应有助于选定关键词和索引，应避免使用生僻的缩略词、字符、代号等。格式要求：宋体小二号字，加粗，居中。
论文在打印时，四周应留足空白边缘，以便装订、复制和读者批注。每一页的上方（天头）和左侧（订口）应分别留边25mm，下方（地脚）和右侧（切口）应分别留边20mm；论文一律使用 A4（210 mm×297 mm）标准大小的白纸，双面打印并装订成册；
1 设计内容
①一级标题为“1”、“2”、“3” ……；
②二级标题为“1.1”、“2.1”、“3.1” ……；
③三级标题为“1.1.1”、“2.1.1”、“3.1.1” ……；
④四级标题为“1.1.1.1”、“2.1.1.1”、“3.1.1.1”……；
①一级标题：宋体四号字，加粗，左对齐。
②二级标题：宋体小四号字，加粗，左对齐。
③三级标题：宋体小四号字，左对齐。
④四级标题：宋体小四号字，左对齐。
2 设计目的与要求
3 设计环境或器材、原理与说明
4 设计过程（步骤）或程序代码（分人写）
5个人遇到的困难与获得的主要成果（分人写）
6 设计结果与分析
7 设计体会与建议
