操作系统（王道）

1. 计算机系统概述

1.1 操作系统的基本概念

1.1.1 操作系统的概念，功能和目标

操作系统的层次结构：

操作系统的概念：

操作系统的功能：

1. 作为系统资源的管理者
   
2. 作为用户和计算机硬件之间的接口
   

用户接口：

图形用户界面：

目标：方便用户使用

3. 作为最接近硬件的层次

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

并发

1.概念：

2.并发VS并行：

共享

1.概念：

2.并发与共享的关系：

虚拟

概念：

虚拟技术：

异步

概念：

总结

1.2 操作系统的发展与分类（手工=>个人计算机）

OS的发展与分类：

手工操作系统

单道批处理系统

多道批处理系统

为何多道处理系统能使资源利用率大幅提升？

若采用多道批处理系统：

分时操作系统

实时操作系统

总结

1.3 操作系统的运行机制与体系结构

OS的运行机制与体系结构知识总览：

1.3.1 操作系统的运行机制和体系结构（大小内核）

指令：处理器（CPU）能识别，执行的最基本命令

两种指令：

CPU 如何判断当前是否可以执行特权指令？

两种处理器状态：

两种程序：

总结：

体系结构

类比：

操作系统的内核：

概念：

大内核与微内核：

总结

1.3.2 中断与异常

中断机制的诞生

早期计算机一次最多只能执行一个程序：

为了解决上述问题，人们发明了操作系统(作为计算机的管理者)，引入中断机制，实现了多道程序并发执行
本质:发生中断就意味着需要操作系统介入，开展管理工作

中断的概念与作用

遗留问题：用户态和核心态是如何转换的？

答:
“用户态→核心态”是通过中断实现的。并且中断是唯一途径；
“核心态→用户态”的切换是通过执行一个特权指令，将程序状态字(PSW) 的标志位设置为“用户态”。

中断的分类

中断的分类：

另一种分类方式：

外中断的处理过程

执行过程：

总结

1.3.3 系统调用

什么是系统调用，有何作用？

操作，系统作为用户和计算机硬件之间的接口，需要向上提供一些简单易用的服务。主要包括命令接口和程序接口。其中，程序接口由一组系统调用组成。

应用程序通过系统调用请求操作系统的服务。系统中的各种共享资源都由操作系统统一掌管，因此在用户程序中，凡是与资源有关的操作(如存储分配，I/0操作、 文件管理等)，都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。

系统调用的分类：

系统调用和库函数的区别

系统调用背后的过程

传递系统调用参数=>执行陷入指令(用户态) =>执行系统调用相应服务程序(核心态) =>返回用户程序

注意:
1. 陷入指令是在用户态执行的，执行陷入指令之后立即引发-一个内中断，从而CPU进入核心态

2.发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行

3.陷入指令是唯一 一个只能在用户态执行，而不可在核心态执行的指令

总结

2. 进程管理

2.1 进程与线程

2.1.1 进程的定义，特征，组成，组织

单道处理：早期计算机只支持单道程序，即所有设备服务一条程序

程序段、数据段、PCB三部分组成了进程实体(进程映像)。一般情况下，我们把进程实体就简称为进程，
例如，所谓创建进程，实质.上是创建进程实体中的PCB;而撤销进程，实质上是撤销进程实体中的PCB。
注意: PCB是进程存在的唯一标志!

从不同的角度，进程可以有不同的定义，比较传统典型的定义有:

1. 进程是程序的一次执行过程。
2. 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
3. 进程是具有独立功能的程序在数据集合上运行的过程，它是系统进行资源分配和调度的一一个独立单位

强调“动态性”

引入进程实体的概念后，可把进程定义为:进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

注:严格来说，进程实体和进程并不一样，进程实体是静态的，进程则是动态的。不过，除非题目专门考察二者区别，否则可以认为进程实体就是进程。因此我们也可以说“进程由程序段、数据段、PCB三部
分组成”

进程的组成

进程由程序段、数据段、PCB三部分组成

PCB中包含的信息：

进程的组成：

进程的组织方式

进程的组织方式：

链接方式：

索引方式：

进程的特征

进程的特征：

注意：
动态性：进程的最基本特征
独立性：进程是系统进行资源分配、调度的独立单位
异步性：各进程以不可预知的速度向前推进，可能导致运行结果的不确定性

