题目描述
现代计算机系统中通常存在多级的存储设备,针对海量 workload 的优化的一种思路是将热点内存页优先放到快速存储层级,这就需要对内存页进行冷热标记。
一种典型的方案是基于内存页的访问频次进行标记,如果统计窗口内访问次数大于等于设定阈值,则认为是热内存页,否则是冷内存页。
对于统计窗口内跟踪到的访存序列和阈值,现在需要实现基于频次的冷热标记。内存页使用页框号作为标识。
输入描述
第一行输入为 N
,表示访存序列的记录条数,0 < N
≤ 10000
第二行为访存序列,空格分隔的 N
个内存页框号
第三行为阈值
输出描述
第一行输出标记为热内存的内存页个数,如果没有被标记的热内存页,则输出 0 。
如果第一行 > 0,则接下来按照访问频次降序输出内存页框号,一行一个,频次一样的页框号,页框号小的排前面。
用例1
输入
10
1 2 1 2 1 2 1 2 1 2
5
输出
2
1
2
说明 :在这个例子中,内存页框号 1 和 2 都被访问了 5 次,达到了阈值,因此它们被标记为热内存页。输出首先是热内存页的数量 2,然后是按照访问频次降序排列的页框号 1 和 2(频次一样的页框号,页框号小的排前面)。
用例2
输入
5
1 2 3 4 5
3
输出
0
说明:在这个例子中,没有任何内存页的访问次数达到阈值 3,因此没有热内存页,输出为 0。
代码
#include <stdio.h>
#include <stdlib.h>
// 定义一个常量,用于限制内存页框号的最大数量
#define MAX_NUM 10000
// 定义结构体PageFrequency,存储每个内存页框号及其访问频次
typedef struct {
int num; // 内存页框号
int frequency; // 访问频次
} PageFrequency;
// 定义比较函数cmp,用于qsort排序。这里按照访问频次降序排序,频次相同时按照页框号升序排序
int cmp(const void *a, const void *b) {
PageFrequency *p1 = (PageFrequency *)a;
PageFrequency *p2 = (PageFrequency *)b;
if (p1->frequency != p2->frequency) {
return p2->frequency - p1->frequency; // 频次高的排在前面
} else {
return p1->num - p2->num; // 频次相同时,页框号小的排前面
}
}
int main() {
int n; // 访存序列记录条数
scanf("%d", &n);
// 创建数组page存储输入的访存序列
int page[n];
for (int i = 0; i < n; i++) {
scanf("%d", &page[i]);
}
int threshold; // 访问频次阈值
scanf("%d", &threshold);
// 初始化所有内存页框的访问频次为0
PageFrequency p[MAX_NUM] = {0};
// 根据访存序列统计各个内存页框的访问频次
for (int i = 0; i < n; i++) {
p[page[i]].num = page[i]; // 设置页框号
p[page[i]].frequency++; // 增加对应页框号的访问频次
}
// 创建hot数组存储标记为热内存页的页框信息
PageFrequency hot[MAX_NUM];
int hot_num = 0; // 热内存页的数量
// 遍历所有内存页框,找出访问频次大于等于阈值的页框并加入hot数组
for (int i = 0; i < MAX_NUM; i++) {
if (p[i].frequency >= threshold) {
hot[hot_num].num = p[i].num;
hot[hot_num].frequency = p[i].frequency;
hot_num++;
}
}
// 输出热内存页的数量
printf("%d\n", hot_num);
// 如果存在热内存页,则对hot数组进行排序,并输出排序后的页框号
if (hot_num > 0) {
qsort(hot, hot_num, sizeof(PageFrequency), cmp);
for (int i = 0; i < hot_num; i++) {
printf("%d\n", hot[i].num);
}
}
return 0;
}
注意
1、为什么 PageFrequency *p1
这里面要加*
在C语言中,*
是指针运算符。当我们声明一个变量如 PageFrequency *p1
时,p1
是一个指向 PageFrequency
结构体类型的指针。
这里的 *
表示 p1
变量存储的是一个地址,这个地址指向一块内存区域,该内存区域存放着一个 PageFrequency
结构体实例的数据(即包含 num
和 frequency
成员)。
在 cmp
函数内部,我们需要访问通过指针传递进来的结构体成员,所以需要对指针解引用。例如,p1->frequency
实际上是访问 p1
所指向的 PageFrequency
结构体实例中的 frequency
成员。这里的 ->
运算符用于通过结构体指针访问结构体成员。
总结一下,PageFrequency *p1
中的 *
表示 p1
是一个指针,并且在后续代码中使用 p1->frequency
或 p1->num
来访问结构体成员时,体现了指针解引用的过程。
2、结构体的初始化
typedef struct {
int num;
int frequency;
} Hot;
Hot hot[MAX_NUM]={0};
Hot hot[MAX_NUM]={0}
;大括号 {0}
是对数组所有元素进行初始化,这里的 0
表示对数组中每个结构体实例的所有成员都初始化为零(即 num
和 frequency
都被初始化为 0
)。