操作系统

计算机系统概述

操作系统的基本概念

操作系统 是一组控制和管理计算机硬件和软件资源，合理地组织计算机工作流程，以及方便用户使用的程序的集合。它是计算机系统的核心与基石。

操作系统的目标：

1. 方便性：使计算机更易于使用。操作系统隐藏了硬件的复杂性，为用户提供了友好的界面。
2. 有效性：提高系统资源的利用率和系统的吞吐量。操作系统负责管理和调度硬件资源，如 CPU、内存、磁盘等。
3. 可扩充性：允许在不影响现有功能的情况下，方便地添加新的功能和模块。
4. 开放性：遵循开放系统标准，使得不同厂商的软硬件能够协同工作。

操作系统的功能：

1. 处理机管理：负责 CPU 的分配和调度，解决 CPU 的竞争问题。
2. 存储器管理：负责内存的分配、回收和保护，提高内存利用率，并提供虚拟内存等技术。
3. 文件管理：负责文件的存储、检索、共享和保护，提供树形目录结构等。
4. 设备管理：负责 I/O 设备的分配、控制和操作，提高设备利用率和 I/O 速度。
5. 用户接口：向用户提供使用计算机的手段，可以是命令接口（如 Shell）或图形用户接口（GUI）。

操作系统发展历程

1. 无操作系统阶段 (手工操作方式)：
   • 用户直接通过控制台开关操作计算机，独占全部资源。
   • 效率低下，CPU 等待人工操作。
2. 批处理系统：
   • 单道批处理系统：引入输入/输出磁带和监督程序，作业成批输入，串行执行。提高了 CPU 利用率，但 CPU 仍有等待 I/O 的时间。
   • 多道批处理系统：允许多个作业同时存放在内存中并并发执行。当一个作业等待 I/O 时，CPU 可以切换到另一个作业执行，显著提高了资源利用率。
     • 特点：宏观上并行，微观上串行。资源共享，提高了吞吐量。
     • 缺点：用户交互性差，作业周转时间长。
3. 分时操作系统：
   • 将 CPU 的运行时间划分成若干个时间片，轮流为各个联机用户服务。
   • 特点：多路性 (多个用户同时使用)、独立性 (用户互不干扰)、及时性 (快速响应)、交互性 (用户与系统进行人机对话)。
4. 实时操作系统：
   • 主要用于需要及时响应外部事件的系统，如工业控制、航空航天等。
   • 特点：高可靠性、及时响应。
   • 分类：硬实时系统 (必须在严格的规定时间内完成处理) 和软实时系统 (能接受偶尔违反时间规定)。
5. 网络操作系统：
   • 使网络中的计算机能够方便地共享资源和相互通信。
   • 特点：网络通信、资源共享、服务分布式。
6. 分布式操作系统：
   • 将多台计算机通过网络连接起来，组成一个统一的系统，对用户透明。
   • 特点：分布性、透明性、健壮性。
7. 嵌入式操作系统：
   • 运行在嵌入式设备中，通常对资源、功耗有严格限制。
   • 特点：微型化、可定制、高可靠性、实时性。
8. 个人计算机操作系统：
   • 如 Windows, macOS, Linux 桌面版，注重用户友好性和多媒体功能。
9. 移动操作系统：
   • 如 Android, iOS，针对移动设备优化，注重触摸交互、低功耗和应用生态。

操作系统运行环境

处理器运行模型

现代处理器通常具有两种或多种运行模式，以保护操作系统内核免受用户程序的干扰，并提供对硬件的受控访问。

• 内核态：
  • 操作系统内核运行在此模式下。
  • 可以执行所有机器指令，访问所有内存和硬件资源。
  • 具有最高权限。
• 用户态：
  • 用户应用程序运行在此模式下。
  • 执行的指令和访问的资源受到限制。
  • 不能直接访问硬件，不能执行特权指令（如 I/O 操作、修改时钟、清内存等）。
  • 如果用户程序需要执行特权操作，必须通过系统调用 请求操作系统内核代为执行。

模式切换：

• 用户态 -> 内核态：唯一的途径是通过中断 或 异常，其中系统调用是一种特殊的软中断。
• 内核态 -> 用户态：当内核完成服务后，通过执行一条特权指令（如 iret 或 rfe）将控制权交还给用户程序。

中断和异常的概念

中断：也称外中断，指来自 CPU 执行指令以外的事件的发生，如 I/O 完成、时钟中断、硬件故障等。中断的发生与当前执行的指令无关。

异常：也称内中断、陷入，指由 CPU 执行指令期间检测到的反常事件或错误条件，如非法指令、除零错误、地址越界、缺页等。异常的发生与当前执行的指令密切相关。

中断/异常处理流程：

1. 保护现场：保存当前被打断程序的 CPU 状态（如程序计数器 PC、程序状态字 PSW、通用寄存器等）到内存（通常是进程的内核栈）。
2. 识别中断/异常源：确定中断或异常的类型和来源。
3. 转向处理程序：根据中断/异常类型，通过中断向量表 找到对应的处理程序入口地址，并将控制权转交给该处理程序。
4. 处理中断/异常：执行相应的中断/异常服务程序。
5. 恢复现场：处理完成后，恢复之前保存的 CPU 状态，返回到被打断的程序或调度其他程序执行。

系统调用

系统调用是操作系统提供给应用程序访问操作系统内核功能和服务的接口。它是用户程序从用户态进入内核态的唯一合法途径。

为什么需要系统调用？

• 用户程序运行在用户态，权限受限，不能直接执行特权指令或访问受保护的资源。
• 系统调用提供了一种受控的机制，使得用户程序可以请求操作系统内核代为执行这些操作，保证了系统的安全性和稳定性。

系统调用的过程：

1. 传递参数：用户程序将系统调用所需的参数通过寄存器、内存栈或参数块传递给内核。
2. 执行陷入指令：用户程序执行一条特殊的陷入指令（如 INT, SYSCALL, SVC），使 CPU 从用户态切换到内核态，并将控制权交给操作系统内核中的系统调用总入口程序。
3. 内核处理：
   • 系统调用总入口程序根据用户程序传递的系统调用号，在系统调用表中查找对应的服务例程。
   • 执行相应的系统调用服务例程。
4. 返回结果：服务例程执行完毕后，将结果返回给用户程序。
5. 返回用户态：操作系统执行特权指令，使 CPU 从内核态切换回用户态，用户程序继续执行。

常见的系统调用类型：

• 进程控制：创建进程 (fork)、终止进程 (exit)、加载并执行程序 (exec)、等待进程 (wait)。
• 文件管理：创建文件 (create)、删除文件 (delete)、打开文件 (open)、关闭文件 (close)、读文件 (read)、写文件 (write)。
• 设备管理：请求设备 (request)、释放设备 (release)、读设备、写设备。
• 信息维护：获取/设置时间日期、获取/设置系统数据。
• 通信：创建/删除通信连接、发送/接收消息。

操作系统结构

操作系统的结构是指操作系统内部各模块的组织方式。常见的结构有：

1. 简单结构 (无结构或整体式结构)：
   • 早期操作系统采用，如 MS-DOS。
   • 操作系统是一组没有明确划分模块的过程集合，各过程可以相互调用。
   • 优点：简单、开销小、响应快。
   • 缺点：结构混乱、难以维护和扩展、可靠性差。
2. 模块化结构：
   • 将操作系统按功能划分为若干具有一定独立性的模块。
   • 模块间通过定义好的接口进行通信。
   • 优点：提高了设计的清晰度和可维护性。
   • 缺点：模块划分和接口设计可能复杂。
3. 层次式结构：
   • 将操作系统功能组织成一系列层次，每一层只使用其下一层提供的服务和功能。
   • 如 THE 操作系统。
   • 优点：结构清晰、易于调试和验证、易于扩充和维护。
   • 缺点：层间通信开销大，效率可能较低；难以精确定义层次。
4. 微内核结构：
   • 将操作系统核心功能（如进程调度、IPC、基本内存管理）保留在内核中，而其他功能（如文件系统、设备驱动、网络协议）作为运行在用户态的服务进程实现。
   • 服务进程之间、服务进程与客户进程之间通过 IPC 进行通信。
   • 优点：内核小而稳定、可靠性高、灵活性好、易于扩展和移植、支持分布式系统。
   • 缺点：IPC 开销较大，可能导致性能下降。
5. 外核结构：
   • 尽可能少地对硬件资源进行抽象，将硬件资源安全地复用给应用程序。应用程序可以根据需要自行管理资源。
   • 优点：应用程序有更大的控制权，可以针对特定需求进行优化。
   • 缺点：增加了应用程序开发的复杂性。
6. 虚拟机结构：
   • 见 虚拟机。

操作系统引导

引导 是计算机加电启动或重启后，将操作系统内核加载到内存并开始运行的过程。

引导过程：

1. 加电自检：
   • 计算机通电后，CPU 首先执行固化在 ROM 中的基本输入/输出系统 (BIOS) 或统一可扩展固件接口 (UEFI) 中的程序。
   • POST 程序检测 CPU、内存、显卡、键盘等基本硬件设备是否正常。
2. 加载引导加载程序：
   • POST 完成后，BIOS/UEFI 会根据预设的启动顺序（如硬盘、U 盘、光驱）查找启动设备。
   • 从启动设备的第一个扇区（主引导记录 MBR 或 GUID 分区表 GPT）读取并执行引导加载程序，如 GRUB、LILO、NTLDR。
   • Bootloader 的任务是将操作系统内核从磁盘加载到内存。对于较大的操作系统，可能会有多阶段的 Bootloader。
3. 加载操作系统内核：
   • Bootloader 找到操作系统内核文件（如 Linux 的vmlinuz，Windows 的ntoskrnl.exe），将其加载到内存的指定位置。
4. 内核初始化：
   • 控制权交给操作系统内核。
   • 内核进行一系列初始化工作：
     • 探测和初始化硬件设备。
     • 建立中断向量表。
     • 初始化内存管理机制。
     • 初始化进程管理机制，创建第一个进程（如 Linux 的init进程或systemd进程）。
5. 启动用户级服务和应用程序：
   • init进程（或类似进程）根据系统配置文件启动各种系统服务和守护进程。
   • 最后，启动用户登录界面或命令行 Shell，等待用户交互。

虚拟机

虚拟机是通过虚拟化技术创建的一个隔离的、模拟完整计算机系统的运行环境。它可以在一台物理计算机上模拟出多台逻辑上的计算机，每台虚拟机都可以运行独立的操作系统和应用程序。

虚拟化的类型：

1. 第一类虚拟机管理程序：
   • 直接运行在物理硬件之上，作为操作系统。例如：VMware ESXi, Microsoft Hyper-V (当作为服务器角色安装时), Xen, KVM (当与 Linux 内核集成时)。
   • Hypervisor 负责管理硬件资源，并为上层的虚拟机分配资源。
   • 优点：性能较高，安全性较好。
2. 第二类虚拟机管理程序：
   • 作为应用程序运行在宿主操作系统之上。例如：VMware Workstation, Oracle VirtualBox, Parallels Desktop。
   • 虚拟机通过 Hypervisor 向宿主操作系统请求资源。
   • 优点：安装简单，易于使用。
   • 缺点：性能通常低于第一类 Hypervisor，因为多了一层操作系统。

虚拟机的优点：

• 服务器整合：在一台物理服务器上运行多个虚拟机，提高硬件利用率，降低成本。
• 隔离性：每个虚拟机都是独立的，一个虚拟机的故障不会影响其他虚拟机。
• 安全性：可以用于运行不可信的软件或测试环境。
• 可移植性：虚拟机可以方便地在不同的物理主机之间迁移。
• 快速部署和灾难恢复：可以快速创建和恢复虚拟机。
• 支持多种操作系统：可以在一台物理机上同时运行不同的操作系统。

虚拟机的缺点：

• 性能开销：虚拟化层会带来一定的性能损失。
• 资源消耗：每个虚拟机都需要分配一部分物理资源。
• 复杂性：管理虚拟机环境可能比管理物理机更复杂。

进程与线程

进程与线程

进程的概念和特征

进程 是程序在一个数据集合上的一次运行活动，是操作系统进行资源分配和调度的基本单位。进程是动态的、具有生命周期的。

进程与程序的区别：

• 程序：是静态的，是一组有序的指令集合，存储在磁盘等介质上。
• 进程：是动态的，是程序的一次执行过程。一个程序可以对应多个进程。

进程的特征 (动态性、并发性、独立性、异步性、结构性)：

1. 动态性：进程是程序的一次执行，有创建、活动、暂停、终止等生命周期。程序是静态的。
2. 并发性：多个进程在一段时间内可以同时执行（宏观上并行，微观上可能串行）。这是操作系统引入进程的主要目的。
3. 独立性：进程是系统进行资源分配和调度的独立单位。每个进程拥有自己独立的地址空间和资源。
4. 异步性：进程按各自独立的、不可预知的速度向前推进。进程间的执行顺序和执行时间是不确定的。
5. 结构性：进程由程序段、数据段和进程控制块 (PCB) 组成。

进程的组成：

