操作系统笔记（II：从进程同步到文件管理）

4.5.2 读者-写者问题

【问题描述】

若干读者、写者，共享文件/数据；

读者：可以同时读数据，不可修改数据。

写者：修改数据，不能同时修改同一份数据，进行修改时读者不能读。

【分析】

采用记录型信号量

互斥：为保证写者进程与其它进程互斥访问共享对象，设置互斥信号量wmutex，初值：

互斥：由于允许有多个读者，为了解目前的读者数量，设置一读者计数变量readcount。多个读者都对readcount进行操作，须设置对其操作的互斥信号量rmutex，初值：

读者行为：读之前readcount加1，读数据，读完，readcount减1；

写者行为：修改数据。

【读者优先方案】

要等所有读进程执行完后，使得信号量wmutex 为1时，才能访问临界资源。

semaphore rmutex = wmutex=1;Int readcount=0
{--reader: while (true) {wait(rmutex);if (readcount==0) wait(wmutex);readcount++;signal(rmutex);reading;wait(rmutex); readcount--;if (readcount==0) signal(wmutex);        signal(rmutex);}writer: while (true) {wait(wmutex);writting;signal(wmutex);}  
--}

【写者优先方案】

semaphore rmutex = wmutex=wwmutex=1;Int readcount=writecount=0
{--reader: while (true) {while(writercount>0) {do nothing}wait(rmutex);if (readcount==0) wait(wmutex);readcount++;signal(rmutex);reading;wait(rmutex); readcount--;if (readcount==0) signal(wmutex);signal(rmutex);}writer: while (true) {wait(wwmutex);writercount++;signal(wwmutex);wait(wmutex);writting;wait(wwmutex);writercount--;signal(wwmutex);signal(wmutex);   }  
--}

4.5.3 哲学家进餐问题

【问题描述】

五个哲学家同座一张圆桌，每人一个碗，左右各一只筷子；

哲学家的行为：思考-吃饭-思考……。

前提：只有拿到左右两只筷子才开始吃饭。

semaphore chopstick[0……4]=1
{--Pi: while (true) {wait(chopstick[i]);wait(chopstick[(i+1) mod 5]);eating;signal(chopstick[i]);signal(chopstick[(i+1) mod 5]);think;}
--}

防止死锁的解决方案：

最多允许4个哲学家同时坐在桌子周围；
仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子；（提高资源利用率）
给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之；
把哲学家分为三种状态，思考，饥饿（加一状态），进食，并且一次拿到两只筷子，否则不拿。

4.6 管程机制

信号量机制的不足：
- critical section、entry section和exit section都由用户编写；
- 信号量原语分散在各程序代码中由进程执行，系统无法有效控制、管理；
- wait和signal操作的错误使用，编译程序和操作系统都无法发现、纠正，可导致死锁。
1971年，Dijkstra引入管程机制，即“秘书”进程：
- 临界资源的同步操作集中；
- 访问需先报告“秘书”；
- “秘书”实现进程同步，从而保证互斥使用；
- 管程有生命周期（与操作系统相同）。
管程组成：
- 局部于管程的共享变量说明（数据结构）；
- 对该数据结构进行操作的一组过程；
- 局部于管程数据的初始化语句。

typedef monitor {variable declarations;condition x,y;void P1(...) { …… };void P2(...) { …… };... ...void Pn(...) { …… };initialization code
} monitor-name

条件变量：
- 用条件变量类型condition来定义条件变量，在管程中声明条件变量；
- 每个条件变量对应一个等待队列，进程通过管程请求临界资源未满足时，管程将其入等待队列；
- 当进程通过管程请求临界资源未满足时，调用同步原语wait()将其放入等待队列；
- 当进程可以访问临界资源时，管程调用同步原语signal()唤醒等待进程。

**【例1】**利用管程解决生产者-消费者问题。

共享变量：缓冲区buffer[n]，指针in、out；对产生的数据进行计数count；

条件变量：

若没有空缓冲区，需要阻塞生产者进程 ——notfull（不满条件）

若全部都是空缓冲区，则需要阻塞消费者进程——notempty（不空条件）

局限于管程内的操作：

put(data)：检查是否全满，若不满，放入，数据计数count+1

get(data)：检查是否全空，若不空，取出，数据计数count-1；

