技术学习：王道操作系统

介绍

操作系统是什么？

计算机结构大概分为四层：

• 用户
• 应用程序
• 操作系统
• 硬件

操作系统是一类系统软件，调度硬件资源，合理分配管理软件（因此操作系统又被称作资源管理器（resource manager））。

程序要运行首先要被放到内存中，然后才能被 CPU 处理；运行中的程序叫进程。

双击打开 QQ.exe，对应进程就会被放到内存中；

QQ 正常运行过程中，对应进程被 CPU 处理。

QQ 若想调用摄像头等，操作系统会把相应硬件分配给他。

计算机还会提供用户和硬件之间的接口。主要分为三种：GUI 接口，命令接口，程序接口。

联机/交互式命令接口：用户说一句，系统做一句。（cmd）

脱机/批处理命令接口：用户说一堆，系统做一堆。（.bat）

程序接口：通过程序才能调用。（.dll）

只有硬件的计算机叫裸机；操作系统将硬件资源转换为通用的、强大的虚拟形式，有时操作系统也被称为虚拟机。操作系统提供几百个系统调用（system call）供其他应用程序使用，实现运行程序、访问内存和设备等操作，也可以说操作系统为其他应用程序提供了一个标准库（standard library）。

操作系统几大特征

操作系统围绕以下几大主题展开：

• 虚拟化（virtualize）：尽管一般只有一个 CPU，但是能同时进行多个进程，造成多个 CPU 的假象。多个程序实例同时用到一片内存地址时，却能各运行各的，值互不干扰。实际上每个进程是在访问自己的私有虚拟内存空间（virtual address space)，虚拟内存通过一定的规则映射到物理内存上，运行中的程序的物理内存是完全独立的。
• 并发（concurrency）**不是并行！并行是同时发生，并发是交替发生。**单核计算机就会采用并发的程序运行方式。现在尽管都有四核计算机，可以进行4个程序的并行操作，但是并发仍然很重要。
• 共享：系统中的某些资源供多个进程使用。

​ 互斥型共享就是一次只能一个程序用，如摄像头；

​ 同时型共享就是两个进程交替使用，如 QQ 微信 同时发送文件。

• 异步性：并发执行的程序有时候会卡住。比如 AB 程序都要用同一个地址，A先用了，B用的时候就要等A用完释放才能用。

操作系统历史

手工操作阶段：用户手工打点，给机器。人机协调不均衡，资源分配不均匀。

批处理阶段——单道批处理系统：用户打好的点交给磁带，磁带读入计算机速度快得多（监督程序，早期的操作系统）。但是利用率仍然很低。

批处理阶段——多道批处理系统：每次内存中同时读入多个程序。多个程序并发执行，有了”中断“的概念。但是用户在程序执行的时候没法干涉，人机交互很差。

分时操作系统：计算机以时间片为单位轮流给所有用户提供服务。用户的请求可以被及时响应，解决了人机交互问题；各个用户之间也感受不到其他用户的存在。但是众生平等，没有优先级。

实时操作系统：优先度高的任务可以先被处理，并且必须在给定的时限内完成任务。

OS 运行机制和体系结构

计算机中的指令有的安全（加减乘除运算），有的危险一点（清空内存）。因此需要通过权限控制限制用户能执行的指令。

具体实现方法为：CPU 处于核心态（管态）时可以执行所有指令；处于用户态（目态）时只能执行非特权指令。

内核程序是系统的管理者，可以执行所有指令，运行在核心态；

应用程序只能执行非特权指令，运行在用户态。

操作系统的内核包含橙黄两部分：大内核。

只包含黄色部分：微内核。

各自的缺点：大内核组织结构混乱，难以维护；微内核频发切换，性能低。

中断

一开始的计算机只是简单的串行执行程序。

现在的操作系统不仅可以并发执行程序，而且收到中断指令时，CPU 会切换到内核模式，中断当前程序的执行，按中断指令调整程序执行顺序，然后恢复到用户态继续执行。

中断分内中断、外中断。区别在于中断指令来自于 CPU 内部还是外部。

系统调用

我们知道计算机硬件为了供用户使用，向上层提供了一些接口。用户直接使用的接口叫命令接口；用户通过应用程序间接使用的接口叫程序接口。系统调用是操作系统提供给应用程序的接口。

系统调用可以增加安全性，不让用户可以直接随意访问所有功能。如两个人去打印店用打印机，第一个人打到一半第二个人发送了他的打印任务请求，可打印机最终还是有序地把两个人的任务分别打印好了。如果用户能直接让打印机打印自己的任务，不加协调，无法实现这样的结果。

哪些操作要通过系统调用的方式进行？凡是和资源相关的。这样可以保证系统的安全性和稳定性。

编程语言提供的一些库函数也是从下往上提供的一些封装的功能。但库函数不一定是系统调用。如求绝对值的库函数，这个库函数就不是系统调用，用户直接就能访问。

现在大多数系统调用都是高级语言中封装的部分库函数。

陷入指令核心态不能执行，可以理解为：核心态只能执行系统调用，不能发起系统调用给自己。

进程

进程（process）是操作系统中最基本的抽象。

进程就是运行中的程序，程序本身只是存放在磁盘上的一些静态指令，是操作系统让其运行起来。

现在我们的计算机可以同时运行上百个进程，是通过虚拟化 CPU 而实现。每个进程只运行一个时间片段，然后跳转到其他进程，造成多个进程同时运行的假象。

内存中存放每个进程的程序段和数据段，但内存怎么知道哪个是哪个进程的？通过一种数据结构叫进程控制块（PCB）找到对应进程的额程序段和数据段。程序段、数据段、PCB 组成了进程实体。

操作系统需要一些低级机制（mechanism）切换程序运行，如上下文切换（context switch，停止当前程序，并运行另一个程序）；还需要一些智能决定要切换到哪个程序，如策略（poliicy，根据一些算法判断要运行哪个程序，如“哪个程序在上一分钟运行的时间更长？”）

进程的几种状态

就绪态就是除了处理机其他资源都准备就绪了。阻塞态还需要准备资源才能进入就绪态。

进程控制

