操作系统2022年总结

导言 #

操作系统的四个特征 #

• 并发
  • 两个或多个事件同时发生，确切的说是同一段时间内,而非一个时刻。如果真的同一时刻同时发生，那叫并行。
• 共享
  • 共享即资源在进程间的共享，分为互斥共享和同时访问共享。前者用于临界资源。
  • 共享为并发提供了条件。如果资源不能被两个进程共同访问，那么他们也就不可能互斥执行。
• 虚拟
  • 把物理的实体变成逻辑上的实体，并能赋予其新的特征。例如虚存、Spooling等。
• 异步
  • 因为对进城来说，资源并不总是充足的，所以进程是走走停停的，也就是他推进的速度是无法预知的。这种无法预知的推进速度即异步。
  • OS需要保证就算这些进程是异步推进的，其执行结果也应当符合预期。（即多次执行，结果一致）

操作系统的作用 #

• 操作系统是工人，它操作计算机这个机器。用户是雇主。

• 操作系统操作机器，即对处理器，存储器、设备、文件四大部分进行管理；

• 雇主要给工人传递命令，工人要反馈，即操作系统要对用户预留

  接口

  。

  • 这种接口分为程序接口和命令接口。前者是例如系统调用API；后者是用户界面。
  • 命令接口分为联机接口和脱机接口。前者是交互式的，例如shell；后者是批处理的，例如slurm。

• 有了工人，机器才能发挥出更大作用，所以操作系统可以

  扩充计算机系统

  。

  • 扩充计算机系统，是相对于计算机裸机（没有软件覆盖的计算机系统）而言的。
  • 有了OS，裸机才能发挥应有的功能。

批处理系统 #

• 为了解决IO速度和CPU之间的速度差异。
• 批处理分为单道批处理和多道批处理。后者是在宏观上并行，在微观上串行。

分时系统 #

• 为了解决用户不能交互的问题。
• 把CPU时间划分成时间片，每个时间片给一个用户，这样轮流使用。如果某作业不能在这个时间片内完成，就进入等待，等待下一次其得到时间片。因为时间片较短，所以用户感觉好像自己独占了计算机。
• 分时系统是交互式系统，通过多个终端连接到中心计算机上实现。其交互性是和批处理系统的最大区别。
• 现在的OS例如Windows可以理解为分时系统，而分时的对象不再是用户，而是一个个进程。

实时系统 #

• 分时系统虽然在宏观上是交互的，但是在微观上其还是会有一定的延迟。这对于诸如导弹发射这样的精确任务不能胜任。
• 实时系统的特点是：必须在完全正确的时间点给出响应（如导弹制导），或必须在一定时间限制内给出响应（如订票系统）。前者称为硬实时，后者称为软实时。
• 常使用抢占式的优先级高者优先调度算法。
• 实时系统的目标是响应速度。为此它可以放弃一定的资源利用率。因此实时系统资源利用率一般比较低。

网络操作系统、分布式操作系统 #

• 网络操作系统
  • 计算机之间可以通信和资源共享。但是不能协作完成工作。
• 分布式操作系统具有分布性、并行性。
  • 计算机之间没有主从关系。计算机之间可以通信和资源共享。
  • 分布性：任何工作可以分布在若干计算机上，协同完成任务。

核心态、用户态及其切换（注意上下文的保存和恢复） #

When the CPU’s mode bit = 0, in kernel mode.

• 可以执行特权指令的状态是核心态。可以理解为CPU有一小开关，控制着当前是否处于核心态。
  • 常见特权指令：IO指令
• 内核运行在核心态，用户程序运行在用户态。
• 从用户态转为核心态的过程称为“陷入”。“陷入”是硬件过程，即只要发生了中断，硬件就会把核心态标志位置1.
• 核心态、用户态切换的过程需要保护现场（CPU寄存器）。这和进程切换类似。因为当进程从用户态转到核心态，实际上就不是跑这个进程的程序了，而是执行内核程序，所以需要保存、恢复现场（就像进程切换那样）。
• All the I/O instructions are privileged instructions.

内核 #

The process which is always running is called a kernel.

• 内核是操作系统最底层的软件，是计算机功能的延伸。
• 内核包括以下四部分内容：
  • 时钟管理
    • 系统维护一个时钟
    • 时钟可以为用户提供标准时间
    • 时钟是分时系统的关键。当进程的时间片用完，它就从执行态转为就绪态。
  • 中断机制
    • 中断发明的初衷是提升CPU的利用率（例如进行IO时，你数据传完了再提出中断去高速CPU，则实现了IO设备与CPU的并行。）
    • 在中断中，内核负责保护现场（仅保存程序状态字，因为PC是隐指令负责的）和恢复现场、转到中断处理程序。
  • 原语
    • 是操作系统最接近硬件的“小程序”，他们具有原子性，并且常常会被频繁调用。
    • 原子性通过进入程序时关中断，离开程序时开中断实现。（只要关闭了中断，就不会被抢占。因为所谓时间片用尽、抢占，这些都是基于中断实现的。）
  • 系统控制的数据结构及处理
    • 数据结构就是用于OS正常运行的状态信息，包括PCB、FCB、Page Table等。

外中断和内中断 #

• 外中断又称中断，是和当前CPU执行的程序没有关系的中断，例如键盘中断、打印机、时钟中断。它的中断处理程序往往不需要上下文信息。

• 内中断又称异常、陷阱。内中断不能被屏蔽，一旦出现必须处理；它的中断处理程序

  需要上下文信息

  。

  • 例：软件出错、硬件出错、访管中断（又称自愿中断，是指调用访管指令（访管指令只能由用户态下执行，用于主动切换核心态，所以它不是特权指令））、用户程序错误地尝试使用特权指令（此时产生中断来防止其使用）等。

• **无论是内中断还是外中断，只要发生中断，CPU就从用户态陷入核心态。**从用户态转为核心态的过程称为“陷入”。“陷入”是硬件过程，即只要发生了中断，硬件就会把核心态标志位置1.

• A Trap is a

  software-generated

  interrupt caused ether by an error or a

  system call

  .

  • error: such as infinite loop: 利用计时器到点（时间片用尽）产生中断

• The OS is interrupt-driven. If the system is idle now, an interrupt could signal it to run.

系统调用 #

• 在用户态下执行陷阱指令，就陷入核心态，此时CPU由内核接管，在核心态执行，提供相应功能。执行完毕后，再返回用户态，从而返回用户程序。
• 在编写C程序时，通过API调用系统调用函数，这些函数会被编译成陷阱指令和若干相关参数。

微内核 #

• 微内核是更具模块化思想的内核设计，把一些不需要在核心态运行的系统程序分离出去，让他们在用户态运行（因为根据定义，内核是运行在核心态的，其他任何程序都在用户态。），然后他们之间的通信要通过内核实现（也就是每次互相通信都要陷入核心），这虽然使内核设计更加简单且更易于扩展，但是效率非常低（因为需要频换切换核心态）。
• 宏内核是把上述那些模块都集成在内核内，他们之间可以直接通信。缺点是过于庞大，不易于扩展与维护。

进程和线程 #

进程 #

• 进程是一个程序在其数据集合上运行的过程，是系统进行资源分配的基本单位。
  • 这里的资源即CPU时间、内存、其他设备和服务。

PCB #

• PCB是进程存在的唯一标志

进程实体（进程映像） #

• 由程序段、数据段、PCB构成。

进程的五状态 #

• 创建态
  • 在这个过程中，PCB被创建，资源被分配。于是，进程实体就产生了。
  • 然后就可以进入就绪态。
• 结束态
  • 进行资源释放和回收。
• 对比：阻塞态和就绪态
  • 阻塞是进程进入了等待，等待一个时间的的发生。在这段时间内，其不可能占用CPU，因为当前它因为除了CPU外的原因无法执行。
  • 和就绪态的区别：就绪态等待的原因只是CPU时间，而阻塞态必然还在等待别的事情。所以两者的区别是：是否单纯因为CPU时间而无法执行。
  • 进程处在阻塞态的时间往往较长，比就绪态长得多。因为CPU时间片是很短的，这就导致进程会频繁而短促地在就绪态和执行态之间转换。而处在阻塞态的程序往往等待很长时间（相比CPU时间片来说），例如访问磁盘。

常见的状态转换 #

• 执行-就绪
  • 可能是时间片用完了
  • 可能是被更高优先级进程抢占了
• 执行-阻塞
  • 这是一个主动行为（主动睡眠）。程序突然需要进行IO了，就等待IO的完成。
• 阻塞-就绪
  • 这是一个被动行为（被动唤醒）。当刚才那个程序的IO完成，它被服务程序唤醒了。

进程管理原语 #

• 创建、终止、阻塞、唤醒、切换这五种操作实际上由OS提供的对应5种原语完成。这些都是原子操作。通过关中断实现。

进程的创建 #

• 一个进程可以创建另一个进程。称为父、子进程。子进程在没有exec之前，直接继承（copy）父进程的资源的内容。子进程如果退出，由父进程负责释放资源、传递返回值等。
• 原语
  • 分配PID，并创建新PCB
  • 分配资源。如果资源不足，则进入等待
  • 初始化PCB，例如设定优先级
  • 放入就绪队列

僵尸进程和孤儿进程 #

Zombie: Process execution is terminated, but the parent process has not yet issued a wait() or waitpid system call to return information about the dead process.

Orphan: 父进程已经退出了。子进程只能归1号进程（init进程）管。

进程的终止 #

• 进程可以正常终止，可以出现异常而结束，可以由外界信号结束（例如SIGINT）

进程的阻塞和唤醒 #

• 阻塞原语（进程主动调用）
  • 找到PCB，保护现场，停止运行，把他插入相应资源的等待队列
• 唤醒原语（其他进程调用，本进程被动唤醒）
  • 从这种资源的等待队列找到PCB，放入就绪队列

进程的切换（注意上下文的保存和恢复） #

• 原语
  • 中止执行，保存上下文（各寄存器）
  • 更新当前进程PCB，并把他移动到相应队列（就绪队列或等待队列）
  • 从就绪队列选择一个新的PCB，更新其PCB
  • 恢复上下文（各寄存器），开始执行

PCB的结构 #

• PCB是哆啦A梦的口袋，任何关于该进程的信息都从这里找。

• 进程描述信息（

  负责进程的标识

  ）

  • 包括UID、PID

• 进程控制和管理信息（

  负责进程的执行

  ）

  • 进程状态（五态之一）
  • 优先级
  • 内存中的代码入口、外存中的代码入口

• 审计信息（

  负责进程的审计

  ）

  • CPU、内存等资源占用时间

• 资源清单（

  负责进程的资源

  ）

  • 各内存段指针（堆栈段，代码段，数据段）
  • 进程FCB
  • 外设

• CPU上下文（

  负责进程的切换

  ）

  • 各寄存器的数值，各标志位的数值（即DOS里面-t出来的那些）

PCB的组织 #

• 系统中有就绪队列，有各种资源分别的阻塞队列。这些队列里面是PCB进行排列。
• 索引方式（数组）
  • 队列里的成员实际上是用了PCB的索引代替。而真正的PCB是集中存放的。
• 链接方式（链表）
  • 队列是链表，元素是PCB。

进程之间的存储共享 #

• 共享存储
  • 分为基于数据结构的共享和直接基于存储空间的共享。这段空间由系统调用进行安排。
  • 属于临界资源，需要互斥访问。
  • 对于一个进程，其各线程之间是天生满足“共享存储”概念的。