总结

2.1.2 进程的状态与转换

进程的状态

进程的三种基本状态：

注意：单核处理机环境下，每时刻最多只能有一个进程处于运行状态（双核可以同时有两个进程处于运行态）

进程的另外两种状态：

进程状态之间的转换

总结

2.1.3 原语实现对进程的控制

进程控制的定义与实现

进程控制：实现各个进程状态之间的转换

进程控制的实现：

原语：

进程控制相关的原语

学习技巧:进程控制会导致进程状态的转换。无论哪个原语，要做的无非三类事情: .

1. 更新PCB中的信息(如修改进程状态标志、将运行环境保存到PCB、从PCB恢复运行环境)
   a.所有的进程控制原语一定都会修改进程状态标志
   b.剥夺当前运行进程的CPU使用权必然需要保存其运行环境
   c.某进程开始运行前必然要恢复期运行环境

2. 将PCB插入合适的队列

3. 分配/回收资源

进程的创建：无=>创建态=>就绪态

进程的终止：就绪态/阻塞态/运行态=>终止态=>无

进程的阻塞：运行态=>阻塞态

进程的唤醒：阻塞态=>就绪态

注意：阻塞原语唤醒原语必须成对使用，因何事阻塞就应因何事唤醒。

进程的切换：运行态=>阻塞态/就绪态；就绪态=>运行态

总结

2.1.4 进程之间的通信

共享存储

共享存储：

管道通信

管道通信：

消息传递

总结

进程通信：

2.1.5 线程概念和多线程模型

引入线程机制

引入线程：

可以把线程理解为“轻量级进程”，线程是一一个基本的CPU执行单元，也是程序执行流的最小单位。

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

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

引入线程带来的变化：

线程的重要属性

线程的属性：

线程的实现方式

用户级线程：

内核级线程：

用户线程映射到内核线程上：

多线程模型

多对一模型：

一对一模型：

多对多模型：

总结

2.2 处理机的调度

2.2.1 处理机调度的概念及层次

调度的概念：

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。

在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。

高级调度：

中级调度：

补充知识，进程的挂起状态与七状态模型：

低级调度：

三种调度：

总结：

2.2.2 进程调度的时机，方式，切换与过程

进程调度的时机

内核程序临界区：

进程调度的方式

进程的切换与过程

总结:

2.2.3 度算法的评价指标

CPU利用率

系统吞吐量

周转时间

等待时间

2.2.4 作业/进程调度算法(FCFS先来先服务，SJF短时间优先，HRRN高响应比优先)

FCFS先来先服务

SJF短时间优先

注意几个小细节

HRRN高响应比优先

总结：

2.2.5 作业/进程调度算法(时间片轮转调度算法，优先级调度算法，多级反馈队列调度算法)

时间片轮转调度算法

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。

另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时恫来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

优先级调度算法

多级反馈队列调度算法

举例：

总结：

2.3 进程的同步与互斥

2.3.1 进程的同步与互斥

什么是进程同步？

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

什么是同步互斥？

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后,另一个进程才能去访问临界资源。

临界资源互斥访问：

注意:
临界区是进程中访问临界资源的代码段。
进入区和退出区是负责实现互斥的代码段。
临界区也可称为“临界段”。

进程互斥需要遵守的原则：

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

总结：

2.3.2 实现临界区进程互斥的软件实现方法(单标志，双标志(先后)，peterson)

单标志法

算法思想:两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

turn表示当前允许进入临界区的进程号，而只有当前允许进入临界区的进程在访问了临界区之后，才会修改turn的值。也就是说，对于临界区的访问，一定是按P0→P1→P0→P1…这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是PO，而P0一直不访 问临界区，那么虽然此时临界区空闲，但是并不允许P1访问。

因此，单标志法存在的主要问题是:违背“空闲让进”原则。

双标志先检查

算法思想:设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿， 比如“flag[0]=ture”意味着0号进程PO现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。

实现：

一个进程检查了还没上锁之前又进行了另一个进程，导致出现问题：两边同时上锁，两边同时访问临界区

双标志后检查

算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查” 的方法，来避免上述问题。

实现：

Peterson算法

算法思想:双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Gary L. Peterson想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试 “孔融让梨”，主动让对方先使用临界区。

