记录：2022-9-12 多路归并 超级丑数 败者树 调度算法实现 帧分配 系统抖动 内存映射文件 内核内存分配

学习时间：2022-9-12

学习内容

1、Leetcode 多路归并

264. 丑数 II
313. 超级丑数
373. 查找和最小的 K 对数字
786. 第 K 个最小的素数分数
1508. 子数组和排序后的区间和
719. 找出第 K 小的数对距离
1439. 有序矩阵中的第 k 个最小数组和
今天做了一类新题，上述列表里面的超级丑数，这种题为多路归并，感觉是用到了动态规划的思想，但实际上和以前做的动态规划还是有不少的区别。

「多路归并」的核心思想与合并 n 个有序链表极其相似，题目详情可见 合并两个有序链表 合并K个升序链表 将 n
个有序链表的头节点加入小根堆的优先队列中，由于n个链表都是递增的顺序，所以第一个最小的元素肯定在这 n 个头节点中产生
选择最小元素后，将该最小元素所在的链表后移一位，并将后一位元素加入队列中，以此类推…

超级丑数

这个题我用的小根堆，会遇到超时和溢出问题，只能使用动态规划

class Solution {
 public int nthSuperUglyNumber(int n, int[] primes) {
     // 指针：每个质因数对应一个指针
     int[] p = new int[primes.length];
     // 由于数据加强了，这里需要使用 long
     long[] ans = new long[n + 1];
     ans[1] = 1;
     // 初始化每个指针指向第一个丑数
     Arrays.fill(p, 1);
     for (int i = 2; i <= n; i++) {
        // 求最小值
        long min = Integer.MAX_VALUE;
        for (int j = 0; j < primes.length; j++) {
            min = Math.min(min, ans[p[j]] * primes[j]);
        }
        // 指针后移 (同时具有去重的效果)
        for (int j = 0; j < primes.length; j++) {
            if (min == ans[p[j]] * primes[j]) {
                p[j]++;
            }
        }
        // 存储到 ans 中
        ans[i] = min;
     }
    // 返回第 n 个丑数
     return (int) ans[n];
    }
}
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

2、败者树

一种对多路归并的优化方法
多路归并可以减少系统的IO次数，败者树可以减少归并次数

3、Linux调度算法具体实现

counter是时间片，这个算法保证了时间片调度和最短时间片调度与他们之间的折中，该程序巧妙的将counter时间片与优先级相结合

while(--i){
	if(p.state == RUNNING && p.counter > c){
		c = p.counter;
		next = i;
	}
}
if(c){
	break;//此时找到就绪状态并且有时间片的进程，退出循环 执行该进程next
}
1
2
3
4
5
6
7
8
9

//分配时间片
for(p = last_task;p>first_task;--p){
	p.counter = p.counter>>2 + p.priority;//每次加1/2 对于等待IO的进程，counter将会越来越高，符合前台应用优先级高的特点
}
1
2
3
4

3、内存：帧分配 系统抖动 内存映射文件 内核内存分配

帧分配

大小

帧的大小会受两方面限制：

1. 所分配的帧不能超过可用帧的数量
2. 必须分配最小数量的帧（性能，防止抖动）

分配算法

平均分配 比例分配

平均分配：按照进程数量平均分配帧，剩下的帧作为空闲帧缓冲池
比例分配：按照进程中内存的大小按比例分配帧

全局分配 局部分配

全局分配允许一个进程从所有的帧集合中找一个帧置换，不管这个帧是否已经分配出去
局部分配：只能分配不能使用其他进程已经使用的帧

系统抖动

若出现分配帧过小的问题，就很可能出现系统的抖动，这个问题主要是因为：
如果一个帧他需要的页多于可以分配的帧，则每一次替换，都会导致缺页错误，每一次缺页错误都会让CPU等待（CPU利用率降低），重新出现页面调度。
如此高速的页面调度，就是系统抖动
这种抖动的产生，很大原因是由于全局分配产生的，每次缺页，就去其他进程找帧，如果其他进程用，由会找帧，这样就会让系统的吞吐量陡降，因为都去调页了。
此时如果想要提高CPU利用率并降低抖动，必须降低多道程度
使用局部调页算法和优先级置换算法可以限制系统的抖动，并且可以使用工作集的方式，限制抖动

