Lecture Notes

Lecture Notes: Operating Systems

COMP3033 Operating Systems

Dr. Sunny Seon Phil JEONG

Chapter 2: Operating-System Structures

1. Operating System Services

Operating systems provide services to users and programs, categorized as:

  • User Services:

    • User Interface (UI): CLI (Command-Line Interface), GUI (Graphical User Interface), Touchscreen, batch processing (批处理)
    • Program Execution
      • Load a program into memory
      • Run a program, and then end execution.
    • I/O Operations: Read/write files, input/output handling
    • File-System Manipulation: Create, delete, read/write files
    • Communications: Process communication & networking
    • Error Detection: Handling software/hardware errors

  • System Efficiency Services:

    • Resource Allocation: CPU, memory, I/O management
    • Logging: Tracking user resource usage
    • Protection & Security:
      • Protection: Ensure that all access to system resources is controlled
      • Security: Avoid attack from outside the system

2. Operating System Interface

  • CLI
    • CLI (Command Line Interface) or command interpreter allows direct command entry
    • Commands are
      • sometimes implemented in kernel
        • commands built-in
      • sometimes by systems program
        • names of programs
        • +Advantage: adding new features doesn’t require modification of interpreter
    • Shell (vs. Kernel)
      • Multiple flavors of interpreters implemented
  • GUI
    • User-friendly

3. System Calls， API，C Libraries

  • System Calls: Interface for processes to request OS services.
    • Examples: read(), write(), fork(), exec() on Unix/Linux
  • API (Application Programming Interface):
    • specifies a set of functions that are available to an application programmer.
    • Three most common APIs (libraries):
      • Win32 API (Windows)
      • POSIX API (Linux, UNIX, macOS)
        • Portable Operating System Interface
      • Java API (JVM-based applications)

API and System Call

  • 调用者只需遵循 API
    • 无需了解系统调用的实现方式
    • 大多数操作系统接口细节都通过 API 隐藏在程序员面前
  • The system call interface invokes the intended system call in OS kernel and returns status of the system call and any return values
  • Each system call has a number (as index)
  • System-call interface maintains a table: indexed according to these numbers

System Call Parameter Passing Methods:

  • Registers: Fastest, but limited number.
    • 将参数直接存放在 CPU 寄存器中，传递给系统调用。
    • 优点：
      • 传输速度快，因为寄存器在 CPU 中。
    • 缺点：
      • 寄存器数量有限，无法传递大量数据。
      • 不适用于传递结构体或数组等复杂数据。
  • Memory Table: Stores parameters in memory and passes address.
    • 将参数保存在内存中的某个位置，并传递该内存地址给系统调用。
    • 优点：
      • 适合传递大量数据，如结构体、数组等。
    • 缺点：
      • 需要额外的内存管理。
      • 可能涉及内存拷贝，增加开销。
  • Stack: Push/pop parameters from the stack.
    • 方式：参数通过 stack 进行传递，调用函数时将参数压入栈中。
    • 优点：
      • 易于实现，符合函数调用约定。
      • 支持变长参数。
    • 缺点：
      • 栈传递的效率不如寄存器传递。
      • 如果参数数量过多，可能导致栈溢出。

Standard C Library vs System Call

  • Advantages of using Standard C Library
    • It is simpler to call a function in a standard C library rather than to make a system call
    • Portability
  • Advantages of using system calls
    • more powerful
    • a little bit faster

Standard C Library vs C POSIX Library: subset ⊏ superset

  • Programs
    • kernel
    • system program
    • application program
  • How can apps be used in multi-operating systems？
    • interpreted language, like Python, Ruby, and interpreter available on multiple operating systems
    • Written in a language that includes a VM containing the running app (like Java)
    • Written in a standard language (like C), compiled separately on each operating system to run on each OS
    • Application Binary Interface (ABI)
      • about how different components of binary code can interface for a given operating system on a given architecture in low-level details
        二进制代码的不同组件如何在低级细节中与给定体系结构上的给定操作系统进行交互

4. Operating System Structure

4.1 OS Architectures

  1. Monolithic（庞大而单一）- Traditional UNIX
    • The traditional UNIX OS follows a monolithic kernel structure.
    • Single large kernel handling everything. 一个单一的大型进程 ，管理大多数操作系统服务，包括文件系统、CPU 调度和内存管理。
    • Fast but complex.
    • The UNIX OS consists of two separable parts
      • Systems programs
      • The kernel
  2. Monolithic Plus Modular - Linux System Structure
    • Advantages for monolithic design
      • High speed
      • High efficiency
    • Advantages for modular design
      • changes in one component affect only that component, and no others
      • Modules can be modified easily.
  3. Layered Approach
    • Divides OS into hierarchical layers.
    • Easy to manage but slower.
    • Advantage
      • Simplicity of construction and debugging.
    • Disadvantages
      • Hard to define each layer.
      • Poor performance.
  4. Microkernel (e.g., Mach)
    • e.g., Mach – Mac OS X kernel (Darwin) partly based on Mach
    • Moves as much components from the kernel into user space
    • More secure but has communication overhead.
  5. Modules
    • loadable kernel modules (best practice)
    • Uses object-oriented approach
  6. Hybrid Systems
    • Combines different architectures (e.g., Windows, macOS).

Chapter 3: Process

1. Process Concept

Process

  • a program in execution in memory
  • execution must progress in sequential fashion

Process 组成

  • the program code (also called text section)
  • stack (函数调用参数、返回地址、局部变量)
  • data section (全局变量、静态变量)
  • heap (动态分配的内存 malloc / new)
  • program counter, processor registers (include all current data of the program inside the CPU)

Process State

  • New: The process is being created
  • Running: Instructions are being executed by CPU
  • Waiting: The process is waiting for some event to occur
  • Ready: The process is waiting to be assigned to a processor
  • Terminated: The process has finished execution
    Process State

2. Process Scheduling

Process Control Block (PCB) (also called task control block)

  • 操作系统管理进程的关键数据结构
  • A PCB is a kernel data structure
    • invisble to Process itself, changed only by the kernel
  • Each process has a corresponding unique PCB in the kernel.
  • 包含
    • Process state – running, waiting, etc.
    • Program counter (PC) – location of instruction to next execute
    • CPU registers – contents of all process-centric registers
    • CPU scheduling information - 调度信息（优先级、队列信息）
    • Memory-management information – 内存管理信息（地址空间）
    • Accounting information – CPU used, clock time elapsed since start, time limits
    • I/O status information – I/O devices allocated to process, list of open files

Process Scheduling

  • Process scheduler (kernal 里的 algorithm)
    • Maintains scheduling queues of processes
    • Ready queue: 等待 CPU 执行的进程。
    • Wait queues: 等待 I/O 事件的进程。
    • 上下文切换 Context Switch:
      • 当 CPU 切换进程时，需要保存和恢复 PCB。
      • 上下文切换是额外开销，依赖硬件支持。

3. Operations on Processes

