1  操作系统重点                                 

              第一章

1.操作系统的目标:有效性;方便性；可扩充性；开放性

2.操作系统的管理对象包括：CPU、存储器、外部设备、信息（数据和软件）；

3.管理的内容：资源的当前状态（数量和使用情况）、资源的分配、回收和访问操作，相应管理策略（包括用户权限）

4.单道批处理系统：系统对作业的处理是成批进行的，内存中始终保持一道作业

5.单道批处理系统的特征：自动性；顺序性；单道性

6.多道程序设计技术带来的好处：提高CPU的利用率；可提高内存和I/O设备利用率；增加系统吞吐量。

7.*多道批处理系统的优缺点：资源利用率高；作业吞吐量大；用户交互性差；作业平均周转时间长

8.分时系统：在一台主机上连接了多个带有显示器和键盘的终端，同时允许许多个用户通过自己的终端，以交互方式使用用计算机，共享主机中的资源

9.分时系统的特征：多路性；独立性；及时性；交互性

10.实时系统：系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行

11.实时系统与分时系统特征比较：多路性：（实时控制系统的多路性主要表现在系统周期性地对多路现场信息进行采集，以及对多个对象或多个执行机构进行控制，分时系统中的多路性则与用户情况有关时多时少）独立性：（实时信息处理系统中的每个终端用户在向实时系统提出服务请求时是彼此独立操作地互不干扰，实时控制系统中，对信息的采集和对象的控制也都是彼此互不干扰）及时性：(实时信息处理系统对实时性的要求和分时性系统类似，都是以人所能接受的等待时间来确定的，而实时控制系统的及时性则是以控制对象所要求的开始截止时间或完成时间来确定的，一般为秒级到毫秒级，甚至有的要低于100微妙)交互性：(实时信息处理系统虽然也具有交互性但这里人与系统的交互仅限于访问系统中某些特定的专用服务程序，它不像分时系统那样能向终端用户提供数据处理和资源共享等服务)可靠性：(分时系统虽然也要求系统可靠但相比之下实时系统则要求具有高度上午可靠性)

12.操作系统的基本特征：

            并发性：是指两个或多个事件在同一时间间隔内发生

                     *并行性(parallel)是指两个或多个事件在同一时刻发生。

            共享性：多个进程共享有限的计算机系统资源

                方式分为：互斥共享方式（如音频设备）资源分配后到释放前不能被

                          其他进程所用；

                    同时访问方式（如可重入代码，磁盘文件）

           虚拟技术：指通过某种技术（分时或分空间）把一个物理实体映射为

                      若干个对应的逻辑实体。

                      实现方式包括：时分复用技术：虚拟处理机技术、虚拟设备技术；

                                     空分复用技术：虚拟磁盘技术、虚拟存储器技术

             异步性：进程是以人们不可预知的速度向前推进。

13.操作系统的各特征之间的关系：虚拟以并发和共享为前提；异步性是并发和共享的必然结果

14.操作系统的功能：处理机管理；存储管理；设备管理信息管理；用户接口

15.操作系统向用户提供的两种接口： 用户接口：包括联机用户接口，脱机用户接口、图形接口用户接口； 程序接口

第二章  进程管理

1、程序：是一组有序指令的集合，有存放于某种介质上，其本身并不具有运动的含义，是静态的

2、进程的特征：

（1）结构特征：为使程序（含数据）能独立运行，应为之配置一进程控制块（PCB）；由程序段、相关的数据段和PCB三部分构成了进程实体

（2）动态性：进程的实质是进程实体的一次执行过程，是进程的最基本的特征，进程由创建而产生，由调度而执行，由撤销而消亡

（3）并发性：指多个进程实体同存于内存中，且能在一段时间内同时运行

（4）独立性：指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位

（5）异步性：指进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行

3、程序和进程的区别：程序是静态的，不能并发执行；进程是动态的，能够并发执行

4、较典型的进程定义有：

 (1) 进程是程序的一次执行。

 (2) 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

 (3) 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

(4) 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

5、进程的三种基本状态（记住）

（1）就绪状态：当进程已分配到除ＣＰＵ以外的所有必要资源后，只要再获得ＣＰＵ，便可立即执行，进程这时的状态称为就绪状态

