Elaine's Blog

Do it while we can do

操作系统知识点汇总

Posted on In
操作系统的常考知识点的简单整理，不含例题，例题可以在GitHub内下载往年试卷练习

一、引论

  1. 定义：一种系统软件
  2. 地位：裸机之上的第一层软件，是建立其他所有软件的基础。它是整个系统的控制管理中心，既管硬件，又管软件，它为其他软件提供运行环境。
  3. 基本特征：并发、共享、异步、虚拟。（最基本特征：并发、共享）
  4. 主要功能：处理机管理、存储器管理、文件管理、设备管理
  5. 发展历程：手工操作阶段、批处理阶段、分时操作系统（有人机交互）、实时操作系统（能优先处理紧急任务）

一些预置概念

  1. 两种指令

    • 特权指令：不允许用户程序使用（只允许操作系统使用）。如IO指令、置中断指令
    • 非特权指令：普通用户的运算指令

  2. 两种程序

    • 内核程序：
    • 应用程序：

  3. 处理机状态

    • 用户态（目态）：CPU只能执行非特权指令
    • 核心态（管态、内核态）：可以执行所有指令
    • 用户态到核心态：通过中断（是硬件完成的）
    • 核心态到用户态：特权指令psw的标注位：0用户态、1核心态

  4. 原语

  5. 中断和异常

    • 内中断（异常，信号来自内部）
      • 自愿中断——指令中断
      • 强迫中断——硬件中断、软件中断
    • 外中断（中断，信号来自外部）
      • 外设请求（如打印机缺纸……）
      • 人工干预

  6. 系统调用

    系统给程序员（应用程序）提供的唯一接口，可获得OS的服务。在用户态发生，核心态处理

  7. 体系结构

    • 大内核
    • 微内核

二、进程调度

2.1 进程管理

  1. 目的

    为了更好地描述和控制程序并发执行，实现操作系统的并发性和共享性

    （进程是动态的，程序是静态的）

  2. 定义

    是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位

  3. 组成

    • 进程控制块PCB：保存进程运行期间相关的数据，是进程存在的唯一标志
    • 程序段：能被进程调度到CPU的代码
    • 数据段

  4. 进程的状态：

    • 运行态
    • 就绪态：一切资源准备完善，等待处理机调度
    • 阻塞态
    • 创建状态
    • 结束状态

  5. 进程的状态转换

    • 运行态->就绪态：时间片用完等
    • 运行态->阻塞态：等待资源或事件等

  6. 线程

    • 引入目的：为了更好的使用多道程序并发执行，提高资源利用率和系统吞吐量
    • 特点：是程序执行的最小单位，基本不拥有任何系统资源（调度的基本单位）‘’资源分配的基本单位还是进程）
    • 线程属于某一个进程，并与进程内的其他线程一起共享进程的资源

  7. 进程和线程的区别

    线程具有许多传统进程所具有的特征，故又称为轻型进程(Light—Weight Process)或进程元；而把传统的进程称为重型进程(Heavy—Weight Process)，它相当于只有一个线程的任务。在引入了线程的操作系统中，通常一个进程都有若干个线程，至少包含一个线程。

    • 根本区别：进程是操作系统资源分配的基本单位，而线程是处理器任务调度和执行的基本单位

    • 资源开销：每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销；线程可以看做轻量级的进程，同一类线程共享代码和数据空间，每个线程都有自己独立的运行栈和程序计数器（PC），线程之间切换的开销小。

    • 包含关系：如果一个进程内有多个线程，则执行过程不是一条线的，而是多条线（线程）共同完成的；线程是进程的一部分，所以线程也被称为轻权进程或者轻量级进程。

    • 内存分配：同一进程的线程共享本进程的地址空间和资源，而进程之间的地址空间和资源是相互独立的

    • 影响关系：一个进程崩溃后，在保护模式下不会对其他进程产生影响，但是一个线程崩溃整个进程都死掉。所以多进程要比多线程健壮。

    • 执行过程：每个独立的进程有程序运行的入口、顺序执行序列和程序出口。但是线程不能独立执行，必须依存在应用程序中，由应用程序提供多个线程执行控制，两者均可并发执行

