操作系统知识点速通

前言

本篇文章适合《操作系统》考试前几天的突击复习，内容比较全但是深度不够，所以仅针对期末考试进行速通，想对某一知识点进行深入了解可以结合其他文章或AI食用。

第一章 引论

什么是操作系统（OS)？

是一组 “控制和管理计算机软硬件资源、合理组织计算机工作流程以及方便用户程序” 的系统软件。

操作系统的作用

• 扩展了的机器：

  • 隐藏硬件细节；

  • 提供方便接口；

• 资源管理器：

  • 时间上复用：实现多道程序；

  • 空间上复用：多用户；

操作系统的基本特征

1. 共享性：多个用户程序共同使用一个计算机系统的软硬件资源。

2. 并行性：具有同时处理多个事件的能力。

3. 虚拟性：一个物理实体可以映射出多个逻辑实体的能力，如虚拟内存、虚拟设备。

4. 异步性：多道程序环境中，进程以不可预知的速度向前推进。

操作系统的基本功能

1. 进程管理： 如进程创建、进程控制、进程同步、进程通信、处理机调度。

2. 存储管理： 如内存分配、内存保护、地址映射、内存扩充。

3. 设备管理： 如缓冲管理、设备分配、设备处理。

4. 文件管理： 如外存管理（文件存储）、目录管理（文件检索）、文件读写和保护。

5. 用户接口： 如系统调用（用户接口）、命令接口、图形接口。

6. 作业管理： 如作业组织、作业调度。

操作系统的四个发展阶段

1. 真空管和穿孔卡片阶段

   • 手工操作，无操作系统；

   • 资源利用率低、可靠性低，CPU与I/O速度不匹配；

2. 晶体管和批处理系统阶段

   • 吞吐量大、平均周转时间长、无交互能力；

   • 提高了CPU和I/O速度的匹配程度；

3. 集成电路和多道程序设计阶段

   • 出现了多道程序设计技术和Spooling技术（假脱机）；

   • 出现了UNIX操作系统；

   • 多道性、交互性、资源效率高；

4. 个人计算机阶段（现代操作系统）

   • 出现了更多OS：个人OS、网络OS、分布式OS、嵌入式OS、智能化OS、面向对象OS；

操作系统的分类

1. 批处理系统：

   • 脱机使用、无交互性、成批处理；

   • 作业周转时间长；

   • 资源利用率高、吞吐量大；

2. 分时系统：

   • 多路性、交互性、及时性、独立性；

   • 系统按时间片轮流为多个终端用户服务；

3. 实时系统：

   • 多路性、交互性、及时性、独立性；

   • 事件驱动服务；

操作系统的体系结构

1. 单核体系结构（宏内核）：主要服务均运行在内核态，各模块直接可直接调用。效率高，但内核规模大、模块联系复杂。

2. 分层体系结构：把操作系统分为若干层，每层只使用下层提供的功能。层次清楚、接口明确，便于设计和验证。

3. 客户端—服务器体系结构：客户进程提出请求，服务器进程提供服务，双方通过消息传递通信。

4. 微内核体系结构：只把进程通信、基本调度等最基本的功能保留在内核，其他服务作为用户态进程运行。

5. 虚拟机体系结构：虚拟机监控程序在一台物理机上建立多个相互隔离的虚拟机，每台虚拟机可运行自己的操作系统。

常见的操作系统

UNIX、Linux、Windows、macOS、iOS、Android 主要属于分时系统。

1. UNIX：是一种多用户、多任务、分时操作系统。传统UNIX通常采用单体内核（宏内核）体系结构。

2. Linux：是一种多用户、多任务、分时操作系统，采用支持动态模块的单体内核（宏内核）体系结构。

3. Windows：是一种通用型、多用户、多任务操作系统，Windows NT系列采用混合内核体系结构。

4. mac/OS：是一种多用户、多任务的桌面操作系统，属于UNIX类操作系统，采用XNU混合内核体系结构。

5. iOS：是一种面向移动设备的多任务操作系统，也可归为嵌入式操作系统，采用XNU混合内核体系结构。

6. Android：是一种基于Linux内核的移动和嵌入式操作系统，整个系统采用分层结构，其内核属于模块化单体内核（宏内核）。

简记：

• UNIX、Linux：宏内核为主；

• Windows：混合内核；

• macOS、iOS：XNU混合内核；

• Android：Linux宏内核＋分层系统结构；

批处理系统

1. 单道批处理：每次只允许一个作用进入内存并运行；

2. 多道批处理：每次可调入多个作业进入内存并运行，并且在单处理器环境下体现出 宏观并行、微观串行的特点。

多道程序设计技术

1. 概念：多道程序设计技术是在内存中同时存放若干道相互独立的程序****，使它们在管理程序控制下交替运行。

2. 优点：

   • 减少CPU空闲等待时间；

   • 提高CPU利用率、设备利用率，系统吞吐量；

3. 原因：当一道程序因为I/O操作而暂停时，CPU可以转去执行另一道就绪程序，使CPU与I/O设备冰箱工作，减少了CPU空闲等待的商家欧酷，提高了CPU利用率、设备利用率和系统吞吐量。

用户接口

1. 系统调用：用户程序使用该接口访问系统资源，从而获取操作系统服务。

2. 命令接口：用户输入命令控制系统运行，常见shell命令：login、logout、ls、cd、mkdir、cp、mv、rm。

3. 图形接口：以窗口、图标等图形化方式向用户提供操作界面。

系统调用

1. 概念：是OS提供给用户程序的程序接口，用户程序通过系统调用获取系统资源并获取OS服务。

2. 意义：使用户程序在不直接执行特权指令的情况下完成对设备、文件、进程的控制。

3. 基本步骤：

   • 用户程序准备参数：将系统调用所需的参数放入寄存器、栈或指定内存区域。

   • 设置系统调用号：将所请求的系统调用编号放入规定的寄存器中，内核根据该编号判断要执行哪一种服务。

   • 执行陷阱指令： 用户程序执行专门的陷阱指令或系统调用指令，引起一次软中断。

   • 由用户态切换到内核态：CPU保存当前用户程序的现场，包括程序计数器、程序状态字和寄存器等，然后进入内核态。

   • 系统调用分派：内核中的系统调用入口程序检查系统调用号和参数，并转入对应的系统调用处理程序。

   • 执行内核服务：内核完成相应操作，例如创建进程、读写文件、申请内存或控制设备。

   • 返回执行结果：内核将执行结果或错误码放入规定的寄存器或内存位置。

   • 恢复用户程序现场： 恢复寄存器、程序计数器等现场，由内核态返回用户态，用户程序从系统调用后的下一条指令继续执行。

   流程简记：准备参数 → 设置调用号 → 陷入内核 → 保存现场 → 分派调用 → 执行服务 → 返回结果 → 恢复现场。

系统启动

• 概念：是将OS读入内存的工作。

• 基本步骤：

  • 加电自检： 计算机上电后，CPU从固定的复位地址开始执行BIOS程序。

  • 内核加载： BIOS找到启动设备后，将引导程序装入内存并执行。

  • 系统初始化： 内核开始运行后，完成系统初始化。

CPU的工作模式

1. 划分标准：按照对 系统资源和机器指令的使用权限 划分的。

   • 内核态： 可以执行全部指令，包括 特权指令和非特权指令，并可访问全部系统资源和所有硬件功能。

   • 用户态：只能执行非特权指令，只能访问操作系统允许的资源，不能直接操作硬件。

2. 划分意义：防止用户程序直接执行特权指令和访问任意硬件，保证系统的安全和稳定。

基础硬件设备

冯·诺伊曼 CPU结构图。

1. 处理器： 通用寄存器（R）、程序计数器（PC）、程序状态字（PSW）、栈指针（Stack Pointer）。

2. 存储器： 寄存器、高速缓存（Cache）、主存、外存（磁盘）、磁带。

3. I/O设备： 设备控制器、设备驱动程序、中断控制器。

4. 总线： CPU、内存、设备控制器通过总线传输数据、地址以及控制信号。

中断与陷阱

1. 中断概念：CPU执行程序过程中出现外部或内部事件时，暂停当前程序，转去执行相应处理程序，处理完成后再恢复原程序。主要由外部事件异步产生。

2. 陷阱概念：由当前指令主动或同步引起的控制转移。用户程序通过陷阱指令进入内核态，常用于实现系统调用。

