操作系统

第一章

1.1 操作系统的基本概念

1.1.1 操作系统的概念、功能

操作系统的概念（定义）

操作系统的功能和目标——作为系统资源的管理者

操作系统的功能和目标——向上层提供方便易用的服务

• 相当于把一系列的命令罗列在了该清单里面，当我们执行这个bat文件的时候，操作系统根据文件当中的这些命令一条一条往后执行

• 狭义的用户接口不包括GUI

操作系统的功能和目标——作为最接近硬件的层次

1.1.2 操作系统的特征

并发

共享

并发和共享的关系

虚拟

异步

1.2 操作系统发展历程

手工操作阶段

批处理阶段——单道批处理系统

批处理阶段——多道批处理系统

分时操作系统

其他集中操作系统

1.3 操作系统的运行环境

1.3.1 操作系统的运行机制

• 本节的指令指的是二进制机器指令

预备知识：程序是如何运行的

内核程序vs应用程序

特权指令vs非特权指令

内核态vs用户态

内核态、用户态的切换

• CPU从用户态变为内核态以后，他会停止运行当前正在运行的应用程序，转而运行一个内核程序

1.3.2 中断和异常

中断的作用

中断的类型

内中断的例子

• 与当前执行的指令有关，中断信号来源于CPU内部

• 陷入指令不是特权指令

外中断的例子

中断机制的基本原理

1.3.3 系统调用

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

系统调用与库函数的区别

什么功能要用到系统调用

系统调用的过程

1.4 操作系统结构

操作系统的内核

• 有的操作系统并不把这些管理功能放在内核当中，而只在内核当中保留与硬件接触最紧密的这些部分
  • 采用微内核结构的情况下，树与内核的功能是要运行在内核态的，不属于内核的管理功能在用户态运行

操作系统的体系结构

• 采用微内核的体系结构，应用程序向操作系统提出服务的请求，接下来操作系统的这几个模块都需要为应用程序服务
  • 而进程管理这个模块在处理应用程序的请求的时候，同样需要得到内核的支持，所以这个模块对内核的访问就涉及到了CPU从用户态转到内核态
  • 服务完成了之后，又会从内核态再转回用户态
  • 同样的，其他管理模块在完成相应的工作的时候，同样也需要得到内核的支持，因此每一个模块都需要请求内核的服务
  • 每一次请求内核的服务，都会涉及到一个cpu状态转换的过程

操作系统结构——分层结构

• 每一层只能向下调用相邻那一层的结构

操作系统结构——模块化

• 主模块就是必不可少的，最重要最核心的模块，没有这些模块，操作系统就无法运行

操作系统结构——宏内核、微内核

• 所有系统功能都放在内核里面

操作系统结构——外核

• 应用程序可以通过系统提供的这些库函数，直接调用普通内核的一些功能
  • 也可以通过库函数去调用外核所提供的一些功能

1.5 操作系统引导

安装操作系统后

• 分区表里面记录了每一个盘每个分区分别占多大的空间，以及每个分区的地址范围

开机过程

• BIOS是基本输入输出系统
• 自举程序（boot程序）
• RAM里面的数据只要关机断电就会清空，但是ROM里面的数据不会因为断电清空
• 执行ROM引导程序的作用就是，指示CPU去把磁盘的主引导记录读入内存
  • 读入主存后，CPU执行磁盘主引导程序，磁盘引导程序会根据分区表去判断C盘的位置，接下来就可以读入C盘的第一部分即引导记录PBR的数据
    • 然后CPU去执行这个引导记录PBR里的程序
    • PBR里的程序的主要作用是会负责找到启动管理器
    • 启动管理器程序通常存放在根目录下面的某个位置
    • 从根目录找到这个启动管理程序，然后CPU再执行这个启动管理程序
    • 接下来这个启动管理程序就会完成操作系统初始化的一系列的工作

1.6 虚拟机

传统计算机

• 两个进程在同一个操作系统上，可能存在一些安全隐患
  • 二者之间可能相互影响，也会相互地争夺操作系统管理的这些资源

虚拟机

• 虚拟机管理程序（VMM）
• 第一类的虚拟机管理程序，会直接运行在硬件之上，由虚拟机管理程序，会把一个物理机器虚拟化为多台虚拟机器，会把一个总的硬件资源划分为多个部分分别给各个虚拟机使用，每一台虚拟机上面，可以安装各自的操作系统，在每个操作系统之上，又可以运行各自的用户进程
• 只有虚拟机管理程序是运行在内核态的，只有它可以使用特权最高的那些指令，而上层的操作系统和应用程序，实际上是运行在用户态的
  • 因此当上层的操作系统想要使用特权指令的时候，这个行为动作会被虚拟机管理程序给截获，这个虚拟机管理程序会把上层的操作系统想要执行的这个特权指令进行等价转换，模拟出指令执行成功的效果