• 消息传递
  • 如果只需要进行信号的传递，可以不必大费周章去申请共享内存并管理他。只需要使用OS提供的消息传递系统调用。
  • 直接消息传递（消息队列法）
    • A向B发送消息，则把消息挂在B的消息队列里面即可。
  • 间接消息传递（信箱法）
    • A向B发消息，则A发到B的信箱，B从信箱取。
• 管道
  • 管道实际上是一个共享文件，连接了两个进程。
  • 管道虽然是文件，但是它限制了最大体积，即它不能无限增大。这可以类比一个有限缓冲区。
  • 管道的两端可以看做是读者-写者。当管道文件满，写者如果还要write就阻塞；当管道文件空，读者如果还要read就阻塞。
  • 管道中的数据一旦读出就被删除。
  • 管道是半双工的，即同一时刻只能由一方作为写（读）者（就算你不close）。如果要实现全双工则需要两条管道。

堆段、栈段、数据段、BSS段的区别 #

段	对应C语言变量	解释
栈段	局部变量、函数参数、函数返回值	栈的LIFO的特性非常有利于像子过程调用这样的应用场景。当进入了一个局部空间，它一定还会再退出来，所以可以用栈。
堆段	动态分配内存变量(new,malloc)	可以联想DBMS里面的堆文件。
数据段	全局变量、静态变量、常量	是为整个程序所用的，所以保存在整体空间中
BSS段	未初始化的全局变量	-

• 栈是从高地址向低地址增长的，堆是低地址向高地址增长的，在现代OS中，他们可能碰头。一般情况下，栈顶和堆顶之间都是有一段空余空间的。

线程 #

• 线程是能表示一个执行中的程序的最小的单元。因此它只包含

  CPU寄存器数据和堆栈段指针

  （即程序执行的上下文）。

  • 堆栈段是这个程序中局部过程需要的执行资源。没有堆栈段就没有局部的概念。你没法拥有自己的变量。
  • 可以说，堆栈段就是一个“现场”。如果只有数据段，你就算不运行这个程序，他也是存在的。但是堆栈段给出了运行这个程序的动态。不同的线程在各自的运行状态中，他们的堆栈段是不一样的，但是他们都共享完全一样的那个数据段。
  • 所有线程都可以访问进程的数据段，因此大家可以通过静态变量或全局变量通信。

• 同一进程中，线程可以创建和撤销其他线程。因此这些线程没有主次之分。

• 同一进程中，所有线程共享这个进程占有的资源。

• CPU的时间调度以线程为单位。如果某次上下文切换发生在统一进程的不同线程之间，则这个切换时间可以忽略不计。

• 好处：

  • 可以看出，线程的TCB（线程控制块）只包含CPU寄存器和堆栈段信息，所以其切换、创建都非常迅速，不需要像进程那样把哆啦A梦的口袋的物件都安排个遍。
  • 便于通信。因为天然地就共用内存空间，相当于共享内存的通信方式已经安排好了。（可以直接通过读写全局变量的方式。）
  • 如果需要创建多个功能一致的进程，显然不如创建这些线程。
  • 在多CPU下，如果这个进程的不同线程在不同的CPU上运行，就可以提升速度。
  • **提升了系统的并发度：**因为上下文切换开销平均来看变小了，则效率变高了，在一定的时间间隔内能运行更多线程。

用户级线程和内核级线程 #

• 区别与联系
  • 内核为该进程分配内核级线程。取决于采用的映射模型，会分配一个或多个。内核级线程是真正占用系统资源的线程实体。
  • 用户级线程是线程库的一种数据结构。用于描述一个逻辑上的线程。
  • 可以理解为：用户级线程是内核级线程执行状态（上下文）的一个镜像。该镜像是用户级线程离开内核级线程时那一瞬间的上下文。当该用户级线程再次被映射到内核级线程上，该镜像用于恢复上次离开时的上下文。
• 用户级线程是线程库提供的结构，其管理、调度都由用户级线程库完成，与内核没有半毛钱关系。属于自娱自乐型。如果进程只被分配了一个内核级线程（即采用多对一映射），那么就算在用户空间是多线程，这个进程仍然作为一个整体被调度。在这个进程内，不同线程之间的调度由线程库自行完成，而不是OS。

• 用户级线程必须被映射到内核级线程上才能执行（因为线程库不能执行这个线程，只能通过OS去执行这个线程。线程库只能维护这个线程的上下文，从而便于把上下文映射给内核去执行）。因此线程库要做的工作就是选择要把哪个用户级线程映射上去。
• 所以，用户级线程只是线程库的一个调度单位，只是一个数据结构，用于保存这个线程的上下文信息。它并不是OS里面的一个真正的线程，而只是一个逻辑上的线程。所以用户级线程可以有无数个，但是OS因为性能的原因只能有有限个内核级线程。
• 可以预见，用户级线程的切换不需要陷入核心态。但是内核级线程的切换是真正的线程切换，需要进入核心态。

• 并不是说自娱自乐（多对一模型）就没有意义。因为这个时候线程库相当于一个小的OS，待映射的那个内核级线程相当于一个CPU，线程库完成了这个进程范围内的线程调度。（同时，这个进程还会作为一个整体被OS调度。因为在多对一模型下，这个进程只有一个线程。）
  • 也就是说，形成了两级调度。
• 为什么说内核看不见用户级线程？因为用户线程只是线程库里面的一种数据结构，和内核没有半毛钱关系。

用户级线程是代码逻辑，内核级线程是线程实体。

多对一模型 #

• 这是线程调度完全交给线程库的模型。在操作系统看来，用户并没有使用OS提供的多线程功能。

因为真正的线程是内核线程，内核线程才是OS进行调度的基本单位，所以每个用户线程只是线程库范围内进行调度的单位，与OS的调度无关。

• 因为实际上只有一个内核线程，所以一旦这个进程中的某个用户线程调用了引起阻塞的系统调用，就引起进程阻塞，这个进程的所有线程相当于是阻塞了（因为整个进程阻塞了）
• 而且这种模型不可能在多CPU环境下，不同用户线程在不同CPU上并行执行。因为它实际上只有一个内核线程，也就是只能被调度给一个CPU。

一对一模型 #

因为真正的线程是内核线程，内核线程才是OS进行调度的基本单位，因为每个用户线程真的就是内核线程了，所以他们都是OS进行调度的单位了。好耶。

• 好处：各线程可实现多CPU下的并行执行。且任意一个阻塞了不影响其他的。
• 缺点：影响性能（需要切换内核态实现调度）。

多对多模型 #

是上述两种方法的折中。

现代处理器的核心数、线程数、超线程（HT）技术 #

• 一个核心就是一个CPU。但是现代操作系统都以线程为调度的单位了，所以线程数量才是其并行能力的关键。
• 一般情况下，一个核心对应一个线程，这是正常情况。因为线程就算代替进程称为调度的基本单位，它也是需要核心去执行的。
• Intel发明超线程技术，只复制核心内供线程执行的必要部件，从而可以让一个核心支持多个线程并行执行。
• 于是，在HT的技术下，就有诸如“8核心16线程、64核心128线程”这样的CPU出来了。在以线程为调度的OS下，OS对核心线程的调度就是做出“让哪个核心线程去占用CPU的线程（逻辑核心）”的决定。线程看起来更像是一个个的==逻辑核心==。使用HT技术，能让逻辑核心数进一步翻倍。

三种调度 #

• 长程调度：选择作业以创建进程

  • 往slurm上提交作业，则这些作业都在外存上等着。此时需要这种调度方法，把外存中的某个适合的作业以进程创建的方式使其进入内存，获得竞争CPU（核心或线程）的权利。
  • 频率低。例如我的模型要pending好几十分钟。

• 中程调度：选择进程以挂起

  • “挂起”由此而来。

  • 如果某进程

    阻塞或==就绪==了

    （即暂时不能运行），则把他的镜像放到外存，从而可以把它从内存清退到外存。当需要唤醒它时，再把它调回主存，进入就绪态。

    • 如果一个挂起了的阻塞进程收到了一个信号，例如IO完成了，那么他可以转换为挂起的就绪态。等着它被换入了（专业的说法是激活（activate），激活和挂起是一对反义词。），才变成就绪态。所以，挂起的就绪态和就绪态是不同的！而且挂起的阻塞态可以直接转换到挂起的就绪态。

  • 所以，挂起态是更加深度的阻塞或==就绪==态。因为它不仅不占用CPU，还不占用内存了。这样能提高内存的利用率。

• 短程调度：选择进程以执行

  • 从就绪队列选择一个执行。
  • 显然频率非常高，可能每过一个时间片的长度就要调度一下。

• 作业调度是前提，没有作业调度就没有进程；进程调度是归宿，最后都需要进程调度才能获得核心或线程；中级调度是优化方法，在阻塞态和就绪态都可能发生。

进程的调度和进程的切换 #

• 切换往往在调度完成后紧接着立即进行。需要保存上一进程的上下文，恢复被调度过来的进程的上下文。内核中为每个进程都分配了一个栈，具体方式是把上一进程上下文入上一进程的内核栈，下一进程的上下文从下一进程的内核栈中弹出。
• 如果当前正在进行中断处理、正在访问临界区、或正在进行原子操作，是不允许进行调度的。因为调度是通过中断完成的（例如时间片耗尽产生中断信号，引发调度），而中断处理、原子操作都是关中断的。

因为当且仅当出现了中断，才会进行进程调度和切换。

剥夺调度和非剥夺调度（又称抢占式和非抢占式调度） #

• 如果设置了请求调度位，在中断处理结束或系统调用结束后返回现场前，即可立即进行进程的调度切换，那么这就是剥夺式调度。

• 如果对于一个进程，直到其

  阻塞了

  才去调度新的进程来执行。

  • 注意，如果存在“时间片用尽”这种情况，则属于剥夺了。

调度算法 #

• FCFS

  • 是非抢占算法，所以直到阻塞才能进行调度
  • 长作业优先：如果长作业来了，其他短作业要等好久
  • 利于CPU型作业，不利于IO型作业：如果频繁IO，则每次都要再排回队首等好久
  • 是其他调度算法的基础

• SJF（短作业优先）：选择最短的作业进行调度

  • 是非抢占算法，所以直到阻塞才能进行调度
  • 是平均等待时间、平均周转时间最短的调度算法。
  • 长作业产生饥饿现象
  • 作业长度不好估计

• 优先级调度：选择

  优先级
  

  
    最高的作业进行调度
  
    - 有抢占、非抢占可选。如果抢占，那么只要来了个优先级更高的就让出核心或线程，否则还是等到阻塞才能进行调度
    - 优先级可以是动态的：例如随着时间的增加
    - **一般情况下，IO型进程优先级应当大于CPU型的。**
  
  

• 高响应比调度：选择

  响应比
  

  
    最高的作业进行调度
  
    - 响应比综合考虑了等待时间和作业长度，是对`SJF`和`动态优先级`的折中。分母是SJF，分子是动态优先级。
    - 短作业优先：在等待时间一定时，作业越短，响应比越大
    - 长作业不饥饿：就算作业较长，也可以通过等待达到相对有竞争力的响应比
  
  

• Round-Robin：带时间片剥夺的

  SJF
  

  
    算法
  
    - 采用SJF方式，但是加入了时间片剥夺。任务一旦被剥夺，就因为来的比较晚而排到就绪队列尾部。
    - 时间片过长会导致退化成SJF算法，时间片过短会导致上下文切换开销过大。
  
  

