操作系统笔记

lesson 1 概论
- 接口层次
lesson 2 操作系统结构
lesson 3 中断，异常
lesson 4 进程
Lesson 5 线程
Lesson 6 进程调度
Lesson 7 同步
Lesson 8 并发：死锁，饥饿
Lesson 9 内存管理
lesson 10 虚拟内存管理
Lesson 11 大容量存储
Lesson 12 IO管理
Lesson 13 文件系统
Lesson 14 文件系统实现
- 文件分配方法
- 统一缓冲区（Unified Buffer Cache）
Lesson 15 典型文件操作和系统
- FAT文件系统笔记

对着课件的内容做的操作系统的笔记，多图多文字预警。在后期复习的时候发现了许多错误，所以该笔记部分内容的正确性需要甄别。

lesson 1 概论

操作系统是在硬件和应用之间的软件层，是在计算机用户和计算机硬件之间起代理作用的程序

计算机系统可分为四个部分：

硬件–提供基本的计算资源
- CPU、内存、I/O设备
操作系统
- 控制和协调各种应用程序和用户之间的硬件使用
应用程序–定义使用系统资源解决用户计算问题的方式
- 文字处理器、编译器、网络浏览器、数据库系统、视频游戏
用户
- 人、机器、其他计算机

接口层次

指令集架构 (Instruction Set Architecture, ISA)：定义了CPU可以执行的指令集，是硬件和操作系统之间的接口。
应用二进制接口 (Application Binary Interface, ABI)：定义了应用程序和操作系统之间的接口，确保应用程序能够在操作系统上运行。
应用编程接口 (Application Programming Interface, API)：定义了应用程序与库/工具之间的接口，简化应用程序开发。

lesson 2 操作系统结构

操作系统的发展

操作系统的发展可以分为以下几个阶段：

1. 串行处理

最早的计算机系统采用串行处理模式，所有任务按顺序执行，没有并发执行的能力。
用户通过控制台直接与计算机进行交互，手动输入指令，计算机逐个执行。

2. 简单批处理

在串行处理的基础上，引入了批处理技术，用户将需要执行的任务提交给操作系统，系统自动按顺序执行这些任务。
用户无需等待前一个任务完成后再手动输入下一个任务，提高了系统利用率和效率。
批处理系统的一个缺点是任务之间无法交互，系统无法动态调整任务的执行顺序。

3. 多道批处理

多道批处理系统进一步改进了简单批处理系统，引入了多任务并发执行的能力。
操作系统可以同时处理多个任务，当一个任务需要等待I/O操作时，CPU可以切换到另一个任务，提高了资源利用率。
多道批处理系统通过时间分片和任务调度算法，使得多个任务可以在短时间内交替执行，用户感觉任务是同时进行的。

4. 分时系统

分时系统是操作系统发展的高级阶段，通过快速的任务切换和调度算法，使得多个用户可以同时共享计算机系统资源。
用户通过终端连接到主机系统，可以同时运行和交互多个任务。
分时系统广泛应用于交互式计算环境，提供了更高效和灵活的资源管理方式。

这个发展过程展示了操作系统在资源管理、任务调度和用户交互方面的不断进步和优化。

操作系统模式

操作系统通常有两种工作模式：用户模式（User Mode）和内核模式（Kernel Mode）。这两种模式的区别主要在于对系统资源的访问权限和可执行指令的限制。

用户模式 (User Mode)

用户程序在用户模式下执行：大多数应用程序运行在用户模式下，以确保系统安全。
某些内存区域对用户访问进行保护：防止用户程序直接访问关键系统数据和代码，确保系统稳定性。
某些指令不能在用户模式下执行：用户模式下的程序不能执行特权指令，以防止系统被恶意操作或意外损坏。

内核模式 (Kernel Mode)

操作系统内核在内核模式下执行：系统的核心组件和关键任务在内核模式下运行，以确保完全的资源控制和管理。
特权指令可以执行：内核模式允许执行所有指令，包括管理硬件和关键资源的特权指令。
可以访问受保护的内存区域：内核模式下的代码可以访问和操作所有内存区域，包括受保护的系统数据。

用户模式和内核模式的分离确保了系统的安全性和稳定性。用户程序的限制防止了对系统资源的非法访问和操作，而内核模式下的特权操作则保证了系统的正常运行和管理。

通过这种双模式的设计，操作系统能够高效地管理资源，同时提供必要的保护措施，以防止系统被破坏或滥用。

操作系统服务

操作系统提供的服务根据不同的操作系统有所不同，但也存在一些共同点。操作系统服务主要包括以下几个方面：

用户接口 (User Interfaces)

GUI（图形用户界面）：提供直观的图形界面，用户可以通过点击、拖动等操作与系统进行交互。
触摸屏界面：主要用于移动设备和触摸屏设备，用户通过触摸屏幕进行操作。
命令行界面：通过输入命令与系统交互，适用于高级用户和系统管理员。

系统调用 (System Calls)

系统调用是应用程序与操作系统之间的接口，提供各种基础服务，包括：

程序执行 (Program Execution)：管理程序的加载、执行和终止。
I/O操作 (I/O Operations)：管理输入输出设备的访问和控制。
文件系统 (File Systems)：提供文件的创建、删除、读取和写入等操作。
通信 (Communication)：管理进程间的通信和数据交换。
资源分配 (Resource Allocation)：管理系统资源的分配和回收。
账户管理 (Accounting)：记录系统资源的使用情况和用户活动。
错误检测 (Error Detection)：监控系统运行，检测和处理错误。
保护和安全 (Protection and Security)：提供数据保护、访问控制和系统安全性。

操作系统提供的服务尽管随具体操作系统有所不同，但都包含了一些基本的功能模块，如程序执行、I/O操作、文件系统、通信、资源分配、错误检测和保护与安全等。这些服务共同保障了计算机系统的高效运行和用户的便捷使用。

程序编译和运行

编译过程

源代码编译成目标文件
- 源代码经过编译器处理，生成目标文件（.obj或.o文件）。
- 目标文件设计为可加载到任何物理内存位置——可重定位目标文件。
链接过程
- 链接器将多个目标文件组合成一个二进制可执行文件。
- 链接过程中，链接器会解决符号引用，将各个目标文件中的函数和变量地址调整到正确的位置。
生成可执行文件
- 最终生成的二进制文件存储在辅助存储器上，准备执行。

加载过程

加载程序带入内存
- 可执行文件在执行前，必须被加载程序带入内存。
- 重新定位：将最终地址分配给程序组件，并调整程序中的代码和数据以匹配这些地址。

现代操作系统的特性

动态链接库
- 现代通用系统不会将库链接到可执行文件中，而是根据需要加载动态链接库（在Windows中为DLL，在Linux中为.so）。
- 动态链接库的好处是：由使用同一库的同一版本的所有用户共享（只加载一次），减少了内存和存储的冗余。

文件格式

目标文件和可执行文件的格式
- 目标文件和可执行文件具有标准格式，使操作系统知道如何加载和自动运行。

通过以上过程，程序从源代码到最终在计算机上执行，经历了编译、链接、加载等多个步骤。每一步都在确保程序能够正确、有效地运行。

宏内核与微内核

宏内核 (Monolithic Kernel)

概念

宏内核是一种操作系统架构，其中所有的操作系统服务都运行在内核空间，包括进程管理、内存管理、文件系统、设备驱动、网络协议等。

特点

单一的大块内核：所有操作系统服务在一个内核空间中运行。
性能高：由于所有服务在内核空间内运行，无需频繁的上下文切换和进程间通信。
复杂性高：由于内核庞大且复杂，开发和维护变得困难。
安全性低：内核空间中的错误可能会影响整个系统，增加了系统崩溃的风险。

优点

高效性：系统调用和服务之间的通信速度快，因为所有服务都在同一个地址空间中。
成熟度：大多数传统操作系统（如Linux、UNIX）采用宏内核结构，经过长期优化和改进，性能和稳定性较高。

缺点

可靠性差：由于所有服务在内核空间运行，一个服务的崩溃可能导致整个系统崩溃。
扩展性差：添加新功能或更新现有功能可能会导致整个内核的重新编译和测试，开发周期长。

微内核 (Microkernel)

概念

微内核是一种操作系统架构，其中只有最基本的操作系统服务运行在内核空间，而其他服务（如设备驱动、文件系统、网络协议等）运行在用户空间，通过消息传递进行通信。

特点

小而精简的内核：内核只包含最基本的功能，如进程间通信、基本的内存管理和CPU调度。
模块化设计：操作系统的其他服务作为用户态进程运行，相互独立，通过消息传递进行通信。
安全性高：由于服务运行在用户空间，内核空间受到保护，一个服务的错误不会影响整个系统。
扩展性好：可以方便地添加或更新服务，而无需对内核进行大规模修改。

优点

稳定性：一个服务的崩溃不会导致整个系统崩溃，只需重启该服务即可。
安全性：由于服务运行在用户空间，内核空间受到更好的保护，减少了系统被攻击的风险。
灵活性：服务模块化设计，便于扩展和维护，可以根据需要动态加载或卸载服务。

缺点

性能低：由于需要频繁的消息传递和上下文切换，导致系统调用的开销较高。
复杂性高：需要设计高效的进程间通信机制和故障恢复机制，增加了开发难度。

比较

特性	宏内核	微内核
内核大小	大	小
服务位置	内核空间	用户空间
性能	高	低
安全性	低	高
稳定性	低	高
扩展性	差	好
复杂性	高	高
代表系统	Linux、UNIX	MINIX、QNX、L4

结论

宏内核和微内核各有优缺点，适用于不同的应用场景。宏内核由于其高效性和成熟度，广泛应用于通用操作系统。而微内核由于其高安全性和稳定性，适用于需要高可靠性和可扩展性的系统，如嵌入式系统和实时操作系统。选择哪种架构需要根据具体的应用需求和系统设计目标来决定。

Unikernel

Unikernel 是一种轻量级、专用的操作系统架构，将应用和操作系统内核打包在一起，形成一个独立的、最小化的运行环境。以下是关于 Unikernel 的详细说明：

Unikernel 特点

专用内核：每个应用都有自己的专用内核，这个内核只包含运行该应用所需的最小功能。
高效性：由于去除了不必要的操作系统功能，Unikernel 的运行效率更高，启动速度更快，资源占用更少。
安全性：最小化的内核减少了攻击面，使得系统更加安全。
易于部署：Unikernel 可以直接部署在虚拟机或云平台上，简化了部署过程。

Unikernel 的架构比较

从图中可以看到三种不同的架构：

Linux Container (共享内核)
- 多个容器共享同一个操作系统内核。
- 容器之间的隔离依赖于操作系统内核的机制。
- 优点：资源共享，开销小。
- 缺点：隔离性不强，内核攻击面大。
Container per VM (每个虚拟机一个容器)
- 每个容器运行在一个独立的虚拟机中，每个虚拟机都有自己的内核。
- 增强了容器之间的隔离性。
- 优点：隔离性强。
- 缺点：内核重复，资源开销大。
Unikernels (专用内核)
- 每个应用都有自己的专用内核，所有的内核功能都与应用紧密集成。
- 提供了高度专用和优化的运行环境。
- 优点：高效、启动快、资源占用少、安全性高。
- 缺点：开发和调试复杂，通用性较差。

Unikernel 的优势

性能优化：Unikernel 通过去除不必要的操作系统功能，减少了系统开销，提升了性能。
快速启动：由于内核体积小，Unikernel 的启动时间通常只有几毫秒。
安全性增强：最小化的内核减少了漏洞的数量和攻击面，提高了系统的安全性。
资源利用率高：Unikernel 仅包含应用所需的功能，极大地降低了资源消耗。

Unikernel 的应用场景

云计算：在云环境中，Unikernel 可以快速启动和销毁实例，提供更灵活的资源管理。
嵌入式系统：由于其高效性和专用性，Unikernel 非常适合资源受限的嵌入式设备。
微服务架构：在微服务架构中，Unikernel 可以为每个微服务提供一个最小化的运行环境，提高整体系统的性能和安全性。

Unikernel 通过其专用内核和最小化设计，提供了高效、安全和灵活的运行环境，适用于云计算、嵌入式系统和微服务架构等多种场景。然而，由于其开发和调试复杂性，Unikernel 目前更多地应用在特定领域，需要权衡应用需求和系统复杂性。

lesson 3 中断，异常

中断、异常和系统调用详解

源头

中断：由外设引发的事件（如键盘输入、网络数据到达等）。
异常：由应用程序执行意想不到的行为引发的事件（如除零错误、非法内存访问等）。
系统调用：由应用程序请求操作系统服务时引发的事件（如文件操作、进程控制等）。

响应方式

中断：异步处理。中断信号可以在任何时候发生，打断当前执行的代码，转而执行中断处理程序。
异常：同步处理。异常发生时，处理器暂停当前执行的指令，立即执行异常处理程序。
系统调用：可以是异步或同步处理。应用程序发起系统调用时，处理器切换到内核模式，执行相应的系统服务。

处理机制

中断：
- 机制：中断处理程序（ISR）持续执行，处理完成后返回到被打断的程序。
- 特点：对应用程序透明，处理完中断后继续执行应用程序。
异常：
- 机制：异常处理程序处理错误，根据错误类型决定是终止程序还是重新执行。
- 特点：异常通常导致程序终止或重新执行，以防止错误扩散。
系统调用：
- 机制：系统调用处理程序等待或持续执行，处理完成后返回结果给应用程序。
- 特点：应用程序主动请求操作系统服务，处理完成后继续执行。

Linux 系统中的中断

中断处理原则

在中断处理过程中做尽量少的事：中断处理程序应尽可能快速地处理关键任务，然后立即返回，避免长时间占用 CPU。
推迟非关键行为：将非关键的处理推迟到中断处理程序返回之后进行，以减少中断处理程序的执行时间。

中断处理结构

中断处理在 Linux 中分为两部分：上半部（Top Half）和下半部（Bottom Half）。

Top Half（上半部）
- 功能：执行中断处理程序的最小部分，快速处理关键任务，如确认中断信号、保存必要的状态信息等。
- 目标：做最少的工作后立即返回，将大部分工作推迟到下半部处理。
Bottom Half（下半部）
- 功能：处理推迟的非关键任务，这些任务可以在中断处理程序返回之后执行，通常包括数据处理、通知其他进程等。
- 实现方式：
  - Softirq：软件中断，通常用于处理高优先级任务，如网络数据包处理。其主要作用包括：
    - 提高系统效率：通过将复杂的处理推迟到稍后执行，软中断减少了硬件中断处理程序的执行时间，从而提高了系统的整体响应效率。
    - 并发处理：软中断是可重入的，可以在多个CPU上同时执行，这提高了系统的并发处理能力。
    - 分担工作负载：将需要大量计算或需要较长时间处理的任务从硬件中断中剥离出来，在稍后的时间点执行，避免阻塞系统的正常运行。
  - Tasklets：一种基于软中断的机制，用于处理低优先级任务。
  - Work Queue：工作队列，用于将任务推迟到内核线程中执行，可以在内核的调度机制下运行。
  - Kernel Thread：内核线程，处理一些复杂的任务，允许在进程上下文中执行，可以休眠和阻塞。

中断处理程序能否在被中断的用户进程的栈上运行？

答案

不，中断处理程序不应在被中断的用户进程的栈上运行。

原因分析

栈的完整性和安全性：
- 用户栈损坏：在用户进程的栈上运行中断处理程序可能导致用户栈的损坏。中断处理程序可能需要大量的栈空间，这可能会覆盖用户栈中的数据。
- 安全问题：用户栈位于用户空间，可以被用户进程操控。如果允许内核代码（中断处理程序）在用户栈上运行，可能会带来安全漏洞。
权限级别的分离：
- 内核模式和用户模式：在受保护的操作系统（如Linux）中，内核空间和用户空间有明确的分离。内核运行在特权模式下，而用户进程运行在非特权模式下。使用用户栈进行内核操作会违反这种分离，可能会影响系统的稳定性和安全性。
一致性和控制：
- 使用内核栈：在Linux中，每个进程除了用户栈之外还有一个单独的内核栈。当进程进行系统调用或被中断时，系统会切换到内核栈。这保证了内核对其执行环境的完全控制，并在不同上下文之间保持一致性。
中断处理机制：
- 专用内核栈：在中断发生时，CPU会从用户栈切换到内核栈，然后执行中断处理程序。这种机制旨在保护用户空间和内核空间的完整性，确保中断处理程序能够安全高效地执行。

lesson 4 进程

进程在内存中的布局

概述

进程在内存中的布局主要分为内核空间和用户空间两部分。每个部分都有特定的用途和管理方式，确保进程能够高效、安全地运行。

详细说明

内核空间（Kernel Space）
- 地址范围：0xC0000000 - 0xFFFFFFFF
- 大小：1GB
- 内容：包括内核代码、内核数据结构、内核栈、内核模块等。所有进程共享这部分地址空间，用于处理系统级的操作。
栈（Stack）
- 地址范围：紧邻内核空间下方
- 大小：1GB（取决于系统配置）
- 功能：用于存储函数调用信息、局部变量、函数参数和返回地址。栈从高地址向低地址增长。
内存映射区（Mmap）
- 功能：用于存储通过内存映射机制映射的文件或设备的内存区域。通常用于动态库和共享内存等。
堆（Heap）
- 地址范围：栈下方，向高地址增长
- 大小：2GB（取决于系统配置）
- 功能：用于动态内存分配，通过malloc、calloc等函数在运行时分配内存。堆从低地址向高地址增长。
未初始化数据段（.bss）
- 功能：存储未初始化的全局变量和静态变量。这些变量在程序开始执行前会自动初始化为零。
已初始化数据段（.data）
- 功能：存储已初始化的全局变量和静态变量。这些变量在程序加载时会被初始化为预定义的值。
代码段（.text）
- 地址范围：最低地址
- 功能：存储程序的执行代码。通常为只读，防止代码被意外修改。
  进程内存布局总结

