2021操作系统王道

概述

以选择题为主，重点掌握操作系统的功能、运行环境和提供的服务。

操作系统的基本概念

操作系统的概念

操作系统（Operating System，OS）是指控制和管理整个计算机系统的硬件和软件资源，合理的组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供提供方便接口与环境的程序集合。

操作系统是计算机系统中最基础的系统软件。

操作系统的特征

1. 并发
   两个或者多个事件在同一时间间隔内发生（对比并行）

2. 共享
   (1).互斥共享方式
   一段时间内只允许一个进程访问资源（这样的资源被称为独占资源或者临界资源）
   (2).同时访问方式
   宏观上同时访问，微观上交替使用资源

3. 虚拟
   虚拟处理器：利用多道计数程序设计技术把一个物理上的CPU虚拟为多个逻辑上的CPU。
   虚拟存储器：将一台机器的物理存储器变为虚拟存储器，以便从逻辑上扩充存储器的容量。

4. 异步

操作系统的目标和功能

1. 操作系统作为计算机系统资源的管理者
   (1). 处理器管理(进程管理)
   功能：进程控制、进程同步、进程通信、死锁处理、处理机调度（采用先来先去调度等方法使用资源）等。
   (2). 存储器管理
   功能：内存分配和回收、地址映射、内存保护与共享、内存扩充等。
   (3). 文件管理
   功能：文件存储空间的管理、目录管理、文件读写管理和保护等。
   (4).设备管理
   功能：缓冲管理、设备分配、设备处理和虚拟设备等。
2. 操作系统作为用户和计算机硬件系统之间的接口
   • 命令接口
     • 联机命令接口：
     • 脱机命令接口：
   • 程序接口：由一组系统调用——又名广义指令 组成。
3. 操作系统作为扩充机器

操作系统的发展与分类

手工操作阶段

此阶段无操作系统
有两个突出的缺点：

1. 用户独占，资源利用率低。  
2. CPU需要手工操作，利用不充分。

批处理阶段

进程管理

进程与线程

进程的概念和特征

1. 进程：
   进程控制块（PCB）是进程存在的唯一标志
   定义：

• 进程是程序的一次执行
• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
• 进程是具有独立功能的程序在一个数据集合上运行的过程，是系统资源分配和调度的一个独立单位

1. 进程的特征(理解)：

• 动态性，进程的最基本特征
• 并发性，多个进程实时共存在内存中，在一段时间内共同运行
• 独立性，进程实体是一个能独自运行，独自获取资源，独立接受调度的基本单位。（未建立PCB->非独立实体）
• 异步性。进程会相互制约，即各进程独自的，按不可预知的速度推进任务。（操作系统需要配套进程同步机制）
• 结构性。

进程的状态和转换

• 运行态
• 就绪态
• 阻塞态（等待态）
• 创建态
• 结束态

进程控制

1. 进程的创建
   父进程与子进程：允许一个进程创建另一个进程，被创建者为子进程。
   • 子进程可以继承父进程的资源，在子进程消失时资源返回父进程
   • 父进程终止时，会同时撤销所有子进程
2. 进程的终止
3. 进程的阻塞(Block)和唤醒(Wakeup)
   • 进程阻塞是进程自身的一种主动行为，只能从运行态变为阻塞态，由自身调用
   • 唤醒是由一个被唤醒进程合作合作其他相关进程调度，进度就绪态准备运行
4. 进程切换
   进程切换与进程调度不同，调度一种决策行为，决定分配方式，切换是一种执行行为，完成分配的动作。

进程的组织

1. 进程控制块(PCB)
   ：进程实体的一部分，也是进程存在的唯一标志。操作系统通过管理PCB管理进程。
2. 程序段：
   程序可以被多个进程运行，一个进程也可以运行多个程序。
3. 数据段
   ：可能是运行对应程序需要的原始数据，也可能是中间变量或最终结果。

进程的通信