• 程序段：存放要执行的指令。
• 数据段：存放程序运行时使用的数据（如全局变量、静态变量）。
• 堆：动态分配的内存区域。
• 栈：存放局部变量、函数参数、返回地址等。
• 进程控制块：操作系统用于管理和控制进程的数据结构，是进程存在的唯一标志。

进程的状态与转换

进程在其生命周期中会经历不同的状态。常见的进程状态有：

1. 创建态：进程正在被创建，尚未进入就绪队列。操作系统为进程分配资源，初始化 PCB。
2. 就绪态：进程已获得除 CPU 以外的所有必要资源，一旦获得 CPU 即可立即执行。多个就绪进程排成一个队列，称为就绪队列。
3. 运行态：进程已获得 CPU，其程序正在 CPU 上执行。在单 CPU 系统中，任一时刻最多只有一个进程处于运行态。
4. 阻塞态：进程因等待某一事件（如 I/O 操作完成、等待信号、等待资源）而暂时停止执行。即使 CPU 空闲，阻塞态进程也无法执行。事件发生后，进程从阻塞态转换为就绪态。
5. 终止态：进程执行完毕或因某种原因（如出错、被其他进程终止）而结束运行。操作系统会回收进程所占有的资源。

状态转换图：

• 创建 -> 就绪：进程创建完成，资源分配基本就绪。
• 就绪 -> 运行：进程被调度程序选中，获得 CPU。
• 运行 -> 就绪：时间片用完，或出现更高优先级的进程。
• 运行 -> 阻塞：进程请求 I/O 操作，或等待某个事件。
• 阻塞 -> 就绪：等待的事件发生（如 I/O 完成）。
• 运行 -> 终止：进程正常结束或异常终止。

有些模型还会引入挂起 状态，当内存不足时，可以将某些就绪态或阻塞态的进程调出到外存，称为挂起就绪或挂起阻塞。

进程的组织方式

操作系统为了管理众多的进程，需要将进程的 PCB 组织起来。常见的组织方式有：

1. 链接方式：将同一状态的进程 PCB 通过指针链接成队列。
   • 就绪队列：所有处于就绪态的进程 PCB。
   • 阻塞队列：因不同事件阻塞的进程可能排在不同的阻塞队列中（如等待磁盘 I/O 队列、等待打印机队列等）。
2. 索引方式：建立不同状态进程的索引表，索引表的表项指向对应状态的某个 PCB。

进程控制块：也称为进程描述符。是操作系统中最重要的记录型数据结构，记录了操作系统所需的、用于描述进程的当前情况以及管理进程运行的全部信息。

PCB 包含的主要信息：

• 进程标识符：唯一的进程 ID。
• 进程状态：如就绪、运行、阻塞等。
• 程序计数器：下一条要执行指令的地址。
• CPU 寄存器：各种通用寄存器、累加器、标志寄存器等的值，用于进程切换时保存和恢复现场。
• CPU 调度信息：进程优先级、调度队列指针等。
• 内存管理信息：基址寄存器、限长寄存器、页表或段表指针等。
• 记账信息：CPU 使用时间、作业号等。
• I/O 状态信息：分配给进程的 I/O 设备、打开的文件列表等。
• 父进程指针、子进程指针等。

进程控制

进程控制是指操作系统对进程生命周期各个阶段的管理，主要通过一组称为原语 的特殊程序来实现。原语的特点是执行不可中断，保证了操作的原子性。

主要的进程控制原语：

1. 创建原语：
   • 申请空白 PCB。
   • 为新进程分配所需资源（如内存、文件等）。
   • 初始化 PCB（设置 PID、状态、PC 等）。
   • 将新进程插入就绪队列。
   • 如 fork() 或 CreateProcess()。
2. 撤销原语：
   • 从 PCB 集合中找到要撤销进程的 PCB。
   • 若进程处于运行态，立即剥夺 CPU。
   • 终止其所有子孙进程（如果需要）。
   • 归还进程拥有的所有资源给父进程或系统。
   • 释放 PCB。
   • 如 exit()。
3. 阻塞原语：
   • 当运行进程需要等待某个事件时，由其自身调用阻塞原语。
   • 保存进程现场，修改 PCB 状态为阻塞态。
   • 将 PCB 插入相应的阻塞队列。
   • 转进程调度程序，从就绪队列中选择另一个进程投入运行。
4. 唤醒原语：
   • 当被阻塞进程所等待的事件发生时，由发现该事件的进程调用唤醒原语。
   • 从阻塞队列中移出被唤醒进程的 PCB。
   • 修改 PCB 状态为就绪态。
   • 将 PCB 插入就绪队列。
5. 挂起原语：将指定进程从内存调到外存，修改状态为挂起态。
6. 激活原语：将指定挂起进程从外存调入内存，修改状态为就绪态或阻塞态（取决于挂起前的状态）。

进程的通信

进程通信是指在不同进程之间交换信息的过程。由于进程具有独立性（独立的地址空间），因此需要操作系统提供机制来实现 IPC。

常见的 IPC 机制：

1. 共享存储：
   • 多个进程共享内存中的一块区域。一个进程向共享内存写入数据，其他进程可以读取。
   • 优点：速度快，因为数据不需要在用户空间和内核空间之间复制。
   • 缺点：需要同步机制（如互斥锁、信号量）来控制对共享内存的访问，避免冲突。
2. 消息传递：
   • 进程间通过操作系统提供的发送消息 (send) 和接收消息 (receive) 两个原语进行通信。
   • 消息可以是固定长度或可变长度的。
   • 直接通信：发送进程直接将消息发送给接收进程。需要指定接收进程的 ID。
   • 间接通信 (信箱/邮箱 Mailbox)：消息发送到中间实体（信箱），接收进程从信箱中获取消息。允许多个进程向同一个信箱发送消息，或从同一个信箱接收消息。
   • 优点：实现简单，不需要复杂的同步。
   • 缺点：消息复制可能带来开销。
3. 管道：
   • 一种半双工的通信方式，数据只能单向流动。通常用于具有亲缘关系的进程之间（如父子进程）。
   • 管道是内存中的一块缓冲区，一端用于写入，另一端用于读取。
   • 匿名管道：只能用于亲缘进程，随进程结束而消失。
   • 命名管道：可以在无亲缘关系的进程间通信，以文件形式存在于文件系统中。
   • 优点：简单易用。
   • 缺点：容量有限，半双工。
4. 信号：
   • 用于通知接收进程某个异步事件已经发生。是一种比较复杂的通信方式，常用于处理错误或异常情况。
   • 如 SIGINT (中断信号), SIGKILL (杀死进程信号)。
5. 套接字：
   • 可用于同一台机器上不同进程间的通信，也可用于不同机器上进程间的网络通信。
   • 提供了一种端到端的通信机制。

线程和多线程模型

线程 是进程内的一个执行单元（或执行流），是 CPU 调度的基本单位。一个进程可以包含多个线程，这些线程共享进程的地址空间和大部分资源（如代码段、数据段、打开的文件、信号等），但每个线程拥有自己独立的：

• 线程 ID
• 程序计数器
• 寄存器集合
• 栈

引入线程的好处：

• 并发性：在一个进程内实现并发执行，提高程序响应速度和吞吐量。
• 开销小：线程的创建、终止和切换比进程快得多，因为它们共享大部分资源，不需要复制整个地址空间。
• 资源共享方便：线程间共享进程的内存空间，数据共享和通信更直接方便。
• 提高多核 CPU 利用率：多线程程序可以在多核 CPU 上并行执行。

线程的实现方式：

1. 用户级线程：
   • 线程的管理（创建、调度、同步）完全在用户空间进行，内核不知道线程的存在。
   • 线程库（如 POSIX Pthreads, Java Threads）提供支持。
   • 优点：线程切换快（不需要内核参与），实现灵活。
   • 缺点：
     • 如果一个用户级线程阻塞（如进行系统调用），整个进程都会阻塞。
     • 不能有效地利用多核 CPU（内核一次只给进程分配一个 CPU）。
2. 内核级线程：
   • 线程的管理由操作系统内核进行。内核知道每个线程的存在，并对其进行调度。
   • 优点：
     • 一个线程阻塞不会影响同进程内其他线程的执行。
     • 可以在多核 CPU 上并行执行。
   • 缺点：线程创建、切换和同步的开销比用户级线程大，因为需要内核参与。
3. 混合模型：
   • 结合了用户级线程和内核级线程的优点。
   • 内核支持多个内核级线程（LWP），用户级线程映射到 LWP 上执行。
   • 允许一个进程创建多个 LWP，每个 LWP 可以调度一个或多个用户级线程。
   • 如 Solaris 的早期线程模型。

多线程模型 (用户级线程与内核级线程的映射关系)：

• 多对一模型：多个用户级线程映射到一个内核级线程。即用户级线程的实现方式。
  • 优点：线程管理在用户空间，效率高。
  • 缺点：一个线程阻塞导致整个进程阻塞；不能利用多核。
• 一对一模型：每个用户级线程映射到一个内核级线程。即内核级线程的实现方式。
  • 优点：并发度高，可利用多核。
  • 缺点：创建一个用户线程就需要创建一个内核线程，开销大。
• 多对多模型：m 个用户级线程映射到 n 个内核级线程 (m >= n)。是上述两种模型的折中。
  • 优点：兼具两者优点，并发度和效率较高。
  • 缺点：实现复杂。

处理机调度

处理机调度是指操作系统按照某种算法从就绪队列中选择一个进程，将 CPU 的使用权分配给它的过程。

调度的概念

调度的层次：

1. 高级调度 (作业调度)：
   • 决定将哪些在外存后备队列中的作业调入内存，创建进程，并分配必要的资源。
   • 主要用于批处理系统。
   • 发生频率低。
2. 中级调度 (内存调度)：
   • 决定将内存中暂时不能运行的进程（如挂起态进程）调到外存，或将外存中具备运行条件的进程调回内存。
   • 目的是提高内存利用率和系统吞吐量。
   • 发生频率中等。
3. 低级调度 (进程调度/CPU 调度)：
   • 决定就绪队列中的哪个进程可以获得 CPU。
   • 是最基本、最重要的调度，发生频率非常高（毫秒级）。

调度的时机 (进程调度)：

• 进程正常终止或异常终止。
• 进程主动阻塞（如等待 I/O）。
• 时间片用完（对于分时系统）。
• 出现更高优先级的进程（对于可剥夺式调度）。
• 中断或异常处理完毕返回用户态时。

调度方式：

• 非剥夺式调度：一旦 CPU 分配给一个进程，该进程会一直执行下去，直到它自愿放弃 CPU（如完成、阻塞）或发生错误。
  • 优点：实现简单，开销小。
  • 缺点：不适合分时系统和实时系统，可能导致高优先级进程长时间等待。
• 剥夺式调度：允许调度程序根据某种原则（如时间片用完、更高优先级进程就绪）暂停当前正在执行的进程，将 CPU 分配给其他进程。
  • 优点：可以优先处理紧急任务，提高系统响应速度和公平性。
  • 缺点：实现复杂，调度开销大。

调度的目标

设计调度算法时通常需要考虑以下目标：

面向用户的指标：

• 周转时间：从作业提交到作业完成所花费的总时间。
  • 周转时间 = 完成时间 - 提交时间
  • 平均周转时间 = Σ(各作业周转时间) / 作业数
• 带权周转时间：周转时间与作业实际运行时间的比值。
  • 带权周转时间 = 周转时间 / 实际运行时间
  • 平均带权周转时间 = Σ(各作业带权周转时间) / 作业数
• 等待时间：进程在就绪队列中等待 CPU 的总时间。
• 响应时间：从用户提交请求到系统首次产生响应所需的时间（对于交互式系统）。

面向系统的指标：

• CPU 利用率：CPU 处于忙碌状态的时间占总时间的百分比。
  • CPU 利用率 = CPU 有效工作时间 / (CPU 有效工作时间 + CPU 空闲等待时间)
• 系统吞吐量：单位时间内系统完成的作业数量。
• 公平性：确保每个进程都能获得合理的 CPU 时间，避免饥饿现象。
• 均衡性：使系统各类资源（CPU、内存、I/O 设备）保持繁忙。

这些目标之间可能存在冲突，调度算法需要在它们之间进行权衡。

调度的实现

调度程序通常由以下几部分组成：

1. 排队器：当进程状态改变时，将其放入相应的就绪队列或阻塞队列。
2. 分派器：将 CPU 的使用权从一个进程交给另一个进程。这是实际进行上下文切换的部分。
   • 上下文切换：保存当前进程的 CPU 现场（寄存器、PC、PSW 等），加载新选定进程的 CPU 现场。
   • 切换到用户模式。
   • 跳转到新进程的 PC 所指位置开始执行。
   • 分派器必须非常快，因为它在每次进程切换时都会运行。
3. 调度器：根据选定的调度算法，从就绪队列中选择一个进程。

典型的调度算法

批处理系统常用算法：

1. 先来先服务：
   • 按作业/进程到达的先后顺序进行调度。
   • 非剥夺式。
   • 优点：公平，实现简单。
   • 缺点：平均等待时间可能较长，对短作业不利（可能导致短作业等待长作业）。不利于 I/O 密集型进程。
