C语言进程调度.doc

大 学
C语言程序设计 课程设计（论文）

题目： 进程调度

院（系）：
专业班级：
学 号：
学生姓名：
指导教师：
教师职称：
起止时间：

课程设计（报告）任务及评语
院（系）： 教研室：
学 号

学生姓名

专业班级

程序设计（报告）题目
进程调度
程序设计（报告）任务

程序设计的任务与要求：
（1）掌握C语言编程的基础知识。
（2）较熟练地编写C语言应用程序。
（3）了解C语言的常用标准函数、编程技巧、异常处理。
（5）联系已学过的内容，巩固所学的理论，增强独立工作能力。
（6）通过设计主要使学生有一个独立编写程序的过程，对理论学习及动手能力都有一个很大的提高。
（7）通过本次设计，进一步培养学生热爱专业的思想，同时对本专业综合素质的提高起一个积极的推动作用。
课程设计过程中，要严格遵守实践环节的时间安排，听从指导教师的指导。正确地完成上述内容，记录实习日记，规范完整地撰写出课程设计报告。

指导教师评语及成绩

成绩： 指导教师签字：

2011 年 1 月 4 日

辽 宁 工 业 大 学 课 程 设 计 说 明 书（论 文）

目 录
第1章 课程设计的目的与要求 1
1.1 课程设计目的 1
1.2 课程设计的实验环境 1
1.3 课程设计的预备知识 1
1.4 课程设计要求 1
第2章 课程设计内容 2
2.1程序功能介绍 2
2.2程序整体设计说明 3
2.2.1设计思路 4
2.2.2数据结构设计及用法说明 5
2.2.3程序结构（流程图） 5
2.2.4各模块的功能及程序说明 8
2.2.5程序结果 8
2.3程序源代码及注释 8
第3章 课程设计总结 18
参考资料 20

第1章 课程设计的目的与要求
1.1 课程设计目的
本课程设计是计算机科学与技术专业重要的实践性环节之一，是在学生学习完《程序设计语言(C)》课程后进行的一次全面的综合练习。本课程设计的目的和任务：
1. 巩固和加深学生对C语言课程的基本知识的理解和掌握
2. 掌握C语言编程和程序调试的基本技能
3. 利用C语言进行基本的软件设计
4. 掌握书写程序设计说明文档的能力
5. 提高运用C语言解决实际问题的能力
1.2 课程设计的实验环境
硬件要求能运行Windows 2000/XP操作系统的微机系统。C语言程序设计及相应的开发环境。
1.3 课程设计的预备知识
熟悉C语言及C语言开发工具。
1.4 课程设计要求
1. 分析课程设计题目的要求
2. 写出详细设计说明
3. 编写程序代码，调试程序使其能正确运行
4. 设计完成的软件要便于操作和使用
5. 设计完成后提交课程设计报告

第2章 课程设计内容
2.1程序功能介绍
在多道程序环境下，进程数目往往多于处理机数目，致使他们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之运行。分配处理机的任务是由进程调度程序完成的。一个进程被建立后，系统为了便于对进程进行管理，将系统中的所有进程按其状态，将其组织成不同点进程队列。于是系统中有运行进程队列、就绪队列和各种事件的进程等待队列。进程调度的功能就是从就绪队列中挑选一个进程到处理机上运行。
本课题模拟实现进程调度算法，选用了优先数调度算法和时间片轮转算法。
2.2程序整体设计说明
进程调度的设计方法
1。数据结构
（1）优先级与时间片的设计
进程因等待放弃CPU时，优先级置为1（高优先级）
进程因时间片到放弃CPU时，优先级置为0（低优先级）
优先1对应时间片4；优先级0对应时间片10。
（2）进程控制块（PCB）的内容
进程标识3---9
进程优先级 0，1
进程优先级 0，1
进程等待时间 20
链接指针
2：程序算法
PCB结构，变量与主程序
struct PCB
{
int pname;
int pri;
int runtime;
int waitting;
struct PCB*next;
}
pcb[7];
struct PCB*running,ready,wait;
int sin=0;
main()
{ 创建PCB[3]--PCB[9]并插入ready队列；／*pname分别为3--9,
pri=0,runtime=10,waittime=0 */
for(;;)/*系统程序，完成初始化和处理机分派功能 */

{cast{sig=0:swtch;
sig=1:waiter;
sig=3:proc3;
sig=4:proc4;
sig=5:proc5;
sig=6:proc6;
sig=7:proc7;
sig=8:proc8;
sig=9:proc9;}
}
}
2.2.1设计思路
1设计进程进程控制块PCB表结构，分别适用于优先数调度算法和循环轮转调度算法。
  PCB结构通常包括以下信息：进程名，进程优先数（或轮转时间片），进程所占用的CPU时间，进程的状态，当前队列指针等。根据调度算法的不同，PCB结构的内容可以作适当的增删。