• 第二类的虚拟机管理程序，并不是直接运行在硬件之上，而是运行在宿主操作系统上面，这个虚拟机管理程序想要给各个虚拟机器分配硬件资源，只能请求操作系统分配，再由虚拟机管理程序进行再分配，硬件资源的管理者依旧是宿主操作系统

常用的虚拟机软件

两类虚拟机管理程序的对比

支持虚拟化的CPU通常分更多指令等级

第二章 进程与线程

2.1 进程与线程

2.1.1 进程的概念、组成、特征

• 在引入了线程之后，进程就不再是接受调度的基本单位了，但是进程依然是获得资源的基本单位

进程的概念

进程的组成——PCB

进程的组成——程序段、数据段

程序是如何运行的

进程的特征

2.1.2 进程的状态与转换、进程的组织

进程的状态——创建态、就绪态

进程的状态——运行态

进程的状态——阻塞态

进程的状态——终止态

进程状态的转换

进程的组织——链接方式

进程的组织——索引方式

进程的组织

2.1.3 进程控制

什么是进程控制

如何实现进程控制

如何实现原语的原子性

• 关中断指令和开中断指令是特权指令，只能让内核程序使用，不能让普通的用户程序使用

进程控制相关的原语

• 作业：此时还放在外存里面的，还没有投入运行的程序
  • 作业调度：从外存当中挑选一个程序，把它放入内存让其开始运行

2.1.4 进程通信

什么是进程间通信

为什么进程通信需要操作系统支持

共享存储

• 数据结构的共享灵活性差、速度慢
• 基于存储区的共享灵活性高、速度快

消息传递

直接通信方式

间接通信方式

管道通信

• 管道通信下数据流动只能是单向的
• 管道通信的情况下数据具有先进先出（FIFO）的特性
• 和共享存储的区别
  • 在共享存储方式中数据的读写很自由，没有限制
  • 管道通信下，数据读写遵从先进先出的特性
    • 固定大小的内存缓冲区本质上是循环队列

• 半双工通信指的是同一时刻只能支持单向的传输，全双工通信是指同一时刻支持双向的传输
• 写进程往管道写数据，即便管道没被写满，只要管道没空，读进程就可以从管道读数据
• 读进程从管道读数据，即便管道没被读空，只要管道没满，写进程就可以往管道写数据

2.1.5 线程的概念

什么是线程，为什么要引入线程

• 在传统的进程机制当中，CPU会轮流地为各个进程进行服务，那么这些进程就可以并发地执行，并且每一个进程会有他自己相应的一系列程序代码，被CPU服务的时候，这些代码就可以一句一句开始往下执行
• 为了满足一个进程当中宏观上同时做很多事情，引入了线程机制，用来增加系统的并发度
  • 引入了线程之后，CPU的调度服务对象就不再是进程，而是进程当中的线程，每一个进程当中可能会包含多个线程，CPU会被轮流地，用一定算法轮流地为这些线程进行服务

线程带来的变化

线程的属性

2.1.6 线程的实现方式和多线程模型

线程的实现方式

用户级线程

• 用户级线程的情况下
  • 线程的管理工作由应用程序通过线程库来完成的，并不是操作系统负责的
  • 线程切换的管理是由线程库即应用程序自己完成的，在用户态下就可以完成线程的切换工作，并不需要操作系统的干涉
  • 操作系统只能看到进程的村早，不能意识到用户级线程的存在

• 用户级线程下CPU的调度单位依然是进程

内核级线程

• 内核级线程的管理工作由操作系统完成
• 线程切换需要操作系统介入，由用户态变为内核态
• 操作系统可以意识到内核级线程的存在

• 在多核CPU的环境下，这几个线程可以分别分派到不同的核心下并行地执行，不同的内核级线程可以跑不同的代码逻辑

多线程模型

• 一对一模型

• 多对一模型

• 多对多模型

• 引入内核级线程之后，一个进程可能会对应多个内核级线程，而只有所有的这些内核级线程都被阻塞的时候，我们才说这个进程进入了阻塞状态

2.1.7 线程的状态与转换

线程的状态与转换

线程的组织与控制

2.2 CPU调度

2.2.1 调度的概念、层次

调度的基本概念