2. 短作业优先：
   • 选择估计运行时间最短的作业/进程投入运行。
   • 可以是非剥夺式 或 剥夺式 (最短剩余时间优先)。
   • 优点：平均等待时间和平均周转时间最短（理论上）。
   • 缺点：
     • 难以准确估计作业的运行时间。
     • 对长作业不利，可能导致饥饿现象。
3. 最高响应比优先：
   • 为每个作业计算响应比，选择响应比最高的作业投入运行。
   • 响应比 = (等待时间 + 要求服务时间) / 要求服务时间 = 1 + 等待时间 / 要求服务时间
   • 非剥夺式。
   • 优点：综合了 FCFS 和 SJF 的优点，既照顾了短作业，又不会使长作业长时间等待（等待时间越长，响应比越高）。
   • 缺点：需要计算响应比，增加了系统开销。

交互式系统常用算法 (分时系统)：

1. 时间片轮转：
   • 将所有就绪进程按 FCFS 原则排成一个队列，每次调度时，把 CPU 分配给队首进程，让其执行一个时间片。
   • 时间片用完后，若进程未完成，则将其移到就绪队列末尾。
   • 剥夺式。
   • 优点：公平，响应及时，适用于分时系统。
   • 缺点：时间片大小的选择很重要。
     • 时间片过小：进程切换频繁，系统开销大。
     • 时间片过大：退化为 FCFS，响应时间变长。
2. 优先级调度：
   • 为每个进程分配一个优先级，总是选择优先级最高的就绪进程投入运行。
   • 可以是非剥夺式或剥夺式。
   • 优先级可以静态确定（创建时指定，运行期间不变）或动态确定（根据进程行为调整）。
   • 优点：能满足紧迫任务的需求。
   • 缺点：可能导致低优先级进程饥饿。
     • 解决方法：老化技术，即等待时间越长，优先级越高。
3. 多级队列调度：
   • 将就绪队列划分为多个独立的队列，每个队列有自己的优先级和调度算法（如前台交互队列用 RR，后台批处理队列用 FCFS）。
   • 进程被固定分配到某个队列。
   • 队列间的调度通常采用固定优先级剥夺式。
   • 优点：可以针对不同类型的进程采用不同的调度策略。
   • 缺点：不够灵活，进程不能在队列间移动。
4. 多级反馈队列调度：
   • 允许多个就绪队列，进程可以在队列之间移动。
   • 新进程进入最高优先级队列，按 FCFS 分配一个较小的时间片。
   • 若时间片用完未完成，则移到下一级优先级较低的队列，分配更长的时间片。
   • 最低级队列通常采用 FCFS。
   • 可以有效防止饥饿，并兼顾周转时间和响应时间。
   • 优点：比较综合，能满足各种类型进程的需求。
   • 缺点：实现复杂，参数（队列数量、各级队列调度算法、时间片大小、升级降级策略）设置困难。

实时系统常用算法：

• 最早截止时间优先：根据任务的截止时间确定优先级，截止时间越早，优先级越高。可以是剥夺式。
• 最低松弛度优先：根据任务的松弛度确定优先级，松弛度 = 截止时间 - 剩余执行时间 - 当前时间，松弛度越小，优先级越高。

同步与互斥

在多道程序环境下，多个进程并发执行，它们之间可能存在资源共享和协作关系。

同步与互斥的基本概念

• 临界资源：一次只允许一个进程访问的资源。如打印机、共享变量、共享数据结构。
• 临界区：进程中访问临界资源的那段代码。
• 互斥：当一个进程在临界区访问临界资源时，其他试图访问该临界资源的进程必须等待，直到当前进程退出临界区。这是保证数据一致性的必要条件。
• 同步：多个相关进程在执行次序上的协调。一个进程的执行依赖于另一个进程的消息或信号。例如，进程 A 产生数据，进程 B 处理数据，B 必须在 A 产生数据后才能处理。

实现临界区互斥的四个准则：

1. 空闲则入：如果没有进程在临界区，并且有进程想进入临界区，那么应允许一个想进入的进程进入。
2. 忙则等待：当一个进程在临界区时，其他试图进入临界区的进程必须等待。
3. 有限等待：任何一个想进入临界区的进程，不应无限期地等待。
4. 让权等待：当进程不能进入临界区时，应立即释放 CPU，避免忙等待。

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

软件实现方法：

1. 单标志法：
   • 设置一个公共布尔变量turn，表示允许哪个进程进入临界区。
   • turn=0允许 P0 进入，turn=1允许 P1 进入。
   • 进程在进入临界区前检查turn，若不是自己的回合则等待。退出后将turn设置为对方。
   • 缺点：必须交替进入，如果一个进程不再需要进入，另一个进程也无法进入。违反“空闲则入”。
2. 双标志先检查法：
   • 设置两个布尔数组flag[i]，flag[i]=true表示 Pi 想进入。
   • Pi 想进入时，先检查flag[j]是否为true，若false则 Pi 进入，并设置flag[i]=true。
   • 缺点：可能同时进入临界区。违反“忙则等待”。
3. 双标志后检查法：
   • Pi 想进入时，先设置flag[i]=true，然后检查flag[j]。若flag[j]为true则等待。
   • 缺点：可能都设置flag为true后互相等待，导致“饥饿”或“死锁”。违反“空闲则入”和“有限等待”。
4. Peterson 算法：结合了双标志法和单标志法。
   • 使用flag[i]表示 Pi 想进入，turn表示谦让。
   • Pi 想进入：flag[i]=true; turn=j; while(flag[j] && turn==j);
   • Pi 退出：flag[i]=false;
   • 优点：遵循了互斥的三个准则（空闲则入、忙则等待、有限等待）。
   • 缺点：仍然存在忙等待，不符合“让权等待”。只适用于两个进程。

硬件实现方法：利用特殊的硬件指令，这些指令的执行是原子的（不可中断）。

1. 中断屏蔽：
   • 在进入临界区前关中断，退出临界区后开中断。
   • 优点：简单有效。
   • 缺点：
     • 关中断时间过长会影响系统效率，甚至丢失中断。
     • 只适用于单 CPU 系统。在多 CPU 系统中，关一个 CPU 的中断不能阻止其他 CPU 上的进程访问临界区。
     • 滥用可能导致危险。
2. 测试并设置指令：
   • TSL R, lock：原子地读取lock到寄存器R，并将lock设置为true。
   • 使用一个共享布尔变量lock (初始为false)。
   • 进入临界区：while(TSL(lock));
   • 退出临界区：lock = false;
   • 优点：实现简单，适用于多 CPU。
   • 缺点：存在忙等待。可能导致饥饿（无法保证等待时间有限）。
3. 交换指令：
   • Swap(a, b)：原子地交换变量a和b的内容。
   • 使用共享布尔变量lock (初始为false) 和每个进程的局部布尔变量key。
   • 进入临界区：key = true; do { Swap(key, lock); } while(key == true);
   • 退出临界区：lock = false;
   • 优点：实现相对简单。
   • 缺点：存在忙等待。可能导致饥饿。

硬件方法通常作为实现更高级同步机制（如信号量、互斥锁）的基础。

互斥锁

互斥锁是一种简单的同步原语，用于保护临界区，确保一次只有一个线程可以访问共享资源。

• 一个共享的布尔变量 available，表示锁是否可用。
• 两个原子操作：
  • acquire() (或 lock(), P操作)：

    while (!available); // 忙等待，直到锁可用
    available = false;  // 获取锁

    或者，为了避免忙等待，可以改为：

    if (!available) {
        // 将当前线程加入等待队列并阻塞
    } else {
        available = false;
    }

  • release() (或 unlock(), V操作)：

    available = true; // 释放锁
    // 如果有等待线程，则唤醒一个

• 使用：在进入临界区前调用acquire()，退出临界区后调用release()。

特点：

• 简单有效。
• 通常用于线程间的互斥。
• 可能会导致忙等待（自旋锁）或线程阻塞。
• 需要正确配对使用acquire和release，否则可能导致死锁或数据不一致。

信号量

信号量是由 Dijkstra 提出的更通用的同步机制。它是一个整数变量 S，只能通过两个标准的原子操作来访问：P操作 (wait/down) 和 V操作 (signal/up)。

• P(S)：

  S--;
  if (S < 0) {
      // 当前进程/线程阻塞，并加入等待队列 Ls
  }

• V(S)：

  S++;
  if (S <= 0) {
      // 从等待队列 Ls 中唤醒一个进程/线程
  }

信号量的类型：

1. 整型信号量：
   • S是一个整数。P操作忙等待，V操作简单增减。
   • 缺点：存在忙等待，不符合“让权等待”。
2. 记录型信号量：
   • S是一个记录型数据结构，包含一个整型值 value (资源计数) 和一个进程等待队列 L。
   • P(S):

     S.value--;
     if (S.value < 0) {
         block(current_process); // 阻塞当前进程
         add_to_queue(current_process, S.L);
     }

   • V(S):

     S.value++;
     if (S.value <= 0) {
         process p = remove_from_queue(S.L);
         wakeup(p); // 唤醒等待队列中的一个进程
     }

   • 优点：遵循“让权等待”。
3. 二进制信号量：
   • S的值只能取 0 或 1。相当于互斥锁。
   • 初始值为 1。用于实现互斥。
4. 计数信号量：
   • S的值可以取任意非负整数。
   • 初始值表示可用资源的数量。用于表示某类资源的可用数量。

使用信号量实现互斥： 定义一个二进制信号量 mutex，初始值为 1。

P(mutex);    // 进入临界区前
// --- 临界区 ---
V(mutex);    // 退出临界区后

使用信号量实现同步： 例如，进程 P1 需要在进程 P2 执行某个操作之后才能继续。 定义一个信号量 sync，初始值为 0。 进程 P1:

// ...
P(sync);     // 等待P2的信号
// P1的后续操作
// ...

进程 P2:

// ...
// P2的某个操作完成
V(sync);     // 向P1发信号
// ...

管程

管程是一种高级的同步机制，由 Hoare 提出，旨在简化并发编程，避免直接使用信号量可能导致的错误。它是一个包含共享数据结构以及对这些数据结构进行操作的一组过程的软件模块。

管程的特性：

1. 数据封装：共享数据结构只能通过管程内定义的过程来访问。
2. 互斥进入：任何时候最多只有一个进程/线程能在管程内执行其过程。这是由编译器保证的，程序员无需显式实现互斥。
3. 条件变量：当一个进程在管程内因某个条件不满足而无法继续执行时，它可以在一个条件变量上等待。
   • 条件变量不是普通的变量，它是一个等待队列。
   • 提供两个操作：
     • c.wait()：调用此操作的进程阻塞，并释放对管程的互斥访问权，加入条件变量 c 的等待队列。
     • c.signal()：如果条件变量 c 的等待队列不为空，则唤醒其中一个等待的进程。如果没有进程在等待，则signal操作无效（与信号量的 V 操作不同）。

c.signal()的语义：

• Hoare 管程：signal后，被唤醒的进程立即执行，发出signal的进程阻塞等待。实现复杂。
• Mesa 管程 (常用)：signal后，被唤醒的进程进入就绪队列，发出signal的进程继续执行。被唤醒的进程需要重新检查条件是否满足（因为在它被唤醒到它实际运行之间，条件可能又改变了）。通常与while循环配合使用：while (!condition) c.wait();

管程的优点：

• 将同步和互斥操作封装在管程内部，降低了并发编程的复杂性。
• 比信号量更容易保证正确性。

管程的缺点：

• 编译器需要支持管程机制。
• 不是所有系统都提供原生的管程支持（Java 中的synchronized和wait/notify/notifyAll提供了类似管程的功能）。

经典同步问题

使用信号量或管程可以解决许多经典的进程同步问题。

1. 生产者-消费者问题：

   • 一组生产者进程生产数据放入缓冲区，一组消费者进程从缓冲区取出数据消费。

   • 缓冲区大小有限。

   • 需要解决的同步互斥问题：

     • 对缓冲区的访问是互斥的。
     • 当缓冲区满时，生产者必须等待。
     • 当缓冲区空时，消费者必须等待。

   • 信号量解决方案：

     • mutex: 二进制信号量，用于互斥访问缓冲区，初始为 1。
     • empty: 计数信号量，表示缓冲区中空闲单元的数量，初始为 n (缓冲区大小)。
     • full: 计数信号量，表示缓冲区中已占用单元的数量，初始为 0。

     // Producer
     while (true) {
         produce_item(item);
         P(empty);       // 等待空位
         P(mutex);       // 进入临界区
         add_item_to_buffer(item);
         V(mutex);       // 退出临界区
         V(full);        // 通知有产品
     }
     
     // Consumer
     while (true) {
         P(full);        // 等待产品
         P(mutex);       // 进入临界区
         remove_item_from_buffer(item);
         V(mutex);       // 退出临界区
         V(empty);       // 通知有空位
         consume_item(item);
     }

