【文档说明】计算机操作系统课件.ppt，共(150)页，2.230 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-76775.html

以下为本文档部分文字说明：

2022年12月1日星期四10时1分50秒计算机操作系统第6章虚拟存储器6.1虚拟存储器的基本概念6.2请求分页存储器管理方式6.3页面置换算法6.4请求分页系统的性能分析6.5请求分段存储器管理方式6.6段的动态链接（补充）2022年12月1日星期四10时1分50秒计算机操作系统6.1虚拟存储

器的基本概念实存管理有两个明显的特性：一次性：作业一次全部入主存；驻留性：作业进入主存后一直驻留直到完成。实存管理的不足：一、虚拟存储器的定义从用户角度，将系统可提供的比实际大很多的内存容量，称为虚拟存储器。二、虚存的2种实现方式请求分页系统和请求分段系统。硬件支持：页/段表扩充，缺页/段中断，地

址变换虚存的4个特征2022年12月1日星期四10时1分50秒计算机操作系统1、离散性：采用离散分配方式；2、多次性：一个作业分成多次调入主存运行；3、对换性：将得不到运行的程序、数据调至外存盘交换区；4、虚拟性：（

OVER）三、虚存的4个特征2022年12月1日星期四10时1分50秒计算机操作系统6.2请求分页存储器管理方式6.2.1请求分页中的硬件支持一、页表机制页号，页框号，状态位P，访问位A，修改位M，外存地址二、缺页中断机构与一般中断的2点区别：1、

是在指令执行期间，发现指令/数据不在主存时产生并处理；2、一条指令在执行期间，可能会产生多次缺页中断。要求系统能保存多次中断的状态。（例）地址变换2022年12月1日星期四10时1分50秒计算机操作系统多次缺

页中断示例设：主存页框大小为128字，有128*128的数组；VarA:array[1..128]ofarray[1..128]ofinteger;程序段：fori:=1to128forj:=1to128A[i][

j]:=0;在Pascal中，数组元素的存放格式为以行为主序，问：执行时缺页次数为多少？A[1,1]A[1,2]A[1,3]...A[1,128]...A[128,1]A[128,2]A[128,3]...A[128,128]...1页1页2022年12月1日星期四10时1分50秒计算机操作系统有

快表的地址变换过程：(P170，F6-2)1、存储保护检查：页号>页表长度？是，越界中断；否则2；2、查快表：找到，修改访问位对于写操作置修改位，并形成物理地址访问；若未找到，查页表状态位：在主存，将

表目写入快表；否则，缺页中断。OVER三、请求分页的地址变换机构页面分配2022年12月1日星期四10时1分50秒计算机操作系统一、最小物理块数保证进程正常运行所需最小的页框数，其值取决于指令的格式、功能和寻址方式。采

用直接寻址：最小物理块数为2；（存放指令的页和存放数据的页）采用间接寻址：最小物理块数为3；6.2.2页面分配页面分配和置换策略2022年12月1日星期四10时1分50秒计算机操作系统二、页面分配和置换策略(三种)分配：固定/可变；置换：局部/全局。1、固定分配局部置换；2、可变分配全局置换；

先分配一定数额，OS保留一个空闲页框队列。进程缺页时，申请新页框：有，追加分配；无，全局置换。3、可变分配局部置换；先分配一定数额，OS保留一个空闲页框队列。进程缺页时，申请新页框：有，追加分配；无，局部置换。分配算法2022年12月1日

星期四10时1分50秒计算机操作系统1、平均分配算法2、按进程大小比例分配算法每个进程分配的页框数为：Si/S*m3、考虑优先权的分配算法系统的总页框数分为两部分：一部分，按比例分配；另一部分，按进程的优先权适当追加；6.2.3页面调入3策略1、何时调入：预调/请调；2、何处调入：交换区/文件区

；3、调入过程：OVER三、固定分配的分配算法2022年12月1日星期四10时1分50秒计算机操作系统6.3页面置换算法(Page-ReplacementAlgorithms)“抖动”(Thrashing)：刚刚被换出的页很快又被访问，需再次调入。使进程花费大部分时间进行页面的置换，称

进程发生了“抖动”。为避免抖动的发生，应选择合适的置换算法。一、最佳置换算法二、先进先出置换算法（FIFO）（例）三、最近最久未使用置换算法(LeastRecentlyUsed)思想：记录页面上次被访问的时间，选择最近最久未使用的页面淘汰。（例）

比较FIFO与LRU得出何结论？OVER页面置换算法（续1）2022年12月1日星期四10时1分50秒计算机操作系统FIFO置换算法示例设页面走向为：1,2,3,4,1,2,5,1,2,3,4,5。当分配的物理块数分别为3、

4时缺页次数/缺页率各为多少2022年12月1日星期四10时1分50秒计算机操作系统S=3标志1+21+321+432+143+214+521+152215321+432+543+缺页次数=10缺页率=10/12LRU

置换算法示例设页面走向为：1,2,3,4,1,2,5,1,2,3,4,5。当分配的物理块数分别为3、4时缺页次数/缺页率各为多少？S=4标志1+21+321+4321+143221435214+152421543215+4321

+5432+缺页次数=8缺页率=8/122022年12月1日星期四10时1分50秒计算机操作系统四、Clock置换算法(LRU的近似算法)1、简单ClockNRU(NotRecentlyUsed)思想：内存中所有页面组成循环队列，置换算法选择淘汰页面时，依次检查访问位：为0，换出；为1，重置为0

，继续检查下一页面。2、改进型Clock置换算法（算法见P179）通过访问位A、修改位M的组合值来确定。A0011M0101淘汰序号0123OVER页面置换算法（续1）页面置换算法（续2）2022年12月1日星期四10时1分50秒计算机操作系统页面置换算法（续2）五、最少使用置换算法(Least

FrequentlyUsed)思想：选择近期使用次数最少的页面淘汰。实现：为每个页面设置一移位寄存器，记录该页被访问的频率。六、页面缓冲算法(PageBufferingAlgorithm)思想：采用可变分配、局部置换方式。置换算法FIFO，被置换的页按是否被修改过而入系统设置的两个链表队

列：修改页面链表、空闲页面链表。如果再次产生缺页中断，首先检查链表队列：有，恢复到进程驻留集中；无，取空闲页面链表中第一页分配。修改页面链表中页面达到一定数量时，集中回写，减少I/O次数。OVER2022年12月1日星

期四10时1分50秒计算机操作系统6.4请求分页系统的性能分析分析内容：1、缺页率对系统性能的影响；2、将缺页率保持在一个合理水平时应分配的页框数。6.4.1缺页率p对有效访问时间T的影响T=(1-p)*ma+p*缺页中断时间t=ma+(t-ma

)*p(ma为存储访问时间)t由三部分组成：1、缺页中断服务时间；2、缺页的读入时间；3、进程恢复执行时间。由于t>>ma，所以T直接比例于p。(P180例,OVER)工作集2022年12月1日星期四10时1分

50秒计算机操作系统进程缺页率高，不仅会使其运行进度减慢，而且增加了CPU开销和通道及外设的负担。1968年，Denning根据程序的局部性理论(进程对页的访问不是均匀的，而是集中的。进程访问页面集合的变化，从一个时间段到另一个时间段是缓慢过渡的)，提出了工作集理论(属LRU算法的发

展)。工作集：进程在某段时间内实际访问页的集合。OVER6.4.2工作集/驻留集(WorkingSet)具体表述2022年12月1日星期四10时1分50秒计算机操作系统设进程在t-到t时间段内访问页的工作集记为：W(t,)（为工作集窗口尺寸）则：|W(t,)|为工作集中包含的页

