现代操作系统拾遗

ch1 引论

什么是操作系统？

一种运行在内核态的软件

• 操作系统的任务是创建好的抽象，并实现和管理它所创建的抽象对象（自顶向下）

• 操作系统的一个主要任务是隐藏硬件，呈现给程序（以及程序员）良好、清晰、优雅、一致的抽象

• 操作系统的任务是在相互竞争的程序之间有序地控制对处理器、存储器以及其他I/O接口设备的资源调配（自底向上的角度）

计算机硬件

处理器

• 计算机的“大脑”，从内存中取出指令并执行

• 每个 CPU 都有一套可执行的专门指令集，不同型号的指令集不兼容

• 流水线设计：一个 CPU 可以有分开的取值单元、解码单元和执行单元，可同时进行

• 超标量设计：有多个执行单元，多个指令同时被取出、解码并装入一个保持缓冲区，这个保持缓冲区又输出到多个执行单元

• CPU 内部主要包括：

  • 因为 CPU 访问内存的时间比执行指令所花费的时间多，所以 CPU 内部也有一个专门用来存储关键变量和临时数据的寄存器，这是 CPU 的“内存”
  • 程序计数器：保存了将要取出的下一条指令的内存地址
  • 堆栈指针：指向内存中堆栈的顶部，每个程序在堆栈中保存了相关的输入参数、局部变量等
  • 程序状态字（PSW）寄存器：包含 CPU 优先级、模式（用户态or内核态）以及其他控制为，在系统调用和I/O中很重要

存储器

• 理想的存储器：读取快速、空间大、便宜

• 一般情况下很难同时满足，于是有分层结构，顶层的存储器速度较高、容量较小、成本也较高，从上往下依次是：

  • CPU 寄存器：因为就在 CPU 中，所以CPU 访问几乎无时延，32位 CPU 中为32x32位，而在64位 CPU 中为64x64位，一般都小于1KB

  • 高速缓存：一般放置在 CPU 内部或非常靠近 CPU 的地方，有个专业名词叫高速缓存命中，如果没命中，则必须访问内存，这就非常耗时，所以有的机器有多级高速缓存，一级比一级更慢、更大

  • 主存（内存）：存储器结构的主力，通常是随机访问存储器（Random Access Memory, RAM），也有机器使用非易失性随机访问存储器，电源中断后，这种存储器不丢失内容，只读存储器（Read Only Memory, ROM）出厂后就不能修改，速度快且便宜，有些机器用于启动计算机的引导加载模块就放在 ROM 中

  • EEPROM（Electrically Erasable PROM，电可擦除可编程ROM）和闪存（flash memory）也是非易失性的，但是它们可擦除和重写，重写过程比较耗时

  • 磁盘：磁道（track）、柱面（cylinder）

    虚拟内存机制：这种机制可以运行大于物理内存的程序，其方法是把程序放在磁盘上，将主存作为一种缓存，用来保存最频繁使用的部分程序

    在多到程序系统（multiprogramming）中，从一个程序切换到另一个程序，称为上下文切换“context switch”

  • 磁带：经常用于磁盘的备份，可以保存非常大量的数据

I/O 设备

• I/O 设备包括设备控制器和设备，控制器是插在电路板上的一块芯片或一组芯片，为操作系统提供一个相对简单的接口，每类设备控制器不同，需要专门的软件控制，这就是设备驱动程序（device driver）
• 完成I/O的输入输出主要有三种方式
  • 忙等待
  • 设备驱动程序启动设备，设备完成操作时发出一个中断
  • 为I/O使用一种特殊的直接存储器访问（Direct Memory Access, DMA）芯片，可以控制在内存和某些控制器之间的位流

总线

• 随着计算机的发展，单总线很难满足高速需求，于是出现了多总线的系统结构，比如Pentium的：高速缓存、局部、内存、PCI、SCSI、USB、IDE、和ISA

• 通用串行总线（Universal Serial Bus, USB）是用来将所有慢速I/O设备，诸如键盘和鼠标，USB是一种集中式的总线，其根设备每1ms轮询一次I/O设备，所有USB设备共享一个USB设备驱动器，这样就不用为新的USB设备安装设备驱动程序

• 要在多总线的环境下工作，OS必须知道什么外部设备连接到了计算机上，这就有了即插即用（plug and play）的I/O系统，在即插即用前，每块I/O卡有一个固定中断请求级别和用于其I/O寄存器的固定地址

计算机的启动

• 基本输入输出系统（Basic Input Output System, BIOS）开始运行，它首先检查所安装的RAM、键盘和其他设备被是否正常，接着扫描总线找出连接的设备
• 然后BIOS查询CMOS存储器中的设备清单决定启动设备，用户可以在系统刚启动时进入BIOS配置程序，对设备清单进行修改（这个操作经常用到）
• 如果有软盘，则系统试图从软盘启动，如果有失败则试用CD-ROM，如果还是失败，则从硬盘启动，启动设备上的第一个扇区被读入内存并执行
• OS询问BIOS，获得配置信息

操作系统大观园

• 大型机OS：一般在大型公司的数据中心可以看到，主要特点是其I/O处理能力，主要提供三类服务：
  • 批处理：处理不需要交互式用户干预的周期性作业，比如保险公司的索赔处理和连锁商店的销售报告
  • 事务处理：大量小的请求，比如航班预订，每个业务量很小，但系统必须每秒处理成千上万个请求
  • 分时处理：允许多个远程用户同时在计算机上作业，比如大型数据库的查询
• 服务器OS：在服务器上运行，服务器可以是大型的个人计算机、工作站、甚至是大型机，通过网络提供服务，允许用户共享硬件和软件资源
• 多处理器OS：用于多个CPU连接的系统
• 个人计算机OS：支持多道程序处理，如Linux、Windows vista、Macintosh，普通计算机用户接触得最多
• 掌上计算机OS：掌上计算机体积非常小，比如Symbian OS（iOS应该也算吧，不过当时还是塞班比较火）
• 嵌入式OS：在控制设备的计算机上运行，这种OS肯定不会运行不可信的软件，处理的任务也是固定的，如微波炉、电视机、汽车
• 传感器节点OS：因为传感器的RAM很小，所以OS也必须小而简单，所有程序都是预装的，如TinyOS
• 实时OS：将时间作为关键参数，比如汽车装配线计算机
  • 硬实时系统：某个动作必须绝对地在规定时间（范围）发生，如流水线上的焊接动作
  • 软实时系统：允许一定的偏差，如多媒体系统
• 智能卡OS：非常严格的运行能耗和存储空间的限制，有些智能卡只具备单项功能，比如电子支付

操作系统概念

进程

• 进程（process）本质上是正在执行的一个程序，每个进程都有：

  • 地址空间（address space）：从某个最小值的存储位置到某个最大存储位置的列表，在这个地址空间中进程可以读写，存放有可执行程序、程序的数据以及程序的堆栈
  • 资源集：通常包括寄存器（包括程序计数器和堆栈指针）、打开文件的清单、突出的报警、有关进程清单以及运行该程序所需要的所有其他信息

• 进程基本上是容纳运行一个程序所需要所有信息的容器

• 进程不可能一直占据CPU，不同进程轮番使用CPU计算机才是高效率的（如何轮番使用请看后文），所以一个进程会被挂起，而它再次启动时必须要与之前暂停时的状态一致，这就意味着挂起时的所有信息都要保存下来，于是大部分OS中都有一张进程表（process table），用来存放一个进程有关的所有信息

• 所以一个挂起的进程包括：进程的地址空间、对应的进程表项

• 若一个进程能创建另一个进程，则称为父进程与子进程，若子进程再创建其子进程，则很容易得到一个进程树，有时完成某项作业需要不同进程间通信，这就叫做进程间通信（interprocess communication）

文件

• OS的一项主要功能就是隐藏磁盘和其他I/O设备的细节特性，并提供给程序员要给良好、清晰的独立于设备的抽象文件模型

• 目录（directory）、根目录（root directory），路径（path）

  Windows/Dos: \Faculty\Prof.Brown\Courses\CS101

  Unix: /Faculty/Prof.Brown/Courses/CS101

• 每个进程有个工作目录（working directory），进程可通过系统调用更换工作目录

• 在读写文件之前，首先要打开文件，检查其访问许可，若权限许可，系统将返回一个小整数，称作文件描述符（file descriptor），若禁止，则返回错误码

• Unix支持文件系统（）

• Unix支持特殊文件（special file），它们可以让I/O设备看起来像文件一般，就像使用系统调用读写文件一样，I/O设备也可以通过系统调用进行读写

  • 块特殊文件：可随机存取的块组成的设备，如磁盘等
  • 字符特殊文件：用于打印机等接受或输出字符路的设备，特殊文件一般在/dev目录中，例如/dev/lp是打印机

系统调用

• 运行在使用者空间的程序向操作系统内核请求需要更高权限运行的服务。系统调用提供了用户程序与操作系统之间的接口（即系统调用是用户程序和内核交互的接口）。

• 任何单CPU计算机一次只能执行一条指令，如果一个进程正在用户态中运行一个用户程序，并且需要一个系统服务，比如一个文件读数据，那么它就必须执行一个陷阱或系统调用指令，将控制转移到OS，OS接着通过参数检查，找出所需要的调用进程，然后OS执行系统调用

习题

1. 什么是多道程序设计（multiprogramming）

   Multiprogramming is the rapid switching of the CPU between multiple processes in memory. It is commonly used to keep the CPU busy while one or more processes are doing I/O.

2. 下面哪条指令只能在内核态使用？

   1. 禁止所有中断
   2. 读日期-时间时钟
   3. 设置日期-时间时钟
   4. 改变存储器映像

   a c d只能在内核态使用

3. 考虑一个有两个CPU的系统，每个CPU有两个线程，假设有三个程序P0 P1 P2，分别以运行时间5ms，10ms，20ms开始，运行这些程序需要花费多少时间？假设这三个程序都是100%受限于CPU，在运行时无阻塞，并且一旦设定就不会更改CPU。

   可能花费20ms，25ms，30ms，取决于OS的调度，如果P0 P1在一个CPU，P2在另一个，则花费20ms，如果P0 P2在一个，P1在另一个，则花费25ms，如果P1 P2在一个，P0在另一个，则花费30ms

4. 一台计算机有四级流水线（4-stage pipeline），每一级都花费小童事件1ns执行其工作，这台机器每秒可执行多少指令？

   Every nanosecond one instruction emerges from the pipeline. This means the machine is executing 1 billion instructions per second. It does not matter at all how many stages the pipeline has. A 10-stage pipeline with 1 nsec per stage would also execute 1 billion instructions per second. All that matters is how often a finished instruction pops out the end of the pipeline.

5. 假设一个计算机有高速缓存、内存（RAM）以及磁盘，OS用虚拟内存。读取缓存中的一个词需要2ns，RAM需要10ns，磁盘需要10ms，如果缓存命中率为95%，内存的是（缓存失效时）99%，读取一个词的平均时间是多少？

   Average access time =
   	0.95 × 2 nsec (word is cache)
   	+0.05 × 0.99 × 10 nsec (word is in RAM, but not in cache)
   	+0.05 × 0.01 × 10,000,000 nsec (word on disk only)
   	= 5002.395 nsec
   	= 5.002395 μsec

