Lane
operating system

operating system

2025年09月18日 19.2k 字 大概 85 分钟

导航

ch1 introduction

1.10 computing environments

traditional

  • mainframe systems
    • 大型机（主机）的操作系统有：批处理系统、分时系统
  • Time-sharing Systems
    • 所谓分时是指多个用户分时共享使用同一台计算机，也就是说把计算机的系统资源（尤其是CPU时间）进行时间上分割，即将整个工作时间分成一个个的时间片，每个时间片分给一个用户使用，这样将CPU工作时间分别提供给多个用户使用，每个用户依次地轮流且使用一个时间片。
    • 响应时间是分时系统的重要指标，它是用户发出终端命令到系统作出响应的时间间隔
  • Desktop Systems

Chapter2 Operating-System Structures

内核模块

Linux系统调用

why

  • 系统调用是内核向用户进程提供服务的唯一方法，应用程序调用操作系统提供的功能模块（函数）。
  • 用户程序通过系统调用从用户态（user mode）切换到核心态（kernel mode），从而可以访问相应的资源。
  • 运行模式
    • 内核模式
    • 用户模式
  • 地址空间
    • 用户空间
    • 内核空间（在每个进程的虚拟地址空间中都是固定的）
  • 上下文

系统调用与内核函数

  • 内核函数在形式上与普通函数一样，但它是在内核实现的，需要满足一些内核编程的要求
  • 系统调用是用户进程进入内核的接口层，它本身并非内核函数，但它是由内核函数实现的
  • 当用户态的进程调用一个系统调用时，CPU切换到内核态并开始执行一个内核函数

系统调用处理程序

  • 系统调用本质上是用户通过执行一条特殊的指令主动请求内核服务。
  • 系统调用本质上是一种特殊的中断，处理程序(system_call()):它是在执行 int $0x80 或 syscall 指令时，内核最先执行到的代码。操作如下:
    • 在内核栈保存大多数寄存器的内容
    • 根据eax中所包含的系统调用号调用对应的特定服务例程
    • 调用名为系统调用服务例程（systemcallserviceroutine）的相应的C函数来处理系统调用
    • 通过ret_from_sys_call()函数从系统调用返回

系统调用中参数传递

  • 每个系统调用至少有一个参数，即通过eax寄存器传递来的系统调用号
  • 用寄存器传递参数必须满足两个条件
    • 每个参数的长度不能超过寄存器的长度
    • 参数的个数不能超过6个（包括eax中传递的系统调用号），否则，用一个单独的寄存器指向进程地址空间中这些参数值所在的一个内存区即可
  • 在少数情况下，系统调用不使用任何参数
  • 服务例程的返回值必须写到eax寄存器中

Chapter3 Process

3.1 进程概念

  • A process is a program in execution(an active entity, i.e. it is a running program),也就是说当一个可执行文件被加载到内存开始执行时就变成了一个进程，它是动态的。
  • 进程的内容:
    A process includes:
    • The program code, also called text section（代码段）
    • Program counter (PC)
    • Registers
    • Data section (global data)（数据段）
    • Stack (temporary data)
    • Heap (dynamically allocated memory)

进程状态

As a process executes, it changes state：

  • New（新）: The process is being created.
  • Running（运行、执行）: Instructions are being executed.需要注意的是一次只有一个进程可以在处理器上运行
  • Ready（就绪）: The process is waiting to be assigned to a processor (CPU).当进程处于就绪状态时，说明此时处理器不是空闲的，一定有进程在处理器上运行。一般按照一定的算法排成一个队列。
  • Waiting（等待、blocked阻塞）: The process is waiting for some event to occur.所有的进程都可能处于等待状态。处于等待事件的进程排在等待队列中，由于等待事件原因不同，等待队列可以按照事件分成几个队列。
  • Terminated（终止）: The process has finished execution.

进程控制块

  • 每个进程在操作系统内用进程控制块（通过链表组织）来表示，它包含与特定进程相关的许多信息：
    • Process state
    • Program counter
    • CPU registers
    • CPU scheduling information
    • Memory-management information
    • Accounting information
    • File management
    • I/O status information

3.2 进程调度

3.2.1 Scheduling Queues

  • Job queue（外存） –set of all processes in the system.尚未被操作系统加载到内存。
  • Ready queue（内存） –set of all processes residing in main memory, ready and waiting to execute.
  • Device queues –set of processes waiting for an I/O device.
  • Process migration between the various queues.

3.2.2 Schedulers

  • Long-term scheduler(or job scheduler)长程调度（或作业调度）
    • selects which processes should be brought into the ready queue.
    • invoked very infrequently (seconds, minutes)-》(may be slow)
    • controls the degree of multiprogramming多道程序的“道”
    • Most modern operating systems have nolong-term scheduler(e.g. Windows, UNIX,Linux)
  • Short-term scheduler(or CPU scheduler)短程调度（或CPU调度）
    • selects which process should be executed next and allocates CPU.
    • invoked very frequently (milliseconds) (must be fast).
  • Medium-Term Scheduler 中程调度
    • 当检测到内存压力过大时，或者某个进程长期处于阻塞状态，它会做出一个决定：暂时将这个进程“挂起 (Suspend)”。被换出的进程状态就从“就绪”或“阻塞”变成了“挂起”。当系统资源变得充裕（例如，其他进程执行完毕释放了内存），或者那个被换出的进程所等待的事件已经发生时，中程调度器可以决定将这个进程重新“激活”。激活的操作就是将该进程之前存放在磁盘交换区的数据重新加载回内存。

3.2.3 Context Switch

  • When CPU switches to another process, the system must save the state of the old process and load the saved state for the new process via a context switch
  • Context of a process represented in the PCB
  • Context-switch time is overhead; the system does no useful work while switching
  • Time dependent on hardware support

3.3 Operations on Processes

3.3.1 Process Creation

  • 创建时间:作业调度程序调度到某个job时将它装进内存并分配资源以创建进程。父进程创建子进程:一个正在运行的进程（称为父进程）可以执行系统调用来创建一个新的进程（称为子进程）。
  • Parent process create children processes, which, in turn create other processes, forming a tree of processes.
  • Generally, process identified and managed via a process identifier (pid)
  • Resource sharing：
    • Parent and children share all resources.
    • Children share subset of parent’s resources.
    • Parent and child share no resources.
  • Unix examples:
    • fork() creates a new process: 从系统调用fork 中返回时，两个进程除了返回值pid不同外，具有完全一样的用户级上下文。在子进程中，pid的值为0;父进程中，pid的值为子进程的进程号。
    • fork()调用一次，返回两次，一次在父进程中，一次在子进程中。

3.3.2 Process Termination

  • 引起进程终止的事件
    • 正常结束
    • 异常结束
    • 外界干预
  • Process executes last statement and asks the operating system to decide it (exit).
    • Output data from child to parent (via wait).
    • Process’ resources are deallocatedby operating system.
  • The parent process may wait for termination of a child process by using the wait()system call. The call returns status information and the pid of the terminated process。pid= wait(&status);
  • If no parent waiting (did not invoke wait()) process is a zombie（僵尸进程：子进程运行终止，父进程尚未调用wait()）
  • If parent terminated without invokingwait, process is an orphan（孤立进程:父进程没有调用wait()就终止了）

3.4 Interprocess Communication

  • IPC provides a Mechanism for processes to communicate and to synchronize their actions without sharing the same address space.
  • Two models of IPC
    • 共享内存：操作系统在物理内存中开辟一块特殊的内存区域，然后通过内存映射技术，将这同一块物理内存分别映射到多个进程各自的虚拟地址空间中。这样，这些进程就可以像访问自己的私有内存一样，直接读写这块共享区域，而无需内核的干预。
    • 消息传递：进程之间交换数据必须通过内核，在内核中开辟缓冲区，进程1把数据从用户空间拷贝到缓冲区，进程2再把这个数据读走，这就是IPC。

3.5 IPC in Shared-Memory Systems

  • 这块“公共白板”就是由操作系统在物理内存 (RAM) 中划出的一块特殊区域。操作系统会对需要通信的进程说：“好了，这块内存你们都可以访问、读取和写入。” 于是，这些进程就都能像访问自己的内存一样，直接访问这块公共区域了。
  • 有限缓冲区(Bounded Buffer):
    • 生产者 (Producer)：是后台的面包师，他不停地烤制新面包。
    • 消费者 (Consumer)：是前台的售货员，他不停地把面包卖给顾客。
    • 有限缓冲区 (Bounded-Buffer)：是柜台上的面包陈列架，它的空间是固定的，比如只能放 10 个面包。
    • 核心同步问题：
      • 缓冲区的状态问题：使用计数信号量来记录缓冲区的状态
      • 互斥访问问题：必须保证在任何时刻，只有一个人（一个进程）能够操作陈列架（缓冲区）。当一个人在操作时，另一个人必须等待。

3.6 IPC in Message-Passing Systems

Direct Communication

  • Processes must name each other explicitly:
    • send(P, message)- send a message to process P
    • receive(Q, message)- receive a message from process Q
  • Properties of communication link
    • Links are established automatically
    • A link is associated with exactly one pair of communicating processes
    • Between each pair there exists exactly one link
    • The link may be unidirectional, but is usually bi-directional

