1. OS的概念、特性

概念

操作系统是计算机系统中的一个系统软件，是一些程序模块的集合。

特性

1. 并发/并行
2. 共享：操作系统与多个用户程序共同使用计算机系统中资源，其中分为：
   • 互斥共享：资源不能同时使用。
   • 同时共享：资源可以同时使用。
3. 虚拟：一个物理实体映射为若干个对应逻辑实体（分时或分空间）。存储器中每个进程都有独立的虚拟地址空间（存代码、数据、堆栈）。
4. 随机：OS要对不可预测的事件进行响应处理。

2. OS的功能

1. 资源分配

• 静态分配策略：把进程所有需要的资源先都分配给它，但这可能导致资源浪费。
• 动态分配策略：进程什么时候需要资源就什么时候分配，如果该资源已被占用，进程会阻塞并进入相应的等待队列。

2. 资源管理

• 进程/线程管理
• 存储管理
• 文件管理
• 设备管理
• 用户接口管理

3. OS的发展历史及分类

1) 批处理操作系统

工作方式

1. 用户将作业（作业：由作业说明书、用户程序、数据组成，且通常为卡片形式，输入设备为卡片机）交给系统操作员。
2. 系统操作员将多个作业组成一批作业，输入到计算机系统中，形成一个自动转接的连续作业流。
3. 启动OS。
4. OS自动执行每个作业，用户无法干预。
5. 执行结果交给用户。

追求目标

• 提高资源利用率，增加作业处理吞吐量。

总体过程

• 从卡片机读入用户作业和编译链接程序，编译链接生成可执行程序，执行程序并输出执行结果。

问题

• 慢速I/O设备与CPU处理速度差异过大，导致CPU在等待数据时空闲。

2) Spooling技术

利用磁盘做缓冲，将输入、计算、输出分别组成独立的任务流，使I/O和计算并行（假脱机：磁盘在高效的计算机上）。

工作流程

1. 用户作业输入磁盘输入。
2. 按照某种调度策略，选几个搭配得当的作业调入内存。
3. 作业运行结果输出到磁盘的输出。
4. 运行结果从输出井到打印机。

备注：输入输出只到输入或输出井，主机不用直接与慢速的I/O打交道，能提高效率和速度。

现代打印机仍然使用这种技术。

应用Spooling技术后：

3) 分时操作系统

工作方式

多个终端（只有I/O设备没有计算能力）连接到同一主机中，然后OS将CPU时间分成若干个片段，OS以时间片为单位，轮流为每个终端用户服务，每次服务使用掉一个时间片。

追求目标

• 及时响应。
• 响应时间：指从终端发出命令到系统给予回答所经历的时间。

4) 实时操作系统

指计算机能及时响应外部时间请求，在规定的严格时间内完成对该事件的处理。

追求目标

• 对外部请求在严格时间范围内做出响应。

---

第二章 OS硬件环境

1. 管态与目态

