操作系统复习笔记

目录

• 操作系统
  • 1.计算机系统概述
    • 1.1操作系统的基本概念
      • 1.1.1操作系统的概念
      • 1.1.2操作系统的特征
      • 1.1.3操作系统的目标和功能
    • 1.2操作系统的发展与分类
      • 1.2.1手工操作阶段
      • 1.2.2批处理阶段
      • 1.2.3分时操作系统
      • 1.2.4实时操作系统
      • 1.2.5网络操作系统和分布式计算机系统
      • 1.2.6个人计算机操作系统
    • 1.3操作系统的运行环境
      • 1.3.1操作系统的运行机制
      • 1.3.2中断和异常
      • 1.3.3系统调用
    • 1.4操作系统的体系结构
      • 1.4.1大内核和微内核
  • 2.进程管理
    • 2.1进程和线程
      • 2.1.1进程的概念和特征
      • 2.1.2进程的状态与转换
      • 2.1.3进程控制
      • 2.1.4进程的组织
      • 2.1.5进程的通信
      • 2.1.6线程概念和多线程模型
    • 2.2处理机调度
      • 2.2.1调度
      • 2.2.2调度的时机、切换与过程
      • 2.2.3进程调度方式
      • 2.2.4调度的基本准则
      • 2.2.5调度算法
    • 2.3进程同步
      • 2.3.1进程同步的基本概念
      • 2.3.2实现临界区互斥的基本方法
      • 2.3.3信号量
      • 2.3.4管程
    • 2.4死锁
      • 2.4.1死锁的概念
      • 2.4.2死锁的处理
  • 3.内存管理
    • 3.1内存管理的概念
      • 3.1.1内存管理的基本原理和要求
      • 3.1.2覆盖与交换
      • 3.1.3连续分配管理方式
      • 3.1.4非连续分配管理方式
    • 3.2虚拟内存管理
      • 3.2.1虚拟内存的概念
      • 3.2.2请求分页管理方式
      • 3.2.3页面置换算法
      • 3.2.4页面分配策略
      • 3.2.5抖动
      • 3.2.6工作集
      • 3.2.7地址翻译
  • 4.文件管理
    • 4.1文件系统基础
      • 4.1.1文件的概念
      • 4.1.2文件的逻辑结构
      • 4.1.3目录结构
      • 4.1.4文件共享
      • 4.1.5文件保护
    • 4.2文件系统实现
      • 4.2.1文件系统的层次结构
      • 4.2.2目录实现
      • 4.2.3文件实现
    • 4.3磁盘组织与管理
      • 4.3.1磁盘结构
      • 4.3.2磁盘调度算法
      • 4.3.3磁盘的管理
  • 5.输入输出管理
    • 5.1IO管理概述
      • 5.1.1IO设备
      • 5.1.2IO控制方式
      • 5.1.3IO子系统的层次结构
    • 5.2IO核心子系统
      • 5.2.1IO子系统
      • 5.2.2IO调度
      • 5.2.3高速缓存与缓冲区
      • 5.2.4设备分配与回收

操作系统

Author: wangml
Date: 2021/7/13
参考书籍：王道计算机考研-操作系统

1.计算机系统概述

1.1操作系统的基本概念

1.1.1操作系统的概念

操作系统：控制和管理计算机系统硬件和软件资源，合理调度计算机工作与资源的分配，为用户和其他软件提供方便的接口与环境的程序集合。

1.1.2操作系统的特征

基本特征：并发、共享、虚拟、异步

1. 并发：并发（同一时刻任然只是一个程序在运行，只是通过调度显得在一段时间内多个程序都在运行）和并行（同一时刻多个程序同时运行）的区别
2. 共享：互斥共享方式、同时访问方式（不需要并发则没必要共享，不能共享则无法并发）
3. 虚拟：由物理的变为逻辑的，时分复用技术、空分复用技术
4. 异步：

1.1.3操作系统的目标和功能

系统资源的管理者

1. 进程管理
2. 存储器管理
3. 文件管理
4. 设备管理
   作为用户和硬件之间的接口
5. 命令接口
6. 程序接口

1.2操作系统的发展与分类

1.2.1手工操作阶段

1.2.2批处理阶段

1. 单通道批处理系统，自动性、顺序性、单通道
2. 多道批处理系统，多道程序交替运行，宏观上并行微观上穿行

1.2.3分时操作系统

将处理器运行时间纷呈很短的时间片，按时间片分配处理器给各个程序
特征：同时性、交互性、独立性、及时性

1.2.4实时操作系统

特征：及时性、可靠性

1. 硬实时系统
2. 软实时系统