2. 读者-写者问题：

   • 多个进程共享一个数据对象。

   • 读者：只读取数据，不修改。

   • 写者：读取和修改数据。

   • 约束条件：

     • 允许多个读者同时读取。
     • 写者必须互斥地访问（即不能有其他读者或写者）。
     • 当有写者正在写时，其他读者和写者都不能访问。

   • 变种：

     • 读者优先：只要有读者想读，写者就必须等待。可能导致写者饥饿。
     • 写者优先：一旦有写者想写，后续的读者必须等待，直到没有写者。可能导致读者饥饿。
     • 公平方案：兼顾读者和写者。

   • 读者优先信号量解决方案：

     • rw_mutex: 二进制信号量，用于写者互斥或第一个/最后一个读者进入/退出时修改read_count的互斥，初始为 1。
     • mutex: 二进制信号量，用于对read_count的互斥访问，初始为 1。
     • read_count: 整型变量，记录当前正在读的读者数量，初始为 0。

     // Writer
     P(rw_mutex);    // 互斥写
     // ... writing ...
     V(rw_mutex);
     
     // Reader
     P(mutex);       // 互斥访问 read_count
     read_count++;
     if (read_count == 1) {
         P(rw_mutex); // 第一个读者，阻止写者
     }
     V(mutex);
     
     // ... reading ...
     
     P(mutex);       // 互斥访问 read_count
     read_count--;
     if (read_count == 0) {
         V(rw_mutex); // 最后一个读者，允许写者
     }
     V(mutex);

3. 哲学家进餐问题：

   • 五个哲学家围坐在一张圆桌旁，每人面前一盘通心粉，每两个哲学家之间放一只筷子。

   • 哲学家交替思考和进餐。进餐需要同时拿起左右两边的筷子。

   • 问题：如何设计一个无死锁、无饥饿的方案。

   • 简单方案可能导致的问题：如果所有哲学家同时拿起左手边的筷子，则都无法拿起右手边的筷子，导致死锁。

   • 解决方案：

     • 限制同时进餐人数：最多允许四个哲学家同时尝试拿筷子。
     • 奇偶编号：奇数号哲学家先拿左筷再拿右筷，偶数号哲学家先拿右筷再拿左筷。
     • 仅当左右筷子都可用时才拿起：使用一个互斥信号量保护拿两只筷子的操作。

   • 信号量解决方案 (避免死锁的一种)：

     • chopstick[5]: 信号量数组，每个元素代表一只筷子，初始都为 1。
     • mutex: 二进制信号量，用于保护取筷子的原子性，初始为 1。

     // Philosopher i
     while (true) {
         think();
     
         P(mutex); // 尝试拿起两只筷子前加锁
         P(chopstick[i]);             // 拿起左筷
         P(chopstick[(i + 1) % 5]); // 拿起右筷
         V(mutex); // 释放锁
     
         eat();
     
         V(chopstick[i]);             // 放下左筷
         V(chopstick[(i + 1) % 5]); // 放下右筷
     }

     注：上述哲学家进餐的信号量解法仍可能死锁。更完善的解法需要更复杂的逻辑，例如引入一个服务员，或者使用管程。

死锁

死锁是指两个或多个进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。

死锁的概念

死锁产生的必要条件：以下四个条件必须同时满足才会发生死锁。

1. 互斥条件：资源是临界资源，任一时刻只能被一个进程使用。
2. 请求与保持条件：进程已至少保持一个资源，但又提出了新的资源请求，而该资源已被其他进程占用，此时请求进程阻塞，但对自己已获得的资源保持不放。
3. 不可剥夺条件：进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
4. 循环等待条件：存在一个进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。即 P0 等待 P1 的资源，P1 等待 P2 的资源，…，Pn 等待 P0 的资源。

资源分配图：用于描述资源和进程之间的分配和请求关系。

• 圆圈代表进程，方框代表资源类型。
• 方框中的点代表该类型资源的实例数量。
• 从进程到资源的有向边 (请求边 P -> R)：表示进程 P 请求一个 R 类型的资源。
• 从资源实例到进程的有向边 (分配边 R -> P)：表示一个 R 类型的资源实例已分配给进程 P。
• 如果图中出现环路，则可能存在死锁。
  • 如果每种资源类型只有一个实例，则环路是死锁的充要条件。
  • 如果每种资源类型有多个实例，则环路是死锁的必要不充分条件。

死锁预防

通过破坏死锁产生的四个必要条件之一或多个，来防止死锁的发生。

1. 破坏互斥条件：
   • 将某些临界资源改造为可共享资源（如 SPOOLing 技术将独占打印机改造为共享设备）。
   • 缺点：并非所有资源都可以改造，且有些资源本质上是互斥的。实用性不高。
2. 破坏请求与保持条件：
   • 一次性分配策略：进程在运行前一次性申请它所需要的所有资源，若不能满足则不投入运行。
   • 缺点：资源浪费严重（很多资源可能只在后期使用），可能导致进程饥饿（某些资源需求大的进程可能一直无法满足）。
3. 破坏不可剥夺条件：
   • 当一个已保持了某些资源的进程去申请新资源而得不到满足时，它必须释放已经保持的所有资源。
   • 或者，允许操作系统剥夺某个进程已占有的资源，分配给更高优先级的进程。
   • 缺点：实现复杂，可能导致前段工作的失效，反复申请和释放资源会增加系统开销。
4. 破坏循环等待条件：
   • 资源有序分配法：将所有资源类型进行线性排序，规定每个进程必须按序号递增的顺序申请资源。
   • 优点：实现相对简单，资源利用率较好。
   • 缺点：限制了新类型设备的增加；对用户编程不方便；可能不必要地限制了资源分配。

死锁预防通常会降低系统并发性和资源利用率。

死锁避免

在资源分配过程中，使用某种算法（如银行家算法）来判断本次分配是否会导致系统进入不安全状态，如果会，则不予分配，让进程等待。目的是确保系统永远处于安全状态。

• 安全状态：系统能按某种进程推进顺序 (安全序列 P1, P2, …, Pn) 为每个进程分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可以顺利完成。如果找不到这样的安全序列，则系统处于不安全状态。
• 不安全状态：不一定会发生死锁，但系统无法保证能按某种顺序为所有进程分配资源使其完成。死锁是不安全状态的一个特例。

银行家算法：Dijkstra 提出的，是最著名的死锁避免算法。适用于每类资源有多个实例的情况。

数据结构：

• Available[m]：长度为 m 的向量，表示每种资源当前可用的实例数。
• Max[n][m]：n x m 矩阵，表示 n 个进程对 m 种资源的最大需求量。
• Allocation[n][m]：n x m 矩阵，表示 n 个进程当前已分配到的 m 种资源的实例数。
• Need[n][m]：n x m 矩阵，表示 n 个进程还需要的 m 种资源的实例数。Need[i][j] = Max[i][j] - Allocation[i][j]。

安全性算法：用于检测系统当前是否处于安全状态。

1. 初始化工作向量 Work = Available，布尔向量 Finish[n] (初始均为false)。
2. 查找是否存在一个进程 Pi 满足：
   • Finish[i] == false
   • Need[i] <= Work (向量比较，每个分量都满足) 如果找不到这样的 Pi，则转步骤 4。
3. 假设 Pi 获得资源并执行完毕释放资源：
   • Work = Work + Allocation[i]
   • Finish[i] = true
   • 返回步骤 2。
4. 如果所有 Finish[i] 都为 true，则系统处于安全状态，否则为不安全状态。

资源请求算法：当进程 Pi 请求资源向量 Request_i 时：

1. 如果 Request_i <= Need[i]，则转步骤 2；否则出错（请求超过最大需求）。
2. 如果 Request_i <= Available，则转步骤 3；否则 Pi 等待（资源不足）。
3. 系统试探性地把资源分配给 Pi：
   • Available = Available - Request_i
   • Allocation[i] = Allocation[i] + Request_i
   • Need[i] = Need[i] - Request_i
4. 执行安全性算法。
   • 如果结果是安全状态，则正式分配资源给 Pi。
   • 如果结果是不安全状态，则撤销本次试探性分配，让 Pi 等待。

银行家算法的优缺点：

• 优点：可以避免死锁，允许比死锁预防更高的并发度。
• 缺点：
  • 需要预先知道进程对各种资源的最大需求量，这在实际中很难。
  • 进程数目和资源种类是固定的。
  • 计算开销大，每次请求都需要执行安全性算法。

死锁检测和解除

如果系统不采用死锁预防或避免措施，则可能发生死锁。需要通过检测机制及时发现死锁，并通过解除措施恢复系统。

死锁检测：

• 检测时机：可以定时检测，也可以在 CPU 利用率下降到某个阈值时检测。
• 检测算法：
  • 类似于银行家算法中的安全性算法。
  • 维护 Available, Allocation, Request (当前请求) 矩阵。
  • 初始化 Work = Available, Finish[n] (对未阻塞的进程设为true，阻塞的设为false)。
  • 查找是否存在一个进程 Pi 满足：
    • Finish[i] == false
    • Request[i] <= Work
  • 如果找到，则 Work = Work + Allocation[i], Finish[i] = true，重复。
  • 如果最后存在 Finish[i] == false 的进程，则这些进程处于死锁状态。

死锁解除：

1. 剥夺资源：
   • 从一个或多个死锁进程中剥夺足够数量的资源分配给其他死锁进程，以解除死锁。
   • 需要考虑的问题：
     • 选择哪个进程被剥夺（代价最小原则：如优先级、已执行时间、已占用资源等）。
     • 如何处理被剥夺资源的进程（通常是回滚到之前的某个安全点）。
2. 终止进程：
   • 终止所有死锁进程：简单粗暴，但代价大。
   • 逐个终止死锁进程：按某种顺序（如优先级、已执行时间）逐个终止，直到死锁解除。每次终止后都要重新检测死锁。代价相对较小。
3. 进程回滚：
   • 将一个或多个死锁进程回滚到足以避免死锁的某个检查点。
   • 需要系统记录进程的历史信息和设置检查点。开销较大。

内存管理

内存是计算机系统中重要的稀缺资源，内存管理的主要目标是提高内存的利用率，方便用户使用内存，并支持多道程序并发执行。

内存管理概念

内存管理的基本原理和要求

内存管理的功能：

1. 内存分配与回收：为进程分配内存空间，并在进程结束时回收其占用的空间。
2. 地址映射：将程序中的逻辑地址转换为内存中的物理地址。
3. 内存保护：确保每个进程在自己的内存空间内运行，互不干扰。防止一个进程访问其他进程或操作系统的内存区域。
4. 内存扩充：通过虚拟内存等技术，在逻辑上为用户提供比物理内存更大的存储空间。

地址空间：

• 逻辑地址：CPU 生成的地址，是程序中使用的地址。逻辑地址空间是程序所有逻辑地址的集合。
• 物理地址：内存单元的实际地址，是加载到内存地址寄存器中的地址。物理地址空间是所有物理地址的集合。

地址重定位：将逻辑地址转换为物理地址的过程。

• 静态重定位：在程序装入内存时一次性完成地址转换。程序一旦装入内存，其物理地址就固定不变。
  • 优点：简单，无需硬件支持。
  • 缺点：程序在内存中不能移动；难以实现内存共享。
• 动态重定位：在程序执行过程中，访问内存指令时才进行地址转换。需要硬件支持（如内存管理单元 MMU）。
  • 优点：程序在内存中可以移动；方便实现内存共享。
  • 缺点：需要硬件支持，增加了系统复杂性。

内存保护机制：

• 界限寄存器：
  • 基址寄存器：存放进程在内存中的起始物理地址。
  • 限长寄存器：存放进程的长度。
  • CPU 生成的逻辑地址 addr 必须满足 0 <= addr < Limit Register。
  • 物理地址 = 基址寄存器 + 逻辑地址。
  • 每次内存访问都会检查地址是否越界。越界则产生异常（陷入）。
• 特权指令：修改界限寄存器的指令是特权指令，只能在内核态执行。

覆盖与交换

这两种技术用于在物理内存不足以容纳整个程序时，使程序能够运行。

覆盖技术：

• 主要用于早期的操作系统，由程序员手动实现。
• 将程序划分为若干功能上相对独立的模块（覆盖段）。
• 不常用的模块不常驻内存，只在需要时调入内存，覆盖掉不再需要的模块。
• 优点：可以在较小的内存空间运行较大的程序。
• 缺点：
  • 需要程序员明确划分模块和覆盖关系，编程复杂。
  • 覆盖结构对程序设计有很大限制。
  • 增加了程序执行时间。

交换技术：

• 由操作系统自动实现。
• 将内存中暂时不能运行的整个进程（或部分）调出到外存的交换区，待需要时再调回内存。
• 用于中级调度，以提高内存利用率和系统并发度。
• 优点：
  • 增加了系统的并发进程数量。
  • 对用户透明。
• 缺点：
  • 交换操作涉及大量的磁盘 I/O，开销大，影响系统性能。
  • 交换单位是整个进程，粒度较大。

连续分配管理方式

指为一个用户程序分配一个连续的内存空间。

