中南大学_操作系统课件.ppt

《中南大学_操作系统课件.ppt》由会员分享，可在线阅读，更多相关《中南大学_操作系统课件.ppt（126页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统原理操作系统原理 Principles of Operating System中南大学信息科学与工程学院中南大学信息科学与工程学院Central South UniversityCollege of Information Science and Engineering2022/12/20计算机操作系统目目 录录REFERANCE第第1部分部分 绪论绪论第第2部分部分 进程管理进程管理第第3部分部分 存储管理存储管理第第4部分部分 I/O设备管理设备管理第第5部分部分 文件管理文件管理第第6部分部分 OS安全与保护安全与保护20 十二月 2022计算机操作系统第第4部分（第部分（第6章

2、）章）I/O设备管理设备管理6.1 I/O系统的组成系统的组成6.2 I/O控制方式控制方式6.3 缓冲管理缓冲管理6.4 设备分配设备分配6.5 设备处理设备处理20 十二月 2022计算机操作系统6.1 I/O系统的组成系统的组成6.1.1 I/O系统的结构系统的结构一、微型机一、微型机I/O系统系统 无通道的无通道的I/O系统，以系统，以CPU为中心（为中心（图例图例）。）。二、主机二、主机I/O系统系统 有通道的有通道的I/O系统，以主存为中心，属四系统，以主存为中心，属四级结构（级结构（图例图例）OVER设备类型设备类型20 十二月 2022计算机操作系统微型机微型机I/O系统结构图

3、例系统结构图例CPURAMI/O1I/On.20 十二月 2022计算机操作系统主机主机I/O系统结构图例系统结构图例主机主机RAMCPU通道通道1控制器控制器1控制器控制器2设备设备1设备设备2设备设备3设备设备4通道通道2控制器控制器3控制器控制器4设备设备5设备设备6设备设备7设备设备8增加通路按任意键增加通路按任意键.20 十二月 2022计算机操作系统6.1.2设备类型设备类型一、按传输速率分一、按传输速率分 1、低速设备：几百字节、低速设备：几百字节/秒，键盘、鼠标；秒，键盘、鼠标；2、中速设备：几千字节、中速设备：几千字节/秒，打印机；秒，打印机；3、高速设备：数兆字节、高速设备

4、：数兆字节/秒，秒，HDD、TYPE；二、按信息交换单位分二、按信息交换单位分 1、块设备：信息存取以块为单位（、块设备：信息存取以块为单位（Block）;2、字符设备：以字符为单位；字符设备：以字符为单位；三、按共享属性三、按共享属性 1、独占设备；、独占设备；2、共享设备；、共享设备；3、虚拟设备；、虚拟设备；设备控制器设备控制器20 十二月 2022计算机操作系统四、设备控制器四、设备控制器DC(Device Controller)DC是是CPU与与I/O设备间的接口，属于可编址设设备间的接口，属于可编址设备，即：备，即：DC连接多个设备时，具有多个设备地址。连接多个设备时，具有多个设备

5、地址。分为：控制字符设备分为：控制字符设备/块设备的控制器。块设备的控制器。一、功能一、功能 1、接收、识别、接收、识别CPU发来的发来的I/O命令命令(Read,Write.);2、通过数据寄存器，完成数据的存储、转发；通过数据寄存器，完成数据的存储、转发；3、借助状态寄存器，记录所连接设备的状态；、借助状态寄存器，记录所连接设备的状态；4、通过地址译码器，实现所连接设备的地址识别；、通过地址译码器，实现所连接设备的地址识别；二、组成二、组成:由由3部分组成（部分组成（图例图例）通道通道20 十二月 2022计算机操作系统设备控制器组成图例设备控制器组成图例 与与CPU接口接口 与设备接口与

6、设备接口数据寄存器数据寄存器控制控制/状态状态寄存器寄存器I/O逻辑逻辑接口接口1接口接口n数据线数据线地址线地址线控制线控制线数据数据数据数据状态状态状态状态控制控制控制控制20 十二月 2022计算机操作系统6.1.4 I/O通道通道一、通道设备的引入一、通道设备的引入 目的：提高目的：提高CPU的利用率。的利用率。与与CPU的的2个区别：个区别：1、仅能执行与、仅能执行与I/O有关指令；有关指令；2、无独立主存，与、无独立主存，与CPU共享；共享；有通道系统有通道系统I/O示例：示例：进程需进程需I/OCPU给通道发给通道发I/O指令指令（通道程序首址、设备）（通道程序首址、设备）通道取

