以下为个人学习笔记和习题整理
书籍:操作系统概念 (Opertating System Concepts)、操作系统导论 (OSTEP)
https://www.bilibili.com/video/BV1HN41197Ko

# 概述

An operating system is software that manages a computer’s hardware . It also provides a basis for application programs and acts as an intermediary between the computer user and the computer hardware. An amazing aspect of operating systems is how they vary in accomplishing these tasks in a wide variety of computing environments.

  • 操作系统管理计算机硬件软件。它还为 应用程序 的运行提供基础,并在 计算机用户计算机硬件 之间充当 中介
  • 操作系统的一个令人惊异的方面是,它们是如何在 各种各样的计算环境 中以不同的方式完成这些任务的。
  1. 为了探索 操作系统现代计算环境 中的角色,首先理解 计算机硬件 的组织和架构是很重要的。

    This includes the CPU , memory , and I/O devices , as well as storage . A fundamental responsibility of an operating system is to allocate these resources to programs.

    • 计算机硬件包括 CPU内存I/O 设备 以及 存储。操作系统的一个基本职责是将这些 资源分配 给程序。
  2. 由于操作系统是即庞大又复杂的,它必须 一部分一部分地 (piece by piece) 被构造。

    Each of these pieces should be a well-delineated portion of the system, with carefully defined inputs , outputs , and functions .

    • 每一部分都应该是系统中 明确定义的一部分,具有仔细定义的 输入输出功能

# 操作系统的功能

我们从 操作系统 在整个 计算机系统 中的角色开始讨论。计算机系统可以大致分为四个部分: 硬件操作系统应用程序用户 ,如图所示。

Untitled_0

  • 硬件 :CPU、内存和 I/O 设备等,为系统提供 基本的计算资源
  • 应用程序 :如文字处理程序、电子表格程序、编译器和网页浏览器,定义了这些资源用来 解决用户的计算问题 的方式。
  • 操作系统控制硬件 ,并为不同的用户 协调各种应用程序 对硬件的使用。

We can also view a computer system as consisting of hardware , software , and data . The operating system provides the means for proper use of these resources in the operation of the computer system. An operating system is similar to a government . Like a government, it performs no useful function by itself. It simply provides an environment within which other programs can do useful work.

  • 我们也可以把 计算机系统 看作是由 硬件软件数据 组成的。操作系统 提供了在计算机系统的运行中 恰当使用这些资源 的方法。

  • 操作系统类似于政府。就像政府一样,它自己不能发挥任何有用的功能。它只是提供了一个环境,其他程序可以在其中完成有用的工作。

# 操作系统的定义

  1. 一般来说,我们 没有 一个关于操作系统的 完全准确的定义。操作系统之所以存在,是因为它们 提供了一种合理的方法 来解决 创建可用的计算系统 的问题。

    • 计算机系统 的基本目标是 执行程序 并使解决用户问题变得更容易, 计算机硬件 就是为了这个目标而构建的。
    • 由于光有 硬件本身 并不是特别容易使用,所以开发了 应用程序
    • 这些程序需要某些 共同的操作 ,例如控制 I/O 设备。这些控制和分配资源的共同的功能被整合到一个软件模块 —— 操作系统 当中。
  2. 另外,对于究竟什么属于 操作系统的一部分,我们也 没有 一个普遍接受的定义。一个比较公认的定义,也是本书所采用的定义:

    The operating system is the one program running at all times on the computer —— usually called the kernel .

    • 操作系统 是在计算机上 始终运行的程序 —— 通常称为 内核
    1. 除了内核之外,还有两种其他类型的程序:

      • 系统程序 (system programs):与操作系统相关联,但不是内核的必要组成部分。
      • 应用程序 (application programs):包括所有与系统操作无关的程序。
    2. 然而,如果我们着眼于如今的 移动设备的操作系统,我们会再次看到,构成操作系统的功能的数量正在增加。移动设备的操作系统通常不仅包括一个核心的内核,还包括一个 中间件 (middleware),它是为 应用程序开发人员 提供额外服务的一组 软件框架

    In summary, for our purposes, the operating system includes the always-running kernel , middleware frameworks that ease application development and provide features, and system programs that aid in managing the system while it is running.

    • 总之,就我们的目的而言, 操作系统 包括始终运行的 内核、简化应用程序开发并提供功能的 中间件框架,以及在系统运行时帮助管理系统的 系统程序

