1.引言

操作系统：

• 应用程序
• 资源管理器

特征：

• 并发：
• 共享
• 虚拟
• 异步

3.中断、异常和系统调用

操作系统和外部打交道的方式：中断、异常和系统调用

• 系统调用：应用程序主动向操作系统发出的服务请求
• 异常：非法指令或者其他原因导致当前指令执行失败（如：内存出错）后的处理请求
• 中断：来自硬件设备的处理请求

三者的区别：

• 源头：
  中断：外设
  异常：应用程序意想不到的行为
  系统调用：应用程序请求操作系统提供服务
• 响应方式：
  中断：异步
  异常：同步
  系统调用：同步或异步
• 处理机制：
  中断：持续，对用户应用程序是透明的
  异常：杀死或重新执行意想不到的应用程序指令
  系统调用：等待和持续

5 物理内存管理、连续内存分配

操作系统内存管理的目标：

• 抽象：逻辑地址空间
• 保护：独立地址空间，每个进程只能访问自己的地址空间
• 共享：访问相同的内存单元
• 虚拟化：更大的地址空间

操作系统内存的管理方式：

• 重定位
• 分段
• 分页
• 虚拟存储

地址空间定义：

• 物理地址空间：硬件支持的地址空间
• 逻辑地址空间：在CPU运行的进程看到的地址空间

连续内存分配和内存碎片：

• 连续内存分配：给进程分配一块不小于指定大小的连续的物理内存区域
• 内存碎片：空闲内存不能被利用
• 外部碎片：分配单元之间未利用的内存
• 内部碎片：分配单元内部的未被利用的内存，取决于分配单元大小是否要取整

连续内存分配：

• 动态分区分配：当程序被加载时，分配一个进程指定大小的可变分区（块、内存），分区的地址是连续的
  操作系统需要维护两个数据结构：所有进程的已分配的分区的地址和空闲分区的地址
  动态分区分配策略：最先匹配（空闲分区按照地址顺序排列，第一个可用的空间）、最佳匹配（空闲分区按大小排序，查找并使用不小于所需空间的最小空闲分区）、最差匹配（寻找尺寸不小于所需空间的最大空闲分区）

碎片整理：当所需的内存不够时，将剩余的空间进行拼接以得到更大的内存空间，以便满足进程的空间需求

• 紧凑：通过紧凑的方式来合并剩余空间（外部碎片）要求，所有的应用程序可以动态重定位
• 分区对换：通过抢占并回收处于等待状态进程的分区，以增大可用内存空间

6 物理内存管理 非连续内存分配

非连续内存分配的实现方式：

• 段式存储管理：段之间不连续，段内空间连续
• 页式存储管理：
  页帧：物理页面
  页面：逻辑页面
  页面到页帧的映射：通过页表来实现，实现逻辑地址到物理地址的转化

快表：

页表如果特别大后，会占用很大的存储空间，解决方法：

• 快表
• 多级页表
• 反置页表

8 虚拟存储

计算机系统通常会出现内存空间不够用的情况。解决方法：

• 覆盖：应用程序手动把需要的指令和数据保存在内存中
• 交换：操作系统自动把暂时不能执行的程序保存到外存中
• 虚拟存储：在有限的容量内存中，以页为单位自动装入更多更大的程序

覆盖技术：在较小的内存中运行较大的程序

• 方法：依据程序的逻辑结构，将程序划分为若干功能相对独立的模块；将不会同时执行的模块共享同一块内存区域

交换技术：增加正在运行或需要运行的程序的内存

• 实现方法：将暂时不能运行的程序放到外存，换出换入的基本单位是进程

虚拟存储技术：只把部分程序放到内存中，从而运行比物理内存大的程序，实现内存和外存之间的交换，从而获得更多的空闲内存空间

• 局部性原理：程序在执行过程中的一个较短的时期，所执行的指令地址和指令的操作数地址分别局限于一定区域

  • 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短的时期内
  • 空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近访问的数据都集中在一个较小的区域内
  • 分支局部性：一条跳转指令的两次执行，很可能跳到相同的内存位置

• 原理：

  • 装载 程序时，只将当前指令执行需要的部分页面或段装入内存
  • 指令执行中需要的指令或数据不在内存中（缺页或确段）时，处理器通知操作系统将相应的页面或段调入内存
  • 操作系统将内存中暂时不用的 页面或段保存到外存

• 实现方式：

  • 虚拟页式存储
  • 虚拟段式存储

• 基本特征：

  • 不连续性：物理内存分配非连续、虚拟地址空间使用非连续
  • 大用户空间：提供给用户的虚拟内存可大于实际的物理内存
  • 部分交换：虚拟存储只对部分虚拟地址空间进行调入和调出

9 置换算法

页面锁定：是指在页面置换过程中不能被换出的页面，也就是必须常驻内存的逻辑页面，通常包括操作系统的关键部分以及要求响应速度的代码和数据，通过也表中锁定的标志位来标识

置换算法评价的标准：页面置换次数越少，算法越好