2.2 处理机调度

  1. 概念

    是对处理机进行分配，即从就绪队列中按照算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

  2. 分类

    • 高级调度（作业调度）次数少
    • 中级调度（内存对换）次数中等，与挂起态有关
    • 低级调度（进程调度）次数多

  3. 调度方式

    • 剥夺式
    • 非剥夺式

  4. 调度准则

    • CPU利用率
    • 系统吞吐量
    • 周转时间
    • 等待时间
    • 响应时间

  5. 进程调度算法

    • 先来先服务FCFS：有利于长作业

    • 最短作业优先算法SJF

    • 最短剩余时间优先算法SRTF：把SJF改为抢占式

    • 最高响应比优先算法HRN：长短作业兼顾

      响应比计算\(R=1+\frac{作业等待时间}{作业处理时间}\)

    • 时间片轮转算法：剥夺式调度

    • 多级反馈队列调度算法：长短作业兼顾

2.3 管程

  1. 组成
    • 名称：管理进程的程序
    • 局部于管程内部的共享结构数据说明
    • 对该数据结构进行操作的一组过程（或函数）
    • 共享数据设置初值
  2. 条件变量（进程阻塞的原因）操作
    • wait（正在调用管程的进程用wait插入等待队列，释放管程）
    • signal（唤醒一个因x条件而阻塞的进程）

2.4 进程同步

  1. 引入原因：协调进程之间的相互制约关系

  2. 制约关系

    • 同步：直接制约关系，访问者对资源有序访问
    • 互斥：间接制约关系，多个进程之间共享临界资源存在的关系，一个进程进入临界区使用临界资源时，另一个进程必须等待。

  3. 临界资源

    一次仅允许一个进程使用的资源（例如：打印机，共享缓冲区，共享变量，公共队列……）

  4. 临界区

    指进程中涉及访问临界资源的那个程序段

  5. 临界区互斥

    • 原则
      • 有空让进
      • 无空等待
      • 多中择一
      • 有限等待
      • 让权等待：如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。
    • 基本方法
      • 信号量->PV操作
        • wait（占有资源）P操作
        • signal（释放资源）V操作

2.5 死锁

  1. m个系统资源总数，n个进程数，k个每个进程最大需求量则：\(m>=n*(k-1)+1\)
  2. 产生原因：非剥夺资源的竞争和进程的不恰当推进顺序（与饥饿不同）
  3. 定义：多个进程因竞争资源而造成的一种僵局，如果没有外力，这些进程将无法推进
  4. 四个必要条件：
    • 互斥使用（资源独占）
    • 不可强占（不可剥夺）：该资源只能由本进程释放
    • 请求和保持（部分分配，占有申请）：进程已经保持一个资源，但提出新的资源请求
    • 循环等待
  5. 解决方法：
    • 预防死锁
      • 破坏不可剥夺条件：在允许进程动态申请资源的前提下，一个进程在申请新的资源不能得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请
      • 破坏请求和保持条件：要求每个进程在运行前一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配
      • 破坏循环等待条件：采用资源有序分配法，把系统中所有资源编号，进程在申请操作资源时必须严格按照资源编号的递增次序进行，否则操作系统不给予分配
    • 避免死锁
      • 安全状态（寻找安全序列）
      • 银行家算法（动态方法）
    • 检测死锁
      • 进程资源分配图+死锁定理
    • 解除死锁
      • 资源剥夺法
      • 撤销进程法
      • 进程回退法

三、内存管理

3.1 功能

  1. 内存空间的分配与回收
  2. 地址转换/地址重定位/地址映射：逻辑地址（相对地址、虚拟地址）转换为物理地址（绝对地址）
  3. 内存空间的扩充：虚拟内存的应用
  4. 存储保护：防止内存地址越界

