操作系统笔记

[TOC]

概述

基本概念

  • 操作系统的定义：
    操作系统是控制、管理、分配、调度计算机硬件与软件资源与工作，为用户和其他软件提供接口与环境的程序集合。操作系统是最基本的系统软件。
  • 操作系统的基本特征：
    • 并发：
      并发是指两个或多个事件在同一时间间隔发生。在
      • 操作系统的并发性是指计算机系统当中同时存在多个运行当中的程序，os具有处理和调试多个程序同时执行的能力。
      • 引入进程的目的是为了使程序能够并发的执行。

        注意并发与并行的区别：

        • 并发：把一段时间切割成很多片，每一小片有且只有一个程序在占用。很多的程序占有时间片，分时交替执行。从宏观上看好像很多程序在在同时执行，但是从微观上看，一个时刻只有一个程序在执行。
        • 并行：是真正的同时执行，在同一时刻能够进行多个程序的工作。
        • 并发是通过操作系统分时实现的，是一种软件层面上的实现；而并行需要硬件的支持，如多处理器。
    • 共享：
      共享是指系统当中的资源可以给多个 并发进行 的进程共同使用。分为两类：
      • 互斥共享：
        只有在进程A访问并释放后，才允许另外一个进程B访问。即在 一段时间 内只允许一个进程访问。这种资源叫做 临界资源， 如打印机。
      • 同时访问：
        从宏观上看，在 一段时间 内可以允许有多个进程同时访问。不过从微观上看，不同进程还是轮流交替访问的。比如磁盘设备。

        并发和共享是os当中 最基本 的两个特征，两者互相依赖，互为存在条件。

    • 虚拟：
      虚拟是指把物理上的实体变成逻辑上的对应物，有以下应用：
    • 异步：
      多个程序可以并发执行，但是由于资源有限（资源竞争），进行的执行以不可预知的速度向前推进，这就是进程的异步性。
      异步性可能会导致程序产生一些与时间有关的错误，如data race。
  • 操作系统作为计算机系统资源管理者的功能：
    • 处理器管理（进程管理）
    • 存储器管理（内存管理）
    • 文件管理
    • IO设备管理
  • 操作系统为用户与计算机硬件之间提供接口：
    • 命令接口：
      • 联机命令接口：
        用户说一句话，os做一件事，并反馈，强调交互性。
      • 命令接口：
        用户把os要做的写在清单上，os按照清单执行，用户不能直接干预。
    • 程序接口：
      程序接口由系统调用（aka广义指令）组成。用户程序可以通过os来使用外设、申请分配和回收内存等等。包括图形用户界面（GUI）也是通过程序接口实现的。

OS的发展与分类

  1. 手工操作阶段（无OS）：
    • 由用户完成程序的装入、运行、结果输出等
  2. 批处理阶段（OS出现）：
    批处理系统是实现作业自动控制而无须人工干预的系统。
    • 单道批处理系统：
      系统对作业（程序）的处理是成批进行的，但是在内存当中始终只有一道作业。
      主要特征有：
      • 自动性：
        磁带上的一批作业（程序）能够自动逐个运行，无须人工干预。
      • 顺序性：
        磁带上的各个作业按顺序进入内存，作业按照队列执行。
      • 单道性：
        内存当中只有一道程序在运行。
    • 多道批处理系统：
      允许多个程序同时进入内存并允许他们在CPU当中交替运行，实现对硬件软件资源的共享。
      主要特征有：
      • 多道
      • 宏观上并行
      • 微观上串行
  3. 分时操作系统
    多道批处理系统无法提供人工干预，而分时os使用时间片轮转，实现了人机交互。
    主要特征有：
    • 同时性（多路性）：
      允许多个终端用户同时使用一台计算机。
    • 交互性
    • 独立性：
      各个用户独立操作，互不干扰
    • 及时性：
      用户请求能在很短时间内得到响应。
  4. 实时操作系统：
    相比于分时系统，实时操作系统可以在接受外部信号之后及时处理。引入了 优先级和可抢占。
  5. 网络os和分布式os
  6. 个人os：如Windows, Mac OS, Linux, Android, etc.

OS运行环境

内核态与用户态

