前言

本仓库是对操作系统原理学习过程的记录，内容主要来自王道操作系统考研课程和书籍。课程链接如下：

王道计算机考研 操作系统

《王道操作系统》学习笔记总目录+思维导图

第一章计算机系统概述

• 1.1 操作系统的基本概念
  • 1.1.1 操作系统的概念、功能和目标（系统资源的管理者、提供接口、作为扩充机器、虚拟机）
    • 操作系统的概念
    • 操作系统的功能和目标
  • 1.1.2 操作系统的特征（并发、共享、虚拟、异步）
    • 1.并发
    • 2.共享
    • 3.虚拟
    • 4.异步
• 1.2 操作系统的发展和分类
  • 1.2.1 操作系统的发展和分类（手工、单道/多道批处理、分时、实时、网络、分布式、嵌入式、个人计算机）
• 1.3 操作系统的运行机制
  • 1.3.1 操作系统的运行机制
  • 1.3.2 中断和异常（内中断和外中断、中断处理过程）
  • 1.3.3 系统调用（执行过程、访管指令、库函数与系统调用）
• 1.4 操作系统体系结构（大内核、小内核）
• 1.5 操作系统引导
• 1.6 虚拟机

1.1 操作系统的基本概念

1.1.1 操作系统的概念、功能和目标（系统资源的管理者、提供接口、作为扩充机器、虚拟机）

操作系统的概念

• 是系统最基本最核心的软件，属于系统软件
• 控制和管理整个计算机的硬件和软件资源
• 合理的组织、调度计算机的工作与资源的分配
• 为用户和其它软件提供方便的接口和环境

操作系统的功能和目标

（1）作为计算机系统资源的管理者

• 管理软硬件资源、合理的组织、调度计算机的工作与资源的分配

1️⃣处理器（CPU）管理

• 在多道程序环境下，cpu的分配和运行都以进程（或线程）为基本单位，因此对cpu的管理可理解为对进程的管理。进程管理的主要功能包括进程控制、进程同步、进程通信、死锁处理、处理机调度等。

2️⃣存储器管理

• 为多道程序的运行提供良好的环境，方便用户使用及提高内存的利用率，主要包括内存分配与回收、地址映射、内存保护与共享和内存扩充等功能。

3️⃣文件管理

• 计算机中所有的信息都是以文件的形式存在的，操作系统中负责文件的管理的部分称为文件系统，文件管理包括文件存储空间的管理、目录管理及文件读写管理和保护等。

4️⃣设备管理

• 设备管理的主要任务是完成用户的I/O请求，方便用户使用各种设备，并提高设备的利用率，主要包括缓存管理、设备分配、设备处理和虚拟设备等功能。

以上4种管理功能都由“工人”负责，“雇主”无序关注。

（2）作为用户与计算机硬件系统之间的接口

为了让用户方便、快捷、可靠的操作计算机硬件并执行自己的程序，操作系统提供了用户接口操作系统提供的接口分为两类：命令接口和程序接口

命令接口：用户可以直接使用的，利用这些操作命令来组织和控制作业的执行

程序接口：用户通过程序间接使用的，编程人员可以使用它们来请求操作系统服务

1️⃣命令接口

• 命令接口分为两类：联机命令接口和脱机命令接口，用户可以直接调用
• 联机命令接口：又称交互式命令接口，适用于分时或实时系统的接口，由一组键盘操作命令组成。用户输入一条指令，操作系统就执行一条指令；
• 脱机命令接口：又称批处理接口，使用于批处理系统，由一组作业控制命令组成。用户输入一堆指令，操作系统运行一堆指令。在操作系统运行这些命令时用户不可干预。

批处理(Batch)，也称为批处理脚本。顾名思义，批处理就是对某对象进行批量的处理，通常被认为是一种简化的脚本语言，它应用于DOS和Windows系统中。批处理文件的扩展名为bat 。

2️⃣程序接口

• 程序接口：由一组系统调用（也称广义指令）组成
• 用户通过在程序中使用这些系统调用来请求操作系统为其提供服务，只能通过用户程序间接调用
• 如使用各种外部设备、申请分配和回收内存及其它各种要求

（3）作为扩充机器（虚拟机）

• 没有任何软件支持的计算机称为裸机
• 覆盖了软件的机器称为扩充机器或虚拟机

1.1.2 操作系统的特征（并发、共享、虚拟、异步）

1.并发

并发：两个或多个事件在同一时间间隔内发生，这些事件在宏观上是同时发生的，在微观上是交替发生的， 操作系统的并发性指系统中同时存在着多个运行的程序 并行：两个或多个事件在同一时刻发生 一个单核(CPU)同一时刻只能执行一个程序，因此操作系统会协调多个程序使他们交替进行（这些程序在宏观上是同时发生的，在微观上是交替进行的） 操作系统是伴随着“多道程序技术出现的”，因此操作系统和并发是一同诞生的

在如今的计算机中，一般都是多核cpu的，即在同一时刻可以并行执行多个程序，但是事实上我们计算机执行的程序并不止8个，因此并发技术是必须存在的，并发性必不可少。

2.共享

资源共享即共享，是指系统中的资源可以供内存中多个并发执行的进程共同使用 共享分为两类：互斥共享和同时共享

（1）互斥共享

计算机中的某个资源在一段时间内只能允许一个进程访问，别的进程没有使用权

临界资源(独占资源)：在一段时间内只允许一个进程访问的资源，计算机中大多数物理设备及某些软件中的栈、变量和表格都属于临界资源，它们被要求互斥共享

举个例子：比如QQ和微信视频。同一段时间内摄像头只能分配给其中一个进程

