• 网课资料: 王道计算机考研 操作系统
  • 对应笔记: lfool.gitbook.io

概述

功能

• 资源的管理者:
  • 处理器管理
  • 存储器管理
  • 文件管理
  • 设备管理
• 向上层提供服务:
  • GUI(图形化用户接口)
  • 命令接口
    • 联机/交互式命令接口【e.g. 终端命令】
    • 脱机/批处理命令接口【e.g. *.bat】
  • 程序接口【在程序中通过系统调用(广义指令)来使用程序接口】
• 对硬件机器的扩展

特征

• 并发【最基本】: 多个事件宏观上"同时"发生，但微观上交替发生。
  • 区别于并行【多个事件同时发生】
• 共享【最基本】: 系统中的资源可供内存中多个并发执行的进程共同使用
  • 共享方式
    • 互斥共享: 一个时间段内只允许一个进程访问某资源【e.g. 一个摄像头无法同时开两个视频】
    • "同时"共享: 允许一个时间段内多个进程"同时"访问对某资源【e.g. 给两个软件发一份文件】
• 虚拟: 把一个物理上的实体变为若干个逻辑上的对应物【e.g. 虚拟内存(空分复用技术)、虚拟处理器(时分复用技术)】
• 异步: 多个程序并发执行，但由于资源有限，进程的执行速度不可以预测

发展与分类

1. 手工操作阶段【纸带机】
2. 批处理阶段
   1. 单道批处理系统: 引入脱机输入输出技术，监督程序通过外围机将程序提前读入磁带，执行程序后写入另一个磁带
      • 读写过程大大加快
      • 每次只能处理完一个程序后再处理另一个，还是串行，浪费了IO时间
   2. 多道批处理系统(操作系统开始出现)
      • 可以实现"并发"执行，共享计算机资源，不浪费IO时间
      • 用户响应时间长，没有人机交互功能，用户提交自己的作业后只能等待计算机处理完成，中间不能控制自己作业的执行【e.g. 调试、输入参数】
3. 分时操作系统: 以时间片为单位轮流为各个用户/作业服务，各个用户通过终端与计算机交互
   • 用户请求可以被及时响应，解决了人机交互问题
   • 允许多个用户同时使用一台计算机，并且相互独立
   • 不能处理一些紧急的任务，循环地为每个用户/作业服务一个时间片，不区分任务的紧急性
4. 实时操作系统: 收到外部信号后能及时处理，并在严格的时限内完成事件
   • 分为硬实时【e.g. 自动驾驶】与软实时【e.g. 12306】
   • 能够优先响应一些紧急任务，某些紧急任务不需要时间片排队
5. 网络操作系统: 实现网络中各种资源的共享(如文件共享)和各台计算机之间的通信【e.g. Windows NT】
6. 分布式操作系统: 系统中各台计算机地位相同，任何工作都可以分布在这些计算机上，并行协同的完成任务
   • 特点: 分布性、并行性
7. 个人计算机操作系统

运行机制

• 内核程序 与 应用程序
• 特权指令 与 非特权指令
  • 应用程序如果使用特权指令会引发中断信号，操作系统会重新获取CPU控制权
• 内核态[核心态、管态] 与 用户态[目态]
  • 判断: 根据程序状态寄存器(PSW)中的某个标志位来判断
  • 转换: 操作系统内核可以通过特权指令设置PSW

中断和异常

广义上的中断:

• 作用: 让操作系统内核夺回CPU控制权【用户态转换为内核态】
• 类型:
  • 内中断[异常]: 与当前执行的指令有关，中断信号来源于CPU内部
    • e.g.:
      • 故障类(fault): 缺页故障
      • 终止类(abort):
        • 应用程序让CPU执行一个特权指令，CPU拒绝并发起内中断
        • CPU执行指令时出现ZeroDivisionError，也会引发内中断
      • 陷入类(trap): 陷入指令/访管指令【应用程序请求内核服务[e.g. 系统调用]】
  • 外中断[狭义上的中断]: 与当前执行的指令无关，中断信号来源于CPU外部
    • e.g.:
      • 时钟中断【依次实现并发】
      • I/O中断【e.g. 打印机】
• 原理:
  1. 检查中断信号:
     • 内中断: CPU执行指令时
     • 外中断: 每个指令周期末尾
  2. 中断处理: 不同的中断信号需要查询中断向量表，用不同的中断程序来处理

系统调用

• 定义: 操作系统给程序员提供的程序接口
• 使用: 可以直接使用，也可以通过高级语言的库函数间接使用【只有部分库函数需要系统调用】
• 需求: 凡是于共享资源有关的操作，都需要系统调用。e.g. Word与WPS先后打印文件，并行执行打印任务，这就需要实现对打印机资源的互斥访问，最简单的方法就是“系统调用”【让操作系统来管理打印机资源】

• 分类:

  • 设备管理: 设备的请求/释放/启动等
  • 文件管理: 文件的读/写/创建/删除等
  • 进程控制: 进程的创建/撤销/阻塞/唤醒等
  • 进程通信: 进程间的消息传递/信号传递等
  • 内存管理: 内存的分配/回收等

• linux系统的系统调用:

  1. 文件操作：open, close, read, write, lseek, fcntl等
  2. 进程控制：fork, execve, exit, wait, pipe等
  3. 网络通信：socket, connect, bind, listen, accept等
  4. 内存管理：brk, mmap, mprotect, munmap等
  5. 信号处理：signal, sigaction, kill, sigprocmask等
  6. 时间处理：time, clock_gettime, gettimeofday, sleep等
  7. 用户权限：getuid, getgid, geteuid, setuid等
  8. 系统信息：uname, sysinfo, gethostname等
  9. 系统调用：syscall等

系统调用也是操作系统提供服务的基础，为系统的正常运作和高效管理提供了保障。

操作系统的体系结构

体系结构图:

原语: 一种特殊的程序，具有原子性【必须一气呵成，不可被“中断”】，通过开中断、关中断两个特权指令来实现

大内核与微内核:

1. 只保留与硬件最紧密关系部分的叫做微内核
2. CPU状态转变的过程是有成本的，频繁变态会降低系统性能
3. 优缺点对比:
   • 大内核: 高性能；内核代码庞大、结构混乱、难以维护
   • 微内核: 内核功能少、结构清晰、方便维护；性能低

分层结构: 每层只能调用相邻的更低一层的接口

外核: 给用户进程分配不抽象的硬件资源，让用户进程可以更灵活的使用硬件资源

e.g.: 外核直接给程序分配物理地址空间，开发者可以根据经常访问的区域来优化程序性能，或者直接分配物理上连续的磁盘空间，从而降低磁头移动。

常见结构及其特点总结:

操作系统引导

含义: 开机时，如何让操作系统运行起来

步骤:

1. 开机后，CPU通上电，执行ROM引导程序【存储位置固定，包含硬件自检等】，读入磁盘的主引导程序(MBR)到主存
2. 根据MBR找到活动分区位置，并读入引导记录(PBR)
3. CPU执行PBR，找到根目录下的启动管理器
4. CPU执行启动管理器，完成开机

虚拟机

进程

进程管理

进程:

• 概念: 程序的一次执行过程
• 操作系统记录的进程信息: 进程ID(PID: Process ID)【开机后永远递增】、进程所属用户ID(UUID)、分配的资源【分配了多少内存、正在使用的I/O设备、正在使用的文件】、运行情况【CPU使用时间、磁盘的使用情况、网络流量使用情况】

• 进程实体(进程映像)的组成: 进程控制块(PCB: Process Control Block)、程序段、数据段

• 特征: 动态性、并发性、独立性、异步性、结构性

进程的状态与转换

进程的五种状态:

进程的状态转化:

进程的组织与控制

进程的组织方式:

• 链接【最常见】
• 索引

进程的创建:

进程的终止:

进程的阻塞和唤醒:

进程的切换:

进程通信

进程间通信(IPC, Inter-Process Communication)是指两个进程之间产生数据交互。

e.g., 知乎文章分享到微信

进程通信需要操作系统支持: 进程是分配系统资源的单位(包括内存地址空间)，因此各进程拥有的内存地址空间相互独立

共享存储

分类:

1. 基于存储区的共享: 操作系统在内存中划出一块共享存储区，数据的形式与存放位置都由通信进程控制，而不是操作系统。速度很快，是一种高级通信方式。
2. 基于数据结构的共享: 比如共享空间里只存放一个长度为10的数组，可以理解为一种特殊的全局变量【不局限于某个进程】。这种共享方式速度慢、限制多，是一种低级通信方式。

具体实现(Linux):

1. shm_open: 申请一片共享内存区
2. mmap: 将共享内存区映射到自己的虚拟地址空间