Indirect Communication

  • Messages are directed and received from mailboxes (also referred to as ports)
    • Each mailbox has a unique id
    • Processes can communicate only if they share a mailbox
  • Properties of communication link
    • Link established only if processes share a common mailbox
    • A link may be associated with many processes,因为中间存在邮箱，所以可能有多个进程。
    • Each pair of processes may share several communication links，每个链路对应一个邮箱。
    • Link may be unidirectional or bi-directional
  • 一个问题:
    • P1, P2,andP3 share mailbox A.P1, sends;P2 and P3 receive.Who gets the message?
    • 解决:Allow a link to be associated with at most two processes.Allow only one process at a time to execute a receive operation.Allow the system to select arbitrarily the receiver.Sender is notified who the receiver was.

同步

Buffering

  • Queue of messages attached to the link.Implemented in one of three ways
    1.Zero capacity –no messages are queued on a link.Sender must wait for receiver (rendezvous)
    2.Bounded capacity –finite length of nmessagesSender must wait if link full
    3.Unbounded capacity –infinite length Sender never waits

chapter3-练习题纠错

  • 解析： 调用子程序（subroutine call）是进程内部的正常执行流程，在用户态完成，不会引起操作系统内核的介入，因此不会触发进程调度。A（中断）、B（等待子进程）和 D（I/O请求）都会导致进程从用户态切换到内核态，并将CPU控制权交给操作系统，此时操作系统可以决定是否切换到另一个进程。
  • 系统调用必然会导致模式切换（Mode Switch，从用户态到内核态）。但它不一定会导致上下文切换（Context Switch，从进程A切换到进程B）。如果系统调用很快完成（例如，获取当前时间），内核会执行该调用然后立即返回到同一个进程的用户态，这期间没有切换到其他进程。
  • “唤醒”（waken up）一个进程意味着它所等待的事件已经发生（例如，I/O操作已完成）。因此，它的状态从等待态（Waiting） 变为就绪态（Ready），表示它现在可以运行了，正在等待CPU。
  • 需要注意的是使用fork()，子进程会创建一个父进程的副本，但是子进程对字段的影响并不会波及父进程。

Chapter4 Threads and Concurrency

4.1 Overview

  • 资源拥有单元称为进程(资源调度的基本单位)（或任务），cpu调度的基本单位称为线程、又称轻型进程（light weight process）。线程只拥有一点在运行中必不可省的资源（程序计数器、一组寄存器和堆栈），但它可与同属一个进程的其它线程共享进程拥有的全部资源。
  • 线程定义为进程内一个执行单元或一个可调度实体。也就是说每一个线程都有一个对应的进程。
  • 线程的内容
    • 有执行状态（状态转换）
    • 不运行时保存上下文
    • 有一个执行栈
    • 有一些局部变量的静态存储
    • 可存取所在进程的内存和其他资源
  • A thread shares withthreads belonging to the same process its:code section,data section,operating-system resources.但是寄存器需要自己拥有，用于保存上下文。

4.2 Multicore Programming

4.3 Multithreading Models

线程的实现机制

  • 用户级线程:不依赖于OS内核（内核不了解用户线程的存在），应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。调度由应用软件内部进行，通常采用非抢先式和更简单的规则，也无需用户态/核心态切换，所以速度特别快。一个线程发起系统调用而阻塞，则整个进程在等待
  • 内核级线程:依赖于OS核心，由内核的内部需求进行创建和撤销，用来执行一个指定的函数。一个线程发起系统调用而阻塞，不会影响其他线程。时间片分配给线程，所以多线程的进程获得更多CPU时间。

Many-to-one

  • Many user-level threads mapped to single kernel thread
  • Implemented by user-level runtime libraries
    • Create, schedule, synchronize threads at user-level
  • OS is not aware of user-level threads
    • OS thinks each process contains only a single thread of control
  • 在这个模型中，一个线程发起系统调用而阻塞，则整个进程在等待
  • Advantages
    • Does not require OS support
    • Can tune scheduling policy to meet application (user level) demands
    • Lower overhead thread operations since no system calls
  • Disadvantages
    • Cannot leverage multiprocessors (no true parallelism),本质上还是操作系统只操控一个内核线程。
    • Entire process blocks when one thread blocks，当一个用户级线程（比如线程 A）需要读取一个文件时，它会触发一个系统调用。这个系统调用最终是由它所映射的那个唯一的内核级线程来执行的。

One-to-one

  • Each user-level thread maps to kernel thread
  • OS provides each user-level thread with a kernel thread
  • Each kernel thread scheduled independently
  • Thread operations (creation, scheduling, synchronization) performed by OS
  • Advantages
    • Each kernel-level thread can run in parallel on amultiprocessor
    • When one thread blocks, other threads from process canbe scheduled
  • Disadvantages
    • Higher overheadfor thread operations
    • OS must scale well with increasing number of threads

Many-to-Many Model

线程优缺点

  1. 线程的优点： 一个进程中可以同时存在多个线程;各个线程之间可以并发的执行；各个线程之间可以共享地址空间和文件等资源，多个线程之间的通信是方便的。
  2. 线程的缺点：当进程中的一个线程崩溃时，会导致该进程内的所有其它线程都崩溃；我们说进程内的资源是线程共享的，那么多个线程来同时访问一块数据的时候该给哪个线程呢？所以线程存在着资源竞争；

4.4 Thread Libraries

4.5 Implicit Threading

Chapter 5:CPU Scheduling

5.1 Basic Concepts

  • CPU调度==处理机调度==进程调度

CPU Scheduler

  • 调度方式
    • 非抢占式:调度程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程.
    • 抢占式:当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。被抢占的进程回到就绪队列的队首。

5.3 Scheduling Algorithms

5.3.1 FCFS

  • FCFS算法
    • 按照进程或作业提交顺序形成就绪状态的先后次序，分派CPU
    • 当前进程或作业占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）在进程或作业唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU
    • 最简单的算法
  • FCFS的特点
    • 比较有利于长进程，而不利于短进程。
    • 有利于CPU Bound的进程，而不利于I/O Bound的进程。

5.3.2 SJF Scheduling

  • 又称为“短进程优先”SPF(Shortest Process First)；这是对FCFS算法的改进，其目标是减少平均周转时间。
  • SJF算法:对预计执行时间短的作业（进程）优先分派处理机。
  • Two schemes:
    • nonpreemptive – once CPU given to the process it cannot be preempted until completes its CPU burst
    • preemptive – if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. This scheme is know as the Shortest-Remaining-Time-First (SRTF)
  • 最优的算法，能够实现最短的平均等待时间。

5.3.3 Priority Scheduling

  • Associate a priority number with each process
  • 该算法总是把处理机分配给就绪队列中具有最高优先权的进程。常用以下两种方法来确定进程的优先权：
    • 静态优先权: 静态优先权是在创建进程时确定的，在整个运行期间不再改变。依据有：进程类型、进程对资源的要求、用户要求的优先权。
    • 动态优先权: 动态优先权是基于某种原则，使进程的优先权随时间改变而改变。假定：最小的整数 = 最高的优先级.
  • 同样具有非抢占式模式和抢占式优先级调度算法。

5.3.4 Round-Robin Scheduling

  • 基本思路：通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率。
  • RR算法：
    • 将系统中所有的就绪进程按照FCFS原则，排成一个队列。
    • 每次调度时将CPU分派给队首进程，让其执行一个时间片 (time slice) 。时间片的长度从几个ms到几百ms。
    • 在一个时间片结束时，暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行就绪队列的队首进程。
    • 进程可以未使用完一个时间片，就出让CPU（如阻塞）。

5.3.5 多级队列调度

  • 根据进程的性质或类型的不同，将就绪队列再分为若干个子队列。
  • 每个进程固定归入一个队列。
  • 各队列的不同处理：不同队列可有不同的优先级、时间片长度、调度策略等。如：系统进程、用户交互进程、批处理进程等。
  • 通常前台的交互式就绪队列采用时间片轮转；后台的批处理就绪队列采用FCFS.
  • 多级队列算法调度须在队列间进行
    • 固定优先级调度，即前台运行完后再运行后台。有可能产生饥饿
    • 给定时间片调度，即每个队列得到一定的CPU时间，进程在给定时间内执行；如，80%的时间执行前台的RR调度，20%的时间执行后台的FCFS调度。

5.3.6 多级反馈队列算法

  • 也是多个就绪队列并赋予不同的优先级，规定优先级越低时间片越长。
  • 每次新的进程会被放入到第一级队列（优先级最高）的末尾，按先来先服务的原则排队等待被调度，如果某个进程在第一级队列设置的时间片内没运行完，则将其转入到第二级队列的末尾，以此类推，直至完成；
  • 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列（如就绪队列3），则停止当前运行的进程（如就绪队列5）并将其移入到原队列末尾，接着让较高优先级的进程运行；

chapter5-习题纠错

Chapter 6:Process Synchronization

6.1 Background

  • 并发:在微观上进程并不是同时运行，而是交替进行。
  • 并行：在微观上进程同时进行。