（2）同时共享

计算机中的某个资源在在一段时间内可以同时允许多个进程访问

同时共享通常要求一个请求分为几个时间片段间隔的完成，即交替进行，“分时共享”

这里的同时指在宏观上是同时的，在微观上是交替进行访问的，只是cpu处理速度很快，我们感觉不到，在宏观上感觉是在同时进行

举个例子：比如QQ在发送文件A，微信在发送文件B，宏观上两个进程A和B都在访问磁盘，在我们看来是同时进行的，但是在微观上两个进程A和B是交替进行访问磁盘的，只是时间太短，cpu处理速度太快，我们感觉不到。

注意：有时候多个进程可能真的是在同时进行资源访问，比如玩游戏时可以放音乐，游戏声音和音乐声音都能听见

（3）并发性和共享性互为存在条件

3.虚拟

多道程序设计：是指在计算机内存中同时存放几道相互独立的程序，使它们在管理程序控制之下，相互穿插的运行。 两个或两个以上程序在计算机系统中同处于开始到结束之间的状态。这就称为多道程序设计。多道程序技术运行的特征：多道、宏观上并行、微观上串行。

虚拟是把一个物理上的实体变为若干逻辑上的对应物。

物理实体（前者）是实际存在的；而后者是虚的，是用户感觉上的事务

虚拟技术：用于实现虚拟的技术

虚拟处理器（CPU）：通过多道程序设计技术，采用让多道程序并发执行的方法，分时来使用一个CPU，实际物理上只有一个CPU，但是用户感觉到有多个CPU

虚拟存储器：从逻辑上扩充存储器容量，用户感觉到的但实际不存在的存储器

虚拟设备：将一台物理设备虚拟为逻辑上的多台设备，使多个用户在同一时间段内访问同一台设备，即同时共享，用户宏观上感觉是同时的，但实际上是微观交替访问同一台设备的

操作系统的虚拟技术可归纳为：

• 时分复用技术：如处理器的分时共享
• 空间复用技术：如虚拟存储器

4.异步

异步：多道程序环境允许多个程序并发执行，但由于资源有限，如cpu只有一个，进程的执行并不是一贯到底的，而是走走停停的，它以不可预知的速度向前推进。

比如A进程正在占用CPU计算，B进程这时也想占用CPU计算，B进程只有等，等A进程算完了，A进程去访问磁盘资源了，这时B进程再占用CPU进行计算，B进程还没计算完，A进程从磁盘取出资源了，A进程发现B这时在占用CPU，这时A进程就需要等待，等B算完后再继续到CPU中进行计算。由于每个进程占用资源的时间不固定，所以进程的执行以不可预知的速度前进

1.2 操作系统的发展和分类

1.2.1 操作系统的发展和分类（手工、单道/多道批处理、分时、实时、网络、分布式、嵌入式、个人计算机）

1.操作系统的分类及其特征优劣

2.操作系统的发展历程

1.3 操作系统的运行机制

1.3.1 操作系统的运行机制

要点概述：

1.操作系统的运行机制和体系结构 2.操作系统内核在计算机系统中的层次结构 3.操作系统体系结构类比 4.操作系统用户态和核心态的转换

1.3.2 中断和异常（内中断和外中断、中断处理过程）

1.3.3 系统调用（执行过程、访管指令、库函数与系统调用）

1.4 操作系统体系结构（大内核、小内核）

1.5 操作系统引导

1.6 虚拟机

进程管理

进程与线程

• 进程的概念、组成、特征
• 进程的状态与转换
• 进程控制
• 进程通信
• 线程

进程的概念、组成、特征

进程和程序的区别和联系：

区别：

1)进程是动态的;程序是静态的。

(2)进程有独立性，能并发执行;程序不能并发执行。

(3)二者无一一对应关系。

(4)进程异步运行，会相互制约;程序不具备此特征。

但是，进程与程序又有密切的联系： 进程不能脱离具体程序而虚设， 程序规定了相应进程所要完成的动作。

(5)组成不同。进程包含PCB、程序段、数据段。程序包含数据和指令代码。

(6)程序是一个包含了所有指令和数据的静态实体。本身除占用磁盘的存储空间外，并不占用系统如CPU、内存等运行资源。

(7)进程由程序段、数据段和PCB构成,会占用系统如CPU、内存等运行资源。 (8)一个程序可以启动多个进程来共同完成。

联系：进程不能脱离具体程序而虚设， 程序规定了相应进程所要完成的动作。

进程的组成其中最重要的就是进程控制块PCB（Process Control Block）

PCB简介：

PCB中记录了操作系统所需的，用于描述进程的当前情况以及控制进程运行的全部信息。

PCB的作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。

或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。

例如，当OS要调度某进程执行时，要从该进程的PCB中查处其现行状态及优先级；在调度到某进程后，要根据其PCB中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其PCB中的程序和数据的内存始址，找到其程序和数据；

进程在执行过程中，当需要和与之合作的进程实现同步，通信或者访问文件时，也都需要访问PCB；

当进程由于某种原因而暂停执行时，又须将器断点的处理机环境保存在PCB中。

可见，在进程的整个生命期中，系统总是通过PCB对进程进行控制的，即系统是根据进程的PCB而不是任何别的什么而感知到该进程的存在的。

所以说，PCB是进程存在的唯一标志。

进程的状态与转换

这里说明一下调度和切换的区别：

调度是指决定资源分配给哪个进程的行为，是一种决策行为

切换是指实际分配的行为，是执行行为

一般来说现有资源调度，后有进程切换

进程控制