调度的三个层次——高级调度

调度的三个层次——低级调度

调度的三个层次——中级调度

进程的挂起态与七状态模型

• 一个处于就绪态的进程，如果此时系统的负载比较高，内存空间已经不够用，就可能把一个处于就绪态的进程暂时调到外存当中，然后该进程就进入了一个就绪挂起的状态。
  • 一直到内存空间空闲或者这个进程又需要继续执行，那么这个进程又会被激活，把它的数据又挪回到内存当中。这样一个就绪挂起的进程又回到了就绪态
• 一个阻塞态的进程也可以被挂起，相应的也可以再重新被调入内存，进行激活，重新回到阻塞态
• 有的操作系统有可能会使一个处于阻塞挂起的进程，当他等待的阻塞事件发生的时候，这个进程就会直接进入到一个就绪挂起的状态，然后之后当他再被重新调回内存的时候，是直接回到就绪态而非阻塞态
• 有的死后一个进程处于运行态，运行结束后，可能这个进程下处理机的时候，可能就会被直接放到外存当中，让他进入就绪挂起的状态
• 有的时候一个处于创建态的进程，当他创建结束之后，创建完PCB之后，有可能出现内存空间不够的情况，这种情况下有可能处于创建态的进程之后会先进入到一个就绪挂起的状态

三层调度的联系、对比

• 高级调度是面向作业的调度
  • 一个作业在刚开始会被调入一次被调出一次，并且作业调入的时候，会为这个作业建立相应的PCB，也就是建立它相应的进程
• 中级、低级调度是面向进程的调度
  • 中级调度是把暂时不会运行的进程相关的一些数据调到外存里

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

进程调度的时机

• 各个进程只能互斥地进入临界区，互斥地执行访问临界资源的代码

进程调度的方式

进程的切换与过程

2.2.3 调度器与闲逛进程

调度器/调度程序

闲逛进程

2.2.4 调度算法的评价指标

CPU利用率

系统吞吐量

周转时间

• 带权周转时间表示的是这个进程的整个周转时间比运行时间大多少倍

等待时间

• 平均等待时间就是把所有进程或者作业的等待时间做一个加和再除以作业的数量

响应时间

2.2.5 调度算法

先来先服务

• 后备队列在外存当中

短作业优先

非抢占式的短作业优先算法

抢占式的短作业优先算法

• 采用了抢占式的短作业优先之后得到的平均周转、平均带权周转、平均等待时间这三个指标比非抢占式的还要更小

对FCFS和SJF两种算法的思考

高响应比优先

时间片轮转

优先级调度算法

多级反馈队列调度算法

多级队列调度算法

2.3 同步与互斥

2.3.1 进程同步、进程互斥

• 进程同步又可以称之为进程之间的直接制约关系，进程之间是有直接的合作的
• 进程互斥又可以称作为进程之间的间接制约关系，因为进程之间并没有直接的合作关系，他们之间只是因为想要互斥地使用某一种系统临界资源，所以才会产生这种制约关系

什么是进程同步

什么是进程互斥

2.3.2 进程互斥的软件实现方法

• 单标志法的精髓在于用一个turn的变量来表示谦让这个动作
• 双标志法的精髓在于用一个flag数组来表示自己想要进入临界区的一个意愿
• peterson算法结合了双标志法和单标志法思想的精髓，每个进程在进入区当中都会先主动地争取和表达自己想要进入临界区的意愿，同时又主动地做出谦让的动作

如果没有注意进程互斥

单标志法

双标志先检查法

双标志后检查法

peterson算法

• 让权等待指的是，当进程进不了临界区，就应该立即释放处理机资源，而不应该继续在CPU上跑

2.3.3 进程互斥的硬件实现方法

中断屏蔽方法

• 关中断指令只对执行关中断指令的那个处理机有用，因此有可能发生两个处理机上的两个进程同时对临界区进行访问的情况

test and set指令

• 在TSL循环中，如果lock本来就是true，即临界区本来就是被上锁的，那么他返回来的old的这个值也会为true，while这个循环就会一直循环下去
  • 一直到lock这个值被当前访问临界区的那个进程在退出区改成了false，那么testandset返回来的old值变为了false
  • 于是之前一直被卡在while循环的进程就可以跳出这个循环，然后正式地开始访问临界区的代码段，一直到访问结束之后再把自己上的锁给解除

swap指令

