操作系统（期末复习知识点）

第1章 操作系统引论

操作系统的目标和作用

操作系统的目标

在计算机系统上配置OS，其主要目的是实现：方便性、有效性、可扩充性、开放性。

操作系统的作用

可以从人机交互、资源管理及资源抽象等不同方面来分析OS在计算机系统中所起到的作用。?

1. OS 作为用户与计算机硬件系统之间的接口
2. OS 作为计算机系统资源的管理者
3. OS 实现了对计算机资源的抽象

操作系统的发展过程

分时系统

分时系统（Time-sharing System）是一种操作系统结构，它允许多个用户通过共享计算机系统的资源和时间来同时访问计算机。分时系统的基本概念是将计算机的处理时间划分成小的时间片，并在每个时间片内为不同的用户提供处理时间，以实现多用户同时使用计算机的效果。

分时系统的特征

1. 多路性，是指系统允许将多台终端同时联接到一台主机上，并按分时原则为每个用户 服务。多路性允许多个用户共享一台计算机，这显著地提高了资源利用率，降低了使用费用， 从而促进了计算机更广泛的应用。
2. 独立性，是指系统提供了一种用机环境，即每个用户在各自的终端上进行操作，彼此 之间互不干扰，给用户的感觉就像是他一人独占主机。
3. 及时性，是指用户的请求能在很短的时间内获得响应。这一时间间隔是根据人们所能 接受的等待时间确定的，通常仅为1～3s。
4. 交互性，是指用户可以通过终端与系统进行广泛的人机对话。其广泛性表现在：用户 可以请求系统提供多方面的服务，如进行文件编辑和数据处理、访问系统中的文件系统和数据 库系统、打印运行结果等。

实时系统

实时系统的类型

1. 工业控制系统。当计算机被用于生产过程的控制，形成以计算机为中心的控制系 统时，该系统应具有能实时采集现场数据，并对所采集的数据进行及时处理，进而能够自动 控制相应的执行机构，使之具有按预定的规律变化的功能，以确保产品的质量和产量。类似 地，也可将计算机用于对武器的控制，如火炮的自动控制系统、飞机的自动驾驶系统以及导 弹的制导系统等。
2. 信息查询系统。该系统接收用户从远程终端上发来的服务请求，根据用户发来的请求 对信息进行检索和处理，并能及时对用户做出正确的回答。具体的信息处理系统有飞机或火车 的订票系统等。
3. 多媒体系统。随着计算机硬件和软件的快速发展，文本、图像、音频和视频等信息已 能被集成在一个文件中，进而形成一个多媒体文件。例如，在使用光盘播放器所播放的数字电 影中，就包含了音频、视频和横向滚动的文字等信息。为了保证好的视觉和听觉感受，用于播 放视频和音频的多媒体系统必须是实时信息处理系统。
4. 嵌入式系统。随着集成电路的发展，已制作出各种类型的芯片，可将这些芯片嵌入各 种仪器和设备中，用于对设备进行控制或对其中的信息进行处理，这样就构成了所谓的智能仪 器和智能设备。此时还须为其配置上嵌入式OS，它同样需要具有实时控制或处理功能。

操作系统的基本特性

• 并发：多个事件交替发生（宏观上同时发生、微观上交替进行）
• 并行：多个事件同时发生
• 共享（Sharing）：系统资源可供内存中多个并发执行的进程共同使用
  • 互斥共享方式：一个时间段内只允许一个进程访问该资源
  • 同时共享方式：允许一个时间段内由多个进程“同时”对它们进行访问?
• 虚拟（Virtual）：将一个物理实体映射为若干个对应的逻辑实体
  • 时分复用技术：一台处理机只能服务一个用户，通过将其时间进行划分，按照时间段轮流服务多个用户，可将一台物理上的处理机虚拟为多台逻辑上的处理机
  • 空分复用技术：将比较大的内存空间按区域划分为多个较小的内存空间，用于存放更多的程序，以提高内存的利用率。
• 异步（Asynchronism）：也成为不确定性，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停的，以不可预知的速度向前推进。只有系统拥有并发性，才有可能导致异步性。

操作系统的结构

简单结构（无结构 or 整体结构）

• 基本概念：简单结构指的是操作系统没有明确的组织结构，所有的功能都集中在一个单一的程序中。
• 优点: 实现简单，适用于资源有限的系统。
• 缺点: 可靠性差，不易维护和扩展，难以应对复杂的系统需求。

模块化结构

• 基本概念: 将OS按其功能精细地划分为若干个具有一定独立性和大小的模块。每个模块负责特定的功能，模块之间通过接口进行通信。
• 优点:?
  • 提高了OS设计的正确性、可理解性和易维护性；
  • 增强了OS的可适应性；
  • 加速了OS的开发过程。