# 计算机系统的组成

现代的通用 计算机系统一个或多个 CPU 和许多 设备控制器 组成,它们之间通过 公用总线 相连,该总线提供了这些组件和共享的 内存 之间的访问,如图所示。

Untitled_1

  1. 每个 设备控制器 (device controllers) 负责 一类特定的设备 (例如,磁盘驱动器、音频设备或图形显示器)。设备控制器维护一些 本地缓冲区存储器 (local buffer storage) 和一组 专用寄存器 ,并负责在其 控制的外围设备 与本地缓冲区存储器之间移动数据。

    Depending on the controller, more than one device may be attached. For instance, one system USB port can connect to a USB hub , to which several devices can connect.

    • 根据控制器的不同,一个控制器可以 连接多个设备。例如,一个 系统 USB 接口 可以连接到一个 USB 集线器 上,该集线器可以连接多个设备。
  2. 通常, 操作系统 对于每个设备控制器都有一个 设备驱动程序 (device driver),该程序理解设备控制器,并为操作系统的其余部分提供设备的 统一接口 (uniform interface)

    The CPU and the device controllers can execute in parallel , competing for memory cycles . To ensure orderly access to the shared memory, a memory controller synchronizes access to the memory.

    • CPU设备控制器 可以 并行执行,竞争 内存周期。为了确保对共享内存的有序访问,需要 内存控制器 来同步对内存的访问。

# 中断

在接下来的小节中,我们将描述这样的一个系统是如何运行的一些基础知识,重点关注系统的三个方面: 中断存储结构I/O 结构

An introduction of interrupts

让我们首先考虑一个典型的计算机操作:一个执行 I/O 操作 的程序。

  • To start an I/O operation, the device driver loads the appropriate registers in the device controller .

    • 为了启动 I/O 操作,设备驱动程序 加载 设备控制器相应的寄存器
  • The device controller , in turn, examines the contents of these registers to determine what action to take (such as “read a character from the keyboard”). The controller starts the transfer of data from the device to its local buffer . Once the transfer of data is complete, the device controller informs the device driver that it has finished its operation.

    • 设备控制器 进而检查这些 寄存器的内容,以决定采取什么操作(例如,从键盘上读取一个字符)。控制器开始将 数据从设备传输 到它的 本地缓冲区

    • 一旦数据传输完成,设备控制器 通知设备驱动程序 它已经完成了它的操作。

  • The device driver then gives control to other parts of the operating system , possibly returning the data or a pointer to the data if the operation was a read. For other operations, the device driver returns status information such as “write completed successfully” or “device busy”.

    • 然后,设备驱动程序 将控制权交给 操作系统 的其他部分,如果操作是读操作,则可能返回数据或指向数据的指针。对于其他操作,设备驱动程序返回状态信息,如 “写操作成功完成” 或 “设备繁忙”。

但是设备控制器是如何 通知设备驱动程序 它已经完成了它的操作的呢?这是通过一个 中断 (interrupt) 完成的。

