操作系统课程设计题目和要求.doc
《操作系统课程设计题目和要求.doc》由会员分享,可在线阅读,更多相关《操作系统课程设计题目和要求.doc(51页珍藏版)》请在冰点文库上搜索。
操作系统原理课程设计
适用专业:
计算机科学与技术专业
课程设计时间:
1周
一、课程设计目的
通过课程设计,加深学生对教材中的重要算法的理解,同时通过用C语言编程实现这些算法,并在LINUX或windows平台上实现,让学生更好地掌握操作系统的原理及实现方法,提高学生综合运用各专业课知识的能力。
二、课程设计内容
以下设计课题任选一个即可:
课题一:
为LINUX设计一个简单的二级文件系统。
要求做到以下几点:
1、可以实现下列几条命令(至少4条)。
Login用户登录
Dir列文件目录
Create创建文件
Delete删除文件
Open打开文件
Close关闭文件
Read读文件
Write写文件
2、列目录时要列出文件名、物理地址、保护码和文件长度。
3、源文件可以进行读写保护。
课题二:
设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率:
1、先进先出的算法(FIFO)
2、最近最少使用算法(LRU)
3、最佳淘汰算法(LFU)
4、最少访问页面算法(NUR)
5、最近最不经常使用算法(NUR)
课题三:
编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度:
1、先来先服务算法(FCFS)
2、最短寻道时间优先算法(SSTF)
3、扫描算法(SCAN)
4、循环扫描算法(CSCAN)
课题四:
编程序模拟银行家算法,要求能体现算法的全过程。
课题五:
编程序模拟至少三种进程调度算法,要求能体现算法的全过程。
课题六:
内存管理:
使用Windows2000/XP的API函数,编写一个包含两个线程的进程,一个线程用于模拟内存分配活动,一个线程用于跟踪第一个线程的内存行为,而且要求两个线程之间通过信号量实现同步。
模拟内存活动的线程可以从一个文件中读出要进行的内存操作,每个内存操作包括如下内容:
时间:
操作等待时间。
块数:
分配内存的粒度。
操作:
包括保留(reserve)一个区域、提交(commit)一个区域、释放(release)一个区域、回收(decommit)一个区域和加锁(lock)与解锁(unlock)一个区域,可以将这些操作编号存放于文件。
保留是指保留进程的虚拟地址空间,而不分配物理存储空间。
提交在内存中分配物理存储空间。
回收是指释放物理内存空间,但在虚拟地址空间仍然保留,它与提交相对应,即可以回收已经提交的内存块。
释放是指将物理存储和虚拟地址空间全部释放,它与保留(reserve)相对应,即可以释放已经保留的内存块。
大小:
块的大小。
访问权限:
共五种,分别为PAGE_READONLY,PAGE_READWRITE,PAGE_EXECUTE,PAGE_EXECUTE_READ和PAGEEXETUTE_READWRITE。
可以将这些权限编号存放于文件中跟踪线程将页面大小、已使用的地址范围、物理内存总量,以及虚拟内存总量等信息显示出来。
三、课程设计考核方式
课程设计成绩评定的依据有设计文档资料、具体实现设计方案的程序及课程设计考勤登记表,其中平时成绩占总成绩的20%。
优:
有完整的符合标准的文档,文档有条理、文笔通顺,格式正确,其中有总体设计思想的论述;程序完全实现设计方案,设计方案先进,软件可靠性好;
良:
有完整的符合标准的文档,文档有条理、文笔通顺,格式正确;有完全实现设计方案的软件,设计方案较先进;
中:
有完整的符合标准的文档,有基本实现设计方案的软件,设计方案正确;
及格:
有完整的符合标准的文档,有基本实现设计方案的软件,设计方案基本正确;
不及格:
没有完整的符合标准的文档,软件没有基本实现设计方案,设计方案不正确。
提交的电子文档和软件必须是由学生自己独立完成,雷同者教师有权视其情况扣分或记零分。
四、提交的资料
1、文档
有关的分析设计文档要求使用计算机打印在学校统一制定的课程设计纸上,同时提交电子文档。
2、软件
软件需提供加注释的源程序(交软盘),并能正常运行。
注:
对于分析设计中未能实现的部分需要加以说明。
对于软件中所参考的部分模块或代码需要加以声明,并说明出处。
五、课程设计任务
课题一主要需完成以下子过程。
为LINUX设计一个简单的二级文件系统。
要求做到以下几点:
1、可以实现下列几条命令(至少4条)
Login
用户登录
Dir
列文件目录
Create
创建文件
Delete
删除文件
Open
打开文件
Close
关闭文件
Read
读文件
Write
写文件
2、列目录时要列出文件名、物理地址、保护码和文件长度
3、源文件可以进行读写保护
实验准备
1、首先应确定文件系统的数据结构:
主目录、子目录及活动文件等。
主目录和子目录都以文件的形式存放于磁盘,这样便于查找和修改;
2、用户创建的文件,可以编号存储于磁盘上。
如file0,file1,file2……并以编号作为物理地址,在目录中进行登记。
实验指导
一、文件管理
要将文件存储在磁盘(带)上,必须为之分配相应的存储空间,这就涉及到对文件存储空间的管理;采取何种方式存储,又涉及到文件的物理结构;为了简化对文件的访问和共享,还应设置相应的用户文件描述表及文件表。
1、文件存储空间的管理
(1)文件卷的组织
UNIX中,把每个磁盘(带)看作是一个文件卷,每个文件卷上可存放一个具有独立目录结构的文件系统。
一个文件卷包含许多物理块,并按块号排列如下图:
0#1#2#3#……K#K+1#……N#
其中,0#块用于系统引导或空闲,1#为超级块(superblock),存放文件卷的资源管理信息,如整个文件卷的盘块数、磁盘索引结点的盘块数、空闲盘块号栈及指针等。
2#~K#存放磁盘索引结点。
每个索引结点64B,第K+1#~N#存放文件数据。
(2)空闲盘块的组织
UNIX采用成组链接法组织空闲盘块。
它将若干个空闲盘块划归一个组,将每组中所有盘块号存放在其前一组的第一个空闲盘块中,而第一组中所有空闲盘块号放入超级块的空闲盘块号栈中。
例:
超级块表
109
106
103
100
95
211
208
205
202
310
307
304
301
(3)空闲盘块的分配与回收
内核要从文件系统中分配一盘块时,先检查超级块空闲盘块号栈是否已上锁。
是则调用sleep睡眠,否则将超级块中空闲盘块栈栈顶盘块号分配出去。
回收时,若空闲盘块号栈未满,直接将回收盘块编号记入空闲盘块号栈中。
若回收时栈已满,须先将栈中的所有空闲盘块号复制到新回收的盘块中,再将新回收盘块的编号作为新栈的栈底块号进栈。
2、文件的物理结构
UNIX未采用传统的三种文件结构形式,而是将文件所占用盘块的盘块号,直接或间接地存放在该文件索引结点的地址项中。
查找文件时,只需找到该文件的索引结点,便可直接或间接的寻址方式获得指定文件的盘块。
过程bmap可将逻辑文件的字节偏移量转换为文件的物理块号。
先将字节偏移量转换为文件逻辑块号及块内偏移量,再把逻辑块号转换为文件的物理块号。
3、用户文件描述符表和文件表的管理
每个进程的U区中设置一张用户文件描述符表。
只在首次打开文件时才需给出路径名。
内核在该进程的用户文件描述符表中,分配一空项,取其在该表中的位移量作为文件描述符fd(filediscriptor)返还给用户。
当用户再次访问该文件时,只需提供fd,系统根据fd便可找到相应文件的内存索引结点。
fd表项的分配由ufalloc完成。
为了方便用户对文件进行读/写及共享,系统中设置了一张文件表。
每个用户在打开文件时,都要在文件表中获得一表项,其中包含下述内容:
f.flag:
文件标志,指示该文件打开是为了读或写;
f.inode:
指向打开文件的内存索引结点指针;
f.offset:
文件读写指针偏移值;
f.count:
文件引用计数。
二、目录管理
UNIX中,为了加速对文件目录的查找,将文件名和文件说明分开,由文件说明形成一个称为索引结点的数据结构,而相应的文件目录项则只由文件符号名和指向索引结点的指针构成。
对目录的管理应包括的功能有:
1、对索引结点的管理
每个文件都有一唯一的磁盘索引结点(di_node)。
文件被打开后,还有一个内存索引结点(i_node)。
创建一新文件时,就为之建立一个磁盘索引结点,以将文件的有关信息记入其中,并将用户提供的文件名和磁盘索引结点号一并组成一个新目录项,记入其父目录文件中。
文件被撤消时,系统要回收该文件的磁盘索引结点,从其父目录中删除该目录项。
随着文件的打开与关闭,系统还要为之分配和回收内存索引结点。
(1)磁盘索引结点
磁盘索引结点中,包含有关文件的下述一系列信息:
文件模式di_mode。
可以是正规文件、目录文件、字符特别文件、块特别文件和管道文件等几种;
文件所有者用户标识符di_uid。
指拥有该文件的用户标识符;
同组用户标识符di_gid。
与拥有该文件的用户在同一小组的用户标识符;
文件长度di_size。
以字节计数的文件大小;
文件的联接计数di_nlink。
表明在本文件系统中所有指向该文件的文件名计数;
文件的物理地址di_addr。
di_addr地址项共有13项,即di_addr(0)到di_addr(12),每个地址项占3字节;
文件的访问时间di_atime。
指文件最近被进程访问的时间;
文件的修改时间di_mtime。
指文件和索引结点最近被进程修改的时间;
文件的建立时间di_citime。
(2)内存索引结点
文件被打开后,系统为它在内存索引结点表区中建一内存索引结点,以方便用户和系统对文件的访问。
其中,一部分信息是直接从磁盘索引结点拷贝过来的,如i_mode、i_uid、i_gid、i_size、i_addr、i_nlink等,并又增加了如下各信息:
索引结点编号i_number。
作为内存索引结点的标识符;
状态i_flag。
指示内存索引结点是否已上锁、是否有进程等待此i结点解锁、i结点是否被修改、是否有最近被访问等标志;
引用计数i_count。
记录当前有几个进程正在访问此i结点,每当有进程访问此i结点时,对i_count+1,退出-1;
设备号i_dev。
文件所属文S件系统的逻辑设备号;
前向指针i_forw。
Hash队列的前向指针;
后向指针i_back。
Hash队列的后向指针;
(3)磁盘索引结点的分配与回收
分配过程ialloc:
当内核创建一新文件时,要为之分配一空闲磁盘i结点。
如分配成功,便再分配一内存i结点。
其过程如下:
检查超级块上锁否。
由于超级块是临界资源,诸进程必须互斥地访问它,故在进入ialloc后,要先检查它是否已上锁,若是则睡眠等待;
检查i结点栈空否。
若i结点栈中已无空闲结点编号,则应从盘中再调入一批i结点号进栈。
若盘中已无空闲i结点,则出错处理,返回;
从空闲i结点编号栈中分配一i结点,并对它初始化、填写有关文件的属性;
分配内存i结点;
将磁盘i结点总数-1,置超级块修改标志,返回。
回收过程ifree:
当删除文件时,应回收其所占用的盘块及相应的磁盘i结点。
具体有:
检查超级块上锁否。
若是,直接返回,即不把本次回收的i结点号记入空闲i结点编号栈中;
检查i结点编号栈满否。
若已满,无法再装入新回收的i结点号,立即返回,若未满,便将回收的i结点编号进栈,并使当前空闲结点数+1;
置超级块修改标志,返回。
(4)内存索引结点的分配与回收
分配过程iget:
虽然iget用在打开文件时为之分配i结点,但由于允许文件被共享,因此,如果一文件已被其他用户打开并有了内存i结点,则此时只需将i结点中的引用计数+1。
如果文件尚未被任何用户(进程)打开,则由iget过程为该文件分配一内存i结点,并调用bread过程将其磁盘i结点的内容拷贝到内存i结点中并进行初始化。
回收过程iput:
进程要关闭某文件时,须调用iput过程,先对该文件内存i结点中的引用计数-1。
若结果为0,便回收该内存i结点,再对该文件的磁盘i结点中的连接计数减1,若其结果也为0,便删除此文件,并回收分配给该文件的盘块和磁盘i结点。
2、构造目录make_node
文件系统的一个基本功能是实现按名存取,它通过文件目录来实现。
为此须使每一个文件都在文件目录中有一个目录项,通过查找文件目录可找到该文件的目录项和它的索引结点,进而找到文件的物理位置。
对于可供多个用户共享的文件,则可能有多个目录项。
如果要将文件删除,其目录项也应删除。
构造目录先调用ialloc为新建文件分配一磁盘i结点及内存i结点。
若分配失败则返回,分配成功时须先设置内存i结点的初值(含拷贝),调用写目录过程wdir,将用户提供的文件名与分配给该文件的磁盘i结点号一起,构成一新目录项,再将它记入其父目录文件中。
3、检索目录namei
用户在第一次访问某文件时,需要使用文件的路径名,系统按路径名去检索文件目录,得到该文件的磁盘索引结点,且返回给用户一个fd。
以后用户便可利用该fd来访问文件,这时系统不需再去检索文件目录。
namei根据用户给出的路径名,从高层到低层顺序地查找各级目录,寻找指定文件的索引结点号。
检索时,对以'/'开头的路径名,须从根目录开始检索,否则,从当前目录开始,并把与之对应的i结点作为工作索引结点,然后用文件路径名中的第一分量名与根或与当前目录文件中的各目录项的文件名,逐一进行比较。
由于一个目录文件可能占用多个盘块,在检索完一个盘块中所有目录项而未找到匹配的文件分量名时,须调用bmap和bread过程,将下一个盘块中的所有目录项读出后,再逐一检索。
若检索完该目录文件的所有盘块而仍未找到,才认为无此文件分量名。
检索方式采用Hash方法。
三、主要文件操作的处理过程
1、打开文件open
检索目录。
内核调用namei从根目录或从当前目录,沿目录树查找指定的索引结点。
若未找到或该文件不允许存取,则出错处理返回NULL,否则转入下一步;
分配内存索引结点。
如果该文件已被其它用户打开,只需对上一步中所找到的i结点引用计数+1,否则应为被打开文件分配一内存i结点,并调用磁盘读过程将磁盘i结点的内容拷贝到内存i结点中,并设置i.count=1;
分配文件表项。
为已打开的文件分配一文件表项,使表项中的f.inode指向内存索引结点;
分配用户文件描述表项。
2、创建文件creat
核心调用namei,从根目录或当前目录开始,逐级向下查找指定的索引结点。
此时有以下二种情况:
重写文件。
namei找到了指定i结点,调用free释放原有文件的磁盘块。
此时内核忽略用户指定的许可权方式和所有者,而保持原有文件的存取权限方式和文件主。
最后打开。
新建。
namei未找到。
调用ialloc,为新创建的文件分配一磁盘索引结点,并将新文件名及所分配到的i结点编号,写入其父目录中,建立一新目录项。
利用与open相同的方式,把新文件打开。
3、关闭文件close
根据用户文件描述符fd,从相应的用户文件描述符表项中,获得指向文件表项的指针fp,再对该文件表项中的f.count-1。
四、主要数据结构
1、i节点
structinode
{structinode*i_forw;
structinode*i_back;
chari_flag;
unsignedinti_ino;/*磁盘i节点标号*/
unsignedinti_count;/*引用计数*/
unsignedshortdi_number;/*关联文件数,当为0时,则删除该文件*/
unsignedshortdi_mode;/*存取权限*/
unsignedshortdi_uid;/*磁盘i节点用户id*/
unsignedshortdi_gid;/*磁盘i节点组id*/
unsignedintdi_addr[NADDR];/*物理块号*/
2、磁盘i节点
structdinode
{unsignedshortdi_number;/*关联文件数*/
unsignedshortdi_mode;/*存取权限*/
unsignedshortdi_uid
unsignedshortdi_gid;
unsignedlongdi_size;/*文件大小*/
unsignedintdi_addr[NADDR];/*物理块号*/
}
3、目录项结构
structdirect
{chard_name[DIRSIZ];/*目录名*/
unsignedintd_ino;/*目录号*/
}
4、超级块
structfilsys
{unsignedshorts_isize;/*i节点块块数*/
unsignedlongs_fsize;/*数据块块数*/
unsignedints_nfree;/*空闲块块数*/
unsignedshorts_pfree;/*空闲块指针*/
unsignedints_free[NICFREE];/*空闲块堆栈*/
unsignedints_ninode;/*空闲i节点数*/
unsignedshorts_pinode;/*空闲i节点指针*/
unsignedints_inode[NICINOD];/*空闲i节点数组*/
unsignedints_rinode;/*铭记i节点*/
chars_fmod;/*超级块修改标记*/
}
5、用户密码
structpwd
{unsignedshortp_uid;
unsignedshortp_gid;
charpassword[PWOSIZ];
};
6、目录
structdir
{structdirectdirect[DIRNUM];
intsize;
};
7、查找内存i节点的hash表
structhinode
{structinode*i_forw;
};
8、系统打开表
structfile
{charf_flag;/*文件操作标志*/
unsignedintf_count;/*引用计数*/
structinode*f_inode;/*指向内存i节点*/
unsignedlongf_off;/*读/写指针*/
};
9、用户打开表
structuser
{unsignedshortu_default_mode;
unsignedshortu_uid;/*用户标志*/
unsignedshortu_gid;/*用户组标志*/
unsignedshortu_ofile[NOFILE];/*用户打开表*/
};
三、主要函数
1、i节点内容获取函数iget()
2、i节点内容释放函数iput()
3、目录创建函数mkdir()
4、目录搜索函数namei()
5、磁盘块分配函数balloc()
6、磁盘块释放函数bfree()
7、分配i节点区函数ialloc()
8、释放i节点区函数ifree()
9、搜索当前目录下文件的函数iname()
10、访问控制函数access()
11、显示目录和文件用函数_dir()
12、改变当前目录用函数chdir()
13、打开文件函数open()
14、创建文件函数create()
15、读文件用函数read()
16、写文件用函数write()
17、用户登录函数login()
18、用户退出函数logout()
19、文件系统格式化函数format()
20、进入文件系统函数install()
21、关闭文件系统函数close()
22、退出文件系统函数halt()
23、文件删除函数delete()
四、主程序说明
begin
step1对磁盘进行格式化
step2调用install(),进入文件系统
step3调用_dir(),显示当前目录
step4调用login(),用户注册
step5调用mkdir()和chdir()创建目录
step6调用creat(),创建文件0
step7分配缓冲区
step8写文件0
step9关闭文件0和释放缓冲
step10调用mkdir()和chdir()创建子目录
step11调用creat(),创建文件1
step12分配缓冲区
step13写文件1
step14关闭文件1和释放缓冲
step15调用chdir将当前目录移到上一级
step16调用creat(),创建文件2
step17分配缓冲区
step18调用write(),写文件2
step19关闭文件2和释放缓冲
step20调用delete(),删除文件0
step21调用creat(),创建文件3
step22为文件3分配缓冲区
step23调用write(