实现：

进入区:

1. 主动争取;
2. 主动谦让;
3. 检查对方是否也想使用，且最后一次是不是自己说了“客气话”

Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。

Peterson算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。

总结：

2.3.3 实现临界区进程互斥的硬件实现方法(中断屏蔽，TestAndSet ，Swap指令)

中断屏蔽方法

TestAndSet (TS指令/TSL 指令)

Swap指令(XCHG指令)

总结：

2.3.4 信号机制(整型信号量，记录型信号P，V)

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

整型信号量

记录型信号

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

举例：

总结：

2.3.5 信号量机制实现进程的互斥，同步与前驱关系

实现进程互斥

实现进程同步

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

保证代码4一定在代码2之后执行：

实现进程的前驱关系

总结：

2.3.6 进程同步与互斥经典问题

生产者—消费者问题

问题描述：

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产-一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注: 这里的“产品”理解为某种数据)

生产者、消费者共享一个初始为空、大小为n的缓冲区。
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。
缓冲区是临界资源，各进程必须互斥的访问

模型实现

能否改变相邻PV操作的顺序？

总结：

多生产者—多消费者问题

问题描述：

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
用PV操作实现上述过程。

问题分析：

实现：

问题:
可不可以不用互斥信号量?

结论:即使不设置专门的互斥变量mutex,也不会出现多个进程同时访问盘子的现象

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

若缓冲区为2：

总结：

吸烟者问题

问题描述：
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复(让三个抽烟者轮流地抽烟)

问题分析：

实现：

总结：

读者—写者问题

问题描述：

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

问题分析：

实现：1

实现：2

总结：

哲学家进餐问题

问题描述：

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时,才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

分析：

若五个哲学家一起拿起自己左手的筷子：死锁

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

方法二：

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

采用各哲学家拿筷子这件事必须互斥执行的方法：

各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了

总结：

2.3.7管程和java中实现管程的机制

信号量机制存在的问题:编写程序困难、易出错能不能设计一种机制， 让程序员写程序时不需要 再关注复杂的PV操作，让写代码更轻松呢?

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

管程的定义：

用管程解决生产者消费者问题（封装思想）

引入管程的目的无非就是要更方便地实现进程互斥和同步。

1. 需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
2. 需要在管程中定义用于访问这些共享数据的“入口”- – -其实就是一些函数(如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品)
3. 只有通过这些特定的“入口”才能访问共享数据
4. 管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入(如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意:这种互斥特性是由编译器负责实现的，程序员不用关心)
   5.可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待(此时，该进程应先释放管程的使用权，也就是让出“入口”) ;可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

java中类似于管程的机制

总结：

2.4 死锁

2.4.1 死锁详解（预防，避免，检测，解除）

死锁的概念：

预防死锁

破坏互斥条件

破坏不剥夺条件

破坏请求和保持条件

破坏循环等待条件

总结

避免死锁（银行家算法）

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

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

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

银行家算法原理：

实际做题(手算)时可用更快速的方法找到-一个安全序列:
经对比发现，(3,3,2) 可满足P1、P3,说明无论如何，这两个进程的资源需求一定是可以依次被满足的，因此P1、 P3一定可以顺利的执行完，并归还资源。可把P1、 P3先加入安全序列。
(2,0,0)+(2, 1,1)+(3,3,2)=(7,4,3)
剩下的PO、P2、P4都可被满足。同理，这些进程都可以加入安全序列。于是，5个进程全部加入安全序列，说明此时系统处于安全状态，暂不可能发生死锁。

若无法找到任何一个安全序列，说明此时系统处于不安全状态，有可能发生死锁。

银行家算法过程：

总结

死锁的检测和解除

死锁的检测

为了能对系统是否已发生了死锁进行检测，必须:
①用某种数据结构来保存资源的请求和分配信息;
②提供一种算法，利用，上述信息来检测系统是否已进入死锁状态。

如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。
相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程…

如果按上述过程分析，最终能消除所有边，就称这个图是 可完全简化的 。此时一定没有发生死锁(相当于能找到一个安全序列)

如果最终不能消除所有边，那么此时就是发生了死锁。

最终还连着边的那些进程就是处于死锁状态的进程。

死锁的检测算法

死锁的解除

总结：