在计算机系统当中，通常CPU可以执行两种不同性质的程序：

  • OS内核程序
  • 用户自编程序（应用程序）
    前者是后者的管理者

内核程序可以执行一些特权指令，而应用程序不行。如IO指令、中断指令、内存保护相关指令等。

基于以上，将CPU的状态划分为 用户态 和 内核态 。

OS的内核构成：

  • 与硬件相关的模块：如 时钟管理、中断处理、设备驱动。
    • 时钟管理：
      • 计时
      • 时钟中断，实现进程的切换（如时间片轮转调度）
    • 中断处理：
      如键鼠输入、进程管理、系统调用、设备驱动、文件访问。
      中断机制当中只有一小部分属于内核，它们负责保护和恢复中断现场的信息，然后转移到相关的处理程序。
    • 原语：逆天的名字，aka Atomic Operation 原子性操作
      底层的一些可以被调用的公用小程序
      • 处于OS的最底层，是最接近硬件的部分。
      • 具有原子性，不可被中断。

        定义原语可以直接关闭中断，完成后再打开中断。
        系统当中的设备驱动、CPU切换、进程通信当中的一些操作都可以定义成原语，成为内核的一部分。

  • 与运行有关的程序，如 进程管理、内存管理、设备管理。
    • 系统控制的数据结构与处理：
      如PCB，TCB，消息队列、内存分配表等等。对其的定义与操作，也是在内核态中完成的。
      常见的功能有：
      • 进程管理
      • 存储器管理
      • 设备管理

内核态指令实际上包括了系统调用类指令和一些针对时钟、中断和原语的操作指令。

中断与异常

也可以叫做中断（外中断）与异常（内中断）。

  • 系统不允许用户程序实现内核态的功能，但是有时候他们又必须使用，就得通过中断或者异常实现。
  • 中断，是指来自 CPU执行指令以外 的事件的发生，如外设请求和人为干预。
  • 异常，除了内中断，也叫陷入（trap），来自 CPU执行指令以内 的事件，如地址越界、算术溢出、缺页中断、专门的陷入指令等等。异常不能被屏蔽，一旦出现要立刻处理。

中断处理的过程：参考计组。

  • 需要注意的是，关中断、保存断点、中断服务程序寻址是通过硬件自动完成的。

状态的转换

用户态与内核态的转换可能发生在以下的情况：

  • 用户要求os服务，即系统调用
  • 发生了一次中断
  • 用户产生的错误状态
  • 用户程序企图执行特权指令
  • trap指令（aka 访管指令）是由用户态执行的，用以陷入内核态，因此trap指令不是特权指令。
  • 从内核态转换回用户态，如中断返回指令，是特权指令。
    从用户态进入内核态，除了CPU状态之外，所使用的堆栈也需要从用户堆栈转移到内核堆栈。

一个经典的系统调用执行过程，如上图所示。

  1. 用户进程传递syscall的参数
  2. 在用户态执行trap指令，将用户态转换为内核态
  3. CPU执行内核态服务程序
  4. 返回用户态

OS结构

在os的结构实现上，有宏内核和微内核两种实现方法。

  • 宏内核：
    • os的主要功能模块，作为一个紧密联系的整体运行在内核态。从而提供 高性能 的系统服务。
    • 各个管理模块之间可能 共享信息，所以节省了通信的时候，具有性能优势。
    • 缺点是内核代码难以维护。
  • 微内核：
    出于宏内核的不易扩展、难以维护的考虑，提出了微内核的体系结构。
    • 将内核当中 最基本的功能（如进程管理） 保留在内核，将其他功能移到用户态，降低了内核的设计复杂性。
    • 这些其他的子模块划分成若干层的服务程序，依靠微内核进行通知。
    • 微内核保证了os的可靠性。
    • 缺点是性能低，因为执行系统功能需要频繁在内核态和用户态之间切换，开销大。

可以参考下面的图：

进程与线程

进程调度

进程调度有两种：

  • 非抢占式调度：指进程由运行->等待或者运行->终止的调度。也就是说，运行的进程除非自己要求，否则不会被打断。
  • 抢占式调度：指进程由运行->就绪或者等待->就绪。对于后者来说，如果等待进程的优先级很高，那么进程等待结束后，进入就绪状态，会以高优点级挤走正在运行的进程。