进程控制大致图解

这里说明一下调度和切换的区别：

调度是指决定资源分配给哪个进程的行为，是一种决策行为

切换是指实际分配的行为，是执行行为

一般来说现有资源调度，后有进程切换

进程的唤醒和阻塞原语

进程的阻塞和唤醒原语是成对存在的，必须成对使用。

阻塞原语是由被阻塞进程自我调用实现的

唤醒原语是由一个被唤醒进程合作或被其他相关的进程调用实现的

进程通信

线程

线程是什么？

可以把线程理解为“轻量级进程”

线程是一个基本的CPU执行单元，也是程序执行流的最小单位。

引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了 系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件）

引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。

引入线程带来的变化及进程与线程的比较

线程的实现方式

前面我们了解了引入线程的好处和引入线程的变化，以及线程的属性，那么线程如何实现呢？

线程的实现分为两类：用户级线程(User-Level Thread,UTL)和内核级线程(Kernel-Level Thread, KTL)。内核级线程又称内核支持的线程。

进程管理

进程同步

• 进程同步的基本概念
• 实现临界区互斥的基本方法
• 进程互斥：锁
• 信号量机制
• 经典同步问题
  • 生产者消费者问题
  • 多生产者多消费者问题
  • 吸烟者问题
  • 读者写者问题
  • 哲学家进餐问题
• 管程

进程同步的基本概念

进程的异步性：各并发执行的进程以各自独立的、不可预知的速度向前推进。

例子：进程通信——管道通信

读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据→读数据”的顺序来执行的。

如何解决这种异步问题，就是“进程同步”所讨论的内容。

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待;
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

do{
	entry section;//进入区
	critical section; //临界区
	exit section;//退出区
	remainder section; //剩余区

}while(true)

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

进程互斥：锁

解决临界区最简单的工具就是互斥锁（mutex lock）。一个进程在进入临界区时应获得锁； 在退出临界区时释放锁。函数acquire()获得锁，而函数release()释放锁。

每个互斥锁有一个布尔变量available，表示锁是否可用。如果锁是可用的，调用acqiure()会 成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。

acquire()
	while(!available)
	;
	//忙等待
	available = false;
	//获得锁
}
release(){
	available = true;
	//释放锁
}

acquire()或release()的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用 acquire()。当多个进程共享同一CPU时，就浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。

需要连续循环忙等的互斥锁，都可称为自旋锁（spin lock），如TSL指令、swap指令、单标志法。

信号量机制

复习回顾+思考：之前学习的这些进程互斥的解决方案分别存在哪些问题？

进程互斥的四种软件实现方式（单标志法、双标志先检查、双标志后检查、Peterson算法）

进程互斥的三种硬件实现方式（中断屏蔽方法、TS/TSL指令、Swap/XCHG指令）

1.在双标志先检查法中，进入区的“检查”、“上锁”操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题；

2.所有的解决方案都无法实现“让权等待”

1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法一一信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互 斥、进程同步。

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量 来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现 的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退 出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。

一对原语：wait(S)原语和 signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal，括号里的信号量S其实就是函数调用时传入的一个参数。

wait、signal原语常简称为P、V操作（来自荷兰语 proberen 和verhogen）。因此，做题的时候常把 wait(S)、signal(S)两个操作分别写为 P(S)、V(S)

信号量机制实现进程同步

进程同步：要让各并发进程按要求有序地推进。

比如，P1、P2 并发执行，由于存在异步性，因此二者交替推进的次序是不确定的。

若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行，那么我们就必须保证“代码4”一定是在“代码2”之后才会执行。

这就是进程同步问题，让本来异步并发的进程互相配合，有序推进。

P1(){
	代码1;
	代码2；
	代码3；
}

P2(){
	代码4；
	代码5；
	代码6;
}

经典同步问题

生产者消费者问题

semaphore mutex = 1;
//互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;
//同步信号量，表示空闲缓冲区的数量
semaphore full = 0;
//同步信号量，表示产品的数量，也即非空缓冲区的数量

多生产者多消费者问题

原因在于：本题中的缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区.

如果盘子的容量为2的话，结果会是什么样？？？

父亲 P(plate)，可以访问盘子→母亲 P(plate)，可以访问盘子→父亲在往盘子里放苹果，同时母亲也可以往盘子里放橘子。于是就出现了两个进程同时访问缓冲区的情况，有可能导致两个进程写入缓冲区的数据相互覆盖的情况。

因此，如果缓冲区大小大于1，就必须专门设置一个互斥信号量mutex来保证互斥访问缓冲区。

总结：在生产者-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。

建议：在考试中如果来不及仔细分析，可以加上互斥信号量，保证各进程一定会互斥地访问缓冲区。

但需要注意的是，实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”。

PV操作题目的解题思路：

1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

吸烟者问题

吸烟者问题可以为我们解决“可以生产多个产品的单生产者”问题提供一个思路。

值得吸取的精华是：“轮流让各个吸烟者吸烟”必然需要“轮流的在桌上放上组合一、二、三”，注 意体会我们是如何用一个整型变量i实现这个“轮流”过程的。

如果题目改为“每次随机地让一个吸烟者吸烟”，我们有应该如何用代码写出这个逻辑呢？

若一个生产者要生产多种产品（或者说会引发多种前驱事件），那么各个V操作应该放在各自对应的 “事件”发生之后的位置。

读者写者问题

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会 产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据 不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。

1.关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。 2.整理思路。根据各进程的操作流程确定P、V操作的大致顺序 3.设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为1， 同步信号量的初始值要看对应资源的初始值是多少）