进程在内存中的布局按照从低地址到高地址的顺序依次排列不同的段，每个段有其特定的功能和用途：

代码段：存储程序执行代码。
数据段：存储已初始化和未初始化的全局变量和静态变量。
堆：用于动态内存分配。
内存映射区：用于存储内存映射文件或设备。
栈：存储函数调用信息和局部变量。
内核空间：用于系统级操作和数据结构。

这种内存布局方式确保了进程的有序执行和内存的高效管理，同时提供了安全隔离，防止不同进程间的相互干扰。

进程的状态

进程在其生命周期中会经历多个状态转换，每个状态表示进程当前的执行情况。以下是5状态进程模型的详细说明：

进程状态

新建 (new)
- 描述：进程正在创建过程中，还未被操作系统接纳。
- 转换：当进程创建完成并被操作系统接纳后，进入就绪状态。
就绪 (ready)
- 描述：进程已准备好运行，但尚未被分配到CPU。
- 转换：
  - 调度分派 (scheduler dispatch)：当调度程序选择该进程执行时，转换到运行状态。
  - 中断 (interrupt)：如果运行的进程被中断，也可能返回到就绪状态。
运行 (running)
- 描述：进程正在CPU上执行。
- 转换：
  - I/O或事件等待 (I/O or event wait)：如果进程需要等待I/O操作或某个事件，转换到等待状态。
  - 退出 (exit)：当进程完成或被终止时，转换到终止状态。
  - 中断 (interrupt)：如果进程被中断，可能转换到就绪状态。
等待 (waiting)
- 描述：进程正在等待某个事件（如I/O操作）完成。
- 转换：
  - I/O或事件完成 (I/O or event completion)：当等待的事件完成后，转换到就绪状态。
终止 (terminated)
- 描述：进程已完成执行或被操作系统终止。
- 转换：此状态是最终状态，进程不会再进行任何状态转换。

状态转换详细说明

从新建到就绪
- 转换条件：进程创建完成并被操作系统接纳，等待被调度执行。
从就绪到运行
- 转换条件：调度程序选择进程执行，进程获得CPU时间片。
从运行到等待
- 转换条件：进程需要等待I/O操作或其他事件完成，主动放弃CPU。
从运行到就绪
- 转换条件：进程被中断（例如时间片耗尽），需要重新排队等待CPU。
从等待到就绪
- 转换条件：进程等待的I/O操作或事件完成，重新排队等待CPU。
从运行到终止
- 转换条件：进程完成所有任务或被操作系统终止，进入终止状态。

操作系统中的表

在操作系统中，内存表、I/O表、文件表和进程表是用于管理和跟踪系统资源和进程状态的重要数据结构。以下是每种表的详细说明：

内存表 (Memory Table)

功能：

管理和跟踪系统内存的使用情况。

内容：

空闲内存块：记录系统中未分配的内存块，方便分配内存给新进程或需要更多内存的进程。
已分配内存块：记录已分配给各个进程的内存块，包括进程ID、内存块的起始地址和大小等信息。
页表/段表：用于虚拟内存管理，记录进程的虚拟地址与物理地址的映射关系。

示例：

页表（Page Table）：每个进程都有一个页表，记录该进程的虚拟内存页到物理内存页的映射。
段表（Segment Table）：每个进程都有一个段表，记录该进程的各个段（如代码段、数据段、堆栈段）在物理内存中的位置。

I/O表 (I/O Table)

功能：

管理和跟踪系统的I/O设备及其状态。

内容：

I/O设备状态：记录每个I/O设备的状态（如空闲、忙碌等）。
I/O请求队列：记录等待某个I/O设备完成的I/O请求。
I/O缓冲区：记录各个I/O设备的输入输出缓冲区，用于暂存数据。

示例：

磁盘I/O表：记录每个磁盘的状态，当前正在处理的请求以及等待队列中的请求。
网络I/O表：记录每个网络接口卡的状态、发送和接收队列等信息。

文件表 (File Table)

功能：

管理和跟踪系统中的文件和文件系统的使用情况。

内容：

文件描述符：记录每个打开文件的文件描述符及其对应的文件信息。
文件位置指针：记录每个打开文件的当前读写位置。
文件属性：记录文件的属性信息，如文件大小、权限、创建和修改时间等。
打开文件计数：记录每个文件当前被多少个进程打开。

示例：

全局文件表：记录系统中所有打开文件的信息。
进程文件表：每个进程有一个文件表，记录该进程打开的文件及其文件描述符。

进程表 (Process Table)

功能：

管理和跟踪系统中所有进程的状态和信息。

内容：

进程ID：每个进程的唯一标识符。
进程状态：记录每个进程的当前状态（如就绪、运行、等待、挂起等）。
进程优先级：记录每个进程的优先级，用于调度。
CPU寄存器状态：记录每个进程在切换时的CPU寄存器状态，以便恢复执行。
内存信息：记录每个进程使用的内存信息，如页表、段表等。
打开文件：记录每个进程打开的文件及其文件描述符。
I/O信息：记录每个进程的I/O请求和I/O设备使用情况。

示例：

系统进程表：记录系统中所有进程的信息。
任务控制块（TCB）：每个进程的具体信息都存储在一个任务控制块中，操作系统通过进程表管理这些TCB。

PCB（进程控制块）

定义

进程控制块 (Process Control Block, PCB) 是操作系统用于存储和管理进程信息的关键数据结构。每个进程都有一个对应的PCB，操作系统通过PCB来跟踪和控制进程的执行。

内容

PCB包含了一个进程的所有关键信息，可以分为以下几类：

进程标识信息：
- 进程ID (PID)：进程的唯一标识符。
- 父进程ID (PPID)：父进程的标识符，用于构建进程层次结构。
进程状态信息：
- 进程状态：如新建、就绪、运行、等待、挂起等。
- 优先级：进程的优先级，用于调度决定。
处理器状态信息：
- 程序计数器 (PC)：指示进程下一条要执行的指令地址。
- CPU寄存器内容：包括通用寄存器、栈指针、程序状态字等，保存进程的运行状态。
内存管理信息：
- 基址寄存器和界限寄存器：用于确定进程的内存区域。
- 页表或段表：用于虚拟内存管理，记录虚拟地址到物理地址的映射。
调度信息：
- 进程调度队列指针：指向进程在调度队列中的位置。
- 进程优先级：调度时参考的优先级信息。
资源分配信息：
- 打开文件列表：进程打开的所有文件及其文件描述符。
- I/O设备列表：进程正在使用的I/O设备及其状态。
- 其他资源：如信号量、消息队列等资源的使用信息。
会计信息：
- CPU使用时间：记录进程运行所消耗的CPU时间。
- 记账信息：包括进程启动时间、累计运行时间、资源使用统计等。

作用

PCB在操作系统中具有以下重要作用：

进程管理：
- 操作系统通过PCB跟踪和管理所有进程的状态和信息，实现对进程的控制和调度。
上下文切换：
- 当进程切换时，操作系统会保存当前进程的上下文信息到PCB中，并从下一个进程的PCB中恢复其上下文信息，保证进程切换的正确性。
资源分配：
- PCB记录了进程所使用的资源信息，操作系统通过这些信息进行资源的分配和回收，确保资源的合理利用。
错误处理和调试：
- PCB提供了丰富的进程信息，操作系统可以根据这些信息进行错误处理和系统调试，提高系统的可靠性和稳定性。
进程间通信：
- PCB中记录的资源和状态信息为进程间通信提供了基础，操作系统可以基于这些信息实现进程间的协调与数据交换。

孤儿进程 (Orphan Process)

定义

孤儿进程是指其父进程已经终止，但它本身仍在运行的进程。孤儿进程将被系统中的init进程（PID为1）收养，以确保其资源能够被正常回收。

特征

父进程终止：
- 孤儿进程的父进程已经终止，导致其失去了父进程的管理和控制。
被init进程收养：
- 在Unix和Linux系统中，init进程会收养所有的孤儿进程，并负责它们的善后处理，如回收其资源、处理其退出状态等。
进程树结构变化：
- 孤儿进程的出现会使进程层次结构从一棵树变成一片森林，因为原本连接在一起的进程被打断了。

原因

父进程异常终止：
- 父进程因某些错误或意外情况终止，而其子进程仍在继续运行。
父进程正常终止：
- 父进程在完成其工作后正常终止，但其子进程尚未完成工作，继续运行。

处理

资源回收：
- 孤儿进程在终止后，由init进程回收其资源，确保系统资源不会被浪费。
退出状态处理：
- 孤儿进程的退出状态由init进程处理，避免僵尸进程的产生。

在 Windows 操作系统中，孤儿进程的处理机制与 Unix/Linux 系统有所不同，但也有一些相似之处。以下是关于孤儿进程在 Windows 中处理的详细说明：

特征

父进程终止：
- 孤儿进程的父进程已经终止，但它本身仍在运行，没有被终止。
孤儿进程继续运行：
- 在 Windows 中，孤儿进程不会被系统自动终止，它们会继续运行直到它们自己完成或被显式终止。

处理

系统不会自动收养孤儿进程：
- 与 Unix/Linux 系统中的 init 进程不同，Windows 系统没有专门的进程来收养孤儿进程。孤儿进程不会被重新分配到系统中的其他进程。
资源管理：
- 孤儿进程在 Windows 中仍然由操作系统管理，它们的资源（如内存、句柄等）会被正常管理和回收，当孤儿进程终止时，其资源会被操作系统回收。
进程监控：
- 管理员可以使用任务管理器或其他系统监控工具查看和管理系统中的孤儿进程。如果需要，管理员可以手动终止这些进程。

使用 `fork()` 创建子进程的典型程序

以下是一个使用 fork() 系统调用来创建子进程的典型 C 程序。fork() 是 Unix/Linux 系统中常用的系统调用，用于创建一个新进程。新创建的进程是原进程的副本，被称为子进程。通过这个程序，可以更好地了解子进程创建的过程。

程序代码

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>

int main() {
    pid_t pid;

    // 创建子进程
    pid = fork();

    if (pid < 0) {
        // fork() 失败
        fprintf(stderr, "Fork Failed\n");
        return 1;
    } else if (pid == 0) {
        // 子进程执行的代码
        printf("This is the child process. PID: %d\n", getpid());
        printf("Child process sleeping for 2 seconds...\n");
        sleep(2); // 子进程休眠2秒
        printf("Child process exiting...\n");
    } else {
        // 父进程执行的代码
        printf("This is the parent process. PID: %d\n", getpid());
        printf("Parent process waiting for child process to complete...\n");
        wait(NULL); // 父进程等待子进程完成
        printf("Child process completed. Parent process exiting...\n");
    }

    return 0;
}

vfork() 与 fork() 类似，用于创建一个子进程。但与 fork() 不同，vfork() 创建的子进程会共享父进程的地址空间，直到子进程调用 exec() 或 exit()。在此期间，父进程会被挂起，直到子进程调用 exec() 或 exit()。

使用 `execl()` 系统调用执行新程序

程序代码示例

#include <stdio.h>
#include <unistd.h>

int main(void) {
    printf("before execl ...\n");
    execl("/bin/ls", "/bin/ls", NULL);
    printf("after execl ...\n");
    return 0;
}

程序解释

包含头文件：
- #include <unistd.h>：POSIX 操作系统 API 的头文件，包含 execl 函数。
主函数：
- printf("before execl ...\n");：在调用 execl 之前，打印一条消息。
- execl("/bin/ls", "/bin/ls", NULL);：调用 execl 执行 /bin/ls 程序。
  - 第一个参数是要执行的程序的路径。
  - 第二个参数是新程序的名称（通常与路径相同）。
  - 最后一个参数是参数列表的结束标志，必须是 NULL。
- printf("after execl ...\n");：在调用 execl 之后打印一条消息。

运行结果和原因

运行结果显示：

$ ./exec_example
before execl ...
exec_example
exec_example.c
$

输出解释：

before execl ... 消息被打印：
- 这表示程序在调用 execl 之前的部分正常执行。
after execl ... 消息未被打印：
- 因为 execl 成功调用后，当前进程的地址空间被新程序的地址空间替换。当前程序从这个时刻起完全变成了新程序 /bin/ls，并开始执行新程序的代码。因此，execl 后的代码不会被执行。
终止原因：
- execl 系统调用替换了当前进程的地址空间，如果成功执行，当前进程的代码和数据将被新程序的代码和数据完全替换，当前进程的执行不会再回到原程序的 execl 调用后面。相反，如果 execl 失败，返回 -1 并设置 errno，那么 printf("after execl ...\n"); 将会被执行。

fork() + exec*() + wait() = system()

进程间通信模型

(a) 共享内存

进程 A 和进程 B 通过共享内存区域进行通信。
特点：
- 共享内存提供了一个共同的内存区域，供多个进程读写。
- 进程可以通过读写共享内存区域来交换数据。
- 需要同步机制（如信号量）来管理对共享内存的并发访问，避免数据竞争和不一致。

(b) 信息传递

进程 A 和进程 B 通过消息队列进行通信。
特点：
- 消息队列是一种链表结构，存储由多个消息组成的队列。
- 进程可以将消息发送到消息队列中，或从消息队列中接收消息。
- 消息传递方式更加结构化，适用于需要严格顺序和消息完整性的通信场景。
- 消息队列由操作系统内核管理，提供了进程间同步和数据交换的机制。
- 在多核处理器系统中，消息传递优于共享内存通信，因为没有高速缓存（Cache）一致性问题。

多核处理器系统中的优先选择

共享内存避免了多次上下文切换和消息传递的开销。
共享内存直接在进程间共享数据，效率更高。
但是存在高速缓存（Cache）一致性的问题。

管道（PIPE）

管道是一种用于进程间通信的机制，允许数据在两个进程之间传输。管道分为普通管道和命名管道。

普通管道（Anonymous Pipe）

特点：
- 单向通信：普通管道是单向的，数据只能从一端流向另一端。
- 父子关系：通常用于有亲缘关系的进程（如父子进程）之间的通信。父进程创建管道后，子进程继承管道的文件描述符。
- 不可命名：普通管道没有名字，只存在于内存中，由操作系统管理。
- 创建方式：使用 pipe() 系统调用创建普通管道。
优点：
- 实现简单，开销较小。
- 非常适合简单的进程间数据传递。
缺点：
- 只能在相关联的进程（如父子进程）之间使用。
- 只支持单向通信，如果需要双向通信，需要创建两个管道。

命名管道（Named Pipe 或 FIFO）

特点：
- 双向通信：命名管道支持双向通信，但通常实现为两个单向通道。
- 无亲缘关系要求：可以在没有亲缘关系的进程之间通信，因此更灵活。
- 可命名：命名管道存在于文件系统中，有一个路径名，可以由不相关的进程通过该路径名访问。
- 创建方式：使用 mkfifo() 系统调用创建命名管道。
优点：
- 可以用于没有亲缘关系的进程之间的通信。
- 支持在系统重启后仍然存在（因为它是文件系统的一部分）。
缺点：
- 需要文件系统支持，并占用文件系统资源。
- 实现相对复杂，系统开销较大。

普通管道

进程 A      进程 B
  |            |
  |            |
  |   pipe()   |
  |----------> |
  |  数据流动  |
  |            |

命名管道

进程 A                进程 B
  |                    |
  |                    |
  |   mkfifo()         |
  |---------------->   |
  |  数据流动         |
  |                    |

管道的使用场景

普通管道：
- 父子进程间的简单数据传输。
- 实现命令管道，例如在 shell 中使用管道符 |。
命名管道：
- 需要在无亲缘关系的进程间传递数据的场景。
- 持久化的数据传输需求，例如日志服务和数据采集应用。

客户机-服务器系统中的通信

套接字（Socket）

定义：套接字被定义为通信的端点，是网络通信中的基本操作单元。
作用：用于在不同主机之间进行数据传输，通过 IP 地址和端口号的结合实现通信。

远程过程调用（RPC）

定义：远程过程调用（Remote Procedure Call, RPC）是一种通过网络执行代码的机制，允许程序调用位于远程系统上的过程或函数。
作用：简化了网络通信，使得分布式计算更加便捷。

套接字详细说明

IP地址和端口的串联：套接字由 IP 地址和端口号组成，包含在消息包开头的数字，用于区分主机上的网络服务。例如：
- 套接字 161.25.19.8:1625 引用主机 161.25.19.8 上的端口 1625。
通信对：通信由一对套接字组成，即一个套接字用于发送数据，另一个套接字用于接收数据。
端口号：
- 1024以下的端口号通常用于标准服务（如 HTTP 使用端口 80，HTTPS 使用端口 443）。
- 特殊 IP 地址 127.0.0.1（环回地址）用于表示正在运行进程的本地系统。

套接字通信示意图

套接字通信：

[Process A] -- Socket A: Port 1234 -- IP 192.168.1.1 -- Network -- IP 192.168.1.2 -- Socket B: Port 5678 -- [Process B]

客户端-服务器模型

客户端：
- 发送请求到服务器的应用程序。
- 通过创建套接字连接到服务器，发送请求并等待响应。
服务器：
- 接收客户端请求并提供相应服务的应用程序。
- 通过监听特定端口上的连接请求，处理请求并返回结果。