# 概览

  1. 硬件可以在 任何时候 通过向 CPU 发送信号 来触发中断,通常是通过 系统总线 的方式。(计算机系统中可能有许多总线,但系统总线是 主要部件 之间的主要通信路径。)

    中断也用于许多其他目的,并且是 操作系统硬件 之间如何交互的关键部分。

  2. 当 CPU 被中断时,它 停止正在做的事情 ,并立即将执行跳转到一个 固定的位置 。固定位置通常包含该中断的 服务例程 (service routine) 所在的 起始地址 。该中断服务例程进而开始执行。完成后,CPU 恢复被中断的计算。该操作的时间线,如图所示,IO 设备与 CPU 并行执行。

    Untitled_2

  3. 中断是 计算机体系结构 (computer architecture) 的重要组成部分。每种计算机设计都有自己的中断机制,但有几个功能是通用的。

    1. 中断必须将 控制转移 到适当的 中断服务例程 (interrupt service routine)

      管理这种转移的直接方法是调用一个 通用例程 (generic routine) 来检查中断信息,这个例程进而会调用特定于中断的 处理程序(handler)

      但是,中断必须 快速处理 ,因为它们发生得 非常频繁 。一个指向若干个 中断例程 (interrupt routines)指针表 可以代替通用例程来提供必要的速度。

      • 由此,中断例程通过这张表间接调用,而不需要中间例程。

      通常,指针表存储在 低内存 (low memory) 中 (前 100 左右的位置)。这些位置保存着各种设备的 中断服务例程的地址

      这个地址数组,或者称为 中断向量 (interrupt vector) ,由一个 唯一的数字 作为索引,这个数字携带于 中断请求 中,用来提供 触发中断的设备 的中断服务例程的地址。

      Windows 和 UNIX 等不同的操作系统都以这种方式调度中断。

    2. 中断体系结构还必须保存任何被中断的计算的 状态信息 ,以便在为中断执行服务之后恢复这些信息。

      如果中断例程需要修改 处理器状态 (例如,通过修改寄存器的值),它必须显式地保存当前状态,然后在返回之前恢复该状态。

      • 在中断被服务后,保存的 返回地址 被加载到 程序计数器 (program counter) 中,中断的计算就像中断没有发生过一样恢复执行。

# 中断的实现

# 基本的中断机制

CPU 硬件有一条叫做 中断请求线 (interrupt-request line) 的线,CPU 在 执行每条指令后 都会感知到这条线。

  1. 当 CPU 检测到一个控制器在中断请求线上 断言 (assert) 了一个信号时,它读取 中断号 (interrupt number) ,并使用该中断号作为中断向量的索引跳转到 中断处理程序例程 (interrupt–handler routine) ,然后在与该索引关联的地址处开始执行。

  2. 中断处理程序 保存 它在运行过程中将要改变的任何 状态 ,确定中断的原因,执行必要的处理,执行状态恢复,并执行 return_from_interrupt 指令,使 CPU 返回到中断之前的执行状态。

    Untitled_3

    我们说 设备控制器 通过在中断请求线上断言一个信号来 引发 (raises) 中断,CPU 捕获 (catches) 这个中断并将其 调度 (dispatches)中断处理程序 (interrupt handler) ,而中断处理程序通过服务设备来 清除 (clears) 这个中断。图 1.4 总结了中断驱动的 I/O 循环。

# 现代操作系统的中断机制

刚才描述的基本中断机制使 CPU 能够响应 异步事件 (asynchronous event) ,比如当设备控制器 准备就绪 (ready for service) 时。

  • 然而,在现代操作系统中,我们需要更复杂的中断处理特性:

    1. 我们需要在关键处理期间 延迟中断处理 的能力。
    2. 我们需要一种 高效的方法 来为设备调度合适的中断处理程序。
    3. 我们需要 多级中断 (multilevel interrupts) ,以便操作系统能够区分 高优先级低优先级 的中断,并能够以适当的 紧急程度 进行响应。

    在现代计算机硬件中,这三个特性是由 CPU中断控制器硬件 (interrupt-controller hardware) 提供的。

  1. 大多数 CPU 都有 两条 中断请求线:

    • 一条中断线是 不可屏蔽中断 (nonmaskable interrupt) ,它是为 不可恢复的内存错误 等事件保留的。
    • 第二条中断线是 可屏蔽的 (maskable) ,CPU 可以在执行不能被中断的关键指令序列之前 关闭 (turned off) 它。

      可屏蔽中断设备控制器 用来请求服务。

  2. 回想一下, 向量化 (vectored) 的中断机制的目的是减少 单个的中断处理程序 去搜索所有可能的中断源以确定哪个中断源需要服务的需要。(亦即,不使用通用例程,而使用中断向量直接索引中断处理程序。)

    然而,实际上,计算机拥有的设备 (从而, 中断处理程序 ) 比它们在中断向量中的 地址元素 (address elements) 要多。

    解决这个问题的一种常见方法是使用 中断链接 (interrupt chaining) ,其中 中断向量 中的每个元素都指向一个中断处理程序的 列表 (list) 的头。当一个中断被引发时,相应列表上的处理程序将被 逐个调用 ,直到找到一个可以服务该请求的处理程序为止。

    这种结构是一个 巨大的中断表 的开销和 单个的中断处理程序 调度中断 (逐个顺序查找) 的低效率之间的 折衷

    • 亦即,中断表的开销增加了 (列表索引 + 中断处理程序地址本身),而查找中断处理程序的效率提高了,典型的空间换时间。
    Intel 处理器的中断向量设计

    Untitled_4

    • 从 0 到 31 的事件是 不可屏蔽 的,用于发出各种 错误条件 的信号。
    • 从 32 到 255 的事件是 可屏蔽 的,用于 设备产生的中断 等目的。
  3. 中断机制还实现了一个 中断优先级级别 (interrupt priority levels) 的系统。

    这些级别使 CPU 可以 延迟低优先级中断 的处理,而不用屏蔽所有的中断,并使 高优先级中断 可以 抢占 低优先级中断的执行。