3. 中断处理步骤：

   • 中断请求： 由外部设备、定时器或程序异常向CPU发出中断请求。

   • 中断判断与响应： CPU在当前执行执行结束后检查中断请求，根据中断优先级和中断屏蔽状态决定是否响应。

   • 保存断点和处理机状态：CPU保存被中断程序的下一条指令地址、程序状态字等信息；操作系统进一步保存通用寄存器等现场。

   • 切换到内核态： CPU由用户态转入内核态，禁止或限制部分中断，防止现场被破坏。

   • 确定中断源： 根据中断类型号、中断向量表或查询设备状态，确定产生中断的设备或原因。

   • 执行中断处理程序： 转入相应的中断服务程序，完成数据传送、状态处理、清除中断请求、唤醒等待进程等工作。

   • 恢复现场： 恢复被中断程序的寄存器、程序状态字和程序计数器等信息。

   • 中断返回： 执行中断返回指令，恢复原来的处理机状态，从断点处继续执行程序；若发生调度，也可能转去执行另一个进程。

   速记：提出请求 → 中断判响 → 保存现场 → 确定中断源 → 执行处理程序 → 恢复现场 → 中断返回。

   与系统调用步骤作区分。

第二章 进程与线程

什么是程序？

• 概念： 是一组静态的指令集合。

• 特点：顺序性、封闭性、可再现性。

什么是进程？

• 概念： 是一次程序的动态执行，是进行系统资源分配的基本单位。

• 特点：

  1. 独立性：进程可以独立运行、独立获得资源和独立接受调度。

  2. 动态性：进程具有创建、运行、阻塞、唤醒、和撤销的生命周期。

  3. 并发性：多个进程可在同一时间间隔内推进。

  4. 异步性：进程按各自独立、不可预知的速度向前推进。

• 组成： 由 程序、数据集合、进程控制块PCB 组成。

进程控制块的作用：

• 是进程存在的唯一标志。

• 包含处理机信息、进程调度信息、描述信息、进程控制信息、资源管理信息。

并发、并行、异步的区分

• 并发：两个或两个以上的事件在同一时间间隔内发生，体现在单处理机环境下的多道程序 宏观并行、微观串行 的特征。

• 并行：两个或两个以上的事件在同一时刻发生，一般在多CPU环境下才能真正实现。

• 异步：发起一个操作后，不必等待该操作完成，就可以继续执行后续任务。操作完成后，再通过回调、事件、通知、消息或返回结果等方式通知其处理结果。

进程与程序的区别

• 程序是静态的指令集合，而进程是动态的程序执行。

• 进程是资源分配的基本单位，而程序通产不直接占用资源。

• 进程可以并发执行，程序不具有并发性。

• 一个程序可以产生多个进程，一个程序可以多次执行。

进程的基本状态

• 就绪态： 进程已获得除CPU外的全部所需资源，只等待处理机（CPU）。

• 运行态： 进程正在占用CPU执行。

• 阻塞态： 进程因等待I/O、信号或事件而暂时不能运行。

转换关系：

• 就绪——>运行：调度程序选择该进程并分配CPU。

• 运行——>就绪：时间片用完、被更高优先级进程抢占或主动让出CPU。

• 运行——>阻塞：进程请求I/O，等待信号或资源。

• 阻塞——>就绪：所等待的事件发生，进程被唤醒并进入就绪队列。

进程的创建

1. 创建原因：

   • 系统初始化；

   • 用户启动一个应用程序；

   • 正在运行的进程通过系统调用创建子进程；

   • 批处理系统调入一个新作业；

   • 为某项服务创建后台进程。

2. 创建步骤：

   • 为新进程分配唯一的进程标识符 PID；

   • 创建并初始化进程控制块 PCB；

   • 为进程分配地址空间、内存及其他资源；

   • 初始化寄存器、程序计数器、优先级、状态等信息；

   • 建立父子进程、队列等组织关系；

   • 将进程插入就绪队列。

3. PCB：

   保存信息：PID、进程状态、程序计数器、CPU寄存器、调度信息、内存管理信息、打开文件和I/O资源、父进程、子进程等关系信息。

4. fork()创建子进程 ：

   fork()执行一次，会在两个进程中返回：
    父进程中返回子进程PID； 
    子进程中返回0； 
    创建失败返回-1。
   

   • fork()具有两个正常返回值，因为父进程和子进程都会从fork()之后继续执行。

   • 父子进程具有各自独立的地址空间，现代系统一般使用**写时复制，**只有发生修改时才真正复制相关内存页。

5. exec()加载并执行新程序：

   用一个新程序替换当前进程的程序映像，它不会创建新的进程。执行后：

   • PID通常不变；

   • 进程仍然是原来的进程；

   • 原来的代码、数据和栈被新程序替换。

6. exit() 终止当前进程。

7. wait() 用于父进程等待并回收子进程。

进程的终止

• 正常结束：进程完成后主动退出。exit（0）；

• 出错退出：程序发现错误，主动结束，例如文件打不开、参数错误。

• 严重错误：除零、非法指令、越界访问、内存访问错误；

• **被其他进程或操作系统终止：**如父进程终止子进程。

进程终止后，资源不会总是在同一时刻全部消失。退出状态可能暂时保留，等待父进程读取。

注意：

• 父进程先结束，子进程成为孤儿进程。

• 子进程已结束、父进程未回收，形成僵尸进程。

• 进程终止时需要释放资源并最终撤销PCB。

进程的层次结构

1. 父进程和子进程：一个进程创建另一个进程时

   • 创建者称为父进程；

   • 被创建者称为子进程。

2. 父子进程是否共享资源：父子进程并不是完全共享所有资源，各自有独立的地址空间、文件描述符、PID和PCB且创建后可独立执行，所以父子进程是两个独立进程，不是同一个进程的两个线程。

进程控制与原语

1. **原语：**在系统态执行的、具有特定系统功能的、不可分割的原子操作，在执行过程中既不可以被中断也不可以与另一源于并发执行。

2. 进程控制：指的是操作系统对进程从创建、运行、状态转换到终止的整个生命周期进行组织和管理。

   • 创建原语：创建PCB、分配必要资源、将进程加入就绪队列。

   • 撤销原语：终止进程、回收内存、文件、设备等资源、释放PCB。

   • 阻塞原语：保存CPU现场、将状态从运行态设为阻塞态、加入等待队列并重新调度。

   • 唤醒原语：设置状态为就绪态、从等待队列移至就绪队列。

3. 采用原语实现的原因：

   进程控制涉及：修改PCB、进程状态、进程队列、分配和回收资源。这些操作必须完整执行，不能执行一半就被中断，因此通常由原语实现。

什么是线程？

线程是轻量级的进程，是一个进程内资源调度的基本单位。每个线程有自己的程序计数器、寄存器以及堆栈信息。

线程与进程的区别

• 进程是资源分配的基本单位，而线程是资源调度的基本单位；

• 多进程共享物理内存、磁盘、打印机等资源，而多线程共享一个进程的地址空间、打开文件以及全局变量等资源；

• 每个进程有独立的地址空间、PCB、资源集合，而每个线程有独立的线程控制块TCB、程序计数器、寄存器以及堆栈信息；

• 进程创建、撤销和切换的开销大，而线程创建、撤销和切换的开销小。

线程的实现方式

1. 用户级线程：由用户空间中的线程库负责创建、撤销、调度和切换，内核不知道现成的存在。

   • 线程管理在用户态完成；

   • 不需要进入内核，切换速度快；

   • 可以由程序自定义调度策略；

   • 一个线程执行阻塞系统调用，可能导致整个进程阻塞；

   • 不能把多个线程同时安排到多个CPU上实现并行。

2. **内核态线程：**由内核态直接创建、管理、调度线程。每个线程在内核中都有相应的TCB，内核可以分别调度每个线程。

   • 现成的创建、撤销、阻塞、调度由内核完成；

   • 一个线程阻塞时，内核可调度同一进程中的其他线程；

   • 多个线程可以真正在多个CPU上同时执行实现并行执行；

   • 创建和切换开销比用户级线程大，且内核需要维护更多线程数据结构。

3. 混合实现线程：混合实现同时使用用户级线程和内核级线程。

   • 用户线程由线程库管理；

   • 内核只管理一定数量的内核线程；

   • 用户线程可复用多个内核线程；

   • 能兼顾用户级线程切换快和内核级线程可并行的优点；

   • 用户线程与内核线程的映射管理比较困难。

线程的优点

• 实现伪并行，进一步提高并发度；

• 更小的系统开销；

• 更高的性能；

• 有利于在多CPU系统中实现真正的并行。

进程的通信

• 基本概念：不同的进程之间进行信息交换和协同工作的机制。由于进程通常具有相互独立的地址空间，一个进程不能直接访问另一个进程的私有内存，因此必须由操作系统提供通信机制。