示例：HTTP 请求

客户端：
- 创建套接字并连接到服务器的 IP 地址和端口（如 80）。
- 发送 HTTP 请求，例如 GET / HTTP/1.1。
- 接收服务器的响应数据。
服务器：
- 在端口 80 上监听连接请求。
- 接收并解析客户端的 HTTP 请求。
- 生成并发送 HTTP 响应数据。
套接字：是网络通信的基础，通过 IP 地址和端口号实现不同主机之间的数据传输。
远程过程调用（RPC）：简化了分布式系统中的过程调用，使得程序能够调用远程系统上的函数。
客户机-服务器模型：客户机发送请求，服务器处理请求并返回结果，是网络应用程序的常见结构。

Lesson 5 线程

线程

定义：线程是 CPU 调度的基本单位。

线程的状态

线程只包含运行时的状态：
- 动态部分由进程提供。
- 包括执行所需的最小状态（主要是寄存器和栈）。

线程与进程的关系

一个进程可以包含多个线程：
- 每个线程共享同一地址空间（方便数据共享和交互）。
- 允许进程内并行执行。

线程的组成部分

线程包含：
- 线程 ID
- 程序计数器
- 寄存器
- 堆栈

线程共享的资源

线程与其他线程共享：
- 代码段
- 数据段
- 其他操作系统资源

总结

线程是进程内的基本调度单元，允许并发执行。
线程共享进程的资源，但有独立的运行状态信息。
多线程的设计有助于提高程序的并发性和响应速度。
多线程的优点

响应性：
- 如果部分线程被阻塞，仍可以继续执行。这对于用户界面设计尤为重要，能提供快速响应。
资源共享：
- 线程共享进程资源，比进程共享内存或消息传递更容易。允许一个应用程序在同一地址空间内有多个不同的活跃线程，方便数据共享和交互。
经济性：
- 比进程创建更便宜，线程切换比上下文切换开销更低。进程创建是线程创建的几倍，进程切换比线程切换慢 5 倍。
可扩展性（可伸缩性）：
- 线程可以利用多核体系结构，提高程序的并行处理能力和性能。

Amdahl 定律

定律公式

Amdahl 定律用于确定在具有串行和并行组件的应用程序中，通过增加处理器数量（计算核心）所获得的性能增益。

公式： [\text{speedup} \leq \frac{1}{S + \frac{(1-S)}{N}}] 其中，S 是串行部分，N 是处理器核心数量。

解释

S 是串行部分：程序中无法并行化的部分。
N 是处理器核心数量：增加的计算核心数。

性能提升

当 N 接近无穷大时，加速比接近 1/S。
应用程序的串行部分对通过增加额外计算核心而获得的性能提升有着不成比例的影响。

线程控制块（TCB）

线程控制块（Thread Control Block，TCB）是操作系统用于管理线程的结构，与进程控制块（PCB）结构类似。

组成部分

Thread ID：
- 线程标识符，唯一标识一个线程。
Thread state：
- 线程状态，表示线程当前的运行状态（如运行、就绪、阻塞等）。
CPU information：
- Program counter：
  - 程序计数器，指示线程下一条将要执行的指令的位置。
- Register contents：
  - 寄存器内容，保存线程运行所需的寄存器值。
Thread priority：
- 线程优先级，用于调度时确定线程的优先级顺序。
Pointer to process that created this thread：
- 指向创建此线程的进程的指针。
Pointer(s) to other thread(s) that were created by this thread：
- 指向由该线程创建的其他线程的指针。

作用

TCB 保存了线程的所有运行信息，便于操作系统对线程进行调度和管理。
在线程上下文切换时，操作系统会保存当前线程的 TCB，并加载下一个线程的 TCB，以恢复其运行状态。
TCB 是实现多线程并发执行的重要数据结构。

类比 PCB

在 Linux 中，进程与线程使用的是同一种数据结构 task_struct，上下文切换中会使用到。
PCB 和 TCB 都是操作系统管理进程和线程的重要数据结构，保存了进程和线程的所有必要信息。

用户级线程与内核级线程

用户级线程（User-Level Threads）

定义：
- 线程管理由用户级库（而不是内核）处理。
- 线程的创建、调度和同步在用户空间中完成。
优点：
- 高效：线程操作（如创建和切换）不需要内核的干预，因此开销较低，速度较快。
- 灵活：用户可以实现自己的线程调度算法，满足特定应用需求。
缺点：
- 缺乏内核支持：内核对用户级线程不可见，导致系统调用等操作不会自动阻塞其他用户级线程。
- 单核限制：由于内核只看到一个进程，多个用户级线程不能在多核系统中并行执行。
常见实现：
- POSIX 线程库（Pthreads）的一些实现可以作为用户级线程使用。

内核级线程（Kernel-Level Threads）

定义：
- 线程管理由内核直接支持。
- 线程的创建、调度和同步由内核完成。
优点：
- 真正并行：多个线程可以在多处理器或多核系统上并行执行，因为内核对每个线程都进行调度。
- 阻塞处理：一个线程的阻塞不会影响同一进程内的其他线程，内核能有效管理资源。
缺点：
- 高开销：线程操作（如创建和切换）涉及内核的系统调用，开销较大。
- 复杂性：内核需要维护更多的上下文信息，增加了内核的复杂性和负担。
常见实现：
- 大多数现代操作系统，如 Linux 和 Windows，都支持内核级线程。

用户级线程与内核级线程的比较

特性	用户级线程	内核级线程
创建与销毁	快速，用户空间完成	慢，涉及内核系统调用
上下文切换	快速，用户空间完成	慢，涉及内核系统调用
并行性	受限于单个内核	可在多核系统上真正并行
阻塞处理	线程阻塞会导致整个进程阻塞	一个线程阻塞不影响其他线程
开发复杂度	高，需要用户管理线程调度和同步	较低，内核负责线程调度和同步
调度灵活性	高，用户可以实现自定义调度算法	较低，依赖内核调度
资源利用	受限，无法充分利用多处理器资源	高效，充分利用多处理器资源

总结

用户级线程：适用于需要快速线程操作且不依赖多核并行的场景，具有高效和灵活的特点，但在处理阻塞和多核利用上有局限。
内核级线程：适用于需要高并行性和内核管理的场景，能充分利用多处理器资源，但线程操作开销较大，复杂性较高。

Lesson 6 进程调度

为什么需要调度

进程执行包含 CPU 执行和 I/O 执行

进程的执行：
- 每个进程的执行都包含两个部分：CPU 执行和 I/O 执行。
CPU 执行时间与频率的关系：
- CPU 执行时间与频率之间的关系形成指数或超指数分布。
- 从分布上看，有大量短 CPU 执行和少量长 CPU 执行。
不同类型的进程：
- I/O 密集型程序：通常是大量短 CPU 执行，频繁进行 I/O 操作。
- CPU 密集型程序：通常是少量长 CPU 执行，较少进行 I/O 操作。

需要调度的原因

多任务处理：
- 由于系统中存在多个进程和线程，需要通过调度来合理分配 CPU 资源，确保各任务能得到公平和有效的处理。
提高系统效率：
- 通过调度，可以在一个进程进行 I/O 操作时，将 CPU 分配给其他需要执行的进程，从而提高系统整体的运行效率。
响应时间：
- 合理的调度策略可以确保高优先级任务能够及时得到处理，改善系统的响应时间，提高用户体验。

调度算法的作用

调度算法的设计旨在根据进程的类型和执行需求，合理安排 CPU 的使用，优化系统性能和资源利用。
常见的调度算法包括：先来先服务（FCFS）、最短作业优先（SJF）、轮转法（Round Robin）、多级反馈队列（Multilevel Feedback Queue）等。

总结

调度是操作系统管理进程和线程的重要功能，旨在通过合理分配 CPU 资源，提高系统的效率和响应速度。根据进程的不同执行需求，采用合适的调度算法能够优化系统性能，确保多任务环境下的稳定运行。

进程调度算法

1. 先来先服务（First-Come, First-Served, FCFS）

特点：
- 按照进程到达的顺序进行调度。
- 非抢占式调度。
优点：
- 实现简单。
- 公平性好，所有进程按照到达顺序依次执行。
缺点：
- 可能导致较长的等待时间，特别是当一个长进程在前面时（称为“长进程问题”）。
- 容易出现“饥饿”现象，即短进程可能需要等待较长时间。

2. 短作业优先（Shortest Job First, SJF）

特点：
- 优先调度执行时间最短的进程。
- 非抢占式调度。
优点：
- 可以最小化平均等待时间。
缺点：
- 实现较复杂，需要知道或估计每个进程的执行时间。
- 容易出现“饥饿”现象，即长作业可能会被短作业无限推迟。

3. 最短剩余时间优先（Shortest Remaining Time First, SRTF）

特点：
- 优先调度剩余时间最短的进程。
- 抢占式调度。
优点：
- 可以进一步优化SJF算法的性能。
缺点：
- 实现复杂，需要不断更新和比较进程的剩余时间。
- 同样容易出现“饥饿”现象。

4. 时间片轮转（Round Robin, RR）

特点：
- 每个进程分配一个固定的时间片，时间片结束后切换到下一个进程。
- 抢占式调度。
优点：
- 响应时间较好，所有进程都能公平地获得CPU时间。
缺点：
- 时间片的选择非常重要，时间片过长会退化为FCFS，时间片过短会导致频繁切换，增加开销。

5. 优先级调度（Priority Scheduling）

特点：
- 每个进程分配一个优先级，优先级高的进程优先调度。
- 可以是非抢占式或抢占式调度。
优点：
- 可以灵活地根据进程的重要性进行调度。
缺点：
- 可能导致低优先级进程的“饥饿”。
- 需要设计合理的优先级分配策略。

6. 多级反馈队列（Multilevel Feedback Queue, MLFQ）

特点：
- 使用多个队列，每个队列有不同的优先级和调度策略。
- 新进程进入高优先级队列，执行时间长的进程逐渐降低优先级。
- 抢占式调度。
优点：
- 综合了多种调度算法的优点，可以适应不同类型的进程。
- 既能保证短进程的响应时间，又能防止长进程“饥饿”。
缺点：
- 实现复杂，需要合理设置队列数目和调度策略。

7. 最短响应比优先（Highest Response Ratio Next, HRRN）

特点：
- 计算每个进程的响应比，响应比=（等待时间+服务时间）/服务时间，选择响应比最高的进程调度。
- 非抢占式调度。
优点：
- 平衡了等待时间和服务时间，可以有效减少平均等待时间。
缺点：
- 需要计算响应比，增加了调度开销。

8. 抢占式调度（Preemptive Scheduling）

特点：
- 当前进程运行时，可以被更高优先级或更紧急的进程打断。
优点：
- 能够更好地响应高优先级进程的需求。
缺点：
- 增加了调度的复杂度和上下文切换的开销。

9. 非抢占式调度（Non-Preemptive Scheduling）

特点：
- 当前进程运行时，直到进程主动放弃CPU或结束，才会进行下一次调度。
优点：
- 实现简单，调度开销较低。
缺点：
- 对高优先级进程的响应较慢。

调度层次

1. 短期调度（Short Term Scheduling）

目标：将进程从就绪队列（Ready Queue）中调度到 CPU 执行。
频率：高频调度，几乎在每一次时钟中断时进行。
涉及状态：Running（运行）、Ready（就绪）、Blocked（阻塞）。
作用：决定哪个进程在下一个时间片内获得 CPU。

2. 中期调度（Medium Term Scheduling）

目标：实现多道程序设计，通过挂起和激活进程来平衡系统的负载。
频率：中等频率调度，根据系统负载和内存状态决定。
涉及状态：Blocked, Suspend（阻塞并挂起）、Ready, Suspend（就绪并挂起）。
作用：将部分进程从内存移到外存（挂起），或者将外存中的进程重新加载到内存（激活），以优化内存的使用。

3. 长期调度（Long Term Scheduling）

目标：控制系统中进程的总数，决定何时创建新进程。
频率：低频调度，通常在进程创建或终止时进行。
涉及状态：New（新）、Exit（终止）。
作用：决定系统允许的并发进程数，以平衡系统性能和响应时间。

调度过程

新进程（New）：通过长期调度决定是否将新进程引入系统，并转移到就绪状态（Ready）。
就绪状态（Ready）：短期调度决定哪个就绪进程获得 CPU，转移到运行状态（Running）。
运行状态（Running）：在时钟中断或其他中断（如 I/O 请求）时，进程可能转移到阻塞状态（Blocked）或返回就绪状态（Ready）。
阻塞状态（Blocked）：等待 I/O 完成或其他事件完成，完成后转移到就绪状态（Ready）。
挂起状态（Suspend）：中期调度决定将部分阻塞或就绪进程挂起，释放内存资源。
终止状态（Exit）：进程完成执行或被终止，转移到终止状态（Exit）。

总结

调度层次包括短期调度、中期调度和长期调度，分别处理进程的即时执行、内存管理和进程总数控制。合理的调度机制能够提高系统的效率和响应速度，确保多任务环境下的稳定运行。

调度类型及其原因

新进程被创建（A new process is created）
- 调度类型：短期调度（Short-Term Scheduling）
- 原因：当一个新进程通过 fork() 创建时，调度器需要立即决定是继续运行父进程还是运行新创建的子进程。这是因为短期调度负责在短时间内管理 CPU 的分配，使得 CPU 不会空闲，确保系统的响应速度。
现有进程终止（An existing process is terminated）
- 调度类型：短期调度（Short-Term Scheduling）
- 原因：当一个进程终止时，它所占用的 CPU 被释放。调度器需要快速选择另一个进程来运行，以确保 CPU 的高效利用。这也是短期调度的职责所在，旨在尽快为空闲的 CPU 分配一个新的进程。
进程等待 I/O（A process waits for I/O）
- 调度类型：短期调度（Short-Term Scheduling）
- 原因：当一个进程在等待 I/O 操作时，它会释放 CPU。调度器需要立即选择另一个准备好运行的进程来利用这段时间，避免 CPU 资源的浪费。因此，这属于短期调度的工作范围。
进程完成 I/O 等待（A process finishes waiting for I/O）
- 调度类型：中期调度（Medium-Term Scheduling） 或 短期调度（Short-Term Scheduling）
- 原因：当一个进程完成 I/O 操作后，它从等待状态转为准备就绪状态，可能需要被调度回 CPU。如果系统中的内存资源紧张，中期调度器可能会决定将一些进程挂起以腾出内存空间。这时，中期调度负责进程的挂起与激活操作。而短期调度负责在进程被激活后，将其分配到 CPU 上运行。因此，具体调度类型取决于当前系统资源的情况以及调度策略。

抢占式调度和非抢占式调度

抢占式调度

定义：抢占式调度是指操作系统能够在进程正在运行时中断它，并强制将 CPU 分配给另一个进程。
特点：
- 实时响应：抢占式调度能够迅速响应高优先级任务，提高系统的实时性。
- 公平性：通过周期性地重新分配 CPU 时间片，确保所有进程都有机会运行，防止某些进程长时间占用 CPU。
- 复杂性：实现较为复杂，需要操作系统维护一个进程优先级队列，并在适当的时候进行进程切换。
适用场景：适用于多任务操作系统，尤其是需要实时响应的系统，如操作系统内核、服务器操作系统。
优点：
- 能够快速响应高优先级任务，提高系统的实时性和响应速度。
- 能够防止低优先级任务长期占用 CPU 资源，保证系统的公平性。
缺点：
- 由于频繁的上下文切换，可能导致系统开销增加，影响整体性能。
- 实现复杂，增加了操作系统设计和维护的难度。

非抢占式调度

定义：非抢占式调度是指一旦进程获得 CPU 控制权，它将一直运行到自行释放 CPU 或进入等待状态才会放弃 CPU。
特点：
- 简单性：实现较为简单，不需要频繁的上下文切换。
- 低开销：由于没有频繁的进程切换，系统开销较低。
- 不可预测性：如果一个进程长时间不释放 CPU，其他进程可能会长时间等待，导致系统响应速度变慢。
适用场景：适用于简单的操作系统或嵌入式系统，如批处理系统、一些实时操作系统。
优点：
- 实现简单，调度开销低，适用于简单的操作系统或嵌入式系统。
- 不需要频繁进行上下文切换，系统开销小。
缺点：
- 可能导致低优先级进程长时间得不到执行，降低系统的响应速度和公平性。
- 对于需要实时响应的系统，可能无法满足其要求。

比较

抢占式调度：
- 优点：实时性好，公平性高，适合多任务操作系统。
- 缺点：实现复杂，系统开销大。
非抢占式调度：
- 优点：实现简单，系统开销小。
- 缺点：实时性差，公平性低。

实例

抢占式调度：
- 时间片轮转（Round-Robin）调度算法
- 多级反馈队列调度算法
非抢占式调度：
- 先来先服务（First-Come, First-Served，FCFS）调度算法
- 最短作业优先（Shortest Job Next，SJN）调度算法（非抢占版本）

调度准则

在设计调度算法时，需要仔细考虑以下几个关键的性能指标：

