操作系统 - 草莓君的妙妙屋

# 操作系统
简单地梳理一下操作系统课程的脉络，回忆用。

[TOC]

## 概述
- 特征：并发、共享、虚拟、异步，前二者为最基本
- 目标
    - 管理计算机资源
    - 为用户提供接口：命令、程序、GUI
- 发展
    - 批处理系统
    - 分时操作系统
    - 实时操作系统
    - 网络和分布式操作系统
- 运行机制
    - 中断、异常
    - 系统调用
    - 核心态，用户态
- 体系结构

## 进程管理
### 进程
- 概念：程序段、数据段、PCB
- 资源分配和调度的单位
- 状态：创建，就绪，运行，阻塞，结束
- 通信
    - PV操作
    - 共享存储区
    - 消息传递：消息队列（直接），信箱（间接）
    - 管道通信

### 线程
- CPU资源分配的单位
- 不拥有系统资源
- 实现方式：
    - 用户级线程
    - 内核级线程
- 多线程模型：
    - 多对一（用户级） 并发性不高
    - 一对一（内核级） 切换开销
    - 多对多（折衷） 集两者长处

### 处理机调度
- 三级调度
    - 作业（高级）调度：内存与辅存
    - 内存（中级）调度：内存与外存，挂起
    - 进程（低级）调度：就绪队列中调度 频率高
- 调度方式
    - 非剥夺调度
    - 剥夺调度
- 调度指标
    - CPU利用率、系统吞吐
    - 周转时间、平均周转、带权周转
    - 等待时间
    - 响应时间
- 调度算法
    - 先来先服务FCFS
    - 短作业优先：饥饿
    - 优先级调度：剥夺非剥夺，静态动态
    - 高相应比优先：非抢占式，响应比=(等待+要执行)/要执行
    - 时间片轮转
    - 多级反馈队列：队列优先级逐级降低，优先级越高时间片越小

### 进程同步
- 基本概念：临界资源、同步、互斥
- 基本实现方法
    - 软件方法
    - 硬件方法
- 信号量
    - 整型
    - 记录型
    - signal，wait
- 管程
- 经典同步问题
    - 生产者消费者
    - 读者写者
    - 哲学家进餐

### 死锁
- 概念
- 产生原因
    - 资源竞争、推进顺序非法
    - 产生的必要条件及破坏
        - 互斥  改造资源为可共享 e.g. spooling技术
        - 不可剥夺  按优先级强制剥夺
        - 请求并保持  静态分配一次全部分配到位
        - 循环等待  顺序资源分配法
- 处理策略
    - 预防（破坏四个必要条件）见上
    - 避免
        - 安全状态与不安全状态
        - 银行家算法 Available Max  Allocation Need
    - 检测与解除
        - 资源分配图
        - 死锁定理（化简资源分配图）
        - 死锁解除：资源剥夺、撤销进程、进程回退法

## 内存管理
内存管理的功能：内存分配与回收，地址转换，内存空间扩充，存储保护

### 基本概念
- 程序的执行
    - 编译：源代码->目标模块
    - 链接：目标模块和库函数->装入模块
        - 静态链接：运行前组合
        - 转入时动态链接：边装入边链接
        - 运行时动态链接：便于实现模块共享
    - 装入：装入程序将 装入模块->内存
        - 绝对装入：编译时直接确定地址
        - 可重定位装入：装入时修改地址，地址变换一次完成，装入后不发生移动
        - 动态运行时装入：重定位寄存器；程序可分配到不连续的区域；只装入部分代码即可
- 逻辑地址空间、物理地址空间
- 内存保护
    - 上下限寄存器
    - 重定位寄存器（物理地址最小值）、界地址寄存器（逻辑地址最大值）
- 覆盖与交换
    - 覆盖 仅一道程序，在同一程序中进行
    - 交换 不同进程间进行；交换整个程序；与虚拟内存的调入调出不同
    - 调入调出

### 内存分配方式
- 连续分配
    - 单一连续分配  系统区，用户区，一道程序
    - 固定分区分配  分区大小相等or不等；无外碎片；有内碎片
    - 动态分区分配
        - 不预先划分内存
        - 外碎片无内碎片；紧凑
        - 分配算法：首次适应、最佳适应（产生最多的外碎片）、最坏适应、临近适应（循环首次适应）
