进程调度程序设计

word长 沙 学 院课程设计说明书题目进程调度程序设计系(部)计算机科学与技术系专业(班级)2009级数据库二班学号指导教师黄彩霞起止日期201264-201261519 / 26课程设计任务书课程名称：操作系统课程设计设计题目：进程调度程序设计技术参数和设计要求：1. 设计任务设计一个虚拟核，该核能支持多任务管理。提供创建进程、终止进程、进程状态转换，进程调度，上下文切换等功能。2. 问题描述2.1 系统组成系统由虚拟核(VKernel)、命令解释程序(mander)、用户程序Application、编译器piler四局部组成。VKernel首先运行，并常驻存。Kernel启动后，创建mander进程。根据用户请求创建多个Application进程。Kernel负责维护6个数据结构，包括时间 (Time), 处理器状态(CPUstate),进程表 (PCBTable), 就绪队列(ReadyState),等待队列(BlockedState),运行进程RunningState。Time是系统时间片。CPUstate应包括程序计数器PC,累加器A、B,状态存放器F的值。PCBTable的每一项为哪一项一个进程的进程控制块(PCB)。mander程序、Application程序是用如下CPU虚拟指令书写的程序： CPU虚拟指令(以下指令仅供参考, 设计者可以自行设计)MOV n /把整数n赋给累加器ASAV m /把累加器A的值存入地址MADD n /从累加器A的值减去整数n，结果送到累加器A。SUB n /从累加器A的值减去整数n，结果送到累加器A。MUL n /从累加器A的值乘以整数n，结果送到累加器A。DIV n /从累加器A的值除以整数n，结果送到累加器A。JEQ m /F为0跳转到mJLG m /F大于0跳转到mJLE m /F大于等于0跳转到mJMP m /无条件跳转到mOUT port /累加器的容输出到端口port。port为0，指显示器；为1，指扬声器。 虚拟系统调用(以下系统调用仅供参考, 设计者可自行设计)exec() /执行程序并创建子进程exit() /进程终止block() /进程等待printk() /在屏幕上打印系统信息scanf() /从键盘输入一字符串msg() /向核发送消息为了简化设计，复杂的系统调用当作广义指令处理。命令解释程序从标准输入重复读入用户命令,然后以消息形式发送给核。命令解释程序处理的命令由设计者定义并实现。2.3 编译器 编译器把虚拟指令和虚拟系统调用编译为可执行字节码。可执行字节码由核解释执行。3. 功能要求 应实现的功能有：(1)能接收用户提交的命令并执行该命令。(2)执行用户程序：创建进程、终止进程、调度进程、管理进程状态转换4. 技术要求采用时间轮转和优先级调度混合算法。优先级以优先数表示，优先数越大如此优先级越高。调度时，就绪队列中优先数最大的进程优先运行，一样优先数进程按FIFO方式调度。进程运行一个时间片以后,其优先数数减1即降低一级；进程在就绪队列中等待3个时间片以后，其优先数加1。优先数围031。5. 界面要求用户界面设计不做统一规定，但应做到界面友好，易于操作。6. 其他要求 编程语言和操作系统不限。4.课程设计时间：2周(2012.06.042012.6.15)5.课程设计的考核方式与评分方法(1) 考核方式课程设计完毕时，在机房当场验收。教师提供测试数据，检查运行结果是否正确。回答教师提出的问题。学生提交课程设计文档A4打印件,教师评阅。(2) 评分方法上机检查:书面报告:辩论=6:3:1，没有通过上机检查的或不提交课程设计报告的，其成绩直接记为不与格。指导教师签名：日期：系主任签名： 日期：学院课程设计鉴定表学号 2009021303专业计算科学与技术班级09数库2设计题目进程调度程序设计指导教师黄彩霞指导教师意见：评定等级： 教师签名： 日期：辩论小组意见：评定等级：辩论小组长签名：日期：教研室意见：教研室主任签名： 日期：系部意见：系主任签名：日期：说明课程设计成绩分“优秀、“良好、“与格、“不与格四类；摘要进程调度程序设计，主要是用于教学的一个程序设计。通过本程序完成达到一个对进程调度的核心原理与实现的深度理解的目的，同时也更加深入的了解计算机。该程序的虚拟核支持多进程。可以实现进程的创建，与进程的优先级调度等等功能。其中，这个蓄力核上并发执行是允许的，优先级调度是是键盘轮转算法和优先级调度算法的混合实现。进程运行一个时间片优先数降1；等待进程等待3个时间片后优先数加1。本次设计选择的是C语言，C语言一直是做底层开发的首先，所以这也是我本次设计选择该语言的原因。关键词：进程，并发，调度，优先级目录1设计容与要求1设计容：1设计要求：12设计说明2需求分析2方案设计2总体解决方案2根本核3核扩展3系统设计架构43根本编码5虚拟指令设计5和CPU设计54测试65总结8参考文献9附录程序源代码101 设计容与要求1.1 设计容：通过对操作系统课程的学习，利用所学的知识原理.设计一个虚拟核，该核能够实现先到先服务与时间轮转片算法的合理利用。能够支持多任务管理。提供创建进程、终止进程、进程状态转换，进程调度，上下文切换。1.2 设计要求：1) 功能要求：预期实现的功能：1能够接收用户提交的命令并执行该命令。2执行用户程序：创建进程、终止进程 3能够按照优先级和时间片实现调度进程、管理进程状态转换。2) 技术要求： 采用时间轮转和优先级调度混合算法。优先级以优先数表示，优先数越大如此优先级越高。调度时，就绪队列中优先数最大的进程优先运行，一样优先数进程按FIFO方式调度。进程运行一个时间片以后,其优先数数减1即降低一级；进程在就绪队列中等待3个时间片以后，其优先数加1。优先数围031。流程如如下列图3) 界面要求： 用户界面简洁。对程序输出速度做一定控制。输出字段简洁易于理解4) 其他要求在设计中须使用make工具建立工程。2 设计说明2.1 需求分析在多道程序系统中，一个进程作业被提交后必须经过处理机调度后，方能获得处理机执行。在较完善的操作系统中，进程调度程序按照一定的策略，动态的把处理机分配给处于就绪队列中的某一个进程，以使之执行。对于不同的调度都有都可以采用不同的调度方式和调度算法。在本程序设计中模拟进程调度中：根据所有的设计要求和容分析把整个设计分为三个局部：一个是伪指令的解释执行程序，二是伪调度算法、系统调用和文件输入，三是进程的创建与mian()函数的总体实现。系统由虚拟核(VKernel)、命令解释程序(mander)、用户程序Application、编译器piler四局部组成。命令解释程序从标准输入重复读入用户命令,然后以消息形式发送给核。命令解释程序处理的命令由设计者定义并实现。编译器把虚拟指令和虚拟系统调用编译为可执行字节码。可执行字节码由核解释执行。 最高优先数优先调度算法的根本思想是：将CPU分配给就绪队列中优先数最高的进程。采用动态优先数，即优先数在创定时由系统给定一个初始值，当进程获得一次CPU后其优先数就减1，然后把它插入就绪等待队列等待CPU 2.2 方案设计2.2.1 总体解决方案实验过程中遇到的问题与解决方案1) 动态优先调度算法与时间片轮转法调度算法的调度过程2) 链队列的相关3) 动态优先权调度算法设计思想：a) 先按优先数大小对就绪队列结点进展排序b) 队首元素为即将运行进程，恢复现场，把相应数据加载到程序计数器和累加器c) 运行队首进程d) 保护现场，把程序计数器和累加器的数据保存到PCBe) 查看其他进程的等待数，如果等待3个时间片，优先级数就增加1，同时把该进程等待数清0，取出运行的元素优先级减1，同时也把该进程的等待数清0.f) 进程假如在一个时间片运行完，如此停止该元素的运行，输出结果，同时把它从队列中去除，再按优先级大小排序。g) 重复2，3。4) 轮转法进程调度算法设计思想：a) 将所有就绪进程按照到达时间的先后顺序插入队列中。b) 取出队首元素运行一个时间片。c) 时间片到就停止该进程的执行，并将其插入队尾。d) 重复2，3。2.2.2 根本核设计分两步走，先实现一个简单的虚拟核，简单虚拟核运行无误后，再在上面扩展。简单虚拟核启动后直接把用户应用程序调入存运行，它只加载一个用户程序即单任务。应用程序也是最简单的，它计算100个自然数的和。用户程序的编译和加载过程如图1所示。代码登记加载编译用户源程序MOV 1ADD 2ADD 3ADD 4ADD 100程序字节码01 010002 020002 030002 040002 6400内存进程PCB表01 010002 020002 030002 040002 6400虚拟内核空闲内存这样的指令100条，计算1+2+100的和。注意，为了简化，简单内核只处理3条指令：MOV 传送指令ADD 加法指令 OUT 输出指令图1 进程加载示意图2.2.3 核扩展在上面根本核根底上扩展，增加10条指令，存放在cpl文件夹中。在编写一个.cpp程序，具有虚拟核能并发执行两个以上程序，基于优先数抢占调度(不含等待态)，指令10条以上(含跳转指令、系统调用)的功能。在typedef struct PCB PCB中，short A存放器A ，int PC 程序计数器PC，char *addr程序加载起始地址，int length程序大小，char name24进程名字，int priority;优先级数, 值为0-31，其中31为最高级，int cputime cpu运行时间，int needtime还需运行的时间state process为 ready,execute,finish三种状态PCB * next。PCB * get_process()用来加载用户程序；界面采用void display()函数，让用户根据自己的需要输入进程名和运行所需的时间；所需时间为0的时候进程完毕使用函数int process_finish()判断；void cpuexerun() 函数用来执行指令其中包含新增加的10条指令；void cpuexe()调用void cpuexerun()，并寻找优先级最高的执行；在main()中调用void priority_cal()将程序运行；最后将无误的.cpp文件和cpl文件夹放在同一目录下，执行程序是只需运行.cpp程序。2.2.4 系统设计架构3 根本编码233.1 CPU虚拟指令设计按照自理定规设计出一套虚拟指令，编写指令编译器，编译指令，3.2 PCB和CPU设计PCB栈的每一项为哪一项一个进程的进程控制块(PCB)，它需要定义存放器、程序计数器、程序加载起始地址、程序大小以与与进程有关的定义，如：进程名、运行所需要的时间、运行状况等等。而CPU包括程序计数器和累加器PCB具体设计如下：CUP具体设计如下：4 测试测试数据如下：A. 进程0计算1+2+3+8+9+10B. 进程1计算10个2相乘然后再除以5个4C. 进程2计算1+2+3+4+5-5-4-3-2-1预期结果为A. 进程0计算结果55B. 进程1计算结果1C. 进程2计算结果0三个进程初始化状态：由前面的需求分析可以得到测试要点：1. 优先数越大如此优先级越高。调度时，就绪队列中优先数最大的进程优先运行分析：进程2的优先级最高在该时间片中2号进程运行，所以测试结果正确。2. 一样优先数进程按FIFO方式调度分析：当进程0和1的优先级都为4时，由于0号进程先进入，所以执行0号进程，测试结果正确。3. 进程运行一个时间片以后,其优先数数减1即降低一级；进程在就绪队列中等待3个时间片以后，其优先数加1。优先数围031分析：连续4个时间片中，0号进程优先级降了3次，1号进程和2号进程的优先级在等待了3个时间片后都加了1。所以符合要求，测试成功！这都是时间片执行以前的截图，实际执行了3个时间片。4. 运行结果正确分析：最后输出结果与预期结果一样，测试成功。5 总结通过这两个周的学习，还是学到了不少的知识！首先是在计算机这个学科上的，不仅纠正了课程学习过程中出现的许多错误，还在试验中验证了自己的一些猜测。让我对操作系统有个更加深入的了解，对计算机的工作有了本质的认识。对计算机的理解不再停留在windows操作系统下的图形界面。在今天这绚丽的图形界面下，其实计算机的在还是想当初一样，是以做运算为核心。在这软硬件都飞速开展的今天，很多人都忘记了计算机的运转原理，这些底层的东西。这个学习将会成为我与其他人的不同，将成为我在社会竞争中的一个优势。其次是在人生领悟上。在学习的过程中有失败，当然也有困惑，有成功，当然就有喜悦。虽然只是课程设计，但我拿出了自己的全部精力去对待，能学到知识固然值得骄傲，能认识到自己的过错和不足不也是一件幸事吗！做学问也是做人，再作学问的过程中体味做人的道理不也是一种收获吗？记得古语中说：“学，然后知不足！希望这次学习只是我学习操作系统的开始，也算是启蒙吧！我必将更加努力的学习它完善自己。这就是我学习这门课的最大感受！参考文献附录 程序源代码C#ifndef _PILER_H_#define _PILER_H_#include iostream.h#include string.h#include stdio.h#define NOP 00/空指令: 消耗一个机器周期#define MOV 01 /传送指令：立即数赋值给存放器A#define ADD 02 /加法指令：存放器A加立即数#define MUL 03 /乘法指令：存放器A乘以立即数#define SUB 04 /减法指令：存放器A减去立即数#define DIV 05 /除法指令：存放器A除以立即数#define TTR 06 /取余指令：存放器A对立即数取余#define AAO 07 /自加1指令：存放器A自加一#define ASO 8 /自减1指令：存放器A自减一#define OUT 80/输出指令: 存放器A的值输出到端口(端口号01-表示显示器)#endifC/cpl.cpp-编译程序 (piler for Virtual Kernel)/版本：v1.0， 2010-06-24/把源程序编译为字节码程序/使用方法：cpl 源程序文件名 字节码文件名#include cpl.h/功能：提取一条指令并去掉空格/参数：buf-指令流, one-从指令流中取出的单条指令/返回：指令流余下的局部char * getcmd(char *buf,char *one)int i=0; /形参buf的下标int j=0; /形参one的下标while(1)while(bufi=0x20 | bufi=0x0d) i+; /去掉空格和换行符if(bufi=0x0a) i+; break; /指令以回车完毕onej=bufi; /复制指令i+; j+; /修改下标，准备下一字节onej=0; /添加完毕符return buf+i; /返回指令流余下的局部int main(int argc, char *argv)if(argc!=3) /判断命令行参数个数是否为3cout命令错。n命令用法：cpl 源程序文件名 字节码文件文件名n;return -1;FILE *fin; /流文件结构char *buf; /读缓冲fin=fopen(argv1,rb); /打开源程序文件if(fin=NULL) /假如打开失败cout找不到源文件。;return -1;fseek(fin,0L,SEEK_END); /读写指针移到文件末尾long fsize=ftell(fin); /求文件长度fseek(fin,0L,SEEK_SET); /读写指针移到文件开头buf=new charfsize; /分配读缓冲fread(buf,1,fsize,fin); /文件读入buf中FILE *fout; /流文件结构fout=fopen(argv2,wb); /打开源程序文件if(fout=NULL)/假如打开失败cout=fsize-2) break; /假如到达文件尾，如此跳出循环/=delete buf;fclose(fin);fclose(fout);return 0;V/vknl.h-Head File for virtual kernel/version 1.0, 2010-06-24#ifndef _VIRTUAL_KERNEL_#define _VIRTUAL_KERNEL_#include iostream.h#include string.h#include stdio.h#define NOP 00/空指令: 消耗一个机器周期#define MOV 01 /传送指令：立即数赋值给存放器A#define ADD 02 /加法指令：存放器A加立即数#define MUL 03 /乘法指令：存放器A乘以立即数#define SUB 04 /减法指令：存放器A减去立即数#define DIV 05 /除法指令：存放器A除以立即数#define TTR 06 /取余指令：存放器A对立即数取余#define AAO 07 /自加1指令：存放器A自加一#define ASO 8 /自减1指令：存放器A自减一#define OUT 80/输出指令: 存放器A的值输出到端口(端口号01-表示显示器)#define MAX_PID 10/系统并发运行的进程数的最大值/定义PCB结构类型typedef struct int pid; /进程号，值-1MAX_PID，-1表示无进程int A;/累加器Aint PC;/程序计数器PC char state;/进程状态：1-新建，2-就绪，3-运行, 4-等待，/05-完成int slice; /时间片大小。为简化，可设置执行几条指令为一个时间片int priority; /优先数, 值为0-31，其中31为最高级 /进程运行一个时间片以后,其优先数数减1即降低一级；/进程在就绪队列中等待3个时间片以后，其优先数加1。int changePri;/判断是否可以优先数加1char *addr;/程序加载起始地址int length;/程序大小PCB;typedef struct CPUint A; /累加器Aint PC; /程序计数器PC;int cur_pid;/当前_进程号int sum_pid; /进程数总和PCB pcbsMAX_PID;/进程控制块数组CPU cpu;/就是一个cpuvoid initSystem(void);/初始化系统int loadProgram(char *name);/加载应用程序void swish();/优先级排序void recover(); /恢复现场int exeInstruction();/执行指令void save();/保护现场void changes();/改变优先级void outState();/输出各个进程状态#endifV/vknl.cpp-virtual kernal/version 1.0, 2010-06-24, by Wendell/使用方法：vknl 字节码文件名#include vknl.h/初始化系统void initSystem(void)cur_pid=0;sum_pid=0;/加载应用程序int loadProgram(char *name)FILE *fin=fopen(name,rb); /打开源程序文件if(fin=NULL) return -1;/假如打开失败，返回-1fseek(fin,0L,SEEK_END); /文件读写指针移到文件末尾long fsize=ftell(fin); /求文件长度fseek(fin,0L,SEEK_SET); /读写指针移到文件开头PCB *pcb=pcbs+cur_pid;/获取当前进程PCBpcb-addr=new charfsize; /为新进程分配存fread(pcb-addr, fsize, 1, fin); /程序读入存fclose(fin); /关闭文件pcb-pid = cur_pid;cout请输入pid进程的优先级pcb-priority;/设置优先级pcb-length=fsize;/进程大小pcb-A=0; /初始化存放器pcb-PC=0;pcb-state = 1;pcb-slice=3;cur_pid+;sum_pid+;pcb-changePri = 0;return 0; /正常返回/优先级排序void swish()PCB temp;for (int i=0; ii; j-)if (pcbsj.prioritypcbsj-1.priority)temp = pcbsj-1;pcbsj-1 = pcbsj;pcbsj = temp; if (pcbsj.priority=pcbsj-1.priority)if (pcbsj.pidpcbsj-1.pid)temp = pcbsj-1;pcbsj-1 = pcbsj;pcbsj = temp; /进程优先级数判定改变/优先级输出for(i=0;isum_pid;i+)cout进程pcbsi.pid的优先级为pcbsi.priorityaddr+cpu.PC); /取操作码short op_dat=*(short*)(pcb-addr+cpu.PC+1); /取操作数/注意,我们约定操作数是16位整数，所以要定义为short。if(op_cmd=MOV)/传送指令cpu.A=op_dat;/操作数赋给累加器Aelse if(op_cmd=ADD)/加法指令cpu.A+=op_dat;/加计算else if (op_cmd=MUL)cpu.A*=op_dat;/乘法计算else if (op_cmd=SUB)cpu.A-=op_dat;/减法计算else if (op_cmd=DIV)cpu.A/=op_dat;/除法计算else if (op_cmd=TTR)cpu.A%=op_dat;/取余计算else if (op_cmd=AAO)cpu.A+;/自加1计算else if (op_cmd=AAO)cpu.A-;/自减法1计算else if(op_cmd=OUT)/输出指令cout_endl;cout进程pid计算结果cpu.Aendl;/输出累加器A的容cout_A = cpu.A;pcb-PC = cpu.PC;/改变优先级void changes()for(int i = 0;isum_pid;i+)if(pcbsi.pid=cur_pid)pcbsi.priority-;elseif(pcbsi.changePri=3)pcbsi.priority+;pcbsi.changePri=0;void outState()/输出各个进程状态cout*进程状态*endl;for(int i = 0;isum_pid;i+)if(pcbsi.state=1)cout进程pcbsi.pid当前状态为：新建endl;else if(pcbsi.state=2)cout进程pcbsi.pid当前状态为：就绪endl;else if(pcbsi.state=3)cout进程pcbsi.pid当前状态为：运行endl;else if(pcbsi.state=4)cout进程pcbsi.pid当前状态为：等待endl;elsecout进程pcbsi.pid当前状态为：完成endl;cout*endl;int main(int argc, char *argv) /argc 参数的个数 argv 参数的字符串形式的数组initSystem();/初始化系统for(int f=0;fargc;f+) loadProgram(argvf); /依次载入应用程序outState();/输出进程状态coutendl_分割线_endl;swish(); /优先级排序int x;int y=0;while(1)cur_pid=pcbs0.pid; recover(); /恢复现场/改变进程状态pcbs0.state=2;for(int i = 1;i PClength) /pclength进入循环，开始执行cout 所以该时间片 cur_pid 号进程执行指令。endl;/改变进程状态pcbs0.state=3;for(int i = 1;i sum_pid;i+)pcbsi.state=4;/-outState();for(x=0;xslice;x+)/按时间片大小执行指令3条exeInstruction();/执行指令save(); /保护现场if(pcb-PC=pcb-length) /执行完毕/改变进程状态pcbs0.state=5;for(int i = 1;i priority=0;delete pcb-addr; /清空、回收存pcbs0 = pcbssum_pid-1;sum_pid-;y+;/记录执行完的进程个数break; /当一个进程执行完后，跳出循环changes(); /改变优先级coutendl_分割线_endl;if(y=(argc-1) break; /进程全部执行完，跳出循环swish(); /优先级排序return 0;