bounded buffer

  • 原来的设计思路：一个大小为 N 的环形缓冲区 (Circular Buffer)：buffer[N]。一个“写入”指针 in：指向下一个空闲的、可以生产物品的位置。一个“读出”指针 out：指向下一个有物品的、可以消费物品的位置。我们牺牲一个存储单元。我们规定，缓冲区中最多只能存放 N-1 个物品。
  • 改进方案:保留 N 个槽位的缓冲区 buffer[N]。保留 in 和 out 指针。引入一个新变量：counter，初始化为 0。生产者逻辑： 每当它在 buffer[in] 放入一个物品，它就执行 counter++。消费者逻辑： 每当它从 buffer[out] 取出一个物品，它就执行 counter–。
  • 但是需要注意的是上述改进方案会引入一个新问题。很多题目也需要这样考虑，一行简单的高级语言代码:counter++,涉及三个步骤：读取，修改，写回。counter 是一个被多个线程（生产者和消费者）同时读写的共享变量会导致竞态。

进程同步的概念

  • 进程之间竞争资源面临三个控制问题：
    • 互斥（mutual exclusion）指多个进程不能同时使用同一个资源。
    • 死锁（deadlock）指多个进程互不相让，都得不到足够的资源。永远得不到资源。
    • 饥饿（starvation）指一个进程长时间得不到资源（其它进程可能轮流占用资源）。资源分配不公平
  • 进程并发执行如果是竞争资源则称为互斥；如果是合作关系则称为同步。

6.2 The Critical-Section Problem

  • 临界区就是每个进程的那段“访问共享数据的代码段”。
  • 必须确保当一个进程在临界区执行时，没有其他进程被允许在它们的临界区执行。
  • 临界资源:一次只允许一个进程使用(访问)的资源。

解决临界区问题必须实现的事

  • Mutual Exclusion(互斥): If process Pi is executing in its critical section, then no other processes can be executing in their critical sections.
  • Progress（空闲让进）：If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely
  • Bounded Waiting（有限等待）:A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted

6.3 Peterson’s Solution

单标志法

  • Only 2 processes, P0and P1
  • Shared variables:
    • int turn;initially turn = 0
    • turn = i：Pi can enter its critical section, i=0,1
  • 在每个进程的退出区将turn设置为另一个进程的编号
  • 缺点：强制轮流进入临界区，没有考虑进程的实际需要。容易造成资源利用不充分：在Pi出让临界区之后，Pj使用临界区之前，Pi不可能再次使用临界区

双标志先检查

  • Shared variables：
    • boolean flag[2];initially flag [0] = flag [1] = false.
    • flag [i] = true：Pi enter its critical section
  • 先检查再上锁。
  • P0和P1可能同时进入临界区。当flag [0] = flag [1] = false时，P0执行了while (flag[1])后，P1执行while (flag[0]) ，这样两个进程同时进入了临界区。

双标志后检查

1
2
3
4
5
6
P0:
flag[0] = true;
while(flag[1]);
critical section;
flag[0] = false;
remainder section;
  • P0和P1可能都进入不了临界区。当P0执行了flag[0] := true后，然后P1执行了flag[1] := true，这样两个进程都无法进入临界区。

Peterson

  • Combined shared variables of algorithms 1 and 2.
  • The two processes share two variables:
    • int turn;
    • boolean flag[2]
  • The variable turn indicates whose turn it is to enter the critical section.谁应该进入。
  • The flag array is used to indicate if a process is ready to enter the critical section. flag[i] = true implies that process Pi is ready!谁准备好进入没有。
1
2
3
4
5
6
7
P0:
flag[0] = true;
turn = 1;
while(turn == 1 && flag[1]);
critical section;
flag[0] = false;
remainder section;

6.4 Synchronization Hardware

Mutual Exclusion with Test-and-Set

  • Test-and-Set 是一种硬件指令，而不是一个普通的软件函数。这一点至关重要。它的关键特性是原子性 (Atomicity)。原子性意味着该指令的整个执行过程是不可分割的。当 CPU 执行这条指令时，它会“锁住”总线，防止任何其他 CPU 或进程在它完成之前访问同一个内存地址。
  • 如何使用Test-and-set实现互斥:
1
2
3
4
5
6
7
boolean lock = false; // 一开始，锁是打开的
while (TestAndSet(&lock) == true) {
    // do nothing; 
    // 只是不断地循环，直到锁被释放
}
临界区
lock = false;

Mutual exclusion with swap

1
2
3
4
5
6
7
while(1) {
key = TRUE;
while (key == TRUE) Swap(&lock , &key);
critical section
lock = false;
remainder section
}

总结

  • 硬件方法的优点
    • 适用于任意数目的进程，在单处理器或多处理器上
    • 简单，容易验证其正确性
    • 可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量
  • 硬件方法的缺点
    • 等待要耗费CPU时间，不能实现”让权等待”
    • 可能“饥饿”：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上
    • 可能死锁：单CPU情况下,P1执行特殊指令(swap)进入临界区，这时拥有更高优先级P2执行并中断P1,如果P2又要使用P1占用的资源，按照资源分配规则拒绝P2对资源的要求，陷入忙等循环。然后P1也得不到CPU，因为P1比P2优先级低。

Bounded-waiting mutual exclusion with TestAndSet

  • lock (布尔变量)：这是一个全局的“主锁”。它由 TestAndSet 原子地操作。lock = true 表示“有人在临界区或正准备进入”。
  • waiting[n] (布尔数组)：这是一个“排队”数组。waiting[i] = true 表示“进程 P_i 正在排队等待进入临界区”。
  • key (局部变量)：这是每个进程自己的一个局部布尔变量，用于控制自己的自旋。
  • 该算法可以成功满足临界区产生的三个问题
  • 进入区
    • 这里打破自旋等待就有两种可能，一种可能是锁没有被占用，成功被这个进程抢占；另一种可能是另外一个进程将资源的控制权交接到这个进程中。
1
2
3
4
5
6
7
8
9
waiting[i] = true;  // 1. 我(P_i)开始排队
key = true;         // 2. 准备开始自旋

// 3. 开始自旋等待
while (waiting[i] && key) {
    key = TestAndSet(lock);
}

waiting[i] = false; // 4. 我不再“等待”了（因为我马上要进入临界区了）
  • 退出区
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 1. 寻找下一个要进入的进程
j = (i + 1) % n; // 从我的下一个进程开始
while ((j != i) && !waiting[j]) {
    j = (j + 1) % n; // 跳过所有不在排队的进程
}

// 2. 决定如何“交接”
if (j == i) {
    // 情况 X: 绕了一圈回到自己，说明没有其他进程在排队
    lock = false; // 释放“主锁”
} else {
    // 情况 Y: 找到了一个正在排队的进程 P_j
    waiting[j] = false; // “交棒”：通过将其 waiting 设为 false 来“唤醒” P_j
}

6.5 semaphores

  • 将信号量想象成一个“受保护的计数器”，它控制着对一组共享资源的访问。
  • 这个“受保护的计数器”由两部分组成：
    • 一个整数 (Integer)： 这个数值表示“可用资源的数量”。
    • 两个原子操作 (Atomic Operations)： P 和 V。P(S) 等同于 wait(S)：尝试申请/消耗一个资源。V(S) 等同于 signal(S)：释放/归还一个资源。
    • “原子”意味着这些操作一旦开始，就必须完整执行到底，中途绝不会被中断。
  • wait的实现
1
2
3
4
5
6
7
8
9
10
11
wait(S) {
    // 1. 检查资源是否可用
    if (S.value > 0) {
        // 资源可用
        S.value--; // 消耗一个资源
    } else {
        // 资源不可用 (S.value == 0)
        // 1. 将当前进程/线程放入 S 的“等待队列”
        // 2. 阻塞 (Block) 该进程，使其进入“睡眠”状态 (不消耗CPU)
    }
}
  • signal的实现
1
2
3
4
5
6
7
8
9
10
11
signal(S) {
    // 1. 检查是否“有进程在等待”这个资源
    if (S 的等待队列中有进程) {
        // 有进程在等待
        // 1. 从等待队列中唤醒 (Wake up) 一个进程
        // 2. (被唤醒的进程将完成它的 wait 操作，并进入临界区)
    } else {
        // 没有进程在等待
        S.value++; // 归还一个资源
    }
}

信号量的类型

  • 计数信号量 (Counting Semaphore)
    • S.value 可以是任意非负整数（0, 1, 2, 3…）。
    • 用途： 用于管理多个相同的资源。
    • 例子： 一个系统有 5 台打印机。我们可以设置一个 S_printers 信号量，初始值为 5。每当一个进程想用打印机，它就执行 wait(S_printers)（计数器减 1）。当 S_printers 减到 0 时，第 6 个想用打印机的进程就会被阻塞，直到有人释放（signal）打印机。
  • 二元信号量 (Binary Semaphore)
    • S.value 只能是 0 或 1。
    • 用途： 用于实现互斥 (Mutual Exclusion)，即“锁”。
    • 说明： 它的功能与互斥锁 (Mutex) 几乎完全相同。