6. 什么是陷阱指令（trap instruction），解释其用途

   A trap instruction switches the execution mode of a CPU from the user mode to the kernel mode. This instruction allows a user program to invoke functions in the operating system kernel.

7. 陷阱和中断的主要差别是什么？

   A trap is caused by the program and is synchronous with it. If the program is run again and again, the trap will always occur at exactly the same position in the instruction stream. An interrupt is caused by an external event and its timing is not reproducible.

8. 分时系统为什么需要进程表，在只有一个进程的个人计算机中，该进程控制整个计算机直到结束，这种计算机需要进程表吗？

   The process table is needed to store the state of a process that is currently suspended, either ready or blocked. It is not needed in a single process system because the single process is never suspended.

   简单解释：分时系统需要切换进程，进程被挂起再复原后，需要和之前的状态一样，所以需要在被挂起时记录其状态，这就需要进程表

9. 系统调用的目的是什么？

   A system call allows a user process to access and execute operating system functions inside the kernel. User programs use system calls to invoke operating system services.

   OS隐藏了底部设备细节，只提供了一些借口，而用户进程通过系统调用来执行内核函数，用户程序通过系统调用来执行OS服务

10. 对于以下系统调用，给出引起失败的条件

    fork

    在多任务操作系统中，进程（运行的程序）需要一种方法来创建新进程，例如运行其他程序。Fork 及其变种在类 Unix 系统中通常是这样做的唯一方式。如果进程需要启动另一个程序的可执行文件，它需要先 Fork 来创建一个自身的副本。然后由该副本即 “子进程” 调用 exec系统调用，用其他程序覆盖自身：停止执行自己之前的程序并执行其他程序。

    exec

    exec is a functionality of an operating system that runs an executable file in the context of an already existing process, replacing the previous executable

    unlink

    unlink is a system call and a command line utility to delete files.

    Fork can fail if there are no free slots left in the process table (and possibly if there is no memory or swap space left). Exec can fail if the file name given does not exist or is not a valid executable file. Unlink can fail if the file to be unlinked does not exist or the calling process does not have the authority to unlink it.