1. 单一连续分配：
   • 内存分为系统区和用户区。用户区只装入一道用户程序。
   • 优点：简单，无外部碎片。
   • 缺点：只能用于单用户单任务系统；存在内部碎片（如果程序小于用户区大小）。
2. 固定分区分配：
   • 将用户内存空间划分为若干个固定大小的分区。每个分区装入一道作业。
   • 分区大小相等：简单，但缺乏灵活性。
   • 分区大小不等：可以满足不同大小作业的需求。
   • 当作业到来时，选择一个能容纳它且尚未分配的分区。
   • 优点：实现简单，可用于多道程序系统。
   • 缺点：
     • 内部碎片：分配给作业的分区可能大于作业实际需求，多余部分无法利用。
     • 分区总数固定，限制了并发执行的作业数量。
3. 动态分区分配：
   • 不预先划分分区，在作业装入时，根据作业的实际需求动态地从可用内存中划分一块连续空间。
   • 优点：没有内部碎片（理论上，如果按需分配）。
   • 缺点：
     • 外部碎片：随着内存分配和回收，会产生许多不连续的小空闲区，这些空闲区总和可能很大，但无法满足较大作业的需求。
     • 需要复杂的分配算法和空闲区管理。

动态分区分配算法 (如何从空闲分区链/表中选择一个分区)：

• 首次适应算法：从空闲分区链首开始查找，选择第一个能满足大小要求的空闲分区。
  • 优点：算法开销小，倾向于保留高地址的大空闲区。
  • 缺点：低地址部分不断被划分，产生较多小碎片。
• 最佳适应算法：遍历整个空闲分区链，选择能满足要求且大小最小的空闲分区。
  • 优点：能最好地满足当前请求，尽量保留大块空闲区。
  • 缺点：算法开销大；容易产生许多难以利用的非常小的碎片。
• 最坏适应算法：遍历整个空闲分区链，选择能满足要求且最大的空闲分区，从中分割一部分给作业，剩余部分作为新的空闲分区。
  • 优点：减少小碎片的产生，剩余的空闲区较大。
  • 缺点：算法开销大；如果大空闲区被分割后，剩余部分不足以容纳大作业，则大作业难以分配。
• 下次适应算法：从上次查找结束的位置开始查找（而不是每次都从头开始），选择第一个能满足大小要求的空闲分区。
  • 优点：算法开销介于首次适应和最佳/最坏适应之间；空闲区分布更均匀。
  • 缺点：可能导致高地址的大空闲区也被分割。

碎片整理： 为了解决外部碎片问题，可以将内存中的所有作业移动到一端，使所有小空闲区合并成一个大空闲区。

• 优点：可以利用外部碎片。
• 缺点：开销大，需要动态重定位支持，且在整理期间系统性能会下降。

基本分页存储管理

将用户程序的逻辑地址空间和内存的物理地址空间都划分为大小相同的、固定大小的块。

• 逻辑地址空间中的块称为 页。
• 物理地址空间中的块称为 页框 或 物理块。
• 页和页框的大小通常是 2 的幂（如 4KB, 8KB）。

原理：

• 进程的逻辑地址空间被划分为若干页，这些页可以离散地存放在内存中不相邻的页框中。
• 操作系统为每个进程维护一个页表，记录逻辑页号到物理页框号的映射关系。
• 页表通常存放在内存中。

地址结构： 逻辑地址分为两部分：页号 和 页内偏移量。 物理地址分为两部分：页框号 和 页内偏移量。 页内偏移量在逻辑地址和物理地址中是相同的。

地址转换过程：

1. CPU 生成逻辑地址 (P, W)。
2. 用页号 P 查询进程的页表，找到对应的物理页框号 F。
   • 页表的起始地址通常存放在页表基址寄存器 中。
   • 页表项地址 = PTBR + P * 页表项大小。
3. 如果 F 有效（即该页在内存中），则物理地址 = F * 页框大小 + W。
4. 访问物理地址。

页表项 至少包含：

• 物理页框号。
• 有效位/存在位：指示该页是否在内存中。
• 其他控制位：保护位 (读/写/执行权限)、修改位、访问位等。

基本分页的优缺点：

• 优点：
  • 没有外部碎片（因为页框大小固定，任何空闲页框都可以分配）。
  • 内存利用率较高。
  • 易于实现内存共享（多个进程的页表项指向同一个物理页框）。
• 缺点：
  • 内部碎片：进程最后一页通常不会占满整个页框，导致页框内有部分空间浪费。
  • 页表开销：每个进程都需要一个页表，页表本身占用内存空间。如果逻辑地址空间很大，页表也会很大。
  • 两次内存访问：第一次访问页表，第二次访问实际数据。可以通过快表 来加速。

快表： TLB 是一个小型的、高速的相联存储器，用于缓存最近使用过的页表项。

• 当 CPU 生成逻辑地址时，首先并行查找 TLB。
• TLB 命中：如果页号在 TLB 中找到，直接获取物理页框号，无需访问内存中的页表。
• TLB 未命中：如果页号不在 TLB 中，则需要访问内存中的页表，获取页表项，并将其存入 TLB (可能会替换掉一个旧的条目)，然后进行地址转换。

基本分段式存储管理

从用户的角度出发，将程序的逻辑地址空间划分为若干个逻辑意义上独立的段，如代码段、数据段、堆栈段等。

• 每个段有自己的名字（或段号）和长度。
• 段的长度可以不同。
• 段的划分由用户或编译器决定。

原理：

• 进程的逻辑地址空间由多个段组成，这些段可以离散地存放在内存中不相邻的区域。
• 操作系统为每个进程维护一个段表，记录段号到段在内存中起始地址和长度的映射关系。
• 段表通常存放在内存中。

地址结构： 逻辑地址分为两部分：段号 和 段内偏移量。

地址转换过程：

1. CPU 生成逻辑地址 (S, W)。
2. 用段号 S 查询进程的段表，找到对应的段基址 (Base) 和段长 (Limit)。
   • 段表的起始地址通常存放在段表基址寄存器 中。
   • 段表项地址 = STBR + S * 段表项大小。
3. 检查段内偏移量是否越界：0 <= W < Limit。如果越界，产生异常。
4. 如果有效，则物理地址 = Base + W。
5. 访问物理地址。

段表项 至少包含：

• 段基址：该段在内存中的起始物理地址。
• 段长：该段的长度。
• 其他控制位：保护位、有效位等。

基本分段的优缺点：

• 优点：
  • 方便编程，用户可以按逻辑结构组织程序。
  • 易于实现分段共享（多个进程的段表项指向同一个物理段）和分段保护（对不同段设置不同权限）。
  • 段的长度可变，按需分配，没有内部碎片。
• 缺点：
  • 外部碎片：由于段长度可变，内存分配和回收后会产生外部碎片。
  • 段表开销。
  • 两次内存访问（可通过 TLB 优化）。

分页与分段的比较：

特性	分页	分段
划分单位	页，物理单位，大小固定	段，逻辑单位，大小可变
用户可见性	对用户透明	对用户可见（程序员需感知段的存在）
地址空间	一维逻辑地址空间	二维逻辑地址空间 (段号, 段内偏移)
碎片	内部碎片	外部碎片
共享	页共享（实现复杂，粒度小）	段共享（实现简单，粒度合适）
保护	以页为单位进行保护	以段为单位进行保护（更符合逻辑）
目的	提高内存利用率，克服物理内存限制	满足用户按逻辑模块化组织程序的需求

段页式管理

结合了分段和分页的优点，先将程序按逻辑结构分段，再将每个段划分为固定大小的页。

原理：

• 每个进程有一个段表，段表项指向该段的页表。
• 每个段有自己的页表。
• 内存被划分为页框。

地址结构： 逻辑地址分为三部分：段号、段内页号、页内偏移量。

地址转换过程：

1. CPU 生成逻辑地址 (S, P, W)。
2. 用段号 S 查询进程的段表，找到该段的页表基址和段长。
   • 检查段号是否越界。
3. 用段内页号 P 查询该段的页表，找到对应的物理页框号 F。
   • 检查页号是否越界（相对于段长）。
4. 如果有效，则物理地址 = F * 页框大小 + W。
5. 访问物理地址。

段页式的优缺点：

• 优点：
  • 兼具分段和分页的优点：按逻辑分段，按物理分页。
  • 易于实现共享和保护。
  • 没有外部碎片，内部碎片仅限于每段的最后一页。
• 缺点：
  • 系统开销大：需要段表和页表，多次内存访问（通常至少三次，可通过 TLB 优化）。
  • 硬件实现复杂。

虚拟内存管理

虚拟内存是一种内存管理技术，它允许程序使用比物理内存更大的逻辑地址空间。它将程序的逻辑地址空间与物理内存分离开来，使得程序认为自己拥有一个大的、连续的地址空间（虚拟地址空间），而实际上只有程序当前需要运行的部分被加载到物理内存中。

虚拟内存的基本概念

目标：

• 在有限的物理内存中运行更大的程序。
• 提高内存利用率和 CPU 吞吐量（允许多个程序并发执行）。
• 简化程序员的内存管理工作。

实现基础：

• 局部性原理：程序在执行时，倾向于在一段时间内集中访问某个局部的存储区域。
  • 时间局部性：如果一个存储单元被访问，那么它在不久的将来很可能再次被访问。
  • 空间局部性：如果一个存储单元被访问，那么它附近的存储单元在不久的将来也很可能被访问。
• 基于分页或分段（或段页式）的离散分配技术。

特征：

1. 离散性：程序的部分内容可以离散地存放在物理内存中。
2. 多次性：程序无需一次性全部调入内存，可以在执行过程中分多次调入。
3. 对换性：允许将内存中暂时不用的部分调出到外存，需要时再调回。
4. 虚拟性：从逻辑上扩充了内存容量，用户看到的虚拟地址空间可以远大于实际物理内存。

请求分页管理方式

是实现虚拟内存最常用的方法。

原理：

• 当进程需要访问某个页时，才将该页从外存调入内存。如果该页已在内存中，则直接访问。
• 需要硬件支持：
  • 页表：除了物理页框号，还需要一些额外的控制位。
  • 缺页中断机构。
  • 地址转换机构。

页表项在请求分页中的扩展：

• 有效位/存在位：
  • 1: 表示该页在内存中，页表项中的物理页框号有效。
  • 0: 表示该页不在内存中（可能在外存，也可能从未被访问过）。访问该页会产生缺页中断。
• 访问位：记录该页在一段时间内是否被访问过。用于页面置换算法。由硬件在访问时自动置 1。
• 修改位：记录该页调入内存后是否被修改过。如果被修改过，则在换出时需要写回外存；否则无需写回（如果外存中已有副本）。由硬件在写入时自动置 1。
• 保护位：读/写/执行权限。
• 外存地址：如果页不在内存中，该字段指向页在外存（如交换区）的位置。

缺页中断处理过程：

1. CPU 执行指令，访问逻辑地址，通过 MMU 进行地址转换。
2. MMU 查找页表，发现对应页表项的有效位为 0，产生缺页中断。
3. CPU 响应中断，操作系统接管控制权。
4. 保护现场：保存当前进程的 CPU 状态。
5. 分析中断原因：确定是缺页中断。
6. 查找所需页在外存的位置：根据页表项中的外存地址信息。
7. 查找空闲页框：
   • 如果内存中有空闲页框，则分配一个给即将调入的页。
   • 如果没有空闲页框，则需要执行页面置换算法，选择一个牺牲页将其换出到外存（如果该页被修改过，则需写回）。
8. 调入所需页：启动磁盘 I/O 操作，将目标页从外存读入分配的物理页框。这是一个耗时的操作，当前进程通常会阻塞。
9. 修改页表：更新调入页的页表项（设置有效位为 1，填入物理页框号，清空修改位和访问位等）。
10. 恢复现场：缺页中断处理完毕，重新执行被中断的指令。

页框分配

在请求分页系统中，需要为每个进程分配一定数量的物理页框。

分配策略：

• 固定分配：为每个进程分配固定数量的页框，运行期间不变。
  • 平均分配：所有进程平分可用页框。
  • 按比例分配：根据进程大小或其他标准按比例分配。
• 可变分配：根据进程运行情况动态调整分配给它的页框数。

页框置换范围：当发生缺页且无空闲页框时，从哪些页框中选择牺牲页。

• 全局置换：可以在所有可换出页框中选择牺牲页，即使是其他进程的页框。
  • 优点：能更好地利用内存，系统整体吞吐量可能更高。
  • 缺点：一个进程的缺页率会受其他进程影响；难以控制单个进程的性能。
• 局部置换：只能在当前缺页进程自己占有的页框中选择牺牲页。
  • 优点：更容易控制单个进程的缺页率和性能。
  • 缺点：可能导致某些进程即使有空闲页框也无法使用，内存利用率可能较低。

页面置换算法

当发生缺页中断且没有空闲物理页框时，需要选择一个内存中的页（牺牲页）将其换出，以便为新调入的页腾出空间。目标是选择一个将来最不可能被访问的页，以减少缺页次数。

1. 最佳置换算法：
   • 选择将来最长时间内不会被访问的页进行置换。
   • 优点：缺页率最低，是评价其他算法性能的基准。
   • 缺点：无法实现，因为操作系统无法预知将来页面的访问序列。
