zuoyediaodu2.cpp

数据结构课程设计

/**
 *THIS IS OPERATION SYSTEM WORK.
 *SECTION 2
 *@AUTHOR 郭光景
 */
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#define getJCB(type) (type*)malloc(sizeof(type)) //计算空间；
#define NULL 0 

//DEFINE JOB'S PROCESS STRUCT
struct jcb {
	char jobName[10];
	int sentTime;
    int neededTime;
	int resourse;
	int startTime;
	char state;
	struct jcb* link;
} *top = NULL, *p, *top2 = NULL,*running = NULL;
typedef struct jcb JCB;  //mark a type of JCB;

int choose; //选择排序方式；

int T = 0; //系统时间；




//init FUNCTION
void init_JCB() {
	//初始化数据JCB
	JCB* temp;

	p = getJCB(JCB);
	top = p;


	strcpy(p->jobName, "job_A");
	p->sentTime = 0;
	p->neededTime = 4;
	p->resourse = 0;
    temp = p;

	p = getJCB(JCB);
	strcpy(p->jobName, "job_B");
	p->sentTime = 2;
	p->neededTime = 5;
	p->resourse = 0;
	temp->link = p;
	temp = p;

	p = getJCB(JCB);
	strcpy(p->jobName, "job_C");
	p->sentTime = 3;
	p->neededTime = 2;
	p->resourse = 0;
	temp->link = p;
	temp = p;

	p = getJCB(JCB);
	strcpy(p->jobName, "job_D");
	p->sentTime = 3;
	p->neededTime = 3;
	p->resourse = 0;
	temp->link = p;
	temp = p;

	p = getJCB(JCB);
	strcpy(p->jobName, "job_E");
	p->sentTime = 5;
	p->neededTime = 6;
	p->resourse = 0;
	temp->link = p;
	p->link = NULL;

	printf("初始化成功...\n");
}

//计算长度
int getLength(JCB* pr) {
	int length = 0;
	while(pr != NULL) {
		length ++;
		pr = pr->link;
	}
	return(length);
}

//sort function 
JCB* sort_S(JCB* waitList) {
	//
	JCB* whead;
	JCB* first;
	JCB* second;
	JCB* temp = waitList;
	//printf("duandian2\n");
	int l = getLength(waitList);
	int i, j;
    //getch();
	//printf("duandian3\n");
	whead = waitList;
	//first = waitList;
	if(whead == NULL || l == 1) {}
	else {
		//采用冒泡发

		for (i = 0; i < l; i ++) {
            first = whead;
			second = first->link;
			for (j = 0; j < (l - i - 1); j ++) {
				if ((first->neededTime) > (second->neededTime)) {

					first->link = second->link;
					second->link = first;
                    
					if(j == 0) {//当在表头时，处理如下；
						whead = second;
						temp = whead;
						second = first->link;
						//printf("%s\n", whead->jobName);
					} else {
					    
					    temp->link = second;
					    temp = second;
				 	    second = first->link;
					}
					if (j == (l- i -2)) p = first; //控制等待列表最后的指向
				  //printf("C");
					//printf("%s\n", p->jobName);
				//	getch();
				} else {
					temp = first;
					first = second;
					second = first->link;
				}
			}
		}
	}
	return (whead);
}

float getHRN(JCB* pr) {
	float der = 0;
	if (pr != NULL) {
		der = (float)(T - (pr->sentTime) + pr->neededTime) / pr->neededTime;
	}
	return der;
}

JCB* sort_HRN(JCB* waitList) {
	//
	JCB* whead;
	JCB* first;
	JCB* second;
	JCB* temp = waitList;
	
	//printf("duandian2\n");
	int l = getLength(waitList);
	int i, j;
    //getch();
	//printf("duandian3\n");
	whead = waitList;
	//first = waitList;
	if(whead == NULL || l == 1) {}
	else {
		//采用冒泡发

		for (i = 0; i < l; i ++) {
            first = whead;
			second = first->link;
			for (j = 0; j < (l - i - 1); j ++) {
				if (getHRN(first) < getHRN(second)) {

					first->link = second->link;
					second->link = first;
                    
					if(j == 0) {//当在表头时，处理如下；
						whead = second;
						temp = whead;
						second = first->link;
						//printf("%s\n", whead->jobName);
					} else {
					    
					    temp->link = second;
					    temp = second;
				 	    second = first->link;
					}
					if (j == (l- i -2)) p = first; //控制等待列表最后的指向
				  //printf("C");
					//printf("%s\n", p->jobName);
				//	getch();
				} else {
					temp = first;
					first = second;
					second = first->link;
				}
			}
		}
		//if(getHRN(running) < getHRN(whead)) {
			//p->link = running;
		//	p = running;
			//running->neededTime = running->neededTime - (T - running->startTime);
		//	running = whead;
			//whead = sort_HRN(whead->link);
	//	}/
	}
	return (whead);
}
//打印全部作业
void display(JCB* test) {
	int l = getLength(test);
	JCB *temp;
	if(test != NULL) {
		printf("-----------------------等待列表----------------------------\n");
		printf("作业名 \t|提交时间\t|运行时间\t|作业状态\t|响应比\n");
		temp = test;
		while(temp != NULL) {
			printf("%8s", temp->jobName);
			printf("%8d", temp->sentTime);
			printf("%8d", temp->neededTime);
			printf("%8c", temp->state);
			printf("%8f\n", getHRN(temp));
			temp = temp->link;
		}
		printf("共%d条作业记录\n", l);
		printf("-----------------------------------------------------------\n");
	} else {
		//printf("No JOBs!!-0-\n");
	}
}


