搜索
操作系统原理课程设计适用专业：计算机科学与技术专业课程设计时间：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条）2、列目录时要列出文件名、物理地址、保护码和文件长度3、源文件可以进行读写保护实验准备1、首先应确定文件系统的数据结构：主目录、子目录及活动文件等。主目录和子目录都以文件的形式存放于磁盘，这样便于查找和修改；2、用户创建的文件，可以编号存储于磁盘上。如file0,file1,file2……并以编号作为物理地址，在目录中进行登记。实验指导Login用户登录Dir列文件目录Create创建文件Delete删除文件Open打开文件Close关闭文件Read读文件Write写文件一、文件管理要将文件存储在磁盘（带）上，必须为之分配相应的存储空间，这就涉及到对文件存储空间的管理；采取何种方式存储，又涉及到文件的物理结构；为了简化对文件的访问和共享，还应设置相应的用户文件描述表及文件表。1、文件存储空间的管理（1）文件卷的组织UNIX中，把每个磁盘（带）看作是一个文件卷，每个文件卷上可存放一个具有独立目录结构的文件系统。一个文件卷包含许多物理块，并按块号排列如下图：0#1#2#3#……K#K+1#……N#其中，0#块用于系统引导或空闲，1#为超级块(superblock)，存放文件卷的资源管理信息，如整个文件卷的盘块数、磁盘索引结点的盘块数、空闲盘块号栈及指针等。2#~K#存放磁盘索引结点。每个索引结点64B，第K+1#~N#存放文件数据。（2）空闲盘块的组织UNIX采用成组链接法组织空闲盘块。它将若干个空闲盘块划归一个组，将每组中所有盘块号存放在其前一组的第一个空闲盘块中，而第一组中所有空闲盘块号放入超级块的空闲盘块号栈中。例：超级块表10910610310095310307304301（3）空闲盘块的分配与回收内核要从文件系统中分配一盘块时，先检查超级块空闲盘块号栈是否已上锁。是则调用sleep睡眠，否则将超级块中空闲盘块栈栈顶盘块号分配出去。回收时，若空闲盘块号栈未满，直接将回收盘块编号记入空闲盘块号栈中。若回收时栈已满，须先将栈中的所有空闲盘块号复制到新回收的盘块中，再将新回收盘块的编号作为新栈的栈底块号进栈。2、文件的物理结构UNIX未采用传统的三种文件结构形式，而是将文件所占用盘块的盘块号，直接或间接地存放在该文件索引结点的地址项中。查找文件时，只需找到该文件的索引结点，便可直接或间接的寻址方式获得指定文件的盘块。过程bmap可将逻辑文件的字节偏移量转换为文件的物理块号。先将字节偏移量转换为文件逻辑块号及块内偏移量，再把逻辑块号转换为文件的物理块号。3、用户文件描述符表和文件表的管理每个进程的U区中设置一张用户文件描述符表。只在首次打开文件时才需给出路径名。内核在该进程的用户文件描述符表中，分配一空项，取其在该表中的位移量作为文件描述符fd(filediscriptor)返还给用户。当用户再次访问该文件时，只需提供fd，系统根据fd便可找到相应文件的内存索引结点。fd表项的分配由ufalloc完成。211208205202为了方便用户对文件进行读/写及共享，系统中设置了一张文件表。每个用户在打开文件时，都要在文件表中获得一表项，其中包含下述内容：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结点。若分配失败则返回，分配成功时须