低级通讯方式：P/V操作
高级通讯方式：

1. 共享内存：进程通信之间存在一个可以直接访问的共享空间。
   • 同步互斥工具：P/V操作
   • 操作系统只负责提供共享空间和同步互斥工具
   • 低级方式的共享通过数据结构，高级方式的共享通过存储区
   • 进程不能直接访问对方的数据，只能通过共享空间间接访问传递
2. 消息传递：利用操作系统提供的消息传递方式，以消息（Message）为单位。
   • 直接通信方式：直接把消息发给接受进程，接受进程从消息缓冲队列获取信息。
   • 间接通信方式：邮箱。发送方发至中间实体，接受方从实体获取信息。
3. 管道通信：pipe通信。
   • 在进程之间创建一个管道(pipe文件)，以字符流的形式读写数据
   • 管道提供三种能力：互斥、同步、确认对方存在
   • Linux中，write()将数据写入管道，read()从管道读出数据。管道变满时，write()进入堵塞，管道变空时，read()进入堵塞。
   • 要实现双向通信需要两个管道

线程和多线程

1. 线程的基本概念
   线程是一个基本的CPU执行单元，也是程序执行的最小单元
   • 具有运行、阻塞、就绪三态。
   • 系统独自调度和分配的基本单位
   • 线程自身不具有资源，可以和同一进程下的其他线程共享进程的资源
2. 线程和进程的比较
   • 调度：没有线程的系统中，进程是独立调度和拥有资源的基本单位；引入线程后，线程是独立调度的基本单位，进程是拥有资源的基本单位。
   • 拥有资源。线程自身没有资源，可以访问其隶属进程的系统资源。
   • 并发性：进程可以并发，线程也可以并发
   • 系统开销：进程的创建和撤销设计系统资源的分配与回收，开销大。类似的，进程切换时需要保持CPU环境和新环境的设置等，同一进程内线程则非常容易实现，甚至不需要系统干预。
   • 地址空间和其他资源（打开的文件）：不同进程的地址空间相互独立，同一进程内的线程共享资源，不同进程的线程互相不可见。
   • 通信方面：进程通信（IPC）通过进程同步和互斥实现，线程可以通过进程内的全局变量。
3. 线程的属性
4. 线程的实现方式
   • 用户级：工作由程序完成
   • 内核级：工作由内核完成
5. 多线程模型：用户级线程对内核级线程的连接方式
   • 一对一模型：每个用户级对应一个内核级，并发能力强但开销大
   • 多对一模型：多个用户及对应一个内核级，效率高，但一个线程阻塞->进程堵塞，且不能运行在多处理机上。
   • 多对多模型：n个用户级对面m个内核级m<=n。集前两模型之所长。

处理机调度

调度的概念

1. 调度的基本概念：
   对处理机进进行分配，让就绪队列按一定的算法选择一个进程并将处理机分配给他运行，以实现进程的并发执行。
2. 调度的层次：
   • 高级调度(作业调度)
   • 中级调度(内存调度)：挂机(移入外存)不能运行的进程(挂起态)，调入外存准备就绪的进程
   • 低级调度(进程调度)
3. 联系：
   • 作业调度为进程活动做准备，中级调度将暂时不能运行的进程挂起
   • 频率：高级调度<中级调度<低级调度
   • 进程最基本的，最不可或缺的

调度的时机、切换和过程

进程调度方式

1. 非剥夺调度方式

   • 当进程在运行时，不会被优先性更高的进程抢占而进入就绪状态，会继续执行
   • 适用批处理系统，系统开销小，实现简单

2. 剥夺调度方式(抢占方式)

   • 当有优先级更高的进程进入就绪队列时，会使正在运行的进程进入就绪态，高优先级的先运行

调度的基本准则

调度的评价准则：

1. CPU利用率
2. 系统吞吐量
3. 周转时间
4. 等待时间
5. 响应时间

典型的调度算法

