操作系统实验 进程调度算法_操作系统实验进程控制与调度算法

**

进程调度算法

**

1. 实验要求

• 编写并调试一个模拟的进程调度程序
• 基础实验：要求实现动态优先数调度
• 加分实验：要求将动态优先数调度修改成静态优先数调度
  （只需要排一次序，rtime不需要）

2.算法描述

1. “最高优先数优先”调度算法的基本思想是把CPU分配给就绪队列中优先数最高的进程。 每个进程有一个进程控制块（ PCB）表示。

2. 进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。

3. 静态优先数是在创建进程时确定的，并在整个进程运行期间不再改变。 （只需要排一次序，rtime错误）

4. 动态优先数是指进程的优先数（0-7，0-255）在创建进程时可以给定一个初始值，并且可以按一定原则修改优先数。例如：在进程获得一次CPU后就将其优先数减少1。

5. 进程等待的时间超过某一时限时增加其优先数的值，等等。动态优先数调度算法流程图如下：

3.实验源程序代码

动态优先数：

#include "stdio.h"
#include <stdlib.h>
#include <conio.h>
#define getpch(type) (type*)malloc(sizeof(type))
#define NULL 0

//进程调度源程序如下： ntime  ==   rtime 结束


struct pcb   /* 定义进程控制块PCB */
{
    char name[10];
    char state;
    int super; //优先级
    int ntime; //进程执行完成所需要时间
    int rtime; //进程已经执行时间
    struct pcb* link;
}*ready=NULL,*p;
typedef struct pcb PCB;
void sort() /* 建立对进程进行优先级排列函数*/
{
    PCB *first, *second;
    int insert=0;
    if((ready==NULL)||((p->super)>(ready->super))) /*优先级最大者,插入队首*/
    {
        p->link=ready;
        ready=p;
    }
    else /* 进程比较优先级,插入适当的位置中*/
    {
        first=ready;
        second=first->link;
        while(second!=NULL)
        {
            if((p->super)>(second->super)) /*若插入进程比当前进程优先数大,*/
            {
                /*插入到当前进程前面*/
                p->link=second;
                first->link=p;
                second=NULL;
                insert=1;
            }
            else /* 插入进程优先数最低,则插入到队尾*/
            {
                first=first->link;
                second=second->link;
            }
        }
        if(insert==0) first->link=p;
    }
}
void input() /* 建立进程控制块函数*/
{
    int i,num;
    system("cls");
    printf("\n 请输入进程个数：");
    scanf("%d",&num);
    for(i=0; i<num; i++)
    {
        printf("\n 进程号No.%d:\n",i);
        p=getpch(PCB);
        printf("\n 输入进程名:");
        scanf("%s",p->name);
        printf("\n 输入进程优先数:");
        scanf("%d",&p->super);
        printf("\n 输入进程运行时间:");
        scanf("%d",&p->ntime);
        printf("\n");
        p->rtime=0;
        p->state='w';
        p->link=NULL;
        sort(); /* 调用sort函数*/
    }
}
int space()
{
    int l=0;
    PCB* pr=ready;
    while(pr!=NULL)
    {
        l++;
        pr=pr->link;
    }
    return(l);
}
void disp(PCB * pr) /*建立进程显示函数,用于显示当前进程*/
{
    printf("\n qname \t state \t super \t ndtime \t runtime \n");
    printf("|%s\t",pr->name);
    printf("|%c\t",pr->state);
    printf("|%d\t",pr->super);
    printf("|%d\t",pr->ntime);
    printf("|%d\t",pr->rtime);
    printf("\n");
}
void check() /* 建立进程查看函数 */
{
    PCB* pr;
    printf("\n **** 当前正在运行的进程是:%s",p->name); /*显示当前运行进程*/
    disp(p);
    pr=ready;
    printf("\n ****当前就绪队列状态为:\n"); /*显示就绪队列状态*/
    while(pr!=NULL)
    {
        disp(pr);
        pr=pr->link;
    }
}
void destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/
{
    printf("\n 进程 [%s] 已完成.\n",p->name);
    free(p);
}
void running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/
{
    (p->rtime)++;
    if(p->rtime==p->ntime)
        destroy(); /* 调用destroy函数*/
    else
    {
        (p->super)--;
        p->state='w';
        sort(); /*调用sort函数*/
    }
}
int main() /*主函数*/
{
    int len,h=0;
    char ch;
    input();
    len=space();
    while((len!=0)&&(ready!=NULL))
    {
        ch=getchar();
        h++;
        printf("\n The execute number:%d \n",h);
        p=ready;
        ready=p->link;
        p->link=NULL;
        p->state='R';
        check();
        running();
        printf("\n 按任一键继续......");
        ch=getchar();
    }
    printf("\n\n 进程已经完成.\n");
    ch=getchar();

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

运行截图：

赋值注意事项：
1、进程个数>=3
2、进程所需要运行时间ntime<=5
3、ntime == rtime进程结束
1
2
3
4

静态优先数：

在动态优先数上进行改变即可：只需要排一次序，删除rtime

#include "stdio.h" 
#include <stdlib.h> 
#include <conio.h> 
#define getpch(type) (type*)malloc(sizeof(type)) 
#define NULL 0 
struct pcb { /* 定义进程控制块PCB */ 
	char name[10]; 
	char state; 
	int super; 
	int ntime; //进程执行完成所需要时间
//	int rtime; //进程已经执行时间
	struct pcb* link; 
}*ready=NULL,*p; 

typedef struct pcb PCB; 

void sort() /* 建立对进程进行优先级排列函数*/ 
{
	PCB *first, *second; 
	int insert=0; 
	if((ready==NULL)||((p->super)>(ready->super))) /*优先级最大者,插入队首*/ 
	{ 
		p->link=ready; 
		ready=p; 
	} 
	else /* 进程比较优先级,插入适当的位置中*/ 
	{ 
		first=ready; 
		second=first->link; 
		while(second!=NULL) 
		{ 
			if((p->super)>(second->super)) /*若插入进程比当前进程优先数大,*/ 
			{ /*插入到当前进程前面*/ 
				p->link=second; 
				first->link=p; 
				second=NULL;
				insert=1; 
			} 
			else /* 插入进程优先数最低,则插入到队尾*/ 
			{ 
				first=first->link; 
				second=second->link; 
			} 
		} 
		if(insert==0) first->link=p; 
	} 
}

void input() /* 建立进程控制块函数*/ 
{ 
	int i,num; 
	system("cls"); /*清屏*/
	printf("\n 请输入进程个数："); 
	scanf("%d",&num);
	for(i=0;i<num;i++) 
	{ 
		printf("\n 进程号No.%d:\n",i); 
		p=getpch(PCB); 
		printf("\n 输入进程名:"); 
		scanf("%s",p->name); 
		printf("\n 输入进程优先数:"); 
		scanf("%d",&p->super); 
		printf("\n 输入进程运行时间:"); 
		scanf("%d",&p->ntime); 
		printf("\n"); 
//		p->rtime=0;p->state='w'; 
		p->link=NULL; 
		sort(); /* 调用sort函数*/ 
	} 
} 

int space() 
{ 
	int l=0; PCB* pr=ready;
	while(pr!=NULL) 
	{ 
		l++; 
		pr=pr->link; 
	} 
	return(l); 
} 

void disp(PCB * pr) /*建立进程显示函数,用于显示当前进程*/ 
{ 
	printf("\n qname \t state \t super \t ndtime \t runtime \n"); 
	printf("|%s\t",pr->name); 
	printf("|%c\t",pr->state); 
	printf("|%d\t",pr->super); 
	printf("|%d\t",pr->ntime); 
//	printf("|%d\t",pr->rtime); 
	printf("\n"); 
}

void check() /* 建立进程查看函数 */ 
{ 
	PCB* pr; 
	printf("\n **** 当前正在运行的进程是:%s",p->name); /*显示当前运行进程*/ 
	disp(p); 
	pr=ready; 
	printf("\n ****当前就绪队列状态为:\n"); /*显示就绪队列状态*/ 
	while(pr!=NULL) 
	{ 
		disp(pr); 
		pr=pr->link; 
	} 
} 
void destroy() /*建立进程撤消函数(进程运行结束,撤消进程)*/ 
{ 
	printf("\n 进程 [%s] 已完成.\n",p->name); 
	free(p); 
} 
//void running() /* 建立进程就绪函数(进程运行时间到,置就绪状态*/
//{(p->rtime)++; 
//if(p->rtime==p->ntime) 
//destroy(); /* 调用destroy函数*/ 
//else 
//{ 
//	(p->super)--; 
//	p->state='w'; 
//	sort(); /*调用sort函数*/ 
//} 
//} 
int main() /*主函数*/ 
{ 
	int len,h=0; 
	char ch; 
	input(); 
	len=space(); 
	while((len!=0)&&(ready!=NULL)) 
	{ 
		ch=getchar(); 
		h++; 
		printf("\n The execute number:%d \n",h); 
		p=ready; 
		ready=p->link; 
		p->link=NULL; 
		p->state='R'; 
		check(); 
	//	running(); 
		printf("\n 按任一键继续......"); 
		ch=getchar(); 
	} 
	printf("\n\n 进程已经完成.\n"); 
	ch=getchar(); 
	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148