CPU利用率（CPU Utilization）：
- 定义：指CPU在执行非空闲任务时所占用的时间百分比。
- 目标：最大化CPU的利用率，使CPU尽可能处于工作状态，而不是空闲状态。
吞吐量（Throughput）：
- 定义：单位时间内完成的进程数量。
- 目标：最大化吞吐量，提升系统的整体处理能力。
周转时间（Turnaround Time）：
- 定义：从进程提交到进程完成所经历的时间，包括等待时间、执行时间和I/O时间。
- 目标：最小化周转时间，使进程尽快完成。
等待时间（Waiting Time）：
- 定义：进程在就绪队列中等待被调度的总时间。
- 目标：最小化等待时间，减少进程在就绪队列中的等待时间。
响应时间（Response Time）：
- 定义：从进程提交到系统首次响应的时间，即从提交到开始执行的时间。
- 目标：最小化响应时间，提高系统对用户请求的响应速度。

性能比较

在所有调度算法中，如果选择下一个任务的服务时间与服务时间无关，那么遵循以下关系式：

[ \frac{T_r}{T_s} = \frac{1}{1 - \rho} ]

其中：

( T_r )：周转时间或驻留时间，即进程在系统中的总时间，包括等待时间和执行时间。
( T_s )：平均服务时间，即进程在运行状态下所花费的平均时间。
( \rho )：处理器利用率。

多线程多核处理器

多线程的两种方法

细粒度多线程：
- 多线程在更细粒度级别上（通常是指令周期）切换线程。
- 线程之间的切换很小，能够充分利用处理器资源。
- 优点：能够有效减少处理器空闲时间，提高处理器利用率。
- 缺点：线程切换频繁，开销较大。
粗粒度多线程：
- 线程一直在处理器上执行，直到一个长延迟时间如内存停顿发生。
- 线程之间的切换成本高，适合在长时间不需要切换的场景。
- 优点：线程切换开销较小，适合长时间运行的任务。
- 缺点：在等待I/O操作时，处理器资源可能被浪费。

多线程多核处理器调度

两级调度：
- 一个级别由操作系统调度，负责整体资源的分配和管理。
- 另一个级别是指定每个核心如何运行哪个硬件线程，进行更细粒度的调度。
- 这种分层调度方式能够更有效地管理多核处理器上的多线程，提高系统的整体性能和响应速度。

硬实时系统和软实时系统

硬实时系统

定义：硬实时系统是指那些必须在严格的时间限制内完成任务的系统。任何任务的延迟都可能导致系统的失败。
特点：
- 时间严格性：任务必须在规定的时间内完成，超时将导致系统不可接受的后果。
- 确定性：系统的行为是可预测的，任务的执行时间是确定的。
- 高可靠性和高安全性：系统必须具备高可靠性和安全性，以保证任务在规定时间内完成。
- 优先级调度：任务通常根据优先级进行调度，高优先级任务会抢占低优先级任务的资源。
应用场景：
- 航空航天系统（如飞行控制系统）
- 医疗设备（如心脏起搏器）
- 工业控制系统（如自动化生产线）
- 导弹制导系统

软实时系统

定义：软实时系统是指那些任务在规定的时间内完成是理想的，但偶尔的延迟是可以接受的，不会导致系统的失败。
特点：
- 时间灵活性：任务在规定时间内完成是理想的，但允许偶尔超时。
- 非确定性：任务的执行时间可能不确定，但系统会尽量在规定时间内完成任务。
- 适度的可靠性和安全性：系统需要具备一定的可靠性和安全性，但不如硬实时系统严格。
- 调度策略多样性：可以使用多种调度策略，如轮转调度、优先级调度等。
应用场景：
- 多媒体系统（如视频播放、音频处理）
- 电信系统（如电话交换系统）
- 网络服务（如网页服务器、电子邮件服务器）
- 在线交易系统

区别总结

时间要求：硬实时系统需要严格的时间限制，而软实时系统则允许一定的灵活性。
任务调度：硬实时系统通常使用优先级调度，高优先级任务可以抢占低优先级任务；软实时系统可以使用多种调度策略。
系统可靠性：硬实时系统对可靠性和安全性要求较高，而软实时系统相对较低。
应用领域：硬实时系统应用于关键任务场景，如航空航天和医疗设备；软实时系统应用于对时间要求较低的场景，如多媒体和网络服务。

Lesson 7 同步

临界区问题

临界区问题是多线程或多进程系统中的一个重要问题，旨在确保多个进程在访问共享资源时不会相互干扰。以下是几种解决临界区问题的方法及其特点：

1. 禁用中断（Disabling Interrupts）

方法：在进入临界区之前禁用中断，离开临界区后重新启用中断。
优点：简单易行，能有效防止中断过程中的竞争条件。
缺点：
- 效率低下：禁用中断会影响系统的响应时间，降低整体效率。
- 不适用于多处理器系统：在多处理器系统中禁用中断并不能解决问题，因为其他处理器仍可以访问临界区。

2. 严格交替法（Strict Alternation）

方法：使用一个共享的变量来严格控制进程交替进入临界区。
优点：确保每个进程轮流进入临界区，避免了冲突。
缺点：
- 违反需求：严格交替的方式可能不符合实际应用需求，导致系统效率低下。
- 忙等待（Busy Waiting）：进程在等待进入临界区时会一直占用CPU资源，造成资源浪费。

3. Peterson算法（Peterson’s Solution）

方法：使用两个共享变量和一个标志变量，确保两个进程不会同时进入临界区。
优点：理论上能在两个进程的情况下确保互斥。
缺点：
- 优先级倒置（Priority Inversion）：低优先级进程可能会阻塞高优先级进程的执行。
- 忙等待：进程在等待进入临界区时会一直占用CPU资源。

4. 互斥锁（Mutex Lock）

方法：使用互斥锁（mutex）来控制进程对临界区的访问。
优点：
- 易于实现：大多数操作系统都提供了对互斥锁的支持。
- 提高并发性：互斥锁能有效管理多个进程对临界区的访问。
缺点：
- 原子性实现（Atomicity Implementation）：需要确保互斥锁操作的原子性，这可能需要硬件支持。
- 忙等待：如果使用自旋锁（spinlock），等待过程会消耗CPU资源。

信号量（Semaphore）

信号量是一种用于进程同步的机制，通过引入一个计数器来控制对共享资源的访问。信号量可以分为两类：计数信号量和二进制信号量。

信号量的类型

计数信号量（Counting Semaphore）
- 定义：计数信号量可以取任意非负整数值，主要用于控制多个资源的并发访问。
- 特点：计数信号量的初始值通常设置为可用资源的数量，每当一个进程请求资源时，计数器减1；当一个进程释放资源时，计数器加1。
二进制信号量（Binary Semaphore）
- 定义：二进制信号量的取值只有0和1，类似于互斥锁，用于实现对临界区的互斥访问。
- 特点：二进制信号量的初始值通常设置为1，表示资源可用；当进程进入临界区时，信号量值变为0，表示资源被占用；当进程离开临界区时，信号量值恢复为1。

信号量的操作

信号量通常提供两个原子操作：wait（P操作）和signal（V操作）。

P操作（wait）
- 描述：如果信号量的值大于0，则将其减1；如果信号量的值为0，进程进入等待状态，直到信号量值大于0。
- 伪代码：
```
wait(S):
    while S <= 0:
        wait
    S = S - 1
```
V操作（signal）
- 描述：将信号量的值加1；如果有进程在等待信号量，将唤醒一个等待的进程。
- 伪代码：
```
signal(S):
    S = S + 1
```

信号量的应用

互斥（Mutual Exclusion）
- 使用二进制信号量来保护临界区，确保同时只有一个进程能进入临界区。
- 伪代码示例：
```
// 初始化信号量
semaphore mutex = 1;

// 进程进入临界区
wait(mutex);
// 临界区代码
signal(mutex);
```
同步（Synchronization）
- 信号量可用于进程间的同步，确保某些操作按特定顺序执行。
- 例如：进程B必须在进程A执行完某些操作之后才能执行。
- 伪代码示例：
```
// 初始化信号量
semaphore sync = 0;

// 进程A
// 执行操作
signal(sync);  // 通知进程B

// 进程B
wait(sync);  // 等待进程A的通知
// 执行操作
```

资源管理（Resource Management）

计数信号量用于控制对有限资源的访问，例如固定数量的数据库连接。

伪代码示例：

// 初始化信号量
semaphore resource = N;  // N为资源数量

// 请求资源
wait(resource);
// 使用资源
signal(resource);  // 释放资源

经典同步问题

有界缓冲区同步问题（生产者-消费者问题）

生产者-消费者问题描述的是两个或多个进程间如何共享一个固定大小的缓冲区，其中一个进程称为生产者，负责生产数据并放入缓冲区，另一个进程称为消费者，负责从缓冲区取出数据进行处理。关键问题在于：

生产者不能在缓冲区满时放入数据；
消费者不能在缓冲区为空时取出数据。

解决方案

使用信号量：一个信号量表示缓冲区中空闲空间的数量，另一个信号量表示缓冲区中已填满的空间数量，再使用一个互斥量保护对缓冲区的访问。

读者写者同步问题

读者写者问题描述的是多个进程同时读写共享数据时如何同步，确保数据一致性。关键问题在于：

多个读者可以同时读数据；
写者进行写操作时，不允许其他进程（读者或写者）进行读或写操作。

解决方案

使用读写锁（Read-Write Lock）：读写锁允许多个读者同时读数据，但在写者进行写操作时，其他读者和写者都必须等待。

哲学家就餐问题

哲学家就餐问题描述的是五个哲学家围坐在圆桌旁，每人面前有一根筷子和一个盘子。哲学家需要两根筷子才能开始进餐。关键问题在于：

如何防止死锁；
如何避免饥饿（某个哲学家永远无法进餐）。

解决方案

使用信号量或互斥锁：通过对筷子的访问进行控制，确保每次只有一个哲学家能够拿到两根筷子。

Lesson 8 并发：死锁，饥饿

死锁的必要条件

互斥

一次只有一个进程可以使用一个资源，其他进程不能访问分配给其他进程的资源。

占有并等待

当一个进程已经占有了资源并等待其他进程时，继续占有已分配的资源。

不可抢占

资源不能被强制抢占，进程必须在自愿释放资源后，其他进程才能使用该资源。

循环等待

存在一个闭合的进程链，每个进程至少占有此链中下一个进程所需的一个资源。

死锁的可能性

以上四个条件同时满足时，系统中可能会发生死锁。

死锁预防

预防策略

预防死锁的策略包括通过打破死锁的四个必要条件之一，来避免死锁的发生。主要策略有：

破坏互斥条件

让多个进程共享可重用资源，即尽可能减少对互斥资源的需求。
例如：共享读访问权限的文件，允许多个进程同时读取。

破坏占有并等待条件

进程在请求资源时，必须一次性请求所有需要的资源，或者在持有资源时不再请求其他资源。
例如：所有资源一次性分配，或者使用资源时释放掉当前占有的资源。

破坏不可抢占条件

允许操作系统强制抢占资源，如果一个进程请求的资源不可用，可以强制撤销进程占有的资源。
例如：当一个进程请求高优先级资源时，可以强制抢占低优先级进程的资源。

破坏循环等待条件

通过对资源类型进行线性排序，并要求进程按序请求资源，防止形成循环等待。
例如：对资源编号，进程必须按编号顺序请求资源，或者每次只能请求一个资源，且在请求下一个资源前必须释放所有已占有的资源。

其他策略

资源分配图：通过绘制资源分配图，检测循环依赖，避免死锁的发生。
银行家算法：在资源分配时，根据进程的最大需求计算安全序列，确保系统始终处于安全状态。

实施预防策略的代价

增加系统复杂性和开销。
可能导致资源利用率降低，系统吞吐量减少。
在实际系统中，通常结合避免和检测死锁的方法，共同防止死锁。

银行家算法

定义

银行家算法是一种用于死锁避免的资源分配算法，主要用于多道程序设计系统中，确保系统在资源分配时始终处于安全状态。（轮询）

基本概念

资源分配矩阵 (Allocation Matrix)：表示每个进程当前占有的资源数量。
最大需求矩阵 (Max Matrix)：表示每个进程对各类资源的最大需求。
需求矩阵 (Need Matrix)：表示每个进程尚未满足的资源需求，计算公式为：Need[i][j] = Max[i][j] - Allocation[i][j]。（可用于判断是否有可能出现死锁）
可用资源向量 (Available Vector)：表示系统当前可用的各类资源数量。

安全状态

系统在某一资源分配状态下，如果能够按某种顺序为所有进程分配资源，使得每个进程都能够顺利完成，那么系统就是安全的。

Lesson 9 内存管理

段错误（Segmentation Fault）

段错误是一种常见的运行时错误，通常在程序试图访问未分配或受保护的内存区域时发生。内存中的各个部分被称为段（Segment），每个段有不同的用途和访问权限。以下是关于段错误的详细笔记：

段错误的原因：

非法访问内存：程序试图读取或写入未分配的内存地址。
越界访问数组：访问数组时超过其定义的范围。
访问空指针：试图通过未初始化或已释放的指针进行内存访问。
栈溢出：递归调用过多导致栈内存耗尽。
无效指针算术：使用无效指针进行算术运算后访问内存。

内存段划分：

栈（Stack）：
- 用于存储局部变量和函数调用信息。
- 栈的大小是有限的，通常是向下增长。
堆（Heap）：
- 用于动态内存分配，程序运行时使用malloc、calloc、realloc等函数分配。
- 堆的大小可以动态扩展，通常是向上增长。
数据段和BSS段（Data Segment & BSS）：
- 数据段存储已初始化的全局变量和静态变量。
- BSS段存储未初始化的全局变量和静态变量，初始值为0。
代码段和常量（Code & Constant）：
- 存储程序的机器指令和常量值。
- 代码段通常是只读的，以防止程序运行时被意外修改。

内存管理

内存管理是操作系统的重要功能之一，负责管理计算机内存的分配和回收，以确保程序能够顺利执行。以下是内存管理的详细笔记：

内存的基本概念

程序加载：
- 程序必须从磁盘加载到内存中才能运行。
- 主存储器和寄存器是CPU可以直接访问的唯一存储器。
内存访问：
- 内存单元可以接收地址和数据进行读写操作。
- 地址 + 读取请求：从指定地址读取数据。
- 地址 + 数据和写入请求：将数据写入指定地址。

内存访问的细节

寄存器访问：
- 寄存器访问在一个CPU时钟周期内完成。
主内存访问：
- 主内存访问可能会占用多个时钟周期，导致CPU暂停（stall）。
缓存（cache）：
- 缓存位于主内存和CPU寄存器之间，加快内存访问速度。
硬件实现：
- 硬件负责确保内存访问的速度和操作的正确性，保护操作系统和程序的内存。

内存分配策略

连续分配：
- 单一连续块的内存分配，适用于简单的系统。
分页（Paging）：
- 将内存分割成固定大小的页（Page），每个页有一个对应的页表（Page Table）。
分段（Segmentation）：
- 将内存分割成不同大小的段（Segment），每个段代表程序中的逻辑部分，如代码段、数据段、堆栈段。
分页与分段结合：
- 结合分页和分段的优点，提供更灵活的内存管理方式。

内存保护与共享

内存保护：
- 使用硬件机制确保程序只能访问分配给它的内存，防止非法访问。
内存共享：
- 允许多个程序共享同一段内存，提高内存使用效率。

内存回收

显式回收：
- 程序显式地释放不再使用的内存。
隐式回收：
- 由操作系统自动进行内存回收，如垃圾回收机制（Garbage Collection）。

内存管理的挑战

内存碎片：
- 内存使用过程中，可能会产生未连续的空闲内存块，导致碎片化。
多任务处理：
- 操作系统需有效管理多任务间的内存分配，确保各任务独立运行。

指令和数据绑定到内存

地址绑定的三种不同阶段

编译时（Compile Time）：
- 如果内存位置已知，则可以生成绝对代码。如果程序的起始位置改变，则必须重新编译代码。
加载时（Load Time）：
- 如果编译时内存位置未知，则必须生成可重定位代码（relocatable code）。这意味着程序在加载到内存时，可以放置在任意位置。
执行时间（Execution Time / Run Time）：
- 如果进程在执行期间可以从一个内存段移动到另一个内存段，则绑定延迟到运行时。此时需要硬件支持地址映射，如基寄存器和限幅寄存器。

内存管理单元（MMU）

作用

内存管理单元（Memory Management Unit，MMU）是一种硬件设备，用于在运行时将虚拟地址映射到物理地址。

工作原理

CPU生成逻辑地址（虚拟地址）：
- 当CPU执行指令时，会生成逻辑地址，这些地址是程序的虚拟地址空间的一部分。
MMU将逻辑地址转换为物理地址：
- MMU接收到CPU生成的逻辑地址，并通过内部的映射表将其转换为物理地址。
- 映射表通常由操作系统维护，并存储在主内存中。
- MMU使用这些映射表将逻辑地址转换为物理地址。
物理地址访问物理内存：
- 经过MMU转换后的物理地址被用来访问物理内存中的实际存储位置。

映射过程

页表：MMU通常使用页表（Page Table）来管理虚拟地址到物理地址的映射。页表包含了虚拟页号和物理页框号的对应关系。
TLB（Translation Lookaside Buffer）：MMU内部的高速缓存，用于存储最近使用的页表条目，加速地址转换过程。
基地址寄存器和限幅寄存器：用于支持简单的段式内存管理，基地址寄存器存储段的起始地址，限幅寄存器存储段的长度。

优势

虚拟内存支持：MMU使得操作系统能够实现虚拟内存，允许进程使用比实际物理内存更大的地址空间。
内存保护：通过MMU，操作系统可以设置不同的访问权限，保护内存区域，防止进程之间的相互干扰。
内存共享：MMU支持多个进程共享相同的物理内存区域，例如共享库。