建立进程就绪队列。对两种不同算法编制入链子程序。编制两种进程调度算法：1）优先度调度；2）循环轮转调度。
本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。
为了便于处理，程序中的运行时间以时间片为单位计算，各进程的优先数或轮转时间数以及进程需要运行的时间片数的初值均由用户给定。
在优先数算法中，初始优先数为50-NEEDTIME,进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1，在轮转算法中，采用固定时间片，时间片数为2进程每执行1次，CPU时间片数加2，进程还需要的时间数减2，并排列到就绪队列的尾上。
2.2.2数据结构设计及用法说明
主要数据结构
定义进程
Typedef struct node
{
int Pname;//进程名
int Rtime;//进程要求执行时间
int rtime;//进程已执行时间
char state;//进程状态
struct node * next;//指针
}Pnode;
主要代码结构
输入运行的进程数
先定义第一个进程输出剩余的进程，输入时采用尾插法，最终建立一个循环链表
对循环链表根据算法思想进行相关的处理。
2.2.3程序结构（流程图）
程序流程图如图2.1、2.2所示。
Toupper(a)==P
printf(“name cput…
printf(“name cput…
Run=ready;
PCB*p;
Run!=NULL
Prt2(algo,run);
P=ready;
P!=PULL
Prt2(algo.p);
N
Y
N
Y
OVER
图 2.1 程序流程图

Y
N
Y
N
Y
N
Y
N
Y
P=finish;
Multiplex
Run!=NULL
Run->cputime=run->c…
Run->next=finish
Run->next=finish;
Multiplex
Prt(alg);
Run->count==ru
Mutltiplex
Charalgo;
Algo==’P’||algo=
Createl(algo);
Algo==’R’||alg
Create2(algo);
N
图 2.2 程序流程图
OVER

2.2.4各模块的功能及程序说明
第一模块：标题输出函数；使用if-else语句编辑。
第二模块：进程PCB输出；使用if-else语句编辑。
第三模块：输出函数；使用if语句和while语句编辑。
第四模块：优先数的插入算法；使用while语句和if-else语句编辑。
第五模块：轮转法插入函数；使用for语句和if-else语句编辑。
第六模块：优先数创建初始PCB信息；使用if-else语句和for语句编辑。
第七模块：轮转法创建进程PCB；使用if-else语句和for语句编辑。
第八模块：优先数调度算法；使用if-else语句，while语句和if语句编辑。
第九模块：时间片轮转法；if-else语句，while语句和if语句编辑。
第十模块：主函数；使用if-else语句编辑。
2.2.5程序结果
程序运行结果如图2.3所示

图 2.3 运行结果
2.3程序源代码及注释
/*8.3.2 源程序*/
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct node
{
char name[10]; /*进程标识符*/
int prio; /*进程优先数*/
int round; /*进程时间轮转时间片*/
int cputime; /*进程占用CPU时间*/
int needtime; /*进程到完成还要的时间*/
int count; /*计数器*/
char state; /*进程的状态*/
struct node *next; /*链指针*/
}PCB;
PCB *finish,*ready,*tail,*run; /*队列指针*/
int N; /*进程数*/
/*将就绪队列中的第一个进程投入运行*/
firstin()
{
run=ready; /*就绪队列头指针赋值给运行头指针*/
run->state='R'; /*进程状态变为运行态*/
ready=ready->next; /*就绪对列头指针后移到下一进程*/
}
/*标题输出函数*/
void prt1(char a)
{
if(toupper(a)=='P') /*优先数法*/
printf(" name cputime needtime priority state\n");
else
printf(" name cputime needtime count round state\n");
}
/*进程PCB输出*/
void prt2(char a,PCB *q)
{
if(toupper(a)=='P') /*优先数法的输出*/
printf(" %-10s%-10d%-10d%-10d %c\n",q->name,
q->cputime,q->needtime,q->prio,q->state);
else/*轮转法的输出*/
printf(" %-10s%-10d%-10d%-10d%-10d %-c\n",q->name,
q->cputime,q->needtime,q->count,q->round,q->state);
}
/*输出函数*/
void prt(char algo)
{
PCB *p;
prt1(algo); /*输出标题*/
if(run!=NULL) /*如果运行指针不空*/
prt2(algo,run); /*输出当前正在运行的PCB*/
p=ready; /*输出就绪队列PCB*/
while(p!=NULL)
{
prt2(algo,p);
p=p->next;
}
p=finish; /*输出完成队列的PCB*/
while(p!=NULL)
{
prt2(algo,p);
p=p->next;
}
getch(); /*压任意键继续*/
}
/*优先数的插入算法*/
insert1(PCB *q)
{
PCB *p1,*s,*r;
int b;
s=q; /*待插入的PCB指针*/
p1=ready; /*就绪队列头指针*/
r=p1; /*r做p1的前驱指针*/
b=1;
while((p1!=NULL)&&b) /*根据优先数确定插入位置*/
if(p1->prio>=s->prio)
{
r=p1;
p1=p1->next;
}
else
b=0;
if(r!=p1) /*如果条件成立说明插入在r与p1之间*/
{
r->next=s;
s->next=p1;
}
else
{
s->next=p1; /*否则插入在就绪队列的头*/
ready=s;
}
}
/*轮转法插入函数*/
insert2(PCB *p2)
{
tail->next=p2; /*将新的PCB插入在当前就绪队列的尾*/
tail=p2;
p2->next=NULL;
}
/*优先数创建初始PCB信息*/
void create1(char alg)
{
PCB *p;
int i,time;
char na[10];
ready=NULL; /*就绪队列头指针*/
finish=NULL; /*完成队列头指针*/
run=NULL; /*运行队列指针*/
printf("Enter name and time of process\n"); /*输入进程标识和所需时间创建PCB*/
for(i=1;i<=N;i++)
{
p=malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->state='w';
p->prio=50-time;
if(ready!=NULL) /*就绪队列不空调用插入函数插入*/
insert1(p);
else
{
p->next=ready; /*创建就绪队列的第一个PCB*/
ready=p;
}
}
clrscr();
printf(" output of priority:\n");
printf("************************************************\n");
prt(alg); /*输出进程PCB信息*/
run=ready; /*将就绪队列的第一个进程投入运行*/
ready=ready->next;
run->state='R';
}
/*轮转法创建进程PCB*/
void create2(char alg)
{
PCB *p;
int i,time;
char na[10];
ready=NULL;
finish=NULL;
run=NULL;
printf("Enter name and time of round process\n");
for(i=1;i<=N;i++)
{
p=malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->count=0; /*计数器*/
p->state='w';
p->round=2; /*时间片*/
if(ready!=NULL)
insert2(p);
else
{
p->next=ready;
ready=p;
tail=p;
}
}
clrscr();
printf(" output of round\n");
printf("************************************************\n");
prt(alg); /*输出进程PCB信息*/
run=ready; /*将就绪队列的第一个进程投入运行*/
ready=ready->next;
run->state='R';
}
/*优先数调度算法*/
priority(char alg)
{
while(run!=NULL) /*当运行队列不空时，有进程正在运行*/
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
run->prio=run->prio-3; /*每运行一次优先数降低3个单位*/
if(run->needtime==0) /*如所需时间为0将其插入完成队列*/
{
run->next=finish;
finish=run;
run->state='F'; /*置状态为完成态*/
run=NULL; /*运行队列头指针为空*/
if(ready!=NULL) /*如就绪队列不空*/
firstin(); /*将就绪对列的第一个进程投入运行*/
}
else /*没有运行完同时优先数不是最大，则将其变为就绪态插入到就绪队列*/
if((ready!=NULL)&&(run->prio<ready->prio))
{
run->state='W';
insert1(run);
firstin(); /*将就绪队列的第一个进程投入运行*/
}
prt(alg); /*输出进程PCB信息*/
}
}
/*时间片轮转法*/
roundrun(char alg)
{
while(run!=NULL)
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
run->count=run->count+1;
if(run->needtime==0)/*运行完将其变为完成态，插入完成队列*/
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
firstin(); /*就绪对列不空，将第一个进程投入运行*/
}
else
if(run->count==run->round) /*如果时间片到*/
{
run->count=0; /*计数器置0*/
if(ready!=NULL) /*如就绪队列不空*/
{
run->state='W'; /*将进程插入到就绪队列中等待轮转*/
insert2(run);
firstin(); /*将就绪对列的第一个进程投入运行*/
}
}
prt(alg); /*输出进程信息*/
}
}
/*主函数*/
main()
{
char algo; /*算法标记*/
clrscr();
printf("type the algorithm:P/R(priority/roundrobin)\n");
scanf("%c",&algo); /*输入字符确定算法*/
printf("Enter process number\n");
scanf("%d",&N); /*输入进程数*/
if(algo=='P'||algo=='p')
{
create1(algo); /*优先数法*/
priority(algo);
}
else
if(algo=='R'||algo=='r')
{
create2(algo); /*轮转法*/
roundrun(algo);
}
}

