操作系统 精髓与设计原理 读书笔记

操作系统处于中间位置,它的一边是应用程序、实用程序和用户,另一边是计算机系统的硬件。


计算机系统概述

操作系统处于中间位置,它的一边是应用程序、实用程序和用户,另一边是计算机系统的硬件。为了理解操作系统的功能和涉及的设计问题,必须首先对计算机组织与系统结构有一定的认识。

基本构成

从最顶层看,一台计算机由处理器、存储器和输入/输出部件组成,每类部件有一个或多个模块。这些部件以某种方式互联,以实现计算机执行程序的主要功能。因此,计算机有 4 个主要结构化部件:

  • 处理器:控制计算机的操作,执行数据处理功能。当只有一个处理器时,它通常指中央处理单元(CPU)
  • 内存:存储数据和程序。此类存储器通常是易失性的,即当计算机关机时,存储器的内容会丢失。相反,当计算机关机时,磁盘存储器的内容不会丢失。内存通常也称为主存储器
  • 输入/输出模块:在计算机和外部环境之间移动数据。外部环境由各种外部设备组成,包括辅助存储器设备(如硬盘)、通信设备和终端
  • 系统总线:为处理器、内存和输入/输出模块间提供通信的设备

处理器的一种功能是和存储器交换数据。为此,它通常使用两个内部(对处理器而言)寄存器:存储器地址寄存器(Memory Address Register, MAR),存储器地址寄存器确定下一次读写的存储器地址;存储器缓冲寄存器(Memory Buffer Register, MBR),存储器缓冲寄存器存放要写入存储器的数据活着从存储器中读取的数据。同理,输出/输出地址寄存器(I/O Address Register)确定一个特定的输入/输出设备,输入/输出缓冲寄存器(I/O Buffer Register)用于在输入/输出模块和处理器间交换数据。

内存模块由一组单元组成,这些单元由顺序编号的地址定义。每个单元包含一个二进制数,可以解释为一个指令或数据。输入/输出模块在外部设备与处理器和存储器之间传送数据。输入/输出模块包含内存缓冲区,用于临时保存数据,直到它们被发送出去。

处理器寄存器

处理器包含一组寄存器,他们提供一定的存储能力,比内存访问速度快,但比内存的容量小。处理器中的寄存器有两个功能:

  • 用户可见寄存器:优先使用这些寄存器,可以减少机器语言或汇编语言的程序员堆内存的访问次数。对高级语言而言,由优化编译器负责决定哪些变量应该分配给寄存器,哪些变量应该分配给内存。一些高级语言(如 C)允许程序员建议编译器把哪些变量保存在寄存器中
  • 控制和状态寄存器:用以控制处理器的操作,且主要被具有特权的操作系统例程使用,以控制程序的执行

这两类寄存器并没有很明显的界限。

用户可见寄存器

用户可见寄存器可以通过由处理器执行的机器语言来引用,它一般对所有的程序都是可用的,包括应用程序和系统程序。通常可用的寄存器类型包括数据寄存器、地址寄存器和条件码寄存器。

数据寄存器:可以被程序员分配给各种函数。在某些情况下,它们实际上是通用的,可被执行数据操作的任何机器指令使用。但通常也有一些限制,例如堆浮点数运算使用专用的寄存器,而堆整数运算使用其他寄存器

地址寄存器:存放数据和指令的内存地址,活着存放用于计算完整地址或有效地址的部分地址。这些寄存器可以是通用的,或者可以用来以某一特定方式或模式寻址存储器。例如:

  • 变址寄存器(index register):变址寻址是一种最常用的寻址方式,它通过给一个基值加一个索引来获得有效地址
  • 段指针(segment pointer):对于分段寻址方式,存储器被划分成段,这些段由长度不等的字块组成,段由若干长度的字组成。一个存储器引用由一个特定段号和段内的偏移量组成。采用这种寻址方式,需要用一个寄存器保存段的基地址。可能存在多个这样的寄存器,例如一个用于操作系统(即当操作系统代码在处理器中执行时使用),一个用于当前正在执行的应用程序
  • 栈指针(stack pointer):如果堆用户可见的栈进行寻址,则应该有一个专门的寄存器指向栈顶。这样就可以使用不包含地址域的指令,如入栈(push)和出栈(pop)