（２）执行状态：进程已获得ＣＰＵ，其程序正在运行

（３）阻塞状态：正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态。致使进程阻塞的典型事件有：请求Ｉ／Ｏ，申请缓冲空间等

6、进程控制块：是进程实体的一部分，操作系统中最重要的记录型数据结构。其作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。

7、原语：是由若干条指令组成的，用于完成一定功能的一个过程。

   原子操作：一个操作中的所有动作要么全做，要么全不做，是一个不可分割的基本单位

8、（1）引起进程阻塞和唤醒的事件：1）请求系统服务      2) 启动某种操作 3) 新数据尚未到达    4) 无新工作可做

  （2）进程阻塞：正在执行的进程，当所请求的某事件没出现时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。进程阻塞是进程自身的一种主动行为。

   (3) 程唤醒：当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup( )，将等待该事件的进程唤醒。

9、进程同步：是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

10、临界资源：临界资源是指每次仅允许一个进程访问的资源。如打印机、磁带机等都属于临界资源。诸进程间应采取互斥方式，实现对这种资源的共享。

11、临界区：把在每个进程中访问临界资源的那段代码称为临界区

12、同步机制应遵循的四条规则：（1）空闲让进 (2) 忙则等待 (3) 有限等待 (4) 让权等待

13、信号量机制

（1）整型信号量：一个用于表示资源数目的整型量，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。

（2）记录型信号量：一种采取了“让权等待”的策略使进程不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。

14、经典进程的同步问题：生产者—消费者问题  P58 （结合P82的课后练习复习）

15、进程通信：指进程之间的信息交换，其所交换的信息量少者是一个状态或数值，多者则是成千上万个字节。

16、管道机制提供的三方面协调能力：（1）互斥 （2）同步 （3）确定对方是否存在，只有确定了对方已存在时，才能进行通信

17、线程：不拥有系统资源，能独立运行的基本单位，也是独立调度和分派的基本单位。

第三章  

处理机调度的层次：（运行频率：低级调度>中级调度>高级调度）

1.高级调度（作业调度、长程调度、接纳调度）：将外存作业调入内存，创建PCB等，插入就绪队列。

一般用于批处理系统，分/实时系统一般直接入内存，无此环节。

2.低级调度（进程调度，短程调度）

主要是决定就绪队列中的哪个进程应获得处理机，然后由分派程序（Dispatcher）分派处理机。

两种调度方式：

1)非抢占方式：简单、系统开销小，实时性差  (如win31)

2)抢占方式：（1）优先权原则（2）短进程优先原则（3）时间片原则

3.中级调度（中程调度）：为提高系统吞吐量和内存利用率而引入的一 内---外存对换功能（换出时，进程为挂起或就绪驻外存状态）

面向系统的准则

（1）吞吐量高（特别是批处理）：单位时间完成作业数

（2）处理机利用率好：（因CPU贵，特别是大中型多用户系统）

（3）各类资源的平衡利用。

先来先服务和短作业（进程）优先调度算法

1.FCFS

特点：简单，有利于长作业（进程） 即CPU繁忙性作业,不利于短作业（进程）

2.短作业（进程）优先调度算法：SJ(P)F

提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）

特点：对长作业不利，有可能得不到服务

估计时间不易确定

计算：带权周转时间=周转时间/服务时间；完成时间：FCFS按顺序完成作业，SJF完成第一个作业后选择服务时间最短的作业依次完成；

3.最先优先权调度算法类型：

1）非抢占式优先权算法

2）抢占式优先权算法，实时性更好。

优先权类型：

1）静态优先权：进程优先权在整个运行期不变。

特点：简单，但低优先权作业可能长期不被调度（饥饿）。

2）动态优先权：进程优先级可随进程的推进或等待时间的增加而改变。

优点：长短兼顾   缺点：需经常计算各进程优先级

高响应比优先调度算法：（短作业RP大）

响应比Rp=（Tw+Ts）/Ts=（等待时间+要求服务时间）/要求服务时间

=优先权=响应时间/要求服务时间

4.时间片轮转调度：系统能在给定的时间内响应所有用户的请求

时间片大小的确定：太大：退化为FCFS；太小：系统开销过大

时间片大小不同时带权周转时间于完成时间也不同；