面数工作集W是二元函数：1、W是t的函数，随时间不同，工作集不同；2、W是的非降函数。若过大，甚至将整个作业地址空间包含在内，则失去虚存意义；过小，会导致频繁缺页。工作集的具体表述抖动的产生和预防2022年12月1日星期四10时1分50秒

计算机操作系统一、产生原因随着多道程序度的提高，CPU的利用率随之而提高，并在某时达到峰值。此时，如果道数再增加，系统缺页次数增加，产生抖动。二、抖动预防的4种方法1、采用局部置换策略，使抖动控制在局部范围；2、在CPU调度程序中引入工作集算法，控制道数；3、采用L=S准则：调整道数，使产生

缺页频率的平均时间=系统处理缺页的平均时间；4、挂起若干进程。6.4.3抖动的产生和预防2022年12月1日星期四10时1分50秒计算机操作系统6.5请求分段存储器管理方式6.5.1请求分段中的硬件支持一、段表机制段名，段长，内存起址，状态位，存取方式，

访问位，修改位，增补位，外存起址二、缺段中断在一条指令的执行期间，产生并处理中断，且可能产生多次缺段中断。（P185，F6-12）三、地址变换机构(P186,F6-13)OVER分段的共享与保护2022年12月1日星期四10时

1分50秒计算机操作系统共享方式：每个共享进程段表中，在相应共享段表目中，指向共享段在内存的起址即可。系统实现：一、设置共享段表/现行分段表二、建立共享段分配、回收操作过程三、完善分段保护机制，有3种常用措施：1、越界检查：2、存取控制检查：3

、环保护机构：类似于软件的层次结构，每层有不同的优先数，0环为操作系统。2个访问规则：A、一个程序可以访问同环或低优先权环中数据；B、一个程序可以调用同环或高优先权环中的服务；6.5.2分段的共享与保护2022年12月1日星期四10时1分50秒计算机

操作系统共享段表说明：1、共享段只有当所有共享进程都不再需要时(Count=0)，才会被释放；2、对同一个共享段，不同进程可以使用不同的段号来共享该段。段名段长内存起址状态外存起址共享进程计数Count

状态进程名进程号段号存取控制......2022年12月1日星期四10时1分50秒计算机操作系统共享段的分配、回收分配：第一个请求使用共享段的进程申请内存分区，调入，修改共享段表相应内容；以后其它进程使用该共享段时，首先在本进程段表中填

入该共享段的物理地址；然后在共享段表中增加一表目，填入进程名，存取控制等信息，并完成Count+1。回收：执行Count-1，取消共享段表中的表目OVER2022年12月1日星期四10时1分50秒计算机操作系统6.6段的动态链接静态链接方式，入内存之前完成：1、外部调用链接；2、重

定位；缺点：由于被链接的分段可能不使用，造成内存和机时的浪费。为克服上述不足，分段存储管理中可采用动态链接方式。即在运行过程中，需要使用某分段时，再完成链接。动态链接实现2022年12月1日星期四10时1分50秒计算机操作系统一、设置连接间接字寻址方式中，包含直接地址的字称为间接字

。分段管理中，间接寻址使用较多，为标志直接地址的段是否已被链接，在进程间接字中设置标志位L(链接标志位)，将这样的间接字称为链接间接字。L=1/0，表示该分段未/已链接；当间接寻址时：若L=1，产生链接中断；若L=0，按链接间接字中的直接地址操作。动态链接的实现L直接地址

编译的准备工作2022年12月1日星期四10时1分50秒计算机操作系统编译原则：1、若被编译段中语句是访问本段单元，则将其编译成直接寻址格式；2、若被编译段中语句是访问外段单元，则将其编译成间接寻址格式。分3个步骤：（例）A、在本段中增设链接间接字，并设L=1；

B、开辟另一个存储单元，保存被访问段的符号名、段内地址(S,w)；C、将间接链接字的地址场指向该符号名所在单元的地址。编译的链接准备工作链接中断2022年12月1日星期四10时1分50秒计算机操作系统编译的链接准备工作示例设：有一作业如下图所示：...Call[x]|<

y>...Y:编译...Call*main|100...1001021main|102[x]|<y>Main分段入内存后0#X分段3#03|yOVER2022年12月1日星期四10时1分50秒计算机操作系统执行间接寻址指令时，硬件判断L=1，触发链接中断，转链接中断处理程序。经4步处理：1

、通过链接间接字，找欲访问的段名|段内地址([x]|<y>)；(例)2、查共享段表、进程段表，判断该段是否在内存；3、是，查段号并修改链接间接字为段号及段内地址，并设置L=0，返回断点；4、否，分配内存，读入该分段，转第3步。三、链接中断2022年12月1

日星期四10时1分50秒计算机操作系统7.1I/O系统的组成7.2I/O控制方式7.3缓冲管理7.4设备分配7.5设备处理第7章设备管理2022年12月1日星期四10时1分50秒计算机操作系统7.1I/O系统的组成7.1.1I/O系统的结构一、微型机I/O系统无通道的I/O系统，以CPU为中心（图

例）。二、主机I/O系统有通道的I/O系统，以主存为中心，属四级结构（图例）OVER设备类型2022年12月1日星期四10时1分50秒计算机操作系统微型机I/O系统结构图例CPURAMI/O1I/On......2022年12月1日星期四10时1分50秒计算机操作系统主机I/O系统结

构图例主机RAMCPU通道1控制器1控制器2设备1设备2设备3设备4通道2控制器3控制器4设备5设备6设备7设备8增加通路按任意键...2022年12月1日星期四10时1分50秒计算机操作系统一、按传输速率分1、

低速设备：几百字节/秒，键盘、鼠标；2、中速设备：几千字节/秒，打印机；3、高速设备：数兆字节/秒，HDD、TYPE；二、按信息交换单位分1、块设备：信息存取以块为单位（Block）;2、字符设备：以字符为单位；三、按共

享属性1、独占设备；2、共享设备；3、虚拟设备；OVER7.1.2设备类型设备控制器2022年12月1日星期四10时1分50秒计算机操作系统DC是CPU与I/O设备间的接口，属于可编址设备，即：DC连接多个设备

时，具有多个设备地址。分为：控制字符设备/块设备的控制器。一、功能1、接收、识别CPU发来的I/O命令(Read,Write...);2、通过数据寄存器，完成数据的存储、转发；3、借助状态寄存器，记录所连接设备的状态；4、通过地址译码器，实现

所连接设备的地址识别；二、组成由3部分组成（图例）OVER设备控制器DC(DeviceController)通道2022年12月1日星期四10时1分50秒计算机操作系统设备控制器组成图例(P200,F7-3)与CPU接口与设备接口数据寄存器

控制/状态寄存器I/O逻辑接口1接口1数据线地址线控制线数据数据状态状态控制控制2022年12月1日星期四10时1分50秒计算机操作系统一、通道设备的引入目的：提高CPU的利用率。与CPU的2个区别：1、仅能执行与I/O有关指令；2、无独立主存，

与CPU共享；有通道系统I/O示例：7.1.4I/O通道进程需I/OCPU给通道发I/O指令（通道程序首址、设备）通道取通道程序执行I/O中断通知CPUOVER通道的类型2022年12月1日星期四10时1分50秒计算机操作系统1