• n级反馈队列调度：

  • 算法
    • 系统中有$n$个队列。
    • 对于第 $i+1$和第 $i(i>=1,i<=n-1)$ 个队列，第 $i+1$ 比第 $i$个的时间片长1倍。
    • 第 $i$个队列开始执行当且仅当前面的 $1，2，3，…,i-1$各队列都是空。但是这是抢占式的：如果此时又有新作业来了，则这第 $i$个队列立即停止运行，转而去服务第1个队列的新来的进程。
    • 第 $1，2，3，…，n-1$个队列采用FCFS调度，第 $n$个队列采用RR调度。
    • 新来的作业总是加入第1个队列中，当它用完该队列对应的时间片，会进入下一级（这里是第2个队列）中，以此类推，直到第$n$级队列，则开始RR。
    • 如果一个作业在某队列中执行完毕，则它原地出局。
  • 过程
    • 如果一个作业很短，例如一个响应式用户操作，那么它进入队列1后，容易在时间片内执行完。而且由于在队列1中，大家的时间片都很短，所以并不需要等待很长时间。
    • 如果一个长作业来了，那么它进入队列1显然跑不完，就进入队列2，用完队列2的时间片再进入队列3，….。
      • 可见，就算一个作业很长，但是它也会第一时间得到响应，因为第1级队列很快。
      • 这个作业一定能执行完，因为它总是可以利用$1，2，3，…,i-1$各队列都是空时，排到它了取执行。如果这个作业执行完了，那么它一定是队列1上执行一点点，队列2上执行2倍时间的任务，队列3上执行4倍时间的任务，以此类推。他是一个渐进的过程。
  • 好处（来自Wikipedia）
    • 为什么称为响应队列？因为不管什么类型的作业，都保证了其响应时间非常短（<=第1级队列的排队时间）
    • 长作业也不会饥饿
    • Give preference to short jobs.
    • Give preference to I/O bound processes.（因为只要去IO了，回来又到队列1了）
    • Separate processes into categories based on their need for the processor.

临界区 #

注意，临界区是访问互斥资源的那段代码。并不是资源！

进程同步的概念 #

• 同步是异步的反义词。之前对异步的解释是：多道程序下，指令执行的先后顺序是不可预期的。现在我们要让他可预期。也就是同步。

• 对临界区的访问

  ，要做到：

  • 空闲让进，忙则等待
  • 有限等待（红绿灯不能一直是红灯）
  • 让权等待（当进程在等待进入时，应进入阻塞，让出核心或线程）

• 实现临界区互斥的基本方法

  • 软件法

    • 4个算法

  • 硬件法

    • 关中断法（因为当且仅当出现中断，才会进行进程调度与切换）
      • 缺点：关中断的权利给了用户，不安全；且限制了多道程序的能力，降低效率。
    • TestAndSet、Swap法（两个原子操作，由函数给出描述，但实际上由硬件实现，不可能被打断（因为根本不属于进程））
    • 硬件法的缺点
      • 不能实现让权等待。（因为是使用while()的方式去等待，所以CPU一直在空转）

  • 信号量法（

    P、V操作也是原子性的

    。）

    • 数值型信号量
      • 一个共享的int型数据。while(sema<=0);
      • 不能实现让权等待。
    • 记录型信号量
      • 可以实现让权等待：即阻塞-唤醒型信号量。
      • 每个信号量都有一个链表，里面是所有等待该信号量的进程。新来一个P操作，就放入链表；空出来一个资源，就从链表取。
    • 信号量常用于前驱图问题、6个经典同步问题。
    • 信号量使用需要注意：先同步，后互斥。（否则就会hold-and-wait，也就是有死锁的可能性）

经典同步问题 #

• 生产者消费者问题
  • 信号量
    • mutex：用于互斥访问缓冲区，所以=1
    • full：缓冲区中的元素个数，所以=0
    • empty：缓冲区中的空位个数，所以=n
  • 生产者
    • P(empty)：申请一个空位
    • P(mutex)，写，V(mutex)：互斥访问缓冲区
    • V(full)：提供一个元素
  • 消费者：
    • P(full)：申请一个元素
    • P(mutex)，读，V(mutex)：互斥访问缓冲区
    • V(empty)：提供一个空位
• 读者写者问题
  • 数据
    • counter：表示当前有多少个读者在读
  • 信号量
    • mutex：互斥访问counter，所以=1
    • rw：读者写者之间的互斥，保证同一时间内要么是读者在操作，要么是写者在操作。所以=1
    • w：防止写者饥饿。读者每次进入也得P(w)，成功进入就V(w)，当写者来了，P(w)；但是写者得写完了才会V(w)。于是，如果写者来了，当写者来之前最后一个读者进入后，写者就把读者封锁了。后面来的读者只能等待。因为是封锁，所以=1.
      • 注意，虽然能防止写者饥饿，但这不属于写者优先。假设很多读者和一个写者几乎同时来，但是写者还是慢了半拍，那么写者也不会排到读者前面。所以这种方式只是防止了饥饿。
  • 读者
    • P(w)：如果写者来了，w就到0了。所以如果写者在等待，读者就被封锁。（防止写者饥饿）
    • P(mutex)：对计数器互斥
    • if(counter==0)P(rw)：如果是第一个读者，就封锁写者（实现读写者之间的互斥）
    • counter++：统计读者数量
    • V(mutex)：对计数器互斥
    • V(w)：已经成功进入
    • reading…..
    • P(mutex)：对计数器互斥
    • counter–：统计读者数量
    • if(counter==0)V(rw)：如果是最后一个读者，撤销封锁（实现读写者之间的互斥）
    • V(mutex)：对计数器互斥
  • 写者
    • P(w)：封锁读者，防止自己饥饿
    • P(rw)：读写者互斥
    • write…..
    • V(rw)：读写者互斥
    • V(w)：撤销封锁
• 哲学家就餐问题
  • 如果哲学家只是简单地申请左右手的筷子，假设有5个哲学家，于是给筷子编号1，2，3，4，5.那么如果这些哲学家同时伸出左手，那么5，1，2，3，4号筷子依次被占用，当他们伸出右手，每个人都发现无筷可拿。这是死锁的一种情况。其他的拿取顺序也会导致类似的死锁。
  • 避免死锁：
    • 限制同时饥饿哲学家数量：如果n个哲学家，可以限制最多有k个哲学家同时感到饥饿，k可以取1到n-1.
    • 限制筷子抓取顺序：也可以让奇数哲学家先拿右手边，偶数哲学家先拿左手边。
  • 信号量：
    • hungry：当前剩余可允许同时感到饥饿的人数，可取1到n-1
    • chopsticks[n]：n支筷子，各自是一个初值1的信号量
  • 哲学家 $i$ ：
    • P(hungry)：申请感到饥饿
    • P(chopsticks[i]) P(chopsticks[(i+1)%5])：分别申请左右手的筷子
    • 干饭
    • V(hungry)：不再感到饥饿
    • V(chopsticks[i]) P(chopsticks[(i+1)%5])：分别放下左右手的筷子
    • 思考
• 抽烟者问题
  • 信号量
    • offer[3]：三种材料组合，各自对应一种信号量，初始值0
    • empty：桌子是否为空（相当于大小为1的缓冲区），所以初始值1
  • 生产者
    • P(empty)：等待桌子为空
    • 产生一个数字 $i$ ，然后V(i)
  • 抽烟者 $i$ ：
    • P(offer[i])：等待自己的材料
    • 抽烟
    • V(empty)：通知生产者
• 商品入库问题
  • 保证A数量-B数量<M，且B数量-A数量<N。
  • 信号量：
    • sa：A和B的数量差，初始化为M-1
    • sb：B和A的数量差，初始化为N-1
    • mutex：每次只能有一个商品入库
  • 以A商品入库为例：
    • V(sa)：A来了，A-B应当增大， 则A-B还能差出去的剩余量应当减少
    • P(mutex)：先同步，后互斥
    • 入库
    • V(mutex)
    • P(sb)：A来了，B-A应当增减少，则B-A还能差出去的剩余量应该减少

可重入代码（纯代码） #

• 即执行过程中不会被更改的代码。也就是说多次执行，不同进程去执行，其逻辑都是一样的。

管程 #

• 对一个特定的数据结构进行封装，在其基础上提供对他的互斥访问、进程同步的方法。这样就可以避免在各个地方分散调用PV而导致不易管理的问题。
  • 即：给临界资源套壳，把互斥情况下对他需要用到的各种操作都封装进来。
  • 例如在实验6的管程OneWay中，封装了arrive、pass、quit方法。可见，管程所封装的方法是较高级的对数据结构进行操作的方法。并不是简单的wait和signal了。
• 管程的组成
  • 封装在内的需要互斥同步的数据结构，这些数据结构是private的。
  • 给数据结构进行初始化的方法（例如构造函数OneWay()）
  • 对数据结构进行操作的方法（例如arrive()、pass()、quit()函数）
• 管程往往是编程语言实现、提供的，例如java中就有。但是实验的时候，C下使我们自己实现的。
• 同一时刻只允许一个进程调用（或者说是进入）管程。这在实验六中采用的是进来就P，出去就V的方式。类似于互斥锁。

进程之间的制约关系 #

• 进程之间有两种制约关系：同步、互斥
  • 同步是指两个进程协同完成一个任务，他们之间的顺序必须严格确定
  • 互斥是指临界资源访问

死锁的概念 #

• 多个进程对

  不可抢占（也就是只能自己主动释放）资源的竞争，导致互相等待

  对方

  释放

  资源才能推进（否则

  永远等待

  。如果只是等待时间长，不能算死锁）。这种情况只能通过

  外力强行剥夺那些不可抢占资源

  才能解开。

  • 如果资源是可抢占的，不可能引起死锁。因为互相等待的任意一方都可以抢占对方占有的资源。

• 常见死锁产生的情况

  • 互相等待对方占有的的资源（因为资源竞争的顺序不当），例如信号量使用顺序不当（此时互相等待对方发出信号）。

死锁的条件 #

• 不可抢占的互斥资源
  • 于是，资源只能一方占有且只能主动释放
• hold-and-wait
  • 在等待其他资源，导致无法执行的时候仍然不释放自己手头的资源
• 循环等待（如果是多实例资源，小心环外搅局者）
  • 即“互相等待”的推广。考虑两个进程互相等待，会造成死锁；如果是很多进程，想要造成死锁，类比哲学家就餐，也就是1等2，2等3，3等4，4又等1，于是谁也不会释放手头的资源，却又在等待其他人手里的资源。
  • 但是需要注意，这个等待的资源必须是只被这个环上的下一个进程所持有的。如果同时还有不属于这个环的进程持有，那么这个死锁在那个不属于这个环的进程释放资源后，可能就会被打破。这种不属于循环等待。也就无死锁。（永远等待才叫死锁。如果只是等待时间长，不能算死锁）
  • 但是如果这些资源都是单实例资源，那么不可能存在如上所述的“环外搅局者”。因为这个资源只有一份，只能是环上的进程所持有。这种情况，只要成环，就符合循环等待的定义了。

所以，如果一些进程是以hold-and-wait的方式互相（即资源分配图成环）**等待**不可抢占的互斥资源的，则死锁了。

（一定要注意循环等待的定义。只要存在环外搅局者，就不能叫循环等待，也就不是死锁了。）

因此，在环上的资源都是单实例资源的情况下，资源分配图是有环图是死锁的充要条件；但是在多实例资源下，其只是必要条件。

死锁处理三方法 #

• 死锁预防
  • 在运行前，设置限制条件，打破死锁的几个条件
• 死锁避免
  • 在运行过程中，避免进入不安全状态（寻找可能的资源分配安全顺序）
• 死锁检测与消除
  • 不加以任何干预。只是定期对死锁进行探测。如果发生了死锁需要能探测到，并且能解开它。
  • Windows系统采用这种方法，而且解开死锁的方式是重启电脑。

死锁预防和死锁避免的区别 #

