操作系统
操作系统
一、OS概念
1.1 操作系统特征
并发：两个或多个事件在同一时间间隔内发生，引入进程的目的是实现并发，通过分时实现。注意并发与并行，并行是同一时刻
1.4 操作系统的运行机制与体系结构
指令：特权指令(内存清零)和非特权指令(普通加法运算)，定义：CPU能识别、执行的最基本的命令
CPU两种状态：通过程序子寄存器(PSW)标志位来判断处于状态
- 用户态(目态) 只能执行非特权指令
- 核心态(管态) 都能执行
程序：内核程序和应用程序
计算机层次结构：
原语是一种特殊的程序，具有原子性、最接近硬件部分
内核是操作系统最底层的软件、是操作系统最基础、最核心的功能。
操作系统体系结构：大内核、微内核
1.5 中断和异常
1.5.1 中断机制的诞生
最初计算机只能串行，后来引入并发且由OS控制中断
CPU收到中断信号，切换为核心态对中断进行处理，由OS内核对信号进行处理
1.5.2 中断概念和作用
CPU 从用户态=>核心态唯一方式： 中断
核心态=>用户态修改标志位
1.5.2 中断分类
1.5.3 外中断处理过程
1.6 系统调用
1.6.1 定义
命令接口：直接给用户使用
程序接口一组系统调用组成：是操作系统提供给应用程序(程序员)使用的接口
1.6.2 为什么要设置系统调用
每个底层操作都只能通过系统调用，最后由OS去管理
分类：
系统调用都是在核心态
1.6.3 系统调用与库函数的区别
一些库函数封装了系统调用
并不是全部库函数都需要系统调用：如取绝对值等。(创建文件调用系统调用)
1.6.4 系统调用过程
将调用参数放入到寄存器中，然后开始陷入指令(int x)，发生中断控制权转到OS，由OS进行处理
Linux 系统调用信号示例
二、进程
2.1 进程概念
2.1.1 定义
程序：一个指令序列。分为程序段和数据段，程序段包含代码。
早期的计算机只支持单道程序，串行执行，后来演化为并行执行，引入进程的概念。
PCB+程序段+数据段构成进程实体，简称进程
严格来说进程是动态的，进程实体的静态的。进程有以下几种定义：
- 进程是程序的一次执行过程。
- 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
- 进程是具有独立功能的程序在数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
或者说进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
单=>多：多道程序设计后，程序的执行就失去了封闭性和顺序性。
2.1.2 PCB包含内容
和进程管理的都放在PCB中
2.1.3 进程的组织
一个系统中通常有很多PCB，为了能有效管理需要组织起来。
链接方式：
索引方式：指针指向一张索引表，而不直接指向一个队列
2.1.4 进程的特征
动态（进程最基本的特称）、并发、独立、异步、结构性
2.2 进程的状态
2.2.1 进程三种基本状态
进程需要被CPU操作，因此分为几种状态：运行、就绪、阻塞态
2.1.2 创建态、终止态
2.1.3 进程状态的转换
注意不能直接从阻塞态转化为运行态
2.3 进程控制
2.3.1 定义
进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。
通过原语(PV操作)实现
注意在转化到运行态时，需要恢复进程运行环境，转为阻塞态时需要保存当前运行环境
2.3.2 原语
用原语实现进程控制，最大特点是中间不允许中断，只能一气呵成，即原子操作。
开关指令显然是核心态下的特权指令
2.3.3 原语作用
创建、撤销、终止、切换原语
阻塞和唤醒原语必须成对使用，两者对应同一事件
2.4 进程通讯
定义：进程之间信息交换、传递
操作系统提供三种方式实现进程通信：共享存储、管道、消息传递
通过共享空间实现交互： 共享空间是互斥的
通过管道通信：管道是半双工（同一时刻是单向），且管道写入必须写满后才能进行读，读完空后再进行写
消息传递：每一个进程有一个消息缓冲队列
2.5 线程概念和多线程模型
2.5.1 线程定义
一个进程可能同时做很多事，而传统的进程只能串行执行，因此引入线程。线程是程序执行流的最小单位，被包含在进程中。可以理解为轻量级进程。
- 是一个基本的cpu执行单位，也是程序执行流最小单位。
- 进程和进程、线程和线程都可并发执行，使得一个进程内也可并发操作
线程属性
2.5.2 线程的实现方式
用户级线程：由应用程序通过线程库实现，所有线程管理都由应用程序负责。只需在用户态下实现。
内核级线程：线程管理由OS控制，在核心态下完成线程切换。
可以二者组合实现线程的实现。
只有内核级线程才是处理机分配的单位，所以最多二核同时执行。
2.5.3 多线程模型
由几个用户级线程映射到几个内核级线程的问题引出“多线程模型”问题
多对一：并发度不高
一对一：并发能力强，可在多核机器并行执行，线程切换需要OS管理，系统开销大
多对多：
2.6 处理机调度
2.6.1 定义
按照一定的算法，选择一个进程并将处理机分配给它运行，以实现并发执行。
2.6.2 调度的三个层次
高级调度： 操作系统管理从后备队列中调入内存，创建相应的PCB
中级调度(内存调度)：
引入挂起状态，PCB在内存中，但数据并不在内存中。
七状态模型:注意挂起和阻塞的区别
低级调度：(进程调度)
速度很快使得宏观上来看是并发的。
调度对比：
2.7 进程调度
2.7.1 时机
不能进行进程调度：
- 处理中断的时候
- 进程在操作系统内核程序临界区中。（注意是内核临界区，操作系统内核临界区可能会影响进程的切换，而普通的临界区并不影响
- 在原子操作中(原语)。原子操作不可中断，需要一气呵成
临界资源:一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源
临界区:访问临界资源的那段代码
内核程序临界区一般是用来访问某种内核数据结构的，如进程的就绪队列。（由各就绪进程的PCB组成）
但普通临界区可以进行进程调度。
2.7.2 进程调度方式
狭义进程调度：指从就绪队列中选取一个进程占用处理机
进程切换：一个进程让出处理及，另一个进程占用处理机
广义进程调度：包含上面两个过程
进程切换：
- 对原来运行进程各种数据的保存
- 对新的进程各种数据的恢复(如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一-般保存在进程控制块)
进程切换是有代价的，过于频繁的切换和调度会使系统效率变低
2.7.3 调度算法评估值
周转时间：
带权周转时间：越小越好
等待时间： 周转时间-运行时间 调度算法一般无法影响CPU和I/O设备的服务时间，仅影响此项。
响应时间
2.7.4 调度算法
FCFS：先到底就绪队列就先开始，适用于非抢占进程。作业调度考虑先到达后备队列、用于进程调度时考虑先到达就绪队列
SJF：短作业优先算法，追求最少的平均周转时间、平均等待时间、最少的平均带权周转时间。有抢占版本(默认非抢占)
可能会导致长作业饥饿(某个作业长时间得不到处理)
HRRN:高响应比优先，
2.8 进程同步、互斥
2.8.1 进程同步
进程有异步性，指的是各并发执行的进程以各自的速度独立推进，无法预知
进程同步解决的是进程异步问题：同步又称为直接制约关系
如这种情况写数据必须在读数据之前
2.8.2 进程互斥
资源共享：互斥共享、同时共享
对于临界资源的访问必须互斥进行
进程互斥需要遵守的原则
2.8.3 进程互斥软件实现
单标志法：
有一个标志位判断当前进程能否进入临界区，每一个进入之前都需要检查标准位，且必须要先PO=>P1，违反了"空闲让进"
双标志先检查法：每个进程独立一个布尔数组以此来判断是否有意愿进入临界区
问题：有可能同时进入临界区
检查和上锁不是一气呵成的，如果按照 1=>5=>2=>6 顺序则可能同时进入，违反"忙则等待"
双标志后检查法：
Peterson算法：
不遵循“让权等待”，进程无法进入临界区，但进程一直卡在循环 while(turn==1 && flag[1]) 这一步中，没有释放处理机
2.8.4 进程互斥的硬件实现
中断屏蔽方法：关中断后不允许中断进程 
TestAndSet(TSL)指令：用硬件实现，执行过程不能被中断
TSL返回 old 值，如果是其他已经上锁在执行检查的时候会一直卡在while，直到解锁后进入TSL指令又重新上锁
用硬件实现和标志法的区别：检查和上锁是原语，中间无法插入其他进程执行。适用多处理机环境。
缺点：不满足 让权等待，即不进入临界区仍占用 cpu 在检查
Swap指令：
应为每个临界资源设置一个共享布尔变量 lock，初值为 false;在每个进程中再设置一个局部布尔变量key，用于与lock交换信息。
在进入临界区前，先利用Swap指令，然后检查key的状态(如果没上锁一步交换就可进入临界区，当有上锁时需要等待解锁，一直循环交换);有进程在临界区时，重复交换和检查过程，直到进程退出。逻辑上看与TSL指令完成任务一直，优缺点相同。
2.9 信息量机制
2.9.1 定义
信息量机制实现进程互斥、同步的方法。信号量就是一个变量，可以表示系统中某种资源的数量
通过原语就能实现进入区和退出区的一气呵成。
一对原语：wait(S) 和 signal(S) 通常简称为 P(S) 和 V(S) S 就是一个信号量
2.9.2 整形信号量
用一个整数型的变量作为信号量，用来表示系统某种资源的数量
仍然无法解决让权等待
此处 wait 中如果一直得不到服务是否会因为原语无法中断而导致处理机一直无法释放？
=> 当原子操作无法完成时，会自动恢复到操作之前的状态。
2.9.3 记录型信号量
存在一个等待队列，资源不足的时候先 block 后 wakeup
遵循了让权等待原则，不会出现忙等
2.9.3 用信号量机制实现进程互斥
2.9.4 信号量实现同步
进程同步：让并发进程有序执行
2.9.5 信号量机制实现进程前驱关系
前V后P
2.10 生成者-消费者问题
本质：互斥、同步问题解决
缓冲区需要互斥访问；且满时需要等待消费者取走，空时需要等待生产者放入，即同步操作
实现互斥的P操作一定在实现同步的P操作之后，否则发生死锁现象：
当empty = 0; full = n(此时缓冲区已满，需要先执行消费者)，执行 1=>2 时因为2阻塞，而再执行3时因为1的执行而又阻塞，发送死锁现象，因此互斥访问的P操作必须在同步之后。V操作不会导致进程阻塞可以交换顺序
PV问题解题思路
- 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
- 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
- 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)
实现一前一后，需要"前操作之后V后操作之前P"
2.11 多生产者多消费者问题
多指代多种类，苹果和橘子多种产品。
如果盘子的容量为1时，各种产品最多只有一种为1，此时不管怎么执行都只会执行一种消费者，其余会阻塞。因此容量为1时可以不使用互斥信号量。当容量大于1时，一定需要使用互斥信号量否则可能会产生缓冲区数据覆盖的情况
在分析关系的时候一定是分析事件的前后关系，例如儿子女儿进程都可以导致父亲母亲可放入水果，但我们只从盘子是否为空这个事件的角度出发，只是一对前后关系。
2.12 吸烟者问题
一个生产者，三个消费者且每个消费者所需的物品不同。并且按照一定顺序拿走自己所需的产品
2.13 读者写者问题
读写两种操作，多个读进程不会有副作用，但写操作不能和其他进程共存.
因此：写进程和其他都互斥，需要一个 rw 信号量，在读写操作都加锁。但这样带来的问题是第二个读进程读入的时会被 rw 信号量卡住，因此引入一个 count 在第一个读进程时加锁后面不加锁，最后一个读进程需要解锁
增加一个mutex互斥变量，保证对count变量的互斥访问
此算法中默认是读进程优先，写进程可能会“饿死”
加入一个信号量w
如果一个读者顺利执行，此时写文件，前面V(w)可用顺利写文件，但下一个读文件会被卡在P(w),等写完文件才会重新开放
2.14 哲学家进餐问题
如果五个哲学家同时并发吃饭，一起拿去左边的筷子则可能发生死锁现象
此问题的关键就是解决死锁问题
方案：每个人吃饭需要两只筷子，即拿起左右两边的筷子，如果别人在占用就等待。这样保证不会发生死锁现象。
2.15 管程
2.15.1 定义
信号量机制存在编写困难、易出错的问题。因此引入管程=>一种高级同步机制
管程是一种特殊的软件模块，由这些部分组成:
- 局部于管程的
共享数据结构说明 - 对该数据结构进行操作的一组过程(函数)
- 对局部于管程的共享数据设置初始值的语句
- 管程有一个名字
管程的基本特征:
- 局部于管程的数据只能被局部于管程的过程所访问 (互斥)
- 一个进程只有通过调用管程内的过程才能进入管程访问共享数据 (private概念)
- 每次仅
允许一个进程在管程内执行某个内部过程 (这样保证了共享数据结构的互斥)
2.15.2 管程解决生产者消费者问题
相当于进行了封装，互斥通过编译器实现、程序员不用关心
2.16 死锁
2.16.1 定义
每个人都有资源且都在等待对方的资源，发生死锁。
死锁：在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉,这些进程都将无法向前推进。
饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如:在短进程优先SPF算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。
死循环:某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。
2.16.2 死锁产生的必要条件
互斥条件：资源必须是互斥使用的，所以发生互相等待
不可剥夺条件：进程未使用完资源前不可强行剥夺使用
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
死锁一定会循环等待，循环等待不一定发生死锁。Eg: 同类资源大于1，循环等待也未必发生死锁，同类资源只有1，则一直循环等待
2.16.3 发生死锁场景
-
对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源(CPU）的竞争是不会引起死锁的。
-
进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2,而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
-
信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。(可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）
总之，对不可剥夺资源的不合理分配，可能导致死锁。
2.16.4 避免死锁
- 预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
- 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法)
- 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施接触死锁
2.17 预防死锁
预防死锁就是破坏形成的四个条件(其一即可)：
2.17.1 破坏互斥条件
Eg:SPOOLing技术。操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备。
2.17.2 破坏不可剥夺条件
- 当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
- 当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如:剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用)
缺点：
- 实现起来比较复杂。
- 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
- 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
- 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。
2.17.3 破坏请求和保存条件
使用静态分配方式：进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。
缺点：有些资源可能只需要使用很短的时间，因此在进程使用期间一直保存资源会导致资源浪费，资源利用率很低。且可能导致一些进程饥饿
2.17.4 破坏循环等待条件
可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。因此申请资源一定是先申请小编号再申请大编号的，这样就不会循环等待。
缺点：
- 不方便增加新的设备，因为可能需要重新分配所有的编号;
- 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费; (比如5、7号代表打印机和扫描仪，但是先使用了扫描仪，而先申请了打印机资源会导致资源浪费)
- 必须按规定次序申请资源，用户编程麻烦。
2.18 避免死锁(银行家算法)
三、内存
3.1 内存概念
3.1.1 定义
内存是
用于存放数据的硬件。程序执行前需要放在内存中才能被CPU处理
2^10 = 1K , 2^20 = 1M , 2^30 = 1G
3.1.2 装入模块装入内存
装入的三种方式（用三种不同的方法完成逻辑地址到物理地址的转换）:
- 绝对装入
- 静态重定位
- 动态重定位
只适合单道程序环境。使用的绝对地址可在编译或汇编的时候给出，也可由程序员直接赋予。
3.1.3 链接
- 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的可执行程序(装入模块)，以后不再拆开。
- 装入时动态链接：将用户源程序编译后所得到的一组目标模块，在装入内存时，釆用边装入边链接的链接方式。
- 运行时动态链接：对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行的链接。其优点是便于修改和更新，便于实现对目标模块的共享。
程序整个流程: 源代码=>编译=>链接=>装入内存
3.2 内存管理
3.2.1 操作系统内存功能
- 操作系统负责内存空间的分配与回收
- 操作系统需要提供某种技术从逻辑上对内存空间进行扩充
- 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换(三种装入方式)
- 操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互低干扰
3.2.2 内存保护
- 设置上下限寄存器
-
重定位寄存器：记录逻辑地址最大长度
3.2.3 内存扩充
覆盖：将程序分为多个段（多个模块)。常用的段常驻内存，不常用的段在需要时调入内存。
内存中分为一个“固定区”和若干个“覆盖区”。
需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束)
不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存
B和C、D和E和F 都不会同时执行，所以共用一个覆盖区需要的时候再调用。此情况只适合有明显调用关系的程序
交换技术：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）
中级调度(内存调度)就是实现交换技术：即内存不足的时候只在内存中保留进程的PCB，并放入挂起队列中
内存不够(如许多进程发生缺页)直接放在对换区。文件区是离散存储，追求存储空间利用率，而对换区追求的是I/O速度
可优先换出阻塞进程;可换出优先级低的进程;为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间
3.2.4 内存连续分配管理方式
单一连续分配：只能有一道用户程序，实现简单无外部碎片。不能并发
内部碎片：存储器利用率很低。
固定分区分配：有分区大小不等和分区大小相等。分成n个区域则可执行运行多到程序。
OS创建分区说明表：每一个表包含分区的大小、起始地址、分配状态。当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表,从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为“己分配”。
优点:实现简单，无外部碎片。
缺点: a.当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能;
b.会产生内部碎片，内存利用率低。
动态分区分配：又称可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。
-
操作系统使用空闲分区表或者空闲分区链来记录内存使用结构
-
当很多个空闲分区都满足需求的时候，使用动态分区算法来决定选择哪个分区进行分配
-
如何进行分区的分配与回收？
分配:修改空闲分区的大小和起始地址，如果直接占满了空闲分区则直接从分区表中删除此分区
回收:修改分区大小和起始地址，有相邻的空闲分区则合并
外部碎片：指内存中的空闲分区太小难以利用上
3.2.5 动态分区分配算法
首次适应算法：每次都从低地址开始,找到第一个合适的分区即可
最佳适应算法：尽可能留下大片连续空间。空闲分区链按照容量递增次序链接，每次分配内存时顺序查找。缺点是产生很多外部碎片无法使用
最坏适应算法：优先使用最大的空闲分区
邻近适应算法：不重新排列链表，直接查找
3.3.6 基本分页存储管理
基本分页存储管理的思想――把内存分为一个个相等的小分区,再按照分区大小把进程拆分成一个个小部分
将内存分称一个个大小相等的分区就是一个个**页框**
将用户进程的地址空间也分为与页框大小相等的一个个区域，称为“页”或“页面”(进程最后一个页面可能没有页框这么大)。每个页面也有一个编号，即“页号”，页号也是从0开始。
各个页面不一定连续存储，可以分散
如何实现逻辑地址的转换?
页号=逻辑地址/页面长度
页内偏移量=逻辑地址%页面长度
每个进程都会创建一个页表
3.3.7 基本地址变换机构
基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。
通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在==进程控制块（PCB）==中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。
有页号后判断是否越界，然后根据页表起始位置，且每个页表项长度是相同的因此可以算出此页号对应的页表项存放位置。
因此得到内存块号，得到实际地址。
3.3.8 具有快表的地址变化结构
局部性原理：
四、文件管理
4.1 基础概念
4.1.1 属性
文件属性：文件名，标识符(唯一)，类型，大小，创建时间，上次修改时间，保护信息等
文件：无结构文件和有结构文件
操作系统提供功能：
以及打开文件(open系统调用）关闭文件(close系统调用)
4.1.2 文件如何存放在外存
外存也分成一个一个块，叫"块/磁盘块/物理块"。
4.2 文件的逻辑结构
所谓的“逻辑结构”，就是指在用户看来，文件内部的数据应该是如何组织起来的。而“物理结构”指的是在操作系统看来，文件
的数据是如何存放在外存中的。
文件的逻辑结构：
4.2.1 无结构文件
无结构文件:文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如:Windows操作系统中的.txt文件
4.2.2 有结构文件
有结构文件:由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如:数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID)
顺序文件：文件中的记录逻辑上相邻，物理上不一定,有顺序存储或链式存储。链式无法随机存取。
4.2.3 索引文件
对于可变长记录文件，要找到第i个记录，必须先顺序第查找前i-1个记录但是很多应用场景中又必须使用可变长记录。
因此引入索引文件
4.2.4 索引顺序文件
将索引分组，并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。
建立多级索引可以提高检索效率
总结
4.3 文件目录
4.3.1 文件控制块
实现文件目标(文件夹)的关键数据结构
目录本身就是一个结构文件，由一条条记录组成。每条记录对应一个放在该目录下的一个文件
目录文件中的一条记录就是一个“文件控制块（FCB)，FCB实现了文件名和文件之间的映射。使用户可以实现按名存取
对目录的操作：
搜索:当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
创建文件:创建一个新文件时，需要在其所属的目录中增加一个目录项
删除文件:当删除一个文件时，需要在目录中删除相应的目录项
显示目录:用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
修改目录:某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项(如:文件重命名)
4.3.2 目录结构
单级目录结构：整个系统中只建立一张目录表，每个文件占一个目录项。因此不能有重名文件，不适合多用户操作系统
两级目录结构：分成主文件目录(MFD)和用户文件目录(UFD)
也可以实现访问限制，但仍缺乏灵活性，用户不能对自己的文件进行分类
多级目录结构
但是树形结构不便于实现文件的共享
==无环图目录结构：==可以用不同的文件名指向同一个文件，甚至同一个目录。
需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。只有当共享计数器减到0以后才会删除此文件
4.3.2 ？索引节点(FCB的改进)
4.4 文件的物理结构(分配方式)
4.4.1 连接分配
在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。
重点的逻辑地址映射到物理地址
连续分配要求文件在磁盘上占有有一组连续的块
记录方式：
读取方式：
例如要访问"aaa" 的逻辑块号2，则起始块号为4，逻辑块号为2，所以物理块号就是在 6 。因此支持随机访问和顺序访问
连续分配在顺序读/写时速度最快，但拓展并不方便(eg：黄色区域拓展但后面的文件已经被其他文件占用)
4.4.2 链接分配
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
隐式链接：记录起始位置和终止位置，并且记录指向下一个块号的指针。只支持顺序访问，查找效率低。但很方便文件拓展，外存利用高
显示链接：把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表（FAT，File Allocation Table)
五、磁盘
5.1 磁盘的结构
5.1.1 定义
磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据。磁盘被分为磁道，一个磁道又分为一个个扇区，一个扇区是为1kb
磁盘是由一个个盘面垒起的，可用柱面号(确定磁道)、盘面号(确定盘面)、扇区号(确定扇区)定位
5.1.2 磁盘分类
根据磁头是否可动分为：活动头磁盘、固定头磁盘
根据磁盘是否可换： 固定盘磁盘、可换盘磁盘
5.2 磁盘调度算法
5.2.1 磁盘读写时间
寻找时间(寻道时间)Ts: 在读/写数据前，将磁头移动到指定磁道所花的时间。
选择10
填空10: 每一章小节 1、3、4节 第四章 第2、12、13 第五章 第1、3、4 小节 第六章 3、5 小节
简答40
计算40:
- 磁盘调度和管理(调度算法)、 p279 15题 p269
- 存储管理(页面置换算法) p198 22题 p177 LRU p139 17题 p118优先级调度
- 死锁 p104 第四题 算法
- 同步与互斥：司机和售票员、吃水果问题 p31 3.5.6 p32 20