1.2.5网络操作系统和分布式计算机系统

1.2.6个人计算机操作系统

1.3操作系统的运行环境

1.3.1操作系统的运行机制

CPU执行：内核程序和应用程序，将CPU的状态划分为内核态和用户态
操作系统内核一般包括

1. 时钟管理
2. 中断机制
3. 原语
4. 系统控制的数据结构及处理

1.3.2中断和异常

通过中断进行用户态与内核态的转换
中duan处理

1. 关中断
2. 保存断点
3. 引出中断服务程序
4. 保存现场和屏蔽字
5. 开中断
6. 执行中断服务程序
7. 关中断
8. 恢复现场和屏蔽字
9. 开中断，中断返回

1.3.3系统调用

1.4操作系统的体系结构

1.4.1大内核和微内核

大内核：将操作系统主要的功能模块都作为一个紧密相连的整体运行在核心态，从而为应用提供高性能的系统服务。
微内核：仅将最基本的功能保留在内核，微内核最大的问题是性能问题，因为需要频繁的进行内核态与用户态的切换

2.进程管理

2.1进程和线程

2.1.1进程的概念和特征

进程：操作系统资源分配和调度的基本单位，程序段、数据段、PCB
引入进程，使得多道程序更好的并发执行，提高资源利用率和系统吞吐量
进程特征

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

2.1.2进程的状态与转换

进程状态

1. 运行态
2. 就绪态
3. 阻塞态
4. 创建态
5. 结束态
   进程状态转换
6. 就绪->运行
7. 运行->就绪
8. 运行->阻塞
9. 阻塞->就绪

2.1.3进程控制

1. 进程的创建，父进程与子进程，资源的分配
2. 进程的终止，资源的回收
3. 进程的阻塞与唤醒，
4. 进程切换，上下文信息的处理，PCB信息的更新，调度相应队列

2.1.4进程的组织

进程控制块：进程存在的唯一标识，保存进程描述信息、控制和管理信息、资源分配信息、处理器信息
程序段
数据段

2.1.5进程的通信

1. 低级通信方式：PV操作
2. 高级通信方式：以高效率传输大量数据
   1. 共享内存，基于数据结构的共享、基于存储区的共享，操作系统只负责提供可共享使用的存储空间和互斥同步工具
   2. 消息传递，直接通信、间接通信
3. 管道通信，半双工、读写的阻塞、缓冲

2.1.6线程概念和多线程模型

线程：程序执行的最小单元，具有标识符、线程控制块、同一个进程内的多花个线程共享进程资源
引入线程，减少程序在并发执行时付出的时空开销，提高操作系统的并发性能
进程与线程的比较

1. 调度
2. 拥有的资源
3. 并发性
4. 系统开销，线程的切换开销远低于进程的切换，可以从进程与线程的性质推导出
5. 地址空间和其他资源
6. 通信方面
   线程的实现方式
7. 用户级线程
8. 内核级线程
9. 组合式
   多线程模型
10. 多对一，线程管理在用户空间进行，效率高、多个线程无法并行运行
11. 一对一，并发能力强，但是开销大
12. 多对多，集上述 两者之长且克服了二者的缺点

2.2处理机调度

2.2.1调度

选择合适的进程将CPU分配给它
调度的层次

1. 作业调度（高级调度），内存与辅存之间的调度，进程的创建与销毁
2. 中级调度（内存调度），进程的就绪与挂起
3. 进程调度（低级调度），进程的就绪到运行

2.2.2调度的时机、切换与过程

不能进行进程的调度与切换的情形

1. 处理中断的过程中
2. 进程在操作系统内核程序临界区内
3. 需要完全屏蔽中断的原子操作过程中

2.2.3进程调度方式

1. 非抢占方式，实现简单、系统开销小、适合大多数批处理系统
2. 抢占方式，可以提高系统吞吐率和响应速度

2.2.4调度的基本准则

1. CPU利用率
2. 系统吞吐量，单位时间内CPU完成作业的数量
3. 周转时间，作业提交到作业完成的时间
4. 等待时间
5. 响应时间

2.2.5调度算法

1. 先来先服务FCFS，有利于CPU繁忙型作业，而不利于IO繁忙型作业
2. 短作业优先SJF，对长作业不利、所谓的短作业是预估得来的
3. 优先级调度算法，
   1. 非剥夺式优先级调度算法
   2. 剥夺式优先级调度算法
   3. 优先级
      1. 静态优先级
      2. 动态优先级
      3. 设置优先级：系统>用户、交互型>非交互型、IO型>计算型
