2020年计算机考研408操作系统重点汇总.pdf

《2020年计算机考研408操作系统重点汇总.pdf》由会员分享，可在线阅读，更多相关《2020年计算机考研408操作系统重点汇总.pdf（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020年计算机考研操作系统重点汇总第一章1.操作系统的目标:有效性（系统管理人员的观点）；方 便 性（用户的观点）可 扩 充 性（开放的观点）开放性2.操作系统的管理对象包括：CPU、存储器、外部设备、信 息（数据和软件，3.管理的内容：资 源 的 当 前 状 态（数量和使用情况）资源的分配、回收和访问操作，相应 管 理 策 略（包括用户权限）4.单道批处理系统：系统对作业的处理是成批进行的，内存中始终保持一道作业5.单道批处理系统的特征：自动性；顺序性；单道性6.多道程序设计技术带来的好处：提 高C P U的利用率；可提高内存和I/O设备利用率；增加系统吞吐量。7.*多道批处理系统的优缺点

2、：资源利用率高；作业吞吐量大；用户交互性差；作业平均周转时间长8.分时系统：在一台主机上连接了多个带有显示器和键盘的终端，同时允许许多个用户通过 自己的终端，以交互方式使用用计算机，共享主机中的资源9.分时系统的特征：多路性；独立性；及时性；交互性10.实时系统：系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行11.实时系统与分时系统特征比较：多路性:（实时控制系统的多路性主要表现在系统周期性地对多路现场信息进行采集，以及对多个对象或多个执行机构进行控制，分时系统中的多路性则与用户情况有关时多时少）独 苗 生（实时信息处理系统中的每个终端用户在向

3、实时系统提出服务请求时是彼此独立操作地互不干扰，实时控制系统中，对信息的采集和对象的控 制也都是彼此互不干扰）及时性：（实时信息处理系统对实时性的要求和分时性系统类似，都是以人所能接受的等待时间来确定的，而实时控制系统的及时性则是以控制对象所要求的开始截止时间或完成时间来确定的,一般为秒级到毫秒级，甚 至 有 的 要 低 于1 0 0微妙）交互性:（实时信息处理系统虽然也具有交互性但这里人与系统的交互仅限于访问系统中某些特定的专用服务程序，它不像分时系统那样能向终端用户提供数据处理和资源共享等服务）可靠性：（分时系统虽然也要求系统可靠但相比之下实时系统则要求具有高度上午可靠性）1 2.操作系统

4、的基本特征：并发性：是指两个或多个事件在同一时间间隔内发生*并行性（p a r a l l e l）是指两个或多个事件在同一时刻发生。共享性：多个进程共享有限的计算机系统资源方式分为：互斥共享方式（如音频设备）资源分配后到释放前不能被其他进程所用；同时访问方式（如可重入代码，磁盘文件）虚拟技术：指通过某种技术（分时或分空间）把一个物理实体映射为 若干个对应的逻辑实体。实现方式包括：时分复用技术：虚拟处理机技术、虚拟设备技术；空分复用技术：虚拟磁盘技术、虚拟存储器技术异步性：进程是以人们不可预知的速度向前推进。1 3.操作系统的各特征之间的关系：虚拟以并发和共享为前提；异步性是并发和共享的必然结

5、果1 4.操作系统的功能：处理机管理；存储管理；设备管理信息管理；用户接口1 5.操作系统向用户提供的两种接口：用户接口：包括联机用户接口，脱机用户接口、图形接口用户接口；程序接口第 二 章 进 程 管 理1、程序：是一组有序指令的集合，有存放于某种介质上，其本身并不具有运动的含义，是静态的2、进程的特征：（1）结构特征：为使程序（含数据）能独立运行，应为之配置一进程控制块（PCB）由程序段、相关的数据段和PCB三部分构成了进程实体(2)动态性：进程的实质是进程实体的一次执行过程，是进程的最基本的特征，进程由创建而产生，由调度而执行，由撤销而消亡(3)并发性：指多个进程实体同存于内存中，且能在