对于有些处理器,过程调用将导致所有用户可见的寄存器自动保存,在调用返回时恢复保存的寄存器。由处理器执行的保存操作和恢复操作是调用指令和返回指令执行过程的一部分。这就允许每个过程独立地使用这些寄存器。而在其他的处理器上,程序员必须在过程调用前保存相应的用户可见寄存器,通过在程序中包含完成此项任务的指令来实现。因此,保存和恢复功能可以由硬件完成,也可以由软件完成,这完全取决于处理器的实现。

控制和状态寄存器

有多重处理器的寄存器用于控制处理器的操作。在大多数处理器上,大部分此类寄存器对用户不可见,其中一部分可被在控制态(或称为内核态)下执行的某些机器指令所访问。

下面的寄存器是指令执行所必需的:

  • 程序计数器(Program Counter, PC): 包含将取指令的地址。
  • 指令寄存器(Instruction Register, IR): 包含最近取的指令内容。

所有的处理器设计还包括一个或一组寄存器,通常称为程序状态字(Program Status Word, PSW),它包含状态信息。PSW 通常包含条件码和其他状态信息,如中断允许/禁止位和内核/用户态位。

条件码是处理器硬件为操作结果设置的位。机器指令通常允许通过隐式访问来读取这些位,但不能通过显式访问进行修改,这是因为它们是为指令执行结果的反馈而设计的。

在使用多重类型中断的处理器中,通常有一组中断寄存器,每个指向一个中断处理例程。

在设计控制和状态寄存器结构时需要考虑很多因素,一个关键问题是堆操作系统的支持。某些类型的控制信息堆操作系统来说有特殊的用途,如果处理器设计者对所用操作系统的功能有所了解,那么可以设计寄存器结构,对操作系统的特殊功能提供硬件支持,如存储器保护和用户程序之间的切换等。

另一个重要的设计决策是在寄存器和存储器间分配控制信息。通常把存储器最初的(最低的)几百个或几千个字用于控制目的,设计者必须决定在昂贵、高速的寄存器中放置多少控制信息,在相对便宜、低速的内存中放置多少控制信息。

指令的执行

处理器执行的程序是由一组保存在存储器中的指令组成的。按最简单的形式,指令处理包括两个步骤:处理器从存储器中一次读取一条指令,然后执行每条指令。程序执行是由不断重复的取指令和执行指令的过程组成的。指令执行可能涉及很多操作,这取决于指令自身。

一个单一的指令需要的处理称为一个指令周期,可使用简单的两个步骤来描述指令周期。这两个步骤分别称作取指阶段和执行阶段。仅当机器关机、发生某些未发现的错误或者遇到与停机相关的程序指令时,程序执行才会停止。

取指令和执行指令

在每个指令周期开始时,处理器从存储器中取一条指令。在典型的处理器中,程序计数器(Program Counter, PC)保存下一次要取的指令地址。除非有其他情况,否则处理器在每次取指令后总是递增 PC,使得它能够按顺序取得下一条指令(即位于下一个存储器地址的指令)。

取到的指令被放置在处理器的一个寄存器中,这个寄存器称作指令寄存器(Instruction Register, IR)。指令中包含确定处理器将要执行的操作的位,处理器解释指令并执行对应的操作。大体上,这些操作可以分为 4 类:

  • 处理器-存储器:数据可以从处理器传送到存储器,或者从存储器传送到处理器
  • 处理器-I/O:通过处理器和 I/O 模块间的数据传送,数据可以输出到外部设备,或者从外部设备输入数据
  • 数据处理:处理器可以执行很多与数据相关的算术操作或逻辑操作
  • 控制:某些指令可以改变执行顺序。

I/O 函数

