实验报告
学院（系）名称： 计算机与通信工程学院
姓名 nasta 学号 nasta 专业 计算机科学与技术
班级 2010 级 2 班 实验项目 实验一：处理机调度算法的实现
课程名称 操作系统 课程代码 0668036
实验时间 2012 年 12 月 3 日 第 3、4 节 实验地点 软件实验室 7-216
批改意见 成绩
教师签字：
实验内容：
1． 设定系统中有五个进程，每一个进程用一个进程控制块表示。
2． 输入每个进程的“优先数”和“要求运行时间” 。
3． 为了调度方便，将五个进程按给定的优先数从大到小连成就绪队列。用一单元指出队列首进程，用
指针指出队列的连接情况。
4． 处理机调度总是选队首进程运行。采用动态优先数算法，进程每运行一次优先数就减“ 1”，同时将
运行时间减“ 1”。
5． 若某进程运行时间为零，则将其状态置为“结束” , 且退出队列。
6． 运行所设计程序，显示或打印逐次被选中进程的进程名，以及进程控制块的动态变化过程。
实验要求：
1． 详细描述实验设计思想、程序结构及各模块设计思路；
2． 详细描述程序所用数据结构及算法；
3． 明确给出测试用例和实验结果；
4． 为增加程序可读性，在程序中进行适当注释说明；
5． 认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等；
6． 实验报告撰写要求结构清晰、描述准确逻辑性强；
7． 实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。
第1页共5页
【实验过程记录（源程序、测试用例、测试结果及心得体会等） 】
设计思想：
模拟单 CPU 系统时间片切换、进程切换。
使用优先队列，让优先级高的进程位于队列顶端。
在每次时钟周期时，从优先队列队首取出优先级最高的进程，并使其运行一个时钟周期，然后将其优先级减 1，已运行时间加 1。然后判断程序是否完成，如果未完成，则重新加入优先队列，参与时钟周期。
数据结构：
使用优先队列，以获得优先级最高程序。
源代码：
#include <cstdio>
#include <queue>
using namespace std;
进程控制块 PCB
structPCB {
unsigned
int
pid;
// 进程 id
unsigned
int
priority;
// 进程优先级
unsigned
int
claimTime;
// 需要运行时间
unsigned
int
runTime;
// 已经运行时间
构造函数
PCB( unsigned int id , unsigned int p, unsigned int ct ) {
pid= id ;
priority= p ;
claimTime= ct ;
runTime=0;
}
运行当前进程一个时钟周期，并使进程优先级减 1，已运行时间加 1 void run() {
runTime++;
if (priority>0)priority--;
}
判断进程是否完成
bool isFinished() {
if (claimTime==runTime)
return true ;
else return false ;
}
第2页共5页
// 重载 <运算符，以使用 STL 中的 priority_queue
bool operator <( const PCB& p ) const {
if (priority!= p.priority)
return priority< p.priority; // 比较优先级
else
优先级相同的话快完成的任务先执行
return claimTime-runTime< p.claimTime- p.runTime;
}
};
int main( int argc , char ** argv ) {
int clock=0;
priority_queue <PCB> q; // 优先队列
for ( int i=0; i<5; i++) {
int p, t;
printf( " 请输入 pid=%u 的进程的优先级（非负数） :\n" , i); scanf( "%u" , &p);
printf( " 请输入 pid=%u 的进程的要求运行时间（非负数） :\n" , i); scanf( "%u" , &t);
printf( "pid = %u, 优先级 = %u, 要求运行时间 = %u\n\n" , i, p, t);
q.push( PCB(i, p, t));
}
while (!q.empty()) { // 模拟单 CPU
printf( " 当前时钟 %2d\t" , clock++);
PCB t = q.top();
q.pop();
printf( "pid = %u 进程运行 , 优先级 = %u, 已运行时间 = %u\n" , t.pid, t.priority, t.runTime);
t.run();
printf( " 执行过后： \tpid = %u, 优先级 = %u, 已运行时间 = %u\n" , t.pid,
t.priority, t.runTime);
if (!t.isFinished())
q.push(t);
else
printf( "pid=%d 进程结束 \n" , t.pid);
}
printf( " 程序结束 \n" );
return 0;
}
测试用例：
进程 pid
优先级
需要运行时间
0
4
3
1
1
4
2
5
4
3
3
6
4
2
2
第3页共5页
执行结果：
第4页共5页
实验问题：
在进程优先级相同时，调度结果不确定。原因：在优先级相同时，未进行相关处理。
解决：添加优先级相同时判断逻辑，快结束的进程先调度
程序陷入死循环。
原因：当忘记判断进程是否结束就加入队列。
解决：判断进程是否结束，如果未结束，则继续参与调度，否则不参与。
实验总结：
要根据调度算法，选择合适的数据结构，以实现相应的调度程序。在调度时，应明确：哪个程序被调度，调度后优先级有什么变化，该进程是否还参与调度等问题。
第5页共5页