Monitor PC{ int in,out,count; item buffer[0..n-1];    condition  notfull,notempty;put(item) {if (count>=n) notfull.wait;		//阻塞buffer(in)=nextp;in=(in+1) mod n;count++;if (notempty.queue) notempty.signal; 			//唤醒}get(item) {if (count<=0)  notempty.wait;nextc=buffer(out);out=(out+1) mod n;count--;if (notfull.queue)notfull.signal;  }
}
Producer() {		//生产者进程while (true) {produce an item in nextp;PC.put(item); }
}
Consumer() {		//消费者进程while (true) {PC.get(item);consume the item in nextc;}
}

管程和进程的比较：
- 设置目的不同：
  - 进程：并发、共享
  - 管程：管理临界资源
- 系统管理的结构不同：
  - 进程：PCB
  - 管程：等待队列
- 管程是OS固有成分，有生命周期（与操作系统相同）
- 管程被进程调用。

4.7 进程通信

IPC(Inter-Process Communication)：协作进程间用来交换数据与信息的机制。

进程间通信类型：
- 低级通信
  - 交换信息量少，仅是数据和状态的变化
  - 通信由程序员完成
- 高级通信
  - 交换信息量大
  - 系统提供高效简捷的传输命令
  - 高级通信类型
    - 共享存储器系统（Shared-Memory System）
    - 共享数据结构、共享存储区
    - 消息传递系统（Message Passing System）
    - 管道通信（Pipe Communication）
消息传递系统
- 利用系统提供的通信原语，以消息或报文为单位进行信息交换。
- 直接通信方式
  - 进程直接把消息发送给目标进程
  - 通信原语
    - Send(Receiver, message);
    - Receive(Sender, message);
- 间接通信方式
  - 进程间通过某种共享的数据结构（如信箱）进行通信。
  - 通信原语
    - 信箱的创建、撤销；
    - 消息的发送和接收
      - Send(mailbox,message)
      - Receive(mailbox,message)
    - 信箱的类型（根据创建者和共用关系不同进行分类）
      - 私用信箱(Private Mailbox)：一对一，单向通信链路
      - 共用信箱(Public Mailbox)：由操作系统创建
      - 共享信箱(Shared Mailbox)：多对多，由某进程创建
- 通信链路问题
  - 显式建立/隐式建立
  - 点-点/多点链接
  - 单向链路/双向链路
  - 无容量/有容量链路（有无缓冲机制）
- 消息格式问题
  - 消息头：发送和接收进程名、消息长度、类型（与所处环境有关）
  - 消息正文
- 进程的同步方式（三种）
  - 发送者、接收者进程阻塞（紧密同步）
  - 发送者不阻塞（一直发）、接收者阻塞（反馈信息）
  - 发送者、接收者都不阻塞
    - 利用率最高，需缓存机制（排序后才可接收）
管道通信
- 管道通信是UNIX系统的重要特色之一。管道是指用于连接一个读进程和一个写进程，以实现进程间通信的共享文件，又叫Pipe文件。
- 进程直接把消息发送给目标进程的命令格式为：Command1|Command 2（管道：|）
- 功能：Command1进程以字符流的形式向管道发送大量的数据，Command2进程则从管道接收数据。两进程实现单向、同步、互斥运行。
  - 单向：Command1只能发送；…
  - 同步：管道满时，Command1等待；…
  - 互斥：同一时刻，只能有一个进程对管道操作。

ch5.死锁

5.1 死锁（Deadlock）的概念

多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程将永远无法推进。

5.2 死锁产生的必要条件

互斥条件（Mutual exclusion）
占有并等待（Hold and wait）
不可抢占（No preemption）
环路等待（Circular wait）

5.3 资源分配图

由节点集合V和边集合E组成的有向图G=(N,E)。

节点集合V：
- 进程集合P={P1,P2,…, Pn} ；
- 资源类型集合R={R1, R2,…, Rm}，其中黑点数表示资源个数。
边集合E：
- 申请边Pi →Rj ——由进程Pi指向资源Rj的有向边，表示还要请求；
- 分配边Rj→Pi ——由资源Rj指向进程Pi的有向边，表示已经分配。

5.4 死锁的处理办法

设计无死锁的系统（系统运行前或运行中）
- 死锁预防（破坏死锁存在的四个必要条件）
- 死锁避免（保证系统随时处于安全状态）
允许系统出现死锁，提供处理方法排除（系统或进程运行后）
- 死锁检测（通过化简资源分配图）
- 死锁恢复（通过破坏死锁的必要条件）
忽视死锁

5.4.1 死锁的预防

预先静态分配法
- 破坏“占有并等待”条件
- 思想：作业调度时，仅将系统能满足运行所需全部资源的作业调入内存运行。
- 缺点：
  - 资源利用率低
  - 作业周转时间长，不利于“并发”
有序资源使用法
- 破坏“环路等待”条件
- 思想：将系统中所有临界资源分配唯一的序号，进程严格按序号递增次序申请使用资源。在任何一个时刻，总有一个进程拥有的资源编写是最大的，那这个进程申请之后的资源必然畅通无阻，因此不可能出现所有进程都阻塞的死锁现象。
- 如果进程需要同一资源类型的多个实例（也就是序号相同的资源），则必须对它们一起进行申请；如果进程后面又想申请序号低的资源（比如5），那就必须把现在拥有的序号为5及其以上的资源全部释放。
- 例如：输入机=1，打印机=2，穿孔机=3，磁带=4。
  
  A：R2…R1（在这里A需要重编译，优先调用R1，浪费R2资源【R2不能利用】）
  
  B：R1（已运行）…R2
- 缺点：
  - 临界资源的顺序定义随时变化（很难定下顺序）
  - 为资源编号限制新设备的增加
  - 资源的排序会占用系统开销

5.4.2 死锁的避免

基本思想：在执行过程中，采用一些算法规避不安全状态，确保系统始终处于安全状态。

系统的安全状态
- 安全状态的定义：系统按某一顺序<P2,P1,P3>(安全序列)为每个进程分配所需资源，使每个进程都可顺序完成，则称系统在该时刻处于安全状态。
- 要考虑的因素为：最大需求、目前已经分配的资源、目前可用的空闲资源。当一个进程获得了它运行所需的最大资源后，将释放资源供给其他进程使用。
- m个进程共享n个同类型资源，每个进程至少1个资源，保证不死锁的条件是： $\left. {\sum\limits_{i = 1}^{m}{\left( {R_{P_{i}} - 1} \right) + 1}} \leq n\rightarrow{\sum\limits_{i = 1}^{m}R_{P_{i}}} \leq n + m - 1 \right.$
  - 例如，5个相同类型资源组成的系统，系统中有3个进程，每个进程最多需要2个资源，该系统不会发生死锁。为每个进程先分配一个资源，然后再给其中任意一个进程分配一个资源，则一个进程将得以运行，且运行完毕后将释放这两个资源供给其他进程使用。在这个问题中最少需要4个进程即可保证不死锁。
银行家算法
- 数据结构：
  - 可用资源向量Available[m]：是一个数组，表示现在系统中每个类型的资源还有多少可用的资源
  - 最大需求矩阵Max[n, m]：表示某进程最多需要多少某资源，一行代表一个进程，一列代表一个资源
  - 分配矩阵Allocation[n,m]：表示系统中现在某类资源分配给某进程的数量
  - 需求矩阵Need[n,m]：表示现在进程中尚需的各类资源数
- 资源请求处理：
  
  设 request 是进程 P 的请求向量，request[A] = K 表示进程 P 需要 A 类资源 K 个。当 P 发出资源请求后，系统按照以下步骤进行检查。
  - 1.如果 request[A] 的值小于 need[P，A]，也就是说如果现在请求的数量小于 need 矩阵中规定的它所需要的数量，那么就转到步骤 2 ；否则认为出错，因为他所请求的数量已经超过了他所宣布的最大值。
  - 2.如果 request[A] 的值小于 available[A]，也就是说请求的值小于现在系统中有的值，则转向步骤 3 ；否则表示尚足够资源，进程 P 需要等待。
  - 3.系统试探着把资源分配给进程 P，并修改下面数据结构中的值：
    - 更新可用：Available = Available - request；
    - 更新已分配：Allocation[P,A] = Allocation[P,A] + request[A]；
    - 更新所需：Need[P,A] = Need[P,A] - request[A];
  - 4.系统执行安全性检测，检查此次资源分配后，系统是否处于安全状态，若安全才将资源分配给进程 P；否则此次的试探分配作废，恢复原来的资源分配状态，让进程 P 等待。
- 安全性检测算法：
  - 1.初始时安全序列为空；
  - 2.从 Need 矩阵中找到符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于等于 Available 向量，找到后，把对应的进程加入安全序列；若找不到，则执行步骤 4；
  - 3.进程 P 进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源，故应执行 Available = Available + Allocation[P]，其中 Allocation[P] 表示进程 P 在 Allocation 矩阵中对应的行，返回步骤 2 。
  - 4.若此时安全序列中已有所有进程，则系统处于安全状态，否则处于不安全状态。
- 银行家算法例题如下。

5.4.3 死锁的检测

死锁检测的2个前提：

保存有关资源的请求和分配信息
提供一种检测系统是否已进入死锁的算法

资源分配图简化算法：

由进程指向资源的边是请求边，由资源指向进程的边是分配边。当资源包中的可用资源数大于0，则响应请求，画出分配边（删去请求边），当一个进程没有请求边时，即可孤立。
如果化简后所有的顶点都成了孤立点，则称该图可完全化简；否则称该图是不可完全化简的。
若经过化简后还存在非孤立点，则非孤立点的进程处于死锁状态。

5.4.4 死锁的恢复与解除

法1：剥夺资源
- 从一部分进程剥夺资源给其他进程，直到死锁解除；
- 具体方法：一次终止一个进程直到死锁循环被解除，选择终止“代价最小”的进程。
法2：撤销进程
- 按照不同策略撤销一个或多个进程，回收资源给其他进程，直到死锁解除；具体考虑有以下几种：
  - 选择一个牺牲品：确定抢占顺序以使代价最小。
  - 回滚：抢占资源，将进程回滚到某个安全状态。
  - 饥饿：防止进程饥饿，让进程有限地被选定。

ch6.内存管理

6.1 基本概念

内存管理的功能：
- 主存空间的分配与回收
- 地址转换与重定位
- 存储保护与共享
- 存储扩充**->**CPU能直接访问的存储设备只有内存和寄存器，其中内存访问需要占用几个CPU时钟周期，寄存器则内置在CPU中，访问只需要只用1个CPU时钟周期。
地址的相关概念：
- 逻辑地址：虚地址，用户程序中使用的地址
- 物理地址：系统中内存单元的地址
- 重定位（Relocation）：将相对地址变为绝对地址的过程
- MMU：内存管理单元，实现重定位的硬件设备

6.2 地址绑定

指令和数据绑定到存储器地址可在下面任意时期进行：
- 编译时期
- 装入时期
- 执行时期

重定位的方式：
- 静态重定位：程序入主存之前由编译/链接程序完成重定位，入主存可立即执行。
  - 场景：管程（系统固有成分，常驻内存）、嵌入式环境（如刷卡）
  - 优点：操作简单，不需要额外的机构或操作。
  - 缺点：
    - 程序不能进出（程序一旦装入后地址就不可再改变，程序也不可以再移动，不利于内存空间的有效使用）
    - 需一次加载所有代码
- 动态重定位：程序入主存之前不进行重定位，入主存执行到与地址相关项时，再进行重定位。
  - 优点：
    - 程序占用的内存空间可变，能提高内存的利用效率
    - 容易实现不同程序对同一副本的共同使用
  - 缺点：
    - 执行速度变慢，占用CPU时间
    - 需要额外的硬件支持
动态运行时装入方式：
- 装入程序按照装入模块中的地址，将程序和数据装入内存，执行时重定位。
- 优点：内存利用率高；大规模程序有利；可通过程序设计来实现；无需操作系统的额外支持；
运行时动态链接方式：
- 将编译后的目标模块及库函数，在程序执行时进行链接。
- 存根程序stub：用于指出如何定位适当的内存驻留库程序，或者在程序不在内存时如何加载库
- 特点：可节省内存空间；可用于系统类库的更新（如修改bug）；需要操作系统的支持。

6.3 交换技术

交换技术（Swapping）：
- 引入目的：解决由于内存不足而无法同时调入多个作业的问题。
- 多道程序环境下的交换
  - 实现：中级调度
  - 类别：进程对换、页/段对换；
- 对换空间管理
  - 外存设置交换区
  - 设置数据结构记录外存空间使用情况

覆盖技术（Overlay）：
- 用于解决程序大小超过物理内存总和的问题。
- 将程序分为多个段（多个模块）。常用的段常驻内存,不常用的段在需要时调入内存。
- 内存中分为一个“固定区”和若干个“覆盖区”。需要常驻内存的段放在“固定区”中,调入后就不再调出(除非运行结束)。不常用的段放在“覆盖区”,需要用到时调入内存,用不到时调出内存。
覆盖、交换的比较：
- 目的是一样的；
- 覆盖是发生在一个进程中的程序内部没有调用关系的模块之间，代价是程序员手动指定和划分逻辑覆盖结构；交换是内存中程序与管理程序或OS之间发生的，以进程作为交换的单位，需要把进程的整个地址空间都换进换出，对程序员是透明的，开销相对较大。

6.4 连续分配存储管理技术

6.4.1 单一连续分配

系统区的低地址存放中断向量、操作系统内核代码，高地址存放设备驱动程序。

6.4.2 固定分区分配

操作系统需要建立一个数据结构（分区说明表），来实现各个分区的分配与回收。每个表项对应一个分区，通常按照分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。
优点：实现简单，无外部碎片。
缺点：
- 当用户程序太大时，可能所有分区都不能满足需求，此时必须采用覆盖技术解决，但会降低性能
- 会产生内部碎片（每个分区内部存在空闲空间），内存利用率低

6.4.3 动态分区分配

使用空闲分区表，每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址等信息。

6.4.3.1 动态分区分配算法

首次适应算法：每次都从低地址以地址递增的次序排列，直至找到第一个大小能满足要求的空闲分区。
循环首次适应算法：为了解决上一个算法导致低地址部分出现很多小的空闲分区，且每次分配查找由于要经过这些分区而增加查找开销。该算法设定一个指针，每次都从指针位置（即上次查找结束的位置）往后查找，直至找到第一个大小能满足要求的空闲分区。
最佳适应算法：从头扫到尾，找到能满足要求且大小最小的（即最合适的）空闲分区。
最坏适应算法：为了解决上一个算法导致留下太多难以利用的小碎片，其在每次分配时优先使用空间最大的空闲分区，使分配后剩余的空闲区不会太小，更方便使用。
空闲分区表变动的两种情况：
- 空闲分区大小比申请空间大小大，则分区数量不改变
分区号分区大小（MB）起始地址（M）状态
1 20 8 空闲
2 10 32 空闲
3 4 60 空闲
分区1有进程5申请4MB的内存空间，则空闲分区表变为：

分区号分区大小（MB）起始地址（M）状态
1 16 12 空闲
2 10 32 空闲
3 4 60 空闲
- 空闲分区大小和申请空间大小相同，则分区数量减一
分区号分区大小（MB）起始地址（M）状态
1 20 8 空闲
2 10 32 空闲
3 4 60 空闲
分区3有进程5申请4MB的内存空间，则空闲分区表变为：

分区号分区大小（MB）起始地址（M）状态
1 16 12 空闲
2 10 32 空闲

分区号	分区大小（MB）	起始地址（M）	状态
1	16	12	空闲
2	10	32	空闲
3	4	60	空闲

分区号	分区大小（MB）	起始地址（M）	状态
1	16	12	空闲
2	10	32	空闲

6.4.3.2 回收问题

有以下四种情况

回收区的后面有一个相邻的空闲分区，则将该分区的分区大小和起始地址进行改变

分区号	分区大小（MB）	起始地址（M）	状态
1	10	32	空闲
2	14	60	空闲

变为：

分区号	分区大小（MB）	起始地址（M）	状态
1	14	28	空闲
2	14	60	空闲

回收区的前面有一个相邻分区（与上面一种情况同理，起始地址不发生变化）
回收区的前、后各有一个相邻的空闲分区

分区号	分区大小（MB）	起始地址（M）	状态
1	20	8	空闲
2	10	32	空闲
3	4	60	空闲

变为：

分区号	分区大小（MB）	起始地址（M）	状态
1	34	8	空闲
2	4	60	空闲

回收区的前、后都没有相邻的空闲分区，则分区数量加一，然后填充信息即可。

6.4.3.3 紧凑技术

动态分区分配无内部碎片，有外部碎片。外部碎片可以通过”紧凑”技术来解决。

紧凑技术是通过移动内存中作业，将分散的多个分区合并成一个大的分区
紧凑技术的前提是采用动态重定位
动态重定位分区分配的思想是：当作业需进入主存时，若主存每一个可用分区都不能满足要求，而可用分区总和又可满足要求时，首先完成内存的“紧凑”，然后调入。在每个分区都不能满足要求的情况下才紧凑，是因为紧凑操作会耗时，时间代价较大。

6.5 离散分配存储管理技术

6.5.1 分页存储管理（Paging）

6.5.1.1 基本内容

基本思想：逻辑地址空间在内存中可以不连续。
将内存空间分为一个个大小相等的分区（比如每个分区4KB），每个分区就是一个“页框”（Frame，内存物理地址空间按 $2^{n}$ 等分，也即页帧、内存块、物理页面），页框的编号称为页框号，从0开始编号。
将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个“页”或“页面” 。页面的编号称为页号，也从0开始编号。
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中，也就是说，进程的页面与内存的页框有一一对应的关系。各个页面不必连续存放，可以放到不相邻的各个页框中。
页表（PMT）(Page Mapping Table)

通常存在于PCB（进程控制块）中，如图：

页表项占用的字节数的计算：

【例】假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节？
- 页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组）。假设页表中的各页表项从内存地址为X的地方开始连续存放，则页号为i的页表项的存放地址=X+3*i。
- 计算机中内存块的数量->页表项中块号至少占多少字节
  - 内存块大小=页面大小=4KB= $2^{12}$ B，故4GB的内存总共会被分为 $2^{32}/2^{12}=2^{20}$ 个内存块，故内存块号的范围应是0到 $2^{20}-1$
  - 内存块号至少要用20bit来表示，则至少要用3B（3*8=24bit）
实现地址转换的方法
- 注意：内存地址是以字节编址的，每个地址的存储单元可以存放8bit的数据。一个字节就是一个房间，然后给这个房间编址。
- 重定位寄存器指明进程在内存中的起始位置。
- 若要访问逻辑地址A，则要先确定逻辑地址A对应的页号P，然后找到P号页面在内存中的起始地址（查页表），最后确定逻辑地址A的页内偏移量W，则逻辑地址A对应的物理地址=P号页面在内存中的起始地址+页内偏移量W。
- 页号=逻辑地址/页面长度（除法的整数部分），页内偏移量=逻辑地址%页面长度（除法的余数部分），则逻辑地址可以表示为：(页号,页内偏移量)，或写作(P,d)
- 由于在计算机内部地址是用二进制表示的，故页面大小设定为2的整数幂。假设某计算机用32个二进制位表示逻辑地址，则页面大小为4KB= $2^{12}$ B=4096B，则有：（红色20位代表页号，黑色12位代表页内偏移量）
  
  故如果每个页面大小为 $2^{k}$ B，用二进制数表示逻辑地址，则末尾k位即为页内偏移量，其余部分就是页号。即页面大小和页内偏移量位数可以相互转换，互相推出。
页表地址寄存器（PTR）：保存当前执行进程页表的起始地址和页表长度，从而计算页表项。
- 页表长度可以判断页号是否越界，通过比较页号P和页表长度M，若 $P\ge M$ ，则产生越界中断（内中断）。在这里P=M也会发生越界，因为页号从0开始，而页表长度至少是1。
- 页表中页号P对应的页表项地址=页表起始地址F + 页号P * 页表项长度，取出该页表项内容b，即为内存块号。
【注意】页表长度指的是这个页表中总共有几个页表项，即总共有几个页；而页表项长度指的是每个页表项占多大的存储空间。
基本地址变换机构：

6.5.1.2 具有快表的地址变换机构

快表，又称联想寄存器（TLB, Translation Lookaside Buffer），是一种访问速度比内存快很多的高速缓冲寄存器，用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。存储机构从快到慢依次是：寄存器、高速缓存（Cache）、内存（RAM）、外存（硬盘）。
引入快表后的访存变化：
- 若快表命中，则访问某个逻辑地址对应的物理地址仅需==一次访存==即可；
- 若没有找到匹配的页号，需访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后访问该物理地址对应的内存单元。故需要访问某个逻辑地址对应的物理地址在未命中情况下需要==两次访存==。
- 注意：在第二种情况下，在找到页表项后，应同时将其存入快表，以便后面可能的再次访问；但若快表已满，则必须按照一定的算法对旧的页表项进行替换。
- 快表的实现依赖于时间局部性（同个数据再次被访问）和空间局部性（由于很多数据在内存中是连续存放的，附近的存储单元很可能被访问）。
有效访问时间（Effective Access Time）
联想寄存器访问时间为 $\varepsilon$ ，内存访问时间为 $t$ ，联想寄存器中的命中率为 $\alpha$ ，则有效访问时间EAT为：

$\text { EAT }=(t+\varepsilon) \alpha+(2 t+\varepsilon)(1-\alpha)=2 t+\varepsilon-t \alpha.$
若系统支持快表、慢表同时查询，则未命中情况下时间是2 $t$ （无 $\varepsilon$ ），可以参考下面的甘特图：

6.5.1.3 两级页表与多级页表

为离散分配的页表再建立一张页表，称为页目录表（外层页表）。

页号

32位逻辑地址空间，页面大小为4KB，则可以设置如下：

将逻辑地址转换为物理地址的步骤：
- 按照地址结构将逻辑地址拆分为三部分
- 从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置（每个页表项记录页表页面的物理块号）
- 根据二级页号查表，找到最终想访问的内存块号
- 结合页内偏移量得到物理地址
若采用多级页表机制，则各级页表的大小不能超过一个页面。

【例】某系统按字节编址，采用40位逻辑地址，页面大小为4KB，页表项大小为4B，假设采用纯页式存储，则要采用____级页表，页内偏移量为____位。

页面大小=4KB= $2^{12}$ B，按照字节编址，因此页内偏移量为12位，页号为40-12=28位。又页表项大小为4B，则每个页面可以存放 $2^{12}/4=2^{10}$ 个页表项。因此各级页表最多包含 $2^{10}$ 个页表项，需要10位二进制位才能映射到 $2^{10}$ 个页表项，故每一级的页表对应页号应为10位。故28位的页号至少要分为3级。
两级页表的访存次数分析（假设没有快表机构）：
- 第一次访存：访问内存中的页目录表
- 第二次访存：访问内存中的二级页表
- 第三次访存：访问目标内存单元
----->n级页表的访存次数是n+1次。

6.5.2分段存储管理（Segmentation）

6.5.2.1 基本内容

进程地址空间的概念：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编址。
内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。
优点：用户编程更方便，程序的可读性更高。也可描述为：方便编程；分段共享保护；动态链接；动态增长。

分段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）组成。段号的位数决定了每个进程最多可以分几个段；段内地址位数决定了每个段的最大长度是多少。

6.5.2.2 段表

程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称”段表“。段表中包含段号、段长、基址。

段表寄存器：段表始址F|段表长度M
作业逻辑地址表示：段号S|段内地址W

6.5.2.3 分段的保护与共享

段的保护
- 段表基址寄存器STBR和段表长度寄存器STLR
- 与段相关的保护位：只读、只写、只执行
- 与段相关的Validation位：为0表示不合法段
段的共享
- 设置共享段表
- 第一个请求使用共享段的进程申请内存分区，调入，修改共享段表内容
- 后续进程使用共享段，在本进程段表填入共享段物理地址；在共享段表中增加表目，将共享段计数count加1
- 回收执行count-1；count=0时撤销该共享段

6.5.2.4 对比

页是信息的物理单位，分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户不可见。
段是信息的逻辑单位，分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且由系统决定，段的长度却不固定，决定于用户编写的程序。
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
分段的用户进程地址空间是二维的，程序员再表示一个地址时，既要给出段名，也要给出段内地址。
分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或可重入代码（不属于临界资源）。

6.5.3 段页式管理方式

段页式系统的逻辑地址结构由==段号、页号、页内地址（页内偏移量）==组成。
设置段表地址寄存器，保存当前执行进程段表的起始地址和段表的长度。
在不引入快表的情况下，访问一个逻辑地址所需访存次数为3次。

ch7.虚存管理

7.1 局部性原理（Locality）

时间局部性：刚刚访问过的指令或数据，不久又会被再次访问。
空间局部性：刚刚访问过的指令或数据，其邻近单元不久会被访问。
顺序局部性（程序的顺序执行）：

通常情况下，CPU跟踪程序的执行是按照在主存中的连续地址进行的。只有在遇到转移指令时，才发生跳转。

7.2 虚拟存储器

定义：从用户角度，将系统可提供的比实际大很多的内存容量，称为虚拟存储器。

实现方式：请求分页系统、请求分段系统

硬件支持：页/段表扩充，缺页/段中断，地址变换

特征：

虚拟性
离散性：采用离散分配方式
多次性：一个作业分成多次调入主存运行
对换性：将得不到运行的程序、数据调至外存交换区

虚存的优势：

比物理内存大的程序可以运行，编程人员无需考虑内存的限制；
可以让更多的程序同时运行，系统吞吐量提高；
更容易实现文件共享；
加载或交换程序到内存所需的I/O更少，程序运行更快；

7.3 请求分页机制

英文名为Demand Paging，页面仅在需要的时候加载进入内存。
惰性交换器Lazy swapper——进程驻留在外存，执行时所需要的页面交换到内存。
调页程序：pager
为进程分配的最小页框数（物理块数）：3个
- 数据段
- 代码段（指令）
- 间接寻址
页表内容：

页号页框号状态位P 访问位A 修改位M 外存地址
访问位表示其是否被访问过，修改位表示其是否被修改过（多为数据）
缺页中断机构与一般中断的2点区别：
- 是在指令执行期间，发现指令/数据不在主存时产生并处理；
- 一条指令在执行期间，可能会产生多次缺页中断。要求系统能保存多次中断的状态。
基本地址变换：
页面分配策略：
- 内存记录空闲页框情况——位示图bitmap
- 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
  - 驻留集：指请求分页存储管理中给进程分配的物理块的集合。
- 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变
页面置换策略：
- 局部置换：发生缺页时只能选进程自己的物理块进行置换。
- 全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
- 与分配策略组合，有以下三种算法：固定分配局部置换、可变分配全局置换、可变分配局部置换

	局部置换	全局置换
固定分配	√	—
可变分配	√	√

【注】全局置换意味着一个进程拥有的物理块数量必然会改变，因此不可能是固定分配。

7.4 页面置换算法

在实际操作中，遇到缺页情况可以在下面标记"+"号。

7.4.1 先进先出置换算法

First In First Out
先进入内存的页面，先置换出内存。
缺页率高
存在==Belady现象==，即分配页框数多，反而缺页率高。

7.4.2 最佳置换算法（Optimal）

以后以段很长时间不用的页面先置换
理想算法，不能实际实现

7.4.3 最近最久未使用算法（LRU）

最近很长时间不用的页面先置换
在操作中，若发现要访问的页面在页框内，需要将其放到最前面；到要置换页框中某个页面时，将最后的移出页框。
计算机中的实现
- 计数法实现：
  
  每个页表项设置一个计数器，若页面被访问，则将当前时间复制到计数器中。
  
  当需要置换时，查找计数器，离当前时间最远的先淘汰；
- 堆栈法实现：
  
  维护一个页号的堆栈，当被访问，就将其移动到top位置；
  
  淘汰堆栈最bottom的页号

7.4.4 Clock置换算法

LRU近似算法
简单Clock NRU（Not Recently Used）：
- 内存中所有页面组成循环队列（设置指针），当需要置换时，依次检查访问位：
  为0，置换；
  为1，重置为0，继续检查下一个页面。
- 如访问序列为123412512345，则：
改进型Clock算法：
- 考虑到仅被淘汰过的页面被修改过，才需写回内存。故在其他条件相同时，应先淘汰未修改过的页面，避免I/O操作。
- 设置**(淘汰位A,修改位M)，A=1表示近期访问过，M=1表示近期修改过，(0,0)应优先淘汰，淘汰优先级为：(0,0),(0,1),(1,0),(1,1)**。

7.4.5 其他算法

最少使用置换算法（Least Frequently Used）：选择近期使用次数最少的页面淘汰；类似还有最多使用置换算法。
页面缓冲算法（Page Buffering Algorithm）：
- 思想：采用可变分配、局部置换方式。置换算法FIFO，被置换的页按是否被修改过而入系统设置的两个链表队列：修改页面链表、空闲页面链表。
- 如果再次产生缺页中断，首先检查链表队列：
  有，恢复到进程驻留集中；
  
  无，取空闲页面链表中第一页分配。
  
  修改页面链表中页面达到一定数量时，集中回写，减少I/O次数。

7.5 请求分页系统性能分析

7.5.1 缺页率与有效访问时间

有效访问时间（Effective Access Time）：

EAT=$ (1-p) $内存访问时间 +$ p$ 缺页中断时间（缺页中断服务时间
+页面置换出去的时间（可选，若未被修改，直接覆盖即可）
+缺页读入时间
+进程恢复执行时间）

7.5.2 工作集/驻留集模型

工作集：指在某段时间间隔里，进程实际访问页面的集合。英文为Working Set Model，是Denning根据程序的局部性理论提出，以解决缺页率高的问题。其可用一个二元函数$W(t, \Delta) $来表示：

$t$ 是当前的执行时刻
$\Delta$ 称为工作集窗口（Working-set window），即一个定长的页面访问的时间窗口（“时间段”）； $\Delta$ 不应过大或过小，过小会导致频繁缺页。
$\Delta)$ =进程在当前时刻 $t$ 之前的 $\Delta$ 时间窗口（在 $t-\Delta$ 到 $t$ 时间段）当中的所有页面所组成的集合（随着 $t$ 的变化，该集合也在不断地变化）； $W$ 是 $\Delta$ 的非降函数。
$\Delta)|$ 为工作集中包含的页面数