Process Creation

  • 父进程（Parent Process） 通过 fork() 创建子进程（Child Process）
  • 父子进程资源共享方式：
    • 完全共享（共享所有资源）
    • 部分共享（共享部分资源）
    • 完全独立（无资源共享）
  • 进程执行方式：
    • 并行执行（父子进程同时运行）
    • 顺序执行（父进程等待子进程完成）

Process Termination

  • 进程调用 exit() 终止自身。
  • 父进程调用 wait() 终止子进程。
  • 父进程可以使用 abort() 终止子进程（如子进程占用过多资源）。
  • 孤儿进程（Orphan Process）：父进程终止，但子进程仍在运行。
  • 僵尸进程（Zombie Process）：
    • 子进程已终止，但 PCB 仍保留，等待父进程读取状态。
    • Reaping (回收)

4. Inter-process Communication (IPC)

  • Advantages/Reasons of process cooperation
    • Information sharing
    • Computation speed-up
    • Modularity
    • Convenience
  • Disadvantages
    • Added complexity
    • Deadlocks (死锁) possible
    • Starvation (饥饿) possible
IPC 方式 说明
共享内存（Shared Memory） 进程直接共享内存，需要同步控制
消息传递（Message Passing） 通过 send() 和 receive() 传递消息

Shared Memory

Major issues: Synchronization (同步) (Discussed in Chapters 6 & 7)

  • Producer-Consumer Problem: Paradigm (范例) for cooperating processes
    • 无界缓冲区（Unbounded Buffer）：无限存储，不会阻塞生产者。
    • 有界缓冲区（Bounded Buffer）：存储大小固定，生产者可能阻塞。

Message Passing

1. 直接通信（Direct Communication）
进程必须显式指定对方：

1
2
send(P, message);
receive(Q, message);

2. 间接通信（Indirect Communication）
通过 邮箱（Mailbox） 进行消息交换：

1
2
send(mailbox, message);
receive(mailbox, message);

Message passing may be either blocking (synchronous) or non-blocking (asynchronous)

方式 发送者 接收者
同步（阻塞） 等待接收方处理 等待消息
异步（非阻塞） 立即返回 立即返回

If both send and receive are blocking, this case is called rendezvous （会合）

Pipe
  • 匿名管道（Ordinary Pipes）：unidirectional 单向，Require parent-child relationship 父子进程通信。
  • 命名管道（Named Pipes）：bidirectional 双向，无需父子关系。

匿名管道示例:

1
2
3
4
5
6
7
8
9
10
11
int fd[2];
pipe(fd);
pid_t pid = fork();

if (pid == 0) {  // 子进程
    close(fd[1]);
    read(fd[0], buffer, sizeof(buffer));
} else {  // 父进程
    close(fd[0]);
    write(fd[1], "Hello", 5);
}

5. Communication in Client-Server Systems

本节介绍 Sockets 和 RPC，他们都属于 IPC 中的 Message Passing

Sockets

  • 用于网络通信（Client-Server）。
  • 套接字 = IP 地址 + 端口号。

服务器端

1
2
3
4
ServerSocket server = new ServerSocket(6013);
Socket client = server.accept();
PrintWriter out = new PrintWriter(client.getOutputStream(), true);
out.println("Hello Client!");

客户端

1
2
3
Socket socket = new Socket("127.0.0.1", 6013);
BufferedReader in = new BufferedReader(new InputStreamReader(socket.getInputStream()));
System.out.println(in.readLine());

Remote Procedure Calls

  • 封装进程间通信，使其看起来像本地函数调用。
  • 基于底层消息传递（通常使用 Socket 进行通信）：
    • 客户端调用 RPC，将请求参数封装成消息，发送给远程服务器。
    • 服务器解包消息，执行相应函数，将结果打包返回。
  • 数据传输
    • 序列化/反序列化（Marshalling & Unmarshalling）：将数据转换为可传输的格式（如 JSON、XML）。
    • 使用 TCP 或 UDP 进行底层传输。

  • Example

    1
    2
    // 客户端调用 RPC 函数
    result = rpc_call("add", 5, 10);  // 实际上底层是 send()/recv()

Chapter 4: Threads & Concurrency

1. Process vs. Thread

  • What is thread?
    • A thread is a single sequence stream within a process.
对比项 进程（Process） 线程（Thread）
创建开销 高（需要分配独立资源） 低（共享进程资源）
内存空间 每个进程有独立的地址空间 同一进程内多个线程共享地址空间
调度与管理 由操作系统负责 由操作系统或用户负责
资源共享 不共享资源 共享进程内的资源
上下文切换 较慢 快

2. Concurrency vs. Parallelism

  • Concurrency is a property of a program where two or more tasks can be in progress simultaneously.
    • 并发是指多个任务的进展，这些任务并不一定同时执行，通常在单核系统中，通过时间片轮转来模拟同时执行。
  • Parallelism is a run-time property where two or more tasks are being executed simultaneously.
    • 并行是指多个任务同时执行，通常需要多核处理器支持，每个核心执行一个任务。
    • 并行是并发的一种实现方式，并行意味着并发，但并发不一定意味着并行。

多核编程（Multicore Programming）

  • 多核编程挑战：任务划分、负载均衡、数据拆分、数据依赖、调试困难等。
  • 并行性（Parallelism）：多个任务同时执行，需要多个处理器或核心支持。
  • 并发性（Concurrency）：多个任务的进度同时进行，单处理器通过上下文切换提供并发。
数据并行（Data Parallelism）：
  • 数据的子集分布在多个核心上，执行相同的操作。
    • 示例：图像处理时，每个核心处理图像的一部分。
任务并行（Task Parallelism）：
  • 将不同任务分配给不同的核心，执行不同的操作。
    • 示例：声音处理时，任务分配到不同的核心处理不同的音频处理（滤波、回声等）。

3. Thread Libraries

  • Thread Libraries 线程库为程序员提供了创建与管理线程的 API。
    • POSIX Pthreads：最常用的线程库，支持用户级和内核级线程。
    • Windows threads：Windows 操作系统的线程库。
    • Java threads：Java 提供的线程模型。

4. Implicit Threading

5. Threading Issues

Chapter 5: CPU Scheduling

1. Basic Concepts

  • Purpose of multiprogramming: maximum CPU utilization
  • CPU–I/O Burst Cycle
    • 进程的执行周期通常包括 CPU 执行和 I/O 等待，每个进程在 CPU 执行和 I/O 等待之间交替进行。

CPU Scheduler

  • CPU Scheduler 负责从 ready queue 中选择一个进程，并将 CPU 分配给该进程。
  • 调度决策发生的时机：
    • 进程从 running 转换到 waiting（non-preemptive 自愿离开CPU 非抢占性调度）。
    • 进程从 running 转换到 ready（preemptive 抢占性调度）。
    • 进程从 waiting 转换到 ready (preemptive)。
    • 进程 terminates（non-preemptive 非抢占性调度）。

抢占式与非抢占式调度

  • 抢占式调度（Preemptive）：
    • CPU 可以被其他进程抢占。
    • 提高响应时间，适用于交互式环境。
    • 可能引发 race conditions 数据竞争问题（需要线程同步）。
  • 非抢占式调度（Non-preemptive）：
    • 进程执行完成或者主动放弃 CPU。
    • 没有数据竞争问题，但可能导致低优先级进程长时间得不到 CPU。