• 前者是在运行环境下给出各种限制；后者是发现将要进入不安全状态了才会限制。
• 很明显，前者是死锁避免的超集，导致限制条件过于保姆（就算是资源空闲了，我也不分配它），于是会对系统效率有非常显著的影响。
• 后者虽然效率高，但是由于在很多情况下很难探测不安全状态（因为无法预测将来的资源请求），所以实用性不高。

死锁预防 #

• 破坏互斥条件（难以实施）

  • 不可能。之所以要互斥是有原因的。

• 破坏不剥夺条件

  • 只能是易于恢复现场的资源，例如CPU。
  • 打印机显然不能剥夺

• 破坏hold-and-wait：

  资源预分配策略

  • 当且仅当进程把需要的资源一次性都申请到了，它才能开始运行，否则只能一直等待下去。
  • 如果有的资源就算是只用1us，那也得一直占着。显然效率非常低。
  • 而且假设一个进程需要系统内所有类型的资源，它就饥饿了。因为等到一个时刻，系统所有资源都没人用，几乎不可能。

• 破坏循环等待（难以实施）：

  资源顺序分配策略

  • 编号法

死锁避免 #

• 安全状态
  • 如果能找出一个安全序列（一个安全的资源分配序列），那当前就是安全状态。
  • 如果当前是不安全状态，则系统可能发生死锁（但不是一定发生死锁，因为假设其他进程能释放这种资源就可能打破死锁）
  • 死锁避免就是避免进入不安全状态。
• 作用
  • 死锁避免充当了一个资源管理员的角色。进程提出资源分配请求，死锁避免算法就检查（进行假分配），假设本次分配后，整体的局面是如何的，然后从这个局面里头寻找安全序列，如果找不到就说明如果同意了本次请求，系统就会进入不安全状态，于是拒绝此请求。

死锁检测：基于死锁定理 #

• 一个系统的资源分配图不能被完全简化（即所有的进程都执行完毕）的充分必要条件是发生了死锁。
• 因此，死锁检测是检测的资源分配图。

死锁解除 #

• 资源剥夺法：强制剥夺资源
• 撤销进程法：强制终止死锁的进程
• 回退法：回退到之前的（当时未发生死锁的）还原点处。这里的还原势必要剥夺资源，但这里的剥夺是自愿的。

内存管理 #

Caching —— the main memory can be viewed as a last cache for secondary storage.

内存管理的基本内容 #

• 内存空间的分配
  • 具体内存的分配由OS来做，于是编程时不需要像汇编那样去手动制定内存单元地址了。
• 地址转换
  • 将逻辑地址（例如C++的指针的值）转换成物理地址
• 内存空间的扩充
  • 虚存
• 保护
  • 保证各进程的内存空间互不干扰

程序的链接 #

• 编译时静态链接

  • 在编译形成可执行文件时就连接上库文件

• 装入时动态链接

  • 把程序装入内存时，才链接

• 运行时

  动态链接

  • 程序运行到需要该模块时，才把它装入内存并链接
  • 程序刚装入时是几乎没有链接的。这个和装入时动态链接的区别在于后者是一链接就全连接上了，更占用内存空间。

程序的装入 #

• 绝对装入
  • 这种程序就像汇编一样，里面的地址给出的是实打实的物理地址，或者是符号地址，经汇编器转换为物理地址。在装入时，就是原封不动放入内存即可！
  • 这样的方式一般只能支持单道程序。你不能预测下一个装进来的程序会不会覆盖掉原来的那个。
• 静态重定位装入（又称重定位装入，硬性修改指令中的地址实现）
  • 程序中的地址使用了虚拟地址。在装入时，把这些虚拟地址**全都转换（采用原地替换的方式）（因为是直接替换，所以是静态的）**成物理地址。
  • 这种装入只是让编程人员方便了，且支持了多道程序（因为OS可以为不同的程序分配内存空间了），但是由于还是硬性替换，在装入时直接定死了内存空间的范围，所以程序内存空间无法扩充与浮动。
  • 必须一次性被装入。因此如果要运行程序，内存可用容量必须>=所需空间。
  • 程序装入后，在运行时就没什么事了，一切都和绝对装入没有区别。而下面要说的动态重定位则是在运行时做文章。
• 动态重定位装入（又称运行时装入，运行时解释地址实现）
  • 程序中的地址使用了虚拟地址。但是在装入时，只装入当前运行必要的部分，且就算装入了也不进行物理地址转换。
  • 物理地址转换在当需要转换时才进行转换（而且并不去替换原来的指令），例如当前要仿存，那么指令给出虚拟地址（即相对地址），经过和重定位寄存器（相当于基址寄存器）加和，得以正确访存。
  • 因为装入时只装入一小部分，所以不能保证程序是连续的。也就是程序会存在非连续空间中。而且由于重定位寄存器的存在，使程序分散存储成为可能。
  • 因为地址变换并不真正改变指令本身，而是在访存时才现去解释他，所以支持程序的浮动，支持内存动态申请。而且因为一开始只装入一点，所以就算没有充足的内存也可以运行这个程序。

内存的保护 #

• 方法1（用于固定分配）：CPU中的上下限寄存器，保存了程序所在内存空间的物理地址上、下限。访存时比较即可。
• 方法2（用于固定分配、固定分区连续分配、可变分区连续分配）：Base和Limit寄存器。其中Base存放基址（物理地址），Limit存放空间长度（逻辑地址）；每次访存时，先用逻辑地址和Limit做比较，如果没有超过Limit，再和Base相加，得到物理地址。

内存的扩充 #

• 覆盖
  • 内存分为固定区和覆盖区。固定区是安全的，程序可以在里面常驻；覆盖区是不安全的，会在运行时（Runtime）经常进行内容覆盖。
  • 例子：OS肯定放在固定区；假如来一个大程序，那么他的主函数应该在固定区，它的各个不经常用到的或周期性用到的函数在外存中存放。当执行到需要调用那个函数时，把那段函数代码从外存读到覆盖区中进行覆盖，于是就能执行他了。当执行下一个函数，类似。
  • 好处：可以运行比内存总量大得多的程序。但是如果某个模块过大，大于内存总量，仍然是无法执行的。
• 交换
  • 交换即中程调度。
• 二者的区别与联系
  • 注意，交换是不同进程之间的，而覆盖一般是统一进程的不同代码模块之间的。二者都是用于“扩充”内存的。
  • 现代的虚存往往使用交换。通过换入换出，可得到一个交换区+内存大小的逻辑内存空间。覆盖现在已经淘汰。

内存的共享 #

• 注意，内存的共享对用户是透明的。所以被共享的内容不能是临界资源。注意，它和并发访问是两个概念。
• 所以，代码一定是纯代码，数据一定是不可修改的常量（否则就是临界资源了。）。

连续内存管理方式——单一连续分配 #

• 把内存空间暴力地分成OS区和用户程序区，因此只支持单道程序。
• 优点：无外碎片。
• 缺点：显然存在内碎片。因为程序很难和这块区域正好一样大。

连续内存管理方式——固定分区分配 #

• 把内存空间暴力地分成若干分区。这些分区可以是大小相等的，也可以是大小不同的。
• 维护一张分区表，其中的字段有base、limit、是否正在使用。
• 当需要分配时，查表即可。
• 优点：无外碎片。
• 缺点：显然存在内碎片。因为程序很难和这块区域正好一样大。

连续内存管理方式——动态分区分配 #

• 一开始内存是空的，可以看做是一块大的连续区域。随着进程加入，这块区域逐渐被瓜分。**每加入一个新的进程（包括换入一个进程），原有的一个分区就被瓜分成两个分区，其中一个是程序使用的区域，另一个就是外碎片（空闲分区剩余部分）。*每结束一个进程（包括换出一个进程），就会合并其上下的空闲分区，使得2-3个分区*合并成同一个分区。
• 外碎片可以通过紧凑算法解决，但是大多数硬件没有给出支持。
• 找空闲分区算法：
  • 首次适应：从上到下遍历这些分区，找到第一个放得下这个程序的。
    • 是效果最好的算法。
  • 最佳适应：找放得下这个程序的分区中最小的那个。
    • 糟糕的算法。
    • 每次“最佳”适应都会留下更小的外碎片，而且越“佳”就越小，导致内存利用率大幅下降。
  • 最坏适应：找放得下这个程序的分区中最大的那个。
    • 糟糕的算法。
    • 虽然瓜分后产生的外碎片比较大，有重新利用的可能，但是这种算法就像是斗地主的时候把炸弹拆开了用一样啥比，破坏了能装更大程序进来的可能。这导致内存中存在的最大的分区的体积越来越小。
  • 临近适应：首次适应。只不过从上次找到了的地方开始找，而不是从头开始找。
• 优点
  • 灵活，无内碎片
• 缺点
  • 有很多外碎片
• （注意，这里产生的碎片类型和前两种方式反过来了）

Introduction To 非连续内存管理方式 #

• 非连续分区的好处：在连续分区中，装下一个程序的关键在于有大于等于其大小的连续空间。但是非连续分区只要求剩余空间总大小大于等于其大小即可。
• 分段和分页的区别：分区大小是否是固定的。

非连续内存管理方式——分页管理 #

• 分页和固定分区非常相似，但是又有区别。前者的“块”要比后者的“区”小得多，并且由于程序也被分成一块一块地，所以虽然一个程序占用

  很多块

  ，却只在其占用的

  最后一块

  产生平均

  半块

  大小的内碎片。因此，分页相比固定分区而言，可以产生小得多的内碎片。

  • 好处：相比固定分区，内碎片变得非常少，且保留不会产生外碎片的优点

• 三种叫法

  • 最小单位在进程中，称为页（联想页表）；在内存中，称为块或帧（联想内存块、栈帧）；在外存中，也是称为块（联想磁盘块）。

• 页面大小的权衡

  • 过小：导致页表过长，占用内存空间（进程对应的页表驻留内存）；程序内存分配和寻址过于繁杂，降低效率。
  • 过大：内碎片过大。极限情况：如果块比程序还大，就退化成固定分区管理了。

• 逻辑

  地址结构

  • 对于单级页表来说，地址由页号+页内偏移量构成。前者决定的了页的总数，后者决定了页的大小。
  • 因为是逻辑地址，所以该地址结构的表示范围决定了虚拟内存寻址范围。

• 页表

  • 页表项表达了页号和内存块号的对应关系。
  • 当进程未被调度，指向页表的Base指针和limit放在其PCB里面；当进程被调度，CPU的PTR（PageTableRegister）寄存器被设置该进程对应的Base和Limit。于是，就可以使用页表寻址了。

采用静态重定位装入：可理解为当程序被装入时，页表也被装入内存。

采用运行时装入：当进程被调度时，才把页表实际装入内存中。如果采用了二级页表的形式，当被调度时只需装入顶级页表即可（且规定顶级页表只能由一页构成，这是约定俗成的规定）。

• 单级页表逻辑地址转换（

  地址变换机构

  ）

  • 逻辑地址除以块大小，得到页号；模块大小，得到偏移量。
  • 拿页号和Limit寄存器比较，如果大于，那么越界，Abort；如果小于等于，那么拿页号和Base寄存器相加，得到物理地址，去寻址即可。（可以看出，不亏是固定分区的翻版，连逻辑地址转换都是一个模子）
  • 为什么不对偏移量进行越界判断？
    • 考虑程序的最后一页：因为只要分给它这一页了，就是它这个进程的了。就算不小心访问到内碎片了，也对整个系统没有影响。
    • 考虑一般的页：而且再怎么也不会跳出了页面的大小，因为它是模出来的。
    • 所以综上不需要对偏移量进行判断。