实时调度：对用户的实时响应

实现实时调度的基本条件

1．提供必要的调度信息

（1）就绪时间；（2）开始/完成截止时间；（3）处理时间；（4）资源要求；（5）优先级；

2．系统处理能力强

3.采用抢占调度方式

1）剥夺方式：一般都采用此方式

2）非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。

4.具有快速切换机制

1）具有快速响应外部中断能力。

2）快速任务分派

死锁：指多个进程在运行过程中因争夺资源而造成的一种僵局。

产生死锁的原因。

1、竞争资源引起死锁。

2.进程间推进顺序非法引起死锁。

产生死锁的必要条件

1．）互斥条件（资源的临界性）

2．）请求和保持条件

3．）不剥夺条件

4．）环路等待条件

处理死锁的基本方法

1．预防死锁：

   破坏4个条件之一：有效，使资源利用率低。

2．避免死锁：防止进入不安全态。

3．检测死锁：检测到死锁再清除。

4．解除死锁：与“检测”配套。

1、）互斥条件是资源固有属性，不能避免。

2、）摒弃请求和保持条件

3、）摒弃“不剥夺”条件，增加系统开销，且进程前段工作可能失效。

4、）摒弃“环路”条件

有序资源分配法：为资源编号，申请时需按编号进行。

缺点：（1）新增资源不便，（原序号已排定）（2）资源与进程使用顺序不同造成浪费

（3）用户不自由

在“避免死锁”方法中的判断条件

安全状态：能找到安全序列的状态为安全状态。（系统按某种顺序并发进程都能达到获得最大资源而顺序完成的序列为安全序列。）例：

银行家算法避免死锁安全序列：p2->p1->p3

available[j]=k: 系统现有Rj类资源k个；

max[i,j]=k: 进程i需要Rj的最大数k个；

alloc[i,j]=k: 进程i已得到Rj类资源k个；  

need[i,j]=k:    进程i需要Rj类资源k个

有：need[i,j]= max[i,j]－alloc[i,j]

（requesti       进程i请求资源数；worki：进程i执行完后系统应有资源数（也即可用数）

finish[i]：布尔量，表进程i能否顺序完成。 ）

Allocation：已分配；Available：可分配 Need：需求

 1.Work：=Available；2.Finish[i]=false  need<=work则Finish[i]=true;

3.work=Available+work； 直到进程的Finish[i]都为true时系统处于安全状态

死锁的解除

1）剥夺资源。

2) 撤消进程。

第四章

1.高速缓存：是现代计算机结构中的一重要部件，其容量大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB,访问速度快于主存储器.

2.磁盘缓存：本身并不是一种实际存在的存储介质，它依托于固定磁盘，提供对主存储空间的扩充，即利用主存中的存储空间，来暂存从磁盘中读出（或写入）的信息。

3.程序的装入方式分为：

1绝对装入方式：编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位,适用于单道系统。

2可重定位装入方式：静态重定位：装入时完成，主要工作是对相对地址中的指令和数据地址的调整过程；可重定位装入方式在装入后不能移动程序

3动态运行时装入方式：该情况一般在执行时才完成相对和绝对地址的转换且有硬件的支持,能保证进程的可移动性

4.连续分配方式分为：

1单一连续分配：是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。可把内存分为系统和用户两个部分系统区仅提供给OS使用，通常是放在内存的低址部分，用户区是系统区以外的全部内存空间，提供给用户使用。

2固定分区分配：是最简单的一种可运行多道程序的存储管理方式，是将内存用户空间分为若干个固定大小的区域，在每个分区中只装入一道作业，这样把用户空间划分为几个分区，便允许有多到作业并发运行。特点：简单，有碎片（内零头）,浪费。划分分区大小的方法：分区大小相等；分区大小不等。内存分配：将分区按大小排序，建立分区使用表，并将其地址、分配标识作记录

3动态分区分配：是根据进程的实际需要，动态地为之分配内存空间。

分区分配中常用的数据结构有两种形式：空闲分区表；空闲分区。

分区分配算法：

1首次适应算法FF：要求：空闲分区链以地址递增的次序链接；

特点：找到第一个大小满足的分区，划分，有外零头，低址内存使用频繁，增加系统开销