、字节多路通道(ByteMultiplexChannel)（图）实现：通道含有许多非分配型子通道，每个子通道连接一台I/O设备。各子通道按时间片轮转方式使用主通道，每次传输一个字节。(用于连接低中速设备)2、数组选择通道(BlockSelectorChannel)实现：一个通道可连接多台I/O设

备，但某段时间只允许一台设备I/O，并独占通道直到传输完成。传输时，每次传输一批数据。(用于连接高速外设)3、数组多路(BlockMultiplexChannel)实现：结合选择通道的高速与字节多路通道分时并行

的优点，传输按成组分时方式进行。OVER二、通道的3种类型瓶颈问题2022年12月1日星期四10时1分50秒计算机操作系统为降低系统成本，并非每一个I/O设备都有自己独立的控制器和通道，所以造成多台I/O设备争用控制器、通道。

使通道成为I/O的主要瓶颈，造成系统吞吐量下降。解决2方法：1、增加通路，提高系统的灵活性、可靠性；(图例)2、设置缓冲区，增加I/O设备的独立性。三、瓶颈问题2022年12月1日星期四10时1分51秒

计算机操作系统字节多路通道示意图字节多路通道控制器1控制器2控制器n...2022年12月1日星期四10时1分51秒计算机操作系统7.2I/O控制方式I/O控制方式发展宗旨：尽量减少CPU对I/O的干预，提高CPU的利用率。发展的

四个阶段：1、程序I/O方式；2、中断驱动I/O控制方式；3、DMA方式；4、通道方式；2022年12月1日星期四10时1分51秒计算机操作系统一、程序I/O方式（ProgrammedI/O）早期无中断系统工作特点：1、“忙测试”：(1)CPU向I/O控制器发一条I/O命令，启动I/O设

备；(2)置设备状态寄存器中busy为1；(3)循环测试busy，直到busy=0;2、每一次，I/O一个字（符）P203，F7-7（a）2022年12月1日星期四10时1分51秒计算机操作系统二、中断驱动I/O控制方式有中断的系统。工作过程：1、进程I/O时，CPU发I/O命

令给设备控制器DC(DeviceController)，并继续工作；2、DC接到命令，控制设备I/O；3、I/O完成，DC向CPU发中断信号；4、CPU检查I/O中是否有错，有：处理；无：继续；每次I/

O一个字（符）2022年12月1日星期四10时1分51秒计算机操作系统三、DMA(DirectMemoryAccess)方式特点：1、I/O基本单位是数据块(Block)；2、I/O是直接从设备入内存，或相反；3、一块/多块完成后，CPU才干预；DMA组成P205工作过程3

步：1、进程I/O，CPU给控制器发送：I/O命令、内存/外存起址、传输字节数；2、CPU启动控制器进行数据I/O；3、I/O完成，DMA向CPU发送中断信号；2022年12月1日星期四10时1分51秒计算机操作系统DMA组成Cou

nt内存起址CPU数据寄存器DR内存地址MAR计数器DC命令寄存器DRI/O逻辑接口1接口n2022年12月1日星期四10时1分51秒计算机操作系统四、通道方式工作过程：1、进程I/O，CPU向通道发送I/O命令，给出通道程序的起址、需访问的设备等；2、通道执行通道程序，

完成I/O，并中断通知CPU。I/O量：以一组数据块为单位。2022年12月1日星期四10时1分51秒计算机操作系统7.3缓冲管理缓冲引入原因1、缓和CPU与I/O设备间速度不匹配的矛盾；2、减少CPU对I/O的干预；3、提高CPU和

I/O设备之间的并行程度；缓冲可分4类：1、单缓冲2、双缓冲3、循环缓冲(多缓冲，类似于生产者-消费者中的缓冲区)4、缓冲池2022年12月1日星期四10时1分51秒计算机操作系统单缓冲(SingleBuffer)工作方式：

进程发出I/O请求时，操作系统在主存分配一个缓冲区，通过缓冲区完成I/O。例：从块设备输入处理（性能分析）1、将一块输入数据输入缓冲区，时间T；2、系统将缓冲区数据复制到用户区，时间M;3、CPU对输入的数据处理，时间C；用户进程操作系统BUF数据区CPU处理C复制M设备输入T2022年12月

1日星期四10时1分51秒计算机操作系统单缓冲性能分析无缓冲区时，每一块数据的处理时间为：T+C单缓冲区时，每一块数据的处理时间为：MAX(C,T)+M由于M<<T或C，所以上式近似为：MAX(T,C)2

022年12月1日星期四10时1分51秒计算机操作系统缓冲池(BufferPool)单、双、循环缓冲都属专用缓冲。为提高缓冲区的利用率，目前广泛采用共用缓冲池，即缓冲池中的缓冲区可供多个进程共享。一、缓冲池的组成缓冲池中的缓冲区既可用作输入缓冲，

也可用作输出缓冲，所以缓冲池中的缓冲区应有三个队列：1、空缓冲队列emq；队首F(emq)，队尾L(emq)2、输入队列inq；队首F(inq)，队尾L(inq)3、输出队列outq；队首F(outq)，队尾L

(outq)四种工作缓冲区2022年12月1日星期四10时1分51秒计算机操作系统为标志缓冲池中各缓冲区的动态过程，系统设置了四个工作缓冲区。1、用于收容输入数据的工作缓冲区hin2、用于收容输出数据的工作缓冲区hout3、用于提取输入数据的工

作缓冲区sin4、用于提取输出数据的工作缓冲区sout相应缓冲区可工作在收容输入、收容输出、提取输入、提取输出四种工作方式下。图例四种工作缓冲区Getbuf和Putbuf过程2022年12月1日星期四10时1分51

秒计算机操作系统缓冲区工作方式图例缓冲池hinsinsouthout用户进程收容输入收容输出提取输入提取输出2022年12月1日星期四10时1分51秒计算机操作系统Getbuf(type)：用于从type指定的队列中得到一个缓冲区；Putbuf(type,number)用于将参数num

ber所指示的缓冲区，挂在type所指队列的队尾；由于缓冲池中的缓冲区被多个进程共享，所以出、入队的操作应该互斥。系统对每个队列type设置2个信号量：资源信号量RS(type);互斥信号量MS(type)；Getbuf和P

utbuf过程描述二、Getbuf和Putbuf过程工作方式2022年12月1日星期四10时1分51秒计算机操作系统Getbuf和Putbuf过程描述ProcedureGetbuf(type)beginwait(RS(type))

;wait(MS(type));B(number):=Takebuf(type);signal(MS(type));endProcedurePutbuf(type,number)beginwait(MS(type));Addbuf(type,number);signal(MS(ty

pe));signal(RS(type));end2022年12月1日星期四10时1分51秒计算机操作系统1、收容输入工作方式（从I/O设备输入到缓冲）(1)进程需输入数据时，调用Getbuf(emq

)，得到一个空缓冲作为收容输入的工作缓冲区hin；图例(2)将数据输入到hin中；(3)调用Putbuf(inq,hin)，将hin入inq的队尾；2、提取输入工作方式(从inq提取所需的数据使用)(1)计算进程需输入数据

时，调用Getbuf(inq)，取得一个缓冲区作为提取输入工作缓冲区sin；(2)计算进程使用完成后，调用Putbue(emq,sin)，将缓冲区挂到emq队尾；其余方式自学三、工作方式2022年12

月1日星期四10时1分51秒计算机操作系统收容输入工作方式图例emq...inq...输入进程Getbuf(emq)hin从设备输入数据Putbuf(inq,hin)F(inq)L(inq)2022年12月1日星期四10时1分51秒计算机操作系