- 非连续分配
    - 基本分页存储管理
        - 页面、页面大小
        - **地址结构**：页号，页内偏移
        - 页表：页号->块号
        - 地址变换机构
        - 快表 TLB ![块表](http://zrawberry.com/media/picture/ed7c5be7073645439f7e264c1aa4b17f.jpeg)
        - 多级页表 一级页号；二级页号；页内偏移
        - 一维地址空间
    - 基本分段存储管理
        - 分段：段号，段内偏移
        - 段表：段号->段长，段起始地址
        - 地址变换机构
        - **段的共享与保护** 可重入代码；越界保护
        - 二维地址空间
    - 段页式存储管理方式
        - 逻辑地址：段号，页号，页内偏移
        - 同一个进程 只有一个段表；可能有多个页表
        - 地址变换机构 ![变换结构](http://zrawberry.com/media/picture/ea77f1a47e114b158f9f9bbdc4068a5c.jpeg)
- **有效访存时间 EAT** 计算
- 位视图

### 虚拟内存
- 基本概念
    - 传统存储管理：一次性、驻留性
    - 局部性原理：时间局部性、空间局部性
    - 虚拟存储器：多次行、对换性、虚拟性（逻辑上扩充）
    - 实现：请求分页/段/段页存储管理
    - 页表，中断机构，地址变换机构
- 请求分页管理
    - 页表 加入 状态位（是否在内存）、修改位、访问字段等
    - 缺页中断机构
    - 地址变换机构 变换过程 ![变换过程](http://zrawberry.com/media/picture/2690cd3076b1498bac20d0875af14e91.jpeg)
- 页面置换算法
    - 最佳置换算法（理想）
    - 先进先出
    - 最近最久未使用 LRU  需要硬件支持
    - 时钟置换算法（二次机会算法）
- 页面分配策略
    - 驻留集大小
        - 固定分配
        - 可变分配全局置换
        - 可变分配局部置换
    - 调入页面的时机
        - 预调页
        - 请求调页
    - 从何处调入页面
        - 对换区
        - UNIX 未运行从文件区调入，运行过换出至对换区
    - 抖动
    - 工作集

## 文件管理
### 文件系统
- 文件
    - 操作：创建、读写、指针重定位、删除、截断
    - 文件指针
    - 文件打开计数
- 逻辑结构
    - 无结构文件（流式）
    - 有结构文件（记录式）
        - 顺序
        - 索引
        - 索引顺序
        - 散列文件
- 目录结构
    - 文件控制块FCB
    - 索引结点
    - UNIX  索引节点和FCB
    - 目录
        - 单级目录
        - 两级
        - 多级目录（树形目录）
        - 无环图目录 （文件共享）
- 文件共享
    - 硬链接：索引节点共享  UNIX
    - 软连接：符号链接 windows
- 文件保护
    - 访问类型 rwx
    - 访问控制 用户组

### 文件系统实现
- 文件系统层次结构
- 目录实现
    - 线性列表
    - 哈希表
- 文件实现
    - 分配方式
        - 连续分配：寻道数最小 时间最短；FCB：起始地址，长度
        - 链接分配：隐式链接（只能顺序访问盘块 FCB起始和尾巴地址）、显式链接（一张FAT表）
        - 索引分配：FCB指索引块
        - UNIX **混合索引分配法**
    - 存储空间管理（空闲块）
        - 空闲表法
        - 空闲链表法
        - 位示图法
        - 成组链接法

### 磁盘组织与管理
- 磁盘结构：磁头、磁道、扇区、盘面、柱面
- 读写时间：寻道时间（磁臂移动）、延迟时间（旋转）、传输时间
- 磁盘调度算法
    - 先来先服务
    - 最短寻找时间优先（饥饿）
    - 扫描 SCAN  LOOK(不到顶部 只到最远的请求处)
    - 循环扫描 C-SCAN  C-LOOK
- 磁盘管理
    - 初始化
    - 引导块
    - 坏块

## I/O管理
### 概述
- 基本功能
    - 隐藏物理设备细节
    - 设备无关性
    - 提高处理机 IO涉笔的李永利
    - 控制IO设备
    - 错误处理
- 设备独立性
    - 逻辑设备 应用请求逻辑设备名
    - 物理设备 执行时系统转换
- 控制设备方法
    - 直接IO指令
    - 内存映射IO
- IO设备分类
    - 速度：低、中、高
    - 信息交换单位：块、字符
    - 共享属性：独占、共享

### 控制方式
- 控制方式
    - 轮询
    - 中断
    - 直接访问存储器 DMA
    - IO通道
- 中断机制 中断向量表 中断优先级
- DMA 绕过CPU直接在IO和内存间传输

### IO内核子系统
- IO调度
- 缓冲
    - 匹配速度差异
    - 协调数据大小不一致
    - cache与缓冲区别 前者是拷贝 后者是唯一副本
- 假脱机SPOOLing
    - CPU高速 IO低速
    - 输入输出进程，输入输出缓冲区，输入输出井（磁盘），井管理程序
    - 独占设备改造为共享设备
- 错误处理  恢复 读写错误；请求失败时候返回错误；出错日志
- IO保护 防止非法命令执行

## 其他学习材料
- [面试常见问题.pdf](http://cloud.zrawberry.com/index.php/s/dqrdNRFbW8TrSfa)

文章信息

标题：操作系统

作者：快刀切草莓君

分类：计算机基础课程

发布时间：2020年5月24日

最近编辑：2020年5月25日

浏览量：1257

↑