注意事项: 为了避免出错，各个进程对共享空间的访问应该是互斥的【通过操作系统提供的同步互斥工具】

消息传递

进程间的数据交换以格式化的消息(Message)为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

格式化的消息：消息头(发送进程ID、接受进程ID、消息长度等)+消息体

分类:

1. 直接通信方式: 消息发送进程要指明接收进程的ID

2. 间接通信方式(信箱通信方式): 通过“信箱”间接地通信

管道通信

定义: 特殊的共享文件(pipe文件)。本质是在内存中开辟一个大小固定的内存缓冲区。

特点:

1. 先进先出
2. 半双工通信
3. 互斥访问【通过操作系统实现】
4. 管道写满时，写进程阻塞；管道读空时，读进程阻塞
5. 由于管道中的数据一旦被读出就会消失，因此多进程同时读一个管道会导致混乱。解决方法：
   1. 一个管道允许多个写进程，一个读进程【官方】
   2. 允许多个读进程，但系统会让各个读进程轮流从管道中读数据【Linux】

线程概念/多线程模型

线程

线程的意义: 有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了"线程"，来增加并发度。【轻量级进程】

线程引入带来的变化:

线程的属性:

多线程模型

实现方式:

1. 用户级线程(User-Level Thread, ULT)【使用线程库来实现】
   • 优点: 用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
   • 缺点: 当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行
2. 内核级线程(Kernel-Level Thread, KLT)【操作系统支持的】
   • 一对一模型: 一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
     • 优点: 当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
     • 缺点: 一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
   • 多对一模型: 多个用户级线程映射到一个内核级线程。且一个进程只被分配线程。
     • 优点: 用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
     • 缺点: 当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行
   • 多对多模型: \(n\)用户级线程映射到m个内核级线程(\(n>=m\))。每个用户进程对应m个内核级线程。 克服了多对一模型并发度不高的缺点(一个阻塞全体阻塞)，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。

线程的状态与转换

线程的组织与控制

处理机调度

调度层次

作业: 一个具体的任务【用户向系统提交一个作业\(\approx\)用户让操作系统启动一个程序(启动了就叫一个进程)】

高级调度(作业调度): 按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。

低级调度(进程调度/处理机调度): 按照某种策略从就绪队列中选取一个进程，将处理机分配给它。

挂起(Suspended)状态: 内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列。

中级调度(内存调度): 按照某种策略决定将哪个处于挂起状态的进程重新调入内存。 一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

七状态模型: 根据进程的挂起态引入

注意"挂起"和"阻塞"的区别，两种状态都是暂时不能获得cpu的服务，但挂起态是将进程映像(状态和数据)调到外存去了，而阻塞态下进程映像还在内存中。

调度的时机、方式与过程

时机:

进程在操作系统内核程序临界区中不能进行调度与切换

• 临界资源: 一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
• 临界区: 访问临界资源的那段代码。
• 内核程序临界区: 一般是用来访问某种内核数据结构的，比如进程的就绪队列(由各就绪进程的PCB组成)。
• 普通程序临界区: 比如打印机IO资源。

方式:

• 非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
  • 实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统
• 剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。
  • 可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能(通过时钟中断)。适合于分时操作系统、实时操作系统。

"狭义的进程调度"与"进程切换"的区别

• 狭义的进程调度指的是从就绪队列中选中一个要运行的进程。(这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换)
• 进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。广义的进程调度包含了选择一个进程和进程切换两个步骤。

过程:

1. 对原来运行进程各种数据的保存
2. 对新的进程各种数据的恢复(如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块)

调度器/调度程序(scheduler)

工作时机:

• 创建新进程
• 进程退出
• 运行进程阻塞
• I/O中断发生(可能唤醒某些阻塞进程)

如果是支持内核级线程的操作系统，调度程序的处理对象是线程

闲逛进程: 没有其他就绪进程时，运行闲逛进程(idle)

• 优先级最低
• 可以是0地址指令，占一个完整的指令周期(指令周期末尾例行检查中断)
• 能耗低

调度算法的评价指标

• CPU利用率: CPU"忙碌"时间占总时间的比例
• 系统吞吐量: 单位时间内完成作业的数量
• 周转时间
  • 周转时间: 从作业被提交给系统开始，到作业完成为止的时间间隔，包括: 作业在外存后备队列上等待作业调度(高级调度)的时间、进程在就绪队列上等待进程调度(低级调度)的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间
  • 平均周转时间: 各作业周转时间之和/作业数
  • 带权周转时间: 作业周转时间/作业实际运行的时间
  • 平均带权周转时间: 各作业带权周转时间之和/作业数
• 等待时间: 进程/作业处于等待处理机状态时间之和【作业比处理机多考虑一个等待作业调度的时间】
• 响应时间: 指从用户提交请求到首次产生响应所用的时间

批处理系统的调度算法

饥饿: 某进程/作业长期得不到服务，如果一直得不到服务，还会"饿死"

抢占式与非抢占式:

• 非抢占式调度策略，只有运行进程阻塞或退出才触发调度程序工作。

• 抢占式调度策略，每个时钟中断或k个时钟中断会触发调度程序工作。缺点是上下文切换开销和进程中断带来的不确定性。

• 先来先服务(FCFS):

  • 算法思想: "公平"
  • 算法规则: 按照作业/进程到达的先后顺序进行服务
  • 算法场景: 用于作业调度时，考虑谁先到达后备队列；用于进程调度时，考虑谁先到达就绪队列
  • 是否可抢占: 非抢占式算法
  • 优缺点:
    • 优点: 公平、算法实现简单
    • 缺点: 排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，FCFS算法对长作业有利，对短作业不利
  • 是否会导致饥饿: 不会
• 短作业优先(SJF)/短进程优先(SPF):
  • 算法思想: 追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间
  • 算法规则: 最短的作业/进程优先得到服务(所谓"最短"，是指要求服务时间最短)
  • 算法场景: 作业调度或进程调度
  • 是否可抢占: SJF与SPF是非抢占式的，但也有抢占式的版本--最短剩余时间优先算法(Shortest Remaining Time Next, SRTN)
  • 优缺点:
    • 优点:
      • 在所有进程都几乎同时到达时，采用SJF/SPF调度算法的平均等待时间、平均周转时间最少
      • 抢占式的短作业/进程优先调度算法SRTN的平均等待时间、平均周转时间最少
    • 缺点:
      • "不公平"，对短作业有利，对长作业不利
      • 运行时间由用户提供，不一定真实，不一定能做到真正的短作业优先
  • 是否会导致饥饿: 长作业饥饿
• 高响应比优先(Highest Response Ratio Next, HRRN):
  • 算法思想: 要综合考虑作业/进程的等待时间和要求服务时间
  • 算法规则: 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务【响应比=(等待时间+要求服务时间)/要求服务时间】
  • 是否可抢占: 非抢占式的
  • 优越点:
    • 优点: 综合考虑了等待时间和运行时间(要求服务时间)
      • 等待时间相同时，要求服务时间短的优先(SJF的优点)
      • 要求服务时间相同时，等待时间长的优先(FCFS 的优点)
  • 是否会导致饥饿: 不会

这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统。

交互式系统的调度算法

分时操作系统更在意响应时间而不是周转时间

• 时间片轮转调度算法(Round-Robin, RR)
  • 算法思想: 公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
  • 算法规则: 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。【如果时间片过大，就会退化为FCFS，降低了响应时间；如果时间片太小，进程切换开销过大】
  • 算法场景: 用于进程调度(只有作业放入内存建立了相应的进程后，才能被分配处理机时间片)
  • 是否可抢占: 若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。
  • 优缺点:
    • 优点: 公平，响应快，适用于分时操作系统；
    • 缺点: 由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。
  • 是否会导致饥饿: 不会
• 优先级调度算法(Priority Scheduling Algorithm, PSA):
  • 算法思想: 随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
  • 算法规则: 每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程
    • 就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置
    • 根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种:
      • 可以从追求公平、提升资源利用率等角度考虑: 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级；如果某进程占用处理机运行了很长时间，则可适当降低其优先级；如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级
    • 优先级规则:
      • 系统进程优先级高于用户进程
      • 前台进程优先级高于后台进程
      • 操作系统更偏好I/O型进程(或称I/O繁忙型进程)
  • 算法场景: 既可用于作业调度，也可用于进程调度。【还可用于I/O调度】
  • 是否可抢占: 抢占式、非抢占式都有
  • 优缺点:
    • 优点: 用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
    • 缺点: 若源源不断地有高优先级进程到来，则可能导致饥饿
  • 是否会导致饥饿: 会