2. Scheduling Criteria

  • CPU utilization：尽量让 CPU 始终处于忙碌状态。
  • Throughput 吞吐量：每单位时间完成的进程数。
  • Response time 响应时间：从提交请求到第一次响应的时间（适用于时间共享系统）。
  • Waiting time 等待时间：进程在就绪队列中等待的总时间。
  • Turnaround time 周转时间：从进程开始到结束所经历的总时间（包括等待时间和执行时间）。
    • Turnaround time = Waiting time + time for all CPU bursts

3. Scheduling Algorithms

  1. First-Come, First-Served (FCFS)
  • 原理：按进程到达的顺序分配 CPU。
  • 缺点：可能导致 长进程 阻塞 短进程，产生 Convey effect 护送效应。
  1. Shortest-Job-First (SJF)
  • 原理：选择 预计 CPU 时间最短 的进程执行。
  • 优点：最小化平均等待时间。
  • 缺点：难以预测下一次 CPU 时间，且可能导致 饥饿现象。
  • Determining Length of Next CPU Burst
    • 通过 过去的 CPU 运行时间 来预测 下一个运行时间，即：
    • $\tau_{n+1} = \alpha t_n + (1 - \alpha) \tau_n$
    • $\tau_n$ 是第 n 次的预测 CPU 运行时间
    • $t_n$ 是实际的第 n 次 CPU 运行时间
    • $\alpha$ 是平滑因子，通常设置为 0.5
  1. Priority Scheduling (PS)
  • 原理：根据进程的优先级分配 CPU，优先级高的进程优先执行。
    • A priority number (integer) may be associated with each process
    • The CPU is allocated to the process with the highest priority (smallest integer = highest priority)
  • 缺点：低优先级进程可能永远得不到执行（Starvation）。
  • 解决方法：Aging 老化，逐步提高低优先级进程的优先级。
  • SJF is priority scheduling where priority is the inverse of predicted next CPU burst time
  1. Round-Robin (RR)
  • 原理：
    • Each process gets a small unit of CPU time (time quantum 定额 q), usually 10-100 milliseconds.
    • After q has elapsed, the process is preempted by a clock interrupt and added to the end of the ready queue.
  • 优点：适用于 时间共享系统，响应较快。
  • 缺点：时间片过小导致频繁 context switch，过大则退化为 FCFS。
  1. Multilevel Queue Scheduling (MQS)
  • 原理：将进程分为多个队列，每个队列采用不同的调度算法。
    • foreground 前台队列（交互式进程）：使用 RR 算法。
    • background 后台队列（批处理进程）：使用 FCFS 算法。
  • 缺点：可能导致 低优先级队列的进程饥饿。
  1. Multilevel Feedback Queue Scheduling (MFQS)
  • 原理：进程可以在不同队列间移动，避免饥饿现象。
    • 新进程先进入最高优先级队列。
    • 时间片未完成的进程被移至较低优先级队列。(aging, prevent starvation)
  • 优点：灵活，适应性强。
  • the most general CPU scheduling algorithm

4. Thread Scheduling

线程调度模型

  • 用户级线程（User-Level Threads）：

    • 线程管理由 thread library 完成，不依赖 kernal。
    • 适用于不支持线程管理的操作系统。
    • process-contention scope (PCS)
    • 优点：不需要系统调用，线程创建和切换速度快。
    • 缺点：无法利用多核系统，线程竞争和调度需要用户自己处理。

  • 内核级线程（Kernel-Level Threads）：

    • 由 kernal 管理。
    • system-contention scope (SCS)
    • 每个线程由操作系统调度，支持多核并行。
    • 优点：能够利用多核架构，操作系统能自动调度线程。
    • 缺点：每个线程管理都需要进行系统调用，开销较大。

  • 多对一、多对多模型（Many-to-One, Many-to-Many）：

    • 多对一（Many-to-One）：多个用户级线程映射到一个内核线程上。
    • 多对多（Many-to-Many）：多个用户级线程映射到多个内核线程上。
    • 一对一（One-to-One）：每个用户级线程都有一个对应的内核线程，常见于 Windows 和 Linux。

5. Multi-Processor Scheduling

  • 多处理器调度更加复杂，尤其在 Symmetric multiprocessing (SMP) 对称多处理 系统中，每个处理器都有自己的 就绪队列 和 线程调度。

SMP（对称多处理） 调度策略：

  1. 共同就绪队列（Common Ready Queue）：

    • 所有线程都在一个共享的就绪队列中，操作系统负责选择哪个线程分配到哪个 CPU 上。
    • 优点：所有线程共享一个队列，避免了资源的浪费。

  2. 私有就绪队列（Private Ready Queue）：

    • 每个处理器有自己的私有队列，操作系统通过调度算法在不同的队列之间分配任务。
    • 优点：避免了调度时的冲突，提高了效率。

负载均衡（Load Balancing）：

  • 推迁移（Push Migration）：检查各处理器的负载，将任务从负载过重的处理器迁移到空闲的处理器。
  • 拉迁移（Pull Migration）：空闲的处理器主动拉取等待队列中的任务。

6. Real-Time CPU Scheduling

实时系统调度：

  • 软实时系统（Soft Real-Time Systems）：高优先级的实时任务优先执行，但不能保证任务会被准时执行。(best try only)
  • 硬实时系统（Hard Real-Time Systems）：任务必须在规定的时间内完成，否则会导致系统错误。

实时调度标准：

  1. Event Latency 响应时间：从事件发生到处理完成所经历的时间。
  2. 调度延迟：
    • Interrupt latency 中断延迟：从中断到 interrupt service routine (ISR) 开始执行的时间。
    • Dispatch Latency 调度延迟：从当前进程被挂起到新的进程开始执行的时间。

实时调度算法：

  • 速率单调调度（Rate-Monotonic Scheduling, RMS）：任务的优先级与其周期的倒数成正比，周期越短优先级越高。
  • 最早截止时间调度（Earliest Deadline First, EDF）：优先级与任务的截止时间成正比，截止时间越早优先级越高。

7. Operating Systems Examples

Midterm Hints

Section A

  1. ch1, p13 Interrupt-Driven
  2. ch1, p26 Caching
  3. ch1, p31 Dual-mode (user & kernal)
  4. ch2, p34 Monolithic - Traditional UNIX
  5. ch3, p14 Context Switch
  6. ch3, p59 Named pipes
  7. ch5, p12, p14 SJF, Determining Length of Next CPU Burst
  8. ch5, p26, p28 MQS, MFQS
  9. ch3, p9 Process Control Block
  10. ch3, p21, p22 Process Creation

Section B

  1. ch2
  2. ch3, p34-37 Zombie and Orphan Process
  3. ch3, p39 IPC Models(Shared memory & Message Passing)
  4. ch4, p11-12 Data and Task Parallelism
  5. ch2, p20 Syscall 传参