信号量的应用

  • 实现互斥
    • P1 调用 wait(mutex)，mutex.value 变为 0，P1 进入临界区。此时 P2 尝试调用 wait(mutex)。此时value为-1，说明等待队列中的进程数为1，P2进入阻塞状态。P1 完成临界区，调用 signal(mutex)。signal 发现 P2 在等待队列中，于是唤醒 P2。
  • 实现同步
    • 假设我们有两个进程，P1 和 P2。我们必须保证 P1 的 语句 A 执行完之后，P2 的 语句 B 才能开始执行。
    • 解决方案： 使用一个信号量 sync，初始值设为 0。初始值： sync = 0 (表示“P1 尚未完成”)。进程1运行完以后调用 signal(sync);进程2在运行代码前调用 wait(sync)。

6.6 经典进程同步问题

6.6.1 Bounded-Buffer problem

  • 我们使用一个大小为 n 的缓冲区，并定义三个信号量：
    • mutex (互斥信号量):用途：确保同一时间只有一个进程（生产者或消费者）可以访问缓冲区。类型： 二进制信号量（Binary Semaphore），也常称为锁。初始值： 1 （表示缓冲区当前可访问）。
    • empty (空槽位计数):用途：记录缓冲区中空闲槽位的数量。类型：计数信号量（Counting Semaphore）。初始值： n （缓冲区大小，表示初始时所有槽位都是空的）。
    • full (满槽位计数):用途：记录缓冲区中已占用槽位的数量（即有多少个数据项）。类型：计数信号量。初始值： 0 （表示初始时缓冲区是空的）。
  • 生产者进程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
do {
    // ... 生产一个数据项 (item) ...

    // 1. 等待空槽位
    //    如果 empty == 0 (缓冲区已满)，则在此阻塞
    wait(empty);

    // 2. 获取缓冲区的访问权限 (加锁)
    wait(mutex);

    // --- 临界区开始 ---
    // ... 将 item 放入缓冲区 ...
    // --- 临界区结束 ---

    // 3. 释放缓冲区的访问权限 (解锁)
    signal(mutex);

    // 4. 通知“满”槽位增加了一个
    signal(full);

} while (true);
  • 消费者进程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
do {
    // 1. 等待“满”槽位 (等待有数据可取)
    //    如果 full == 0 (缓冲区为空)，则在此阻塞
    wait(full);

    // 2. 获取缓冲区的访问权限 (加锁)
    wait(mutex);

    // --- 临界区开始 ---
    // ... 从缓冲区取出一个 item ...
    // --- 临界区结束 ---

    // 3. 释放缓冲区的访问权限 (解锁)
    signal(mutex);

    // 4. 通知“空”槽位增加了一个
    signal(empty);

    // ... 消费这个 item ...

} while (true);

6.6.2 Readers-Writers Problem

  • 读者优先进行解决：
    • 允许多个读者
    • 写者和读者互斥，写者之间也互斥
    • 读者优先：只要有任何读者在读，写者就必须等待，新来的读者的优先级高于写者。
  • 定义了三个共享变量：
    • Semaphore mutex = 1:这是一个互斥信号量（锁）。当读者需要执行 readcount++ 或 readcount– 时，必须先获取 mutex 锁，以防止两个读者同时修改 readcount 导致竞态条件（Race Condition）。
    • Semaphore wrt = 1:这也是一个互斥信号量（锁）。作用：它用来保证写者的独占访问，也是读者用来锁住写者的关键。
    • Integer readcount = 0:一个计数器，用来记录当前有多少个读者正在读取数据。
  • 写者进程
1
2
3
4
5
do {
    wait(wrt);
    // ... writing is performed ...
    signal(wrt);
} while (TRUE);
  • 读者进程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
do {
    // 1. "进入区" (Entry Section)
    wait(mutex);
    readcount++;
    if (readcount == 1) {
        wait(wrt);  // 第一个读者负责锁住“写锁”
    }
    signal(mutex);

    // 2. "读取区" (Critical Section for Reading)
    // ... reading is performed ...
    
    // 3. "退出区" (Exit Section)
    wait(mutex);
    readcount--;
    if (readcount == 0) {
        signal(wrt); // 最后一个读者负责释放“写锁”
    }
    signal(mutex);

} while (TRUE);

6.6.3 Dining Philosophers Problem

  • 如果使用一般的方法就会导致死锁的情况
  • 可能的几种解决措施
    • 允许最多四个哲学家参与拿筷子的过程
    • 只有两只筷子都可用时才能允许哲学家拿起来
    • 奇数序号的哲学家优先拿左侧的筷子；偶数序号的哲学家优先拿右侧的筷子。

6.7 Monitors

6.8 OS Synchronization

Chapter 6-review questions

  • 有一个东西方向的桥，东西方向都有行人通过，同一方向的行人可以连续过桥，另一方向的行人必须等待。
  • 创建三个信号量: x,mutexA,mutexB
  • countA,countB为两个信号量的计数器
1
2
3
4
5
6
7
8
9
10
11
12
13
//其中一个方向的代码
while(1)
{
  P(mutexA);
  countA++;
  if(countA==1) P(x);
  V(mutexA);
  walk
  P(mutexA);
  countA--;
  if(countA==0) V(x);
  V(mutexA);
}

Chapter 7:Deadlocks

7.1 System Model

The Deadlock Problem

  • 死锁：指多个进程因竞争共享资源而造成相互等待的一种僵局，若无外力作用，这些进程都将永远不能再向前推进

7.2 Deadlock Characterization

  • 死锁的必要条件：
    • Mutual exclusion:互斥
    • Hold and Wait:占有资源并等待
    • No preemption:不能抢占
    • Circular Wait:循环等待

Resource-Allocation Graph

  • 图中的节点主要分为两类：进程节点集合 ($P$)：$P = {P_1, P_2, \dots, P_n}$代表系统中所有活动的进程。图形表示：通常用圆圈 (Circle) 表示。资源节点集合（$R$）：$R = {R_1, R_2, \dots, R_m}$代表系统中所有的资源类型（如 CPU、打印机、内存块、互斥锁等）。图形表示：通常用矩形 (Rectangle) 表示。
  • 有向边描述了进程与资源之间的交互关系：申请边 (Request Edge)：$P_i \to R_j$含义：进程 $P_i$ 想要申请资源 $R_j$ 的一个实例，目前正在等待。方向：从 圆圈 指向 矩形。分配边 (Assignment Edge)：$R_j \to P_i$含义：资源 $R_j$ 的一个实例已经分配给了进程 $P_i$。方向：从 矩形内的黑点 指向 圆圈。
  • If graph contains no cycles：no deadlock.
  • If graph contains a cycle
    • if only one instance per resource type, then deadlock.
    • if several instances per resource type，possibility of deadlock.
  • 资源分配图的简化:
    • 先看系统还剩下多少资源没分配，再看有哪些进程是不阻塞的
    • 把不阻塞的进程的所有边都去掉，形成一个孤立的点，再把系统分配给这个进程的资源回收回来
    • 看剩下的进程有哪些是不阻塞的，然后又把它们逐个变成孤立的点。
    • 最后，所有的资源和进程都变成孤立的点。这样的图就叫做“可完全简化”。如果一个图可以完全简化则不会产生死锁

7.3 Methods for Handling Deadlocks

7.4 Deadlock Prevention

  • 互斥:not required for sharable resources; must hold for nonsharable resources.
  • Hold and wait:must guarantee that whenever a process requests a resource, it does not hold any other resources.
  • No preemption:
    • 当一个进程（Process）已经持有了一些资源，并且它现在申请新的资源。如果这个新申请的资源不能立刻被满足,那么该进程当前持有的所有资源都会被强制释放
  • Circular Wait:
    • 给每个资源赋予唯一的整数编号 $F(R)$,进程申请资源必须按照编号严格递增的顺序进行。如果你持有资源 $R_i$，你想申请 $R_j$，必须满足 $F(R_j) > F(R_i)$

7.5 Deadlock Avoidance

7.5.1 Safe state

  • 安全状态是指系统的一种状态，在此状态开始系统能按某种顺序（如P1、P2……Pn）来为各个进程分配其所需资源，直至最大需求，使每个进程都可顺序地一个个地完成。这个序列（P1、P2…….Pn）称为安全序列。若系统此状态不存在一个安全序列，则称系统处于不安全状态。
  • If a system is in safe state:no deadlocks.
  • If a system is in unsafe state:possibility of deadlock.
  • Avoidance:ensure that a system will never enter an unsafe state.

7.5.2 Resource-Allocation Graph Algorithm

  • 新的概念：需求边 (Claim Edge)为了进行预判，我们需要在标准的资源分配图中引入一种新的边：定义：$P_i \dashrightarrow R_j$ （虚线箭头）含义：表示进程 $P_i$ 在未来可能会申请资源 $R_j$。
  • 算法逻辑流程:
    • 检查该请求边 ($P_i \to R_j$) 是否可以变为分配边 ($R_j \to P_i$)。前提是资源 $R_j$ 当前必须是空闲的
    • 试探性分配，修改图，再检测是否存在环(我们在检测环的时候，要把所有的需求边也考虑在内，当作实线来看待,这代表了“最坏情况”下的依赖关系)
    • 如果有环则系统处于不安全状态，拒绝分配。否则处于安全状态，正式分配资源给$P_i$

