分时系统

1. 多路性：系统允许将多台终端同时连接到一台主机上，并按分时原则为每个用户服务
2. 独立性：各用户在各自的终端上操作互不影响
3. 及时性：用户的请求能在短时间内得到响应
4. 交互性：用户可通过终端与系统进行广泛的人机对话（即请求系统提供各种服务）

---

开始截止时间：指某任务在某时间以前必须开始执行
完成截止时间：指某任务在某时间以前必须完成
硬实时任务：必须满足任务对截至时间的要求，否则可能出现难以预测的后果
软实时任务：有截止时间但并不严格，偶尔错过了也不会造成什么大的影响

---

实时系统与分时系统特征的比较：

1. 多路性：分时系统中的多路性都表现为系统按分时原则为多个终端用户服务；实时控制系统的多路性则是指系统周期性的对多路现场信息进行采集，以及对多个对象或多个执行机构进行控制
2. 独立性：二者差不多
3. 及时性：一个是依据人所能接受等待的时间确定，一个是以控制对象所要求的截止时间来确定
4. 交互性：实时系统中，人与系统的交互性仅局限于访问系统中某些特定的专用服务程序
5. 可靠性：分时系统要求系统可靠，而实时系统要求系统高度可靠

---

• 单用户单任务操作系统：CP/M MS-DOS
• 单用户多任务操作系统：window
• 多用户多任务操作系统：UNIX LINUX

---

• 并行性：指两个或多个事件在同一时刻发生
• 并发性：指两个或多个事件都在同一时间间隔内发生

---

并发和共享时多用（多任务）OS的两个最基本的特征

---

• 时分复用技术
• 空分复用技术
  时分复用技术（多道程序技术）是通过利用处理机的空闲时间运行其他程序，提高了运行处理机的利用率，空分复用技术，则是利用存储器的空闲时间分区域存放和运行其他的多道程序，以此来提高内存的利用率

---

处理及管理功能：

1. 进程控制：创建进程，分配资源，结束进程等
2. 进程同步
3. 进程通信
4. 调度

---

微内核OS系统

基本概念

1. 足够小的内核
2. 基于客户/服务器模式
3. 应用“机制与策略分离”原理
4. 采用面向对象技术

---

前驱图

有向无循环图，可记为DAG：用于描述进程之间执行的先后顺序
进程（或程序）之间的前驱关系可用“->”表示

如果进程Pi和Pj存在着前驱关系，可表示为（Pi，Pj）属于->，也可以写作Pi->Pj
表示Pj开始执行前Pi必须完成，此时称Pi是Pj的直接前驱，Pj是Pi的直接后继
没有前驱的结点称为初始结点，没有后继的结点称为中止结点

---

程序顺序执行时的特征

1. 顺序性
2. 封闭性
3. 可再现性

程序并发执行时的特征

1. 间断性
2. 失去封闭性
3. 不可再现性

---

进程的定义

进程控制块：PCB
由程序段、相关的数据段和PCB三部分便构成了进程实体（又称进程映像），简称为进程
==创建进程实质是创建进程实体中P的CB，而撤销进程实质就是撤销进程的PCB==
进程的特征：

1. 动态性
2. 并发性
3. 独立性
4. 异步性

进程的三种基本状态

1. 就绪状态（Ready）
2. 执行状态（Running）
3. 阻塞状态（Block）

就绪状态 被进程调度 执行
执行 时间片用完 就绪
阻塞 I/O完成 就绪
执行 I/O请求 阻塞

创建状态：

• 申请一个空白的PCB，并向PCB中填写用于控制和管理进程的信息
• 为进程分配运行时所必须的资源
• 把继承转入就绪状态并插入就绪队列中，若进程所需资源尚不能满足，则其仍为创建状态
  终止状态
• 等待操作系统进行善后处理
• 将其PCB清零，并将PCB空间返还系统

挂起操作的引入（将进程由内存移到外存）：基于系统和用户的如下需要

