操作系统 · 空闲空间管理、目录与作业管理

这就是文件存储设备管理。由于文件存储设备是分成许多大小相同的物理块并以块为单位交换信息，因此文件存储设备的管理实质上是对空闲块的组织和管理问题，包括空闲块的组织、空闲块的分配与空闲块的回收。原文明确写了：有 3 种不同的空闲块管理方法，它们分别是索引法、链接法和位示图法。是三种，先把这个数字锁死。

索引法把空闲块作为文件并采用索引技术；为了有效，索引对应于一个或由几个空闲块构成的空闲区，这样磁盘上每一个空闲块区都对应于索引表中一个条目，这个方法能有效地支持每一种文件分配方法。链接法使用链表把空闲块组织在一起，当申请者需要空闲块时分配程序从链首开始摘取所需的空闲块，反之管理程序把回收的空闲块逐个挂入队尾。链接方法可以按释放的先后顺序链接，也可以按空闲块区的大小顺序链接；后者有利于获得连续的空闲块的请求，但在分配请求和回收空闲块时系统开销多一点。

位示图法是在外存上建立一张位示图，记录文件存储器的使用情况，每一位仅对应文件存储器上的一个物理块，取值 0 和 1 分别表示空闲和占用。原文还有一句一模一样的定性，考试就抄这句：位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，当其值为 0 时表示对应的盘块空闲，为 1 时表示已分配；由所有盘块对应的位构成一个集合，称为位示图。别把 0 和 1 记反——0 空闲、1 已分配。

这就是这道题的坑：干扰项给了四个，位示图法、索引法、链接法、空闲表法，前三个是原文写死的三种方法，空闲表法这个名字在原文里根本没有，它的内容其实被并进了索引法——索引对应的是一个或几个空闲块构成的空闲区。所以答题路径是：看到「二进制的一位」「0 和 1」直接锁位示图法；索引法是把空闲块当文件建索引，链接法是用链表串起来，都不涉及一位一位地标。

有。文件存储器上的物理块依次编号为 0、1、2 等等；假如系统中字长为 32 位、有 4096 个物理块，那么在位示图中的第 1 个字对应文件存储器上的 0 到 31 号物理块，第 2 个字对应 32 到 63 号物理块，第 128 字对应 4064 到 4095 号物理块。算法你要会：需要多少个字，等于物理块总数除以字长，4096 除以 32 就是 128 个字。位示图也可以描述为一个二维数组 map。

在计算机的文件系统中一般采用树型目录结构：树的根结点为根目录，数据文件作为树叶，其他所有目录均作为树的结点。根目录隐含于一个硬盘的一个分区中、在最顶层，它包含的子目录是一级子目录，每一个一级子目录又可以包含若干二级子目录，这样的组织结构就叫作目录树。当前盘和当前目录是系统默认的操作对象，如果用户没有指明操作对象，系统就将用户命令指向当前盘和当前目录。

要，还带一个结论。路径是指从根目录或者当前目录开始到访问对象，在目录树中路经的所有目录的序列。关键结论是：在树型目录结构中，从根目录到任何数据文件之间只有一条唯一的通路，把全部目录文件名与数据文件名依次连接起来构成该数据文件的路径名，且每个数据文件的路径名是唯一的——这样便可以解决文件重名问题。「解决重名」就是树型目录被考的理由。

从树根开始的路径为绝对路径；如果文件系统有很多级时使用不是很方便，所以引入相对路径，即从当前目录开始，再逐级通过中间的目录文件，最后到达所要访问的数据文件。绝对路径给出文件或目录位置的完全描述，通常由层次结构的顶端即根目录开始；相对路径通常由目录结构中的当前位置开始，一般都比绝对路径要短。还有一句细节：每个目录下都有代表当前目录的一个点文件和代表当前目录父目录的两个点文件，相对路径名一般就是从两个点开始的。

两个角度。从用户的角度看，作业是系统为完成一个用户的计算任务或一次事务处理所做的工作总和；例如用户编制的源程序需经过编译、连接编辑或连接装入及运行产生计算结果，其中的每一个步骤常称为作业步，作业步的顺序执行即完成了一个作业。从系统的角度看，作业则是一个比程序更广的概念，它由程序、数据和作业说明书组成，系统通过作业说明书控制文件形式的程序和数据使之执行和操作。还有一句爱考：在批处理系统中，作业是占据内存的基本单位。