• 缺点:
  • 模块之间的接口设计和管理需要一定的复杂性；
  • 容易造成各种决定的“无序性”（在模块化结构设计中，各模块的设计齐头并进，无法寻找到一个可靠的决定顺序）

分层式结构

• 基本概念：分层式结构将操作系统划分为多个层次，每个层次提供不同的抽象和功能。较低的层次依赖于更高的层次，而更高的层次则构建在较低的层次之上。常见的层次包括硬件层、设备驱动层、操作系统核心层、用户界面层等。
• 优点：
  • 易保证系统的正确性
  • 可保证系统的易维护性和可扩充性
• 缺点：
  • 系统效率低

微内核结构

• 基本概念：微内核结构将操作系统核心的功能限制在最小的集合中，其他功能通过可加载的模块（称为服务器）来实现。微内核只提供最基本的功能，如进程管理、内存管理和进程间通信，而其他功能如文件系统、网络协议栈等则由独立的服务器提供。
• 优点：
  • 提高了系统可扩展性。
  • 增强了系统的可靠性。
  • 增强了系统的可移植性。
  • 提供了对分布式系统的支持。
  • 融入了面向对象技术。
• 缺点：
  • 由于模块化的开销，微内核结构可能导致性能损失。
  • 与传统的单体内核相比，微内核结构的实现和调试更加复杂。

外核结构

• 基本概念: 外核结构将操作系统的核心功能划分为两部分，一部分运行在内核空间，另一部分运行在用户空间。
• 优点:
  • 提高了系统的可靠性和安全性，支持更高的系统可定制性，易于维护和扩展。
• 缺点:
  • 由于涉及内核与用户空间之间的切换，可能导致性能损失。

第2章 进程的描述与控制

前驱图

所谓前趋图（precedence graph），是指一个有向无环图（directed acyclic graph，DAG）， 它用于描述进程之间执行的先后顺序。

图中的每个节点均可用于表示一个进程或一段程序，甚至是一条语句，节点间的有向边则表示两个节点之间所存在的偏序（partial order）或前趋关系 （precedence relation）。

在上面所示的无循环的前趋图中，存在着如下前趋关系：

P1 → P2，P1 → P3，P1 → P4，P2 → P5，P3 → P5，P4 → P6，P4 → P7，P5 → P8，P6 → P8，P7 → P9， P8→ P9。

上述关系还可表示为：

P={P1，P2，P3，P4，P5，P6，P7，P8，P9} → ={(P1，P2)，(P1，P3)，(P1，P4)，(P2，P5)，(P3，P5)，(P4，P6)，(P4，P7)，(P5，P8)，(P6，P8)，(P7，P9)， (P8，P9)}。

进程通信

是指进程之间的信息交换，通常有低级和高级之分。

低级通信的特点：

• 效率低
• 通信对用户不透明

高级通信的特点：

• 使用方便
• 高效地传送大量数据

进程通信的类型

1. 共享存储器系统
   1. 基于共享数据结构的通信方式
   2. 基于共享存储区的通信方式
2. 管道通信系统（必须提供以下3方面协调能力）
   1. 互斥
   2. 同步
   3. 确定对方是否存在
3. 消息传递系统
   1. 直接通信方式
   2. 间接通信方式
4. 客户机-服务器系统
   1. 套接字
   2. 远程过程调用和远程方法调用

线程的概念

线程的基本定义

线程是操作系统中能够独立执行的最小单位，它是进程中的一个实体。一个进程可以包含多个线程，这些线程共享进程的资源，如内存空间、文件句柄等。线程拥有自己的程序计数器、寄存器集合和栈空间，但共享同一进程的其他资源。

线程和进程的区别如下：

1. 调度和执行: 进程是操作系统进行资源分配和调度的基本单位，而线程是进程内部的执行单元。进程由操作系统进行调度，而线程由线程调度器进行调度。一个进程可以包含多个线程，这些线程可以并发执行，共享进程的资源。

2. 资源占用: 进程拥有独立的地址空间和系统资源，如内存、文件句柄等。每个进程都有自己的地址空间，进程间的通信需要特殊的机制，如管道、共享内存等。而线程共享同一进程的资源，它们可以直接访问进程的共享内存和全局变量，线程间的通信更加方便和高效。

3. 创建和销毁开销: 创建和销毁进程的开销较大，需要为进程分配独立的资源和初始化环境。而创建和销毁线程的开销较小，因为它们共享进程的资源，只需要为线程分配独立的栈空间和一些必要的数据结构。

4. 并发性: 由于进程之间拥有独立的地址空间和资源，进程间的并发性相对较低。而线程共享进程的资源，可以实现更高的并发性，多个线程可以同时执行不同的任务。