Section C

  1. ch5, p10-20 Scheduling Algorithms(FCFS, SJF, RR)
  2. ch3, p22-30 fork()
  3. ch4, p26-30 pthreads.h

Chapter 6 & 7: Process Synchoronization

1. 进程同步背景

  • 并发执行：多个进程可以并发执行，可能会在任何时刻被中断。
  • 共享数据问题：并发进程访问共享数据可能导致数据不一致。

示例：生产者-消费者问题

  • 生产者和消费者共享一个缓冲区，生产者放入数据，消费者取出数据，若没有同步机制，可能导致数据冲突或丢失。

2. 竞争条件（Race Condition）

  • 定义：多个进程同时访问和操作共享数据，结果依赖于它们的执行顺序。
  • 例子：计数器的递增和递减操作，可能会出现竞争条件，导致最终结果不符合预期。

3. 临界区问题（Critical Section Problem）

  • 临界区：进程执行需要访问和修改共享资源的代码段。
  • 问题：当一个进程在临界区时，其他进程不能进入该临界区，否则会发生数据不一致。
  • 目标：设计一个协议，确保多个进程能够同步访问共享资源，避免数据竞争。

临界区的通用结构：

  1. 请求进入临界区。
  2. 执行临界区的操作。
  3. 离开临界区，允许其他进程进入。

4. 临界区问题的解决方案

解决方案必须满足以下三条要求：

  1. 互斥（Mutual Exclusion）：如果进程 $P_i$ 正在执行临界区，其他进程不能同时执行其临界区。
  2. 进度（Progress）：如果没有进程在临界区，且有其他进程等待进入临界区，必须选择一个进程进入。
  3. 有界等待（Bounded Waiting）：如果进程请求进入临界区，必须有一个上限保证其他进程的请求不会被无限制地推迟。

5. Peterson’s Solution

  • 目的：为两个进程解决临界区问题。
  • 变量：
    • turn: 记录哪个进程可以进入临界区。
    • flag[]: 指示进程是否准备进入临界区。
  • 算法：
    • 当一个进程请求进入临界区时，它会设置自己的标志位，并将 turn 设置为另一个进程，以便对方能进入。
    • 如果另一个进程不在临界区，它就会等待对方退出。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include <stdbool.h>

#define N 2  // Number of processes (for Peterson’s solution, N = 2)

int turn;
bool flag[N];

// Function for process Pi
void Peterson(int i) {
    int j = 1 - i;  // If i = 0, j = 1, and if i = 1, j = 0 (since there are only two processes)

    // Entry section
    flag[i] = true;   // Indicate that process i wants to enter its critical section
    turn = j;         // Give turn to the other process
    while (flag[j] && turn == j) {
        // Busy-wait: process i will wait as long as process j wants to enter the critical section
        // or it's the turn of process j
    }

    // Critical section
    printf("Process %d is in the critical section.\n", i);

    // Exit section
    flag[i] = false;  // Process i exits the critical section, allows other processes to enter

    // Remainder section
    printf("Process %d is in the remainder section.\n", i);
}

int main() {
    // Initializing flag to false
    for (int i = 0; i < N; i++) {
        flag[i] = false;
    }

    // Simulating two processes P0 and P1
    // Process 0 and 1 will be executed concurrently
    // In a real OS, these would be separate processes or threads
    Peterson(0);  // Process 0 tries to enter its critical section
    Peterson(1);  // Process 1 tries to enter its critical section

    return 0;
}

代码讲解

  1. flag[i] 和 turn 变量：

    • flag[i] 是一个布尔数组，用于标记进程 i 是否准备进入临界区。当一个进程想进入临界区时，它将 flag[i] 设置为 true。
    • turn 变量用于表示哪个进程应该被允许进入临界区。如果 turn 的值为进程 i，那么进程 i 被允许进入。如果 turn 是另一个进程的编号，它将让其他进程优先进入。

  2. Entry Section（进入部分）：

    • 在进入临界区之前，每个进程都会通过设置 flag[i] = true 来告诉其他进程它希望进入临界区。
    • 然后，它将 turn 设置为另一个进程 j，这确保了对方进程有机会先执行。
    • 然后，进程进入一个循环，检查 flag[j] 是否为 true 并且 turn == j。如果这两个条件都成立，表示进程 j 想进入临界区，并且是 j 的回合，所以当前进程就会等待，直到对方进程退出临界区。

  3. Critical Section（临界区）：

    • 当进程通过 while 循环检查后发现对方进程不再想进入临界区或轮到它自己时，它就可以进入临界区执行任务。在这个区域，访问共享资源时不会被其他进程打断。

  4. Exit Section（退出部分）：

    • 在完成临界区的任务后，进程将 flag[i] = false，表示它退出了临界区，其他进程可以进入。

  5. Remainder Section（剩余部分）：

    • 这是进程完成临界区操作后的其他任务区域，它不涉及共享资源。

6. 同步硬件（Synchronization Hardware）

  • 测试与设置（test_and_set）指令：检查一个变量并将其设置为 true，用于实现互斥锁。

    • 如果 lock 是 false，说明锁未被占用，可以将其设置为 true，并进入临界区。
    • 如果 lock 是 true，则表示锁已经被占用，进程需要等待。

  • 比较与交换（compare_and_swap）指令：将锁的值与预期值进行比较，如果匹配则交换值。

    • 这种原子操作能有效解决并发进程中的临界区问题。

7. 互斥锁（Mutex Locks）

  • 概念：互斥锁用于保护临界区，保证同一时间只有一个进程能够访问共享资源。
  • 操作：
    • acquire(): 请求获取锁。
    • release(): 释放锁。
  • 自旋锁（Spinlock）：如果锁未被释放，进程会持续检查并等待锁的释放，这会造成忙等待。

8. 信号量（Semaphore）

  • 信号量：用于控制多个进程对共享资源的访问。
    • 类型：
      • 计数信号量：可以接受任意整数值。
      • 二进制信号量：值只能是 0 或 1，类似互斥锁。

信号量操作：

  1. wait(S)：如果 S > 0，将 S 减 1；否则，进程阻塞。
  2. signal(S)：将 S 增 1，如果有进程在等待信号量，唤醒一个进程。

9. 经典同步问题

1. 有界缓冲问题（Bounded-Buffer Problem）

  • 生产者-消费者问题：多个生产者和消费者通过缓冲区共享数据，必须保证缓冲区的互斥访问。
  • 信号量设计：
    • mutex: 用于保护缓冲区。
    • empty: 表示缓冲区的空槽数量。
    • full: 表示缓冲区的满槽数量。

2. 读者-写者问题（Readers-Writers Problem）

  • 问题：多个进程读写共享数据，要求多个读者可以同时读，但写者必须是独占访问。
  • 解决方案：
    • 使用信号量和读者计数来控制读者和写者的访问。
    • 读者优先或写者优先的策略可以避免死锁和饿死现象。