I/O 模块(例如磁盘控制器)可以直接与处理器交换数据。正如处理器可以通过指定存储单元的而地址来启动对存储器的读和写一样,处理器也可以从 I/O 模块中读数据或向 I/O 模块中写数据。对于后一种情况,处理器需要指定被某一 I/O 模块控制的具体设备。

在某些情况下,允许 I/O 模块直接与内存发生数据交换,以减轻在完成 I/O 任务过程中的处理器负担。此时,处理器允许 I/O 模块具有从存储器中读或往存储器中写的特权,这样 I/O 模块与存储器之间的数据传送无需通过处理器完成。在这类传送过程中,I/O 模块对存储器发出读命令或写命令,从而免去了处理器负责数据交换的任务。这个操作称为直接内存存取(Direct Memory Access, DMA)

中断

利用中断功能,处理器可以在 I/O 操作的执行过程中执行其他指令。当外部设备做好服务的准备,也就是说,当它准备好从处理器接收更多的数据时,该外部设备的 I/O 模块给处理器发送一个中断请求信号。这时处理器会做出响应,暂停当前程序的处理,转去处理服务于特定 I/O 设备的程序,这个程序称作中断处理程序(interrupt handler)。注意,中断可以在主程序中的任何位置发生,而不是在一条指定的指令处。

从用户程序的角度看,中断打断了正常执行的序列。当中断处理完成后,再恢复执行。因此,用户程序并不需要为中断添加任何特殊的代码,处理器和操作系统负责挂起用户程序,然后在同一个地方恢复执行。

为了适应中断产生的情况,在指令周期中要增加一个中断阶段,如下图

在中断阶段中,处理器检查是否有中断发生,即检查是否出现中断信号。如果没有中断,处理器继续运行,并在取指周期取当前程序的下一条指令;如果有终端,处理器挂起当前程序的执行,并执行一个中断处理程序。这个中断处理程序通常是操作系统的一部分,它确定中断的性质,并执行所需要的操作。

很显然,在这个处理中有一定的开销,在中断处理程序中必须执行额外的指令以确定中断的性质,并决定采用适当的操作。然而,如果简单地等待 I/O 操作的完成将花费更多的时间,因此使用中断能够更有效地使用处理器。

中断处理

具体来说步骤如下

  1. 设备给处理器发出一个中断信号
  2. 处理器在响应中断前结束当前指令的执行
  3. 处理器对中断进行测定,确定存在未响应的中断,并给提交中断的设备发送确认信号,确认信号允许该设备取消它的中断信号
  4. 处理器需要为把控制权转移到中断程序中去做准备。首先,需要保存从中断点恢复当前程序所需要的信息,要求的最少信息包括程序状态字(PSW)和保存在程序计数器中的下一条要执行的指令地址,它们被压入系统控制栈中
  5. 处理器把响应此中断的中断处理程序入口地址装入程序计数器中。可以针对每类中断有一个中断处理程序,也可以针对每个设备和每类中断各有一个中断处理程序,处理器就必须决定调用哪一个,这个信息可能已经包含在最初的中断信号中,否则处理器必须给发中断的设备发送请求,以获取含有所需信息的响应。

一旦完成对程序计数器的装入,处理器则继续到下一个指令周期,该指令周期也是从取指开始。由于取指是由程序计数器的内容决定的,因此控制被转移到中断处理程序,该程序的执行引起以下的操作:

  1. 在这一点,与被中断程序相关的程序计数器和 PSW 被保存到系统栈中,此外,还有一些其他信息被当做正在执行程序的状态的一部分。特别需要保存处理器寄存器的内容,因为中断处理程序可能会用到这些寄存器,因此所有这些值和其他任何的状态信息都需要保存。
  2. 中断处理器程序现在可以开始处理中断,其中包括检查与 I/O 操作相关的状态信息或其他引起中断的事件,还可能包括给 I/O 设备发送附加命令或应答
  3. 当中断处理结束后,被保存的寄存器值从栈中释放并恢复到寄存器中
  4. 最后的操作是从栈中恢复 PSW 和程序计数器的值,其结果是下一条要执行的指令来自前面被中断的程序。