1. 终端用户的需要
2. 父进程的需要
3. 负荷调节的需要
4. 操作系统的需要

引入挂起原语操作后三个进程状态的转换

挂起原语Suspend 激活原语Active

1. 活动就绪->禁止就绪
2. 活动阻塞->静止阻塞
3. 静止就绪->活动就绪
4. 静止阻塞->活动阻塞

---

PCB的具体作用

1. 作为独立运行基本单位的标志（==PCB是进程存在于系统中的唯一标识==）
2. 能实现间断性运行方式
3. 提供进程管理所需要的信息
4. 提供进程调度所需要的信息
5. 实现与其他进程的同步与通信

进程控制块中的信息：

1. 进程标识符
   1. 外部标识符
   2. 内部标识符
2. 处理及状态
3. 进程调度信息
4. 进程控制信息

进程控制块的组织方式：1.线性方式 2.链接方式 3.索引方式

---

系统操作内核

• 系统态（管态）
• 用户态（目态）

支撑功能

• 中断处理
• 时钟管理
• 原语管理

资源管理功能

• 进程管理
• 存储器管理
• 设备管理

---

引起进程终止的事件

• 正常结束
• 异常处理
• 外界干预

终止进程时还应将其所有子孙进程都终止，以防其成为不可控的进程，将所有终止进程的资源归还给其父进程或系统

---

两种形式的制约关系

1. 间接相互制约关系（互斥）

对于临界资源（又称为共享资源，互斥资源）必须保证多个进程对之只能互斥地访问

2. 直接相互制约关系（同步）

多个进程为完成同一项任务而相互合作

由于存在着上述两类相互制约关系，进程在运动过程中能否获得处理及运行与以怎样的熟读运行，并不能由进程自身所控制，即进程的异步性

临界区：在每个进程中访问临界资源的那段代码称为临界区

一个访问临界资源的循环进程描述：

while(TRUE)
{
    进入区
    临界区
    推出区
    剩余区
}

同步机制应遵循的规则

• 空闲让进
• 忙则等待
• 有限等待
• 让权等待

---

P、V操作(原子操作)

wait(S) :P （S减1）
signal(S):V （S加1）

1. 整型信号量（未遵循“让权等待”）
2. 信号记录量
3. AND型信号量
4. 信号量集

AND同步机制的基本思想：将继承在整个运行过程中需要的所哟资源，一次性全部分配给进程，待进程使用完后在一起释放

---

利用信号量实现进程互斥
为使多个进程能互斥地访问某临界资源，只需为该资源设置--互斥信号量mutex，并设其初始值为1，然后将进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。
利用信号量实现前驱关系：

实例：实现下图的前驱关系  
p1(){S1;signal(a);siganl(b);}  
p2(){wait(a);S2;signal(c);signal(d);}  
p3(){wait(b);S3;signal(e)}  
p4(){wait(c);S4;signal(f)}  
p5(){wait(d);S5;signal(g)}  
p6(){wait(e);wait(f);wait(g);S6;}  
main(){
    semaphore a,b,c,d,e,f,g;
    a.value = b.value = c.value = 0;
    d.value = e.value =0;
    f.value = gi.value = 0;
    cobegin
    p1();p2();p3();p4();p5();p6();
    coend
}

graph LR
s1-->s2
s2-->s5
s2-->s4
s4-->s6
s5-->s6
s1-->s3

---

进程的两个基本属性：

1. 进程是一个可拥有资源的独立单位
2. 进程是一个可独立调度和分配的基本单位

线程--作为调度和分派的基本单位

不同于进程，将 调度和分派 与 拥有资源 ，这两个属性分开

---

进程与线程的比较

1. 调度的基本单位：
   • 传统的OS中，进程是作为独立调度和分派的基本单位，每次被调度时，都需要进行上下文切换开销较大
   • 在引入线程的OS中，把贤臣作为调度和分派的基本单位，因而线程是能独立运行的基本单位，当线程切换时，仅需保存和设置少量寄存器内容，切换代价远低于进程
   • ==在同一进程中，线程的切换不会引起线程的切换，但从一个进程中的线程切换到另一个线程中的线程时，必然会引起进程的切换==