5. 安全性: 由于线程共享进程的资源，多个线程之间的共享数据需要进行同步和互斥操作，以避免竞态条件和数据一致性问题。而进程之间的数据共享相对较少，因此在安全性上更容易管理和控制。

总结来说，进程是资源分配和调度的基本单位，而线程是执行和调度的基本单位。线程共享进程的资源，可以实现更高的并发性和更高效的通信，但也需要更加复杂的同步和互斥机制来保证数据的一致性和安全性。

第3章 处理机调度与死锁

处理机调度的层次

高级调度

高级调度（high level scheduling）又称为长程调度或作业调度，它的调度对象是作业，主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进 程、分配必要的资源，并将它们放入就绪队列。高级调度主要用于多道批处理系统中，而在分 时系统和实时系统中，不设置高级调度。

中级调度

中级调度（intermediate scheduling）又称为内存调度。引入中级调度的主要目的是提高内存利用率和系统吞吐量。为此，应把那些暂时不能运行的进程调至外存等待，此时进程的状态称为就绪驻 外存状态（或挂起状态）。当它们已具备运行条件且内存稍有空闲时，由中级调度来决定把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改它们的状态为就绪状态，挂在就绪队列 上等待。

低级调度

低级调度（low level scheduling）又称为短程调度或进程调度，其所调度的对象是进程（或 LWP）。其主要功能是，根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派 程序将处理机分配给被选中的进程。低级调度是最基本的一种调度，在多道批处理、分时和实 时这3种系统中，都必须配置这种调度。

调度算法

先来先服务调度算法

（First-Come, First-Served Scheduling Algorithm）：

• 基本思想：按照作业到达的顺序进行调度，先到达的作业先执行。
• 优点：实现简单，公平性较高。
• 缺点：平均等待时间较长，可能出现“饥饿”现象，不适合长作业。

短作业优先调度算法

（Shortest Job First Scheduling Algorithm）：

• 基本思想：选择估计运行时间最短的作业进行调度，以减少平均等待时间。
• 优点：最大程度地减少平均等待时间，适合短作业。
• 缺点：难以准确估计作业的运行时间，可能导致长作业等待时间过长。

优先级调度算法

（Priority Scheduling Algorithm）：

• 基本思想：为每个作业分配一个优先级，优先级高的作业先执行。
• 优点：根据作业的重要性进行调度，可以满足不同作业的需求。
• 缺点：可能导致低优先级的作业长时间等待，可能出现“饥饿”现象。

轮转调度算法

（Round Robin Scheduling Algorithm）：

• 基本思想：将CPU的执行时间划分为多个时间片，每个作业按照顺序执行一个时间片，然后切换到下一个作业。
• 优点：公平性较高，适合时间片大小相对较小的场景。
• 缺点：响应时间较长，可能导致长作业的等待时间过长。

多级队列调度算法

（Multilevel Queue Scheduling Algorithm）：

• 基本思想：将作业划分为多个队列，每个队列有不同的优先级，不同队列采用不同的调度算法。
• 优点：根据作业的特性和优先级进行调度，灵活性较高。
• 缺点：难以确定各个队列的优先级和调度算法，可能导致某些队列的作业长时间等待。

多级反馈队列调度算法

（Multilevel Feedback Queue Scheduling Algorithm）：

• 基本思想：将作业划分为多个队列，每个队列有不同的优先级，作业根据执行情况在队列间进行调度。
• 优点：根据作业的执行情况进行动态调整，适应不同作业的需求。
• 缺点：调度算法较为复杂，可能导致过多的上下文切换。

基于公平原则的调度算法

• 基本思想：根据作业的执行时间、优先级或其他指标，按照公平的原则进行调度，以保证所有作业都能得到合理的执行时间。
• 优点：保证公平性，避免某些作业长时间等待。
• 缺点：可能导致长作业的等待时间过长，不适合对响应时间要求较高的场景。

死锁预防

破坏“请求和保持”条件

破坏“不可抢占”条件

破坏“循环等待”条件

死锁避免

银行家算法

第4章 进程同步

硬件同步机制

1. 关中断
2. 利用Test-and-Set指令实现互斥
3. 利用swap指令实现进程互斥

信号量机制

大佬blog

第5章 存储器管理

程序的装入

1. 绝对装入方式

当计算机系统很小，且仅能运行单道程序时，完全有可能知道程序将驻留在内存的什么位 置。此时可以采用绝对装入方式（absolute loading mode）。???????

2. 可重定位装入方式

