操作系统课程设计之进程调度.doc

操作系统课程设计之进程调度

———————————————————————————————— 作者：
———————————————————————————————— 日期：

2

个人收集整理 勿做商业用途
目录
一． 成绩评定表
二． 任务书
三． 计目的意义、设计内容
四． 计方案（软硬件环境，开发工具或语言选择及思路）
五． 程序功能模块设计(程序功能模块划分及层次等）
六． 程序总控流程图
七． 数据结构设计
八． 程序代码结构（函数调用关系或类层次关系）
九． 程序主要代码解析
十． 测试数据及测试结果
十一．设计过程中遇到的问题及解决方法
十二．结论(系统实现情况、系统特点、设计体会及收获等）
十三. 目前资料收集情况(含指定参考资料）

二．任务书：
课程设计题目
模拟进程调度功能的设计与实现
学院
计算机学院
专业
计算机科学与技术专业
年级
2006级
已知参数和设计要求：
运用课堂学习的操作系统理论知识，参考操作系统课程里讲述的文件系统有关算法，用C、C++或JAVA语言编程，模拟实现普通操作系统的进程调度功能。本课程设计目的如下：
1)编程实现模拟操作系统进程调度子系统的基本功能；理解进程调度的概念，通过课程设计深入了解进程控制块的功能、进程的创建、删除以及进程各个状态间的转换过程；实现先来先服务、时间片轮转、多级反馈轮转法对进程进行的调度过程；通过观察有关的队列结构的内容的动态变化过程深入体会各个调度算法的特点;从而能够更好的巩固从书本上学到的知识.
2）编程过程中需要建立队列等结构进行各种操作，通过该次试验,可以督促学生从实用的角度对《数据结构》课程内容进行更深入理解和更熟练的应用.
3）实验编程语言要求使用java语言或C++语言。通过对调度功能的编程实现，不但能有效训练学生对编程语言的熟练使用，还能促进学生独立思考解决问题、以及独立查新获取知识的能力.

操作系统课程设计报告要求：
按要求格式和纸张写出设计报告，报告正文内容如下：
1、 设计目的意义、设计内容
2、 设计方案(软硬件环境，开发工具或语言选择及思路等）
3、程序功能模块设计(程序功能模块划分及层次等）
4、程序总控流程图
4、数据结构设计
6、程序代码结构（函数调用关系或类层次关系）
7、程序主要代码解析
8、测试数据及测试结果
9、设计过程中遇到的问题及解决方法
10、结论（系统实现情况、系统特点、设计体会及收获等。）
报告字数要求：3000

评分标准
（1）设计报告情况； （2）、运行演示情况;
（3)教师质疑回答情况； （4）、算法难易程度； (5）、协作配合情况
学生应完成的工作：
实现进程调度子系统如下功能模块：
1）实现进程相关数据结构（如进程控制块task_struct）的创建和查看功能。
2）实现多种进程调度算法:先来先服务算法、优先级调度算法、时间片轮转法、多级反馈轮转法等。
3）实现对执行进程的阻塞,对等待进程的唤醒等功能。
4）实现相关队列在进程调度中的动态变化过程。

分组要求：可按班级自由组合小组成员,一组2—3人组成。
注意：
希望同组同学分工明确，团结协作。每位同学需交课程设计报告(主要写自己负责部分）。

小组成员及分工情况:由学生填写
目前资料收集情况（含指定参考资料):

著作:[1] 张尧学,史美林.计算机操作系统教程第2版.清华大学出版社2000年
著作：［2］ 张尧学。计算机操作系统教程第2版 习题与实验指导。2000年

课程设计的工作计划：
课程设计的时间为一周，上机时间共20学时。工作计划如下:
星期一:准备工作，理解、分析设计要求.总体方案设计，确定组内分工.
星期二:程序模块结构设计,模块层次调用关系、模块之间接口约定.
星期三：程序设计、模块测试。
星期四：程序设计、模块集成；总体测试；写课程设计报告.
星期五：完善程序和报告。向老师提交课程设计报告和程序。

任务下达日期 2009年 6月 20 日
完成日期 2009 年 6月 26 日
指导教师 (签名）
学 生 （签名）

三．设计目的意义、设计内容
1． 编程实现模拟操作系统进程调度子系统的基本功能；理解进程调度的概念，通过课程设计深入了解进程控制块的功能、进程的创建、删除以及进程各个状态间的转换过程；实现先来先服务、时间片轮转、多级反馈轮转法对进程进行的调度过程;通过观察有关的队列结构的内容的动态变化过程深入体会各个调度算法的特点;从而能够更好的巩固从书本上学到的知识.
2． 编程过程中需要建立队列等结构进行各种操作，通过该次试验，可以督促学生从实用的角度对《数据结构》课程内容进行更深入理解和更熟练的应用。
3． 实验编程语言要求使用java语言或C++语言。通过对调度功能的编程实现，不但能有效训练学生对编程语言的熟练使用，还能促进学生独立思考解决问题、以及独立查新获取知识的能力.

四．设计方案（软硬件环境，开发工具或语言选择及思路等)
<1〉设计环境平台:该软件在Windows XP，JDK1。6
<2>开发工具: eclipse+designer
〈3>设计思路 ：
1、 进程概念:进程是被独立分配资源的最小单位。进程是动态概念，必须程序运行才有进程的产生。
2、 进程的状态模型：
（1）运行：进程已获得处理机，当前处于运行状态。
（2）就绪:进程已经准备好，一旦有处理器就可运行。
（3)阻塞：进程因为发生某事件而暂停执行，亦即进程的执行受到阻塞。
3、处理机调度：在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。处理机调度就是从就绪队列中,按照一定的算法选择一个进程并将处理机分配给它运行,以实现进程并发地执行。
4、 进程调度算法的功能
记录系统中所有进程的执行情况
选择占有处理机的进程
进行进程的上下文切换
5、进程调度的算法：
（1）先来先服务算法:最先进入等待队列的进程先执行，进程结束后执行下一个进程。这是最简单的处理机调度算法,其基本思想是按照进程进入就绪队列的先后顺序调度并分配处理机执行.先来先服务调度算法是一种不可抢占的算法，先进入就绪队列的进程，先费培处理机运行。一旦一个进程占有了处理机,它就一直运行下去，知道该进程完成工作或者因为等待某事件而不能继续运行时才释放处理机
(2)优先数算法：即进程的执行顺序由高优先级到低优先级。系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。该算法核心是确定进程的优先级。
（3）时间片轮转算法：固定时间片,每个进程在执行一个时间片后,轮到下一进程执行，知道所有的进程执行完毕。处理器同一个时间只能处理一个任务。处理器在处理多任务的时候，就要看请求的时间顺序,如果时间一致，就要进行预测.挑到一个任务后，需要若干步骤才能做完，这些步骤中有些需要处理器参与，有些不需要(如磁盘控制器的存储过程）。不需要处理器处理的时候,这部分时间就要分配给其他的进程。原来的进程就要处于等待的时间段上.经过周密分配时间,宏观上就象是多个任务一起运行一样，但微观上是有先后的，就是时间片轮换。
(4) 多级反馈轮转法： 把系统中的所有进程分成若干个具有不同优先级别的组,同一组的进程都具有与所在组同样的优先级别,并且把每组进程组织成一个先进先出的队列。在设计时，按优先级别越高的组中的进程应得时间片越短的原则分配时间片。在调度时，调度器每次都从优先级别高的就绪队列中队首选择就绪进程。当在高优先级别的队列中找不到就绪进程时，才到低优先级别的就绪进程队列中选取.
注：优先数算法

时间片轮转法

多级反馈队列调度法

五．程序功能模块设计
1．
模拟进程调度算法模块
界面模块
进程调度模块
事件模块
先来先服务算法模块
优先
数算
法模
块
时间
片轮
转算
法模
块
多级
反馈
队列
调度
法模
块
六．程序总控流程图

开始

创建进程及属性

选择算法

先来先服务算法
优先数算
法
时闾片轮转法
多级反馈队列调度法

显示进程执行状态

结束

七．数据结构设计
本组在实现进程调度算法时采用了一个有特色的模拟方式———
线程模拟进程。
数据结构设计如下：
创建JAVA中的thread对象，并将创建好的各个对象放入数据容器
Vector（）中，各个调度算法对个进程的排序，其实就是对vector
中的thread对象排序，决定其执行顺序.

八．程序代码结构（函数调用关系或类层次关系）
开始执行:public class MainThread
——>弹出程序运行窗口
——〉选择进程调度算法
{comboBox。getSelectedItem（)==”Pri；
comboBox.getSelectedItem(） == "T_Slice"；
comboBox.getSelectedItem() == ”M_FB_Slice”}
——>创建进程:
从窗体控件获取相应参数创建进程new RefreshList(list_3， list_1， list_2, textField_3）。run(）
——〉对进程进行控制：
阻塞
(首先判断有无进程在执行：JOptionPane。showMessageDialog(null， ”已经无进程处于运行状态，请创建进程!"）,若有，则终止执，行将执行进程从就绪队列调入等待队列: v1。addElement(v2。get（0））；
v11.addElement（v0.get（0)）；
v2.remove(0）；
v0。remove（0）;
list_2.setListData(v11)；
list_1。setListData(v0);）；
唤醒：
将等待队列中的进程重新调入就绪队列的对尾

九．程序主要代码解析
public void run(） {
if (MainForm。algorithm.equals（”T_Slice”）） {
// System。out。println(”T_Slice”)；
execute_T_Slice();
refresh（)；
} else if （MainForm.algorithm.equals（”M_FB_Slice")） ｛
//System.out.println（"M_FB_Slice”）;
executeM_T_Slice()；
refresh（);
｝ else ｛
execute(）；
refresh(）;
｝
｝

public void refresh（） // 刷新列表，并且执行下一个进程
｛
MainForm。list_1。setListData（MainForm.v0);
if （MainForm。v0.size() > 0) ｛
MainForm。textField_3.setText（(String) MainForm.v0.get(0）)；
} else
MainForm。textField_3。setText（”无进程”）;
if (k < MainForm。n) {
ShowInfo show = new ShowInfo()；
show.setVisible（true）;
Thread t = new Thread（show)；
t.start(）;
} // 进程执行过程
}

public void execute（） ｛ //FCFS和优先级调度算法
int maximum = progressBar。getMaximum（);
progress = ((CrtProcess) MainForm.v2。get(0））。getProgress(）；
// System.out。println（progress+”sfsdf”+MainForm.v2.size(）)；
label_3。setText（(（CrtProcess）MainForm.v2。get(0）).getProcessName（））;
label_4.setText((（CrtProcess）MainForm。v2。get（0）)。getUserName（)）;
int i = progress；
while （i < maximum） ｛
try {
// int value = progressBar。getValue(）；
int value = progress;
source = MainForm。resource；
if （MainForm。resource == true） ｛
progress = value + 1；
progressBar.setValue（progress）;
CrtProcess process = (CrtProcess）MainForm。v2。get(0）；
process。setProgress（progress)；
MainForm。v2.remove(0);
MainForm。v2。add（0， process)；
Thread.sleep（DELAY);
i++；
prog++；
} else ｛
this.setVisible（false)；
MainForm.resource = true;
break;
｝
｝ catch (InterruptedException ignoredException) {
｝
}
if （source == true） {
// MainForm.v1。addElement（MainForm。v2。get(0)）；
MainForm。v2。remove（0);
MainForm。v0。remove(0)；
k++； // 记录已经执行结束的进程
this。setVisible(false);
// CrtProcess process=（CrtProcess) MainForm。v2.get（0);
// process。setFinished（true）;
// MainForm。v2。remove（0）;
// MainForm.v2。add（0，process）；
} else {
k++;
}
source = true；
｝

public void execute_T_Slice（） ｛ //时间片轮转算法
int maximum = progressBar.getMaximum（);
// int init=(（CrtProcess)MainForm。v2.get（k）).getProgress()；
// System。out.println（k)；
int i = 0；
progress = （(CrtProcess） MainForm.v2。get(0））。getProgress（）；
label_3.setText(（（CrtProcess)MainForm。v2。get（0）)。getProcessName（））;
label_4.setText(((CrtProcess) MainForm。v2.get(0))。getUserName()）;
int time = ((CrtProcess） MainForm.v2。get（0））。getTime_Slice（);
double percent = 1。0；
if (time 〉 MainForm.cpuTime_Slice) {
percent = MainForm。cpuTime_Slice / time； // 进度条的比例
｝
while （progress < maximum ＆＆ i 〈percent*maximum） {
try ｛
int value = progressBar.getValue();
source = MainForm.resource;
if （MainForm。resource == true) ｛
progress = value + 1;
progressBar.setValue(progress）；
（（CrtProcess)MainForm。v2.get（0）)。setProgress（progress)；
Thread.sleep(DELAY ＊ time）；
i++;
｝ else ｛
this。setVisible（false）;
MainForm。resource = true；
break；
}
｝ catch (InterruptedException ignoredException) {
｝
}
if (source == true && percent == 1.0) {
// MainForm.v1。addElement(MainForm。v2.get(0)）;
MainForm.v2。remove（0)；
MainForm。v0。remove(0);
k++； // 记录已经执行结束的进程
this.setVisible（false)；
}
if （source == true && percent ！= 1.0） ｛
CrtProcess process = （CrtProcess) MainForm.v2。get（0）；
process。setTime_Slice(time — （int) MainForm.cpuTime_Slice）;
MainForm。v2。remove（0);
MainForm.v0。remove（0)；
MainForm.v2.addElement(process）；
MainForm。v0.addElement（process。getProcessName（））；
k++；
MainForm。n++;
this.setVisible（false）；
｝
if （source == false)
k++；
source = true；
｝

public void executeM_T_Slice（) {
for （int i = 0; i < MainForm。vector_Num; i++）
size［i] = MainForm。vQueue[i］。size（）；
int maximum = progressBar.getMaximum();
// int init=（(CrtProcess）MainForm.v2。get(k)).getProgress()；
// System。out.println（k）；
int i = 0；
progress = (（CrtProcess) MainForm。v2.get(0)）.getProgress()；
label_3.setText（（（CrtProcess）MainForm。v2.get(0)）.getProcessName（))；
label_4.setText(（(CrtProcess) MainForm。v2.get（0)）。getUserName(））;
int time = (（CrtProcess） MainForm.v2。get（0))。getTime_Slice()；
double percent = 1。0;
if （time > MainForm。cpuTime_Slice) ｛
percent = MainForm.cpuTime_Slice/time； // 进度条的比例
}
while (progress 〈 maximum &＆ i 〈percent*maximum) {
try {
int value = progressBar.getValue（）;
source = MainForm.resource；
if （MainForm。resource == true) {
progress = value + 1；
progressBar。setValue（progress)；
（（CrtProcess)MainForm.v2.get(0)）。setProgress（progress）；
Thread。sleep(DELAY ＊ time)；
i++;
} else ｛
this.setVisible（false)；
MainForm.resource = true；
break；
｝
｝ catch (InterruptedException ignoredException) ｛
｝
}
if (source == true ＆＆ percent == 1。0） {
MainForm.v2.remove（0)；
MainForm。v0.remove（0）;
k++; // 记录已经执行结束的进程
this.setVisible(false);
｝
if （source == true &＆ percent != 1.0） {
if （k < n — 1) {
CrtProcess process = （CrtProcess） MainForm。v2.get（0)；
process.setTime_Slice（time — (int) MainForm.cpuTime_Slice）；
MainForm。v2。remove（0)；
MainForm.v0。remove（0）；
for (i = 0； i < MainForm。vector_Num ； i++) ｛
sum1 += size［i];
// System.out.println(”sum1:"+sum1);
if （k 〈=sum1) ｛
sum2 = sum1 + size[i + 1］;
MainForm.v2.add（sum2—k, process）;
MainForm。v0.add（sum2—k, process。getProcessName(））;
break;
｝
｝
k++;
MainForm.n++；
this.setVisible（false）；
}
// if (k == n - MainForm。vQueue［MainForm.vector_Num — 1].size（） - 1＆＆MainForm.vQueue[MainForm。vector_Num—1］。size(）!=1） {
// CrtProcess process1 = (CrtProcess) MainForm。v2。get(0)；
// process1.setTime_Slice（time - (int) MainForm.cpuTime_Slice)；
// MainForm。v2.remove（0)；
// MainForm。v0.remove(0）;
// MainForm.v2。addElement（process1）;
// //System.out。println（((CrtProcess） MainForm.v2.get（0））.getProcessName(）)；
// MainForm.v0。addElement（process1。getProcessName（))；
// k = 0；
// MainForm.n = MainForm。v2.size（)；
// this。setVisible(false)；
// ｝
if (source == false）
k++；
source = true；

｝

}

十．测试数据及测试结果

时间片算法
创建进程 进程名 5 4 3 2 1
时 间 6 4 3 7 1

执行时间片算法调度

执行时，先执行进程5，而进程5的执行时间为6，比时间片5（程序设定)大，先执
行时间5，再执行下一个进程4,而进程5放入就绪队列末尾,依次执行。执行过程为
5 4 3 2 1 5 2