• 多级反馈队列调度算法(Multi-level Feedback Queue, MLFQ):
  • 算法思想: 对其他算法的折中权衡
  • 算法规则:
    1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
    2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾。
    3. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片。
  • 算法场景: 进程调度
  • 是否可抢占: 抢占式。在k级队列的进程运行过程中，若更上级的队列(1~k-1级)中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。
  • 优点:
    • 对各类型进程相对公平(FCFS的优点)
    • 每个新到达的进程都可以很快就得到响应(RR的优点)
    • 短进程只用较少的时间就可完成(SPF的优点)
    • 不必实现估计进程的运行时间(避免用户作假)
    • 可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程【可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级】
  • 是否会导致饥饿: 会
• 多级队列调度算法:
  • 队列之间可采取固定优先级，或时间片划分
    • 固定优先级: 高优先级空时低优先级进程才能被调度【其实不合理】
    • 时间片划分: 如三个队列分配时间50%、40%、10%
  • 各队列可采用不同的调度策略，如:
    • 系统进程队列采用优先级调度
    • 交互式队列采用RR
    • 批处理队列采用FCFS

进程同步与互斥

进程同步:

进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。因此，操作系统要提供"进程同步机制"来实现某种特定的进程处理顺序。

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

进程互斥:

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。

互斥访问的实现逻辑:

• 进入区: 负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志(可理解为"上锁")，以阻止其他进程同时进入临界区
• 临界区/临界段: 访问临界资源的那段代码
• 退出区: 负责解除正在访问临界资源的标志(可理解为"解锁")
• 剩余区: 做其他处理

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则:

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
2. 忙则等待。当己有进程进入临界区时，其他试图进入临界区的进程必须等待；
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)；
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

软件实现方法

• 单标志法
  • 算法思想: 两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。
    • 该算法
    • turn变量背后的逻辑: 谦让
  • 算法分析:
    • 只能允许轮流访问，违反空闲让进原则。
    • 可以实现"同一时刻最多只允许一个进程访问临界区"
• 双标志先检查
  • 算法思想: 设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如flag[0]=true意味着0号进程PO现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[0]设为true，之后开始访问临界区。
  • 算法分析:
    • 违反了"忙则等待"原则【"检查"和"上锁"不是一气呵成的，中间可能发生进程切换】
• 双标志后检查
  • 算法思想: 双标志先检查法的改版。前一个算法的问题是先"检查"后"上锁"，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先"上锁"后"检查"的方法，来避免上述问题。
  • 算法分析:
    • 遵循了"忙则等待"
    • 违背了"空闲让进"和"有限等待"
• Peterson 算法
  • 算法思想: 结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以做谦让。
  • 算法分析:
  • 遵循了空闲让进、忙则等待、有限等待
  • 违反了让权等待

硬件实现方法

• 中断屏蔽方法
  • 算法思想: 利用"开/关中断指令"实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)
  • 算法分析:
    • 优点: 简单、高效
    • 缺点:
      • 不适用于多处理机
      • 只适用于操作系统内核进程，不适用于用户进程(开/关中断指令只能运行在内核态)
• TestAndSet(TS指令)/TestAndSetLock(TSL指令)
  • 算法思想: (TSL指令是用硬件实现的) 相比软件实现方法，把"上锁"和"检查"操作用硬件的方式变成了一气呵成的原子操作。
  • 算法分析:
    • 优点:
      • 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞
      • 适用于多处理机环境
    • 缺点: 不满足"让权等待"原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令
• Swap指令/XCHG指令
  • 算法思想: 类似TS指令...
  • 算法分析: 类似TS指令...

互斥锁

解决临界区最简单的工具就是互斥锁(mutex lock)。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数acquire()获得锁，而函数release()释放锁。每个互斥锁有一个布尔变量available，表示锁是否可用。如果锁是可用的，调用acquire()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。

• 自旋锁(spin lock): TSL指令、swap指令
  • 缺点: 循环忙等【当资源不可用时需要循环调用acquire()】，违反让权等待
  • 优点: 等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低。常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区。【不太适用于单处理机系统，忙等的过程中不可能解锁】
• 读写锁(Read-Write Lock): 也被称为共享-互斥锁。它允许多个线程同时读取共享资源，但只允许一个线程写入共享资源。这样可以提高并发性，因为多个线程可以同时读取，而写操作需要互斥执行。

信号量

目前的进程互斥方法存在的问题:

1. 软件方法中，进入区的"检查"、"上锁"操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题
2. 所有的解决方案都无法实现"让权等待"

信号量机制: 用户进程可以通过使用操作系统提供的一对原语(wait(S), signal(S))来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

wait、signal原语常简称为P、V操作(来自荷兰语 proberen 和 verhogen)。因此，做题的时候常把wait(S)、signal(s)两个操作分别写为P(S)、V(S)。

整型信号量: 用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。

• 只支持初始化、P操作、V操作 逻辑上跟双标志先检查的先检查后上锁一样
• 不满足"让权等待"，会存在忙等现象
• 原语既然不可以被中断，那这个while不就退不出了

记录型信号量: 用记录型数据结构表示(一个等待队列+一个整型信号量)

• 遵循了"让权等待"原则，不会忙等
• 可以实现真正的进程互斥、进程同步

信号量机制实现进程互斥:

1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
2. 设置互斥信号量mutex，初值为1(semaphore代表记录型信号量)
3. 在进入区P(mutex)一一申请资源
4. 在退出区V(mutex)一一释放资源

信号量机制实现进程同步:

1. 分析什么地方需要实现"同步关系"，即必须保证"一前一后"执行的两个操作
2. 设置同步信号量S，初始为0
3. 在"前操作"之后执行V(S)
4. 在"后操作"之前执行P(S)

信号量机制实现前驱关系:

经典问题

解题思路:

1. 关系分析: 找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
2. 整理思路: 根据各进程的操作流程确定P、V操作的大致顺序。
3. 设置信号量: 设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)

关键点:

1. 实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起"死锁"
2. 如果缓冲区大小大于1，就必须设置一个互斥信号量mutex来保证互斥访问缓冲区
3. 如果一个进程需要同时持有多个临界资源的情况，应该分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。

经典问题:

1. 生产者-消费者问题: 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用【注：这里的"产品"理解为某种数据】。生产者、消费者共享一个初始为空、大小为n的缓冲区；只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待；缓冲区是临界资源，各进程必须互斥地访问。
   • 分析:
     • 缓冲区没满 -> 生产者生产
     • 缓冲区没空 -> 消费者消费
     • 各进程互斥访问缓冲区
   • 实现: P操作不可交换，会产生死锁；V操作可交换，因为V操作内没有block；要让临界区的代码尽可能短
2. 多生产者-多消费者问题(多类): 桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放革果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。
   • 分析:
     • 对缓冲区(盘子)的互斥访问
     • 父亲放入苹果 -> 女儿取出苹果
     • 母亲放入橘子 -> 儿子取出橘子
     • 只有盘子为空，父亲或母亲才能放入水果【资源】
   • 实现: 可以不实现mutex，是因为其他三个信号量中最多只有一个会是1，意味着最多只有一个进程的P操作不会被阻塞，并顺利进入临界区。
   • 复盘:
3. 吸烟者问题: 假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复(让三个抽烟者轮流地抽烟)。用PV操作实现上述过程。
   • 分析:
     • 桌上有组合一 -> 第一个抽烟者取走东西
     • 桌上有组合二 -> 第二个抽烟者取走东西
     • 桌上有组合三 -> 第三个抽烟者取走东西
     • 发出完成信号 -> 供应者将下一个组合放到桌上
   • 实现:
     • 精华: 如何实现"轮流": 整型变量取余
4. 读者写者问题: 有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求：
   1. 允许多个读者可以同时对文件执行读操作；
   2. 只允许一个写者往文件中写信息；
   3. 任一写者在完成写操作之前不允许其他读者或写者工作；
   4. 写者执行写操作前，应让己有的读者和写者全部退出。
   5. 分析:
      • 写进程与其他进程(写/读)互斥
   6. 实现:
      • 第一版: 存在漏洞--写进程会饿死
        • 其核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数。我们可以用count 的值来料断当前讲入的讲程是否是第一个/最后一个读进程，从而做出不同的处理。
        • 对count变量的检查和赋值不能一气呵成会导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。
      • 第二版: 实现了相对公平的先来先服务--"读写公平法"
5. 哲学家进餐问题: 一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭、哲学家们倾注毕生的精力用于想考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子己在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。
   • 分析:
     • 哲学家与其邻居对两者中间的筷子的访问是互斥的
     • 每个哲学家需要同时掌握两个临界资源(筷子)才能吃饭【可能会产生死锁】
   • 实现:
     • 第一版: 依次拿起左右的筷子--> 死锁
     • 第二版: 可以对哲学家进程施加一些限制条件:
       1. 最多允许四个哲学家同时进餐
       2. 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反
       3. 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。 这种实现方法让哲学家拿筷子变得互斥

