前言
去年学的操作系统，现在有学妹问调度算法实现发现自己没有复习竟然忘了很多，借此机会把原来的知识捡回来。本文是原来通过C实现作业调度算法的集合。
一、进程入队与出队模拟
入队代码：
#include <malloc.h> #include <stdio.h> #include <string.h> #define NULL 0 typedef struct processpcb { int id;/*进程控制块编号*/ struct processpcb *next; }node; int n; node *creat(void) /*建立进程控制块队列表*/ { node *head,*p1,*p2; n=0; printf("Input processpcb table:ID\n"); p1=p2=(node *)malloc(sizeof(node)); scanf("%d",&p1->id); head=NULL; while (p1->id>0) { n=n+1; if (n==1) head=p1; else p2->next=p1; p2=p1; p1=(node *) malloc (sizeof(node)); scanf("%d",&p1->id); } p2->next=NULL; return(head); } node *append(node *head,node *q) /*增加一个进程进入队列*/ { node *p=head; if(!p) return q; else { while(p->next) p=p->next; p->next=q; q->next=NULL; return head; } } void print (node *head) /*输出链表*/ { node *p; p=head; if(!p) printf("链表为空!"); else { printf("元素为："); while(p) { printf("%5d",p->id); p=p->next; } } } int main() { node *p,*q; int pcbid; p=creat(); printf("\nappend a processpcb\n"); scanf("%d",&pcbid); q=(node *)malloc(sizeof(node)); q->id=pcbid; q->next=NULL; printf("\ninit_processpcb queue is:\n"); print(p); p=append(p,q); printf("\nappend_processpcb queue is:\n"); print(p); }
出队代码：
#include <malloc.h> #include <stdio.h> #include <string.h> #define NULL 0 typedef struct processpcb { int id;/*进程控制块编号*/ struct processpcb *next; }node; int n; node *creat(void) /*建立进程控制块队列表*/ { node *head,*p1,*p2; n=0; printf("Input processpcb table:ID\n"); p1=p2=(node *)malloc(sizeof(node)); scanf("%d",&p1->id); head=NULL; while (p1->id>0) { n=n+1; if (n==1) head=p1; else p2->next=p1; p2=p1; p1=(node *) malloc (sizeof(node)); scanf("%d",&p1->id); } p2->next=NULL; return(head); } node *find(node *head,int x) { node *p=head->next; while(p&&p->id!=x) p=p->next; if(!p) return 0; else return p; } node *del(node *head,int pcb) { node *p=head,*q; q=p->next; if(p->id==pcb) return q; while(q&&q->id!=pcb) { p=q; q=q->next; } if(p->id=pcb) p->next=q->next; return head; } void print (node *head) /*输出链表*/ { node *p; p=head; if(!p) printf("链表为空!"); else { printf("元素为："); while(p) { printf("%5d",p->id); p=p->next; } } } int main() { node *p,*q; int pcbid; p=creat(); printf("\nappend a processpcb\n"); scanf("%d",&pcbid); q=(node *)malloc(sizeof(node)); q->id=pcbid; q->next=NULL; printf("\ninit_processpcb queue is:\n"); print(p); p=del(p,pcbid); printf("\nappend_processpcb queue is:\n"); print(p); }
二、FCFS调度算法
代码：
#include <malloc.h> #include <stdio.h> #include <string.h> typedef struct table { int key; /*进程ID号*/ int sequence; /*进程进入队列顺序号*/ char message[10]; /*进程说明信息*/ struct table *next; }node; /* 定义函数，建立进程链表 */ node *creat(void) { node *head; node *p1, *p2; int n = 0; p1 = p2 =(node *)malloc(sizeof(node)); scanf("%d%d", &p1->key, &p1->sequence); gets(p1->message); head = NULL; while (p1->key != 0) { //输入0表示结束 ++n; if (n == 1) head = p1; else p2->next = p1; p2 = p1; p1 = (node *)malloc(sizeof(node)); scanf("%d%d", &p1->key, &p1->sequence); gets(p1->message); } p2->next = NULL; return head; } /* 模拟当前就绪进程队列中最先进入进程出队并输出的调用过程 */ node *fcfs(node *head) { node *p, *q; p = head; printf("key=%d,sequence=%d,message=%s\n",p->key,p->sequence,p->message); q = p; p = p->next; free(q); return p; } void print(node *head) //输出链表 { node *p; printf("\n The table is : \n"); p = head; while (p) { printf("%d, %d, %s\n", p->key, p->sequence, p->message); p = p->next; } } int main(void) { int count = 0; node *p, *q; printf("新建的进程控制表为:\nkey sequence message\n"); p = creat(); //输入进程控制表 print(p); while (p) { ++count; printf("\n第%d次被调度的就绪进程为:\n",count); q = fcfs(p); p = q; } return 0; }
3.优先级调度算法
这个好像没有找到，回头再补吧。
4.时间片轮转调度算法
#include <malloc.h> #include <stdio.h> #include <string.h> #define NULL 0 typedef struct table { int key; /*进程ID号*/ int run_time; /*进程运行时间*/ char message[10]; /*进程说明信息*/ struct table *next; }node; node *creat(void) /*定义函数，输入ID号和顺序号，按照输入次序建立进程链表*/ { node *head,*p1,*p2; int n=0; p1=p2=(node *)malloc(sizeof(node)); scanf("%d %d %s",&p1->key,&p1->run_time,&p1->message); head=NULL; while (p1->run_time>0) { n=n+1; if (n==1) head=p1; else p2->next=p1; p2=p1; p1=(node *) malloc (sizeof(node)); scanf("%d %d %s",&p1->key,&p1->run_time,&p1->message); } p2->next=NULL; return(head); } void print (node *head) /*输出链表*/ { node *p; p=head; if(!p) { printf("该链表为空！"); } else { while(p) { printf("%d , ",p->key); printf("%d , ",p->run_time); printf("%s",p->message); p=p->next; printf("\n"); } } } node *insert(node *head,node *news) /*将进程news插入到队列尾部*/ { node *t; t=head; while(t->next) { t=t->next; } t->next=news; news->next=NULL; return head; } node *timeslice(node *head,int cpu_base_time) /*模拟时间片轮转调度过程:队列首进程使用一个时间片的CPU*/ { node *r,*q; r=head; q=(node *)malloc(sizeof(node)); if(r->run_time>cpu_base_time) { q->run_time=r->run_time-cpu_base_time; q->key=r->key; strcpy(q->message,r->message); insert(r,q); } return head; } void main() { int count=0,cpu_base_time; node *p; printf("新建的进程控制表为:\nkey run_time message\n"); p=creat(); /*输入进程控制表*/ printf("所建的进程控制表为:\n"); print(p); /*输出原始进程控制表*/ printf("CPU运行的单位时间片cpu_base_time为:\n"); scanf("%d",&cpu_base_time); while(p) /*模拟按单位时间片进程逐个被调度并进入CPU运行的过程*/ { p=timeslice(p,cpu_base_time); printf("第%d次被调度的就绪进程:\n",count+1); printf("key=%d,run_time=%d,message=%s\n",p->key,p->run_time,p->message); printf("recent table is:\n"); print(p->next); printf("\n"); count++; p=p->next; } printf("distribute is over!\n"); }