1. 先来先去服务(FCFS)
2. 短作业优先服务(SJF)
3. 优先级调度算法
   • 剥夺式和非剥夺式
   • 静态优先级和动态优先级
4. 高响应比优先调度算法
   响应比$R_P$=${等待时间+要求服务时间 \over 要求服务时间}$
5. 时间片轮转调度算法
6. 多级反馈队列调度算法

进程同步

利用PV操作解决进程同步问题

进程同步的基本概念

1. 临界资源： 具有互斥属性的共享公共资源，一次只能有一个进程使用
2. 同步：直接制约关系，指为了完成某种任务而建立的两个或多个进程
3. 互斥：间接制约关系，不同进程需要使用同一临界资源
   有四个准则：
   • 空闲让进：临界区空闲时应让请求进程进入
   • 忙则等待：临界区有进程时让请求资源等待
   • 有限等待：让请求进程的等待时间有限制
   • 让权等待：请求进程无法进入临界区时应立即释放

实现临界区互斥的基本方法

1. 软件实现方法
   • 单标志法:违背空闲让进
     只能让两个进程交替进入临界区，若任一进程完成后离开，另一进程无法进入

     int turn = 0; 设置公共变量用于标志
     P1                            P2
     while(turn ！= 0);            while(turn != 1);
     进入区;                       进入区;
     临界区;                       临界区;
     退出区(tuen = 1);             退出区(tuen = 0);
     剩余区;                       剩余区;

   • 双标志法先检查:违背忙则等待

     int flag[]; 设置公共变量用于标志
     P1                            P2
     while(flag[j]);               while(flag[i]);
     flag[i]=TRUE;                 flag[j]=true;
     进入区;                        进入区;
     临界区;                        临界区;
     退出区(flag[i]=FALSE);         退出区(flag[j]=FALSE);
     剩余区;                        剩余区;

   • 双标志法后检查：可能会出现饥饿现象

     int flag[]; 设置公共变量用于标志
     P1                            P2
     flag[i]=TRUE;                 flag[j]=true;
     while(flag[j]);               while(flag[i]);
     进入区;                        进入区;
     临界区;                        临界区;
     退出区(flag[i]=FALSE);         退出区(flag[j]=FALSE);
     剩余区;                        剩余区;

   • Peterson’s Algorithm

     int flag[]; 设置公共变量用于标志
     P1                            P2
     flag[i]=TRUE;turn=j;           flag[j]=true;turn=i;
     while(flag[j]&&turn==j);       while(flag[i]&&turn==i);
     进入区;                        进入区;
     临界区;                        临界区;
     退出区(flag[i]=FALSE);         退出区(flag[j]=FALSE);
     剩余区;                        剩余区;

2. 硬件实现方法(低级方法/元方法)

信号量

信号量机制可以用来解决同步和互斥问题，用两个原语wait(S)和signal(S)完成，也可记为P和V。

1. 整型信号量：一个被用于表示资源数目的整型变量S

   wait(S){
      while(S<=0);
      S=S-1;
   }
   signal(S){
      S=S+1;
   }

   未遵循让权等待
2. 记录型信号量:遵循让权等待

   typedef struct{      //记录型信号量的结构
      int value;        //代表资源数目的整型变量
      struct process *L; //进程链表，链接所有等待的进程
   } semaphore;
   void wait(semaphore S) {  //申请资源
      S.value--;
      if(s.value<0>){
         add this process to S.L;
         block(S.L);
      }
   }
   void signal(semaphore S){  //释放资源
      S.value ++;
      if(S.value<=0){
         remove a process P from S.L;
         wakeup(P);
      }
   }

3. 利用信号量实现同步

   semaphore S=0;    //初始化信号量
   p1(){
      x1;             //执行语句
      V(S);          //同步p2，任务x1已完成
      y1;             //后续语句y
   }
   p2(){
      x2;             //执行语句
      P(S);          //收到x1完成信息，执行y2
      y2;
   }