统7.4设备分配功能：进程发出I/O请求时，按照一定的策略将I/O所需设备分配给进程。(有通道结构)7.4.1设备分配中的4个数据结构1、设备控制表DCT(DeviceControlTable)系统为每个设备配置一张DCT,用于记录该设备的相关参数。

2、控制器控制表COCT(ControllerControlTable)3、通道控制表CHCT(ChannelControlTable)4、系统设备表SDT(SystemDeviceTable)设备分配应考虑的因素2022年12月1日星期四10时1分51秒计算机操作系统设备分配中的4个数据

结构设备类型type设备标识符：deviceid设备状态：等待/不等待忙/闲指向控制器表的指针重复执行次数/时间设备队列的队首指针控制器标识符控制器状态：忙/闲与控制器相连的通道指针控制器队列的队首指针控制器

队列的队尾指针通道标识符通道状态：忙/闲与通道相连的控制器指针通道队列的队首指针通道队列的队尾指针DCTCOCTCHCT设备类型设备标识符DCT驱动程序入口表目1表目iSDT2022年12月1日星期四10时1分51秒计算

机操作系统一、设备的固有属性：独占、共享、虚拟；二、设备分配算法：1、FCFS；2、优先级高者优先；三、设备分配的安全性1、安全分配方式：进程发出I/O请求后，立即阻塞，直到I/O完成；2、不安全分配方

式：只有申请的设备无法满足要求时，进程才阻塞。为保证安全性，需在分配时作安全性检查。over7.4.2设备分配应考虑的因素设备的独立性2022年12月1日星期四10时1分51秒计算机操作系统也称设备无

关性：应用程序独立于具体使用的物理设备。2个相关概念1、逻辑设备：用户程序中使用某类设备名称（PRN）来使用该类设备；2、物理设备：系统I/O进程实际执行I/O操作时，使用的设备名称（整数编码），物理设备直接指向某台具体设备。OVER7.4.3设备的独立性(Dev

iceIndependence)实现设备独立性的好处2022年12月1日星期四10时1分51秒计算机操作系统1、增加设备分配时的灵活性(1)某设备被占用，可分配其它同类空闲设备；(2)系统增加同类外设时，无需修改源程序即可使用；(3)进程使用设备故障时，系统可

分配其它同类设备给进程；2、易于实现I/O重定向重定向(redirection)：I/O进程，不改变应用程序即可改变设备完成数据的I/O。例：dir>prnOVER实现设备独立性的好处逻辑设备到物理设备的映射2022年12月1日星期四10时1分51秒计算机操作系统1、

逻辑设备表LUT(LogicalUnitTable)逻辑设备名物理设备号驱动程序入口地址/dev/tty31024/dev/print52046......2、LUT的2种设置方式(1)整个系统设置一张缺点：不同用户的

逻辑设备名不允许相同。(2)每个用户进程设置一张，置于进程PCB中。逻辑设备到物理设备的映射SPOOLing技术2022年12月1日星期四10时1分51秒计算机操作系统思想：通过在高速外存设置I/O缓冲，将独占型设备改造成为可共享的虚设备。SPOOLing----

在线同时外围操作(SimultaneousPeripheralOperationOn-Line)一、SPOOLing系统的组成(3部分)1、输入井和输出井在磁盘开辟存储空间，收容输入、输出数据。2、输入缓冲和输出缓冲在内存设置缓冲，暂存从设备输入或从输入井输入的数据。3、输入进程SPi和输

出进程SPo7.4.5SPOOLing技术工作过程2022年12月1日星期四10时1分51秒计算机操作系统SPOOLing系统组成示意图SpiSpo输入缓冲区InBuff输出缓冲区OutBuff输入设备输出设备磁盘输

入井输出井2022年12月1日星期四10时1分51秒计算机操作系统输入过程：SPOOLing输入程序Spi主要工作是负责将输入设备上的作业以作业为单位通过内存缓冲区传输至输入井，并建立JCB，同时维持后备队列。Spi是系统中一个独立的进程，无任务时，处于等待状态（睡眠状态

）。Spi被唤醒的时机有3个，Spi被唤醒后，根据收到的信号作相应的工作：1、当输入设备上有作业输入请求时；2、当输入设备工作结束时；3、向磁盘输入井传输一道作业结束时；OVER二、SPOOLing系统的工作过程SPOOLing的特点2022年12月1日星期四10时

1分51秒计算机操作系统根据唤醒时机不同，Spi的工作1、设备有输入请求；Spi启动相应通道，将作业输入到内存输入缓冲区，自身进入等待；2、输入设备出现“结束中断”；Spi根据输入缓冲区中的内容，建立JCB，并在输入井中为作业分配空间，启动磁盘通道将输入缓冲

区中作业输到输入井，自身进入等待。3、向输入井传输作业结束，出现“磁盘结束”中断；Spi将作业JCB加入后备队列，并向作业调度程序发信号，引起作业调度，自身进入等待。OVER2022年12月1日星期四10时1分51秒计算机操作系统1、提高

了I/O速度；由对低速设备的I/O改为对输入/输出井的存取，缓和了CPU与低速设备的矛盾；2、将独占型设备改造为共享设备；3、实现了虚拟设备功能；多个进程同时（并发）地从输入/输出井存取数据，感觉是独占I/O设备。OVERSPOOLing的3特点2022年12月1日

星期四10时1分51秒计算机操作系统7.5设备处理设备处理程序/设备驱动程序功能：接收上层软件的I/O命令，转化为具体的I/O要求，控制设备完成I/O操作。处理6过程：1、将抽象要求转换为具体要求；即将I/O命令转换为控制

器可接受的命令格式；例：磁盘块号转换为盘面、道号、扇区；2、检查I/O请求的合法性；3、读出和检查设备状态；4、传送必要的参数；如传输字节数、内存地址；5、设置工作方式；异步/同步通信；6、启动I/O设备；完成I/O。2022年12月1日星期四10

时1分51秒计算机操作系统第8章文件系统8.1文件和文件系统8.2文件结构8.3目录管理8.4文件共享8.5文件保护2022年12月1日星期四10时1分51秒计算机操作系统8.1文件和文件系统8.1.1文件、记录和数据项（数据元素/字段/域）记录：一组相关数据项的集合；文件：具有文件

名的一组相关信息的集合；8.1.2文件类型（5）1、按用途分：系统、用户、库文件；2、按存取控制属性：只读、读写、只执行文件；3、按文件的逻辑结构：有结构、无结构文件；4、按文件的物理结构：顺序、链接、索引文件；5、按文件中的数据形式：源、目标、可执

行文件；文件系统模型2022年12月1日星期四10时1分51秒计算机操作系统8.1.3文件系统模型文件系统：用于操纵和管理各种文件，方便用户使用文件的软件集合。文件系统模型层次结构(P229，F8-2)一

、管理对象文件、目录、外存空间二、操纵和控制内容1、文件存储空间管理；2、目录管理；3、地址映射；4、R/W管理；5、共享和保护；三、文件系统接口1、命令接口；2、程序接口；OVER文件操作2022年12月1日星期四10时1分51秒计算机操作系统文件操作分2大类：一、

对记录操作记录增、删、改；记录的查询；二、对文件的操作创建文件；删除文件；读写文件；设置读写位置；8.1.4文件操作2022年12月1日星期四10时1分51秒计算机操作系统文件系统模型层次结构文件系统接口逻辑文件系统基本I/O管理程