总之,中断在整个现代操作系统中都被使用,以处理 异步事件 。(至于其他目的,我们将在本文中讨论)

  • 设备控制器硬件故障 (hardware faults) 会引发中断。
  • 为了使 最紧急的工作 先完成,现代计算机采用了 中断优先级 系统。
  • 由于中断在对时间敏感的处理中被大量使用,因此需要 高效的中断处理 来获得良好的系统性能。

# 存储结构

Wikipedia: Computer memory

In computing, memory is a device or system that is used to store information for immediate use in a computer or related computer hardware and digital electronic devices. The term memory is often synonymous with the term primary storage or main memory . An archaic synonym for memory is store.

  • Computer memory operates at a high speed compared to storage that is slower but offers higher capacities. If needed, contents of the computer memory can be transferred to storage; a common way of doing this is through a memory management technique called virtual memory .

  • Modern memory is implemented as semiconductor memory , where data is stored within memory cells built from MOS transistors and other components on an integrated circuit. There are two main kinds of semiconductor memory, volatile and non-volatile.

    • Examples of non-volatile memory are flash memory and ROM, PROM, EPROM and EEPROM memory.
    • Examples of volatile memory are dynamic random-access memory (DRAM) used for primary storage, and static random-access memory (SRAM) used for CPU cache.
  • Most semiconductor memory is organized into memory cells each storing one bit (0 or 1). Flash memory organization includes both one bit per memory cell and multi-level cell capable of storing multiple bits per cell. The memory cells are grouped into words of fixed word length, for example, 1, 2, 4, 8, 16, 32, 64 or 128 bits. Each word can be accessed by a binary address of N bits , making it possible to store 2N2^N words in the memory.

# 主存