第3章 课程设计总结
通过完成本次进程调度程序设计的任务，使我熟练和掌握了这学期所学的有关Turboc2.0中的一些主要知识点和应用点，如函数定义，语句的判断等等。原来我还不知道进程调度这个名词，通过这次课程设计，也让我充分了解留什么是进程调度。可以所学有所学，所有所用，不至于自己所学知识由于没有经历可用过程，而放弃对它的兴趣。
本次作为一门软件设计的课程，具有极强的实践性，使我加强了灵活应用理论知识的能力及面向对象程序设计技能。
此次，应用程序的设计和创建，经历了平时在课堂中和考试中，决不会有的重重难题和问题。而这些问题，又都是课本上很少提到的、更深一层的知识领域和应用领域。这些问题，并不是我们平时只靠课本，就可以轻易解决的。所以，锻炼了我们面对难题，自己思索，自己探索，自己查资料发现问题、解决问题的独断能力。
当然，此次任务的完成，也体现出同学之间的团结精神。所遇种种难以解决的问题，大家都会把它当作共同遇到的问题，在一起共同探讨，共同发挥自己所学和所知，投入式的互相帮助和解决困难。
“实践是检验真理的唯一标准”。没有实践，就不会发现和深刻体会它的真实所在。只有通过检验的真理，在自己的心里，才会认可它的真实性。面向对象程序设计的完成，使我们懂得了真理的重要性，理论和实际的相结合，才能真正把握所学和所掌握的知识。
理论的拥有并不能代表我们的实力和能力，一切的事件和其成功都是理论和实践的结合。总之，我们学习和掌握的知识，只有通过实际应用，才能真正的理解和掌握，才能更好的去应用。
在为期不到两周的课程设计中，我体会颇多，学到很多东西。我懂得了如何用 Turboc2.0编写应用程序，我加强了对，利用设计这次简单计算器的机会的认识，复习了自己以前的知识，自己的逻辑思考能力也提高不少。从而对Turboc2.0又有了更深入的认识！在这次课程设计中，我还懂得了程序开发的一些比较重要的步骤，比如需求分析、总体设计、数据库设计，程序模块设计(含功能需求、用户界面设计、程序代码设计与分析、运行结果)、系统使用说明等。
本次的课程设计，让我巩固了原来所学习的C语言理论知识，而且还扩大了知识面，更多接触了课本所没有的东西。初步掌握了文本菜单的制作、函数功能的实现等编程。总之，这次课程设计让我对系统的设计有了一个初步的了解，同时也对c语言的应用有了一个好的开始，加深了我对c语言的理解。相信经过这次的课程设计，我的c语言应用能力将有比较大的提高。
参考资料
[1] 《C语言程序设计教程》（第二版）秦友淑编著 华中科技大学出版2002年12月
[2] 《C高级实用程序设计》 王士元 编著  清华大学出版社   2000年3月
[3] 《Turbo C使用大全第一册，第二册》  徐金梧等编译     北京科海培训中心
[4] 《C语言程序设计》 张磊 高等教育出版社   书号：ISBN-7-04-016437-6 – X
[5] 《C语言最新编程技巧200例》 作者：鲁沐浴，电子工业出版社，1997，1
[6] 《C语言程序设计实用技巧与程序实例》 作者：梁   翎，李爱齐，上海科普出版社，1996，5
[7] 张基温.C语言程序设计教程.上海:高等教育出版社,1992
[8] 崔武子.C程序设计辅导与实训. 清华大学出版社.2004
[9] 毕万新.C 语言程序设计.2005年版.大连. 大连理工大学出版社.2005
[10]徐德民.最新C语言程序设计.北京:电子工业出版社,1990
[11]李春葆 张植民 肖忠付，《C语言程序设计题典》，清华大学出版社，2002
[12]张小潘/译，[美]科汉/著，《C语言编程（第3版）》，电子工业出版社，2006
[13]夏云庆编著VisualC++6.0数据库高级编程北京希望电子出版社
[14]谭浩强.C语言程序设计.北京:清华大学出版社,2000:74-80
[15]谭浩强主编，《C程序设计题解与上机指导（第3版）》，清华大学出版社，2005

