操作系统原理

发表于 分类于 ， Waline：
本文字数： 3.4k 阅读时长 ≈ 3 分钟

死锁

  1. 充分必要条件：互斥、占有且等待、不可抢占、循环等待
  2. 死锁预防：破坏上面几个条件（除了互斥）
    1. 一次性请求所有资源（防止占有且等待）
    2. 抢占
    3. 资源排序（防止循环等待）
  3. 死锁检测：周期性测试死锁

死锁避免

相关向量：R(Resource)资源总量，V(Available)可用资源

相关矩阵：C(Claim)最大需求，A(Allocate)资源分配情况

  1. 进程启动拒绝：如果：新进程的C+现有进程的C > R，就不允许启动新进程

  2. 资源分配拒绝（银行家算法）：

    总进程数和总资源数固定的情况下

    安全状态：至少有一个资源分配序列不会导致死锁（进程都能依次结束）

    判断是否在安全状态，就是使用回溯法尝试逐个满足进程的剩余需求，然后回收已分配的资源，再接着满足其它进程，要是资源不够就回退，尝试先分配给其他进程。如果所有分配顺序都不能顺利执行完所有进程，那就是不安全的。

    银行家算法就是保证始终处于安全状态下。

    比如进程P1请求n个R3，可以假设满足此请求，R3减少n个(R[R3] -= n)，再判断是否还是在安全状态下，如果不是，则说明不能同意。

虚实地址转换

页框：内存中的定长块

页：外存中的定长块，一个页和页框的大小相同

段：外存中的变长块

  1. 分页：虚地址格式为页号和偏移量，用页号查页表，得到对应页表项中保存的页框号，页框号和偏移组合成实地址（物理地址）

    比如“...32个2KB的页...”，可以得知：

    1. 页表长度为32，页号占5位
    2. 页大小为2KB，页偏移量占11位
    3. 页框大小也是2KB。如果又有“共1MB物理空间”，那么页框数量就是\(\frac{1MB}{2KB}=2^9\)个，从而页框号占9位。如果忽略页表项的控制位，那么页表宽度就是9位。

    一个页和一个页框等大，但是页号和页框号所占的位数不一定相等，因为虚地址空间和实地址空间不一定等大（通常都是不一样大的）

  2. 分段：虚地址格式为段号和偏移量，用段号查段表，先检查偏移量是否超过对应段表项中记录的长度，超过了的话就发生段错误，否则得到对应段基址，跟偏移量组合得到实地址。

  3. 段页式：虚地址格式为段号、页号和偏移量，分别查段表、页表，最后得到页框号，和偏移量组合得到实地址。

    比如“一个任务分成4个等长段，每段一个8项的页表，页尺寸2KB”，可知：

    1. 每段最大为（8页）\(8\times 2KB=16KB\)，逻辑地址空间最大为（4段）$ 4 16KB=64KB$

    2. 此段页式的虚地址中，段号占2位，页号占3位，偏移量占11位

      如果告知一个十六进制物理地址00021ABC，那么说明物理地址共有32位，物理空间为\(2^{32}=4GB\)

1
2
3
4
5
6
7
8
9
10
11
// 虚地址转换为实地址
bool Translate(int virtAddr, int* physAddr){
    int index = virtAddr / PageSize; // 页号
    if(index >= PageTableSize){
        physAddr = NULL;
        return false;
    }
    *physAddr = PageTable[index].physicalPage * PageSize + 
                virtAddr % PageSize; // 偏移
    return true;
}

页面置换算法

  1. OPT(Optimal)最佳：替换下次访问最晚的页（不可能实现）
  2. LRU(Least Recently Used)最近最少使用：替换最长时间未使用的页
  3. FIFO(First In First Out)先进先出：按到来的先后顺序轮流替换
  4. Clock时钟：设置一个使用位u，每次因没命中而要替换时就循环遍历寻找u为0的，遇到u为1的要改成0。找到位置并替换后，把指针后移。如果是命中了，则把u设置1（指针不移动）
  5. 时钟改进：增加一个修改位m，没命中而要替换时：
    1. 遍历寻找(u=0,m=0)的，找到就替换
    2. 如果没找到，重新遍历寻找(u=0,m=1)的，路过的u要改成0
    3. 如果没找到，回到第1步

单处理器调度算法