4. 利用信号量实现互斥

   semaphore S=0;    //初始化信号量
   p1(){
      x1;            
      P(S);          //加锁
      y1;            
      V(S);          //解锁
   }
   p2(){
      x2;
      P(S);          //加锁
      y2;            
      V(S);          //解锁
   }

5. 利用信号量实现前驱关系

管程

1. 管程
   • 代表共享资源的数据结构，以及由对该共享数据结构十十操作的一组过程所组成的资源管理程序，称为管程。
   • 管程由四部分组成
     • ①名称
     • ②局部于管程内部的共享数据结构说明
     • ③对该数据结构的一系列操作
     • ④于局部于管程内部的共享数据结构的初始化
   • 管程一次只允许一个进程访问

2. 条件变量

   monitor Demo{
      共享数据结构(临界区) S;
      condition x;            //条件变量x
      init_code(){};          //初始化
      take_away(){
         if(S<0)x.wait();
         else
         do();                
      }
      give_pack(){S++};
      if(有进程在等待) x.signal;//唤醒阻塞进程
   }

   同步问题

3. 生产-消费者问题

4. 读者-作者问题
5. 哲学家问题
6. 吸烟问题

死锁

死锁的概念

1. 死锁的定义
   多个进程因竞争资源造成的一种僵局(互相等待)，若无外力，则进程都将无法前进
2. 产生原因
   • 系统资源的竞争(不可剥夺资源)
   • 进程推进顺序非法
     • 两个进程$P_1$P_2$都需要资源$R_1$R_2$，$P_1$申请了$R_1$，$P_2$申请了$R_2$，就会因为互相占用而阻塞。
     • 信号量等待：进程A等待进程B的消息，进程B等待进程A的消息，互相等待陷入死锁。
   • 产生的必要条件
     • 互斥条件
     • 不剥夺条件
     • 请求并保持条件
     • 循环等待条件

死锁的处理策略

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

死锁预防

1. 破坏互斥条件
2. 破坏不剥夺条件
3. 破坏请求并保持条件
4. 破坏循环等待条件

死锁避免

1. 系统安全状态
2. 银行家算法

   request_i[j]=k ,表示进程i在某一时间运行中向系统请求的j类资源k个。
   n：进程数目 m：资源种类
   数据结构：
   可获取资源数组:available，含m个元素的数组，available[j]=k表示现在有j类资源k个。
   最大需求矩阵Max[n,m],Max[i,j]=K表示进程ij类资源，最大需求为k
   分配矩阵：Allocation[n,m]，Allocation[i,j]=K表示进程i当前已获得的j类资源的数目为k。
   需求矩阵Need[n,m]，Need[i,j]=K表示进程i还需要的j类资源的数目为k。
   算法：
   if(request_i[j]<=Need[i,j])
      if(request_i[j]<=available[j]){
         available=available-request_i;
         Allocation[i,j]=Allocation[i,j]+request_i[j];
         Need[i,j]=Need[i,j]-request_i[j];
      }
   安全性算法

3. 安全性算法

   设变量work初始化为available;
   步骤一：设安全序列L为空
   步骤二：在need矩阵中寻找一个向量比work小的行，加入安全序列，不然跳转步骤四
   步骤三：对该行代表的进程P_i进行执行银行家算法，此时将顺利执行，执行完成后work=work+Allocation[i]；
   步骤四：若安全队列非空，则系统安全，不然不安全。

死锁的检测和解除

内存管理

内存管理概念

内存管理的基本原理和要求

操作系统对内存的划分和动态分配，就是内存管理的概念。
内存的功能：

• 内存空间的分配和回收
• 地址转换
• 内存空间的扩充
• 存储保护
  1. 程序的装入和链接