6、一段时间内同时运行(4)独立性：指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位(5)异步性：指进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行3、程序和进程的区别：程序是静态的，不能并发执行；进程是动态的，能够并发执行4、较典型的进程定义有：(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。(4)进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位5、进程的三种基本状态(记住)(1)就绪状态：当进程已分配到除C P U以

7、外的所有必要资源后，只要再获得C P U,便可立即执行，进程这时的状态称为就绪状态(2 )执行状态：进程已获得C P U,其程序正在运行（3）阻塞状态：正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而 处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态。致使进程阻塞的典型事件有：请 求I/0,申请缓冲空间等讲程的三种基本状本及其转族6、进程控制块：是进程实体的一部分，操作系统中最重要的记录型数据结构。其作用是使一个在多道程序环境下不能独立运行的程序（含数据）,成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，O S是 根 据PCB来对并发执行的

8、进控制和管理的。7、原语：是由若干条指令组成的，用于完成一定功能的一个过程。原子操作：一个操作中的所有动作要么全做，要么全不做，是一个不可分割的基本单位8、（1）引起进程阻塞和唤醒的事件：1）请求系统服务 2）启动某种操作3）新数据尚未到达 4）无新工作可做（2）进程阻塞：正在执行的进程，当所请求的某事件没出现时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。进程阻塞是进程自身的一种主动行为。（3）程I细星:当襁瞳进程所期I琬勺事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程（比如，用完并释放了该I/O设备的进程）调用唤醒原语wakeupO,将等待该事件的进程

9、唤醒。9、进程同步：是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。10、临界资源：临界资源是指每次仅允许一个进程访问的资源。如打印机、磁带机等都属于 临界资源。诸进程间应采取互斥方式，实现对这种资源的共享。11、临界区：把在每个进程中访问临界资源的那段代码称为临界区12、同步机制应遵循的四条规则：（1）空 闲 让 进（2）忙 则 等 待（3）有 限 等 待（4）让权等待13、信号量机制（1）整型信号量：一个用于表示资源数目的整型量，除初始化外，仅能通过两个标准的原子操作（Atomic Operation）wait（S）和

10、signal（S）来访问。（2）记录型信号量：一种采取了“让权等待”的策略使进程不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L,用于链接上述的所有等待进程。14、经典进程的同步问题：生产者一消费者问题P58（结 合P82的课后练习复习）15、进程通信：指进程之间的信息交换，其所交换的信息量少者是一个状态或数值，多者则 是成千上万个字节。16、管道机制提供的三方面协调能力：（1）互 斥（2）同 步（3）确定对方是否存在，只有确定了对方已存在时，才能进行通信1 7、线程：不拥有系统资源，能独立运行的基本单位，也是独立调度和分派的基本单位

11、。第三章处理机调度的层次：（运行频率：低级调度 中级调度 高级调度）1 .高级调度（作业调度、长程调度、接纳调度）将外存作业调入内存，创建PCB等，插入就绪队列。一般用于批处理系统，分/实时系统一般直接入内存，无此环节。2 .低级调度（进程调度，短程调度）主要是决定就绪队列中的哪个进程应获得处理机，然后由分派程序（D i s p at c h e r）分派处理机。两种调度方式：1）非抢占方式：简单、系统开销小，实时性差（如w i n 3 1）2）抢占二方式（1）优先权原则（2）短进程优先原则（3）时间片原则3 .恤 调 度（中程调度）为提高系统吞吐量和内存利用率而引入的一内一外存对换功能（换出

12、时，进程为挂起或就绪驻外存状态）面向用户的准则（1）周 转 时 间 短（常用于批处理系统）概念：作业从提交到完成的时间.分为：驻外存等待调度时间；驻内存等待调度时间；执行时间；阻塞时间1 平均周转时间:T=为 /=!1W=平均带权时间：i-（可见带权W越小越好,T s为实际服务时间。）“i=面向系统的准则（1）吞 吐 量 高（特别是批处理）单位时间完成作业数（2）姻断利用率好：（因CPU贵，特别是大中型多用户系统）（3）各类资源的平衡利用。先来先服务和短作业（进程）优先调度算法1.FCFS特点：简单，有利于长作业（进程）即 CPU 繁忙性作业,不利于短作业（进程）2.短作业（进程）优先调度算法

13、：SJ（P）F提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）特点：对长作业不利，有可能得不到服务估计时间不易确定调度进程名ABODE平 均到达时间0 12 3 4服务时间4 3 5 2 4FC FS完成时间4 7 12 14 18周转时间4 6 10 11 149带权周转时间1 2 2 5.5 3.52.8S J F3)完成时间4 9 18 6 13周转时间4 8 16 3 98带权周转时间1 2.67 3.1 1.5 2.252.1计算：带权周转时间=周转时间/服务时间；完成时间：FC FS按顺序完成作业，SJF完成第一个作业后选择服务时间最短的作业依次完成；3.最先优先权调度