7.5.3 Banker’s Algorithm

  • 四个关键数据结构,为了做出决策，操作系统需要维护以下数据：
    • Available（可利用资源向量）：系统中当前还剩下多少资源可用。例如：[3, 3, 2] 表示 A 类资源剩 3 个，B 类剩 3 个，C 类剩 2 个。
    • Max（最大需求矩阵）：每个进程这辈子总共需要多少资源。这是进程启动前就声明好的“信用额度”。
    • Allocation（分配矩阵）：每个进程目前已经手里拿着多少资源。
    • Need（需求矩阵）：每个进程还需要多少资源才能完成任务。计算公式：Need = Max - Allocation
  • 算法主逻辑（资源请求算法）：
    • 当进程 $P_i$ 发出资源请求向量 $Request_i$ 时：
    • 检查合法性：如果 $Request_i \le Need_i$，继续。否则，报错（请求超过了它声明的最大需求）。
    • 检查可用性：如果 $Request_i \le Available$，继续。否则，$P_i$ 等待（当前系统资源不足）。
    • 试探性分配 (Pretend to allocate)：修改系统状态，假设把资源分给它：$Available = Available - Request_i$$Allocation_i = Allocation_i + Request_i$$Need_i = Need_i - Request_i$
    • 执行安全性检查 (Safety Algorithm)：如果结果为 Safe $\Rightarrow$ 正式分配资源。如果结果为 Unsafe $\Rightarrow$ $P_i$ 必须等待，系统恢复到原来的状态（Rollback）。
  • 算法子逻辑即前面使用的安全性算法：
    • 初始化工作向量：Work = Available （表示当前可用于分配的资源副本）Finish = 全为 false 的向量 （长度为 $n$，标记进程是否完成）
    • 寻找可执行进程：查找满足以下两个条件的下标 $i$：Finish[i] == false （尚未完成）$Need_i \le Work$ （当前闲置资源足够满足该进程的需求）如果找不到这样的 $i$，跳转步骤 4。
    • 模拟进程执行与回收：Work = Work + Allocation_i （进程完成，归还资源）Finish[i] = true跳转回步骤 2。
    • 判断结果：如果所有 $i$ 的 Finish[i] 都为 true，则系统处于 安全状态 (Safe State)。否则，处于 不安全状态 (Unsafe State)。

7.6 Deadlock Detection

7.6.1 Single Instance of Each Resource Type

  • 核心概念：等待图 (Wait-for Graph)等待图是资源分配图 (Resource-Allocation Graph) 的简化变形。节点 (Nodes)： 代表进程 ($P_i$)。边 (Edges)： $P_i \to P_j$ 表示 $P_i$ 正在等待被 $P_j$ 占用的资源。转换方法： 将资源分配图中“资源节点”去掉，直接将请求资源的进程指向持有资源的进程。
  • 检测算法规则： 系统定期调用算法在图中搜索环 (Cycle)。结论： 如果等待图中存在环，则系统存在死锁；环上的所有进程都是死锁进程。算法复杂度： $O(n^2)$，其中 $n$ 是顶点（进程）的数量。

7.6.2 Several Instances of a Resource Type

  • 数据结构：
    • Available (向量 $m$)： 每种资源当前的空闲数量。
    • Allocation (矩阵 $n \times m$)： 每个进程当前已持有的资源数量。
    • Request (矩阵 $n \times m$)： 每个进程当前正在请求的资源数量。Request[i,j] = k：进程 $P_i$ 正请求 $k$ 个 $R_j$ 资源。
  • 检测流程：
    • 初始化 (Initialization)：设置两个辅助向量 Work (长度 $m$) 和 Finish (长度 $n$)。
    • 寻找可满足的进程寻找一个下标 $i$，满足以下两个条件：Finish[i] == false （尚未标记为完成）$Request_i \le Work$ （当前可用资源能满足它的请求）如果找不到这样的 $i$，跳转至步骤 4。
    • 模拟回收资源 假设该进程获得资源并运行结束：Work = Work + Allocation[i] （回收它占用的资源）；Finish[i] = true；跳转回步骤 2。
    • 判断死锁：如果存在某个i使得finishi[i] == false，则系统处于死锁状态。

Chapter 8: Main Memory

8.1 Background

地址绑定与重定位 (Address Binding)

  • 即指令和数据如何绑定到具体的内存地址。这个过程可以在三个不同的阶段发生：
    • 编译时 (Compile time):如果编译时就知道进程将驻留在内存的哪个位置，可以直接生成绝对代码 (Absolute code)。缺点: 如果起始地址发生变化，必须重新编译代码。
    • 加载时 (Load time):如果编译时不知道内存位置，编译器生成可重定位代码 (Relocatable code)。绑定推迟到加载时进行。
    • 执行时 (Execution time):如果进程在执行期间可以从一个内存段移动到另一个内存段，则绑定能延迟到运行时。要求: 需要特定的硬件支持（如基地址寄存器和界限寄存器）。现代通用操作系统大多采用这种方式。

用户程序的处理流程

  • 源代码-编译器-目标代码-链接器-可执行文件-加载器-内存中的程序

内存管理单元

  • MMU 是实现虚拟地址到物理地址映射的关键硬件设备。
    • 核心机制: 在简单的 MMU 方案中，通过重定位寄存器 (Relocation Register) 来实现。
    • 计算方式: $物理地址 = 逻辑地址 + 重定位寄存器的值$。当用户进程生成地址发送到内存时，硬件自动加上重定位寄存器的值
    • 重要概念: 用户程序只处理逻辑地址 (Logical Address)，永远看不到真实的物理地址。这提供了内存保护和抽象。

动态加载和动态链接

  • 动态加载
    • 只有在子程序被调用时才被加载到内存，所有程序以可重定位的形式存储在磁盘上。
  • 动态链接
    • 链接过程推迟到运行时。通常用于系统库
    • 技术层面：可执行文件中没有库函数的代码，只有一小段引用信息。真正的代码在程序运行时才由操作系统加载。
  • 两者的区别：动态加载不需要操作系统而是由程序本身实现，它侧重于单个进程的内存优化。动态链接由操作系统负责，它侧重于多进程间的代码共享。

8.2 Swapping

  • 定义: 进程可以暂时从内存中被换出（Swapped out）到备份存储中，随后再被换入（Brought back）内存继续执行。
  • 目的: 让物理内存能够承载比实际容量更多的并发进程。

8.3 Contiguous Allocation

8.3.1 单一连续分配

  • 内存布局:
    • 内存被分为两个区域：驻留操作系统 (Resident OS): 通常放在低地址内存（Low memory），与中断向量表在一起。用户进程区: 放在高地址内存（High memory）。
    • 硬件保护 (Hardware Protection):
      • 为了防止用户进程修改操作系统或其他进程的代码/数据，需要硬件支持。
      • 重定位寄存器 (Relocation/Base Register): 存放最小的物理地址值（基地址）。
      • 界限寄存器 (Limit Register): 存放逻辑地址的范围值（长度）。
      • 检查机制: 逻辑地址必须小于界限寄存器值，然后加上重定位寄存器值得到物理地

8.3.2 Multiple-parttion Allocation

  • 内存被划分为多个区域，每个分区容纳一个进程。
固定分区
  • 原理: 系统启动时将内存划分为若干个固定大小的分区（大小可以相等也可以不等）。
  • 缺点: 灵活性差，容易产生内部碎片（分区很大，进程很小，浪费了分区内的空间）。
动态分区
  • 管理: 操作系统必须维护两个表/链表：
    • 已分配分区表: 记录被占用的内存。
    • 空闲分区表 (Free partitions / Holes): 记录可用的内存孔洞。

8.3.3 动态分区算法

  • 背景：当有一个大小为n的进程申请内存时，如何从空闲空洞列表中选择。
  • First-Fit：从头开始查找，找到第一个足够大的孔洞就分配。
  • Netx-Fit：类似于首次适应，但不是每次都从头找，而是从上次查找结束的位置开始继续往后找
  • Best-Fit：搜索整个列表，找到最小的且适合这个进程的孔洞。
  • Worst-Fit：搜索整个列表，找到最大的孔洞。
  • 速度与利用率: 在速度和存储利用率方面，First-fit (首次适应) 和 Best-fit (最佳适应) 通常优于 Worst-fit (最差适应)。

8.3.4 碎片

  • 碎片的分类
    • 内部碎片：分配给进程的内存块比进程实际需要的稍大。浪费发生在已分配的内存块内部。
    • 外部碎片：系统中总的空闲内存足够满足新的请求，但这些空闲内存不连续，分散在各处，导致无法分配。
  • 外部碎片的解决方法：紧缩（compaction）
    • 移动内存中正在运行的进程，将所有分散的小空闲块“挤”到一起，合并成一个大的空闲块。
    • 必须支持动态重定位 (Dynamic Relocation): 地址绑定必须在执行时 (Execution time) 进行。
    • 代价昂贵：紧缩需要大量的CPU时间复制内存数据。

8.4 Paging

Implementation of Page Table

Effective Access Time (EAT)

1. Without TLB (Translation Lookaside Buffer):

每次数据/指令访问需要 2次 内存访问：

  1. 访问页表 (Page Table) 获取物理帧号。
  2. 访问实际物理地址获取数据。