两类进程：写进程、读进程

互斥关系：写进程一写进程、写进程一读进程。读进程与读进程不存在互斥问题。

哲学家进餐问题

如何防止死锁的发生呢？

①可以对哲学家进程施加一些限制条件，比如最多充许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的

②要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。

③仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

知识回顾与重要考点

哲学家进餐问题的关键在于解决进程死锁。

这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有 两个临界资源，因此就有“死锁”问题的隐患。

如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分 析题中给出的进程之间是否会发生循环等待，是否会发生死锁。

可以参考哲学家就餐问题解决死锁的三种思路。

管程

为什么要引入管程？

信号量机制存在的问题：编写程序困难、易出错

能不能设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松呢？

1973年，Brinch Hansen首次在程序设计语言（Pascal)中引入了“管程”成分一一一种高级同步机制

管程的定义和基本特征

管程是一种特殊的软件模块，有这些部分组成：

1.局部于管程的共享数据结构说明；

2.对该数据结构进行操作的一组过程；

3.对局部于管程的共享数据设置初始值的语句；

4.管程有一个名字。

跨考Tips：“过程”其实就是“函数”

管程的基本特征：

1.局部于管程的数据只能被局部于管程的过程所访问；

2.一个进程只有通过调用管程内的过程才能进入管程访问共享数据;

3.每次仅允许一个进程在管程内执行某个内部过程。

死锁

• 死锁的概念
  • 什么是死锁
  • 进程死锁、饥饿、死循环的区别
  • 死锁产生的必要条件
  • 什么时候会发生死锁
• 死锁的处理策略
  • 预防死锁
  • 避免死锁
  • 死锁的检测和解除

死锁的概念

什么是死锁

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”发生死锁后若无外力干涉这些进程都将无法向前推进

进程死锁、饥饿、死循环的区别

死锁产生的必要条件

什么时候会发生死锁

1．对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资 源（CPU）的竞争是不会引起死锁的。

2.进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1, 两者会因为申请的资源被对方占有而阻塞，从而发生死锁。

3.信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的 P操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资 源)

总之，对不可剥夺资源的不合理分配，可能导致死锁。

死锁的处理策略

1．预防死锁。破坏死锁产生的四个必要条件中的一个或几个。

2．避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）

3．死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。

预防死锁

避免死锁

什么是安全序列？什么是系统的不安全状态，与死锁有何联系？

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。

如何避免系统进入不安全状态 银行家算法

死锁的检测和解除

存储管理

内存管理

• 内存的基础知识
• 内存管理的概念
• 覆盖与交换
• 连续分配管理
• 动态分区分配算法
• 基本分页存储管理的概念
• 基本地址变换机构
• 具有快表的地址变换机构
• 两级页表
• 基本分段存储管理方式
• 段页式管理方式

内存的基础知识

进程运行的基本原理

（1）指令的工作原理---操作码+若干参数（可能包含地址参数）

（2）逻辑地址（相对地址）vs物理地址（绝对地址）

（3）从写程序到程序运行---编译、链接、装入

（4）装入模块装入内存

（5）装入的三种方式

①绝对装入

②静态重定位

③ 动态重定位

（6）链接的三种方式

① 静态链接

②装入时动态链接

③运行时动态链接

内存管理的概念

覆盖与交换

连续分配管理

动态分区分配算法

基本分页存储管理的概念

基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。

通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。 进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系 统内核会把它们放到页表寄存器中。

注意：页面大小是2的整数幂

设页面大小为L，逻辑地址A到物理地址E的变换过程如下：

①计算页号P和页内偏移量W（如果用十进制数手算，则P=A/L，W=A%L；但是在计算机实际 运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页 内偏移量)

②比较页号P和页表长度M，若P≥M，则产生越界中断，否则继续执行。（注意：页号是从0开 始的，而页表长度至少是1，因此P=M时也会越界）

③页表中页号P对应的页表项地址=页表起始地址F+页号P*页表项长度，取出该页表项内容b， 即为内存块号。（注意区分页表项长度、页表长度、页面大小的区别。页表长度指的是这个页 表中总共有几个页表项，即总共有几个页；页表项长度指的是每个页表项占多大的存储空间； 页面大小指的是一个页面占多大的存储空间）

④计算E=b*L+W，用得到的物理地址E去访存。（如果内存块号、页面偏移量是用二进制表 示的，那么把二者拼接起来就是最终的物理地址了）

具有快表的地址变换机构

引入快表后，地址的变换过程

①CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。

②如果找到匹配的页号，说明要访问的页表硕在快表中有副本，则直接从中取出该页对应的内存块 号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。

因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。

③如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块 号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。

因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换) 由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。

因为局部性原理，一般来说快表的命中率可以达到90%以上。

例：某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时 1us，访问一次内存耗时100微秒。若快表的命中率为 90%，那么访问一个逻辑地址的平均耗时是多少？

有的系统支持快表和慢表同时查找，如果是这样，平均耗时应该是(1+100)*0.9+(100+100)*0.1=110.9 微秒

(1+100) * 0.9 +(1+100+100) * 0.1 = 111 微秒

若未采用快表机制，则访问一个逻辑地址需要100+100=200微秒

显然，引入快表机制后，访问一个逻辑地址的速度快多了。

两级页表

基本分段存储管理方式

分段比分页更容易实现信息的共享和保护。

分段、分页管理的对比

页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管 理上的需要，完全是系统行为，对用户是不可见的。

段是信息的逻辑单位。分页的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻 辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。

页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。

分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。

分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。

分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或可重入代码（不属于临 界资源），这样的代码是可以共享的。可修改的代码是不能共享的

