《操作系统课程设计》指导书
课程设计要求：
1、 根据每道题目的人数要求指定题目，要求每两名同学之间课程设计内容应该不同。如果有选择相同题目的小组，则设计方案不同，否则视为操袭。
2、 分析设计要求，给出解决方案，建立必要的数据结构，然后设计总体流程
（包括界面）、详细设计必要的算法，并最终显示出结果。 基于Windows 或 Linux操作系统都可以,用何种编程语言都可以。
3、 提交设计报告,包括设计要求、设计思想及流程、设计所涉及的主要数据结构、程序清单、运行结果、设计心得、参考资料等。
4、 最终成绩决定因素＝设计质量（40）＋设计报告（30）＋答辩（30）
5、 时间安排：16周——确定题目，查找资料，上机编程；20周——上机编程调试，验收答辩,提交课程序设计报告书。
6、 设计报告内容与他人相同者无成绩。
课程设计题目：
1． Windows多线程控制台程序（1人）
目的：学习和掌握如何编写Windows多线程控制台程序。通过编写程序，加深对进程和线程关系的理解，掌握多线程程序的执行和编写技巧。
内容要求：写一个单进程多线程的Windows控制台程序，该程序在一个进程内建立N个线程来执行指定的任务。N由命令行传递给系统。 Win32控制台应程序中，主函数的格式如：
void main(int argc,char* artv[])，可以获取命令行参数。
通过VC++“工程／设置”的C／C++属性页设置应用程序为“MTD”多线程。
利用Win32 API CreateThread()来生成线程。
参考书：《操作系统原理与实践教程》周湘贞 曾宪权编 清华出版社 2． 睡眠理发师问题（2人）
实验目的：了解信号量机制，了解并掌握进行同步和机制，熟悉信号量的操作函
数，利用信号量实现对共享资源的控制。
设计要求：
1．编写程序实现理发师与顾客进程的同步。
问题描述：这是另一种经典的IPC问题，理发店有一位理发师，一把理发椅和n把用来等候理发的椅子。如果没有顾客，则更好师便在理发椅上睡觉，顾客到来时，如理发师闲则理发，否则如有空等候椅则坐等，没有空椅则离开，编写程序实现理发师和顾客程序，实现进程控制，要求不能出现竞争。
2．将1题中问题修改为有两位理发师，设计程序实现同步控制。
问题提示：可以用一个变量waiting来记录等候理发的顾客数，另使用三个信号量：用来记录等候理发的顾客数customers；用来记录理发师是否空闲的信息号量barbers，一个用于互斥访问waiting变量的mutex。
3． 进程调度模拟程序（2人）
实验目的：深入掌握进行调度的概念原理和实同方法。
设计要求：编写一个进程调度程序，允许多个进程并行执行。
进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）、先来先服务算法、按时间片轮转调度算法，最终总结该算法的优缺点，写出设计体会。
每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。
进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为输入进程的时间。
进程的运行时间以时间片为单位进行计算。
每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。
4． 进程调度模拟程序2（1人）
实验目的：深入掌握进程调度的概念原理和实现方法。
设计要求：编写一个进程调度程序，允许多个进程并行执行。
进程调度算法：采用最高优先数与按时间片轮转调度结合算法，最终总结该算法的优缺点，写出设计体会。
就绪进程获得CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。
如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。
每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。
重复以上过程，直到所要进程都完成为止。
5． 读者与写者问题（进程同步问题）（1人）
实验目的：了解进程同步的概念，理解信号量机制的原理，掌握运用信号量解决进程同步问题的方法，进而学会运用进程的同步与互斥 。
设计要求：编程模拟教材中讨论的读者与写者问题，要求能显示结果。
6． 模拟文件管理系统（3人）
实验目的：深入了解文件管理系统，初步掌握文件管理系统的实现方法。 设计要求：编写一程序，模拟一个简单的文件管理系统。树型结构，目录下可以是目录，也可以是文件。
在此文件管理系统，可实现的操作有：
改变目录：格式：cd <目录名>
显示目录：格式：dir [<目录名>]
创建目录：格式：md <目录名>
删除目录：格式：rd <目录名>
新建文件：格式：edit <文件名>
删除文件：格式：del <文件名>
退出文件系统：exit
实现参考：
1．文件系统采用二叉树型存储结构，结点结构如下：
struct FileNode
{
char filename[FILENAME_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退出为止。
7． 内存的申请与释放(2人)
实验目的：了解操作系统内存分配的算法。
实验要求：1、定义一个自由存储块链表，按块地址排序，表中记录块的大小。当请求分配内存时，扫描自由存储块链表，直到找到一个足够大的可供分配的内存块，若找到的块大小正好等于所请求的大小时，就把这一块从自由链表中取下来，返回给申请者。若找到的块太大，即对其分割，并从该块的高地址部分往低地址部分分割，取出大小合适的块返回给申请者，余下的低地址部分留在链表中。若找不到足够大的块，就从操作系统中请求另外一块足够大的内存区域，并把它链接到自由块链表中，然后再继续搜索。
释放存储块也要搜索自由链表，目的是找到适当的位置将要释放的块插进去，如果被释放的块的任何一边与链表中的某一块临接，即对其进行合并操作，直到没有合并的临接块为止，这样可以防止存储空间变得过于零碎。
2、空闲区采用分区说明表的方式实现1中的功能。要求同上。
8． Window磁盘直接读写实验（1人）
实验目的：了解磁盘设备编程的特点。
实验要求：通过本实验了解在Windows系统中如何直接使用磁盘的读写功能；所编应用程序能够响应用户指定的读写磁盘扇区的请求，也能提供查看磁盘相关参数的功能。技术的关键是使用了Windows提供的API（应用程序接口）来实现所要求的功能。用户可以利用API进行底层的磁盘操作。
相关知识：（下列函数的详细使用方法参看VC++的MSDN文档）
1、 CreateFile：用来创建或者打开一个文件、管道、磁盘设备等，它返回一个
句柄用于以后对这个对象的访问。
2、 DeviceIoControl：本API直接向相应设备的驱动程序发出指令，以完成在
函数参数中所指定的动作。
3、 WriteFile：本API用于向文件中写入数据，写入操作可以采用同步方式或
者异步方式，写入操作从文件指针处开始，写操作后会被相应调整。磁盘设备被当作文件看待。
4、 ReadFile：本API用于从文件中读出数据，读出操作从文件指针处开始，
文件指针在读操作后会被相应调整。用法同写文件函数相似。
5、 SetFilePointer：用于移动一个打开的文件中的读写指针。
9． 处理机调度（2人）
实验目的：加深作业概念的理解，深入了解多道程序设计系统中如何组织作业、管理作业和调度作业，加深对作业调度算法的理解。
实验要求：采用短作业优先调度算法、先来先服务调度算法和最高响应比调度算法实现处理机对作业的调度。
作业调度算法的关键是在已有的作业后备队列上按照一定的规则选择一个作业，如何在已有的数据结构上进行操作的问题。
10． 页面置换算法（2人）
实验目的：深入掌握内存调度算法的概念原理和实现方法。
设计要求：编写程序实现：1）先进先出页面置换算法（FIFO）
2）最近最久未使用页面置换算法（LRU）
3）最佳置换页面置换算法（OPT）
专题：设计一个虚拟存储区和内存工作区,编程序演示以上三种算法的具体实 现过程,并计算访问命中率。
演示页面置换的三种算法。
通过随机数产生一个指令序列，
将指令序列转换成为页地址流。
计算并输出各种算法在不同内存容量下的命中率。
11． 售票员与乘客（信号量操作）（1人）
实验目的： 了解进程同步的概念，理解信号量机制的原理，掌握运用信号量解决进程同步问题的方法，进而学会运用进程的同步与互斥 。
设计要求：编程序模拟车站售票厅内进程同步问题，售票厅任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，厅外的购票者可立即进入，否则需要在外面等待。每个购票者可看成一个进程。
12． 生产者—消费者问题（2人）
实验目的：掌握信号的使用方法和PV操作的定义，掌握使用PV操作实现进行之间同步和互斥的方法，加深对进行同步互斥概念的理解。
设计要求：设计一个程序，由一个父进程创建三个子进程，三个子进程一个是生产者进程，两个是消费者进行，父子进程都使用父进程创建的共享存储区进
行通信，由生产者进程将一个数组中的十个数值发送到由5个缓冲区组成的共享内存中，两个消费者进程轮流接收并输出这十个数值，同时将两个消费者进程读出的数值进行累加求和。
13． 驱动调度（1人）
实验目的：掌握驱动调度算法的原理
设计要求：模拟电梯调度算法，实现对磁盘的驱动调度。
要求模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。通过实验理解和掌握驱动调度的职能。
通过输入一个0～1的数来确定函数执行“接受请求”命令，还是执行“驱动调度”命令。同时可以根据自己需要确定是否继续执行。
调用数组对输入的进程进行存储，并运用循环进行显示同时对I/O请求列表进行初始化。
运用电梯调度算法，对I/O列表中的磁盘请求进行调度，同时对I/O列表进行排序，调度完成后显示新的列表
14． 银行家算法（1人）
实验目的：了解多道程序系统中，多个进程并发执行的资源分配。
管理员可以把一定数量的作业供多个用户周转使用，为保证作业的安全管理员规定：
当一个用户对作业的最大需求量不超过管理员现有的资金就要接纳该用户； 用户可以分期贷款,但贷款的总数不能超过最大需求量；
当管理员现有的作业不能满足用户的沿需数时,对用户的请求可推迟支付,但总能使用户在有限的时间里得到请求；
当用户得到所需的全部作业后,一定能在有限的时间里归还所有的作业。
15． 交通信号灯模拟（2人）
一个十字路口,共有四组红绿灯,每个路口的车辆都遵循"红灯停,绿灯行"的原则,假设将每一台汽车都作为一个进程,请设计良好的机制,展示出合理的"十字路口交通管理"情况.
车辆通行设定:路口宽度不限,对一个路口而言,只有当一辆车通过路口(越过对面路口的交通灯后)后,其后续车辆才能继续通过交通灯,车辆通过路口的时间可以固定,可以自行计算。
进程的互斥:交通灯进程实际上是互斥的,即不能同时为红或者同时为绿. 进程的消息通信或其他通信方式:对车辆进程而言,每一个车辆在通过路口前,必须确认前面的车辆已经通过了路口.
进程的调度:停留在一个路口的车辆,决定其前进或等候的因素是交通灯和前面车辆的状态,需要设计一个良好的进程调度机制来控制所有车辆的通行。
16． 哲学家进餐问题（1人）
实验目的：通过实现哲学家进餐问题的同步深入了解和掌握进程同步和互斥的原理。
设计要求：哲学家有N个,也定全体到齐后开始讨论:在讨论的间隙哲学家进餐,每人进餐时都需使用刀、叉各一把，所有哲学家刀和叉都拿到后才能进餐。哲学家的人数、餐桌上的布置自行设定，实现刀和叉的互斥使用算法的程序实现。 司机与售票员（信号量操作）（1人）
实验目的：掌握信号的使用方法和PV操作的定义，掌握使用PV操作实现进行之间同步和互斥的方法，加深对进行同步互斥概念的理解。
设计要求：设计程序模拟在公共汽车上，司机和售票员操作的同步。 司机：启动车辆，正常行车，到站停车。售票员：上乘客，关车门，售票，开车门，下乘客。
用PV操作对其控制。
17． 磁盘调度算法（2人）
设计要求：编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度： 要求设计主界面可以灵活选择某算法，且以下算法都要实现
1、先来先服务算法（FCFS）
2、最短寻道时间优先算法（SSTF）
3、扫描算法（SCAN）
4、循环扫描算法（CSCAN）
18． 收银员与顾客问题（信号量操作） （1人）
实验目的：了解信号量机制，了解并掌握进行同步和机制，熟悉信号量的操作函数，利用信号量实现对共享资源的控制。
实验要求：编程模拟下面同步问题：在某超市里有一个收银员，且同时最多允许有n个顾客购物，我们可以将顾客和收银员看成是两类不同的进程，且工作流程如下图所示。为了利用PV操作正确地协调这两类进程之间的工作，设置了三个信号量S1、S2和Sn，且初值分别为0、0和n。
19． 信号量的操作2（1人）
实验目的：了解信号量机制，了解并掌握进行同步和机制，熟悉信号量的操作函数，利用信号量实现对共享资源的控制。
实验要求：通过对Windows系统的内核同步对象Mutexes和Semaphores的使用来实现进程同步的控制。利用CreateSemaphore、 WaitForSingleObject等函数检测内核同步对象的状态。
假设某宿舍楼有一共用浴室，学校颁布法令：当有一个女生正在使用浴室，则其他女生可以进入，但是男生不行，反之亦然。在每个浴室门上有一个滑动指示符号，表示当前处于以下三种可能状态之一：
1. 空
2. 有女生
3. 有男生
选用一种程序设计语言编写下面的过程：woman_wants_to_enter,
man_wants_to_enter, woman_leaves, man_leaves.
20． 进程间通信（2人）
实验目的：了解进程间通信的机制，实现进程的两种通信方式,多次执行，观察结果，并对两种通信方式进行比较。
实验要求：利用系统提供的通信系统调用,进行一种方式的进程通信的程序设计,并对结果进行分析,同时了解另一种通信方式,将两种方式进行比较分析.
1. 消息的创建发送和接收
使用系统调用msgget()，msgsnd()，msgrev()， msgctl()来编写长度为500字节的发送和接收程序。
用一个程序先后创建两个子进程,SERVER 和CLIENT,进行消息队列方式通信.
由SERVER建立消息队列,等待其他进行发来消息,当遇到类型为1的消息,则作为通信结束的信号,取消消息队列,退出。SERVER分接收到一个消息显示在屏幕上。
CLIENT判断一个数据中的整数是否为素数，然后使用SERVER建立的消息队列，将某数是否为素数的消息依次发送给SERVER，然后退出。CLIENT每次发送时把消息显示在屏幕上。
2．共享存储区的创建，附接和断接
使用系统调用shmget(), sgmat(),shmctl()编写一个与上面1中相同功能的程序。
参考书目：《操作系统实验教程》，张丽芬、刘利雄、王全玉等，清华大学出版社