7、通道程序通道取通道程序执行执行I/O中断通知中断通知CPU通道的类型通道的类型20 十二月 2022计算机操作系统二、通道的二、通道的3种类型种类型1、字节多路通道、字节多路通道(Byte Multiplex Channel)（图图）实现：通道含有许多非分配型子通道，每个子通道连接一台实现：通道含有许多非分配型子通道，每个子通道连接一台I/O设备。各子通道按时间片轮转方式使用主通道，每次传输一个字设备。各子通道按时间片轮转方式使用主通道，每次传输一个字节节。(用于连接低中速设备用于连接低中速设备)2、数组选择通道、数组选择通道(Block Selector Channel)实现：一个通道可连接

8、多台实现：一个通道可连接多台I/O设备，但某段时间只允许一台设设备，但某段时间只允许一台设备备I/O，并独占通道直到传输完成。传输时，每次传输一批数据。并独占通道直到传输完成。传输时，每次传输一批数据。(用于连接高速外设用于连接高速外设)3、数组多路、数组多路(Block Multiplex Channel)实现：结合选择通道的高速与字节多路通道分时并行的优点，传实现：结合选择通道的高速与字节多路通道分时并行的优点，传输按成组分时方式进行。输按成组分时方式进行。瓶颈问题瓶颈问题20 十二月 2022计算机操作系统三、瓶颈问题三、瓶颈问题 为降低系统成本，并非每一个为降低系统成本，并非每一个I/

9、O设备都设备都有自己独立的控制器和通道，所以造成多台有自己独立的控制器和通道，所以造成多台I/O设备争用控制器、通道。使通道成为设备争用控制器、通道。使通道成为I/O的主要瓶颈，造成系统吞吐量下降。的主要瓶颈，造成系统吞吐量下降。解决解决2方法：方法：1、增加通路，提高系统的灵活性、可靠性；、增加通路，提高系统的灵活性、可靠性；(图图例例)2、设置缓冲区，增加、设置缓冲区，增加I/O设备的独立性。设备的独立性。20 十二月 2022计算机操作系统字节多路通道示意图字节多路通道示意图字节多路通道字节多路通道控制器控制器1控制器控制器2控制器控制器n.20 十二月 2022计算机操作系统6.2 I

10、/O控制方式控制方式I/O控制方式发展宗旨：控制方式发展宗旨：尽量减少尽量减少CPU对对I/O的干预，提高的干预，提高CPU的利用率。的利用率。发展的四个阶段：发展的四个阶段：6.2.1 程序程序I/O方式；方式；6.2.2 中断驱动中断驱动I/O控制方式；控制方式；6.2.3 DMA方式；方式；6.2.4 通道方式；通道方式；20 十二月 2022计算机操作系统6.2.1 程序程序I/O方式（方式（Programmed I/O）早期无中断系统早期无中断系统工作特点：工作特点：1、“忙测试忙测试”：(1)CPU向向I/O控制器发一条控制器发一条I/O命令，启动命令，启动I/O设备；设备；(2)

11、置设备状态寄存器中置设备状态寄存器中busy为为1；(3)循环测试循环测试busy，直到直到busy=0;2、每一每一次，次，I/O一个字（符）一个字（符）20 十二月 2022计算机操作系统6.2.2 中断驱动中断驱动I/O控制方式控制方式 有中断的系统。有中断的系统。工作过程：工作过程：1、进程、进程I/O时，时，CPU发发I/O命令给设备控制器命令给设备控制器DC(Device Controller)，并继续工作；并继续工作；2、DC接到命令，控制设备接到命令，控制设备I/O；3、I/O完成，完成，DC向向CPU发中断信号；发中断信号；4、CPU检查检查I/O中是否有错，中是否有错，有：

12、处理；有：处理；无：继续；无：继续；每次每次I/O一个字（符）一个字（符）20 十二月 2022计算机操作系统6.2.3 DMA(Direct Memory Access)方式方式特点：特点：1、I/O基本单位是数据块基本单位是数据块(Block)；2、I/O是直接从设备入内存，或相反；是直接从设备入内存，或相反；3、一块、一块/多块完成后，多块完成后，CPU才干预；才干预；DMA组成组成 工作过程工作过程3步：步：1、进程、进程I/O，CPU给控制器发送：给控制器发送：I/O命令、内存命令、内存/外存起址、传输字节数；外存起址、传输字节数；2、CPU启动控制器进行数据启动控制器进行数据I/O