访问一个逻辑地址需要几次访存？

分页（单级页表）：第一次访存一一查内存中的页表，第二次访存一一访问目标内存单元。总共两次访存

分段：第一次访存一一查内存中的段表，第二次访存一一访问目标内存单元。总共两次访存

与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以 少一次访问，加快地址变换速度。

段页式管理方式

虚拟内存

• 虚拟内存的基本概念
• 请求分页管理方式
• 页面置换算法
• 页面分配策略、抖动、工作集
• 内存映射文件
• LRU调度机制实现
  • 问题描述
  • 自己写出的无法处理大规模输入数据的代码
    • 问题分析
  • GPT4给出的正确代码
    • 修正的关键点

虚拟内存的基本概念

请求分页管理方式

页面置换算法

页面分配策略、抖动、工作集

内存映射文件

LRU调度机制实现

问题描述

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存

int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 最好以 O(1) 的平均时间复杂度运行。

输入说明

输入若干行：

第一行输入一个整数capacity表示LRU缓存的容量。

后面每行输入为put或get：

如果指令为put类型，后面需要输入两个整数表示key和value。

如果指令为get类型，后面需要输入一个整数表示key。

提示：

1 <= capacity <= 3000

0 <= key <= 10000

0 <= value <= 10^5

最多调用 2 * 10^5 次 get 和 put

输出说明

输出若干行:

每行一个整数，表示为get指令的返回值。

示例

输入

2
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4

输出

1
-1
-1
3
4

解释

LRUCache lRUCache = new LRUCache(2);//容量为2，即最多只能保存两个关键字

lRUCache.put(1, 1); // 缓存是 {1=1}

lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}

lRUCache.get(1);    // 返回 1。注意，这里使用了1

lRUCache.put(3, 3); // 该操作会使得关键字 2 作废（在关键字1和2中，2是最久未被使用的），缓存是 {1=1, 3=3}

lRUCache.get(2);    // 返回 -1 (未找到)

lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}

lRUCache.get(1);    // 返回 -1 (未找到)

lRUCache.get(3);    // 返回 3

lRUCache.get(4);    // 返回 4

自己写出的无法处理大规模输入数据的代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <sstream>
#include <utility>
using namespace std;

struct item{
    int new_count = 0;
    pair<int, int> kv = {0, 0};
};



class LRUCache{
public:
    int capacity = 0;
    vector<item> Cache;
    LRUCache(int capacity){
        this->capacity = capacity;
    }

    int get(int key){
        int size = Cache.size();
        for(int i = 0; i < size; i++){
            if(Cache[i].kv.first == key){
                for(int j = 0; j < size; j++){
                    if(Cache[j].new_count < Cache[i].new_count)
                        Cache[j].new_count++;
                }
                Cache[i].new_count = 1;

                return Cache[i].kv.second;
            }
        }
        return -1;
    }

    void put(int key, int value){
        int size = Cache.size();
        bool exist = false;
        if(size < capacity){
            for(int i = 0; i < size; i++){
                if(Cache[i].kv.first == key){
                    Cache[i].kv.second = value;
                    exist = true;
                }
            }
            if(!exist){
                item temp = {1, {key, value}};
                Cache.push_back(temp);
                for(int i = 0; i < size; i++){
                    Cache[i].new_count++;
                }
            }
        }else{
            int maxCount = 0;
            int index = 0;
            for(int i = 0; i < size; i++){
                if(Cache[i].new_count > maxCount){
                    maxCount = Cache[i].new_count;
                    index = i;
                }
                Cache[i].new_count++;
            }
            Cache[index].new_count = 1;
            Cache[index].kv = {key, value};
        }
    }

};


int main() {

    int n;

    cin >> n;

    LRUCache lRUCache = LRUCache(n);

    string operation;

    int key, value;

    string line;
    while (getline(cin, line)) {
        istringstream iss(line);
        iss >> operation;
        if (operation == "put") {
            iss >> key >> value;
            lRUCache.put(key, value);
        } else if (operation == "get") {
            iss >> key;
            cout << lRUCache.get(key) << endl;
        }
    }

    return 0;
}

问题分析

1. 超出容量处理问题：代码中处理容量达到上限时的逻辑有些问题，特别是如何更新缓存。如果缓存已经满了（即缓存大小等于容量），需要逐出最久未使用的元素，但目前的逻辑没有处理好这些情况。
2. 更新 new_count 时未考虑边界情况：当缓存中已经有该元素时，代码没有正确更新 new_count。
3. 容量最大时（即 capacity = 3000）：代码没有专门处理这个边界值的情况。标准的 LRU 要求 O(1) 时间复杂度，而目前的实现需要 O(n) 时间复杂度。

GPT4给出的正确代码

为了修正这些问题，应该采用另一种更高效的数据结构来优化 LRU 缓存的实现。一个常见的方法是使用 unordered_map和 list相结合来实现 LRU 缓存，以达到 O(1) 时间复杂度。

以下是修正后的实现：

#include <iostream>
#include <unordered_map>
#include <list>
#include <string>
#include <sstream>
#include <utility>