进程调度的基本准则

  • CPU利用率：
    CPU运行时间的比例，应当尽可能使得CPU保持忙碌。
  • 系统吞吐量：
    单位时间内完成作业的数量。

    系统吞吐量大 $\Leftrightarrow$ CPU使用率高 + 上下文切换代价小

  • 周转时间：
    指作业从 作业提交 到 作业完成 所用的时间。
  • 等待时间：
    指作业 处于等待状态的时间之和。
  • 响应时间：
  • 指作业从 作业提交 到 系统首次产生响应 所用的时间。

先来先服务调度算法FCFS

FCFS是最简单的一个调度算法，它是 非抢占式 的。

每次从就绪队列当中选出 最先 进入队列的进程，然后一直运行，直到退出或阻塞。

问题在于， 当一个长作业先运行了，后面的短作业就会等待很长。不利于短作业。

最短作业优先调度算法SJF

SJF也很简单，它是 非抢占式 的，会优先选择 运行时间最短 的进程来进行。有利于提高系统的吞吐量。

SJF对长作业不利，因为它可能会一直排队，造成响应时间很长。

最短剩余作业优先调度SRJF

SJF的 可抢占 版本。新来的作业不必等当前任务结束，只要其时间比当前任务的剩余时间更短，就可以打断当前任务。

高响应比优先调度算法HRRN

FCFS和SJF的问题在于没有办法权衡短作业和长作业。因此提出了 高响应比优先算法。

每次调度时，选择 响应比优先级 最高的进程投入运行。计算公式如下：

$$
优先权 = \frac{等待时间+要求服务时间}{要求服务时间}=1+\frac{等待时间}{要求服务时间}
$$

可以看到，要求服务时间越短，响应比越高，因此短作业会优先执行。

而对于长作业，随着其等待时间的增加，响应比也会上升，从而获得了运行的机会，解决了SJF的问题。

时间片轮询调度（Round-Robin RR）

RR主要适用于 分时系统，抢占式调度。

系统所有就绪进程形成一个队列，依据一个FCFS原则，一次分配一个时间片（如20ms）。

使用一个时间片之后，即使进程还没完成运行，也必须释放CPU，给下一个就绪进程。

时间片应当大小适中，如果太大，会退化为FCFS，如果太小，会造成进程上下文切换开销过大。

由以下因素决定：

  • 系统响应时间
  • 进程数量
  • 系统的处理能力

最高优先级调度算法HPF

从就绪队列中选择最高优先级的进程进行运行。可以是抢占的也可以不是。

进程的优先级有：

  • 静态优先级：在进程创建的时候就决定的。如系统进程比用户进程优先。
  • 动态优先级：在运行过程当中动态变化。比如上面的响应比作为优先级。

可以看到，上面的HRRN就是HPF的一种。

多级反馈队列调度算法MFQ

MFQ是RR和HPF算法的综合和发展。
MFQ

  • 多级：表示有多个队列，每个队列都有一个优先级，从高到低。优先级高的，时间片短。
  • 反馈：如果有新的进程加入优先级高的队列，会停止当前进程，去优先级高的队列运行。所以，它是 抢占式 的。

它的工作过程是这样的：

  • 新进程会放入第1级队列的末尾，按照FCFS（optional）进行调度，分配时间片S1。
  • 如果进程在S1结束后还是没有执行完，会进入2级队列，等待分配。
  • 只有在第1级队列为空时，才会运行第2级队列。

可以看到，对于MFQ，短作业可以在第1级队列很快处理完，而对于长作业，虽然在2、3级队列当中等待的时间更长，但是他们获得的运行时间也变长的。所以，MFQ 兼顾了长短作业，同时有较好的响应时间。

注意，MFQ可能存在 饥饿，也就是某个很长的任务长期得不到运行。

彩票算法Lottery

假设任务A有75张彩票，B有25张。调度器进行抽签：

内存管理

I/O与存储

文件系统

操作系统
操作系统笔记
https://max-wzm.github.io/2023/02/10/course/os/
作者
Max Wang
发布于
2023年2月10日
许可协议