• 制约方式：

  • 直接制约： 进程自行使用共享资源或由进程间合作引起的某一进程直接通过某些机构发消息给其他进程，从而引起其他进程的执行。

  • 间接制约： 进程对共享资源的使用通过系统来协调，使得进程间执行速度相互影响。

• 通信方式：

  1. 共享内存：

     • 概念： 操作系统把同一块物理内存映射到多个进程的地址空间中。

     • 特点： 通信速度快、适合传输大量数据、建立共享区后，数据交换不必频繁经过内核复制，必须配合互斥锁、信号量或条件变量，防止并发读写出错。共享内存通常是同一台计算机上效率最高的进程通信方式。

  2. 内存映射文件：

     • 概念： 多个进程把同一个文件映射到自己的地址空间，通过内存读写完成通信。

     • 特点： 文件持久化、共享内存式访问。

  3. 消息传递：

     • 概念： 进程不直接共享地址空间，而是通过操作系统提供的发送、接收操作交换信息。

       send(消息)
       receive(消息)
       

     • 特点： 安全性和隔离性较好、操作系统负责消息传送、通常存在系统调用和数据复制开销，既适合同一主机，也适合网络通信。

  4. 管道：

     • 概念：分为匿名管道具有亲缘关系的进程，例如父子进程和命名管道（FIFO）。管道是内核内存中的一个环形缓冲区。当进程A通过write写入数据时，数据必须先从A的用户态内存复制到内核态管道缓冲区；进程B通过read读取时，数据又要从内核缓冲区复制到B的用户态内存。这经历了两次数据拷贝。

     • 特点： 单向半双工通信、缓冲区大小受内核固定限制、经过内核缓冲区拷贝两次（用户态↔内核态）。

  5. 消息队列：

     • 概念： 由操作系统维护，进程以“消息”为单位发送和接收。

     • 特点：保留消息边界、每条消息可带类型或优先级、比管道更适合传输结构化消息、发送方和接收方不必同时运行。

     管道传输的是连续字节流**，**消息队列传输的是一条条独立消息。

  6. 套接字：

     • 概念： 既可以用于同一台计算机中的进程通信，也可以用于不同计算机之间的网络通信。

     • 特点： 支持客户端—服务器结构、支持TCP、UDP等协议、通信范围最广、可实现双向通信。

  7. 信号：

     • 概念： 信号是一种异步事件通知机制。主要用于通知进程终止、暂停、子进程结束、发生异常。

     • 特点：传递的信息量很少、不适合传送大量数据。

  8. 文件通信：

     • 概念：两个进程可以通过普通文件交换数据。

     • 特点：简单、数据可以长期保存、速度慢、需要处理数据一致性、不适合频繁的实时通信。

临界资源

概念： 一次只允许一个进程使用的资源。

临界区

概念： 每个进程中，访问临界资源的那部分代码。

同步

• 概念： 并发执行的进程或线程之间，为了完成共同任务，必须按照某种先后次序或速度协调执行。同步通常是由进程之间的直接制约关系引起的，多个进程为完成同一个任务而相互合作。

• 同步原则：

  • 空闲让进： 临界区空闲时，允许进程进入。

  • 忙则等待： 已有进程进入临界区时，其他进程不能进入。

  • 有限等待： 等待进入临界区的进程不能无限期等待。

  • 让权等待： 进程不能进入临界区时，应主动阻塞，释放CPU。

• 同步实现：

  1. 信号量与P、V操作：

     semaphore S = 0；
     
     进程P1：
             执行操作A；
             V(S)；
     进程P2：
             P(S)；
             执行操作B；
     

     与互斥信号量的区别：

     • 互斥信号量通常初值为1；

     • 同步信号量通常初值为0；

     • 互斥控制“只能一个进入”；

     • 同步控制“必须先后执行”。

  2. 条件变量： 常见操作由wait()、signal()、broadcast();

     lock(mutex);
     
     while (!condition) {
         wait(cond, mutex);
     }
     
     执行操作;
     
     unlock(mutex);
     

     条件变量通常必须与互斥锁配合使用，因为条件通常依赖共享数据。

  3. 管程：把共享数据、对共享数据的操作、互斥控制、条件变量封装在一起。管程比直接使用P、V操作更结构化，也更不容易写错。

  4. 事件或信号通知： 通过事件机制通知另一个进程某个条件已经发生。

     进程A完成任务
     → 设置事件
     → 唤醒等待事件的进程B
     

  5. 消息传递： 进程可以通过发送和接收消息实现同步。

     进程A完成数据处理
     send(P2, message)
     
     进程B
     receive(P1, message)
     继续执行
     

互斥

• 概念： 不允许两个或以上共享同一临界资源的并发进程同时进入临界区。互斥通常是由进程之间的间接制约关系引起的。

• 互斥原则：

  • 不假设各并发进程的相对执行速度；

  • 处于临界区外的进程不能阻止其他进程进入临界区；

  • 任何时刻只允许一个进程处于临界区中；

  • 不能使进程在临界区外永远等待。

• 互斥实现：

  1. 关中断法： 进程进入临界区前关闭中断，退出后再开启中断。因为CPU不会被时钟中断打断，所以当前进程可以连续执行临界区代码。

  2. 互斥锁法：

     lock(mutex);
     临界区；
     unlock(mutex);
     

     锁空闲时，线程获得锁; 锁被占用时，线程等待。一般由加锁者负责解锁，适合保护临界资源。

  3. 信号量法：P(S)申请进入临界区、V(S)退出临界区并释放资源。s为信号量。

     • P(S)：执行S=S-1，若S<0，则进程进入等待队列并阻塞。其中S表示正在等待使用资源的进程数。

     • V(S)：执行S=S+1；若S>=0，则从等待队列中唤醒一个进程。其中S表示可供并发进程使用的资源实体数。

     P、V都是原语操作。

  4. 管程法：保证任意时刻最多只有一个进程或线程在管程内部执行。通常配合条件变量：wait(); signal() 实现等待和唤醒 。

  5. 其它方法： TSL指令法、轮转法。

同步和互斥的区别

1. 同步：针对协作关系，保证执行顺序。如生产者——消费者的执行顺序。

2. 互斥：针对临界资源，阻塞和让权等待，保证安全执行。如打印机排队。

线程的通信

• 同一进程：线程之间共享地址空间，因此线程之间通常通过全局变量、静态变量、堆对象和共享队列进行通信。为防止多个线程并发访问共享数据产生竞态条件，需要配合互斥锁、读写锁、信号量、条件变量和事件等同步机制。

• 不同进程： 线程不能直接共享普通变量，必须通过进程间通信机制交换数据。

经典的同步问题

1. 生产者——消费者：生产者写入前要求缓冲区至少有一个空单元；消费者读取前要求至少有一个满单元。缓冲区是临界资源。

2. 哲学家就餐：若每人先拿一把叉子再等待另一把，就会产生环路等待。可用服务员、限制同时就餐人数、一次获取两把叉子等方式避免死锁。

3. 读者——写者：多个读者可以同时读，写者必须独占。不同方案需要处理读者优先、写者优先和公平性。

进程的调度

1. 概念：OS按照一定的调度算法，从就绪队列中选择一个进程，把CPU分配给它运行。注意：调度对象是就绪态进程，就绪态——>运行态。

2. 调度层次：

   • 高级调度：作业调度

     • 概念： 从外存的后备作业队列中选择作业，将其调入内存，建立进程。

     • 特点： 决定哪些作业进入内存；控制多道程序的道数；调度频率较低。

   • 中级调度：交换调度

     • 概念： 把暂时不能运行的进程换出内存，或把挂起进程重新换入内存。

     • 特点： 提高内存利用率和系统吞吐量、调整内存中的进程数量、缓解内存压力。

   • 低级调度： 进程调度

     • 概念：从就绪队列中选择一个进程占用CPU。

     • 特点： 调度频率最高、调执行速度必须快、也叫“CPU调度”。

3. 调度时机：与进程状态转换有关

   • 当前进程正常终止；

   • 当前进程因等待I/O或事件进入阻塞态；

   • 当前进程时间片用完；

   • 出现优先级更高的就绪进程；

   • 进程主动让出CPU；

   • 中断或异常处理结束后重新调度。

4. 基本准则：

   • 所有系统：公平、策略的强制执行、均衡。

   • 批处理系统：大的吞吐量短的周转时间、高的CPU利用率。

   • 交互系统：短的响应时间、均衡性。

   • 实时系统：满足实时性要求、具有可预测性。

抢占式与非抢占式调度

1. 非抢占式调度： 一个进程获得CPU后，会一直运行到**正常结束、主动阻塞、主动让出CPU。**实现简单，调度开销小，响应时间可能较长，长进程可能长期占用CPU，不适合交互式和实时系统。