11. 假设一个10MB文件在磁盘连续扇区的同一个轨道上（轨道号50），磁盘的磁臂此时位于第100号轨道上，要想从磁盘上找回这个文件，需要多长时间，假设磁臂从一个柱面移动到另一个柱面需要1ms，当文件的开始部分存储在的扇区旋转到磁头下需要5ms，并且读的速率是100MB/s

    Time to retrieve the file =
    	1 * 50 ms (Time to move the arm over track # 50)
    	+5 ms (Time for the first sector to rotate under the head)
    	+10/100 * 1000 ms (Read 10 MB)
    	= 155 ms

ch2 进程与线程

创建进程、终止进程、进程层次结构

• 主要有四种情况导致进程创建

  1. 系统初始化

     启动OS后，会创建前台、后台进程，有一些进程就像备胎一样默默地守护着OS，比如处理电子邮件、web页面、打印之类的进程，它们叫做守护进程（daemon）

  2. 正在运行的进程执行了“创建进程”的系统调用

     进程可以创建多个进程来协助完成工作

  3. 用户请求创建进程

     在交互式系统中，键入一个命令或双击一个图标就可以启动一个程序，这都会创建新进程

  4. 批处理作业的初始化

     用户在大型机的批处理系统中作业，OS认为有足够资源可以进行下一项作业时，就会创建一个新进程来对下一项作业

• UNIX：fork

  • 父进程与子进程拥有相同的存储映像（image）
  • fork系统调用创建一个新（子）进程
  • fork之后，exec系统调用装入一个新程序
  • 父进程与子进程只有pid不一样，其他资源都一样，父进程的pid>0，子进程的pid=0
  • fork后执行父进程还是子进程，取决于内核所使用的调度算法

  

  • Windows：CreateProcess

• 进程的终止

  • 正常退出（自愿）
    • 多数进程是由于完成了它们的工作而终止的
    • UNIX：exit
    • Windows：ExitProcess
  • 出错退出（自愿）
    • 比如程序中的错误，除0
  • 严重错误（非自愿）
  • 被其他进程杀死（非自愿）
    • UNIX：kill
    • Windows：TerminateProcess

• 进程的层次结构

  • 在UNIX中，进程和其子进程后裔组成一个进程组，init进程是开机后的第一个进程，所有的进程都以它为根，形成进程树，进程的父子关系不能更改
  • Windows没有进程层次的概念，所有进程地位相同，但父进程创建子进程时会得到一个特别的令牌，称为句柄，该句柄可以用来控制子进程，父进程有权把句柄传送给其他进程，这样就不存在层次结构了

进程的状态

• 运行态

  此进程实际占用CPU

• 就绪态

  可运行，但因其他进程正在运行而暂时停止，仅仅因为暂时没有CPU分给就绪态的进程

• 阻塞态

  除非某种外部事件发生，否则进程不能进入运行

• 进程的三种状态可有以下几种转换关系（1234对应abcd）

  1. 进程为等待而阻塞

     比如正在等待输入的进程

  2. 调度程序选择另一个进程

     调度程序认为当前进程占用CPU时间过长，决定让其他进程使用CPU

  3. 调度程序选择这个进程

     调度程序选择了这个进程，于是从就绪态变为运行态

  4. 出现有效输入（外部事件）

     出现外部事件，阻塞态变为就绪态，若此时CPU空闲，则可以立即触发转换3，变为运行态，切记阻塞态不能直接转换为运行态

进程的管理

• OS维护着一张表格（一个结构数组），即进程表（process table），每个进程占用一个进程表项，有些作者称之为进程控制块（PCB），该表项包含了进程状态的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、帐号和调度信息，以及其他在进程由运行态转换到就绪态或阻塞态时必须保存的信息，从而保证该进程随后能再次启动，就像从未被中断过一样
• 与每一个I/O类关联的是中断向量（interrupt vector）的位置，它包含中断服务程序的入口地址
• 例如：当磁盘中断发生时，用户进程正在运行，则中断硬件将程序计数器、程序状态字，有时还有一个或多个寄存器压入堆栈，计算机随即跳转到中断向量所指示的地址

多道程序设计模型

• 采用多道程序设计可以提高CPU的利用率

• 从概率的角度来看CPU的利用率，假设一个进程等待I/O操作的时间与其停留在内存时间的比为p，当内存中同时有n个进程时，则所有n个进程都在等待I/O（此时CPU空转）的概率是p^n（应该忽略了进程切换的消耗），此时CPU就是空闲，所以可以得到CPU的利用率公式

  CPU利用率=1-p^n

  这样理解比较好：

  一个进程有20%的时间使用CPU计算，另外80%时间用来进行I/O，则使用单道程序设计，CPU利用率只有20%，但如果使用二道程序设计，则CPU利用率将提高到36%（CPU只有在两个进程同时进行I/O时才处于闲置状态，闲置概率是0.8x0.8=0.64，故利用率是1-0.8x0.8=0.36）。

  同理，如果使用三道，CPU将提高到48.8%，四个将为59%。

• 下图给出了以n 为变量的函数，表示 CPU 的利用率，n 称为多道程序设计的道数（degree of multiprogramming）

  

• 可以清楚地看到，如果进程花费 80% 的时间等待 I/O，为使 CPU 的浪费低于 10%（即CPU利用率大于90%），至少要有 10 个进程同时在内存中

  虽然模型很简单、很粗略，它依然对预测 CPU 的性能很有效。例如，假设计算机有 8GB 内存，操作系统及相关表格占用 2GB，每个用户程序也占用 2GB。这些内存空间允许 3 个用户程序同时驻留在内存中。若 80% 的时间用于 I/O 等待，则 CPU 的利用率（忽略操作系统开销）大约是 1-0.83，即大约 49%。在增加 8GB 字节的内存后，可从 3 道程序设计提高到 7 道程序设计，因而 CPU 利用率提高到 79%。换言之，第二个 8GB 内存提高了 30% 的吞吐量。增加第三个 8GB 内存只能将 CPU 利用率从 79% 提高到 91%，吞吐量的提高仅为 12%。通过这一模型，计算机用户可以确定，第一次增加内存是一个划算的投资，而第二个则不是。

线程

• 线程：“轻量级的进程”(lightweight process)

• 为什么多线程？

  • 并行实体共享同一个地址空间和所有可用数据的能力，这正是多进程模型（具有不同地址空间）没有的
  • 线程比进程更轻量级，所以它们比进程更容易、更快创建，也更容易撤销
  • 如果存在大量的CPU计算和I/O处理，拥有多个线程允许这样活动彼此重叠进行，从而会加快应用程序执行速度
    • Windows 多线程
    • Linux 单线程
  • 应用场景：字处理软件分为两个线程，一个与用户交互，另一个在后台进行文档的重新格式化，还可以再加上一个线程，用来处理磁盘备份。显然，多进程在这里是不能工作的，因为三个线程都需要在同一个文件上进行操作，而三个线程共享公共内存，于是它们可以访问同一个正在编辑的文件

• 线程模型：

  • 多个线程共享同一个地址空间和其他资源，比如共享全局变量
  • 进程中的不同线程不像不同进程之间那样存在很大的独立性，线程之间无保护
  • 严格来说，同一时刻只有一个线程占用CPU，但高速切换给人带来并行运行的假象
  • 线程与进程一样，也具有三种状态，运行态、就绪态、阻塞态，并且转化关系也一样（见上文的图）
  • 每个线程都有其自己的堆栈，其中有一帧，供各个被调用但还没返回的过程中使用，在该帧存放了相应过程的局部变量以及过程调用完成之后使用的返回地址
  • 常见的线程调用：thread_yield，它允许线程自动放弃CPU从而让另一个线程运行，因为不同于进程，线程无法利用时钟中断强制让出CPU

• 线程和进程的区别：

  • 调度 ：在引入线程的操作系统中，线程是调度和分配的基本单位 ，进程是资源拥有的基本单位 。把传统进程的两个属性分开，线程便能轻装运行，从而可显著地提高系统的并发程度。 在同一进程中，线程的切换不会引起进程的切换；在由一个进程中的线程切换到另一个进程中的线程时，才会引起进程的切换。
  • 并发性 ：在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。
  • 拥有资源 ：不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立 单位，它可以拥有自己的资源。 一般地说，线程自己不拥有系统资源（只有一些必不可少的资源），但它可以访问其隶属进程的资源。
  • 系统开销： 由于在创建或撤消进程时，系统都要为之分配或回收资源，因此，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。 进程切换的开销也远大于线程切换的开销。

• 实现线程包：在用户空间中和在内核中

  1. 内核级线程：

     • 线程的创建、撤销和切换等，都需要内核直接实现，即内核了解每一个作为可调度实体的线程。
     2. 这些线程可以在全系统内进行资源的竞争。
     3. 内核空间内为每一个内核支持线程设置了一个线程控制块（PCB），内核根据该控制块，感知线程的存在，并进行控制。
     4. 在一定程度上类似于进程，只是创建、调度的开销要比进程小。有的统计是1：10
     • 内核线程的优点：
       1. 不需要任何新的、非阻塞的系统调用；
       2. 当有多个处理机时，一个进程的多个线程可以同时执行。
     • 内核线程的缺点：
       1. 由内核进行调度，如果线程的操作比较多，就会带来很大的开销。

  2. 用户级线程：

     • 用户级线程仅存在于用户空间。——>对比内核(3)
     2. 内核并不能看到用户线程。——>重要的区别
     3. 内核资源的分配仍然是按照进程进行分配的；各个用户线程只能在进程内进行资源竞争。
     • 用户进程的优点：
       1. 线程的调度不需要内核直接参与，控制简单；具有较好的可扩展性。
     • 内核线程的缺点：
       1. 资源调度按照进程进行，多个处理机下，同一个进程中的线程只能在同一个处理机下分时复用；
       2. 如果有一个线程引起页面故障，由于内核不知道有线程的存在，通常会把整个进程阻塞直到磁盘I/O完成为止，尽管其他线程是可以运行的。

• 多线程设计不是并行设计（而是切换进行）

进程间通信（Inter Process Communication, IPC）

• 三个问题：

  • 进程之间如何传递消息？
  • 确保多个进程在关键活动时不会交叉？
  • 正确的顺序

• 竞争条件（race condition）：两个或多个进程读写某些共享数据，而最后结果取决于进程运行时的精确时序

• 互斥（mutual exclusion）：解决竞争条件的手段，确保当一个进程在使用一个共享变量或文件时，其他进程不能做同样的操作

• 临界区域（critical region）：对共享内存进行访问的程序片段称作临界区域，或临界区（critical section）

• 解决并发的方案，需要满足4个条件：

  1. 空闲让进
  2. 忙则等待
  3. 有限等待
  4. 让权等待（阻塞的进程把CPU让给其他进程）

• 忙等待互斥的5种方法：

  1. 屏蔽中断：进程进入临界区后立即屏蔽所有中断（包括时间中断），因为CPU只有在发生中断时才会进行进程切换，所以可以实现互斥。
     • 结论：对于操作系统而言是很用的，但是对于用户进程而言则不是一个合适的方法，因为把屏蔽中断的权力交给用户不明智
  2. 锁变量：软件解决方案，这把锁实际就是个变量，可用0来表示当前进程可以进入临界区，1表示已有进程在临界区中。
     • 最后还是有可能两个进程同时进入临界区
  3. 严格轮换法：
     • 虽然可以实现互斥，但不能让权等待
     • 忙等待（busy waiting）：连续测试一个变量直到某个值出现为止，浪费CPU，只有当确定等待时间很短时才能使用忙等待，用于忙等待的锁称为自旋锁（spin lock）
     • 若一个进程比另一个慢很多，则严格轮换法效率很低，且可能会出现”进程被临界区外的进程阻塞”
  4. Peterson解法：忙等待的一种，不能让权等待
  5. TSL指令：测试并加锁（Test and Set Lock），需要硬件支持，同属于忙等待，不能让权等待

• 生产者-消费者（producer-consumer）问题

  • 描述：两个进程共享一个公共的固定大小的缓冲区，其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区中取出消息。

  • 问题1：当缓冲区已满时，生产者还想向其中放入一个新的数据项要怎么办？

    • 解决：让生产者睡眠，待消费者从缓冲区中取出一个或多个数据项时再唤醒它。

  • 问题2：当缓冲区为空时，消费者想从中取出一个数据项怎么办？

    • 解决：让消费者睡眠，待生产者放入数据项后再唤醒它

  • 代码：

    # define N 100 
    int count = 0;
    void producer(void)
    {
         int item;
         while(TRUE){
              item = produce_item();
              if(count == N)sleep();
              insert_item(item);
              count = count + 1;
              if(count == 1)wakeup(consumer);
         }
    }
    void consumer(void)
    {
         int item;
         while(TRUE){
              if(count == 0)sleep();
              item = remove_item();
              count = count - 1;
              if(count == N-1)wakeup(producer);
              consume_item(item);
         }
    }

  • 这样的代码会出现竞争条件：缓冲区为空，当消费者刚刚读取count值发现为0，此时调度程序正好决定切换为生产者进程，生产者生产后发现count值为0，于是调用wakeup来唤醒消费者，然而此时消费进程并未睡眠，wakeup信号丢失，等到调度程序切换为消费者时，消费者会继续回到上次的状态，于是睡眠。这样生产者会源源不断的生产，而消费者再也无法唤醒

  • 不完美的解法：wakeup信号丢失是关键，若加上一个唤醒等待位，当发送wakeup信号时，唤醒等待位置1，随后当进程要睡眠时，如果唤醒等待位为1，则将其置0，进程保持清醒

    感觉作者没写完整，

    应该在remove_item的上或下行，加上一个判断语句，如果唤醒等待位为1，则置为0，因为如果能执行消费，那证明wakeup信号成功接收了

    当消费者要睡眠时，必须检查唤醒等待位，只有该位为0，才能睡眠

    注意生产者、消费者在唤醒等待位的方法中可互换，这样两者都不会陷入死睡眠

  • 虽然简单地解决了问题，但是当进程多起来，唤醒等待位也要随之增加，这没有从根本上解决问题

科普文章：A gentle introduction to multithreading

信号量（semaphore）

• 大牛Dijkstra建议使用一个整型变量来累计唤醒次数，供以后使用，取值可以为0（表示没有保存下来的唤醒操作），或者为正值（表示有一个或多个唤醒操作），这就是信号量

• 信号量强调进程/线程之间的同步

• Dijkstra建议设立两种操作：down和up（分别为一般化后的sleep和wakeup）

  • 对一个信号量执行down操作，则是检查其值是否大于0，若大于0，则将其-1（即用掉一个保存的唤醒信号）；若该值为0，则进程将睡眠束

  检查数值、修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成的。保证一旦一个信号量操作开始，则保证操作完成或阻塞之前，其他进程均不允许访问该信号量

  原子操作：指一组关联的操作要么不间断地执行，要么都不执行

  • up操作对信号量的值增1，也就是释放一个资源，唤醒一个睡眠的进程

互斥量（mutex）

• 如果不需要信号量的计数能力，可以简化，称作互斥量，它仅仅适用于管理共享资源或一小段代码，因为实现容易且高效，所以在实现用户空间线程包时特别有用

• 互斥量有两种取值，解锁（取0）和加锁（取其他值）

• 当一个进程/线程需要访问临界区时，调用mutex_lock，如果该互斥量当前是解锁的（即临界区可用），则调用成功，可以进入临界区

• 另一方面，如果该互斥量已经加锁，调用线程被阻塞，直到在临界区中的线程完成并调用mutex_unlock

• 互斥锁与信号量的区别：

  1、信号量一般以同步的方式对共享资源进行控制，而互斥锁通过互斥的方式对共享资源对其进行控制；

  2、信号量可以对进程的共享资源进行控制，而互斥锁不行；

  3、信号量的值为非负整数，而互斥锁的值只能为 0 或 1；

  4、互斥量的加锁和解锁必须由同一线程分别对应使用，信号量可以由一个线程释放，另一个线程得到；

• 自旋锁与互斥锁的区别：

  1、因为自旋锁不会引起调用者睡眠，所以效率比较高

  2、自旋锁比较适用于锁使用者保持锁时间比较短的情况。

  3、自旋锁容易造成死锁，所以需要安全使用它；

之前一直隐藏了一个问题，多个进程有不连续的地址空间，如何共享某个变量呢？

1. 共享数据结构，如数据量，放在内核中，并且通过系统调用来访问
2. 多数现代OS（如Windows和UNIX）支持多个进程共享部分地址空间，这种情况下，缓冲区和其他数据结构可以共享，即使是最坏的情况，还可以共享文件

之前提到了进程和线程的区别，地址空间共享与否是关键，这里进程与线程的界限变得模糊起来，但是两者的差别还是有的，用户级线程的效率肯定要更高

• 屏障（barrier）是一种同步机制，用于进程组，规定只有所有进程做好了进入下一阶段的准备，才能允许其中任一进程进入下一阶段。当一个进程到达屏障时，它会被阻拦，直到所有进程都到达屏障为止

调度（schedule）

• 调度程序（scheduler）：当多进程同时竞争CPU时，只要有超过两个的进程处于就绪态，那么单CPU必须选择下一个要运行的进程，完成选择工作的程序称为调度程序（另称CPU调度器）

• CPU分配器（Dispatcher）：调度器决定了将CPU分配给谁，然后分配器将CPU控制权交给该进程，操作内容通常包括：

  • 上下文切换（switching context）：这通常是一种额外开销（overhead），切换时间取决于CPU硬件支持力度
  • 从内核态（kernel mode）转移至用户态（user mode）

• 调度算法（scheduling algorithm）：调度程序所使用的算法

• 进程行为：进程的行为一般分为I/O和计算（CPU），根据占用时间不同，分为I/O密集型（I/O burst）进程和CPU密集型（CPU burst）进程

  有必要指出：随着CPU变得越来越快，更多进程倾向于I/O密集型（I/O-bound），因为CPU的改进比磁盘快得多

• 何时调度：

  1. 创建一个新进程之后，需要决定是运行父进程还是子进程（调度程序可以合法选择）
  2. 当一个进程退出时必须作出调度决策
  3. 当一个进程阻塞在I/O和信号量上或由于其他原因阻塞时，必须选择另一个进程运行
  4. 在一个I/O中断发生时，必须作出调度决策

• 如果硬件时钟提供50Hz或其他频率的周期性中断，可以在每个时钟中断或每k个时钟中断时做出调度决策，根据何时处理时钟中断，调度算法分为两类：

  1. 非抢占式（nonpreemptive）调度算法：挑选一个进程让它一直执行直至被阻塞或自动释放CPU（在这种情况下，该进程若交出CPU都是自愿的）
  2. 抢占式（preemptive）调度算法：挑选一个进程让它运行某个固定时间的最大值，结束时会被挂起，调度程序会选择另一个合适的进程来运行（优先级高的先调度），必须要有可用的时钟来发生时钟中断，不然只能用非抢占式调度算法

• 三种环境的目标

  • 批处理：抢和非抢
    • 吞吐量（throughout）：系统每小时完成的作业数量
    • 周转时间（turnaround time）：从一个批处理作业提交时刻开始直到该作业完成时刻位置的统计平均时间
    • CPU利用率（CPU Utilization）
  • 交互式：抢
    • 响应时间——快速响应请求
    • 均衡性——满足用户的期望
  • 实时：非抢
    • 满足截止时间——避免丢失数据
    • 可预测性——在多媒体系统中避免品质降低
  • 所有系统的共同目标
    • 公平——给每个进程公平的CPU份额
    • 策略强制执行
    • 平衡——保持系统的所有部分都忙碌

• 衡量调度程序（调度算法）好坏的几个指标：

  • 吞吐量（throughout）：系统每小时完成的作业数量

  • 周转时间（turnaround time）：从一个批处理作业提交时刻开始直到该作业完成时刻位置的统计平均时间

    能提高吞吐量的算法不一定有最小的周转时间，例如，短作业和长作业的组合，调度算法只调度短作业，吞吐量肯定很大，但是长作业根本没法完成，这样平均周转时间无限长

  • CPU利用率（CPU Utilization）

• 调度算法（批处理、交互式、实时）：

  • 批处理系统：
    • 非抢占式的先来先服务（FCFS：first-come first-served）
      • 容易理解：建立一个队列，选取进程运行时，从队列头部选取，添加进程时，添加到队列的尾部
      • 但是通过例子可以发现，短进程比长进程先执行，平均等待时间会缩短
    • 非抢占式的最短作业优先法（shortest job first）
      • 前提：预知进入就绪队列的进程执行时间
      • 原理：假设有4个进程，其运行时间分别为a，b，c，d，第一个进程在a时刻结束，第二个进程在a+b时刻结束，以此类推，平均周转时间为（4a+3b+2c+d）/4，可以看到a对平均值的影响最大，所以a应该取最小值才好，这样平均周转时间才能取到最小值
      • 抢占式的最短作业优先算法：当一个进程进入就绪队列，如果它的CPU时间小于当前拥有CPU的进程的剩余“预估”时间，前者抢占后者的CPU，称为 最短剩余时间优先（Shortest-Remaining-Time-First，SRTF）
      • SJF算法是最优的算法，但必须保证所有作业都可同时运行
      • SJF有致命缺陷，如何预估进入就绪队列的进程的执行时间？
        • 不可能准确地预测，比如需要用户输入，这是不可知的
        • 只能根据过去的CPU burst cycle来预测
      • HRN（Highest response Ratio Next）
        • HRN = （W + T）/ T
        • W为等待时间，T代表预估CPU时间
  • 交互式系统：

    • 轮转调度（Round Robin，RR）

      • 时间片（quantum）：每个进程被分配一个时间段，即允许该进程在该时间段中运行，如果在时间片结束时该进程还在运行，则将剥夺CPU给下一个进程，如果该进程在时间片结束前阻塞或结束，则CPU立即切换
      • 轮转调度算法是最古老的、最简单的、最广的，并且实现很容易，只需要维护一张可运行进程列表
      • 假设n个就绪进程，时间片q，每个就绪进程得到1/n的CPU时间，任何就绪进程最多等待(n-1)q单位时间
      • 平均周转时间通常优于SJF
      • 响应时间一定优于SJF
      • 性能分析：
        • q如果很大，则FIFO
        • q如果很小，则进程切换，或称上下文切换（context switch）开销太大，所谓上下文切换是：从一个进程切换到另一个进程是需要一定的时间的，所以q必须远远大于上下文切换时间
      • 结论：时间片设得太短会导致过多的进程切换，降低了CPU的效率；而设得太长有可能引起对短的交互请求的响应时间变长，通常将时间片设为20ms~50ms是合理的折中

    • 优先级调度（Priority Schedule）

      • 每个进程都有一个优先数（priority number），通常是整数，允许优先级最高的可运行进程先运行，Scheduler每次会选取就绪队列中，优先级最高的进程执行
      • 当优先级定义为“进程需要的CPU时间”时，SJF算法就是优先级调度
      • 优先级可由系统动态确定，例如：有些进程为I/O密集型，其多数时间在等待I/O操作，当这样的进程需要CPU时，应尽快地给它CPU，已便它能很快地执行完CPU操作然后去等待I/O操作，下一个进程就可以同时进入CPU。如何实现这样的效果呢？一个简单算法：其优先级设为1/f，f为该进程在上一个时间片所占的部分，比如假设时间片为50ms，某个进程只使用了1ms，那么它将获得优先级50，用掉全部时间片的进程的优先级为1
      • 给不同的进程设置了优先级后，还可以给相同优先级的进程归入一个优先级组，高优先级组内的进程使用轮转调度算法，低优先级组的进程只能干巴巴的等着，这样就会出现饥饿现象
      • 进程饥饿（Starvation）：优先级较低的进程可能永远得不到CPU
      • 解决：Aging思想，优先级要考虑就绪进程在就绪队列里的等待时间，因此，若一个进程在就绪队列中等待，那它的优先级会单调递增

    • 多级队列（Multilevel Queue）

      • 把就绪队列拆分成几个队列
      • 每个队列有其自己的调度算法，比如前台就绪队列需交互性，采用轮转法，后台就绪队列需批处理，采用先来先服务法
      • CPU怎么在队列间分配？
        • 固定优先权法，例如，先前台队列，再后台队列
        • 时间片办法，例如，80%的CPU时间给前台队列，20%的CPU时间给后台进程

    • 多级反馈队列（Multilevel Feedback Queue）

      • 基于多级队列，但另外考虑了进程在就绪队列之间可以迁移
      • 给不同就绪队列的作业分配不同长度的时间片，第一级别队列时间片最小，随着优先级别的降低，时间片增大
      • 各级队列按照时间片轮转方式进行调度
      • 当一个新进程创建后就绪后就进入第一级队列
      • 进程用完时间片后就会进入下一级队列，同时获得的时间片更大
      • 既能使高优先级的作业得到响应又能使短作业（进程）迅速完成
      • 定义这样的算法应该着重考虑：
        • 队列个数
        • 每级队列的调度算法
        • 如何将就绪进程升级至高层次队列
        • 如何将就绪进程降低至低层次队列
        • 当一个就绪进程进入就绪队列时，应该去哪一级？

    • 最短进程优先

      • 由于最短作业优先法常常伴随最短响应时间

      • 如何从当前可运行进程中找出最短的那一个进程？可以根据进程过去的行为进行预测，并执行估计运行时间最短的那个

      • 假设某个终端上每条命令的估计运行时间为T0，现在假设其下一次运行时间为T1，可以用着两个值的加权和来改进估计时间，即aT0+(1-a)T1，通过选择a的值，可以决定是尽快忘掉老的运行时间，还是在一段长的时间内记住它们，a称为遗忘值

      • 当a=1/2时，可以得到如下序列

        T0, 
        T0 /2 + T1 /2, 
        T0 /4 + T1 /4 + T2 /2, 
        T0 /8 + T1 /8+ T2 /4 + T3 /2

      • 老化（aging）算法在a=1/2特别容易实现，只需要将新值加到当前估计值上，然后除以2（即右移一位）

    • 彩票调度（lottery scheduling）

      • 向所有进程提供关于CPU时间的彩票，有点需要作出一项调度决策时，就随机抽出一张彩票，拥有该彩票的进程获得该资源
      • 重要进程可以得到更多份额的彩票，以提高它被抽中的概率
      • 彩票调度有很有趣的性质，如果新出现了一个进程，获得一定份额的彩票，那么它在下次调度时就有相应的机会赢得奖励，换句话说，彩票调度是迅速的
      • 根据概率知识，通过分配进程的彩票比例，各进程得到CPU时间也是成比例的
  • 实时系统中的调度

    • 实时系统是一种时间起着主导作用的系统

    • 硬实时（hard real time）调度：调度机制确保一个关键任务能在指定时间前完成

    • 软实时（soft real time）调度：调度机制尽量给予关键任务最高优先级，尽量在指定时间前完成

    • 实时系统中的时间可以按照其分类为周期性时间（以规则的时间间隔发生）或非周期性事件（发生时间不可知），一个系统可能要响应多个周期性事件流。根据每个事件需要处理时间的长短，系统有可能无法处理完所有的事件。例如，如果有m个周期事件，事件i以周期Pi发生，并要Ci秒CPU时间处理一个事件，那么可以处理负载的条件是

      ∑Ci/Pi≤1

      满足这样条件的实时系统称为可调度的（隐含了一个假设，即上下文切换的开销很小，可忽略不计）

• 策略和机制

  • 之前讨论的调度算法都没有从用户进程获得有关进程的信息
  • 主进程管理子进程，不同子进程负责不同的功能实现，主进程当然知道哪些进程是必要且紧急的，如果能从中获得进程相关的信息，调度结果会更优
  • 解决办法：将调度机制（scheduling mechanism）与调度策略（scheduling policy）分离，也就是将调度算法以某种形式参数化，而参数可以由用户进程填写

哲学家就餐问题

• 几个哲学家围坐在圆桌旁，每个人面前都有一盘通心粉，需要两把叉子才能固定住，相邻两个哲学家之间有一把叉子，只有哲学家拿到左右两把叉子才会进食，能否编写一段程序使得不会发生死锁（既没人饿死）
• 使用二元信号量可以解决死锁问题，但只能同时允许一位哲学家进餐，实际上五把叉子可以允许两位哲学家进餐
• 使用数组state跟踪每一位哲学家实在就餐、思考还是饥饿状态（试图拿叉子），使用信号量数组对应每一位哲学家，这样在所需的叉子被占用时，想就餐的哲学家就会被堵塞

习题

1. 对于进程的三种状态，理论上有六种转换，图中只给了四种转换，还有两种它们有可能发生吗？

   

   The transition from blocked to running is conceivable（可想象的）. Suppose that a process is blocked on I/O and the I/O finishes. If the CPU is otherwise idle, the process could go directly from blocked to running. The other missing transition, from ready to blocked, is impossible. A ready process cannot do I/O or anything else that might block it. Only a running process can block.

2. 多个作业并行运行的速度当然要比顺序执行要快。假设有两个作业同时开始，每个需要10min CPU时间，如果顺序执行，那么最后一个作业需要多长时间完成？如果并行执行又需要多长时间？假设I/O等待占50%

   If each job has 50% I/O wait, then it will take 20 minutes to complete in the absence of competition. If run sequentially, the second one will finish 40 minutes after the first one starts. With two jobs, the approximate CPU utilization is 1 − 0.5^2 . Thus each one gets 0.375 CPU minute per minute of real time. To accumulate 10 minutes of CPU time, a job must run for 10/0.375 minutes, or about 26.67 minutes. Thus running sequentially the jobs finish after 40 minutes, but running in parallel they finish after 26.67 minutes.

3. 一个多线程Web服务器，如果读取文件的唯一途径是正常的阻塞read系统调用，那么Web服务器应该使用用户级线程还是内核级线程，为什么？

   A worker thread will block when it has to read a Web page from the disk. If user-level threads are being used, this action will block the entire process, destroying the value of multithreading. Thus it is essential that kernel threads are used to permit some threads to block without affecting the others.

4. 存在单线程服务器更好的场景吗？

   Yes. If the server is entirely CPU bound（CPU密集型）, there is no need to have multiple threads. It just adds unnecessary complexity

5. 线程可以被时钟中断抢占吗？如果可以，在什么情况下可以？如果不可以，在什么情况下不可以？

   User-level threads cannot be preempted by the clock unless the whole process’ quantum has been used up. Kernel-level threads can be preempted individually. In the latter case, if a thread runs too long, the clock will interrupt the current process and thus the current thread. The kernel is free to pick a different thread from the same process to run next if it so desires

6. 在用户空间实现线程，其最大的优点和缺点是什么？

   The biggest advantage is the efficiency. No traps to the kernel are needed to switch threads. The biggest disadvantage is that if one thread blocks, the entire process blocks.

7. 创建线程和打印消息严格按以下顺序执行：创建线程1，线程1打印消息，线程1结束；创建线程2，线程2打印消息，线程2结束；…

   问怎么做到？

   Yes, it can be done. After each call to pthread_create, the main program could do a pthread_join to wait until the thread just created has exited before creating the next thread.

8. 如果一个系统只有两个线程，可以使用屏障来同步它们吗?

   If the program operates in phases and neither process may enter the next phase until both are finished with the current phase, it makes perfect sense to use a barrier.

9. 当阻塞在I/O之前时，平均每个进程运行时间为T，一次进程切换需要的时间为S，这里S实际上就是开销，对于采用时间片长度为Q的轮转调度，请给出以下各种情况CPU利用率的公式

   1. Q=∞
   2. Q>T
   3. S<Q<T
   4. Q=S
   5. Q趋近于0

   The CPU efficiency is the useful CPU time divided by the total CPU time.
   When Q ≥ T, the basic cycle is for the process to run for T and undergo a
   process switch for S. Thus (a) and (b) have an efficiency of T/(S + T). When the quantum is shorter than T, each run of T will require T/Q process switches, wasting a time ST/Q. The efficiency here is then
   T/(T + ST/Q), which reduces to Q/(Q + S), which is the answer to (c).

   For (d), we just substitute Q for S and find that the efficiency is 50%.

   Finally, for (e), as Q → 0, the efficiency goes to 0.

10. 有5个待运行作业，估计它们的运行时间分别为：9，6，3，5，X，采用哪种次序运行这些作业可得到最短的平均响应时间（结果取决于X）

其实就是最短作业优先法（shortest job first）

Shortest job first is the way to minimize average response time.
0 < X ≤ 3: X, 3, 5, 6, 9.
3 < X ≤ 5: 3, X, 5, 6, 9.
5 < X ≤ 6: 3, 5, X, 6, 9.
6 < X ≤ 9: 3, 5, 6, X, 9.
X > 9: 3, 5, 6, 9, X.

11. 有个5个批处理作业A到E，它们几乎同时到达调度中心，估计它们的运行时间分别为10，6，2，4，8min，其优先级分别为3，5，2，1，4，其中5为最高优先级，对于下列每种调度算法，计算其平均周转时间（可忽略进程切换的开销）

    1. 轮转法
    2. 优先级调度
    3. 先来先服务（按照10，6，2，4，8）
    4. 最短作业优先

    对a假设系统具有多道程序处理能力，每个作业均公平共享CPU时间，对b到d，假设同一时刻只有一个作业运行，直到结束，所有的作业都是CPU密集型作业

    For round robin, during the first 10 minutes each job gets 1/5 of the CPU. At the end of 10 minutes, C finishes. During the next 8 minutes, each job gets 1/4 of the CPU, after which time D finishes. Then each of the three remaining jobs gets 1/3 of the CPU for 6 minutes, until B finishes, and so on. The finishing times for the five jobs are 10, 18, 24, 28, and 30, for an average of 22 minutes.

    For priority scheduling, B is run first. After 6 minutes it is finished.
    The other jobs finish at 14, 24, 26, and 30, for an average of 18.8 minutes. (感觉算错了，应该是(6+14+24+26+30)/5=20min吧)

    If the jobs run in the order A through E, they finish at 10, 16, 18, 22, and 30, for an average of 19.2 minutes.

    Finally, shortest job first yields finishing times of 2, 6, 12, 20, and 30, for an average of 14 minutes.

    从这里可以看到，sjf算法是最优的

12. 运行在CTSS的一个进程需要30个进程片完成，该进程必须被调入多少次，包括第一次（再该进程运行之前？）

    The first time it gets 1 quantum. On succeeding runs it gets 2, 4, 8, and 15, so it must be swapped in 5 times.

13. a=1/2的老化算法用来预测运行时间，先前的四次运行，从最老的一个到最近的一个，其运行时间分别是40ms，20ms，40ms和15ms。下一次的预测时间是多少？

    The sequence of predictions is 40, 30, 35, and now 25.

    T0														= 40
    T0 /2 + T1 /2 								= 30
    T0 /4 + T1 /4 + T2 /2 				= 35
    T0 /8 + T1 /8+ T2 /4 + T3 /2	= 25

14. 一个软实时系统有4个周期时间，其周期分别为50ms，100ms，200ms和250ms，假设这4个事件分别需要35ms，20ms，10ms和x ms的CPU时间，保持系统可调度的最大x值是多少？

    35/50 + 20/100 + 10/200 + x/250 <= 1
    x<=12.5ms

15. 一个实时系统需要处理两个语音通信，每个运行5ms，然后每次突发消耗1msCPU时间，加上25帧/秒的一个视频，每一帧需要20ms的CPU时间，这个系统是可调度的吗？

    Each voice call runs 200 times/second and uses up 1 msec per burst, so each voice call needs 200 msec per second or 400 msec for the two of them. The video runs 25 times a second and uses up 20 msec each time, for a total of 500 msec per second. Together they consume 900 msec per second, so there is time left over and the system is schedulable.

ch3 存储管理

• 存储管理器的作用：有效地管理内存，即记录哪些内存正在使用，哪些内存是空闲的，在进程需要时分配为其分配内存，在进程使用完后释放内存。

无存储器抽象

• 最简单的存储器抽象就是根本没有抽象，每一个程序都直接访问物理内存
• 在这种情况下，要想在内存中同时运行连个程序是不可能的，所以无进程概念

存储器抽象：地址空间

• 把物理地址暴露给进程会带来严重问题

  • 如果用户程序可以寻址内存的每个字节，它们可以很容易地破坏OS
  • 同时运行多个程序是很困难的（如果只有一个CPU就轮流执行）

• 要保证多个程序同时处于内存中并且互不影响的关键：保护和重定位

• 解决办法：地址空间（类似于进程是对CPU的抽象，地址空间就是对内存的抽象）

• 地址空间是一个进程可用于寻址内存的一套地址集合

• 每个进程都有一个自己的地址空间，并且独立于其他进程的地址空间

• 基址寄存器与界限寄存器（以前常用）

  • 使用动态重定位，简单地把每个进程的地址空间映射到物理内存的不同部分，使用基址寄存器（程序的起始物理地址）和界限寄存器（程序的长度）
  • 缺点：每次访问内存都需要进行加法和比较运算，速度较慢

交换技术

• 把所有进程一直保存在内存中需要巨大的内存

• 交换（swapping）技术：把一个进程完整地调入内存，使该进程运行一段时间，然后把它存回磁盘。空闲进程主要存储在磁盘上，所以当它们不运行时就不会占用内存（尽管它们的一些内存会周期性地被唤醒已完成相关工作，然后就又进入睡眠状态）

  

• 使用交换技术会在内存中产生多个空闲区（hole，有时也称为空洞）

• 内存紧缩（memory compaction）：把小的空闲区合成一大块，这个操作不经常进行，因为需要大量CPU时间

• 大部分进程在运行时都在增长，为了减少进程交换和内存紧缩的开销，当进程被创建或被换入的时候就为它分配一些额外的内存

• 如下图，有两种分配额外内存的方式

  

空闲内存管理

• 在动态使用内存时，OS必须对其管理

• 使用位图的存储管理：内存被划分为分配单元，每个分配单元对应于位图中的一位，0 表示空闲，1 表示占用

  

• 使用了链表的存储管理：维护一个记录已分配内存段和空闲内存段的链表，每一个结点都包含以下域：空闲区（H）或进程（P）的指示标志、起始地址、长度、和指向下一节点的指针。

  

• 当按照地址顺序在链表中存放进程和空闲区时，用来为创建的进程（或从磁盘换入的已存在的进程）的算法有以下几种：

  • 首次适配（first fit）：存储管理器沿着段链表进行搜索，直到找到一个足够大的空闲区，将空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。速度很快
  • 下次适配（next fit）：与first fit大抵相似，不同的是每次找到合适的空闲区时都记录当时的位置，以便下次寻找空闲区时从上次结束的地方开始搜索。性能略低于first fit
  • 最佳适配（best fit）：搜索整个链表找到能够容纳进程的最小的空闲区。速度很慢，而且反直觉的浪费更多内存，因为会产生大量无用的小空闲区
  • 最差适配（worst fit）：总是分配最大的空闲区。性能也不高
  • 快速适配（quick fit）：为常用大小的空闲区维护单独的链表。寻找指定大小的空闲区很快，但是当进程终止或换出，寻找相邻块，查看是否可以合并的过程是非常费时的。

虚拟内存（virtual memory）/分页（paging）

• 由于程序大于内存，早期解决方法是覆盖（overlay），程序开始执行时，将覆盖管理模块装入内存，从覆盖0开始一层一层往上叠

• 虚拟内存：每个程序拥有自己的地址空间，这个空间被分割为多个块，每一块称为一页或页面（page），每一页有连续的地址范围

• 这些页面被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序，当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时，由OS负责将缺失的部分装入物理内存并重新执行失败的指令

• 从某个角度来讲，虚拟内存是对基址寄存器和界限寄存器的一种综合

• 虚拟内存很适合在多道程序设计系统中使用

• 由程序产生的地址称为虚拟地址（virtual address），虚拟地址组成虚拟地址空间，内存管理单元（MMU）负责把虚拟地址映射为物理内存地址

  

• 虚拟地址空间按照固定大小划分为页面，在物理内存中对应的单元称为页框，页面和页框一般大小相同，RAM和磁盘之间的交换总是以整个页面为单元进行的

• 缺页中断（page fault）：当访问虚拟中没有被映射的页面时发生的系统调用，解决方法：操作系统找到一个很少使用的页框并把它写到磁盘，随后把需要访问的页面读到该页框，修改映射关系，然后重新启动引起陷阱的指令（如何决定这个“很少使用”？且看后文的“页面置换算法”）

• 页表：虚拟地址映射到物理地址的概括，虚拟地址被分为虚拟页号（高位）和偏移量（低位）两部分。虚拟页号用作页表的索引，找到该虚拟页面对应的页表项，由页表项可以找到页框号（如果可用），然后把页框号拼接到偏移量的高位，以替代虚拟页号，形成送往内存的物理地址。

• 页表的目的：把虚拟页面映射为页框，从数学角度出发，页表是一个函数

  

加速分页过程

• 分页系统需要考虑两个主要的问题：虚拟地址到物理地址的映射必须非常快（避免映射成为一个主要瓶颈）；如果虚拟地址空间很大，页表也会很大（计算机使用至少 32 位虚拟地址）
• 每个进程都需要自己的页表，因为他有自己的虚拟地址空间
• 加速分页问题的解决方法
  • 转换检测缓冲区：为计算机设置一个小型的硬件设备，将虚拟地址直接映射到物理地址，而不必再访问页表，这种设备被称为 转换检测缓冲区（TLB），或称为块表，通常在 MMU 中 即缓存最常用的页面
  • 软件 TLB 管理：当发生 TLB 访问失效时，不再是由 MMU 到页表中查找并取出需要的页表项，而是生成一个 TLB 失效并将问题交给操作系统解决
    两种不同的 TLB 失效：（1）软失效 （2）硬失效

针对大内存的页表

• 多级页表

  • 32 位虚拟地址被划分为 10 位 PT1+10 位 PT2+12 位 Offset
  • 引入的目的是避免把全部页表一直保存在内存中

  

• 倒排页表（inverted page table）

  • 实际内存中每个页框对应一个表项，而不是每个虚拟页面对应一个表项

  • 优点：节省了大量的空间（优于多级列表）

  • 缺点：从虚拟地址到物理地址的转换会变得很困难，使用 TLB 来解决，当发生 TLB 失效，用散列表（hashtable）方法来搜索倒排页表，用虚拟地址来散射

    

页面置换算法

• 在发送缺页中断时，需要选择一个页面，将其换出内存，以便腾出空间

• 虽然可以随即地选择一个页面来置换，但是如果每次都选择经常使用的页面，这会带来不必要的开销，所以一个高效的算法是很有必要的

• 最优页面置换算法

  • 算法描述：每个页面用在该页面首次被访问前所要执行的指令数作为标记，每次替换标记数目最大的页面
  • 不可能实现，当缺页中断发生时，OS无法知道各个页面下一次将在什么时候被访问

• 最近未使用页面置换算法（NRU, not recently used）

  • 使用 R 位（访问位）和 M 位（修改位）设置的一个简单的页面置换算法

  • 当启动一个进程时，它所有的页面的R位和M位都由操作系统设置为 0，R 位被定期地清零（比如在每次时钟中断时），以区别最近没有被访问和访问的页面，当发生缺页中断，操作系统检查所有页面的这两位的值，并分为四类，NRU 算法随机地从类编号最小的非空类中挑选一个页面淘汰

    

  • 第1类初看似乎不可能，但是第3类在它的R位被时钟中断清零了后就成了第1类

• 先进先出页面置换算法（FIFO）

  • 由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最早的放在表头
  • 当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾
  • 因为FIFO可能会扔掉经常使用的页面，所以很少使用纯粹的FIFO算法

• 第二次机会页面置换算法（second chance）

  • 发生缺页中断时，在 FIFO 基础上检查 R 位，为 0，淘汰，为 1，则清0，并加入表尾
  • 这种算法的思想就是寻找一个最近的时钟间隔以来没有被访问过的页面

• 时钟页面置换算法（clock）

  • 把所有页面保存在一个类似钟面的环形链表中，一个表针指向最古老的页面

  • 发生缺页中断时，首先检查表针指向的页面，如果R是0，则淘汰，如果R是1，则清楚R位，并把表针前移一个位置

  • 是对second chance的改进

    

• 最近最少使用页面置换算法（LRU, least recently used）

  • 在缺页中断发生时，置换未使用时间最长的页面
  • 虽然理论可行的，但是代价很高，硬件实现方法：64 位计数器 C

• 最不常用置换算法（NRU, not frequently used）

  • 对LRU的软件模拟算法
  • 将每一个页面与一个软件计数器相关联，每次时钟中断时，根据 R 位更新计数器，置换计数器最小的页面。
  • 缺点：不会忘记任何事情，所以容易置换有用的页面

• 老化算法（aging）

  • 老化算法对NRU进行简单的改进就可以很好地模拟LRU

  • 在 R 位被加进来之前先将计数器右移一位；将 R 位加到计数器的最左端位

  • 老化算法与LRU的区别：

    • 老化算法无法分辨在每个时钟滴答中哪个页面访问更早
    • 老化算法的计数器只有有限位数，这就限制了其对以往页面的记录

    

• 工作集页面置换算法

  • 请求调页（demand paging）策略：页面在被需要时调入，而不是预先

  • 工作集（working set）：一个进程当前正在使用的页面集合

  • 颠簸（thrashing）：每执行几条指令程序就发生一次缺页中断

  • 工作集模型（working set model）：在进程运行前就预先装入其工作集页面，即预先调页（prepaging）

  • 大多数程序会任意访问一小部分页面，但是这个集合随时间缓慢变化，通过工作集推导出合理页面置换算法，其思想是：淘汰不在工作集中的页面

  • 维护移位寄存器可以确定k值，但不切实际

  • 改进：不是向后找最近 k 次的内存访问，而是考虑其执行时间（更容易实现，因为每个进程只计算执行时间）

    

• 工作集时钟页面置换算法

  • 由于上面的算法每次置换都要扫描整个页表，比较费时，所以改进算法，基于时钟算法，并且用到了工作集称为 WSClock (工作集时钟算法)

  • 性能较好，使用广泛

    

• 页面置换算法小结

  

局部分配策略与全局分配策略

• 问题：怎样在互相竞争的可运行进程之间分配内存？换出的页面与换入的页面必须是同一进程的吗？
• 局部（local）页面置换算法：可以有效地为每个进程分配固定的内存片段
• 全局（global）页面置换算法：在可运行的进程之间动态地分配页框，因此分配给各个进程的页框数是随时间变化的
• 全局算法通常情况工作得更好，当工作集的大小随进程运行时间发生变化时，这种现象更加明显；7在使用局部算法时，工作集的增长会导致颠簸，工作集缩小，局部算法又会浪费内存；在使用全局算法时，系统必须不停确定应该给每个进程分配多少个页框，一种方法是监测工作集的大小，由“老化”位指出，但这不能防止颠簸，另一种方法是使用一个为进程分配页框的算法，等额或者按照进程大小分配
• 管理动态内存算法：PFF（缺页中断率算法）指出何时增加或减少分配给一个进程的页面，PFF仅控制分配集的大小，没有说明发生缺页中断时应替换掉哪个页面

负载控制/页面大小

• 一旦所有进程的组合工作集超出了内存容量，就可能发生颠簸

• 减少竞争内存的进程数的一个好办法是将一部分进程交换到磁盘，并释放他们所占有的所有页面

• 还需考虑多道程序设计的道数，因为进程数过低，cpu 可能长时间处于空闲

• 确定最佳页面大小需要在几个互相矛盾的因素之间进行权衡

• 选择小页面原因：
  （1）大页面容易出现内部碎片，浪费最后一个页面，这种浪费叫做内部碎片（internal fragmentation）
  （2）分阶段执行每阶段可能只需要小的内存

• 不选择小页面的原因：
  （1）需要更大的页表，页面传输（内存和磁盘之间）用时长
  （2）小页面需更多 TLB 表项
  （3）切换程序装载页面寄存器用时长

• 通过数学推导出最优页面大小：P = 根号(2*s*e)，其中s是进程平均字节，e是每个页表项字节

分离的指令空间和数据空间/共享页面/共享库/内存映射文件

• 大多数计算机只有一个地址空间，既放程序也放数据

• 链接器必须知道如何使用分离的 I 空间和 D 空间，因为当使用他们时，数据被重定位到虚拟地址 0，而不是程序之后

• 在使用这种设计的计算机，两种地址空间都可以进行分页

• 共享页面：只读的页面（诸如程序文本）可以共享，数据页面不能，共享 I 空间，各自维护自己的 D 空间

• 两个进程通过共享程序表来共享同一个程序

• 可以使用其他的粒度取代单个页面实现共享，即共享库

• 现代OS中，有很多大型库被众多进程使用，更加通用的技术就是共享库（在Windows中被称为DLL或动态链接库）

• 链接的概念：链接器寻找未定义外部函数（undefined externals），找到后把他们加载成一个可执行二进制文件写到磁盘，其中包括了所需的全部函数

• 由于每次链接加载库函数太麻烦，所以使用共享库。当一个程序链接共享库时，链接器没有加载被调用的函数而是加载了一小段能够在运行时绑定被调用函数的存根例程。如果其他程序已经装载了某个共享库，就没有必要再次装载它了 (共享关键所在)

• 共享库优点：可执行文件小、节省内存空间、如果共享库中一个函数被修改，不需要重新编译调用这个函数的程序，旧的二进制文件依旧可以执行

• 共享库的一个问题：重定位问题。解决方案：（1）写时复制（不妥，与共享库思想相悖） （2）使用相对地址的指令的代码，即位置无关代码（position-independent code）

• 共享库实际上是内存映射文件（memory-mapped file）的一个特例：进程可以通过发起一个系统调用，将一个文件映射到虚拟空间中的一部分

• 内存映射文件提供了一种 I/O 可选模型，提供了一个进程之间的高带宽通信

清除策略

• 分页守护进程（paging daemon）：在大多数时候睡眠，但定期被唤醒以检查内存的状态，这是为了保证有足够的空闲页框
• 一种清除策略方法：双指针时钟，前指针由分页守护进程控制，增加干净页面，后指针用于页面置换

虚拟内存接口

• 允许程序员对内存映射进行控制的一个原因是为了允许共享内存，或实现高性能的信息传递系统
• 分布式共享内存：允许网络上的多个进程共享一个页面集合

有关实现的问题

• 与分页有关的工作

  • 操作系统做分页工作的时间段：进程创建时、进程执行时、缺页中断时、进程终止时
  • 创建，确定程序与数据初始化时有多大，并在内存中为页表分配空间并对其进行初始化
  • 执行，为新进程重置MMU，刷新TLB，新进程的页表必须成为当前页表
  • 中断，确定哪个虚拟地址造成了缺页中断，通过该信息，计算出页面，并在磁盘上定位页面，必须找到合适的页框来存放新页面，必要还要置换老页面，然后把所需的页面读入页框
  • 终止，释放该进程的页表

• 缺页中断处理（细节）

  （1）硬件陷入内核，在堆栈中保存程序计数器
  （2）启动一个汇编代码例程（例程是某个系统对外提供的功能接口或服务的集合。）保存通用寄存器和其他易失信息，以免被操作系统破坏
  （3）当操作系统发现一个缺页中断时，尝试发现需要哪个虚拟页面（4）一旦知道了发生缺页中断的虚拟地址，操作系统检查这个地址是否有效，并检查存取与保护是否一致。然后找空闲页框，若没有，淘汰一个页面
  （5）如果页框是脏的，安排该页写回磁盘，并发生一次上下文切换，挂起缺页中断的进程，让其他进程运行直至磁盘传输结束。（6）一旦页框干净，操作系统查找所需页面在磁盘上的地址，通过磁盘操作将其装入
  （7）当磁盘中断发生，表明该页已经被装入，页表已经更新可以反映其位置，页框也被标记为正常
  （8）恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令（9）调度引起缺页中断的进程，操作系统返回调用他的汇编语言例程
  （10）该例程恢复寄存器和其他信息，返回到用户空间继续执行，就好像缺页中断从未发生。

• 指令备份

  • 重新启动引起陷阱指令不是一件容易的事情
  • 解决方法：通过使用一个隐藏的内部寄存器，在每条指令执行之前，把程序计数器的内容复制到该寄存器，有些机器可能有第二个寄存器，用来提供哪些寄存器已经自动增加或者自动减少以及增减的数目等信息。

• 锁定内存中的页面

  • 虚拟内存和 IO 通过微妙的方式相互作用着
  • 设想一个进程正在等待I/O完成，然后被调度器挂起，另一个进程被允许运行，而这个进程产生了一个缺页中断，如果分页算法是全局算法，那么包含I/O缓冲区的页面是有可能被换出内存的，这当然不是等待I/O的进程所期待的
  • 解决方法：锁住正在做I/O操作的内存中的页面，以保证它不会被移出内存，叫做在内存中钉住（pinning）页面
  • 还有一种方法：在内核缓冲区完成所有I/O操作，然后再将数据复制到用户页面

• 后备存储

  • 问题：当页面被换出时会存在磁盘上的哪个位置。
  • 一个简单的算法：在磁盘上设置特殊的交换分区，甚至从文件系统划分一块独立的磁盘。
  • 进程启动前必须初始化交换分区，一种办法是将整个进程映像复制到交换区，一种方法是将整个进程装入内存中
  • 另一个极端情况：事先什么也不分配，在页面换出时为其分配磁盘空间，并在换入时回收磁盘空间，这样内存中的进程就不需要任何交换空间
  • 不能总保证能够实现固定的交换分区

• 策略和机制的分离

  • 通过使大多数存储管理器作为用户级进程运行，就可以把该项原则应用到存储管理器中

  • 优点：有更多的模块化代码和更好的适应性

  • 缺点：由于多次交叉用户 - 内核边界引起的额外开销，以及系统模块间信息传递所造成的额外开销

    

分段

• 多个独立地址空间比一个好

• 每个区的大小变化不一致，需要一种令程序员不用管理表扩张和收缩的办法，一个通用的办法是提供多个相互独立的段（segment），段由一个从0到最大线性地址序列构成

• 分段存储管理，每一个段都可以独立地增大或减小而不会影响其他的段

• 段是一个逻辑实体，一般不会包含多种不同类型的内容

• 段的优点：（1）简化数据结构管理 （2）方便过程的链接 （3）有助于在几个进程之间共享过程和数据

  

• 分段和分页本质不同：页面是定长而段不是

• 系统运行一段时间后，内存被划分为许多块，一些块包含着段，一些则成了空闲区，这种现象称为棋盘形碎片或外部碎片（external fragmentation），空闲区的存在使内存被浪费了，这可以通过内存紧缩来解决

习题

1. 在一个交换系统中，按内存地址排列的空闲区大小是：10KB、4KB、20KB、18KB、7KB、9KB、12KB和15KB，对于连续的段请求：a）12KB；b）10kb；c）9KB。使用首次适配算法，将找出哪个空闲区？最佳适配呢？最差适配呢？下次适配呢？

   First fit takes 20 KB, 10 KB, 18 KB. Best fit takes 12 KB, 10 KB, and 9 KB.
   Worst fit takes 20 KB, 18 KB, and 15 KB. Next fit takes 20 KB, 18 KB, and 9KB.

2. 对于下面十进制虚拟地址，分别使用4KB页面和8KB页面计算虚拟页号和偏移量：20000，32768，60000

   For a 4-KB page size the (page, offset) pairs are (4, 3616), (8, 0), and (14,
   2656). For an 8-KB page size they are (2, 3616), (4, 0), and (7, 2656).

   4KB页面的大小就是4096，8KB页面大小就是8192，用十进制虚拟地址除以4096or8192，所得的商就是虚拟页号，余数就是偏移量

3. 一个机器有32位地址空间和8KB页面，页表完全用硬件实现，页表的每一项为一个32位字。进程启动时，以每个字100ns的速度将页表从内存复制到硬件中，如果每个进程运行100ms（包含装入内存的时间），用来装入页表的CPU时间比例是多少？

   The page table contains 2^32 /2^13 entries, which is 524,288=2^19. Loading the page table takes 52 msec. If a process gets 100 msec, this consists of 52 msec for loading the page table and 48 msec for running. Thus 52% of the time is spent loading page tables.

   页大小为 8KB，所以页内地址为 13 位，故页框有 19 位，可表示的物理空间有 219 个页框。只考虑单进程，运行之前把所有页框复制到硬件的时间为 219×100ns=52.42ms，故装入页表的时间比例为 52.4288/100×100%=52.42%。

4. 假设一个机器有 38 位的虚拟地址和 32 位的物理地址。

   ​ a) 与一级页表比较，多级页表的主要优点是什么？

   ​ b) 一个有 16KB 个页、4 字节表项的二级页表，应该对第一级页表域分配多少位，对第二级页表域分配多少位？请解释原因。

   (a) A multilevel page table reduces the number of actual pages of the page table that need to be in memory because of its hierarchic structure. In fact, in a program with lots of instruction and data locality, we only need the top-level page table (one page), one instruction page and one data page.

   (b) 共有2^14=16KB个页，而机器的虚拟地址为38位，所以2^38/2^14 = 2^24，故页面长度为 2^24，需要 24 位偏移量，而二级页表的表项为 4 字节，故 PT2 = 2 ，所以 PT1 = 38 - 2 - 24 = 12，因此，对第一级页表域分配 12 位，对第二级页表分配域 2 位。