3. 哲学家进餐问题（Dining-Philosophers Problem）

  • 问题：哲学家交替进行思考和进食，使用两个筷子来吃饭，避免死锁和饿死现象。
  • 解决方案：
    • 死锁避免：最多允许四个哲学家同时坐下。
    • 非对称解决方案：奇数哲学家先拿左边筷子，再拿右边筷子，偶数哲学家则相反。

10. Pthreads 同步

  • Pthreads API：为线程同步提供的跨平台接口，支持互斥锁、条件变量和信号量。
    • 互斥锁：
      1
      2
      3
      4
      pthread_mutex_t mutex;
      pthread_mutex_init(&mutex, NULL);
      pthread_mutex_lock(&mutex);
      pthread_mutex_unlock(&mutex);
    • 条件变量：
      1
      2
      3
      pthread_cond_t cond;
      pthread_cond_wait(&cond, &mutex);
      pthread_cond_signal(&cond);

11. POSIX 信号量

  • POSIX 信号量用于线程和进程同步：
    • 初始化：
      1
      2
      sem_t sem;
      sem_init(&sem, 0, 1); // 信号量初始化
    • 操作：
      1
      2
      sem_wait(&sem); // 等待信号量
      sem_post(&sem); // 发出信号量

总结

  • 进程同步涉及到多个进程或线程对共享资源的有序访问，避免竞争条件和数据不一致。
  • 主要工具：互斥锁、信号量、条件变量等。
  • 常见问题包括：生产者-消费者问题、读者-写者问题、哲学家进餐问题。
名称 类型 原理 优点 缺点
Peterson’s Solution 软件方法 用两个变量 flag 和 turn 实现互斥 简单、无需硬件支持 仅适用于两个线程，现代 CPU 指令重排可能破坏其正确性
Semaphore（信号量） 操作系统原语 用整数变量 S 控制资源访问，wait()/signal() 操作 强大灵活，能实现互斥和同步 易写错，可能导致死锁、饿死等
Mutex（互斥锁） 低级同步机制 类似信号量，但专用于互斥访问资源 简单直接，适用于临界区保护 只能用于互斥，不能用于复杂同步
Monitor（监视器） 高级同步抽象 将数据和方法封装，自动控制互斥，配合条件变量 安全抽象、结构清晰，自动管理临界区 实现较复杂、灵活性不如信号量
  • Peterson’s Solution：教材经典算法，理论上能保证互斥，但实际中不常用。
  • Semaphore：底层通用工具，强大但容易误用。
  • Mutex：专门用于实现互斥的信号量，是信号量的简化版。
  • Monitor：面向对象风格的同步工具，更现代、结构化，常见于 Java synchronized、Python with threading.Lock()。

Chapter 9: Main Memory

1. 存储系统基础

存储层级（Storage Hierarchy）【见第3页图示】

  • 寄存器（Registers）：最快速、最小容量。
  • 高速缓存（Cache）
  • 主存（Main Memory）
  • 非易失存储（硬盘、SSD）
  • 磁带（最慢，最大容量）
  • CPU 只能直接访问寄存器和主存。

2. 地址绑定（Address Binding）

三种绑定时机【第7页】

绑定时间 特点 示例
编译时（Compile time） 地址写死 嵌入式系统
装载时（Load time） 相对地址→绝对地址 老式多道程序系统
运行时（Execution time） 逻辑地址→物理地址 现代系统，需硬件支持（如MMU）

3. 地址类型与映射

  • 逻辑地址（Logical Address）：CPU生成，又称虚拟地址。
  • 物理地址（Physical Address）：内存单元地址。
  • 地址空间映射由内存管理单元（MMU）完成【第13页图示】

4. 动态加载与链接

  • 动态加载 Dynamic Loading：只有在需要时加载某段代码（节省内存）。
  • 动态链接 Dynamic Linking：程序运行时将库函数加载进内存（如 DLL/so）。

5. 连续内存分配（Contiguous Allocation）

方式：

  1. 固定分区（Fixed Partition）
    • 多个等大小分区，容易产生内外部碎片。
  2. 可变分区（Variable Partition）
    • 根据进程大小动态分配内存，使用空洞（hole）管理。

分配策略【第19页】

  • First Fit：第一个足够大的空洞。
    • 简单、速度快，但可能在低地址区留下许多小碎片。
  • Best Fit：最小满足的空洞（易产生小碎片）。
    • 理论上最佳利用空间，但需要扫描所有 hole，并容易留下过小碎片。
  • Worst Fit：最大空洞。
    • 留给后续分配最大的空洞，反而更易产生中等尺寸碎片，利用率最差。

6. 碎片问题（Fragmentation）

外部碎片（External）

  • 空间足够但不连续。
  • 解决：压缩（Compaction）或分页。
    • 压缩（Compaction）：把所有占用的内存挪拢到一端，使空闲空间连成一个大块（仅在执行时动态重定位时可行）。
    • 使用非连续分配：例如分页或分段技术，直接消除外部碎片。

内部碎片（Internal）

  • 分配空间 > 实际使用，造成空间浪费。

7. 非连续内存分配：分页（Paging）

  • 进程的物理地址空间可以是不连续的，只要所有空闲内存块之和足够，就可以为进程分配内存，从而避免外部碎片。
  • 将内存划分为固定大小的块：页框（Frame）
    • 每个 Frame 的大小是 2 的幂次，通常在 512 字节到 16 MB 之间。
  • 将逻辑内存划分为页（Page）, 其大小等于 Frame 大小。
  • 每个进程维护自己的页表（Page Table），用于将页号 → 页框号【第27页图】

页与页框的映射

  • 将逻辑内存也划分为大小相同的页（page），其大小等于页框大小。
  • 要运行一个 $N$ 页的程序，需要找 $N$ 个空闲的页框，把各页加载进去；各页框在物理内存中可以任意分散（非连续）。
  • 需要页表（page table）来完成逻辑地址到物理地址的转换。

地址结构【第28页图】

  • 假设逻辑地址是 $m$ 位，页面大小 $2^n$，则：
    • 页号（Page Number）= 高 $m-n$ 位
    • 页内偏移（Offset）= 低 $n$ 位

8. 内部碎片与页大小

  • 若页太大，内存浪费多；太小，则页表变大，效率下降。
  • 页大小通常为 4K、2MB、1GB（现代系统支持多种）。

9. 页表管理优化

问题：页表大（如 32位地址+4KB页 → 页表大小=4MB）

解决方法：

  1. 多级页表（Hierarchical Page Table）【第42页】

    • 将页表划分为两级甚至多级结构，节省内存。

  2. 哈希页表（Hashed Page Table）【第45页】

    • 针对地址空间很大的系统，使用哈希查找页。

  3. 反向页表（Inverted Page Table）【第47页】

    • 每个帧对应一个条目（包括进程ID + 虚拟页号）

10. TLB（Translation Lookaside Buffer）缓存机制

  • TLB 是快速缓存页表映射的小型内存（64~1024 项）【第36页】
  • TLB命中率（Hit Ratio） 越高越好
  • 命中：直接从TLB获取帧号
  • 未命中：访问页表，并更新TLB

访问效率计算【第39页】

有效访问时间（Effective Access Time, EAT）