13、；3、I/O完成，完成，DMA向向CPU发送中断信号；发送中断信号；20 十二月 2022计算机操作系统DMA组成组成Count 内存内存起址起址CPU数据寄存器数据寄存器DR内存地址内存地址MAR计数器计数器DC命令寄存器命令寄存器DRI/O逻逻辑辑接口接口1接口接口n20 十二月 2022计算机操作系统6.2.4 通道方式通道方式工作过程：工作过程：1、进程、进程I/O，CPU向通道发送向通道发送I/O命令，给出通命令，给出通道程序的起址、需访问的设备等；道程序的起址、需访问的设备等；2、通道执行通道程序，完成、通道执行通道程序，完成I/O，并中断通知并中断通知CPU。I/O量：以一组数据

14、块为单位。量：以一组数据块为单位。20 十二月 2022计算机操作系统6.3 缓冲管理缓冲管理一、缓冲引入原因一、缓冲引入原因 1、缓和、缓和CPU与与I/O设备间速度不匹配的矛盾；设备间速度不匹配的矛盾；2、减少、减少CPU对对I/O的干预；的干预；3、提高、提高CPU和和I/O设备之间的并行程度；设备之间的并行程度；二、缓冲的种类二、缓冲的种类 1、单缓冲、单缓冲 2、双缓冲、双缓冲 3、循环缓冲、循环缓冲(多缓冲，类似于生产者多缓冲，类似于生产者-消费者中消费者中的缓冲区的缓冲区)4、缓冲池、缓冲池20 十二月 2022计算机操作系统1、单缓冲、单缓冲(Single Buffer)工作方

15、式：工作方式：进程发出进程发出I/O请求时，操作系统在主存分配一个缓冲请求时，操作系统在主存分配一个缓冲区，通过缓冲区完成区，通过缓冲区完成I/O。例：从块设备输入处理例：从块设备输入处理（性能分析性能分析）1、将一块输入数据输入缓冲区，时间、将一块输入数据输入缓冲区，时间T；2、系统将缓冲区数据复制到用户区，时间系统将缓冲区数据复制到用户区，时间M；3、CPU对输入的数据处理，时间对输入的数据处理，时间C；用户进程用户进程操作系统操作系统BUF数据区数据区CPU处理处理C复制复制M设备输入设备输入T20 十二月 2022计算机操作系统单缓冲性能分析单缓冲性能分析无缓冲区时，每一块数据的处理时

16、间为：无缓冲区时，每一块数据的处理时间为：T+C单缓冲区时，每一块数据的处理时间为：单缓冲区时，每一块数据的处理时间为：MAX(C,T)+M 由于由于Mprn逻辑设备到物理设备的映射逻辑设备到物理设备的映射20 十二月 2022计算机操作系统三、逻辑设备到物理设备的映射三、逻辑设备到物理设备的映射1、逻辑设备表、逻辑设备表LUT(Logical Unit Table)逻辑设备名逻辑设备名 物理设备号物理设备号 驱动程序入口地址驱动程序入口地址 /dev/tty 3 1024 /dev/print 5 2046 .2、LUT的的2种设置方式种设置方式 (1)整个系统设置一张整个系统设置一张 缺点

17、：不同用户的逻辑设备名不允许相同。缺点：不同用户的逻辑设备名不允许相同。(2)每个用户进程设置一张，置于进程每个用户进程设置一张，置于进程PCB中。中。SPOOLingSPOOLing技术技术20 十二月 2022计算机操作系统6.4.5 SPOOLing技术技术思想：通过在高速外存设置思想：通过在高速外存设置I/O缓冲，将独占型设备改缓冲，将独占型设备改造成为可共享的虚设备。造成为可共享的虚设备。SPOOLing-在线同时外围操作在线同时外围操作 (Simultaneous Peripheral Operation On-Line)一、一、SPOOLing系统的系统的组成组成(3部分部分)1

18、、输入井和输出井、输入井和输出井 在磁盘开辟存储空间，收容输入、输出数据。在磁盘开辟存储空间，收容输入、输出数据。2、输入缓冲和输出缓冲、输入缓冲和输出缓冲 在内存设置缓冲，暂存从设备输入或从输入井输入的数据。在内存设置缓冲，暂存从设备输入或从输入井输入的数据。3、输入进程、输入进程SPi和输出进程和输出进程SPo 工作过程工作过程20 十二月 2022计算机操作系统SPOOLing系统组成示意图系统组成示意图Spi Spo输入缓冲区输入缓冲区InBuff输出缓冲区输出缓冲区OutBuff输入设备输入设备输出设备输出设备磁盘磁盘输入井输入井输出井输出井20 十二月 2022计算机操作系统二、二