using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = cacheMap.find(key);
        if (it == cacheMap.end()) {
            return -1;  // key 不存在
        } else {
            cacheList.splice(cacheList.begin(), cacheList, it->second); // 移动当前的 (key, value) 对到链表头部
            return it->second->second;  // 返回 value
        }
    }

    void put(int key, int value) {
        auto it = cacheMap.find(key);
        if (it != cacheMap.end()) {
            cacheList.splice(cacheList.begin(), cacheList, it->second); // 移动当前的 (key, value) 对到链表头部
            it->second->second = value;  // 更新 value
        } else {
            if (cacheList.size() == capacity) {
                auto last = cacheList.back(); // 取出链表末尾的 (key, value) 对
                cacheMap.erase(last.first);  // 从 map 中删除该 key
                cacheList.pop_back();  // 移除链表末尾的元素
            }
            cacheList.emplace_front(key, value);  // 在链表头部添加新的 (key, value) 对
            cacheMap[key] = cacheList.begin();  // 在 map 中记录该 key 对应的 list 迭代器
        }
    }

private:
    int capacity;
    list<pair<int, int>> cacheList;  // 保存缓存的 (key, value) 对的链表
    unordered_map<int, list<pair<int, int>>::iterator> cacheMap;  // 保存 key 及其在链表中的位置
};

int main() {
    int n;
    cin >> n;

    LRUCache lRUCache(n);

    string operation;
    int key, value;
    string line;
    while (getline(cin, line)) {
        if (line.empty()) continue; //忽略空行
        istringstream iss(line);
        iss >> operation;
        if (operation == "put") {
            iss >> key >> value;
            lRUCache.put(key, value);
        } else if (operation == "get") {
            iss >> key;
            cout << lRUCache.get(key) << endl;
        }
    }

    return 0;
}

修正的关键点

1. 使用 list 和 unordered_map 来实现 LRU 缓存，以保证 get 和 put 操作都在 O(1) 时间复杂度内完成。
2. 每当 get 或 put 操作时，都将相应的 (key, value) 对移动到链表头部，从而实现 LRU 机制。
3. 当缓存达到容量限制时，直接移除链表末尾的元素，并从 unordered_map 删除对应的键，这样可以处理容量为 3000 的边界情况。

这段代码解决了之前版本中存在的多个问题，并使得 LRU 缓存能够在效率上达标，且能够有效处理给定的输入限制。

文件管理

文件系统基础

• 文件的概念
• 文件的逻辑结构
• 目录结构
  • 文件控制块
  • 单级目录结构
  • 二级目录结构
  • 多级目录结构（树形目录结构）
  • 无环图目录结构
  • 索引节点（FCB的改进）
• 文件的物理结构/文件分配方式
  • 连续分配
  • 链式分配
  • 索引分配
  • 逻辑结构 VS 物理结构
• 文件存储空间管理
• 文件的基本操作
• 文件共享
• 文件保护
  • 口令保护
  • 加密保护
  • 访问控制

文件的概念

一个文件有哪些属性？

文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件

标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。

类型：指明文件的类型位置：文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见)

大小：指明文件大小

创建时间、上次修改时间文件所有者信息

保护信息：对文件进行保护的访问控制信息

文件的逻辑结构

按文件是否有结构分类，可以分为无结构文件、有结构文件两种。

无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如：Windows操作系统中的.txt文件。

有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。

有结构文件在逻辑上可分为三种：顺序文件、索引文件、索引顺序文件

目录结构

文件控制块

FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项

FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。

最重要，最基本的还是文件名、文件存放的物理地址。

FCB实现了文件名和文件之间的映射。使用户（用户程序）可以实现“按名存取

需要对目录进行哪些操作？

• 搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
• 创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
• 删除文件：当删除一个文件时，需要在目录中删除相应的目录项
• 显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
• 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名)

单级目录结构

早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。

单级目录实现了“按名存取”，但是不允许文件重名。

在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。

显然，单级目录结构不适用于多用户操作系统。

二级目录结构

早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，UserFlie Directory）。

多级目录结构（树形目录结构）

例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径”。

在Linux中，“.”表示当前目录，因此如果“照片”是当前目录，则"自拍jpg"的相对路径为：“./2015-08/自拍.jpg”。从当前路径出发，只需要查询内存中的“照片”目录表，即可知道"2015-08"目录表的存放位置，从外存调入该目录，即可知道“自拍jpg”存放的位置了。

可见，引入“当前目录”和“相对路径”后，磁盘I/O的次数减少了。这就提升了访问文件的效率。

用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。例如：自拍.jpg 的绝对路径是“/照片/2015-08/自拍.jpg”。

每次都从根目录开始查找，是很低效的。因此可以设置一个“当前目录”。例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径”。

在 Linux 中，“.”表示当前目录，因此如果“照片”是当前目录，则"自拍jpg"的相对路径为:“./2015-08/自拍.jpg”。

树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”。

无环图目录结构

索引节点（FCB的改进）

当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。

存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。

相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。

文件的物理结构/文件分配方式

操作系统需要对磁盘块进行哪些管理？

• 对非空闲磁盘块的管理 （存放了文件数据的磁盘块）：“文件的物理结构/文件分配方式”要探讨的问题
• 对空闲磁盘块的管理：“文件存储空间管理”要探讨的问题

在内存管理中，进程的逻辑地址空间被分为一个一个页面

同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。

于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。

操作系统为文件分配存储空间都是以块为单位的

用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射

连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块。

读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。

结论：连续分配的文件在顺序读/写时速度最快

结论：物理上采用连续分配的文件不方便拓展。

结论：物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片可以用紧凑来处理碎片，但是需要耗费很大的时间代价。

连续分配（总结）

连续分配方式要求每个文件在磁盘上占有一组连续的块。

优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快

缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片

链式分配

链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。

隐式链接一一除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。

优点：很方便文件拓展，不会有碎片问题，外存利用率高。

缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

如何实现文件的逻辑块号到物理块号的转变？

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB）...

从目录项中找到起始块号，若i>O，则查询内存中的文件分配表FAT，往后找到i号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。