• old记录原来的lock值，swap交换之后，以前的lock的值会放在old里面，old本来是true，true这个值又会被设置到lock里面
  • 之后while循环会检查以前的lock值是否为true，如果old值为true（即原lock为true），说明在之前这个临界区就已经被上锁了，那么这个循环会一直循环下去，一直到old为false，说明之前这个临界区是没有被上锁的状态，那么就会跳出这个循环，顺利地进入临界区访问这些代码段

2.3.4 互斥锁

进程互斥：锁

• 锁相当于一个bool型变量，当变量为true，说明已经上锁，变量为false，说明没有上锁

• 缺点：锁都有忙等的问题，违反让权等待原则，一直占用cpu资源
  • 一个进程在忙等，暂时进不了临界区，并不会一直占用处理机，如果这个进程的时间片用完，调度程序依旧会让他下处理机

• 多核处理器系统中一个核的运算能力可能会被吃掉在忙等，但其他核可以照常工作，并且快速释放临界区
• 单处理机系统下，进程吃掉了唯一的核，只有他的时间片用完并且上锁的那个进程上处理机解锁之后，才有可能获得这个锁

2.3.5 信号量机制

信号量机制

整型信号量

记录型信号量

• 如果value–之后value的值小于0，说明在这之前已经没有空闲资源分配给申请的进程
• 如果value++之后value的值小于等于0，说明在这个进程释放这个资源之前，依然还有一些进程是处于等待队列的

2.3.6 用信号量实现进程互斥、同步、前驱关系

• 每年至少1个大题

信号量机制实现进程互斥

• 系统中的某些资源是比须互斥访问的，而访问这种系统资源的那段代码叫做临界区

• 如果题目没有特别说明的话，我们对一个信号量的定义，只需要写semaphore mutex=多少即可，并不需要写出这个信号量的数据结构
• 只要用semaphore这个关键字来开头的话，就意味着这个信号量不是整型信号量，而是记录型信号量，也就是说这个信号量是带有排队阻塞功能的，并不会忙等

信号量机制实现进程同步

信号量机制实现前驱关系

2.3.7 生产者-消费者问题

问题描述

• 当一个消费者从缓冲区取走数据之后，如果此时有生产者是处于阻塞状态的，那么消费者进程应该把生产者进程给唤醒，让他重新回到就绪态

问题分析

• 消费者消费同步关系中，P操作实际上是在申请一个产品，同步信号量对应的资源应该是产品的数量，也就是非空缓冲区的数量

如何实现

• 生产者进程在把产品放入缓冲区之前，需要申请一个空闲的缓冲区，因此当它放入产品之前，需要对empty这个同步信号量执行一个p操作
• P是消耗，V是增加

思考：能否改变相邻P、V操作的顺序

• 逻辑上看使用和生产产品的指令可以放在PV操作中间，但这样做会导致临界区代码更长，即一个进程对临界区上锁的时间变得更长，不利于各个进程交替地使用临界区资源

2.3.8 多生产者-多消费者问题

问题描述

• 多消费者的多不是指数量而是指类别
• 一说P是测试，V是增加

问题分析

如何实现

2.3.9 吸烟者问题

问题描述

问题分析

如何实现

2.3.10 读者写者问题

• 第一个读者进程会对共享资源上锁，而当最后一个读者读完文件之后，会对共享文件进行一个解锁

问题描述

问题分析

如何实现

2.3.11 哲学家进餐问题

问题描述

问题分析

如何实现

2.3.12 管程

为什么要引入管程

管程的定义和基本特征

• 管程当中定义的这些共享的数据结构，只能被管程当中定义的这一些函数所修改

拓展1：用管程解决生产者消费者问题

拓展2：JAVA中类似于管程的机制

2.4 死锁

2.4.1 死锁的概念

什么是死锁

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

• 死锁和饥饿肯定不会是运行态

死锁产生的必要条件

什么时候会发生死锁

死锁的处理策略

2.4.2 死锁的处理策略——预防死锁

破坏互斥条件

破坏不剥夺条件

破坏请求和保持条件

破坏循环等待条件

2.4.3 死锁的处理策略——避免死锁

什么是安全序列

安全序列、不安全状态、死锁的联系

• 进入不安全状态未必发生死锁，但如果发生了死锁，一定是处于不安全状态

银行家算法

实际做题手算的快速方法

• 找得到安全序列的情况

• 找不到安全序列的情况

用代码实现银行家算法

2.4.4 死锁的处理策略——检测和解除

死锁的检测

• 结束了归还资源相当于把边拆了

检测死锁的算法

• 不阻塞是说这个进程申请的这些资源的数量足够满足它的需求
  • 图中p1是不阻塞进程，p2是阻塞进程