2. 先进先出置换算法：
   • 选择在内存中驻留时间最长的页进行置换。
   • 维护一个包含所有在内存中页面的队列，按到达时间排序。
   • 优点：实现简单。
   • 缺点：性能较差，可能换出经常访问的页。会产生Belady 异常（即分配给进程的页框数增加，缺页次数反而增加的现象）。
3. 最近最久未使用算法：
   • 选择过去最长时间内未被访问的页进行置换。基于局部性原理，认为最近最久未使用的页在将来也最不可能被访问。
   • 优点：性能接近 OPT，是一种较好的算法。
   • 缺点：实现开销大，需要记录每个页的访问时间或维护一个按访问时间排序的栈/链表。
   • 硬件支持实现：
     • 计数器：每个页表项关联一个时间戳寄存器。每次访问页时，将当前时钟值复制到该寄存器。置换时选择时间戳最小的页。开销大。
     • 栈：维护一个页号栈。页被访问时，将其移到栈顶。栈底的页是 LRU 页。开销也较大。
4. 时钟置换算法：
   • 是 LRU 的一种近似实现，开销较小。
   • 将内存中的页组织成一个循环队列（像一个时钟的表面），有一个指针指向其中一个页。
   • 每个页表项有一个访问位。
   • 算法流程：
     1. 当需要置换页时，从指针当前位置开始顺序检查队列中的页。
     2. 如果当前页的访问位为 1，则将其置为 0，指针下移，继续检查下一个页（给它第二次机会）。
     3. 如果当前页的访问位为 0，则选择该页为牺牲页进行置换，新页放入该位置，指针下移。
   • 优点：开销比 LRU 小，性能尚可。
5. 改进的时钟算法：
   • 同时考虑访问位 (A) 和 修改位 (M)。将页分为四类：
     1. (A=0, M=0)：最近未访问，未修改 (最佳牺牲页)。
     2. (A=0, M=1)：最近未访问，已修改 (次佳，换出前需写回磁盘)。
     3. (A=1, M=0)：最近已访问，未修改。
     4. (A=1, M=1)：最近已访问，已修改 (最不应被牺牲)。
   • 算法会优先从类别低的页中选择牺牲页。
   • 具体实现：可以进行多轮扫描。第一轮找 (0,0)；第二轮找 (0,1) 并将扫描过的 (1,x) 页的访问位置 0；以此类推。
6. 最不常用算法：
   • 选择过去一段时间内被访问次数最少的页进行置换。
   • 每个页表项需要一个访问计数器。
   • 缺点：实现开销大；可能将早期频繁访问但近期不再使用的页保留在内存中。
7. 最常用算法：
   • 认为访问次数最少的页可能是刚调入还未被充分使用，所以选择访问次数最多的页进行置换。
   • 通常性能不佳。

抖动和工作集

抖动： 如果分配给进程的物理页框太少，导致进程频繁发生缺页中断，大部分时间都用于页面换入换出，而实际有效计算时间很少，从而导致系统性能急剧下降的现象。

产生抖动的原因：

• 同时运行的进程过多，导致每个进程分配到的页框数不足。
• 页面置换算法选择不当。

防止抖动的方法：

• 采用局部置换策略。
• 基于工作集模型进行页框分配。
• 控制并发进程的数量（如通过中级调度）。
• 选择合适的页面置换算法。

工作集模型： Denning 提出，基于局部性原理。一个进程在某段时间间隔 Δ 内实际访问的页面的集合称为其在该时刻的工作集 WS(t, Δ)。

• Δ 称为工作集窗口大小。
• 工作集的大小 |WS(t, Δ)| 会随时间变化。
• 原理：操作系统跟踪每个进程的工作集，并为其分配足够的页框以容纳其工作集。如果一个进程的工作集中的所有页都在内存中，那么它在接下来的 Δ 时间内不太可能发生缺页。
• 应用：
  • 页框分配：为进程分配其工作集大小的页框。如果物理内存不足以容纳所有进程的工作集，则应挂起某些进程。
  • 页面置换：可以优先换出不在当前工作集中的页面。

内存映射文件

一种允许将磁盘文件的内容直接映射到进程的虚拟地址空间的技术。映射后，可以像访问内存一样通过指针来读写文件内容，而无需使用 read() 和 write() 等文件 I/O 系统调用。

优点：

• 方便：像访问内存一样访问文件。
• 高效：对于某些操作（如随机访问、小数据量读写），可能比传统 I/O 更高效，因为它利用了虚拟内存的按需分页机制，避免了数据的多次复制。
• 共享：多个进程可以将同一个文件映射到各自的地址空间，实现共享内存。

实现： 通过系统调用（如 POSIX 的mmap()）实现。操作系统在进程的页表中建立文件页与虚拟地址页的映射。当访问这些虚拟地址时，如果对应的文件页不在内存，则发生缺页中断，由操作系统从磁盘调入。对映射区域的修改可以根据映射参数写回磁盘。

虚拟存储器性能影响因素

• 物理内存大小：物理内存越大，能容纳的页越多，缺页率越低。
• 页面大小：
  • 页面太小：页表项增多，页表占用空间大；页面换入换出效率低。
  • 页面太大：内部碎片增大；程序局部性利用不充分。
• 页面置换算法：好的算法能显著降低缺页率。
• 程序编写方式：具有良好局部性的程序缺页率低。
• 外存（交换区）速度：影响页面换入换出的速度。
• 处理机速度：影响缺页中断处理的速度。
• 并发进程数量：过多进程会导致每个进程页框不足，引发抖动。

地址翻译

即逻辑地址到物理地址的转换过程，在分页、分段、段页式系统中都有涉及，由 MMU 硬件完成。

以请求分页为例的详细过程 (结合 TLB)：

1. CPU 生成逻辑地址 (页号 P, 页内偏移 W)。
2. 查 TLB：MMU 首先用页号 P 在 TLB 中查找。
   • TLB 命中：
     • 从 TLB 中直接获得物理页框号 F。
     • 检查访问权限。若无权限，产生保护性中断。
     • 物理地址 = F * 页框大小 + W。
     • 硬件设置访问位。如果是写操作，设置修改位。
     • 访问物理内存。
   • TLB 未命中：
     • 查页表：MMU 需要访问内存中的页表。页表基址寄存器 (PTBR) 指向当前进程页表的起始地址。页表项地址 = PTBR + P * 页表项大小。
     • 从内存中读取页表项。
     • 检查有效位：
       • 有效位为 1 (页在内存中)：
         • 获取物理页框号 F。
         • 检查访问权限。若无权限，产生保护性中断。
         • 物理地址 = F * 页框大小 + W。
         • 将该页表项加载到 TLB 中（可能会替换 TLB 中的一个旧条目）。
         • 硬件设置访问位。如果是写操作，设置修改位。
         • 访问物理内存。
       • 有效位为 0 (缺页)：
         • 产生缺页中断，CPU 控制权转交给操作系统。
         • 操作系统执行缺页中断处理程序。
         • 处理完成后，重新执行被中断的指令（此时页已在内存，TLB 可能也已更新）。

这个过程对程序员是透明的。

文件管理

文件系统是操作系统中负责管理和组织外存（如磁盘）上的文件，并向用户提供方便、统一的访问接口的部分。

文件系统基础

文件的基本概念

文件：一组有意义的相关信息的集合，通常存储在二级存储器（如磁盘）上，并赋予一个名字。文件是操作系统进行信息存储和管理的基本单位。

文件的属性 (元数据)：描述文件特征的信息，通常存储在文件控制块中。

• 名称：用户可读的文件名。
• 标识符：文件系统内部使用的唯一标签。
• 类型：如可执行文件、文本文件、图像文件等。
• 位置：指向文件在存储设备上位置的指针。
• 大小：文件当前的大小。
• 保护：访问控制信息（如读/写/执行权限）。
• 时间、日期和用户标识：创建时间、最后修改时间、最后访问时间、所有者等。

文件控制块和索引结点

文件控制块：操作系统为管理文件而设置的数据结构，用于存放与文件相关的所有管理信息（即文件属性）。FCB 是文件存在的标志。所有文件的 FCB 集合构成了文件目录（或称为目录文件）。

索引结点：在类 UNIX 系统中，FCB 中的文件名等描述性信息与文件控制信息（如物理地址、权限、大小等）分离。

• 目录项：只包含文件名和指向该文件索引结点的指针。
• 索引结点：包含文件的除文件名以外的所有元数据，如文件类型、权限、所有者、时间戳、大小、指向数据块的指针等。
• 优点：
  • 一个文件可以有多个文件名（硬链接），都指向同一个 inode。
  • 提高了目录操作的效率（目录项变小）。
  • 方便文件系统检查和修复。

文件的操作

操作系统提供一组系统调用来对文件进行操作：

• 创建文件：在文件系统中创建一个新文件，分配必要的存储空间，建立 FCB。
• 删除文件：删除文件，回收其占用的存储空间和 FCB。
• 打开文件：在对文件进行读写等操作前，需要先打开文件。操作系统会将文件的 FCB（或部分信息）从外存调入内存（通常是系统维护的打开文件表），并返回一个文件描述符或句柄给进程，后续操作通过此描述符进行。
  • 打开文件表：
    • 系统级打开文件表：包含所有已打开文件的 FCB 副本和一些全局信息（如打开计数器）。
    • 进程级打开文件表：每个进程维护一张表，记录其打开的文件，表项指向系统级打开文件表中的对应条目，并包含进程特定的信息（如当前读写位置）。
• 关闭文件：进程完成对文件的操作后，应关闭文件。操作系统会将内存中与该文件相关的表项（如进程级打开文件表项）释放，并将系统级打开文件表中的打开计数器减 1。如果计数器为 0，则可将 FCB 写回磁盘（如果被修改过）。
• 读文件：从文件的当前读写位置读取数据到内存缓冲区。
• 写文件：将内存缓冲区的数据写入到文件的当前读写位置。
• 定位文件：移动文件的当前读写位置。
• 获取/设置文件属性：读取或修改文件的元数据。
• 重命名文件：改变文件名。

文件保护

确保文件不被未授权的用户或进程访问或修改。

保护机制：

• 访问控制列表：
  • 为每个文件维护一个列表，记录了哪些用户（或用户组）对该文件拥有哪些访问权限（如读、写、执行、删除等）。
  • 优点：灵活，可以精确控制权限。
  • 缺点：列表可能很长，管理和检查开销大。
• 访问权限矩阵：
  • 行代表主体（用户/进程），列代表客体（文件/资源），矩阵元素表示主体对客体的权限。
  • 通常是稀疏矩阵，实现上可以转换为 ACL（按列存储）或能力表（按行存储）。
• 基于用户类别的权限控制：
  • 将用户分为三类：文件所有者、同组用户、其他用户。
  • 为每类用户分别设置读(r)、写(w)、执行(x)权限。例如 rwxr-xr--。
  • 优点：简单高效。
  • 缺点：不够灵活，不能对特定用户精确授权。
• 口令保护：
  • 为文件设置口令，只有提供正确口令才能访问。
  • 缺点：口令易泄露，不适合多用户共享。
• 加密保护：
  • 对文件内容进行加密，只有拥有密钥才能解密访问。
  • 优点：安全性高。
  • 缺点：加解密开销大。

文件的逻辑结构

指文件在用户视图中的组织方式，与文件在存储介质上的物理存放方式无关。

1. 无结构文件 (流式文件)：
   • 文件被看作是一系列连续的字节流或字符流。
   • 操作系统不关心文件内部结构，由应用程序自行解释。
   • 如文本文件、可执行文件。
   • 优点：简单通用。
2. 有结构文件 (记录式文件)：
   • 文件由一系列具有相同或不同长度的记录组成。每条记录有其内部结构。
   • 操作系统提供按记录访问的功能。
   • 定长记录：所有记录长度相同。
   • 变长记录：记录长度可不同。
   • 类型：
     • 顺序文件：记录按顺序排列，只能按序访问（或通过模拟随机访问）。
     • 索引文件：为文件建立索引表，根据记录的键值通过索引快速定位记录。
     • 索引顺序文件：将顺序文件和索引文件结合，记录顺序存储，同时建立索引。支持顺序访问和按键随机访问。
     • 直接文件/散列文件：根据记录的键值通过散列函数直接计算出记录的物理地址。

现代操作系统大多采用无结构文件，将文件内部结构的解释交给应用程序。

文件的物理结构

指文件在辅存（如磁盘）上的存放方式和组织方式。

1. 连续分配：
   • 为每个文件分配一组连续的磁盘块。
   • 目录中记录文件的起始块号和长度（块数）。
   • 优点：
     • 支持顺序访问和随机访问，速度快（磁头移动少）。
     • 实现简单。
   • 缺点：
     • 外部碎片：难以找到足够大的连续空闲空间。
     • 文件创建时必须知道文件大小，难以动态增长。
     • 需要进行磁盘碎片整理。