EAT 是衡量使用 TLB 后系统平均访问一条数据/指令所需的时间。

公式：
$$
\text{EAT} = \alpha \times (c + m) + (1 - \alpha) \times (c + 2m)
$$

  • $\alpha$：TLB 命中率（命中概率）
  • $c$：访问 TLB 的时间（比如 10 纳秒）
  • $m$：访问内存的时间（比如 90 纳秒）

11. 共享内存页（Shared Pages）

  • 多个进程共享只读的库函数代码（如 printf）【第40页】

  • 只保留一份物理副本，节省内存。

  • 操作系统允许多个进程共享同一份只读代码（如 libc 中的 printf()）：

    • 每个进程的虚拟地址空间中都有自己的 libc 页
    • 但它们的页表都映射到相同的物理内存页

  • 条件：只读 + 相同代码

12. 分段与分页结合（Intel IA-32 示例）

  • 支持段（Segment）+分页（Paging）双重机制【第51页图】
  • 每个进程最多有 16K 段。
  • 段由 段选择子（Selector） 管理，分页负责页内管理。

13. 现代架构支持

x86-64（Intel）【第52页】

  • 虚拟地址：48 位（可扩展至 64 位）
  • 实际支持 4K、2MB、1GB 页大小
  • 使用 4 级页表结构

ARM 架构【第53页】

  • 支持多级 TLB、可变页大小（4KB、16KB、1MB、16MB）
  • 广泛应用于移动设备

总结表

技术 特点 优势 缺点
连续分配 固定或可变分区 实现简单 容易产生碎片
分页 页 + 帧映射 避免外部碎片 内部碎片 + 页表管理开销
TLB 页表缓存 提高地址转换速度 命中率低时效率下降
多级页表 节省页表空间 动态加载页表 增加地址访问次数
哈希页表 快速定位页 适用于大地址空间 冲突处理复杂
反向页表 每帧一个映射 节省空间 查找慢，需全表遍历
ARM/Intel 分页 支持多种页大小 灵活性高 实现复杂

Chapter 10: Virtual Memory

一、背景与动机（Background & Motivation）

多道程序设计（Multiprogramming）

  • 多个进程可以同时驻留在内存中以提高资源利用率。
  • 问题：当可用物理内存不足时，新进程无法运行。
  • 解决方案：使用换入/换出（swap in/out）机制，把当前进程移出内存，将新进程调入。

后备存储（Backing Store）

  • 是一个高速大容量磁盘空间，保存所有进程的镜像。
  • 支持直接访问内存映像。

见第4页图示：展示了操作系统如何交换 Process P 的映像。

二、虚拟内存概念（Virtual Memory）

定义

  • 虚拟内存允许程序的逻辑地址空间大于物理内存。
  • 只有需要的页面（pages）会被加载进内存。

优点

  • 程序不再受物理内存限制。
  • 提高程序运行速度，减少不必要的 I/O。
  • 支持更多用户/进程同时运行。

见第9页图示：展示虚拟地址空间远大于实际物理内存的结构。

三、请求分页（Demand Paging）

基本概念

  • 页面只有在被访问时才加载，未访问的不加载。
  • Pager 会在缺页时按需加载对应页面。

缺页中断（Page Fault）

  • 当进程访问尚未加载的页面时触发，由 MMU 检测。
  • 若地址非法（invalid），进程终止。
  • 若地址合法但页面未加载，则从硬盘读入并更新页表。

见第15页图示：详细描述了处理 Page Fault 的 6 个步骤。

四、局部性原理与性能（Locality & Performance）

局部性（Locality of Reference）

  • 进程访问内存时，往往集中在某些区域（局部性）。
  • 分为时间局部性与空间局部性。
  • 由此产生了工作集模型（Working-set Model）。
    • 定义：一个进程在一段时间内活跃使用的页面集合，称为工作集（working set）。
    • 用于预测进程当前所需的页面，避免频繁换入换出。
    • 使用固定窗口大小 Δ（Working Set Window）表示最近 Δ 次内存引用。
      记法：
      $WS(t, \Delta)$ 表示时刻 $t$ 前 $\Delta$ 次访问中的页面集合

有效访问时间（Effective Access Time, EAT）

  • EAT = (1 - p) * memory_access_time + p * page_fault_time
  • Page fault 频率 $p$ 需保持极小，通常 $< 0.0000025$。

Copy-on-Write (COW)

Copy-on-Write 是一种延迟复制技术，在父子进程共享页面时常被使用，主要用于提高进程创建效率。

1. 背景

  • 通常在使用 fork() 创建子进程时，系统需要复制父进程的所有内存页面。
  • 如果子进程只是 exec() 新程序，或者并不修改数据，复制会造成资源浪费。

2. 机制

在 Copy-on-Write (COW) 中：

  • 父子进程最初共享相同的物理页面。
  • 所有共享页面均设置为 只读（read-only）。
  • 若任一进程尝试修改共享页面，会触发写时异常（page fault），此时：
    1. 系统复制该页面（仅此一页）。
    2. 新页面分配给写操作的进程。
    3. 更新该进程的页表，使其指向新的页面。

图示见第24页图：
展示了共享页表如何在写入操作后产生新副本（f4 替代原 f3）。

3. 优势

  • 节省内存：直到需要写入前不实际分配页面。
  • 加快进程创建：fork() 不再复制整个地址空间，仅复制页表。
  • 结合 vfork() 使用效果更好：vfork() 保证子进程先执行 exec()，因此避免写入原有数据。

4. 实现要点

  • 页表项需设置“写保护”位（protection bit）。
  • Page Fault 处理程序需能识别 COW 页面，完成复制操作。
  • 适用于现代操作系统，如 Linux、Windows。

五、页面置换（Page Replacement）

背景

  • 内存满时需选择旧页面进行替换（victim page）。
  • 替换策略目标：最小化缺页次数。

全局 vs 局部分配（Global vs Local Allocation）

策略 描述 优点 缺点
Global 所有页面在系统全局池中共享，任何进程可抢占页面 提高吞吐量 单个进程性能不可控，容易饥饿
Local 每个进程只能使用自己分配的页框 性能稳定 总体内存利用率不高

置换算法（Replacement Algorithms）

  1. FIFO：先进先出，容易导致 Belady’s Anomaly。
  • 维护一个队列
  • Belady’s Anomaly
    • 直觉: 给进程2:分配更多内存（页框数增加）应当减少缺页次数。
    • 在某些情况下，页框数增加后缺页次数反而上升！
    • 原因：
      • 在 FIFO 算法 中，页面的淘汰只和“进入内存的先后顺序”有关：
      • 并不考虑页面是否频繁被访问
      • 所以可能会淘汰正被频繁访问的重要页面
      • 当页框数更多时，历史页面保留更久，因此“重要页面”更容易因为过早进入而被淘汰，从而导致缺页。
  1. OPT (Optimal)：理想算法，用于衡量其他算法。
  • 替换将来最长时间内不会被访问的页面。
  • 理论上最佳，提供评估标准
  • 未来不可预知，不能实际实现，仅供理论分析
  1. LRU (Least Recently Used)：最近最少使用，常用且较优。
  • 思想：替换最近最久未使用的页面。
  • 实现方法：
      1. Counter 方法：每个页面打时间戳，替换时选时间戳最小的。
      1. Stack 方法：使用链表维护访问顺序，每次访问将页面移到栈顶。
  1. Second-Chance：对 FIFO 加 reference bit 改进。
  • 若要淘汰的页面 reference bit 为 1 → 设为 0，跳过；
  • 为 0 → 直接替换。
  1. Enhanced Second-Chance：增加 modify bit。
  • 改进：使用二元组（reference bit, modify bit）作为淘汰依据，按下列优先级选淘汰页面：
  • (0,0) → 最佳，既没被用也没改动
  • (0,1) → 未用但已改动（需写回磁盘）
  • (1,0) → 被用过但未改动
  • (1,1) → 最差，最近被用且已改动