通常CPU执行两种不同性质的程序：一种是操作 系统内核程序；另一种是 用户自编程序或系统外层的应用程序。对操作系统而言，这两种程序的作用不同，前者是后者的管理者，因此“管理程序”要执行一些特权指令(不允许用户直接使用的指令，如I/O指令、置中断指令等），而“被管理程序”出于安全考虑不能执行这些指令。所以我们将机器分为两种状态，通过状态的切换来保护操作系统程序。

• 管态(核心态、系统态)：在此状态下，CPU可以执行指令系统的全集，是一种具有较高特权的执行状态，可以访问所有寄存器和存储区。另外OS内核通常是运行在系统态的，进程控制是由OS内核实现。
• 目态(用户态)：在此状态下，CPU只能执行非特权指令。可访问指定的寄存器和存储区，只具有较低的特权。一般的用户程序在此状态下执行。

特权指令

所谓特权指令是指有特权权限的指令，由于这类指令的权限最大，如果使用不当，将导致整个系统崩溃。比如：清内存、置时钟、分配系统资源、修改虚存的段表和页表，修改用户的访问权限等。

为了保证系统安全，这类指令只能用于操作系统或其他系统软件，不直接提供给用户使用。因此，特权执行必须在核心态执行。实际上，cpu在核心态下可以执行指令系统的全集。形象地说，特权指令就是 那些儿童不宜的东西，而非特权指令则是老少皆宜。

为了防止用户程序中使用特权指令，用户态下只能使用非特权指令，核心态下可以使用全部指令。当在用户态下使用特权指令时，将产生中断以阻止用户使用特权指令。所以把用户程序放在用户态下运行，而操作系统中必须使用 特权指令的那部分程序在核心态下运行，保证了计算机系统的安全可靠。从用户态转换为核心态的唯一途径是中断或异常

2. 多级存储体系

原因

计算机采用多级存储，主要是基于 容量、速度、成本 这三个因素考虑的。

多级存储结构 从上到下，容量越来越大，速度越来越慢，成本越来越低；

同时这种多级存储的模式有利于计算机CPU发挥其性能，还解决了数据存储的问题；

因为外存虽然成本低，但是比较慢；它的运行频率、工作频率，数据的传送情况都是比较慢的；

寄存器虽然速度很快，但是成本高，容量小；

Cache

Cache是现代计算机在CPU和主存之间设置的一个高速、小容量的缓冲存储器，填补了CPU和主存在速度上的巨大差距，可用用于提高整个计算机系统的性能。

Cache先被访问，如果不命中，内存后被访问

cache 映射

◆ 直接映像 ➢ 某一主存块只能固定映射到某一缓冲块 ◆ 全相联映像 ➢ 某一主存块能映射到任一缓冲块 ◆ 组相联 ➢ 某一主存块只能映射到某一缓冲组中的任一块

靠近CPU的Cache要求高速，采用直接相联或路数较少的组相联；中间层次采用组相联；距离CPU最远的Cache采用全相联，对利用率强调越高。

cache 优化

cache例题1

多级cache例题1

①强制性失效：当第一次访问一个块时，需要从下一级存储器中调入Cache，这种失效称为强制性失效。也称为冷启动失效或首次访问失效。强制性失效发生在对初始空Cache的访问中。 ②容量失效：由于Cache容量有限，使得程序执行所需的块不能全部调入Cache中，所以当某些块被替换后如果重新被访问就会发生失效。这种失效就称为容量失效。 ③冲突失效：在组相联或直接映像Cache中，多个块映像到同一组（个）块中，则会出现该组中的某一个块被别的块替换后又被重新访问的情况，这就发生了冲突失效。冲突失效也称为碰撞失效或干扰失效。

关于Cache失效的一些结论：

①Cache容量对失效的影响：强制性失效不受到Cache容量的影响，但是容量失效随着容量的增加而减少； ②相联度对失效的影响：强制性失效和容量失效不受相联度的影响，但是相联度越高冲突失效就越少； ③经验规则：大小为N的直接映像Cache的失效率约等于大小为N/2的2路组相联Cache的失效率。

抖动现象(颠簸)

在一个存储层次中如果高一级的存储器的容量比程序所需的空间小得多，就有可能出现由于过多容量失效而产生的抖动现象：大量数据要进行替换，程序执行的大部分时间都用于在两级存储器之间移动数据，机器的运行速度接近于只有第二级存储器的情况，甚至更慢。

局部性原理

局部性原理表现在以下两个方面：

• 时间局部性 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
• 空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。

虚拟存储

虚拟存储器的分块

虚存的分块方式：虚存的分块可以分为段式、页式和段页式三种。采用哪一种分块方式对操作系统的性能具有很大的影响。 ①页式分块：页式虚存把空间划分为大小相同的页面，其中每个存储单元的地址都是单一、固定长度的地址字，由页号和页内位移两部分组成。 ②段式分块：往往是按照程序的逻辑结构进行划分，段的长度可变。这种方式中地址一般用两个字表示：一个是段号，另一个是段内位移。 ③段页式分块：同时采用段式和页式，也就是将每个段划分为若干个页面。这种方式不仅保持了段作为逻辑单元的优点，又简化了替换操作的实现。

---

第三章 用户接口与作业管理

作业的概念，作业级接口与程序级接口

1. 作业的概念

作业就是用户一次请求计算机系统为用户完成任务所做工业的综合

2. 接口

• **程序级接口：**系统为用户在程序一级提供有关服务而设置的，由一组系统调用命令组成
• 作业级接口: 系统为用户提供的各种命令接口，用户利用这些操作命令来组织和控制作业的执行或管理计算机系统

JCB；作业的状态及转换

作业状态及转换

一个作业在其生命周期内会经历多个状态，这些状态的变化反映了作业当前所处的阶段。常见的作业状态包括：

• 提交状态：当用户将作业提交给系统后，作业处于提交状态。此时，作业的信息正在进入外存的“作业收容井”中。
• 后备状态：作业已全部进入外存，等待被调度进入内存。在此状态下，系统为作业创建了作业控制块（JCB），记录了作业的各种属性和状态信息。
• 执行状态：作业被选中加载到内存中开始执行。这个阶段可能包括编译、链接、装入和实际运行等子阶段。一旦作业进入了执行状态，它就处于宏观上的运行中。
• 完成状态：作业已经执行完毕，所有资源已经被回收，作业结果可能已经输出。此时作业处于完成状态，等待最终的数据输出或删除。

作业控制块(JCB)

作业控制块（JCB）是作业在系统中存在的唯一标志，它记录了与该作业有关的所有必要信息。JCB的内容通常包含以下方面：

• 作业标识：如作业号、用户名等。
• 作业类型：CPU繁忙型、I/O繁忙型、批量型、终端型等。
• 作业状态：反映作业当前的状态，如后备、执行、完成等。
• 资源需求：作业所需的内存大小、I/O设备类型和数量等。
• 优先级：根据作业的性质设定的优先级。
• 其他信息：如预计运行时间、实际运行时间、收费标准等。

JCB对于作业管理和调度至关重要，因为它是操作系统了解作业需求并据此进行决策的基础。每当作业的状态发生变化时，相应的JCB也会更新，以反映最新的作业状态。

作业调度算法：FCFS/SJF/HRN

1. 先来先服务

原理：按照作业到达系统的顺序进行调度，即最早到达的作业最先得到处理。

优点：实现简单，公平性好。 缺点：如果长作业位于队首，则短作业可能需要等待很长时间，导致平均周转时间较长。

例题： 假设有以下四个作业按如下时间提交给系统：

• 作业A：提交时刻10:00，运行时间2小时
• 作业B：提交时刻10:06，运行时间1小时
• 作业C：提交时刻10:15，运行时间0.25小时

使用FCFS算法计算它们的平均周转时间和平均带权周转时间。

解答：

• 作业A开始时间10:00，结束时间12:00，周转时间2小时，带权周转时间1
• 作业B开始时间12:00，结束时间13:00，周转时间2.9小时，带权周转时间2.9
• 作业C开始时间13:00，结束时间13:15，周转时间3小时，带权周转时间12

平均周转时间 = (2 + 2.9 + 3) / 3 ≈ 2.63 小时 平均带权周转时间 = (1 + 2.9 + 12) / 3 ≈ 5.30 小时

2. 短作业优先

原理：选择估计运行时间最短的作业优先执行。

优点：可以减少平均等待时间，提高系统响应速度。 缺点：可能导致长作业长时间得不到执行，造成“饥饿”现象。

例题： 假设同样有上述三个作业，使用SJF算法计算它们的平均周转时间和平均带权周转时间。

解答：

• 作业A开始时间10:00，结束时间12:00，周转时间2小时，带权周转时间1
• 作业B开始时间12:15，结束时间13:15，周转时间3.1小时，带权周转时间3.1
• 作业A开始时间12:00，结束时间12:15，周转时间2小时，带权周转时间8

平均周转时间 = (2 + 3.1 + 2) / 3 小时 平均带权周转时间 = (1 + 3.1 + 8) / 3 小时

3. 高响应比优先

原理：根据作业的响应比来决定调度顺序，响应比定义为 (等待时间 + 作业长度) / 作业长度。

优点：平衡了等待时间和作业长度，防止饥饿现象。 缺点：需要动态计算响应比，增加了系统开销。

例题： 假设有四个作业提交给系统，其信息如下：

• 作业D：提交时刻8:00，运行时间2小时
• 作业E：提交时刻8:30，运行时间0.5小时
• 作业F：提交时刻9:00，运行时间0.1小时
• 作业G：提交时刻9:30，运行时间0.2小时

使用HRRN算法计算它们的平均周转时间和平均带权周转时间。

解答：

• 作业D完成时间10:00
• 作业F完成时间10:06
• 作业E完成时间10:36
• 作业G完成时间10:46

作业D周转时间2小时，带权周转时间1 作业F周转时间0.1小时，带权周转时间1 作业E周转时间1.5小时，带权周转时间3 作业G周转时间1.2小时，带权周转时间6

平均周转时间 = (2 + 0.1 + 1.5 + 1.2) / 4 = 1.2 小时 平均带权周转时间 = (1 + 1 + 3 + 6) / 4 = 2.75 小时

系统调用（访管中断）

访管指令是一条可以在用户态（又称目态）下执行的指令。在用户程序中，因要求操作系统提供服务而有意识地使用访管中断，从而产生一个中断事件（自愿中断），将操作系统转换为核心态，称为访管中断。访管中断由访管指令产生，程序员使用访管指令向操作系统请求服务。

为什么要在操作系统中引入访管指令

这是因为用户程序只能在用户态（目态）下运行，如果用户程序想要完成在用户态下无法完成的工作，该怎么办？

解决这个问题要靠访管指令。访管指令本身不是特权指令,其基本功能是 让程序拥有“自愿进管”的手段，从而引起访管中断。 当处于用户态的用户程序使用访管指令时，系统根据访管指令的操作数执行访管中断处理程序，访管中断处理程序将按系统调用的操作数和参数转到相应的例行子程序。完成服务功能后，退出中断，返回到用户程序断点继续执行。

tip

访管指令是非特权指令，是程序员主动获得使用特权指令的手段。

---

第四章 进程管理

1. 程序的顺序执行的特点；多道程序并发执行的特点

顺序执行时

1.顺序性：严格的按照顺序执行

2.封闭性：程序运行时独占全机资源 资源状态只有本程序才能改变它，程序一旦开始执行，不受外界影响

3.可再现性：无论如何执行 都可缺获得相同的结果

并发执行时

1.间断性：由于资源有限，并发执行的程序存在相互制约的关系

2.失去封闭性：并发执行的程序共享计算机资源，这些资源的状态由这些程序改变

3.不可再现性：并发执行的程序执行的顺序不同可能有不同的执行结果

3个点分别对立

1. 顺序性 -> 间断性, 程序执行相互制约
2. 封闭性 -> 失去封闭性, 资源状态随程序进行改变
3. 可再现性 -> 不可再现性, 每次执行都可能结果不同

2. 进程的状态及变迁

进程

进程是指一个 具有独立功能的程序在某个数据集合上的一次动态执行过程，它是 操作系统进行资源分配和调度的基本单元。一次任务的运行可以激活多个进程，这些进程相互合作来完成该任务的一个最终目标

进程的三个状态

进程一般分为三个状态:

• 运行（running）态：进程占有处理器正在运行的状态。进程已获得CPU，其程序正在执行
• 就绪（ready）态：进程 具备运行条件，等待系统分配处理器以便运行 的状态。当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行，进程这时的状态称为就绪状态
• 等待（wait）态：又称阻塞态或睡眠态，指进程 不具备运行条件，正在等待某个时间完成的状态。也称为等待或睡眠状态，一个进程正在等待某一事件发生（例如请求I/O而等待I/O完成等）而暂时停止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态。

状态变迁

1. 运行态 → 等待态 当一个运行程序 因某件时间受阻 时，如申请资源被占用、启动数据传输未完成等，其状态会变迁； 详细点就是 请求外部传输：一个程序在运行时需要进行打印，提出外部请求使用打印机，然后从运行态变迁为等待态；

2. 等待态 → 就绪态 当所等待的事件发生时，如得到被申请资源、数据传输完成，其状态会由等待变为就绪；

3. 就绪态 → 运行态 当一个就绪程序获得CPU时，其状态就由就绪态变为运行态；

4. 运行态 → 就绪态 运行进程被剥夺处理器资源； 在分时操作系统中，该程序 用完了系统分配的时间片； 或者 出现高优先级别的其他进程；

5. 就绪态 → 等待态 不是全错，还是有可能的； 可能有，只是 现在的OS一般都没有这个变迁；

6. 等待态 → 运行态

   全错；这个变迁是绝对没有的；

3. 进程调度与时间片

例题

4. 进程控制

原语

原语是在管态(管理状态)下执行、完成系统特定功能的程序。

原语是一种特殊的程序段，具有 “原子性” ，即要么不执行要么执行，一旦执行，其过程将不允许被中断。

进程控制原语

系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程在各个状态之间的转换。

用于实现多进程高效率并发执行、协调和共享资源的目的。

• 阻塞原语:

  • 进程的阻塞是要靠调用阻塞原语来实现。
  • 阻塞原语在进程期待某事件发生，但没有发生时(或所需资源尚不具备时)，被该进程调用来阻塞自己。(所以可以发现，阻塞常常是一种自我阻塞的过程，类似于人的欲望得不到满足，就降低要求)

• 唤醒原语:

  • 事件发生进程 和 被唤醒进程 之间是合作关系，唤醒原语既可被系统进程调用，也可被事件发生进程调用。(当然，进程不能够被自己唤醒，需要 “外界的激励” )

• 挂起原语与激活原语:

  • 挂起原语即可由进程自己也可由其他进程调用，但激活原语却只能由其他进程调用。

5. pv操作

pv

6. 进程间通信

• 管道(pipe)

  管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。

• 有名管道 (namedpipe)

  有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。

• 信号量(semaphore)

  信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

• 消息队列(messagequeue)

  消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

• 信号 (sinal)

  信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

• 共享内存(shared memory)

  共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。

• 套接字(socket)

  套接口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同设备及其间的进程通信。

线程

线程（最小运行单位、非基础分配单位）

7. 死锁

产生条件

1. 互斥条件 ： 指进程对所分配的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直到占有资源的进程用完后释放资源。

2. 占有且等待条件 ： 指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程阻塞，但它不会释放自己已经占有的资源。

3. 非抢占条件 ： 指进程已经获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

满足以上三个条件可能会产生死锁，但如果只有这三个条件，则不一定产生死锁。对死锁的产生，还需要第四个条件。

4. 循环等待条件 : 存在一个封闭的进程链，使得每个资源至少占有此链中下一个进程所需要的一个资源。

解决

1. 破坏“互斥“条件 就是在系统里取消互斥。若资源不被一个进程独占使用，那么死锁是肯定不会发生的。但一般来说，第一个条件是不可能被禁止的，比如打印机等临界资源只能互斥使用。

2. 破坏“占有并等待”条件 就是在系统中不允许进程在已获得某种资源的情况下，申请其他资源，要求进程一次性地请求所有需要的资源，并且阻塞这个进程直到所有请求都同时满足。

   这样做有几个个缺陷，会很低效：

   一个进程可能被阻塞很长时间，等待满足其所有的资源请求，而实际上，只要有一部分资源，它就可以继续执行。 分配给一个进程的资源可能有相当长的一段时间处于不可用状态，并且再次期间，它们不能被其他进程使用。 一个进程可能事先并不会知道它所需要的所有资源。

3. 破坏“非抢占“条件 如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占用的资源，如果有必要，可再次请求这些资源和另外的资源。 另一种方法是，要求两个进程不具有相同的优先级时才能有效预防死锁。即如果一个进程请求当前另外一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。

上述这两种方法只有在资源状态可以很容易地保存和恢复的情况下（如处理器），比较实用。

4. 破坏“循环等待“条件

   循环等待条件可以通过定义资源类型的线性顺序来预防。如果一个进程已经分配到了R 类型的资源，那么接下来请求的资源只能是那些排在R 类型之后的资源类型。

8. 银行家算法

银行家算法

---

第五章 存储管理

1. 页面置换算法

页面置换算法

存储管理的目的

在计算机系统中，存储管理的主要目的是有效地利用存储空间，确保系统在运行过程中有足够的存储空间，同时也要避免存储空间的浪费

地址映射

• 静态: 程序装入时由操作系统完成逻辑地址到物理地址的映射
• 动态: 程序执行过程中把逻辑地址转换为物理地址

虚拟存储器

借助辅存在逻辑上扩充内存，解决内存不足的问题

过程：

• 迁入：将要运行的部分装入内存
• 迁出：把不运行的部分暂时放在辅存

前提

短时间内进程不运行的部分往往占大部分

存储管理

存储管理

碎片回收

• 碎片紧凑

  • 实现方式：通过移动分配给进程的内存分区，以合并外部碎片。

• 分区对换

  • 抢占并回收处于等待状态进程的分区，以增大可用内存空间

• 伙伴系统

  • 空闲块按大小和起始位置组织称二维数组；
  • 初始状态时，只有一个大小为的空闲块；

  分配过程：

  • 由小到大在空闲块数组中找最小的可用空闲块；
  • 如果空闲块过大，对可用空闲块进行二等分，一个放入空闲块列表，另一块继续比较，直到得到合适的可用空闲块

2. 段页式内存

段页式内存

覆盖与交换

1、内存覆盖（Overlay）

在早期的计算机系统中，主存容量很小。虽然主存中仅存放一道用户程序，但是存储空间放不下用户进程的现象也经常发生。这一矛盾可以用覆盖技术来解决。覆盖的基本思想是：由于程序运行时并非任何时候都要访问程序及数据的各个部分（尤其是大程序）， 因此可以把用户空间分成一个固定区和若干个覆盖区。将经常活跃的部分放在固定区，其余部分按调用关系分段。首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统再将其调入覆盖区，替换覆盖区中原有的段。

2、内存交换（Swapping）

交换（对换）的基本思想是：

---- 把处于等待（阻塞）状态（或在CPU调度原则下被剥夺运行权利）的程序（进程）从内存移到辅存（外存），把内存空间腾出来，这一过程又叫换出。把准备好竞争CPU运行的程序从辅存移到内存，这一过程又称为换入。中级调度（策略）就是釆用交换技术。

---

第六章 文件系统

文件结构的分类

按文件是否有结构分类，可以分为无结构文件、有结构文件两种。

• 无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如：Windows操作系统中的.txt文件。

• 有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID），根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。

1. 有结构文件的逻辑结构

顺序文件

顺序文件：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。

定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取；若能再保证记录的顺序结构，则可实现快速检索（即根据关键字快速找到对应记录）

一般来说，考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。可见，顺序文件的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单）

索引文件

索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。

另外，可以用不同的数据项建立多个索引表。如：

学生信息表中，可用关键字“学号”建立一张索引表。也可用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。

（Eg：SQL就支持根据某个数据项建立索引的功能）

索引顺序文件

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

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

若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找（这里指的并不是定长记录、顺序结构的顺序文件），平均须查找5000个记录。

若采用索引顺序文件结构，可把10000个记录分为√10000 = 100 组，每组100个记录。则需要先顺序查找索引表找到分组（共100个分组，因此索引表长度为100，平均需要查50次），找到分组后，再在分组中顺序查找记录（每个分组100个记录，因此平均需要查50次）。可见，采用索引顺序文件结构后，平均查找次数减少为50+50 = 100次。同理，若文件共有106个记录，则可分为1000个分组，每个分组1000个记录。根据关键字检索一个记录平均需要查找500+500 = 1000次。这个查找次数依然很多，如何解决呢？

多级索引顺序文件

为了进一步提高检索效率，可以为顺序文件建立多级索引表。例如，对于一个含106个记录的文件，可先为该文件建立一张低级索引表，每100个记录为一组，故低级索引表中共有10000个表项（即10000个定长记录），再把这10000个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有100个表项。

2. 文件目录

文件目录与FCB

FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项。FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。最重要，最基本的还是文件名、文件存放的物理地址。

【FCB实现了文件名和文件之间的映射。使用户（用户程序）可以实现“按名存取”】

---

第七章 设备管理

1. 设备的分类；设备控制（I/O 4方式）；设备管理的功能；高速缓存
2. 虚拟设备技术；SPOOLing技术；（输入井输出井，预输入缓输出）
3. 设备独立性