19、、SPOOLing系统的工作过程系统的工作过程输入过程：输入过程：SPOOLing输入程序输入程序Spi主要工作是负责将输入设备上的作主要工作是负责将输入设备上的作业以作业为单位通过内存缓冲区传输至输入井，并建立业以作业为单位通过内存缓冲区传输至输入井，并建立JCB，同时维持后备队列。同时维持后备队列。Spi是系统中一个独立的进程，无任务时，处于等待状态是系统中一个独立的进程，无任务时，处于等待状态（睡眠状态）。（睡眠状态）。Spi被唤醒的时机有被唤醒的时机有3个，个，Spi被唤醒后，根据被唤醒后，根据收到的信号作相应的收到的信号作相应的工作工作：1、当输入设备上有作业输入请求时；、当输入设备

20、上有作业输入请求时；2、当输入设备工作结束时；、当输入设备工作结束时；3、向磁盘输入井传输一道作业结束时；、向磁盘输入井传输一道作业结束时；SPOOLing的特点的特点20 十二月 2022计算机操作系统根据根据唤醒时机不同，唤醒时机不同，Spi的工作的工作(1)设备有输入请求；设备有输入请求；Spi启动相应通道，将作业输入到内存输入缓冲区，自身进启动相应通道，将作业输入到内存输入缓冲区，自身进入等待；入等待；(2)输入设备出现输入设备出现“结束中断结束中断”；Spi根据输入缓冲区中的内容，建立根据输入缓冲区中的内容，建立JCB，并在输入井中为并在输入井中为作业分配空间，启动磁盘通道将输入缓冲

21、区中作业输到输入井，作业分配空间，启动磁盘通道将输入缓冲区中作业输到输入井，自身进入等待。自身进入等待。(3)向输入井传输作业结束，出现向输入井传输作业结束，出现“磁盘结束磁盘结束”中断；中断；Spi将作业将作业JCB加入后备队列，并向作业调度程序发信号，加入后备队列，并向作业调度程序发信号，引起作业调度，自身进入等待。引起作业调度，自身进入等待。20 十二月 2022计算机操作系统三三、SPOOLing的的3特点特点1、提高了、提高了I/O速度；速度；由对低速设备的由对低速设备的I/O改为对输入改为对输入/输出井的存取，缓和了输出井的存取，缓和了CPU与低速设备的矛盾；与低速设备的矛盾；2、

22、将独占型设备改造为共享设备；、将独占型设备改造为共享设备；3、实现了虚拟设备功能；、实现了虚拟设备功能；多个进程同时（并发）地从输入多个进程同时（并发）地从输入/输出井存取数据，感输出井存取数据，感觉是独占觉是独占I/O设备。设备。20 十二月 2022计算机操作系统6.5 设备处理设备处理设备处理程序设备处理程序/设备驱动程序功能：设备驱动程序功能：接收上层软件的接收上层软件的I/O命令，转化为具体的命令，转化为具体的I/O要求，要求，控制设备完成控制设备完成I/O操作。处理操作。处理6过程：过程：1、将抽象要求转换为具体要求；即将、将抽象要求转换为具体要求；即将I/O命令转命令转换为控制器

23、可接受的命令格式；例：换为控制器可接受的命令格式；例：磁盘块号转换为盘面、道号、扇区；磁盘块号转换为盘面、道号、扇区；2、检查、检查I/O请求的合法性；请求的合法性；3、读出和检查设备状态；、读出和检查设备状态；4、传送必要的参数；如传输字节数、内存地址；、传送必要的参数；如传输字节数、内存地址；5、设置工作方式；异步、设置工作方式；异步/同步通信；同步通信；6、启动、启动I/O设备；完成设备；完成I/O。20 十二月 2022计算机操作系统第第4部分部分 文件系统文件系统7.1 文件和文件系统文件和文件系统7.2 文件结构文件结构7.3 目录管理目录管理7.4 文件共享文件共享7.5 文件保

24、护文件保护20 十二月 2022计算机操作系统7.1文件和文件系统文件和文件系统7.1.1文件、记录和数据项（数据元素文件、记录和数据项（数据元素/字段字段/域）域）记录：一组相关数据项的集合；记录：一组相关数据项的集合；文件：具有文件名的一组相关信息的集合；文件：具有文件名的一组相关信息的集合；7.1.2文件类型（文件类型（5）1、按用途分：系统、用户、库文件；、按用途分：系统、用户、库文件；2、按存取控制属性：只读、读写、只执行文件；、按存取控制属性：只读、读写、只执行文件；3、按文件逻辑结构：有结构、无结构文件；、按文件逻辑结构：有结构、无结构文件；4、按文件物理结构：顺序、链接、索引文

