记录：2022-9-8 编辑距离 内核级线程的切换 分区 分段

学习时间：2022-9-8

学习内容

1、LeetCode 一道困难题

这道题很难想到有动态规划求解，因为非常难找子过程，我自己想用贪心做这道题，但过了1000个案例，剩了一些过不了。
我的解法如下，按块来移动

class Solution {
    public int minDistance(String word1, String word2) {
        //用一个2*2方块来框选
        //1、第一列若相同，方块后移一位
        //2、第二列相同，res++ 方块后移2位
        //3、左向右对角相同，下字符串删除一位，res++ 方块后移一位
        //4、右向左对角相同，上字符串删除一位，res++ 方块后移一位
        //5、上诉都不满足 res++，方块后移一位  若上述情况有出现部分越界，则这部分跳过

        //边界：若下方i 越界，但上方未越界，则加上上方剩余所有
        //若上方i越界，下方未越界，则加上下方剩下所有
        int res = 0;
        int n = Math.max(word1.length(),word2.length());
        for(int i = 0;i<n;i++){
            boolean isWord1Over = i >= word1.length();
            boolean isWord2Over = i >= word2.length();
            boolean isNextWord1Over = i+1 >=word1.length();
            boolean isNextWord2Over = i+1 >=word2.length();
            if(isWord1Over&&isWord2Over){
                //均越界 退出循环
                break;
            }   
            if(isWord1Over){
                res+=word2.length() - i;
                break;
            }
            if(isWord2Over){
                res+=word1.length() - i;
                break;
            }

            if(word1.charAt(i) == word2.charAt(i)){
                //第一列相同，方块后移一位
                continue;
            }else if(!isNextWord1Over&&!isNextWord2Over&&word1.charAt(i+1) == word2.charAt(i+1)){
                //第二列相同，res++ 方块后移2位
                res++;
                i++;
                continue;
            }else if(!isNextWord2Over&&word1.charAt(i) == word2.charAt(i+1)){
                //左向右对角相同，下字符串删除一位，res++ 方块后移一位
                res++;
                word2 = word2.substring(1,word2.length());
                continue;
            }else if(!isNextWord1Over&&word1.charAt(i+1) == word2.charAt(i)){
                //右向左对角相同，上字符串删除一位，res++ 方块后移一位
                res++;
                word1 = word1.substring(1,word1.length());
                continue;
            }else{
                res++;
                continue;
            }
        }
        return res;
    }
}
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

这道题的子过程，可以看作两个词组，每个词组都有他自己的子过程，dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]) + 1;
这里 每一个dp的子过程，代表的是一种操作，操作可以被简化成三种：A的插入 B的插入 A与B的替换，当A与B需要替换时，替换完成后，两个值可以同时去掉，所以可以变成 dp[i-1][j-1]的子过程，A的插入可以变成dp[i-1][j]的子过程，dp[i][j-1]可以看作B的插入，所以dp[i][j] 就可以看成三种情况的最小值+1。
这是如果i与j字符不相同的情况，如果字符相同，那么他其实可以不用替换，因此dp[i-1][j-1]不需要+1

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        // 有一个字符串为空串
        if (n * m == 0) {
            return n + m;
        }

        // DP 数组
        int[][] D = new int[n + 1][m + 1];

        // 边界状态初始化
        for (int i = 0; i < n + 1; i++) {
            D[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            D[0][j] = j;
        }

        // 计算所有 DP 值
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = D[i - 1][j] + 1;
                int down = D[i][j - 1] + 1;
                int left_down = D[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    left_down += 1;
                }
                D[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return D[n][m];
    }
}

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

2、内核级线程的切换

不同于用户级线程，内核级线程切换的数据结构是一套栈，这套栈由用户栈和内核栈组成，当用户栈需要调用系统功能时，需要切换到内核栈，内核栈中需要存储用户栈地址和当前执行位置，最后得到当前TCB，如果当前内核线程需要切换，则由操作系统调度到另外一个内核线程，这个线程挂起。

内核级线程的切换可以看作五段：

当前线程的用户线程-当前线程的内核级线程-当前线程的内核级线程调度-另一个内核级线程-另一个线程的用户线程

3、内存 分区 分段

交换

进程必须要在内存中执行，但进程可以暂时从内存交换到备份存储，当再次需要时才回到内存，这样做可以使进程的总物理空间大于真实系统的物理空间，增加了多道程序的程度。
这种交换会使用分派器进行调用，分派器检查就绪队列的下一个进程是否在内存中，如果不在，并且没有空闲内存，则等待，否则分派器将会换出内存中的进程，并换入此进程。并重新加载寄存器，将控制权转移到所选进程。

连续内存分配

内存保护

保护内存的方法使用重定向寄存器和界限寄存器，如100040，界限=74600，则可以到100040 - 174640
这种方式允许操作系统动态改变大小

分区

1、固定分区

每个分区包含一个进程，多道程序的程度受限于分区数。
当一个分区空闲，则可以选择一个进程进入分区

2、可变分区

操作系统会存在一个表，记录哪些内存可用，哪些进程已用。
内存将会被看作一个一大块的可用内存，被称为孔
内存中还存在一个集合，这个集合将会包含各种大小的孔
当新进程需要内存，系统查找是否存在足够大的孔，若孔太大 则分成两块，当进程终止，他将释放内存，该内存还给孔集合，如果孔与其他孔相邻，则合并
从一组可用的孔选择空闲孔的方法包括：

1. 首次适应 分配首个足够大的孔
2. 最优适应 分配最小的足够大的孔
3. 最差适应 找最大的孔 但同样需要找整个列表

碎片

当总的可用内存之和可用满足请求，但是不连续，此时就出现了外部碎片。
一个解决方法是紧缩，目的是移动内存内容，让所有空闲空间合成一块（静态地址无法紧缩）
第二个解决方法是允许进程的逻辑地址空间不连续，当物理内存可用，则允许为进程分配内存，有两种方式：分段 分页

分段

基本方法

指定：段名称与段内偏移
结构：

<段号，偏移>

编译时链接的库可能分配到不同的段，加载程序会装入所有的段，并为他们分配段号
以下是一个分段的例子

硬件

用段表映射逻辑地址空间与物理内存，并将不同的程序分段