用户的作业可以通过直接的方式，由用户自己按照作业步顺序操作；也可以通过间接的方式，由用户率先编写的作业步依次执行的说明，一次交给操作系统，由系统按照说明依次处理。前者称为联机方式，后者称为脱机方式。自己一步步动手是联机，写好说明书一次性交出去是脱机。

一个作业从交给计算机系统到执行结束退出系统，一般都要经历提交、后备、执行和完成 4 个状态。提交状态：作业由输入设备进入外存储器、也称输入井的过程称为提交状态，处于提交状态的作业其信息正在进入系统。后备状态：当作业的全部信息进入外存后，系统就为该作业建立一个作业控制块 JCB。执行状态：一个后备作业被作业调度程序选中而分配了必要的资源并进入了内存，作业调度程序同时为其建立了相应的进程后，该作业就由后备状态变成了执行状态。完成状态：当作业正常运行结束、它所占用的资源尚未全部被系统回收时的状态为完成状态。

这道题答案就是后备状态，四个选项逐个划清界线：提交是信息「正在」进入系统、还没全部进外存；后备是全部信息已进外存并建好了 JCB；执行是已分配资源并进入内存、还建了相应进程；完成是运行结束但资源尚未全部被回收。口诀——正在进是提交，进完外存建 JCB 是后备，进内存建进程是执行，跑完没收干净是完成。JCB 本身也考：系统通过 JCB 感知作业的存在，主要内容包括作业名、作业状态、资源要求、作业控制方式、作业类型及作业优先权等。

先把接口的树画清。用户接口也称为用户界面，含义有两种：一种是指用户与操作系统交互的途径和通道，即操作系统的接口；另一种是指这种交互环境的控制方式，即操作环境。操作系统的接口又可分成命令接口和程序接口：命令接口包含键盘命令和作业控制命令；程序接口又称为编程接口或系统调用，程序经编程接口请求系统服务，即通过系统调用程序与操作系统通信。然后是原文那句定性，一字不改地背——系统调用是操作系统提供给编程人员的唯一接口。

所以那道题选的是「操作系统提供给编程人员的唯一接口」。命令接口是跟命令接口并列的另一半，是给用户敲命令用的，不是系统调用；菜单界面和视窗环境属于操作环境和交互界面的形态——原文说操作系统的交互界面已经从早期的命令驱动方式发展到菜单驱动方式、图符驱动方式和视窗操作环境，跟接口的定义不沾边。再补两条：系统调用对用户屏蔽了操作系统的具体动作而只提供有关功能；系统调用大致分为设备管理、文件管理、进程控制、进程通信和存储管理等，是五类。

第一块进程管理：就绪状态是已分配除 CPU 外所有必要的资源、只要获得处理机便能立即执行；阻塞态不能直接进执行态、必须先变就绪，就绪态也不能直接进阻塞态；前趋图里一条指令的取指、分析、执行三步之间是直接制约，多个操作之间相同步骤是间接制约；互斥是资源的竞争关系、同步是进程间的协作关系；P 操作把信号量减 1，小于 0 则进等待状态，V 操作加 1，小于等于 0 则唤醒一个等待进程。

接着是死锁与存储：死锁四个必要条件是互斥、保持和等待、不剥夺、环路等待，先来先服务是调度算法不是死锁条件；银行家算法属于死锁避免。存储管理记两条：段页式的虚地址是段号、页号、页内偏移三段，页式是页号加页内偏移、段式是段号加段内偏移；FIFO 页面调度会出现分配页面数增多而缺页次数反而增加的异常，LRU 和 OPT 不会。

第三块设备与今天这两块：DMA 是窃取或挪用处理器的工作周期和控制总线，通道又称 IOP、独立执行通道程序，SPOOLING 用一道程序模拟外围控制机、把低速独占设备改造成可共享设备、必须有高速大容量可随机存取的外存支持。文件：三种分配策略只有顺序、链接、索引，既适用顺序存取又适用随机存取的只有索引分配；三种空闲块管理是索引法、链接法、位示图法，位示图用二进制一位表示一个盘块、0 空闲 1 已分配。作业：提交、后备、执行、完成四状态，全信息进外存建 JCB 是后备；系统调用是给编程人员的唯一接口。

去做，错的题对回原文再重听对应那一集。下一章我们进数据库系统，三级模式、范式、SQL 和并发控制，那边的分值比这章还重。