CPU 只能从 内存 (memory) 中加载 指令 (instructions) ,所以任何 程序 (programs) 必须先加载到内存中才能运行。

  1. 通用计算机的大部分程序都是运行在 可重写的存储器 (rewritable memory) ,称为 主存储器 (main memory) 中的。

    主存也称为 随机存取存储器 (random-access memory, RAM) ,通常采用 半导体技术 实现,称为 动态随机存取存储器 (DRAM)

    维基百科:动态随机存取存储器

    动态随机存取存储器(Dynamic Random Access Memory,DRAM)是一种 半导体存储器 ,主要的作用原理是利用 电容内存储电荷的多寡 来代表一个二进制比特(bit)是 1 还是 0。由于在现实中晶体管会有漏电电流的现象,导致电容上所存储的电荷数量并不足以正确的判别资料,而导致资料毁损。因此对于 DRAM 来说, 周期性地充电 是一个不可避免的条件。由于这种 需要定时刷新 的特性,因此被称为 “动态” 存储器。相对来说,静态存储器(SRAM)只要存入资料后,纵使不刷新也不会丢失记忆。

    • 与 SRAM 相比,DRAM 的优势在于结构简单 —— 每一个比特的资料都只需一个电容跟一个晶体管来处理,相比之下在 SRAM 上一个比特通常需要六个晶体管。正因这缘故,DRAM 拥有非常高的密度,单位体积的容量较高因此 成本较低 。但相反的,DRAM 也有 访问速度较慢 ,耗电量较大的缺点。

    • 与大部分的随机存取存储器(RAM)一样,由于存在 DRAM 中的资料会在电力切断以后很快消失,因此它属于一种易失性存储器设备。

  2. 计算机也使用 其他形式的存储器 。例如,计算机上电后运行的第一个程序是 引导程序 (bootstrap program) ,它运行后会加载 操作系统

    1. 由于 RAM 是易失性的,当电源关闭或其他情况下将丢失它的内容,因此我们不能信任它来保存引导程序。

    2. 取而代之的,计算机使用 电可擦可编程只读存储器 (EEPROM) 以及其他形式的 固件 (firmware) ,这种不经常被写入的、非易失性的存储,来保存引导程序。

      EEPROM 存储的内容可以被更改,但 不能频繁更改 。此外,它的速度较慢,因此它包含的大部分是 不经常使用的 静态程序和数据。

      • 例如,iPhone 使用 EEPROM 来存储设备的序列号和硬件信息。

    所有形式的内存都提供一个 字节数组 (an array of bytes) ,每个字节都有自己的 地址

    • 与内存的交互是通过对特定的 内存地址 (memory addresses) ,执行一系列的 load 指令store 指令 来实现的。
      • load 指令:将 一个字节 (byte)一个字 (word)主存 移动到 CPU 内部的寄存器 ,而
      • store 指令:将一个 寄存器 中的内容移动到 主存
    • 除了显式的 load 和 store 指令,CPU 为了执行会 自动地 从主存中加载指令,该指令的位置从 程序计数器 中获得。
  3. 一个典型的 指令-执行周期 (instruction-execution cycle) ,在具有 冯诺伊曼体系结构 的系统上执行时,

    1. 首先从内存中 取出 (fetch) 一条指令,并将该指令存储在 指令寄存器 (instruction register) 中。
    2. 该指令随后被 解码 (decode) ,并可能导致 操作数 (operands) 从内存中被取出并存储在某个内部 寄存器 中。
    3. 在指令完成对操作数的 执行 (execute) 后,结果可能会被存储回内存中。

    注意到内存单元只看到一个 内存地址流 (a stream of memory addresses) ,它不知道这些地址是如何生成的(通过指令计数器、索引、间接、字面值地址或其他方式),也不知道它们的用途(是指令,还是数据)。

    • 因此,我们可以 忽略 程序是 如何生成 内存地址的,而只对运行的程序生成的 内存地址序列 感兴趣。

# 辅存

  1. 理想情况下,我们希望程序和数据永久地驻留在主存中。这种安排在大多数系统上通常是不可能的,原因有二:

    • 主存通常太小,无法永久存储所有需要的程序和数据。
    • 如前所述,主存储器是易失性的,它在电源关闭或其他丢失时丢失其内容。

    因此,大多数计算机系统都提供 辅助存储器 (secondary storage) 作为主存储器的扩展。对辅存的主要需求是它能够永久地保存大量的数据。

    最常见的辅助存储设备是 硬盘驱动器 (hard-disk drives, HDDs)非易失性存储器 (nonvolatile memory, NVM) 设备 ,它们为程序和数据提供存储。

  2. 大多数程序(系统程序和应用程序),在 加载到内存之前 都存储在辅助存储器中,因而许多程序使用辅助存储器作为它们处理的 源 (source)目的地 (destination) 。同时,辅助存储器也比主存储器 慢得多 。因此,正如我们在第 11 章中讨论的那样,对辅助存储器的适当管理对于计算机系统是至关重要的。

# 存储器层次结构

然而,从更广泛的意义上说,我们所描述的存储结构(由 寄存器主存储器辅助存储器 组成),只是许多可能的存储系统设计中的一种。

  • 其他可能的组件包括 高速缓存存储器 (cache memory) 、CD-ROM 或蓝光光盘、磁带等。
  • 那些足够慢、足够大、只用于特殊目的的存储设备(例如,存储其他设备上的材料的备份副本),被称为 三级存储 (tertiary storage)