选择进程来运行

  • 三个时间参数：\(T_w\)已停留时间，\(T_e\)已执行时间，\(T_s\)总服务时间
  • \(周转时间T_r=等待（停留）时间+服务（执行）时间\)
  • \(归一化周转时间=\frac{周转时间}{总服务时间}=\frac{T_r}{T_s}\)

  1. FCFS(First Come First Served)或FIFO先来先服务：就是字面意思，使用一个队列，按先后顺序一个一个执行到结束

  2. RR(Round Robin)时间片轮转：轮流执行q，q为时间片大小，执行q后就抢占，按照队列顺序选下一个

  3. SPN(Shortest Process Next)最短作业优先：优先选择估计总时间最短的，排序后逐个执行

  4. SRT(Shortest Remaining Time)最短剩余时间：优先选择估计剩余时间最短的，如果要新来的进程更短，就会抢占运行中的进程，并把老进程放到队列里

  5. HRRN(Highest Response Ratio Next)最高响应比优先：优先选则\(响应比R=\frac{T_w+T_s}{T_s}\)大的，排序后逐个执行

  6. (Feedback)反馈：基于轮转，但是设置了多个优先级队列，优先执行高优先级队列里的进程。0号队列优先级最高，刚来的进程都是进入0号，运行时间片q之后抢占，放到下一级队列后面，已经最低级的话就不再下一级了，而是直接放到后面。

    时间片q可以是固定值（也就是每个队列都一样），也可以是\(2^i\)（i是队列号）

磁盘调度策略

按照一定的顺序响应I/O请求，尽量减少寻道时间

  1. Random随机：字面意思，性能最差（可以用来评估其它算法的性能）
  2. FIFO(First In First Out)先进先出：字面意思，按请求顺序寻道
  3. Priority优先级：先满足优先级高的，一般较短的批作业和交互作业的优先级较高
  4. LIFO(Last In First Out)后进先出：字面意思
  5. SSTF(Shortest Service Time First)最短服务时间优先：优先选择离当前磁头最近的请求
  6. SCAN扫描：也叫电梯算法，按照当前磁头臂的方向一直移动到头，然后反向回来（就像电梯上下楼一样）。默认使用LOOK策略，也就是不需要真的移动到另一头，只要前面没有请求了就可以掉头。
  7. C-SCAN(Circular SCAN)循环扫描：相对于SCAN来说，永远只按照一个方向移动，页就是在到头之后不是掉转反向，而是直接“跳”到另一头，再按照原来的方向移动。
  8. N步SCAN：先把请求队列分成多个长为N的子队列，对每个队列执行SCAN，新来的请求放到其它不是正在处理的队列后面
  9. FSCAN：使用两个队列，正在处理现有队列时，新来的请求放到另一个队列里

UNIX文件索引节点间接寻址

比如“逻辑块容量为4KB，块地址占4B，共8个直接地址，2个间接地址”，则：

  1. 直接地址可寻：\(8\times 4KB=32KB\)
  2. 一级间接地址可寻：\(\frac{4KB}{4B}\times 4KB=4MB\)
  3. 二级间接地址可寻：\(\frac{4KB}{4B}\times \frac{4KB}{4B}\times 4KB=4GB\)

分布式快照算法

第5版书 - 分布式全局状态

算法：启动算法的进程向相邻节点发送Marker标记，收到Marker的进程停止接收和发送消息，启动算法，记录下此时的快照，并向相邻节点转发Marker。

快照：记录进程在启动算法前从其他进程收到了哪些消息，有哪些消息还在路上，以及发送了哪些消息。

  1. 求快照

    根据题意，把发送的消息都写在进程间的连线上，已经收到的消息写在进程节点旁（注明来源）。比如进程1启动算法前向进程2发送三条消息，进程2启动算法前从进程1那里收到两条，那么快照就是：

    1
    2
    3
    4
    进程1
        流出通道
            2 发送 1，2，3
        流入通道
    1
    2
    3
    4
    进程2
        流出通道
        流入通道
            1 接收 1, 2 存储 3

    存储就是指还在路上的

  2. 由快照反推哪个进程先启动了算法

    先假设，然后由反证法很容易推出矛盾。

令牌传递方法

第五版书 - 分布式互斥

有一个令牌在所有进程之间传递，得到令牌的进程才可以访问临界区

token是全局数组，token[i]是进程i最后一次拿到令牌的时间

request是每个进程一个数组，request[j]表示当前进程从进程j收到最后一次请求的时间

token_held表示是否需要用令牌

token_present表示是否持有令牌（虽然按照字面意思应该跟上面的对调，但是按照算法中的使用，应该表示持有）

参考

[1] 操作系统精髓与设计原理 第8版

[2] 操作系统精髓与设计原理 第5版

相关文章