25、件；、按文件物理结构：顺序、链接、索引文件；5、按文件中数据形式：源、目标、可执行文件；、按文件中数据形式：源、目标、可执行文件；文件系统模型文件系统模型20 十二月 2022计算机操作系统7.1.3 文件系统模型文件系统模型文件系统：用于操纵和管理各种文件，方便用户使用文件系统：用于操纵和管理各种文件，方便用户使用文件的软件集合。文件的软件集合。文件系统模型层次结构文件系统模型层次结构一、管理对象一、管理对象 文件、目录、外存空间文件、目录、外存空间二、操纵和控制内容二、操纵和控制内容 1、文件存储空间管理；、文件存储空间管理；2、目录管理；、目录管理；3、地址映射；、地址映射；4、R/W管

26、理；管理；5、共享和保护；、共享和保护；三、文件系统接口三、文件系统接口 1、命令接口；、命令接口；2、程序接口；、程序接口；文件操作文件操作20 十二月 2022计算机操作系统7.1.4文件操作文件操作文件操作分文件操作分2大类：大类：一、对记录操作一、对记录操作 记录增、删、改；记录增、删、改；记录的查询；记录的查询；二、对文件的操作二、对文件的操作 创建文件；创建文件；删除文件；删除文件；读写文件；读写文件；设置读写位置；设置读写位置；20 十二月 2022计算机操作系统文件系统模型层次结构文件系统模型层次结构文件系统接口文件系统接口 逻辑文件系统逻辑文件系统 基本基本I/O管理程序管理

27、程序 基本文件系统（物理基本文件系统（物理I/O层）层）I/O控制层（设备驱动程序）控制层（设备驱动程序）对象及其属性说明对象及其属性说明对对象操纵对对象操纵和管理的软件和管理的软件集合集合启动启动I/O操作、接收中断操作、接收中断处理内、外存数据交换处理内、外存数据交换设备选择、地址映射、设备选择、地址映射、空闲块管理、缓冲设置空闲块管理、缓冲设置目录管理、存取控制验证目录管理、存取控制验证命令、程序接口命令、程序接口文件、目录、外存文件、目录、外存20 十二月 2022计算机操作系统7.2文件结构文件结构文件结构分文件结构分2类：类：7.2.1 逻辑结构逻辑结构/文件组织文件组织 从用户观

28、点出发，所观察到的文件组织形式。是用从用户观点出发，所观察到的文件组织形式。是用户可以直接处理的数据和结构，独立于物理特性。户可以直接处理的数据和结构，独立于物理特性。逻辑结构可分为：逻辑结构可分为：（1）有结构）有结构(记录记录)文件：定长文件：定长/变长记录变长记录 （2）无结构）无结构(流式流式)文件文件7.2.2 物理结构物理结构/存储结构存储结构 文件在外存上的存储组织形式，与存储介质的存储文件在外存上的存储组织形式，与存储介质的存储性能有关。性能有关。20 十二月 2022计算机操作系统7.2.1文件的文件的3种逻辑结构种逻辑结构一、顺序文件一、顺序文件 文件记录的排列、存取按顺序

29、进行。文件记录的排列、存取按顺序进行。适用场合：对记录批量存取；顺序介质；适用场合：对记录批量存取；顺序介质；二、索引文件二、索引文件 为变长记录文件建立一张索引表（或多级索引），为变长记录文件建立一张索引表（或多级索引），用户通过关键字访问记录。用户通过关键字访问记录。适用场合：对信息处理及时性要求高的场合。适用场合：对信息处理及时性要求高的场合。三、索引顺序文件三、索引顺序文件 顺序文件记录分组，并建立索引表，索引表项为顺序文件记录分组，并建立索引表，索引表项为各组的第一记录指针。各组的第一记录指针。20 十二月 2022计算机操作系统顺序文件示意图顺序文件示意图R0R1R2.Ri.定长记

30、录文件定长记录文件Rprt=Ptr+i*l lPtr=0L0R0L1R1.LiRi.Ptr=0Rprt L0变长记录文件变长记录文件20 十二月 2022计算机操作系统索引文件的组织索引文件的组织索引号索引号 长度长度m 指针指针Ptr0 M0 1 M1 .I Mi .R0R1.Ri.索引表索引表逻辑文件逻辑文件变长记录变长记录20 十二月 2022计算机操作系统索引顺序文件的组织索引顺序文件的组织 键值键值 逻辑地址逻辑地址 An QiBao RongChen Lin 姓名姓名 其它属性其它属性An QiAn Kang .Bao Rong .Chen Lin .索引表索引表逻辑文件逻辑文件2