2. 抢占式调度：操作系统可以暂停当前进程，将CPU分配给其他进程。进程的时间片用完、更高优先级进程到达、实时任务到达。响应快、公平性好、适合分时和实时系统，上下文切换开销大，实现更复杂。

进程的调度算法

1. 先来先服务 FCFS：

   • 概念：按到达顺序调度。

   • 特点：非抢占式、实现简单、有利于长作业而不利于短作业。

2. 短作业优先 SJF：

   • 概念：优先选择预计运行时间最短的作业。抢占式版本叫最短剩余时间优先 SRTF，每次选择剩余运行时间最短的进程。

   • 特点：通常是非抢占式、平均等待时间较短、有利于短作业、长作业可能饥饿。

3. 高响应比优先 HRRN：

   • 概念**：响应比 =（等待时间 + 服务时间）/ 服务时间**。优先选择响应比最高的作业。

   • 特点：通常是非抢占式、同时考虑等待时间和作业长度、可以缓解长作业饥饿问题**。**

4. 时间片轮转 RR：

   • 概念：就绪进程按队列顺序轮流使用CPU，每次运行一个时间片。

   • 特点：抢占式、公平性好、适合分时系统、响应速度快、上下文切换过于频繁，系统开销大。

5. 优先级调度：

   • 概念：优先选择优先级最高的进程。

   • 特点：有抢占式和非抢占式、低优先级进程可能长期得不到CPU，发生饥饿，可用老化防止低优先级饥饿。

6. 多级队列调度：

   • 概念：根据进程类型建立多个就绪队列，不同队列可以采用不同算法。

   • 特点：进程通常固定属于某一队列、队列之间也需要设置优先级。

调度算法的评价指标

1. CPU利用率：CPU利用率 = CPU忙碌时间 / 总时间，越高越好。

2. 吞吐量： 单位时间内**完成的作业或进程数量，**越大越好。

3. 周转时间：周转时间=完成时间-提交时间（到达时间），表示作业从提交到完成所经历的总时间。

4. 带权周转时间：带权周转时间 = 周转时间 / 实际运行时间，用来消除长作业和短作业运行时间差异的影响。

5. 等待时间：等待时间 = 周转时间 - 运行时间。

什么是作业？

• 概念：用户提交给计算机系统、要求系统完成的一项完整工作。

• 组成： 程序、数据、作业说明书或控制信息。

• 基本状态：

  • 提交状态：用户正在向系统提交作业。

  • 后备状态：作业已存入外存，等待作业调度。

  • 运行状态：作业已调入内存，建立进程并运行。

  • 完成状态：作业执行完毕，系统回收资源并输出结果。

• 程序、进程、作业的区分：

  • 程序：静态的指令集合。

  • 作业：用户提交的一项完整工作，包括程序、数据和控制信息。

  • 进程：程序在处理机上的一次动态执行过程。

CPU密集型与I/O密集型进程

• CPU密集型进程： CPU计算时间长、I/O操作较少、CPU执行周期较长。例如：科学计算、 视频编码、大规模数值计算。

• I/O密集型进程： 经常进行I/O、CPU运行时间较短、经常主动阻塞。例如：文件处理、网络服务、交互式程序。

第三章 存储管理

基本功能

1. 内存分配与回收： 记录内存的使用情况，按照进程需要分配内存，并在进程结束后回收。

2. 地址映射： 把程序的逻辑地址或虚拟地址变换为物理内存地址。

3. 内存保护： 防止进程越界访问，保护操作系统和其他进程的存储空间。

4. 内存共享： 允许多个进程在受控条件下共享程序和数据。

5. 内存扩充： 借助覆盖、交换技术和虚拟存储，从逻辑上扩大可用内存。

三级存储体系

1. Cache高速缓存：速度最快、容量最小、成本最高，易失性。Cache位于CPU和内存之间，用于缓解CPU与内存速度不匹配的问题；

2. 内存：速度容量成本适中，同样易失内存；

3. 外存：低速、成本低、非易失性的磁盘存储。

地址空间

• 逻辑地址/虚拟地址空间：程序运行时使用的地址。

• 物理地址：内存单元的实际地址。

地址转换

• 地址映射：把虚拟地址转为物理地址的过程。

• 重定位： 将虚拟地址变换为内存地址的过程，称为地址映射，也称为地址重定位。

  • 静态重定位：程序装入内存时，一次性完成地址转换。装入后不能随意移动，开销小，灵活性差。

  • 动态重定位：在程序执行过程中，每当访问一条指令或数据时，由硬件MMU配合基址寄存器（或页表）实时完成地址转换。这是现代操作系统（如Linux、Windows）采用的主流方式，是实现虚拟内存、支持程序在内存中移动和部分装入的基础。

• 基址寄存器：

  • 作用： 保存当前正在运行的进程在物理内存中的起始地址。

  • 功能： CPU在执行进程的指令时，会将程序产生的逻辑地址与基址寄存器中的值相加，从而得到真正的物理地址。

• 界限寄存器：

  • 作用： 保存当前进程的地址空间大小。

  • 功能： 它负责越界检查。在地址转换前，CPU会将程序产生的逻辑地址与界限寄存器的值进行比较。

基址寄存器和界限寄存器实现简单、高效，支持动态重定位，同时提供了硬件级的内存保护。

进程必须连续地装入到物理内存中，且进程大小受限于界限寄存器的值，不支持程序的局部装入，即不适用于现代虚拟内存的分页机制，分页机制会使用更复杂的MMU和页表，而不仅仅是这一对寄存器。

物理内存管理方式

连续分配存储管理方式：

1. 单一连续分配： 一次只装入一个用户程序，结构简单，利用率低。

2. 固定分区： 系统启动时将内存划分为若干固定分区，会产生内部碎片。

3. 可变分区： 按实际进程需要动态划分连续分区，减少内部碎片，但会产生外部碎片。

非连续分配存储管理方式：

1. 分页： 进程划分页，主存划分页框，页可离散装入页框，消除外部碎片，但存在内部碎片。

2. 分段： 按程序逻辑结构划分可变长段，便于共享和保护，但存在外部碎片，一般没有内部碎片。

3. 段页式： 先按逻辑结构分段，再对每个段内部按固定页框进行分页，消除外部碎片，地址结构为**段号 + 页号 + 页内偏移。**它兼具分段和分页的优点，但需要同时查段表和页表，硬件开销和查表时间都更大。

页面分配策略

分配策略和置换策略

• 固定分配： 每个进程分配固定数量页框；

• 可变分配： 进程运行时可动态增加或减少页框；

• 局部置换： 只能淘汰本进程的页面；

• 全局置换： 可以淘汰系统中的其他进程的页面。

组合包括：

• 固定分配、局部置换；

• 可变分配、局部置换；

• 可变分配、全局置换。

注意：没有 “固定分配+全局置换” ，因为逻辑冲突，固定分配代表页框数量不变，而全局置换允许系统从任意进程抢走页框，发生了数量变化。

内存扩充技术

在逻辑上扩充内存的技术：

• 覆盖技术：程序员手动将程序划分为不同功能的模块，把不会同时执行的程序模块安排在同一内存区域，需要时由外存调入。

• 交换技术：将暂时不能运行的整个程序换出到磁盘，需要运行时再换入主存。能释放内存，换入换出I/O开销大，需要动态重定位。

空闲存储管理

记录哪些内存块或磁盘块已经被占用，哪些块仍然空闲。

• 位图： 先把内存划分为大小相同的分配单位，例如页框和固定大小的块，然后用一个二进制位表示块的状态。

  例如：0表示空闲，1表示已分配。

  内存块：0 1 2 3 4 5 6 7
  位图：  1 1 0 0 1 0 0 1
  

  特点： 结构简单、容易判断某个块是否空闲、适合管理固定大小的页框、磁盘块；查找空闲块时可能需要扫描位图、分配单位越小，位图本身越大、查找很长的连续空闲区域可能较慢。

  用途： 常用于分页存储中的空闲页框管理、磁盘空闲块管理、固定大小内存块管理。

• 空闲链表： 把空闲内存区域组织成链表，每个节点记录一段空闲区域的信息 如起始地址、区域长度、指向下一个空闲区的指针。申请内存时，系统从链表中选择一个足够大的空闲区；释放内存时，把释放区域重新加入链表，并与相邻空闲区合并。

  [起址100，长度40]
          ↓
  [起址300，长度80]
          ↓
  [起址600，长度20]
  

  表示系统中有三块空闲区域。

动态分区分配算法

在空闲区上查找可用的内存块。