• 快表（相联存储器 TLB）（

  带有快表的

  地址变换机构）

  • 快表是位于地址变换机构中的一个Cache。其工作方式和Cache一样，只不过其存储的对象是页表项。其中保存了最近用到过的页表项。（索引是页号，被索引元素是对应块号）
  • 变换时，先在TLB中找，没有的话就访存，并且把取回来的同时也存入TLB。
  • 相对而言，主存中驻留的那个页表就称为慢表。

• 二级页表

  • 如果调度时，要把进程的页表全都装入内存，那么这个可能过大。（例如某内存检查程序需要占用大部分内存空间，假设程序代码本身只需要1个页面，但是页表却需要10个页面才能装下（因为要包含很多页），这非常的浪费空间）
  • 于是不是说那个页表需要10个页面吗。现在假设这10个页面已经调入了内存，里面都是页表。现在需要建立一个页表来对这10个页面进行管理。为什么要建立新页表？因为这10个页面一般不是连续分配到内存中的，而是见缝插针的。如果他们连续，我们完全不需要二级页表，而是base、limit就解决了。于是二级页表项就是一个二级页表号到二级页表块号的映射。比如我1号页表存在了第7块，2号页表存在了第11块。（与一般页表的区别是：“2号页面存在了第11块”）。因为一个页表就是一页的大小，所以实际上就是实现了分页管理。只不过这里的页的内容不是程序或数据，而是页表。
  • 所以，假设现在10个页面装下了整张页表，这10个页面分散存储在了内存的10个块中，那么现在建立一个页号范围是1-10的页表，来管理这10个页面，就是二级页表。

• 二级页表的逻辑地址空间

  • 于是，就可以通过一级页表的索引找到二级页表中的页表项了。所以由一级页号、二级页号（这个编号显然是在一个占用空间大小为一页的页表内编号，因为逻辑地址空间总长度相对不采用一级页表的情况是不变的（假设都是32位，页内偏移地址为12位（因为页面大小4KB）），那么二级页号势必就被砍了（原来是32-12=20位，现在因为页面大小是4KB，页表项大小是4B，那么一页可以放下1K个页表项，需要10位地址来表示，那么因为二级页表被分成了很多页，被进行了分页管理，所以每个二级页表所在页就是页大小，也就是需要10位编址，还剩下10位编址，显然正好是可以编一页的大小（因为一页可以容纳1K个页表项），正好给到一级页表编址））、和页内偏移量（这个和单级页表没有区别）构成。
  • 因此，可以便于实现下面的“运行时装入”思想：因为为了方便查找，一级页表一般限制在一页的大小，所以装入时只装入一级页表可谓轻轻松松。然后在程序运行过程中，用到了哪个二级页表页（也就是一级页表号所在页），就把哪个页动态装入，并更新一级页表。

• 常见的几个结构

结构	上级结构	说明	一般长度
页表项	最低级页表	存放了页面号到块号的映射	4B
页			4KB
一级页表页表项		存放了一级页号到所在块号的映射	4B

非连续内存管理方式——分段管理 #

分段管理是动态分区的升级版，分页管理是固定分区的升级版。

• 逻辑地址格式：段号+段内偏移量。
  • 和分页不同，这里的段号和偏移量需要程序员给出。可以认为这两部分地址是人指定的，如果一个段并没有达到其最大可表示长度，那么逻辑地址之间是有跳变的。而分页中，其逻辑地址只是对原逻辑地址进行了划分，逻辑地址是连续的。
  • 在汇编中，可以通过offset等指令或使用标号让编译器自动实现分段逻辑地址的制定。并不需要手敲。
• 段表
  • 和页表类似，也是记录了哪一段在内存的哪个地方。
  • 但是分段管理类似于动态分区，其给出了每一段的base和limit（而分页由于大小一致，且非常规整，只需给出编号）。段号是隐式给出的（就是表项的索引），或是显式给出的（直接作为一些位）。从0开始递增。
• 地址转换
  • 首先判断是否越界。因为段长不固定，所以这里不仅查看段号是否越界（即越过段表长度），还要查看段内偏移是否越界。
  • CPU中有段表的Base和Limit寄存器，其作用和页表Base、Limit寄存器一样，都是为了执行时能够访问段表。

分段分页方式的比较 #

• 分页方式的内碎片小，不会产生外碎片（因为继承自固定分区），对程序员透明；
• 分段方式无内碎片（因为继承自动态分区），但是产生外碎片，对程序员非透明；
• 分页方式能提升内存利用率（其碎片相比分段小得多），分段方式便于**==整体结构的==共享**，段能体现程序的逻辑结构（不像分页拆的什么也看不出来）。

比较	分页	分段
目的	方便系统管理	方便用户理解
地址	一维（只需要一个int型即可映射到物理地址）	二维（需要同时给出段号和段内地址，且逻辑地址空间不连续）
逻辑性	无逻辑瞎几把分页	按功能逻辑进行分段
单元大小	页的大小是相等的	段的大小是可变的（但是由于段表项的长度限制，有上限）
共享	难	易
动态链接	难	易
保护	比较页号	比较段号和段内地址

非连续内存管理方式——段页式管理 #

• 思想是两者结合，“先段后页”。先将程序正常分段管理，但是每个段都拆成若干页进行分页管理。因此，每个段就对应了一个页表。**一个进程有多少段，就可以有多少张页表。**因此，一个进程可以有一个段表和若干页表。
• 逻辑地址格式
  • 段表中给出的段内偏移地址，实际上被当成了分页管理中的逻辑地址。因此结构是段号，页号，页内偏移量。
  • 这就导致需要三次访存：先访问段表，再访问所在段对应的页表，最后才去取到数据。因此可以用快表加速。快表的索引是段号+段内页号，被索引元素是块号。

虚存的概念 #

• 传统管理方式的问题
  • 程序必须全部装入内存中才能运行，这就导致大程序装不进来，或者程序过多就无法再装入
  • 程序就算是阻塞，也占用内存空间。就算是它因为阻塞而让出了CPU，又有什么用呢？新的程序无法取代他，因为连内存都进不来。
• 理论依据：局部性原理
  • 时间局部性：现在用的，一会可能也要用
  • 空间局部性：现在访问这块地址，不久后这块及其周围地址也回访问
  • 虚拟存储器就是基于局部性原理，以此为指导进行动态的页面置换。

Introduction To 请求式内存管理方式 #

• 所谓请求式，就是程序开始运行时，只把开始必须的程序、数据装入内存，其他的都留在外存。等到真正需要用到了，却不在内存中，则产生缺页中断，请求OS把他调入内存。（Lazy Loading）
• 以请求式进行管理，实现了虚拟存储。
• 因为整个都是基于局部性原理，所以内存看起来就像一个大Cache（以至于它的替换算法都直接照搬Cache那一套，例如LRU）。它只会存放当前需要用到的程序和数据，并在逻辑上给用户提供一种好像它整个都装进去了的假象。

请求式内存管理方式——请求分页管理 #

• 页表项格式
  • 为了支持虚存，在原有基础上添加“是否在内存中”位、LRU位，脏位。分别用于标志是否在内存中、用于实现局部性原理、用于懒写回。
• 命中：正常访存
  • 访问页表，并修改其LRU位，如果是写指令还要修改脏位。
  • 这个过程也可用TLB加速。
• 不命中：缺页中断
  • 如果进程访问的页面不在内存中（查页表可知），则产生一个缺页中断（是一种特殊的内中断），该中断在指令执行的过程中就会打断进程的执行（而不是像一般中断那样，执行完才检查中断）；一条指令的执行可能产生多次缺页中断（例如好几个操作数分别不在同一页）
  • 缺页中断产生则立即处理。从外存中找到缺页，看看内存是否满，如果没满就装入，如果满了就利用页面置换算法换出。在换出时，如果被置了脏位，需要写回外存。

页面置换算法 #

• OPT - 最佳置换算法
  • 确实最佳，但是非常理想主义：它选择最长时间以内不会被访问的页进行换出。显然这样做最符合局部性原理，理论上能得到最小的缺页率。但是不可能实现（无法预知未来）。

可以看做是LRU的对称算法（但是考察侧重点不一样）。LRU是综合考虑当前时间点之前（考察使用次数），而OPT是综合考虑当前时间点之后（考察时间间隔长短）。

• FIFO - 先进先出算法
  • 选择在内存中呆的时间最久的页面换出。这种算法比较暴力，只考虑大家在内存中待的时间长度应该是公平的。但是对于那些频繁使用的部分，他们本该呆的更久。把他们换走，不符合局部性原理，会导致更多缺页中断的发生。
  • 会产生Belady异常——如果给进程分配更多的物理块（例如，一个进程原来只能有3个物理块，倒换来倒换去，现在让他4个物理块倒换），会导致缺页中断次数不降反升。只有FIFO这种算法才会导致Belady异常。
• LRU - 最近最少使用算法
  • 一听这名字就知道奔着局部性原理去了。
  • 因为采用堆栈实现，而不是FIFO那种队列，经过实验证明，堆栈类算法必然不会有Belady异常，但是队列会有。因为采用堆栈实现，它的性能也会比FIFO要好。
• CLOCK（NRU）- 时钟算法（最近没有使用算法、第二次机会算法）
  • LRU的性能好（几乎接近OPT），但是需要额外的堆栈和寄存器来实现；FIFO性能差，但是不需要什么额外条件；所以设计CLOCK算法的目的是找到一种性能接近LRU，但是额外开销（自己就能跑）的算法。
  • 叫CLOCK的原因是：它在需要寻找替换对象的时候，会有指针按循环的方式遍历整个内存空间。因为是循环，并且是循环遍历，这就像一个CLOCK（钟表）一样。
  • 注意，指针只是寻找替换目标并进行替换而使用。并不是用于访问。当正常访问时，只是会置访问位为1，指针是不移动的。当需要替换， 指针才来活了：它循环遍历内存空间，并最终指向替换目标的位置，完成替换，然后紧接着指向下一单元（防止刚装入的又有被换出的危险）。

也就是“按表走上了”。所以叫CLOCK算法。

• • 在内存块上做文章：每个块都关联一个访问位，表示最近是否被使用过（这是一个bool类型的，也就是只能是0或1）。
    • 如果某页被访问到了，其对应的内存块的访问位设为1.
    • 如果某页刚被装入，其对应的内存块的访问位设为1，并且指针要指向其下一个位置。
    • 如果某页需要被装入，并且没地方了，需要替换，则指针就来活了：按表走一波，只要找到访问位=1的，就设置为0；只要找到一个访问位=0的，就停止遍历，并作为受害者。
• 改进CLOCK（NRU）算法——优先考虑脏位=0的进行替换
  • 思想：如果脏位=1，说明还是有用的。并且需要写回还浪费一点时间。所以尽量不替换他们。
  • 需要替换时：
    • 第一步：指针先走一轮遍历寻找脏位=0，且访问位=0的，并且这次遍历不修改访问位。
    • 第二步：如果没找到，则继续遍历，但是这次遍历见了1就改0，并且寻找访问位=0的就直接确定受害者了，与脏位没有关系了。重复第二步。
  • 可见，改进CLOCK算法只是在正常CLOCK之前加了一步，也就是先找一遍有没有访问位=0且脏位=0的，如果没有，直接跑正常CLOCK即可。

页面分配算法 #

• 驻留集及其大小
  • 驻留集是为某进程分配的物理块的集合。
  • 如果驻留集过小，会导致缺页率升高，但是可以同时调入更多程序；如果驻留集过大，随着驻留集大小提升到一定阈值，再往上并没有性能的显著提升，所以是浪费行为（因为局部性原理，现在能用到的有效的页面并不是那么多）。