绝对装入方式只能将目标模块装入内存中事先指定的位置，这只适用于单道程序环境。而在 多道程序环境下，编译程序不可能预知经编译后所得到的目标模块应放在内存的何处。因此，对 于用户程序编译所形成的若干个目标模块，它们的起始地址通常都是从0开始的，程序中的其他地址也都是相对于起始地址计算的。此时，不可能再用绝对装入方式，而应采用可重定位装入方式 （relocation loading mode），它可以根据内存的具体情况，将装入模块装入内存的适当位置。

3. 动态运行时装入方式

可重定位装入方式可将装入模块装入内存中任何允许的位置，故可用于多道程序环境。但该方式并不允许程序运行时在内存中移动位置。因为程序在内存中的移动，意味着它的物理位 置发生了变化，这时必须对程序和数据的地址（绝对地址）进行修改后，程序方能运行。然而 实际情况是，在运行过程中它在内存中的位置可能经常要改变，例如，在具有对换功能的系统 中，一个进程可能被多次换出，又被多次换入，每次换入后的位置通常是不同的。在这种情况 下，就应采用动态运行时装入方式（dynamic run-time loading mode）。

连续分配存储管理方式

单一连续分配

固定分区分配

动态分区分配

动态分区分配算法

基于顺序搜索的动态分区分配算法（顺序分配算法）

按照内存地址的顺序搜索可用的内存分区，找到第一个满足作业大小的分区进行分配。

首次适应算法

（First Fit Algorithm）：

• 基本思想：按照内存地址的顺序搜索可用的内存分区，找到第一个满足作业大小的分区进行分配。
• 优点：分配速度较快，适用于各种作业大小。
• 缺点：可能导致外部碎片的产生，分配不均匀。

循环首次适应算法

（Next Fit Algorithm）：

• 基本思想：从上一次分配的位置开始搜索可用的内存分区，找到第一个满足作业大小的分区进行分配。
• 优点：相比首次适应算法，减少了搜索范围，分配速度较快。
• 缺点：可能导致外部碎片的产生，分配不均匀。

最佳适应算法

（Best Fit Algorithm）：

• 基本思想：从所有可用的内存分区中选择最小的满足作业大小的分区进行分配。
• 优点：能够更好地利用内存空间，减少外部碎片的产生。
• 缺点：分配速度较慢，需要遍历所有可用分区。

最坏适应算法

（Worst Fit Algorithm）：

• 基本思想：从所有可用的内存分区中选择最大的满足作业大小的分区进行分配。
• 优点：能够更好地利用内存空间，减少外部碎片的产生。
• 缺点：分配速度较慢，需要遍历所有可用分区。

基于索引搜索的动态分区分配算法（索引分配算法）

维护一个索引表，记录每个内存分区的状态和大小，根据索引表进行分配和回收。

快速适应算法

（Quick Fit Algorithm）：

• 基本思想：将内存分为多个大小相等的快速适应表，每个表对应一定范围的作业大小，根据作业大小选择对应的快速适应表进行分配。
• 优点：分配速度较快，能够较好地适应不同大小的作业。
• 缺点：可能导致内部碎片的产生，需要预留一定的内存空间用于快速适应表。

伙伴系统

（Buddy System）：

• 基本思想：将内存分为大小为2的幂次方的块，根据作业大小选择合适大小的块进行分配，如有剩余则进行分割，合并时检查是否有相邻的同等大小的块。
• 优点：能够有效避免外部碎片的产生，分配和回收速度较快。
• 缺点：可能导致内部碎片的产生，需要额外的管理开销。

哈希算法

• 基本思想：将内存分为多个大小相等的哈希表，根据作业的哈希值选择对应的哈希表进行分配。
• 优点：能够较好地适应不同大小的作业，减少外部碎片的产生。
• 缺点：分配和回收速度较慢，需要额外的哈希函数计算。

分页存储管理方式

分页存储管理方式

分段存储管理方式

段页式存储管理方式

分页存储管理的基本方法

1. 页面和物理块

1）页面

分页存储管理将进程的地址空间分成若干个页，并为每页加以编号，从0开 始，如第0页、第1页等。相应地，也把内存空间分成若干个块，同样也为它们加以编号，如0# 块、1#块等。在为进程分配内存时，以块为单位，将进程中的若干个页分别装入多个可以不相 邻接的物理块中。由于进程的最后一页经常装不满一块，进而形成了不可利用的碎片，称之为 “页内碎片”或“内碎片”。

2）页面大小

在分页系统中，若选择过小的页面大小，则虽然可以减小内部碎片，起 到减少内部碎片总空间的作用，有利于内存利用率的提高，但是会造成每个进程占用较多的页 面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换入/换出的效率。然而， 如果选择过大的页面大小，则虽然可以减少页表的长度，以及提高页面换入/换出的效率，但是 又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为1KB、 2KB、4KB、8KB。