14、算法类型：1）非抢占式优先权算法2）抢占式优先权算法，实时性更好。优先权类型：1）静态优先权：进程优先权在整个运行期不变。特点：简单，但低优先权作业可能长期不被调度（饥饿）2）动态优先权：进程优先级可随进程的推进或等待时间的增加而改变。优点：长 短 兼 顾 缺 点：需经常计算各进程优先级高响应比优先调度算法：（短作业R P 大）响 应 比 Rp=（Tw+Ts）/T s=（等待时间+要求服务时间）/要求服务时间=优先权=响应时间/要求服务时间4.时间片轮转调度：系统能在给定的时间内响应所有用户的请求时间片大小的确定：太大：退 化 为 FCFS；太小：系统开销过大时间片大小不同时带权周转时间于完成

15、时间也不同;作业名ABCDE平均到达时间01234服务时间43424RRq=l完成时间151216917周转时间15111461311.8带权周转时间 3.753.673.533.333.46RRq=4完成时间47111317周转时间46910138.4带权周转时间 122.2553.332.5实时调度:对用户的实时响应实现实时调度的基本条件1.提供必要的调度信息(1)就绪时间；(2)开始/完成截时间；(3)姐 期 间(4)资 艘 求(5)优先级;2.系统处理能力强3.采用抢占调度方式1）剥夺方式：一般都采用此方式2）非剥夺方式（实现简单）一般应使实时任务较小，以及时放弃CPU。4.具有快速切

16、换机制1）具有快速响应外部中断能力。2）快速任务分派死锁：指多个进程在运行过程中因争夺资源而造成的一种僵局。产生死锁的原因。1、竞争资源引起死锁。2.进程间推进顺序非法引起死锁。产生死锁的必要条件1）互 斥 条 件（资源的临界性）2）请求和保持条件3）不剥夺条件4）环路等待条件处理死锁的基本方法1.预防死锁：破 坏4个条件之一：有效，使资源利用率低。2.避免死锁：防止进入不安全态。3.检测死锁：检测到死锁再清除。4.解除死锁：与“检测”配套。1）互斥条件是资源固有属性，不能避免。2）摒弃请求和保持条件3）摒弃“不剥夺”条件，增加系统开销，且进程前段工作可能失效。4）摒弃“环路”条件有序资源分配

17、法：为资源编号，申请时需按编号进行。缺 点（1）新增资源不便（原序号已排定）（2）资源与进程使用顺序不同造成浪费（3）用户不自由在“避免死锁”方法中的判断条件安全状态：能找到安全序列的状态为安全状态。（系统按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。）例：安全序列：p2-pl-p3进程最大需求已分配可用Pl1053P242P392银行家算法避免死锁availablej=k:系统现有R j类资源k 个；maxi,j=k:进程i 需要R j的最大数k 个；aUoci,j=k:进程i 已得到R j类资源k 个;needi,j=k:进程i 需要R j类资源k 个有：need|i,