2循环首次适应算法：从上次找到的空闲分区的下一个开始查找。

特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。

3最佳适应算法：每次分配内存是总是把能满足要求、又是最小的空闲区分配给作业，避免大材小用。分区按大小递增排序；分区释放时需插入到适当位置

4最坏适应算法：选一个最大的空闲区分割给作业使用。优点：使剩下的空闲区不至太小，产生碎片的几率最小对中小作业有利，查找效率高。缺点：缺乏大的空闲分区

5快速适应算法：按空闲分区容量分类，对每类相同容量的所有空闲分区，单独设立一个空闲分区链表，管理索引表。优点：查找效率高；缺点：算法复杂，系统开销大。

5.动态分区存储管理中主要操作（分区分配操作）：

1分配内存：系统应用某种算法，从空闲分区链（表）中找到所需大小的分区

2回收内存：上邻空闲区：合并，改大小。下邻空闲区：合并，改大小，首址。上、下邻空闲区：合并，改大小。不邻接，则建立一新表项。

6.动态重定位的实现：p126

7.对换:把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。

类型：整体对换/进程对换：一整个进程为单位，应该于解决内存紧张

部分对换：页面对换/分段对换/部分对换：是请求分段和请求分页式存储管理的基础，提供虚存支持。

8.基本分页存储管理：不具备页面对换功能，不具备支持现实虚拟存储器的功能，要求把每个作业全部妆容内存后方可运行。

页面或页：将一个进程的逻辑地址空间分成若干个大小相等的片，并为各页加以编号；

物理块或页框：把内存空间分成与页面相同大小的若干个存储块，并为它们加以编号；

页号P；逻辑地址A；页面大小L；页内地址d

                  P= INT[A/L]         d=A mod L

例如，系统的页面大小为1KB，设A=2170B，求页号和页内地址。

解：1KB=2¹⁰B=1024B   页号P=INT[2170/1024]=2  页内地址d=2170mod1024=122

2.页表的作用：是实现从页号到物理块号的地址映射。

3.分页系统的地址变换机构：实现从逻辑地址到物理地址的转换，见P132 图4-13。

4.具有快表的地址变换机构：不具快表，则需两次访问内存：第一次访问页表；第二次访问得到绝对地址内容。

为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲器，又称为“联想寄存器”或“快表”。

6.分段系统的基本原理（只要看得懂就行）P136

7.段页式系统基本原理，是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名，即“先分段后分页”。

8.在段页式系统中，为了获得一条指令或数据，须三次访问内存。第一次访问段表取得页表始址；第二次访问页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正从第二次访问所得的地址中，取出指令或数据。

9.虚拟存储器的三大主要特征：

（1）多次性：一个作业被分成多次调入内存运行。

（2）对换性：允许在作业的运行过程中进行换进、换出。

（3）虚拟性：能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

4.7请求分页存储管理方式：

   1，请求分页中的硬件支持：一定容量的内存，外存的计算机系统，还需要页表机制，缺页中断机构以及地址变换机构。

  2、页面分配和置换策略。

1）固定分配局部置换。缺点：难以确定固定分配的页数.(少：置换率高    多：浪费)

2）可变分配全局置换

3）可变分配局部置换根据进程的缺页率进行页面数调整，进程之间相互不会影响。

4.8 页面置换算法：

   1）最佳置换算法，2）先进先出（FIFO）页面置换算法 3）最近最久（LRU）未使用置换算法 

4.9 请求分段存储管理方式：

   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操作，解脱CPU对I/O的组织、管理。

3、I/O控制方式：

  1）程序I/O方式：或称为忙-等待方式，即在处理机向控制器发出一条I/O指令启动输入设备输入数据时，要同时把状态寄存器中的忙/闲标志busy至为1，然后不断地循环测试busy。这种方式CPU资源浪费极大。

  2）中断驱动I/O控制方式：即当某进程要启动某个I/O设备工作时，便由CPU向相应的设备控制器发出一条I/O命令，然后立即返回继续执行原来的任务。

   这种方式用于字符设备I/O。

  3）直接存储器访问（DMA）I/O控制方式：用于块设备的I/O。

6.（5-4~~5-6）