• 不是孤点指的是与这个进程至少有一个边相连

死锁的解除

• 优先级低的优先牺牲
  • 执行时间越长，说明让其回退或者撤销的代价越高，所以一般选择执行时间较短的进程进行牺牲
  • 优先让马上结束的进程优先获得资源
  • 优先把拥有更多资源的进程牺牲
  • 优先牺牲批处理式的进程

第三章 内存管理

3.1 内存管理概念

3.1.1 内存的基础知识

内存的定义和作用

指令的工作原理

装入的三种方式

绝对装入

静态重定位（可重定位装入）

动态重定位（动态运行时装入）

从写程序到程序运行

链接的三种方式

静态链接

装入时动态链接

运行时动态链接

3.1.2 内存管理的概念

内存空间的分配与回收

内存空间的扩展

地址转换

• 绝对装入由编译器而非操作系统完成

内存保护

3.1.3 覆盖与交换

• 一般来说只会在选择题中考察

覆盖技术

交换技术

3.1.4 连续分配管理方式

单一连续分配

• 并不支持多道程序并发运行

固定分区分配

动态分区分配（可变分区分配）

3.1.5 动态分区分配算法

• 很可能作为选择题考察，甚至会作为大题进行考察

首次适应算法

最佳适应算法

最坏适应算法

邻近适应算法

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

什么是分页存储

重要的数据结构——页表

• 页面是虚拟的逻辑空间，而页框是内存块的区域

每个页表占多少字节

• 先计算内存块会被分为几个页框
  • 页框大小=页面大小
  • 页框数量=物理内存大小空间/页框大小

如何实现地址的转换

• 页号=逻辑地址/页面长度（取除法的整数部分）
• 页内偏移量=逻辑地址%页面长度（取除法的余数部分）

逻辑地址结构

3.1.7 基本地址变换机构

• 既有可能作为选择题也有可能作为大题进行考察

基本地址变换机构

• 逻辑地址转换为物理地址的几个要素
  • 知道逻辑地址对应的页号
  • 知道逻辑地址对应的页内偏移量
  • 知道逻辑地址对应的页面在内存当中存放的位置
  • 根据页面在内存当中的起始位置和页内偏移量得到最终的物理地址

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

3.1.8 具有快表的地址变换机构

什么是快表

• 快表是专门的硬件，当进程切换的时候，快表的内容也需要被清除

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

局部性原理

3.1.9 两级页表

单级页表存在的问题

如何解决单级页表的问题

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

• 这里的二级页表相当于页表的逻辑地址

需要注意的几个细节

3.1.10 基本分段存储管理方式

分段

• 用户编程的时候使用的是段名，在cpu具体执行的时候，使用的是段号这个参数

段表

地址变换

!

分段、分页管理的对比

3.1.11 段页式管理方式

分页、分段的优缺点分析

分段+分页=段页式管理

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

• 段式管理中地址结构是二维的，页式管理中地址结构是一维的

段表、页表

• 一个进程会对应一个段表，但一个进程可能对应多个页表

3.2 虚拟内存管理

3.2.1 虚拟内存的基本概念

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

虚拟内存的定义和特征

如何实现虚拟内存技术

• 这里的请求掉调页和页面置换对应的是分页存储管理方式，如果采用分段式存储管理，则需要请求调段和段置换功能

3.2.2 请求分页管理方式

页表机制

缺页中断机构

地址变换机构

• 红框内是请求分页管理方式和分页管理方式相比增加的部分和内容

3.2.3 页面置换算法

最佳置换算法（OPT）

• 理想化的算法，算式中无法实现

先进先出置换算法（FIFO）

最近最久未使用置换算法（LRU）

时钟置换算法（CLOCK）

改进型的时钟置换算法

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

• 系统为某个进程分配了n个物理块，等价于某个进程的驻留集大小是n
• 一个进程采用固定分配局部置换的策略，该条件即指的是系统为一个进程分配的物理块数是不会改变的
• 一般作为选择题考察，但某些内容可能作为大题的条件

页面分配、置换策略

• 固定分配局部置换的灵活性比较低

何时调入页面

从何处调入页面

抖动（颠簸）现象

工作集

• 对于局部性很好的进程来说，工作集的大小一般是要比窗口尺寸的大小更小的

3.2.5 内存映射文件

内存映射文件（memory-mapped files）

方便程序员访问文件数据