附录资料：不需要的可以自行删除
SHA算法的实现

C语言程序：
#include <iostream>
#include <vector> //定义vector数组
#include <string> //记录消息
using namespace std;

const int NUM = 8; //一个字由32比特(或者8个16进制数)
const int BIT = 512; //消息认证码要以512比特一组

//字常量
string H0 = "67452301";
string H1 = "EFCDAB89";
string H2 = "98BADCFE";
string H3 = "10325476";
string H4 = "C3D2E1F0";

//定义SHA1(安全哈希算法)类
class SHA1
{
public:
//将一个字符串形式的字转化为vector数组
vector<int> hex_into_dec(string word);

//将vector转化为string字符串形式
string num_into_message(vector<int> A);

//两个字X和Y的逻辑"和"
vector<int> word_AND(vector<int> A,vector<int> B);

//两个字X和Y的逻辑"或"
vector<int> word_OR(vector<int> A,vector<int> B);

//两个字X和Y的逻辑"异或"
vector<int> word_XOR(vector<int> A,vector<int> B);

//两个字X和Y的逻辑"补"
vector<int> word_COMPLEMENT(vector<int> A);

//两个字X和Y的摸2^32整数加
vector<int> word_ADD(vector<int> A,vector<int> B);

//将字X循环左移s个位置
vector<int> ROTL(vector<int> A,int s);

//SHA-1的填充方案,我们设定msg由ASCII码组成
vector<vector<int> > SHA_1_PAD(string msg);

//将SHA-1压成以字为单位
vector<vector<vector<int> > > compress(vector<vector<int> > result);

//定义ft函数，每个ft函数都有B,C,D三个字作为输入，并产生一个字作为输出
vector<int> Ft(int t,vector<int> B,vector<int> C,vector<int> D);

//定义字常数K
vector<int> K(int t);

//开始进行SHA-1(安全Hash算法)的加密
vector<vector<int> > SHA_1(string msg);

};