3.2 装入模块放入内存方式

  1. 绝对装入：适合单道程序
  2. 可重定位装入：静态重定位，适合多道程序
  3. 动态运行时装入：动态重定位

3.3 内存保护方式

  1. 在CPU中设施一对上下寄存器
  2. 采用重定位寄存器+界地址寄存器

3.4 扩充内存

  1. 多道程序环境下
    • 覆盖
    • 交换：中级调度技术
  2. 虚拟内存管理
    • 局部性原理
      • 空间局部性
      • 时间局部性
    • 特征
      • 多次性
      • 对换性
      • 虚拟性
    • 管理内存方式
      • 请求分页管理方式
        • 新增功能
          • 请求调页功能
          • 页面置换功能
            • 最佳置换算法
            • 先进先出算法：出现Belady异常
            • 最近最久未使用算法
            • 时钟置换算法：淘汰最近未使用的
            • 改进时钟算法：最先淘汰被修改且没有访问的
          • 页面分配策略
            • 固定分配局部置换：产生内部碎片
            • 可变分配全局置换：产生外部碎片
            • 可变分配局部置换
          • 调入页面时机
            • 预调页策略
            • 请求调页策略
        • 异常
      • 请求分段管理方式
    • 最大：不超过计算机的地址位数

3.5 管理内存的方式

  1. 连续分配方式
    • 单一连续分配
    • 固定分区分配
      • 产生内部碎片、无外部碎片
    • 动态分区分配
      • 产生外部碎片
      • 分配算法：首次适应法、循环首次适应法、最佳适应法、最坏适应法、邻近适应法
  2. 离散分配方式
    • 分页存储管理方式
      • 单级分页
        • 类似固定分区技术，产生内部碎片
        • 逻辑结构分页号+页内偏移量
        • 引入快表，加速地址变换的速度
      • 二级分页
    • 分段存储管理方式
      • 分段管理的地址空间是二维的
    • 段页式存储管理方式

四、文件管理

4.1 文件

  1. 文件的组成：文件体+文件说明

  2. 文件的逻辑结构：

    • 记录式文件
    • 流文件

  3. 文件的存取方法：

    • 顺序存取
    • 直接存取
    • 索引存取

  4. 文件的物理结构

    • 连续文件
    • 串联文件
    • 索引文件

  5. 文件的存储设备

    • 顺序存储设备
    • 直接存储设备

4.2 文件目录结构

  1. 数据结构：
    • 文件控制块
      • 文件名
      • 物理地址
    • 索引节点
  2. 操作：搜索、创建、删除、显示目录、修改目录
  3. 结构：
    • 单级目录结构
    • 二级目录结构
    • 树形目录结构
    • 无环图目录结构

4.3 文件共享

  1. 基于索引节点的共享方式（硬链接）：链接到多个目录中
  2. 基于符号链实现文献共享（软链接）：指存放路径link

4.4 文件保护

  1. 访问类型：读写执行添加
  2. 访问控制：控制用户身份
  3. 口令密码

4.5 文件系统层次结构

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

4.6 目录实现

  1. 线性列表
  2. 哈希表

4.7 文件分配方式

  1. 连续分配
  2. 链接分配
  3. 索引分配

4.8 文件存储空间管理

  1. 初始化：目录区、文件区
  2. 管理方法：
    • 空闲表法
    • 空闲链表法
    • 位示图法

4.9 磁盘

  1. 磁盘地址：柱面号x盘面号x扇区号
  2. 读写操作时间：寻找时间、延迟时间、传输时间
  3. 磁盘调度算法
    • 先来先服务FCFS
    • 最短寻找时间优先SSTF：存在“饥饿”现象
    • 扫描算法/电梯算法SCAN
    • 循环扫描算法CSCAN
  4. 磁盘管理
    • 磁盘初始化
    • 引导块
    • 坏块
  5. 提高磁盘I/O速度的方法
    • 提前读
    • 延迟写
    • 虚拟盘（RAM盘）

五、IO外设管理

5.1 分类

  1. 块设备：如磁盘……
  2. 字符设备：如打印机……