碎片管理

外部碎片

定义：存在满足请求的总内存空间，但它不是连续的。
例子：操作系统中分配和释放内存后，内存中形成的很多小块，这些小块无法合并成一个大块。

内部碎片

定义：分配的内存可能略大于请求的内存；此大小差异是分区内部的内存，但未被使用。
例子：当进程请求的内存量不正好等于一个分区的大小时，分区内部未使用的部分就形成了内部碎片。

选择合适的分配算法

首次适应：从头开始搜索第一个足够大的空闲块并分配。
最优适应：搜索整个空闲链表，找到最小的足够大的空闲块进行分配。
影响：不同的分配策略会影响碎片的数量和内存的利用效率。

首次适应算法的分析

给定分配的N个块，0.5N个块因碎片而丢失：
- 通常情况下，内存中的1/3可能无法使用。
- 50%规则：大约50%的空闲内存会被外部碎片所占据，导致内存利用率降低。

碎片管理总结

碎片问题是内存管理中的一个重要问题，合理选择内存分配算法可以减少碎片，提高内存利用率。
外部碎片和内部碎片都是内存管理中的常见问题，需要通过有效的策略来减少对系统性能的影响。

分段（Segment）

概述

程序和其相关的数据划分到几个段（segment）
- 所有段的长度不一定相等；
- 段有最大长度；
逻辑地址由两部分构成：
- 段号
- 偏移量

特点

分段类似于动态分区；
需要将程序的所有分段都装入内存；
一个程序占据多个分区，并且这些分区不要求是连续的；
消除了内部碎片，但会产生外部碎片。

详细解释

优点：灵活性高，方便数据共享和保护，可以根据程序需求动态调整段的大小。
缺点：容易产生外部碎片，需要复杂的内存管理机制。

分段管理中的问题

外部碎片：由于段是动态大小的，内存分配和释放后可能形成很多不连续的空闲空间，无法有效利用。
段表管理：段表需要额外的存储空间，并且在段表的查找和维护上也会增加系统开销。
保护与共享：需要通过段表来实现段的保护与共享，不同段可以有不同的访问权限，但这也增加了管理的复杂性。

分页

概述

进程的物理地址空间可以是不连续的；只要物理内存可用，就为进程分配物理内存。
- 避免外部碎片
- 避免了大小不一的内存块问题

细节

将物理内存划分为称为帧的固定大小的块
- 大小是2的幂，介于512字节和16MB之间
将逻辑内存划分为大小相同的块（称为页）
跟踪所有空闲帧；
要运行大小为N页的程序，需要找到N个空闲帧并加载程序；
设置页表以将逻辑地址转换为物理地址；
备份存储区（磁盘）同样拆分为多个页面；
仍然有内部碎片；

详细解释

页表：每个进程有一个页表，用于记录每一页在物理内存中的位置。页表中每个条目对应一页，包含物理帧的地址。（存在有效位）
逻辑地址到物理地址的转换：
- 逻辑地址：由页号和页内偏移量组成；
- 页号用来索引页表，得到物理帧的基址；
- 页内偏移量加上物理帧的基址，得到物理地址。
内部碎片：由于每个页面和帧的大小固定，可能会出现分配给页面的内存有未使用的部分，导致内部碎片。
外部碎片：分页技术有效避免了外部碎片的问题，因为进程的页可以放置在内存的任意空闲帧中，不要求连续。

散列页表（哈希页表）

概述

公共地址空间>32位；
虚拟页码散列到页表中：
- 虚拟页码作为哈希值，此页表包含散列到同一位置的元素链；
每个元素都包含：
- 虚拟页码；
- 映射的页帧码；
- 指向下一个元素的指针；

搜索匹配项

在链中比较虚拟页码以搜索匹配项：
- 如果找到匹配，则提取相应的物理帧；
- 如果不匹配，查找链表的下一个元素；

64位地址的变体：聚簇页表

与哈希页表类似，但每个条目引用多个页面（如16页），而不是1页；
特别适用于稀疏地址空间（内存引用不连续且分散）；

倒排页表

概述

与其每个进程都有一个页表并跟踪所有可能的逻辑页，不如跟踪所有物理页；
内存的每一物理页有一个条目；
条目由存储在该实际内存位置的页的虚拟地址以及有关拥有该页的进程的信息组成；

优点

减少存储每个页表所需的内存，但在发生页引用时增加搜索表所需的时间；
使用哈希表将搜索限制为一页或最多几页的表项：
- TLB可以加速访问；

挑战

共享内存实现：
- 虚拟地址到共享物理地址的一种映射。

lesson 10 虚拟内存管理

虚拟内存概述

示例程序解析

在这段程序中，父进程和子进程都有一个名为 pid 的变量，并且它们的地址相同，但值不同。这是因为每个进程都有自己的虚拟地址空间，即使变量名相同，它们也不会相互影响。

int main(void) {
    int pid;
    pid = fork();
    printf("PID %d: %p.\n", getpid(), &pid);
    if(pid)
        wait(NULL);
    return 0;
}

输出结果展示了两个不同进程中的同一个变量地址，但是值不同：

$ ./same_addr
PID 1234: 0xbfe85e0c.
PID 1235: 0xbfe85e0c.

结果解释

两个不同的进程，变量名相同，但值不同。
使用相同的地址（即变量 pid 的地址相同）。

内存地址的意义

逻辑地址：即虚拟内存地址。进程使用的地址是逻辑地址，需要通过地址转换才能得到物理地址。
地址转换：逻辑地址或虚拟地址需要转换成物理地址才能访问实际的内存。
虚拟内存的使用：虚拟内存提供了一种抽象，使得每个进程都认为自己独占整个内存空间，提高了内存利用率和系统安全性。

虚拟内存

虚拟内存：将用户逻辑内存与物理内存分离的一种内存管理技术。

部分程序执行：只有部分程序需要在内存中才能执行。
逻辑地址空间大于物理地址空间：逻辑地址空间可以比物理地址空间大得多，这使得程序可以使用更多的内存。
多进程共享：多个进程可以共享同一个逻辑地址空间。
高效进程创建：虚拟内存允许更高效的进程创建，因为不需要每个进程都实际占用物理内存。
多任务处理：虚拟内存支持更多程序同时运行，提升系统的并发能力。
减少I/O操作：虚拟内存技术通过延迟加载或交换部分内存内容，减少了I/O操作的频率，提高了系统性能。

虚拟内存通过地址映射机制，将逻辑地址动态转换为物理地址，确保进程间的隔离和安全性。

虚拟地址空间

进程如何存储在内存中的逻辑视图：
- 通常从地址0开始，连续地址直到空间结束。
- 物理内存按页帧组织，分配给进程的物理页帧可以不连续。
- 内存管理单元 (MMU) 将逻辑页映射到物理页帧。

虚拟内存的实现方式

请求分页 (Demand Paging)：仅在需要时将页面加载到物理内存中。
按需分段 (Segmented Paging)：按需将段加载到物理内存中，提供更灵活的内存管理。

处理缺页

步骤

检查内部表：
- 内部表通常与PCB（进程控制块）一起保存，用于确定内存引用是否有效。
无效引用处理：
- 如果引用无效，终止进程。
- 如果引用有效但未调入页面，那么发生缺页中断。
查找空闲帧：
- 在内存中找到一个空闲的页帧，用于存储所需的页面。
磁盘操作：
- 通过磁盘调度操作将页面从磁盘交换到刚分配的页帧中。
重置表项：
- 磁盘操作读取完成后，重置内部表和页表，指示当前页面在内存中。
重新启动进程：
- 重新启动导致缺页的指令，使进程能够访问所需的页面。

请求分页的性能

主要活动

在请求分页中，有三个主要的活动需要进行：

处理中断：
- 当发生缺页中断时，必须处理该中断。精心编写的代码意味着只需要几个百个指令即可完成处理。
读取页面：
- 从磁盘读取页面需要大量时间，因为磁盘I/O操作相对较慢。
重新启动进程：
- 再次重新启动导致缺页的进程，这需要很少的时间。

页面错误率 (Page Fault Rate)

页面错误率表示在访问内存时发生缺页错误的概率，范围是0到1之间：

( p = 0 ) 时，没有页面错误。
( p = 1 ) 时，每次内存引用都会导致页面错误。

有效访问时间 (Effective Access Time, EAT)

有效访问时间表示在存在页面错误的情况下，访问内存的平均时间。其计算公式为：

内存访问时间 (memory access time)：假设内存访问时间为m，在没有缺页错误时，访问内存的时间为m。
页面错误开销 (page fault overhead)：处理缺页错误的额外时间，假设为pf。
换出页面时间 (swap page out time)：将一个页面换出到磁盘的时间，假设为sw_out。
换入页面时间 (swap page in time)：将一个页面从磁盘换入内存的时间，假设为sw_in。

将这些因素代入公式中，可以得到EAT的具体计算：

[ EAT = (1 - p) \times m + p \times (pf + sw_out + sw_in) ]

写时复制 (Copy-on-Write, CoW)

定义

写时复制（CoW）是一种资源管理技术，允许多个进程共享相同的资源，直到其中一个进程尝试修改资源。此时，会为尝试修改的进程创建资源的副本，从而确保每个进程都有其私有的资源副本。

优点

共享初始页面：
- 在使用CoW时，父进程和子进程最初共享内存中的相同页面。
- 如果任一进程修改了共享页面，该页面会被复制，这样每个进程都有自己的副本。
提高进程创建效率：
- CoW允许更高效的进程创建（例如fork()），因为只有在需要修改页面时才复制页面。
- 通常，空间页面是从按需填充的页面池中分配的。
页面池的使用：
- 页面池应始终具有用于快速请求页面执行的空闲帧。
- 不希望必须释放一个帧及其他处理页面错误的时间。

页面初始化

空间页面通常是从按需填充的页面池中分配的。
为什么在分配页面之前将其归零？清除之前的内容，确保安全性和一致性。

`vfork()` 系统调用

vfork()是fork()的一个变体，父进程挂起，子进程使用父进程的地址空间，不采用写时复制。因此，父进程可以看到子进程的修改。
- 设计目的：用于子进程调用exec()的情况。
- 效率高：不需要复制内存页面。

写时复制的详细过程

进程创建：
- 父进程调用fork()创建子进程，子进程初始时共享父进程的内存页面。
页面标记为只读：
- 共享的页面被标记为只读，以便在任一进程尝试修改时触发页面错误。
页面错误处理：
- 当进程尝试写入共享页面时，会触发页面错误。
- 操作系统捕获页面错误，并分配一个新的物理页面。
页面复制：
- 操作系统将原始页面的内容复制到新页面。
- 更新页表，使进程指向新的物理页面。
恢复执行：
- 进程重新执行导致页面错误的指令，现在可以写入其私有的页面副本。

总结

写时复制是一种有效的资源管理策略，特别是在进程创建和内存管理中，能够提高系统效率并减少资源浪费。同时，vfork()提供了一种高效的进程创建方式，适用于特定场景。

页面和帧置换算法

帧分配算法

目标：决定每个进程需要分配多少帧（物理内存块）。
要考虑的问题：
- 每个进程需要多少帧？
- 当内存不足时，需要更换哪些页帧？

页面置换算法

目标：最小化页面置换错误率。
希望实现的效果：
- 第一次访问页面和重新访问页面的页面错误率最低。

评估页面置换算法的方法

引用字符串：
- 引用字符串是指特定内存访问序列中的页面码。
- 页面码只是页码，而不是完整地址。
页面错误计算：
- 重复访问同一页面不会导致页面错误。
- 页面错误的结果取决于可用的帧数。

常见的页面置换算法

先进先出（FIFO）算法：
- 最简单的页面置换算法。
- 根据页面进入内存的顺序来进行置换。
- 当需要置换页面时，最先进入内存的页面将被替换。
- 有Belady异常
最近最久未使用（LRU）算法：
- 选择最近最久未使用的页面进行置换。
- 通过追踪每个页面的使用情况来确定最久未使用的页面。
最不常用（LFU）算法：
- 选择使用次数最少的页面进行置换。
- 通过记录每个页面的使用次数来确定置换页面。
最优（Optimal）算法：
- 理想状态下的置换算法。
- 选择将来最长时间内不会被访问的页面进行置换。
- 实际实现困难，因为需要预测未来的页面访问情况。

近似 LRU（Least Recently Used）

定义

近似 LRU 是一种用于替代完全 LRU 算法的页面置换算法，目的是在减少实现复杂度和开销的同时，尽可能接近 LRU 算法的效果。

原理

完全 LRU 算法需要记录每个页面最近被访问的时间，开销较大。因此，近似 LRU 算法通过简化的方式，近似实现 LRU 的效果。

实现方法

二次机会算法（Second Chance Algorithm）
- 维护一个循环队列（环形缓冲区）来存储页面。
- 每个页面有一个参考位（reference bit），初始时设置为 0。
- 当页面被访问时，将参考位设置为 1。
- 页面置换时，从队列头部开始检查页面的参考位：
  - 如果参考位为 1，将其重置为 0，并将页面移到队列尾部，给予第二次机会。
  - 如果参考位为 0，则替换该页面。
时钟算法（Clock Algorithm）
- 二次机会算法的一种实现形式，页面存储在一个环形缓冲区中，指针（时钟指针）指向当前待替换的页面。
- 页面被访问时，将参考位设置为 1。
- 页面置换时，指针顺时针移动，检查页面的参考位：
  - 如果参考位为 1，将其重置为 0，指针移动到下一个页面。
  - 如果参考位为 0，则替换该页面。
增强的二次机会算法（Enhanced Second Chance Algorithm）
- 在二次机会算法的基础上，增加修改位（dirty bit），形成四种状态的组合：
  1. 参考位 = 0，修改位 = 0（最优先替换）
  2. 参考位 = 0，修改位 = 1
  3. 参考位 = 1，修改位 = 0
  4. 参考位 = 1，修改位 = 1（最不优先替换）
- 页面置换时，优先替换参考位和修改位均为 0 的页面。
NRU（Not Recently Used）算法
- 周期性地将所有页面的参考位清零。
- 置换时，随机选择一个参考位为 0 的页面。

优点

近似 LRU 算法在硬件实现和计算开销方面优于完全 LRU 算法。
保留了 LRU 算法的优点，即优先替换最近较少使用的页面，从而减少页面错误率。

缺点

近似 LRU 算法无法完全准确地记录每个页面的最近使用情况，可能导致页面置换不如完全 LRU 精确。
需要额外的硬件支持（例如参考位、修改位）和周期性操作（例如清零参考位）。

适用场景

适用于需要接近 LRU 效果但又对实现开销有较高要求的系统。
常用于操作系统的内存管理中，以提高页面置换的效率。

通过近似 LRU 算法，可以在实现复杂度和性能之间找到平衡，提高系统的整体效率。

页面缓冲算法

页面缓冲算法是一种用于优化页面置换的技术，通过利用一个空闲帧池和可能的修改页列表，提高页面置换的效率和系统性能。

主要思想

空闲帧池（Free Frame Pool）： 维护一个空闲帧池，用于快速处理页面置换而不需要立即写出修改页。
修改页列表（Modified Page List）： 记录可能被修改过的页面，以便在必要时快速写出并释放帧。

实现步骤

保持空闲帧池
- 初始化： 系统始终保持一定数量的空闲帧。
- 页面置换： 当发生缺页错误时，选择一个受害者页进行替换。
- 将受害者页移动到空闲帧池： 将受害者页移入空闲帧池，并将新的页面加载到该帧中。
- 驱逐操作： 如果需要驱逐的页面没有被修改，可以直接丢弃，不需要写回磁盘。
保留修改过的页面列表
- 记录修改页： 当一个页面被修改时，将其记录到修改页列表中。
- 延迟写回： 在空闲帧池中写入页面，并将其标记为非脏页，增加无需要写出的页面比例。
保持空闲帧池
- 标记空闲帧： 记录哪些页面存储在哪些帧中。
- 重复引用： 如果在页面再次被引用之前仍然在空闲帧池中，则无需从磁盘重新加载。
- 减少开销和损失： 如果选择错误的受害者页，有助于减少由于需要重新加载而产生的开销。

优点

快速处理缺页： 通过预先保持一定数量的空闲帧，快速处理缺页错误。
减少I/O操作： 延迟写回和记录修改页，减少写回磁盘的次数。
提高系统性能： 优化页面置换，减少由于页面置换引起的开销。

缺点

增加复杂度： 需要额外的内存来维护空闲帧池和修改页列表。
空间开销： 维护空闲帧池和修改页列表需要占用额外的内存空间。

适用场景

内存有限的系统： 通过减少I/O操作和优化页面置换，提高系统性能。
频繁页面访问的应用： 在需要频繁访问页面的应用中，通过减少缺页错误和I/O操作，提高响应速度。

页面缓冲算法通过维护一个空闲帧池和修改页列表，有效地减少页面置换的开销，提高系统性能，特别适用于内存资源紧张和需要频繁页面访问的场景。

系统抖动（Thrashing）

系统抖动是指当计算机系统过度使用虚拟内存时，系统频繁进行页面交换，导致CPU大部分时间都在进行页面调度而不是执行实际的计算任务，从而导致系统性能急剧下降的一种现象。

系统抖动的基本概念

定义： 系统抖动是由于内存不足导致频繁的页面换入换出，进而使得系统性能显著下降的现象。
原因： 当一个进程需要访问的页面数超过了分配给它的物理内存页数时，就会发生频繁的页面调度，导致系统抖动。

产生抖动的条件