//将vector转化为string字符串形式
string SHA1::num_into_message(vector<int> A)
{
int i;
string msg = "";
for(i = 0;i < A.size();i++)
{
if(A[i] >= 0 && A[i] <= 9)
msg += '0' + A[i];
else if(A[i] >= 10 && A[i] <= 15)
msg += 'A' + (A[i] - 10);
}
return msg;
}

//将一个字符串形式的字转化为vector数组
vector<int> SHA1::hex_into_dec(string word)
{
int i;
vector<int> result(NUM,0);
for(i = 0;i < NUM;i++)
{
if(word[i] >= '0' && word[i] <= '9')
{
result[i] = word[i] - '0';
}
else if(word[i] >= 'A' && word[i] <= 'F')
{
result[i] = 10 + word[i] - 'A';
}
}
return result;
}

//两个字X和Y的逻辑"和"
vector<int> SHA1::word_AND(vector<int> A,vector<int> B)
{
vector<int> result(NUM,0);
int i;
for(i = 0;i < NUM;i++)
{
result[i] = A[i] & B[i];
}
return result;
}

//两个字X和Y的逻辑"或"
vector<int> SHA1::word_OR(vector<int> A,vector<int> B)
{
vector<int> result(NUM,0);
int i;
for(i = 0;i < NUM;i++)
{
result[i] = A[i] | B[i];
}
return result;
}

//两个字X和Y的逻辑"异或"
vector<int> SHA1::word_XOR(vector<int> A,vector<int> B)
{
vector<int> result(NUM,0);
int i;
for(i = 0;i < NUM;i++)
{
result[i] = A[i] ^ B[i];
}
return result;
}

//两个字X和Y的逻辑"补"
vector<int> SHA1::word_COMPLEMENT(vector<int> A)
{
vector<int> result(NUM,0);
int i;
for(i = 0;i < NUM;i++)
{
result[i] = 15 - A[i];
}
return result;
}

//两个字X和Y的摸2^32整数加
vector<int> SHA1::word_ADD(vector<int> A,vector<int> B)
{
vector<int> result(NUM,0);
int i;
for(i = NUM - 1;i >= 0;i--)
{
result[i] = A[i] + B[i];
if(i != 0)
{
int temp = result[i] / 16;
result[i-1] += temp;
}
result[i] %= 16;
}
return result;
}

//将字X循环左移s个位置
vector<int> SHA1::ROTL(vector<int> A,int s)
{
vector<int> result = A;
vector<int> temp(NUM,0);
int i,j;
for(i = 0;i < s;i++)
{
for(j = NUM - 1;j >= 0;j--)