Example:
If a memory reference takes 50 nanoseconds:
Paged memory reference time = 50ns (page table) + 50ns (data) = 100 nanoseconds.
性能降低了 100% (慢了一倍)。

2. With TLB:

为了解决上述速度问题，引入了 **TLB (快表)**。

  • Associative Lookup = $\epsilon$ time unit （快表访问时间）
  • Assume memory cycle time is $t$ （内存访问时间）
  • Hit ratio = $\alpha$ （命中率）
  • Effective Access Time (EAT):
    $$ \text{EAT} = (t + \epsilon)\alpha + (2t + \epsilon)(1 - \alpha) $$
    • Hit: TLB lookup ($\epsilon$) + Memory access ($t$)
    • Miss: TLB lookup ($\epsilon$) + Page table access ($t$) + Memory access ($t$)

Structure of the Page Table

Hierarchical Page Table
Hashed Page Table
Inverted Page Table

通常每个进程都有一个页表，页表项的数量取决于虚拟地址空间的大小。对于 64 位系统，虚拟地址空间非常大，导致页表占用大量内存。

反向页表 (Inverted Page Table) 的设计思路是：

  • 全局唯一：整个系统只有一个页表。
  • 基于物理内存：页表项的数量等于物理内存帧 (Frame) 的数量，而不是虚拟页面的数量。
  • 表项内容：每个表项包含：
    • 存储在该物理帧中的虚拟页号 (Virtual Page Number)。
    • 拥有该页面的进程 ID (Process ID, pid)。

地址转换过程：

  1. 虚拟地址包含 <pid, page_number, offset>。
  2. 系统在反向页表中搜索匹配 <pid, page_number> 的表项。
  3. 如果找到匹配项位于索引 i，则物理地址为 <frame_i, offset>。
  4. 如果未找到，则发生非法访问。

优缺点：

  • 优点：大幅减少了页表占用的内存空间（只与物理内存大小有关）。
  • 缺点：查找速度慢（最坏情况需要遍历整个表）。通常配合 哈希表 (Hash Table) 来加速查找。共享内存实现较困难。

8.5 Segmentation

Chapter 9: Virtual Memory

9.1 Background

9.2 Demand Paging

  • 如果这个页需要并且不在内存中，才从磁盘调入内存，这种方式称为需求分页 (Demand Paging)。

Page Fault

  1. 如果有对一个页的访问，第一次访问要陷入OS缺页，检查进程的页表，以确定该引用是合法还是非法的地址访问。
  2. 如果引用非法，那么终止进程。如果引用有效但是尚未调入页面，那么现在应调入。
  3. 找到一个空闲帧（从空闲帧链表中取一个）：如果没有空闲帧时，就需要使用页置换。
  4. 调度磁盘操作，以便将所需要的页调入刚分配的帧
  5. 当磁盘读操作完成后，修改进程的内部表和页表，以表示该页已在内存中。
  6. 重新开始因非法地址陷阱而中断的指令。进程现在能访问所需的页，就好像它似乎总在内存中。
  7. Three major components of the page-fault service time
    Service the page-fault interrupt(缺页中断服务时间)
    Read in the page(将缺页读入时间)
    Restart the process(重新启动进程时间)

9.3 Process Creation

Copy-on-Write

Copy-on-Write (COW) 是一种优化策略，用于在 fork() 系统调用时减少开销。

  • 基本原理：

    • 传统的 fork() 会创建子进程并完整复制父进程的地址空间（代码段、数据段、堆栈等），这非常耗时且浪费内存。
    • 使用 COW 技术，fork() 之后，父子进程共享相同的物理内存页面，而不是立即复制。
    • 这些共享页面被标记为**只读 (read-only)**。

  • 写时复制过程：

    • 如果父进程或子进程只是读取页面，它们继续共享物理内存。
    • 当任一进程尝试修改 (write) 共享页面时，硬件会触发一个保护故障（trap）。
    • 操作系统捕获该故障，分配一个新的物理帧，将该页面的内容复制到新帧中。
    • 更新执行写操作进程的页表，使其指向新的物理帧，并将页面标记为**可读写 (read-write)**。
    • 此时，两个进程各自拥有该页面的私有副本，互不干扰。

  • 优点：

    • 效率高：fork() 速度极快，因为只需复制页表，不需要复制大量数据。
    • 节省内存：如果子进程（如紧接着调用 exec()）不修改数据，就永远不需要复制物理页面。

  • **vfork()**：

    • 在 COW 出现之前，为了优化 fork() 后立即 exec() 的场景，引入了 vfork()。
    • vfork() 不复制页表，子进程直接在父进程的地址空间运行，父进程被挂起直到子进程调用 exec() 或 exit()。
    • 随着 COW 的普及，vfork() 的优势已不明显，且容易出错（子进程修改变量会影响父进程）。

9.4 Page Replacement

1. 概念与需求

在进程运行过程中，如果发生缺页 (Page Fault)，此时内存中又无空闲块 (Free Frame) 时，为了保证进程能正常运行，就必须从内存中调出一页程序或数据送磁盘的交换区。

  • 功能：需要调入页时，选择内存中哪个页被置换。这称为 **置换策略 (Replacement Policy)**。
  • 出发点：把未来不再使用的或短期内较少使用的页调出，通常只能在局部性原理指导下依据过去的统计数据进行预测。
  • 目标：从理论上讲，应将那些以后不再被访问的页换出，或把那些在较长时间内不会再被访问的页换出。

2. Basic Page Replacement (基本页面置换过程)

  1. 找到需要的页在磁盘上的位置。
  2. 找到一个空闲帧 (Find a free frame):
    a. 如果有一个空闲帧，使用它。
    b. 如果没有空闲帧，使用 页面置换算法 选择一个 **牺牲帧 (victim frame)**。
    c. 将牺牲帧的内容写入磁盘（如果它被修改过），并修改页表和帧表。
  3. 将需要的页读入到 (最新腾出的) 空闲帧中。更新页表和帧表。
  4. 重启进程 (Restart process)。

3. 优化与评估

  • Modify Bit (Dirty Bit):

    • 为了减少开销，使用修改位 (modify bit / dirty bit)。
    • 只有被修改过的页面 (modified pages) 才需要写回磁盘。如果页面未被修改，直接丢弃即可（因为磁盘上已有副本）。
    • 页面置换完成了逻辑内存与物理内存的分离，使得可以在较小的物理内存上提供巨大的虚拟内存。

  • 算法评估 (Algorithm Evaluation):

    • 目标：最低的缺页率 (lowest page-fault rate)。
    • 方法：在特定的 引用串 (reference string) 上运行算法，计算缺页次数。
    • 引用串示例：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

4.页面置换算法

页面置换算法用于选择哪个页面被置换出内存。好的算法应尽可能减少缺页率。以下是常见的页面置换算法。

1. FIFO Page Replacement (先进先出)

  • 描述：选择最早进入内存的页面进行置换。维护一个队列，新页面加入队尾，置换队头页面。

  • 优点：简单，易于实现。

  • 缺点：可能置换频繁使用的页面（Belady 异常：增加帧数可能增加缺页率）。

  • 例子：引用串 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，3 帧。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    引用 | 帧内容          | 缺页?
    1     | 1               | 是
    2     | 1 2             | 是
    3     | 1 2 3           | 是
    4     | 2 3 4           | 是 (置换 1)
    1     | 3 4 1           | 是 (置换 2)
    2     | 4 1 2           | 是 (置换 3)
    5     | 1 2 5           | 是 (置换 4)
    1     | 2 5 1           | 是 (置换 2)
    2     | 5 1 2           | 是 (置换 5)
    3     | 1 2 3           | 是 (置换 1)
    4     | 2 3 4           | 是 (置换 2)
    5     | 3 4 5           | 是 (置换 3)
    总缺页数: 12
2. Optimal Page Replacement (最优置换)

  • 描述：选择未来最长时间不会被访问的页面进行置换。需要预知未来引用串。

  • 优点：缺页率最低，理论最优。

  • 缺点：无法实现（需要预知未来），仅用于比较其他算法。

  • 例子：同上引用串，3 帧。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    引用 | 帧内容          | 缺页?
    1     | 1               | 是
    2     | 1 2             | 是
    3     | 1 2 3           | 是
    4     | 1 2 4           | 是 (置换 3, 3 下次在 10)
    1     | 1 2 4           | 否
    2     | 1 2 4           | 否
    5     | 1 2 5           | 是 (置换 4, 4 下次在 11)
    1     | 1 2 5           | 否
    2     | 1 2 5           | 否
    3     | 1 2 3           | 是 (置换 5, 5 下次在 12)
    4     | 1 4 3           | 是 (置换 2, 2 已无未来)
    5     | 5 4 3           | 是 (置换 1, 1 已无未来)
    总缺页数: 7