• 驻留集如何确定大小
  • 固定大小（驻留集大小不能改变）
    • 程序装入时就确定了其驻留集大小。缺点：并不能很好地确定大小是否合适。没有什么依据。
  • 可变分配全局置换（只要缺页就盲目增加驻留集大小）
    • 每次缺页，都给这个进程添加一个新的物理块。也就是调入页面时，并不需要置换，而是直接拿个新块装入了。
    • 所谓全局置换，就是在内存中的所有块中进行置换。
  • 可变分配局部置换（根据缺页情况动态调整驻留集大小）
    • 缺页还是运行页面置换算法，在驻留集范围内置换。如果缺页率过高，就给这个进程多分俩物理块；反之可以给这个进程减少俩物理块。
    • 所谓局部置换，就是在驻留集范围内进行置换。

页面调入算法 #

• 预读
  • CPU空闲的时候进行Page Caching。
• 请求
  • 即正常的方式。

抖动（即当驻留集大小小于当前频繁访问的页面数量） #

• 页面置换最糟糕的情况是：刚刚换出的页面应为还要使用又要立即被换进来。显然，这是因为驻留集不够大。例如：现在需要频繁使用的页面有5个，但是驻留集大小为3，那么3个空位要来回倒换5个页面，想想都头大。
• 这会导致系统大部分资源都用来响应缺页中断了。

当前时刻的工作集跟踪方法 #

• 类似于驻留集，工作集指的是最近这段时间内访问过的页面的集合。
• 防止抖动的精髓在于：驻留集至少要比工作集大，否则根据局部性原理，有较大概率发生抖动。
• 工作集可以使用一个工作集窗口跟踪实现，其有点类似于LRU：例如窗口大小为5，则跟踪当前页面及其之前访问过的4个页面，把他们加入当前这个时刻的工作集。因为随着时间变化，工作集窗口会移动，导致工作集的内容和大小都会发生变化（可以预见，程序的局部性越好，其工作集大小就越小于工作集窗口。），所以我们说工作集只能是基于当前时刻的。
• 系统需要保证每个进程的工作集都小于等于其驻留集。如果不能保证这一点，就很容易发生抖动。于是，需要暂时挂起一些进程，让他们腾出空闲块，从而扩充现行各进程的驻留集。

文件管理 #

文件系统的体系结构 #

• 文件系统接口
• 用于操纵对象和管理对象的软件（自顶向下分为：）
  • 逻辑文件系统层
    • 实现文件相关访问和操作，包括保护（例如权限控制）
  • 基本IO管理程序层
    • 进行逻辑地址和物理地址映射、管理磁盘空闲快、设置IO缓冲区
  • 物理文件系统层（由OS提供的用于控制外设的层）
    • 利用驱动程序，处理内存与磁盘之间的数据交换
  • 设备驱动程序层（由厂家提供的用于控制外设的层）
    • RT
• 文件系统的对象
  • 包括文件、目录（目录项应当包含文件名、属性、物理存储空间指针）、外存存储空间。

什么是Open和Close #

• 用户对文件进行读写时，需要从磁盘上找到他。寻找的方式是通过检索文件目录进行。于是需要通过文件名去检索文件目录（如前所述，检索该目录可以在对应记录下获得指向文件的指针和该文件的属性等）。
• 当找到了，就把文件的属性、指向物理位置的指针存放到一个打开文件表中，并把这个文件表项的索引返回给用户（即fd）。
• 以后对文件的任何操作，包括移动读写指针、关闭等，都不需要提供文件名，只需提供fd。因为通过fd可以直接找到表项进而找到指针，比按照文件名检索目录要快得多。
• 当操作完成，可调用close。也就是把这个fd对应的文件表项删除。

逻辑文件的分类 #

• 按是否有结构
  • 有结构文件（DBMS采用）：由多个记录构成的文件。每个记录里面是数据，这些记录可以是定长的可以是变长的。
    • 定长记录文件
    • 变长记录文件
  • 无结构文件：可以理解为记录大小是1B的定长记录文件
    • 无结构文件可通过读写指针来读取，相当于有一个指针在遍历所有的大小为1B的记录。
    • 常见的文件都是无结构的，例如文本文件、可执行文件、库文件。
• 按文件的组织方式
  • 顺序文件
    • 按一系列记录按照一定顺序排列
    • 如果能按主码排序，则可以折半查找增加查找效率，但是大多数情况下不可以。因为排序也耗时。
    • 顺序存储设备只能装入顺序文件才能正常工作。例如磁带。
  • 索引文件
    • 每个记录都被安排了一个索引，以类似指针数组的形式进行索引
  • 索引顺序文件
    • 索引是指向一组顺序文件的。是前面两种的结合：组内是顺序文件的方式，组间是索引文件的方式。
      • 在原顺序文件的基础上，每过100个就划分一个组，索引文件中的每个表项就指向其对应的组的第一个记录，并且其索引关键字就是此第一个记录的值。
    • 因为组内顺序，组间索引，这个就变成了类似于书本分页的样子。可以认为每一组就是一页，然后可以使用页码去快速翻到某一页
    • 例如$10^6$个记录，那么如果组大小是100，那么需要$10^4$个索引项构成的表，其需要查找的记录数约是原顺序文件的2次开根次。
    • 如果进行二级索引，也就是对一级索引表（因为索引表本身还是顺序文件）再次进行顺序索引，也就是说二级索引只需要$10^2$个记录。那么查找所需次数是原来的3次开根次。
    • 顺序索引文件能够大大提速顺序文件的查找。但是对于增加、删除、修改，可以通过overflow表来实现。类比数据库重组，可以实现文件的维护。

记录寻址（寻的是顺序文件中的逻辑地址） #

• 隐式寻址（用于实现

  顺序访问

  ）

  • 对于定长记录，可以拿一个指针从上向下遍历，每次+长度。
  • 对于变长记录，可以拿一个指针从上向下遍历，每次+变长。

• 显式寻址（

  仅

  对定长记录有效，用于实现

  随机访问

  ）

  • 对于定长记录，可以通过长度乘索引，算出逻辑地址。这样就不用遍历了。
  • 但是变长记录由于不能这样算出逻辑地址，所以还是只能从上到下遍历。因此变长记录不可随机访问。

直接文件（直接根据键算出物理地址） #

• 这种文件组织形式，知道了记录的关键字，就可以算出文件，以关键字为键，则实现了一次键值转换。
• 常用的键值转换方式就是哈希。OS提供一个哈希函数，可以用它实现直接文件。于是，可以用关键字映射到物理地址。

变长记录文件的索引 #

• 思想：把顺序访问变长记录文件转化为随机访问定长记录文件。索引文件就是一个定长记录文件，其中每个记录是指向其索引的变长记录文件中的记录的。
• 而且索引文件的索引属性是可以自己定义的，比如对于图书管理系统，可以使用ISBN号，也可以使用作者等等。因此为了在各种情况下查找都会快一些，可以建立多张索引属性不同的索引表。
• 缺点：有额外的存储开销（要多存索引表）

FCB的结构 #

• 基本信息
  • 名称，指向磁盘物理块的指针，逻辑结构（流式文件还是记录式），物理结构（是顺序的，链接的还是索引的），及其他的文件属性
• 权限信息
  • ACL
• 使用信息
  • 脏位，封锁，打开数等

文件目录查找优化——i节点指针 #

• 文件系统实现按名存取。查找一个文件的方法在于拿着文件名和文件目录里面的文件进行比对。意味着可能要对文件目录进行遍历。
• 如果文件目录的每个节点都存放关于文件的全部信息（即FCB内的全部信息），那么文件目录占用的空间将会过大，因为每个目录项会过大。文件目录整个是存放在磁盘上的，那么查找一次文件，可能需要调出过多的文件目录所在的磁盘块，会导致访问一个文件，却需要提前访问好几十次磁盘。
• 解决这个问题的方法就是精简文件目录。让每个目录项存放尽可能少的信息，于是linux把文件目录和文件其他信息独立开来，前者仍然叫文件目录，后者叫inode表。inode相当于原来的FCB，然后文件目录项只保存文件名（用于查找文件，作为主码）和指向该文件inode的指针。于是就把文件目录和FCB独立了：文件目录只负责文件查找，找到了就直接通过inode可以调出inode表中该文件的所有信息。

磁盘inode表、内存inode表 #

• inode表原本是存在磁盘上的。当一个文件被open了，就会把其inode拷贝一份放到内存中，并且增加若干字段，例如打开计数、是否上锁等。
• 老师称后者为aFCB，即active FCB。

U区、内存inode表、文件 #

• 进程的U区存放了fd和指向内存inode表的指针（显然，fd是局限于进程之中的）。每次有新的一次打开，都会新开一个内存中的inode节点，即便它是同一个文件。
• 当且仅当进程创建了子进程，U区被复制，inode表中原来那些文件的引用数才能被+1.（如果单纯打开第二遍是不会+1的）。

FCB和inode表 #

• FCB在linux系统中基本就是inode表。因为inode表的信息和FCB是一样的。

树形文件结构 #

• 其中包含两种节点：目录节点和文件节点。分别对应的FCB是文件FCB和目录FCB。为了提升效率，FCB应当可以在目录FCB和文件FCB两种FCB模式下相互转换。所以目录FCB和文件FCB都是存在同一个inode中的，只不过其中有一位（例如isFile）是不同的。

文件目录中的查找方法 #

• 线性查找法
  • 把给出的目标路径拆分，把其中的分量进行拆分，也就是各级路径的名称。一开始从根目录开始，按线性的方式（因为每一级目录终归还是一个线性表，虽然整体是树的结构）比对是否是需要的名称，如果是需要的，则找到他的inode，（当然是个目录FCB），其中必然记录了该目录的那个线性表存在哪个磁盘块上，于是递归地以此类推。
• Hash法
  • 利用Hash来直接算出文件在目录的哪里，可能一次性就定位到其目录项了，然后直接利用指针跑到inode上，就可以完成对文件的访问
  • 缺点：
    • 会产生哈希冲突
    • 不支持通配符（例如任意文件： *.*）

文件共享 #

• DAG+inode法（硬链接法）
  • 可以让一个文件拥有多个所在目录。也就是可以允许多个目录下的文件目录项指向这个文件，但是这样会破坏树的结构，不过无所谓。
  • 如果把目录中各个文件的数据都放在文件目录中，例如所在磁盘块、长度等信息，那么这样共享显然会造成数据不一致：如果一个目录下，对这个文件更改了，却没有通知另一个共享了该文件的目录，就会出现问题。
  • 可以采用inode解决：也就是上面说的把文件目录和inode表独立出来的方法。这样，一处修改就能在任意处得到体现。
    • 此时，inode中有“链接数”字段。这个主要是防止其中一方删除文件导致的空指针。当每次删除，链接数自减，当=0时才删除。
• 符号链接（软链接法）（可以不用DAG图，也能实现）
  • 引入一种新的文件类型：LINK类型。其中包含了被链接文件的绝对路径。每次用户要对这个LINK类型的文件进行读写时，这个读写请求就会被OS中间件截获，系统对LINK的任何操作都会变成对被链接文件进行读写。
  • 问题：会增大磁盘访问的频率。因为还需要额外去找被链接的文件，不像DAG法，直接就拿到物理地址指针了。
  • 相比DAG好处：是标准的文件目录树结构，其算法更容易实现。且如果文件主删除文件，不会出现空指针。
• 通病
  • 无论采用哪种方法，因为同一个文件能通过多种方式到达，会导致遍历文件系统的时候一些文件被遍历了很多次。

域（Domain） #