3.0 内存

3.1内存管理的概念

3.1.1 什么是内存，进程的基本管理，指令的理解及过程

什么是内存：

补充知识：

逻辑地址VS物理地址

从写程序到程序运行

装入模块，装入内存

绝对装入

静态重定位

动态重定位

链接的三种方式

总结:

3.1.2 内存管理管些什么？

1. 负责内存空间的分配与回收
2. 操作系统需要提供某种技术从逻辑上对内存空间进行扩充（虚拟技术）
3. 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地
   址的转换
4. 操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰

3.1.3 覆盖技术与交换技术的思想

覆盖技术

覆盖技术的思想:将程序分为多个段(多个模块)常用的段常驻内存，不常用的段在需要时调入内存。

内存中分为一个“固定区”和若干个“覆盖区”。

需要常驻内存的段放在**“固定区**”中，调入后就不再调出(除非运行结束)

不常用的段放在**“覆盖区，需要用到时调入内存，用不到时调出内存**

交换技术

总结

3.1.4 内存的分配与回收

连续分配:指为用户进程分配的必须是一个连续的内存空间。

单一连续分配方式

固定分区分配

动态分区分配

采用什么样的数据结构？

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。

动态分区分配没有内部碎片，但是有外部碎片。
内部碎片,分配给某进程的内存区域中，如果有些部分没有用上。
外部碎片，是指内存中的某些空闲分区由于太小而难以利用。
如果内存中空闲空间的总和本来可以满足某进程的要求，
但由于进程需要的是- -整块连续的内存空间，因此这些
“碎片”不能满足进程的需求。
可以通过紧凑(拼凑，Compaction) 技术来解决外部碎片。

总结：

3.1.5 动态分区分配的四种算法

首次适应算法(First Fit)

最佳适应算法(Best Fit)

最坏适应算法(Worst Fit)

邻近适应算法(Next Fit)

总结：

3.1.6 分页存储

非连续分配:为用户进程分配的可以是一些分散的内存空间。

基本分页存储管理的思想一一把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分

分页存储管理的基本概念：

如何实现地址的转换

计算：

计算机内部计算方式：

结论:如果每个页面大小为2^k B，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号
因此，如果让每个页面的大小为2的整数幂，计算机就可以很方便地得出一个逻辑地址对应的页号和页内偏移量。

逻辑地址结构

页表：

总结

3.1.7 分页存储管理的基本地址变换结构

基本地址变换结构：

举例：

对页表项大小的进一步讨论

总结

3.1.8 快表的地址变换结构

局部性原理

①CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
②如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块
号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
③如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存(注意:在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换)

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。
因为局部性原理，一般来说快表的命中率可以达到90%以上。

举例：

总结

3.1.9 二级页表的原理和地址结构

单级页表存在什么问题?如何解决?

两级页表的原理、逻辑地址结构

如何实现地址变换?

两级页表问题需要注意的几个细节

总结：

3.1.10 基本分段存储原理

什么是分段(类似于分页管理中的"分页")

什么是段表(类似于分页管理中的“页表”)

如何实现地址变换

分段、分页管理的对比

总结

3.1.11 段页式存储管理

分页、分段管理方式中最大的优缺点

分段管理中产生的外部碎片也可以用“紧凑”来解决，只是需要付出较大的时间代价

分段+分页的结合

段页式管理的逻辑地址结构

段表、页表

一个进程只能对应一个段表，但一个进程可以对应多个页表

如何实现地址变换

总结

3.2 虚拟内存管理

3.2.1 虚拟内存的基本概念

传统存储管理方式的特征、缺点

局部性原理

虚拟内存的定义和特征

虚拟内存有一下三个主要特征:
多次性:无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
对换性:在作业运行时无需- .直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
虚拟性:从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。

如何实现虚拟内存技术

总结

3.2.2 请求分页管理方式

页表机制

缺页中断机构

5：在具有快表机构的请求分页系统中，访问一个逻辑地址时，若发生缺页，则地址变换步骤是:
查快表(未命中)–查慢表(发现未调入内存)一-调页(调
入的页面对应的表项会直接加入快表)–查快表(命中)–访问目标内存单元

总结：

3.2.3 页面置换算法

最佳置换算法（OPT）

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

先入先出置换算法（FIFO）