18、j=maxi,j allocfij（requesti 进程i 请求资源数；worki：进程i 执行完后系统应有资源数（也即可用数）finishi：布尔量，表进程i 能否顺序完成。）Allocation：已分配；Available：可分配 Need：需求 1.Work：=Available；2.Finishi=falseneed=work 则 Finish|i=true;3.work=Available+work；直到进程的Finishi都为true时系统处于安全状态死锁的解除1）剥夺资源。2）撤 消 进 程。第四章1 .高速缓存：是现代计算机结构中的一重要部件，其容量大于或远大于寄存器，而比内

19、存约 小两到三个数量级左右，从几十K B到几M B,访问速度快于主存储器.2 .磁盘缓存：本身并不是一种实际存在的存储介质，它依托于固定磁盘，提供对主存储空间 的扩充，即利用主存中的存储空间，来暂存从磁盘中读出（或写入）的信息。3 .程序的装入方式分为：。绝对装入方式：编译后，装入前已产生了绝对地址（内存地址）装入时不再作地址重定位,适用于单道系统。5 重定位装入方式：静态重定位：装入时完成，主要工作是对相对地址中的指令和数据地址的调整过程；可重定位装入方式在装入后不能移动程序C动态运行时装入方式:该情况一般在执行时才完成相对和绝对地址的转换且有硬件的支持,能保证进程的可移动性4 .连续分配方

20、式分为：8 一 整 分 配：是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。可把内存分为系统和用户两个部分系统区仅提（博合OS使用，通常是放在内存的低址部分，用户区是系统区以外的全部内存空间，提供给用户使用。固定分区分配：是最简单的一种可运行多道程序的存储管理方式，是将内存用户空间分为若干个固定大小的区域，在每个分区中只装入一道作业，这样把用户空间划分为几个分区，便允许有多到作业并发运行。特点：简单，有碎片（内零头），浪费。划分分区大小的方法：分区大小相等;分区大小不等。内存分配：将分区按大小排序，建立分区使用表，并将其地址、分配标识作记录C动态分区分配：是根据进程的实际需要

21、，动态地为之分配内存空间。分区分配中常用的数据结构有两种形式：空闲分区表；空闲分区。分区分配算法：。首次适应算法F F：要求：空闲分区链以地址递增的次序链接;特 点：找到第一个大小满足的分区，划分，有外零头，低址内存使用频繁，增加系统开销。循环首次适应算法：从上次找到的空闲分区的下一个开始查找。特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。最佳适应算法：每次分配内存是总是把能满足要求、又是最小的空闲区分配给作业，避免大材小用。分区按大小递增排序；分区释放时需插入到适当位置C最坏适应算法：选一个最大的空闲区分割给作业使用。优点：使剩下的空闲区不至太小，产生碎片的几率最小对中小作业有利

22、，查找效率高。缺点：缺乏大的空闲分区（W适应算法：按空闲分区容量分类，对每类相同容量的所有空闲分区，单独设立一个空闲分区链表，管理索引表。优点：查找效率高；缺点：算法复杂，系统开销大。5.动态分区存储管理中主要操作（分区分配操作）C分配内存：系统应用某种算法，从 空 闲 分 区 链（表）中找到所需大小的分区回收内存：上邻空闲区：合并，改大小。下邻空闲区：合并，改大小，首址。上、下邻空闲区:合并，改大小。不邻接，则建立一新表项。6.动态重定位的实现：P1267.对换:把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序

23、和数据调入内存。类型：整体对换/进程对换：一整个进程为单位，应该于解决内存紧张能，不具备支持现实虚拟存储器的功能,处 珊 机 i侧要求把每个作业全部妆容内存后方可运行。页面或页：将一个进程的逻辑地址空间分成若干个大小相等的片，并为各页加以编号;物理块或页框：把内存空间分成与页面相同大小的若干个存储块，并为它们加以编号;地址结构：3 1 1 2 1 1 0页 号P位 移 量W页号P;逻辑地址A；页面大小L；页内地址d P=IN T|A/L|d=A m od L例 如，系 统 的 页 面 大 小 为1 K B,设A=2 1 70 B,求页号和页内地址。解：1 K B=2 B=1 O2 4 B 页号