管程

信号量机制存在的问题: 编写程序困难、易出错

组成部分:

1. 局部于管程的共享数据结构说明：
2. 对该数据结构进行操作的一组过程；
3. 对局部于管程的共享数据设置初始值的语句；
4. 管程有一个名字。

基本特征:

1. 局部于管程的数据只能被局部于管程的过程所访问；
2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
3. 每次仅允许一个进程在管程内执行某个内部过程。

思想: 封装

经典问题解法:

1. 需要在管程中定义共享数据
2. 需要在管程中定义用于访问这些共享数据的"入口"一一其实就是一些函数
3. 只有通过这些特定的"入口"才能访问共享数据
4. 管程中有很多"入口"，但是每次只能开放其中一个"入口"，并且只能让一个进程或线程进入【注意：这种互斥特性是由编器负责实现的，程序员不用关心】
5. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待[此时，该进程应先释放管程的使用权，也就是让出"入口"】；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

Java中的实现: 如果用关键字synchronized来描述一个函数，那么这个函数同一时间段内只能被一个线程调用。

死锁

现象: 哲学家进餐问题中使用"依次拿左右的筷子"就会出现

定义: 在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是"死锁"。发生死锁后若无外力干涉，这些进程都将无法向前推进。

饥饿: 由于长期得不到想要的资源，某进程无法向前推进的现象。 死循环: 某进程执行过程中一直跳不出某个循环的现象。

根本原因: 独占资源不足和资源分配不当

条件:

1. 互斥条件: 只有对必须互斥使用的资源的争抢才会导致死锁。
2. 不剥夺条件: 进程所获得的资源在未使用完之前，不能由其他进程强行夺定，只能主动释放。
3. 请求和保持条件: 进程己经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己己有的资源保持不放。
4. 循环等待条件: 存在一种进程资源的循环等待链，链中的每一个进程己获得的资源同时被下一个进程所请求。 > 发生死锁时一定有循环等待，但是发生循环等待时未必死锁(循环等待是死锁的必要不充分条件) > 循环等待+同类资源只有一个就必然死锁

时机:

1. 对系统资源的竞争。各进程对不可剥夺的资源(如打印机)的竞争可能引起死锁，对可剥夺的资源(CPU)的竟争是不会引起死锁的。
2. 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。
3. 信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。(可以把互斥信号量、同步信号量也看做是一种抽象的系统资源)

处理策略:

1. 预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
   • 破环互斥条件: 如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。例如，操作系统可以采用SPOOLing技术把独占式设备在逻辑上改造成共享设备。比如，用SPOOLing技术将打印机改造为共享设备...
     • 缺点: 并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。
   • 破坏不剥夺条件:
     • 方案:
       • 方案一: 当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。
       • 方案二: 当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。一般需要考虑各进程的优先级(比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用)
     • 缺点:
       • 实现起来比较复杂。
       • 释放己获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
       • 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
       • 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。
   • 破坏请求和保持条件: 可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。
     • 缺点:
       • 有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪贵，资源利用率极低。
       • 有可能导致某些进程饥饿。
   • 破坏循环等待条件: 可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源。【不会出现环】
     • 缺点:
       • 不方便增加新的设备，因为可能需要重新分配所有的编号
       • 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
       • 必须按规定次序申请资源，用户编程麻烦。
2. 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁(银行家算法)
   • 相关概念:
     • 安全序列: 指如果系统按照这种序列分配资源，则每个进程都能顺利完成。
     • 安全状态: 只要能找出一个安全序列，系统就是安全状态。【安全序列可能有多个】
     • 不安全状态: 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。【如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况，不安全状态时资源分配图一定不可完全化❌】
     • 如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁【处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态】
   • 银行家算法
     • 核心思想: 在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
     • 算法流程:
3. 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。
   • 死锁检测:
     • 需求:
       1. 用某种数据结构来保存资源的请求和分配信息；
       2. 提供一种算法，利用上述信息来检测系统是否己进入死锁状态。
     • 实现:
       • 数据结构: 资源分配图
         • 两种节点:
           • 进程结点: 对应一个进程
           • 资源结点: 对应一类资源，一类资源可能有多个
         • 两种边:
           • 进程结点->资源结点: 表示进程想申请几个资源(每条边代表一个)
           • 资源节点->进程结点: 表示已经为进程分配了几个资源(每条边代表一个)
       • 检测方法: 判断能否消除资源分配图上所有的边(相当于找到一个安全序列)，如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁(死锁定理)
   • 死锁解除:【并不是系统中所有的进程都是死锁状态，用死锁检测资源分配图后，还连着边的那些进程就是死锁进程】
     • 方法:
       • 资源剥夺法【防止饥饿】
       • 撤销进程法/终止进程法
       • 进程回退法【要求操作系统记录进程的历史信息，设置还原点】
     • 对象:
       • 进程优先级
       • 已执行多长时间
       • 还要多久能完成
       • 进程已经使用了多少资源
       • 进程是交互式的还是批处理式的

内存

内存管理基本概念

操作系统在内存管理中的责任:

1. 操作系统负责内存空间的分配与回收
   • 连续分配管理方式: 单一连续分配、固定分区分配、可变分区分配
   • 非连续分配管理方式: 基本分页存储管理、基本分段存储管理、段页式存储管理
2. 操作系统需要提供某种技术从逻辑上对内存空间进行扩充
   • 覆盖技术
   • 交换技术
   • 虚拟存储技术
3. 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换【通过装入】
4. 操作系统需要提供内存保护功能，保证各进程在各自存储空间内运行，互不干扰
   • 在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。
   • 采用重定位寄存器(又称基址寄存器)和界地址寄存器(又称限长寄存器)进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

从写程序到程序运行:

• 链接的三种方式:
  1. 静态链接: 在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件(装入模块)，之后不再拆开。
  2. 装入时动态链接: 将各目标模块装入内存时，边装入边链接的链接方式。
  3. 运行时动态链接: 在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享，提升内存的利用率。
• 装入内存: 装入程序(Loader)功能是将存储在外部存储器(如硬盘、固态硬盘)上的装入模块(可执行文件)加载到计算机的内存中，以便执行。
  • 关键: 如何把指令中的逻辑地址转换为物理地址【指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址】
  • 方法:
    1. 绝对装入: (早期) 编程/编译/汇编时生成绝对地址
    2. 可重定位装入(静态重定位): 根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行"重定位"，将逻辑地址变换为物理地址(地址变换是在装入时一次完成的)。
       • 在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。
       • 作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。
    3. 动态运行时装入(动态重定位): 装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。这种方式需要一个重定位寄存器的支持。
       • 可将程序分配到不连续的存储区中；
       • 在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存；
       • 便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。

内存空间的分配与回收

连续分配管理方式

连续分配: 指为用户进程分配的必须是一个连续的内存空间。 内部碎片: 分配给某进程的内存区域中有没用上的部分。 外部碎片: 是指内存中的某些空闲分区由于太小而难以利用。【可以用紧凑/拼凑(Compaction)技术解决，但需要较大的时间代价】

1. 单一连续分配: 在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。
   • 评价:
     • 优点: 实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护(e.g., 早期的PC操作系统 MS-DOS)。
     • 缺点: 只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。
2. 固定分区分配: 将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。【操作系统需要建立一个分区说明表(数组或链表)，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态(是否已分配)。】
   • 方案:
     • 分区大小相等: 缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合
     • 分区大小不等: 增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分(比如: 划分多个小分区、适量中等分区、少量大分区)
   • 评价:
     • 有点: 实现简单，无外部碎片
     • 缺点:
       • 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能
       • 会产生内部碎片，内存利用率低
3. 动态分区分配/可变分区分配: 不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。
   • 问题:
     1. 系统要用什么样的数据结构记录内存的使用情况？空闲分区表、空闲分区链【最好用链】
     2. 当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？
        • 首次适应算法(First Fit)
          • 思想: 每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
          • 实现: 空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
        • 最佳适应算法(Best Fit)
          • 思想: 优先使用更小的空闲区，方便大的空闲分区发挥作用。
          • 实现: 空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
          • 缺点: 会产生大量的外部碎片。
        • 最坏适应算法(Worst Fit)
          • 思想: 优先利用大的空闲区，这样剩余的空闲区不会太小，更方便利用。
          • 实现: 空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
          • 缺点: 会导致大分区快速消耗，让后来的大进程无分区可用。
        • 邻近适应算法(Next Fit)
          • 思想: 从上次查找结束的位置开始检索第一个适应的分区【应对首次适应算法带来的低地址部分小分区过多的问题(降低查找的开销)】
          • 实现: 空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
          • 缺点: 与FF相比，高地址部分的大分区会被消耗。
     3. 如何进行分区的分配与回收操作？【以表为例】
        • 分配: 删除表项、更新分区大小和起始地址
        • 回收: 增加表项、删除表项、更新分区大小和起始地址

非连续分配管理方式

基本分页存储管理:

• 分页:
  • 将内存空间分为一个个大小相等的分区(比如每个分区4KB)，每个分区就是一个"页框"(PageFrame, 页框=页帧=内存块=物理块=物理页面)。每个页框有一个编号，即"页框号"(页框号=页帧号=内存块号=物理块号=物理页号)，页框号从0开始。
  • 将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个"页"或"页面"。每个页面也有一个编号，即"页号"，页号也是从0开始。
  • 操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。
• 页表: 为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。【页表通常存在PCB中】
  • 内容: 页表中索引是页号，元素是块号
  • 位置: 通常会在系统中设置一个页表寄存器(PTR)，存放页表在内存中的起始地址F和页表长度M
    • 进程未执行时，页表的始址和页表长度放在进程控制块(PCB)中
    • 当进程被调度时，操作系统内核会把它们放到页表寄存器中
  • 存储: (实际应用中)为了方便将页表项的查询，需要让页面项的长度可以被页面大小整除【不会有页内碎片影响查询】
• 地址变换:【如果页面大小是2的整数次幂，就更方便对逻辑地址进行拆分和映射】
  1. 确定逻辑地址A对应的"页号"P: P=逻辑地址/页面长度
  2. 找到P号页面在内存中的起始地址(需要查页表)
  3. 确定逻辑地址A的"页内偏移量"W: W=逻辑地址%页面长度
  4. 逻辑地址A对应的物理地址=P号页面在内存中的起始地址+页内偏移量W
• 地址变换机构:
  • 基本地址变换机构:
    • 定义: 用于实现逻辑地址到物理地址转换的一织硬件机构)
    • 作用: 借助进程的页表将逻辑地址转换为物理地址
    • 实现:
    • 缺点: 访问一个地址需要访问两次内存【查页表一次，访问目标单元一次】
  • 具有快表的地址变换机构:
    • 概念:
      • 快表: 又称联想寄存器(TLB, translation lookaside buffer)，是一种访问速度比内存快很多的高速缓存(不是内存)，用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。
      • 局部性原理:
        • 时间局部性: 如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，很可能再次被访问。(因为程序中存在大量的循环)
        • 空间局部性: 一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)
    • 实现:
    • 优点: 一般来说快表的命中率可以达到90%以上，可以大大提高查找速度。