【注】工作集大小的变化与程序的局部性有关。

驻留集：指请求分页存储管理中给进程分配的物理块（物理空间）的集合，即进程实际驻留在内存当中的页面集合。

工作集和驻留集不同，驻留集表示当前要访问的页面在内存中的集合，工作集表示当程序运行过程中要访问的页的集合。

在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。如果一个进程的整个工作集都在内存中，即驻留集 $\supseteq$ 工作集，则进程将很顺利的进行，不会造成太多的缺页中断。

若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；若驻留集太大，又会导致多道程序并发度下降，资源利用率降低。

7.5.3 抖动现象

刚刚被换出的页很快又被访问，需再次调入。使进程花费大部分时间进行页面的置换，称进程发生了“抖动”。

预防抖动的方法：

采用局部置换策略，使抖动控制在局部范围
在CPU调度程序中引入工作集算法，控制道数
调整道数，使产生缺页频率的平均时间=系统处理缺页的平均时间（L=S准则）
挂起若干进程
增大页面大小（页面大小的选择）
预调页面

7.6 请求分段机制

英文名为Demand Segmentation
段表机制：

段名	段长	内存地址	状态位（该段在不在内存）	存取方式（可读/可写/可执行）	访问位（是否被访问）	修改位	增补位（如该段是否可以动态增长）	外存地址