保存被中断程序的所有状态信息并在以后恢复这些信息,这是十分重要的,这是由于中断并不是程序调用的一个例程,它可以在任何时候发生,因此可以在用户程序执行过程中的任何一点上发生,它的发生是不可预测的。

多个中断

假设当正在处理一个中断时,可以发生一个或多个中断,这时候怎么办呢?处理多个中断有两种方法。第一种方法是当正在处理一个中断时,禁止再发生中断。禁止中断的意思是处理器将对任何新的中断请求信号不予理睬。如果在这期间发生了中断,通常中断保持挂起,当处理器再次允许中断时,再由处理器检查。因此,当用户正在执行并且有一个中断发生时,立即禁止中断;当中断处理程序完成后,在恢复用户程序之前再允许中断,并且由处理器检查是否还有中断发生。这个方法很简单,因为所有中断都严格按顺序处理。但是没有考虑到相对优先级和时间限制的要求。例如,当来自通信线的输入到达时,可能需要快速接收,以便为更多的输入让出空间。如果在第二批输入到达时第一批还没有处理完,就有可能由于 I/O 设备的缓冲区装满或溢出而丢失数据。

第二种方法是定义中断优先级,允许高优先级的中断打断低优先级的中断处理程序的运行

存储器的层次结构

计算机存储器的设计目标可以归纳成三个问题:多大的容量?多快的速度?多贵的价格?这三个问题之间的关系是:

  • 存取时间越快,每一个『位』的价格越高
  • 容量越大,每一个『位』的价格越低
  • 容量越大,存取速度越慢

有没有办法既保证容量大,又保证存取速度快,还不贵呢?解法是不依赖与单一的存储组件或技术,而是使用存储器的层次结构,从高层到低层看,趋势是这样的:

  • 每一个『位』的价格递减
  • 容量递增
  • 存取时间底层
  • 处理器访问存储器的频率递减

高速缓存

尽管高速缓存对操作系统是不可见的,但它与其他存储管理硬件相互影响。此外,很多用户虚拟存储的原理也可以用于高速缓存。

设计:高速缓存大小、块大小、映射函数、替换算法、写策略。

适当小的高速缓存可以对性能产生显著的影响。另一个尺寸问题是关于块大小的,即高速缓存与内存吉间的数据交换单位。当块大小从很小增长到很大时,由于局部性原理,命中率首先会增加。局部性原理指的是位于被访问字附近的数据在近期被访问到的概率比较大。当块大小增大时,更多的有用数据被取到高速缓存中。但是,当块变得更大时,新近取到的数据被用到可能性开始小于那些必须移出高速缓存的数据再次被用到的可能性(移出高速缓存是为了给新块让出位置),这时命中率反而开始降低。

当一个新块被读入高速缓存中时,由映射函数确定这个块将占据哪个高速缓存单元。设计映射函数要考虑两方面的约束。首先,当读入一个块时,另一个块可能会被替换出高速缓存。替换方法应该能够尽量减少替换出的块在不久的将来还会被用到的可能性。映射函数设计得越灵活,就有更大的余地来设计出可以增大命中率的替换算法。其次,如果映射函数越灵活,则完成搜索以确定某个指定块是否位于高速缓存中的功能所需要的逻辑电路也就越复杂。

在映射函数的约束下,当一个新块加入到高速缓存中时,如果高速缓存中的所有存储槽都已被别的块占满,那么替换算法要选择替换不久的将来被访问的可能性最小的块。这个策略称为 LRU。标识最近最少使用的块需要硬件机制支持。

如果高速缓存中某个块的内容被修改,则需要在它被换出高速缓存之前把它写回内存。写策略规定何时发生存储器写操作。一种极端情况是每当块被更新后就发生写操作;而另一种极端情况是当块被替换时才发生写操作。后一种策略减少了存储器写操作的次数,但是使内存处于一种过时的状态,这会妨碍多处理器操作以及 I/O 模块的直接内存存取。

I/O 通信技术

三种可能的技术:可编程 I/O,,中断驱动 I/O,直接内存存取(DMA)

操作系统概述