就是这几种进程状态之间的切换。

通过两个指针实现：就绪队列指针和阻塞队列指针，用于存放就绪和阻塞的进程（阻塞队列可能还有好几个，按阻塞原因分组）。

状态切换使用原语，因为原语执行过程中不会受到中断的干扰。

原语做的操作无非是：1. 修改 PCB；2. 把 PCB 放到对应队列中；3. 分配/释放资源。

进程通信

进程之间互相通信，安全起见不能直接进行。

1. 共享存储，共用一块存储空间。有基于数据结构的分享（给定数据结构存储方式）和基于存储区的分享（内存中划定一块存储区，进程自己决定怎么存储）。

   共享的缓冲区叫做管道，如果只采用一个管道只能使用半双工型，全双工型需要两根管道。两个进程访问该管道要互斥的访问。

   管道写满才能读，读空了才能写。

   读出来的数据就直接被丢弃了。所以安全起见只能有一个读的进程。

2. 消息传递。类似计网的数据报，消息封装好之后发给另一个进程的消息队列。

线程

让一个进程可以并发执行多个任务。比如 qq 聊天的同时可以发文件收消息发消息。

一个进程包含多个线程。线程是调度， CPU 的程序执行单元，进程是资源分配的单元，比如把显示器资源分配给 QQ。

线程有两种实现方式：

1. 用户级线程 （ULT），进程的切换由应用程序实现，而不需要操作系统管理，因此用户态下就能实现线程的切换，且线程的存在对用户透明，对操作系统不透明。
2. 内核级线程（KLT），线程管理靠操作系统在核心态下实现、
3. 两者组合的形式，n 个用户级线程映射到 m 个内核级线程上。

操作系统分配 CPU 处理机只能分配给内核级线程（因为用户级线程对操作系统来说不透明）。所以如果有三个用户级线程，但这个应用程序只有两个内核级线程，最多也只能被分配到两个处理机，最多也只能有两个用户线程并发执行（哪怕这个操作系统是三核的，四核的，有很多核空闲出来）。

几个用户级进程映射到几个内核级进程上？这就是多线程模型问题。

1. 多个用户级进程映射到一个内核级进程上。

   

   线程切换不用在核心态下进行，切换效率高，但是并发度不高。

2. 一对一。

   

   优缺点正好和1相反。

3. n 对 m，用户级线程多于内核级线程，较为折中。

   

进程调度和切换

线程数往往多于处理机数，因此要考虑按怎样的算法分配处理机。

进程调度和切换的区别是什么？

进程调度先选再切换。

进程切换包括：

1. 保存原来运行的数据
2. 恢复新进程的数据。

切换会影响效率。

调度层次1：高级调度（→就绪态）

首先先不说处理机够不够处理内存中的线程，有时候线程多到内存中放不下。高级调度需要按一定的原则从外存中挑选一些作业放到内存中并建立进程（PCB），让他们有进一步竞争处理机的机会。主要解决的是调入问题。

调度层次2：中级调度（挂起态→就绪态）

引入虚拟存储技术之后，暂时不能运行的进程可以先调至外存等待（挂起）。等可以运行再拿回来，这样能提高内存利用率和系统吞吐量。

其对应的 PCB 并不会一起移出内存，而是存储了被挂起的进程的信息，被放到内存中的挂起队列里。

中级调度就是挑选挂起的进程调入内存。

引入挂起的进程实际上可以说是有七种状态。不能运行的进程都会先放到就绪挂起态或阻塞挂起态，能运行再回到内存（有的操作系统阻塞挂起态直接回到就绪挂起态）。注意挂起和阻塞的区别！

调度层次3：初级调度（就绪态→运行态）

就是从就绪队列中按一定算法挑一个进程来执行。

调度时机

当前运行的进程主动（运行完了，或者异常终止）或被动放弃处理机，就会发生调度。

有以下几种情况不能调度：

1. 进程在处理中断时。
2. 进程在操作系统内核程序临界区中。（临界资源及临界区（内核/普通）以及三种进程不能切换的情况_Unstoppable~~~的博客-CSDN博客_内核临界区 在此感谢这位博主！调度区和调度资源是两回事，调度区又分普通调度区和内核调度区。）
3. 原语执行时.

调度方式

非剥夺/非抢占调度方式：只允许进程主动放弃处理机。哪怕有更紧急的进程到达，也不会把当前正在使用处理机的进程挤开。开销小，但没法处理紧急情况。

剥夺/抢占调度方式：允许进程主动或被动放弃处理机。

调度算法评价指标

CPU 利用率：CPU 有活干的时间/总时间。

系统吞吐量：完成了的作业道数/总用时。

周转时间：提交作业到作业完成用时。包括在外存等待高级调度→在内存就绪队列等待低级调度→在 CPU 上执行→等待 I/O 操作完成的时间。

注意概念问题，进程是运行中的程序，所以作业在外存的时候不可以被称为进程。进入内存才创建了进程。

带权周转时间：周转时间/实际运行时间。越小越好（排队用时少吧）。

等待时间：作业等待处理机状态的时间之和。（不包括 IO）

响应时间：用户提交请求到首次产生响应的时间。

调度算法

早期批处理调度算法：只根据等待时间和预估处理时间调度，不考虑是否紧急。

算法名	思想	规则	用于何种调度	是否可抢占	优缺点	是否会导致饥饿（某个作业长期得不到服务）
先来先服务 FCFS	公平	先来后到	都用	非抢占式	公平；但排在后面的短作业体验差	不会
短作业优先 SJF	让平均等待、周转、带权周转时间最短	最短的作业优先服务	都用	非抢占式（最短剩余优先算法是抢占式的，当有进程入队的时候立刻调度。平均时间抢占式的更少）	平均时间少，但对长作业不公平，可能“饥饿	会
高响应比优先 HRRN	综合考虑等待时间和处理时间	，优先执行响应比大的	都用	非抢占式（当前进程主动结束时才进行调度）	综合考虑了等待时间和服务时间，长作业等久了也会执行	不会

后期交互式系统算法：