1. 首次适应算法 First Fit：

   • 概念：从低地址开始查找，选择第一个满足要求的空闲区。

   • 特点：查找速度快、高地址通常保留较大空闲块。

2. 下次适应算法 Next Fit：

   • 概念：从上次查找结束的位置继续查找。

   • 特点：空闲区分布均匀，高地址空闲区容易被破坏。

3. 最佳适应算法 Best Fit：

   • 概念：选择满足要求的最小空闲区。

   • 特点：单次分配剩余空间最小、容易产生大量很小的外部碎片、不一定使整体利用率最高。

4. 最坏适应算法 Worst Fit：

   • 概念：选择最大的空闲区。

   • 特点：分配后仍可能保留较大空闲区、大空闲区消耗较快、通常内存利用率较低。

回收空闲区数量

回收区域：

• 无相邻空闲区：空闲区数量加1；

• 只有一个相邻空闲区：数量不变；

• 上下都有空闲区：三个区域合并，空闲区数量减1。

碎片

• 内部碎片：已分配区域内部未被使用的空间。常见于固定分区、分页存储。

• 外部碎片：总量足够的空闲空间被分散成多个不连续的小块。常见于动态分区、分段存储。

抖动

• 概念：进程频繁发生缺页，大部分时间都用于页面换入换出，而不是执行指令。

• 原因：

  • 分配给进程的页框过少；

  • 多道程序的道数过高；

  • 工作集不能完整装入内存。

• 解决方法：

  • 减少多道程序的道数；

  • 为进程增加页框；

  • 使用工作集模型；

  • 使用缺页率控制法。

虚拟存储

• 概念： 利用程序的局部性原理，使得程序不必全部装入内存即可运行，并为进程提供大于实际物理内存的逻辑地址空间。

• 局部性原理：

  • 时间局部性：最近访问的内容可能很快再次访问；

  • 空间局部性：访问某个位置后，附近位置可能很快被访问。

• 实现条件：

  • 分页或分段机制；

  • 请求调入功能；

  • 页面置换功能；

  • 外存交换区；

  • 地址转换硬件。

分页存储管理

• 概念： 把进程的虚拟地址空间划分为固定大小的页，把物理内存划分为同样大小的页框。将空闲页框分配给逻辑页，并借助页表完成地址映射。

• 页面： 逻辑地址空间划分出固定大小块。

• 页框/物理块：物理内存划分出固定大小块。页面大小等于页框大小。

• 逻辑地址结构：

  逻辑地址=页号 + 页内偏移量

  如若页大小为2^n 字节，页内偏移占n位，页号占 逻辑地址总位数-n位。最大页数=2^(m-n)。 其中m为逻辑总位数，n为页内偏移位数。

• 地址转换： 先从逻辑地址中分离页号和页内偏移，查页表得到页框号，物理地址为页框号与页内偏移组合。

  物理地址=页框号 x 页面大小+页内偏移。

• 页表： 页表记录着逻辑页号和物理页框之间的对应关系。**每个进程都有独立页表，**一般包含：页框号、存在页、访问位R、修改位M、保护位。多级页用于解决单极页表过大的问题。

• 快表TLB： 保存近期使用的页表TLB是页表项的高速缓存，可以加快虚拟地址到物理地址的转换。

• 请求分页： 只在访问某页时才将该页调入内存。

• 缺页中断： 访问的页面不在内存时，产生缺页中断。处理步骤：

  1. 检查访问是否合法；

  2. 查找空闲页框；

  3. 若无空闲页框，则选择淘汰页；

  4. 若淘汰页被修改，写回磁盘；

  5. 从磁盘调入所需页面；

  6. 修改页表；

  7. 重新执行被中断的指令。

  过程涉及到：修改页表、磁盘I/O、分配页框。

页面置换算法

1. OPT最优算法：

   • 概念：淘汰未来最长时间不会被访问的页面。

   • 特点：缺页率最低、实际无法实现、常用于比较其他算法。

2. FIFO先进先出：

   • 概念：淘汰最早进入内存的页面。

   • 特点：实现简单、可能出现Belady异常，即页框增加反而缺页率上升。

3. 第二次机会/CLOCK时钟算法：

   • 概念：使用访问位判断页面是否近期被访问。

   • 特点：访问位为0：淘汰；访问位为1：置0并继续扫描。

4. 改进CLOCK：

   • 概念：进行两轮扫描，同时考虑访问位A，修改位M。

   • 特点：优先淘汰顺序：(0,0)→(0,1)→(1,0)→(1,1)。

   最佳淘汰页是：A=0，M=0。

5. LRU最近最少使用：

   • 概念：淘汰最近最长时间未被访问的页面。

   • 特点：性能较好、实现开销较大、属于栈式算法；

6. NRU最近未使用：

   • 概念：根据访问位R和修改位M将页面分为四类：

   • 特点：

     1. R=0，M=0；

     2. R=0，M=1；

     3. R=1，M=0；

     4. R=1，M=1。

     优先淘汰编号较小的类别。

缺页率与有效访问时间

缺页率：

缺页率=缺页次数/页面访问总次数

有效访问时间通常形式：

EAT=(1−p)×内存访问时间+p×缺页处理时间

其中 p为缺页率。

由于缺页处理涉及磁盘I/O，即使缺页率很低，也可能显著降低性能

分段式存储

• 概念：把虚拟地址空间按程序的逻辑关系划分为若干可变长段，每段从0开始。例如代码段、数据段、栈段、子程序段。

• 逻辑地址： 逻辑地址=段号 + 段内偏移。

• 段表： 段表项通常包括段基址、段长、保护信息。

• 物理地址：

  物理地址=段基址+段内偏移

  但必须检查：段内偏移<段长

• 分段特点： 段长可变、符合程序逻辑结构、便于共享和保护、会产生外部碎片。

分页与分段的区别

• 划分依据： 分页按物理管理需要；分段按程序逻辑结构。

• 大小： 分页的页面大小固定；分段的段长可变。

• 地址结构： 页号+页内偏移；段号+段内偏移。

• 碎片： 内部碎片；外部碎片。

• 共享和保护： 以页为单位，不一定对于逻辑模块；以逻辑段为单位，便于共享和保护。

• 用户可见性： 通常不可见；对程序员可见。

• 目的： 提高内存利用率；体现程序逻辑结构。

段页式存储管理

• 概念： 程序先按逻辑分段，再把每段划分为固定大小的页。逻辑地址由段号、段内页号、页内偏移组成，每个进程有自己的段表，每个段由页表。

• 逻辑地址： 段号+段内页号+页内偏移；

• 物理地址： 根据段号查段表，再用页号查页表得到页框号，最后形成物理地址。

• 特点： 保留了分段的逻辑性、避免了分段的外部碎片、地址转换过程复杂。

内存保护与共享

• 概念：防止进程访问不属于自己的内存。

• 常见方法：

  • 基址寄存器和界限寄存器；

  • 页表保护位；

  • 段表访问权限；

  • 用户态和内核态权限控制。

• 页面共享：多个进程的页表项可以指向同一物理页框。

• 共享内容：公告代码段、动态链接库、共享内存。

第四章 文件管理

什么是文件？

• 概念：文件是由文件名标识的一组相关信息的集合，是操作系统进行信息存储和管理的基本单位。

• 特点：

  • 长期保存在外存中；

  • 具有文件名；

  • 可被创建、读取、修改和删除；

  • 通过文件系统统一管理。

文件组成

从用户角度看，包括：

• 文件名；

• 文件内容；

• 文件结构；

• 文件操作；

• 文件存取；

• 文件属性。

其中文件属性包括：

• 文件类型；

• 文件长度；

• 文件所有者；

• 创建、修改时间；

• 存取权限；

• 文件所在位置；

• 文件状态。

文件系统

• 概念：负责文件存储、组织、访问、保护和管理的软件以及相关数据结构的集合。

• 功能：

  • 按名存取；

  • 管理文件目录；

  • 管理磁盘存储空间；

  • 实现文件的读写和定位；

  • 提供共享和保护机制；

  • 保证文件系统可靠性；

  • 提高文件访问性能。

文件结构

按逻辑结构划分：

• 流式文件（字节序列）：文件是一个无结构的连续字节流。例如：.txt文件文本，.exe可执行文件。