2. 地址结构

该结构包含两部分内容：前一部分为页号P，后一部分为位移量W，即页内地址。图5-17中 的地址长度为32位，其中0～11位为页内地址，即每页的大小为4KB；12～31位为页号，地址空 间最多允许有1M页。

3. 页表

在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，以保证进程仍然能够正确地运行，即能在内存中找到每个页面所对应的物理块。为此，系统又为每个进程建立了一张页面映像表，简称页表。是一种用于虚拟内存管理的数据结构，用于将虚拟地址空间映射到物理地址空间。它是操作系统中的一个重要组成部分，用于实现虚拟内存的分页机制。

页表的作用：

页表将虚拟地址空间划分为固定大小的页（Page），并将每个页映射到物理内存中的一个块（Page Frame）。页表通常由操作系统维护，每个进程都有自己的页表。

地址变换机构

快表

快表（Translation Lookaside Buffer，TLB）是一种高速缓存，用于加速虚拟地址到物理地址的转换。它是位于CPU内部的一块快速访问的存储区域，用于存储最近使用的地址映射结果。

快表的作用：

当CPU访问虚拟地址时，首先会在快表中查找对应的物理地址映射。如果快表中存在对应的映射，则可以直接获得物理地址，加速地址转换过程。如果快表中不存在对应的映射，则需要通过页表进行地址转换，并将结果存入快表，以便下次访问时可以直接使用。

第6章 虚拟存储器

页面置换算法

最佳页面置换算法

Optimal Page Replacement Algorithm）的基本思想是选择在未来最长时间内不再被访问的页面进行置换。它是一种理论上的最优算法，但在实际中很难实现，因为需要预测未来的页面访问模式。

优点：

• 理论上是最优的页面置换算法，可以最小化页面置换次数。

缺点：

• 需要预测未来的页面访问模式，实际中很难实现。
• 实现复杂度高，需要对未来的页面访问模式进行准确的预测。

先进先出页面置换算法

（First-In-First-Out Page Replacement Algorithm）的基本思想是选择最早进入内存的页面进行置换。

优点：

• 实现简单，只需要使用一个队列来记录页面进入内存的顺序。
• 公平性较好，每个页面都有平等的机会留在内存中。

缺点：

• 无法考虑页面的访问频率和重要性，可能会导致频繁访问的页面被置换出去。

最近最久未使用页面置换算法

（Least Recently Used Page Replacement Algorithm）的基本思想是选择最近最久未使用的页面进行置换。

优点：

• 考虑了页面的访问历史，更有可能置换掉长时间未被访问的页面。
• 在实际中相对容易实现。

缺点：

• 实现复杂度较高，需要记录每个页面的访问时间。
• 可能会受到访问模式的影响，当访问模式发生变化时，可能无法准确判断最近最久未使用的页面。

最少使用页面置换算法

（Least Frequently Used Page Replacement Algorithm）的基本思想是选择最少被访问的页面进行置换。

优点：

• 考虑了页面的访问频率，更有可能置换掉最少被访问的页面。

缺点：

• 实现复杂度较高，需要记录每个页面的访问次数。
• 可能会受到访问模式的影响，当访问模式发生变化时，可能无法准确判断最少使用的页面。

第7章 输入/输出系统

中断和中断处理程序

中断简介

1．中断和陷入

（1）中断（interrupt）

中断是指CPU对I/O设备发来的中断信号的一种响应。CPU暂停正在执行的程序，保存CPU现场环境后，自动转去执行该I/O设备的中断处理程序。执行完后再回到断点，继续执行原来的程序。I/O设备可以是字符设备，也可以是块设备以及通信设备等。由于中断是由外部设备引起的，故其又被称为外中断或硬中断。

（2）陷入或陷阱（trap）

另外还有一种由CPU内部事件所引起的中断，例如进程在运算过程中发生了上溢或下溢，再如程序出错（如指令非法、地址越界、电源故障等）以及执行到程序中预设的软中断指令。通常把这类中断称为内中断，或软中断，或陷入。与中断一样，若 系统发现了陷入事件，CPU也将暂停正在执行的程序，转去执行该陷入事件的处理程序。中断和陷入的主要区别是信号的来源不同，即来自CPU外部还是CPU内部。

2．中断向量表和中断优先级

（1）中断向量表

为了实现处理上的方便，通常会为每种设备配以相应的中断处理程序， 并把该程序的入口地址放在中断向量表的一个表项中，为每个设备的中断请求规定一个中断号，它直接对应中断向量表的一个表项。当I/O设备发来中断请求信号时，由中断控制器确定该请求的中断号，并根据该中断号查找中断向量表，从中取得该设备相应的中断处理程序的入口地址，这样便可转入中断处理程序并执行。