2. 并发性：不仅线程之间可以并发执行，一个进程中的多个线程间亦可并发执行
3. 拥有资源：线程本身并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源
4. 独立性：线程之间的独立性低于进程之间的独立性，因为每个进程都拥有一个独立的地址控件和其他资源，除了共享变量外，不允许其他进程的访问
5. 系统开销：线程开销低于进程开销
6. 支持多处理机系统：对于多线程进程，就可以将一个进程中的多各线程分配到多个处理及上，使它们并行执行，加速进程的完成

---

线程运行的三个状态：

1. 执行状态
2. 就绪状态
3. 阻塞状态

线程控制块（TCB）

---

处理机调度的层次

1. 高级调度（又称为 长程调度 或 作业调度 ）
   • 调度对象为 ==作业==
   • 外存 调入 内存
2. 低级调度（又称为 进程调度 或 短程调度）
   • 调度对象 ==进程==
   • 内存中处理（分配处理机）
3. 中级调度（内存调度）
   • 目的：提高内存利用率和系统吞吐量
   • 内存 调出 外存

进程调度的运行频率最高

---

CPU的利用率 = cpu有效工作时间/（cpu有效工作时间+cpu空闲等待时间）

分时系统的目标：

• 响应时间块
• 均衡性

实时系统的目标

• 截止时间的保证
• 可预测性

---

作业和作业步

• 作业：一个比程序更为广泛的概念。不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存
• 作业步：作业的么一个加工步骤称为 一个作业步

作业控制块（JCB）
作业运行的三个阶段和三种状态

1. 收容阶段：后备状态
2. 运行阶段：运行状态
3. 完成阶段：完成状态

---

作业的调度算法

1. 先来先服务调度算法（FCFS）
2. 短作业优先的调度算法（SJF）
3. 优先级调度算法（PSA）
4. 高响应比优先调度算法（HRRN）

   优先权 = （等待时间+要求服务时间）/要求服务时间
   - 如果作业的等待时间相同，则要求服务的时间啊俞短，其优先权俞高
   - 当要求服务的时间相同时，作业的优先权又决定于其等待的时间
   - 对于长作业的优先级可以虽等待时间的增加而提高

---

进程调度的任务：

1. 保存处理间的现场信息
2. 按某种算法选取进程
3. 把处理器分配给进程

进程调度方式：

1. 非抢占方式
   • 正在执行的进程运行完毕，或因发生某时间而使其无法再继续运行
   • 正在执行中的进程因提出I/O请求而暂停执行
   • 在进程通信或同步过程中，执行了某种原语操作
2. 抢占式方式
   • 优先权原则
   • 短进程优先原则
   • 时间片原则

轮转调度算法

---

实时调度的实现：
提供必要信息

1. 就绪时间
2. 开始截止时间和完成截止时间
3. 处理时间
4. 资源要求
5. 优先级

最低松弛度优先算法（LLF）

松弛度最低的任务排在最前面（紧急程度越高，松弛度越低）
松弛度 = 必须完成时间 - 其本身的运行时间 - 当前时间

优先级倒置

例如：高优先级的进程P3由于和低优先级P1的共享资源的原因，必须等待P1运行完成后才能运行，而二者之间，由于优先级调度算法，P2抢占了P1资源，而P3又抢占了P2的资源，导致P3进程因P1进程被阻塞了，又由于P2的存在，而延长了P3被阻塞的时间，只有等待P2进程运行完成后，p1运行，再最后P3运行

---

死锁

死锁的定义

如果一组进程中的每一个进程都在等待仅由改组进程中的其他进程才能引发的四件，那马改组进程是死锁的
产生死锁的必要条件

1. 互斥条件
2. 请求和保持条件
3. 不可抢占条件
4. 循环等待条件

处理死锁的方法

1. 预防死锁
2. 避免死锁
3. 检测死锁
4. 解除死锁