最近最久未使用置换算法

始终置换算法

改进的时钟置换算法

总结

3.2.4 页面分配策略

何时调入页面

工作集

总结

4.0 文件

4.1 文件系统

4.1.1 初识文件管理和概念

文件的属性

一个文件有哪些属性?
文件名:由创建文件的用户决定文.件名，主要是为了方便用户找到文
件，同一目录下不允许有重名文件。
标识符:一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。
类型:指明文件的类型.
位置:文件存放的路径(让用户使用)、在外存中的地址(操作系统使用，对用户不可见)
大小:指明文件大小
创建时间，上 次修改时间，文件所有者信息
保护信息:对文件进行保护的访问控制信息

文件内部的数据组织形式

文件之间的组织形式

操作系统向上提供的几个基本功能

总结

4.1.2 文件逻辑结构

有结构文件逻辑结构

顺序文件

注:一般来说，考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。之后的讲解中提到的顺序文件也默认如此。
可见，顺序文件的缺点是增加/删除一个记录比较困难(如果是串结构则相对简单)

索引文件

索引顺序文件

索引顺序文件效率分析

多级索引顺序文件

总结

4.1.3 文件目录结构

文件控制块

单级目录结构

两级目录结构

多级目录结构

无环图目录结构

索引节点

总结

4.1.4 文件的物理结构

文件块，磁盘块

文件分配方式—连续分配

1.连续分配的文件在顺序读/写时速度最快

2.物理.上采用连续分配的文件不方便拓展。

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

文件分配方式—链接分配

索引分配

实现逻辑块到物理块的转换

索引分配

多层索引

混合索引

超级超级超级重要考点:①要会根据多层索引、混合索引的结构计算出文件的最大长度(Key: 各级索引表最大不能超过一一个块) ;②要能自己分析访问某个数据块所需要的读磁盘次数(Key: FCB中会 存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件–顶级索引块是否已调入内存)

总结

4.1.5 文件存储管理

存储空间的管理与初始化

存储空间管理—空闲表法

存储空间管理—空闲链表法

空闲盘块链

空闲盘区链

存储空间管理—位示图法

存储空间管理—成组链接法

成组链接法

分配一个空闲块

分配100个空闲块

如何回收1

若超级块中有一个空闲块，在要回收一个空闲块的情况下，直接插入超级块即可。

如何回收2

4.1.6 文件的基本操作原理

文件的基本操作：

4.1.7 文件共享

基于索引节点的共享方式（硬链接）

基于符号链的共享方式（软链接）

总结

4.1.8 文件保护

文件保护：

4.1.9 文件系统的层次结构

举例：

4.2 磁盘组织与原理

4.2.1 磁盘的结构

4.2.2 磁盘调度算法

先到先服务算法（FCFS）

最短寻找时间优先算法（SSTF）

扫描算法（SCAN）

LOOK调度算法

循环扫描算法（C-SCAN）

C-LOOK调度算法

总结

4.2.3 减少磁盘延迟时间的方法

4.2.4 磁盘管理

5.0 IO控制

5.1 I/O管理概述

5.1.1 什么是I/O设备？有几类？

5.1.2 I/O设备控制器

I/O控制器的组成

值得注意的小细节:①一个1/0控制器可能会对应多个设备;
②数据寄存器、控制寄存器、状态寄存器可能有多个(如:每个控制/状态寄存器对应一个具体的设备)，且这些寄存器都要有相应的地址，才能方便CPU操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O;另一些计算机则采用I/0专用地址，即寄存器独立编址。

内存影像IO VS 寄存器独立编制

总结：

5.1.3 控制I/O设备的几种方式

需要注意的问题:

1. 完成一次读/写操作的流程;
2. CPU干预的频率;
3. 数据传送的单位;
4. 数据的流向;
5. 主要缺点和主要优点。

程序直接控制方式

中断驱动方式

DMA方式

DMA方式

DMA控制器

通道控制方式

总结：

5.1.4 I/O软件的层次结构

5.2 I/O核心子系统

5.2.1 内核的I/O核心子系统及功能

5.2.2 I/O设备假脱机技术

5.2.3 I/O设备的分配与回收

5.2.4 缓冲区管理

单缓冲

双缓冲

第一种情况：

第二种情况：

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

总结：