2. 链接分配：
   • 文件的数据块可以离散地存放在磁盘的任意空闲块中。
   • 每个数据块中包含一个指向下一个数据块的指针。
   • 目录中记录文件的起始块号和结束块号（可选）。
   • 优点：
     • 没有外部碎片，提高了磁盘空间利用率。
     • 文件可以动态增长。
   • 缺点：
     • 只支持顺序访问，随机访问效率低（需要从头遍历指针链）。
     • 指针占用了一部分存储空间。
     • 可靠性差，指针损坏会导致文件数据丢失。
   • 改进：文件分配表：
     • 将所有数据块的链接指针集中存放在磁盘开头的一个专用区域——文件分配表 (FAT) 中。
     • FAT 的每个表项对应一个磁盘块，存放下一块的块号；如果是文件末尾，则为特殊标记；如果是空闲块，也为特殊标记。
     • 目录项中只需记录文件的起始块号。
     • 优点：支持随机访问（通过查询 FAT），提高了可靠性（FAT 可以有备份）。
     • 缺点：FAT 需要全部或部分读入内存，占用内存；访问 FAT 可能成为瓶颈。
3. 索引分配：
   • 为每个文件分配一个索引块，索引块中存放指向文件所有数据块的指针（磁盘块号）。
   • 目录项中记录文件的索引块号。
   • 优点：
     • 支持直接访问（随机访问），只需读取索引块即可。
     • 没有外部碎片。
     • 文件可以动态增长。
   • 缺点：
     • 索引块本身占用存储空间。如果文件很小，索引块开销相对较大。
     • 对于大文件，一个索引块可能不够用，需要多级索引。
   • 多级索引：
     • 一级索引：索引块直接指向数据块。
     • 二级索引：索引块指向下一级索引块，下一级索引块再指向数据块。
     • 以此类推，可以支持非常大的文件。
     • 例如 UNIX 的 inode 中的地址项就采用了混合索引方式（直接指针、一级间接、二级间接、三级间接）。

目录

目录本身也是一种特殊的文件（称为目录文件），其内容是该目录下所有文件和子目录的目录项。

目录的基本概念

目录：用于组织和管理文件的一种机制，它将文件名与文件在存储设备上的信息（如 FCB 或 inode 指针）联系起来。

目录的功能：

• 实现“按名存取”。
• 提供文件共享。
• 限制对文件的访问。
• 提高文件系统的组织性和查找效率。

目录结构

1. 单级目录结构：
   • 整个文件系统中只有一个目录，所有文件都在这个目录下。
   • 优点：简单。
   • 缺点：文件名必须唯一，查找速度慢，不适用于多用户。
2. 二级目录结构：
   • 分为主文件目录 和用户文件目录。
   • MFD 的每个条目指向一个 UFD。每个用户拥有自己的 UFD。
   • 优点：解决了文件名冲突问题，不同用户可以使用相同的文件名。
   • 缺点：用户间文件共享不方便。
3. 树形目录结构：
   • 最常用的结构。目录可以包含文件和其他目录（子目录）。
   • 形成一个树状结构，根目录是树的根。
   • 路径名：从根目录到目标文件/目录所经过的目录序列。
     • 绝对路径：从根目录开始的完整路径。
     • 相对路径：从当前工作目录 开始的路径。
   • 优点：层次清晰，管理方便，易于实现文件共享和保护。
   • 缺点：查找文件可能需要遍历多级目录，效率可能不高。
4. 无环图目录结构：
   • 在树形结构的基础上，允许目录或文件有多个父目录，即允许共享子目录或文件（通过链接实现）。
   • 共享的文件或目录只有一个物理副本。
   • 优点：文件共享更灵活。
   • 缺点：
     • 实现复杂，需要处理链接计数（判断何时真正删除文件）。
     • 可能出现悬空指针问题（如果被链接的文件/目录被删除）。
5. 通用图目录结构：
   • 允许目录结构中存在环路。
   • 缺点：实现非常复杂，查找可能陷入死循环，垃圾回收困难。实际中很少使用。

目录的操作

• 创建目录
• 删除目录：通常要求目录为空才能删除。
• 打开目录：读取目录内容前需要打开。
• 关闭目录
• 读目录：列出目录下的文件和子目录。
• 重命名目录
• 改变当前工作目录
• 搜索文件：在目录下查找指定文件。

目录实现

目录信息通常存储在外存。常用的实现方法：

1. 线性列表：
   • 目录条目（文件名+属性/指针）以线性列表形式存储。
   • 优点：实现简单。
   • 缺点：查找、插入、删除文件时效率较低（可能需要线性搜索）。
2. 哈希表：
   • 根据文件名通过哈希函数计算出在哈希表中的位置，存储目录条目。
   • 优点：查找速度快。
   • 缺点：需要处理哈希冲突；哈希表大小固定可能导致空间浪费或性能下降。

当目录文件很大时，也可能采用类似文件数据块的索引分配方式来管理目录条目。

文件共享

允许多个用户或进程共同访问同一个文件。

实现方式：

1. 基于索引结点的共享 (硬链接)：
   • 多个目录项中的文件名指向同一个文件的索引结点。
   • inode 中需要有一个链接计数器，记录有多少个目录项指向它。
   • 当删除一个链接时，链接计数减 1。只有当链接计数为 0 时，才真正删除文件数据和 inode。
   • 优点：所有链接具有同等地位。
   • 缺点：只能对同一文件系统内的文件创建硬链接；不能对目录创建硬链接（防止循环）。
2. 基于符号链接的共享 (软链接)：
   • 创建一个特殊类型的文件（链接文件），其内容是另一个文件的路径名。
   • 当访问软链接时，操作系统会根据其内容找到目标文件。
   • 优点：可以链接不同文件系统中的文件，也可以链接目录。
   • 缺点：
     • 如果目标文件被删除或移动，软链接会失效（悬空指针）。
     • 访问软链接需要额外的路径解析开销。
     • 软链接本身也占用 inode 和数据块。

文件系统

文件系统结构

文件系统通常采用分层结构，每一层利用其下层提供的服务，并向其上层提供服务。

典型的分层结构：

1. 用户接口层：提供用户与文件系统交互的命令或 API（如 open, read, write, close）。
2. 文件目录系统层：管理目录结构，将文件名映射到文件控制块，进行权限检查。
3. 存取控制验证层：将逻辑块号转换为物理块号，管理空闲空间。
4. 基本文件系统层：向设备驱动程序发出通用命令（如读/写某个物理块）。
5. 设备驱动程序层：与特定 I/O 设备控制器交互，将上层命令转换为设备特定的操作。
6. 物理设备层：磁盘、磁带等存储硬件。

文件系统布局

磁盘分区上的文件系统通常包含以下部分：

1. 引导控制块：
   • 通常在分区的第一个扇区。
   • 包含从该分区引导操作系统所需的信息。
2. 分区控制块：
   • 包含文件系统的元数据，如分区中块的总数、空闲块数、块大小、inode 数量、空闲 inode 数量、文件系统类型、魔数等。
   • 文件系统装载时，超级块会被读入内存。
3. 索引结点区：
   • 存放所有文件的索引结点。
4. 数据块区：
   • 存放文件实际数据内容和目录文件内容。
5. 空闲空间管理信息：
   • 如空闲块位图或空闲块链表。

外存空闲空间管理

记录磁盘上哪些块是空闲的，以便在创建文件或追加数据时进行分配。

1. 空闲表法：
   • 将所有空闲块链接起来形成一个或多个链表。
   • 管理简单，但分配和回收可能较慢（需要遍历链表）。
2. 空闲链表法：
   • 将所有空闲块链接成一个链表。每个空闲块中存放指向下一个空闲块的指针。
   • 优点：不需要额外空间存储链表。
   • 缺点：分配多个连续块时效率低；读取一个空闲块信息就需要一次磁盘 I/O。
   • 改进：成组链接法：将多个空闲块的块号存放在一个空闲块中，最后一个块号指向下一个存放空闲块号的块。UNIX 采用此法。
3. 位图法：
   • 用一位二进制位来对应磁盘上的一个块。
   • 1表示块已分配，0表示块空闲（或反之）。
   • 优点：很容易找到一个或多个连续的空闲块；分配和回收速度快。
   • 缺点：位图本身可能很大，需要占用一定存储空间（通常放在内存）。
4. 计数法：
   • 记录第一个空闲块的块号以及紧随其后的连续空闲块的数量。
   • 适用于空闲块经常连续出现的情况。

虚拟文件系统

现代操作系统通常需要支持多种不同的文件系统类型（如 FAT32, NTFS, ext4 等）。VFS 是一个在内核中的软件层，它提供了一个统一的、抽象的文件系统接口给上层应用程序。

VFS 的作用：

• 对上层屏蔽了底层具体文件系统的差异。
• 使得可以方便地添加对新文件系统的支持。
• 允许文件操作跨越不同的文件系统（如从一个 ext4 分区复制文件到 NTFS 分区）。

VFS 的实现： 定义了一组通用的文件系统对象（如超级块对象、inode 对象、目录项对象、文件对象）和操作这些对象的方法。具体文件系统需要实现这些标准接口。当上层进行文件操作时，VFS 会调用对应具体文件系统的相应方法。

分区和安装

磁盘分区： 将一个物理磁盘划分为一个或多个逻辑区域，每个区域称为一个分区。每个分区可以被当作一个独立的逻辑磁盘来使用，可以安装不同的文件系统或操作系统。

文件系统安装： 为了访问一个文件系统（通常位于某个磁盘分区上），需要将其安装 到当前文件系统目录树的某个安装点（通常是一个空目录）。 安装后，该文件系统的内容就通过安装点目录可见和访问。 卸载操作则相反。

输入/输出管理

I/O 管理是操作系统的重要组成部分，负责管理计算机的各种输入输出设备，并为用户和上层软件提供方便、统一的 I/O 操作接口。

I/O 管理概述

I/O 设备

计算机系统中的 I/O 设备种类繁多，特性各异。

按使用特性分类：

• 人机交互设备：用于用户与计算机通信。如键盘、鼠标、显示器、打印机。速度相对较慢。
• 机-机通信设备：用于计算机之间或计算机与外部设备通信。如磁盘驱动器、磁带驱动器、网络接口卡、传感器。速度范围广。
• 存储设备：用于存储数据。如磁盘、固态硬盘、光盘。

按传输速率分类：

• 低速设备：如键盘、鼠标。每秒几个字节到几百个字节。
• 中速设备：如打印机、扫描仪。每秒几千字节到几十万字节。
• 高速设备：如磁盘、网络接口。每秒几兆字节到几吉字节甚至更高。

按信息交换单位分类：

• 块设备：以固定大小的数据块（如磁盘扇区）为单位进行信息存储和传输。可寻址（随机访问）。如磁盘、固态硬盘。
• 字符设备：以字符为单位进行数据输入输出，不可寻址（通常是顺序访问）。如键盘、打印机、串口。

I/O 设备的组成：

• 机械部件：设备本身。
• 电子部件 (设备控制器/适配器)：
  • 是 CPU 与 I/O 设备之间的接口。
  • 接收 CPU 发来的命令，控制 I/O 设备工作，并向 CPU 报告设备状态和操作结果。
  • 通常包含数据寄存器、状态寄存器、控制寄存器。
  • 可以实现数据缓冲、错误检测等功能。

I/O 控制方式

指 CPU 如何管理和控制 I/O 设备的操作。

1. 程序直接控制方式 (轮询)：
   • CPU 主动执行 I/O 指令来启动设备，并不断检测设备状态寄存器，直到 I/O 完成。
   • 优点：硬件简单。
   • 缺点：CPU 在等待 I/O 期间处于忙等待状态，CPU 利用率低。
2. 中断驱动方式：
   • CPU 发出 I/O 命令启动设备后，就去执行其他任务。
   • 当 I/O 设备完成操作后，会向 CPU 发出中断请求。
   • CPU 响应中断，转去执行中断处理程序，处理 I/O 结果。
   • 优点：大大提高了 CPU 利用率。
   • 缺点：
     • 每次 I/O 操作完成都需要中断，对于高速设备，频繁中断会消耗大量 CPU 时间。
     • 数据传输仍需 CPU 参与（从设备控制器寄存器读数据到内存，或从内存写数据到寄存器）。
3. 直接存储器存取方式：
   • 在 I/O 设备和主存之间开辟直接的数据通路。
   • 需要 DMA 控制器。
   • 过程：
     1. CPU 向 DMAC 发出 I/O 命令（包括要读/写的数据块的内存起始地址、磁盘地址、数据块大小、传输方向等）。
     2. DMAC 接管总线控制权（或通过周期窃取方式），直接在设备和内存之间传输数据，无需 CPU 干预。
     3. 数据传输完成后，DMAC 向 CPU 发出中断信号。
   • 优点：进一步减少了 CPU 对 I/O 操作的干预，CPU 只需在数据传输开始和结束时参与。特别适合高速块设备。
   • 缺点：硬件比中断方式复杂。