3. LRU Page Replacement (最近最少使用)

  • 描述：选择最长时间未被访问的页面进行置换。基于局部性原理。

  • 优点：性能好，近似最优。

  • 缺点：实现复杂，需要硬件支持（如栈或时间戳）。

  • 例子：同上引用串，3 帧。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    引用 | 帧内容          | 缺页?
    1     | 1               | 是
    2     | 1 2             | 是
    3     | 1 2 3           | 是
    4     | 2 3 4           | 是 (置换 1, 1 最久未用)
    1     | 3 4 1           | 是 (置换 2, 2 最久未用)
    2     | 4 1 2           | 是 (置换 3, 3 最久未用)
    5     | 1 2 5           | 是 (置换 4, 4 最久未用)
    1     | 2 5 1           | 否 (1 最近使用)
    2     | 5 1 2           | 否 (2 最近使用)
    3     | 1 2 3           | 是 (置换 5, 5 最久未用)
    4     | 2 3 4           | 是 (置换 1, 1 最久未用)
    5     | 3 4 5           | 是 (置换 2, 2 最久未用)
    总缺页数: 10
4. Clock Page Replacement (时钟算法)
  • 描述：改进的 FIFO，使用访问位。页面形成环形，指针扫描，置换访问位为 0 的页面。
  • 优点：简单，性能接近 LRU。
  • 缺点：仍可能置换有用页面。
  • 步骤：
    1. 扫描，访问位为 1 设为 0，继续。
    2. 找到访问位为 0 的页面置换。
算法比较
算法 优点 缺点 缺页率 (示例)
FIFO 简单 Belady 异常 高
OPT 最优 不可实现 最低
LRU 性能好 复杂 中等
Clock 平衡 近似 LRU 中等
5. 附加引用算法 (Additional Reference Bits Algorithm)
  • 描述：在 Clock 算法基础上，为每个页面维护一个 8 位引用计数器。每当页面被访问时，最高位设为 1，其他位右移。选择计数器值最小的页面置换。
  • 优点：近似 LRU，考虑近期访问历史。
  • 缺点：实现复杂，需要计数器。
  • 例子：页面访问时更新计数器，选择最小值置换。
6. 二次机会算法 (Second Chance Algorithm)
  • 描述：Clock 算法的别名。页面形成环形队列，指针扫描。如果页面访问位为 1，清零并继续；为 0 则置换。
  • 优点：简单，改进 FIFO，避免置换有用页面。
  • 缺点：仍可能不准确。
  • 步骤：
    1. 检查当前页面访问位。
    2. 如果 1，清零，继续下一个。
    3. 如果 0，置换。
7. 计数算法 (Counting-Based Algorithms)

计数算法使用访问计数器跟踪页面使用频率。

  • **LFU (Least Frequently Used)**：

    • 描述：选择访问次数最少的页面置换。维护每个页面的访问计数器。
    • 优点：基于长期使用频率，避免短期突发。
    • 缺点：可能保留旧页面，新页面难以进入；实现开销大。
    • 例子：页面 A 访问 10 次，B 访问 5 次，置换 B。

  • **MFU (Most Frequently Used)**：

    • 描述：选择访问次数最多的页面置换。假设频繁使用的页面近期不会再用。
    • 优点：适合某些工作负载。
    • 缺点：反直觉，可能置换有用页面；不如 LFU 常用。
    • 例子：页面 A 访问 10 次，B 访问 5 次，置换 A。

9.5 Allocation of frames

帧分配决定如何将物理内存帧分配给进程。主要考虑公平性和效率。

1. 固定分配 vs. 动态分配

  • **固定分配 (Fixed Allocation)**：

    • 每个进程分配固定数量的帧。
    • 优点：简单，易管理。
    • 缺点：不灵活，可能浪费或不足。

  • **动态分配 (Dynamic Allocation)**：

    • 根据进程需要动态调整帧数。
    • 优点：灵活，提高利用率。
    • 缺点：复杂，可能导致颠簸。

2. 局部置换 vs. 全局置换

  • **局部置换 (Local Replacement)**：

    • 进程只能置换自己的帧。
    • 优点：保护进程间干扰。
    • 缺点：可能低效。

  • **全局置换 (Global Replacement)**：

    • 进程可以置换任何帧。
    • 优点：灵活，高利用率。
    • 缺点：可能影响其他进程。

3. 分配算法

  • **相等分配 (Equal Allocation)**：每个进程分配相同帧数。
  • **比例分配 (Proportional Allocation)**：根据进程大小比例分配。
  • **优先级分配 (Priority Allocation)**：高优先级进程分配更多帧。

4. 工作集模型 (Working Set Model)

  • 定义：工作集是进程近期访问的页面集合。
  • 分配：根据工作集大小分配帧，避免颠簸。
  • 优点：适应进程行为。

5. 缺页频率 (Page-Fault Frequency)

  • 机制：根据缺页率调整帧数。
  • 上界和下界：缺页率过高增加帧，过低减少帧。

9.6 Thrashing

  • Thrashing  a process is busy swapping pages in and out.

Chapter 10: File-System Interface

10.1 File Concept

文件是存储在某种介质上（如磁盘、光盘、SSD等）并具有文件名的一组相关信息的集合。

File Attributes

文件属性是操作系统用来管理文件的关键信息。以下是常见的文件属性：

  • Name: 唯一的人类可读标识符，用于标识文件。
  • Identifier: 文件系统内部的唯一数字标签，用于系统识别。
  • Type: 文件类型（如文本、图像等），用于支持不同类型的文件系统。
  • Location: 文件在设备上的位置指针。
  • Size: 文件的当前大小（以字节为单位）。
  • Protection: 访问控制信息，决定谁可以读取、写入或执行文件。
  • Time, date, and user identification: 时间戳和用户标识，用于保护、安全和使用监控。

这些属性信息通常存储在目录结构中，并保存在磁盘上。

File Operations

（待补充：常见的文件操作如创建、打开、读取、写入、关闭等）

File Types

从操作系统角度，文件可以根据其性质和用途进行分类，主要包括：

  • 普通文件 (Regular Files): 包含数据或程序的普通文件，如文本文件、二进制可执行文件等。
  • 目录文件 (Directories): 包含其他文件和目录信息的文件，用于组织文件系统结构。
  • 特殊文件 (Special Files):
    • 字符设备文件 (Character Device Files): 如终端、打印机等，按字符流访问。
    • 块设备文件 (Block Device Files): 如磁盘，按块访问。
    • 管道文件 (Pipes/FIFOs): 用于进程间通信。
    • 套接字文件 (Sockets): 用于网络通信。
    • 符号链接 (Symbolic Links): 指向其他文件的指针。

从用户角度，使用文件扩展名分类文件。

File Structure

  • None (流文件结构): 序列化的字或字节，无结构。
  • Simple record structure (记录文件结构): 固定长度或可变长度的记录。
  • 复杂结构: 如树状或数据库结构。

10.2 Access Methods

  • 顺序访问 (Sequential Access): 文件按顺序从头到尾访问。
  • 直接存取 (Direct Access): 可以随机访问文件中的任意位置。

10.3 Directory Structure

目录结构是文件系统中用于组织和管理文件的层次结构。它包含了所有文件的相关信息，并与文件一起存储在磁盘上。目录结构的备份通常保存在磁带上。

目录的概念

  • 目录是一个节点集合，包含所有文件的相关信息。
  • 目录和文件都驻留在磁盘上。

磁盘结构

  • 磁盘可以划分为分区（partitions）。
  • 分区可以是RAID保护的，以防止故障。
  • 分区可以是原始的（无文件系统）或格式化为文件系统。
  • 包含文件系统的实体称为卷（volume）。
  • 每个卷跟踪文件系统信息在设备目录或卷目录中。
  • 除了通用文件系统，还有许多专用文件系统。

目录操作

目录支持以下操作：

  • 搜索文件
  • 创建文件
  • 删除文件
  • 列出目录
  • 重命名文件
  • 遍历文件系统

目录组织方式

目录组织的目标包括：

  • 效率: 快速定位文件。
  • 命名: 方便用户，避免重名问题（不同用户可有相同文件名，同一文件可有多个名称）。
  • 分组: 根据属性逻辑分组文件（如所有Java程序、游戏等）。
单级目录 (Single-Level Directory)
  • 所有用户共享一个目录。
  • 存在命名冲突和分组问题。
二级目录 (Two-Level Directory)
  • 每个用户有单独的目录。
  • 支持路径名。
  • 允许不同用户有相同文件名。
  • 搜索高效，但缺乏分组能力。
树型目录 (Tree-Structured Directories)
  • 高效搜索。
  • 支持分组。
  • 有当前目录（工作目录）概念。
  • 支持绝对路径和相对路径。
  • 创建/删除文件和子目录在当前目录中。
  • 删除目录会删除整个子树。
无环图目录 (Acyclic-Graph Directories)
  • 允许共享子目录和文件（硬链接）。
  • 支持别名（多个名称指向同一文件）。
  • 删除时可能导致悬空指针。
  • 解决方案：逆向指针、菊花链组织、表项保留计数（Unix/Linux中的硬链接）。
普通图目录 (General Graph Directory)
  • 允许更复杂的链接。
  • 可能形成环。
  • 保证无环的方法：只允许链接到文件而非子目录、使用垃圾回收、每次添加链接时运行环检测算法。
  • 快捷方式和符号链接可能形成环。

10.4 File System Mounting

文件系统挂载（Mounting）是将一个文件系统附加到现有目录树中的过程，使得该文件系统上的文件和目录可以被访问。

