作业调度实习报告

2009118252 计科一 樊星 一、实习题目

采用先来先服务算法和运行时间最短者优先算法模拟设计作业调度程序。 二、结构及说明

程序采用结构体来定义进程控制块PBC单元，整个控制块利用单向循环链表。 typedef struct tagPCB //进程控制块PBC {

int num; //进程号 char user; //用户名 char name[5]; //进程名 struct tagPCB *next; //下个进程 int demand_time; //需求时间 int demand_memory; //需求内存 int demand_tap; //需求磁带 int used_time; //已用时间

}PCB;

同时采用另一结构体来定义作业控制块，整个控制块利用单向循环列表。 typedef struct tagWORK //作业控制块 {

int num; //作业号 char user; //用户名 char name[5]; //作业名 struct tagWORK *next; //下个作业 int demand_time; //需求时间 int demand_memory; //需求内存 int demand_tap; //需求磁带

}WORK;

分别编写先到先服务（FIFS）与短作业优先（SJF）的作业调度算法： int FIFS(); int SJF();

在实际操作中分别用这两个函数来替代作业调度过程，达到不同的效果。 三、源程序 #include \"stdafx.h\" #include \"stdlib.h\" #include \"iostream.h\" #include \"string.h\" #include \"fstream.h\"

//-----------------------------------------------

typedef struct tagPCB //进程控制块PBC {

int num; //进程号 char user; //用户名

char name[5]; //进程名 struct tagPCB *next; //下个进程 int demand_time; //需求时间 int demand_memory; //需求内存 int demand_tap; //需求磁带 int used_time; //已用时间

}PCB;

typedef struct tagWORK //作业控制块 { int num; //作业号

char user; //用户名 char name[5]; //作业名 struct tagWORK *next; //下个作业 int demand_time; //需求时间 int demand_memory; //需求内存 int demand_tap; //需求磁带

}WORK;

//--------------------------------------------------

WORK *work_head,*work_p; //工作表链首指针，活动指针 PCB *head_r, *r_p; //就绪链首指针，活动指针 int process_num=0; //进程数 int free_memory=100; //内存剩余空间 int free_tap=5; //磁带剩余数 int current_thread=0; //当前进程数 int total_work;

//----------------------------------------------------

int i,j; //自由变量 ifstream infile(\"indata.txt\"); //文件输入 ofstream outfile(\"outdata.txt\"); //文件输出 //----------------------------------------------------函数声明 int create_work();

int init_work_table(WORK **,WORK **); int enter_work_table(WORK **,WORK **); WORK *exit_work_table(WORK *); int create_process(WORK *); int init_link(PCB**,PCB**); int enter_link(PCB*,PCB*); PCB *exit_link(PCB*);

int random_choose_process(); int execute_process(PCB *); int FIFS();

int SJF();

//----------------------------主程序---------------------------// int main(int argc, char* argv[])

{

init_link(&head_r, &r_p);

init_work_table(&work_head,&work_p); //////////////////////////////////////初始化

infile>>total_work; for (i=0;icreate_work();

while ((current_thread < 2)&&(total_work > 0))

FIFS();//作业调度，下一次用SJF()替代

}

while (head_r->next != head_r) { }

printf(\"Hello GHouan!\\n\"); infile.close(); outfile.close(); return 0;

random_choose_process();

if ((current_thread < 2)&&(total_work > 0)) { FIFS();//作业调度，下一次用SJF()替代 }

}

/*****************************************************************************/ int create_work() //创建作业信息 {

WORK *temp;

temp = (WORK *)malloc(sizeof(WORK)); temp->num = i; infile>>temp->user; infile>>temp->name;

infile>>temp->demand_time; infile>>temp->demand_memory; infile>>temp->demand_tap;

enter_work_table(&work_p,&temp); return 0; }

int init_work_table(WORK **head,WORK **p) //作业队列初始化 {

(*head) = (WORK *)malloc(sizeof(WORK));

(*head)->next = (*head);

(*p) = (*head); return 0; }

int enter_work_table(WORK **p,WORK **temp) //加入作业队列 {

(*p)->next = (*temp);

if (total_work-1 == (*temp)->num) { } else { }

(*p)= (*temp);

(*temp)->next = work_head;

return 0; }

WORK *exit_work_table(WORK *p) //退出作业队列 {

WORK *q; q = p;

while (p != q->next) { q = q->next; }

q->next = p->next;

return p; }

/*****************************************************************************/ int create_process(WORK *current) //创建进程 {

PCB *temp;

temp = (PCB *)malloc(sizeof(PCB)); temp->num = process_num++; temp->user = current->user; strcpy(temp->name,current->name);

temp->demand_time = current->demand_time; temp->used_time = 0;

temp->demand_memory = current->demand_memory; temp->demand_tap = current->demand_tap;