• 两级页表:
  • 单级页表的问题:
    • 页表连续存储: 需要为每个进程的页表准备的页框要占用太多的连续内存
    • 页表过大: 根据局部性原理可知，很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。
  • 解决方法:
    • 可将页表分组，使每个内存块刚好可以放入一个分组；然后用一个页目录表/顶级页表来记录每个页表分组所在的内存块号
    • 可以在需要访问页面时才把页面调入内存(虚拟存储技术)。可以在页表项中增加一个标志位，用于表示该页面是否己经调入内存。
  • 注意事项: 若采用多级页表机制，则各级页表的大小不能超过一个页面
  • 缺点:
    • 需要增加一次访存

基本分段存储管理:

• 分段:
  • 进程的地址空间: 按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名(在低级语言中，程序员使用段名来编程)，每段从0开始编址。
  • 内存分配规则: 以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。
  • 分段系统的逻辑地址结构由段号(段名)和段内地址(段内偏移量)所组成。段号的位数决定了每个进程最多可以分几个段；段内地址位数决定了每个段的最大长度是多少。
• 段表: 操作系统需要为每个进程建立一张段映射表(段表)来实现逻辑段到物理段的映射【每个段表项包含段号、段长、基址】。
• 地址交换:
• 分段VS分页:
  • 用途: 分页是为了提高内存利用率，分段是为了方便用户需求。
  • 可见性: 分页对用户不可见，分段对用户可见。
  • 大小: 页的大小固定且由系统决定，段的长度不固定且取决于用户编写的程序。
  • 地址: 分页的用户进程地址空间是一维的，分段的用户进程地址空间是二维的。
  • 分段比分页更容易实现信息的共享和保护:
    • 共享: 两个进程的段号指向同一块内存区域【只有纯代码可以共享】
    • 保护: 只需要在段表中添加一位"允许访问"标记位

段页式存储管理:

• 分段、分页优缺点分析
• 段页式管理: 逻辑地址由段号、页号、页内地址(页偏移量)组成
  • 这里的段表记录的是每个段对应的页表长度和页表存放块号
• 地址转换:

内存扩充技术

覆盖技术

思想: 将程序分为多个段(多个模块)。常用的段常驻内存，不常用的段在需要时调入内存。 内存中分为一个"固定区"和若干个"覆盖区": 需要常驻内存的段放在“固定区”中，调入后就不再调出(除非运行结束)；不常用的段放在"覆盖区"，需要用到时调入内存，用不到时调出内存。

评价: 必须由程序员声明覆盖结构，操作系统完成自动覆盖。缺点: 对用户不透明，增加了用户编程负担。只用于早期操作系统。

交换技术

思想: 内存空间紧张时，系统将内存中某些进程暂时换出外存(PCB会常驻内存，不会被换出外存)，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)【注意与中级调度(内存调度)的联系】

要点:

1. 应该在外存(磁盘)的什么位置保存被换出的进程? 具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。 文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式；对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式。总之，对换区的I/O速度比文件区的更快。
2. 什么时候应该交换? 交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如: 在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程；如果缺页率明显下降，就可以暂停换出。
3. 应该换出哪些进程? 可优先换出阻塞进程；可换出优先级低的进程；为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间。

虚拟内存技术

传统存储管理方式的特征、缺点:

• 一次性: 作业必须一次性全部装入内存后才能开始运行。
  • 大内存作业无法运行
  • 多道程序并发度下降
• 驻留性: 一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。
  • 很多暂时用不到的数据也会长期占用内存，导致内存利用率不高。

虚拟内存-定义: 基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。

与交换技术的区别: 交换技术是在内存紧缺时换出进程，而虚拟内存技术说的是换出页面。

特性:

• 多次性: 无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
• 对换性: 在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
• 虚拟性: 从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。

实现: 如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上。

• 请求分页存储管理
  • 页表机制:
    • 需求:
      • 操作系统需要知道每个页面是否己经调入内存：如果还没调入，那么也需要知道该页面在外存中存放的位置。
      • 当内存空间不够时，要实现"页面置换"，操作系统需要通过某些指标来决定到底换出哪个页面；有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。
    • 实现:
  • 缺页中断机构: 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。
    • 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
    • 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。
  • 地址变换机构:
    • 新增步骤1: 请求调页(查到页表项时进行判断)
    • 新增步骤2: 页面置换(需要调入页面，但没有空闲内存块时进行)
    • 新增步骤3: 需要修改请求页表中的表项
• 请求分段存储管理
• 请求段页式存储管理

---

在使用虚拟内存技术的情况下，进程不需要获得运行所需要的全内存空间，可以通过置换来实现运行，但这引出了两个新问题:

1. 假设给定了一些内存空间，运行时发现不够该置换哪些空间？
2. 既然不需要完全分配需要的内存，那分配多少合适？
3. 页面调入的时机和位置是怎样的？

页面置换算法: 追求更少的缺页率

• 最佳置换算法(Optimal, OPT): 每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。 由于进程无法预测访问的页面次序，所以最佳置换算法是无法实现的。
• 先进先出置换算法(FIFO): 每次选择淘汰的页面是最早进入内存的页面【队列的头，队列长度为内存块数】
  • Belady异常: 当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
  • 只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差。
• 最近最久未使用置换算法(least recently used, LRU): 每次淘汰的页面是最近最久未使用的页面【赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间】
  • 该算法虽然性能接近OPT，但实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大
• 时钟置换算法(CLOCK, Not Recently Used, NRU):
  • 简单的CLOCK算法: 为每个页面设置一个访问位，再将内存中的页面都通过链按指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。
    • 如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面。
    • 若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描【第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描】
  • 改进型的时钟置换算法:
    • 原理: 只有被淘汰的页面被修改过，才需要写回外存。因此应该优先淘汰没有修改过的页面。
    • 实现: 用(访问位、修改页)表示页面状态，将所有可能被置换的页面排成一个循环队列
      • 第一轮: 从当前位置开始扫描到第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位
      • 第二轮: 若第一轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换。本轮将所有扫描过的帧访问位设为0
      • 第三轮: 若第二轮扫描失败，则重新扫描，查找第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位
      • 第四轮: 若第三轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换。