高页面调度率： 系统频繁发生页面调度，使得大量时间花费在内存与磁盘之间的页面交换上。
内存不足： 物理内存不能满足当前运行进程的需求，导致频繁的页面换入换出。
多任务运行： 系统同时运行大量进程，每个进程都需要大量的内存，超出了物理内存的容量。

系统抖动的影响

性能下降： 由于大量时间花费在页面换入换出上，实际用于执行进程的时间减少，导致系统整体性能下降。
响应时间增加： 系统响应时间显著增加，用户操作的延迟变长。
系统资源浪费： 大量的I/O操作占用了系统资源，使得系统效率低下。

如何检测系统抖动

高页面错误率： 如果系统中的页面错误率非常高，可能意味着发生了抖动。
低CPU利用率： 由于大量时间用于页面调度，实际执行任务的时间减少，导致CPU利用率低。
系统响应变慢： 用户操作系统的响应速度明显变慢。

解决系统抖动的方法

增加物理内存： 最直接的方法是增加系统的物理内存，使得每个进程有足够的内存来运行。
减少同时运行的进程数量： 通过减少同时运行的进程数量来降低内存需求。
调整页面调度算法： 采用更高效的页面调度算法，如工作集模型，来减少页面调度次数。
提高页面交换速度： 使用更快速的存储设备（如SSD）来提高页面交换速度。

工作集模型

定义： 工作集模型是一种动态内存分配算法，基于进程在一段时间内的页面访问行为来决定分配给进程的内存页数。
原理： 通过跟踪进程在最近一段时间内访问的页面集合（工作集），动态调整分配给进程的内存页数，以减少页面调度次数。
优点： 有效减少系统抖动，提高系统性能。

伙伴系统（Buddy System）

伙伴系统是一种内存分配算法，用于管理计算机内存中的空闲内存块。它的基本思想是将内存分割成大小为2的幂的块，以便快速分配和释放内存。

伙伴系统的基本概念

内存分割： 内存被分割成大小为2的幂的块，称为“伙伴”。
伙伴关系： 两个块如果它们的起始地址满足特定条件（通常是相邻且大小相等），就被称为“伙伴”。
分割和合并： 内存分配时，可能需要将大块内存分割成多个小块；内存释放时，如果两个伙伴都空闲，则可以合并成一个更大的块。

伙伴系统的内存分配

请求内存： 当进程请求内存时，系统查找能够满足请求的最小的空闲块。
分割内存： 如果找到的空闲块大于请求的大小，则不断将其分割成两个相等的伙伴块，直到其中一个块的大小正好满足请求。
分配内存： 将满足请求的内存块分配给进程。

伙伴系统的内存释放

释放内存： 当进程释放内存时，系统将该内存块标记为空闲。
合并伙伴： 系统检查该内存块的伙伴是否也为空闲。如果是，则将两个伙伴合并成一个更大的块。
递归合并： 合并后的新块继续检查其新的伙伴是否也为空闲，如果是，则再次合并，直到无法再合并为止。

伙伴系统的优点

快速分配和释放： 内存分配和释放的速度很快，因为只需进行有限次数的分割和合并操作。
内存利用率高： 能够较好地利用内存，减少内存碎片。

伙伴系统的缺点

内部碎片： 由于内存块大小是2的幂，可能会导致分配的内存块比实际需要的内存块大，从而产生内部碎片。
外部碎片： 合并伙伴时，可能会因为某个伙伴块被占用而无法合并，导致外部碎片。

伙伴系统的实现细节

空闲块列表： 系统维护一组空闲块列表，每个列表存储特定大小的空闲块。
分配策略： 常用的分配策略包括首次适应（First Fit）和最佳适应（Best Fit）。
块标识： 每个块的头部通常包含块的大小和是否空闲的信息。

示例

初始状态： 假设有一个大小为64KB的空闲内存块。
请求20KB内存：
- 找到大小为64KB的块。
- 分割为两个32KB的块。
- 再次分割一个32KB块为两个16KB的块。
- 再次分割一个16KB块为两个8KB的块。
- 分割一个8KB块为两个4KB的块。
- 分割一个4KB块为两个2KB的块。
- 分配一个2KB的块和多个块以满足20KB请求。
释放内存： 释放20KB内存，合并相邻的伙伴块，直到无法再合并为止。

Lesson 11 大容量存储

存储分层

存储分层是计算机系统中内存和存储设备按照访问速度、容量和成本等因素进行的层次化组织。不同的存储层具有不同的特性，优化系统的性能和成本。

存储分层的层次

寄存器（Registers）：
- 访问速度： 非常快
- 容量： 极小
- 成本： 高
- 用途： 存储处理器当前正在使用的数据和指令
缓存（Cache）：
- 访问速度： 非常快，但比寄存器稍慢
- 容量： 小
- 成本： 高
- 用途： 存储频繁访问的数据，以减少访问主内存的延迟
主内存（Main Memory）：
- 访问速度： 快
- 容量： 中等
- 成本： 中等
- 用途： 存储当前运行的程序和数据
固态硬盘（Solid-State Disk，SSD）：
- 访问速度： 快，但比主内存慢
- 容量： 大
- 成本： 中等
- 用途： 存储需要快速访问的大量数据
硬盘（Hard Disk，HDD）：
- 访问速度： 较慢
- 容量： 大
- 成本： 低
- 用途： 存储大量数据，包括操作系统、应用程序和文件
光盘（Optical Disk）：
- 访问速度： 较慢
- 容量： 大
- 成本： 低
- 用途： 存储长期保存的数据和备份
磁带（Magnetic Tapes）：
- 访问速度： 非常慢
- 容量： 非常大
- 成本： 非常低
- 用途： 存储归档数据和长期备份

SSD 和 HDD 的对比

固态硬盘（SSD）

速度： 读取和写入速度比 HDD 快很多。
可靠性： 由于没有机械部件，更耐用且不易损坏。
噪音： 没有移动部件，运行时完全静音。
功耗： 通常比 HDD 更节能。
成本： 单位存储成本较高。

机械硬盘（HDD）

速度： 读取和写入速度比 SSD 慢。
可靠性： 有机械部件，容易受到物理损伤。
噪音： 运行时有噪音，特别是高速旋转时。
功耗： 通常比 SSD 更耗电。
成本： 单位存储成本较低，适合大容量存储。

存储分层的意义

性能优化： 通过将频繁访问的数据放置在更快的存储层，可以显著提高系统的整体性能。
成本效益： 不同存储层的组合使用，可以在性能和成本之间找到平衡点。
数据管理： 根据数据的访问频率和重要性，将其存储在不同的层次，有助于更有效地管理数据。

总结来说，存储分层通过利用不同存储设备的特性，实现了性能和成本的优化组合，提高了计算机系统的效率和灵活性。

磁盘工作机制

组成部分

盘片（Platters）：
- 磁盘的数据存储在多个盘片上，每个盘片两面都有磁道。
- 盘片围绕磁盘轴旋转。
磁道（Tracks）：
- 每个盘片面上有许多同心圆形的磁道。
- 每个磁道被分成多个扇区。
扇区（Sectors）：
- 磁道进一步分成多个扇区，扇区是磁盘上最小的存储单位。
柱面（Cylinders）：
- 同一盘片上对应的所有磁道的集合。
- 同一柱面上的磁道在不同盘片上垂直对齐。
磁头（Read/Write Heads）：
- 磁头负责读取和写入数据。
- 每个盘片面上有一个磁头，通过磁头组来移动磁头。
磁盘轴（Spindle）：
- 驱动盘片旋转的轴，连接到马达。

读取/写入过程

寻道时间（Seek Time）：
- 磁头组需要移动到目标磁道所在的位置。
- 磁头定位到期望的磁道所需的时间称为寻道时间。
旋转延迟（Rotational Latency）：
- 磁头到达目标磁道后，还需要等待目标扇区旋转到磁头下方。
- 从零扇区开始到达目标扇区的时间称为旋转延迟。
数据传输：
- 磁头定位到目标扇区后，开始读取或写入数据。

平均旋转延迟时间计算

公式： 平均旋转延迟时间 = 磁盘旋转一周时间的一半。
由于扇区的到达是随机的，所以平均旋转延迟时间是磁盘旋转一圈所需时间的一半。

总访问时间

总访问时间由以下几个部分组成：

寻道时间： 磁头移动到目标磁道所需的时间。
旋转延迟： 磁盘旋转使目标扇区到达磁头下方所需的时间。
数据传输时间： 读取或写入数据所需的时间。

了解磁盘工作机制对于优化磁盘性能和数据存储管理非常重要。通过减少寻道时间和旋转延迟，可以提高磁盘的访问效率。

易失性和非易失性内存

易失性内存（Volatile Memory）

定义：
- 易失性内存是一种在断电后数据会丢失的存储器。
- 主要用于高速访问的数据存储。
主要类型：
- 随机存取存储器（RAM, Random Access Memory）：
  - 静态随机存取存储器（SRAM, Static RAM）：
    - 使用触发器存储数据，每个存储单元由多个晶体管组成。
    - 速度快、功耗高，主要用于缓存（Cache）。
  - 动态随机存取存储器（DRAM, Dynamic RAM）：
    - 使用电容存储数据，需要周期性刷新。
    - 速度较慢、功耗较低，主要用于系统主内存（Main Memory）。
特点：
- 读写速度快，适用于需要快速访问的数据。
- 需要持续供电才能保持数据。
- 常见于计算机的主存储器和高速缓存中。
应用：
- SRAM: CPU缓存（L1, L2, L3 Cache）。
- DRAM: 计算机主内存（RAM模块）。

非易失性内存（Non-Volatile Memory）

定义：
- 非易失性内存是一种即使在断电后数据仍然保留的存储器。
- 主要用于长期数据存储。
主要类型：
- 只读存储器（ROM, Read-Only Memory）：
  - 可编程只读存储器（PROM, Programmable ROM）：
    - 一次编程，数据不可修改。
  - 可擦除可编程只读存储器（EPROM, Erasable Programmable ROM）：
    - 可通过紫外线擦除和重新编程。
  - 电可擦除可编程只读存储器（EEPROM, Electrically Erasable Programmable ROM）：
    - 可通过电信号擦除和重新编程。
- 闪存（Flash Memory）：
  - 类似EEPROM，但读写速度更快。
  - 分为NAND闪存和NOR闪存。
- 硬盘驱动器（HDD, Hard Disk Drive）：
  - 使用磁性存储介质，适用于大容量存储。
- 固态硬盘（SSD, Solid-State Drive）：
  - 使用闪存芯片存储数据，速度快、抗震性强。
特点：
- 数据持久性强，即使断电数据也不会丢失。
- 读写速度通常慢于易失性内存，但有较高的存储密度。
- 使用寿命相对较长，但写入次数有限。
应用：
- ROM: 固件存储，如BIOS。
- Flash Memory: USB闪存驱动器、存储卡、SSD。
- HDD: 大容量数据存储设备。
- SSD: 高性能数据存储设备，应用于笔记本电脑、台式机、服务器等。

比较

| 特性 | 易失性内存 | 非易失性内存 | |————–|——————|———————-| | 数据保留 | 断电后丢失 | 断电后保留 | | 读写速度 | 高 | 相对较低 | | 应用 | RAM、CPU缓存 | ROM、HDD、SSD、Flash | | 能耗 | 高（需要持续供电）| 低（断电数据保留） | | 存储密度 | 低 | 高 | | 成本 | 高 | 相对较低 |

硬盘与主机之间的连接

硬盘（包括传统HDD和SSD）通过不同的接口和总线连接到计算机主机，以便进行数据传输。以下是详细的连接方式和相关组件介绍：

1. I/O端口和接口类型

I/O端口： 硬盘通过I/O端口连接到主机，进行数据的输入和输出。
常见接口类型：
- ATA（并行ATA）： 旧式接口，传输速率较低。
- SATA（串行ATA）： 当前最常见的硬盘接口，速度较快，支持热插拔。
- eSATA： 外部SATA接口，用于外接硬盘。
- SCSI（SAS，串行SCSI）： 主要用于服务器和高性能计算，支持多设备连接和高数据传输率。
- USB： 通用串行总线，广泛用于外接存储设备。
- FC（光纤通道）： 主要用于企业存储，支持远距离高速数据传输。

2. NVMe和PCIe

NVMe（Non-Volatile Memory express）： 专为闪存存储设计的接口协议，利用PCIe（Peripheral Component Interconnect Express）总线，提供极高的数据传输速率和低延迟。
- NVMe驱动器直接连接到PCIe总线，绕过传统的存储控制器瓶颈，显著提高性能。

3. 控制器和HBA

主机控制器：
- 计算机主板上的控制器，通过总线与CPU通信，控制I/O设备的操作。
- 主机控制器将存储命令发送给硬盘的控制器。
硬盘控制器：
- 硬盘内置的电子控制器，负责具体的读写操作和数据传输。
HBA（Host Bus Adapter）：
- 主机总线适配器，提供主机与存储设备之间的数据通道。
- 常用于SCSI和FC等高性能存储系统。

4. 数据传输流程

内存映射I/O：
- 计算机通过内存映射的方式，将I/O设备的控制寄存器映射到系统内存地址空间。
- CPU可以通过内存地址直接控制I/O设备。
DMA（Direct Memory Access）：
- 直接内存访问技术，允许设备直接与系统内存进行数据交换，而无需经过CPU。
- 提高数据传输效率，减少CPU负担。

磁盘调度

磁盘调度是操作系统为了优化磁盘I/O性能，减少磁盘访问时间和提高吞吐量而采用的一系列算法。以下是一些常见的磁盘调度算法及其特点：

1. 先来先服务（FCFS, First-Come, First-Served）

算法描述： 按照请求到达的顺序进行磁盘访问。
优点： 简单易实现，公平性高。
缺点： 磁头移动距离较大，可能导致较高的平均寻道时间。

2. 最短寻道时间优先（SSTF, Shortest Seek Time First）

算法描述： 每次选择离当前磁头位置最近的请求进行服务。
优点： 减少平均寻道时间。
缺点： 可能导致饥饿现象，远端请求长时间得不到处理。

3. 扫描算法（SCAN, Elevator Algorithm）

算法描述： 磁头像电梯一样在磁盘上来回移动，按顺序处理请求，直到最远端再反向移动。
优点： 减少了平均响应时间，适合负载较均衡的环境。
缺点： 边缘请求等待时间较长。

4. 循环扫描算法（C-SCAN, Circular SCAN）

算法描述： 类似于SCAN算法，但磁头只在一个方向上移动，当达到一端后快速返回起点继续扫描。
优点： 平均响应时间更稳定，避免了SCAN算法中边缘请求的长等待时间。
缺点： 在返回起点时的寻道开销较大。

5. 循环LOOK算法（C-LOOK）

算法描述： 类似于C-SCAN，但磁头只在有请求的范围内移动，不会移动到磁盘的最边缘。
优点： 减少不必要的寻道，进一步优化响应时间。
缺点： 需要额外的逻辑来判断磁头移动范围。

6. LOOK算法

算法描述： 类似于SCAN，但磁头只在有请求的范围内移动。
优点： 减少不必要的寻道。
缺点： 实现较为复杂。

7. N-step-SCAN算法

算法描述： 将请求分为若干批次，每批次按SCAN算法处理。
优点： 提高了系统的响应时间，避免了SSTF的饥饿问题。
缺点： 批次间可能存在一定的延迟。

磁盘调度算法比较

算法	优点	缺点
FCFS	实现简单，公平	寻道时间长，效率低
SSTF	寻道时间短	可能导致饥饿
SCAN	减少了响应时间，适合负载均衡	边缘请求等待时间长
C-SCAN	平均响应时间稳定，边缘请求等待时间短	返回起点时的寻道开销大
LOOK	减少不必要的寻道	实现复杂
C-LOOK	减少不必要的寻道，响应时间稳定	实现复杂
N-step-SCAN	提高系统响应时间，避免饥饿	批次间存在延迟

磁盘调度算法的选择

1. SSTF（Shortest Seek Time First, 最短寻道时间优先）

常见性：SSTF是常见的调度算法，具有天然的吸引力。
优点：减少平均寻道时间。
缺点：可能导致饥饿现象，因为总是优先处理最近的请求，远端请求可能长期得不到处理。

2. SCAN和C-SCAN（电梯调度算法）

适用性：对于磁盘负载较大的系统性能更好。
优点：
- 减少饥饿现象，均衡处理所有请求。
- SCAN算法在一个方向上处理所有请求，到达终点后反向处理。
- C-SCAN算法在一个方向上处理所有请求，到达终点后快速返回起点，继续处理下一批请求。
缺点：仍有可能出现饥饿现象，特别是边缘请求等待时间较长。

3. Linux中的载止时间调度器

目的：为了解决饥饿问题，Linux实现了载止时间调度器。
特点：
- 维护单独的读和写队列，提供读优先级，因为进程更可能在读时阻塞而不是写时阻塞。
- 实现了四个队列：2个读取队列和2个写入队列。
  - 1个读和1个写队列按LBA（逻辑块地址）顺序排序，基本上实现了C-SCAN。
  - 1个读和1个写队列按FCFS顺序排序。
- 批量发送的所有I/O请求都按队列顺序排序。
- 每批处理后，检查FCFS中是否有任何请求早于配置的时间（默认500毫秒）。
- 如果是，将为下一批I/O选择包含该请求的LBA队列。

4. 其他调度算法