置换算法分类：

• 局部页面置换算法：置换页面的选择范围仅限于当前进程占用的物理页面
• 全局页面置换算法：置换页面的选择范围是所有可能换出的物理页面

最优置换算法（OPT）：置换在未来最长时间不访问的页面

• 实现：缺页时，计算每个逻辑页面下一次访问的时间，选择未来最长时间不访问的页面。该方法不能实现，因为无法预料未来哪个页面什么时间访问，只能作为性能评价依据

先进先出算法（FIFO）：选择驻留时间最长的作为替换，无需动态的调整顺序

最近最久未使用算法（LRU）：选择最长时间未使用的页面作为置换

时钟页面置换算法（Clock）:仅对页面的访问情况进行大致统计

• 指针指向最先调入的页面

最不常用算法（LFU）：置换访问次数最小的页面

Blady现象：采用FIFO算法，可能出现分配的物理页面增加，缺页次数反而升高；LRU没有Belady现象

全局置换算法：局部置换算法没有考虑进程访存的差异

• 思路：给进程分类可变数目的物理页面，因为进程在不同阶段的需求是不同的
• 工作集：一个进程正在使用的逻辑页面集合
• 常驻集：在当前时刻，进程实际驻留在内存中的页面集合
• 工作集置换算法：换出不在工作集的页面；访存时，换出不在工作集的页面，更新访存链表；缺页时，换入页面
• 缺页率置换算法：（缺页率：缺页平均时间间隔的倒数）

抖动：进程物理页面少，不能包含工作集，造成大量缺页，频繁置换

负载控制：控制并发进程数

11 进程和线程

进程：一个具有独立功能的程序在一个数据集合上一次动态执行过程

进程是执行中的程序，进程= 程序 + 数据 + 进程控制块，进程是动态的，程序是静态的。

进程控制块：控制管理进程运行所需的信息的集合

• 进程控制块是进程存在的唯一标志，每个进程在操作系统中都有一个对应的进程控制块
• 进程创建时生成进程控制块，进程结束时，回收进程控制块

进程生命周期的划分：

• 创建、执行、等待、抢占、唤醒、结束
• 特别注意：进程的时间片用完后处于就绪状态
• 进程挂起：处在挂起状态的进程映像在磁盘上，目的是减少进程占用内存，挂起是将进程从内存转到外存
  等待挂起：进程在外存并等待某事件出现
  就绪挂起：进程在外存，但只要进入内存即可运行
• 进程状态的队列：就绪队列、等待队列

线程：是进程的一小部分，是进程中指令执行的最小单元，是CPU调度的基本单位

线程的三种实现方式：

• 用户线程：在用户空间实现
  通过一组用户级的线程库来完成线程的管理，包括线程的创建、终止、同步和调度
• 内核线程：在内核中实现
  由内核通过系统调用实现的线程机制，由内核完成线程的创建、终止和管理
• 轻量级进程：在内核中实现，支持用户线程
  一个进程可有一个或多个轻量级进程，每个轻权进程由一个单独的内核线程来支持。

17.同步和互斥

同步的三种方法（属于底层的硬件方法）：禁用中断、原子操作指令、软件方法

18.信号量与管程

信号量与管程是操作系统中提供的两种同步的方法（相当于对底层硬件方法的高层抽象，统一称为“锁”）

信号量：信号量是操作系统提供的一种协调共享资源访问的方法，操作系统是管理者，地位高于进程，信号量表示系统资源的数量。
信号量是一种抽象的数据类型，由一个整型变量和两个原子操作组成
P操作： 申请资源，整型变量减一；如果小于0进入等待状态
V操作： 释放资源，整型变量加一；如果小于等于0，唤醒一个等待进程

信号量的使用：

• 互斥访问
  每类资源设置一个信号量，初值为1
  必须成对使用P（）操作和V（）操作；
  P（）操作保证互斥访问临界资源
  V（）操作在使用后释放临界资源
  PV操作不能次序错误、重复或者遗漏

• 条件同步
  条件同步设置一个信号量，其初值为0
  
  线程A等待线程B执行完V()操作后，也就是将当前资源释放后才能执行接下来的N。

管程： 一种用于多线程互斥访问共享资源的程序结构

• 任何一个时刻只有一个线程执行管程代码
• 正在管程中的线程可临时放弃管程的互斥访问，等待事件出现时恢复
• 管程的使用：在对象/模块中，收集相关共享数据，定义共享数据的方法

管程由一个锁（控制管程代码的互斥访问），0个或者多个条件变量（管理共享数据的并发访问）组成，如果是0个条件变量等同于临界区。
条件变量是管程内部的等待机制：

• Wait()操作：将自己阻塞在等待队列中，唤醒一个等待者或者释放管程的互斥访问
• Signal()操作（释放操作）：将等待队列中的一个线程唤醒，如果等待队列为空，则等同空操作
  

20.死锁和进程通信

进程的通信机制：信号、管道、消息队列、共享内存。