页面分配、置换策略:

• 驻留集: 指请求分页存储管理中给进程分配的物理块的集合。在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。
  • 分析:
    • 若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；
    • 驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。
• 抖动(颠簸)现象:
  • 定义: 刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。
  • 原因: 进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够）
  • 工作集: 指在某段时间间隔里，进程实际访问页面的集合。
    • 根据窗口尺寸来算，工作集小说明进程的局部性好
    • 驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页
    • 基于局部性原理可知，进程在一段时间内访问的页面与不久之后会访问的页面是有相关性的。因此，可以根据进程近期访问的页面集合(工作集)来设计一种页面置换算法--选择一个不在工作集中的页面进行淘汰。
• 策略选项:
  • 分配策略:
    • 固定分配: 操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。
    • 可变分配: 先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。
  • 置换策略:
    • 局部置换: 发生缺页时只能选进程自己的物理块进行置换。
    • 全局置换: 可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。【全局置换的进程物理块必然会变】
• 策略组合:
  • 固定分配局部置换: 系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。
    • 很难在刚开始就确定应为每个进程分配多少个物理块才算合理【一般根据进程大小、优先级、或是根据程序员给出的参数来确定内存块数】
  • 可变分配全局置换: 刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程：若已无空闲物理块，则可选择一个未锁定(如内核数据可以设位被锁定)的页面换出外存，再将该物理块分配给缺页的进程。
    • 采用这种策略时，只要某进程发生缺页，就能获得新的物理块，空闲物理块用完后，系统还会选择别的进程的页面分给该进程，会导致别的页面的缺页率增加。
  • 可变分配局部置换: 刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进率特别低，则可适当减少分配给该进程的物理块。

页面调入的时机和位置:

• 何时调入页面:
  1. 预调页策略: 根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。
     • 故这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分。
  2. 请求调页策略: 进程在运行期间发现缺页时才将所缺页面调入内存。
     • 由这种策略调入的页面一定会被访问到，但I/O开销较大。
• 从何处调入页面:
  1. 系统有足够的对换区空间:
  2. 系统缺少足够的对换区空间: 对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入
  3. UNIX方式: 未使用过的从文件去换入；使用过的重新换入则从对换区

内存映射文件

内存映射文件-定义: (Memory-Mapped Files, MMap) 操作系统向上层程序员提供的功能(系统调用)

内存映射文件-功能:【不是所有的文件存储结构都支持，比如隐式链接】

• 方便程序员访问文件数据
• 方便多个进程共享同一个文件

传统的文件访问方式:

• open系统调用: 打开文件
• seek系统调用: 将读写指针移到某个位置
• read系统调用: 从读写指针所指位置读入若干数据(从磁盘读入内存)
• write系统调用: 将内存中的指定数据，写回磁盘(根据读写指针确定要写回什么位置)

内存映射文件-实现:

• 文件访问:
  • open系统调用: 打开文件
  • mmap系统调用: 将文件映射到进程的虚拟地址空间
    • 以访问内存的方式访问文件数据
    • 只是映射到内存，并不是完整的复制
    • 操作系统回自动读入数据，而不需要read
    • 进程关闭文件时，操作系统自动将文件被修改的数据写回磁盘
• 文件共享: 多个进程可以映射同一个文件，实现共享在物理内存中，一个文件对应同一份数据，当一个进程修改文件数据时，另一个进程可以立马"看到"

文件管理

基本问题

1. 计算机中存放了各种各样的文件，一个文件有哪些属性？
   • 文件名: 同一目录下不允许有重名文件
   • 标识符: 操作系统用于区分各个文件的一种内部名称，唯一，对用户来说毫无可读性。
   • 文件类型: 方便设置打开方式
   • 位置: 在内存中的路径(让用户使用)、在外存中的地址(操作系统使用)
   • 创建时间、上次修改时间、文件所有者信息
   • 保护信息: 对文件进行保护的访问控制信息
2. 文件内部的数据应该怎样组织起来？【文件的逻辑结构】
3. 文件之间又应该又应该怎么组织起来？通过目录树按照层次组织
4. 从上往下看，文件数据应该怎么存放在外存(磁盘)上？
   • 对非空闲磁盘块的管理【文件的物理结构】
   • 对空闲磁盘块的管理【存储空间管理】
5. 从下往上看，OS应提供哪些功能，才能方便用户、应用程序使用文件？【文件的基本操作】+【文件共享】+【文件保护】

文件内部组织(逻辑结构)

无结构文件(如文本文件): 由一些二进制或字符流组成，又称"流式文件"，无逻辑结构

有结构文件(如数据库表): 由一组相似的记录组成，又称"记录式文件"

• 顺序文件:
  • 特性:
    • 每条记录有一个数据项为关键字
    • 按照记录长度可分为定长记录和可变长记录
  • 组织: 文件中的记录一个接一个地顺序排列(逻辑上)，记录可以是定长的或可变长的。【各个记录在物理上可以顺序存储或链式存储】
    • 结构:
      • 串结构: 记录之间的顺序与关键字无关
      • 顺序结构: 记录之间的顺序按关键字顺序排列
    • 注意: 操作系统中会用日志文件来记录对文件的操作，从而降低I/O频率
• 索引文件:
  • 需求: 解决可变长记录文件的查找速度问题
  • 方法: 建立索引表来加快检索进度
    • 索引表本身是定长顺序文件
    • 可以用不同的数据项建立多个索引表
  • 场景: 用于对即使性要求比较高的场合
• 索引顺序文件:
  • 需求: 解决索引文件里索引表项占空间过大的问题
  • 方法: 索引顺序文件中，一组记录对应一个索引表项。
    • 索引顺序文件的索引项也不需要按关键字顺序排列【极大地方便新表项的插入】
    • 为了进一步提高检索效率，可以为顺序文件建立多级索引表。

文件目录

目录本身就是一种有结构文件，由一条条记录组成。每条记录对应一个在该放在该目录下的文件。 其中的一条记录就是一个文件控制块(FCB)【实现文件目录的关键数据结构】。 FCB中包含文件的基本信息(文件名、物理地址、逻辑结构、物理结构)、存取控制信息(是否刻读/可写、禁止访问的用户名单等)、使用信息(建立时间、修改时间)。

目录操作:

• 搜索: 当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
• 创建文件: 创建一个新文件时，需要在其所属的目录中增加一个目录项
• 删除文件: 当删除一个文件时，需要在目录中删除相应的目录项
• 显示目录: 用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
• 修改目录: 某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项(如: 文件重命名)

目录结构:

• 单级目录结构: 单级目录实现了"按名存取"，但是不允许文件重名。【不适用于多用户操作系统】
• 两级目录结构: 早期的多用户操作系统，采用两级目录结构。分为主文件目录(MFD, Master File Directory)和用户文件目录(UFD, User Flie Directory)
• 多级目录结构(树形目录结构)
  • 缺点: 树形结构不便于实现文件的共享
• 无环图目录结构: 在树形目录结构的基础上，增加一些指向同一节点的有向边使整个目录成为一个有无环图。
  • 可以更方便地实现多个用户间的文件共享
  • 使用共享计数器实现文件删除功能【文件不被任何目录包含】

索引节点(Inode): 【对文件控制块的优化】

• 需求: 其实在查找各级目录的过程中只需要用到"文件名"这个信息，只有文件名匹配时，才需要读出文件的其他信息。因此可以考虑让目录表"瘦身"来提升效率。
• 实现:
• 原理: 通过降低磁盘块的I/O操作提升文件检索速度【索引节点占用空间小，一个磁盘块可以放入很多】
• 使用:
  • 当找到文件名对应的目录项时，才需要将索引结点调入内存
  • 存放在外存中的索引结点称为"磁盘索引结点"，当索引结点放入内存后称为"内存索引结点"。相比之下内存索引结点中需要增加一些信息，比如: 文件是否被修改、此时有几个进程正在访问该文件等。

文件分配方式(物理结构)

类似于内存页，外存的存储单元也会分为一个个"块/磁盘块/物理块"。同样类似的是，文件的逻辑地址也可以分为(逻辑块号，块内地址)，操作系统同样需要将逻辑地址转换为外存的物理地址(物理块号，块内地址)的形式。很多操作系统中，磁盘块的大小与内存块、页面的大小相同。

• 连续分配: 要求每个文件在磁盘上占有一组连续的块
  • 实现:
    • FCB/Inode需要记录存放的起始块号和长度
    • 用户转化逻辑块号为物理块号时需要检验是否合法
  • 分析:
    • 优点:
      • 支持随机访问
      • 可以减少机械硬盘的磁头移动，提高顺序读写速度
    • 缺点:
      • 不方便文件拓展【如果文件需要拓展，则需要迁移原本的文件块到空间更大的空闲区，开销较大】
      • 存储空间利用率低，会产生"外部碎片"【只能通过开销很大的紧凑来解决】