• 先使用open系统调用指明打开一个文件
  • 接下来使用mmap这个系统调用，让操作系统把文件映射到进程的虚拟地址空间当中
  • 这个系统调用会给程序员返回一个指针，这个指针会指向刚才映射的这片区域的起始地址
  • 接下来可以用访问内存的方式去访问这些数据
    • 给一个起始地址指针，可以用指针加偏移量取访问指针后面的某些区域
  • 假定此时要访问的数据刚好是在文件的第二块，此时操作系统发现这一块的数据还没有调入主存，处于缺页异常，此时操作系统会自动地把这一块的数据读入主存
    • 程序员不需要再自己去调用read函数，读入数据的过程是由操作系统自动完成的
  • 调入内存后，程序员可以对数据进行修改
  • 如果进程不再需要该文件，可以使用lclose系统调用来关闭文件
  • 关闭文件后，操作系统会自动地把文件当中被修改的数据写入磁盘
• 操作系统只是建立了文件数据和内存之间的映射关系，但并没有把文件数据直接给读入内存，相当于一个缺页的状态

方便多个进程共享同一个文件

• 两个进程的虚拟地址空间是相互独立的，但是操作系统会把这两块虚拟地址空间映射到相同的物理内存上
  • 操作系统只需要修改这两个进程的页表，让对应的页面映射到相同的一个物理页框上，使两个进程实际上是在共享同一份文件的数据
• 当一个进程修改了文件的数据之后，另一个进程立马可以看到这一块文件数据的改变

传统的文件访问方式

第四章 文件管理

4.1 文件系统基础

4.1.1 初识文件管理

前情回顾

文件的属性

文件内部的数据应该怎样组织起来

文件之间应该怎样组织起来

操作系统应该向上提供哪些功能

文件应该如何存放在外存

• 文件的物理结构讨论的是文件这些数据在物理上应该是怎么存放，怎么组织的一个问题

• 文件的逻辑结构指的是文件的各个记录在逻辑上应该是什么样的一种组织关系的问题

• 其他需要操作系统实现的文件管理功能

4.1.2 文件的逻辑结构

有结构文件

有结构文件的逻辑结构

顺序文件

• 在实际应用当中，为了减少磁盘的IO次数，操作系统会管理一个日志文件，用这个日志文件来记录对这个文件当中的各个记录进行修改的一些信息。然后每隔一段比较长的时间再把这些信息统一地合并到外存当中的文件数据中，这样可以减少顺序存储的顺序文件进行增删改所带来的一些开销了

索引文件

索引顺序文件

• 索引顺序文件的索引表，它其实是一个定长记录的串结构的顺序文件

索引顺序文件（检索效率分析）

多级索引顺序文件

4.1.3 文件目录

文件控制块

目录结构——单级目录结构

• 有很多用户在使用的话，不同的用户的文件名很容易发生重复，因此单级目录结构不适用于多用户操作系统

目录结构——两级目录结构

目录结构——多级目录结构

目录结构——无环图目录结构

索引结构（FCB的改进）

4.1.4 文件的物理结构

• 经常作为选择题考察，偶尔会出大题

文件块、磁盘块

文件分配——连续分配

总结

文件分配方式——连接分配

链接分配——隐式链接

连接分配——显式链接

文件分配方式——索引分配

总结

4.1.5 逻辑结构vs物理结构

例：C语言创建无结构文件

逻辑结构（从用户视角看）

物理结构（从操作系统视角看）

例：C语言创建顺序文件

物理结构（从操作系统视角看）

链式存储的顺序文件采用连接分配

逻辑结构：索引文件

4.1.6 文件存储空间管理

存储空间的划分与初始化

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

• 第一种情况下会在空闲表中新增一个表项
  • 第二种情况下需要把它前后的空闲区还有这个新回收的区域合并成同一个空闲区，因此表项的数量会减少一个
  • 三四情况不会导致表项的改变

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

存储空间管理——位示图法

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

• 最后一个分组的盘块数要比其他的分组的更少一块

分配

• 超级块其实就充当了一个链头的作用，在这个链头当中，永远要保持指向下一个分组的一些信息

回收

4.1.7 文件的基本操作

创建文件

删除文件

打开文件

关闭文件

读文件

写文件

4.1.8 文件共享

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

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

软链接的情况下删除一个文件

• 找不到文件，软链接失效

4.1.9 文件保护

口令保护

加密保护

访问控制

4.3 文件系统

4.3.1 文件系统的层次结构

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

原始磁盘

物理格式化

• 坏扇区的存在对操作系统来说是透明的
  • 磁盘驱动器在物理格式化之后知道操作系统访问的是一个坏扇区，磁盘驱动器就会用一个备用扇区，一个好的扇区来替代坏扇区