---

银行家算法

1. 数据结构
   1. 可利用资源向量Avaliable
   2. 最大需求矩阵Max
   3. 分配矩阵Allocation
   4. 需求矩阵Need

---

死锁定理：
S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。

该充分条件被称为：死锁定理

常采用的解除死锁的两种方法：

1. 抢占资源：从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态
2. 终止（撤销）进程：终止一个或多各死锁进程，直至打破循环环路，是系统从死锁状态中走出

---

用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为以各可以执行的程序，通常要经过以下几个步骤：

1. 编译：对源程序进行编译，形成若干个目标模块
2. 链接：由链接程序将编译后形成的一组目标模块以及它们所需要的库函数链接一起，形成一个完整的装入模块
3. 装入：由装入程序将装入模块装入内存

重定位：在装入时对目标程序中指令和数据地址的修改过程称为 重定位

---

连续分配方式可分为四类：

• 单一连续分配
• 固定分区分配
• 动态分区分配
• 动态可重定位分区分配算法

---

基于顺序搜索的动态分区分配算法

• 首次适应算法（FF）
• 循环首次适应算法（NF）
• 最佳适应算法（BF）
• 最坏适应算法（WF）

动态重定位：程序在执行时，真正访问的内存地址是相对地址与重定位寄存器终端地址相加而形成的

---

根据在离散分配时所分配地址空间的基本单位的不同，又可以将离散分配分为以下三种：

• 分页存储管理方式

相应的将内存空间分为若干个物理块或页框，页和块的大小相同

• 分段存储管理方式
• 段页式存储管理方式

分页地址中的地址结构：

31 12|11 0
页号P | 位移量W
前一段位页号 P，后一部分为位移量W，即页内地址

页表的作用是：实现从页号到物理块号的地址映射。

由于页表是存放在内存中的，这使CPU在没存取一个数据时，都要两次访问内存
第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据。

为了提高地址变换速度，可在地址变换机构中共增设一个具有并行查寻能力的特殊高速和缓冲寄存器，又称为”联想寄存器“，或称为”快表“
内存的有效访问时间（EAT)：从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单位并取出数据，所需要花费的总时间，称为内存的有效访问时间

EAT = t+t = 2t t为访问一次内存所需的时间

---

分页和分段的主要区别

1. 页是信息的物理单位，分段存储管理方式中的段则是信息的逻辑单位
2. 页的大小固定且由系统决定，段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序在对源程序进行编译时，根据信息的性质来划分
3. 分页的用户程序地址空间是一维的，完全是系统的行为，而分段是用户的行为，故在分段系统中，用户程序的地址空间是二维的

段页是存储管理方式：
地址结构由段号，段内页号，页内地址三部分组成

获得一条指令或数据，需三次访问内存。第一次访问内存中的段表，获得页表始值，第二次访问内存中的页表，从中取出该页所在的物理块号，并将该块号和页内地址一起形成指令或数据的物理地址，第三次访问才是真正的数据或指令

---

虚拟存储器的基本工作情况：基于局部原理，应用程序在运行之前没有必要将之全部装入内存，而仅需将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在攀上。程序在运行时，如果他要访问的页已调入内存，便可继续执行下去，但如果程序索要访问的页尚未调入内存，便发出缺页中断请求，此时OS将利用请求调页功能将它们调入内存，以使进程能继续执行下去。如果此时内存已满，无法在装入新的，还需使用页的置换功能，将内存汇总暂时不用的页调至盘上，腾出所需的空间，调入要访问的页入内存。

这样，便可使一个大的用户程序在较小的内存空间中运行，也可在内存中同时装入更多的进程，使它们并发执行

虚拟存储器：具有请求调入功能和置换功能，能从逻辑上对应内存容量加以扩充的一种存储器系统
虚拟存储器的特征：

1. 多次性

可以分次将程序和数据放入内存

2. 对换性

程序运行期间，允许将暂不使用的代码和数据从内存调至外存的兑换去，待以后需要以后再从外存调入内存