NOOP（No Operation, 不操作调度）：在RHEL 7中提供，适用于一些特定的存储设备，采用电梯调度。
CFQ（Completely Fair Queuing, 完全公平排队）：适用于需要公平调度的场景，默认值因存储设备而异。

NVM调度

特点

没有磁头或旋转延迟：NVM（非易失性存储器）没有像传统硬盘那样的磁头寻道或旋转延迟，但是仍然存在优化空间。
RHEL 7中的调度策略：
- 使用NOOP（无操作调度、电梯调度），但会合并相邻的LBA请求以提高效率。

性能

I/O性能：
- NVM的最佳I/O方式是随机I/O，传统硬盘则更适合顺序I/O。
- 使用NVM时，每秒输入/输出操作数（IOPS）要高得多，NVM的IOPS可以达到几十万次，而传统硬盘通常只有几百次。

写放大效应

问题：
- 写放大（即一次写入操作导致多次读/写操作，或者引发垃圾收集）会降低NVM的性能。
- 写放大效应导致的多次操作会增加NVM的磨损，影响其使用寿命。

总结

NVM由于没有磁头和旋转延迟，使其在随机I/O方面具有显著优势。然而，为了充分利用其高IOPS能力，需要优化调度策略（如NOOP）。同时，需要注意写放大效应对性能和寿命的影响，采取适当的措施来减少写放大效应。

存储设备管理

低级格式化或物理格式化

目的：将磁盘划分为磁盘控制器可以读写的扇区。
内容：每个扇区保存头信息、数据和纠错码（ECC）。
- 数据量：通常为512字节，但可以选择不同大小。

操作系统在磁盘上记录数据结构

必要性：为了使用磁盘保存文件，操作系统需要记录自己的数据结构。
磁盘分区：
- 将磁盘划分为一组或多组柱面，每组柱面视为逻辑磁盘。
逻辑格式化或“创建文件系统”：
- 创建文件系统，将磁盘组织成可以存储文件的结构。

提高效率的方法

分组完成I/O操作：
- 磁盘I/O在块中完成，以减少寻道时间和旋转延迟。
- 文件I/O在簇中完成，以便更有效地管理空间和提高性能。

这些过程确保磁盘可以有效地读写数据，并且操作系统可以管理文件系统的存储和检索。

交换区管理笔记

定义

目的：当DRAM不足以容纳所有进程时，用于将整个进程（交换）或页面（分页）从DRAM移动到辅助存储器。

操作系统提供交换空间管理

性能优化重要性：
- 辅助存储比DRAM慢，性能优化非常重要。
多个交换空间：
- 通常有多个交换空间，以减少任何给定设备上的I/O负载。
专用设备：
- 最好使用专用设备来处理交换。
分区或文件系统：
- 交换空间可以在原始分区中，也可以在文件系统中的文件中（为了方便添加）。

交换操作步骤

检查内存是否充足：
- 如果内存不足，将进程或页面从内存中移出。
选择交换空间：
- 选择合适的交换空间存放被移出的页面或进程。
移动数据：
- 将内存中的数据移动到交换空间中，并更新相关的映射表。
优化性能：
- 避免频繁的I/O操作，通过高效的管理策略减少性能损失。

RAID（独立磁盘冗余阵列）

RAID（Redundant Array of Independent Disks）是一种将多个物理硬盘驱动器组合在一起形成一个逻辑单元，以提高数据存储的性能和可靠性的技术。根据不同的实现方式，RAID可以分为不同的层次，每个层次具有不同的性能和可靠性特性。

RAID层次概述

RAID 0（条带化）
- 描述：数据分散在多个磁盘上，数据条带化。
- 磁盘需求：N（数据盘数量）
- 数据可用性：比单个磁盘低
- 大I/O数据传输容量：非常高
- 小I/O请求率：读写都非常高
RAID 1（镜像）
- 描述：数据镜像到另一个磁盘上。
- 磁盘需求：2N（两倍数据盘数量）
- 数据可用性：比RAID 2、3、4、5高；比RAID 6低
- 大I/O数据传输容量：比单个磁盘高，写入类似于单个磁盘
- 小I/O请求率：读请求率最高可达两倍于单个磁盘；写入类似于单个磁盘
RAID 2（汉明码校验）
- 描述：通过汉明码实现冗余。
- 磁盘需求：N + m（数据盘数量加上冗余校验盘数量，m与logN成比例）
- 数据可用性：比单个磁盘高得多；与RAID 3、4、5类似
- 大I/O数据传输容量：所有RAID层次中最高
- 小I/O请求率：约为单个磁盘的两倍
RAID 3（位交错校验）
- 描述：使用位交错的奇偶校验。
- 磁盘需求：N + 1（数据盘数量加上一个奇偶校验盘）
- 数据可用性：比单个磁盘高得多；与RAID 2、4、5类似
- 大I/O数据传输容量：所有RAID层次中最高
- 小I/O请求率：约为单个磁盘的两倍
RAID 4（块交错校验）
- 描述：使用块交错的奇偶校验。
- 磁盘需求：N + 1（数据盘数量加上一个奇偶校验盘）
- 数据可用性：比单个磁盘高得多；与RAID 2、3、5类似
- 大I/O数据传输容量：读取类似于RAID 0；写入显著低于单个磁盘
- 小I/O请求率：读取类似于RAID 0；写入显著低于单个磁盘
RAID 5（块交错分布式奇偶校验）
- 描述：使用块交错的分布式奇偶校验。
- 磁盘需求：N + 1（数据盘数量加上一个奇偶校验盘）
- 数据可用性：比单个磁盘高得多；与RAID 2、3、4类似
- 大I/O数据传输容量：读取类似于RAID 0；写入比RAID 0低
- 小I/O请求率：读取类似于RAID 0；一般比单个磁盘低
RAID 6（块交错双重分布式奇偶校验）
- 描述：使用块交错的双重分布式奇偶校验。
- 磁盘需求：N + 2（数据盘数量加上两个奇偶校验盘）
- 数据可用性：所有RAID层次中最高
- 大I/O数据传输容量：读取类似于RAID 0；写入比RAID 5低
- 小I/O请求率：读取类似于RAID 0；显著低于RAID 5

总结

RAID通过不同层次的实现方式，提供了从性能优化（RAID 0）到数据冗余保护（RAID 1、RAID 5、RAID 6）的多种选择，用户可以根据具体需求选择适合的RAID层次，以平衡性能和数据安全性。

RAID（独立磁盘冗余阵列）笔记

RAID层次概述

RAID 0（条带化）
- 描述：数据分散在多个磁盘上，数据条带化。
- 磁盘需求：N（数据盘数量）
- 数据可用性：比单个磁盘低
- 大I/O数据传输容量：非常高
- 小I/O请求率：读写都非常高
RAID 1（镜像）
- 描述：数据镜像到另一个磁盘上。
- 磁盘需求：2N（两倍数据盘数量）
- 数据可用性：比RAID 2、3、4、5高；比RAID 6低
- 大I/O数据传输容量：比单个磁盘高，写入类似于单个磁盘
- 小I/O请求率：读请求率最高可达两倍于单个磁盘；写入类似于单个磁盘
RAID 2（汉明码校验）
- 描述：通过汉明码实现冗余。
- 磁盘需求：N + m（数据盘数量加上冗余校验盘数量，m与logN成比例）
- 数据可用性：比单个磁盘高得多；与RAID 3、4、5类似
- 大I/O数据传输容量：所有RAID层次中最高
- 小I/O请求率：约为单个磁盘的两倍
RAID 3（位交错校验）
- 描述：使用位交错的奇偶校验。
- 磁盘需求：N + 1（数据盘数量加上一个奇偶校验盘）
- 数据可用性：比单个磁盘高得多；与RAID 2、4、5类似
- 大I/O数据传输容量：所有RAID层次中最高
- 小I/O请求率：约为单个磁盘的两倍
RAID 4（块交错校验）
- 描述：使用块交错的奇偶校验。
- 磁盘需求：N + 1（数据盘数量加上一个奇偶校验盘）
- 数据可用性：比单个磁盘高得多；与RAID 2、3、5类似
- 大I/O数据传输容量：读取类似于RAID 0；写入显著低于单个磁盘
- 小I/O请求率：读取类似于RAID 0；写入显著低于单个磁盘
RAID 5（块交错分布式奇偶校验）
- 描述：使用块交错的分布式奇偶校验。
- 磁盘需求：N + 1（数据盘数量加上一个奇偶校验盘）
- 数据可用性：比单个磁盘高得多；与RAID 2、3、4类似
- 大I/O数据传输容量：读取类似于RAID 0；写入比RAID 0低
- 小I/O请求率：读取类似于RAID 0；一般比单个磁盘低
RAID 6（块交错双重分布式奇偶校验）
- 描述：使用块交错的双重分布式奇偶校验。
- 磁盘需求：N + 2（数据盘数量加上两个奇偶校验盘）
- 数据可用性：所有RAID层次中最高
- 大I/O数据传输容量：读取类似于RAID 0；写入比RAID 5低
- 小I/O请求率：读取类似于RAID 0；显著低于RAID 5

总结

Lesson 12 IO管理

I/O设备的要素

端口（Ports）
- I/O设备通过端口与计算机连接，端口是设备与系统进行通信的接口。
总线（Busses）
- I/O设备通过总线与系统连接，总线是设备之间传输数据的路径。
设备控制器（Device Controllers）
- 设备控制器是设备内部的一个组件，用于管理设备的操作并与操作系统进行通信。

I/O 技术

1. 编程I/O（Programmed I/O）

基本概念
- 处理器主动不断地检查I/O设备的状态，以确定是否有数据可以读取或写入。
- 处理器执行I/O指令直接与设备通信。
优点
- 实现简单，适用于较简单的I/O设备。
- 不需要额外的硬件支持，纯软件实现。
缺点
- 效率低，处理器需要花费大量时间轮询设备状态。
- 导致处理器其他任务的处理时间减少，系统整体性能下降。
工作原理
1. 处理器发送I/O请求。
2. 处理器不断轮询设备状态，直到设备准备好数据。
3. 处理器从设备读取数据或向设备写入数据。
4. 重复以上过程，直到所有I/O操作完成。
适用场景
- 简单的、低速的I/O设备，如键盘、鼠标等。

2. 中断驱动的I/O（Interrupt-driven I/O）

基本概念
- 处理器向I/O设备发出请求后，不需要等待设备响应，而是继续执行其他任务。
- 当I/O设备准备好数据时，会向处理器发送中断信号，通知处理器进行数据传输。
优点
- 提高了处理器的效率，处理器可以在等待I/O设备响应期间执行其他任务。
- 减少了处理器的等待时间，提高了系统的响应速度。
缺点
- 实现复杂，需要支持中断机制。
- 需要处理中断请求，中断处理程序增加了系统的复杂度。
工作原理
1. 处理器发送I/O请求。
2. 处理器继续执行其他任务，不等待I/O设备响应。
3. I/O设备准备好数据后，发送中断信号给处理器。
4. 处理器接收到中断信号，停止当前任务，处理中断请求。
5. 处理器从设备读取数据或向设备写入数据。
6. 处理完成后，处理器返回继续执行原任务。
适用场景
- 大多数I/O设备，如磁盘、网络接口等，适合需要实时响应的场景。

3. 直接内存访问（DMA，Direct Memory Access）

基本概念
- DMA控制器负责在内存和I/O设备之间直接传输数据，而无需处理器的干预。
- 处理器只需初始化DMA传输，然后可以继续执行其他任务，DMA控制器完成数据传输后会向处理器发送中断信号。
优点
- 提高了系统效率，数据传输由专用硬件完成，减少了处理器的负担。
- 适用于高速、大量数据传输的设备，如磁盘和网络设备。
缺点
- 需要额外的硬件支持，增加了系统成本。
- 实现复杂，涉及DMA控制器的配置和管理。
工作原理
1. 处理器初始化DMA传输，设置源地址、目的地址和数据大小。
2. DMA控制器开始传输数据，处理器继续执行其他任务。
3. DMA控制器完成数据传输后，发送中断信号给处理器。
4. 处理器接收到中断信号，检查数据传输结果，处理可能的错误。
适用场景
- 高速、大量数据传输的设备，如硬盘、光盘、网络接口等。

I/O设备操作系统分组

I/O设备可以被操作系统分为以下几类，每一类都有其独特的特性和操作方式：

1. 块I/O（Block I/O）

特点
- 数据以固定大小的块为单位进行传输。
- 设备支持随机访问，数据可以从任何位置开始读写。
- 典型设备包括磁盘驱动器、SSD等。
优点
- 高效的数据传输，适合大数据量的读写操作。
- 支持随机访问，灵活性强。
应用场景
- 文件系统、数据库等需要频繁访问大数据块的应用。

2. 字符I/O（Character I/O，流）

特点
- 数据以字符为单位进行传输，通常是逐字节传输。
- 设备不支持随机访问，数据必须按顺序读取或写入。
- 典型设备包括键盘、鼠标、串行端口等。
优点
- 实现简单，适合小数据量的传输。
- 实时性好，适合交互式应用。
应用场景
- 用户输入设备、传感器数据读取等需要逐字符处理的应用。

3. 内存映射文件访问

特点
- 文件内容被映射到内存地址空间，应用程序可以像访问内存一样访问文件内容。
- 提供了高效的文件读写方式，减少了I/O操作的开销。
优点
- 高效的数据访问，尤其适合频繁读写操作。
- 简化了文件与内存之间的数据交换。
应用场景
- 数据库系统、大型文件处理等需要频繁读写文件的应用。

4. 网络套接字

特点
- 提供网络通信的接口，通过套接字进行数据传输。
- 支持多种通信协议，如TCP/IP、UDP等。
优点
- 灵活的网络通信方式，适用于多种网络应用。
- 支持点对点通信、广播通信等多种模式。
应用场景
- 网络应用程序，如Web服务器、FTP客户端/服务器、远程登录等。

流式I/O（Stream I/O）

流式I/O是一种在Unix System V及其更高版本中用于用户级进程与设备之间的全双工通信通道。它提供了一种模块化的方法来处理I/O操作，使得I/O设备驱动程序能够更灵活地适应不同的设备和需求。

1. 流式I/O的结构

流式I/O包括以下几个组件：

流头（Stream Head）：与用户进程接口。负责处理从用户进程发送到流中的数据，以及将数据从流中发送到用户进程。
驱动程序端（Driver End）：与设备接口。负责处理与设备相关的具体操作，包括读取和写入设备。
流模块（Stream Module）：位于流头和驱动程序端之间。一个流可以包含零个或多个流模块，用于处理和转换数据。

2. 流模块

每个流模块包含两个队列：

读队列（Read Queue）：用于处理从设备到用户进程的数据流。
写队列（Write Queue）：用于处理从用户进程到设备的数据流。

3. 消息传递

流式I/O使用消息传递机制在队列之间进行通信：

消息队列：用于在流模块之间传递数据和控制信息。
流量控制：流模块可以选择性地控制消息传递的速率，以避免数据丢失或缓冲区溢出。流量控制选项包括指示队列是可用还是忙碌。
内部异步：流模块之间的通信是异步的，用户进程与流头之间的通信也是异步的，这使得流式I/O能够高效地处理并发I/O操作。

流式I/O的优点

模块化设计：允许在流中插入或移除流模块，提供了灵活的I/O处理机制。
全双工通信：支持同时进行读和写操作，提高了I/O操作的效率。
消息传递：提供了一种统一的数据和控制信息传递机制，便于流模块之间的协作。

性能改进

在操作系统设计和优化中，提高系统性能是一个重要目标。以下是一些常见的性能改进方法：

1. 减少上下文切换的数量

上下文切换是指操作系统在多任务处理时，从一个进程或线程切换到另一个进程或线程的过程。上下文切换会消耗大量的系统资源和时间，减少上下文切换的数量可以提高系统的整体性能。方法包括：

使用长时间运行的任务
优化调度算法，减少不必要的切换

2. 减少数据复制

数据复制会消耗系统的内存和CPU资源，减少数据复制可以提高I/O操作的效率。方法包括：

使用零拷贝技术，直接在用户空间和内核空间之间传输数据
通过共享内存区域在进程间传递数据

3. 使用大型传输、智能控制器和轮询减少中断

大规模传输可以减少I/O操作的频率，提高传输效率。智能控制器可以自主处理一些I/O操作，减少对CPU的依赖。减少中断的频率可以减少CPU的负载。方法包括：

使用批量传输技术
部署具备智能功能的I/O控制器
使用轮询技术替代频繁的中断

4. 使用DMA（直接内存访问）

DMA允许I/O设备直接与内存进行数据传输，而无需CPU的干预。这样可以大大减轻CPU的负担，提高数据传输的效率。

5. 使用更智能的硬件设备

现代硬件设备通常具备更多的智能功能，可以自主处理一些复杂的操作，减少CPU的负载。例如：

使用具备智能缓存管理的硬盘或SSD
部署具备智能I/O调度的网络设备

6. 平衡CPU、内存、总线和I/O性能以获得最高吞吐量

系统的性能瓶颈可能出现在不同的硬件组件上，通过平衡CPU、内存、总线和I/O的性能，可以最大化系统的吞吐量。例如：

提高内存带宽，减少数据传输的延迟
优化总线的传输速率，提高数据传输效率

7. 将用户模式进程/守护进程移动到内核线程

在一些情况下，可以将一些高频次调用的用户模式进程或守护进程移动到内核线程中执行，这样可以减少上下文切换的开销，提高系统性能。

Lesson 13 文件系统

文件操作

文件操作是文件系统中基本且重要的功能，以下是常见的文件操作及其功能描述：

