操作系统课程设计之一

1、 . . . 实验一二三四五六七八九十总评成绩大学珞珈学院课程实验(设计)报告课程名称： 操作系统设计 2011年11 月 10 日实习一 处理器调度一、实习容选择一个调度算法，实现处理器调度。二、实习目的本实习模拟在单处理器环境下的处理器调度，加深了解处理器调度的工作。三、实习题目本实习有两题，可任选一题。第一题：设计一个按优先数调度算法实现处理器调度的程序。提示：(1)假定系统有5个进程，每个进程用一个PCB来代表。PCB的结构为：·进程名如P1P5。·指针按优先数的大小把5个进程连成队列，用指针指出下一个进程PCB的首地址。·要求运行时间假设进程需要运行的单

2、位时间数。·优先数赋予进程的优先数，调度时总是选取优先数大的进程先执行。·状态假设两种状态：就绪和结束，用R表示就绪，用E表示结束。初始状态都为就绪状态。(2) 开始运行之前，为每个进程确定它的“优先数”和“要求运行时间”。通过键盘输入这些参数。(3) 处理器总是选择队首进程运行。采用动态改变优先数的办法，进程每运行1次，优先数减1，要求运行时间减1。(4) 进程运行一次后，若要求运行时间不等于0，则将它加入就绪队列，否则，将状态改为“结束”，退出就绪队列。(5) 若就绪队列为空，结束，否则转到(3)重复。要求能接受键盘输入的进程优先数与要求运行时间，能显示每次进程调度的情

3、况，如哪个进程在运行，哪些进程就绪，就绪进程的排列情况。四. 实验过程 1.实验算法分析：优先数调度算法又称优先权调度算法，在进程调度中，优先数调度算法每次从就绪队列中选择优先数高的进程，将处理机分配给他，使之投入运行。根据进程调度方式的不同，又可以将调地算法分为非强占式优先数调度算法和抢占式优先数调度算法。 2.本实验采用非抢占式优先数调度算法实现进程的调度，实现5个进程的调度情况，实现代码的分析，并验证过程。 3. 实验的流程图如下图所示：4.代码段分析：struct PCB/定义一个进程结点数据域，为每一个进程定义一个进程控制块char name3; /进程名int run_time;

4、/运行时间int level; /优先数char state; /运行状态struct PCB *next; /指向下一个结点的指针;struct PCB *creat() /创建一个函数，用于返回一个链表 包含输入各个节点的信息 并实现调度算法 void display(struct PCB *p) /用于输出当前链表中各结点的状态 输出各个时刻各个节点的状态信息void main( void )struct PCB *head, *tail, *p;head = creat();/调用函数creat，head指向头结点p = head;tail = p;printf("初始进程的

5、情况: n"); 下面是对算法的总体实现，以与对输出操作-display(p); /显示当前结点的情况 输出实验结果-5. 实验结果请输入第1个结点的优先数: 1请输入第1个结点的运行时间: 10请输入第2个结点的优先数: 2请输入第2个结点的运行时间: 20请输入第3个结点的优先数: 3请输入第3个结点的运行时间: 30请输入第4个结点的优先数: 4请输入第4个结点的运行时间: 40请输入第5个结点的优先数: 5请输入第5个结点的运行时间: 50初始进程的情况: P5 50 5 R P4 P4 40 4 R P3 P3 30 3 R P2 P2 20 2 R P1 P1 10 1

6、R (null)最新进程调度的情况:P5-> P5 50 5 R P4 P4 40 4 R P3 P3 30 3 R P2 P2 20 2 R P1 P1 10 1 R (null)最新进程调度的情况:P4-> P4 40 4 R P5 P5 49 4 R P3 P3 30 3 R P2 P2 20 2 R P1六.调试结果与分析通过本次试验的学习，我深入的了解了进程的调度情况，从算法的设计中学到了每个进程用进程控制块的优点，并从中学习了操作系统中任务的运作流程。实习二 主存空间的分配和回收一、实习容主存储器空间的分配和回收。二、实习目的通过本实习帮助理解在不同的存储管理方式下应怎

7、样进行存储空间的分配和回收。三、实习题目本实习有两题，可任选一题。可变分区管理方式下采用首次适应算法实现主存分配和回收(1) 可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存容量查看是否有足够的空闲空间，若有，则按需分配，否则，作业无法装入。假定存大小为128K，空闲区说明表格式为：·起始地址指出空闲区的起始地址；·长度一个连续空闲区的长度；·状态有两种状态，一种是“未分配”状态；另一种是“空表目”状态，表示该表项目前没有使用。(2) 采用首次适应算法分配回收存空间。运行时，输入一系列分配请求和回收请求。要求能接受来自键盘

8、的空间申请与释放请求，能显示分区分配与回收后的存布局情况。四. 实验过程 1.算法分析：首次适应算法又称最先适应算法，该算法要求空袭那分区按地址递增的次序排列。在进行存分配时，从空闲分区表（或空闲分区链）首开始顺序查找，直到找到第一个能满足其大小要求的空闲分区为止。然后，再按照作业的大小，从该分区中划出一块存空间分配给请求者，余下的空闲分区仍然留在空闲分区表中。 2 程序的流程图： 开始输出四个选项供选择根据不同的选择查看内存分配申请内存分配申请回收内存显示内存分配情况输入任务名，并给任务分配内存输入任务，回该作业所占内存3 实现并验证算法的程序分析1) 定义数据结构类型struct MZon