5. 一个32位地址的计算机使用两级页表，虚拟地址被分为9位的顶级页表域、11位的二级页表域和一个偏移量，问页面大小是多少？在地址空间中一共有多少个页面？

   Twenty bits are used for the virtual page numbers, leaving 12 over for the offset. This yields a 4-KB page. Twenty bits for the virtual page implies 2^20 pages

6. 假设一个32位虚拟地址被分为a、b、c、d四个域，前三个域用于一个三级页表系统，第四个域d是偏移量。页面数与这四个域的大小都有关系吗？如果不是，有哪些因素有关以及与哪些因素无关？

   The number of pages depends on the total number of bits in a, b, and c combined. How they are split among the fields does not matter.

   页面数=2^(bit_of_a+bit_of_b+bit_of_c)

7. 假设虚拟页码索引流中有一些长的页码索引序列的重复，序列之后有时会是一个随机的页码索引。例如，序列 0，1，…，511，431，0，1，…，511，332， 0，1，… 中就包含了 0，1，…，511 的重复，以及跟随在它们之后的随机页码索引 431 和 332。

   a) 在工作负载比该序列短的情况下，标准的页面置换算法（LRU，FIFO，Clock) 在处理换页时为什么效果不好？

   ​ b) 如果一个程序分配了 500 个页框，请描述一个效果优于 LRU、FIFO 或 Clock 算法的页面置换方法

   .
   (a) Every reference will page fault unless the number of page frames is 512,the length of the entire sequence.
   (b) If there are 500 frames, map pages 0–498 to fixed frames and vary only one frame.

   a) 标准的页面置换算法是针对已经在内存中的页面研究的。当工作负载比序列短时，会出现内存容量不够而长生颠簸，这种情况下 LRU、Clock、FIFO 算法达不到预期的效果。

