操作系统课程设计
学号： 1233050169
姓名： 安心
专业： 计算机科学与技术
课程： 操作系统
指导教师：
时间： 2015/3/9
成绩：
目录
目录................................................................................................... 1
1．设计题目与要求........................................................................ 2
1.1设计目的............................................................................... 2
1.2设计要求........................................................................... 2
2． 总体设计思想.......................................................................... 2
2.1总体设计思想...................................................................... 2
3． 功能设计.................................................................................. 4
3.1 数据结构设计..................................................................... 4
3.2程序清单............................................................................ 4
3.3运行结果............................................................................ 7
4. 设计心得................................................................................... 9
5. 参考资料................................................................................... 9
附录................................................................................................. 10
程序源代码：................................................................................ 10
一．设计题目与要求
课题：理机调度模拟程序：选择一个调度算法，实现处理机调度。
1.设计目的：
在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个。也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩固和加深处理机调度的概念。
2.设计要求：
1）进程调度算法包括：时间片轮转法，短作业优先算法，最高响应比优先算法。
2）可选择进程数量
3）本程序包括三种算法，可用C语言实现，执行时在主界面选择算法（可用函数实现），进入子页面后输入进程数及每个进程的运行时间，每个进程的优先数由随机函数产生且优先数随等待时间而变化，执行，显示结果。
二．总体设计思想
(1)进程的创建：由系统为某个进程设置一个进程控制块PCB，用于对进程进行控制和管理。进程任务完成，由系统收回其PCB，该进程便消亡。
(2)进程的三种状态：运行、就绪、完成。进程的三种状态可以通过设计三个链队列来实现：finish为完成队列的头指针，ready为就绪队列的头指针，tail为循环轮转法队列的尾指针。因为每一时刻，CPU只能运行一个进程，所以运行队列只有一个run指针指向当前运行进程。
(3)进程调度的功能：按照一定的策略从就绪队列的多个进程中选取一个进程，使其获得CPU而运行。
①动态优先数调度算法：
思想：为每一个进程设一个优先数，它总是把处理机给就绪队列中具有最高优先级的进程。初始的进程优先数是随机产生的，随着进程的运行对优先数进行调整，每次运行时都是从就绪队列中选取优先数最大的进程运行，所以将就绪队列按照优先数的大小从高到低排序，这样，每次取对首进程即可。将进程按优先数的大小排列在就绪队列中，每次选取就绪队列中优先权最高的进程首先占用处理机。优先数由随机函数产生进程最初的优先数。优先数的动态变化：进程每执行一次优先数-1。优先数随着进程的执行进行调整，每次执行时都从就绪队列中选取优先数最大的进程投入运行。
②时间片轮转调度算法：
思想：将所有进程按照先来先服务的规则排成一个队列，把CPU分配给就绪队列的队首进程，并规定它的执行时间（称此时间为时间片），当时间片用完但并未执行结束时，剥夺该进程的执行，将其链接到就绪队列的队尾，等待下一次的选择。将就绪队列的队首指针投入运行。
③短作业优先调度算法（不可剥夺式的）
思想：根据估计运行时间的长短，将各个进程排成一个就绪队列（估计运行时间最短的进程排在队首），每次运行将队首进程投入运行，直到运行结束，将此进程连接到完成队列的队尾。然后，再将下一个队首进程投入运行，直到所有的进程都运行完毕。
三．功能设计
1.数据结构设计
PCB结构体：
typedef struct node
{ char name[10]; /*进程时间轮转时间片*/
int pid; /*进程的标号*/
int prio; /*优先级*/
int round; /*时间片*/
int cputime; /*进程占用cpu的时间*/
int runtime; /*进程运行所用的时间*/
int waittime; /*进程的等待时间*/
int length; /*进程的长度*/
int count; /*计数器*/
char state; /*进程的状态*/
struct node *next;/*链指针*/
}PCB ; PCB结构体用于标识进程的创建与撤消。
链指针：
PCB *finish,*ready,*tail,*run;.
Finish：完成队列的首指针，用于标识完成队列；
Ready：就绪队列的首指针，用于标识就绪队列；；
Run：运行队列的首指针，用于标识运行队列；；
Tail：循环轮转队列的尾指针；
2.程序清单
（1）Create1（），create2（），create3（）分别为创建进程的函数
① Create1（ ）：按照优先级调度算法创建进程，用户输入进程名及进程所需的时间后，创建每个进程的PCB，将每个进程的PCB调用函数insert1（）按照优先数从高到低排列到就绪队列中。
② create2（ ）：按照时间片调度算法创建进程，用户输入进程名及进程所需的时间后，创建每个进程的PCB，将每个进程的PCB调用函数insert2（ ）将每个进程PCB按照输入的先后顺序插入到就绪队列的末尾。
③ create3（ ）：按照短作业优先调度算法创建进程，用户输入进程名及进程所需的时间后，创建每个进程的PCB，将每个进程的PCB调用函数insert3（ ）：按照作业估计执行时间的长短从高到低排列到就绪队列中。
就绪队列创建好后，将队列当中的第一个PCB变为运行态“R”，将run 指针指向它，ready指针后移，作为就绪队列的新头指针，然后调用调度算法。注意每个时刻只能有一个进程处于运行态。
（2） insert1（），insert2（），insert3（）分别为插入函数
这三个函数完成的是就绪队列的创建和管理。
①insert1（）的功能是将未完成且优先数小于其它进程的PCB按进程优先数的顺序插入到就绪队列中去。
②insert2（）的功能是将执行了一个时间片且还未完成的进程的PCB插入到就绪队列的队尾。
③ insert3（）的功能是将未完成且作业的执行时间小于其它进程的PCB按进程的作业的执行时间的长短插入到就绪队列中去。
（3）priority（）优先数调度算法
①假定系统有三个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：
typedef struct node
{
int pid; /*进程的标号*/
int prio; /*优先级*/
int cputime; /*进程占用cpu的时间*/
int runtime; /*进程运行所用的时间*/
char state; /*进程的状态*/
struct node *next;/*链指针*/
}PCB;
（4） roundrun（）时间片轮转法调度算法
① 假定系统有三个进程，每一个进程用一个进程控制块PCB来代表。进程控制块的格式为：
进程名，进程占用cpu的时间，进程到完成还需的时间，时间片，计数器，状态
进程名——作为进程的标识，假设三个进程的进程名分别是p1，p2，p3。
时间片——时间片轮转循环所需的时间总数。
计数器——对进程执行时间进行计数。
进程占用cpu的时间——假设进程已经运行的单位时间数，初始值为“0”。
状态——有三种状态，“就绪”状态，“运行”状态和“完成”状态。三个进程的初始状态都为“就绪”，用“w”表示，当一个进程运行结束后，它的状态为“完成”，用“F”表示，当一个进程正在占用cpu 时，它的状态为“运行”状态。
② 每次运行所设计的时间片轮转调度程序之前，为每个进程任意确定它的“要求运行时间”。
③ 把三个进程按先来先服务的顺序排成循环队列，用指针指出队列连接情况。时间片轮转调度总是选择ready指针指示的进程运行。而是执行：
进程到完成还需的时间－1
进程占用cpu的时间+1
计数器+1
来模拟进程的一次运行，表示进程已经运行过一个单位的时间。
（5） shortjob（）短作业优先法调度算法
①假定系统有三个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：
进程名，进程占用cpu的时间，进程到完成还需的时间，状态
进程名——作为进程的标识，假设三个进程的进程名分别为P1，P2，P3。
进程占用cpu的时间——假设进程已经运行的单位时间数，初始值为“0”。
状态——有三种状态，“就绪”状态，“运行”状态和“完成”状态。三个进程的初始状态都为“就绪”，用“w”表示，当一个进程运行结束后，它的状态为“完成”，用“F”表示，当一个进程正在占用cpu 时，它的状态为“运行”状态。
②在每次运行所设计的短作业优先调度程序之前，为每个进程任意确定它的“要求运行时间”。
③ 为了调度方便，把三个进程按任意给定的作业长短进行排序。用一单元指出队首进程，用指针指出队列的连接情况。每次取对首进程即可。
④ 短作业调度总是选队首进程运行。进程每运行一次，
要求运行时间-1
进程占用cpu的时间+1
来模拟进程的一次运行。
⑤进程运行一次后，若要求运行时间〉0，则再将它插入就绪队列（按作业长短插入，且置队首标志）；若要求运行时间=0，则把它的状态修改成“完成”（F），且退出队列。
⑥ 若“就绪”状态的进程队列不为空，则重复上面（4）和（5）的步骤，直到所有进程都成为“完成”状态。
⑦ 在设计的程序中有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化及状态。
⑧ 为三个进程随机确定“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。
（6） 界面设计：
主界面：选择调度算法；
子界面：输入进程数，进程名及进程所需的时间；
利用c语言中的画图函数及清屏函数设计界面。
3．运行结果
主界面设计：（1,2,3算法 4退出）
算法1：动态优先级算法
算法2：时间片轮转法
算法3：短作业优先法
四．心得体会及总结：
处理机调度问题实际上是处理机分配问题。只有那些参与竞争处理机所必须的资源都已得到满足的进程才能享受竞争处理机的资格，这时它们处于内存就绪状态。这些必须的资源包括内存、外设及有关数据结构等。作业调度程序必须先调用存储管理、外设管理，分配资源，让它们能有竞争资格。
为了提高资源利用率，一部分在内存中处于就绪、等待状态而短期内不能执行进程、作业换出内存，所以外存中除了处于后备状态的作业，还有处于就绪状态的作业。这就需要一定的方法和策略来为这部分作业分配空间。
学习完《操作系统原理》课程后，进行的这次全面的综合训练，通过课程设计，使我更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力，并与编程相结合应用于实际中。
五．参考资料
[1]宗大华，宗涛，陈吉人著 操作系统 北京：人民邮电出版社，2009
[2]李爱华，程磊著 面相对象程序设计（C++语言） 北京: 清华大学出版社，2010
[3]宋晓宇 ， windows操作系统核心编程实验教程 中国铁道出版社
[4]张丽芬 刘利雄 王金玉编著 操作系统实验教程 清华大学出版社
附录：
程序源代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
typedef struct node
{
char name[10];
int prio;
int round;
int cputime;
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;
}
int timesj(void)
{
int i,xt;
time_t t;
srand((unsigned) time(&t));
xt = rand() % 10 +1;
return xt;
}
void prt1(char a)
{
if(toupper(a)=='1')
printf(" name cputime needtime priority state\n");
else
if(toupper(a)=='2')
printf(" name cputime needtime priority state\n");
else
printf(" name cputime needtime priority state\n");
}
void prt2(char a,PCB *q)
{
if(toupper(a)=='1')
printf(" %-10s%-10d%-10d%-10d %c\n",q->name,
q->cputime,q->needtime,q->prio,q->state);
else
if(toupper(a)=='2')
printf(" %-10s%-10d%-10d%-10d %c\n",q->name,
q->cputime,q->needtime,q->prio,q->state);
else
printf(" %-10s%-10d%-10d%-10d %c\n",q->name,
q->cputime,q->needtime,q->prio,q->state);
}
void prt(char algo)
{
PCB *p;
prt1(algo);
if(run!=NULL)
prt2(algo,run);
p=ready;
while(p!=NULL)
{
prt2(algo,p);
p=p->next;
}
p=finish;
while(p!=NULL)
{
prt2(algo,p);
p=p->next;
}
getch();
return;
}
insert1(PCB *q)
{
PCB *p1,*s,*r;
int b;
s=q;
p1=ready;
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->next=s;
s->next=p1;
}
else
{
s->next=p1;
ready=s;
}
}
insert2(PCB *p2)
{
tail->next=p2;
tail=p2;
p2->next=NULL;
}
insert3(PCB *q)
{
PCB *p1,*s,*r;
int b;
s=q;
p1=ready;
r=p1;
b=1;
while((p1!=NULL)&&b)
if(p1->needtime<=s->needtime)
{
r=p1;
p1=p1->next;
}
else
b=0;
if(r!=p1)
{
r->next=s;
s->next=p1;
}
else
{
s->next=p1;
ready=s;
}
}
void create1(char alg)
{
PCB *p;
int i,time,sjt,priost;
char na[10];
ready=NULL;
finish=NULL;
run=NULL;
printf("Enter name and time of process\n");
printf("----\n");
for(i=1;i<=N;i++)
{
p=malloc(sizeof(PCB));
printf("Enter name%d",i);
printf(":");
scanf("%s",na);
printf("Random time%d",i);
printf(":");
sjt=timesj();
printf("%d\n", sjt);
printf("Random priority%d",i);
printf(":");
printf("%d\n", 20-sjt);
strcpy(p->name,na);
p->cputime=0;
p->needtime=sjt;
p->state='w';
p->prio=20-sjt;
if(ready!=NULL)
insert1(p);
else
{
p->next=ready;
ready=p;
}
}
printf(" Display Process Of Priority:\n");
printf("-----\n");
prt(alg);
run=ready;
ready=ready->next;
run->state='R';
}
void create2(char alg)
{
PCB *p;
int i,time,sjt;
char na[10];
ready=NULL;
finish=NULL;
run=NULL;
printf("Enter name and time of round process\n");
printf("-----\n");
for(i=1;i<=N;i++)
{
p=malloc(sizeof(PCB));
printf("Enter name%d",i);
printf(":");
scanf("%s",na);
printf("Random time%d",i);
printf(":");
sjt=timesj();
printf("%d\n", sjt);
printf("Random priority%d",i);
printf(":");
printf("%d\n", 20-sjt);
strcpy(p->name,na);
p->cputime=0;
p->needtime=sjt;
p->round=1;
p->state='w';
p->count=0;
p->prio=20-sjt;
if(ready!=NULL)
insert2(p);
else
{
p->next=ready;
ready=p;
tail=p;
}
}
printf(" Display Process Of Roundrobin\n");
printf("-----\n");
prt(alg);
run=ready;
ready=ready->next;
run->state='R';
}
void create3(char alg)
{
PCB *p;
int i,time,sjt;
char na[10];
ready=NULL;
finish=NULL;
run=NULL;
printf("Enter name and time of process\n");
printf("----\n");
for(i=1;i<=N;i++)
{
p=malloc(sizeof(PCB));
printf("Enter name%d",i);
printf(":");
scanf("%s",na);
printf("Random time%d",i);
printf(":");
sjt=timesj();
printf("%d\n", sjt);
printf("Random priority%d",i);
printf(":");
printf("%d\n", 20-sjt);
strcpy(p->name,na);
p->cputime=0;
p->needtime=sjt;
p->state='w';
p->prio=20-sjt;
if(ready!=NULL)
insert1(p);
else
{
p->next=ready;
ready=p;
}
}
printf(" Display Process Of Priority:\n");
printf("-----\n");
prt(alg);
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-1;
if(run->needtime==0)
{
run->next=finish;
finish=run;
run->state='C';
run=NULL;
if(ready!=NULL)
firstin();
}
else
if((ready!=NULL)&&(run->prio<ready->prio))
{
run->state='W';
insert1(run);
firstin();
}
prt(alg);
}
}
roundrun(char alg)
{
while(run!=NULL)
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
run->count=run->count+1;
run->prio=run->prio-1;
if(run->needtime==0)
{
run->next=finish;
finish=run;
run->state='C';
run=NULL;
if(ready!=NULL)
firstin();
}
else
if(run->count==run->round)
{
run->count=0;
if(ready!=NULL)
{
run->state='W';
insert2(run);
firstin();
}
}
prt(alg);
}
}
shorttask(char alg)
{
while(run!=NULL)
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
run->prio=run->prio-1;
if(run->needtime==0)
{
run->next=finish;
finish=run;
run->state='C';
run=NULL;
if(ready!=NULL)
firstin();
}
else
if((ready!=NULL)&&(run->needtime>ready->needtime))
{
run->state='W';
insert1(run);
firstin();
}
prt(alg);
}
return;
}
menu()
{ char algo;
printf("\n\n COMPUTER OS WORK\n\n");
printf("\n\n By wanghao(Class 2) \n\n\n");
printf(" choose one of following:\n");
printf("\n 1.PRIORITY.\n\n");
printf(" 2.ROUNDROBIN.\n\n");
printf(" 3.SHORTTASK.\n\n");
printf(" 4.EXIT.\n\n\n");
printf("\n please enter your choice:");
scanf("%c",&algo);
if(algo=='1')
{
printf("Enter process number\n");
scanf("%d",&N);
create1(algo);
priority(algo);
}
else
if(algo=='2')
{
printf("Enter process number\n");
scanf("%d",&N);
create2(algo);
roundrun(algo);
}
else
if(algo=='3')
{
printf("Enter process number\n");
scanf("%d",&N);
create3(algo);
shorttask(algo);
return;
}
else if(algo=='4')
exit(0);
}
main()
{
while(1)
{
menu();
}
}