31、0 十二月 2022计算机操作系统7.2.2文件的物理结构文件的物理结构 对磁盘、磁带、磁鼓等辅存介质的分配、回收是对磁盘、磁带、磁鼓等辅存介质的分配、回收是以块以块(Block)为单位。通常，对于记录型文件存储时，为单位。通常，对于记录型文件存储时，可能情况为：可能情况为：1、一个物理块可以存放若干逻辑记录；、一个物理块可以存放若干逻辑记录；2、一个逻辑记录需要占用多个物理块；、一个逻辑记录需要占用多个物理块；为简单起见，设一个逻辑记录占用一个物理块。则为简单起见，设一个逻辑记录占用一个物理块。则文件的逻辑结构分为以下文件的逻辑结构分为以下3类：类：一、一、顺序结构顺序结构/顺序文件顺序文件

32、二、二、链接结构链接结构/串联文件串联文件三、三、索引结构索引结构/索引文件索引文件20 十二月 2022计算机操作系统顺序结构顺序结构/顺序文件顺序文件组织：一个逻辑文件的记录，依此存储在辅存连续的组织：一个逻辑文件的记录，依此存储在辅存连续的物理块中。物理块中。优缺点：优缺点：例如：文件例如：文件A有三个记录，存储在有三个记录，存储在6，7，8三个物理三个物理块中。块中。.文件名文件名第一物理块号第一物理块号文件长度文件长度.文件文件 说明说明 R0 R1 R2文件文件A20 十二月 2022计算机操作系统链接结构链接结构/串联文件串联文件组织：每个块设一个指针，指向该文件下一记录所在组织

33、：每个块设一个指针，指向该文件下一记录所在物理块号。（物理块号。（图例图例）优点：记录数可任意增减。优点：记录数可任意增减。缺点：无法直接存取，且为单向查找。缺点：无法直接存取，且为单向查找。实现双向查找的实现双向查找的2种方法：种方法：1、采用双向链表；、采用双向链表；2、某一物理块链表指针值设置为：、某一物理块链表指针值设置为：其前、后两个物理块号的其前、后两个物理块号的“异或异或”值值(按位加按位加)；若该物理块为文件的首、尾记录，其前、后物理块块若该物理块为文件的首、尾记录，其前、后物理块块号设为号设为0。（。（例如例如）20 十二月 2022计算机操作系统链接结构示意图链接结构示意图

34、例如：文件例如：文件A有三个记录，存储在有三个记录，存储在4，12，8三个物三个物理块中。理块中。.文件名文件名起始物理块号起始物理块号.R0/412R1/128R2/8NIL按任意键为异或双向链表按任意键为异或双向链表查找过程：查找过程：向下查找：本记录链表指针值与上记录块号向下查找：本记录链表指针值与上记录块号“异或异或”向上查找：本记录链表指针值与下记录块号向上查找：本记录链表指针值与下记录块号“异或异或”0异或异或12124异或异或81212异或异或0124异或异或8010010001100=1220 十二月 2022计算机操作系统索引结构索引结构/索引文件索引文件组织：为每一个文件建

35、立一张索引表，每一个表目指向记录组织：为每一个文件建立一张索引表，每一个表目指向记录所在的物理块号。所在的物理块号。20 十二月 2022计算机操作系统7.3 目录管理目录管理 借助于文件目录，可将每个文件的符号名与借助于文件目录，可将每个文件的符号名与其所在存储空间地址联系起来。其所在存储空间地址联系起来。对文件目录管理的要求：对文件目录管理的要求：1、实现、实现“按名存取按名存取”；2、有较高的目录检索速度：合理组织文件目录；、有较高的目录检索速度：合理组织文件目录；3、允许文件重名；、允许文件重名；4、提供文件共享功能；、提供文件共享功能；7.3.1文件控制块和索引结点文件控制块和索引结

36、点 一、一、文件控制块文件控制块(FCB-File Control Block)二、二、索引结点索引结点常见目录结构常见目录结构20 十二月 2022计算机操作系统一、文件控制块一、文件控制块(FCB-File Control Block)FCB是一个文件目录项。通常，一个文件目录是一个文件目录项。通常，一个文件目录也被看做是一个文件也被看做是一个文件-目录文件。目录文件。FCB包含的信息有包含的信息有3类：类：1、基本信息：文件名、外存物理位置、逻辑结构（定长、基本信息：文件名、外存物理位置、逻辑结构（定长/变长）、物理结构；变长）、物理结构；2、存取控制信息：文件主、存取控制信息：文件主/