4. 高响应比优先调度算法
5. 时间片轮转调度算法
6. 多级反馈队列调度算法

2.3进程同步

2.3.1进程同步的基本概念

临界资源
同步
互斥

2.3.2实现临界区互斥的基本方法

1. 软件实现
   1. 单标志法
   2. 双标志法先检查：可能出现多个进程同时进入临界区
   3. 双标志法后检查：出现饥饿现象
   4. Peterson's Algorithm
2. 硬件实现
   1. 中断屏蔽
   2. 硬件指令

2.3.3信号量

整型信号量
记录型信号量

2.3.4管程

1. 管程把对共享资源的操作封装起来
2. 每次仅允许一个进程进入管程
   条件变量
   生产者消费最问题
   读者-写者问题
   哲学家进餐问题
   吸烟者问题

2.4死锁

2.4.1死锁的概念

多个进程因竞争资源产生的相互等待现象，再无外部干涉的情况下，多个进程都将无法继续向前推进
产生的原因

1. 系统资源的竞争
2. 进程对资源的请求和释放的顺序不当
   死锁产生的必要条件
3. 互斥
4. 不剥夺
5. 请求并等待
6. 循环等待（死锁比循环等待要求更严格）

2.4.2死锁的处理

处理策略

1. 死锁预防，破坏产生死锁的必要条件
2. 避免死锁，在资源分配的动态过程中、银行家算法
3. 死锁的检测与解除，
   1. 资源剥夺
   2. 撤销进程
   3. 进程回退

3.内存管理

3.1内存管理的概念

3.1.1内存管理的基本原理和要求

系统内存大小限制了无法将所有进程和数据放入内存，因此需要对内存进行动态分配
内存管理的功能

1. 内存空间的分配和回收
2. 地址转换
3. 内存空间的扩充
4. 存储保护
   物理地址与逻辑地址
   内存保护
5. 用户进程无法影响操作系统
6. 用户进程不会相互影响

3.1.2覆盖与交换

覆盖打破必须将一个进程全部信息都装入内存才能运行的限制
交换将处于等待状态的进程从内存转移到辅存

3.1.3连续分配管理方式

1. 单一连续分配，仅适用于单用户单任务
2. 固定分区分配，内部碎片问题
   1. 分区大小相等
   2. 分区大小不等
3. 动态分区分配，外部碎片问题
   1. 首次适应算法，空闲分区链按地址排序，大小能满足的第一个分区、最简单，通常也最好最快
   2. 最佳适应算法，空闲分区链按容量大小递增排序，找到第一个满足要求的分区
   3. 最坏适应算法，空闲分区链按容量大小递减排序，找到第一个满足的分区，即最大分分区
   4. 邻近适应算法，分配空闲分区时，从上一次查找的结束位置开始查找

3.1.4非连续分配管理方式

运行作业时是否需要将作业所有页面都装入内存基本分页存储管理方式、请求分页存储管理方式

1. 基本分页存储管理方式，
   1. 分页 只会产生很小的内部碎片，
   2. 页面大小、地址结构（页号、偏移量）、页表
   3. 地址变换
   4. 快表，存放当前访问的若干表项，加快地址变换速度
   5. 局部性原理，快表命中率可以达到90%
   6. 两级页表
   7. 分页机制对用户完全透明
   8. 有效的提高内存利用率
2. 基本分段存储管理方式，
   1. 分段，段式管理方式按照用户进程中的自然段划分逻辑空间、段号和段内偏移量由编译程序完成
   2. 段表
   3. 地址变换
   4. 分段式管理能反映程序的逻辑结构，并有利于段的共享
3. 段页式管理方式
   1. 地址变换，段表->段号->页表->页号->页内偏移量
   2. 一个进程只有一个段表，但可能有多个段表

3.2虚拟内存管理

3.2.1虚拟内存的概念

1. 传统存储管理方式的特征
   1. 一次性，需要将作业全部装入内存才能运行
   2. 驻留性，程序结束之前不会被换出内存
2. 局部性原理，
   1. 时间局部性，此事被执行的指令不久后会再次执行
   2. 空间局部性，某个存储单元被访问后，它周围的存储单元也将被访问，内存、层次结构的高速缓存、
3. 虚拟存储器的定义和特征，装入程序时只需要装入一部分，而将其他部分放在外存，在需要时进行交换，使得在程序看来，操作系统提供了一个更大的内存
   1. 多次性，程序不需要一次性全部装入内存
   2. 对换性，程序不需要常驻内存，只需要在必要时换入换出
   3. 虚拟性，逻辑上扩充内存容量而非物理上