• 三步：编译，链接，装入
• 链接分为 静态链接、动态链接、运行时动态链接三种 、
• 内存的装入方式
  • 绝对装入
  • 可定位重装入
  • 动态运行装入(动态重定位)
    1. 逻辑地址空间和物理地址空间
       *地址重定位：逻辑地址转换为物理地址的过程
    2. 内存保护
• 上下限寄存器：记录用户作业在主存中的上下边界，当CPU访问时，判断是否越界
• 重定位寄存器(基址寄存器)和界地址寄存器(限长寄存器)

连续分配管理方式

1. 单一连续分配
   • 优点：简单，无外部碎片，无需额外技术支持，可用覆盖
   • 缺点：只适用单用户单任务的操作系统，有内部碎片，存储器利用率低
2. 固定分区分配
   • 分区大小相同
   • 分区大小不同
   • 检索表
3. 动态分区分配
   • 外部碎片
   • 紧凑法

非连续分配管理方式

1. 基本分页存储管理方式
   • 分页存储的几个基本概念
     • 页面和页面大小：进程中的块被称为页，内存中的块被称为页框。进程在执行时需要申请主存空间——为每个页面分配可用页框，这使页和页框一一对应。页面太小会使页数太多，页面太大会降低内存利用率，增加业内碎片。页面大小应该是2的整数幂。
     • 地址结构：地址结构有两部分，页号和业内偏移量。在下表例子中，页面大小是$2^{12}=4KB$,页的数量是$2^{20}$。
       | 31 …..12 |11 ………. 0|
       | :————: | :—————-: |
       | 页号P | 页内偏移量 |
     • 页表：页表由页号和块号组成，为了便于方便在内存中查找对应的物理块，系统为每个进程建了一张表，用于记录页面在内存中的对应块号，页表一般存于内存中。与地址结构区分。
   • 基本地址变换机构
     • 计算页号P和页内偏移量W（如果用十进制数手算，则P=A/L，W=A%L；但是在计算机实 际运行时，逻辑地址结构是固定不变的，因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量）
     • 比较页号P和页表长度M，若P>=M，则产生越界中断，否则继续执行。（注意：页号是从0开始的，而页表长度至少是1，因此P=M时也会越界）
     • 页表中页号P对应的页表项地址=页表起始地址F+页号P*页表项长度，通过页表项地址找到这个页表项，并取出该页表项内容b，即为内存块号。（注意区分页表项长度、页表长度、页面大小的区别。页表长度指的是这个页表中总共有几个页表项，即总共有几个页；页表项长度指的是每个页表项占多大的存储空间；页面大小指的是一个页面占多大的存储空间），页面大小L
     • n计算E=b*L+W，用得到的物理地址E去访存。（如果内存块号、页面偏移量是用二进制表示的，那么把二者拼接起来就是最终的物理地址了）

       例：若页面大小L为1K字节，页号2对应的内存块号b=8，将逻辑地址A=2500转换为物理地址E。等价描述：某系统按字节寻址，逻辑地址结构中，页内偏移量占10位(说明一个页面的大小为2^10 B=1KB)，页号2对应的内存块号b=8，将逻辑地址A=2500转换为物理地址E。
       解：
       计算页号、页内偏移量
       页号P=A/L=2500/1024=2；页内偏移量W=A%L=2500%1024=452
       根据题中条件可知，页号2没有越界，其存放的内存块号b=8（容易被忽略的步骤）
       物理地址E=b*L+W=8*1024+452=8644在分页存储管理（页式管理）的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。
       因此，页式管理中地址是一维的。即，只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统这个逻辑地址中，页内偏移量占多少位。

   • 具有快表的地址变换机构：局部定理
   • 两级页表：对页表分级