5.2 I/O控制方式

  1. 程序直接控制：没有中断机制，是忙查询；造成CPU资源浪费
  2. 中断驱动方式：字节；外设做好了再呼唤CPU；实现CPU和设备并行
  3. DMA方式：数据块 ；不经过CPU；内存和设备之间建立了一条数据通路
  4. 通道控制方式：一种I/O专用处理器；效率比DMA高

5.3 I/O子系统层次结构

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

5.4 I/O管理内容

  1. 状态跟踪
  2. 设备存取
  3. 设备分配
  4. 设备控制

5.5 I/O核心子系统

  1. 服务

    • IO调度
    • 缓冲与高速缓存
    • 设备分配与回收
    • 假脱机
    • 设备保护与差错处理

  2. 高速缓存+缓冲区

    • 高速缓存
    • 缓冲区：单缓冲、双缓冲、循环缓冲、缓冲池

  3. 设备分配时数据结构

    • 设备控制表DCT
    • 控制器控制表COCT
    • 通道控制表CHCT
    • 系统设备表SDT

  4. 设备分配步骤

    • 分配设备 SDT找DCT
    • 分配控制器 COCT
    • 分配通道 CHCT

  5. 设备分配算法

    • 先来先服务算法
    • 优先级高者优先

  6. SPOOLing系统

    • 定义：SPOOLing系统既不同于脱机方式，也不同于直接藕合方式，SPOOLing技术实际上是一种外围设备同时联机操作技术，又称为排队转储技术。它在输入和输出之间增加了“输入井”和“输出井”的排队转储环节，以消除用户的“联机”等待时间。在系统输入模块收到作业输入请求信号后，输入管理模块中的读过程负责将信息从输入装置中读入输入井缓冲区。当缓冲区满时，由写过程将信息从缓冲区写到外存的输入井中，读过程和写过程反复循环，直到一个作业输入完毕。当读过程读到一个硬件结束标志之后，系统再次驱动写过程把最后一批信息写入外存输入井并调用中断处理程序结束该次输入。然后，系统为该作业建立作业控制块，从而使输入井中的作业进入作业等待队列，等待作业调度程序选中后进入内存运行。系统在管理输入井过程中可以“不断”读入输入的作业，直到输入结束或输入井满而暂停。

    • 组成

      • 输入井和输出井：在磁盘中
      • 输入缓冲区和输出缓冲区：在内存中
      • 输入进程和输出进程

      从输入井读取信息，作业执行结果暂存输出井

    • 特点

      • 提高了IO速度
      • 设备不被任何进程独占
      • 实现了虚拟设备功能

六、大题涉及知识点

  1. 信号量、PV操作

    • 机票问题
    • 生产者——消费者问题
    • 读者和写者问题
    • 理发师问题

  2. 银行家算法

  3. 进程调度算法

  4. 页面置换算法

    • 最佳置换算法OPT：选择永不使用的或在最长时间内不再被访问的页面进行置换
    • 先进先出置换算法FIFO：选择最炫进入内存的页面进行置换
    • 最近最久未使用置换算法LRU：选择最近一段时间内最长时间没有被访问过的页面进行置换
    • 时钟置换算法/最近未使用置换算法Clock/NRU：
    • 最少使用置换算法LFU：把当前为止被访问次数最少的页面淘汰（设置访问计数器）

  5. 逻辑地址转换物理地址

    • 先来先服务FCFS：有利于长作业

    • 最短作业优先算法SJF

    • 最短剩余时间优先算法SRTF：把SJF改为抢占式

    • 最高响应比优先算法HRN：长短作业兼顾

      响应比计算\(R=1+\frac{作业等待时间}{作业处理时间}\)

    • 时间片轮转算法：剥夺式调度

    • 多级反馈队列调度算法：长短作业兼顾

  6. 磁盘驱动臂调度算法

    • 先来先服务FCFS

    • 最短寻找时间优先SSTF：存在“饥饿”现象

    • 扫描算法/电梯算法SCAN

    • 循环扫描算法CSCAN