操作系统总结


微内核OS结构

基本概念:

  1. 足够小的内核
  2. 基于客服/服务器模式
  3. 应用“机制与策略分离”原理
  4. 采用面向对象技术

基本功能:

  1. 进程(线程)管理
  2. 低级存储器管理
  3. 中断和陷入处理

进程

程序并发执行时的特征:

  1. 间断性
  2. 失去封闭性
  3. 不可再现性

进程的特征:

  1. 动态性
  2. 并发性
  3. 独立性
  4. 异步性

进程状态:

  1. 就绪 -> 执行
  2. 执行 -> 就绪、阻塞、终止
  3. 阻塞 -> 就绪
  4. 创建 -> 就绪
  5. 终止

操作系统内核:

  1. 支撑功能:中断处理、时钟管理、原语操作
  2. 资源管理功能:进程管理、存储器管理、设备管理

同步机制应遵循的规则:

  • 空闲让进
  • 忙则等待
  • 有限等待
  • 让权等待

进程通信

  1. 共享存储器(内存)系统(Shared-Memory System)
  2. 管道,共享pipe文件,互斥读写,半双工
  3. 消息传递系统/消息队列。直接通信、间接通信
  4. client-server通信。socket、rp

线程与进程的比较

  1. 调度的基本单位
  2. 并发性
  3. 拥有资源
  4. 独立性
  5. 系统开销

线程的实现

  1. 内核支持线程KST (Kernel Supported Thread)
  2. 用户级线程ULT (User Level Thread)

调度算法:

  • 先来先服务FCFS
  • 短作业优先SJF
  • 优先级PSA
  • 高相应比HRRN (等待时间+要求服务时间)/要求服务时间

调度方式:

  • 抢占式
  • 非抢占式 优先权、短进程、时间片

轮转调度

  • 根据FCFS进行时间片轮转
  • 优先级,静态、动态
  • 多级队列 ,多个队列不同调度算法
  • 多级反馈队列,优先级越高时间片越短

公平调度:根据获得CPU时间的比率、根据用户数

实时系统调度算法

  • 非抢占性:轮转,优先级排序 抢占性:基于时钟中断、立即抢占
  • 最早截止时间优先EDF算法
  • 最低松弛度优先LLF
  • 优先级倒置的解决办法:优先级继承

死锁的原因

  1. 竞争不可抢占性资源引起死锁
  2. 竞争可消耗资源引起死锁
  3. 进程推进顺序不当引起死锁

死锁的条件

  1. 互斥条件
  2. 请求与保持
  3. 不可抢占
  4. 循环等待

处理死锁的方法

  1. 死锁预防:破坏一个或多个条件、一次性或逐步分配释放资源
  2. 死锁避免:银行家算法(贪心)
  3. 死锁检测:资源分配图(拓扑排序?)
  4. 死锁解除:终止所有进程、逐个终止进程、最小代价

分页储存管理

  • 页面、页面大小(1~8KB)
  • 页表 逻辑位置到物理位置的映射,控制位
  • 地址变换机构 页表寄存器、快表
  • 两级和多级页表
  • 反置页表

分段存储管理方式

  • 方便编程
  • 信息共享
  • 信息保护
  • 动态增长
  • 动态链接

段页式

虚拟存储器

局部性:时间局部性、空间局部性

特征:多次性、对换性,虚拟性

请求页表机制:

  • 状态位P: 是否已经调入内存
  • 访问字段A:记录一段时间内的访问次数
  • 修改位M:调入内存后是否被修改过
  • 外存地址:此页在外存上的地址

缺页中断

页面调入策略:

  • 何时:预调页策略、请求调页策略
  • 何地:足够空间的对换区Swap空间、未被修改直接换出修改过的进入swap、unix方式为运行的在文件区运行过的在对换区

页面置换算法:

  • 最佳Optimal(无法实现)
  • 先进先出FIFO
  • LRU
  • LFU
  • Clock算法、改进Clock (循环遍历,未被访问则换出,改进后根据访问位A和修改位M分四类,都为0则为最佳,都为1则为最不佳)
  • 页面缓冲PBA

抖动:页面反复换进换出

中断

中断和陷入:中断来自CPU外部、陷入来自CPU内部

中断向量表(函数偏移表)、中断优先级

对多中断源的处理方式:屏蔽中断、嵌套中断

中断处理程序:

  1. 测定是否有未响应的中断信号
  2. 保护被中断进程的CPU状态(所有CPU寄存器的内容)
  3. 转入相应的设备处理程序
  4. 中断处理
  5. 恢复CPU现场并退出中断

使用中断的可编程I/O

假脱机技术(预先把数据读出来)、SPOOLing技术

缓冲:单缓冲(互斥)、双缓冲、环形缓冲

磁盘

磁道、扇区(数据、控制字段、gap间隔)

磁盘调度算法:

  • 先来先服务FCFS
  • 最短寻道时间优先SSTF(离当前磁道最近的,可能导致饥饿)
  • 扫描算法SCAN(像电梯一样往一个方向扫)
  • 循环扫描算法CSCAN (来回扫)

磁臂沾着:某进程反复请求对某一次到的I/O操作,从而垄断整个磁盘设备

解决的算法:

  • NStepSCAN算法(多个队列,当前正在扫描的队列和其他扫描的队列)
  • FSCAN(两个队列、当前和下一轮)

文件管理

索引文件: