操作系统课程复习

---

一、操作系统引论

操作系统

• 定义： 一组能有效地组织和管理计算机硬件和软件资源、合理地对各类任务进行调度，以及方便用户使用的程序的集合
• 基本特征：并发，共享，虚拟，异步
• 功能：处理及管理，存储器管理，设备管理，文件管理，人机接口

多道程序系统：多个程序同时在内存中并发进行。由作业调度程序按一定的算法从后备队列选择若干作业调入内存，使其共享CPU和系统的各种资源

• 后备队列：用户所提交的程序先存放在外存上并排成一个队列，称为后备队列

• 系统吞吐量：指从作业进入系统（后备队列）开始所完成的总量

• 周转时间：指从作业进入系统开始，直至完成并退出系统为止所经历的时间

分时系统的特征：多路性，独立性，及时性（响应时间），交互性

实时系统的特征：实时性，可靠性

并发：多个事件在同一时间段内发生

并行：多个事件在同一时刻发生

微内核结构

• 应用场景：支持多处理机，适用于分布式系统环境
• 定义：精心设计的实现现代操作系统核心功能的小型内核，而并非一个完整的操作系统，仅为构建通用操作系统提供一个重要基础
• 服务方式：客户-服务器（C/S）模式
• 特征：以微内核为操作系统的核心，以C/S模式为基础，采用面向对象的程序设计方法

【各种操作系统提出的目的】

二、进程的描述与控制

进程

• 定义：是进程实体的运行过程，是系统进行资源分配和调度的一个基本单位
• 引入目的：使多个程序能够并发执行，以提高资源利用率和系统吞吐量
• 属性：操作系统拥有资源和独立运行的基本单位
• 进程实体：程序（数据段 + 程序段）+ 进程控制块（PCB）
• PCB的作用：使多道系统中不能独立运行的程序，成为能够独立运行且能并发执行的进程。
• 特性：动态，并发，独立，异步
• 【进程和程序的区别与联系】
  • 结构上进程实体除了程序段和数据段外，还包含进程控制块PCB
  • 进程是程序的一次执行过程，具有动态，即由创建产生，调度执行，撤销消亡；程序具有静态性，是一组指令的有序结合
  • 多个进程实体能够同时在内存中并发执行，而程序的并发执行具有不可再现性，因此程序无法正确地并发执行
  • 进程是拥有资源和独立运行的基本单位，而程序无法在多道程序环境下独立运行
  • 进程和程序不一一对应：同一程序的一次或多次运行形成不同的进程，而一个进程在生命周期的不同阶段可以执行不同程序
• 基本状态：就绪，执行，阻塞
• 相互转换
• 阻塞：进程调用阻塞原语block将自己阻塞
• 唤醒：有关进程调用唤醒原语wakeup将等待该事件的进程唤醒，自己无法唤醒

进程同步

• 主要任务：协调多个相关进程的执行次序，使并发执行的进程能按一定的规则或时许共享资源和相互合作，从而使程序的执行具有可再现性
• 临界资源：访问时进程间应采取互斥方式实现共享
• 临界区
  • 定义：每个进程中访问临界资源的代码段
  • 作用：保证各进程互斥地进入或执行自己的临界区，以实现对临界资源的互斥访问
• 同步机制遵循的规则：空闲让进，忙则等待，有限等待，让权等待

信号量机制

• 基本思想
  • 使用信号量标记临界资源是否被利用
  • 检查和释放信号量的任务由操作系统完成
  • 应用程序中可调用相应的原语，以完成对信号量的检查和释放
• 应用：限制访问和协调进行
• 【根据前驱图写代码描述】
• 【进程同步问题】
  • 司机和售票员
  • 生产者-消费者
  • *哲学家进餐
  • 读者-写者
  • 无死锁的哲学家进餐
  • 售票
  • 单行车道
  • 阅览室
  • 缓冲队列

线程

• 引入目的：减少程序在并发执行时所付出的时空开销，使操作系统有更好的并发性
• 属性
  • 轻型实体
  • 独立调度的基本单位
  • 可并发执行
  • 共享进程的资源
  • 可以创建或撤销另一个线程

*【 * 线程和进程的区别与联系】*

• 线程是调度和分派的基本单位，进程是拥有资源的基本单位

• 除必不可少的资源外，线程不拥有系统资源，但可以访问并获得其隶属进程的系统资源

• 支持多线程的操作系统中，不仅不同进程中的线程间可以并发，同一进程内的线程间也可以并发

• 进程具有独立性，独立地申请资源和运行，但同一进程内的多个线程共享进程的地址空间和其他资源，独立性较低

• 线程的系统开销很小，仅需要保存和设置少量信息，而进程切换时时空开销较大

• 线程和进程都支持多处理机系统

【内核级线程和用户级线程的区别】

• 内核级线程有内核支持，而用户级线程无内核支持
• 内核级线程调度一个应用程序中的多个线程同时在多个处理机上并行运行，从而提高执行速度和运行效率；而用户级线程一次只为一个进程分配一个处理器
• 内核级线程的调度单位是线程，CPU执行时间多，切换速度较慢
• 用户级线程的调度单位是进程，CPU执行时间少，切换速度较快
• 系统调用时内核级线程仅阻塞该线程，而用户级进程阻塞整个进程

三、处理机调度与死锁

作业调度算法

• 先来先服务（FCFS）调度算法
• 短作业优先（SJF）调度算法
• 优先级（PSA）调度算法
• 高响应比优先（HRRN）调度算法

进程调度

• 调度方式
  • 抢占式：实时系统
  • 非抢占式：批处理系统
• 进程调度算法
  • 先来先服务（FCFS）调度算法
  • 短进程优先（SPF）调度算法
  • 优先级（PSA）调度算法
  • 高响应比优先（HRRN）调度算法
  • 轮转（RR）调度算法
  • 多队列调度算法
  • 多级反馈队列调度算法

实时调度算法

• 最早截至时间优先（EDF）算法
• 最低松弛度优先（LLF）算法

死锁

• 起因：对不可抢占资源或可消耗资源的争夺
• 定义：若一组进行中的每一个进程都在等待仅有该组进程中的其他进程才能引发的事件，那么该组进程是死锁的
• 必要条件（需要同时满足）
  • 互斥
  • 请求和保持
  • 不可抢占
  • 循环等待

避免死锁

• 安全序列：系统能按照某顺序为某进程分配所需资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成

• 系统安全状态：能够找到一个安全序列，从而不会导致死锁的状态

• 实质：系统在进行资源分配时，如何避免系统进入不安全状态

• 【银行家算法】

• 【安全性算法】

死锁定理：当且仅当一个状态对应的资源分配图是不可简化的，此时为死锁状态

死锁的解除：

• 抢占资源（资源争夺法）
• 终止（撤销）进程

四、存储器管理

单一连续分配（单道）：把内存分为系统区和用户区两部分

固定分区分配（多道）

• 基本思想：把用户区划分为若干大小固定的分区，每个分区只放一个进程，当一个分区空闲时，可以选择一个新进程进入该分区运行
• 划分分区的方法
  • 分区大小相等
  • 分区大小不等

动态分区分配（可变分区分配）

• 数据结构

  • 可变分区表
  • 可变分区链

• 分配算法

  • 首次适应（FF）算法
  • 循环首次适应（NF）算法
  • 最佳适应（BF）算法
  • 最坏适应（WF）算法

• 内存回收

  • 与前一个空闲分区邻接：修改前一分区大小
  • 与后一个空闲分区邻接：二者合并，新空闲分区大小为二者之和，回收区首址为新分区首址
  • 与前后两个空闲分区邻接：三者合并，大小为三者之和，使用前一个分区表项和首址，取消后一个分区表项
  • 不与前后两个空闲分区邻接：新空闲分区为回收区的表项和首址，插入到空闲分区链的适当位置

动态可重定位分区分配

分页存储管理

• 页面：进程的逻辑地址空间分成若干大小相等的页，大小由机器地址结构决定

• 物理块：把内存的存储空间划分为与页大小相等的块

• 注意

  • 分页由系统完成
  • 每一页的页内地址相对于0开始
  • 调度时，必须一次性地把进程的所有页装入内存的物理块中

• 地址结构：页号+页内地址

  • 页号和页内地址的划分由操作系统自动完成，对用户透明

  【页内地址和偏移量相关计算】

• 地址变换机构：将逻辑地址重定位为物理地址

• 【快表原理】

  1. CPU给出有效地址后，地址变换机构自动将页号送入快表

  2. 将此页号与快表中所有页号比较：

     • 若有匹配页号=>直接从快表中读出对应的物理块号=>送入物理地址寄存器
     • 若无匹配页号=>访问内存中的页表=>将对应块号送入物理地址寄存器，同时将此页表项加入快表寄存器单元

  3. 若快表已满=>操作系统找到一个最早的且不再需要的页表项换出

分段存储管理

• 地址结构：段号+段内地址

• 注意

  • 段和段之间可以不连续，但是每一段内的空间连续
  • 每一段大小可以不相等

• 【分页和分段的主要区别】

  • 页是信息的物理单位，分页由于系统管理的需要，为了消减内存碎片，提高内存利用率

    段是信息的逻辑单位，分段为了更好地满足用户的需要，段含有一组其意义相对完整的信息

  • 页的大小固定，由系统决定，系统把逻辑地址划分为页号和页内地址，是由机器硬件实现，系统中只能有一种大小的页面

    段的长度不固定，取决于用户所编写的程序，其大小在编译时根据信息的性质划分

  • 分页的作业地址空间是一维的，即单一的线性地址空间，只需记忆符表示一个地址

    分段的作业地址空间是二维的，既需要给出段名。又需给出段内地址

五、虚拟存储器

虚拟存储器

• 定义：具有请求调入功能和置换功能，能从逻辑上扩充内存容量的一种存储器系统
• 逻辑容量 = 内存容量 + 外存容量
• 最大容量：由计算机的地址结构决定
• 实现方法
  • 请求分页存储管理方式
  • 请求分段存储管理方式
  • 段页式虚拟存储管理方式

请求分页存储管理方式

• 与基本分页系统的异同

• 硬件支持

  • 请求页表机制
  • 缺页中断机构
  • 地址变换机构

• 【缺页中断与一般中断的区别】

  • 缺页中断在指令执行期间产生和处理中断信号。通常，CPU只能在指令之间接受中断，而缺页中断在指令执行中间得到服务。即发现要访问的数据或指令不在内存时，立即产生缺页中断并进行处理
  • 一条指令可能引起多次不同的页面中断，系统中的硬件机制能够保存多次中断时的状态

抖动（由于置换算法选择不当引起）：系统一直忙于页面的换入和换出，大部分CPU时间用于处理缺页中断和页面淘汰，很少顾及到用户进程的实际执行

页面置换算法

• 最佳置换算法（Optimal）
• 先进先出置换算法（FIFO）
• 最近最久未使用置换算法（LRU）

Belady现象：分配的页面数增多但缺页率反而提高的异常现象（FIFO存在这种现象）

六、输入输出系统

对I/O设备的控制方式

• 使用轮询的可编程I/O方式（程序控制方式）忙—等待方式，CPU和设备串行工作

• 使用中断的可编程I/O方式（中断驱动方式）CPU与IO设备并行工作，以字节为单位进行I/O

• 直接存储器访问方式（DMA方式）

DMA与中断方式的区别

• 中断的时机不同

  • 中断方式是在数据寄存器满后，发中断请求，CPU进行中断处理
    • DMA方式是在所要求传送的数据块全部传送结束时要求CPU进行中断处理，大大减少了CPU进行中断处理的次数

• CPU控制方法不同

  • 中断方式的数据传送是由CPU控制完成的

  • DMA方式是在DMA控制器的控制下不经CPU控制完成的

I/O通道控制方式

• 通道：通过执行通道程序并与设备控制器共同实现对I/O设备控制

• 瓶颈问题：通道价格昂贵，配备不可能太多，产生了I/O瓶颈

  解决方法：增加设备到主机间的通路而不增加通道

设备分配算法

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

用户层的I/O软件

• Spooling技术（假脱机系统）

  • 目的：可以将一台物理设备虚拟为多台逻辑设备，以允许多个用户共享一台物理设备

  • 实质：模拟脱机输入/输出

  • 组成：必须建立在具有多道程序功能的OS上，有高速随机外存（通常为磁盘）的支持

    • 输入井、输出井
      磁盘上的两块存储区，用于暂存输入、输出的数据
    • 输入缓冲区、输出缓冲区
      位于内存中，作用是缓和CPU、设备之间的速度差异
    • 输入进程、输出进程
      • 输入进程：利用输入缓冲区为中介，把输入设备的数据存入输入井
      • 输出进程：设备空闲时，将输出井中的数据利用输出缓冲区送入设备
    • 井管理程序
      控制任务与井之间信息的交换

  • 特征

    • 提高了I/O速度
    • 将独占设备改造为共享设备
    • 实现了虚拟设备功能

  **Spooling技术提高了独占设备的利用率**

【缓冲区引入的原因】

• 缓和CPU和I/O设备之间速度不匹配的矛盾
• 减少对CPU的中断频率，放宽对CPU中断响应时间的限制
• 解决生产者和消费者之间数据粒度（单元大小）不匹配的问题
• 提高CPU和I/O设备之间的并行性，提高系统的吞吐量和设备的利用率

缓冲区的类型

• 单缓冲区：每当用户进程发出一次I/O请求时，OS便在内存中为之分配一个缓冲区

• 双缓冲区：设备输入时，先将数据送入缓冲区1，装满后转向缓冲区2，此时OS可从缓冲区1中读取数据，并送入用户进程。

• 环形缓冲区：多个缓冲区，多个指针

• 作为输入的缓冲区可设置三个指针

  • Nexti: 指示输入进程下次可用空缓冲区R
  • Nextg: 指示计算进程下一个可用缓冲区G
  • Current: 指示计算进程正使用的缓冲区C

• 进程同步问题：使用输入循环缓冲，指针Nexti和指针Nextg将不断地沿着顺时针方向移动，这样就可能出现下述两种情况:

  • Nexti指针追赶上Nextg指针

    • 表示输入数据的速度大于处理数据的速度，已无空缓冲区可用。
    • 此时，输入进程应阻塞，直到计算进程把某个缓冲区中的数据读取完，使之成为空缓冲区R，并调用Releasebuf过程将它释放时，才将输入进程唤醒。
    • 这种情况被称为系统受计算限制

  • Nextg指针追赶上Nexti指针

    • 表示输入数据的速度低于处理数据的速度，此时无装满数据的缓冲区供计算进程使用。
    • 这时，计算进程只能阻塞，直至输入进程又装满某个缓冲区，并调用Releasebuf过程将它释放时，才去唤醒计算进程。
    • 这种情况被称为系统受I/O限制

缓冲池

• 缓冲区都是专用缓冲，是为完成某个任务专门开辟的。
• 因此，任务较多时，开销会很大，而且利用率低。
• 可以设立公用缓冲池，池中设立多个缓冲区，为多个进程共享，以提高利用率。

缓冲区、缓冲池的区别

• 缓冲区：单个内存区域或一组内存区域组成的链表
• 缓冲池：包含一个管理的数据结构、一组操作函数的管理机制，用于管理多个缓冲区

磁盘存储器的管理

​ 目前几乎所有的机械式硬盘都以“温彻斯特”技术为基本原理

磁盘的组织和格式

• 磁盘包括一或多个物理盘片。

• 每个盘片分一个或两个存储面。

• 每个面被组织成若干同心环，这种环称为磁道(track)，磁道之间留有间隙(gap)。为使处理简单，磁道上可存储的字节数目是相同的。

• 磁道又被逻辑上划分成若干扇区(sector) 。扇区之间保留一定的间隙。

• 一个扇区称为一个盘块(或数据块)

  磁盘上存储的数据块数目是由扇区数、磁道数以及磁盘面数所决定的

  （为充分利用磁盘外面磁道的存储能力，现代磁盘不再把内外磁道划分为相同数目的扇区，而是利用外层磁道容量较大的特点，将盘面划分成若干环带，同一环带内的所有磁道具有相同的扇区数。显然，外层环带的磁道拥有更多的扇区）

【磁盘调度算法】

• 先来先服务(FCFS)

• 最短寻道时间优先(SSTF)算法

• 扫描(SCAN)算法

• 循环扫描(CSCAN)算法

七、文件管理

数据组

• 数据项
• 记录
• 文件

文件

• 定义：由创建者所定义的，具有文件名的一组相关元素的集合

• 分类

  • 有结构文件（记录式文件）：数据结构、数据库
  • 无结构文件（流式文件）：源程序、可执行文件、库函数

• 类型

  • 按用途分类
    • 系统文件
    • 用户文件
    • 库文件
  • 按文件中数据的形式分类
    • 源文件
    • 目标文件
    • 可执行文件
  • 按存取控制属性分类
    • 只执行文件
    • 只读文件
    • 读写文件

  某些系统，如UNIX等，把I/O设备设为特殊文件

• 文件操作

  ①创建文件

  ②删除文件

  ③读文件

  ④写文件

  ⑤截断文件

  ⑥设置文件的读/写位置

  ⑦文件的“打开”和“关闭”操作

索引文件

• 目的：使变长记录文件可以直接存取

• 存在的问题：存储量比较大，每个记录都要建索引

文件目录

• 定义：是一种数据结构，用于标识系统中的文件及其物理地址，供检索文件时使用
• 要求：
  • 实现按名存取，只提供文件名，便可快速找到文件在外存上的位置
  • 提高对目录的检索速度
  • 文件共享
  • 允许文件重名，允许不同用户对不同文件使用相同的文件名

文件目录形式

• 单级文件目录
  • 含义：系统中仅一张目录表，每个文件一个目录项
  • 优点：简单，能实现目录管理的基本功能—按名存取
  • 缺点
    • 查找速度慢：特别是大文件系统
    • 不允许重名
    • 不便于实现文件共享：不同用户不能用不同名字访问同一个文件，不灵活
• 两级文件目录
  • 含义：为每个用户再建立一个单独的用户文件目录 (UFD)
  • 优点
    • 提高了检索目录的速度
    • 不同用户目录中，可以使用相同的文件名
    • 不同用户还可使用不同的文件名来访问系统中的同一个共享文件