• 域是对一些对象及其允许的访问方式构成的集合。
• 可以理解为，权限组就是域（的一种）。（但是域是对进程而言的，权限组是对用户而言的）
• 进程在不同的运行阶段中可以切换其所在的域，这种方式称为进程和域之间的动态联系方式（当然也有静态联系方式）。这样就能做到“授权最小化”，也就是不需要在运行前就给他所有可能用到的权限。

访问矩阵 #

• 实际上是一张表，每一列是一种资源、一个文件或一个域，每一行是一个域。横着看，就是这个域对于各个文件有什么权限。竖着看，就是这个文件在不同的域下允许被以什么样的方式访问。对于资源或文件，可以有R、W、X、O四种方式，对于域，可以有S、C两种方式。

访问方式（访问权限）	所属对象类型	解释
R	资源或文件	读取
W	资源或文件	写入
X	资源或文件	执行
R*	资源或文件	读取（限制拷贝）
W*	资源或文件	写入（限制拷贝）
X*	资源或文件	执行（限制拷贝）
O	资源或文件	拥有：如果在该域下拥有此文件，那么它可以任意修改这个文件在其他任意域下的访问方式。
S	域	切换：可以从当前域切换到这个标注了S的域去。（但是如果目标域在当前域这里没有标S，那可就回不来了。）
C	域	控制：可以任意修改标注了C的那个域，也就是修改其访问的对象及其访问方式

• C和O的区别
  • 一个是对域，一个是对资源或文件。
  • 所以，一个是改一行，一个是改一列。
• 限制拷贝
  • 如果拥有的权限是属于限制拷贝的，那么可以把他拷贝给其他域，但是其他域的那个副本就是不带“*”的，也就是不能接着像泛洪一样再拷贝给其他域。

访问矩阵的实现——ACL表和文件权限表 #

因为每个域涉及的文件可能不多，所以这个矩阵过于稀疏。于是就可以给出以下的实现方式：

• ACL表（与每个文件关联）
  • ACL表实际上是访问矩阵的一列。其效果类似于Windows下的文件属性-安全。
• 文件权限表（是全局性质的）
  • 文件权限表实际上是访问矩阵的一行。其效果类似于 ls -la，其中存放了该域下，对所有文件、资源或域的访问权限情况。

磁盘管理 #

磁盘组织方式 #

• 主要分为连续方式、索引方式、链接方式。

方式	组织方式	inode存放内容	磁盘上的特殊结构	缺点	优点
连续方式	连续方式	文件的base（首块）、limit（连续块数）	-	产生外碎片；大小无法扩展；难以移动文件的位置；可能因为文件大小估计错误而出现大量内碎片	访问速度快，多用于SWAP分区
隐式链接方式	链接方式	文件的start（首块号）、end（末块号）	每个块有指向下一块的指针	不支持随机访问；一环完蛋就全部完蛋	大小可扩展
显式链接方式（FAT）	链接方式	start（首块号）	整个磁盘上一个FAT表	不支持随机访问；当硬盘空间比较大时，FAT表将占用很大空间（存在磁盘上，占用很多磁盘空间；使用时调入内存，占用大量内存空间；）	FAT会追留在内存。可在内存中就完成文件的定位，非常快
单级索引方式	索引方式	索引块所在的块号	每个文件都以索引块开始	小型文件：索引块有非常大的内碎片；大型文件：一个索引块不够用（注意，必须用一个块来做索引块，且这个快就算有内碎片也不能做他用）	支持随机访问；不需要过多的额外空间（因为只需要保存当前读取的文件的各块信息了，而不是磁盘所有的块的信息了，且如果访问的话，可以只把当前文件涉及到的块的信息调入内存）
多级索引方式	索引方式	最高级索引块所在的块号	每个文件都以索引块开始，但是这个索引块中的某些块可能指向其他二级、甚至更高级的索引块	-	把索引块用索引进行索引，所以支持更大的文件

FAT文件系统 #

注意，磁盘块又称扇区。而簇是若干连续的磁盘块的统称。

块（扇区）可以理解为内存单元，而簇可以理解为帧。

• 为了安全，FAT文件系统中还存放了FAT表及其备份，进行一个镜像的数据保护。分别称为FAT1表和FAT2表。
• 对于FAT12，每个表项是12位，所以只能寻址$2^{12}$的范围，也就是4096个地址，也就最大允许有4096个磁盘块，因为磁盘块（实际上就是扇区）大小一般是512B，所以最大只能带8MB的磁盘。
• 后来，出现簇的概念，也就是FAT表指向的地址不再是块地址，而是簇地址。磁盘被按“簇”进行管理。
  • 块（扇区）可以理解为内存单元，而簇可以理解为帧。文件被划分成一页一页的，页大小和簇大小一样，然后按簇为基本单位进行分配。
  • 这样一来，只要簇是n块，FAT12可以管理的空间就是原来的n倍了。
  • 但是出现问题：如果簇过大， 就会导致内碎片过大。因为现在分配磁盘空间都是按簇了。
• 于是，出现FAT16、FAT32等文件系统。这样就不用过大的簇，也能管理更大的空间了。

磁盘块分配和回收算法 #

• 空闲表法（类似表项构成的数组）
  • 表的每一行是连续空闲块构成的base和limit，这适用于连续分配。
  • 注意在回收的时候需要进行合并。
• 空闲链表法
  • 空闲盘块链法
    • 每次需要磁盘块，就从链头部取；每次回收磁盘块，就挂到链尾部。因为文件一般包含很多磁盘块，所以可能要多次访问空闲盘块链，且因为磁盘很大，所以这个链过长
  • 空闲盘区链法
    • 类似于空闲表法的链表实现
• 位视图法
  • 不像数组、链表那样，需要占用大量空间：因为采用byte类型数据进行存储，所以非常省空间（因为一位就是一块），因此可以驻留内存，这样分配起来更快
• 成组链接法
  • 现在定义组的大小是100，即100个块构成一个盘块组。
  • 内存中存放一个“空闲盘块号栈”这种特殊的数据结构，其大小应当为100，另外还有一个数据，来记录这个组中实际有多少盘块。于是，这101个单元构成了基本的数据结构。
  • 这样的栈里面，每个的值都是一个空闲的盘块号。栈底的那个指向的盘块比较特殊：它存放了他所在的组（也就是当前这个组的下一组）的该数据结构。也就是，每个组的栈底所在的块负责存放下一组的这样的数据结构。
  • 最后一组则不需要这样一个指向存放了下一组的这样的数据结构的盘块，所以它的栈底的值是0，代表不指向任何的盘块。
  • 内存中的“空闲盘块号栈”是当前活动的盘块组。当分配盘块或回收盘块时，优先往这里面操作。
    • 分配盘块
      • 如果当前内存中的“空闲盘块号栈”非空且剩余了**>1个元素**，那就让它的数量字段-1，然后取栈顶的指向的块分配出去
      • 如果正好剩余1个，就先把它指向的那个块拷贝到“空闲盘块号栈”来（因为它是下一组的数据结构），然后再把那个块分出去。显然，剩余1个的这个组自动消失了，取而代之的是下一个全新的组。
    • 回收盘块
      • 如果当前栈不满，就把收回来的块的号加到栈顶，然后计数++；
      • 如果当前栈满，那就把当前内存中的“空闲盘块号栈”拷贝到这个收回来的块上，然后把“空闲盘块号栈”初始化，把块入栈，然后设置计数器=1.
    • 注意，一个是还剩一个就空了，一个是已经满了。这两个的临界条件是不一样的。

磁盘读取时间 #

• 寻道时间
  • $T=m\times n+s$.其中，s是发动磁头的时间，n是需要移动的磁道数量，m是移动一个磁道的距离，磁头需要的时间
• 旋转时间
  • 利用平均旋转时间计算，是个常量，一般是50ms
  • 如告知每秒转数(circles/s)为r，那么旋转时间平均为 $\frac{1}{2r}$.
• 传输时间
  • 传输时间利用当前读取的数据占了一圈磁道的比例来计算。当前知道了转一圈磁道要多长时间，那么就可以算出了
  • 所以传输时间本质上并不是数据在数据线内的传输时间（因为几乎是光速），而是磁头已经定位到磁道上后，通过旋转而读取数据的时间。
  • 已知需要读取b个字节，一圈磁道有N个字节，转数仍然是r，那么时间是 $\frac{b}{rN}$.
• 加起来就是~。

磁盘调度算法 #

• FCFS

  • 磁头的移动方向不固定。

• SSTF（最短寻道优先）

  • 送外卖算法——产生饥饿现象：老是不往山东大学送，只是在海大周围转悠
  • 磁头的移动方向不固定。

• SCAN（扫描算法；

  电梯算法

  ）

  • 到了磁盘的尽头才往回走，否则不允许回头
  • 明显是为了消除饥饿而设计
  • 磁头周期性地恒定方向移动，碰到边界就更改方向。

• CSCAN（循环扫描；循环电梯）

  • 到了尽头可以不往回走，而是从另一端的尽头开始继续扫描
  • 因此规定磁头只能单向移动，也就是例如只能从里向外。

• LOOK

  • 电梯算法，但是不需要到头
  • 磁头周期性地恒定方向移动，碰到最靠边的访问点就更改方向。

• CLOOK

  • 循环电梯算法，但是不需要到头
  • 规定磁头只能单向移动，也就是例如只能从里向外。

扇区的构成 #

• 由头、尾和中间的数据部分（一般是512B）构成。

Bootstrap和启动区程序的区别？ #

• 在ROM中保存了用于实现装入启动区程序到内存中的一段程序。为什么不把完整的启动程序都放在ROM中是因为如果更换其他操作系统，还得去改ROM，这非常麻烦。这样一来，一个ROM就能适应多种操作系统了：我ROM只是负责装，而怎么启动是磁盘上存放的操作系统启动区决定的。
• 带有启动区的磁盘称为启动盘。
• 这就是为什么开机那么麻烦，还要先运行Bootstrap，才能装入Loader，然后再跑Loader。因为前者属于BIOS的范畴，后者属于OS的范畴。

Unix混合索引分配 #

• 假设磁盘块大小是4KB，那么10个直接地址项可索引最大40KB的文件。（iaddr0到iaddr9都是直接索引，直接指向盘块）
• 大于40KB的部分就进入了一级间址区域。也就是把一个磁盘块拿出来作为索引块，其中全都是直接索引，然后iaddr10就可以指向这个放满了直接索引的盘块。因为盘块大小是4KB，所以可以存放1K个块号（假设每个直接索引的大小是4B），那么如果利用上iaddr0到iaddr10，可以存放40KB+4MB的文件了，约等于4MB。
  • 可见，如果采用多级索引，就相当于地址加高m位（其中m是可表示的范围，这里是1K，那么现在就是4K上面再加1K的范围，就是4MB）（因为0级索引是4KB，所以1级索引就在高位上叠个1K的表示范围，也就是4KB。）
• 如果还不够，就使用iaddr11，它是一个2级索引。根据地址上面加高理论，可以叠两层表示范围，也就是1K叠1K再叠其大小4KB，也就是4GB。同理，如果用到iaddr12，那就是三级索引，可以类似得出需要叠三层1K，也就是可以表示4TB的文件。（注意，每次“叠高位”都是做了乘法，用了排列组合的乘法原理。）
• 这种“叠高位”的思想还可以用到之前说的多级页表上。也是完全适用的。

磁盘性能优化 #

• Page Caching（又称Disk Caching）
  • 额外增加一个Cache，来保存磁盘局部性内容
  • 或是说把内存中所有剩余空间都读入最近会可能用到的页面，这样到时候就不用再读入了