挂载的概念

  • 挂载点 (Mount Point): 目录树中的一个目录，用于挂载文件系统。
  • 挂载 (Mount): 将设备（如磁盘分区、USB驱动器）上的文件系统连接到挂载点。
  • 卸载 (Unmount): 断开文件系统与挂载点的连接。

挂载的目的

  • 允许操作系统访问不同存储设备上的文件系统。
  • 提供统一的目录视图，无论文件存储在哪个物理设备上。

示例

在Linux中，使用 mount 命令挂载文件系统：

1
mount /dev/sdb1 /mnt

这将 /dev/sdb1 分区挂载到 /mnt 目录。

10.5 File Sharing

（待补充：文件共享机制，如多用户访问、权限控制等）

10.6 Protection

（待补充：文件保护机制，如访问控制列表、权限位等）

Chapter 11: File System Implementation

（重要章节: 11.4, 11.5）

11.1 File-System Structure

文件系统采用分层设计：

  • 最顶层为应用程序
  • 逻辑文件系统：通过文件控制块维护文件结构（内存）
  • 文件组织模块（外存）
  • 基本文件系统：向合适的设备驱动程序发送一般命令就可对磁盘上的物理块进行读写
  • I/O控制

File System Types

文件系统类型多种多样，根据操作系统和用途而异。以下是常见的文件系统类型：

  • FAT (File Allocation Table): 简单、兼容性好，用于USB驱动器和早期Windows系统。支持文件大小有限（最大4GB）。
  • NTFS (New Technology File System): Windows现代文件系统，支持大文件、权限控制、加密和压缩。
  • ext4 (Fourth Extended File System): Linux主流文件系统，支持大容量、日志记录和性能优化。
  • APFS (Apple File System): macOS文件系统，支持快照、加密和空间共享。
  • ZFS (Zettabyte File System): 高可靠性文件系统，支持RAID、快照和数据完整性检查，常用于服务器。
  • Btrfs (B-Tree File System): Linux文件系统，支持快照、子卷和动态调整。
  • HFS+ (Hierarchical File System Plus): 旧版macOS文件系统，现被APFS取代。

In-Memory File System Structures

内存中的文件系统结构用于运行时管理，提高性能。这些结构包括：

  • In-Memory Partition Table (分区表): 记录磁盘分区的映射信息，帮助操作系统快速定位文件系统位置。
  • In-Memory Directory Structure (目录结构): 缓存目录项的副本，用于快速解析路径和查找文件，避免每次从磁盘读取。
  • System-Wide Open-File Table (系统打开文件表): 全局表，记录所有打开文件的元数据，如文件指针、访问模式和引用计数。确保文件一致性。
  • Per-Process Open-File Table (进程打开文件表): 每个进程的私有表，指向系统表的条目，支持进程级文件描述符管理。

这些结构通过缓存减少I/O操作，提升文件访问速度。示例：Linux VFS (Virtual File System) 抽象了不同文件系统的接口，实现统一访问。

11.3 Directory Implementation

11.4 Allocation Methods

文件系统中的分配方法决定如何在磁盘上为文件分配物理块。常见方法包括连续分配、链接分配和索引分配。

Contiguous Allocation

  • 描述: 每个文件占据磁盘上的一组连续的物理块。只需记录文件的起始块号和长度。
  • 优点:
    • 简单实现。
    • 访问文件容易，寻道时间最少（顺序访问高效）。
  • 缺点:
    • 为新文件找连续空间困难（类似内存的连续分配）。
    • 文件增长困难（需预留空间或移动文件）。
  • 应用: CP/M、一些嵌入式文件系统。

Linked Allocation

  • 描述: 每个文件是磁盘块的链表，块可分布在磁盘任何地方。使用指针链接块。
  • 优点:
    • 简单，只需起始位置。
    • 文件创建和增长容易，无需连续空间。
  • 缺点:
    • 不能随机访问（也就是说不能像contiguous allocation一样随机访问文件的某个块），必须遍历链表。
    • 指针占用空间（每个块需存储指针）。
    • 可靠性低（指针损坏会导致文件丢失）。
  • 改进: 使用簇（Cluster，将多个块组合），减少指针开销，提高访问效率。如Windows FAT。
  • 应用: FAT文件系统家族、部分Unix File System (UFS)。
FAT (File Allocation Table)

FAT是FAT32最关键的数据结构，用于管理磁盘空间分配和文件链。以下是关键点：

  • 位置: 位于保留区之后，通常有两个副本（FAT1和FAT2）以防损坏。FAT从卷的第N个扇区开始（N由BPB指定）。
  • 结构: 一个数组，每个条目对应一个簇（cluster，通常4KB）。条目值表示：
    • 0: 空闲簇。
    • 非0: 下一个簇号（形成文件链）。
    • 特殊值: 如0x0FFFFFF8表示文件结束，0x0FFFFFF7表示坏簇。
  • 作用:
    • 分配: 创建文件时，从FAT找空簇，标记为已用。
    • 链接: 文件的簇通过FAT链起来，支持文件增长。
    • 释放: 删除文件时，清空FAT条目，回收簇。
    • 性能: FAT常驻内存，减少磁盘访问。
  • 为什么关键: FAT使FAT32支持非连续分配（链接分配），平衡了灵活性和访问效率。FAT损坏会导致数据丢失，因此有备份。
FAT32 磁盘结构

FAT32磁盘结构基于MBR分区方案，分为多个区域。以下是FAT32卷（分区）的典型布局（从分区起始扇区开始）：

  • 保留区 (Reserved Area): 包括引导扇区（Boot Sector，第一个扇区），存储FAT32的引导代码、BPB（BIOS Parameter Block，包含卷信息如扇区大小、簇大小、FAT位置等）和备份引导扇区。
  • FAT区 (FAT Area): 包含主FAT表和备份FAT表（FAT2）。FAT是文件分配表，记录簇的分配和链接。
  • 根目录区 (Root Directory Area): 在FAT32中，根目录是普通目录，存储在数据区的一个簇中（不像FAT16有固定位置）。
  • 数据区 (Data Area): 存储文件和目录数据，按簇分配。

启动过程: BIOS加载MBR（分区表）→ 激活分区的引导扇区 → 加载FAT32引导代码 → 操作系统初始化。

FAT32 目录项结构

目录项（Directory Entry） 是文件系统中目录的组成部分，每个目录项是一个固定大小的记录（在FAT32中为32字节），用于存储文件或子目录的元数据信息。它相当于目录中的“条目”，描述了文件/目录的名称、属性、位置、大小等，帮助操作系统快速查找和管理文件。

  • 每个目录项32字节：这是FAT32的标准大小，确保一致性和效率。
  • 短文件名项（Short File Name Entry）：用于兼容旧系统，存放基本信息。
    • 文件名（8字节 + 3字节扩展名）。
    • 属性（1字节）：如只读、隐藏、系统、目录等（属性值0x20表示普通文件）。
    • 起始簇号（2字节）：文件数据的起始位置。
    • 文件大小（4字节）：以字节为单位。
    • 时间戳：包括创建时间、修改时间、最后访问日期等。
  • 长文件名项（Long File Name Entry）：支持超过8.3格式的长文件名，使用Unicode编码。
    • 由多个32字节项组成（每个项存放13个Unicode字符）。
    • 属性：固定为0x0F，表示长文件名项。
    • 校验和：用于验证短文件名项的完整性（防止不匹配）。
    • 顺序标记：低5位表示项的顺序（如00001为第一项），第6位为1表示最后项。
    • 多余空间：用0x00结束，然后用0xFF填充。

目录项存储在目录的簇中，形成目录的内容。操作系统通过解析这些项来列出目录或访问文件。

Indexed Allocation

索引分配（Indexed Allocation）是一种文件分配方法，每个文件使用一个索引块（index block）来存储指向数据块的指针数组。索引块本身存储在磁盘上，其位置记录在文件的inode或目录项中。

  • 描述: 文件的数据块可以分散在磁盘上，但通过索引块集中管理指针。要访问文件的第n个块，直接从索引块的第n个指针读取，无需遍历。
  • 优点:
    • 支持随机访问：可以直接跳转到任意块，提高性能。
    • 灵活：文件块无需连续，易于增长。
    • 无外部碎片：块分散但通过索引统一。
  • 缺点:
    • 索引块占用额外空间：对于小文件，索引块可能浪费（例如，一个块的文件仍需一个索引块）。
    • 复杂性：需要管理索引块，可能导致内部碎片。
    • 大文件问题：如果索引块满，需要多级索引（如间接块）。
  • 变体:
    • 单级索引: 索引块直接指向所有数据块。
    • 多级索引: 索引块指向其他索引块，形成树状结构，支持超大文件（如Unix的inode使用直接、间接、双间接指针）。
  • 应用: Unix文件系统（UFS）、NTFS的部分实现。适合需要随机访问的应用，如数据库文件。

11.5 Free-Space Management

  • 为了记录空闲磁盘空间，系统需要维护一个空闲空间链表，它记录了所有空闲磁盘空间，即未分配给文件或目录的空间。（不一定以链表的方式实现）
本文总阅读量次
本文作者：Lane
本文链接：https://lakerswillwin.github.io/2025/09/18/os/
版权声明：本文采用 CC BY-NC-SA 3.0 CN 协议进行许可
cs课程