（2）中断优先级

实际情况是经常会有多个中断信号源，每个中断信号源对服务要求的紧 急程度并不相同，例如，键盘的中断请求的紧急程度不如打印机，而打印机的中断请求的紧急 程度又不如磁盘等。为此，系统就需要为它们分别规定不同的优先级。

磁盘性能概述

磁盘是一种相当复杂的机电设备，在此仅对其某些性能（如数据的组织与格式、磁盘的类 型、磁盘的访问时间等）做扼要阐述。

数据的组织和格式

磁盘可包括一个或多个物理盘片，每个盘片有一个或两个盘面（surface），如图7-29（a） 所示，每个盘面上有若干条磁道（track），磁道之间留有必要的间隙。为使处理简单起见， 在每条磁道上可存储相同数目的二进制位。这样，针对磁盘密度，即每英寸中所存储的位 数，显然是内层磁道的密度较外层磁道的密度高。每条磁道又从逻辑上被划分成若干个扇区 （sectors），软盘大约为8至32个扇区，硬盘则可多达数百个扇区，图7-29（b）显示了一个磁道被分成8个扇区。一个扇区称为一个盘块（或数据块）。各扇区之间保留一定的间隙。

一个物理记录存储在一个扇区上，磁盘上能存储的物理记录数目是由扇区数、磁道数以及 磁盘面数所决定的。例如，一个10GB容量的磁盘，有8个双面可存储盘片，共16个存储面（盘 面），每面有16383个磁道（也称柱面），每个磁道含63个扇区。?

磁盘的类型

• 固定头磁盘
• 移动头磁盘

磁盘的访问时间

• 寻道时间
  • ??????????????这是指把磁臂（磁头）移动到指定磁道上所经历的时间，该时间是启动 磁臂的时间k与磁头移动n条磁道所花费的时间之和，即：其中，m是一个常数，其与磁盘驱动器的速度有关，对于一般的磁盘，m=0.2；对于高速磁盘， m≤0.1；磁臂的启动时间约为2ms。这样，对于一般的温盘，其寻道时间将随寻道距离的增大而 增加，为5ms～30ms。
• 平均旋转延迟时间
  • ??????????????这是指某扇区移动到磁头下面所经历的时间，在不同类型的磁 盘中，旋转速度至少相差一个数量级，如软盘为300r/min，硬盘一般为7 200r/min到15 000r/min 甚至更高。对于磁盘的Tτ而言，如果是硬盘，则旋转速度为15 000r/min，每转耗时4ms，Tτ为 2ms；而如果是软盘，则旋转速度为300r/min或600r/min，这样，Tτ为50ms～100ms。Tτ的具体表 达如下：其中，r为磁盘每秒的转数。
• 传输时间
  • ??????????????这是指从磁盘读出数据或向磁盘写入数据所经历的时间。Tt的大小与每 次所读/写的字节数b和旋转速度有关，关系如下：其中，N为一条磁道上的字节数，当一次读/写的字节数相当于半条磁道上的字节数时，Tt与Tτ相同，因此，可将访问时间Ta表示为：由上式可以看出，在访问时间中，寻道时间和平均旋转延迟时间基本上都与所读/写数据 的多少无关，而且它们通常占据了访问时间中的大头。

磁盘调度算法

早期的磁盘调度算法

FCFS算法

（First-Come, First-Served）的基本思想是按照作业到达的顺序进行调度，先到先服务。即先来先服务，不考虑作业的执行时间或优先级。

优点：

• 简单易实现，没有复杂的调度算法。
• 公平性较好，每个作业都有平等的机会执行。

缺点：

• 不考虑作业的执行时间，可能导致长作业等待时间过长，影响系统的响应性能。
• 无法适应实时系统的需求，对于有紧迫性的作业无法及时响应。

SSTF算法

（Shortest Seek Time First）的基本思想是选择离当前磁头位置最近的磁道进行调度。

优点：

• 可以减少平均寻道时间，提高磁盘访问效率。
• 适用于磁盘访问模式具有局部性的情况。

缺点：

• 可能产生饥饿现象，即某些磁道会被频繁选择，而其他磁道很少被选择。
• 对于随机访问模式或磁道分布较为均匀的情况，效果不如其他算法。

基于扫描的磁盘调度算法

SCAN调度算法

基本思想是磁头按照一个方向移动，直到到达最边缘，然后改变方向继续移动，形成类似扫描的过程。

优点：

• 可以较好地平衡磁盘上的作业访问，避免某些磁道被长时间忽略。
• 适用于磁盘访问模式具有一定连续性的情况。

缺点：

