记录：2022-9-10 完美数 快乐数 括号生成 请求调页 页面置换 写时复制 页面缓冲算法

学习时间 2022-9-10

学习内容

1、leetcode 两道简单题 一道中等题

优化是靠的退出时机，当除出来的数已经小于除数时，说明后续的已经不需要继续做了，并且如果除出来的余数为0，说明这两个数都是正因子

class Solution {
    public boolean checkPerfectNumber(int num) {
        int ans = 1;
        if(num == 1){
            return false;
        }
        for(int i = 2;i<num;i++){
            int num2 = num / i;
            if(num2 <= i){
                break;
            }
            if(num % i == 0){
                //可以找到两个正因子
                ans += i;
                ans += num2;
            }
        }
        if(ans == num) return true;
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

如果不是快乐数，他在循环的过程中会重复某个值，这就导致他无法回到1

class Solution {
    public boolean isHappy(int n) {
        //中途若出现循环 则结束
        HashSet<Integer> set = new HashSet<Integer>();
        while(n != 1){
            n = getNext(n);
            if(set.contains(n)){
                return false;
            }
            set.add(n);
        }
        return true;
    }
    public int getNext(int n){
        int sum = 0;
        while(n != 0){
            int s1 = n%10;
            sum+=s1*s1;
            n = n/10;
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

我的解法（暴力枚举）

class Solution {
    public List<String> generateParenthesis(int n) {
        HashSet<String> set = new HashSet<String>();
        set.add("()");
        //滑动窗口
        for(int i = 1;i<n;i++){
            HashSet<String> newSet = new HashSet<String>();
            for(String s : set){
                newSet.add("("+s+")");
                for(int j = 0;j<=s.length();j++){
                    newSet.add(s.substring(0,j)+"()"+s.substring(j,s.length()));
                }
            }
            set = newSet;
        }
        return new ArrayList(set);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这个题我更愿意用回溯，因为动态规划的最优子结构不好找 不过目前暂时不太会回溯，先贴个答案

class Solution {
        List<String> res = new ArrayList<>();
        public List<String> generateParenthesis(int n) {
            if(n <= 0){
                return res;
            }
            getParenthesis("",n,n);
            return res;
        }

        private void getParenthesis(String str,int left, int right) {
            if(left == 0 && right == 0 ){
                res.add(str);
                return;
            }
            if(left == right){
                //剩余左右括号数相等，下一个只能用左括号
                getParenthesis(str+"(",left-1,right);
            }else if(left < right){
                //剩余左括号小于右括号，下一个可以用左括号也可以用右括号
                if(left > 0){
                    getParenthesis(str+"(",left-1,right);
                }
                getParenthesis(str+")",left,right-1);
            }
        }
    }
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

2、单调队列优化DP问题

当0<=j 当i-j<=j<=i时（两头变），此时可以使用单调队列维护状态：
假设这个栈是单调减的，头部的元素最大，则可以这样定义：如果头部index过期，则头部出，元素从尾部进，如果他遇到了比进去的元素更小的元素，则可以说明队列中元素不需要了（只需要最大的，如果进的那个元素已经大于队列尾部的元素，说明尾部的元素已经轮不到前面了）
这个解法并不只是在DP中作优化，本身单调队列也可以做一种解法
如滑动窗口最大值问题，就可以用单调队列代替查找，每一次循环将会减少k此循环，从O(mk) -> O(m)

3、请求调页 页面置换 写时复制

请求调页

概念

一种只加载需要的页的技术，常常用于虚拟内存系统
从未访问的那些页从不加载到物理内存中
当调用不存在在内存中的页面时，将会发生缺页错误
缺页错误的解决方法如下：

1. 检查进程的内部表，确定该引用是有效还是无效
2. 如果无效，终止进程，如果引用有效但是没有调入页面，则现在调入
3. 找到一个空闲帧
4. 调度一个磁盘操作（I/O），以将所需页面读到刚分配的帧
5. 当磁盘读取完成时，修改内部表和页表，以指示该页现在处于内存中
6. 重启被中断的指令

性能

缺页发生动作如下：

1. 抛出异常
2. 保存用户寄存器和进程状态
3. 确定中断是否为缺页错误
4. 检查页面引用是否合法，并确定页面的磁盘位置
5. 从磁盘读到空闲帧
6. 在等待时，将CPU分配给其他用户（CPU调度 可选）
7. 收到来自IO子系统的中断（完成IO）
8. 保存其他用户的寄存器和进程状态
9. 确定该中断来自上述磁盘
10. 修正页表和其他表，表示目前已经在内存中
11. 等待CPU再次分配给本进程
12. 恢复用户寄存器 进程状态 页表，重新执行指令
    

缺页处理时间主要由三部分构成：

1. 处理错误中断（1-100ms）
2. 读入页面
3. 重新启动进程（1-100ms）

这种算法很需要降低缺页的错误率

由于移动操作系统内存较小，所以不支持交换

写时复制

页面共享，有可能绕过请求调页（如fork函数），这种情况可以采用写时复制技术，让进程在最开始拥有一样的副本，意味着当进程写入了共享页面，就创建共享页面的副本

页面置换

页面置换有多种算法，这个算法是当发生缺页错误时，发现了空闲帧列表没有空闲位置，这时候需要换出一个空闲位置，这个位置如何去找的不同策略。不同的算法效率不同。

FIFO页面置换

选择最旧的页面更新
性能不太理想 可能可以和其他算法配合使用 比如页面缓冲算法 不过这个算法理解很简单

最优页面置换

最优置换可以说是最好的算法，但是由于很难找到这个整体的最优解，所以一般很难实现。他的思想是置换最长时间不会使用的页面，这个最长是根据全局而言
这个算法一般用于比较其他的算法，毕竟这个是最优的

LRU（Last-Recent-Used）最近最少使用算法

使用的最多的算法，只看局部上的最少使用，并换掉他。（时间上向后看的最优页面置换算法）
这种算法在硬件层面上需要一定的支持，对于硬件来说，要确定由上次使用时间定义的帧的顺序。

近似LRU算法

由于很少有操作系统可以提供LRU的硬件支持，所以使用近似LRU算法，这个算法近似于LRU，通过检查引用位来确定哪些页面被使用，用引用位来代替时间定义的帧序。

基于计数的页面置换

页面置换算法还有很多，基于计数的页面置换是为每个页面引用次数保存一个计数器

LFU 最不经常使用页面置换算法

置换有最小计数的页面，策略：积极使用的页面拥有较大的计数

MFU 最经常使用算法

置换有最小计数的页面，策略：最小的页面是刚刚进入并且没有被使用频繁

页面缓冲算法

这不是一个页面置换算法，而是另外一个策略（措施）：系统保留一个空闲帧缓冲池，当出现缺页错误，会选择一个牺牲帧。在写出之前，所需页面就可以读到来自缓冲池的空闲帧，这样可以让程序更加快速的启动。当牺牲帧以后被写出，它会被添加到空闲帧池