广工操作系统实验报告.doc

计算机 学院 软件工程 专业 2 班_组、学号 3110006294 姓名 黄煜财 协作者 无 教师评定_实验题目 进程调度 一、实验目的用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解。二、实验内容和要求设计一个有 N个进程共行的进程调度程序。要求采用最高优先数优先算法，时间片轮转算法，多级队列调度算法这三种算法。 每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。 进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。 进程的运行时间以时间片为单位进行计算。 每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。 就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。 如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。重复以上过程，直到所有的进程都完成为止。三、实验原理及设计方案1、进程调度算法：采用多级反馈队列调度算法。其基本思想是：当一个新进程进入内在后，首先将它放入第一个队列的末尾，按FCFS原则排队等待高度。当轮到该进程执行时，如能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚为完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行，以此类推。2、实验步骤:（1）按先来先服务算法将进程排成就绪队列。（2）检查所有队列是否为空，若空则退出，否则将队首进程调入执行。（3）检查该运行进程是否运行完毕，若运行完毕，则撤消进程，否则，将该进程插入到下一个逻辑队列的队尾。（4）是否再插入新的进程,若是则把它放到第一逻辑队列的列尾。（5）重复步骤（2）、（3）、（4），直到就绪队列为空。四、程序流程图进程完成，撤消该进程就绪队列首进程投入运行时间片到，运行进程已占用CPU时间+1运行进程已占用CPU时间已达到所需的运行时间把运行进程插入到下一个队列的队尾插入新的进程开始初始化PCB,输入进程信息所有队列都为空各进程按FCFS原则排队等待调度五、重要数据结构及难程序列表typedef struct pcb/进程管理块char name10;/进程名字char state;/进程状态int queue;/进程所在的队列int ntime;/进程需要运行的时间int rtime;/进程已经运行的时间int etime;/进程在本队列可运行的时间片struct pcb *link;PCB;PCB*ready = NULL, *pinsert = NULL, *pfend = NULL,*p =NULL;/就绪队列，进程插入位置的变量void insert()/插入进程if(!ready )ready = p;pfend = p;pinsert = p;else if(ready ->queue = 1)/第一队列存在p->link = pfend->link;pfend->link = p;pfend = p;findpos();elsep->link = ready;ready = p;findpos();void sort()/调整进程队列if(!ready->link |ready->queue < ready->link->queue) return;p = ready ->link;ready ->link = pinsert ->link;pinsert ->link = ready;pinsert = ready;ready = p;if (ready && ready -> queue = pinsert ->queue)findpos();六、运行结果七、分析与小结在这个多级反馈的实验中，我采取了用一条实际上的链表队列来模拟多个逻辑上的队列，通过维护几个链表的状态信息来找到每个进程运行完后应该插入的地方，还有一个标志位Fend用来表明新插入的队列的位置。虽然实验原理很简单，但是在编写代码的过程中遇到了不少的问题，在两个小时之内已经完成的大体代码的编写，但是之中存在不少的问题，导致了用了差不多四个小时的时间去调试才把它弄好，这主要归咎于在开始设计代码的不太合理，在后期使得代码结构有些混乱，使得调试更加的麻烦，以及对编程的不熟悉。通过这个实验不仅使我对进程的调度算法有了更深的认识，使得理论知识得到的实践，也使我的编程能力得到了进一步提高。 计算机 学院 软件工程 专业 2 班_组、学号 3110006294 姓名 黄煜财 协作者 无 教师评定_实验题目 作业调度 一、 实验目标本实验要求学生模拟作业调度的实现，用高级语言编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解。二、实验内容和要求为单道批处理系统设计一个作业调度程序(1)、编写并调试一个单道处理系统的作业调度模拟程序。(2)、作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 先来先服务就是每次调度都是从后备作业队列中，选择一个最先进入该队列的作业，将它调入内存，为它分配资源、创建进程，然后放入就绪队列，投入运行，一直运行到完成或发生某事件而阻塞后，才放弃处理。最短作业优先是从后备队列中选择一个估计运行时间最短的作业，将它调入内存运行并一直执行到完成，或发生某事件而被阻塞放弃处理时，再重新调度。 响应比高者优先是通过计算出作业的响应比，按响应比高而进行调度的，其计算公式是：优先权（等待时间+要求服务时间）/要求服务时间.(3)、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。(4)、每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。(5)、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。三、实验原理及设计方案1、实验原理 先来先服务算法：是按照作业进入输入井的先后次序来挑选作业，先进入输入井的作业优先被挑选，当系统中现有的尚未分配的资源不能满足先进入输入井的作业，那么顺序挑选后面的作业。 FCFS算法简单易行，但性能却不大好。短作业优先算法：总是按照作业要求运行时间来选择作业，每次挑选要求作业执行时间短且资源要求能满足的作业优先分派处理机，通常后来的短作业不抢先正在执行的作业。SJF改善平均周转时间和平均带权周转时间，缩短作业的等待时间 ,提高系统的吞吐量,但对长作业非常不利。响应比高者优先算法：最高响应比优先法(HRN，Highest Response_ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。 响应比R定义如下： R =(W+T)/T = 1+W/T 其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。2、 设计方案struct source /*定义资源需求结构*/char memery5; /*主存需求*/int machine; /*磁带机数量*/;struct jcb /* 定义作业控制块PCB */ char name10; char state; /* 状态 */ double super; /* 响应比优先权 */ int ntime; /* 需要运行时间 */ int rtime; /* 开始运行时间 */int ptime; /*提交时间*/int ftime; /*完成时间*/ source *needsources; /*资源需求链*/ struct jcb* link; /* 下一个作业控制块的地址 */*ready=NULL,*run,*p;四、程序流程图12响应比高优先算法短作业优先算法先来先服务算法初始化作业JCB和资源source，所有作业按照先后顺序排列，作业提交时间为系统默认时间p->ptime=Systemtim，作业完成时间p->ftime=03作业调度算法？开始YNNNYY用响应比高优先算法，先计算所有作业高响应比，调度队响应比最高的首作业投入运行，更改作业状态为R，记录作业开始运行时间和完成时间，修改下一作业指针等，计算运行作业i的完成时刻，周转时间和带权周转时间计算并打印这组作业的平均周转时间及带权平均周转时间用短作业算法调度需求时间最短的作业投入运行，更改作业状态为R，记住作业开始运行时间，修改下一作业指针等，计算运行作业i的完成时刻，周转时间和带权周转时间结束等待队列空？释放该作业占用资源作业运行完毕？用先来先服务算法调度队首作业投入运行，更改作业状态为R，记住作业开始运行时间，修改下一作业指针等，计算运行作业i的完成时刻，周转时间和带权周转时间五、重要数据结构及难程序列表#include <stdio.h> #include <stdlib.h> #include <conio.h> #define getpch(type) (type*)malloc(sizeof(type) int Select;int Systemtime = 0; /*系统初始时间*/int JCBnum = 0; /*总作业数*/int JCBtime = 0; /*总周转时间*/double JCBtotaltime =0; /*总带权周转时间*/struct source /*定义资源需求结构*/char memery5; /*主存需求*/int machine; /*磁带机数量*/;struct jcb /* 定义作业控制块PCB */ char name10; char state; /* 状态 */ double super; /* 响应比优先权 */ int ntime; /* 需要运行时间 */ int rtime; /* 开始运行时间 */int ptime; /*提交时间*/int ftime; /*完成时间*/ source *needsources; /*资源需求链*/ struct jcb* link; /* 下一个作业控制块的地址 */*ready=NULL,*run,*p; typedef struct jcb JCB;typedef struct source SOURCE;void sort() /* 建立对进程进行优先级排列函数*/ JCB *first, *second,*temp; int insert=0; switch(Select)case 1: /*先来先去服务算法*/if(ready=NULL) /*队首空插入队首*/p->link=ready;ready=p;else /*否则插入队尾*/first=ready;second=ready->link;while(second!=NULL)first=first->link;second=second->link;first->link=p;break;case 2: /*最短作业优先算法*/ if(ready=NULL)|(p->ntime)<(ready->ntime) /*队首*/ p->link=ready; ready=p; else /* 往后搜索适当的位置插入*/ first=ready; second=first->link; while(second!=NULL) /*插入队伍中间*/ if(p->ntime)<(second->ntime) p->link=second; first->link=p; second=NULL; insert=1; else first=first->link; second=second->link; if(insert=0) first->link=p; /* 插入队尾*/ break;case 3: /*响应比高者优先算法*/ /*响应比=(等待时间+需求时间)/需求时间*/ temp=ready;p->super=(double)(Systemtime-p->ptime+p->ntime)/(double)(p->ntime); /*计算插入队列作业优先权*/ while(temp) /*计算就绪队列作业优先权*/ temp->super=(double)(Systemtime-temp->ptime+temp->ntime)/(double)(temp->ntime);temp=temp->link; /*响应比越大优先权越高*/ if(ready=NULL)|(p->super)>(ready->ntime) /*队首*/ p->link=ready; ready=p; else /* 往后搜索适当的位置插入*/ first=ready; second=first->link; while(second!=NULL) /*插入队伍中间*/ if(p->super)>(second->super) p->link=second; first->link=p; second=NULL; insert=1; else first=first->link; second=second->link; if(insert=0) first->link=p; /* 插入队尾*/ break; default:break;六、运行结果主程序菜单先来先服务算法单道作业批处理系统初始化，输入三个作业，按照提示输入其时间，资源需求等：第一轮作业调度，如图显示了每个作业提交时间、需求时间、响应比、即时状态、主存需求、磁带机数量等，每次调度完毕输出作业完成时间、周转时间、带权周转时间、释放的资源：同样，第二轮调度，作业22完成，如下显示：同样，第二轮调度，作业22完成，如下显示：全部作业运行完毕，计算总的平均周转时间和带权周转时间：短作业优先算法单道作业批处理系统初始化，输入三个作业，按照提示输入其时间，资源需求等：第一轮作业调度，如图显示了每个作业提交时间、需求时间、响应比、即时状态、主存需求、磁带机数量等，每次调度完毕输出作业完成时间、周转时间、带权周转时间、释放的资源：同样，第二轮调度，作业33完成，输出作业完成时间、周转时间、带权周转时间、释放的资源：同样，第三轮调度，作业22完成，输出作业完成时间、周转时间、带权周转时间、释放的资源：全部作业运行完毕，计算总的平均周转时间和带权周转时间：七、分析与小结有了第一次实验的基础，做第二个实验就感觉轻松多了，虽然我选择的题目还是比较简单的单道作业批处理系统，整体设计过程还是可以借鉴第一次的方法，关键就是几个作业调度算法的实现，只要熟读书本注意处理好细节的问题实现不会有太大困难，通过再一次的整体设计不但使我对各种作业调度算法有更深刻的理解，而且对C语言的编程技巧也有很大的提升，当然这次功能的实现与我预期的还有一些差距，希望通过更多的实验让自己得到更大的提升！ 计算机 学院 软件工程 专业 2 班_组、学号 3110006294 姓名 黄煜财 协作者 无 教师评定_实验题目 主存空间的分配与回收 一、 实验目的熟悉主存的分配与回收。理解在不同的存储管理方式下，如何实现主存空间的分配与回收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。二、实验内容和要求主存的分配和回收的实现是与主存储器的管理方式有关的。所谓分配，就是解决多道作业或多进程如何共享主存空间的问题。所谓回收，就是当作业运行完成时将作业或进程所占的主存空间归还给系统。可变分区管理是指在处理作业过程中建立分区，使分区大小正好适合作业的需求，并且分区个数是可以调整的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入，作业等待。随着作业的装入、完成，主存空间被分成许多大大小小的分区，有的分区被作业占用，而有的分区是空闲的。实验要求使用可变分区存储管理方式，分区分配中所用的数据结构采用空闲分区表和空闲分区链来进行，分区分配中所用的算法采用首次适应算法、循环首次适应算法、最佳适应算法三种算法来实现主存的分配与回收。同时，要求设计一个实用友好的用户界面，并显示分配与回收的过程。三、实验原理及设计方案1、循环首次适应算法在该算法中，把主存中所有空闲区按其物理地址递增的次序排列。在为作业分配存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足要求的空闲区，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区表或链中。2、 实验步骤（1）初始化空闲分区；（2）反复对现有的空闲分区进行进程创建和撤消，即内存分配和回收；（3）退出。四、程序流程图 五、重要数据结构及难程序列表typedef struct Memory/可用分区链表节点int base;/基地址int size;/大小struct Memory *next;MEM;MEM *pm = getMEM();/可用分区的链表头MEM *temp;/int SIZE;/总的内存的大小，由用户输入部分主要函数bool check(MEM* pm, int base, int size)/检查用户输入的合法性MEM *p = pm;p = pm;while(p->next)if(p->base + p->size <= base && base <= p->next->base && p->next->base >= base + size)return true;p= p ->next;if(!p->next && p->base + p->size < SIZE)if(p->base + p->size <= base && base <= SIZE && SIZE >= base + size)return true;return false;bool release(MEM *pm, int base, int size)/释放内存空间MEM *p = pm;if(!check(pm, base ,size)return false;while(p->next)if(base + size <= p->next->base)break;p = p->next;if(base = p->base + p->size)/低地址相邻if(p ->next && p->next->base = base + size)/释放区上下都相邻p->size += size + p->next->size;temp = p->next;p->next = p->next->next;free(temp);else/仅与地地址相邻p->size += size;else if (p->next && p->next->base = base +size)/仅高地址相邻p->next->base = base;p->next->size += size;else/释放区上下与空闲区都不相邻temp = getMEM();temp->size = size;temp->base = base;temp->next = p->next;p->next = temp;return true;int allocMem(MEM *pm, int size)/分配内存空间MEM *p = pm;int base;while(p->next)if(p->next->size >= size)break;p = p->next;if(!p->next)return -1;if(p->next->size = size)/空闲分区大小刚好等于所需分区base = p->next->base;p->next = p->next->next;elsep->next->size -= size;base = p->next->base;p->next->base += size;return base;六、运行结果初始化主存大小后的状态按1后分配一块内存：按1后分配一块内存：按2释放内存：七、分析与小结本实验我采取用一条链表同时表示空闲分区链和主存空间占用情况，因为主存总大小是固定的，把空闲分区链所表示的区域从总的内存里去除就是被占用的空间的大小，这个实验还是比较简单的，因此很快就完成了，通过它使我学习了主存空间的分配与回收，同时也让我意识到了在回收内存时的一些问题，使我对课本知识有了更进一步的理解。 计算机 学院 软件工程 专业 2 班_组、学号 3110006294 姓名 黄煜财 协作者 无 教师评定_实验题目 文件系统 一、实验目的模拟文件系统实现的基本功能,了解文件系统的基本结构和文件的各种管理方法,加深理解文件系统的内部功能及内部实现。通过用高级语言编写和调试一个简单的文件系统，模拟文件管理的工作过程，从而对各种文件操作命令的实质内容和执行过程有比较深入的了解。二、实验内容和要求编程模拟一个简单的文件系统，实现文件系统的管理和控制功能。要求本文件系统采用两级目录，即设置主文件目录MFD和用户文件目录UED。另外，为打开文件设置运行文件目录AFD。设计一个10个用户的文件系统，每次用户可保存10个文件，一次运行用户可以打开5个文件，并对文件必须设置保护措施。在用户程序中通过使用文件系统提供的Create、open、read、write、close、delete等文件命令，对文件进行操作。三、实验设计方案及原理1、实验原理 因为系统小，对文件目录检索使用简单的线性搜索，为了便于实现，对文件读写做了简化，在执行读写命令时，只修改读写指针，并不实际对文件进行操作，其中初始状态下，读指针=0，写指针=文件长度，文件保护码使用三位保护码：1：表示文件允许的读 2：表示文件可写 3.表示文件可执行，创建文件时通过模拟磁盘的使用情况来实现。2、设计方案程序采用两级目录结构，第一级威设置主文件目录MFD,第二级为用户文件目录UFD，另外为打开文件设置运行目录AFDstruct mdf /* 第一级：主目录 MDF */ char name10; /* 用户名 */ UFD* directory; /* 文件目录指针 */ maindir10; /* 用户数组 */typedef struct mdf MDF;struct ufd /* 第二级：用户文件目录 UFD */ char filename10; /* 文件名 */ char procode3; /* 保护码 1:读 2:写 3:执行*/ int length; /* 文件长度 */ *p;typedef struct ufd UFD;struct afd /* 文件运行目录 */ char filename10; /* 文件名 */ char procode3; /* 保护码 1:读 2:写 3:执行*/ int rw; /* 读写指针 初始状态读:0 写:文件长度 */ afd5; 系统提供8条命令：create delete open close read write display quit，可以提供创建、删除、打开、关闭、读入、写出、显示、退出等功能。、 Create在用户当前目录下创建一个文件，该文件的管理信息登录到用户文件信息管理模块中。命令格式：create、 delete删除当前用户目录下的一个文件，删除后文件无法打开。命令格式：delete 、 open在当前用户目录打开某个文件并修改标志位，对文件各种操作都需先打开。命令格式：open、 close关闭用户运行的文件。执行该命令后，用户在系统中运行文件状态位被修改为关闭。命令格式：close、 read从用户已打开文件读信息，将文件信息读入并修改读取标志位，未打开文件无法读取。命令格式：read、 write-向用户已打开文件写入信息，修改标志位，未打开文件无法写出操作。命令格式：write、 display用户目录文件列表显示。命令格式：display、 quit用户注销命令。当使用该命令时，用户退出系统。命令格式： quit四、程序流程图显示目录写出文件读入文件安全退出关闭文件打开文件删除文件创建文件displaywritereadquitcloseopenndelete输入操作命令用户不存在create是什么命令？显示该用户目录下的所有文件管理信息在MFD中找到该用户？用户登录新用户注册开始结束自动保存目录五、重要数据结构及难程序列表struct ufd /* 第二级：用户文件目录 UFD */ char filename10; /* 文件名 */ char procode3; /* 保护码 1:读 2:写 3:执行*/ int length; /* 文件长度 */ *p;typedef struct ufd UFD;struct mdf /* 第一级：主目录 MDF */ char name10; /* 用户名 */ UFD* directory; /* 文件目录指针 */ maindir10; /* 用户数组 */typedef struct mdf MDF;struct afd /* 文件运行目录 */ char filename10; /* 文件名 */ char procode3; /* 保护