六、页框分配（Frame Allocation）

出于性能考虑，每个进程需要一个最小数量的帧。
这个最小值由计算机架构（如CPU）定义。
帧的最大数量由系统中的总帧数量（即物理内存）决定。

策略

  • 固定分配（Fixed Allocation）：相同/按比例分配页框。
    • 等量分配（Equal Allocation）：
      • 每个进程分配相同数量的帧。
      • 缺点： 对于小进程会浪费空间。
    • 比例分配（Proportional Allocation）：
      • 根据进程大小分配帧数。
      • 缺点： 进程大小可能在执行过程中发生变化。
  • 优先级分配（Priority Allocation）：依据进程优先级及大小动态分配。
    • 帧的分配比例依赖于进程的大小和优先级。
    • 会优先置换低优先级进程的页面。
  • 页面置换在页框数下降到阈值以下时启动。

见第48页图示：展示内存中页框回收与分配机制。

七、系统颠簸（Thrashing）

概念

  • 缺页率过高时，进程频繁进行换页，几乎没有执行有用工作。
  • 导致 CPU 利用率下降，系统反应恶性循环。
  • Thrashing（颠簸）： 进程忙于页面交换，而不是完成有用的工作。

解决办法

  1. 减少多道程序数量（降低进程数量）。
  2. 设置“可接受”的缺页频率阈值并使用局部页面置换策略。
  3. 增加物理内存。
  4. 升级硬盘性能。

缺页频率（Page-Fault Frequency）

  • 如果实际缺页率过低，说明分配的帧太多，可以回收一些帧。
  • 如果缺页率过高，说明帧不够，应该增加帧数

八、内核内存分配（Kernel Memory Allocation）

特点

  • 内核需要连续物理页，且结构尺寸多样。
  • 两种常用方法：
    1. Buddy System：按 2 的幂进行内存块分配。
    2. Slab Allocator：使用 slab 缓存，每 slab 存储固定类型对象。

第53-55页图示详细演示 Slab 分配方式及其内存布局。

九、其他优化考虑（Other Considerations）

  • 预分页（Pre-paging）：提前加载页面，减少缺页但可能浪费。
  • 页大小选择：在碎片、TLB、页表规模之间平衡。
  • 程序结构优化：应尽量行优先存取数组数据，减少缺页（见第57页示例）。

十、实际系统案例（Windows）

  • 使用请求分页并引入 clustering（簇式分页）。
  • 设置每个进程的 working set minimum / maximum。
  • 当系统内存紧张时，执行工作集修剪（Working set trimming）以释放内存。

以下是根据《Chapter 13: File-System Interface》幻灯片整理的中文详细讲义笔记（含英文关键术语），适用于操作系统课程教学或复习使用。讲义围绕文件系统接口的核心组成进行了结构化归纳。

Chapter 13: File-System Interface

一、文件的基本概念（File Concept）

文件（File）

  • 是一组相关信息的命名集合，存储在辅助存储器（secondary storage）上（如磁盘、SSD、U盘等）。
    a named collection of related information that is recorded on secondary storage (e.g. Disk, SSD, Flash, etc.)
  • 可能是字节序列、记录集合、位流，其含义由文件创建者定义。
    a sequence of bits, bytes, lines, or records, the meaning of which is defined by the file’s creator
  • 是用户视角下最小的逻辑存储单元，对应一个连续的逻辑地址空间（logical address space）。
    Smallest logical storage unit for user view
    uses contiguous logical address space

文件系统（File System）

  • 运行于磁盘之上，提供用户接口。
    resides on secondary storage (disks)
  • 将逻辑地址映射到物理存储，提供高效且方便的数据存储与访问能力。
    Provides user interface to storage, mapping logical to physical
    Provides efficient and convenient access to disk by allowing data to be stored, located, retrieved easily

二、文件属性与类型（File Attributes & Types）

文件属性（Attributes）包含：

  • Name：可读名称
  • Identifier：文件系统内部唯一标识符
  • Type：系统支持不同文件类型时必需
  • Location：磁盘上位置指针
  • Size：文件当前大小
  • Protection：访问权限（读/写/执行）
  • 时间戳与用户信息：用于保护、审计和监控用途

文件类型（File Types）

  • 通过扩展名（如 .c, .exe, .pdf, .jpg）识别。
  • 操作系统据此选择合适的程序打开文件。
  • 图示表格（第10页）清晰列出常见类型及其用途。

三、文件操作（File Operations）

操作系统支持如下基本操作：

  1. Create
  2. Write
  3. Read
  4. Reposition（移动文件指针）
  5. Truncate（清空内容但保留属性）
  6. Delete

除创建和删除外，所有操作必须先 open，再 close 文件。

四、文件访问方式（Access Methods）

1. 顺序访问（Sequential Access）

  • 按顺序依次读取/写入，支持命令：read_next，write_next，reset。

2. 直接访问（Direct / Random Access）

  • 可任意定位、读取指定块，支持命令：read n，write n，position to n。

3. 索引访问（Indexed Access）

  • 使用索引文件记录逻辑地址与物理位置的对应关系（如 VMS 操作系统）。

第11-12页图示清晰对比了三种访问方式的使用场景与结构。

五、目录结构（Directory Structure）

功能

  • 管理文件、提供命名与分组能力。
  • 每个文件系统对应一个目录结构。

常见结构：

  1. 单级目录（Single-level）
  2. 两级目录（Two-level）
  3. 树型结构（Tree-structured）
  4. 无环图结构（Acyclic-graph）

第17页图示对比了这四种目录结构，指出了文件共享、多名路径等扩展能力。

六、文件系统挂载（Mounting）

  • 文件系统在使用前必须先进行“挂载（mount）”。
  • 需指定一个“挂载点（mount point）”，通常是一个 an empty directory 空目录。
  • 系统会用新的文件系统替换挂载点原有内容。

第21页图示说明了挂载前后文件系统的结构变化。

七、文件共享与锁（File Sharing & Locking）

1. 文件共享（File Sharing）

  • 支持用户组共享文件访问权限。
  • 拥有者控制文件属性并授予访问权限。