• 记录式文件（记录序列）：文件由若干个逻辑记录组成，每个记录包含若干字段。常见于数据库文件或早期的批处理系统。

  用于组织和检索记录的四种具体组织方式的有结构文件：

  • 顺序文件：

    • 定义：文件中的记录按某个关键字的顺序依次排列，并且物理存储顺序与逻辑顺序一致。

    • 特点：支持顺序存取，只能用二分法进行随机查找。适合磁带打印，修改效率极低。

  • 索引文件：

    • 定义：文件由数据区和索引表两部分组成，索引表包含地址映射关系。

    • 特点：支持高速随机存取，查找时先查索引表，再根据地址直接定位记录。查询效率高，但索引表体积大且每次增删维护索引的开销大。

  • 索引顺序文件：

    • 定义：是顺序文件和索引文件的结合体。

    • 特点：既支持顺序存取，也支持快速随机存取。查找速度比纯顺序文件快得多，又比纯索引文件节省索引空间，缺点是维护难。

  • 散列文件：

    • 定义：利用哈希函数，将记录的关键字直接计算出一个数值，该数值映射为记录的物理磁盘块号。

    • 特点：查找速度最快，非常适合等值查询，但不支持范围查询且存在哈希冲突问题。

• 树形结构文件：文件内部数据按树形层次组织，如XML、JSON，允许在文件内部进行更复杂的嵌套检索。

按物理结构划分：文件的数据块在磁盘上的实际组织和分配方式。

• 连续结构：

  • 定义：文件占用一组连续的磁盘块。记录起始块号、文件长度或块数。

  • 特点：顺序访问速度快、随机访问方便、地址结算简单。逻辑块号为时，物理块号=起始块号+i。文件扩展困难、容易产生外部碎片。

  文件需要频繁修改或扩展时，最不适合使用连续分配。

• 链表结构：

  • 定义：文件的各磁盘块可以分散存放，每个磁盘块保存下一个块的地址。

  • 特点：文件扩展方便、不产生外部碎片、随机访问效率低、指针占用磁盘空间、磁盘块分散，寻道次数可能增加。

• FAT方式：

  • 定义：文件分配表FAT把指针集中保存在一张表中。

  • 特点：FAT通常可以缓存在内存中、仍属于链接分配。

• 索引结构：

  • 定义：为每个文件建立一个索引块，存放所有指向数据块的指针。

  • 特点：支持随机访问、文件扩展方便、不需要连续磁盘空间、不存在外部碎片。索引块需要额外空间。

  适合随机访问并且容易扩展的物理结构是索引结构。

多级索引

文件较大时，一个索引块装不下所有数据块指针，于是用“索引的索引”来层层嵌套（类似多级页表），采用UNIX i节点方式设计：

• 直接地址：i节点中的指针直接指向数据块。

• 一级间接地址：指针指向一个间接索引块，索引块中再保存数据块地址。

• 二级间接地址：指针指向一级索引块，该块中的指针又指向二级索引块。

• 三级间接地址：再增加一级索引。

计算方法：当直接地址=d，磁盘块大小=B，每个块的指针大小=P时。

根据x级间接地址：最大文件容量= [d+B/N+(B/N)^2+ (B/N)^3+ ……+(B/N)^x]B

文件控制块FCB

• 概念：OS为管理文件而建立的数据结构，保存文件的属性、位置和控制信息。

• 包含：文件名、文件类型、文件大小、文件存储位置、所有者、访问权限、创建和修改时间、当前状态、物理块信息。

FCB是文件存在的标志。

文件访问

• 顺序访问： 按文件内容的先后顺序执行依次读写。适合连续处理，不适合随机定位。

• 随机访问： 程序根据位置或记录号直接访问文件中的任意部分。查找速度快，支持关键字访问，需要额外保存索引。

目录

• 作用： 用于保存文件名及其管理信息，实现按名查找文件。

• 功能：

  • 按文件名查找文件；

  • 创建和删除文件；

  • 显示文件列表；

  • 重命名文件；

  • 管理文件层次；

  • 实现文件共享；

  • 实现访问控制。

• 目录结构：

  • 单极目录：

    • 概念：所有文件放在一个目录中。

    • 特点：结构简单、不允许文件重名、文件多时查找困难、不适合多用户系统。

  • 两级目录：

    • 概念：每个用户有自己的用户文件目录。

    • 特点：不同用户可以使用相同文件名、用户文件相互隔离。

  • 树形目录：

    • 概念：目录可以包含子目录和文件。

    • 特点：层次清晰、支持分类管理、允许不同目录出现同名文件、是现代操作系统常用结构。

  • 无环图目录：

    • 概念：允许文件或目录被多个目录共享，但不允许形成环。

  • 通用图目录：

    • 概念：允许目录共享并形成环。

    • 特点：遍历复杂，删除和垃圾回收困难、可能出现无限循环。

• 目录实现方式：

  • 线性表：

    • 定义：目录项依次存放。

    • 特点：实现简单，查找时需要顺序扫描，文件较多时速度慢。

  • 哈希表：

    • 定义：对文件名计算哈希值，定位目录项。

    • 特点：查找速度快，存在哈希冲突、需要额外的哈希结构。

  • B树或B+树：

    • 定义：大型文件系统常使用树形索引管理目录项。

    • 特点：适合大量目录项，查找、插入、删除效率较高。

路径名

• 绝对路径：

  • 定义：从根目录开始的完整路径。例如：/home/user/report.txt

  • 特点：与当前目录无关、路径唯一明确。

• 相对路径：

  • 定义：从当前工作目录开始的路径。例如：docs/report.txt

• 当前目录与父目录：

  • .：当前目录；

  • ..：父目录。

文件操作

• 创建文件；

• 删除文件；

• 打开文件；

• 关闭文件；

• 读文件；

• 写文件；

• 定位文件指针；

• 截断文件；

• 重命名文件；

• 获取或修改属性。

创建文件

主要步骤：

1. 在目录中建立目录项；

2. 建立FCB或i节点；

3. 初始化文件属性；

4. 必须时分配磁盘空间。

删除文件

主要步骤：

1. 删除目录项；

2. 释放文件占用的磁盘块；

3. 释放FCB或i节点；

4. 若是共享文件，更新链接计数；

5. 处理相关共享关系。

不需要把原磁盘数据全部清零。

读文件

流程：

1. 用户程序调用read；

2. 根据文件描述符找到打开文件表；

3. 根据当前偏移量确定逻辑块；

4. 通过文件物理结构找到磁盘块；

5. 检查数据是否已在缓存中；

6. 若不在，发出磁盘I/O；

7. 将数据复制到用户缓冲区；

8. 更新文件偏移量。

打开文件是使用文件的必要前提。

写文件

流程：

1. 用户程序调用write；

2. 检查写权限；

3. 根据文件偏移确定目标块；

4. 必要时分配新磁盘块；

5. 修改缓存中的数据；

6. 标记为脏块；

7. 后续写回磁盘；

8. 更新文件大小、时间和偏移量。

文件共享

主要方式：

• 硬链接：

  • 定义：多个目录项指向同一个i节点。

  • 特点：多个文件名共享同一i节点、i节点中有链接计数、删除一个文件名，只使链接计数减1、链接计数为0时，文件才真正被删除、一般不能跨文件系统、通常不能对目录创建普通硬链接。

• 符号链接：

  • 定义：也叫软链接，符号链接是一个特殊文件，其内容保存另一个文件的路径名。

  • 特点：可以跨文件系统、可以链接目录、原文件删除后符号链接可能失效，符号链接有独立的i节点。

文件保护

• 概念： 用于防止非法访问和破坏。

• 常见方法： 访问控制矩阵、访问控制表ACL、用户权限表、UNIX权限位。

磁盘空闲空间管理

• 概念： 文件系统需要记录哪些是磁盘空闲块、哪些已被占用。

• 常见方法：

  • 位示图： 每个磁盘块对应一个二进制位。0空闲，1占用。

  • 空闲链表： 把所有空闲磁盘块连接成链表。

  • 成组链接法： 将空闲块分组，每组保存下一组空闲块号。UNIX常采用成组链接法。

位图计算

若磁盘共有N块，则位图需要N位，换算成字节：N/8。

若位图中的位号为i，每个字包含w位，则：

字号=$\lfloor \frac{i}{w}\rfloor$，字内位号=$i\mathrm{mod}w$

文件备份

• 完全备份；

• 增量备份；

• 差异备份。

文件系统性能优化

• 块高速缓存： 把常用磁盘块保存在内存中，减少磁盘访问。

• 预读： 读取一个块时，提前读取后续可能访问的块，适合顺序访问。

• 延迟写： 先修改内存缓存，稍后批量写回磁盘。

• 合理分配磁盘块： 尽量让同一文件的数据块连续、靠近i节点或目录。

• 磁盘调度： 通过FCFS、SSTF（短作业优先）、SCAN（电梯调度）等算法重新安排磁盘请求顺序。

查找磁盘次数计算

例如：

• 一个FCB大小64B；

• 一个磁盘块大小1KB；

• 目录中有3200个FCB。

每块可存FCB数：