• 可能会产生较大的平均寻道时间，特别是当磁头需要跨越多个磁道时。
• 对于随机访问模式或磁道分布较为离散的情况，效果不如其他算法。

CSCAN调度算法

（Circular SCAN）的基本思想是磁头按照一个方向移动，直到到达最边缘，然后立即返回到最开始的磁道，继续移动。

优点：

• 可以减少平均寻道时间，特别是当磁头需要跨越多个磁道时。
• 适用于磁盘访问模式具有一定连续性的情况。

缺点：

• 可能会产生较大的平均寻道时间，特别是当磁头需要跨越多个磁道时。
• 对于随机访问模式或磁道分布较为离散的情况，效果不如其他算法。

第8章 文件管理

文件共享

在现代计算机系统中，必须提供文件共享手段，即指系统应允许多个用户（进程）共享同 一份文件。这样，在系统中只须保留该共享文件的一份副本即可。如果系统不能实现文件共享 功能，则意味着凡是需要该文件的用户，都须各自备有此文件的副本，显然这会造成对存储空 间的极大浪费。随着计算机技术的发展，文件共享的范围也在不断扩大，从单处理机系统中的 共享扩展为多处理机系统中的共享，进而又扩展为计算机网络中的共享，甚至是全世界范围内的共享。

利用有向无环图实现文件共享

那现在问题就来了，如何建立父目录D5与共享文件F8之间的链接？如果在文件目录中所包含的是文件的物理地址，即文件所在盘块的盘块号，则在建立链接时，必须将文件的物理地址复制到D5目录中。但如果以后D5或D6还要继续向该文件中添加新内容，则必然要相应地再增加新的盘块，这将会由附加操作Append来完成。而这些新增加的盘块，也只会出现在执行了操 作的目录中。可见，这种变化对其他用户而言是不可见的，因而新增加的这部分内容已不能被共享。

为了解决上述问题，可以引用索引节点，即诸如文件的物理地址及其他文件属性等信息不 再放入目录项中，而是放在索引节点中。在文件目录中只设置文件名及指向相应索引节点的指 针，如下图所示。该方法在UNIX系统中被称为硬链接（hard link）。在下图中的用户Wang 和Lee的文件目录中，都设置有指向共享文件的索引节点指针。此时，由任何用户对共享文件所 进行的Append操作或修改，都将引起相应索引节点内容的改变（如增加了新的盘块号和文件长 度等），这些改变是其他用户可见的，从而也就可以将该文件提供给其他用户来共享。

在索引节点中还应有一个链接计数count，用于表示链接到本索引节点（亦即文件）上的用 户目录项的数目。?

利用符号链接实现文件共享

利用符号链接（symbolic link）实现文件共享的基本思想是，允许一个文件或子目录有多 个父目录，但其中仅有一个作为主（属主）父目录，其他父目录都是通过符号链接方式与之相链接的，故将它们简称为链接父目录。该图与上面那张图基本相同，差别仅在于将上面那张图中的某些实线改为了虚线，如在上面那张图中有三条实线指向了文件F8，而在下图中仅有D6指向F8的一条实线，另外两条指向F8的实线都已成为虚线。这表示F8仍然有3个父目录，但只有D6才是其主父目 录，而D5和D3都是其链接父目录。类似地，D6的主父目录是D2，D1是其链接父目录。这样做的最大好处是，属主结构（用实线连接起来的结构）仍然是简单树，这对于文件的删除、查找等操作而言都更为方便。

为使链接父目录D5能共享文件F，可以由系统创建一个LINK类型的新文件，也取名为F， 并将F写入链接父目录D5中，以实现D5与文件F8的链接。在新文件F的内容中只包含被链接文 件F8的路径名。这样的链接方法被称为符号链接或软链接。新文件F中的路径名被看作符号 链。当用户通过D5访问被链接的文件F8且正要读LINK类型的新文件时，此要求将被OS截获， OS会根据新文件中的路径名去查询文件F8，然后对它进行读/写操作，这样就实现了用户D5对 文件F的共享。

第9章 磁盘存储器管理

提高磁盘I/O速度的途径

磁盘高速缓存

在这里所要介绍的磁盘高速缓存，是指在内存中为磁盘盘块所设置的一个缓冲区，在该缓冲 区中保存了某些盘块的副本。当出现一个磁盘访问请求时，由内核先去查看所请求的盘块内容 是否已在磁盘高速缓存中，如果在，则可从磁盘高速缓存中直接获取，这样就省去了启动磁盘的操作，而且可使本次访问速度提高几个数量级；如果不在，则需要启动磁盘以将所需要的盘 块内容读入，并把读入的盘块内容送到磁盘高速缓存中，以便于以后又需要访问该盘块的内容 时直接从磁盘高速缓存中获取。

其他方法