序基本文件系统（物理I/O层）I/O控制层（设备驱动程序）对象及其属性说明对对象操纵和管理的软件集合启动I/O操作、接收中断处理内、外存数据交换设备选择、地址映射、空闲块管理、缓冲设置目录管理、存取控制验证

命令、程序接口文件、目录、外存2022年12月1日星期四10时1分51秒计算机操作系统8.2文件结构文件结构分2类：1、逻辑结构/文件组织从用户观点出发，所观察到的文件组织形式。是用户可以直接处理的数据

和结构，独立于物理特性。逻辑结构可分为：（1）有结构(记录)文件：定长/变长记录（2）无结构(流式)文件2、物理结构/存储结构文件在外存上的存储组织形式，与存储介质的存储性能有关。2022年12月1日星期四10

时1分51秒计算机操作系统8.2.1文件的3种逻辑结构一、顺序文件文件记录的排列、存取按顺序进行。适用场合：对记录批量存取；顺序介质；二、索引文件为变长记录文件建立一张索引表（或多级索引），用户通过关键字访问记录。适用场合：对信息处理及时性要求高

的场合。三、索引顺序文件顺序文件记录分组，并建立索引表，索引表项为各组的第一记录指针。OVER2022年12月1日星期四10时1分51秒计算机操作系统顺序文件示意图(P234,F8-3)R0R1R2......Ri......定长记录文件Rprt=Ptr

+i*llPtr=0L0R0L1R1......LiRi...Ptr=0RprtL0变长记录文件2022年12月1日星期四10时1分51秒计算机操作系统索引文件的组织(P235,F8-4)索引号长度m指针Ptr0M01M1......IMi...R0R1.....

.Ri......索引表逻辑文件变长记录2022年12月1日星期四10时1分51秒计算机操作系统索引顺序文件的组织(P236,F8-5)键值逻辑地址AnQiBaoRongChenLin姓名其它属性AnQiAnKang..

.BaoRong...ChenLin...索引表逻辑文件2022年12月1日星期四10时1分51秒计算机操作系统8.2.2文件的物理结构对磁盘、磁带、磁鼓等辅存介质的分配、回收是以块(Block)为单位。通常，对于记录型

文件存储时，可能情况为：1、一个物理块可以存放若干逻辑记录；2、一个逻辑记录需要占用多个物理块；为简单起见，设一个逻辑记录占用一个物理块。则文件的逻辑结构分为以下3类：一、顺序结构/顺序文件二、链接结构/串联文件三、索引结构/索引文件2022

年12月1日星期四10时1分51秒计算机操作系统顺序结构/顺序文件组织：一个逻辑文件的记录，依此存储在辅存连续的物理块中。优缺点：例如：文件A有三个记录，存储在6，7，8三个物理块中。...文件名第一物理块号文件长度...文件说明R0R1R2文件A2022年12月1日星期四10时1分51秒计算机

操作系统链接结构/串联文件组织：每个块设一个指针，指向该文件下一记录所在物理块号。（图例）优点：记录数可任意增减。缺点：无法直接存取，且为单向查找。实现双向查找的2种方法：1、采用双向链表；2、某一物理块链表指针值设置为：其

前、后两个物理块号的“异或”值(按位加)；若该物理块为文件的首、尾记录，其前、后物理块块号设为0。（例如）OVER2022年12月1日星期四10时1分51秒计算机操作系统链接结构示意图例如：文件A有三个记录，存储在4，12，8三个物理块中。...文件名起始物理块号

......R0/412R1/128R2/8NIL按任意键为异或双向链表查找过程：向下查找：本记录链表指针值与上记录块号“异或”向上查找：本记录链表指针值与下记录块号“异或”0异或12124异或81212异或0124异或8010010001100=122022年12月1日星

期四10时1分51秒计算机操作系统索引结构/索引文件组织：为每一个文件建立一张索引表，每一个表目指向记录所在的物理块号。2022年12月1日星期四10时1分51秒计算机操作系统8.3目录管理借助于文件目录，可将每个

文件的符号名与其所在存储空间地址联系起来。对文件目录管理的要求：1、实现“按名存取”；2、有较高的目录检索速度：合理组织文件目录；3、允许文件重名；4、提供文件共享功能；8.3.1文件控制块和索引结点一、文件控制块(FCB-FileControlBlock)二、索

引结点OVER常见目录结构2022年12月1日星期四10时1分51秒计算机操作系统文件控制块(FCB-FileControlBlock)FCB是一个文件目录项。通常，一个文件目录也被看做是一个文件----目录文件。FCB

包含的信息有3类：1、基本信息：文件名、外存物理位置、逻辑结构（定长/变长）、物理结构；2、存取控制信息：文件主/核准用户/一般用户的存取权限；3、管理信息：创建的日期/时间、上次修改的日期/时间、要求保

留的时间。2022年12月1日星期四10时1分51秒计算机操作系统索引结点（P238）1、引入原因减少磁盘I/O，提高目录查找速度。例2、磁盘索引结点指存放在磁盘上的索引结点，系统中每个文件都有唯一的磁盘索引结点及编号(外存inode区的顺序号)。主要内容3、内存索引结点存放在内存的索引结点

。当文件被打开时，将磁盘索引结点复制到内存索引结点中。内存索引结点包括内容OVER2022年12月1日星期四10时1分51秒计算机操作系统示例设一个FCB为64B，Block=1KB，则每个磁盘块可存放16个目录项。若共有3200

个FCB，则需200个Block，查找一个文件平均启动磁盘100次。改进方法：由于文件查找时，首先根据文件名查找，找到匹配的文件名后，再读取文件的描述信息。为此，可将FCB分成2部分：文件名和文件描述。实现：用一个数据结构(称为索引结点/inode)记录文件的描述信息，每个文件有唯一的

inode号。例：Unix文件目录结构OVER2022年12月1日星期四10时1分51秒计算机操作系统Unix文件目录结构示例Unix中，一个文件目录项共16B。其中14B保存文件名，2B存放i结点指针。则：1Block可存放64个目录项；查找一个文件平均启动磁盘

的次数减少到1/4。文件名外存inode号文件名1文件名2......2022年12月1日星期四10时1分51秒计算机操作系统磁盘索引结点inode主要包括7部分信息1、文件主标识/组标识；2、文件类型：普

通文件/目录文件/块设备文件/字符设备文件；3、文件存取权限；4、文件物理地址：数据文件的盘块号；5、文件长度；6、文件连接计数：文件在目录中具有的路径名数；图例7、文件存取时间：文件最近被存取、修改时间，索引结

点修改时间。2022年12月1日星期四10时1分51秒计算机操作系统文件连接图例...Name1inode:n...目录/a/b...Name2inode:n...目录/c/d...连接计数：2物理地址...外存inode:n文件存储块Unix采用索引结构2022年12月1日星

期四10时1分51秒计算机操作系统内存索引结点/活动索引结点表每个文件在外存都有一个inode。当需要查询、修改外存inode中信息时，一般是将其临时调入内存，处理完毕后再回写到外存。由于系统对inode的访问频繁，按该方式进行很不经济。为此，可在内存设置索引结点，其内容

较外存inode略有增减，增加部分主要有5部分：1、外存索引结点编号；2、状态：指示i结点是否被修改、上锁；3、访问计数：共享该i结点的进程数；4、文件所在设备的逻辑设备号；5、链接指针：空闲/散列队列指针2022年1

2月1日星期四10时1分51秒计算机操作系统8.3.2单级目录结构(SingleLevelDirectory)8.3.3两级目录结构(TwoLevelDirectory)8.3.4树型目录结构/多级目录(Tree-structuredDirectory)8.3.5目录查询技术常见目录结构及查