4. 通道控制方式：
   • 是 DMA 方式的进一步发展，引入了通道（一种专门负责 I/O 处理的处理机）。
   • CPU 只需向通道发出 I/O 指令，指明要执行的通道程序（一组 I/O 命令）在内存中的位置。
   • 通道会执行通道程序，控制多台 I/O 设备与内存进行数据交换。
   • 完成后，通道向 CPU 发出中断。
   • 优点：进一步解放了 CPU，实现了 CPU 与 I/O 操作的高度并行。主要用于大型机。
   • 缺点：硬件非常复杂，成本高。

I/O 软件层次结构

I/O 软件通常组织成层次结构，以实现设备独立性和提高软件可维护性。

1. 用户层 I/O 软件：
   • 提供给用户的库函数（如 C 标准库的printf, scanf, fopen, fread等）。
   • 将用户请求转换为对操作系统内核的系统调用。
2. 设备独立性软件层：
   • 操作系统的核心 I/O 部分。
   • 向上层提供统一的 I/O 接口（如对块设备和字符设备的统一抽象）。
   • 负责设备命名、设备保护、提供与设备无关的块大小、缓冲技术、设备分配与回收、错误报告等。
3. 设备驱动程序层：
   • 与特定 I/O 设备控制器直接交互。
   • 将上层发来的抽象 I/O 请求（如读一个逻辑块）转换为对设备控制器的具体操作序列（如设置寄存器、启动设备）。
   • 处理设备产生的中断。
   • 每个设备类型通常都有一个对应的设备驱动程序。
4. 中断处理程序：
   • 当中断发生时，保存 CPU 现场，分析中断原因，调用相应的设备驱动程序中的中断服务例程。
   • 处理完毕后，恢复现场。
5. 硬件层：
   • 包括 I/O 设备控制器和 I/O 设备本身。

应用程序 I/O 接口

操作系统向应用程序提供的进行 I/O 操作的接口，通常是一组系统调用。

• 块设备接口：如 read block, write block。访问特定块。
• 字符设备接口：如 get char, put char。顺序读写字符。
• 网络设备接口：如套接字接口。
• 时钟和定时器接口：获取当前时间，设置定时器。
• 其他接口：如图形用户界面相关的 I/O。

这些接口通常被封装在用户库函数中，方便应用程序调用。

设备独立性软件

也称为 I/O 核心子系统，目标是向上层提供统一的 I/O 视图，隐藏底层硬件设备的差异。

与设备无关的软件

• 统一命名：为所有文件和设备提供统一的命名空间和路径名（如 UNIX 中设备被当作文件处理）。
• 设备保护：确保只有授权用户才能访问设备。
• 提供与设备无关的块大小：向上层提供统一的逻辑块大小，屏蔽不同设备物理块大小的差异。
• 缓冲技术：见下一节。
• 存储分配：管理块设备的存储空间（如磁盘块的分配与回收）。
• 设备分配与回收：管理独占设备的分配与回收。
• 错误处理与报告：处理 I/O 错误，向上层报告。

高速缓存与缓冲区

缓冲：在 I/O 设备和 CPU（或内存）之间设置一个临时存储区域（缓冲区），用于暂存数据。

引入缓冲的目的：

1. 缓和 CPU 与 I/O 设备之间速度不匹配的矛盾：高速 CPU 与低速 I/O 设备可以通过缓冲区协调工作。
2. 减少对 CPU 的中断频率，放宽对 CPU 中断响应时间的限制：数据可以先批量送入缓冲区，再统一处理。
3. 提高 CPU 与 I/O 设备之间的并行性：CPU 可以将数据输出到缓冲区后继续做其他事，由缓冲区将数据传给 I/O 设备。
4. 解决数据粒度不匹配的问题：如发送方和接收方处理数据块大小不同。

缓冲区的实现：

• 单缓冲：设置一个缓冲区。
  • 输入时：设备数据 -> 缓冲区 -> 用户区。
  • 输出时：用户区 -> 缓冲区 -> 设备。
  • 当缓冲区满（输入）或空（输出）时，进程可能需要等待。
• 双缓冲：设置两个缓冲区。
  • 一个缓冲区用于 I/O 设备操作，另一个用于 CPU 操作，两者可以并行。
  • 当一个缓冲区满（输入）或空（输出）后，切换到另一个缓冲区。
  • 提高了并行度，减少了等待时间。
• 循环缓冲：将多个缓冲区组织成循环队列。
  • 适用于生产者-消费者模型，如输入输出流。
• 缓冲池：由系统统一管理一组缓冲区，供多个 I/O 请求共享。
  • 当进程请求 I/O 时，从缓冲池中分配一个缓冲区。
  • 提高了缓冲区的利用率。

高速缓存： 与缓冲区类似，也是一块高速存储区域，但主要用于保存频繁访问的数据副本，以加快后续访问速度。

• 磁盘高速缓存：内存中开辟一块区域，缓存最近访问过的磁盘块。
  • 当需要读磁盘块时，先检查 Cache，若命中则直接从 Cache 读取。
  • 写操作可以采用写穿（同时写 Cache 和磁盘）或延迟写/回写（先写 Cache，适当时机再写回磁盘）。
• 与缓冲区的区别：
  • 缓冲区主要目的是缓和速度差异和提高并行性。
  • 高速缓存主要目的是利用局部性原理，通过保存副本加快访问。
  • 一个数据项可能只在缓冲区中临时存放一次，但可能在高速缓存中存放多次。

设备的分配与回收

操作系统需要管理系统中所有 I/O 设备的状态，并根据用户请求进行分配和回收。

设备分配的数据结构：

• 设备控制表：每个设备一张，记录设备类型、标识符、状态、指向控制器表的指针等。
• 控制器控制表：每个设备控制器一张，记录控制器状态、指向通道表的指针等。
• 通道控制表：每个通道一张，记录通道状态等。
• 系统设备表：整个系统一张，记录所有已连接设备的情况。

设备分配的考虑因素：

• 设备固有属性：独占设备（如打印机）、共享设备（如磁盘）、虚拟设备。
• 设备分配算法：先来先服务、优先级等。
• 设备分配的安全性：避免死锁（如静态分配、按序分配）。

设备分配步骤（以独占设备为例）：

1. 进程发出 I/O 请求，指定所需设备类型。
2. 系统查找 SDT，看是否有该类型空闲设备。
3. 若有，则分配给进程，修改 DCT 等表项状态。
4. 若无，则将进程阻塞，放入该设备类型的等待队列。
5. 设备使用完毕后，进程释放设备，系统回收设备，并唤醒等待队列中的进程（如果队列不空）。

SPOOLing 技术

SPOOLing 是一种将独占的慢速 I/O 设备（如打印机、卡片阅读机）改造成共享设备的技术，以提高设备利用率和系统效率。

原理： 在磁盘上开辟输入井 和输出井 作为缓冲区。

• 输入过程：输入进程将用户从输入设备（如卡片机）输入的数据先存放到磁盘输入井中。当 CPU 需要输入数据时，直接从高速的输入井中读取。
• 输出过程：输出进程将用户程序的输出结果先存放到磁盘输出井中。待输出设备（如打印机）空闲时，再由专门的输出程序将输出井中的数据实际输出到设备。

组成：

• 输入井和输出井：磁盘上的存储区域。
• 输入缓冲区和输出缓冲区：内存中的缓冲区，用于暂存与井交换的数据。
• 输入进程 和 输出进程：专门负责数据与井之间传输的系统进程。
• 井管理程序：负责井中作业的排队和管理。

优点：

• 虚拟了设备：将独占设备改造成了共享设备，多个用户可以同时“使用”该设备。
• 提高了 I/O 速度：缓和了 CPU 与慢速设备的速度矛盾。
• 提高了设备利用率。
• 实现了并行操作：CPU 计算、数据从设备到井、数据从井到设备可以并行进行。

设备驱动程序接口

设备驱动程序是操作系统内核的一部分，它直接与特定的硬件设备控制器交互。设备独立性软件层通过一个标准的接口来调用设备驱动程序的功能。

这个接口通常定义了一组标准函数，如：

• open(): 初始化设备。
• close(): 关闭设备。
• read(): 从设备读取数据。
• write(): 向设备写入数据。
• ioctl(): 执行设备特定的控制操作。
• strategy(): 对于块设备，用于提交一个读/写请求到设备请求队列。

设备驱动程序负责将这些通用请求转换为设备控制器能理解的具体命令序列。

磁盘和固态硬盘

磁盘

磁盘是计算机系统中常用的辅助存储设备，容量大，速度相对较快，可随机访问。

物理结构：

• 盘片：一个或多个圆形金属或玻璃盘片，双面涂有磁性材料。
• 磁道：盘片上的一系列同心圆。
• 扇区：每个磁道被划分为若干个扇形区域，是磁盘读写的最小单位（通常 512 字节或 4KB）。
• 柱面：所有盘片上半径相同的磁道构成的圆柱面。
• 磁头：每个盘面对应一个磁头，用于读写数据。所有磁头固定在同一个磁头臂上，同步移动。

磁盘地址：通常由 (柱面号, 磁头号/盘面号, 扇区号) 组成。

磁盘访问时间：

1. 寻道时间：磁头从当前位置移动到目标磁道所需的时间。这是最主要的部分。
2. 旋转延迟时间：等待目标扇区旋转到磁头下方所需的时间。平均为磁盘旋转半圈的时间。
3. 传输时间：数据从磁盘读出或写入磁盘所需的时间。取决于数据量和磁盘转速/密度。

总访问时间 = 寻道时间 + 旋转延迟时间 + 传输时间

磁盘管理

• 磁盘格式化：
  • 低级格式化 (物理格式化)：在磁盘上划分磁道和扇区，写入扇区头、尾和校验码等控制信息。出厂前完成。
  • 高级格式化 (逻辑格式化)：创建文件系统结构，如写入引导块、超级块、inode 区、根目录等。
• 引导块：包含引导加载程序，用于启动操作系统。
• 坏块管理：
  • 磁盘上可能存在物理损坏的扇区（坏块）。
  • 可以在格式化时检测坏块，并将其标记，文件系统会避开使用它们。
  • 有些控制器会自动进行扇区备用或扇区前移。

磁盘调度算法

当有多个磁盘 I/O 请求等待时，磁盘调度算法决定处理这些请求的顺序，以减少总寻道时间，提高磁盘吞吐量。

假设当前磁头位置，以及一个等待访问的柱面号队列。

1. 先来先服务：
   • 按请求到达的顺序处理。
   • 优点：公平。
   • 缺点：平均寻道时间可能很长，效率不高。
2. 最短寻道时间优先：
   • 选择与当前磁头位置最近的请求进行处理。
   • 优点：平均寻道时间较短，吞吐量较高。
   • 缺点：可能导致“饥饿”现象（某些远离磁头的请求长时间得不到服务）。
3. 扫描算法 (电梯算法)：
   • 磁头在一个方向上移动（如从内到外），处理沿途所有请求。到达磁盘一端后，再反向移动，处理沿途请求。
   • 优点：克服了 SSTF 的饥饿问题，寻道性能较好，对各个位置的请求响应比较公平。
   • 缺点：对于刚经过的位置，如果出现新请求，需要等待磁头完整往返一次。两端磁道的请求等待时间较长。
4. 循环扫描算法：
   • SCAN 算法的改进。磁头只在一个方向上处理请求（如从内到外）。到达一端后，立即快速返回到另一端（如最内侧），然后重新开始单向扫描。
   • 优点：比 SCAN 更公平，请求的等待时间更均匀。
   • 缺点：返回过程不处理请求，略有浪费。
5. LOOK 算法 和 C-LOOK 算法：
   • 是 SCAN 和 C-SCAN 的改进。磁头移动到该方向上最远的一个请求处即改变方向，而不是移动到磁盘的物理端点。
   • LOOK: 磁头在两个方向上移动，到达最远请求后反向。
   • C-LOOK: 磁头在一个方向上移动到最远请求后，直接跳到另一端（有请求的最内/外侧），再开始单向扫描。
   • 优点：避免了不必要的磁头移动到磁盘末端，效率更高。C-LOOK 是实践中常用的算法。

固态硬盘

SSD 使用闪存作为存储介质，没有机械部件。

特性：

• 优点：
  • 读写速度快（尤其是随机读）。
  • 无寻道时间和旋转延迟。
  • 低功耗，抗震动，噪音小。
• 缺点：
  • 单位容量价格比传统磁盘高。
  • 闪存有擦写次数限制（寿命问题，但通过磨损均衡技术有所改善）。
  • 写操作比读操作慢，且擦除操作更慢（通常需要先擦除整个块才能写入）。

SSD 的 I/O 调度： 由于没有寻道时间和旋转延迟，传统磁盘调度算法（如 SSTF, SCAN）对 SSD 意义不大。 SSD 的调度更多考虑闪存的特性，如：

• 磨损均衡：尽量均匀地擦写所有闪存块，延长寿命。
• 垃圾回收：整理无效数据，回收可擦除的块。
• 一些 SSD 控制器内部实现了自己的调度逻辑，操作系统层面可能只需 FCFS 或简单的优先级调度。
• TRIM 命令：操作系统通知 SSD 哪些数据块已不再使用，SSD 可以在空闲时进行擦除，提高后续写入性能。