2. 基本分段存储管理方式：如何分段在编程时决定
   • 分段
   • 段表
   • 地址变换机构
   • 段的共享和保护
     • 多道环境下，多个子程序和应用程序被多个用户使用。如果每个用户进程或作业都在内存保留它们共享的程序和数据的副本，会极大地浪费内存空间。最好的办法是内存中只保留一个副本，供多个用户使用，称为共享。如果用户进程或作业需要共享内存中的某段程序或数据，只要使用相同的段名，在新的段表中填入已存在于内存之中的段的起始地址，并置以适当的读写控制权，就可做到共享一个逻辑上完整的内存段信息。
     • 保护
       • 地址越界保护：段表中的段长项 VS. 虚拟地址中的段内相对地址。若段内相对地址大于段长，系统产生保护中断。不过，在允许段动态增长的系统中，段内相对地址大于段长是允许的。为此，段表中设置相应的增补位以指示该段是否允许动态增长。
       • 存取方式控制保护：除了存入、读取的控制保护之外，还需要考虑数据共享的保护。在段表中设立相应的共享位用于判断该段是否正被某个进程调用。
3. 段页式管理方式
   • 一个进程只有一个段表，可以有多个页表

     虚拟内存管理

虚拟内存的基本概念

1. 传统存储管理的特征
   • 一次性：作业必须一次全部进入内存，才能开始运行
   • 驻留性：作业装入后会一直在内存中驻留知道作业结束
2. 局部性原理
   • 时间局部性：运行过的程序很可能被再次运行，被访问过的数据很可能被再次访问(循环操作)
   • 空间局部性，访问某一数据时，其周围数据也可能被访问(数组，簇)
3. 虚拟存储器的定义和特征
   • 多次性：作业无需全部进入内存，允许多次调入
   • 对换性：作业无需常驻内存，允许调入调出
   • 虚拟性：内存大小实际没变，但用户使用的远大于实际
4. 虚拟内存技术的实现
   • 请求页式存储管理
   • 请求段式存储管理
   • 请求段页式存储管理

请求分页管理方式

页号	物理块号	状态位P	访问字段A	修改位M	外存地址

1. 页表机制
   • 状态位P：该页是否已调入内存
   • 访问字段A：记录被访问次数，或者上次访问时间
   • 修改位M：调入内存后是否被修改
   • 外存地址：该页在外存上的地址
2. 缺页中断机构
   • 属于内部中断
   • 一条指令执行期间可能多次中断
   • 中断后在外村调入缺页，调页完成唤醒
3. 地址变换机构
   • 快表

页面置换算法

1. 最佳置换算法(OPT)
   • 理论算法，无法实现
   • 注意与LRU区别
2. 先进先出算法(FIFO)
   • Belady算法(只有FIFO有)，增加内存块不一定会使缺页中断减少，反而增加。
3. 最近最久未使用算法(LRU)
4. 时钟算法(CLOCK)

页面分配策略

1. 驻留集大小
2. 调入页面的时机
3. 从何处调入页面

抖动

抖动(颠簸)：刚刚进入内存的页面马上又要换出主存，刚刚换出的页面要马上进入内存。

主要原因：某个进程频繁访问的页面数目高于可用的物理页帧数目。

工作集

地址翻译

文件管理

文件系统基础

文件的概念

1. 文件的定义：关于文件无严格的定义，是用户进行的输出、输入过程中的基本单位，从自底向上的定义，文件有以下结构：
   • 数据项
     • 基本数据项：数据中可命名的最小逻辑数据单位，即原子数据。(单一的姓名、日期、证件号等)
     • 组合数据项：由多个基本数据项组成
   • 记录：记录一组相关的数据项的集合(一个人的性命、日期、证件号)
   • 文件：创建者定义的一组信息的集合
     • 有结构文件(记录式文件)：日常见到的
     • 无结构文件(流式文件)：二进制文件或者字符文件
2. 文件的属性(通常而言)
   • 名称：文件名唯一，容易读取
   • 标识符：不可读
   • 类型
   • 位置
   • 大小
   • 保护：对文件进行保护的访问控制信息
   • 时间、日期和用户标识