3. 虚拟性：从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量

---

页面置换算法：

• 最佳置换算法（OPT）

理想上的算法

• 先进先出算法（FIFO）
• 最近最久未使用置换算法（LRU）
• 最近最少使用置换算法（LFU）

---

产生”抖动“的原因：
同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程再运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存，导致调入调出的进程数目增加，使处理及的利用率急剧下降并趋于0

工作集：
指再某段时间间隔里，进程实际所要访问页面的集合。

”抖动“的预防方法

1. 采取局部置换策略：当某进程发生缺页时，只能在分配给自己的内存空间内进行置换，不允许从其他进程去获得新的物理快
2. 把工作集算法融入到处理机调度中
3. 利用”L=S“准则调节缺页率

L 是缺页之间的平均时间 S 是平均缺页服务时间（用于置换一个页面所需的时间）
如果L<<S，则说明缺页，缺页的速度超过磁盘的处理能力

4. 选择暂停的进程

---

I/O软件的层次结构

1. 用户层I/O软件：实现用户交互的接口，用户可直接调用该层所提供的、与I/O操作有关的库函数对设备进行操作

产生I/O请求，格式化I/O，Spooling

2. 设备独立性软件：用于实现用户程序与设备驱动器的统一接口、设备命名、设备的保护以及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间

映射、保护、分块、缓冲、分配

3. 设备驱动程序：与硬件直接相关，用于具体实现系统对设备发出的操作指令，驱动I/Oshebei工作的驱动程序

设置设备驱动器：检查状态

4. 终端处理程序：用于保存被终端进程的CPU环境，转入相应的中断处理程序进行处理，处理完毕再恢复被中断进程的现场后，返回到被终端的进程

5. 硬件：执行I/O操作

---

I/O系统的分层：

1. 中断处理程序：处于I/O系统的底层
2. 设备驱动程序：处于I/O系统的次底层
3. 设备独立性软性

---

I/O设备的类型：

1. 按使用特性分类：
   1. 存储设备（外存等）
   2. I/O设备（键盘）
2. 按传输速率分类
   1. 低速设备（键盘等）
   2. 中速设备（打印机等）
   3. 高速设备（磁带机等）

---

中断和陷入

1. 中断：CPU对I/O设备发来的中断信号的一种响应
2. 陷入：CPU内部时间所引起的中断

中断向量表和中断优先级

1. 中断向量表

为了处理上的方便，通常是为每种设备配以相应的中断处理程序，并把该程序的入口地址放在中断向量表的一个表项中，并为每一个设备的中断请求规定一个中断号，直接对应于中断向量表的一个表项中

2. 中断优先级

对多中断源的处理方式

1. 禁止（屏蔽）中断

当处理机再处理一个中断时，将屏蔽掉所有的中断，即对于新到的中断暂时不理，让它们处于等待状态

2. 嵌套中断
   1. 当同时有多个不同优先级的中断请求时，Cpu响应最高优先级的中断请求
   2. 高优先级的中断请求可以抢占正在运行的低优先级中断的处理及，类似于基于优先级的抢占式进程调度

---

DMA工作过程

当CPU要从磁盘读入以数据块时，便向磁盘控制器发送一条读命令。该命令被送入命令寄存器CR中。同时，需要将本次要读入数据在内存的起始目标地址送入内存地址寄存器MAR中，将要读数据的字（节）数送入数据计数器DC中。还需将磁盘中的源地址直接送至DMA控制器的I/O控制逻辑上。然后启动DMA控制器进行数据传送。以后，CPU便可去处理其他任务，整个数据传送过程由DMA控制器进行控制。当DMA控制器已从磁盘中读入一个字（节）的数据，并送入数据寄存器DR后，再挪用一个存储走起，将该字（节）传送到MAR所指示的内存单元中。然后便对MAR内容加1，将DC内容减1，若减1后DC内容不为0，标识传送未完，便继续传送下一个字（节）；否则，由DMA控制器发出中断请求。