询技术2022年12月1日星期四10时1分51秒计算机操作系统单级目录结构图例(P239)1、查找速度慢：N个目录，平均查找N/2个目录项；2、不允许重名；文件名状态位物理地址...AlphaReportText......空表目2个缺点：实现：整个系统只建立一张目录表

，为每个文件分配一个目录项。2022年12月1日星期四10时1分51秒计算机操作系统两级目录结构(P240)实现：目录分2种类型：1、主文件目录MFD(MasterFileDirectory)2、用户文件目录UFD(UserFileDirectory)系统设置一个

目录MFD，为每个用户文件建立一个目录UFD，每个用户文件目录在MFD中有一个目录项。图例2个优点：1、提高了查找速度：设共n个用户，每个用户m个文件。则二级目录需查找(n+m)/2个目录项;若n=m，共n；一级目录需查找n*m/2个目录项；若n=m，共n2/2;2、不同用户文件可以重名2022年

12月1日星期四10时1分51秒计算机操作系统两级目录结构图例User1User2User3......UsernAlphaProgram1AlphaTest......MFDUFD2022年12月1日星期四10时1分5

1秒计算机操作系统树型目录结构/多级目录一、实现在两级目录中，允许用户创建自己的子目录并组织其文件，即可形成多级目录结构。图例二、路径名从根目录到文件之间的通路。三、当前目录相对路径名：从当前目录到文件之

间的路径。绝对路径名：从根目录到文件之间的路径。四、目录的增加和删除增加：无重名。删除：不删除非空目录/可删除非空目录。OVER2022年12月1日星期四10时1分51秒计算机操作系统树型目录结构图例（P241，F8-10）AB

CABDFEDGAACJNKJMKAHF当前目录2022年12月1日星期四10时1分51秒计算机操作系统目录查询技术目前，采用的目录查询技术有两种：线性检索法和Hash方法。一、线性检索法按照用户给定文件名，顺序查找文件目录表

，得到文件目录项。见P243，F8-11图例。二、Hash方法略。2022年12月1日星期四10时1分51秒计算机操作系统8.4文件共享多个用户（进程）共享同一份文件，即系统中只保存共享文件的一个副本。8.4.1早期文件共享方法1、绕弯路法2、连访法3、用基本文件目录实现共享8.4.2基于索引

结点的共享方式8.4.3利用符号链实现文件共享OVER2022年12月1日星期四10时1分51秒计算机操作系统绕弯路法实现：系统设置当前目录指针，用户可对当前目录下的文件直接访问。当需访问其它目录下的文件时，通过指定路径来完成。系统设定*表示当前目录的

父目录。例如：*.E.J表示访问其父目录下E子目录中的J文件。图示2022年12月1日星期四10时1分51秒计算机操作系统连访法实现：建立目录之间的链接，使一个目录中的目录项直接指向另一个目录中的目录项。同时在文件说明中增设“连访”属性标识物理地址是文件或目录

项的指针；增设“用户计数”标识共享文件的用户数。例如：图示F8-102022年12月1日星期四10时1分51秒计算机操作系统用基本文件目录实现共享实现：系统将原文件目录分成两部分：1、基本文件目录BFD(BaseFileDirectory)每个文件/目录有一个目

录项，包含：文件标识数，其它目录信息。2、符号文件目录SFD(SymbolFileDirectory)每个用户有一个，其中目录项指示其文件的文件名和文件标识数。图示F8-12提高文件访问速度的方法：系统在内存设置一张活动文件表AFT，为每

个用户设置一张活动名字表ANT。执行OPEN操作时将SFD内容入ANT；BFD内容入AFT。OVER2022年12月1日星期四10时1分51秒计算机操作系统用基本文件目录实现共享图示0123456789...

BFD空闲文件目录Wang3Zhang4Sqrt5Beta6...Mist7Alpha6Report8Oaf9...MFDFFDWangSFDZhangSFD2022年12月1日星期四10时1分51秒计算机操作系统8.4.2基于索引结点的共享方式与设置BDF、SFD实现共享类似。实现

：设置索引结点，存储文件的物理地址、链接计数（共享计数）及其它文件属性；文件目录只包括文件名和该文件对应索引结点的指针。图8-14优点：任何对索引结点内容的修改对其它共享用户都是透明的。2022年12月1日星期四10时1分51秒计算机操作系统8.4.3利用符号链实现文件共享实现：设B为了共享C

的文件F，在B中创建一个Link类型的新文件，新文件目录中只包含被链接文件F的路径名，称这种链接方法为符号链接(symbolicLinking)说明：只有文件主人的目录中有文件索引结点的指针，其它用户目录中只有路径名。2022年12月1日星期四10

时1分51秒计算机操作系统8.5文件保护影响文件系统安全性的3个主要因素：1、人为因素；2、系统因素：系统部分软件、介质故障；3、自然因素：存放在磁盘中的数据，随着时间的推移发生溢出或逐渐消失；文件系统保护机构应有的3个功能：1、防止未核准用户存取文

件；2、防止一个用户冒充另一个用户存取文件；3、防止核准用户误用文件；文件保护措施2022年12月1日星期四10时1分51秒计算机操作系统文件保护：防止合法用户由于误操作而破坏文件；文件保密：防止未核准用户使用文件；可采用下列3种措施保证文件系统的安全

：1、通过存取控制机制，防止人为因素造成的不安全性；2、通过容错技术，防止系统部分的故障造成的不安全性；3、通过“后备系统”，防止自然因素造成的不安全性；文件保护措施存取控制机制2022年12月1日星期四1

0时1分51秒计算机操作系统实现文件存取控制方法较多，且各有特点，主要介绍基本概念和常见存取控制机制。8.5.1保护域(ProtectionDomain)8.5.2访问矩阵(AccessMatrix)8.5.3访问矩阵的修改8

.5.4访问矩阵实现一、访问控制表(AccessControlList)二、访问权限表(AccessCapabilitiesList)8.5.5分级安全管理（自习）OVER存取控制机制2022年12月1日星期四10时1分5

1秒计算机操作系统8.5.1保护域(ProtectionDomain)进程可访问的对象称为保护域。对不同的对象，系统允许进程执行的操作不同。一个进程对某对象可执行操作的权限成为访问权。可用有序对(对象名，权集)表示，例如：（F1

，{R|W}）表示进程对文件F1的操作权限为读、写。一组对象访问权的集合用域表示，可将每个用户或每个进程视为一个域。例F8-16进程与域的联系方式有2种：1、静态联系：进程可用资源集是固定的。2、动态联系：进程可用资源集是变化的。2022年12月1日星期四10

时1分51秒计算机操作系统例F8-16(F1,{R})(F2,{R|W})(F3,{R})(F4,{RWE})(F5,{RW})(F6,{RWE})(Printer1,{W})域1域2域32022年1

2月1日星期四10时1分51秒计算机操作系统8.5.2访问矩阵(AccessMatrix)描述域及所属对象的矩阵称为访问矩阵。访问矩阵中对象访问权由资源拥有者或管理者确定。通过设置域间切换开关实现进程与域的动态联系。文件1文件2文件3文件4打印机1绘图仪

