操作系统专业课程设计题目与要求.doc

操作系统课程设计题目和要求
一、课程设计要求：
1．依据每道题人数选定题目。（假如自己有好想法能够和我联络，能够做其它题目）
2．分析设计要求，给出处理方案，建立必需数据结构，然后设计总体步骤（包含界面）、具体设计必需算法，并最终显示结果。基于WINDOWS或LINUX操作系统全部能够，用何种编程语言全部有能够。
3．提交设计汇报，包含设计要求、设计思想步骤、设计所包含关键数据结构、程序清单、运行结果、设计心得、参考资料等，时间在18周星期一（课程设计没补考，没及格到大四再做，期望大家认真对待）。
4．严禁剽窃，复制设计内容，查出后相关同学设计成绩以零分处理。
5．所提交源程序应是能够运行经过完整程序。
6．课程设计参考评分标准：
设计思想说明（10分）；数据结构说明（6分）；各模块算法步骤图（10分）；程序清单：注意加注释（包含关键字、方法、变量等），在每个模块前加注释；（共70分，其中书面源程序占35分，试验检验结果、程序运行情况占35分）体会，总结及体会提议（4分）。

二、设计题目
1． Windows多线程控制台程序（1人）
目标：学习和掌握怎样编写Windows多线程控制台程序。经过编写程序，加深对进程和线程关系了解，掌握多线程程序实施和编写技巧。
设计要求：写一个单进程多线程Windows控制台程序，该程序在一个进程内建立N个线程来实施指定任务。N由命令行传输给系统。
Win32控制台程序中，主函数格式如：
Void main(int argc,char *argv[])，能够获取命令行参数。
经过VC++“工程/设置”C/C++属性页设置应用程序为“MTD”多线程。
利用win32 API CreateThread()来生成线程。
2． 睡眠剪发师问题（2人）
目标：了解信号量机制，了解并掌握进程同时和互斥机制，熟悉信号量操作函数，利用信号量实现对共享资源控制。
设计要求：
（1）编写程序实现剪发师和用户进程同时。
问题描述：这是一个经典IPC问题，剪发店有一位剪发师，一把剪发椅和n把用来等候剪发椅子。假如没有用户，则剪发师在剪发椅上睡觉，用户理来时，如剪发师闲则剪发，不然如有空椅则坐等，没有空椅则离开，编写程序实现剪发师和用户程序，实现进程控制，要求不能出现竞争。
（2）将（1）题中问题修改为有两位剪发师，设计程序实现同时控制。
问题提醒：能够用一个变量waitting来统计等候剪发用户数，另使用三个信号量：用来统计等候剪发用户数customers；用来统计剪发师是否空闲信号量barbers，一个用于互斥访问waitting变量mutex.。
3． 进程调度模拟程序（2人）
目标：深入掌握进程调度概念原理和实现方法。
设计要求：编写一个进程调度程序，允很多个进程并行实施。
进程调度算法：采取最高优先数优先调度算法（即把处理机分配给优先数最高进程）、先来先服务算法、按时间片轮转调度算法，最终总结该算法优缺点，写出设计体会。
每个进程有一个进程控制块（PCB）表示，进程控制块能够包含以下信息：
进程名、优先数、抵达时间、需要运行时间、已用CPU时间、进程状态等等。
进程优先数及需要运行时间能够事先人为指定（也能够由随机数产生）。进程抵达时间为输入进程时间。进程运行时间以时间片为单位进行计算。每个进程状态能够是就绪W（wait）、运行R（run）或完成F（finish）三种状态之一。
4． 进程调度模拟程序2（1人）
目标：深入掌握进程调度概念原理和实现方法。
设计要求：编写一个进程调度程序，允很多个进程并行实施。
进程调度算法：采取最高优先数优先和按时间片轮转调度结合算法，最终总结该算法优缺点，写出设计体会。
假如运行下个时间片后，进程已占用CPU时间已达成所需要运行时间，则撤消该进程，假如运行一个时间片后进行已占用CPU时间还未达成所需要运行时间，也就是进程还需要继续运行，此时应将进程优先数减1(即降低一级)，然后把它插入就绪队列等候CPU。每进行一次调度程序全部打印一次运行进程、就绪队列、和各个进程PCB，方便进行检验。反复以上过程，直到全部进程全部完成为止。
5． 读者和写者问题（进程同时问题）（1人）
目标：了解进程同时概念，了解信号量机制原理，掌握利用信号量处理进程同时问题方法，进而学会利用进程同时和互斥。
设计要求：编程模拟读者和写者问题，要求显示结果。
问题描述：
（1）多个进程共享一个文件，其中只读文件称之为读者，其它只写文件称为写者。读者能够同时读，不过写者只能独立写。
（2）对（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． Windows磁盘直接读写试验（1人）
目标：了解磁盘设备编程特点。
设计要求：经过本试验了解在windows系统中怎样直接使用磁盘读写功效；所编应用程序能够响应用户指定读写磁盘扇区请求，也能提供查看磁盘相关参数功效。技术关键是使用了windows提供API（应用程序接口）来实现所要求功效。用户能够利用API进行底层磁盘操作。
相关知识：（下列函数具体使用方法参看VC++MSDN文档）
（1） CreateFile:用来创建或打开一个文件、管道、磁盘设备等，它返回一个句柄用于以后对这信对象访问。
（2） DeviceControl:本API直接向对应设备驱动程序发出指令，以完成在函数参数中所指定动作。
（3） WriteFile：本API用于向文件中写入数据，写入操作能够采取同时方法或异步方法，写入操作从文件指针处开始，写操作后会被对应调整。磁盘设备被看成文件看待。
（4） ReadFile:本API用于文件中读出数据，读出操作从文件指针处开始，文件指针在读操作后会被对应调整。使用方法同写文件函数相同。
（5） SetFilePointer:用于移动一个打开文件中读写指针。
9． 处理机调度（2人）
目标：加深作业概念了解，深入了解多道程序设计系统中怎样组织作业、管理作业和调度作业，加深对作业调度算法了解。
设计要求：采取短作业优先调度算法、先来先服务调度算法和最高响应比调度算法实现处理机对作业调度。
作业调度算法关键是在已经有作业后备队列上根据一定规则选择一个作业，怎样在已经有数据结构上进行操作问题。
10． 页面置换算法（2人）
目标：深入掌握内存调度算法概念原理和实现方法。
设计要求：编写程序实现：
（1） 优异先出页面置换算法（FIFO）
（2） 最近最久未使用页面置换算法（LRU）
（3） 最好置换页面置换算法（OPT）
专题：设计一个虚拟存放区和内存工作区，编程序演示以上三种算法具体实现过程，并计算访问命中率。演示页面置换三种算法。经过随机数产生一个指令序列，将指令序列转换成为页地址流。计算并输出多种算法在不一样内存容量下命中率。
11． 售票员和乘客（信号量操作）（1人）
目标：了解进程同时概念，了解信号量机制原理，掌握利用信号量处理进程同时问题方法，进而学会利用进程同时和互斥。
设计要求：编程序模拟车站售票厅内进程同时问题，售票厅任何时刻最多可容纳20名购票者进入，不然需要在外面等候。每个购票者可看成一个进程。
12． 生产者—消费者问题（2人）
目标：掌握信号使用方法和PV操作定义，掌握使用PV操作实现进程之间同时和互斥方法，加深对进程同时互斥概念了解。
设计要求：设计一程序，由一个进程创建三个子进程，三个子进程一个是生产者进程，两个是消费者进程，父子进程全部使用父进程创建共享存放区进行通信，由生产者进程将一个数组中十个数值发送到由5个缓冲区组成共享内存中，两个消费者进程轮番接收并输出这十个数值，同时将两个消费者进程读出数值进行累加求各和。
13． 驱动调度（2人）
目标：掌握驱动调度算法原理
设计要求：模拟电梯调度算法，实现对磁盘驱动调度。
要求模拟设计一个驱动调度程序，观察驱动程序动态运行过程。经过试验了解和掌握驱动调度职能。
经过输入一个0~1数来确定函数实施“接收请求”命令，还是实施“驱动调度”命令。同时能够依据自已需要确定是否继续实施。
调用数组对输入进程进行存放，并利用循环进行显示同时对I/O请求列表进行初始化。
利用电梯调度算法，对I/O列表中磁盘请求进行调度，同时对I/O列表进行排序，调度完成后显示新列表。
14． 银行家算法（1人）
目标：了解多道程序系统中，多个进程并发实施资源分配。
设计要求：管理员能够把一定数量作业供多个用户周转使用，为确保作业安全，管理员要求：当一个用户对作业最大需求量不超出管理员现有资金就要接纳该用户；用户能够分期贷款，但贷款总数不能超出最大需求量；当管理员现有作业不能满足用户所需数时，对用户请求能够推迟支付，但总能使用户在有限时间里得到请求。当用户得到所需全部作业后，一定能在有限时间里归还全部作业。
15． 交通信号灯模拟（2人）
目标：了解信号量机制，了解并掌握进程同时和互斥机制，熟悉信号量操作函数，利用信号量实现对共享资源控制。
设计要求：编程模拟交通信号灯控制。
问题描述：一个十字路口，共有四组红绿灯，每个路口车辆全部遵照“红灯停，绿灯行”标准，假设将每一台汽车全部作为一个进程，请设计良好机制，展示出合理“十字路口交通管理”情况。
车辆通行设定：路口宽度不限，对一个路口而言，只有当一辆车经过路口（越过对面路口交通灯后），其后续车辆才能继续经过交通灯，车辆经过路口时间能够固定，能够自行计算。
进程互斥：交通灯进程实际上是互斥，即不能同时为红或同时为绿。
进程消息通信或其通信方法：对车辆进程而言，每一个车辆在经过路口前，必需确定前面车辆已经经过了路口。
进程调度：停留在一个路口车辆，决定其前进或等候原因是交通灯和前面车辆状态，需要设计一个良好进程调度机制来控制全部车辆通行。
16． 哲学家进餐问题（1人）
目标：经过实现哲学家进餐问题互步，深入了解和掌握进程互斥原理。
设计要求：哲学家有N个，要求全体到齐后开始讨论，在讨论间隙哲学家进餐，每人进餐时全部需使用刀、叉合一把，全部哲学家刀和叉全部拿到后才能进餐。哲学家人数、餐桌上部署自行设定，实现刀和叉互斥使用算法程序实现。
17． 司机和售票员（信号量操作）（1人）
目标：掌握信号使用方法和PV操作定义，掌握使用PV操作实现进程之间同时和互斥方法，加深对进程同时互斥概念了解。
设计要求：设计程序模拟在公共汽车上，司机和售票员操作同时。司机：开启车辆，正常行车，到站停车。售票员：上乘客，关车门，售票，开车门，下乘客。用PV操作对其控制。
18． 磁盘调度算法（2人）
目标：了解磁盘管理原理，掌握磁盘调度种算法。
设计要求：编程序实现下述磁盘调度算法，并求出每种算法平均寻道长度：要求设计主界面能够灵活选择算法，且以下算法全部要实现。
（1） 先来先服务算法（FCFS）
（2） 最短寻道时间优先算法（SSTF）
（3） 扫描算法（SCAN）
（4） 循环扫描算法（CSCAN）
19． 收银员和用户问题（信号量操作）（1人）
目标：了解信号量机制，了解并掌握进程同时和互斥机制，熟悉信号量操作函数，利用信号量实现对共享资源控制。
设计要求：编程模拟下面同时问题：在某超市有下收银员，且同时最多许可有n个用户购物，我们能够将用户和收银员看成是两类不一样进程，且工作步骤以下图所表示。为了利用PV操作正确地协调这两类进程之间工作，设置了三个信号量S1、S2和Sn，且初值分别为0、0、和n。
20． 信号量操作2（1人）
目标：了解信号量机制，了解并掌握进程同时和互斥机制，熟悉信号量操作函数，利用信号量实现对共享资源控制。
设计要求：经过对windows系统内核同时对象mutexes和semaphores使用来实现进程同时控制。利用CreateSemaphore、WaitForSingleObject等函数检测内核同时对象状态。
21． 男女生洗澡问题（信号量操作）（1人）
目标：了解信号量机制，了解并掌握进程同时和互斥机制，熟悉信号量操作函数，利用信号量实现对共享资源控制。
设计要求：编程模拟男女生洗澡问题。
问题描述：假设某宿舍楼有一共用浴室，学校颁布要求：当有一个女生正在使用浴室，则其它女生能够进入，不过男生不行，反之亦然。在每个浴室门上有一个滑动指示符号，表示目前处于以下三种可能状态之一：
（1） 空 (2)有女生 （3）有男生
选择一个程序设计语言编写下面过程：
woman_wants_to_enter,man_wants_to_enter,woman_leaves,man_leaves。
22． 进程间通信（2人）
目标：了解进程间通信机制，实现进程两种通信方法，数次实施，观察结果，并对两种通信方法进行比较。
设计要求：利用系统提供通信系统调用，进行一个方法进程通信程序设计，并对结果进行分析，同时了解另一个通信方法，将两种方法进行比较分析。
（1） 消息创建发送和接收
使用系统调用msgget()、msgsnd()、msgrev()、msgctl()来编写长度为500字节发送和接收程序。用一个程序前后创建两个子进程server和client，进行消息队列方法通信。由server建立消息队列，等候其它进程发来消息，当碰到类型为1消息，则作为通信结束信号，取消消息队列，退出。Server每接收到一个消息显示在屏幕上。
Client判定一个数据中整数是否为素数，然后使用server建立消息队列，将某数是否为素数消息依次发送给server,然后退出。Client每次发送时把消息显示在屏幕上。
（2） 共享存放区创建，附接和断接
使用系统调用shmget(),shmat(),shmctl()编写一个和上面(1)中相同功效程序。
23． 虚拟文件系统实现（3人）
目标：过一个简单多用户文件系统设计，加深文件系统内部功效和内部实现。
设计要求：
在Windows或Linux下设计一个二级（或树型）结构文件系统，要求最少实现以下功效：
login 用户登录
dir 列出文件目录
create 创建文件
del 删除文件
open 打开文件
close 关闭文件
read 读文件
write 写文件
cd 进入子目录
rd 删除子目录
md 创建子目录
设计提醒：实现虚拟文件系统通常思绪是调用系统文件创建（如c中fopen函数w方法即可）一个新文件，将此文件作为虚拟磁盘，在完成本设计要求内容时，要求所生成文件目录和文件等内容全部是存放在此磁盘中。
24． 分时系统实现（2人）
目标： 了解计算机系统开启过程，实模式和保护模式区分，进程管理功效具体实现。
设计要求：
  （1）制作计算机开启盘。
  （2）实现由实模式进入到保护模式。
（3） 静态建立多个进程，采取时间片轮转调度策略调度进程实施。
25． 苹果问题（2人）
目标：了解信号量机制，了解并掌握进程同时和互斥机制，熟悉信号量操作函数，利用信号量实现对共享资源控制。
设计要求：编程模拟实现这一问题程序控制，分析处理过程，
问题描述：桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。父亲专向盘子放苹果（apple），母亲专向盘子中放桔子（orange）；两个儿子专等吃盘子中桔子，两个女儿专等吃盘子中苹果。请用P、V操作来实现父亲、母亲、儿子、女儿之间同时和互斥关系。

参考书目：
《操作系统试验教程》，张丽芬、刘利雄、王全玉等，清华大学出版社。
《操作系统原理和实践教程》周湘贞、曾宪权编，清华大学出版社。
《Windows操作系统关键编程试验教程》，宋晓宇，中国铁道出版社。