FIFO调度算法

FIFO：First-In-First-Out
中文名：先进先出调度算法

定义：

一种缓存调度算法，经常用作内存的页面置换算法。FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中停留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，新页面从队尾插入，每次淘汰队头页面（最老的页面）。但该算法并不是每次都是淘汰最老页面，因为在进程中，有些页面经常被访问，但被访问到的页面已存在于缓存中时缓存队列不会变换位置，也就是说当你访问的页面在缓存中且该页面位于队头时，尽管它已经算作是一个最新页面了，但FIFO算法还是会把它还是算作停留时间最长页面，因为缓存队列顺序没有发生改变（这一点于LRU截然相反）。下一次访问一个新页面时淘汰的永远都是队头。因此，FIFO 算法并不能保证每次淘汰的都是最老页面。

可能定义你看起来太过于抽象，下面用一个具体例子描述FIFO算法的调度过程

可以观察与LRU算法不同之处

假设缓存大小为3，访问页面顺序为2,6,4,8,5,4,1,5,6,3,9。

->2
->6 2
->4 6 2
->8 4 6
->5 8 4
->5 8 4 4调入内存，但4已经存在，故内存结构不变
->1 5 8
->1 5 8 5调入内存，但5已经存在，故内存结构不变
->6 1 5
->3 6 1
->9 3 6

C语言代码

#include<stdio.h>
#define MAX 3//缓存最大页面容量 
typedef struct fifo{
	int fifo[MAX];//存放页面号 
}FIFO;

int main()
{
	int flag = 0;//0表示访问的这个页面是一个新页面，1表示访问的这个页面已存在于缓存中 
	int data;//页面号 
	fifo f;
	for(int i=0; i<MAX; i++)
	{
		f.fifo[i]=-1;
	}
	for(int i=0; i<MAX; i++)
	{
		flag=0;
		printf("请输入第%d个页面号：",i);
		scanf("%d",&data);
		for(int j=0; j<MAX; j++)
		{
			if(data == f.fifo[j])//如果这个页面已存在于缓存中 
			flag = 1;
		}
		if(flag != 1)//如果这个页面不存在于缓存中 
		f.fifo[i] = data;
		else//如果这个页面已存在于缓存中 
		{
			printf("对不起，你输入的页面也存在，请重新输入！\n\n");
			i--;
		}
		
	}
	printf("开始页面分别为\n");
	printf("->->->->->->->->->\n");
	for(int i = MAX-1; i >= 0; i--)
	printf("%d \t",f.fifo[i]);
	printf("\n\n\n");
	while(true)
	{
		flag = 0;
		printf("请输入一个新的页面：");
		scanf("%d",&data);
		for(int i=0; i<MAX; i++)
		{
			if(data == f.fifo[i])//如果这个页面已存在于缓存中 
			flag = 1;
		}
		if(flag==1)//如果这个页面已存在于缓存中 
		{
			printf("对不起，你输入的页面也存在，请重新输入！\n\n");
			continue;
		}
		else//如果这个页面不存在于缓存中 
		for(int i=0; i<MAX; i++)
		{
			f.fifo[i] = f.fifo[i+1];
			if(i == MAX-1)
			f.fifo[i] = data;
		}
		printf("换替换后的页面结果为\n");
		printf("->->->->->->->->->\n");
		for(int i=MAX-1; i>=0; i--)
		printf("%d \t",f.fifo[i]);
		printf("\n\n\n");
		
	}
	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

执行结果

请输入第0个页面号：5
请输入第1个页面号：6
请输入第2个页面号：6
对不起，你输入的页面也存在，请重新输入！

请输入第2个页面号：5
对不起，你输入的页面也存在，请重新输入！

请输入第2个页面号：4
开始页面分别为
->->->->->->->->->
4       6       5


请输入一个新的页面：6
对不起，你输入的页面也存在，请重新输入！

请输入一个新的页面：5
对不起，你输入的页面也存在，请重新输入！

请输入一个新的页面：3
换替换后的页面结果为
->->->->->->->->->
3       4       6


请输入一个新的页面：1
换替换后的页面结果为
->->->->->->->->->
1       3       4


请输入一个新的页面：
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

总的来说，这个算法比较简单。用的是结构体实现。
本人菜鸟一枚妥妥，可能代码写的不规范也可能代码有冗余存在，或者定义出现的名词不规范等问题，欢迎各位大佬指教。