十二。结论
从一开始的设计思想到后面的不断精简，无疑面对的是一个重要的问题:"用线程模拟进程的控制难度”。说到这里，不得不承认本课程设计的最重要的特色之处就是通过每创建一个进程，就对应一个线程来控制其执行状态。鉴于执行态采用的是通过另外一个窗体中的进度条实现程序的执行状态，通过设置优先级只能保证执行的先后顺序，却不能保证前一线程在是否结束时才能继续执行下一个线程，这样体现出的是”并发执行"，而模拟进程展现在我们面前的确实进程的”并行执行”中的同时性。所以采用了另外一种实现机制，即根据进程的调度算法,来实现进程的执行顺序。采用串行执行，即展现出在同一时刻只能有一个进程占用处理机资源，对于FCFS算法，仅仅是简单的顺序执行。对于优先级算法，则是按照优先级的高低进行排序，然后顺序执行，注意不论是何种算法,应该先执行第一个被创建的进程，先到达进程，处理机资源处于空现状态,所以先执行，后面的则根据相应的算法,进行排序后调度,至于轮转法则比较容易处理,就是根据进程所需的时间片与CPU分配给每一个进程的时间片的大小进行比较，若时间片大于CPU的时间片，则执行完CPU时间片后进入就绪队列尾部，等待下一个CPU时间片的到来，反之,则执行完毕,从就绪队列中删除。多级轮转法，则是采用的多个队列来控制他的执行顺序。本课程设计动态创建n个队列后，默认为下标小的优先级高，则根据输入的进程的优先级加入到相应的队列，然后每个队列分配一个CPU时间片，如果高优先级队列即下标小的队列中的进程未执行完毕，则加入到下标增一得队列尾部,继续执行，一直执行到尾部时，如果正在执行的进程分配的时间片不足以让其执行完毕，则直接进入该队列的尾部，即轮转法的规则相同。不管怎样，第一个首先创建一个显示进程执行状态的线程，进行执行。等执行完毕后，接着根据以通过调度算法排好序的队列顺序创建线程，即顺序执行，这样就可实现通过线程控制进程的串行执行。个人收集整理，勿做商业用途个人收集整理，勿做商业用途

十三. 目前资料收集情况(含指定参考资料）
著作:［1] 张尧学,史美林。计算机操作系统教程第2版。清华大学出版社2000年
著作：［2］ 张尧学。计算机操作系统教程第2版 习题与实验指导.2000年