算法名	思想	规则	用于何种调度	是否可抢占	优缺点	是否会导致饥饿
时间片轮转 RR	公平轮流地为所有进程服务	按先来后到，轮流给各个进程一个时间片执行。如果没执行完就交给下一个进程，然后重新到队尾排队（时间片大小要合适。太大就是 FCFS 算法了，太小效率低）	进程调度	是	公平；响应快；但是频繁切换效率低，不区分紧急程度	不会
优先级调度	按紧急程度处理	优先度高的先执行	都用	是	可以优先处理紧急任务；但总是高优先级任务到来可能饥饿	会
多级反馈队列调度算法	根据时间片计算优先级	进程刚到达放入1队列，一个时间片内没完成放入2队列，还没完成一直往后放，如果已经在最后一个队列了就重新放到该队列结尾。1队列优先级最高	进程调度	是	综合了各个调度算法优点	会

进程同步和互斥

虽然之前提过进程是异步的，各个进程相互独立，但是有的工作是有顺序的，比如先读入再写。

同步，即相互制约，指部分工作的次序需要协调。

互斥：一些共享资源不允许多个进程同时访问。比如一次只允许一个进程访问的资源叫临界资源。

进程互斥遵循以下原则：

1. 空闲让进
2. 忙则等待
3. 有限等待，防止饥饿，不让进程等太久
4. 让权等待，如果该进程进不去，那就不给他了，赶紧给别人。

进程互斥软件实现方法

1. 单标志法

​ 一开始只允许 P1 访问。一直到P1把 turn 变为0，然后切时间片的时候才能交给 P0. 两者交替访问。

​ 但是违背了空闲让进。如果只有 P0 想访问临界区，就一直进不去。

2. 双标志先检查法

   

   判断对方有没有在访问。

   但是如果按照①⑤③②⑥⑦的顺序，两者会同时访问临界资源，违反了忙则等待。

3. 双标志后检查法

   先上锁再检查。但是两个进程要是都先锁住了，就都执行不了了，可能出现死锁问题。

4. Peterson 算法

   

   可惜没有遵守让权等待。

进程互斥硬件实现方法

1. 中断屏蔽方法

   访问临界资源的时候把中断关上；访问完了打开，再允许调度。但是用户态不适用（用户态不应该搞中断的问题），而且对多处理机不适用。

2. TestAndSet 指令

   是硬件实现方法，下图为软件实现方式。

   

   如果 lock 原来是 true，那么其他进程访问的时候一直卡在 while 处。知道访问临界区的进程退出并解锁，其他进程访问的时候 lock 才是 false，才能跳出循环。

   但是无法解决让权等待问题，如果有一个进程把 lock 变成 true 之后又进不去临界区，其他进程就永远无法访问，一直忙等。

3. Swap 指令

   

   逻辑上等同于 TS，也无法解决让权等待问题。

4. 信号量

   信号量用于表示系统中某种资源的数量。我们用一对原语（等待 P，信号 V）对信号量做操作.信号量涉及到的三个操作就是初始化、P、V。

   

   然而这样的信号量也没能解决让权等待问题。不过一个记录型信号量可以解决。

   

   释放完资源，S.value≤0 说明还有进程在阻塞队列中，直接把当前刚释放的处理机给阻塞队列的进程执行。

   这样如果该进程进不去自己的处理机，就会把自己调整到堵塞态，把处理机让出来给别人，解决了让权等待问题。

信号量实现进程同步和互斥

互斥：

同步：如怎样保证2一定在4之前执行

进程种类

生产者和消费者

生产者把产品放入未满的缓冲区，消费者从未空的缓冲区取出。两者要互斥地对缓冲区访问；同时如果生产者要放入满缓冲区要先等消费者取出，消费者要从空缓冲区取要先等生产者放，这两件事是同步关系。

注意 决定互斥的 mutex 顺序不能和决定同步的 empty full 颠倒！！！

如上图，如果先进行①②，则互斥锁打开，生产者因为仓库已满无法放入，阻塞。消费者又因为互斥锁打开无法取东西，阻塞，就死锁了。

多生产者 多消费者

缓冲区大小（盘子）如果为1，那么不用互斥变量也能解决。

因为苹果、橘子、盘子变量同时只能有一个=1，每次最多也只能有一个变量访问。如果缓冲区变为2就需要 mutex 了，父母同时放入水果可能覆盖对方的值。

吸烟者问题

因为只有一个缓冲区，所以不需要 mutex 就能实现互斥。

吸烟者问题其实是实现了一个生产者生产多种产品的问题。此例中生产者生产的产品顺序固定，还可以修改生产顺序逻辑。

读者-写者问题

允许多人同时读，但是有人在写的时候其他人不能读写。

读进程有限的解决办法：mutex 用于所有读进程互斥访问 count 变量，当 count 变量=0时才可写入。但是写进程有饿死的风险。

如果再加一个写的互斥信号量，就能让写操作优先于读操作了。

哲学家进餐问题

一个进程同时持有多个临界资源的情况。

如果只是简单地用两个信号量判断左右两根筷子是否空闲，可能所有进程并发拿起了左手的筷子，并发地卡住了右手的筷子，造成死锁。

有几种解决方案：①拿两只筷子的行为添加一个互斥信号量。这样一个哲学家拿不起来被阻塞的时候，其他哲学家也不会尝试拿。

②奇数先拿左手，偶数先拿右手，这样相邻的人拿筷子就会互斥。

管程

信号量挺琐碎的，而且容易出错，顺序错了都会影响结果。

管程内的数据只有在管程内的过程（函数）才能访问；一次只允许一个进程进入管程。

monitor 是 java 语法的管程，每次只允许一个进程访问（互斥），进程只能通过管程提供的特定入口进入。我们可以自己定义逻辑判断，让进程等待或释放（同步）。

关键字 synchronized 修饰的函数同一时间段内只能被一个进程访问。

死锁

A等B，B等C，C等A，都在等对方手里的资源。

和饥饿不一样，饥饿是如果一直来新进程自己可能一直无法继续。

死锁的四个条件：

1. 互斥，对某一资源互斥使用。
2. 不剥夺，不能抢资源。
3. 请求和保持，在新资源还在请求时可以保持自己手里已有的资源。
4. 循环等待，存在资源的循环等待链。比如有12两个资源，进程一申请顺序：12，进程二申请顺序：21，两者正好互相锁住。