每个存储系统都提供基本的 存储数据 的功能,并将该数据保存到以后被 检索 (retrieve) 为止。

  • 不同存储系统之间的主要区别在于 速度 (speed)大小 (size)易失性 (volatility)

Untitled_5

如图所示,各种各样的 存储系统 (storage systems) 可以根据 存储容量访问时间 组织成一个 层次结构

  1. 一般的规则是,大小和速度之间要有 权衡 ,越小的和越快的存储器 越靠近 CPU

    • 如图所示,除了速度和容量不同之外,各种存储系统要么是 易失性的 ,要么是 非易失性的

    • 图中最上面的四层存储器是用 半导体存储器 (semiconductor memory) 构成的,半导体存储器是由半导体电路组成的。

    • 第四级的 NVM (nonvolatile memory) 设备有几种变体,但通常都 比硬盘快

      NVM 设备最常见的形式是 闪存 (flash memory) ,它在智能手机和平板电脑等 移动设备 中很流行。

      • 闪存也越来越多地用于笔记本电脑、台式机和服务器的长期存储。
  2. 由于 存储 (storage) 在操作系统结构中扮演着重要的角色,我们将在本文中经常提到它。一般来说,我们会使用以下术语:

    1. 易失性存储器 (Volatile storage):将会被简称为 内存 (memory)
      如果需要强调特定类型的存储设备(例如,寄存器),我们将会显式地说明。

    2. 非易失性存储器 (Nonvolatile storage):在失电时保留其内容,它将被称为 NVS (★)

      我们在介绍 NVS 上花费的绝大多数时间,都是在 辅助存储 上。

      辅助存储可以分为两种不同的类型(正如存储器层次结构图中所示):

      • 机械式的 (Mechanical)。这种存储系统的几个例子是 磁盘驱动器 (HDDs) 、光盘、全息存储和磁带。

        如果我们需要强调特定类型的机械存储设备(例如,磁带),我们将会显式地说明。

      • 电子式的 (Electrical)。这种存储系统的几个例子是 闪存 (flash memory) 、FRAM、NRAM 和 固态磁盘 (solid-state disk, SSD)

        电存储器将被称为 NVM (nonvolatile memory) 。如果我们需要强调特定类型的电存储设备(例如,SSD),我们将会显式地说明。

      机械存储通常比电存储更大,每字节更便宜。相反,电存储通常比机械存储成本高,体积小,速度快。

  3. 一个完整的存储系统的设计,必须平衡刚才讨论的所有因素:它必须只使用 必要的 昂贵内存,同时提供 尽可能便宜 的非易失性存储。

    当两个组件之间的 访问时间 (access time)传输速率 (transfer rate) 存在较大差异时,可以安装 高速缓存 (cache) 来提高性能。

# I/O 结构

操作系统代码的 很大一部分 都用于 管理 I/O ,这既是因为它对系统的可靠性和性能很重要,也是因为设备有着不同的性质。

回想一下,在本节的开始,通用计算机系统由多个设备组成,所有这些设备都通过公共总线交换数据。第 1.2.1 节中描述的 中断驱动的 I/O 的形式适用于 移动少量的数据 ,但用于 NVS I/O 等 大量数据移动 时可能会产生 很高的开销

为了解决这个问题,使用了 直接内存访问 (direct memory access, DMA) :在为 I/O 设备设置了缓冲区、指针和计数器之后, 设备控制器 直接在 设备主存 之间传输将整个 数据块 ,而不需要 CPU 的干预。图 1.7 显示了计算机系统中所有组件的相互作用。

  • 每个块 只产生 一个中断 ,以告诉设备驱动程序操作已经完成,而不是像低速设备那样 每个字节 产生一个中断。
  • 当设备控制器执行这些操作时,CPU 可以完成其他工作。

Untitled_6

一些高端系统采用 交换 (switch) 而不是总线架构。在这些系统上,多个组件可以 并发地 与其他组件通信,而不是竞争共享总线的周期。在这种情况下,DMA 更为高效。

# 操作系统的执行