3. 文件的基本操作
   • 创建文件
   • 读文件
   • 写文件
   • 文件重定位(移动文件位置)
   • 删除文件
   • 截断文件：文件属性不变，清空文件内容
4. 文件的打开和关闭

文件的逻辑结构

1. 无结构文件(流式文件)
   最简单的文件组织形式。操作方便，但搜索等应用实践不简单。
2. 有结构文件(记录式文件)
   • 顺序文件：文件按一定顺序排布
   • 索引文件：建立索引表(索引表是是定长的顺序文件)，记录索引号(key)和文件位置(逻辑地址/指针)，如果是可变长文件，还要继续文件长度
   • 索引顺序文件：索引表可以无序，索引表指向的一组文件时顺序文件
   • 直接文件或者散列文件：利用哈希查找分布的文件(可能有冲突——不同文件哈希值相同)

目录结构

1. 文件控制块和索引节点
   • 文件控制块(FCB)：用来存放控制文件需要的各种信息的数据结构。
   • 索引结点
2. 目录结构
   • 操作：搜索、创建文件、删除文件、显示目录、修改目录
   • 单级目录结构
   • 两级目录结构
   • 多级目录结构
   • 无环图目录结构(实现文件共享)

文件共享

1. 基于索引结点的共享方式(硬链接)
2. 利用符号链实现的文件共享(软链接)

文件保护

1. 访问类型
   • 读
   • 些
   • 执行
   • 添加
   • 删除
   • 列表清单
2. 访问控制
   • 为每个文件和目录增加一个访问控制列表(ACL),规定用户名名及其访问类型
   • 口令
   • 密码

文件系统实现

文件系统层次结构

1. 用户调用接口
2. 文件目录系统
3. 存取控制验证模块
4. 逻辑文件系统与文件信息缓冲区
5. 物理文件系统
6. 辅助分配系统
7. 设备管理程序模块

目录实现

1. 线性列表
2. 哈希表

文件实现——文件分配方式

1. 连续分配
   • 每个文件在磁盘上占用一个连续的块
   • 目录标记文件名、文件开始地址和文件长度
   • 支持顺序访问和直接访问
2. 链接分配
   • 隐式链接
     1. 每个文件对应一个磁盘块的链表，磁盘块的末尾指向下一个磁盘块，目录包括指向第一个磁盘块和最后一个磁盘块的指针。
     2. 无法直接访问盘块，只能通过指针顺序访问，而且指针会消耗存储空间
   • 显示链接
     1. 创建一个分配表FAT，记录磁盘块号和接下来的块号，-1表示结尾块号，-2表示空闲块号
     2. 在系统启动时写入内存，能显著提高查找速率和减少磁盘访问次数
3. 索引分配

	访问第n条记录	优点	缺点
连续分配	需要访问磁盘一次	顺序存取时速度快，定长文件可根据文件起始地址和访问长度随机访问	文件存储要求连续的存储空间，有碎片，不利于文件动态扩充
隐式链接分配	需要访问磁盘n次	可以解决外存碎片问题，提高外村空间的利用率，动态增长方便	只能通过指针顺序访问，查找效率低，而且指针会消耗存储空间
显式链接分配
索引分配	m需要访问磁盘m次	可以随机访问，文件易于增删	索引表增加空间开销，索引表查找策略对效率影响很大

文件实现——文件存储空间管理

文件存储设备分成许多大小相同的物理块，以块为单位交换信息，文件存储的管理实质上是对空闲块的管理，包括空闲块的组织，分配和回收。

1. 空闲表法——对应连续分配
2. 空闲链表法
3. 位示图法
4. 成组链表法

磁盘组织月管理

磁盘的结构

磁盘调度算法

磁盘的管理

输入/输出(I/O)管理

I/O管理概述

I/O设备

I/O控制方式

I/O子系统的层次结构

I/O核心子系统

I/O子系统概述

I/O调度概念

高速上缓存和缓冲区

SPOOLing技术