（3）SPOOLing系统：

  概念：在联机情况下同时出现外围操作。

  组成：输入井和输出井   输入缓冲区和输出缓冲区   输入进场Spi和输出进程SPo

  特点：提高I/O速度；  将独占设备改造为共享设备；  实现了虚拟设备功能

（4）磁盘的结构和布局：P192页的图

（5）磁盘访问时间：1）寻道时间：TS=m*n+s

                     m：常量，n：磁道数，s：磁臂启动时间。

                 2）旋转延时间Tr：指定扇区旋转到磁头下所需时间。

                    设每秒r转，则Tr＝1/2r（均值）

                3）数据传输时间Tt＝b/rN

                            b：读写字节数N：每道上的字节数

                            访问时间：Ta=Ts+1/2r+b/rN

（6）磁盘调度

  （1）FCFS（Fisrt Come First Served）先来先服务

          特点：公平、简单，寻道时间长，相当于随机访问模式。

                仅适用于请求磁盘I/O的进程数目较少的场合。

 （2）、SSTF（最短寻道优先）最短寻道时间优先

             SSTF比FCFS有更好的寻道性能

          贪心的算法

          饥饿现象

          不能保证平均寻道时间最短

 FCFS调度算法                               SSTF调度算法

（3）SCAN 扫描算法（也称为电梯算法）。

SCAN算法：

           在移动方向固定的情况下采用了SSTF，以避免饥饿现象

           存在请求进程等待延迟现象

（4）、循环扫描CSCAN

           磁头单向移动

           一个方向读完，不是象SCAN那样回头，而是循环扫描。

           请求延迟时间：2T?T+Smax

SCAN调度算法示例                             CSCAN调度算法示例  

（7）磁盘高速缓存

  形式 ：逻辑上是磁盘、物理上是驻留在内存中的盘块

         固定大小和可变大小

（8）虚拟盘：利用内存空间去仿真磁盘，又称RAM盘

  和磁盘高速缓存区别：虚拟盘由用户控制；磁盘高速缓存由系统控制。

第六章

一、文件类型

ü  按用途分类：系统文件，用户文件，库文件。（用户对以上三者的访问权限不同）

ü  按文件中的数据形式分类：源文件，目标文件，可执行文件。

ü  存取控制：只执行文件，只读文件，读写文件。（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次

八、连续分配方式

连续分配（磁带，磁盘都可采用）（顺序文件）

每个文件分配一组相邻盘块。

优点：

因磁头移动距离小，顺序访问容易且速度快.

缺点：

要求连续空间，一段时间后需整理磁盘以消除外部碎片。

必须事先知道长度，文件不易动态增长和删除。

文件对应目录项（属性）中包含：

始址、总块数、最后一块字节数。

九、连接方式分为隐式链接和显示连接两种形式。

隐式链接：

文件目录表中有start块号，每块中有指向下一块号的指针。

缺点：只适合于顺序访问，对随机访问效率低，可靠性差。

十、索引分配

1、单级索引分配

链接分配问题：

不能高效直接存取；

FAT需占较大的内存。

概念：为每个文件分配一个索引块   

特点：支持直接访问；不会产生外部碎片

问题：

（1）文件较大时有利。文件较小时浪费外存空间（还需为小文件建索引块）

（2）当文件较大时，索引块太多，查找速度减慢

解决：当索引太大时，则需建立多级索引

2、多级索引分配

两级:为索引块再建立一级索引

设一个盘块大小为1k，每个盘块号占4byte，则一个索引块可存放256个盘块号。

所以两级索引存放的文件的盘块号总数为：256×256=64k,故文件的最大长度为64M

三、四级:适用于文件更大时

3.混合索引分配方式

设每个块大小为4k，一索引项（盘块号）占4字节，则

1)直接地址iadd(0)-iadd(9)：小文件（<=40k)则立即读出。

2)一次间址iadd(10)：一次间址块中存放1K个盘块，4M大小

3)多次寻址:

二次间址iadd(11)：1K*1K个盘块，4G

三次间址iadd(12): 1K*1K*1K个盘块，4T

例子：

十一、文件控制块：为了能对系统中的大量文件施以有效的管理，在文件控制块中通常有三类信息——基本信息，存取控制信息，使用信息。

十二、索引结点：含文件描述信息。