8. 如果将 FIFO 页面罝换算法用到 4 个页框和 8 个页面上，若初始时页框为空，访问字符串为 0172327103，请问会发生多少次缺页中断？如果使用 LRU 算法呢？

   操作系统为每个进程维护一条链表，链表的每个结点记录一张页面的地址。调用一次页面，则把该页面的结点从链中取出，放到链尾；要装入新页，则把链头的页面调出，同时生成调入页面的结点，放到链尾。

   下面答案要竖着看，从左往右看，x代表的就是链表的值

   The page frames for FIFO are as follows:
   x0172333300
   xx017222233
   xxx01777722
   xxxx0111177
   The page frames for LRU are as follows:
   x0172327103
   xx017232710
   xxx01773271
   xxxx0111327
   FIFO yields six page faults; LRU yields seven.

   具体计算方法可参考这篇文章：FIFO、LRU、OPT 这三种置换算法的缺页次数

9. 考虑图 3- 15b 中的页面序列。假设从页面 B 到页面 A 的 R 位分别是 11011011。 使用第二次机会算法，被移走的是哪个页面？

   

   将选择 R 位为 0 第一页，在这种情况下为 D。

10. 一台小计算机有 4 个页框。在第一个时钟滴答时 R 位是 0111（页面 0 是 0，其他页面是 1），在随后的时钟滴答中这个值是 1011、1010、1101、0010、1010、 1100、0001。如果使用带有 8 位计数器的老化算法，给出最后一个滴答后 4 个计数器的值。

    The counters are
    Page 0: 0110110
    Page 1: 01001001
    Page 2: 00110111
    Page 3: 10001011

    竖着写，按时间顺序从右往左写

