操作系统重点知识汇总（1）

操作系统重点 第一 章 有效性（系统管理人员的观点） ;方便性（用户的观点）；可扩充性（开放的观点）；开放性 储器、外部设备、信息（数据和软件）； 源的当前状态（数量和使用情况）、资源的分配、回收和访问操作，相应管理策略（包括用户权限） 统对作业的处理是成批进行的，内存中始终保持一道作业 动性；顺序性；单道性 ：提高 利用率；可提高内存和 I/O 设备利用率；增加系统吞吐量。 7.*多道批处理系统的优缺点：资源利用率高；作业吞吐量大；用户交互性差；作业平均周转时间长 一台主机上连接了多个带有显示器和键盘的终端，同时允许许多个用户通过自己的终端，以交互方式使用用计算机，共享主机中的资源 路性；独立性；及时性；交互性 统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行 路性：（实时控制系统的多路性主要表 现在系统周期性地对多路现场信息进行采集，以及对多个对象或多个执行机构进行控制，分时系统中的多路性则与用户情况有关时多时少）独立性：（实时信息处理系统中的每个终端用户在向实时系统提出服务请求时是彼此独立操作地互不干扰，实时控制系统中，对信息的采集和对象的控制也都是彼此互不干扰）及时性： (实时信息处理系统对实时性的要求和分时性系统类似，都是以人所能接受的等待时间来确定的，而实时控制系统的及时性则是以控制对象所要求的开始截止时间或完成时间来确定的，一般为秒级到毫秒级，甚至有的要低于 100 微妙 )交互性： (实时信息处 理系统虽然也具有交互性但这里人与系统的交互仅限于访问系统中某些特定的专用服务程序，它不像分时系统那样能向终端用户提供数据处理和资源共享等服务 )可靠性： (分时系统虽然也要求系统可靠但相比之下实时系统则要求具有高度上午可靠性 ) 并发性：是指两个或多个事件在同一时间间隔内发生 *并行性 (指两个或多个事件在同一时刻发生。 共享性：多个进程共享有限的计算机系统资源 方式分为：互斥共享方式（如音频设备）资源分配后到释放前不能被 其他进程所用； 同时访问方式（如可重入代码，磁盘文件） 虚拟技术：指通过某种技术（分时或分空间）把一个物理实体映射为 若干个对应的逻辑实体。 实现方式包括：时分复用技术：虚拟处理机技术、虚拟设备技术； 空分复用技术：虚拟磁盘技术、虚拟存储器技术 异步性：进程是以人们不可预知的速度向前推进。 拟以并发和共享为前提；异步性是并发和共享的必然结果 理机管理；存储管理；设备管理信息管理；用户接口 用户接口：包括联机用户接口，脱机用户接口、图形接口用户接口； 程序接口 第二章 进程管理 1、程序：是一组有序指令的集合，有存放于某种介质上，其本身并不具有运 动的含义，是静态的 2、进程的特征： （ 1）结构特征：为使程序（含数据）能独立运行，应为之配置一进程控制块（ 由程序段、相关的数据段和 （ 2）动态性：进程的实质是进程实体的一次执行过程，是进程的最基本的特征，进程由创建而产生，由调度而执行，由撤销而消亡 （ 3）并发性：指多个进程实体同存于内存中，且能在一段时间内同时运行 （ 4）独立性：指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位 （ 5）异步性：指进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步 方式运行 3、程序和进程的区别：程序是静态的，不能并发执行；进程是动态的，能够并发执行 4 (1) (2) (3) 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。 (4) 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位 5、进程的三种基本状态（记住） （ 1）就绪状态：当进程已分配到除以外的所有必要资源后，只要再获得，便可立即执行， 进程这时的状态称为就绪状态 （）执行状态：进程已获得，其程序正在运行 （）阻塞状态：正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态。致使进程阻塞的典型事件有：请求，申请缓冲空间等 6、进程控制块：是进程实体的一部分，操作系统中最重要的记录型数据结构。其作用是使一个在多道程序环境下不能独立运行的程序 (含数据 )，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说， 根据 对并发执行的 进程进行控制和管理的。 7、原语：是由若干条指令组成的，用于完成一定功能的一个过程。 原子操作：一个操作中的所有动作要么全做，要么全不做，是一个不可分割的基本单位 8、（ 1）引起进程阻塞和唤醒的事件： 1）请求系统服务 2) 启动某种操作 3) 新数据尚未到达 4) 无新工作可做 （ 2）进程阻塞：正在执行的进程，当所请求的某事件没出现时，由于无法继续执行，于是进程便通过调用阻塞原语自己阻塞。进程阻塞是进程自身的一种主动行为。 (3) 程唤醒：当被阻塞进程所期待的事 件出现时，如 I/O 完成或其所期待的数据已经到达，则由有关进程 (比如，用完并释放了该 I/O 设备的进程 )调用唤醒原语 )，将等待该事件的进程唤醒。 9、进程同步：是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。 10、临界资源：临界资源是指每次仅允许一个进程访问的资源。如打印机、磁带机等都属于临界资源。诸进程间应采取互斥方式，实现对这种资源的共享。 11、临界区：把在每个进程中访问临界资源的那段代码称为临界区 12、同步机制应 遵循的四条规则：（ 1）空闲让进 (2) 忙则等待 (3) 有限等待 (4) 让权等待 13、信号量机制 （ 1）整型信号量：一个用于表示资源数目的整型量，除初始化外，仅能通过两个标准的原子操作 ()和 )来访问。 （ 2）记录型信号量：一种采取了“让权等待”的策略使进程不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量 ，还应增加一个进程链表 L，用于链接上述的所有等待进程。 14、经典进程的同步问题：生产者 消费者问题 结合 课后练习复习） 15、进程通信：指进程之间的信息交换，其所交换的信息量少者是一个状态或数值，多者则是成千上万个字节。 16、管道机制提供的三方面协调能力：（ 1）互斥 （ 2）同步 （ 3）确定对方是否存在，只有确定了对方已存在时，才能进行通信 17、线程：不拥有系统资源，能独立运行的基本单位，也是独立调度和分派的基本单位。 第三章 处理机调度的层次 ：（运行频率：低级调度 中级调度 高级调度） 业调度、长程调 度、接纳调度）：将外存作业调入内存，创建 ，插入就绪队列。 一般用于批处理系统，分 /实时系统一般直接入内存，无此环节。 程调度，短程调度） 主要是决定就绪队列中的哪个进程应获得处理机，然后由分派程序（ 派处理机。 两种调度方式： 1)非抢占方式：简单、系统开销小，实时性差 (如 2)抢占方式：（ 1）优先权原则（ 2）短进程优先原则（ 3）时间片原则 程调度）：为提高系统吞吐量和内存利用率而引入的一 内 出时，进程为挂起 或就绪驻外存状态） 面向用户的准则 （ 1）周转时间短（常用于批处理系统） 概念：作业从提交到完成的时间 外存等待调度时间；驻内存等待调度时间；执行时间；阻塞时间 平均周转时间： 平均带权时间： （可见带权 w 越小越好 ,实际服务时间。） 面向系统的准则 （ 1）吞吐量高（特别是批处理）：单位时间完成作业数 （ 2）处理机利用率好：（因 ，特别是大中型多用户系统） （ 3）各类资源的平衡利用。 先来先服务和短作业（进程）优先调度算法 点：简单，有利于长作业（进程） 即 忙性作业 ,不利于短作业（进程） 程）优先调度算法 ： )F 提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量） 特点：对长作业不利，有可能得不到服务 估计时间不易确定 计算：带权周转时间 =周转时间 /服务时间；完成时间： 顺序完成作业， 成第一个作业后选择服务时间最短的作业依次完成； 11 ni n ii 型： 1）非抢占式优先权算法 2）抢占式优先权算法，实时性更好。 优先权类型： 1）静态优先权：进程优先权在整 个运行期不变。 特点：简单，但低优先权作业可能长期不被调度（饥饿）。 2）动态优先权：进程优先级可随进程的推进或等待时间的增加而改变。 优点：长短兼顾 缺点：需经常计算各进程优先级 高响应比优先调度算法：（短作业 ） 响应比 s） /等待时间 +要求服务时间） /要求服务时间 =优先权 =响应时间 /要求服务时间 系统能在给定的时间内响应所有用户的请求 时间片大小的确定：太大：退化为 小：系统开销过大 作业名 A B C D E 平均 到达时间 0 1 2 3 4 服务时间 4 3 4 2 4 RR q 1 完成时间 15 12 16 9 17 周转时间 15 11 14 6 13 权周转时间 R q 4 完成时间 4 7 11 13 17 周转时间 4 6 9 10 13 权周转时间 1 2 间片大小不同时带权周转时间于完成时间也不同； 实时调度 ：对用户的实时响应 实现实时调度 的基本条件 1提供必要 的调度信息 （ 1）就绪时间；（ 2）开始 /完成截止时间；（ 3）处理时间；（ 4）资源要求；（ 5）优先级； 2系统处理能力强 1）剥夺方式：一般都采用此方式 2）非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃 1）具有快速响应外部中断能力。 2）快速任务分派 死锁： 指多个进程在运行过程中因争夺资源而造成的一种僵局。 产生死锁的原因。 1、竞争资源引起死锁。 产生死锁的必要条件 1）互斥条件（资源的临界性） 2）请 求和保持条件 3）不剥夺条件 4）环路等待条件 处理死锁的基本方法 1预防死锁： 破坏 4 个条件之一：有效，使资源利用率低。 2避免死锁：防止进入不安全态。 3检测死锁：检测到死锁再清除。 4解除死锁：与 “检测 ”配套。 1、）互斥条件是资源固有属性，不能避免。 2、）摒弃请求和保持条件 3、）摒弃 “不剥夺 ”条件，增加系统开销，且进程前段工作可能失效。 4、）摒弃 “环路 ”条件 有序资源分配法：为资源编号，申请时需按编号进行。 缺点：（ 1）新增资源不便，（原序号已排定）（ 2）资源与进程使用顺序 不同造成浪费 （ 3）用户不自由 在 “避免死锁 ”方法中的判断条件 安全状态： 能找到安全序列的状态为安全状态。 （ 系统按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。） 例： 进程 最大需求 已分配 可用 0 5 3 2 2 安全序列： 银行家算法避免死锁 j=k: 系统现有 资源 k 个； i,j=k: 进程 i 需要 最大数 k 个； i,j=k: 进程 i 已得到 资源 k 个； i,j=k: 进程 i 需要 资源 k 个 有： i,j= i,j i,j （ 程 i 请求资源数； 程 i 执行完后系统应有资源数（也即可用数） i：布尔量，表进程 i 能否顺序完成。 ） 分配； 分配 求 =i= i= 直到进程的 i都为 系统处于安全状态 死锁的解除 1） 剥夺资源。 2) 撤消进程。 第四章 现代计算机结构中的一重要部件，其容量大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十 几 问速度快于主存储器 . 身并不是一种实际存在的存储介质，它依托于固定磁盘，提供对主存储空间的扩充，即利用主存中的存储空间，来暂存从磁盘中读出（或写入）的信息。 1 绝对装入方式：编译后，装入前已产生了绝对地 址（内存地址），装入时不再作地址重定位 ,适用于单道系统。 2 可重定位装入方式：静态重定位：装入时完成，主要工作是对相对地址中的指令和数据地址的调整过程；可重定位装入方式在装入后不能移动程序 3 动态运行时装入方式：该情况一般在执行时才完成相对和绝对地址的转换且有硬件的支持 ,能保证进程的可移动性 1 单一连续分配：是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。可把内存分为系统和用户两个部分系统区仅提供给 用，通常是放在内存的低址部分，用户区是系统区以外的全部内存空间，提供给用户使用。 2 固定分区分配：是最简单的一种可运行多道程序的存储管理方式，是将内存用户空间分为若干个固定大小的区域，在每个分区中只装入一道作业，这样把用户空间划分为几个分区，便允许有多到作业并发运行。特点：简单，有碎片（内零头） ,浪费。划分分区大小的方法：分区大小相等；分区大小不等。内存分配：将分区按大小排序，建立分区使用表，并将其地址、分配标识作记录 3 动态分区分配：是根据进程的实际需要，动态地为之分配内存空间。 分区分配中常用的数据结构有两种形式：空闲分区表；空闲分区。 分区分配算法： 1 首次适应算法 求：空闲分区链以地址递增的次序链接； 特点：找到第一个大小满足的分区，划分，有外零头，低址内存使用频繁，增加系统开销 2 循环首次适应算法：从上次找到的空闲分区的下一个开始查找。 特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。 3 最佳适应 算法：每次分配内存是总是把能满足要求、又是最小的空闲区分配给作业，避免大材小用。分区按大小递增排序；分区释放时需插入到适当位置 4 最坏适应算法：选一个最大的空闲区分割给作业使用。优点：使剩下的空闲区不至太小，产生碎片的几率最小对中小作业有利，查找效率高。缺点：缺乏大的空闲分区 5 快速适应算法：按空闲分区容量分类，对每类相同容量的所有空闲分区，单独设立一个空闲分区链表，管理索引表。优点：查找效率高；缺点：算法复杂，系统开销大。 要操作（分区分配操作）： 1 分配内存：系统应用某种算法，从空闲分区链（表）中找到所需大小的分区 2 回收内存：上邻空闲区：合并，改大小。下邻空闲区：合并，改大小，首址。上、下邻空闲区：合并，改大小。不邻接，则建立一新表项。 把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。 类型：整体对换 /进程对换： 一整个进程为单位，应该于解决内存紧张 部分对换：页面对换 /分段对换 /部分对换：是请求分段和请求分页式存储管理的基础，提供虚存支持。 具备页面对换功能，不具备支持现实虚拟存储器的功能，要求把每个作业全部妆容内存后方可运行。 页面或页：将一个进程的逻辑地址空间分成若干个大小相等的片，并为各页加以编号； L O A D 1 , 2 5 0 03 6 501 0 02 5 0 05 0 0 02 5 0 0相 对 地 址1 0 0 0 0重 定 位 寄 存 器L O A D 1 , 2 5 0 03 6 51 0 0 0 01 0 1 0 01 2 5 0 01 5 0 0 0作 业 机 一 侧 存 储 器 一 侧主 存物理块或页框：把内存空间分成与页面相同大小的若干个存储块，并为它们加以编号； 地址结构： 31 12 11 0 页号 P 位移量 W 页号 P；逻辑地址 A；页面大小 L； 页内地址 d P= d=A 例如，系统的页面大小为 1 A=2170B，求页号和页内地址。 解： 110B=1024B 页号 P=170/1024=2 页内地址 d=217022 实现从页号到物理块号的地址映射。 现从逻辑地址到物理地址的转换，见 4 具快表，则需两次访问内存：第一次访问页表；第二次访问得到绝对地址内容。 为了提高地址变换速度 ，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲器，又称为“联想寄存器”或“快表”。 辑地址结构可描述如下： 外层页号 外层页内地址 页内地址 2 d 31 22 21 12 11 0 要看得懂就行） 分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名 ，即“先分段后分页”。 了获得一条指令或数据，须三次访问内存。第一次访问段表取得页表始址；第二次访问页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正从第二次访问所得的地址中，取出指令或数据。 1）多次性：一个作业被分成多次调入内存运行。 （ 2）对换性：允许在作业的运行过程中进行换进、换出。 （ 3）虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。 求分页存储管理方式： 1，请求分页中的硬件支持：一定容量的内存，外存的计算机系统，还需要页表机制，缺页中断机构以及地址变换机构。 2、页面分配和置换策略。 1）固定分配局部置换。缺点：难以确定固定分配的页数 .(少：置换率高 多：浪费 ) 2）可变分配全局置换 3）可变分配局部置换根据进程的缺页率进行页面数调整，进程之间相互不会影响。 面置换算法： 1）最佳置换算法， 2）先进先出（ 面置换算法 3）最近最久（ 使用置换算法 (要懂的这几种算法的实现，看例题 ) 求分段存储管理方 式： 1，请求分段管理所需的硬件支持有段表机制，缺段中断机构，以及地址变换机构 2，在请求芬顿式管理中所需的主要数据结构式段表。 第五章 设备管理 1、 I/O 设备的类型： 1）按设备的使用特性分类： （ 1）存储设备 （ 2）输入 /输出设备 （ 3）交互式设备 2）按传输速率分类： （ 1）低速设备 如键盘、鼠标器等 （ 2）中速设备 如打印机 （ 3）高速设备 如磁带机 3）按信息交换的单位分类： （ 1）块设备 磁盘 ,可定位 （ 2）字符设备 打印机 4）按设备的共享属性分类： （ 1）独占设备。指一段时间内质循序一个用户（进程）访问的设备。即临界资源。 （ 2）共享设备。指在一段时间内循序多个进程同时访问的设备。如磁盘。 （ 3）虚拟设备。指通过虚拟即使将一台独占设备变换为若干台逻辑设备，供若干个用户（进程）同时使用。 2、 I/O 通道：是一种特殊的处理机，它具有执行 I/O 指令的能力，并通过执行通道（ I/O）程序来控制 I/O 操作。 引入的目的是为了建立独立的 I/O 操作，解脱 I/O 的组织、管理。 3、 I/O 控制方式： 1）程序 I/O 方式：或称为忙 在处 理机向控制器发出一条 I/O 指令启动输入设备输入数据时，要同时把状态寄存器中的忙 /闲标志 为 1，然后不断地循环测试 种方式 源浪费极大。 2）中断驱动 I/O 控制方式：即当某进程要启动某个 I/O 设备工作时，便由 相应的设备控制器发出一条 I/O 命令，然后立即返回继续执行原来的任务。 这种方式用于字符设备 I/O。 3）直接存储器访问（ I/O 控制方式：用于块设备的 I/O。 4、单缓冲：（简单了解原理） 工作区处理 ( C )缓冲区传送 ( M ) 输入 ( T )I / O 设备( a )T 1M 1C 1T 2M 2C 2T 3M 3C 3T 4t( b )用户进程 块设备输入时（图 a），系统每一块数据 的处理时间表示为 ,T)+M；字符设备输入时 (图 b)，缓冲区用于暂存用户输入的一行数据，在输入期间，用户进程被挂起以等待数据输入完毕，在输出时，用户进程将一行数据输入到缓冲区后，继续进行处理。 5、双循环 在块设备输入时（图 a），先将数据送入第一缓冲区，装满后便转向第二缓冲区，此时操作系统可从第一缓冲区中移出数据，送入用户进程。系统处理一块数据的时间可以粗略地认为是 ,T)；对于字符设备（图 b），用户在输入完第一行之后，在 行第一行中的命令时，用户可向第二缓冲区输入下一行数据。 6、循环缓冲 循环缓冲由多个缓冲区和多个指针组成。 6.（ 55 工作区用户进程缓冲区 1缓冲区 2 I / O 设备T 1 ( 缓冲 1 )M 1C 1M 2C 2M 3C 3T 2 ( 缓冲 2 ) T 3 ( 缓冲 3 )M 4C 4T 4 ( 缓冲 4 )( a )( b )3） 统： 概念：在联机情况下同时出现外围操作。 组成：输入井和输出井 输入缓冲区和输出缓冲区 输入进场 输出进程 点：提高 I/O 速度； 将独占设备改造为共享设备； 实现了虚拟设备功能 （ 4） 磁盘的结构和布局： 的图 （ 5） 磁盘访问时间： 1）寻道时间： TS=m*n+s m：常量， n：磁道数， s：磁臂启动时间。 2）旋转延时间 定扇区旋转到磁头下所需时间。 设每秒 r 转，则 1/2r（均值） 3）数据传输时间 b/rN b：读写字节数 N：每道上的字节数 访问时间： s+1/2r+b/ 6） 磁盘调度 （ 1） 来先服务 特点：公平、简单，寻道时间长，相当于随机访问模式。 仅适用于请求磁盘 I/O 的进程数目较少的场合。 （ 2）、 短寻道优先）最短寻道时间优先 更好的寻道性能 贪心的算法 饥饿现象 不能保证平均寻道时间最短 度算法 度算法 （ 3） 描算法（也称为电 梯算法）。 法： 在移动方向固定的情况下采用了 避免饥饿现象 存在请求进程等待延迟现象 （ 4）、循环扫描 头单向移动 一个方向读完，不是象 样回头，而是循环扫描。 请求延迟时间： 2T T+度算法示例 度算法示例 （ 7） 磁盘高速缓存 形式 ：逻辑上是磁盘、物理上是驻留在内存中的盘块 固定大小和可变大小 （ 8） 虚拟盘：利用内存空间去仿真磁盘，又称 和磁盘高速缓存区别：虚拟盘由用户控制；磁盘高速缓存由系统控制。 第六章 一、文件类型 按用途分类：系统文件，用户文件，库文件。（用户对以上三者的访问权限不同） 按文件中的数据形式分类 ： 源文件，目标文件，可执行文件。 存取控制：只执行文件，只读文件，读写文件。 （ E， R， R/W） 按组织形式和处理方式分类：普通文 件，目录文件，特殊文件。 二、最基本的文件操作：创建文件，删除文件，读文件，写文件，截断文件，设置文件的读 /写位置。 三、文件存在的两种形式： 文件的逻辑结构：用户所能观察和访问到的文件的数据结构组织，独立于物理特性，容易检索和修改。它可以分为 2类：（ 1）有结构文件（ 2）无结构文件 文件的物理结构：又称文件的存储结构，是指文件在外存上的组织形式。这不仅与存储介质的存储性能有关，且与所采用的外存分配方式有关。 四、文件逻辑结构的类型 1、有结构文件：记录式文件 a 类： （ 1）定长记录 （ 2）变长记录 b 类： （ 1）顺序文件：通常是定长记录，（为何，因变长采用此方式查询速度慢） （ 2）索引文件： （ 3）索引顺序文件：顺序组织多个组，每组记录中的第一个记录设置一索引项。 2、无结构文件：流式文件 以字节为单位，利用读 /写指针进行访问。 五、顺序文件 1、逻辑记录的排序 （ 1）按记录录入的时间排 :串结构。 （ 2）按关键字排序：顺序结构。 后一种情况更有利于提高查询速度。如可用折半查找法等。 2、对顺序文件的读 /写操作 定长记录顺序文件：例：顺序读 易于定位，甚至可随机读取。 变长记录：不易定位，只能顺序读取 。 六、索引文件 由变长记录组成的顺序文件不容易直接存取，因此，为其建立一有序的索引表，对索引采用折半查找，速度更快。 特点：提高了速度，增加了存储开销 放索引文件。 增、删记录时，对索引表作相应的修改。 七、索引顺序文件 将顺序文件中若干记录分为一组，每组的第一项在索引表中占一项。 速度： 例 1： 10000 个记录，顺序文件： 5000 次查找查到。 索引顺序文件，设 100 个记录一组，索引表的找法设为顺序法的情况下，则平价查找次数为 50+50=100。 例 2： 1000000 个纪录： 一级索引：（ 100 个纪录 一组）：平价查找 5050 次 二级索引：平价查找 50+50+50=150 次 八、连续分配方式 连续分配（磁带，磁盘都可采用）（顺序文件） 每个文件分配一组相邻盘块。 优点： 因磁头移动距离小，顺序访问容易且速度快 . 缺点： 要求连续空间，一段时间后需整理磁盘以消除外部碎片。 必须事先知道长度，文件不易动态增长和删除。 文件对应目录项（属性）中包含： 始址、总块数、最后一块字节数。 九、连接方式分为隐式链接和显示连接两种形式。 隐式链接： 文件目录表中有 号，每块中有指向下一块号的指针。 缺点：只适合 于顺序访问，对随机访问效率低，可靠性差。 十、索引分配 1、单级索引分配 链接分配问题： 不能高效直接存取； 占较大的内存。 概念：为每个文件分配一个索引块 特点：支持直接访问；不会产生外部碎片 问题： （ 1）文件较大时有利。文件较小时浪费外存空间（还需为小文件建索引块） （ 2）当文件较大时，索引块太多，查找速度减慢 解决：当索引太大时，则需建立多级索引 2、多级索引分配 两级 :为索引块再建立一级索引 设一个盘块大小为 1k，每个盘块号占 4一个索引块可存放 256 个盘块号。 所以两级 索引存放的文件的盘块号总数为： 256 256=64k,故文件的最大长度为 64M 三、四级 :适用于文件更大时 设每个块大小为 4k，一索引项（盘块号）占 4 字节，则 1)直接地址 )：小文件（ =40k)则立即读出。 2)一次间址 0)：一次间址块中存放 1K 个盘块， 4M 大小 3)多次寻址 : 二次间址 1)： 1K*1K 个盘块， 4G 三次间址 2): 1K*1K*1K 个盘块， 4T 例子： 十一、文件控制块：为了能对系统中的大量文件施以有效的 管理，在文件控制块中通常有三类信息 基本信息，存取控制信息，使用信息。 十二、索引结点：含文件描述信息。 为何引入： 含 :文件名、描述信息，它们较占空间 十三、多级目录结构： 树型目录结构（多级目录） 特点： 能有效地提高对目录的检索速度 允许文件重名 便于实现文件共享 （ 1）目录结构： 目录文件中的目录项可为：目录文件（节点）、数据文件（树叶） （ 2）路径名： （ 3）当前目录 /工作目录。 十四、空闲表法和空闲链表法 1、空闲表法： 分配：首次 /循环首次 /最佳 /最坏 回收：判断是否合并 。 由于连续分配比较快，因此对对换空间及小文件的管理适用。 1)空闲盘块链 缺点：可能该链很长。 2)空闲盘区链： 一个盘区含多个盘块，类似于内存分区分配与回收 (合并 )。 十五、位示图 1、盘块的分配： （ 1）顺序扫描，找一个或一组 =0 的块。（ 2）根据找到的行 /列得以盘块号。 b=n(j （ 3）修改位图，令 i,j=1。 2、回收 （ 1）由磁块号得 (i,j) i=(n +1 j=(n +1 （ 2）修改位图：令 i,j=0。 特点：因不占空间，可放入内存，易于访问 以下 的大题，大家看看并做做不懂得再问问： 第四章 (以下题目是老师讲到过的 ) 例 1：某系统采用页式存储管理策略，拥有逻辑空间 32 页，每页 2K，拥有物理空间 1M 写出逻辑地址的格式 若不考虑访问