工作集模型 ※

工作集是一种大而全的模型，这个模型基于局部性假设（在计算机学科的概念中，局部性原理是一个常用的术语，指处理器在访问某些数据时短时间内存在重复访问，某些数据或者位置访问的概率极大，大多数时间只访问局部的数据），这个模型采用参数Δ，检查最近使用的Δ个页面引用，这最近的这些页面集合就是工作集。如果一个页面处于活动使用状态，那么他处于工作集中。
工作集的精度取决于Δ的大小，当Δ够大时，相当于就是整个进程的页面的集合。如果Δ太小，不能包含整个局部。
一旦选中了Δ，工作集的模型使用就很简单：操作系统监视每个进程的工作集，并为他分配大于其工作集的帧数，如果还存在额外的帧，则可以启动另外一个进程。

缺页错误频率

工作集用到系统抖动上面，有点重了，不够轻量，缺页错误频率的方法，是解决系统抖动的一个轻量级解决方案
主要思想是控制缺页的错误率，如果缺页率太高，说明可能需要更多的帧，如果缺页率太低，则说明进程有太多的帧，以这种方法来动态平衡，设置缺页错误率的上下限，因此，可以直接测量和控制缺页错误率，以防止抖动

内存映射文件

允许一部分虚拟内存与文件进行逻辑关联，这种方法叫内存映射文件
这种方式让文件担任一个中间件的职责，进程的虚拟内存将映射到文件上，然后文件再映射到物理内存上。
多个进程允许并发的内存映射同一文件，以便允许数据共享。

以一个Windows的生产者消费者内存映射读取为例：

//消费者
int main(int argc,char *argv[])
{
	HANDLE hMapFile;
	LPVOID lpMapAddress;
	//找到映射文件
	hMapFile = OpenFileMapping(FILE_MAP_ALL_ACCESS,FALSE,TEXT("SharedObject"));
	lpMapAddress = MapViewOfFile(hMapFile,FILE_MAP_ALL_ACCESS,0,0,0);//创建读取视图
	printf("Read message %s",lpMapAddress);//读取内容
	UnmapViewOfFile(lpMapAddress);
	CloseHandle(hMapFile);
}
1
2
3
4
5
6
7
8
9
10
11
12

//生产者
int main(int argc,char *argv[])
{
	HANDLE hMapFile，hFile;
	LPVOID lpMapAddress;
	//创建文件
	hFile = CreateFile("temp.txt",GENERIC_READ,0,NULL,OPEN_ALWAYS,FILE_ATTRIBUTE_NORMAL,NULL);
	//映射该文件
	hMapFile = CreateFileMapping(hFile,NULL,PAGE_READWRITE,0,0,TEXT("SharedObject"));
	lpMapAddress = MapViewOfFile(hMapFile,FILE_MAP_ALL_ACCESS,0,0,0);//创建读取视图
	sprintf(lpMapAddress,"shared message");//写入内容
	UnmapViewOfFile(lpMapAddress);
	CloseHandle(hMapFile);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

内核内存分配

当数据小于一页时，如何分配？

1. 内核应该保守的使用内存，并努力最小化碎片浪费。
2. 用户模式进程分配的页面不必位于连续物理内存

伙伴系统

伙伴系统，类似于把内存分离，举个例子：如果有一个21KB的进程需要分配，内存段最初的大小是256KB，此时分为伙伴A1和伙伴A2,每个伙伴128KB，此时21KB还是小于128KB，继续分离成伙伴B1和B2，每个大小64KB，由于比21KB大的最小内存为32KB，所以当分离成32KB时，不再继续分离，分配伙伴C1给进程。
好处：可以快速合并分成更大的段
坏处：形成内部碎片

slab分配

每个slab由一个或多个物理连续的页面组成，每个cache由一个或多个物理连续的页面组成
每个cache中包含一定内核数据结构的实例，如信号量，进程描述符等。
cache创建时标记若干free对象在cache中，对象数量取决于相关slab的大小