1．提前读

如果采用顺序访问方式对文件进行访问，则可以预知下一次要读的盘块。此时可采取预先 读的方式，即在读当前块的同时要求将下一个盘块（提前读的盘块）中的数据也读入缓冲区。 这样，当下一次要读该盘块中的数据时，由于其已被提前读入缓冲区，因而此时可直接从缓冲 区中取得下一个盘块的数据，而无须再去启动磁盘I/O，从而大大减少了读数据的时间，有效地 提高了磁盘I/O的速度。“提前读”这一方法已被广泛采用。

2．延迟写

延迟写是指缓冲区A中的数据本应立即写回磁盘，但考虑到该缓冲区中的数据可能会在不 久之后再次被本进程或其他进程访问（共享资源），因而并不会立即将该缓冲区A中的数据写回 磁盘，而是会将它挂在空闲缓冲区队列的末尾。随着空闲缓冲区的使用，缓冲区也会缓缓往前 移动，直至移到空闲缓冲队列之首。当再有进程申请到该缓冲区时，就将该缓冲区中的数据写 回磁盘，同时把该缓冲区作为空闲缓冲区分配出去。只要该缓冲区仍在队列中，任何访问该缓 冲区中的数据的进程就都可以直接读出其中的数据而不必访问磁盘。这样，又可进一步减少磁 盘的I/O时间。同样，“延迟写”这一方法也已被广泛采用。

3．优化物理块的分布

在采用链接组织方式和索引组织方式时，可以将一个文件分散存储在磁盘的任意位置，但如果 过于分散，则会增加磁头的移动距离。例如，将文件的第一个盘块安排在最里边的一条磁道上，而 把第二个盘块安排在最外边的一条磁道上，这样，在读完第一个盘块后转去读第二个盘块时，磁头 要从最里边的磁道移到最外边的磁道上。如果我们将这两个数据块安排在属于同一条磁道的两个盘 块上，则显然会由于消除了磁头在磁道间的移动而大大提高对这两个盘块的访问速度。 对文件盘块位置的优化应在为文件分配盘块时进行。如果系统中的空闲存储空间采用位 示图进行表示，则要想将同属于一个文件的盘块安排在同一条磁道上或相邻的磁道上是十分 容易的事。此时，只要从位示图中找到一片相邻接的多个空闲盘块即可。但当系统采用线性表 第 9 章磁盘存储器管理 （链）法来组织空闲存储空间时，要为一个文件分配多个相邻接的盘块就要困难一些。此时可 以将在同一条磁道上的若干个盘块组成一簇（如一簇包括4个盘块），在分配存储空间时以簇为 单位进行分配。这样就可以保证在访问这几个盘块时，不必移动磁头或者仅移动一条磁道的距 离即可，从而减少了磁头的平均移动距离。

4．虚拟盘

由于访问内存的速度远高于访问磁盘的速度，于是有人试图利用内存空间去仿真磁盘，进而 形成所谓的虚拟盘，又称为RAM盘。该盘的设备驱动程序可以接受所有标准的磁盘操作，但这些 操作的执行不是在磁盘上而是在内存中进行。它们对用户而言都是透明的。换言之，用户不会发 现这与真正的磁盘操作有何不同，仅是略微快了些而已。虚拟盘存在的主要问题是：它是易失性 存储器，一旦系统或电源发生故障，或系统重启，原来保存在虚拟盘中的数据就会丢失。因此， 虚拟盘通常用于存放临时文件，如编译程序所产生的目标程序等。虚拟盘与磁盘高速缓存的主要 区别在于：虚拟盘中的内容完全由用户控制，而磁盘高速缓存中的内容则是由OS控制的。例如， 虚拟盘在开始时是空的，仅当用户（程序）在其中创建了文件后，其中才会有内容。

廉价磁盘冗余阵列

当今存在着一种非常有用的设计思想：如果仅使用一个组件对系统性能进行改进会受到很大 的限制，那么可通过使用多个相同的组件来获得系统性能的大幅度提升，这种情况在计算机领域 已屡见不鲜。正是在这种设计思想的推动下，单处理机系统演变成了多处理机系统，芯片上的单 核演变成了多核；同样，用这种设计思想来指导磁盘存储器的设计，于1987年开发出了由多个小 磁盘组成的一个容量很大的廉价磁盘冗余阵列（redundant array of inexpensive disk，RAID）。 RAID利用一台磁盘阵列控制器来统一管理和控制一组（几台到几十台）磁盘驱动器，进而 组成一个大型磁盘系统。RAID不仅大幅度增加了磁盘的容量，而且极大地提高了磁盘的I/O速度 和整个磁盘系统的可靠性。因此，RAID一经推出便被许多大型系统所采用。