D1D2D3D1RRWSD2RRWEWSD3WW2022年12月1日星期四10时1分51秒计算机操作系统8.5.3访问矩阵的修改为满足系统动态变化的需要，访问矩阵中的权限应允许有限制地进行修改，为此，系统中增设拷贝权、所有权和控制权。一、拷贝权(CopyRig

ht)若进程对域中某一对象访问权有拷贝权（*），则它可将对该对象的访问权拷贝到其它域中，使其它域中进程对同一对象也有相同的访问权。拷贝访问权的2种应用：1、转移拷贝权：拷贝后取消原域的权限；例2、限制拷贝：拷贝后的访问权无拷贝权；例2022年1

2月1日星期四10时1分51秒计算机操作系统拷贝权示例文件1文件2文件3D1EW*D2ER*ED3E文件1文件2文件3D1ED2ER*ED3EW*文件1文件2文件3D1EW*D2ER*ED3EW转换拷贝权

限制拷贝任意键，限制拷贝...2022年12月1日星期四10时1分51秒计算机操作系统访问控制表(AccessControlList)当系统中的域和对象数量较大时，访问矩阵对内存的要求会很高。一般地，由于并非每一个用户进程对系统

中每一个对象都进行访问，所以访问控制矩阵是稀疏矩阵，为此，将访问矩阵按列划分，每列建立一张访问控制表ACL，删除其中空项。ACL由（域，权集）组成，如果其对象是文件，则可将对应的ACL存放在该文件的目录项中。用户/进程对文件进行访问时，系

统先检查ACL，确定访问是否合法：是，执行访问操作；否，拒绝访问，提示相关信息。2022年12月1日星期四10时1分51秒计算机操作系统访问权限表(AccessCapabilitiesList)将访问矩阵按行（域）进行划分，

每一行构成一张访问权限表。例如：D2域的访问权限表为：对象类型访问权限对象文件R指向文件3的指针文件RWE指向文件4的指针打印机1W指向打印机1的指针2022年12月1日星期四10时1分51秒计算机操作系统8.5.5分级安

全管理2022年12月1日星期四10时1分51秒计算机操作系统9.1磁盘I/O9.2外存分配方法9.3空闲存储器的管理9.4磁盘容错技术9.5文件系统性能的改善9.6数据一致性控制第9章磁盘存储管理2022年12月1日星期四10时1分51秒计算机操作系统9.1磁盘I/O

一、磁盘的2种类型（图例）1、固定头磁盘2、移动头磁盘二、移动头磁盘访问时间的3个组成部分1、寻道时间Ts2、旋转延迟时间Tr3、数据传输时间Tt磁盘调度算法2022年12月1日星期四10时1分51秒计算机操作系统磁盘类型图例2022年12月1日星期四10时1分51秒计算机操作系统

1、先来先服务FCFS(FirstComeFirstServed)2、最短寻道时间优先SSTF(ShortestSeekTimeFirst)3、4种扫描算法*扫描算法SCAN（电梯调度法）*循环扫描CSCAN（CircularSCAN）*N步扫描（

NStepSCAN）*FSCAN磁盘调度算法2022年12月1日星期四10时1分51秒计算机操作系统先来先服务FCFS思想：选择等待队列中最先到达的访问请求，作为下一次的访问对象。例：P261，F9-2100磁道低磁道高磁道2022年

12月1日星期四10时1分51秒计算机操作系统最短寻道时间优先SSTF思想：选择等待队列中离当前磁道最近的访问请求，作为下一次的访问对象。例：P261，F9-3100磁道低磁道高磁道2022年12月1日星期四10时1分51秒计算机操作系统扫描算法S

CAN（电梯调度法）思想：选择等待队列中离当前磁头移动方向最近的访问请求，作为下一次的访问对象。例：P262，F9-3设，磁头向磁道增加方向移动100磁道低磁道高磁道2022年12月1日星期四10时1分51秒计算机操作系统循环扫描CSCAN思想：单向扫描，选择等待队列中离当

前磁头移动方向最近的访问请求，作为下一次的访问对象，直到该方向最后一个请求，反向。例：P262，F9-4设，磁头向磁道增加方向移动100磁道低磁道高磁道2022年12月1日星期四10时1分51秒计算机操作系

统N步扫描思想：将磁盘请求队列分为若干长度为N的子队列，并按FCFS算法依次处理这些队列，在处理每一个队列时，采用SCAN算法。(分析N=1和N为无穷情况)例：设N=3，到达次序：55,58,39,18,90,160,150,38,184100磁道低磁道高磁道2022年12月1日星期四

10时1分51秒计算机操作系统FSCAN算法思想：将磁盘请求队列分为2个子队列，其中一个为当前所有请求构成的队列，另一个为扫描期间新到达的请求构成的队列，并按N步扫描处理。2022年12月1日星期四10时1分51秒计算机操作系统9.2外存分配方法一般有3种：连续分配、链接分配和索引

分配。一、连续分配思想：文件在外存分配连续的磁盘块。优点：1、支持顺序访问、直接访问；2、磁头定位时间短，顺序访问速度快。缺点：1、要求连续盘块，易产生碎片；2、需预知文件长度OVER链接分配2022

年12月1日星期四10时1分51秒计算机操作系统外存分配方法（续1）二、链接分配思想：通过磁盘块中的链接指针，将文件所属盘块链成链表，构成链接文件。分为2种：1、隐式链接（P265，F9-7）实现：文件目录中

只给出文件第一、最后一个盘块的指针，其余由链接指针给出。2、显式链接（P266，F9-8）实现：系统设置一张链接表（FAT），存放每一个链接文件各物理块的指针。文件目录中保存第一块的盘块号。缺点：不支持直接访问，FAT需磁盘空间。索引分配2022年12月1日星期四10时1分51秒计算机操作系统外

存分配方法（续2）三、索引分配（分3种）1、单级索引分配（P267，F9-10）建立一张索引表保存文件所分配的块号。2、多级索引分配（F9-11）思考题3、混合索引分配结合直接地址和索引分配方式的分配方式。例：在UNIXS5系统中，有13个地址项，若每个盘块大小为4KB，一个盘块

可存放1K个盘块号，则按照F9-12混合分配方式文件最大长度可达4TB。2022年12月1日星期四10时1分51秒计算机操作系统多级索引分配思考题某文件有1000个记录，文件采用索引分配，设每一个盘块存放一个记录，每一盘块可以存放10个索

引表目。问：1、保存该文件需要建立几级索引？2、共需要多少磁盘块？2022年12月1日星期四10时1分51秒计算机操作系统9.3空闲存储器的管理主要功能：1、设置相应数据结构，记录空闲存储空间的分配情况；2、实现存储空间的分配与回收。空闲存储器

的4种管理方法：1、空闲表法（空白文件目录）2、空闲块链3、位示图法4、成组链接法2022年12月1日星期四10时1分51秒计算机操作系统1、空闲表法（空白文件目录）管理：系统为每一个空白文件（一个连续未分配

的区域）建立一个目录，每个空闲区有一个表目。主要结构为：第一个空白块地址空白块数分配：系统依次扫描空白文件目录，找到一个合适的空白文件分配。回收：动态修改空白文件表（合并）。2个特点：1、适用于建立顺序文件；2、当有大量小的空白文件时，效率

降低。2022年12月1日星期四10时1分51秒计算机操作系统2、空闲块链管理：将所有空闲块链接在一起，组成队列。分配：从链首依次摘取1块或n块。回收：回收块入链尾。特点：操作简单；当链较长时，效率较低。改进：采用空闲盘区链：将所有空闲盘区链接在一起，每个