• 链接分配: 采取离散分配的方式，可以为文件分配离散的磁盘块。
  • 隐式链接【默认链接分配方式】
    • 实现:
      • FCB/Inode需要记录了文件存放的起始块号和结束块号。【也可以增加一个字段来表示文件的长度】
      • 除了文件的最后一个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针，这些指针对用户是透明的
    • 分析:
      • 缺点:
        • 地址转换过程需要读磁盘
        • 只支持顺序访问，不支持随机访问，查找效率低
        • 指向下一个块的指针也会消耗存储空间
      • 优点:
        • 方便文件拓展
        • 不会有碎片问题，外存利用率高
  • 显式链接: 把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表(FAT, File Allocation Table)
    • 实现:
      • FCB/Inode需要记录起始块号
      • FAT中包含物理块号和对应的下一块块号
      • 下一块块号为-1代表文件的结尾
      • 一个磁盘仅需设置一张FAT。开机时，将FAT读入内存，并常驻内存。FAT的各个表项在物理上连续存储。
    • 分析:
      • 优点:
        • 地址转换的过程不需要读磁盘
        • 支持随机访问
      • 缺点:
        • 文件分配表的需要占用一定的存储空间
• 索引分配: 系统会为每个文件建立一张索引表用于地址转换
  • 实现:
    • 索引表存放的磁盘块称为索引块，文件数据存放的磁盘块称为数据块
    • FCB/Inode记录索引块
    • 索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表)
    • 逻辑块号可以隐含，只需要存储物理块号
  • 分析:
    • 优点:
      • 支持随机访问
      • 容易实现文件拓展
    • 缺点:
      • 索引表需要占用一定的存储空间
      • 大文件的数据块号在一个索引块中存不下
        • 链接方案: 如果素引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。【FCB/Inode中只需要记录起始索引块】
          • 缺点:
            • 需要顺序读索引块
            • 对大文件限制较大
        • 多层索引: 建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。
          • 缺点:
            • 影响小文件的读写速度
        • 混合索引: 多种索引分配方式的结合【既包含直接地址索引(直接指向数据块)，又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)】

存储空间管理

存储空间的划分与初始化:

• 划分: 一般是将物理磁盘划分为一个个文件卷/逻辑卷/逻辑盘，但有的系统支持将多个物理磁盘组成一个大的文件卷
• 初始化: 将各个文件卷划分为目录区(包含目录、空闲表、位示图、超级块等)、文件区

存储空间管理方法:

• 空闲表法: 空闲盘块表里存放第一个空闲盘块号和空闲盘块数【适用于连续分配】
  • 分配: 可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间【与内存管理中的动态分区分配类似】
  • 回收: 【也类似动态分区分配】
• 空闲盘块链:
  • 空闲盘块链: 以盘块为单位组成一条空闲链，系统保存着链头链尾的指针
    • 如何分配: 若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。
    • 如何回收: 回收的盘块依次挂到链尾，并修改空闲链的链尾指针。
  • 空闲盘区链: 以盘区为单位组成一条空闲链，系统保存着链头链尾的指针【离散分配、连续分配都适用】
    • 如何分配: 若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件；若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
    • 如何回收: 若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。
• 位示图法:
  • 分配: 若文件需要K个块，先顺序扫描位示图，找到K个相邻或不相邻的"0"，然后根据字号、位号算出对应的盘块号，将相应盘块分配给文件，最后将相应位设置为"1"
  • 回收: 先根据回收的盘块号计算出对应的字号、位号；然后将相应二进制位设为"0"
• 成组链接法: 文件卷的目录区中专门用一个磁盘块作为"超级块"，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的"超级块"数据一致。
  • 分配与回收: 就像操作链表一样，不断调整超级块
  • 分析: UNIX采用的策略，适应大型文件系统的存储管理方法【空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大】

文件的基本操作

• 创建文件(create系统调用)
  • 参数: 所需外存大小、文件存放路径、文件名
  • 实现:
    1. 在外存中找到文件所需的空间
    2. 按照文件存放路径找到对应的目录表，创建该文件对应的目录项
• 删除文件(delete系统调用)
  • 参数: 文件存放路径、文件名
  • 实现:
    1. 找到文件名对应的目录项
    2. 根据目录项，回收文件占用的外存磁盘块
    3. 从目录表中删除对应的目录项
• 打开文件(open系统调用)
  • 参数: 文件存放路径、文件名、操作类型(r, w, rw)
  • 实现:
    1. 找到文件名对应的目录项，并检查用户是否有指定的操作权限
    2. 将目录项复制到内存中的"打开文件表"中。并将对应表项的索引号(文件描述符)返回给用户。之后用户使用打开文件表的索引号来指明要操作的文件。【可以加快文件的访问速度】
       • 系统有唯一的一张打开文件表，每个用户进程也有一张打开文件表
• 关闭文件(close系统调用)
  • 实现:
    • 删除进程的打开文件表中的对应表项
    • 回收分配的内存空间等资源
    • 系统打开文件表的对应count减一，如果count为0，则删除该表项
• 读取文件(read系统调用)
  • 参数: 进程的打开文件表的索引号、需要读入的数据量、读入数据的内存存储位置
  • 实现: 从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。
• 写入文件(write系统调用)
  • 参数: 进程的打开文件表的索引号、需要写入的数据量、写回数据的内存存储位置
  • 实现: 从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。

文件共享

多个用户共享同一个文件，意味着系统中县有"一份"文件数据。并且只要某个用户修 改了该文件的数据，其他用户也可以看到文件数据的变化。

• 基于索引结点的共享方式(硬链接):
  • 文件删除时需要判断count是否为0
  • 如果目标已经删除，硬链接仍然可以访问
• 基于符号链的共享方式(软链接):
  • 如果目标已经删除，那软链接也访问不了

文件保护

• 口令保护: 口令一般存放在文件对应的FCB/Inode中。用户访问文件前需要先输入"口令"，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许该用户访问文件。
  • 优点: 空间时间开销都小
  • 缺点: 正确的"口令"存放在系统内部，不够安全
• 加密保护: 系统不保存密码，而是保存加密后的数据【e.g. 异或加密】
  • 优点: 保密性强，不需要在系统中存储“密码”
  • 缺点: 编码/译码，或者说加密/解密要花费一定时间
• 访问控制:
  • 在文件对FCB/Inode中增加一个访问控制列表(Access-Control List, ACL)，该表中记录了各个用户可以对该文件执行哪些操作。
    • 访问控制会传递到子层
  • 精简的访问列表: 以"组"为单位，标记各"组"用户可以对文件执行哪些操作。【可以分为系统管理员、文件主、文件主的伙伴、其他用户】
  • Windows: 一般拒绝项优先于允许项
  • Linux: 主组优于附属组

文件系统

文件系统的全局结构(布局)

文件系统在外存中的建立:

• 原始磁盘
• 物理格式化(低级格式化): 划分扇区，检测坏扇区，并用备用扇区替换坏扇区【备用扇区在磁盘的末尾连续排列】
• 逻辑格式化: 磁盘分区/分卷(Volume)，完成各分区的文件系统初始化
  • 逻辑格式化后，灰色部分就存实际数据了，白色部分还没有数据

文件系统在内存中的机构:

文件系统的层次结构

虚拟文件系统 & 文件系统挂载(安装)

普通文件系统:

虚拟文件系统:

1. 向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异
2. VFS要求下层的文件系统必须实现某些规定的函数功能，如: open/read/write。
3. 每打开一个文件，VFS就会在主存中新建一个vnode，用统一的数据结构表示文件。
   • vnode只会存在于主存中，而inode既会被调入主存，也会在外存中存储

文件系统挂载/安装(mounting):

1. 在VFS中注册新挂载的文件系统。内存中的挂载表(mount table)包含每个文件系统的相关信息，包括文件系统类型、容量大小等。
2. 新挂载的文件系统，要向VFS提供一个函数地址列表
3. 将新文件系统加到挂载点(mount point)，也就是将新文件系统挂载在某个父目录下

设备管理

I/O管理基础

I/O设备分类

• 按使用特性:
• 按信息交换的单位分类:

I/O控制器

作用: I/O设备由电子部分和机械部分组成。CPU无法直接控制I/O设备的机械部件，因此I/O设备还要有一个电子部件作为CPU和I/O设备机械部件之间的"中介"，用于实现CPU对设备的控制。

功能:

1. 接受和识别CPU发出的命令: 【通过控制寄存器】
2. 向CPU报告设备的状态:【通过状态寄存器】
3. 数据交换:【通过数据寄存器】
4. 地址识别:【通过地址寄存器】

组成:

• 一个I/O控制器可能会对应多个设备；
• 数据寄存器、控制寄存器、状态寄存器可能有多个，且这些寄存器都要有相应的地址，才能方便CPU操作。
  • 有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O；
  • 另一些计算机则采用I/O专用地址，即寄存器独立编址。

I/O控制方式

• 程序直接控制方式(轮询)
  • 流程:
  • CPU干预的频率: 很频繁，I/O操作开始之前、完成之后需要CPU介入，并且在等待I/O完成的过程中CPU需要不断地轮询检查。
  • 数据的传送单位: 一个字
  • 数据的流向: I/O设备->CPU->内存(读)
  • 优缺点:
    • 优点: 实现简单
    • 缺点: 只能串行工作，CPU需要一直轮询检查，长期忙等，CPU利用率低

• 中断驱动方式:

  • 流程:
    • 由于I/O设备速度很慢，因此在CPU发出读/写命令后，可将等待I/O的进程阻塞，先切换到别的进程执行。
    • 当I/O完成后，控制器会向CPU发出一个中断信号，CPU检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。
    • 处理中断的过程中，CPU从I/O控制器读一个字的数据传送到CPU寄存器，再写入主存。
    • 接着，CPU恢复等待I/O的进程(或其他进程)的运行环境，然后继续执行。
  • 注意:
    • CPU在指令周期的末尾检查中断
    • 中断处理过程中需要保存、恢复进程的运行环境，中断频率过高也会影响性能
  • CPU干预的频率: 每个I/O操作开始前，需要CPU介入
  • 数据的传送单位: 一个字
  • 数据的流向: I/O设备->CPU->内存(读)
  • 优缺点:
    • 优点: 与"程序直接控制方式"相比，在"中断驱动方式"中，I/O控制器会通过中断信号主动报告I/O己完成，CPU不再需要不停地轮询。CPU和I/O设备可并行工作，CPU利用率得到明显提升。
    • 缺点: 每个字在I/O设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间。

• DMA方式(Direct Memory Access, 直接存储器存取)【主要用于块设备的I/O控制】

  • 流程:
    • CPU指明此次要进行的操作，并说明要读入多少数据、数据要存放在内存的什么位置、数据在外部设备上的地址(如: 在磁盘上的地址)，后阻塞I/O进程。
    • DMA控制器会根据CPU提出的要求完成数据的读/写工作，整块数据的传输完成后，才向CPU发出中断信号。。。
  • CPU干预的频率: 传输一块的开始和结束
  • 数据的传送单位: 块
  • 数据的流向: 设备->内存(读)
  • 优缺点:
    • 优点:
      • 数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加
      • CPU和/0设备的并行性得到提升
    • 缺点: CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块。
• 通道控制方式
  • 流程:
  • CPU干预的频率: 极低，通道会根据CPU的指示执行相应的通道程序
  • 数据传送的单位: 每次读/写一组数据块
  • 数据的流向: 设备->内存(读)
  • 优缺点:
    • 缺点: 实现复杂，需要专门的通道硬件支持
    • 优点: CPU、通道、I/O设备可并行工作，资源利用率很高。

I/O软件层次结构

• 用户层软件: 实现了与用户交互的接口，为上层提供系统库函数【如printf】
• 设备独立性软件:
  • 向上层提供统一的调用接口【如read/write系统调用】
  • 实现对设备的保护【设备也可以看作一种文件】
  • 设备差错处理
  • 设备的分配与回收
  • 数据缓冲区管理
  • 建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序【通过逻辑设备表LUT记录】
    • 只有单用户系统才设置系统级的LUT，否则就会设置用户级LUT
• 设备驱动程序: 主要负责对硬件设备的具体控制，将上层发出的一系列命令(如read/write)转化成特定设备"能听得懂"的一系列操作。包括设置设备寄存器、检查设备状态等。
• 中断处理程序: 当I/O任务完成时，I/O控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。

输入输出管理

• I/O应用程序接口
  • 网络设备接口(网络套接字接口, socket):
• 设备驱动程序接口

I/O核心子系统

组成:

• 设备独立性软件
• 设备驱动程序
• 中断处理程序

功能:

• I/O调度: 类似处理机调度
  • 磁盘调度: 先来先服务算法、最短寻道优先算法、SCAN算法、C-SCAN算法、LOOK算法、C-LOOK算法)
  • 打印机等设备: 先来先服务算法、优先级算法、短作业优先算法
• 设备保护: 类似文件管理中FCB中的ACL等
• 假脱机技术(SPOOLing技术): 【实际是在应用层软件中实现】
• 设备分配与回收
• 缓冲区管理(即缓冲与高速缓存)

SPOOLing技术(假脱机技术)

概念:

• 脱机技术: 缓解设备与CPU的速度矛盾，实现预输入、缓输出
• 假脱机技术: 用软件的方式模拟脱机技术。

组成:

- 必须要有多道程序技术的支持。系统会建立"输入进程"和"输出进程"

共享打印机原理分析:

设备分配与回收

• 设备分配时应考虑的因素
  • 设备的固有属性可分为三种: 独占设备、共享设备、虚拟设备
  • 设备分配算法: FCFS, SJB, HRRN等
  • 设备分配安全性:
    • 安全分配方式: 一个时间段内每个进程只能使用一个设备
      • 优点: 破坏了“请求和保持”条件，不会死锁
      • 缺点: 对于一个进程来说，CPU和I/O设备只能串行工作
    • 不安全分配方式: 只有某个I/O请求不满足时才会被阻塞
      • 优点: 进程的计算任务和I/O任务可以并行处理，使进程迅速推进
      • 缺点: 有可能发生死锁
• 静态分配与动态分配
  • 静态分配: 进程运行前为其分配全部所需资源，运行结束后归还资源【破坏了"请求和保持"条件，不会发生死锁】
  • 动态分配: 进程运行过程中动态申请设备资源
• 设备分配管理中的数据结构
  • 设备控制表(DCT): 系统为每个设备配置一张DCT，用于记录设备情况
  • 控制器控制表(COCT): 每个设备控制器都会对应一张COCT。操作系统根据COCT的信息对控制器进行操作和管理。
  • 通道控制表(CHCT): 每个通道都会对应一张CHCT。操作系统根据CHCT的信息对通道进行操作和管理。
  • 系统设备表(SDT): 记录了系统中全部设备的情况，每个设备对应一个表目。
• 设备分配的步骤
  • 流程:
    1. 根据进程请求的物理设备名查找SDT【物理设备名是进程请求分配设备时提供的参数】
    2. 根据SDT找到DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程。
    3. 根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。
    4. 根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。
  • 缺点:
    • 用户编程时必须使用“物理设备名”，底层细节对用户不透明，不方便编程
    • 若换了一个物理设备，则程序无法运行
    • 若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待
• 设备分配步骤的改进方法: 建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名【利用LUT】

缓冲区管理

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。

• 使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合【如快表】
• -般情况下，更多的是利用内存作为缓冲区，【设备独立性软件】

设备独立性软件中的缓冲区作用:

• 缓和CPU与I/O设备之间速度不匹配的矛盾
• 减少对CPU的中断频率，放宽对CPU中断相应时间的限制
• 解决数据粒度不匹配的问题: 【e.g. 输出进程每次可以生成一块数据，但I/O设备每次只能输出一个字符】
• 提高CPU与I/O设备之间的并行性

设备独立性软件中的缓冲区策略:

• 单缓冲: 操作系统会在主存中为其分配一个缓冲区(若题目中没有特别说明，一个缓冲区的大小就是一个块)。【当缓冲区数据非空时，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。】

  

  计算每处理一块数据平均需要多久？假定一个初始状态，分析下次到达相同状态需要多少时间，这就是处理一块数据平均所需时间。

  • T > C
  • T < C

  结论: 处理一个数据块的平均耗时为Max(T, C) + M

• 双缓冲: 操作系统会在主存中为其分配两个缓冲区(若题目中没有特别说明，一个缓冲区的大小就是一个块)

  

  设初始状态为工作区空，其中一个缓冲区满，另一个缓冲区空。

  • T > C + M
  • T < C + M

  结论: 处理一个数据块的平均耗时为Max(T, C+M)

使用单/双缓冲在通信时的区别:

循环缓冲区:

将多个大小相等的缓冲区链接成一个循环队列。【以下图示中，橙色表示己充满数据的缓冲区，绿色表示空缓冲区。】

缓冲池:

硬盘与固态硬盘

磁盘结构

磁盘调度算法

减少磁盘延迟时间的方法

磁盘管理

固态硬盘(SSD)