void printGetWait(JCB* pr) {

	pr->state = 'W';
    printf("作业【%s】进入等待列表==...\n", pr->jobName);
}
void printGetReading(JCB* pr) {

    printf("当前作业【%s】正在运行...\n", pr->jobName);
}
void printGetFinish(JCB* pr) {

	pr->state = 'F';
    printf("作业【%s】已经运行结束...\n", pr->jobName);
}

//组建waitList 队列
JCB* getWaitList(JCB* waitList) {
	JCB* wHead;

	wHead = waitList;
    while(top != NULL && top->sentTime == T) {
		if(wHead == NULL) {
			wHead = top;
			p = top;
			top = top->link;
			p->link = NULL;
		} else {
			p->link = top;
            p = top;
			top = top->link;
			p->link = NULL;
		}	
		printGetWait(p);
		//printf("%s\n", p->jobName);
		//getch();
		//display(wHead);
	}
	//getch();
	//printf("duandian1\n");
    
	//getch();
	if(choose == 2) {
		wHead = sort_S(wHead);
	} else if(choose == 3) {
        wHead = sort_HRN(wHead);
	}

	display(wHead);
	
	return (wHead);
}

//运行函数;
void runFunction() {
	JCB* waitList = NULL;
    //JCB* running = NULL;
	JCB* temp = NULL;
	//int l = getLenght(top);
	//根据sortType选择不同的作业调度方案
    //全局变量T代表系统运行的时间，
    //系统按照T的变化而进行运行
    system("cls");
	/*初始化JCB；*/
    init_JCB();
	printf("选择调度算法：1, 先来先服务；2，短作业优先；3，高响应比\n");
	scanf("%d", &choose);
	while(choose > 4) {
		printf("wrong!!!\n");
		scanf("%d", &choose);
	}
	/*建立临时等待列表*/
	
	top2 = top;
	
	do {
		printf("\n==当前时刻是【 Time = %d 】========================================\n", T);
		//插入等待列表
		waitList = getWaitList(waitList);
        
        if(top != NULL && waitList == NULL && running == NULL) {
			printf("==================================================================\n\n\n");
			T ++; 
			continue;
		}
        //检查是否有运行，没有则到等待列表里提取；
		//有则继续运行，并检查是否结束
		if (running == NULL) {
			    running = waitList;
			    waitList = waitList->link;
			    running->startTime = T;
			    running->state = 'R';
				running->link = NULL;
				if (temp != NULL) temp->link = running;
			    printf("作业【 %s 】开始进入CPU运行！\n", running->jobName);
		} else {
		        if((running->neededTime + running->startTime) == T) {
	                printGetFinish(running);
					if(waitList != NULL) {
						temp = running;
						temp->link = waitList;
						running = waitList;
			            waitList = waitList->link;
			            running->startTime = T;
			            running->state = 'R';
			            printf("作业【 %s 】开始进入CPU运行！\n", running->jobName);
					} else {
						temp =running;
					    running = NULL;
					}
				} else {
			        printGetReading(running);
				}
		}
		
		
		printf("==================================================================\n\n\n");
		//getch();
		T ++;
	}while (top != NULL || waitList != NULL || running != NULL);
	printf("全部作业运行结束！\n按任意键查看结果...");
}

//================================================================================
int getZhouzhuang(JCB* temp) {
	int zhouzhuan;
	zhouzhuan = temp->startTime + temp->neededTime - temp->sentTime;
	return zhouzhuan;
}

float getDC(JCB* temp) {
	float dc;
	dc = (float)getZhouzhuang(temp) / temp->neededTime;
	return dc;
}

void printResult() {
	 p = top2;
	 int sum = 0;
	 float sumDC = 0;
	 system("cls");
	 while(p != NULL) {
		 printf("作业名称     【 %s 】\n", p->jobName);
	     printf("提交时刻      %d\n", p->sentTime);
		 printf("运行时间      %d\n", p->neededTime);
		 printf("开始时刻      %d\n", p->startTime);
		 printf("完成时刻      %d\n", p->startTime + p->neededTime);
		 printf("周转时间      %d\n", getZhouzhuang(p));
		 printf("带权周转时间  %0.2f\n", getDC(p));
		 printf("======================================\n");
         sum += getZhouzhuang(p);
		 sumDC += getDC(p);
		 p = p->link;
	 }
	 printf("【该组作业的平均周转时间是：    %0.2f】\n", (float)sum / getLength(top2));
	 printf("【该组作业的平均带权周转时间是：%0.2f】\n", sumDC / getLength(top2));
}



void main() {
	runFunction();
	
	getch();
	//display(top2);
	//getch();
	printResult();
	getch();
}