逻辑格式化

文件系统在外存中的结构

文件系统在内存中的结构

open系统调用打开文件的背后过程

4.3.3 虚拟文件系统

普通的文件系统

虚拟文件系统

• 任何一个文件系统，只要想在操作系统上被支持使用，必须按照虚拟文件系统所给的要求实现虚拟文件系统规定好的函数

• 每当open一个文件之后，虚拟文件系统就会给这个文件在主存当中新建一个vnode（v结点）

文件系统挂载（mounting）

• 例如插u盘，那么u盘的文件系统就要挂载到电脑的操作系统，或者说虚拟文件系统上上

第五章 输入/输出（I/O）管理

5.1 I/O管理概述

5.1.1 I-O设备的概念和分类

什么是I/O设备

I/O设备的分类

按使用特性

按传输速率分类

按信息交换的单位分类

5.1.2 I-O控制器

I/O设备的机械部件

I/O设备的电子部件（I/O控制器）

I/O控制器的组成

• 地址线指明操作的设备，控制线向I/O控制器发出具体的指令

内存映像I/O vs 寄存器独立编址

5.1.3 I-O控制方式

程序直接控制方式

中断驱动方式

• 每次只读入一个字

DMA方式（直接存储器存取）

DMA控制器

• DMA控制器是一种特殊的IO控制器

• DMA控制器也是一个字一个字地传输，以DR作为媒介

通道控制方式

• 通道程序是一系列通道指令的集合

• 一个通道能够控制多个IO控制器，而一个IO控制器又可以控制多个设备

5.1.4 I-O软件层次结构

用户层软件

• 设备独立性软件层也被称为系统调用处理层

设备独立性软件

为什么不同的设备需要不同的设备驱动程序

设备驱动程序

• 设备独立性软件不可以直接操纵硬件，必须调用厂家提供的设备驱动程序，由这个设备驱动程序来完成对硬件的具体控制

中断处理程序

• 中断处理程序和设备驱动程序都会和硬件打交道，而用户层软件和设备独立性软件不会直接和硬件打交道

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

输入/输出应用程序接口

• 上层的用户应用程序需要通过系统调用的方式来请求使用底层的某一种I/O设备

• ip地址定位到了一台电脑，一台主机，如果再加上一个端口号，那么这个端口号就可以映射到计算机当中的某一个应用程序
• 网卡用于实现网络数据包的收发

• 网络套接字：申请一片内核空间（内核存储空间），这篇空间会用于接收或者发送数据
  • socket系统调用会给用户进程返回一个描述符，相当于指向这个套接字的指针
  • 有了套接字对象之后，要把套接字绑定到本地的某个端口，这样套接字就可以等待着被链接

• p1想给p3发送一个数据包
  • p1首先在自己的用户区准备好这个数据，然后使用write系统调用，指明要往fd所指向的这个套接字中写入数据
  • 设备独立性软件接收到write这个系统调用之后，就会把用户进程准备好的这一块数据复制到内核区（套接字所对应的这一片缓冲区）中
  • 设备独立性软件这一层会调用网络控制器的驱动程序来处理这片数据
  • 这个驱动程序会负责把准备好的数据给它输出到网络设备上
  • 接下来网络控制器就可以把这些数据包发送到网络上了
  • 这些数据被传输到主机2的网络控制器上
  • 这个网络控制器接收到数据包之后，会向主机2发出一个中断信号
  • 主机2的中断处理程序出来工作，发现中断信号来自于网络控制器
  • 因此中断处理程序会调用网络控制器的驱动程序，让驱动程序来把网络控制器里面收到的这些数据，搬到内核的缓冲区里面
  • 接下来p3要接收网络数据包，只需要使用read的系统调用，指明我要从fd所指的这个套接字对象中读出一个数据包
  • 设备独立性软件会从缓冲区里面把数据复制到用户进程的用户区当中
  • 这样用户进程p3就可以使用它收到的这一块数据了

阻塞/非阻塞I/O

• 阻塞：只要设备的输入动作没有完成，就得一直等待下去，进程没有办法继续往下执行
• 非阻塞I/O：即便磁盘正在忙碌，也不需要用户进程等待，因为进程准备的数据是在用户区，而操作系统内核又有内核区
  • 当应用程序发出write系统调用，想要把这一块数据写到磁盘的时候，即便磁盘现在正在忙碌，那设备独立性软件那一层也会迅速响应系统调用请求，先把请求写入的数据复制到内核。
  • 只要数据复制到内核区，接下来内核慢慢地把这个数据写回磁盘即可，用户进程只要完成了这个数据赋值的过程，就可以继续往下执行
  • 因此这种类型的系统调用不需要阻塞等待，可以迅速地返回