$$\frac{1024}{64}=16$$
目录共占磁盘块数：

$$\frac{3200}{16}=200$$
若采用顺序查找，平均查找一半：

$$\frac{200}{2}=100$$
因此平均启动磁盘次数为：100次。

第五章 设备管理

什么是设备管理？

• 概念：研究如何统一管理各种I/O设备，完成设备分配、数据传输、驱动控制、缓冲、错误处理以及磁盘调度。

• 核心目标：

  • 提高CPU与I/O设备的并行性；

  • 提高设备的利用率；

  • 为用户提供统一方便的设备访问接口；

  • 实现设备独立性；

  • 保证I/O操作安全、可靠。

I/O设备分类

• 按信息交换单位分类：

  1. 字符设备：

     • 定义：以字符或字节为单位传输数据，例如：打印机、鼠标、键盘等。

     • 特点：不能随机定位、多采用顺序访问。

  2. 块设备：

     • 定义：以固定大小的数据为单位传输。例如：固态硬盘、磁盘、U盘。

     • 特点：支持随机访问、每个数据块都有地址，通常可以缓存。

  3. 网络设备：

     • 定义：按数据包收发，如网卡、网桥和路由器接口。

     • 特点：用于和远程设备进行通信。

• 按使用方式分类：

  1. 独占设备：同一时间只能由一个进程使用。例如：扫描仪、打印机。

  2. 共享设备：多个进程可以交替访问。例如：磁盘、网络设备。

  3. 虚拟设备：利用软件技术把一台物理独占设备模拟成多台逻辑设备。典型技术如SPOOLing（假脱机技术）。

• 按传输速度分类：

  • 低速设备：键盘、鼠标；

  • 中速设备：打印机；

  • 高速设备：磁盘、网卡。

I/O基本组成

CPU
  ↓
总线
  ↓
设备控制器
  ↓
I/O设备

1. 设备控制器： 位于CPU和设备之间，负责控制具体设备。

   主要功能：

   1. 接收CPU命令；

   2. 控制设备执行；

   3. 完成数据缓冲；

   4. 检测设备状态；

   5. 产生中断；

   6. 完成数据格式转换。

2. 设备寄存器：包含数据、状态、控制器寄存器。CPU通过读写这些寄存器控制设备。

I/O软件的层次结构

从上到下：

• 用户级I/O软件： 位于用户空间，通过系统调入进入内核。

  主要包括：

  • 标准I/O库；

  • 格式化输入输出；

  • 缓冲库；

  • SPOOLing程序；

  • 用户级设备管理程序。

• 设备无关I/O软件： 不依赖具体设备型号。

  主要功能：

  • 提供统一的设备访问接口；

  • 逻辑设备名到物理设备的映射；

  • 设备保护与权限检查；

  • 缓冲管理；

  • 错误报告；

  • 设备分配与释放；

  • 设置与设备无关的数据块大小；

  • 检查数据是否在高速缓存中。

  高频判断：

  • 检查用户是否有权使用设备：设备无关层；

  • 检查请求块是否在缓存：设备无关层；

  • 逻辑设备到物理设备的映射：设备无关层。

• 设备驱动程序： 直接控制具体设备控制器的软件。

  主要功能：

  • 把上层抽象I/O请求转换为具体设备命令；

  • 计算设备地址；

  • 设置控制器寄存器；

  • 启动设备；

  • 检查设备状态；

  • 处理设备错误。

  向设备寄存器写命令，以及计算磁道、磁头、扇区，通常由设备驱动程序完成。

• 中断处理程序： 设备完成I/O后，产生中断。唤醒等待设备完成的驱动程序或进程，通常由中断处理程序完成。

• 硬件设备

• I/O请求处理流程：用户程序 → 系统调用处理程序 → 设备驱动程序 → 中断处理程序 → 硬件设备。

I/O编址方式

• 独立编址： I/O端口与内存使用两个地址空间，采用专用I/O指令。不占内存地址空间，保护清楚，驱动程序需要专门指令。

• 内存映射I/O： 设备控制器占用内存地址，普通装入/存储指令访问。禁止缓存设备寄存器，并处理多总线路由。

• 混合方式： 部分寄存器内存映射，部分使用I/O端口，兼顾兼容性和实现需求。

CPU与设备之间的数据传输方式

• 程序控制I/O： 轮询方式或忙等待方式，CPU不断查询设备状态，设备就绪后逐字传送，CPU浪费大量时间在等待设备上，CPU利用率低。

• 中断驱动方式： CPU发出I/O命令后继续执行其他程序，设备完成后产生中断。提高CPU与设备的并行性，但频繁中断仍有开销。

• DMA方式： 直接存储器访问，可以在设备与内存之间直接传送一批数据，不需要CPU逐字传输。适合高速块设备、一次可传输一个数据块。需要DMA硬件。

• 通道方式： 专用I/O处理机执行通道程序，独立控制多个设备和多次传输。进一步减轻CPU负担。

轮询最简单，中断免忙等，DMA传整块，通道管一批。

设备独立性

• 概念： 用户程序不需要了解具体物理设备的特性，只使用逻辑设备名访问设备。逻辑设备名 → 物理设备

• 作用：

  • 用户程序与具体设备无关；

  • 更换设备时不必修改应用程序；

  • 便于设备分配；

  • 便于系统统一管理设备；

  • 提高程序可移植性。

程序员通过系统调用访问设备时，通常使用逻辑设备名或设备类相对号，而不是物理设备名。

缓冲技术

• 概念： 在CPU、内存、设备之间设置临时存储区域，用来暂存输入输出数据。

• 原因：

  • 缓解CPU和I/O速度不匹配；

  • 减少CPU等待时间；

  • 提高CPU与设备并行性；

  • 减少中断次数；

  • 协调数据传输单位不一致。

采用缓冲技术的主要目的是提高CPU与I/O设备之间的并行程度。

• 缓冲方式：

  • 单缓冲：只设置一个缓冲区，设备和CPU仍可能互相等待。

  • 双缓冲：设置两个缓冲区。CPU和设备可以更充分并行。

  • 循环缓冲：设置多个缓冲区并构成循环队列。适合连续数据流。

  • 缓冲池：设置多个公共缓冲区，供多个进程和设备共享。

• 与缓存的区别：

  • 缓冲Buffer：主要解决CPU与I/O速度不匹配、数据传输单位不一致、并行问题。

  • 缓存Cache：主要保存常用数据的副本，一剑豪啊再次访问慢速设备。例如磁盘高速缓存。

SPOOLing技术

• 概念： 全称外部设备联机并行操作，又叫假脱机技术。利用磁盘作为大容量中间存储区，将独占设备改造成逻辑上的具有共享特征的虚拟设备。如打印机管理。

• 组成： 输入井、输出井、输入进程、输出进程、输入缓冲区、输出缓冲区。

• 作用：

  • 将独占设备逻辑上改造成共享设备；

  • 提高独占设备利用率；

  • 提高CPU与设备并行性；

  • 用户进程不必等待慢速设备；

  • 支持虚拟设备。

物理打印机仍然是独占设备，但通过磁盘输出井，使多个进程感觉自己都拥有一台逻辑打印机。

设备分配

• 概念： 是指OS根据进程请求，为其分配设备及相关控制结构。

  需考虑：

  • 设备是否空闲；

  • 设备是独占还是共享；

  • 进程优先级；

  • 是否可能发生死锁；

  • 所需控制器和通道是否可用。

• 数据结构：

  • 设备控制表DCT；

  • 控制器控制表COCT；

  • 通道控制表CHCT；

  • 系统设备表SDT。

• 分配方式：

  • 静态分配：进程运行之前一次性申请全部设备，不容易发生死锁，但是设备利用率低，进程可能长期占有用不到的设备。

  • 动态分配：进程徐云过程中按需申请设备。设备利用率高，容易发生死锁。

磁盘结构：

• 组成： 盘面、磁道、扇区、柱面。

• 磁盘访问时间：磁盘访问时间=寻道时间+旋转延迟时间+数据传输时间。

  • 寻道时间：磁头移动到目标道所需的时间。

  • 旋转延迟：等待目标扇区旋转到磁头下方的时间。

  • 传输时间：实际读写数据需要的时间。

磁盘调度算法

目标：减少磁头移动距离，从而降低平均寻道时间。

• 先来先服务FCFS： 按请求到达顺序处理。磁头可能来回大幅移动，平均寻道距离较大。

• 最短寻道时间优先SSTF： 优先处理离当前磁头位置最近的请求。平均寻道距离较小，性能通常优于FCFS。远处请求可能长期得不到服务，可能发生饥饿。