DMA控制器由三部分组成：主机与DMA控制器的接口；DMA控制器与块设备的接口；I/O控制逻辑

为了实现在主机与控制器之间成块数据的直接交换，必须在DMA控制器中，设置如下四类寄存器：

1. 命令/状态寄存器CR
2. 内存地址寄存器MAR
3. 数据寄存器DR
4. 数据计数器DC（存放本次CPU要读或写的字（节）数）

---

独占设备的分配程序

1. 基本的设备分配程序
   1. 分配设备
   2. 分配控制器
   3. 分配通道
2. 设备分配程序的改进

不同于以上使用物理设备名分配，使用逻辑设备名请求I/O，以获得设备的独立性

---

假脱机系统（Spooling）

如果说，通过躲到程序技术可将一台物理CPU虚拟成为多台逻辑CPU，从而允许多个用户共享一台主机，那么，通过假脱机技术，则可将一台物理I/O设备虚拟成为多台逻辑I/O设备，这样也就允许多个用户共享一台物理I/O设备

SPOOLing系统主要由以下四部分组成：

1. 输入井和输出＃
2. 输入缓冲区和输出缓冲区
3. 输入进程和输出进程
4. ＃管理程序

SPOOLing系统的特点：

1. 提高了I/O的速度
2. 将独占设备改造为共享设备
3. 实现了虚拟设备功能

---

缓冲引入的原因：

1. 缓和CPU与I/O设备间速度不匹配的矛盾
2. 减少对CPU的中断频率，放宽对CPU中断响应时间的限制
3. 解决数据力度不匹配的问题
4. 提高CPU和I/O设备之间的并行性

• 单缓冲区
• 双缓冲区（也称为 缓冲对换）
• 环形缓冲区

多个缓冲区 多个指针
Nextg：指示计算进程下一个可用缓冲区G的指针；
Nexti：指示输入进程下次可用的空缓冲区R的指针
Current：用于指示计算进程正在使用的缓冲区C的指针

Nexti指针和Nextg指针沿着顺时针方向移动

Nexti指针追上Nextg指针。意为着输入进程输入数据的速度大于计算进程处理数据的速度,已把全部可用的空缓冲区装满，再无缓冲区可用，此时输入进程应阻塞，直到计算进程把某个缓冲区的数据全部提取完，再唤醒输入进程。这种情况被称为系统受计算限制

Nextg指针追上Nexti指针。意为输入数据的速度低于计算进程处理数据的速度，使全部装有输入数据的缓冲区都被抽空。此时应阻塞计算进程。这种情况称为系统受I/O限制

缓冲区与缓冲池的区别：
蝗虫去仅仅是一组内存块的链表，而缓冲池则是包含了一个管理的数据结构及一组操作函数的管理机制，用于管理多个缓冲区

---

1. 固定磁头磁盘：

每条磁道上都有一读/写磁头，所有的磁头都被装在一刚性臂中，通过这些磁头可访问所有各磁道，并进行并行读/写，有效的提高了磁盘的I/O速度。这种结构主要用于大容量磁盘上

2. 移动头磁盘

每一个盘面仅配有一个磁头，也被装入磁臂中，为了能访问该盘面上的所有此导，该磁头必须能移动以进行寻道。因此，移动磁头仅能以串行方式读/写，指示I/O速度较慢，但由于结构简单，广泛用于中小型磁盘设备中。

磁盘访问时间

1. 寻道时间

启动磁臂的时间与磁头移动n条磁道所花费的时间之和（占大份）

2. 旋转延迟时间
3. 传输时间

---

磁盘调度算法

1. 先来先服务（FCFS）
2. 最短寻道服务时间（SSTF）

基于扫描的磁盘调度算法

1. 扫描算法（SCAN）（又称为“电梯调度算法）

磁头从当前方向一直移动到边缘，再调转方向从边缘到另一个

2. 循环扫描算法（CSCAN）

磁头只能自里向外移动

---

文件系统的层次系统