11. 请给出一个页面访问序列，其第一个被选择置换的页面必须不同于 Clock 和 LRU 算法。假设一个进程分配了 3 个页框，访问串中的页号属于集合 0，1，2，3

    The sequence: 0, 1, 2, 1, 2, 0, 3. In LRU, page 1 will be replaced by page 3. In clock, page 1 will be replaced, since all pages will be marked and the cursor is at page 0.

12. 在图 3-21c 的工作集时钟算法中，表针指向那个 R = 0 的页面。如果 τ=400，这个页面将被移出吗？如果 τ= 1000 呢？

    

    The age of the page is 2204 − 1213 = 991. If τ = 400, it is definitely out of
    the working set and was not recently referenced so it will be evicted. The
    τ = 1000 situation is different. Now the page falls within the working set
    (barely), so it is not removed.

13. 

    NRU removes page 2. （从类编号最低的页面中随即地抽取一个页面）

    FIFO removes page 3. （最早装入的是页面3，所以最先出）

    LRU removes page 1. （置换未使用时间最长的页面）

    Second chance removes page 2.（最早装入的是页面3，但是R=1；次早的是页面0，但是R=1；次次早的是页面2，R=0，所以换出）

ch6 死锁（deadlock）

• 在很多应用中，需要一个进程排他性地访问若干种资源而不是一种，容易造成死锁。
• 死锁也有可能发生在机器之间。 加锁过程也会产生死锁。 所以，软硬件都有可能死锁。

