长 沙 学 院
课程设计说明书
题系
(
部
目 )
进程调度程序设计 计算机科学与技术系 2009级数据库二班
黄彩霞
2012．6．4-2012．6．15
专业(班级) 姓学指起
名 号
导止
教日
师 期
课程设计任务书
课程名称：操作系统课程设计 设计题目：进程调度程序设计
已知技术参数和设计要求： 1. 设计任务
设计一个虚拟内核，该内核能支持多任务管理。提供创建进程、终止进程、进程状态转换，进程调度，上下文切换等功能。
2. 问题描述 2.1 系统组成
系统由虚拟内核(VKernel)、命令解释程序(Commander)、用户程序（Application）、编译器（Compiler）四部分组成。VKernel首先运行，并常驻内存。Kernel启动后，创建Commander进程。根据用户请求创建多个Application进程。Kernel负责维护6个数据结构，包括时间 (Time), 处理器状态(CPUstate),进程表 (PCBTable), 就绪队列(ReadyState),等待队列(BlockedState),运行进程（RunningState）。Time是系统时间片。CPUstate应包括程序计数器PC,累加器A、B,状态寄存器F的值。PCBTable的每一项是一个进程的进程控制块(PCB)。Commander程序、Application程序是用下列CPU虚拟指令书写的程序：
① CPU虚拟指令(以下指令仅供参考, 设计者可以自行设计) MOV n //把整数n赋给累加器A SAV m //把累加器A的值存入地址M
ADD n //从累加器A的值减去整数n，结果送到累加器A。 SUB n //从累加器A的值减去整数n，结果送到累加器A。 MUL n //从累加器A的值乘以整数n，结果送到累加器A。 DIV n //从累加器A的值除以整数n，结果送到累加器A。 JEQ m //F为0跳转到m JLG m //F大于0跳转到m JLE m //F大于等于0跳转到m JMP m //无条件跳转到m
OUT port //累加器的内容输出到端口port。port为0，指显示器；为1，指扬声器。 ② 虚拟系统调用(以下系统调用仅供参考, 设计者可自行设计) exec() //执行程序并创建子进程 exit() //进程终止 block() //进程等待
printk() //在屏幕上打印系统信息
1
scanf() //从键盘输入一字符串 msg() //向内核发送消息
为了简化设计，复杂的系统调用当作广义指令处理。 2.2命令解释程序
命令解释程序从标准输入重复读入用户命令,然后以消息形式发送给内核。命令解释程序处理的命令由设计者定义并实现。 2.3 编译器
编译器把虚拟指令和虚拟系统调用编译为可执行字节码。可执行字节码由内核解释执行。
3. 功能要求
应实现的功能有：(1)能接收用户提交的命令并执行该命令。(2)执行用户程序：创建进程、终止进程、调度进程、管理进程状态转换
4. 技术要求
采用时间轮转和优先级调度混合算法。优先级以优先数表示，优先数越大则优先级越高。调度时，就绪队列中优先数最大的进程优先运行，相同优先数进程按FIFO方式调度。进程运行一个时间片以后,其优先数数减1（即降低一级）；进程在就绪队列中等待3个时间片以后，其优先数加1。优先数范围0～31。
5. 界面要求
用户界面设计不做统一规定，但应做到界面友好，易于操作。
6. 其他要求
编程语言和操作系统不限。
4. 课程设计时间：2周(2012.06.04～2012.6.15) 5. 课程设计的考核方式及评分方法 (1) 考核方式
■ 课程设计结束时，在机房当场验收。
■ 教师提供测试数据，检查运行结果是否正确。 ■ 回答教师提出的问题。
■ 学生提交课程设计文档（A4打印件）,教师评阅。
(2) 评分方法
上机检查:书面报告:答辩=6:3:1，没有通过上机检查的或不提交课程设计报告的，其成绩直接记为不及格。
指导教师签名： 日期：
系主任签名： 日期：
2
长沙学院课程设计鉴定表
姓名 学号 专业 2009021303 进程调度程序设计 计算科学与技术 班级 09数库2 设计题目 指导教师意见： 指导教师 黄彩霞 评定等级： 教师签名： 日期： 答辩小组意见： 评定等级： 答辩小组长签名： 日期： 教研室意见： 教研室主任签名： 日期： 系（部）意见： 系主任签名： 日期： 3
说明 课程设计成绩分“优秀”、“良好”、“及格”、“不及格”四类； 4
摘要
进程调度程序设计，主要是用于教学的一个程序设计。通过本程序完成达到一个对进程调度的核心原理及实现的深度理解的目的，同时也更加深入的了解计算机。该程序的虚拟内核支持多进程。可以实现进程的创建，及进程的优先级调度等等功能。其中，这个蓄力内核上并发执行是允许的，优先级调度是是键盘轮转算法和优先级调度算法的混合实现。进程运行一个时间片优先数降1；等待进程等待3个时间片后优先数加1。
本次设计选择的是C语言，C语言一直是做底层开发的首先，所以这也是我本次设计选择该语言的原因。
关键词：进程，并发，调度，优先级
目录
1
设计内容与要求 .............................................................................................................................. 1 1.1 1.2 2
设计内容：........................................................................................................................... 1 设计要求：........................................................................................................................... 1
设计说明......................................................................................................................................... 2 2.1 2.2
需求分析 .............................................................................................................................. 2 方案设计 .............................................................................................................................. 2 2.2.1 2.2.2 2.2.3 2.2.4
总体解决方案............................................................................................................. 2 基本内核.................................................................................................................... 3 内核扩展.................................................................................................................... 3 系统设计架构............................................................................................................. 4
3 基本编码......................................................................................................................................... 5 3.1 3.2
CPU虚拟指令设计 ............................................................................................................... 5 PCB和CPU设计.................................................................................................................. 5
4 5
测试................................................................................................................................................ 6 总结................................................................................................................................................ 8
参考文献................................................................................................................................................ 9 附录 程序源代码 ..................................................................................................................................10
1 设计内容与要求
1.1 设计内容：
通过对操作系统课程的学习，利用所学的知识原理.设计一个虚拟内核，该内核能够实现先到先服务与时间轮转片算法的合理利用。能够支持多任务管理。提供创建进程、终止进程、进程状态转换，进程调度，上下文切换。
1.2 设计要求：
1) 功能要求： 预期实现的功能：
（1）能够接收用户提交的命令并执行该命令。 （2）执行用户程序：创建进程、终止进程
（3）能够按照优先级和时间片实现调度进程、管理进程状态转换。
2) 技术要求：
（采用时间轮转和优先级调度混合算法。优先级以优先数表示，优先数越大则优先级越高。调度时，就绪队列中优先数最大的进程优先运行，相同优先数进程按FIFO方式调度。进程运行一个时间片以后,其优先数数减1（即降低一级）；进程在就绪队列中等待3个时间片以后，其优先数加1。优先数范围0～31。流程如如图所示
3) 界面要求： 用户界面简洁。对程序输出速度做一定控制。输出字段简洁易于理解
4) 其他要求
在设计中须使用make工具建立工程。
1
2 设计说明
2.1 需求分析
在多道程序系统中，一个进程（作业）被提交后必须经过处理机调度后，方能获得处理机执行。在较完善的操作系统中，进程调度程序按照一定的策略，动态的把处理机分配给处于就绪队列中的某一个进程，以使之执行。对于不同的调度都有都可以采用不同的调度方式和调度算法。在本程序设计中模拟进程调度中：根据所有的设计要求和内容分析把整个设计分为三个部分：一个是伪指令的解释执行程序，二是伪调度算法、系统调用和文件输入，三是进程的创建及mian()函数的总体实现。
系统由虚拟内核(VKernel)、命令解释程序(Commander)、用户程序（Application）、编译器（Compiler）四部分组成。命令解释程序从标准输入重复读入用户命令,然后以消息形式发送给内核。命令解释程序处理的命令由设计者定义并实现。编译器把虚拟指令和虚拟系统调用编译为可执行字节码。可执行字节码由内核解释执行。
最高优先数优先调度算法的基本思想是：将CPU分配给就绪队列中优先数最高的进程。采用动态优先数，即优先数在创定时由系统给定一个初始值，当进程获得一次CPU后其优先数就减1，然后把它插入就绪等待队列等待CPU
2.2 方案设计
2.2.1 总体解决方案
实验过程中遇到的问题及解决方案
1) 动态优先调度算法与时间片轮转法调度算法的调度过程 2) 链队列的相关
3) 动态优先权调度算法设计思想：
a) 先按优先数大小对就绪队列结点进行排序
b) 队首元素为即将运行进程，恢复现场，把相应数据加载到程序计数器和累加器 c) 运行队首进程
d) 保护现场，把程序计数器和累加器的数据保存到PCB
e) 查看其他进程的等待数，如果等待3个时间片，优先级数就增加1，同时把该进
程等待数清0，取出运行的元素优先级减1，同时也把该进程的等待数清0. f) 进程若在一个时间片内运行完，则停止该元素的运行，输出结果，同时把它从队
列中清除，再按优先级大小排序。 g) 重复（2），（3）。
4) 轮转法进程调度算法设计思想：
a) 将所有就绪进程按照到达时间的先后顺序插入队列中。 b) 取出队首元素运行一个时间片。
c) 时间片到就停止该进程的执行，并将其插入队尾。 d) 重复（2），（3）。
2
2.2.2 基本内核
设计分两步走，先实现一个简单的虚拟内核，简单虚拟内核运行无误后，再在上面扩展。简单虚拟内核启动后直接把用户应用程序调入内存运行，它只加载一个用户程序（即单任务）。应用程序也是最简单的，它计算100个自然数的和。用户程序的编译和加载过程如图1所示。
用户源程序 MOV 1 ADD 2 ADD 3 ADD 4 ? ADD 100 编译 程序字节码 01 0100 02 0200 02 0300 02 0400 ? 02 6400 代码 01 0100 02 0200 02 0300 02 0400 这样的指令100条， 计算1+2+…+100的和。 注意，为了简化，简单内核只处理3条指令： MOV 传送指令 ADD 加法指令 OUT 输出指令 ? 02 6400 空闲内存 加载 登记 内存 虚拟内核 进程PCB表
图1 进程加载示意图
2.2.3 内核扩展
在上面基本内核基础上扩展，增加10条指令，存放在cpl文件夹中。在编写一个.cpp程序，具有虚拟内核能并发执行两个以上程序，基于优先数抢占调度(不含等待态)，指令10条以上(含跳转指令、系统调用)的功能。在typedef struct PCB{} PCB中，short A寄存器A ，int PC 程序计数器PC，char *addr程序加载起始地址，int length程序大小，char name[24]进程名字，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文件夹放
3
在同一目录下，执行程序是只需运行.cpp程序。
2.2.4 系统设计架构
开始加载所有进程加载所有进程,设置优先级对进程按优先级排序优先级最高的进程调入CPU，恢复现场，改变进程状态运行一个时间片当前进程优先级-1,等待进程优先级+1保护现场否所有进程执行完毕?是结束
4
3 基本编码
3.1 CPU虚拟指令设计
按照自理定规范设计出一套虚拟指令，编写指令编译器，编译指令，
3.2 PCB和CPU设计
PCB栈的每一项是一个进程的进程控制块(PCB)，它需要定义寄存器、程序计数器、程序加载起始地址、程序大小以及与进程有关的定义，如：进程名、运行所需要的时间、运行状况等等。
而CPU包括程序计数器和累加器 PCB具体设计如下：
CUP具体设计如下：
5
4 测试
测试数据如下：
A. 进程0计算1+2+3+??+8+9+10
B. 进程1计算10个2相乘然后再除以5个4 C. 进程2计算1+2+3+4+5-5-4-3-2-1 预期结果为
A. 进程0计算结果55 B. 进程1计算结果1 C. 进程2计算结果0 三个进程初始化状态：
由前面的需求分析可以得到测试要点：
1. 优先数越大则优先级越高。调度时，就绪队列中优先数最大的进程优先运行
分析：进程2的优先级最高在该时间片中2号进程运行，所以测试结果正确。 2. 相同优先数进程按FIFO方式调度
6
分析：当进程0和1的优先级都为4时，由于0号进程先进入，所以执行0号进程，测试结果正确。
3. 进程运行一个时间片以后,其优先数数减1（即降低一级）；进程在就绪队列中等待3个时间片以
后，其优先数加1。优先数范围0～31
分析：连续4个时间片中，0号进程优先级降了3次，1号进程和2号进程的优先级在等待了3个时间片后都加了1。所以符合要求，测试成功！（这都是时间片执行以前的截图，实际执行了3个时间片）。
4. 运行结果正确
分析：最后输出结果与预期结果相同，测试成功。
7
5 总结
通过这两个周的学习，还是学到了不少的知识！首先是在计算机这个学科上的，不仅纠正了课程学
习过程中出现的许多错误，还在试验中验证了自己的一些猜想。让我对操作系统有个更加深入的了解，对计算机的工作有了本质的认识。对计算机的理解不再停留在windows操作系统下的图形界面。在今天这绚丽的图形界面下，其实计算机的内在还是想当初一样，是以做运算为核心。在这软硬件都飞速发展的今天，很多人都忘记了计算机的运转原理，这些底层的东西。这个学习将会成为我与其他人的不同，将成为我在社会竞争中的一个优势。
其次是在人生领悟上。在学习的过程中有失败，当然也有困惑，有成功，当然就有喜悦。虽然只是
课程设计，但我拿出了自己的全部精力去对待，能学到知识固然值得骄傲，能认识到自己的过错和不足不也是一件幸事吗！做学问也是做人，再作学问的过程中体味做人的道理不也是一种收获吗？记得古语中说：“学，然后知不足”！希望这次学习只是我学习操作系统的开始，也算是启蒙吧！我必将更加努力的学习它完善自己。这就是我学习这门课的最大感受！
8
参考文献
[1] 孙钟秀、费翔林、骆斌《操作系统（第四版）》.高等教育出版社.2008 [2] 严蔚敏、吴伟民 《数据结构（c语言版）》.清华大学出版社.2007 [3] 王挺、周会平、贾丽丽、徐锡山《c++程序设计）》.清华大学出版社.2005
9
附录 程序源代码
Cpl.h
#ifndef _COMPILER_H__ #define _COMPILER_H__
#include \#include \#include \
#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--表示显示器) #endif
Cpl.cpp
//cpl.cpp--编译程序 (Compiler for Virtual Kernel) //版本：v1.0， 2010-06-24
//把源程序编译为字节码程序
//使用方法：cpl 源程序文件名 字节码文件名
#include \
//功能：提取一条指令并去掉空格
//参数：buf--指令流, one--从指令流中取出的单条指令 //返回：指令流余下的部分 char * getcmd(char *buf,char *one) {
int i=0; //形参buf的下标 int j=0; //形参one的下标
while(1) { while(buf[i]==0x20 || buf[i]==0x0d) i++; //去掉空格和换行符 if(buf[i]==0x0a) {i++; break;} //指令以回车结束
10
}
one[j]=buf[i]; //复制指令
i++; j++; //修改下标，准备下一字节
}
one[j]=0; //添加结束符
return buf+i; //返回指令流余下的部分
int main(int argc, char *argv[]) {
if(argc!=3) //判断命令行参数个数是否为3 { }
cout<<\命令错。\\n命令用法：cpl 源程序文件名 字节码文件文件名\\n\return -1;
FILE *fin; //流文件结构 char *buf; //读缓冲
fin=fopen(argv[1],\打开源程序文件 if(fin==NULL) //若打开失败 {
cout<<\找不到源文件。\
return -1; }
fseek(fin,0L,SEEK_END); //读写指针移到文件末尾 long fsize=ftell(fin); //求文件长度
fseek(fin,0L,SEEK_SET); //读写指针移到文件开头 buf=new char[fsize]; //分配读缓冲 fread(buf,1,fsize,fin); //文件读入buf中
FILE *fout; //流文件结构
fout=fopen(argv[2],\ //打开源程序文件 if(fout==NULL) //若打开失败 { }
cout<<\找不到目标文件。\fclose(fin); return -1;
char *p=buf; //临时指针 char cmd; //操作码
11
short data; //操作数 int i=0; //数组下标 char one[128];//用于存放单条指令
while(1) { p=getcmd(p,one); //提取一条指令并去掉空格 }
12
if( strncmp(one,\ cmd=MOV;
else if( strncmp(one,\ cmd=ADD; else if( strncmp(one,\ cmd=OUT; else if( strncmp(one,\ cmd = MUL; else if( strncmp(one,\ cmd = SUB; else if( strncmp(one,\ cmd = DIV;
else if( strncmp(one,\ cmd = TTR;
else if( strncmp(one,\ cmd = AAO;
else if( strncmp(one,\ cmd = ASO;
fwrite(&cmd,1,1,fout); //操作码存盘
//if(cmd!=PRT) { data=0; i=3; while(one[i]!=0) //求操作数
{
data*=10;
data+=one[i]-0x30; //ASCII转为10进制数 i++;
}
fwrite(&data,1,2,fout); //操作数存盘
}
if(p-buf>=fsize-2) break; //若到达文件尾，则跳出循环
}
//=================== delete [] buf; fclose(fin); fclose(fout);
return 0;
Vknl.h
//vknl.h--Head File for virtual kernel //version 1.0, 2010-06-24
#ifndef __VIRTUAL_KERNEL__ #define __VIRTUAL_KERNEL__
#include \#include \#include \
#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; //进程号，值-1～MAX_PID，-1表示无进程 int A; //累加器A
int PC;
//程序计数器PC
char state;
//进程状态：1--新建，2--就绪，3--运行, 4--等待， //05--完成
int slice; //时间片大小。为简化，可设置执行几条指令为一个时间片
int priority; //优先数, 值为0--31，其中31为最高级
//进程运行一个时间片以后,其优先数数减1（即降低一级）； //进程在就绪队列中等待3个时间片以后，其优先数加1。
int changePri;//判断是否可以优先数加1
13
}
}
//改变进程状态 pcbs[0].state='3';
for(int i = 1;i < sum_pid;i++) pcbs[i].state='4';
//----------- outState();
for(x=0;x
exeInstruction();//执行指令
save(); //保护现场
if(pcb->PC>=pcb->length) //执行完毕 {
//改变进程状态
pcbs[0].state='5';
for(int i = 1;i < sum_pid;i++) pcbs[i].state='4'; //-----------
outState();
pcb->priority=0;
delete [] pcb->addr; //清空、回收内存
pcbs[0] = pcbs[sum_pid-1]; sum_pid--;
y++; //记录执行完的进程个数 break; //当一个进程执行完后，跳出循环
}
}
changes(); //改变优先级
cout< } if(y==(argc-1)) break; //进程全部执行完，跳出循环 swish(); //优先级排序 return 0; 19
