OS考点（二）https://developer.aliyun.com/article/1498393
读写者问题
问题描述：
- 共享数据，有两类使用者
- 读者：只读取/查询数据
- 写者：修改数据
- 读-读允许：同一时刻，允许有多个读者同时读
- 读-写互斥：
- 当有读者在，写者不能写
- 当有写者在，读者不能读
- 写-写互斥：两个写者不能同时写
示例：访问查询型数据库，通常，读者的数量远大于写者
可否直接用一个互斥信号量实现？
- 不能。当读者获得数据库后无法让其它读者访问。
能否借用生产者-消费者中的同步思路？
- 与生产者-消费者问题不同，不存在一个有界的缓冲区，因此不能用一组信号量来控制读者-写者的互相等待
读者-写者问题解决方案 
读者-写者锁
一些程序语言和操作系统提供了读写锁（Readers-writer lock）接口 读写锁适合于：
- 读进程和写进程可以区分开
- 读者进程数量比写者进程多
读者优先
- 又称第一类读者写者问题
- 只要有读者正在读，后来的读者都能直接进入
- 如读者持续不断进入，则写者就处于饥饿
写者优先
- 第二类读者写者问题
- 只要有写者就绪，写者应尽快执行写操作
- 如写者持续不断就绪，则读者就处于饥饿
- 该方法并发度和效率较低
读写锁替代策略：RCU
读写锁允许读者之间不互斥的读取数据
- 但是对于Rcount变量的操作需要加锁
- 当99%以上都是读者，且数量很大时，开销太大
- 读-复制-更新（Read-Copy-Update）
哲学家就餐问题
5个哲学家围圆桌而坐，每2人之间放一只叉子，哲学家的动作包括思考和进餐，同时拿到左右两边的叉子才能进餐，思考时将叉子放回原处。
可能的解决方案
- 至多只允许有四位哲学家去拿左边的筷子，最终能保证至少 有一位哲学家能够进餐，并可在用毕时释放出他用过的筷子， 从而使更多的哲学家能够进餐。
- 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子 进餐。
- 规定奇数号哲学家先拿左边的筷子再拿右边的筷子；而偶数 号哲学家先拿右边的筷子再拿左边的筷子。
- 增加一根筷子（完美解决）
管程
管程是一种抽象数据类型(ADT)，代表共享资源，及对该资源的互斥操作确保任一时刻最多只有一个进程进入管程，使用共享数据
思想：用锁(locks，通常是隐含的)实现互斥，用条件变量 (condition variable)实现同步，提供与信号量相同的功能
包含面向对象思想，封装了同步机制
死锁
如果一个进程集合中的每一个进程都在等待只能由该进程集合中的其它进程才能引发的事件，那么该进程集合就是死锁（deadlock）的。
大部分死锁和资源有关。资源是进程/线程为了完成工作，所需要的实体
- 可重用资源：CPU、内存、文件、设备……
- 可消耗资源：缓冲区产品、IPC的消息、中断……
- 可抢占资源：CPU、内存（有挂起）……
- 不可抢占资源：打印机、内存（无挂起）、文件……
死锁发生的条件
- 互斥（Mutual exclusion）
- 任何时刻只能有一个进程使用一个资源实例
- 请求和保持（Hold-and-wait，持有并等待 ）
- 进程持有至少一个资源，并正在等待获取其他进程持有的资源
- 不可抢占（No preemption）
- 资源只能在进程使用后自愿释放
- 循环等待（Circular Wait）
- 存在一个进程集合{P0，P1，...，PN}
- P0正在等待P1所占用的资源，P1 正在等待P2占用的资源……PN正在等待P0所占用的资源
如果四个条件中的任何一个不满足，死锁将不会发生
如果发生了死锁，四个条件一定都已满足
死锁的预防
死锁预防（Deadlock Prevention）
破坏四个必要条件之一，确保系统永远不会进入死锁状态
- 破坏“互斥”条件（资源不可分享，任一时刻只有一个进程可以使用该资源的一个实例）
- 破坏“持有并等待”条件（进程持有至少一个资源，并正在等待获取其他进程持有的资源）进程在开始执行时，一次请求所有需要的资源，要么拥有全部资源，要么不拥有资源例：申请全局锁后再申请全部资源缺点：
- 资源利用率低，并发性被降低；
- 饥饿，如果所需资源不断被其它进程使用
- 破坏“不可抢占”条件（资源只能在进程使用后自愿释放）如果资源本身是可以抢占的，则并不会死锁。当进程请求了不能立即分配的资源，则将自己已占用的资源也释放。在交通死锁的例子中，车辆如果发现不能通过就倒车缺点：
- 代价太大（打印机、刻录机、扫描仪）
- 可能造成反复申请-释放资源，进程的执行被无限制的延迟（活锁）
- 破坏“循环等待”条件（存在一个进程-资源的循环链）对资源排序，要求进程按顺序请求资源缺点：
- 应用程序员完全可以无视此规定
- 由于大型程序资源依赖关系复杂且普遍封装，难以设计和测试
小结
死锁避免（Deadlock Avoidance）
- 提前进行判断，只允许不会出现死锁的进程请求资源
避免死锁就是确保系统不会进入不安全状态
安全状态一定不会死锁，不安全状态可能死锁
所谓安全状态，是指系统能按某种进程顺序如<P1，P2，…，Pn>，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。
若系统不存在这样一个安全序列，称系统处于不安全状态
银行家算法：判断是否存在某个进程执行顺序，让系统能安全运行，并找到他
死锁检测和恢复（Deadlock Detection & Recovery）
- 在检测到运行系统进入死锁状态后，进行恢复
资源分配图，可以看出是否出错
终极方法：鸵鸟方法
操作系统忽略死锁，不做任何处理
存储器管理
物理地址
- 又称实地址、绝对地址
- 内存所看到的地址
物理寻址
- CPU直接使用物理地址访问主存储器
虚拟地址（virtual address）
- 又称逻辑地址
- CPU所生成的地址
虚拟寻址（virtual addressing）
- CPU通过虚拟地址访问主存，虚拟地址经过地址翻译转换为物理地址
- 地址翻译由CPU里的内存管理单元(MMU)负责.
程序的装入
- 绝对装入
- 用户在程序设计时直接给出物理地址
- 或程序包含符号地址，编译/汇编时转换成物理地址
- 缺点：不能加载到内存任意位置；只适合单道程序
- 可重定位装入，静态重定位
- 编译器仅产生相对地址
- 加载器在加载时将相对地址转化为绝对地址
- 缺点：不允许在运行时改变在内存中的位置；
- 动态运行时装入，动态重定位
- 加载器在加载时仍使用相对地址
- CPU在运行时将相对地址转化为绝对地址
- 需要地址转换硬件（MMU，重定位寄存器）支持
程序的链接
链接器（linker）把一组目标模块作为输入，产生一���包含完整代码和数据的加载模块（load module），传递给加载器
- 静态链接（static linking）
缺点：常用的库不能共享，库函数若更新，需重新链接 - 动态链接（static linking）
加载时动态链接
基地址-界限
分配一块连续的内存
基地址+逻辑地址实现地址转换
界限地址实现地址保护
内存分配
- 单一连续分配
- 固定分区分配
- 动态分区分配
管理动态分区分配的数据结构，要能动态跟踪每个已占用和空闲的分区情况
可用：二维数组；链表；位图(bitmap)
动态分区分配算法
- First Fit算法
分配n个字节，使用第一个可用的空间比n大的空闲块。 - Next Fit算法
分配n个字节，从上一次找到的分区向下寻找，使用下一个可用的空间比n大的空闲块。 - Best Fit
分配n字节分区时， 查找并使用大于n的最小空闲分区 - Worst Fit
分配n字节，使用尺寸不小于n的最大空闲分区
基于索引搜索的分配算法
- 快速适应
根据空闲区的容量作分类，设立大、中、小等多个链表方便索引 - 伙伴系统
分配时可能多次分割，回收时可能多次合并
时间性能和利用率折中了快速适应与顺序搜索
可以兼顾大小进程的分区需求
没有外部碎片，但有内部碎片，每块最大为2i−12^i-12i−1
分页式存储管理
基于基地址-界限的存储管理方式简单有效，可以实现内存 分配、地址转换、地址保护，但始终解决不好碎片的问题 原因在于，内存总是只能寻找一段连续的空间才能分配
解决方案：分页（Paging）管理
核心思想：离散分配，将进程打散，分到不同的空间中去
页式地址变换
虚拟地址结构：页号(page number)+页偏移量(page offset)
物理地址：物理块(frame number)+页偏移量(page offset)
页框：以页框为单位为各个进程分配内存空间，最小的一块储存单元大小
将用户程序的地址空间分为若干个固定大小的区域，称为“页”或“页面”。相应地，将内存空间分为若干个物理块或页框（frame），页和页框大小相同。
在页表中，每一行存储的是属于那个物理页面的信息，又称为“页表项(Page Table Entry) 按位数
没有外部碎片
- 因为块是物理内存分配的最小单位
- 空闲的物理块可以用位图（bitmap）或链表（freelist）管理
- 每一块都可以分配出去，不存在浪费；回收简单
很小的内部碎片
- 每个进程最多在最后一个页产生浪费
- 内碎片最大为：页面大小 – 1Byte
存取控制字段
页表是系统为每个进程建立的页面映射表
每个页表项的结构为：页号 + 物理块号
问题
- 访问页表时间
- 基地址-界限方式，直接通过MMU的寄存器转换地址
- 页表在内存里，每次寻址多了一次内存访问
- 页表占据空间
- 随着系统位数提升，页表会占有越来越多的空间
快表
通过缓存，加速页的访问
t: 访问一次内存的时间
λ：查找快表的时间
α：快表命中率
有效访问时间：α(λ+t)+(1−a)(λ+2t)+t=2t+λ−αtα(λ + t) + (1 - a)(λ + 2t) + t = 2t + λ - αtα(λ+t)+(1−a)(λ+2t)+t=2t+λ−αt
多级页表
减少直接寻址存储器的大小空间
反向页表
让页表与物理地址空间的大小相对应
基于Hash映射值查找页表对应的帧号f 用链表处理hash冲突
减少直接寻址存储器的大小空间
段式存储管理
虚拟存储器
zhuanlan.zhihu.com/p/391327282
页面置换算法
当需要调入新页面，但内存已满时，页面置换算法 选择一个被换出的页面，再将新页面载入
先进先出算法
OPT页面置换算法
最佳算法（OPTimal）：选择未来最久不被访问的
不可能实现！（预测未来最热卖的商品）
意义：给出理论上的最好结果，以供比较
最近最久未使用（Least Recently Used）LRU
选择自上次被访问以来经历时间最久的
硬件开销太大，难以实现
实际OS中，采用近似LRU的方法
Clock算法
循环队列，依次检查。若A（访问位）=0，换出；若A=1，置A=0，检查下一个。
改进后
不仅利用访问位A，还利用修改位D
- A=0，D=0，最近未访问，也未被修改；
- A=0，D=1，最近未访问，但被修改；
- A=1，D=0，最近被访问，但未被修改；
- A=1，D=1，最近被访问，且被修改。
AD=00最应该被替换，AD=11最不应替换
页面分配策略
给每个进程分配至少多少个物理块
固定分配和可变分配
给每个进程分配多少个物理块？
固定
- 平均分配算法
- 比例分配算法
- 优先级分配算法
可变
允许分配给进程的物理块数随时间变化
全局&局部置换
可变分配在置换时，换出属于谁的页面？
若每个进程已经固定分配物理页面数量，则不可能去抢夺其它进程的页面，因而也就不可能全局置换。
全局置换（Global Replacement）
- 可以置换所有进程的页面
局部置换（Local Replacement）
- 仅置换进程自己的页面
页面缓冲算法
页缓冲算法（PBA，Page Buffering Algorithm）
- 空闲页面池，统一管理空闲的物理页面
- 修改页面池，将D=1的页面暂存
好处：防止将被换出的页面马上又要使用的情况（house keeping）
实用策略-工作集
- 进程开始执行后，随着访问新页面逐步建立较稳定的工作集
- 当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定
- 局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值
抖动
- CPU利用率与并发进程数存在相互促进和制约的关系
- 进程数少时，提高并发进程数，可提高CPU利用率
- 并发进程进一步增加，导致内存访问增加
- 分配给每个进程的物理块太少，导致缺页率上升和CPU利用下降
- 抖动：每个进程频繁的缺页，换进/换出
- 抖动
- 进程物理页面太少，不能包含工作集
- 造成大量缺页，频繁置换
- 进程运行速度变慢
- 产生抖动的原因
- 随着驻留内存的进程数目增加，分配给每个进程的物理页面数
- 不断减小，缺页率不断上升
- 抖动的预防方法
- 采用局部置换策略
- 把工作集算法融入处理机调度
- “L=S”准则
- 选择暂停的进