可能发生死锁的情况：

• 竞争不能共用的系统资源时；
• 进程推进顺序不当；（哲学家拿筷子，都先拿左手的）
• 信号量使用不当（如生产者消费者一例，先互斥锁再信号量锁。生产者先进入满仓库，因为当前只有自己进程进入仓库所以互斥锁不干扰；但是仓库已满，无法放入导致阻塞；消费者又因为生产者正在访问，互斥锁限制导致阻塞）。

预防死锁

破坏四个条件之一。

1. 把资源改为可以共享使用的；不过不是所有设备都能强行改的。

2. 剥夺：要么如果当前进程资源不足时立刻全部释放资源，等一会再重新运行；要么根据优先级，高优先级抢低优先级的资源使用。但是比较复杂而且会影响前一个进程，常用于易于保存和恢复状态的进程（如 CPU）；效率低；方案一还可能导致饥饿。

3. 请求保持：采用静态分配方法，进程开始运行时就把所有需要的资源都给他，全程让他运行。但是可能有的资源这个进程就用一两下，一直占着会比较浪费；可能导致饥饿。

4. 

   比如上例，两个进程申请资源顺序都从小到大，先1后2，就不会死锁了。但是实际资源使用顺序可能并不是从小到大，效率低；而且增添设备要修改编号，不方便；而且用户编程要注意顺序，比较费事。

避免死锁

安全序列就是按某种顺序分配资源，所有进程都能顺利得到，不会死锁。存在一种安全序列的情况，那么当前系统就是处于安全状态。

银行家算法：

如图，剩余资源 (3, 3, 2)，视作一个一维数组。P0 全分配也不够，不行；P1可以，全分配给P1后P1归还资源，剩余资源数变成 (5, 3, 2)；然后P2不够，P3可以，变成 (7, 4, 3)；p4 变成 (7, 4, 5); P1 变成 (7, 5, 5)，最后 P2 P4，五轮循环全部分配。

最大需求：Max

已分配：Allocation

最多还需要：Need

当次发起申请的请求量：Request

Request≥Need：出错了

Request≤Available：说明有多余空闲。系统先尝试分配一下，成功后证明安全，正式分配。

检测、消除死锁

点表示进程，方框表示资源，箭头表示分配。如果所有箭头都能被顺利消除，证明不会发生死锁。

P1向R2要一个。R2给了P2一个自己还剩下一个，所以可以要到。（P1释放后，就能把P1的所有边去掉了）

P2向R1要一个。但是R1三个都给出去了，所以P2要不到，阻塞了。

P1运行完释放，R1里就有两个空闲的了，P2就能要到了。

下例就没法全部消除，死锁了。只有P3能正常运行并释放。

解决办法：可以挂起或终止死锁的部分节点，或者回退到没有发生死锁的断点。

内存

存放数据的硬件，程序要先被放到内存中才能被处理.

代码被编译成指令，通常还会涉及到几个地址。比如一个加法指令涉及的三部分（A，B，C）A代表：这是一个加法指令；B C代表：把B中的数据加到C中。

指令中采取的是相对的逻辑地址，因为还不能确定物理存到了哪里。

装入有三种：

1. 绝对装入，编译时就知道要放到哪个物理地址里，编译时直接采用物理地址；适用于单道程序环境。
2. 静态重定位装入，编译时采用相对地址，装入时根据相对地址存入到物理地址。但是如果内存中容量不够，就不能装入。用于早期操作系统。
3. 动态重定位装入，刚进内存不会装入，等到程序运行时再装入。允许程序运行中在内存里移动。现代操作系统。

链接也有三种，装入前链接成一块，边装入边链接，运行时再链接。

内存管理

内存中存了多少？空闲多少？进程分配到哪里？怎么释放？内存扩充（游戏60G，内存4G，采用虚拟内存的方式扩充）、地址转换（就是装入。逻辑地址和物理地址之间的链接 是操作系统解决，程序员不用管）、内存保护。

覆盖与交换技术

覆盖技术：解决内存太小的问题。内存中分固定区和覆盖区。

缺点在于固定区覆盖区要程序员自己规定，不透明。

交换技术：把内存中某些进程拿出来，再把某些进程换进去。磁盘中专门有一块交换区，追求交换的速度，采用连续存储方式，IO 比文件区要快得多。缺页率高时换出得多。优先换出阻塞和优先级低的进程。

覆盖是同一个进程中的，交换是多个进程中的。

内存保护限制每个进程只能访问自己范围内的数据。可以设置上下限寄存器；或者重定向寄存器决定上限，界地址寄存器代表最大长度。

内存分配

连续分配：内存分为系统区和用户区。系统区存放操作系统相关数据；用户区存进程，只能存一个。实现简单，没有外部碎片（内存空闲区域太小，没法分配给进程的情况），可以通过覆盖技术扩大内存，不一定要保护；但是利用率低，而且有内部碎片（分配给某个进程的内存区域，有些部分没有用到）。

固定分区分配：内存分成很多个分区，每个分区只装一道作业。

（分区大小相等，缺乏灵活性，但是适用于一台计算机控制多个相同对象的场合；

也可以设置不同大小的分区，适用于各种作业）

操作系统需要叫分区说明表的数据结构，让内核程序知道哪些分区可用不可用，起始位置，大小等。没有外部碎片，但是有内部碎片；而且可能有过大的用户程序，所有分区都满足不了，就只能覆盖，降低效率。

动态分区分配：根据进程大小动态建立分区。系统区大小都是不固定的。可以采取空闲表或空闲链的数据结构存储信息。

动态分配的算法：

1. 要插入的进程比空闲区小：更新空闲区起始位置和大小。
2. 要插入的进程和空闲区一样大：直接在空闲分区表中删掉这一条空闲区的记录。

动态分区回收算法

1. 要回收的分区前面或后面有一块空闲：更新那块空闲的起始位置和大小。
2. 前后没有空闲：新增一条空闲记录。
3. 前后都有空闲：空闲表中两条记录 更新成一整条。