37、核准用户核准用户/一般用户的存取权一般用户的存取权限；限；3、管理信息：创建的日期、管理信息：创建的日期/时间、上次修改的日期时间、上次修改的日期/时间、时间、要求保留的时间。要求保留的时间。20 十二月 2022计算机操作系统二、索引结点二、索引结点1、引入原因、引入原因 减少磁盘减少磁盘I/O，提高目录查找速度。提高目录查找速度。例例2、磁盘索引结点、磁盘索引结点 指存放在磁盘上的索引结点，系统中每个文件都有唯指存放在磁盘上的索引结点，系统中每个文件都有唯一的磁盘索引结点及编号一的磁盘索引结点及编号(外存外存inode区的顺序号区的顺序号)。主要内容主要内容3、内存索引结点、内存索引结点

38、存放在内存的索引结点。当文件被打开时，将磁盘索存放在内存的索引结点。当文件被打开时，将磁盘索引结点复制到内存索引结点中。引结点复制到内存索引结点中。内存索引结点包括内容内存索引结点包括内容20 十二月 2022计算机操作系统示例示例 设一个设一个FCB为为64B，Block=1KB，则每个磁盘块则每个磁盘块可存放可存放16个目录项。若共有个目录项。若共有3200个个FCB，则需则需200个个Block，查找查找一个文件平均启动磁盘一个文件平均启动磁盘100次。次。改进方法：改进方法：由于文件查找时，首先根据文件名查找，找到匹由于文件查找时，首先根据文件名查找，找到匹配的文件名后，再读取文件的描

39、述信息。为此，可将配的文件名后，再读取文件的描述信息。为此，可将FCB分成分成2部分：文件名和文件描述。部分：文件名和文件描述。实现：用一个数据结构实现：用一个数据结构(称为索引结点称为索引结点/inode)记录文记录文件的描述信息，每个文件有唯一的件的描述信息，每个文件有唯一的inode号。号。例例：Unix文件目录结构文件目录结构20 十二月 2022计算机操作系统Unix文件目录结构示例文件目录结构示例 Unix中，一个文件目录项中，一个文件目录项共共16B。其中。其中14B保存文件名，保存文件名，2B存放存放i结点指针。结点指针。则：则：1Block可存放可存放64个目录项；个目录项；

40、查找一个文件平均启动磁盘的查找一个文件平均启动磁盘的次数减少到次数减少到1/4。文件名文件名 外存外存inode号号文件名文件名1文件名文件名2 .20 十二月 2022计算机操作系统磁盘索引结点磁盘索引结点inode主要包括主要包括7部分信息部分信息1、文件主标识、文件主标识/组标识；组标识；2、文件类型：普通文件、文件类型：普通文件/目录文件目录文件/块设备文件块设备文件/字符设备文字符设备文件；件；3、文件存取权限；、文件存取权限；4、文件物理地址：数据文件的盘块号；、文件物理地址：数据文件的盘块号；5、文件长度；、文件长度；6、文件连接计数：文件在目录中具有的路径名数；、文件连接计数：

41、文件在目录中具有的路径名数；图例图例7、文件存取时间：文件最近被存取、修改时间，索引结点、文件存取时间：文件最近被存取、修改时间，索引结点修改时间。修改时间。20 十二月 2022计算机操作系统文件连接图例文件连接图例.Name1inode:n.目录目录/a/b.Name2inode:n.目录目录/c/d.连接计数：连接计数：2物理地址物理地址.外存外存inode:n文件存储块文件存储块Unix采用采用索引结构索引结构20 十二月 2022计算机操作系统内存索引结点内存索引结点/活动索引结点表活动索引结点表 每个文件在外存都有一个每个文件在外存都有一个inode。当需要查询、当需要查询、修改外

42、存修改外存inode中信息时，一般是将其临时调入内中信息时，一般是将其临时调入内存，处理完毕后再回写到外存。由于系统对存，处理完毕后再回写到外存。由于系统对inode的访问频繁，按该方式进行很不经济。为此，可在的访问频繁，按该方式进行很不经济。为此，可在内存设置索引结点，其内容较外存内存设置索引结点，其内容较外存inode略有增减，略有增减，增加部分主要有增加部分主要有5部分：部分：1、外存索引结点编号；、外存索引结点编号；2、状态：指示、状态：指示i结点是否被修改、上锁；结点是否被修改、上锁；3、访问计数：共享该、访问计数：共享该i结点的进程数；结点的进程数；4、文件所在设备的逻辑设备号；、

43、文件所在设备的逻辑设备号；5、链接指针：空闲、链接指针：空闲/散列队列指针散列队列指针20 十二月 2022计算机操作系统7.4 常见目录结构及查询技术常见目录结构及查询技术7.4.1 单级目录结构单级目录结构 (Single Level Directory)7.4.2 两级目录结构两级目录结构 (Two Level Directory)7.4.3 树型目录结构树型目录结构/多级目录多级目录 (Tree-structured Directory)7.4.4 目录查询技术目录查询技术20 十二月 2022计算机操作系统7.4.1 单级目录结构单级目录结构图例图例1、查找速度慢：、查找速度慢：N个