24、P=IN T 2 1 70/1 0 2 4=2 页内地址d=2 1 70 m od l 0 2 4=1 2 22.页表的作用：是实现从页号到物理块号的地址映射。3.分页系统的地址变换机构：实现从逻辑地址到物理地址的转换，见P 1 3 2图4-1 3。4.具有快表的地址变换机构：不具快表，则需两次访问内存：第一次访问页表；第二次访问 得到绝对地址内容。为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲器，又 称 为“联想寄存器”或“快 表”。5.两级页表：逻辑地址结构可描述如下：3 1 2 2 2 1 1 2 1 1 0外层页号外层页内地址页内地址PlP2d6.分 段

25、系统的基本原理（只要看得懂就行）P1 3 67.段页式系统基本原理，是分段和分页原理的结合，即先将用户程序分成若干个段，再把每 个段分成若干个页，并为每一个段赋予一个段名，即“先分段后分页”。8.在段页式系统中，为了获得一条指令或数据，须三次访问内存。第一次访问段表取得页表始址；第二次访问页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正从第二次访问所得的地址中，取出指令或数据。9.虚拟存储器的三大主要特征：（1）多次性：一个作业被分成多次调入内存运行。（2）对换性：允许在作业的运行过程中进行换进、换出。（3）虚拟性：能够从逻辑上扩充内存容量

26、，使用户所看到的内存容量远大于实际内存容量。4.7 请求分页存储管理方式：1，请求分页中的硬件支持：一定容量的内存，外存的计算机系统，还需要页表机制，缺 页 中断机构以及地址变换机构。2、页面分配和置换策略。1）固定分配局部置换。缺点：难以确定固定分配的页数.（少：置 换 率 高 多：浪费）2）可变分配全局置换3）可变分配局部置换根据进程的缺页率进行页面数调整，进程之间相互不会影响。4.8 页面置换算法：1）最佳置换算法，2）先 进 先 出（F I F O）页面置换算法3）最 近 最 久（L R U）未使用 置 换 算 法（要懂的这几种算法的实现，看例题）4.9 请求分段存储管理方式：1,请求

27、分段管理所需的硬件支持有段表机制，缺段中断机构，以及地址变换机构2,在请求芬顿式管理中所需的主要数据结构式段表。第 五 章 设 备 管 理1、I/O设备的类型：1）按设备的使用特性分类：（1）存 储 设 备（2）输 入/输 出 设 备（3）交互式设备2）按传输速率分类:（1）低速设备如键盘、鼠 标 器 等（2）中速设备如打印机（3）高速设备如磁带机3）按信息交换的单位分类：（1）块设备 磁 盘,可 定 位（2）字符设备 打印机4）按设备的共享属性分类：（1）独占设备。指一段时间内质循序一个用户（进程）访问的设备。即临界资源。（2）共享设备。指在一段时间内循序多个进程同时访问的设备。如磁盘。（3

28、）虚拟设备。指通过虚拟即使将一台独占设备变换为若干台逻辑设备，供若干个 用 户（进程）同时使用。2.1/0 通道：是一种特殊的处理机，它 具 有 执 行 I/O 指令的能力，并通过执行通道（I/O）程 序 来 控 制 I/O 操作。引入的目的是为了建立独立的I/O 操作，解脱C P U 对I/O 的组织、管理。3、I/O 控制方式：1）程序 I/O 方式：或称为忙-等待方式，即在处理机向控制器发出一条I/O 指令启动输入设备输入数据时，要同时把状态寄存器中的忙/闲标志bu s y 至为1,然后不断地循环测试bu s y o 这种方式C P U 资源浪费极大。2）中断驱动1/0 控制方式：即当某