动态分配算法 没有内部碎片，但有外部碎片。可以通过“拼凑”来解决。

具体怎么选择空闲分区分配？

动态分区分配算法

首次适应算法：从小地址到大逐渐找。空闲区按地址从小到大存储在空闲链中。

最佳适应算法：优先找能容得下的最小的空闲区，大的留着给大的进程预备着。空闲分区从小到大存储在空闲链中。小碎片会越来越多，导致外部碎片。

最坏适应算法：优先使用最大的空闲分区，避免外部碎片。但是大进程到来的时候可能插入不进来了。

临近适应算法：因为首次适应算法每次都从头找，头部可能有很多小碎片，每次又要遍历。临近适应算法每次从上次结束的地方开始查找。也是优先使用最大分区，类似最坏适应算法。

基本分页存储算法

是一种非连续分配。

每个分区10MB，A进程23MB，可以拆成10+10+3MB存储。

但是这样导致第三个分区内部碎片达到7MB。如果分区大小为2MB，那么只有最后一个分区有1MB内部碎片。

每个分区是一个页框，有页框号，从0开始。把进程分配成页框的大小，叫做一个个页，有页号。

分的页并不是连续存储在分区中的，可以不连续存储，根据逻辑地址找页与页之间的关系。

页号：逻辑地址/页面长度。

偏移量：逻辑地址%页面长度。

如第80个内存单元，页面长度50，那么页号=1，偏移量=30.

如果页面大小是2的整数次幂，那么页面范围就是00000……0001000……0000到00000……00010111……11111，末尾的部分就是页面偏移量。

页表存储页面信息，页表项包含页号和块号信息，每个页表项应该能表示出所有块数的信息。比如有2^20个块，则每个页表项要有20种状态，20位即至少三个字节。(但是通常采用4个字节 这样让总内存数可以等于证书个页表项)

基本地址变换机构

用于实现分页管理逻辑地址转变为物理地址的操作。

基本地址变换结构 每次要访问两次内存。

查页表，知道要访问的数据的位置：一次；

去访问数据：二次。

具有快表的地址变换机构

让最近访问过的页表项存到快表中。

如果快表中有该页表项，直接取出该项计算出物理地址，就不用到慢表中查表了。

访问快表命中了，就只需要一次访存。

两级页表

1. 单极页表必须连续存储；
2. 并不是整张页表都会被频繁访问到。

可以把长长的页表再分成离散的几块，即第二级页表。又叫顶级页表。这样就解决了问题1.

然后对于没有进内存的目标页，访问的时候产生缺页中断，然后调入页。

但是没有快表的话，两级页表要访存3次。

基本分段存储管理方式

按逻辑把程序分为一个个段（如 主函数，sum 函数……）分段离散的存储到内存中。可读性更高。

段号规定了可以有多少个段，段内地址规定了段的大小。

当然啦，为了查找到哪个段放在哪里，也需要段表。段表每一条包含段号、基址（起始位置）、段长。

段表寄存器存储在系统区的 PCB 中，即段表的位置。

相比分页，分段是有意义的，是二维的，用户既要给出段名（如 main 函数的段），又要给出地址。

分段也更容易实现信息共享和保护。首先什么代码可以共享？不能修改的代码可以共享，如常量，防止多个进程并发访问会出问题。

然后分段是按逻辑分的。比如每个函数分一个段。分页是按大小直接截断的。所以分段可能提取出可以共享的代码片段，分页会更难一些。

分段也是两次访存，也可以尝试快表。

段页式管理方式

分段和分页的缺点是什么？

分页划分固定分区，但不便于信息共享和保护。

分段根据程序分配大小不确定的分区，可能有外部碎片（紧凑还是付出代价很大的）。而且进程太大的话也难以找到一大块连续区域。

那，把大的段分页就好了。

分页的页表包含：页号 页内偏移量信息。分段的段表包含：段号 段长 基址信息（段号可以隐含）。

段页式系统的逻辑地址结构 段包含：段号 页表长 页存放块号（起始地址）。页包含：页号 页面存放的内存块号。

虚拟内存

归根结底，以上的内存分配方法需要把整个程序都装入内存运行。而且由于内存的驻留性，程序运行完之前整个都一直留在内存中。

第一，没必要，程序的某些部分不常使用，不用一直占在内存里，内存利用率低。第二，太大的程序装不进来。第三，很多程序排队时，这样一次只能运行很少的几个，并发性差。

根据之前快存学到的局部性原理，可以把常用的部分留到内存中，不常用的拿出去。要用到的不在内存里，就拿进来；内存太满，就把不常用的再拿出去。

虚拟内存有多次性（分多次装入）、对换性（可以换出来）、虚拟性。

存储方式：采用连续型并不合适，因为要分多次装入。改用请求式管理。

请求分页管理

和基本分页管理的区别在于：1. 要访问的信息可能在内存中，也可能不在。不在的话要调入进来。要存储该页是否在内存中的信息。

2. 暂时不用的可以换出去。如果在内存中做过修改，那么不用拿回到外存；如果做过修改了就要了。

先根据状态位判断要访问的页在不在内存中，不在里面，就先产生缺页中断，调入内存。如果有空闲块就插到空闲块里，没有就根据页面置换算法换出来一个不常用的。调出内存的页面如果发生改变就要写入外存，没有就直接丢掉。最后还要修改请求页表中的状态信息。

缺页中断是自行产生的内中断。

几个值得注意的点：

1. 我们知道，如果内存中的内容被修改（发生了”写“操作），状态位中的修改位变为1，移出内存时要再写入外存。实际上修改位的改变不一定用在内存中修改，可能只修改快表中的修改位即可，这样少访存。
2. 换入换出页面太频繁，开销会很大。
3. 页面调入内存后，直接就放到快表里，之后访问就访问快表就行。

页面置换算法

追求更小的缺页率，这样换入换出更少。

最佳置换算法 OPT：选择不再使用，或者最长时间内不再被访问的页面淘汰。

插入701之后满了，再想插入2就要顶掉一个。看看后面要访问的页面，7是最不着急的，先把7顶掉。后面以此类推。