结论：采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的0~i-1号逻辑块），由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。

索引分配

如何实现文件的逻辑块号到物理块号的转换？

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB）。

从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可只i号逻辑块在外存中的存放位置。

可见，索引分配方式可以支持随机访问。文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可）但是索引表需要占用一定的存储空间。

①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

链接方案不支持直接访问。

逻辑结构 VS 物理结构

文件存储空间管理

空闲链表法

操作系统保存着链头、链尾指针。

如何分配：若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。

如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作

空闲链表法

操作系统保存着链头、链尾指针。

如何分配：若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。

如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高

位示图：每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。

如何分配：若文件需要K个块，①顺序扫描位示图，找到K个相邻或不相邻的“0”；②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；③将相应位设置为“1”。

如何回收：①根据回收的盘块号计算出对应的字号、位号；②将相应二进制位设为“0”

适用于离散分配和连续分配的情况。

文件的基本操作

文件共享

文件保护

口令保护

为文件设置一个“口令”（如：abc112233），用户请求访问该文件时必须提供“口令”。

口令一般存放在文件对应的FCB或索引结点中。用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许该用户访问文件

优点：保存口令的空间开销不多，验证口令的时间开销也很小。

缺点：正确的“口令”存放在系统内部，不够安全。

加密保护

访问控制

目录

文件系统和虚拟文件系统

• 文件系统层次结构
• 文件系统的全局结构（布局）
• 虚拟文件系统

文件系统层次结构

文件系统的全局结构（布局）

物理格式化，即低级格式化一一划分扇区，检测坏扇区，并用备用扇区替换坏扇区

下图展示了文件系统在内存中的结构：

注：近期访问过的目录文件会缓存在内存中，不用每次都从磁盘读入，这样可以加快目录检索速度

虚拟文件系统

虚拟文件系统的特点：

①向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异

②VFS要求下层的文件系统必须实现某些规定的函数功能，如：open/read/write。

一个新的文件系统想要在某操作系统上被使用，就必须满足该操作系统VFS的要求

打开文件后，创建vnode，并将文件信息复制到vnode中，vnode的功能指针指向具体文件系统的函数功能。

I/O管理

I/O 管理概述

• I/O 设备的基本概念与分类
• I/O 控制器
• I/O 控制方式
• IO软件层次结构
• 输入输出应用程序接口和驱动程序接口

I/O 设备的基本概念与分类

“l/O”就是“输入/输出”（Input/Output)

I/O 设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的 硬件部件。

UNIX系统将外部设备抽象为一种特殊的文件，用户可以使用 与文件操作相同的方式对外部设备进行操作。

Write操作：向外部设备写出数据

Read操作：：从外部设备读入数据

I/O 设备的分类一一按使用特性

• 人机交互类外部设备：数据传输速度慢
• 存储设备：数据传输速度快
• 网络通信设备：数据传输速度介于上述二者之间

I/O 设备的分类一一按传输速率分类

• 低速设备：鼠标、键盘等一一传输速率为每秒几个到几百字节
• 中速设备：如激光打印机等——传输速率为每秒数千至上万个字节
• 高速设备：如磁盘等一传输速率为每秒数千字节至千兆字节的设备

I/O 设备的分类一一按信息交换的单位分类

• 块设备，传输速率较高，可寻址，即对它可随机地读/写任一块I/O设备按信息交换的单位分类，块设备：如磁盘等一一数据传输的基本单位是“块”。
• 字符设备，传输速率较慢，不可寻址，在输入/输出时常采用中断驱动方式。字符设备：鼠标、键盘等，数据传输的基本单位是字符。

I/O 控制器

I/O设备的机械部件主要用来执行具体I/O操作。

如我们看得见摸得着的鼠标/键盘的按钮；显示器的LED屏；移动硬盘的磁臂、磁盘盘面。

I/O设备的电子部件通常是一块插入主板扩充槽的印刷电路板。

I/O 控制方式

IO软件层次结构

输入输出应用程序接口和驱动程序接口

阻塞/非阻塞I/O

阻塞I/O：应用程序发出I/0系统调用，进程需转为阻塞态等待。

eg：字符设备接口－－从键盘读一个字符 get

非阻塞I/O：应用程序发出I/O系统调用，系统调用可迅速返回，进程无需阻塞等待。

eg：块设备接口－一往磁盘写数据write

I/O 核心子系统

• I/O 核心子系统概述
• SPOOLing 技术（假脱机技术）
• 设备的分配与回收
• 缓冲区管理
  • 单缓冲
  • 双缓冲
  • 使用单/双缓冲在通信时的区别
  • 循环缓冲区
  • 缓冲池

I/O 核心子系统概述

操作系统需要实现文件保护功能，不同的用户对各个文件有不同的访问权限（如：只读、读和写等）。

在UNIX系统中，设备被看做是一种特殊的文件，每个设备也会有对应的FCB。当用户请求访问某个设备时，系统根据FCB中记录的信息来判断该用户是否有相应的访问权限，以此实现“设备保护”的功能。（参考“文件保护”小节)

SPOOLing 技术（假脱机技术）

什么是脱机技术？

批处理阶段引入了脱机输入/输出技术（用磁带完成）。

在外围控制机的控制下，慢速输入设备的数据先被输入到更快速的磁带上。之后主机可以从快速的磁带上读入数据，从而缓解了速度矛盾

Tips：为什么称为“脱机”——脱离主机的控制进行的输入/输出操作。

引入脱机技术后，缓解了CPU与慢速I/O设备的速度矛盾。另一方面，即使CPU在忙碌，也可以提前将数据输入到磁带；即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带。