盘区可包含若干空闲盘块。分配/回收：类似动态分区分配。OVER2022年12月1日星期四10时1分51秒计算机操作系统3、位示图法管理：系统专设几个字，每个字的每一位对应一个磁盘块。F9-14位：为1表示该块已分配；为0表示该块未分配。每位对应盘块号b=(i-1)*n+j其中：i、j分别为行列

值，n为每行位数2个特点：1、由于辅存物理块数固定，位示图尺寸固定；2、位示图较小，可常驻内存，分配/回收速度快。2022年12月1日星期四10时1分51秒计算机操作系统4、成组链接法（Unix采用）管理：设置空闲盘块号栈，存放当前可用的一组空闲盘块的盘块号（最多存放100个号），以及堆栈

中尚有的空闲块数。说明：1、栈属于临界资源，应互斥使用；2、S.free(0)是栈底，栈满时，栈顶为S.free(99)。例：设共有10000个盘块，第201-7999号盘块用于存放文件，则成组链接法结构见F9-15空闲盘块的

分配与回收（P273）2022年12月1日星期四10时1分51秒计算机操作系统UNIX成组链接法图例空闲盘块号栈...100300299298...202201...100400399......301100500499......4019907999......7901299

3997899799920130178017901.....................3004007900S.free01298992022年12月1日星期四10时1分51秒计算机操作系统9.4磁盘

容错技术通过增加冗余的磁盘驱动器、控制器来提高磁盘系统的可靠性。磁盘冗错技术/系统冗错技术SFT(SystemFaultTolerance)分3个级别：SFT-I：低级，防止磁盘表面缺陷引起的数据丢失。SFT-2：中级，防止驱动器、控制器故障引起的不正常。SFT-3：高级

，利用冗余的存储信息作错误校正。2022年12月1日星期四10时1分51秒计算机操作系统9.4.1第一级冗错技术主要措施：双目录、双FAT、写后读校验。一、双目录和双FAT实现：在不同盘或同一盘的不同区域

，建立2份目录和FAT。系统初启时验证一致性。二、热修复重定向和写后读校验防止将数据写入有缺陷的盘块中。1、热修复重定向：磁盘设置热修复重定向区，存放发现盘块有缺陷时的待写数据，并登记。2、写后读校验：将写

入磁盘的数据立即读入内存另一缓冲区，并与原数据比较是否一致。2022年12月1日星期四10时1分51秒计算机操作系统9.4.1第二级冗错技术1、磁盘镜像(DiskMirroring)实现：用同一磁盘控制器来控制2个完全相同的驱动器，每次对主磁盘写入数据后，采用写后读校

验方式，写入备份盘。F9-16缺点：磁盘利用率低；无法处理控制器故障。2、磁盘双工（DiskDuplexing）实现：将2台磁盘驱动器分别连到2个磁盘控制器、通道上，并镜像成对。F9-17优点：A、2个独立通道，可并行写操作；B、读数据时，可

采用分离搜索技术，从响应快的通道取数据。2022年12月1日星期四10时1分51秒计算机操作系统磁盘镜像/双工示意图磁盘镜像示意图磁盘双工示意图主机磁盘控制器通道磁盘驱动器主机磁盘控制器通道磁盘控制器通道磁盘驱动器20

22年12月1日星期四10时1分51秒计算机操作系统9.4.3廉价磁盘冗余阵列RAIDRedundantArrayofInexpensiveDisk用1台磁盘阵列控制器，管理、控制一组磁盘驱动器，组成高度可靠、快速的大容量磁盘系统。分3部分：一

、并行交叉存取二、RAID的分级三、RAID的优点后备系统2022年12月1日星期四10时1分51秒计算机操作系统一、并行交叉存取为提高磁盘的访问速度，在多磁盘驱动器系统中，将每一盘块中的数据分成若干部分，分别存储到各个不同磁盘的相同

位置，达到并行存取的目的。12N......2022年12月1日星期四10时1分51秒计算机操作系统二、RAID的分级有8级，RAID0级-RAID7级。1、RAID0：仅提供并行交叉存取，无校验功能。2、RAID1：在RA

ID0基础上，增加镜像盘。3、RAID3：在RAID0基础上，增加奇偶校验盘。4、RAID5：每个驱动器都有独立的数据通路，可独立进行读写。校验信息以螺旋方式散布在所有数据盘中。5、RAID6：设置专用、可快速访问且有独立数据通路的校验盘。6、RAID7：阵列中所有磁盘都有较高传输速率。202

2年12月1日星期四10时1分51秒计算机操作系统三、RAID的3个优点1、高可靠性。除RAID0外，都采用了冗错技术。2、采用磁盘并行交叉存取，I/O速度快。3、与大型磁盘系统相比，有较高的性能/价格（Performance/Cost）比。2022年12月1

日星期四10时1分51秒计算机操作系统9.4.4后备系统一、后备系统的3种类型1、磁带机适用于存储顺序文件。优缺点：容量大，价格低；速度慢，几千KB/S。2、磁盘机2种方式：A、利用活动盘。速度快，费用高。B、大容量磁盘兼作后备系统。F9-193、光盘优点：容量大，保存期长

，费用适中缺点：速度较慢，单倍速150KB/S。OVER后备方法2022年12月1日星期四10时1分51秒计算机操作系统2个磁盘互为后备系统示意图数据0数据1备份区数据1数据0备份区CPU定期备份2022年12月1日星期四10时1分51秒计算机操作系统二、后备方法2种后备方法：1、全量转储2、

增量转储(IncrementalDumps)设置转储时间表，记录每个文件最后一次的转储时间。每次转储时，判断在最后一次转储后是否发生变化。2022年12月1日星期四10时1分51秒计算机操作系统9.5文件系统性能的改善

衡量文件系统性能的主要指标：1、文件访问的快速性；2、文件数据的可共享性；3、文件系统使用的方便性；4、数据的安全性；5、数据的一致性；主要介绍文件访问的快速性和数据的一致性。提高文件访问速度措施2022年12

月1日星期四10时1分51秒计算机操作系统从3个层次来考虑：1、改进文件的目录结构及目录检索算法，减少对文件的查找时间；2、选择好的文件存储结构，提高访问速度；3、提高磁盘I/O速度，以提高数据传输速度。提高文件访问

速度的措施提高磁盘I/O速度的方法：1、设置磁盘高速缓冲(DiskCache)；2、优化磁盘的数据分布；3、其它方法。2022年12月1日星期四10时1分51秒计算机操作系统9.5.1磁盘高速缓冲一、实现：在内存开辟大容量缓冲，存放磁盘读出的一系

列盘块中的信息。有2种形式：1、在内存开辟大小固定的存储空间作为高速缓冲，不受内存中进城数量影响；2、将内存未用的空间作为缓冲池，供磁盘I/O时共享。其大小随磁盘I/O频度和内存中进程数而调整。2022年12月1日星期四10时1分51秒计算机操作系统9.5.1磁盘高速缓冲（续1）二、数据交付

(DataDelivery)：将磁盘高速缓冲中数据传送给请求者进程，称为数据交付。进程有磁盘I/O时，先检查缓冲区，有数据拷贝，交付给进程；无数据拷贝，从磁盘读入交付，并入缓冲。数据交付的方式：1、数据交付：将数据传到进程内存工作区；2、指

针交付：2022年12月1日星期四10时1分51秒计算机操作系统9.5.1磁盘高速缓冲（续2）三、回写为保证数据一致性，应将高速缓冲中重要或不再使用的盘块数据写回磁盘。高速缓冲中数据置换可采用LRU，为了避免使用频繁的数据块长期不能回写，系统可采用周期性回写方式。