注意缺页不一定就会发生页面置换。如果还有块空闲就不用。

但最大问题就是操作系统无法提前预判后面的页面访问序列。

先进先出置换算法 FIFO：最早进来的页面最早被淘汰。就是队列的数据结构。

但是这就是再猜啊。怎么能因为用的早就觉得下一秒他不会用了呢？买彩票呢。可能会引发 Belady 异常（为进程分配的物理块变大时，缺页次数反而变多）。

最近最久未使用置换算法 LRU：

哪个最久没用过，就先替换掉哪个。

性能确实好，但是开销大，实现困难。

时钟置换算法 CLOCK：每个页面添加一个访问位，初值都是0，访问过了改为1.每次优先替换掉0的页面。如果全为1，则全置0后再次扫描。

改进的时钟置换算法：同时考虑访问位和修改位。

替换：第一轮扫描找0，0的替换。这种不仅最近没用过，而且不用写入外存。

第二轮找0，1的替换。这种最近没用过，但是之前修改过，要写入外存。

如果这两轮都没找到，说明所有的第一位都是1.全部置0，再进行扫描。

第三轮找0，0，类似第一轮。

第四轮找0，1，类似第二轮。

页面分配策略

驻留集：请求分页存储管理中分给内存的物理块的集合。虚拟存储中，驻留集大小一般小于进程总大小。太小，频繁缺页出入内存效率低；太大，并发性降低。

固定分配：一开始给定每个进程固定大小的驻留集。

动态分配：根据运行过程中的情况动态分配大小。

局部置换：缺页时只能当前进程自己的物理块置换需要的页进来。

全局置换：可以用空闲的物理块，或其他进程的物理块置换。全局置换大小肯定不固定，肯定是动态分配。

调入哪些页？

首次调入时，根据局部性原理，某个页相邻的页也会容易用到。因此一调调一小片。

运行中缺页调入时，只调缺少的页。

从何处调入页面？

抖动/颠簸现象：刚换出去的页面又换进来。主要原因是驻留集太少了，少于要频繁使用的块。

工作集：运行时进程实际访问的页面集合。驻留集不应小于工作集。

文件

有信息的数据集合。

文件包含的信息：文件名、标识符（操作系统要看）、类型、大小、创建修改时间、所有者、安全信息。

文件管理

文件分为无结构的流式文件和有结构的记录式文件。记录式文件由一条条记录组成。

文件存放在根目录里的目录里。

操作系统应该向上提供给用户的功能：CRUD，打开和关闭文件。

文件存放在外存类似进程在内存中，是分块存放的（救命啊，我刚把那块学过去）。

初次子海外，操作系统还应该提供文件共享和保护功能。

文件的逻辑结构

无结构文件（如txt）很简单。

有结构文件一般有关键字区分各个记录；记录存储长度不同又分为定长和可变长。

有结构文件逻辑结构：

1. 顺序/链式存储。顺序定长存储可以实现随机存取，想找第i位直接起始位置+i*单位长度即可。顺序可变长无法计算，链式存储不连续也无法实现随机存取。顺序定长存储如果物理上也采用顺序存储，则可实现快速检索。

2. 索引文件。对于可变长记录文件，可以建立一个定长的索引表，包含索引号、长度、起始位置指针的信息。检索速度很高。但是索引表和记录数一样，占的空间不小。

3. 索引顺序文件，一条索引代表一组记录。可能查找速度还是很慢，那就建立多级索引。

   类似数据结构中学到的中间表，如果索引中只存储必要的少部分信息（文件名，指针），索引占的小，能放更多的索引，用更少的磁盘块存储，就平均需要访问更少的磁盘块就能找到文件。

​ 外存中的索引节点叫磁盘索引节点，内存中的叫索引节点，可能包含更多信息，如文件是否被修改、同时有几个进程在访问等。

文件目录

文件控制块 FCB 中存储文件名、类型（是否是目录）、权限、地址等信息。

目录支持的功能有：搜索、创建、删除、显示、修改文件。

早期操作系统只支持单文件目录，那就不能重名了。

早期多用户操作系统支持双文件目录，一个主文件目录，其中包含多个用户目录。不同用户目录各自文件可以重名。但是用户自己没办法创建多级目录。

后来的多级目录结构支持多级目录了。

引入当前目录概念：如果没有此概念，我们要找根目录下 /目录1/目录2/照片.jpg，需要三次访存。根目录找目录1，目录1找目录2，目录2找jpg。要是有当前目录的相对路径就会方便得多。

树形目录结构缺点在于不能共享文件。

无环图目录结构

不同用户不同目录下可以访问到相同的共享文件。

共享文件要设置共享计数器。当有用户取消共享后，要删除共享信息，共享计数器–。减为0时删除共享节点。

文件的物理结构

很多操作系统中，磁盘块和内存块、页大小相同，成块成块拿进来。

类似内存，文件存储的逻辑地址分为逻辑块号和块内地址两部分。

连续分配

自不必多说~物理块号=起始块号+逻辑块号。支持顺序访问和随机访问。但是不方便拓展，比如1~3块的A文件想扩展，但是4~6是B文件，不是空闲文件，A文件想拓展只能整体挪到空闲区域；而且还可能产生大量磁盘碎片。

链接分配

隐式链接：FCB存储起始块号和结束块号。像链表一样从第一个找到结尾（每个磁盘块中包含指向下一个盘块的指针，但是这对用户来说是透明的），没法随机存取，但是拓展方便。

显示链接：FCB 中包含起始块号，此外还有一张文件分配表 FAT，其中包含所有块号的下一块指针。隐式链接想找一个块，要先在 FCB 中找到起始位置，再读磁盘，找磁盘里的下一块。显示连接可以先不用读磁盘，根据分配表推测出要找的逻辑块的物理地址再去读磁盘，访问速度更快。

链接分配都不会有外部碎片。

索引分配

每个文件建立一个索引表。索引表存放的磁盘块叫索引块，文件数据存放的磁盘块叫数据块。FAT是一个磁盘对应一张，索引表是一个文件对应一张。

也支持随机存取，也方便拓展，但是索引表占空间。

要是文件太大，索引表一个索引块存不下，需要多个。