虽然系统中只有一个台打印机，但每个进程提出打印请求时，系统都会为在输出井中为其分配一个存储区（相当于分配了一个逻辑设备），使每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享。

SPOOLing 技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享设备。

设备的分配与回收

设备分配时应考虑的因素

• 设备的固有属性
• 设备分配算法
• 设备分配中的安全性

设备的固有属性可分为三种：独占设备、共享设备、虚拟设备。

独占设备——一个时段只能分配给一个进程（如打印机）

共享设备——可同时分配给多个进程使用（如磁盘），各进程往往是宏观上同时共享使用设备，而微观上交替使用。

虚拟设备一一采用SPOOLing技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用（如采用 SPOOLing技术实现的共享打印机）

设备的分配算法：先来先服务、优先级高者优先、短任务优先……

从进程运行的安全性上考虑，设备分配有两种方式：

安全分配方式：为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒。（eg：考虑进程请求打印机打印输出的例子）

一个时段内每个进程只能使用一个设备

优点：破坏了“请求和保持”条件，不会死锁

缺点：对于一个进程来说，CPU和I/O设备只能串行工作

不安全分配方式：进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞。

一个进程可以同时使用多个设备

优点：进程的计算任务和/O任务可以并行处理，使进程迅速推进

缺点：有可能发生死锁（死锁避免、死锁的检测和解除）

静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源

破坏了“请求和保持”条件，不会发生死锁

动态分配：进程运行过程中动态申请设备资源

设备分配的步骤

①根据进程请求的物理设备名查找SDT（注：物理设备名是进程请求分配设备时提供的参数）

②根据SDT找到DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程。

③根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。

④根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。

注：只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/O设备进行数据传送

缺点：

①用户编程时必须使用“物理设备名”，底层细节对用户不透明，不方便编程

②若换了一个物理设备，则程序无法运行

③若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待

改进方法：建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名

逻辑设备表（LUT）建立了逻辑设备名与物理设备名之间的映射关系。

某用户进程第一次使用设备时使用逻辑设备名向操作系统发出请求，操作系统根据用户进程指定的设备类型（逻辑设备名）查找系统设备表，找到一个空闲设备分配给进程，并在LUT中增加相应表项。

如果之后用户进程再次通过相同的逻辑设备名请求使用设备：则操作系统通过LUT表即可知道用户进程实际要使用的是哪个物理设备了，并且也能知道该设备的驱动程序入口地址。

逻辑设备表的设置问题：

整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复，适用于单用户操作系统

每个用户一张LUT：不同用户的逻辑设备名可重复，适用于多用户操作系统

缓冲区管理

什么是缓冲区？有什么作用？

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。

使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合（如存储器管理中所用的联想寄存器，由于对页表的访问频率极高，因此使用速度很快的联想寄存器来存放页表项的副本)

一般情况下，更多的是利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理 好这些缓冲区。

单缓冲

双缓冲

双缓冲

假设某用户进程请求某种块设备读入若干块的数据。若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）

双缓冲题目中，假设初始状态为：工作区空，其中一个缓冲区满，另一个缓冲区空

结论：采用双缓冲策略，处理一个数据块的平均耗时为 Max(T,C+M)

使用单/双缓冲在通信时的区别

循环缓冲区

缓冲池

磁盘与固态硬盘

• 磁盘的结构
• 磁盘调度算法
• 减少磁盘延迟时间的算法
• 磁盘的管理
• 固态硬盘SSD

磁盘的结构

磁盘的分类：

磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道

磁头不可移动的称为固定头磁盘。这种磁盘中每个磁道有一个磁头

磁盘调度算法

一次磁盘读/写操作需要的时间

寻找时间（寻道时间）T：在读/写数据前，将磁头移动到指定磁道所花的时间。

①启动磁头臂是需要时间的。假设耗时为S;

②移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道。则：

寻道时间Ts=S+m*n

延迟时间T：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r（单位：转/秒，或转/分），则平均所需的延迟时间T=(1/2)*(1/r)=1/2r

传输时间T：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为 N。则:传输时间Tt=(1/r)*(b/N)=b/(rN)

每个磁道要可存N字节的数据，因此b字节的数据需要b/N个磁道才能存储。而读/写一个磁道所需的时间刚好又是转一圈所需要的时间1/r

总的平均存取时间Ta=Ts+1/2r+b/(rN)

延迟时间和传输时间都与磁盘转速相关，且为操线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间

减少磁盘延迟时间的算法

减少延迟时间的方法：交替编号

若采用交替编号的策略，即让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。

思考：为什么？

磁盘的物理地址是（柱面号，盘面号，扇区号）而不是（盘面号，柱面号，扇区号）？

答：读取地址连续的磁盘块时，采用（柱面号，盘面号，扇区号）的地址结构可以减少磁头移动消耗的时间

磁盘的管理

磁盘初始化：

Step1：进行低级格式化（物理格式化），将磁盘的各个磁道划分为扇区。一个扇区通常可分为头、数据区域（如512B大小）、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验、CRC循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误)

Step 2：将磁盘分区，每个分区由若干柱面组成（即分为我们熟悉的C盘、D盘、E盘)

Step 3：进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（如位示图、空闲分区表)

坏块的管理

坏了、无法正常使用的扇区就是“坏块”。这属于硬件故障，操作系统是无法修复的。应该将坏块标记出来，以免错误地使用到它

对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在FAT表上标明。（在这种方式中，坏块对操作系统不透明)

对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表。

在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。

会保留一些“备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明

固态硬盘SSD