缺段中断：在一条指令的执行期间，产生并处理中断，且可能产生多次缺段中断。可采用紧凑技术/淘汰几个段（多为代码段）。
请求分段的共享和保护：
- 共享方式为：每个共享进程段表中，在相应共享段表目中，指向共享段在内存的起址即可。系统实现方式为：
  - 设置共享段表/现行分段表
  - 建立共享段分配、回收操作过程
- 完善分段保护机制，有3种常用措施：越界检查，存取控制检查，环保护机构（即软件层次结构设置优先规则，外环访问内环需系统调用，内环可以直接访问外环）。

ch8.文件系统接口

8.1 概念

8.1.1 文件的概念及逻辑结构

文件是具有文件名的一组相关信息的集合，是一个由操作系统定义和实现的抽象数据类型；其组成的大小关系为文件-----记录-----数据项（组成文件的原子性数据，如类型、值）。文件逻辑结构是指从用户观点出发，所观察到的文件组织形式。它是用户可以直接处理的数据和结构，独立于物理特性。

文件逻辑结构分为以下几种结构：

无结构：字或字节的序列（如记事本）
简单记录结构：行、固定长度、可变长度
复杂结构：
- 格式化文档
- 可重定位加载文件

操作系统、程序决定文件的逻辑结构。有结构文件按记录的组织形式可分为：

