动态优先数进程调度模拟程序操作系统课程设计.doc

题目： 动态优先数进程调度模拟程序 课程设计任务书及成绩评定课程设计的任务和具体要求一、实验目的观察、体会操作系统的进程调度方法，并通过一个简单的进程调度模拟程序的实现，加深对进程调度算法，进程切换的理解。 二、实验内容采用动态优先数的方法，编写一进程调度程序模拟程序。模拟程序只进行相应的调度模拟操作。指导教师签字： 日期： 指导教师评语成绩： 指导教师签字： 日期： 课程设计所需软件、硬件等本次课程设计主要分为操作题和编程设计题，主要考查同学们对LINUX的掌握的熟练程度，以及用语言来模拟操作系统的主要功能的能力。所以，规定试验环境如下：系统：Windows XP上的虚拟机上运行的Red Hat Linux语言：C/C+开发工具：GCC课程设计进度计划起至日期工作内容备注6.136.14-6.156.16分析题目并查资料开始着手写程序调试并完成程序明确算法所要实现的功能编写功能函数调试成功参考文献、资料索引序号文献、资料名称编著者出版单位1 C程序设计（第三版） 谭浩强 清华大学出版社2 数据结构（C语言版） 严蔚敏 吴伟民 清华大学出版社3 计算机操作系统（修订版）汤子瀛 哲风屏 汤小丹 西安电子科技大学出版社10目录一、引言2Linux的出现2Linux内核2基本思想3二、Linux系统常用基本命令介绍31. Linux目录管理有关命令32.更改目录或文件访问权限的命令33.显示文件内容的命令44.文件管理命令45.vi操作的方式（几个常用键）4三.进程调度程序的设计51处理机调度52.优先权调度算法53.程序的设计思路54程序代码75.程序运行情况10四实验过程中出现的问题及解决方法12五总结12一、引言Linux的出现最早开始于一位名叫Linus Torvalds的计算机业余爱好者，当时他是芬兰赫尔辛基大学的学生。他的目的是想设计一个代替Minix（是由一位名叫Andrew Tannebaum的计算机教授编写的一个操作系统示教程序）的操作系统，这个操作系统可用于386、486或奔腾处理器的个人计算机上，并且具有Unix操作系统的全部功能，因而开始了Linux雏形的设计。 最初的设想中，Linux 是一种类似Minix这样的一种操作系统。1991年4月，芬兰赫尔辛基大学学生Linus Benedict Torvalds（当今世界最著名的电脑程序员、黑客）不满意Minix这个教学用的操作系统。出于爱好，他根据可在低档机上使用的MINIX设计了一个系统核心Linux 0.01，但没有使用任何MINIX或UNIX的源代码。他通过USENET（就是新闻组）宣布这是一个免费的系统，主要在x86电脑上使用，希望大家一起来将它完善，并将源代码放到了芬兰的FTP站点上任人免费下载。本来他想把这个系统称为freax，意思是自由（ free） 和奇异（freak） 的结合字，并且附上了X这个常用的字母，以配合所谓的Unix-like的系统。可是FTP的工作人员认为这是Linus的MINIX，嫌原来的命名“Freax”的名称不好听，就用Linux这个子目录来存放，于是它就成了“Linux”。由于许多专业用户（主要是程序员）自愿地开发它的应用程序，并借助Internet拿出来让大家一起修改，所以它的周边的程序越来越多，Linux本身也逐渐发展壮大起来。 Linux内核绝大多数基于Linux内核的操作系统使用了大量的GNU软件，包括了shell程序、工具、程序库、编译器及工具，还有许多其他程序，例如Emacs。正因为如此，GNU计划的开创者理查德马修斯托曼博士提议将Linux操作系统改名为GNU/Linux。但有些人只把操作系统叫做Linux。 基本思想Linux的基本思想有两点：第一，一切都是文件；第二，每个软件都有确定的用途。其中第一条详细来讲就是系统中的所有都归结为一个文件，包括命令、硬件和软件设备、操作系统、进程等等对于操作系统内核而言，都被视为拥有各自特性或类型的文件。至于说Linux是基于Unix的，很大程度上也是因为这两者的基本思想十分相近。 过去，Linux主要被用作服务器的操作系统，但因它的廉价、灵活性及Unix背景使得它很合适作更广泛的应用。传统上有以Linux为基础的“LAMP（Linux, Apache, MySQL, Perl/PHP/Python的组合）”经典技术组合，提供了包括操作系统、数据库、网站服务器、动态网页的一整套网站架设支持。而面向更大规模级别的领域中，如数据库中的Oracle、DB2、PostgreSQL，以及用于Apache的Tomcat JSP等都已经在Linux上有了很好的应用样本。除了已在开发者群体中广泛流行，它亦是现时提供网站务供应商最常使用的平台。二、Linux系统常用基本命令介绍1. Linux目录管理有关命令（1）pwd -显示当前工作目录的绝对路径格式: pwd （2）cd -改变当前工作目录命令格式：cd 目录名 （3）Ls- 列出文件目录的信息命令格式：ls 可选项 子目录名 文件名（4）mkdir - 建立目录命令格式：mkdir 可选项 目录名 （5）rmdir -删除目录本命令用于删除指定的一个或多个目录，必须保证要删除的目录中没有任何文件。命令格式：rmdir 可选项 目录名 2.更改目录或文件访问权限的命令 （1）Ls-查看访问权限格式: ls l 文件名（2） chmod -改变文件或目录的访问权限 命令格式：chmod 可选项 权限 目录或文件名 （3）chgrp命令 -改变文件或目录所属的组。 命令格式：chgrp 选项 group filename选项： -R：递归式地改变指定目录及其下的所 有子目录和文件的属组 （4） chown -更改某个文件或目录的属主和属组 命令格式：chown 选项 文件或目录的新属主.文件或目录所在的新组 文件名|目录 3.显示文件内容的命令（1） cat -显示，新建，连接文件（2） more -在终端屏幕按屏显示文本文件。 命令格式： more - 选项 文件 （3）Head-显示文件或标准输入的头几行 命令格式：head - n 文件 （4）tail-显示文件的尾部 命令格式：tail + / - num 参数 文件 4.文件管理命令（1）touch -功能：将文件的修改时间改为当前时间，如果文件不存在则建立一个空文件。 命令格式： touch - 选项 文件 （2） cp -功能：文件或目录的拷贝 ，如同dos的copy 命令格式： cp 选项 源文件或目录 目标文件或目录 （3） mv -功能：为文件或目录改名或将文件由一个目录移入另一 个目录中 命令格式： mv 选项 源文件或目录 目标文件或目录 （4） rm -功能：删除一个目录中的一个或多个文件或目录，它也可以将某个目录及其下的所有文件及子目录均删除 命令格式： rm 选项 文件 5.vi操作的方式（几个常用键）进入vi开始编辑：$vi 新文件名例如：$vi newfile （打开名为newfile的旧文档，或新编一个名为newfile的新文档）刚开启vi时为命令模式，按下【i, I, o, O, a, A, r, R】等字母之后会进入编辑模式。编辑完毕按下【ESC】返回命令模式操作；在命令模式中按下【:】或【/】可进入指令列模式。在指令列模式中（有【:】提示时），可输入w（存档）、q（离开vi）、wq（存档并离开vi）、q!（不存档离开vi）、h或help（在线说明）、以及其它搜寻取代等指令。再按【ESC】回到命令模式。即： :w- 将编辑的文本存盘。:w!- 若文件属性为“只读”时，强制存盘:q- 退出 vi :q!-退出且不存盘。:wq-存盘并退出三.进程调度程序的设计1处理机调度处理机调度的基本概念:在多道程序环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。进程调度的任务:控制协调进程对CPU的竞争,即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。进程调度方式：非抢占方式：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。抢占方式：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。2.优先权调度算法该算法总是把处理机分配给就绪队列中具有最高优先权的进程。优先权调度算法类型：非抢占式、抢占式优先权算法。优先权类型：静态优先数法：静态优先权是在创建进程时确定的，在整个运行期间不再改变。动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。3.程序的设计思路（1）总体设计方案本程序采用模块化设计方法，来模拟实现动态优先数进程调度模拟。其中包括进程的创建模块、进程队列的排序模块、进程的运行模块以及进程的输出模块四个模块。通过模拟进程调度的效果来实现动态优先数进程调度模拟（只进行相应的调度模拟操作）。（2）模块的设计1进程队列的创建进程结点的构建我们将每一个进程用一个进程控制块PCB来代表，在程序中采用结构体来表示一个PCB，PCB结点结构如下：typedef struct PCB进程名；指针；要求运行时间；优先数；状态；其中，进程名作为进程的标识，假设五个进程的进程名分别为P1，P2，P3，P4，P5。指针按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“0”。要求运行时间假设进程需要运行的单位时间数。优先数赋予进程的优先数，调度时总是选取优先数大的进程先执行。状态可假设有两种状态，“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”，用“R”表示，当一个进程运行结束后，它的状态为“结束”，用“E”表示。进程队列的初始化采用带头结点的单链表将各个进程链接成一个链表队列。算法如下：Createlist()开辟头结点的指针域置空；for ( )开辟进程节点，并输入初值；节点插入到表头；返回；2进程队列按优先数由大到小排序此时需分为两个函数，一个是用于首次排序，是将一个无序链表按优先数由大到小排列。另一个是将单个进程节点按原有的规则插入到有序链表中。两函数的算法如下：首次排序的算法：inorder(PCB *pro)开辟新的头结点；用指针r指向待插入的进程节点；q 指向有序表的尾节点；while(r-next!=null)把待插入的进程节点在有序表中找到正确的位置插入；各个指针作出相应的调整；单节点的插入算法onep(PCB *p,PCB *q)将p所指向的进程节点插入到q链表中，依然按照优先数由大到小的顺序排列；3进程的运行过程处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减“1”。由于本实习是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行：优先数-1要求运行时间-1来模拟进程的一次运行。同时，链表队列中等待的所有进程的优先权都加“1”。运行算法如下：PCB *run(PCB *p)取队首进程作相应操作并将原链表队列指针作出相应调整；若运行一次后的进程要求运行的时间不为0，则调用onep(PCB *p,PCB *q)函数再将其插入；否则将它的状态位置为e,并调用printe(r)函数输出结束进程；若链表队列不为空，则调用printr(p)函数输出就绪进程；4进程的输出进程的输出又分为结束进程的输出函数printe()和链表中等待运行的就绪进程的输出函数printr()输出相应的进程。4程序代码本程序分为四个文件，c1.h和c2.h为头文件，c3.c为实现相应功能的功能函数，main.c为主函数，各个文件的源代码如下：c1.h#include#include#include#include#define true 1#define false 0#define overflow -2#define ok 1#define null 0c2.htypedef struct PCBchar id3;int time;int pri;char sta;struct PCB *next;PCB,*plist;c3.cplist creatlist() /*建立进程队列*/ int i; plist p; pro=(plist)malloc(sizeof(PCB); pro-next=null; for(i=0;iid,&p-time,&p-pri); scanf(%c); (*p).sta=r; p-next=pro-next;pro-next=p; return(pro);PCB *linsert(PCB *p1,PCB *p2,PCB *p3) /*插入进程*/ PCB *p4,*p5; for(p4=p3-next,p5=p3;p1-pripri&p4-next!=null;p4=p4-next,p5=p5-next); if(p4-next=null) if(p1-pripri) p2-next=p1; p2=p2-next; else p5-next=p1; p5-next-next=p4; else p5-next=p1; p5-next-next=p4; p2-next=null; return(p3);PCB *lastp(PCB *p,PCB *q) /*单个进程的插入*/q-next=p; q-next-next=null; return(q);plist sort(PCB *pro) /*按优先数由大到小排序*/plist p,q,r,s,t;r=pro;r=r-next;p=(plist)malloc(sizeof(PCB);p-next=null;q=p;while(r-next!=null)if(r!=pro-next)for(s=p-next,t=p;r-pripri&s!=null;t=t-next,s=s-next) ;if(q-next=s&q-pri=s-pri)q-next=r; q=q-next;r=r-next;q-next=null;else t-next=r; r=r-next; t-next-next=s;else q-next=r; q=q-next;r=r-next; q-next=null;for(q=p;q-next!=null;q=q-next);p=linsert(r,q,p);printr(p) ;return(p);PCB *run(PCB *p) /*进程运行过程*/static int i=1;PCB *q,*r;r=p-next;r-time-;r-pri-;if(p-next-next!=null)p-next=r-next;for(q=p-next;q-next!=null;q=q-next) q-pri+; q-pri+; if(r-time!=0) p=linsert(r,q,p); if(p-next!=null) printf(di %d ci yun xing hou ,i+); printr(p); if(r-time=0) r-sta=e; printe(r); return(p);elsep-next=null;if(r-time!=0) p=lastp(r,p);if(p-next!=null) printf(di %d ci zhi xing hou ,i+); printr(p); if(r-time=0) r-sta=e; printe(r); return(p);printe(PCB *p) /*输出结束进程*/printf(jie shu de jin cheng:n); printf( id time pri stan); printf( %s %d %d %cn,p-id,p-time,p-pri,p-sta);ge