可以让索引块之间链接起来。但是不支持顺序存储，要找最后一块就要从头便历。

可以建立多级索引。每级大小不超过一个数据块。k级表访问数据，要访问k+1次磁盘块（k次查找位置，1次查找数据）。

混合索引：

小文件层级小一点。因小文件访问可能频繁一些，就少访问几次。

文件存储空间管理

操作系统的盘有什么用？又叫文件卷，每个文件卷都包含目录区和文件区。

空闲表法

分配磁盘块给用户：类似动态分区分配，可采用首次适应、最佳适应、最坏适应等。

回收磁盘块：也类似动态分区分配，考虑前后有无空闲块。

空闲链表法

空闲盘块链分配：空闲链从链头摘下来k个空闲块，并修改链头位置。

空闲盘块链回收：回收的空闲块挂到空闲链结尾，并修改链尾位置。

空闲盘区链分配：先按算法找到合适的空闲盘区。如果没有合适的，也可以把不同盘区的盘块同时给一个文件。

空闲盘区链回收：如果和空闲盘区挨着，直接合并。否则变成一个单独的空闲盘区挂到队尾。

位示图法

一定注意从0还是1开始！

分配：扫描位图，找到连续的k个0，修改为1.

回收：算出回收盘块的位图字号、位号，置为0.

成组链接法

大文件不适用空闲块法。

超级块存放在内存中，其中包含下一组空闲块块数和块号。

如果没有下一级了，下一组空闲盘块数可以用特殊标识符如-1表示。

空闲分配：如果<100个，从超级块分配就够。

如果=100个，不能直接分配超级块因为这样超级块对后面的链接就消失了。要先把300的内容提到超级块作为新的超级块，再分配。

回收：直接加到超级块上。如果超级块最大大小为100，已经满了，还要回收，就要让新回收的块作为新的超级块，并指向原来的超级块。

文件基本操作

文件创建

需要关注：文件名；文件路径；需要的外存空间。

1. 在外存中找到合适大小的内存空间；
2. 在目录表中更新新文件的信息。

文件删除

1. 根据目录表找到该目录项；
2. 外存中回收内存；
3. 目录表中删除该文件信息。

打开文件

需要用户提供的信息：文件名；文件目录；打开方式（读；写；……）

操作系统先去目录表找到对应的文件，复制到内存中。并且把目录项复制到内存系统的“打开文件表”中。

关闭文件

删除用户打开文件表的对应项；回收空间；系统打开文件表的打开计数器-1，减到0则删除打开文件表的对应项。

读文件

指明要读的文件，要读入多少数据，读入的数据在内存中的位置。读入指定大小放入内存中。

写文件

和read很像。最后再通过write系统调用写回外存。

文件共享

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

count说明还有几个进程在共享该文件。

要删除时，count–，若>0则不能删除，=0才能删除。

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

删掉文件1，软链接仍然存在，只是无法通过软链接去访问文件1了。

因为访问共享文件要查询多级目录，进行多次 IO，因此采用软链接。

文件保护

口令保护：规定一个口令，用户要说对应口令才能访问。但是口令保存在系统内部，不安全。

加密保护：用密码对文件加密。如异或加密。有点费时。

访问控制：文件的 FCB 中增加一个访问控制列表 ACL，记录用户可以有哪些权限（读写运行ls）。以组为单位，如：管理员，文件主，文件主的伙伴，陌生人。

文件系统的层次结构

磁盘

磁盘调度算法

先来先服务算法 FCFS：就是单纯的先处理先来的进程。

最短寻找时间优先 SSTF：先找离当前磁道近的。

扫描算法 SCAN：只有磁道移到最外侧之后才允许往回移动，避免 SSTF 的左右横跳。

LOOK 调度算法：改进 SCAN 算法，观察到当前磁道已经是访问请求最右边的磁道后，就可以立即改变磁道移动方向往回。

循环扫描算法 C-SCAN：

C-LOOK 算法：

减少延迟时间

磁盘一直旋转的。如果要读几个相邻的扇区，读了第一个处理的过程中磁盘还在转，处理好了的时候可能又转到不知道哪里去了。可能就会产生很长的延迟时间。

解决办法：交替编号。逻辑上相邻的扇区物理上分开。

为什么磁盘的物理地址是（柱面号，盘面号，扇区号）而不是（盘面号，柱面号，扇区号）？因为更改柱面号需要移动磁头臂，更改盘面号不用移动臂，只需要激活相邻盘面的磁头即可。可以减少磁头移动消耗的时间。

磁盘管理

初始化：

​ 物理格式化：把磁盘划分为扇区。扇区包含头、尾、中间数据部分。头尾会存放一些扇区校验码之类的信息。

​ 磁盘分区：分为几个文件卷。

​ 逻辑格式化：创建文件系统（根目录、管理空间的数据结构如位示图、空闲分区表等）。

​ 磁盘的初始化程序：放在哪里？

​ ROM 只读存储器中的数据出厂时就写好了且不能更改，集成在主板上。但是磁盘的初始化程序说不定以后会更新换代，ROM 中的内容又不能更新，因此初始化程序不放在 ROM 中，而是放在磁盘（C）里。初始化程序的装入程序写在 ROM 中。

坏块的管理：坏掉的扇区。简单的磁盘直接在 FAT 中标记出来防止被使用到（对操作系统不透明）。复杂的磁盘交给磁盘控制器维护坏块链表，而且保留一些备用分区（对操作系统透明）。

I/O 设备

I/O 设备分类

按使用特性分类

人机交互类外设：如鼠标打印机键盘等。数据传输慢。

存储设备：移动硬盘、光盘等，数据传输速率快。

网络通信设备：调制解调器等用于网络通信，速度中等。

按速率分类

低速设备：鼠标键盘。

中速：激光打印机。

高速：移动硬盘等。

按信息交换的单位分类

块为单位：磁盘。

字符为单位：鼠标键盘等。

I/O 控制器

IO设备包括：

• 机械部件：用于执行具体 IO 操作的，如鼠标按钮、显示器屏、磁盘盘面。

• 电子部件：插入主板扩充槽的印刷电路板。