• 对IO缓冲区的花哨玩法
  • 提前读
    • 在CPU空闲的时候，把很可能访问到的下一个块也一起读进缓冲区。（因为CPU必须要从缓冲区中取IO的数据）当下次CPU要请求IO时，就直接拿到了这些数据。
    • 可以提升很大的效率。被广泛应用。
  • 延迟写
    • 当CPU往磁盘写东西，也是先写到缓冲区里面。当CPU结束IO请求，缓冲区相当于利用完毕，进入空闲状态。但是却不往磁盘立即写回，而是把这个缓冲区挂到空闲缓冲区队列末尾（假设使用的是缓冲池结构），那么当这个缓冲区再次被利用时，才会把它先写回磁盘，然后再去利用它。
    • 可以提升很大的效率。被广泛应用。
• 优化盘块分布
  • 不要把一个文件存在距离过大的磁道上
  • 尽量连续分配（例如以簇的方式管理磁盘可以减少寻道次数）
• 虚拟盘
  • 虚拟盘是把内存的一部分当成磁盘来用。但是用户却没有感觉到。显然能提速。

磁盘容错 #

• 一级容错技术SFT-1
  • 双份FAT表、双份目录表
    • FAT文件系统采用了双份FAT表、双份目录表。因为如果FAT表坏了或者目录表坏了，磁盘就没人能解读了。
  • 热修复重定向
    • 用于替补坏块。
    • FAT在磁盘的2%-3%的空间中预留了一些保留块，如果磁盘有一些块坏了（可以用写后读校验检测出来），就把读写重定向到这些保留块上来
  • 写后读校验
    • 用于检测坏块。
    • 对于一个块，先写入数据，在立即读出，然后和之前写入的比较。如果不同，则说明块坏了，需要使用热修复重定向进行替补。
• 二级容错技术SFT-2
  • 磁盘映像
    • 完全备份磁盘。写第一个同时也写第二个。
  • 磁盘双工
    • 对磁盘映像进行改进：两个磁盘并不接到同一IO控制器上，而是分别接到两个独立的控制器上。这样就可以排除IO控制器造成的出错问题。

IO管理 #

设备控制器 #

• 由缓冲区和设备驱动程序构成。

• 一类设备控制器控制一类外设。

• 所有设备控制器都接到数据总线上。

• IO实际上就是主存（

  工作区

  ）经过数据总线和某设备控制器的

  缓冲区

  的数据交换。

  • 注意，每个控制器都有一个缓冲区。

三种数据传递控制方式 #

• 中断方式传输数据，是以CPU为中心的，必须经过CPU才能进入内存。所以虽然美其名曰并行工作，实际上只是数据准备的过程并行，传递数据的过程仍然是串行的。
  • 每次传输一个字都要中断CPU，并且需要CPU进行传输。
• DMA方式传数据，CPU只负责设置要传递的块大小等信息，无论是数据准备过程还是数据传输过程都是和CPU并行了。
  • 每次传输完规定大小的块才需要中断CPU，并且不需要CPU进行传输。
• 通道方式传递数据，CPU只负责下达IO指令，给出通道程序首地址和IO设备地址，于是通道程序执行通道程序即可（注意，通道程序是放在内存中的，也就是说通道要读取内存中的通道程序）。当IO工作全部完毕，才会发送中断请求报告CPU。
  • 整个IO过程都完成了才会中断CPU，并且不需要CPU进行传输。
  • 通道方式相比DMA的好处，就是前者支持多个设备，并且前者的数据块大小等基本信息不需要CPU来设置，而是通道程序就可以决定的（即由通道自行决定）。（DMA比较傻，不知道自己该干什么，但是通道因为通道程序的存在，可以知道自己该干什么）

IO子系统的层次结构 #

• 用户层IO软件
  • 实现与用户交互的接口、用户程序编程的接口。这部分软件大部分属于OS，所以往往通过系统调用访问到。
• 设备独立性软件（实现设备抽象）
  • 实现统一的调用接口（read、write、open）、统一的设备状态信息（例如文件不存在）
  • 实现逻辑设备与物理设备的映射（/dev/dsk1 -> HDD1）。
• 设备驱动程序
  • 向下走：将上层发来的统一接口调用（例如write）转换成实际应该执行的操作（例如往打印机里传递数据），控制设备进行工作
  • 向上走：把设备发来的状态信息转换成统一的状态信息（例如文件不存在），发送给上层
• 中断处理程序
  • 设备驱动程序可以调用中断处理程序，来完成一系列的IO操作。因为中断处理程序被设备驱动程序调用，所以它位于更下面一层。
• 硬件设备

当用户要打印，其办公软件进行系统调用，OS向/dev/usb/usb-hp3110 这个逻辑设备发送write请求（该请求由设备独立性软件规定），设备独立性软件接收到write，把这个write根据请求的/dev/usb/usb-hp3110 映射到具体的打印机并且把这个write命令传递给他，这个具体的打印机收到了write，则转换为自己的一套具体实现，这套实现需要通过调用中断处理程序完成具体的IO过程。最后落实到硬件设备和通道之间的交互。

IO调度 #

• 在实际应用情况下，IO请求的发出是混乱无序的，这可能导致IO效率的降低（联想磁盘调度算法）。解决这个问题的关键在于重新排列这些调度的顺序。
• IO请求被安排在一个队列里面进行排列。IO调度的任务就是对这个队列进行重排。

设备分类 #

• 独占设备
  • 例如打印机
• 分时共享设备
  • 例如磁盘，各个进程在不同的时间内访问
• SPOOLing设备
  • 例如打印机

设备分配算法 #

• 安全分配
  • 进程发出IO请求当即进入阻塞，直到IO结束才就绪。
  • 大多采用这种方式。但缺点是进程只能串行和IO设备工作。
• 不安全分配
  • 进程发出IO请求但是不阻塞。因此它后面如果需要，还能连续发出其他的多个IO请求。
  • 缺点：可能因为资源分配的顺序出现问题而进入不安全状态，最终导致死锁。
  • 优点：一个进程能够同时操纵多个设备，或同时提出多个请求。

番外：现代CPU的三级缓存 #

• L1、L2、L3距离核心的距离分别变远，容量分别变大，速度分别变慢。
• L1分为数据cache和指令cache，每个核心都有两个这样的L1缓存。他是最小的，也是最快的。例如32KB。
• L2不区分指令数据，一般一个核心配备一个。大小例如128KB。
• L3整个CPU配备一个，不区分指令和数据。大小例如4MB。

缓冲区、环状缓冲区、缓冲池 #

• 缓冲区的作用
  • 协调数据传输速度不一致性、数据传输块大小（粒度）不一致性
  • 减少CPU中断频率（类似于我的归并排序），以提升并行性
• 缓冲区的特性
  • 缓冲区满时，才能往外取数据。
• 工作区
  • 工作区空时，才能再次开始读取缓冲区的数据。（不能看吃碗里看锅里）
• 体系结构
  • 一般把IO输入暂存的地方称为缓冲区，程序运行的地方称为工作区。
  • 假设工作区和缓冲区大小是一样的。
  • 现在要完成的目标是：IO设备输入到缓冲区，缓冲区打入到工作区，并由CPU处理。IO设备输入到缓冲区需要时间T，缓冲区输入到工作区需要时间M，CPU处理工作区需要时间C。
• 单缓冲区
  • 假设初始情况下，工作区空，缓冲区满，则传递到工作区需要M，此时的状态是工作区正好满，缓冲区正好空；如果工作区先空了，就要等待缓冲区满；反之也一样。
  • **总之，CPU有可能实现连续读取（如果T<=C,即外设够快），但是外部设备不可能实现连续输入（最少也要间隔M的时间去清空缓冲区）。**最后的时间是$M+min(C,T)$.
  • **即，中间有M的时间，双方是都停止了工作的。这部分时间是必须的。**剩下就看谁拖后腿了，所以$M+min(C,T)$就是这么来的。
  • 它支持单工的缓冲区通信。
• 双缓冲区
  • 假设初始情况下，A缓冲区满，B空，工作区空，则传递到工作区需要M，与此同时另一个缓冲区正在输入数据。
  • 让CPU无需等待外设输入的条件是：M+C时刻，B已满（因为只有一个外部设备，所以被较早填满的是另一个那个缓冲区），即T<=M+C.
  • 让外设可以实现连续输入的条件是：T时刻，A已空。即T>=M+C.（M+C是长远来看的。如果只看一轮，则T>=M即可。但是这必然会导致后续淹没缓冲区，不可能实现外设连续输入。）
  • **总之，CPU有可能实现连续读取，外部设备有可能实现连续输入（因为此时不需要间隔M了），但是二者不可得兼。**最后的时间是$min(C+M,T)$.
  • 它支持单工的缓冲区通信。
• 循环缓冲区
  • 各缓冲区排成一个环，设置in、out指针，他们都按统一的旋转方向进行移动。in指向前进方向上第一个空缓冲区，out指向前进方向上第一个满缓冲区。可见，他们分别用于数据接收和数据输出。
  • **它支持单工的缓冲区通信。**即in、out只是进入缓冲区、提取出缓冲区的意思。
• 缓冲池
  • 缓冲池是由非常多的缓冲区构成的数据结构。
  • 这些缓冲区中，某一时刻下，有4个特殊的缓冲区，分别是收容输入缓冲区、提取输入缓冲区、收容输出缓冲区、提取输出缓冲区。注意，这些名称只是这个缓冲区在这一时刻临时扮演的角色。
  • 缓冲池还维护三个队列，他们的队首分别是上面的角色：空缓冲区队列，输入满缓冲区队列，输出满缓冲区队列。其中，收容输入缓冲区、收容输出缓冲区都是空缓冲区队列的队首，提取输入缓冲区是输出满缓冲区队列的队首，提取输入缓冲区是输入满缓冲区队列的队首。
  • **它支持全双工的缓冲区通信。**这里的输入缓冲区、输出缓冲区分别就是两个通信方向了。

LUT（逻辑设备表 Logic Unit Table） #

• 完成逻辑设备到物理设备的映射。
• 可以理解为linux下的dev路径。
• 表项包括逻辑设备名、物理设备名、设备驱动程序入口地址。

SPOOLing #

• 复习一下什么是脱机

  • 早期人工直接与计算机打交道，人的手速比CPU慢太多，也就是可以理解为人是一个非常慢的IO设备
  • 后来，人们把数据记录到例如纸袋上，外围设备识别这些纸带，然后把读出的数据存到外存中（例如磁带、磁盘），然后交给主机，主机只需要和这些较为高速的外存设备打交道就可以了。然后主机把结果写入输出磁带/磁盘，人再通过外围设备读出。

• 实现细节

  • 在磁盘上开辟一些空间，分别是输入井、输出井，这两个井模拟了原先通过磁带输入输出时的那些磁带。同时，内存中也有相应的输入、输出缓冲区。这些缓冲区一头连接了磁盘上的井，一头连接了外部慢速设备。另外还有输入、输出进程，负责SPOOLing的过程，他们就相当于磁带时代的

    程序员

    。而缓冲区另一头的打印机，就相当于操作员。

    • 磁盘上的井是不能直接和外部设备之间传递数据的。需要经过内存中的缓冲区。（协调速度、粒度等）

  • 如果当前一个很慢的设备需要输入，可以由输入进程负责让外部设备把数据读入输入缓冲区，然后从输入缓冲区中存到输入井中。当CPU真正需要这些数据时，再直接从磁盘上的输入井读入即可。这样就不至于让CPU一直等着外面那个速度非常慢的设备输入了。

  • 如果当前需要输出到一个很慢的设备例如打印机，可以负责由输出进程输出到输出缓冲区，从而输出到硬盘上的输出井。当可以打印时，输出进程负责从磁盘的输出井中经过输出缓冲区送到打印机内。