为何引入：FCB中含:文件名、描述信息，它们较占空间

十三、多级目录结构：

树型目录结构（多级目录）

特点：

能有效地提高对目录的检索速度  允许文件重名  便于实现文件共享

（1）目录结构：

目录文件中的目录项可为：目录文件（节点）、数据文件（树叶）

（2）路径名：  （3）当前目录/工作目录。

十四、空闲表法和空闲链表法

1、空闲表法：

分配：首次/循环首次/最佳/最坏     回收：判断是否合并。

由于连续分配比较快，因此对对换空间及小文件的管理适用。

2.空闲链表法

       1)空闲盘块链    缺点：可能该链很长。

       2)空闲盘区链：  一个盘区含多个盘块，类似于内存分区分配与回收(合并)。

十五、位示图

1、盘块的分配：

（1）顺序扫描，找一个或一组=0的块。（2）根据找到的行/列得以盘块号。b=n(i-1)+j

（3）修改位图，令map[i,j]=1。

2、回收

（1）由磁块号得(i,j)     i=(b-1)div n +1        j=(b-1)mod n +1

（2）修改位图：令map[i,j]=0。

特点：因不占空间，可放入内存，易于访问

以下PPT上的大题，大家看看并做做不懂得再问问：

第四章(以下题目是老师讲到过的)

例1：某系统采用页式存储管理策略，拥有逻辑空间32页，每页2K，拥有物理空间1M

   ①写出逻辑地址的格式

   ②若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？

   ③如果物理空间减少一半，页表结构应相应作怎样的改变？

答：

   ①该系统拥有逻辑空间32页，故逻辑地址中页号必须用5位描述；而每页为2K，因此，页内地址必须用11位描述，格式如下：

    15        11 10                          0

   ②每个进程最多32个页面，因此进程的页表项最多为32项；页表项只需给出页所对应的物理块块号，1M的物理空间可分为29个内存块，故每个页表项至少有9位。

   ③如果物理空间减少一半，则页表中页表项数不变，但每项的长度减少1位。

例2：已知某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。

   （1）将十进制的逻辑地址1023、2500、3500、4500转换成物理地址？

   （2）以十进制的逻辑地址1023为例画出地址变换过程图？

答：

       ①逻辑地址1023：1023/1K，得页号为0，页内地址为1023，查页表找到对应的物理块号为2，故物理地址为2×1K+1023=3071

   ②逻辑地址2500：2500/1K，得页号为2，页内地址为452，查页表找到对应的物理块号为6，故物理地址为6×1K+452=6596

   ③逻辑地址3500：3500/1K，得页号为3，页内地址为428，查页表找到对应的物理块号为7，故物理地址为7×1K+428=7596

   ④逻辑地址4500：4500/1K，得页号为4，页内地址为404，因页号不小于页表长度，故产生越界中断。

第六章

1、有一个计算机系统利用下图所示的位示图（行号、列号都从0开始编号）来管理空闲盘块。如果盘块从1开始编号，每个盘块的大小为1KB。

   （1）现要从文件分配两盘块，试具体说明分配过程。

   （2）若要释放磁盘的第300块，应如何处理？（这道题是较早前复习时老师提到的）

答：（1）分配过程

线形检索得：i1=2，j1=2； i2=3，j2=6。

计算空闲盘块号：

 b1=i1×16+j1+1=2×16+2+1=35    b2=i2×16+j2+1=3×16+6+1=55

修改位示图：

 令map[2，2]=map[3，6]=1，并将对应块35，55分配出去

（2）释放过程

计算出第300块所对应的二进制行号i和j

i=（300-1）/16=18  j= （300-1）% 16=11

修改位示图： 令map[18，11]=0。

2、对于采用混合索引分配方式的UNIX系统中。如果每个盘块的大小为512字节，若盘块号需要3个字节来描述，而每个盘块最多存放170个盘块地址：

(1) 该文件系统允许的最大长度是多少？

(2) 将文件的字节偏移量15000转换为物理块号和块内偏移量。

(3) 假设某文件的FCB已在内存中，但其他信息均在外存，为了访问该文件中某个位置的内容，最多需要几次访问磁盘？

（以下答案是百度来的，题目较原题只多部分内容，请注意相关解答）

操作系统重点