29、进程要启动某个I/O 设备工作时，便由C P U 向相应的设备控制W出一条I/O 命令，然后立即返回继续执行原来的任务。这种方式用于字符设备I/O。3）直接存储器访问（D M A）I/O 控制方式：用于块设备的I/0 o4、单 缭 由（简单了解原理）用户进程处理（C）传送（M）_-缓冲区|输入（T）-I/。设备块设备输入时（图a）系统每一块数据的处理时间表示为Max（C,T）+M；字符设备输入时（图b）,缓冲区用于暂存用户输入的一行数据，在输入期间，用户进程被挂起以等待数据输入完 毕，在输出时，用户进程将一行数据输入到缓冲区后，继续进行处理。5、双循环用户进程在块设备输送入第一缓缓冲区1入 时

30、（图a）先将数据冲区，装满后便转向第二缓冲区，此时操作（a）工作区 I/O设备系统可从第一缓冲区中移出数据T入用户进程。系统处理一块数据的时间可以粗略地认为缓冲区2是Max（C,T）；对于字符设备（图b）用户在输入完第一行之后，在CPU执行第一行中的命令时，用户可向第二缓冲区输入下一行数第六章一、文件类型/按用途分类：系统文件，用户文件，库文件。（用户对以上三者的访问权限不同）/按文件中的数据形式分类：源文件，目标文件，可执行文件。/存取控制：只执行文件，只读文件，读写文件。（E,R,R/W）/按组织形式和处理方式分类：普通文件，目录文件，特殊文件。二、最基本的文件操作：创建文件，删除文件，读

31、文件，写文件，截断文件，设置文件的读/写位置。三、文件存在的两种形式：文件的逻辑结构：用户所能观察和访问到的文件的数据结构组织，独立于物理特性，容易检索和修改。它可以分为2类（1）有结构文件（2）无结构文件文件的物理结构：又称文件的存储结构，是指文件在外存上的组织形式。这不仅与存储介质 的存储性能有关，且与所采用的外存分配方式有关。四、文件逻辑结构的类型1、有结构文件：记录式文件a类：（1）定 长 记 录（2）变长记录b类：（1）顺序文件：通常是定长记录，（为何，因变长采用此方式查询速度慢）（2）索引文件:(3)索引顺序文件：顺序组织多个组，每组记录中的第一个记录设置一索引项。2、无结构文件：

32、流式文件以字节为单位，利用读/写指针进行访问。五、顺序文件1、逻辑记录的排序（1）按记录录入的时间排:串结构。（2）按关键字排序：顺序结构。后一种情况更有利于提高查询速度。如可用折半查找法等。2、对顺序文件的读/写操作定长记录顺序文件：例：顺序读易于定位，甚至可随机读取。变长记录：不易定位，只能顺序读取。六、索引文件由变长记录组成的顺序文件不容易直接存取，因此，为其建立一有序的索引表，对索引采用 折半查找，速度更快。特点:提高了速度,增加了存储开销放索引文件。增、删记录时，对索引表作相应的修改。七、索引顺序文件将顺序文件中若干记录分为一组，每组的第一项在索引表中占一项。速度：例1：1 0 0

33、0 0个记录,顺序文件：5 0 0 0次查找查到。索引顺序文件，设1（）（）个记录一组，索引表的找法设为顺序法的情况下，则平价查找次数为5 0+5 0=1 0 0 例2：1 0 0 0 0 0 0个纪录：F 索引：（1 0 0个纪录一组）平 价 查 找5 0 5 0次二级索引：平价查找5 0+5 0+5 0=1 5 0次八、连续分配方式连 续 分 配（磁带，磁盘都可采用）（顺序文件）每个文件分配一组相邻盘块。优点：因磁头移动距离小，顺序访问容易且速度快.缺点：要求连续空间，一段时间后需整理磁盘以消除外部碎片。必须事先知道长度，文件不易动态增长和删除。文件对应目录项(属性)中包含：始址、总块数、

34、最后一块字节数。九、连接方式分为隐式链接和显示连接两种形式。隐式链接：文件目录表中有start块号，每块中有指向下一块号的指针。缺点：只适合于顺序访问，对随机访问效率低，可靠性差。十、索引分配1、单级索引分配链接分配问题：不能高效直接存取；FAT需占较大的内存。概念：为每个文件分配一个索引块特点：支持直接访问；不会产生外部碎片问题：(1)文件较大时有利。文件较小时浪费外存空间(还需为小文件建索引块)(2)当文件较大时，索引块太多，查找速度减慢解决：当索引太大时，则需建立多级索引2、多级索引分配两级:为索引块再建立一级索引设一个盘块大小为1 k,每个盘块号占4byte,则一个索引块可存放256个