顺序文件
- 文件记录的排列、存取按顺序进行。
- 适用场合：对记录批量存取（大量文件的备份）；顺序介质（磁带）
- 缺点：增删不方便、读取慢、查找性能差
索引文件
- 为变长记录文件建立一张索引表（或多级索引），用户通过关键字访问记录。
- 适用场合：对信息处理及时性要求高的场合。
- 优点：随机存取
- 缺点：索引需要额外开销
索引顺序文件
- 顺序文件记录分组，并建立索引表，索引表项为各组的第一记录指针。
  
  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OVdjtTT3-1649573738299)(https://gitee.com/sxpicture_bed/Images/raw/master/image-20220401163047706.png)]

8.1.2 文件属性及操作

文件的属性有：

名称：人类可读形式保存的唯一信息
标识符：唯一标记文件系统的文件，通常是数字
类型：支持不同类型文件的系统所需要的信息
位置：指向设备与设备上文件位置的指针
大小：当前文件的尺寸及最大尺寸
- 总大小：文件内容的总大小
- 总计文件大小：文件信息和文件内容的总大小
保护：确定谁能读写执行操作的访问控制信息
- 可读
- 可写
- 可执行
时间、日期和用户标识（谁创建、修改）
扩展文件属性

文件的操作有：

对记录的操作：增、删、改、查；
对文件本身的操作：
- 创建
- 读、写
- 查找
- 删除
- 截断（truncate，分成两个文件）
- 打开、关闭文件
- 设置读写位置

8.1.3 文件类型

按用途分：系统、用户、库文件（标准子程序、常用例程，.lib）
按存取控制属性：只读文件、读写文件、只执行文件
按文件逻辑结构：有结构、无结构文件
按文件物理结构：顺序、链接、索引文件
按文件中数据形式：源文件、目标文件、可执行文件
按信息存储的期限：临时文件、永久文件、档案文件
UNIX系统内的文件类型：
- 普通文件（r）
- 目录文件（d）
- 特殊文件（s），即设备文件，分为块设备文件和字符型设备文件
  - 块设备文件描述的是以随机访问的数据库为单元的设备。在打开一个块设备文件后。可以直接去访问它的某一个数据块，而不用管其文件系统的内部结构，如硬盘。
  - 字符设备文件指以字符流方式进行操作的设备，如打印机、调制解调器。

8.1.4 文件系统

文件系统是用于操纵和管理各种文件，方便用户使用文件的软件集合。

8.2 文件访问方法

8.2.1 顺序访问

文件信息按顺序（如一条一条记录）进行处理，用于归档等场合。

Read_next()：读取文件的下一部分
Write_next()
reset

8.2.2 直接访问

允许程序按任意顺序进行读取和写入，用于磁盘等场合。磁盘上的文件可以通过顺序或直接访问。

Read(n)：读取文件的第n条记录
Write(n)
Position_file(n)：定位（查找）文件

8.3 文件目录结构

8.3.1 概述

文件目录结构是用于有效管理和组织文件的结构。借助于文件目录，可将每个文件的符号名与其所在存储空间地址联系起来。目录结构和文件都驻留在外存（如磁盘）上。

对目录管理的要求有：
- 实现“按名存取”
- 有较高的目录检索速度：合理组织文件目录
- 允许文件重名
- 提供文件共享功能

文件的地址以其磁盘位置开始。
设备目录需要提供以下信息：名称、类型、地址、当前长度、最大长度、最后访问时间、最后更新时间、创建者，保护信息等。
对目录的操作有：创建、删除、重命名、查找、列表内容、遍历文件系统（ls）、复制、设置目录权限等。

8.3.2 常见目录结构

8.3.2.1 单级目录结构

Single Level Directory
整个系统只建立一张目录表，为每个文件分配一个目录项。

优点：
- 空间开销小
- 可以实现“按名存取”
缺点：
- 查找速度慢（线性表需遍历）： N个目录，平均查找N/2个目录项
- 不允许重名
- 不能实现共享

8.3.2.2 两级目录结构

Two-Level Directory
系统建立一张主文件目录MFD，为每个用户建立用户文件目录UFD，每个用户文件目录在MFD中分配一个目录项。

优点：
- 提高了查找速度：
  
  设共n个用户，每个用户m个文件，则二级目录需查找 $(n + m) / 2$ 个目录项（若n=m，则共n个）；
  
  而如果设一级目录，则需查找 $n * m / 2$ 个目录项（若n=m，共 $n^{2}/2$ 个）。
- 不同用户文件允许重名
缺点：不能文件共享。

8.3.2.3 树形目录结构

Tree-Structured Directories
在两级目录基础上，允许用户创建自己的子目录并组织其文件。

路径名：从根目录到文件之间的通路。
当前目录：
- 相对路径：从当前目录到文件之间的路径
- 绝对路径：从根目录到文件之间的路径
目录的增加和删除：
- 增加：无重名 mkdir <dir-name>
- 删除：不删除非空目录/可删除非空目录

8.3.2.4 无环图目录结构

Acyclic-Graph Directories
目录结构中有共享的子目录和文件，如“快捷方式”。
优点：
- 可共享：链接方式实现、复制文件信息
- 更灵活
- 遍历图相对简单
其他需要考虑的问题：
- 多个绝对路径名？——别名问题
- 删除——悬挂指针问题

8.3.2.5 通用文件结构

General Graph Directory
允许系统中存在环。

如何保证无环结构：
- 仅可link到文件，不能link到目录
- 增加新链接时，采用检测算法
缺点：
- 查找时对环要进行必要处理
- 删除：garbage collection

8.4 文件共享

文件共享是指多个用户（进程）共享同一份文件，系统只保存文件的一个副本。

早期文件共享方法有：

基本文件目录
- 实现：将源文件目录分为基本文件目录BFD和符号文件目录SFD
- BFD：每个文件/目录有一个目录项，文件标识数、其他信息
- SFD：每个用户一个，目录项只是其文件名和文件标识数
- 提高文件访问速度：系统设置活动文件表AFT,用户设置活动名字表ANT

连访法
- 建立目录间的链接，使目录项直接指向另一个目录项
- 在文件说明中增设“连访”属性，标识文件说明中的物理地址是一文件或目录项的指针
- 增设“用户计数”标识共享文件的用户数（当用户计数count=0时，才能删除文件内容）
绕弯路法
- 实现：系统设置当前目录指针，用户对当前目录下的文件直接访问，当需访问其它目录下文件时，通过指定路径完成。

现今常用文件共享方式有：

多个用户（进程）共享同一份文件，系统只保存文件的一个副本。

基于索引节点的共享方式：
- 实现：设置索引结点，存储文件的物理地址、链接计数（共享计数）及其它文件属性；文件目录只包括文件名和该文件对应索引结点的指针。
- 优点：任何对索引结点内容的修改对其它共享用户都是透明的。
利用符号链实现文件共享：
- 实现：设B为了共享C的文件F，在B中创建一个Link类型的新文件，新文件目录中只包含被链接文件F的路径名，称这种链接方法为符号链接(symbolic Linking)。
- 说明：只有文件主人的目录中有文件索引结点的指针，其它用户目录中只有路径名。

8.5 文件保护

8.5.1 概述

影响文件系统安全性的主要因素
- 人为因素
- 系统因素：系统部分软件、介质故障
- 自然因素：存放在磁盘中的数据，随时间变化发生溢出或消失
文件保护功能：
- 防止未核准用户存取文件（文件保密）
- 防止一个用户冒充另一个用户存取文件
- 防止核准用户误用文件
保护措施：
- 存取控制机制
- 容错技术
- 后备系统

8.5.2 存取控制机制的概念及实现

保护域——进程可访问的对象
- 访问权：一个进程对某对象可执行操作的权限，表示为有序对==(对象名，权集)==，权限有R（可读）、W（可写）、E（可执行）
- 域：一组对象访问权的集合
- 进程与域的联系方式：
  - 静态联系：进程可用资源集是固定的
  - 动态联系：进程可用资源集是可变的，需提供域转换机制、read to know须知原则。

访问矩阵(Access Matrix)——描述域及所属对象的矩阵（Lampson矩阵）
- 访问矩阵中对象访问权由资源拥有者或管理者确定。
- 通过设置域间切换开关实现进程与域的动态联系。
- 为满足修改的需要，增设：
  - 拷贝权（权限copy）
  - 所有权（标明owner）
  - 控制权
- 拷贝权的应用：将具有拷贝权的对象访问权拷贝到其他域中，使其他域中进程对同一对象具有相同访问权。
- 访问矩阵为稀疏矩阵，所以实现上可以采用：
  - 访问控制表(Access Control List)——按列划分，用**(域,权集)表示，设置到文件对象中（文件[属性]控制块FCB**）
  - 权能表(Access Capability List)——按行划分，用**(对象,权集)表示，设置到进程控制块PCB**中
  对一个文件的访问，常由用户访问权限和文件属性共同限制。
- 文件拥有者对文件进行保护：
  - 访问模式：读、写、执行
  - 用户分类：文件拥有者（owner）、和文件同属于一组的用户（group）、其他用户（other）
  - 构成9位权限位

文件系统是所有文件、目录的集合，操作系统一般采用层次型模型对文件系统进行管理。分级安全管理有如下几个层次：

系统级安全管理：注册、登录
用户级安全管理：用户分类、文件访问权限
目录级安全管理：文件目录访问权限、用户分别设置
文件级安全管理：每个文件访问存取控制权限机制

ch9.文件系统实现

9.1 磁盘的结构及功能实现

磁盘的表面被划分成一个个磁道（track），一个磁道又被划分成一个个扇区（sector），可以给每个扇区进行编号，各个扇区存放的数据量相同（如1KB）。由于最内侧磁道上的扇区面积最小，因此数据密度最大。
一个盘片可能有两个盘面；所有的磁头都是连在同一个磁臂上的，所有磁头“共进退”。所有盘面中相对位置相同的磁道（如上图的三个蓝色磁道）组成柱面。
可用**(柱面号,盘面号,扇区号)**来定位任意一个“磁盘块”。根据该地址可以读取一个”块“：
- 根据”柱面号“移动磁臂，让磁头指向指定柱面
- 激活指定盘面对应的磁头
- 磁盘旋转的过程中，指定的扇区会从磁头下面划过，由此完成对指定扇区的读/写。

9.2 磁盘访问时间

寻道时间 $T s$

移动磁臂到预期读取的柱面（磁道）所需要的时间。假设移动（跨越）一个柱面（磁道）所需时间为t，需要移动n个磁道，则 $T s = n t$ 。

旋转延迟时间 $T r$

磁盘旋转使磁头定位到目标扇区所需要的时间，设磁盘转速为 $r$ （单位：转/秒或转/分）， $1 / r$ 为转一圈需要的时间，找到目标扇区平均需要转半圈，故 $T r = (1 / 2) * (1 / r) = 1 / 2 r$ 。若前面单位为分，后面单位为秒，则需要 $T r = 30 / r (s)$ 。

数据传输时间 $T t$

从磁盘读出或向磁盘写入数据所经过的时间，设传输的字节总数 $T o t a l$ ，磁盘转速为 $r$ 转/分，一转的字节数（每个磁道上的字节数）为 $b$ ；则有：每个磁道可以存 $b$ 个字节，则 $T o t a l$ 字节的数据需要 $T o t a l / b$ 个磁道才能存储。而读/写一个磁道所需时间刚好是转一圈所需要的时间 $1 / r$ ，则 $T t = T o t a l / r b$ 。

总平均存取时间为三个时间之和。

【例】设某磁盘平均寻道时间为10ms，转速为10000r/m，每个磁道有320个扇区，每个扇区512字节。求读取一个包含2560个扇区、大小为1.2MB的文件所需的时间。

假设文件顺序存储：

$T s = 10 m s$ ， $T r = 3 m s$ ，读取320个扇区的时间 $T t 1 = 1 / r * 60000 = 6 m s$ ，则 $T 总 = 19 + 7 \times 9 = 82 m s$ ；（每次换道还需旋转找到该磁道的第一号扇区）

假设文件随机存储：

$T 总 = 2560 \times (10 + 3 + 60000 / 10000 / 320) = 33328 m s$ （每个扇区中的数据传输时间为：1/r(读一磁道) * 1/320(读一扇区)[*60000是分与微秒的单位换算]）。

【注】文件内容所占用的空间要比真实的文件所占用空间要小，扇区是磁盘读写的最小单位。

9.3 磁盘调度算法

目标：最小化寻道时间。

先来先服务FCFS(First Come First Served)：

思想：选择等待队列中最先到达的访问请求，作为下一次的访问对象。

假设磁盘请求序列为55, 58, 39, 18, 90, 160, 150, 38, 184 （柱面号），总的柱面号为0-199，当前磁头位置在100号柱面。

最短寻道时间优先SSTF：

思想：选择等待队列中离当前磁道最近的访问请求，作为下一次的访问对象。注意此算法是局部优，最终不一定是最优的。

假设磁盘请求序列为55, 58, 39, 18, 90, 160, 150, 38, 184 （柱面号），总的柱面号为0-199，当前磁头位置在100号柱面。

优点：吞吐量大，任务平均响应时间更快；

缺点：任务响应机会不均等（低磁道、高磁道两边的请求无限滞后）。

扫描算法SCAN（也称电梯调度法）：

思想：选择等待队列中离当前磁头移动方向最近的访问请求，作为下一次的访问对象。

假设磁盘请求序列为55, 58, 39, 18, 90, 160, 150, 38, 184 （柱面号），总的柱面号为0-199，当前磁头位置在100号柱面，设磁头向磁道增加的方向移动。

原始算法需到最高磁道才会返回，改进LOOK则到序列中最高的磁道后即返回。题目中扫描算法默认是改进LOOK算法。

缺点：存在armstickiness（磁臂黏着）现象，一个或多个进程反复请求某个磁道，从而垄断整个磁道，导致”饥饿“。

扫描算法C-SCAN：

思想：单向扫描，选择等待队列中离当前磁头移动方向最近的访问请求，作为下一次的访问对象，直到该方向最后一个请求，反向。

假设磁盘请求序列为55, 58, 39, 18, 90, 160, 150, 38, 184 （柱面号），总的柱面号为0-199，当前磁头位置在100号柱面，设磁头向磁道增加的方向移动。

N步扫描算法N-SCAN：

思想：将磁盘请求队列分为若干长度为N的子队列，并按FCFS算法依次处理这些队列，在处理每一个队列时，采用SCAN算法。(当N=1时等价于先来先服务算法，N为无穷时等价于SCAN算法)

假设磁盘请求序列为55, 58, 39, 18, 90, 160, 150, 38, 184 （柱面号），当前磁头位置在100号柱面，设磁头向磁道增加的方向移动，采用N=3的N步扫描算法。

FSCAN扫描算法：

思想：将磁盘请求队列分为2个子队列，其中一个为当前所有请求构成的队列，另一个为扫描期间新到达的请求构成的队列，并按N步扫描处理。

各种算法比较：
- SSTF较为常用
- SCAN和C-SCAN在负载较重的情况（输入/输出任务较多）下性能更好
- 性能的取得一般依赖请求序列，而请求序列与文件分配方式相关
- SSTF和LOOK常会选为缺省算法

9.4 文件物理结构

9.4.1 连续分配

文件在外存分配连续的磁盘块。

优点：支持顺序访问、直接访问；磁头定位时间短，顺序访问速度快。

缺点：要求连续盘块，易产生碎片（外碎片）；需预知文件长度。

顺序文件中的逻辑记录依次存储在连续的磁盘块。

9.4.2 链接分配

9.4.2.1 单向链表

通过磁盘块中的链接指针，将文件所属盘块链成链表。

隐式链接的实现：文件目录中只给出文件第一、最后一个盘块的指针，其余由链接指针给出。

显式链接的实现：系统设置一张链接表（FAT），对每个物理块，存放的是与该物理块链接的下一个物理块号，文件目录中保存第一块的盘块号。

缺点：不支持直接访问，FAT需要磁盘空间。

串联/链接文件中的逻辑记录存储的磁盘块中设指针指向下一条记录所在物理块号。

优点：简单、记录数可任意增减；

缺点：查找只能单向查找，不能直接找某个磁盘块；可靠性差（1个出错整个文件的存储均会出现问题）；磁盘块中会少一个链接指针对应的空间。

9.4.2.2 异或双向链表

设文件A有三个记录，存储在4，12，8三个物理块中。

查找过程：

向下查找：本记录链表指针值与上记录块号“异或”
向上查找：本记录链表指针值与下记录块号“异或”

付出时间（计算）代价。

9.4.3 索引分配

建立索引表保存文件所分配的磁盘块号。

单级索引分配：只有一个磁盘块存放索引表
多级索引分配：多个磁盘块存放索引表

混合索引分配：结合直接地址和多级索引分配的方式

每个索引文件建立一张索引表，每一个表目指向记录所在的物理块号。

优点：可支持直接访问、顺序访问；无外部碎片；

缺点：索引表需要额外开销。

**【例】**某文件有1000条记录，文件采用索引分配，设每一个盘块存放一个记录，每一盘块可以存放10个索引表目。

（1）保存该文件需要建立几级索引？（2）共需要多少磁盘块？

【解】（1）三级索引；（2）共需要1+10+100+1000=1111块。

9.5 空闲空间管理方法

主要功能：

设置相应数据结构，记录空闲存储空间的分配情况
实现存储空间的分配与回收

空闲表法：设定空白文件目录

管理：系统为每一个空白文件（一个连续未分配的区域）建立一个目录，每个空闲区有一个表目。
数据结构：第一个空白块地址，空白块数
分配：系统依次扫描空白文件目录，找到一个合适的空白文件分配
回收：动态修改空白文件表（合并）
特点：
- 适用于建立顺序文件
- 当有大量小的空白文件时，效率降低

空闲块链：

管理：将所有空闲块链接在一起，组成队列。
数据结构：链表
分配：从链首依次摘取1块或n块；
回收：回收块入链尾。
特点：
- 操作简单
- 当链较长时，效率较低
改进：空闲盘区链

位示图：

管理：系统专设几个字，字中每一位对应一个磁盘块。
数据结构：字；位——1：表示已分配；0表示空闲
分配：找到0所指示的空闲块进行分配；每位对应的盘块号b=i*n+j（b，i，j从0开始计数；i，j分别为行列值，n表示每行位数）
特点：位示图尺寸固定；可常驻内存，分配回收快
注意：第x块=块号+1

成组链接法（Unix采用）：

管理：设置空闲盘块号栈，存放当前可用的一组空闲盘块的盘块号（最多存放100个号），以及堆栈中尚有的空闲块数。
数据结构：堆栈
说明：
- 栈属于临界资源，应互斥使用
- S.free(0)是栈底
- 栈满时，栈顶为S.free(99)。

image-20220409173108133" style=“zoom:67%;” />