free_memory-=current->demand_memory; free_tap-=current->demand_tap; enter_link(head_r,temp);

current_thread++; //增加一线程

return 0; }

int init_link(PCB **head,PCB **p) //PBC表初始化 { (*head) = (PCB *)malloc(sizeof(PCB)); (*head)->demand_time = 0; (*head)->used_time = 32768; (*head)->next = (*head); (*p) = (*head);

return 0;

}

int enter_link(PCB *head,PCB *temp) { temp->next = head->next; head->next = temp;

return 0;

}

PCB *exit_link(PCB *p) { PCB *q; q = p;

free_memory+=p->demand_memory; free_tap+=p->demand_tap; while (p != q->next) { q = q->next;

}

q->next = p->next;

current_thread--; return p;

}

//--------------------------------------------

int random_choose_process() { int x;

x = rand() % process_num; r_p = head_r; for (j=0;jnext;

}

//加入进程队列 //退出进程队列 //减少一线程 //处理器随机调度算法 //产生随机数 //活动指针返回链首 if (r_p == head_r)

{ r_p = r_p->next; }

execute_process(r_p); }

int execute_process(PCB *p) //作业执行过程 {

(p->used_time)++;

outfile<name<<\"运行时间+1\"<demand_time == p->used_time) {

exit_link(p);

outfile<<\"用户\"<user<<\"的作业\"<name<<\"执行完毕\"<}

return 0; }

/*************************************************************/ int FIFS() //先进先服务作业调度 {

WORK *temp;

temp = work_head->next;

while ((free_memory-(temp->demand_memory)<0) || (free_tap-(temp->demand_tap)<0)) {

temp = temp->next; }

if (work_head == temp) {

return 0;

}

create_process(temp);

outfile<<\"作业\"<name<<\"被选入，放入主存执行\"<if (0 == total_work) { outfile<<\"输入井中已无作业\"<return 0; }

int SJF() //短作业优先作业调度

{

WORK *temp;

int min_time = 32768; int indicate_num;

temp = work_head->next; while(temp != work_head) {

if ((temp->demand_time < min_time) && (free_memory-(temp->demand_memory)>=0) && (free_tap-(temp->demand_tap)>=0))

{

indicate_num = temp->num;

min_time = temp->demand_time;

}

temp = temp->next;

}

temp = work_head->next;

while(temp->num != indicate_num) { temp = temp->next; }

create_process(temp);

outfile<<\"作业\"<name<<\"被选入，放入主存执行\"<if (0 == total_work)

outfile<<\"输入井中已无作业\"<{

} return 0; }

四、运行参数及结果 运行前作业表：

用户名 A B C D E

输入数据： 5

A ZYA 3 15 2

作业名 ZYA ZYB ZYC ZYD ZYE 状态 收容 收容 收容 收容 收容 运行时间 0.3小时 0.5小时 0.1小时 0.4小时 0.1小时 资源要求 主存 15k 60k 50k 10k 30k 磁带 2 1 3 2 3 B ZYB 5 60 1 C ZYC 1 50 3 D ZYD 4 10 2 E ZYE 1 30 3 输出

FIFS算法： 作业ZYA被选入，放入主存执行 作业ZYB被选入，放入主存执行 ZYB运行时间+1 ZYB运行时间+1 ZYB运行时间+1 ZYB运行时间+1

ZYB运行时间+1

用户B的作业ZYB执行完毕 作业ZYC被选入，放入主存执行 ZYC运行时间+1

用户C的作业ZYC执行完毕 作业ZYD被选入，放入主存执行 ZYA运行时间+1 ZYA运行时间+1 ZYA运行时间+1

用户A的作业ZYA执行完毕 作业ZYE被选入，放入主存执行 输入井中已无作业 ZYE运行时间+1

用户E的作业ZYE执行完毕 ZYD运行时间+1 ZYD运行时间+1 ZYD运行时间+1 ZYD运行时间+1

用户D的作业ZYD执行完毕 SJF算法：

作业ZYC被选入，放入主存执行 作业ZYA被选入，放入主存执行 ZYA运行时间+1 ZYA运行时间+1 ZYA运行时间+1

用户A的作业ZYA执行完毕 作业ZYD被选入，放入主存执行 ZYD运行时间+1 ZYC运行时间+1

用户C的作业ZYC执行完毕 作业ZYE被选入，放入主存执行 ZYE运行时间+1

用户E的作业ZYE执行完毕 作业ZYB被选入，放入主存执行 输入井中已无作业 ZYB运行时间+1 ZYB运行时间+1 ZYD运行时间+1 ZYB运行时间+1 ZYB运行时间+1 ZYB运行时间+1

用户B的作业ZYB执行完毕 ZYD运行时间+1 ZYD运行时间+1

用户D的作业ZYD执行完毕