4. 虚拟内存技术的实现，有以下三种方式，需要段页表、中断机制、变址机制
   1. 分页
   2. 分段
   3. 段页式

3.2.2请求分页管理方式

在基本分页管理的基础上增加了请求调页和页面置换功能

1. 页表机制
2. 缺页中断机制
3. 地址变换机制

3.2.3页面置换算法

1. OPT最佳置换算法，淘汰最不可能再被使用的页面，最长时间未被使用的页面（推测未来，向后看）
2. FIFO先进先出页面置换算法
   1. Belady异常、随着分配的物理块增加，缺页现象不减反正
3. LRU最近最久未使用置换算法（根据已知，向前看）
4. 时钟置换算法，

3.2.4页面分配策略

1. 驻留集大小，
   1. 固定分配局部置换，每个进程的物理块数固定，缺页则换出程序拥有的已分配配的一页
   2. 可变分配全局置换，缺页时将操作系统拥有的空闲物理块分配给程序
   3. 可变分配局部置换，缺页置换进程自身拥有的已在内存的页出来，频繁缺页系统再为进程分配额外的物理块，缺页率低减少分配给该进程的物理块
2. 页面调入时机
   1. 预调页策略
   2. 请求调页策略
3. 从何处调入页面，
   1. 对换空间足够，可以全部从对换区调入所需页面
   2. 对换空间不足，不会被修改的文件从文件区调入，可能被修改的从对换区调入
   3. Unix方式，

3.2.5抖动

刚被换出的页面有需要调入内存，产生频繁的页面调度行为

3.2.6工作集

某段时间间隔内，进程要访问的页面集合

3.2.7地址翻译

4.文件管理

4.1文件系统基础

4.1.1文件的概念

文件存储在计算机上的信息集合
文件是用户输入输出时的基本单位

1. 内容信息
2. 索引信息
3. 权限信息
   对文件的操作
4. 文件的打开关闭等
5. 文件控制块PCB
6. 文件属性

4.1.2文件的逻辑结构

1. 无结构文件（流式文件）
2. 有结构文件（记录式文件）

4.1.3目录结构

1. 文件控制块和索引结点
2. 目录结构

4.1.4文件共享

1. 基于索引结点的共享方式（硬链接）
2. 利用符号链实现文件共享（软连接、快捷方式）

4.1.5文件保护

1. 访问类型，
2. 访问控制

4.2文件系统实现

4.2.1文件系统的层次结构

1. 用户调用接口
2. 文件目录系统
3. 存取控制验证模块
4. 逻辑文件系统与文件信息缓冲区
5. 物理文件系统
6. 辅助分配模块
7. 设备管理程序模块

4.2.2目录实现

1. 线性列表
2. 哈希表

4.2.3文件实现

1. 文件分配方式
   1. 连续分配
   2. 链接分配，显式、隐式
   3. 索引分配
2. 文件存储空间管理
   1. 文件的数据信息和控制信息的分离
   2. 目录区和文件区
   3. 文件存储器空间管理
      1. 空闲表法
      2. 空闲链表法
      3. 位视图法
      4. 成组链接法

4.3磁盘组织与管理

4.3.1磁盘结构

磁盘、磁头、磁道

4.3.2磁盘调度算法

1. 寻道时间，磁头移动到指定磁道的时间
2. 延迟时间，磁头定位到指定扇区的时间
3. 传输时间，从磁盘读出或写入数据的时间
   磁盘调度
4. FCFS
5. 最短寻找时间优先
6. SCAN算法，电梯调度算法，不利于远离磁头一端的访问
7. 循环扫描算法

4.3.3磁盘的管理

1. 磁盘初始化
2. 引导块坏块

5.输入输出管理

5.1IO管理概述

5.1.1IO设备

按特性

1. 交互设备
2. 存储设备
3. 网络通信设备
   块设备和字符设备

5.1.2IO控制方式

1. 程序直接控制方式，CPU和IO设备串行工作，极大的浪费了CPU效率
2. 中断驱动方式，
3. DMA方式，
4. 通道控制方式

5.1.3IO子系统的层次结构

1. 用户层IO软件
2. 设备独立性软件
3. 设备驱动程序
4. 中断处理程序
5. 硬件设备

5.2IO核心子系统

5.2.1IO子系统

5.2.2IO调度

5.2.3高速缓存与缓冲区

1. 磁盘高速缓存
2. 缓冲区
   1. 单缓冲
   2. 双缓冲
   3. 循环缓冲
   4. 缓冲池

5.2.4设备分配与回收

设备分配

1. 独占式使用设备
2. 分时式共享使用设备
3. SPOOLing