1. Create

描述：创建一个新的文件。
作用：在文件系统中分配一个新的文件结构，通常包括文件名和元数据。

2. Write

描述：将数据写入文件的写指针位置。
作用：将指定的数据写入到文件中当前写指针的位置，写指针通常会在写入后移动。

3. Read

描述：从文件的读指针位置读取数据。
作用：从文件中当前读指针的位置读取指定数量的数据，读指针通常会在读取后移动。

4. Reposition within file (Seek)

描述：在文件内重新定位读写指针。
作用：将读写指针移动到文件中的指定位置，以便下一次读写操作从该位置开始。

5. Delete

描述：删除文件。
作用：从文件系统中移除文件，并释放该文件所占用的所有资源。

6. Truncate

描述：截断文件。
作用：将文件的长度截断到指定大小，如果新大小小于当前大小，则超出部分的数据将被丢弃。

7. Open (Fi)

描述：打开文件。
作用：搜索磁盘目录结构中的文件条目，将该条目内容移到内存中，以便后续的读写操作。

8. Close (Fi)

描述：关闭文件。
作用：将内存中的文件条目内容移回磁盘目录结构，保存对文件所做的任何更改，并释放内存中的相关资源。

这些基本操作构成了文件系统中最小的一组文件操作集合，它们共同实现了文件的创建、读写、定位、删除和管理功能。在实际的操作系统中，这些操作可能会进一步细化并提供更多高级功能，但基本操作的原理和目的通常是一致的。

文件访问方法

文件访问方法定义了如何在文件系统中读取和写入数据。常见的文件访问方法包括顺序访问、直接访问和其他访问方法。以下是每种方法的详细说明：

1. A file is fixed length logical records

描述：文件由固定长度的逻辑记录组成。
作用：简化了文件的管理和访问，因为每条记录的长度是固定的，便于计算和定位。

2. Sequential Access（顺序访问）

描述：文件按顺序进行访问，从头到尾依次处理每个记录。
特点：
- 读写操作按顺序进行。
- 适用于日志文件、连续记录文件等。
- 典型操作包括读取下一个记录、写入到文件尾部。
优点：实现简单，适合处理顺序数据流。
缺点：不适用于频繁随机访问的场景，效率较低。

3. Direct Access（直接访问）

描述：允许直接访问文件中的任意记录。
特点：
- 文件被视为一个大的数组，每个记录有一个唯一的编号。
- 读写操作可以随机进行，不需要按顺序处理。
- 典型操作包括读写指定位置的记录、跳转到文件中的任意位置。
优点：适用于频繁的随机访问，如数据库。
缺点：实现复杂，可能需要更多的计算和管理。

4. Other Access Methods（其他访问方法）

描述：包括基于索引的访问、哈希访问等特殊方法。
特点：
- 基于索引的访问：文件系统维护一个索引表，通过索引表快速定位记录。
- 哈希访问：利用哈希函数计算记录位置，适合快速查找和插入。
- 其他自定义的访问方法，根据具体需求设计。
优点：针对特定应用场景优化，提高访问效率。
缺点：需要额外的结构和算法支持，增加了实现和管理的复杂度。

磁盘分区和目录结构

磁盘分区

分区A和B在磁盘1上：
- 磁盘1被划分为两个分区：分区A和分区B。
- 每个分区包含自己的目录和文件。
分区C跨越磁盘2和磁盘3：
- 分区C是一个更大的分区，跨越了两个物理磁盘：磁盘2和磁盘3。
- 分区C有一个统一的目录结构和文件系统，尽管其物理存储分布在两个磁盘上。

目录和文件

每个分区都有一个目录（directory）：
- 目录用于管理和组织文件系统中的文件。
- 目录中记录了文件的名称、位置和属性等信息。
目录下存储文件：
- 文件是存储数据的基本单元，包含实际的用户数据或应用程序数据。
- 目录中包含文件的引用或指针，用于定位文件在磁盘上的实际位置。

分区和卷

分区（Partition）：
- 分区是磁盘上的逻辑划分，可以包含独立的文件系统。
- 分区可以是独立的，也可以跨越多个物理磁盘。
卷（Volume）：
- 卷是一个逻辑存储单元，可以由一个或多个分区组成。
- 卷通常包含一个文件系统，用于组织和管理数据。

文件系统

文件系统管理：
- 文件系统负责管理存储在分区或卷中的文件和目录。
- 文件系统提供接口，使得操作系统和应用程序可以访问、修改和管理文件。

示例说明

磁盘1包含分区A和分区B，每个分区有独立的目录和文件：
- 例如，分区A可能用于操作系统文件，分区B用于用户数据。
分区C跨越磁盘2和磁盘3，形成一个统一的存储空间：
- 例如，分区C可以用于大规模数据存储，如数据库或视频文件。

文件系统目录结构

1. 单级目录（Single-Level Directory）

概念：
- 所有文件都存储在一个单独的目录中，没有子目录。
特点：
- 简单易实现。
- 文件名称必须唯一。
优点：
- 易于实现和管理。
缺点：
- 随着文件数量增加，文件名冲突和管理复杂度上升。
- 不支持文件分组和分类。

2. 两级目录（Two-Level Directory）

概念：
- 每个用户有自己的独立目录，所有用户的目录都在一个根目录下。
特点：
- 每个用户有自己的命名空间。
- 文件名在用户目录内必须唯一，但不同用户可以有相同文件名。
优点：
- 文件名冲突减少。
- 方便用户文件管理。
缺点：
- 不支持进一步的文件分组和分类。
- 对于大型系统，目录结构仍然有限。

3. 树形目录（Tree-Structured Directory）

概念：
- 目录结构类似于一棵树，根目录下可以有子目录，每个子目录又可以有自己的子目录。
特点：
- 支持层次化的文件组织。
- 文件和目录可以嵌套，形成层级结构。
优点：
- 灵活的文件组织和管理。
- 便于文件分类和分组。
缺点：
- 实现和管理比单级和两级目录复杂。
- 需要有效的路径解析机制。

4. 无环图目录（Acyclic Graph Directory）

概念：
- 允许共享文件和目录，结构类似于树形目录，但可以有多个父节点。
- 确保目录结构中没有循环（环）。
特点：
- 支持文件和目录共享。
- 允许一个文件或目录在多个位置引用。
优点：
- 提高文件和目录的复用性。
- 减少冗余存储。
缺点：
- 实现较复杂。
- 需要处理引用计数或垃圾回收，以防止删除共享文件时的问题。

5. 通用图目录（General Graph Directory）

概念：
- 允许任意的文件和目录连接，形成一个通用图结构，可以有循环（环）。
特点：
- 最大的灵活性，任何文件或目录都可以引用任何其他文件或目录。
优点：
- 最灵活的文件组织和共享机制。
- 适用于复杂的文件系统需求。
缺点：
- 实现和管理最复杂。
- 需要解决循环引用和垃圾回收问题。

总结

单级目录适用于简单的小型文件系统，两级目录适用于多用户系统，但仍有局限。
树形目录提供了灵活的层次结构，适用于大多数文件系统需求。
无环图目录和通用图目录提供了共享和复用的高级功能，但实现和管理较复杂，需要额外的机制来处理循环和引用问题。

无环图目录（Acyclic Graph Directory）

特点

别名（Aliasing）：允许一个文件或目录有多个名字。
悬空指针（Dangling Pointer）：如果删除包含某文件指针的目录项，可能会导致悬空指针。

解决方法

反向指针（Backpointers）：
- 每个文件记录其指向的所有目录项指针，以便删除时可以删除所有指针。
- 可变大小记录的问题：反向指针可能导致文件记录的大小不固定，增加复杂性。
链式反向指针（Backpointers using a Daisy Chain Organization）：
- 使用链表组织的反向指针，每个目录项指向下一个目录项，形成链条。
持有计数（Entry-Hold-Count Solution）：
- 每个文件记录持有它的目录项数量，在删除目录项时更新计数。
- 当计数为0时，删除文件以避免悬空指针。

新的目录项类型

链接（Link）：
- 链接是指向现有文件的另一个名字（指针）。
- 符号链接（软链接，Symlink）：一个指向另一个文件路径的文件。
- 硬链接（Hardlink）：直接指向文件的物理位置，多个硬链接共享同一文件数据。
解析链接（Resolve the Link）：
- 通过跟随指针来定位文件。

Lesson 14 文件系统实现

文件分配方法

文件分配方法是文件系统中将文件数据存储在磁盘上的不同方式。主要有三种分配方法：连续分配、链接分配和索引分配。每种方法都有其优点和缺点。

1. 连续分配（Contiguous Allocation）

描述：

文件的所有块存储在磁盘上的连续块中。
文件的目录项包含文件的起始块号和文件长度（块数）。

优点：

简单且性能高，因为顺序访问和直接访问文件都非常快速。
适用于需要顺序访问的大文件，如多媒体文件。

缺点：

存储空间的外部碎片问题严重，需要定期的磁盘压缩。
难以扩展文件，因为连续的空闲块可能不足。

示例：

| 文件A | 文件B | 文件C | 空闲 | 文件D |

2. 链接分配（Linked Allocation）

描述：

文件存储在任意的块中，每个块包含指向下一个块的指针。
文件的目录项仅包含文件的起始块号。

优点：

不需要连续的空闲块，解决了外部碎片问题。
文件的大小可以动态增长，只需找到下一个空闲块。

缺点：

顺序访问速度较慢，因为每次读取块都需要通过指针找到下一个块。
直接访问困难，只能顺序读取。
指针占用空间，增加了额外的存储开销。
如果一个指针损坏，整个文件可能会丢失部分数据。

示例：

文件A：块1 -> 块2 -> 块3
文件B：块4 -> 块5 -> 块6

3. 索引分配（Indexed Allocation）

描述：

为每个文件建立一个索引块，索引块包含指向文件所有数据块的指针。
文件的目录项包含索引块的地址。

优点：

直接访问和顺序访问都非常高效。
不需要连续的空闲块，解决了外部碎片问题。
文件可以动态增长，只需更新索引块。

缺点：

索引块增加了存储开销。
如果文件很大，单个索引块可能不够，需要多级索引。

示例：

文件A：
索引块 -> [块1, 块2, 块3, 块4]

文件B：
索引块 -> [块5, 块6, 块7, 块8]

总结

每种文件分配方法都有其适用场景和局限性。选择合适的分配方法取决于文件系统的具体需求和使用场景：

连续分配适用于对性能要求高且文件大小较为固定的场景。
链接分配适用于文件大小不固定且顺序访问较多的场景。
索引分配适用于需要频繁直接访问和文件大小不固定的场景。

统一缓冲区（Unified Buffer Cache）

统一缓冲区是一种将内核缓冲区（Kernel Buffer Cache）和页面缓存（Page Cache）结合在一起的缓存机制，旨在减少冗余的缓存层次，并提高I/O操作的效率。

主要概念

内核缓冲区（Kernel Buffer Cache）：
- 用于缓存磁盘块，主要用于文件系统的块设备I/O操作。
- 缓存的单位是磁盘块。
页面缓存（Page Cache）：
- 用于缓存文件的内存页，主要用于内存映射文件I/O操作。
- 缓存的单位是内存页。
统一缓冲区：
- 将内核缓冲区和页面缓存合并成一个统一的缓存系统。
- 无论是块设备I/O还是内存映射文件I/O，都使用同一套缓存机制。

统一缓冲区的优势

减少冗余数据：
- 通过合并缓冲区，避免了同一数据在不同缓存层次中的重复存储。
简化缓存管理：
- 统一了缓存管理的机制，减少了代码的复杂度。
- 提高了缓存管理的效率，因为所有的I/O操作都经过同一缓存系统。
提高I/O效率：
- 统一缓冲区减少了内存与磁盘之间的数据传输次数。
- 由于减少了冗余数据的缓存，提高了内存利用率和I/O操作的速度。

工作机制

读操作：
- 首先检查统一缓冲区中是否有所需的数据。
- 如果存在，则直接从缓存中读取。
- 如果不存在，则从磁盘读取数据并缓存到统一缓冲区。
写操作：
- 数据首先写入统一缓冲区。
- 缓存系统根据策略（例如延迟写、同步写）将数据写回磁盘。
缓存一致性：
- 统一缓冲区通过一致性协议确保缓存中的数据与磁盘上的数据保持一致。
- 当数据被修改时，缓存系统会标记相应的缓存块为“脏”块，并在适当的时机将其写回磁盘。

实现细节

缓冲区管理：
- 统一缓冲区使用哈希表、链表等数据结构管理缓存块。
- 使用LRU（Least Recently Used）等缓存替换算法来决定缓存块的替换策略。
内存管理：
- 统一缓冲区需要与操作系统的内存管理子系统协作，分配和释放内存页。
- 通过引用计数、回收机制等方法管理缓存块的生命周期。
性能优化：
- 为了提高I/O性能，统一缓冲区会结合预读、延迟写、合并写等技术。
- 根据系统的负载和应用需求动态调整缓存策略。

Lesson 15 典型文件操作和系统

FAT文件系统笔记

FAT（File Allocation Table，文件分配表）文件系统是由微软开发的一种文件系统格式，广泛应用于各种存储设备。它具有简单易用、兼容性强等优点。以下是关于FAT文件系统的详细笔记：

1. FAT文件系统的基本结构

引导区（Boot Sector）：包含用于启动操作系统的代码以及文件系统的基本信息，如每个簇的大小、保留区域的大小等。
文件分配表（FAT）：一个链表结构，用于跟踪文件在磁盘上的存储位置。每个文件都有一个FAT条目，记录了文件的各个簇之间的链接关系。
根目录区（Root Directory Region）：存放文件和子目录的目录条目，包括文件名、文件属性、创建时间、大小等信息。
数据区（Data Region）：存放实际的文件数据。数据区被划分为若干个簇（cluster），是文件系统中最小的存储单元。

2. FAT的种类

FAT12：用于较小的磁盘分区，支持最多4078个簇，适用于软盘等存储设备。
FAT16：用于较大的磁盘分区，支持最多65536个簇，广泛应用于硬盘、U盘等设备。
FAT32：改进了FAT16的限制，支持最多2^28个簇，适用于更大容量的存储设备。

3. FAT文件系统的工作原理

文件存储：文件在磁盘上分配一系列非连续的簇，通过FAT链表记录各个簇的链接关系。例如，文件A占用簇2、5、8，FAT表中簇2指向簇5，簇5指向簇8，簇8指向结束标记。
文件读取：通过根目录区找到文件的起始簇，然后通过FAT表依次读取文件的各个簇，直到文件结束。
文件删除：将文件的FAT表条目标记为“空闲”，即可以被新文件覆盖，实际的数据仍然保留在数据区，直到被新数据覆盖。

4. FAT文件系统的优缺点

优点：
- 简单易用，适合小型存储设备。
- 兼容性强，几乎所有操作系统都支持FAT文件系统。
- 适用于便携式存储设备，如U盘、SD卡等。
缺点：
- 不支持文件权限管理和硬链接。
- 容易产生磁盘碎片，影响读写性能。
- FAT32单个文件最大只能为4GB，不适合大文件存储。

5. FAT文件系统的应用

嵌入式系统：由于FAT文件系统简单高效，广泛应用于嵌入式系统中，如相机、MP3播放器等。
移动存储设备：FAT文件系统的高兼容性使其成为U盘、SD卡等移动存储设备的首选文件系统。
跨平台数据传输：FAT文件系统支持多种操作系统，适合在不同平台间进行数据传输。

6. FAT文件系统的维护

碎片整理：定期进行磁盘碎片整理，优化文件存储，提高读写性能。
错误检查：使用工具检查并修复FAT表中的错误，防止数据丢失。
备份：重要数据应定期备份，避免因文件系统损坏导致的数据丢失。

操作系统笔记

lesson 1 概论

接口层次

lesson 2 操作系统结构

操作系统的发展

1. 串行处理

2. 简单批处理

3. 多道批处理

4. 分时系统

操作系统模式

用户模式 (User Mode)

内核模式 (Kernel Mode)

操作系统服务

用户接口 (User Interfaces)

系统调用 (System Calls)

程序编译和运行

编译过程

加载过程

现代操作系统的特性

文件格式

宏内核与微内核

宏内核 (Monolithic Kernel)

微内核 (Microkernel)

比较

结论

Unikernel

Unikernel 特点

Unikernel 的架构比较

Unikernel 的优势

Unikernel 的应用场景

lesson 3 中断，异常

中断、异常和系统调用详解

源头

响应方式

处理机制

Linux 系统中的中断

中断处理原则

中断处理结构

中断处理程序能否在被中断的用户进程的栈上运行？

答案

原因分析

lesson 4 进程

进程在内存中的布局

概述

详细说明

进程内存布局总结

进程的状态

进程状态

状态转换详细说明

操作系统中的表

内存表 (Memory Table)

I/O表 (I/O Table)

文件表 (File Table)

进程表 (Process Table)

PCB（进程控制块）

定义

内容

作用

孤儿进程 (Orphan Process)

定义

特征

原因

处理

特征

处理

使用 fork() 创建子进程的典型程序

程序代码

使用 execl() 系统调用执行新程序

程序代码示例

程序解释

运行结果和原因

进程间通信模型

(a) 共享内存

(b) 信息传递

多核处理器系统中的优先选择

管道（PIPE）

普通管道（Anonymous Pipe）

命名管道（Named Pipe 或 FIFO）

普通管道

命名管道

使用 `fork()` 创建子进程的典型程序

使用 `execl()` 系统调用执行新程序