44、目录，平均查找个目录，平均查找N/2个目录项；个目录项；2、不允许重名；、不允许重名；文件名文件名 状态位状态位 物理地址物理地址 .AlphaReportText .2个缺点：个缺点：实现：整个系统只建立一张目录表，为每个文件分配一实现：整个系统只建立一张目录表，为每个文件分配一个目录项。个目录项。20 十二月 2022计算机操作系统7.4.2 7.4.2 两级目录结构两级目录结构实现：目录分实现：目录分2种类型：种类型：1、主文件目录、主文件目录MFD(Master File Directory)2、用户文件目录用户文件目录UFD(User File Directory)系统设置一个目录系

45、统设置一个目录MFD，为每个用户文件建立一为每个用户文件建立一个目录个目录UFD，每个用户文件目录在每个用户文件目录在MFD中有一个目录中有一个目录项。项。图例图例2个优点：个优点：1、提高了查找速度：设共、提高了查找速度：设共n个用户，每个用户个用户，每个用户m个个文件。则文件。则二级目录需查找二级目录需查找(n+m)/2个目录项个目录项;若若n=m，共共n；一级目录需查找一级目录需查找n*m/2个目录项；若个目录项；若n=m，共共n2/2;2、不同用户文件可以重名、不同用户文件可以重名20 十二月 2022计算机操作系统两级目录结构图例两级目录结构图例User1 User2 User3 .

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

47、录的增加和删除四、目录的增加和删除 增加：无重名。增加：无重名。删除：不删除非空目录删除：不删除非空目录/可删除非空目录。可删除非空目录。20 十二月 2022计算机操作系统树型目录结构图例树型目录结构图例A B CA B DF E DG A A C J N K J M KA H F当前当前目录目录20 十二月 2022计算机操作系统7.4.4 目录查询技术目录查询技术 目前，采用的目录查询技术有两种：线性检索法目前，采用的目录查询技术有两种：线性检索法和和Hash方法。方法。一、线性检索法一、线性检索法 按照用户给定文件名，顺序查找文件目录表，得按照用户给定文件名，顺序查找文件目录表，得到文

48、件目录项。到文件目录项。见见P243，F8-11图例。图例。二、二、Hash方法方法 略。略。20 十二月 2022计算机操作系统7.5 文件共享文件共享 多个用户（进程）共享同一份文件，即多个用户（进程）共享同一份文件，即系统中只保存共享文件的一个副本。系统中只保存共享文件的一个副本。7.5.1 早期文件共享方法早期文件共享方法 一、一、绕弯路法绕弯路法 二、二、连访法连访法 三、三、用基本文件目录实现共享用基本文件目录实现共享7.5.2 基于索引结点的共享方式基于索引结点的共享方式7.5.3 利用符号链实现文件共享利用符号链实现文件共享20 十二月 2022计算机操作系统一、绕弯路法一、绕

49、弯路法实现：系统设置当前目录指针，用户可对当前目录下的文件实现：系统设置当前目录指针，用户可对当前目录下的文件直接访问。当需访问其它目录下的文件时，通过指定路径来直接访问。当需访问其它目录下的文件时，通过指定路径来完成。完成。系统设定系统设定*表示当前目录的父目录。表示当前目录的父目录。例如：例如：*.E.J表示访问其父目录下表示访问其父目录下E子目录中的子目录中的J文件。文件。图示图示实现：建立目录之间的链接，使一个目录中的目录项直接指实现：建立目录之间的链接，使一个目录中的目录项直接指向另一个目录中的目录项。同时在文件说明中增设向另一个目录中的目录项。同时在文件说明中增设“连访连访”属性标

50、识物理地址是文件或目录项的指针；增设属性标识物理地址是文件或目录项的指针；增设“用户计数用户计数”标识共享文件的用户数。标识共享文件的用户数。例如：例如：图示图示二、连访法二、连访法20 十二月 2022计算机操作系统用基本文件目录实现共享用基本文件目录实现共享实现：系统将原文件目录分成两部分：实现：系统将原文件目录分成两部分：1、基本文件目录、基本文件目录BFD(Base File Directory)每个文件每个文件/目录有一个目录项，包含：文件标识数，其它目目录有一个目录项，包含：文件标识数，其它目录信息。录信息。2、符号文件目录、符号文件目录SFD(Symbol File Direct