• 扫描算法SCAN： 梯算法，磁头沿一个方向移动，依次处理该方向上的请求，到达一端后改变方向。服务较均匀、 不易发生饥饿、 不频繁改变磁头方向。

• LOOK算法： 与SCAN类似，但磁头不必走到磁盘物理端点。磁头只移动到该方向上最远的请求位置，然后反向。

  区别：

  • SCAN走到磁盘端点再返回；

  • LOOK走到最远请求处就返回。

磁盘I/O性能优化

常见方法：

• 使用磁盘调度算法；

• 设置磁盘高速缓存；

• 预读；

• 延迟写；

• 合并相邻I/O请求；

• 优化文件块布局；

• 将相关文件放在相近磁道；

• 减少磁盘碎片；

• 使用RAID；

• 使用SSD降低机械寻道开销。

不能明显改善单块物理磁盘I/O性能的做法通常是： 仅仅把同一磁盘划分为多个逻辑分区。

RAID基础

概念：RAID通过多个磁盘组合，提高性能和可靠性。

1. RAID 0

   • 数据条带化；

   • 无冗余；

   • 性能高；

   • 任一磁盘损坏都可能导致数据丢失。

2. RAID 1

   • 镜像；

   • 可靠性高；

   • 存储利用率约为50%。

3. RAID 5

   • 条带化；

   • 分布式奇偶校验；

   • 可容忍一块磁盘故障。

错误处理：

I/O操作可能出现：

• 设备未就绪；

• 校验错误；

• 超时；

• 坏扇区；

• 设备离线；

• 控制器故障。

处理方法：

• 重试；

• 报告错误；

• 使用备用块；

• 重新校准设备；

• 终止I/O操作；

• 唤醒并通知请求进程。

第六章 死锁

什么是死锁？

本质是多个进程因竞争资源而形成的 循环等待且无法推进的阻塞状态。

指的是一组进程中，每个进程都在等到其他进程释放资源，但自身又不释放已占用的资源，从而导致所有进程无法继续执行。

特征：

• 进程处于永久阻塞状态

• 资源无法被释放或重新分配

• 系统整体吞吐下降甚至停滞

死锁产生的必要条件

四个条件必须同时满足时才会形成死锁：

• 互斥条件：资源一次只能被一个进程使用

• 请求和保持条件：进程已占有部分资源，同时等待其他资源。

• **不可剥夺条件：**已分配资源不能被强制回收。

• **循环等待；**进程形成资源等待环。

资源

• 分类：

  • 可抢占资源：拥有他的进程中抢占而不会产生任何副作用。

  • 不可抢占资源：拥有它的进程中抢占会引起计算失败，例如打印机、记录锁。

• 资源分配图：有向图：表示进程与资源关系

  • P → R：请求资源

  • R → P：资源分配

  若图中存在环： 单实例资源 → 一定死锁 ；多实例资源 → 可能死锁

死锁处理策略

1. 死锁预防：

破坏四个必要条件之一：

• 破坏互斥（不可行）

• 破坏占有且等待（一次申请全部资源）

• 破坏不可剥夺（资源可抢占）

• 破坏循环等待（资源编号排序法）

特点：保守，但资源利用率低。

2. 死锁避免：动态判断是否进入“不安全状态”。经典算法：银行家算法。核心概念： 安全状态 / 不安全状态 ；安全序列。

3. 死锁检测：允许死锁发生，但定期检测： 资源分配图检测环

或矩阵检测算法。

4. 死锁解除：检测到死锁后处理：

• 进程终止：

  • 终止所有死锁进程

  • 或逐个终止直到解除

• 资源剥夺：

  • 抢占资源并回收

  • 可能导致回滚

死锁 = 四条件同时成立 + 资源循环等待无法打破
处理方式 = 预防 / 避免 / 检测 / 解除四种策略体系

高频考点：

系统调用/进程切换

【例题】

判断哪些操作会导致从用户态 到内核态的切换：（BC）

A. sin函数调用

B. read系统调用

C. 整数除0

D. 函数调用

【考点】

考查：用户态进入内核态的三种方式

① 系统调用

② 异常（Exception）

③ 外部中断（Interrupt）

【解析】

sin函数调用浮点数计算CPU直接处理不需要操作系统介入、普通函数调用在都是用户空间完成，不会主动触发内核中断。

read涉及访问磁盘等硬件，用户程序无权直接操作硬件。整数除0会触发一个陷阱，CPU强制跳转到内核中的预设异常处理程序，以被动形式（硬件出发）进入内核态。

系统调用执行过程

【例题】

系统调用执行过程正确的是（B）

A 用户程序→内核→系统调用

B 用户程序→系统调用→Trap→内核程序→返回用户程序

C 用户程序→函数调用→结束

D 用户程序→中断处理程序

【考点】

考查：系统调用执行过程

【解析】

完整流程：用户程序→调用C库函数（read/open等）→执行Trap（软中断）→CPU切换到内核态→执行系统调用服务程序→返回结果→恢复到用户态继续执行。

其中open、read、write、fork、exec、wait、pipe、socket都是系统调用。

PCB进程控制块

【例题】

下面关于PCB说法错误的是（C）

A PCB是进程存在的唯一标志

B 创建进程时建立PCB

C PCB内容始终保持不变

D Linux中PCB对应task_struct

【考点】

考查：PCB的作用、内容、生命周期

【解析】

PCB记录PID、进程状态、CPU现场、打开文件、内存信息、优先级，随着运行不断变化。PCB才是操作系统管理的核心对象。

进程状态转换

【例题】

下面关于进程状态说法错误的是（A）

A 阻塞进程得到CPU即可运行

B 就绪进程等待CPU

C 单CPU运行态最多一个

D 阻塞等待事件

【考点】

考查：三种状态的转换条件

【解析】

运行中时间片到、被高优先级抢占、主动让出CPU到就绪态；运行中请求I/O、等待事件到阻塞态；阻塞I/O请求完成、等待事件完成到就绪态；就绪态获得CPU到运行态。

线程的使用

【例题】

下列适合采用线程的是（B）

A 初始化程序

B 多窗口程序

C 顺序计算

D 单任务程序

【考点】

考查：线程引入的目的——提高并发响应速度和资源利用率

【解析】

B中的多窗口程序需要同时处理多个独立的用户交互，为每个窗口分配一个线程，从而使整体界面不会因为等待数据而阻塞卡死。ACD是顺序执行的单个任务，创建线程反而会引入多余的切换开销。一般提到多个任务时就需要线程，顺序、单个、初始化不适合用线程。

临界资源与临界区

【例题】

下面关于临界区说法错误的是（C）

A 一个进程可有多个临界区

B 临界区中访问临界资源

C 两个进程可同时进入同一临界区

D 临界资源可为共享变量

【考点】

考查：临界资源、临界区、互斥

【解析】

临界资源：一次只能一个进程访问。

临界区：访问临界资源的代码。

必须保证：同一时刻只有一个进程进入。

同步和互斥

【例题】

生产者消费者问题主要体现了（D）

A 同步

B 互斥

C 同步+互斥

D 死锁

【考点】

考查：同步、互斥

【解析】

互斥：多个进程竞争同一资源。例如：多个进程写缓冲区。

同步：多个进程按规定顺序执行。例如：生产后才能消费。

信号量P、V操作

【例题】

系统中有多个生产者进程和多个消费者进程，共享一个最多可存放1000件产品的缓冲区（初始为空）。当缓冲区未满时，生产者可放入一件产品，否则等待；当缓冲区非空时，消费者可取出一件产品，否则等待。要求：一个消费者连续取出10件产品后，其他消费者才能继续取产品。请利用信号量的P、V（wait、signal）操作实现进程同步与互斥，写出完整过程，并说明各信号量的含义及初值。

【考点】

考查：互斥和同步

【答案】

mutex = 1
empty = 1000
full = 0
consume = 1

P1：生产者
while(1)
{
    P(empty);

    P(mutex);

    放产品;

    V(mutex);

    V(full);
}

P2：消费者
while(1)
{
    P(consume);

    for(i=0;i<10;i++)
    {
        P(full);

        P(mutex);

        取产品;

        V(mutex);

        V(empty);
    }

    V(consume);
}

【解析】

1. mutex：控制缓冲区，一次只能一个进程进入，属于互斥信号量。初始值为1。

2. empty：空缓冲区数量，初值为1000，每放一个产品P(empty)，每取一个产品V(empty)。

3. full：已有产品数量，初值为0，生产一个V(full)，消费一个P(full)。

4. consumer：保证一次只有一个消费者连续消费10件商品。初值为1，消费者进入P(consumer)，完成10件消费V(consumer)。

参考资料

现代操作系统第四版
课程ppt