1. 对象及其属性
   1. 文件
   2. 目录
   3. 磁盘（磁带）存储空间
2. 对对象操纵和管理的软件集合
   1. I/O控制层
   2. 基本文件系统层
   3. 基本I/O管理程序
   4. 逻辑文件系统
3. 文件系统的接口
   1. 命令接口
   2. 程序接口

---

文件的逻辑结构

1. 按文件是否有结构分类、
   1.有结构文件
   1. 定长记录
   >广泛用于数据处理中
   2. 边长记录
   >广泛用于许多商业领域
   2. 无结构文件（流式文件）
2. 按文件的组织方式
   1. 顺序文件
   2. 索引文件
   3. 索引顺序文件

对于顺序存储设备，也只有顺序文件才能被存储并能有效的工作

---

文件控制块和索引节点

==文件控制块（FCB)==
三类信息：

1. 基本信息：
   1. 文件名
   2. 文件物理位置
   3. 文件逻辑结构
   4. 文件的物理结构
2. 存取控制信息
3. 使用信息

磁盘索引节点：

1. 文件主标识符
2. 文件类型
3. 文件存取权限
4. 文件物理地址
5. 文件长度
6. 文件连接计数
7. 文件存取时间

内存索引结点

1. 索引节点编号
2. 状态
3. 访问计数
4. 文件所属文件系统的逻辑设备号
5. 链接指针

---

树形目录
主目录：称为根目录
数据文件：称为树叶
其他的目录称为：树的结点

从树根开始的路径名称为 绝对路径名
从当前目录开始直到数据文件为止的路径名称为 相对路径名

---

外存的组织方式

1. 连续组织方式

优点：
顺序访问容易
顺序访问速度快
缺点：
要求为一个文件分配连续的存储空间
必须事先知道文件的长度

2. 连接组织方式

优点：
消除了磁盘的外部碎片，提高了外存的利用率
对插入、删除和修改记录都非常容易
能适应文件的动态增长，无需事先知道文件的大小
隐式链接 显示链接

3. 索引组织方式

FAT12

每个FAT表项为12位，因此，在FAT表中最多允许有4096（2^12）个表项，如果盘块为基本单位，每个盘块的大小为512字节，那么每个磁盘分区的容量为2MB(4096*512B)，一个物理磁盘能支持4个逻辑磁盘分区，所以相应的磁盘最大容量仅为8MB。

簇

一组相邻的扇区，在FAT中它是作为一个虚拟山区。在进行盘块分区时，以簇作为分配的基本单位。簇的大小一般是2n个盘块，例如当一个簇仅有一个扇区时，磁盘的最大容量为8MB，当一个簇包含了8个扇区时，磁盘的最大容量为64MB
优点：
能减少FAT表中项数，使FAT表占更少的存储空间，减少存取开销
缺点：
造成更大的簇内零头（与存储管理器中的页内零头相似）（限制磁盘容量的主要原因）

FAT16

FAT12对磁盘容量限制的原因在于，FAT12表中的表项有限制，即最多只允许2^12个，如果我们将FAT表项中位数增为16，则最大表项数将增至2^16个，此时便能将一个磁盘分区分为2^16个簇,在FAT的每个粗重可以有的盘块数为4，8。。。直到64。
由此可以得出管理的最大分区空间为2^16*64*512=2048MB

FAT32

在FAT有最小管理空间的限制，FAT32卷必须至少有65537个簇，所以不支持容量小于512MB的分区
FAT32的单个文件长度也不能大于4GB
FAT43不能保持向下兼容

块大小	FAT2	FAT16	FAT32
0.5 KB	2 MB
1 KB	4 MB
2 KB	8 MB	128 MB
4 KB	16 MB	256 MB	1 TB
8 KB		512 MB	2 TB
16KB		1024MB	2 TB
32KB		2048MB	2 TB

NTFS新特征

1. 使用64为磁盘地址
2. 在NTFS中可以很好地支持长文件名
3. 具有系统容错功能
4. 能保证系统中地数据一致性