35、盘块号。所以两级索引存放的文件的盘块号总数为：256X256=64k,故文件的最大长度为64M三、四级:适用于文件更大时3.混合索引分配方式设 每 个 块 大 小 为4 k,一索 引 项（盘块号）占4字节，则1）直接地址i a dd（0）-i a dd（9）：小 文 件（=4 0 k）则立即读出。2）一次间址i a dd（1 0）：一次间址块中存放1K个盘块，4M大小3）多次寻址：二 次 间 址i a dd（l l）：1 K*1 K个盘块，4 G三次间址i a dd（1 2）:1 K*1 K*1 K个盘 块，4T例子：十一、文件控制块：为了能对系统中的大量文件施以有效的管理，在文件控制块中通常

36、有三 类信息基本信息，存取控制信息，使用信息。十二、索引结点：含文件描述信息。为何引入：FCB中含:文件名、描述信息，它们较占空间十三、多级目录结构：树 型 目 录 结 构（多级目录）特 点：能有效地提高对目录的检索速度允许文件重名便于实现文件共享（1）目录结构：目录文件中的目录项可为：目 录 文 件（节 点）数 据 文 件（树 叶）（2）路径名：（3）当前目录/工作目录。十 四、空闲表法和空闲链表法1、空闲表法：分配：首次/循环首次/最佳/最坏 回收：判断是否合并。由于连续分配比较快，因此对对换空间及小文件的管理适用。2.空闲链表法1）空闲盘块链 缺点：可能该链很长。2）空闲盘区链：一个盘区

37、含多个盘块，类似于内存分区分配与回收（合并）。十五、位示图1、盘块的分配：(1)顺序扫描，找一个或一组=0的块。(2)根据找到的行/列得以盘块号。b=n(i-l)+j(3)修改位图，令ma pi,j =l o2、回收(1)由磁块号得(i,j)i=(b-l)di v n+l j=(b-l)mod n+1(2)修改位图：令ma p|i,j =O o特点：因不占空间，可放入内存，易于访问以 下 PPT上的大题，大家看看并做做不懂得再问问：第四章(以下题目是老师讲到过的)例1：某系统采用页式存储管理策略，拥有逻辑空间32页，每 页2K,拥有物理空间1 M写出逻辑地址的格式若不考虑访问权限等，进程的页表

38、有多少项？每项至少有多少位？如果物理空间减少一半，页表结构应相应作怎样的改变？答：该系统拥有逻辑空间32页，故逻辑地址中页号必须用5位描述；而每页为2 K,因此，页内地址必须用11位描述，格式如下：1 51 1 1 00页号 页内地址每个进程最多3 2个页面，因此进程的页表项最多为3 2项；页表项只需给出页所对应的物理块块号，1M的物理空间可分为2 9个内存块，故每个页表项至少有9位。如果物理空间减少一半，则页表中页表项数不变，但每项的长度减少1位。例2：已知某分页系统，主存容量为6 4 K,页面大小为1 K,对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。(1)将

39、十进制的逻辑地址1 0 2 3、2 5 0 0、3 5 0 0、4 5 0 0转换成物理地址？（2）以十进制的逻辑地址1 0 2 3为例画出地址变换过程图？答：逻辑地址1 0 2 3：1 0 2 3/1 K,得页号为0,页内地址为1 0 2 3,查页表找到对应的物理块号为2,故物理地址为2 X 1 K+1 0 2 3=3 0 7 1i g辑地址2 5 0 0：2 5 0 0/1 K,得页号为2,页内地址为4 5 2,查页表找到对应的物理块号为6,故物理地址为6 X l K+4 5 2=6 5 9 6锹 辑 地 址3 5 0 0：3 5 0 0/1 K,得页号为3,页内地址为4 2 8,查页表找