关于操作系统设计的主题涉及很多领域,学习时很容易在大量的细节中迷失方向,且在讨论某个特定问题时容易丢掉问题的前后关系。本书从操作系统的目标和功能开始陈述,然后描述一些在历史上非常重要的系统和操作系统的功能。通过这样的论述,可在一个简单的环境中给出基本的操作系统设计原理,从而使不同的操作系统功能之间的关系变得十分清楚。

本章简述操作系统的发展历史。这个历史本身很有趣且从中也可以大致了解操作系统的原理。显示介绍操作系统的目标和功能,然后讲述操作系统如何从原始的批处理系统演变成高级的多任务、多用户系统。

操作系统的目标和功能

操作系统是控制应用程序执行的程序,并充当应用程序和计算机硬件之间的接口,目标

  • 方便:操作系统使计算机更易于使用
  • 有效:操作系统允许以更有效的方式使用计算机系统资源
  • 扩展能力:在构造系统时,应该允许在不妨碍服务的前提下有效地开发、测试和引进新的系统功能

简单来说,操作系统通常提供了以下几个方面的服务:

  • 程序开发:操作系统提供各种各样的工具和服务,如编辑器和调试器,用于帮助程序员开发程序。通常,这些服务以实用工具程序的形式出现,严格来说并不属于操作系统核心的一部分;它们由操作系统提供,称作应用程序开发工具
  • 程序运行:运行一个程序需要很多步骤,包括必须把指令和数据载入到内存、初始化 I/O 设备和文件、准备其他一些资源。操作系统为用户处理这些调度问题。
  • I/O 设备访问:每个 I/O 设备的操作都需要特有的指令集或控制信号,操作系统隐藏这些细节并提供了统一的接口,因此程序员可以使用简单的读和写操作访问这些设备。
  • 文件访问控制:对操作系统而言,关于文件的控制不仅必须详细了解 I/O 设备的特性,而且必须详细了解存储介质中文件数据的结构。此外,对有多个用户的系统,操作系统还可以提供保护机制来控制对文件的访问
  • 系统访问:对于共享或公共系统,操作系统控制对整个系统的访问以及对某个特殊系统资源的访问。访问功能模块必须提供对资源和数据的保护,以避免未授权用户的访问,还必须解决资源竞争时的冲突问题
  • 错误检测和响应:计算机系统运行时可能发生各种各样的错误,包括内部和外部硬件错误,如存储器错误、设备失效或故障,以及各种软件错误,如算术溢出、试图访问被禁止的存储器单元、操作系统无法满足应用程序的请求等。对每种情况,操作系统都必须提供响应以清除错误条件,使其对正在运行的应用程序影响最小。响应可以是终止引起错误的程序、重试操作或简单地给应用程序报告错误。
  • 统计:一个好的操作系统可以收集对各种资源使用的统计信息,监控诸如响应时间之类的性能参数。在任何系统中,这个信息对于预测将来增强功能的需求以及调整系统以提高性能都是很有用的。

一台计算机就是一组资源,这些资源用于对数据的移动、存储和处理,以及对这些功能的控制。而操作系统负责管理这些资源。

操作系统的发展

串行处理

对于早期的计算机,从 20 世纪 40 年代后期到 20 世纪 50 年代中期,程序员都是直接与计算机硬件打交道的,因为当时还没有操作系统。这些机器都是在一个控制台上运行的,控制台包括显示灯、触发器、某种类型的输入设备和打印机。用机器代码编写的程序通过输入设备(如卡片阅读机)载入计算机。如果一个错误使得程序停止,错误原因由显示灯指示。如果程序正常完成,输入结果将出现在打印机中。

这些早期系统引出了两个主要问题:

  • 调度:大多数装置都使用一个硬拷贝的登记表预订机器时间。通常,一个用户可以以半小时为单位登记一段时间。用可能用户登记了 1 小时,而只用了 45 分钟就完成了工作,在剩下的时间中计算机只能闲置,这就是浪费。另一方面,如果用户没有在分配的时间内完成工作,在解决这个问题之前就会被强制停止。
  • 准备时间:一个程序称作作业,它可能包括往内存中加载编译器和高级语言程序(源程序),保存编译器好的程序(目标程序),然后加载目标程序和公用函数并链接在一起。每一步都可能包括安装或拆卸磁带,或者准备卡片组。如果在此期间发生了错误,用户只能全部重新开始。因此,在程序运行前的准备需要花费大量的时间。

