1、操作系统课程实践570191操作系统原理课程实践报告专 业 计算机科学与技术 班 级 学 号 姓 名 指导教师 陈 珂 完成时间 成 绩 操作系统原理课程设计报告撰写说明如下：1、内容完整，包括：设计题目、设计内容与要求、主要思想、算法描述与流程、实现过程与结果、源程序清单、实验总结。2、封面统一，用A4纸张打印。3、可选做下列题目之一。4、提交报告一份、源码一份（注明运行平台window或linux）。纸板报告由学委统一收齐上交；电子版和源码发到gajiajie。5、验收时间另行通知。操作系统课程设计任务书题目一 进程调度算法模拟 一、设计目的 编程实现进程调度的算法，更好地掌握操作系统的原
2、理及实现方法，从而有利于把握进程调度细节。三、设计要求 (1)要求实现先来先服务,短作业优先,时间片轮转,高优先权调度算法四种算法并进行对比分析.(2)要求界面简单,易懂,关键代码部分要注释.(3)编程语言可以采用自己任意精通的语言四、设计思想说明 先来先服务：程序的执行调度顺序按先进入队列的先获得执行，并且其他进程都不能中断正在执行的进程，要等进程完成后才能，让出CPU给其他进程。执行的时候可以随时在队列中插入进程。 短作业优先：进程的调度顺序按程序的服务时间来决定，进程的执行顺序。服务时间短的先被调用。调度时先从队列中选取服务时间最短的进程来执行。进程中途不能中断，即使此时队列中存在服务时
3、间比其更短的进程，仍需要等待该进程执行完后才能被执行。 高优先权调度：选取进程中优先级最高的一个，以优先级的值大，优先级就大。调度时总是选取队列中进程优先级最高的来执行，不管是否有某个进程在执行，只要存在比正在执行进程优先级高的进程，则就会立刻中断正在执行的进程，让给跟高优先级的进程。 时间片轮转：本课程设计采用多级反馈队列调度算法，设立4个进程队列，分给队列1的时间片为3秒，队列2的时间片为6秒，队列3的时间片为12秒，队列4的时间片为24秒。队列1的优先级最高，队列4的优先级最低。高优先级的队列没执行完，即不为空，就永远不执行其下面的低优先级的队列里面的进程。当执行低优先级队列里面的进程时
4、，突然间高优先级的队列插入了进程就立刻跳到高优先级的队列执行其里面的进程。每个队列的进程都是按先来先执行的顺序执行。进程初次执行肯定要进入队列1。如何从头到尾执行一遍队列1中的进程是，存在某些进程在队列1的时间片内还没执行完，就把进程移交到下一个队列中。每个队列都如此类推。直到最后一个队列4，如果在队列4还有进程在本时间片内还没没执行完，就把该程序放到队尾，从新等待时间片执行。题目二 存储管理一、实验目的1加深对操作系统存储管理的理解2模拟页面置换算法，加深理解操作系统对内存的管理二、背景知识进先出的算法（FIFO）最近最少使用的算法（LRU）最佳淘汰算法(OPT)三、设计内容设计一个虚拟存储
5、区和内存工作区,并使用下列算法计算访问命中率.（1） 先进先出的算法（FIFO）（2） 最近最少使用的算法（LRU）（3） 最佳淘汰算法(OPT) 命中率=1-页面失效次数/页地址流长度程序设计 本程序设计基本上按照设计内容进行。即首先用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。相关定义如下：1 数据结构 (1)页面类型 typedef struct int pn,pfn,counter,time; pl-type;其中pn 为页号,pfn为面号, counter为一个周期内访问该页面的次数, time为访问时间
6、. (2) 页面控制结构pfc-struct int pn,pfn; struct pfc_struct *next; typedef struct pfc_struct pfc_type;pfc_type pfc_structtotal_vp,*freepf_head,*busypf_head;pfc_type *busypf_tail; 其中pfctotal_vp定义用户进程虚页控制结构,*freepf_head为空页面头的指针,*busypf_head为忙页面头的指针,*busypf_tail为忙页面尾的指针.2函数定义 （1）Void initialize( ):初始化函数,给每个相关
7、的页面赋值. （2）Void FIFO( ):计算使用FIFO算法时的命中率. （3）Void LRU( ):计算使用LRU算法时的命中率. （4）Void OPT( ):计算使用OPT算法时的命中率. （5）Void LFU( ):计算使用LFU算法时的命中率. （6）Void NUR( ):计算使用NUR算法时的命中率.3.变量定义 (1)int atotal_instruction: 指令流数据组. (2)int pagetotal_instruction: 每条指令所属的页号. (3)int offsettotal_instruction: 每页装入10条指令后取模运算页号偏移值. (
8、4)int total_pf: 用户进程的内存页面数. (5)int disaffect: 页面失效次数.题目三文件管理一、实验目的1加深对文件、目录和文件系统等概念的理解2通过设计一个简单的文件系统加深理解操作系统中文件文件系统的实现二、背景知识阅读Linux文件系统相关源码三、实验内容为Linux系统设计一个简单的二级文件系统。要求做到以下几点：1.可以实现下列几条命令： login 用户登录 dir 列目录 create 创建文件 delete 删除文件 open 打开文件 close 关闭文件 read 读文件 write 写文件2列目录时要列出文件名，物理地址，保护码和文件长度3源文
9、件可以进行读写保护(1)设计思想本文件系统采用两级目录，其中第一级对应于用户账号，第二级对应于用户帐号下的文件。另外，为了简便文件系统未考虑文件共享，文件系统安全以及管道文件与设备文件等特殊内容。对这些内容感兴趣的读者，可以在本系统的程序基础上进行扩充。(2)主要数据结构a) I节点struct inodestruct inode *i_forw;struct inode *i_back;char I_flag;unsigned int i_into; /*磁盘i节点标号*/unsigned int i_count; /*引用计数*/unsigned short di_number; /*关联
10、文件书，当为0时，则删除该文件*/unsigned short di_mode; /*存取权限*/unsigned short di_uid; /*磁盘i节点用户*/unsigned short di_gid; /*磁盘i节点组*/Unsigned int di_addrNADDR; /*物理块号*/b) 磁盘i结点Struct dinode unsigned short di_number; /*关联文件数*/ unsigned short di_mode; /*存取权限*/ unsigned short di_uid; unsigned short di_gid;unsigned long
11、 di_size; /*文件大小*/unsigned int di_addrNADDR; /*物理块号*/c)目录项结构Struct direct char d_nameDIRSIZ; /*目录名*/ unsigned int d_ino; /*目录号*/d)超级块Struct filsys unsigned short s_isize; /*i节点块块数*/ unsigned long s_fsize; /*数据块块数*/ unsigned int s_nfree; /*空闲块块数*/ unsigned short s_pfree; /*空闲块指针*/ unsigned int s_free
12、NICFREE; /*空闲块堆栈*/ unsigned int s_ninode; /*空闲i节点数*/ unsigned short s_pinode; /*空闲i节点指针*/ unsigned int s_inodeNICINOD; /*空闲i节点数组*/ unsigned int s_rinode; /*铭记i节点*/ char s_fmod; /*超级块修改标志*/;e)用户密码Struct pwd unsigned short P_uid;unsigned short P_gid;char passwardPWOSIZ;f) 目录Struct dir strut direct dir
13、ectDIRNUM; int size;g).查找i内存节点的hash表Struct hinode strut inode *iforw;h).系统打开表Struct filechar f_flag; /*文件操作标志*/unsigned int f_count; /*引用计数*/struct inode *f_inode; /*指向内存节点*/unsigned long f_off; /*读/写指针*/i)用户打开表Struct user unsigned short u_default_mode;unsigned short u_uid; /*用户标志*/unsigned short u_
14、gid; /*用户组标志*/unsigned short u_ofileNOFILE; /*用户打开表*/3.主要函数 （1）i节点内容获取函数iget()（详细描述略）。 （2）节点内容释放函数iput()（详细描述略）。 （3）目录创建函数mkdir()（详细描述略）。 （4）目录搜索函数namei()（详细描述略）。（5）磁盘块分配函数balloc()（详细描述略）。（6）磁盘块释放函数bfree()（详细描述略）。 （7）分配i节点区函数ialloc()（详细描述略）。 （8）解释结点区函数ifree（ ）（详细描述略）。 （9）搜索当前目录下文件的函数iname（ ）（详细描述略）。
15、 （10）访问控制函数access（ ）（详细描述略）。 （11）显示目录和文件函数_dir（ ）（详细描述略）。 （12）改变当前目录用函数chdir（ ）（详细描述略）。 （13）打开文件函数open（ ）（详细描述略）。 （14）创建文件函数create（ ）（详细描述略）。 （15）读文件用函数read（ ）（详细描述略）。 （16）读文件用函数write（ ）（详细描述略）。 （17）用户登陆函数login（ ）（详细描述略）。 （18）用户退出函数logout（ ）（详细描述略）。 （19）文件系统格式化函数format（ ）（详细描述略）。 （20）进入文件系统函数install
16、（ ）（详细描述略）。 （21）关闭文件函数close（ ）（详细描述略）。 （22）退出文件系统函数halt（ ）（详细描述略）。 （23）文件删除函数delecte（ ）（详细描述略）。4主程序说明begin Step1 对磁盘进行格式化 Step2 调用install（），进入文件系统 Step3 调用_dir（），显示当前目录 Step4 调用login（），用户注册 Step5 调用mkdir（）和chdir（）创建目录 Step6 调用create（），创建文件0 Step7 分配缓冲区 Step8 写文件0 Step9 关闭文件0和释放缓冲 Step10 调用mkdir（）和ch
17、dir（）创建子目录 Step11 调用create（），创建文件1 Step12 分配缓冲区 Step13 写文件1 Step14 关闭文件1和释放缓冲 Step15 调用chdir将当前目录移到上一级 Step16 调用create（），创建文件2 Step17 分配缓冲区 Step18 调用write（），写文件2 Step19 关闭文件1和释放缓冲 Step20 调用delecte（），删除文件0 Step21 调用create（），创建文件1Step22 为文件3分配缓冲区Step23 调用write（），写文件2Step24 关闭文件3并释放缓冲区 Step25 调用open()，
18、打开文件2 Step26 为文件2分配缓冲 Step27 写文件3后关闭文件3 Step28 释放缓冲 Step29 用户退出（logout） Step30 关闭（halt）End由上述的描述过乘可知，该文件系统实际是为用户提供一个解释执行相关命令的环境。主程序中的大部分语句都被用来执行相应的命令。题目四 银行家算法一、实验目的通过银行家算法理解操作系统安全状态和不安全状态。二、实验要求根据教材在T0时刻系统分配的资源，用银行家算法判断系统是否处于安全序列，它的安全序列怎样。三、实验方法内容1、算法设计思路操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷
19、款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。主要的常量变量n：系统中进程的总数 m：资源类总数 Available: ARRAY1.m of integer; Max: ARRAY1.n,1.m of int
20、eger; Allocation: ARRAY1.n,1.m of integer; Need: ARRAY1.n,1.m of integer; Request: ARRAY1.n,1.m of integer; 符号说明： Available 可用剩余资源 Max 最大需求 Allocation 已分配资源 Need 需求资源 Request 请求资源主要模块当进程pi提出资源申请时，系统执行下列 步骤：(“=”为赋值符号，“=”为等号) step（1）若Request=Need, goto step（2）；否则错误返回 step（2）若Request=Available, goto st
21、ep（3）；否则进程等待 step（3）假设系统分配了资源，则有： Available=Available-Request; Allocation=Allocation+Request; Need=Need-Request 若系统新状态是安全的，则分配完成 若系统新状态是不安全的，则恢复原状态，进程等待 为进行安全性检查，定义数据结构： Work:ARRAY1.m of integer; Finish:ARRAY1.n of Boolean; 安全性检查的步骤： step (1): Work=Available; Finish=false; step (2) 寻找满足条件的i： a.Finis
22、h=false; b.Need=Work; 如果不存在，goto step(4) step(3) Work=Work+Allocation; Finish=true; goto step(2) step (4) 若对所有i,Finish=true,则系统处于安全状态，否则处于不安全状态。题目五 模拟内存管理，实现内存块的分配与回收。一、实验的目的要求及内容通过对首次适应算法的编程应用，更加深入地理解首次适应算法的原理及工作机制，理解内存分配过程及原理。二、算法设计思想设计思想：由于此系统是为了模拟一个可变式分区分配的存储管理系统，而且采用首次适应算法，所以应该确定所管理的存储容量，而且还应为其
23、开始进行分区；由于首次首次适应算法的一个特点就是在分区时，后面的分区容量不小于前面的分区容量，所以在为系统初始化时，应动态地显示在不同阶段的未分区容量，以便进行分区；在创建分区时，应有该区的容量、首尾地址（由于在计算机系统地址采用16进制，在此也采用16进制）和标识符等信息。由于作业随时会调入和调出内存，所以，还应对内存进行动态地分配与回收。题目六 模拟磁盘调度一、实验目的及内容1模拟一个磁盘调度算法；2要求能够模拟FCFS、最短寻道时间、电梯算法三个磁盘调度算法；3输入为一组作业的磁道请求；4输出为按选择的算法执行时的磁头移动轨迹。二、算法设计思想磁盘调度主要思想设备的动态分配算法与进程调度
24、相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+Mi+MN）/N其中Mi
25、为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：寻找时间磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间指定扇区旋转到磁头下所需的时间。传送时间由磁头进程读写完成信息传送的时间。其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱
26、面上。所以各磁盘的编号按柱面顺序（从0号柱面开始），每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘是，应采用一种最佳调度算法，以使各种进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标，是使磁盘的平均寻道时间最少。目前常用的磁盘帝调度算法有：先来先服务、最短寻道时间优先及扫描等算法。三、主要算法分析各个算法分析 1.先来先服务算法（FCFS）最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正
27、在50号柱面上执行输出操作，而等待访问者依次要访问的柱面为130、199、32、159、15、148、61、99，那么，当50号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面，最后到达99号柱面。采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。2.最短寻道时间优先算法（SSTF）最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论，现在当50号柱面的操作结束后，应该先处理61号柱面的请求，然后到达32号
28、柱面执行操作，随后处理15号柱面请求，后继操作的次序应该是99、130、148、159、199。采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了200多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（SSTF）调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。3.扫描算法（SCAN）SCAN 算法又称电梯调度算法。SC
29、AN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。