40、到对应的物理块号为7,故物理地址为7 X 1 K+4 2 8=7 5 9 6逻辑地址4 5 0 0：4 5 0 0/1 K,得页号为4,页内地址为4 0 4,因页号不小于页表长度,故产生越界中断。第六章1、有一个计算机系统利用下图所示的位示图（行号、列 号 都 从0开始编号）来管理空闲盘块。如 果 盘 块 从1开始编号，每个盘块的大小为1 KB。（1）现要从文件分配两盘块，试具体说明分配过程。（2）若要释放磁盘的第3 00块，应如何处理？（这道题是较早前复习时老师提到的）01234567891011121314150111111111111111111111111111111111211011

41、1111111111131111110111101111：000000000000000015答（1）分配过程线形检索得：il=2,jl=2；i2=3,j2=6 o计算空闲盘块号：bl=il X1 6+jl +l=2 Xl 6+2+1 =3 5 b2=i2 X 1 6+j2+1 =3 X 1 6+6+1 =5 5修改位示图：令 m ap 2,2 =m ap 3,6 =1,并将对 应 块 3 5,5 5 分配出去(2)释放过程计算出第3 0 0 块所对应的二进制行号i 和ji=(3 00-1)/1 6=1 8 j=(3 00-1)%1 6=1 1修改位示图：令 m ap 1 8,l l =0o2

42、、对于采用混合索引分配方式的U N IX 系统中。如果每个盘块的大 小 为 5 1 2 字节，若盘块号需要3个字节来描述，而每个盘块最多存放1 7 0个盘块地址：(1)该文件系统允许的最大长度是多少？(2)将文件的字节偏移量1 5 000转换为物理块号和块内偏移量。(3)假设某文件的FCB已在内存中，但其他信息均在外存，为了访问该文件中某个位置的内容，最多需要儿次访问磁盘？(以下答案是百度来的，题目较原题只多部分内容，请注意相关解答)5.解：(I)该文件系统中一个文件的最大长度可达：(课本2 2 3 解秣)1 O+1 7 O+I 7 OX 1 7 0+1 7 0X 1 7()X 1 7 0=4

43、 9 4 2 08 0 块=4 9 4 2 08 0X5 1 2 字节=2 4 7 l 04 0KB(2)5 000/5 1 2 得而为9.余数为3 9 2,即逻辑块号为9,块内儡移位3 9 2.由于9 曲故可直接从该文件的F C B 的第9个地址力处得到物理就块号.块内偏移地址为3 9 2。1 5 000/5 1 2 得商为2 9.余数为1 5 2。即逻辑块号为2 9,块内偏移位1 5 2。由1 1 0=2 9 1 0+1 7 0,而2 9-1 0=1 9.故川直接从该文件的F C B 的第1 0个地址顶处.即一次间址项中得列一次间址块的地址;并从一次间址块的第1 9 项中获得对应的物理盘块

44、号,块内偏移地址为1 5 2,1 5 UOOO/5 1 2 得 商 为 2 9 2.余 数 为 4 9 6；即逻转块号为2 9 2,块内偏移位496由丁1 0+1 7(k=2 9 2 1 0+1 7 0+1 7 0X 1 7 0,r f n 2 9 2-(1 0+1 7 0)=1 1 2.1 1 2/1 7 0 得到商为 0，余数为 1 1 2.故可从该文件的F C B 的第I I 个地址项处，即1.次间址项中得到二次间址块的地址;并从二次间址块的第0 项中获得一次间址的地址，再从一次间址块的第1 1 2 项获用对应的物理盘块号，块内偏移地址为4 9 6.画出索引节点图(略)(3)由一文件的索引结点已在内存,为了访问文件中某个位置的内容,少需要1 次访问磁盘(即第次可通过索引结点的直接撤址直接读文件盘块);最多需要4 次访问磁盘(第一次访问是读三次间址块,第二次是读二次间址块,第三次是读一次间址块,第四次是读文件盘块M