2. 文件锁（File Locking）

  • 类似于读写锁（reader-writer lock）：
    • Shared lock：可并发读
    • Exclusive lock：独占写
    • Mandatory lock（如 Windows）：系统强制控制
    • Advisory lock（如 Unix）：需开发者遵守

第8页介绍了 Java 中使用 FileChannel.lock() 进行文件锁的代码示例。

八、文件保护（Protection）

1. 访问类型

  • Read：读
  • Write：写
  • Execute：执行
  • Append：追加
  • Delete：删除
  • List：列出属性

2. 访问控制

  • 每个文件有一份访问控制列表（ACL）。
  • UNIX权限位机制：
    • 使用 3 组权限位（owner, group, others）
    • 每组三个位：RWX
    • 例如：
      • rwxr-x--x 表示：
        • owner: 可读写执行
        • group: 可读执行
        • other: 仅执行

第27页展示了 UNIX ls -l 命令输出的文件权限详解。

九、远程文件共享（Remote File Sharing）

支持多种远程访问实现方式：

模式 描述
FTP 手动传输，支持匿名或认证访问
DFS（Distributed File System） 本地可见的远程目录
Web 浏览 文件浏览下载，实为 FTP 封装
Cloud computing 提供计算+存储+应用，常见于云盘服务

Chapter 14: File System Implementation

一、概览与结构（Overview & Structure）

文件系统实现目标：

  • 支持本地文件系统和目录结构。
  • 探讨磁盘块分配策略与空闲空间管理。
  • 优化性能。
  • 引入实例：WAFL 文件系统。

二、文件系统结构（File-System Structure）

1. 移动磁头机制（Moving-head Disk）

  • 每个扇区（sector）对应一个块（block），一般大小为512字节。
  • 所有磁盘I/O以块为单位操作。
  • 逻辑记录（logical record）不一定匹配物理块，需进行打包（packing）处理。

2. 分层结构（Layered File System）

  • 自顶向下分为：
    • 应用程序层（open, read, write, close）
    • 文件逻辑层（block 映射）
    • 文件组织模块（block分配）
    • 磁盘文件层（设备控制）
    • I/O控制（设备驱动、控制器）

三、磁盘上的结构（On-Disk Structures）

包括：

  • Boot control block：记录启动信息（如boot sector）
  • Volume control block（如superblock）：记录块数、空闲块等
  • Directory structure：包含文件名与 inode 或 FCB 号
  • File Control Block (FCB)：包含权限、大小、时间戳等元数据

见第8页图示：详细展示了不同操作系统（Unix/Linux/Windows）中的命名差异。

四、内存中的结构（In-Memory Structures）

包括：

  • 挂载表（mount table）：记录挂载点与文件系统类型。

  • 目录缓存（directory cache）：加速目录访问。

  • 系统全局打开文件表（system-wide open-file table）：

    • 包含FCB副本
    • 跟踪所有打开的文件

  • 每进程打开文件表（per-process open-file table）：

    • 保存指向全局表的指针与访问权限

  • Open a file

    • Search the directory structure on disk for the file and copy the content of entry (metadata) to system-wide open file table if the file is opened for the first time
    • Update the per-process open-file table by adding a pointer to system-wide open file table

  • Close a file

    • Remove the file entry in system-wide open file table if no process to use it any more
    • Update the per-process table by removing a pointer to system-wide open file table

五、虚拟文件系统（Virtual File System, VFS）

  • 提供统一接口支持多种文件系统。
  • 使用 对象模型，主要对象包括：
    • inode object：表示文件
    • file object：表示打开文件
    • superblock object：表示整个文件系统
    • dentry object：表示目录项

第12页图解说明：VFS 将不同文件系统抽象为统一接口层。

六、目录实现（Directory Implementation）

两种主要方式：

  1. 线性列表（linear list）：简单但查找慢
    • 改进：使用链表保持有序或 B+ 树加快查找。
  2. 哈希表（Hash Table）：提供更快搜索，冲突处理采用链表

七、磁盘块分配（Disk Allocation Methods）

1. 连续分配（Contiguous Allocation）

  • 优点：访问快、磁头移动少。
  • 缺点：需提前声明大小；可能产生外部碎片。

2. 修改的连续分配（Extent-Based）

  • 每个文件由多个连续块“extent”组成，支持动态增长。

3. 链式分配（Linked Allocation）

  • 每个块包含指向下一个块的指针。
  • 优点：无外部碎片。
  • 缺点：随机访问性能差。

4. FAT（File Allocation Table）

  • Windows常用。
  • 类似链表，但所有指针集中在一个FAT表中，便于缓存与访问。

5. 索引分配（Indexed Allocation）

  • 每个文件有一个索引块（index block），其中存储所有数据块指针。
  • 优点：支持随机访问。
  • 缺点：需要额外空间。
扩展方案（处理大文件）：
  • Linked Index Scheme
  • Multilevel Index
  • Combined Scheme（Unix UFS使用）：
    • 直接指针、间接、双重间接、三重间接

当然可以，以下是一个简洁明了的表格，总结了四种常见的磁盘块分配方法及其对 逻辑地址（LA）到物理地址（PA） 计算的影响：

📋 文件块分配方式与物理地址计算对比表

分配方式 逻辑地址拆解 物理块查找方式 是否需遍历链表 是否支持随机访问 物理地址计算方式
Contiguous LA ÷ block_size 起始块号 + Q ❌ ✅ (start_block + Q) × block_size + R
Linked LA ÷ (block_size - ptr_size) 顺着链表跳 Q 次 ✅ ❌ 找到第 Q 块的地址 + R
FAT LA ÷ block_size 在 FAT 表中跳 Q 次 ✅（可缓存） ✅ FAT[Q] 得到块号 → block × block_size + R
Indexed LA ÷ block_size 从索引块读取 Q 项 ❌ ✅ index_block[Q] → block × block_size + R
  • Q 是逻辑块号：Q = ⌊LA / block_size⌋
  • R 是块内偏移量：R = LA mod block_size
  • ptr_size 通常为1B（链式结构中的指针大小）

八、空闲空间管理（Free-Space Management）

常见方法：

  1. 位图法 (Bit vector (map))：使用0/1位表示块状态。
  2. 链表法 (Linked List)：空闲块构成链表。
  3. 分组法 (Grouping)：块中嵌套指向下一组空闲块。
  4. 计数法 (Counting)：记录起始块地址与连续块数量。

示例见第32-34页图解。

九、性能优化（Efficiency & Performance）

方法：

  • 使用缓冲区缓存（buffer cache）加速访问。
  • 异步写入（Asynchronous Write）减少阻塞。
  • 内存映射文件（Memory-Mapped Files）：利用虚拟内存技术将文件映射为内存页，可被多个进程共享，并支持 Copy-on-Write。
  • 统一缓冲区缓存（Unified Buffer Cache）：避免双重缓存，提高 I/O 效率。

Lecture Notes: Operating Systems

https://tosakaucw.github.io/lecture-notes-operating-systems/

Author

TosakaUCW

Posted on

2025-02-26

Updated on

2025-05-28

Licensed under

Comments

Catalogue

×