资源

• 需要排他性使用的对象称为资源，可以是硬件设备或是一组信息，简单来说，资源就是随着时间推移，必须能够获得、使用以及释放地任何东西。

• 可抢占资源（preemptable resource）：可以从拥有它的进程中抢占而不会产生任何副作用，如打印机和内存资源

• 不可抢占资源（nonpreemptable resource）：在不引起相关地计算失败地情况下，无法把它从占有它的进程处抢占过来（如刻盘），和死锁有关

• 死锁和不可抢占资源有关，有关可抢占资源的潜在死锁通常可以通过在进程之间重新分配资源而化解。资源是否可抢占取决于上下文环境

• 使用一个资源所需要的时间顺序：
  （1）请求资源 （2）使用资源 （3）释放资源

• 若请求资源不可用，则请求进程被迫等待，在一些OS中，资源请求失败时进程会自动被阻塞，在资源可用时再唤醒，而在其他OS中，资源请求失败会返回一个错误代码

• 通过初始值为1的信号量配置每一个资源，当两个进程想获得两个资源时，有这样两种编码风格，a）相同次序请求资源、b)不同次序请求资源

  

  对于a)，其中一个进程先获得资源，这个进程能够成功地获得第二个资源并完成它的任务，如果另一个进程想在第一个资源被释放之前获取该资源，那么它会由于资源加锁而被阻塞，直到该资源可用为止

  对于b)，可能一个进程获取了两个资源并成功阻塞了另一个进程，也有可能进程A获取了资源1，进程B获取了资源2，每个进程都想请求所缺的另一个资源，相互阻塞，这就是死锁

死锁概述

• 规范定义：如果一个进程集合中地每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么，该进程集合就是死锁

• 最常见的就是资源死锁（resource deadlock）

• 资源死锁的四个必要条件，死锁发生时，这四个条件一定同时满足
  （1）互斥条件，每个资源要么已经分配给了一个进程，要么就是可用的
  （2）占有和等待条件，已经得到某个资源的进程可以再请求新的资源
  （3）不可抢占条件，已经分配给一个进程的资源不可被抢占
  （4）环路等待条件，死锁发生时，一定有由两个或以上的进程组成的环路
  通过破坏上述条件就可以预防死锁

• 死锁建模

  方形代表资源，圆形代表进程 ，资源指向进程代表分配，进程指向资源代表请求

  

  假设有三个进程ABC和三个资源RST，下面这张图a-j展示了死锁是如何产生的， k-q展示了死锁是如何避免的

  

  对于一个可能会引起死锁的资源请求，OS可以干脆不批准该请求，并把该进程挂起，这样死锁就避免了，当q执行完后，就可以把资源S分配给B了。

  资源分配图中出现环路证明有死锁，反之没有。

  处理死锁的策略：
  （1） 忽略该问题
  （2）检测死锁并恢复
  （3）仔细对资源进行分配，动态地避免死锁。
  （4）通过破坏引起死锁的四个必要条件之一，防止死锁的产生