设备驱动程序接口

5.2 设备独立性软件

5.2.1 IO核心子系统

这些功能要在哪个层次实现

I/O调度

设备保护

• 在unix系统中，系统会为各个设备建立一个相应的FCB（文件控制块）

5.2.2 假脱机技术

• 假脱机技术实际上是用软件的方式来实现了脱机技术

什么是脱机技术

假脱机技术——输入井和输出井

共享打印机原理分析

5.2.3 设备的分配与回收

设备分配时应考虑的因素

设备的固有属性

设备分配算法

静态分配和动态分配

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

• 一个系统中可能存在多个通道

设备分配的步骤

设备分配步骤的改进

• 只有这个类型的设备全部都处于忙碌状态的时候，才需要把这个进程阻塞

5.2.4 缓冲区管理

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

单缓冲

双缓冲

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

循环缓冲区

缓冲池

• 当一个输入进程要请求输入一块数据的时候，系统会从空缓冲队列的队头当中取下这一块空的缓冲区，把它作为收容输入数据的缓冲区，当它被充满之后就会被挂到输入队列的队尾上

• 当一个进程想要取得一块输入数据，操作系统会从输入队列的队头取下一个缓冲区，把它作为提取输入的工作缓冲区
  • 这块缓冲区的数据会被传送到计算进程的工作区当中
  • 所以这块缓冲区当中的数据就被取空了
  • 取空后会被挂到空缓冲队列的队尾

• 计算进程想要把准备好的数据冲入缓冲区，系统会从空缓冲队列的队头，取下一个空闲的缓冲区，把这个缓冲区作为收容这个进程想要输出数据的工作缓冲区
  • 接下来这个缓冲区会被充满
  • 充满后这块数据会被挂到输出队列的队尾

• 输出进程请求输出数据，系统会从输出队列的队头取下一块缓冲区，把它作为提取输出数据的工作缓冲区
  • 接下来缓冲区中的输出数据会被取走，当缓冲区被取空之后，就可以把这个缓冲区挂回到空缓冲队列的队尾

5.3 磁盘和固态硬盘

5.3.1 磁盘的结构

磁盘、磁道、扇区

如何在磁盘中读/写数据

盘面、柱面

磁盘的物理地址

• 柱面号是用来定位盘面的某一个磁道的
• 盘面号是用来选择到底是哪一个盘面当中的磁道
• 扇区号是用来选择在这个磁道当中到底是哪个扇区
• 柱面号、盘面号、扇区号三者合一可以定位到某一个盘面当中某一个扇区

磁盘的分类

5.3.2 磁盘的调度算法

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

先来先服务算法（FCFS）

最短寻找时间优先（SSTF）

扫描算法（SCAN）

• 扫面算法要求磁头必须移动到最极端的磁道
  • 即使没有更远的需要处理的磁道访问请求，依旧需要把磁头移动到极端磁道

LOOK调度算法

循环扫描算法（C-SCAN）

C-LOOK调度算法

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

前情回顾

• 磁头并不能在读完二号扇区之后立马读取三号扇区

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

磁盘地址结构的设计

减少延迟时间的方法：错位命名

• 空间平面都错位

5.3.4 磁盘的管理

磁盘初始化

引导块

坏块的管理

5.3.5 固态硬盘SSD

固态硬盘的结构

• 闪存翻译层：将逻辑地址翻译成物理地址

• 如果读写的逻辑块是存放在固态硬盘里面的，那么这里所谓的一个逻辑块对应固态硬盘里的一个页而不是一个块

• 固态硬盘里的一个页对应磁盘的一个块/扇区，一个块对应磁盘的一个磁道

固态硬盘的删

• 固态硬盘会把块内的其他数据给复制到另一块对应的位置，然后再把想写入的数据写到对应的位置

• 接着把原来的块擦干净，可以保证块内的其他数据不被丢失

• 由于之前闪存翻译层把某一范围的逻辑块号映射到了刚才被擦除的位置，但是由于目前这些逻辑块号所对应的数据已经被移动，为了让地址的映射关系保持正确，闪存翻译层在做了数据迁移的动作之后，会把逻辑块号重新进行映射，映射到新的位置，原有的映射就被舍弃
• 所以对于固态硬盘来说，逻辑地址所对应的物理地址可能发生改变，只不过闪存翻译层会把映射关系修改正确