CPU 要通过 IO 控制器作为中介才能控制机械部件。

一个 IO 控制器可能控制多个设备；而且可能有多个寄存器。有的操作系统让这些寄存器存到内存里，叫做内存映像 IO；有的采用专门的地址，即寄存器独立编址。独立编址不在内存里，因此还要设置专门的指令来实现对其的操作，还要指明具体对哪个控制器操作。

IO 控制方式

关注：一次读写操作的流程；CPU 干预的频率；数据传送单位；数据流向；优缺点。

程序直接控制

读：

重点在轮询。CPU要不断轮询。

数据传送单位：每次一个字。

数据流向：内存和 IO 设备经由 CPU 读写。每个字读写都需要 CPU 帮助。

简单，但是 CPU 和 IO 只能串行工作，CPU 一直轮询检查效率也很低。

中断驱动方式

CPU 发出读写命令后，等待 IO 的进程暂时阻塞，先运行其他程序。IO 完成后控制器会向 CPU 发一个中断信号，CPU 收到后继续执行。

CPU 执行完每个指令的周期末尾检查中断。中断处理过程需要保存、恢复进程的运行环境，也需要一定时间开销。

CPU 只有 IO 开始时干预一下，等待 IO 过程中就运行其他进程了。

数据传送单位：每次一个字。

数据流向：内存和 IO 设备经由 CPU 读写。每个字读写都需要 CPU 帮助。

相比程序直接控制，CPU 利用率高一点了。但是一个字一个字的传，速度还是慢。

DMA 方式

数据传输单位是块；设备和内存之间数据传输不用每次都经过 CPU ，只有开始传输或结束时才需要干预。

缺点：CPU 每发一条 IO 指令，只能读写几次连续的数据块。离散的数据块就要多次中断。

通道控制方式

通道相当于简化版的 CPU。CPU向通道发出指令，指明通道程序在内存中的位置，并指明要操作的是哪个 IO 设备，然后 CPU 就去运行其他程序了。

通道能执行的指令很单一，而且放在内存中。

CPU 干预次数极少，效率也高，就是需要专门的通道程序支持。

I/O 软件层次

设备独立性软件：向上提供接口（入库函数）。校验用户是否有权限使用当前设备。差错处理。分配和回收设备。管理数据缓冲区。建立逻辑设备名到物理设备名的映射，并根据实际的物理设备选择合适的驱动程序。

可以只设立一个系统 LUT，但是所有用户的逻辑设备名不能重复；也可以给每个用户设计一个。

为什么不同设备驱动程序也不同？因为不同设备内部结构也不一样。比如不同打印机内部寄存器数量可能不一样。驱动程序一般作为单独的进程。

设备驱动程序：主要负责具体控制硬件设备。

中断处理程序：IO 顺利完成后，进行中断处理。并从设备读入一个字长的数据。

I/O 核心子系统

假脱机技术

脱机技术是什么？我们记得最早期的计算机是人手动打孔纸带放入计算机中的，因为人打孔太慢，CPU 运行再快也得等着。

批处理几段引入了脱机输入，先通过外围控制机把数据输入到更快速的磁带上再让主机读入。脱机指的是脱离主机控制的 IO 操作。

不仅 IO 快了，而且 CPU 忙的时候用户也可以先处理数据到磁带上。

假脱机技术 SPOOLing 用软件模拟脱机技术。

输入输出进程模拟外围控制机。

借助 SPOOLing 技术，可以让打印机实现共享。收到用户的打印请求时，在输出井里申请空闲缓冲区（在磁盘上），并放入要打印的数据；且给用户进程申请一张空白的打印请求表，里面存储打印的相关信息，并把该表挂到假脱机文件队列上。打印机空闲时从队列中取出打印请求表，根据表取出打印的数据到输出缓冲区，再到打印机打印。

设备的分配和回收

分配设备要考虑：设备属性（独占？共享？虚拟？虚拟就是假脱机技术等独占改成共享）。设备分配算法（FCFS 优先级高的优先 短任务优先）。安全性。

分配分为静态分配和动态分配。

设备分配管理中的数据结构

设备控制表 DCT

控制器控制表 COCT

通道控制表 CHCT

系统设备表 SDT

设备分配步骤

1. 根据进程的物理设备名，去 SDT 找设备。
2. 根据 SDT 找 DCT，空闲就直接把设备分给这个进程，忙碌就把这个进程的 PCB 挂到设备等待队列中。
3. 根据 DCT 找到 COCT，空闲就分配，不空闲就等待。
4. 根据 COCT 找到 CHCT，空闲就分配，不空闲就等待。

以上方法缺点在于用户要知道物理设备名，不透明；而且只指定这一个设备，如果该设备坏了或者堵塞哪怕其他设备能用也无法切换。

可以建立逻辑设备，用逻辑设备找物理设备。

SDT 中设备类型就是逻辑设备名。

通过逻辑设备表 LUT 建立逻辑设备名和物理设备名之间的映射关系。

缓冲区

缓冲区是一个存储区域，可以用专门的硬件寄存器，也可以用内存做。速度快，成本高，容量小，比如快表。本节中介绍的主要是内存缓冲区。

可以缓冲 CPU 和 IO 之间速度不匹配的矛盾，进而 CPU 中断次数也会减少；解决数据颗粒度不匹配的问题；提高 CPU 与 IO 的并行性。

单缓冲区

某用户进程请求设备读入若干个块的数据。。如果采用单缓冲策略，主存中会被分配一个缓冲区（一般是一个块大小）。缓冲区中只有空的时候才能冲入数据，只有非空的时候才能传出数据。

双缓冲区

一满一空，可以空的边读，满的边往工作区写。

用时=Max(C+M, T)

如果两台机器各配置2个缓冲区，就能同时收发了。

循环缓冲区

多个大小相同的缓冲区链接成一个循环队列。

缓冲池

放满了各种各样缓冲区的池子。

输入：取出一个空缓冲区挂到收容输入队列中，输入放到收容输入队列中，装好了挂到输入队列中。

提取输入：从输入队列取下来，放到提取输入队列中提取到用户进程，再挂回空缓冲区。