9、e /存分区 /空闲区起始地址 int begin_addr; /一个连续空闲区的长度 int length; /状态 int state; /存中任务名 char task_name32; /指向下一个空闲分区 struct MZone *next; ;2) 插入任务到空闲分区并，分配存/Minsert函数，功能插入任务到空闲分区 int Minsert(struct MZone* Mnew) 插入任务到空闲分区/memoallocate函数，用于分配存void memoallocate(void) struct MZone *Mnew = (struct MZone*)malloc(siz

10、eof(struct MZone); printf("输入要分配存大小(kb):n"); scanf("%d",&Mnew->length); printf("输入任务名:n"); scanf("%s",&Mnew->task_name); Minsert(Mnew)?printf("分配存成功n"):printf("没有符合大小的空闲分区，存分配失败。n"); system("pause"); free(Mnew);3) 回收

11、存int Mreturn(char taskname) 显示分配存的情况4) 显示存分配情况 /存头指针 struct MZone * Mhead = NULL;/showmemory函数，显示当前存分配情况 void showmemory() struct MZone *Mpoint = Mhead; printf("存的使用情况n"); printf("beginaddrtlengthtstatettaskn"); while( NULL!=Mpoint) printf("%dktt",Mpoint->begin_addr)

12、; printf("%dkt",Mpoint->length); Mpoint->state?printf("CANUSEt"):printf("CANTUSEt"); printf("%sn",Mpoint->task_name); Mpoint = Mpoint->next; system("pause");5) 验证算法的正确性int main(void) int func_ = 0; /初始化Mhead Mhead = (struct MZone*)malloc(

13、sizeof(struct MZone); Mhead->begin_addr = 0; Mhead->length = MSIZE; Mhead->state = CANUSE; memset(Mhead->task_name, 0, sizeof(char)*32 ); Mhead->next = NULL; while( 1 ) printf("*首次适应算法实现主存分配和回收系统（存MSIZE）*n"); printf("|1:查看存分配情况n"); printf("|2:申请分配存n"); pr

14、intf("|3:申请回收存n"); printf("|4:退出程序n"); printf("*n"); scanf("%d",&func_); switch( func_ ) case 1 :showmemory();break; case 2 :memoallocate();break; case 3 :memoreturn();break; case 4 :return 1; system("cls"); 五.实验的输出结果/*首次适应算法实现主存分配和回收系统（存MSIZE）*

15、|1:查看存分配情况 |2:申请分配存 |3:申请回收存 |4:退出程序*1存的使用情况beginaddr length state task0k 128k CANUSE请按任意键继续. . . *2输入要分配存大小(kb):100输入任务名:1分配存成功请按任意键继续. . . *3输入要收回的任务名1存回收成功！请按任意键继续. . .*/-六.调试结果与分析 通过对可变分区管理方式下采用首次适应算法实现主存分配和回收算法的设计与分析，是我充分的认识了存的运作流程，存的分配与回收至关重要，因此存的分配算法也很重要，通过本次试验，我认识到作为一个系统工程师所要做的事情。实习三 磁盘存储空间的

16、分配和回收一、实习容模拟磁盘空闲空间的表示方法，以与模拟实现磁盘空间的分配和回收。二、实习目的磁盘初始化时把磁盘存储空间分成许多块（扇区），这些空间可以被多个用户共享。用户作业在执行期间常常要在磁盘上建立文件或把已经建立在磁盘上的文件删去，这就涉与到磁盘存储空间的分配和回收。一个文件存放到磁盘上，可以组织成顺序文件（连续文件）、文件（串联文件）、索引文件等，因此，磁盘存储空间的分配有两种方式，一种是分配连续的存储空间，另一种是可以分配不连续的存储空间。怎样有效地管理磁盘存储空间是操作系统应解决的一个重要问题，通过本实习使学生掌握磁盘存储空间的分配和回收算法。三、实习题目本实习有三个题目，可以任

17、选一个，但不能与存管理的题目类似。 连续磁盘存储空间的分配和回收提示：(1) 要在磁盘上建立顺序文件时，必须把按序排列的逻辑记录依次存放在磁盘的连续存储空间中。可假定磁盘初始化时，已把磁盘存储空间划分成若干等长的块（扇区），按柱面号和盘面号的顺序给每一块确定一个编号。随着文件的建立、删除、磁盘存储空间被分成许多区（每一区包含若干块），有的区存放着文件，而有的区是空闲的。当要建立顺序文件时必须找到一个合适的空闲区来存放文件记录，当一个文件被删除时，则该文件占用的区应成为空闲区。为此可用一空闲区表来记录磁盘存储空间未占用的部分，格式如下：序 号起始空闲块号空闲块个数状 态156未 分 配2143未

18、 分 配32130未 分 配4(2) 建立文件时，先查找空闲区表，从状态为“未分配”的表项中找出一个块数能满足要求的区，由起始空闲块号能依次推得可使用的其它块号。若不需要占用该区的所有块时，则剩余的块仍应为未分配的空闲块，这时要修改起始空闲块号和空闲块数。若占用了该区的所有块，则相应登记栏中的状态修改成“空表目”。删除一个文件时，需要考虑空闲块的合并情况。磁盘存储空间的分配和回收算法类似于主存储器的可变分区方式的分配和回收。同学们可参考实习二的第一题。(3) 当找到空闲块后，必须启动磁盘把信息存放到指定的块中，启动磁盘必须给出由三个参数组成的物理地址：盘面号、柱面号和物理记录号（即扇区号）。故

19、必须把找到的空闲块号换算成磁盘的物理地址。为了减少移臂次数，磁盘上的信息按柱面上各磁道顺序存放。现假定一个盘组共有200个柱面，（编号0-199）每个柱面有20个磁道（编号0-19，同一柱面上的各磁道分布在各盘面上，故磁道号即盘面号。），每个磁道被分成等长的6个物理记录（编号0-5，每个盘面被分成若干个扇区，故每个磁道上的物理记录号即为对应的扇区号）。那么，空闲块号与磁盘物理地址的对应关系如下：则 物理记录号=空闲块号 % 6磁道号=（空闲块号 / 6 ）% 20 柱面号=（空闲块号 / 6）/20(4) 删除一个文件时，从文件目录表中可得到该文件在磁盘上的起始地址和逻辑记录个数，假定每个逻辑

20、记录占磁盘上的一块，则可推算出归还后的起始空闲块号和块数，登记到空闲区表中。换算关系如下：起始空闲块号=（柱面号´20+磁道号）´6+物理记录号空闲块数=逻辑记录数(5) 请设计磁盘存储空间的分配和回收程序，要求把分配到的空闲块转换成磁盘物理地址，把归还的磁盘空间转换成空闲块号。要求能接受来自键盘的空间申请与释放请求，能显示或打印分配与回收后的空闲区表以与分配到的磁盘空间的起始物理地址：包括柱面号、磁道号、物理记录（扇区号）。四数据结构与流程 用到的数据结构 本程序用到的数据结构为空闲表，其组成元素为结构体，其中用来存空闲表的数组元素定义为： struct float ad

21、dress; /*分区起始地址*/ float lenth; /*空闲长度，单位为块*/ int flag; /*空闲表登记栏标志，用“0”表示空栏目，“1”表示未分配*/ tablen; /*空闲表*/ 其中实型address作为分区起始块号，用于记录个空闲分区的起始块号，在程序开始时，数组第0项address被初始化为0（默认起始块号）其他元素对应项在初始化是不赋值。第二项length表示所对应的项的长度，单位为块，在进程请求磁盘空间时，就是根据这一项大小为其分配合适的地址块，在初始化，第0元素该项被值为1000（默认地址块数），其他项不被置值，最后一项flag用于空闲表登记栏标志，用”0

22、”表示空栏目，表明此项不用于指示磁盘空闲区，则该项其他元素都无效，“1”表示未分配，表明此项其他元素代表磁盘区域，可用于分配给文件，在初始化实第0项被初始化为1，其他项被初始化为0，表示为空。 另一个结构体used_table，用于表示已分配表，从中可以看出已分配得的使用情况。其中address表示已分配分区起始块号，length表示已分配分区长度，单位为字节，在初始化使所有项该元素都不赋值，flag表示已分配区登记栏标志，用“0“表示空栏目，表明该项所有元素都无效，若不为0则代表该磁盘区域分配给的文件名，在初始化时由于没有文件，所以全为0。 (2)主程序流程 系统初始化，输入a的值。 选择需

23、要的服务类型。如a=1转，否则若a=2，转，否则若a=3转，否则退出。 输入文件的名字和所需空间大小，为其分配磁盘区域。转。 输入需要撤销的文件的名字，将其所占有的磁盘回收，转。 将磁盘空闲表和磁盘分配区表打印，转。 输入a的值，返回。 结束。 磁盘分配流程 输入文件的名字name和所需空间大小length，=0. 当i<n且right=0时，判断tablei.flag 是否为1且tablei.lengthlength，若满足则将right置为1，i项为分配的磁盘区域。 在空闲表中找一空标志项j，将其address置为tablei.address,长度为文件所需长度，flag置为文件名。

24、 将tablei.address置为tablei.address+length, tablei.length置为tablei.length-length. (4)磁盘回收流程 输入想撤销的文件的名字。 在used_table中寻找flag 为name的项。若找不到。则报错。若找到，继续， 将used_tablei的起始块号分别负给head，tail,用于判断磁盘中该区域的上下相临区域是否被占用，若无，则分情况将其合并。五.代码分析实现磁盘连续分配的算法choice (void)while(a = !4)if(a = 1)else if(a = 2)else if(a = 3)printf(&q

25、uot;请选择服务类型:"); scanf("%d",&a); 主函数测试： int main(void) for(i=0;i<n;i+) used_tablei.flag=0; /*已分配区表初始化*/ table0.address=0.0; table0.length=1000.0; table0.flag=1; /*空闲表初始化*/ for(i=1;i<m;i+) tablei.flag=0; printf("请选择服务类型 n"); printf("-请选择服务类型- n"); printf(" 1 调入新的文件n"); printf(" 2 收回文件磁盘空间 n"); printf(&