这种操作模式称作串行处理,反映了用户必须顺序访问计算机的事实。后来,为使串行处理更加有效,开发了各种各样的系统软件工具,其中包括公用函数库、链接器、加载器、调试器和 I/O 驱动程序,它们作为公用软件,对所有的用户来说都是可用的。

简单批处理系统

早期的计算机是非常昂贵的,同时由于调度和准备而浪费时间是难以接受的,因此最大限度地利用处理器是非常重要的。(现在的计算机目标也是如此,尤其是云资源,服务器资源等等,其实所有的资源,都希望在一定投入之后尽可能多产出)

为了提高利用率,人们有了开发批处理操作系统的想法。第一个批处理操作系统(同时也是第一个操作系统)- IBM 701 上的 WEIZ81.

简单批处理方案的中心思想是是用一个称作监控程序的软件。通过使用这类操作系统,用户不再直接访问机器,相反,用户把卡片或磁带中的作业提交给计算机操作员,由他把这些作业按顺序组织成一匹,并将整个批作业放在输入设备上,共监控程序使用。每个程序完成处理后返回到监控程序,同时,监控程序自动加载下一个程序。

监控程序或者说批处理操作系统,只是一个简单的计算机程序。它依赖于处理器可以从内存的不同部分取指令的能力,以交替地获取或释放控制权。此外,还考虑到了其他硬件功能:

  • 内存保护:当用户程序正在运行时,不能改变包含监控程序的内存区域。如果视图这样做,处理器硬件将发现错误,并将控制转移给监控程序,监控程序取消这个作业,输入错误信息,并载入下一个作业
  • 定时器:定时器用于防止一个作业独占系统。在每个作业开始时,设置定时器,如果定时器时间到,用户程序被停止,控制权返回给监控程序
  • 特权指令:某些机器指令设计成特权指令,只能由监控程序执行。如果处理器在运行一个用户程序时遇到这类指令,则会发生错误,并将控制权转移给监控程序。I/O 指令属于特权指令,因此监控程序可以控制所有 I/O 设备,此外还可以避免用户程序意外地读到下一个作业中的作业控制指令。如果用户程序希望执行 I/O,它必须请求监控程序为自己执行这个操作
  • 中断:早期的计算机模型并没有中断能力。这个特征使得操作系统在让用户程序放弃控制权或从用户程序获得控制权时具有更大的灵活性。

内存保护和特权指令引入了操作模式的概念。用户程序执行在用户态,在这个模式下,有些内存区域是受到保护的,特权指令也不允许执行。监控程序运行在系统态,也可以称为内核态,在这个模式下,可以执行特权指令,而且受保护的内存区域也是可以访问的。

对批处理操作系统来说,用户程序和监控程序交替执行。这样存在两方面的缺点:一部分内存交付给监控程序;监控程序消耗了一部分机器时间。所有这些都构成了系统开销,尽管存在系统开销,但是简单的批处理系统还是提高了计算机的利用率。

多道程序设计批处理系统

multiprogramming / multitasking,是现代操作系统的主要方案

分时系统

第一个分时系统是由 MIT 开发的 CTSS

主要的成就

操作系统是最复杂的软件之一,这反应在为了达到那些困难甚至相互冲突的目标(方便、有效和易扩展性)而带来的挑战上。五个重要的理论进展:进程、内存管理、信息保护和安全、调度和资源管理、系统结构。

Windows / Unix / Linux

三大系统发展历史与小故事

需要重点关注的章节

  • 第五章 并发性:互斥和同步
  • 第六章 并发:死锁和饥饿
  • 第八章 虚拟内存
  • 第十六章 分布式处理、客户/服务器和集群
捧个钱场?