鸵鸟算法

• 最简单的解决办法是鸵鸟算法，把头买到沙子里，假装根本没有问题发生:0

死锁检测和死锁恢复

• 不试图阻止死锁的发生，而是允许死锁发生，当检测到死锁发生时采取措施进行恢复

• 每种类型一个资源的死锁检测

  • 每种资源类型只有一个资源
  • 简单方法：资源分配图里面找环
  • 比如下图的7个进程6个资源的资源分配图，可以看到存在环，有死锁

  

• 每种类型多个资源的死锁检测P250

  有多种相同的资源存在
  基于现有资源向量、可用资源向量、当前分配矩阵、请求矩阵

• 从死锁中恢复

  • 利用抢占恢复
  • 利用回滚恢复
    • 可以周期性地对进程进行检查点检查（checkpointed），进程检查点检查就是将进程的状态写入一个文件以备以后重启
    • 一旦检测到死锁，就很容易发现需要哪些资源，从一个较早的检查点上开始，这样拥有所需要资源的进程会回滚到一个时间点
    • 检查点之后的输出必须丢弃
  • 通过杀死进程恢复
    • 最直接的也是最简单的办法，杀死环中的一个进程，如果还不行，继续杀死别的进程直到打破死锁

死锁避免

• 保证在安全的条件下分配资源从而避免死锁

• 资源轨迹图

  • 使轨迹不进入死锁区域

  

• 安全状态和不安全状态

  • 如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的
  • 不安全状态并不是死锁，不安全状态还是可以运行一段时间的，甚至有的进程也许可以完成任务
  • 安全与不安全状态的区别就在于：从安全状态出发，系统能够保证所有进程都能完成；而从不安全状态出发，就没有这样的保证

• 单个资源的银行家算法（banker’s algorithm）

  • 判断请求的满足是否会导致进入不安全状态，如果是，则拒绝请求，如果满足请求后系统仍然是安全的，就予以分配 ；若否，就推迟对这一请求的满足

  

• 多个资源的银行家算法

  

  

死锁预防

• 死锁避免从本质上来说是不可能的，因为它需要获知未来的请求，而这些请求是不可知的，回顾死锁产生的四个必要条件，只要有一个不成立，那么死锁将不会发生

• 破坏互斥条件

  • 如果一个资源不被一个进程所独占，那么死锁肯定不会发生
  • 假脱机打印机（spooling printer），只有守护进程使用物理打印机
  • 避免分配那些不是绝对必需的资源，尽量做到尽可能少的进程可以真正请求资源

• 破坏占有和等待条件

  • 禁止已持有资源的进程再等待其他资源，规定所有进程在开始执行前请求所需的全部资源，如果全部资源可用，则全部分配给这个进程，否则该进程等待
  • 但实际上很多进程直到运行时才知道需要多少资源，而且，如果进程能够知道它需要多少资源，完全可以使用银行家算法
  • 另一个问题是，这种方法的资源利用率不是最优的
  • 略有不同的方案：当一个进程请求资源时，先暂时释放其当前占用的所有资源，然后再尝试一次获取全部所需资源

• 破坏不可抢占条件

  • 抢占
  • 虚拟化

• 破坏环路等待条件

  • 将所有资源统一编号，进程可以随时提出资源请求，但必须要按照资源编号的顺序提出，这样就不会出现环
  • 变种：摒弃必须按升序请求资源的限制，而仅仅要求不允许进程请求比当前所占有资源编号低的资源
  • 尽管对资源编号的方法消除了死锁问题，但几乎找不出一种使每个人都满意的编号次序

  

其它问题

• 两阶段加锁（two-phase locking）

  • 第一阶段：进程试图对所有所需的记录进行加锁，一次锁一个记录
  • 第二阶段：若第一阶段成功，完成更新然后释放锁

• 通信死锁（communication deadlock）

  • 两个或两个以上的进程发送消息来通信，A向B发送请求信息，然后阻塞直至B回复，假设请求信息丢失，B将会一直阻塞等待一个请求，因此发生死锁
  • 超时技术经常用来中断通信死锁，联想一下TCP三次握手、四次挥手

• 活锁（livelock）

  • 活锁指的是任务或者执行者没有被阻塞，由于某些条件没有满足，导致一直重复尝试，失败，尝试，失败，CPU一直被占用，但是没有取得任何进展
  • 比如行人互相让路导致堵塞
  • 活锁有可能自行解开，死锁则不能
  • 下图为作者介绍活锁的例子，到底是死锁还是活锁呢？网上也有不同的声音

  

• 饥饿（starvation）

  • 有一些不是死锁的进程永远得不到服务

  • 解决方案：处理最老的文件（先来先服务）

习题

1. 发生死锁有四个必要条件，为什么这四个条件不是充分条件？试举例说明

   Suppose that there are three processes, A, B and C, and two resource types, R and S. Further assume that there are one instance of R and two instance of S. Consider the following execution scenario: A requests R and gets it; B requests S and gets; C requests S and gets it (there are two instances of S); B requests R and is blocked; A requests S and is blocked. At this stage all four conditions hold. However, there is no deadlock. When C finishes, one in stance of S is released that is allocated to A. Now A can complete its execution and release R that can be allocated to B, which can then complete its execution.

   These 4 conditions are enough if there is 1 resource of each type.（当每种资源只有一个时，这四个条件是充分的）

   

2. 资源分配图是否存在不合理的结构，使得在结构上违反了使用资源的模型？

   Yes, illegal graphs exist. We stated that a resource may only be held by a
   single process. An arc from a resource square to a process circle indicates that the process owns the resource. Thus a square with arcs going from it to two or more processes means that all those processes hold the resource, which violates the rules. Consequently, any graph in which multiple arcs leave a square and end in different circles violates the rules unless there are multiple copies of the resources. Arcs from squares to squares or from circles to circles also violate the rules.

3. 给出一个实例：发生死锁的资源分配图中，存在一个进程不在环路中

   Consider three processes, A, B and C and two resources R and S. Suppose A is waiting for I that is held by B, B is waiting for S held by A, and C is waiting for R held by A. All three processes, A, B and C are deadlocked. However, only A and B belong to the circular chain.

   可以看到，这种模型中每种资源只有一个，所以会产生死锁，与第一题区别

   

4. 资源轨迹图能否说明三个进程和三个资源的死锁问题？

   Yes. Do the whole thing in three dimensions. The z-axis measures the number of instructions executed by the third process.

5. 考虑银行家算法，当进程P请求资源R时，即使R可用也拒绝了P的请求，这是否意味着当前情况下如果同意R分配给P会导致死锁？

   No. An available resource is denied to a requesting process in a system using the banker’s algorithm, if there is a possibility that the system may deadlock by granting that request. It is certainly possible that the system may not have deadlocked if that request was granted.

6. 银行家算法的一大限制就是需要知道所有进程的最大资源需求的信息，有没有可能设计一个不需要这些信息而避免死锁的算法？解释你的方法

   Other than forcing a sequential execution of processes, it is not possible to avoid deadlocks if the information about the maximum resource needs of all processes is not available in advance. Consider the example of two processes that want to record a scanned document on a CD-ROM. When process B requests the CD-ROM recorder, it is impossible to determine if granting this request will lead to an unsafe state, because it is not known if A will need the CD-ROM recorder later and B will need the scanner later.

   除非能保证进程顺序执行，否则无法避免死锁

7. 对于银行家算法，如图的b场景，如果D再多请求1个单位，会导致安全状态还是不安全状态？如果是C呢？

   A request from D is unsafe, but one from C is safe.

   ？？？

   感觉答案正好搞反了，C多请求一个，那C就会缺3，但空闲只有2，就算把空闲的2个全分配给C也无法满足，而其他的进程也同理，所以是不安全状态

   D多请求一个，银行家还是可以拖延除C以外的贷款请求，先把C缺的2个满足，然后C会释放4个，再满足BorD，完成后再释放，这样就皆大欢喜了，于是是安全状态

   

8. 两个进程，三个相同的资源，每个进程最多需要两个资源，问有无可能产生死锁

   The system is deadlock free（无死锁）. Suppose that each process has one resource. There is one resource free. Either process can ask for it and get it, in which case it can finish and release both resources. Consequently, deadlock is impossible.

9. 继续考虑上一问题，资源类型相同，假设有p个进程，每个最多需要m个资源，并且有r个资源可用

   If a process has m resources it can finish and cannot be involved in a deadlock. Therefore, the worst case is where every process has m − 1 resources and needs another one. If there is one resource left over, one process can finish and release all its resources, letting the rest finish too. Therefore the condition for avoiding deadlock is r ≥ p(m − 1) + 1.

10. 若保持该状态为安全状态，求x的最小值

    

    If x is 0, we have a deadlock immediately. If x is 1, process D can run to
    completion. When it is finished, the available vector is 1 1 2 2 1. Unfortunately we are now deadlocked. If x is 2, after D runs, the available vector is 1 1 3 2 1 and C can run. After it finishes and returns its resources the available vector is 2 2 3 3 1, which will allow B to run and complete, and then A to run and complete. Therefore, the smallest value of x that avoids a deadlock is 2.

11. 两个进程A和B，每个进程都需要数据库中的3个记录1、2、3。如果A和B都以1、2、3的次序请求，将不会发生死锁，但是如果B以3、2、1的次序请求，那么死锁就有可能发生。对于这三种资源，每个进程共有3!（即6种）次序组合，这些组合有多大的可能可以保证不会发生死锁

    Suppose that process A requests the records in the order a, b, c. If process B also asks for a first, one of them will get it and the other will block. This situation is always deadlock free since the winner can now run to completion without interference. Of the four other combinations, some may lead to deadlock and some are deadlock free. The six cases are as follows:

    a b c deadlock free
    a c b deadlock free
    b a c possible deadlock
    b c a possible deadlock
    c a b possible deadlock
    c b a possible deadlockSince four of the six may lead to deadlock, there is a 1/3 chance of avoiding a deadlock and a 2/3 chance of getting one.

12. 

    To avoid circular wait, number the resources (the accounts) with their account numbers. After reading an input line, a process locks the lower-numbered account first, then when it gets the lock (which may entail waiting), it locks the other one. Since no process ever waits for an account lower than what it already has, there is never a circular wait, hence never a deadlock.

    回顾本章的死锁预防方法，其实就是要破坏死锁产生的四个条件，在电子交易系统中，破坏环路比较简单，只需要给每个账户编号优先级即可，这个编号只需要按照账户的号码来编写，所以不存在不公平的情况

13. 解释死锁、活锁、饥饿

    A deadlock occurs when a set of processes are blocked waiting for an event that only some other process in the set can cause.

    On the other hand, processes in a livelock are not blocked. Instead, they continue to execute checking for a condition to become true that will never become true. Thus, in addition to the resources they are holding, processes in livelock continue to consume precious CPU time.

    Finally, starvation of a process occurs because of the presence of other processes as well as a stream of new incoming processes that end up with higher priority that the process being starved. Unlike deadlock or livelock, starvation can terminate on its own, e.g. when existing processes with higher priority terminate and no new processes with higher priority arrive.

本文许多图来自于https://blog.csdn.net/qq_28897525，感谢作者！

本文落笔于 2019-03-11