中南大学操作系统.ppt

2020/5/28,计算机操作系统,操作系统原理PrinciplesofOperatingSystem,CentralSouthUniversityCollegeofInformationScienceandEngineering,2020/5/28,计算机操作系统,目录,REFERANCE第1部分绪论第2部分进程管理第3部分存储管理第4部分I/O设备管理第5部分文件管理第6部分OS安全与保护,2020/5/28,计算机操作系统,第4部分（第6章）I/O设备管理,6.1I/O系统的组成6.2I/O控制方式6.3缓冲管理6.4设备分配6.5设备处理,2020/5/28,计算机操作系统,6.1I/O系统的组成,6.1.1I/O系统的结构一、微型机I/O系统无通道的I/O系统，以CPU为中心（图例）。二、主机I/O系统有通道的I/O系统，以主存为中心，属四级结构（图例）OVER,设备类型,2020/5/28,计算机操作系统,微型机I/O系统结构图例,CPU,RAM,I/O1,I/On,.,2020/5/28,计算机操作系统,主机I/O系统结构图例,主机,RAM,CPU,通道1,控制器1,控制器2,设备1,设备2,设备3,设备4,通道2,控制器3,控制器4,设备5,设备6,设备7,设备8,增加通路按任意键.,2020/5/28,计算机操作系统,6.1.2设备类型,一、按传输速率分1、低速设备：几百字节/秒，键盘、鼠标；2、中速设备：几千字节/秒，打印机；3、高速设备：数兆字节/秒，HDD、TYPE；二、按信息交换单位分1、块设备：信息存取以块为单位（Block）;2、字符设备：以字符为单位；三、按共享属性1、独占设备；2、共享设备；3、虚拟设备；,设备控制器,2020/5/28,计算机操作系统,四、设备控制器DC(DeviceController),DC是CPU与I/O设备间的接口，属于可编址设备，即：DC连接多个设备时，具有多个设备地址。分为：控制字符设备/块设备的控制器。一、功能1、接收、识别CPU发来的I/O命令(Read,Write.);2、通过数据寄存器，完成数据的存储、转发；3、借助状态寄存器，记录所连接设备的状态；4、通过地址译码器，实现所连接设备的地址识别；二、组成:由3部分组成（图例）,通道,2020/5/28,计算机操作系统,设备控制器组成图例,与CPU接口与设备接口,数据寄存器,控制/状态寄存器,I/O逻辑,接口1,接口n,数据线,地址线,控制线,数据,数据,状态,状态,控制,控制,2020/5/28,计算机操作系统,6.1.4I/O通道,一、通道设备的引入目的：提高CPU的利用率。与CPU的2个区别：1、仅能执行与I/O有关指令；2、无独立主存，与CPU共享；有通道系统I/O示例：,进程需I/O,CPU给通道发I/O指令（通道程序首址、设备）,通道取通道程序,执行I/O,中断通知CPU,通道的类型,2020/5/28,计算机操作系统,二、通道的3种类型,1、字节多路通道(ByteMultiplexChannel)（图）实现：通道含有许多非分配型子通道，每个子通道连接一台I/O设备。各子通道按时间片轮转方式使用主通道，每次传输一个字节。(用于连接低中速设备)2、数组选择通道(BlockSelectorChannel)实现：一个通道可连接多台I/O设备，但某段时间只允许一台设备I/O，并独占通道直到传输完成。传输时，每次传输一批数据。(用于连接高速外设)3、数组多路(BlockMultiplexChannel)实现：结合选择通道的高速与字节多路通道分时并行的优点，传输按成组分时方式进行。,瓶颈问题,2020/5/28,计算机操作系统,三、瓶颈问题,为降低系统成本，并非每一个I/O设备都有自己独立的控制器和通道，所以造成多台I/O设备争用控制器、通道。使通道成为I/O的主要瓶颈，造成系统吞吐量下降。解决2方法：1、增加通路，提高系统的灵活性、可靠性；(图例)2、设置缓冲区，增加I/O设备的独立性。,2020/5/28,计算机操作系统,字节多路通道示意图,字节多路通道,控制器1,控制器2,控制器n,.,2020/5/28,计算机操作系统,6.2I/O控制方式,I/O控制方式发展宗旨：尽量减少CPU对I/O的干预，提高CPU的利用率。发展的四个阶段：6.2.1程序I/O方式；6.2.2中断驱动I/O控制方式；6.2.3DMA方式；6.2.4通道方式；,2020/5/28,计算机操作系统,6.2.1程序I/O方式（ProgrammedI/O）,早期无中断系统工作特点：1、“忙测试”：(1)CPU向I/O控制器发一条I/O命令，启动I/O设备；(2)置设备状态寄存器中busy为1；(3)循环测试busy，直到busy=0;2、每一次，I/O一个字（符）,2020/5/28,计算机操作系统,6.2.2中断驱动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一个字（符）,2020/5/28,计算机操作系统,6.2.3DMA(DirectMemoryAccess)方式,特点：1、I/O基本单位是数据块(Block)；2、I/O是直接从设备入内存，或相反；3、一块/多块完成后，CPU才干预；DMA组成工作过程3步：1、进程I/O，CPU给控制器发送：I/O命令、内存/外存起址、传输字节数；2、CPU启动控制器进行数据I/O；3、I/O完成，DMA向CPU发送中断信号；,2020/5/28,计算机操作系统,DMA组成,Count,内存,起址,CPU,数据寄存器DR,内存地址MAR,计数器DC,命令寄存器DR,I/O逻辑,接口1,接口n,2020/5/28,计算机操作系统,6.2.4通道方式,工作过程：1、进程I/O，CPU向通道发送I/O命令，给出通道程序的起址、需访问的设备等；2、通道执行通道程序，完成I/O，并中断通知CPU。I/O量：以一组数据块为单位。,2020/5/28,计算机操作系统,6.3缓冲管理,一、缓冲引入原因1、缓和CPU与I/O设备间速度不匹配的矛盾；2、减少CPU对I/O的干预；3、提高CPU和I/O设备之间的并行程度；二、缓冲的种类1、单缓冲2、双缓冲3、循环缓冲(多缓冲，类似于生产者-消费者中的缓冲区)4、缓冲池,2020/5/28,计算机操作系统,1、单缓冲(SingleBuffer),工作方式：进程发出I/O请求时，操作系统在主存分配一个缓冲区，通过缓冲区完成I/O。例：从块设备输入处理（性能分析）1、将一块输入数据输入缓冲区，时间T；2、系统将缓冲区数据复制到用户区，时间M；3、CPU对输入的数据处理，时间C；,用户进程,操作系统,BUF,数据区,CPU处理C,复制M,设备输入T,2020/5/28,计算机操作系统,单缓冲性能分析,无缓冲区时，每一块数据的处理时间为：T+C单缓冲区时，每一块数据的处理时间为：MAX(C,T)+M由于Mprn,逻辑设备到物理设备的映射,2020/5/28,计算机操作系统,三、逻辑设备到物理设备的映射,1、逻辑设备表LUT(LogicalUnitTable)逻辑设备名物理设备号驱动程序入口地址/dev/tty31024/dev/print52046.2、LUT的2种设置方式(1)整个系统设置一张缺点：不同用户的逻辑设备名不允许相同。(2)每个用户进程设置一张，置于进程PCB中。,SPOOLing技术,2020/5/28,计算机操作系统,6.4.5SPOOLing技术,思想：通过在高速外存设置I/O缓冲，将独占型设备改造成为可共享的虚设备。SPOOLing-在线同时外围操作(SimultaneousPeripheralOperationOn-Line)一、SPOOLing系统的组成(3部分)1、输入井和输出井在磁盘开辟存储空间，收容输入、输出数据。2、输入缓冲和输出缓冲在内存设置缓冲，暂存从设备输入或从输入井输入的数据。3、输入进程SPi和输出进程SPo,工作过程,2020/5/28,计算机操作系统,SPOOLing系统组成示意图,SpiSpo,输入缓冲区InBuff,输出缓冲区OutBuff,输入设备,输出设备,磁盘,输入井,输出井,2020/5/28,计算机操作系统,二、SPOOLing系统的工作过程,输入过程：SPOOLing输入程序Spi主要工作是负责将输入设备上的作业以作业为单位通过内存缓冲区传输至输入井，并建立JCB，同时维持后备队列。Spi是系统中一个独立的进程，无任务时，处于等待状态（睡眠状态）。Spi被唤醒的时机有3个，Spi被唤醒后，根据收到的信号作相应的工作：1、当输入设备上有作业输入请求时；2、当输入设备工作结束时；3、向磁盘输入井传输一道作业结束时；,SPOOLing的特点,2020/5/28,计算机操作系统,根据唤醒时机不同，Spi的工作,(1)设备有输入请求；Spi启动相应通道，将作业输入到内存输入缓冲区，自身进入等待；(2)输入设备出现“结束中断”；Spi根据输入缓冲区中的内容，建立JCB，并在输入井中为作业分配空间，启动磁盘通道将输入缓冲区中作业输到输入井，自身进入等待。(3)向输入井传输作业结束，出现“磁盘结束”中断；Spi将作业JCB加入后备队列，并向作业调度程序发信号，引起作业调度，自身进入等待。,2020/5/28,计算机操作系统,三、SPOOLing的3特点,1、提高了I/O速度；由对低速设备的I/O改为对输入/输出井的存取，缓和了CPU与低速设备的矛盾；2、将独占型设备改造为共享设备；3、实现了虚拟设备功能；多个进程同时（并发）地从输入/输出井存取数据，感觉是独占I/O设备。,2020/5/28,计算机操作系统,6.5设备处理,设备处理程序/设备驱动程序功能：接收上层软件的I/O命令，转化为具体的I/O要求，控制设备完成I/O操作。处理6过程：1、将抽象要求转换为具体要求；即将I/O命令转换为控制器可接受的命令格式；例：磁盘块号转换为盘面、道号、扇区；2、检查I/O请求的合法性；3、读出和检查设备状态；4、传送必要的参数；如传输字节数、内存地址；5、设置工作方式；异步/同步通信；6、启动I/O设备；完成I/O。,2020/5/28,计算机操作系统,第4部分文件系统,7.1文件和文件系统7.2文件结构7.3目录管理7.4文件共享7.5文件保护,2020/5/28,计算机操作系统,7.1文件和文件系统,7.1.1文件、记录和数据项（数据元素/字段/域）记录：一组相关数据项的集合；文件：具有文件名的一组相关信息的集合；7.1.2文件类型（5）1、按用途分：系统、用户、库文件；2、按存取控制属性：只读、读写、只执行文件；3、按文件逻辑结构：有结构、无结构文件；4、按文件物理结构：顺序、链接、索引文件；5、按文件中数据形式：源、目标、可执行文件；,文件系统模型,2020/5/28,计算机操作系统,7.1.3文件系统模型,文件系统：用于操纵和管理各种文件，方便用户使用文件的软件集合。文件系统模型层次结构一、管理对象文件、目录、外存空间二、操纵和控制内容1、文件存储空间管理；2、目录管理；3、地址映射；4、R/W管理；5、共享和保护；三、文件系统接口1、命令接口；2、程序接口；,文件操作,2020/5/28,计算机操作系统,7.1.4文件操作,文件操作分2大类：一、对记录操作记录增、删、改；记录的查询；二、对文件的操作创建文件；删除文件；读写文件；设置读写位置；,2020/5/28,计算机操作系统,文件系统模型层次结构,文件系统接口逻辑文件系统基本I/O管理程序基本文件系统（物理I/O层）I/O控制层（设备驱动程序）对象及其属性说明,对对象操纵和管理的软件集合,启动I/O操作、接收中断,处理内、外存数据交换,设备选择、地址映射、空闲块管理、缓冲设置,目录管理、存取控制验证,命令、程序接口,文件、目录、外存,2020/5/28,计算机操作系统,7.2文件结构,文件结构分2类：7.2.1逻辑结构/文件组织从用户观点出发，所观察到的文件组织形式。是用户可以直接处理的数据和结构，独立于物理特性。逻辑结构可分为：（1）有结构(记录)文件：定长/变长记录（2）无结构(流式)文件7.2.2物理结构/存储结构文件在外存上的存储组织形式，与存储介质的存储性能有关。,2020/5/28,计算机操作系统,7.2.1文件的3种逻辑结构,一、顺序文件文件记录的排列、存取按顺序进行。适用场合：对记录批量存取；顺序介质；二、索引文件为变长记录文件建立一张索引表（或多级索引），用户通过关键字访问记录。适用场合：对信息处理及时性要求高的场合。三、索引顺序文件顺序文件记录分组，并建立索引表，索引表项为各组的第一记录指针。,2020/5/28,计算机操作系统,顺序文件示意图,R0R1R2.Ri.,定长记录文件,Rprt=Ptr+i*l,l,Ptr=0,L0R0L1R1.LiRi.,Ptr=0,Rprt,L0,变长记录文件,2020/5/28,计算机操作系统,索引文件的组织,索引号长度m指针Ptr0M01M1.IMi.,R0R1.Ri.,索引表,逻辑文件变长记录,2020/5/28,计算机操作系统,索引顺序文件的组织,键值逻辑地址AnQiBaoRongChenLin,姓名其它属性AnQiAnKang.BaoRong.ChenLin.,索引表,逻辑文件,2020/5/28,计算机操作系统,7.2.2文件的物理结构,对磁盘、磁带、磁鼓等辅存介质的分配、回收是以块(Block)为单位。通常，对于记录型文件存储时，可能情况为：1、一个物理块可以存放若干逻辑记录；2、一个逻辑记录需要占用多个物理块；为简单起见，设一个逻辑记录占用一个物理块。则文件的逻辑结构分为以下3类：一、顺序结构/顺序文件二、链接结构/串联文件三、索引结构/索引文件,2020/5/28,计算机操作系统,顺序结构/顺序文件,组织：一个逻辑文件的记录，依此存储在辅存连续的物理块中。优缺点：例如：文件A有三个记录，存储在6，7，8三个物理块中。,.文件名第一物理块号文件长度.,文件说明,R0R1R2,文件A,2020/5/28,计算机操作系统,链接结构/串联文件,组织：每个块设一个指针，指向该文件下一记录所在物理块号。（图例）优点：记录数可任意增减。缺点：无法直接存取，且为单向查找。实现双向查找的2种方法：1、采用双向链表；2、某一物理块链表指针值设置为：其前、后两个物理块号的“异或”值(按位加)；若该物理块为文件的首、尾记录，其前、后物理块块号设为0。（例如）,2020/5/28,计算机操作系统,链接结构示意图,例如：文件A有三个记录，存储在4，12，8三个物理块中。,.文件名起始物理块号.,R0/412,R1/128,R2/8NIL,按任意键为异或双向链表,查找过程：向下查找：本记录链表指针值与上记录块号“异或”向上查找：本记录链表指针值与下记录块号“异或”,0异或1212,4异或812,12异或012,4异或8010010001100=12,2020/5/28,计算机操作系统,索引结构/索引文件,组织：为每一个文件建立一张索引表，每一个表目指向记录所在的物理块号。,2020/5/28,计算机操作系统,7.3目录管理,借助于文件目录，可将每个文件的符号名与其所在存储空间地址联系起来。对文件目录管理的要求：1、实现“按名存取”；2、有较高的目录检索速度：合理组织文件目录；3、允许文件重名；4、提供文件共享功能；7.3.1文件控制块和索引结点一、文件控制块(FCB-FileControlBlock)二、索引结点,常见目录结构,2020/5/28,计算机操作系统,一、文件控制块(FCB-FileControlBlock),FCB是一个文件目录项。通常，一个文件目录也被看做是一个文件-目录文件。FCB包含的信息有3类：1、基本信息：文件名、外存物理位置、逻辑结构（定长/变长）、物理结构；2、存取控制信息：文件主/核准用户/一般用户的存取权限；3、管理信息：创建的日期/时间、上次修改的日期/时间、要求保留的时间。,2020/5/28,计算机操作系统,二、索引结点,1、引入原因减少磁盘I/O，提高目录查找速度。例2、磁盘索引结点指存放在磁盘上的索引结点，系统中每个文件都有唯一的磁盘索引结点及编号(外存inode区的顺序号)。主要内容3、内存索引结点存放在内存的索引结点。当文件被打开时，将磁盘索引结点复制到内存索引结点中。内存索引结点包括内容,2020/5/28,计算机操作系统,示例,设一个FCB为64B，Block=1KB，则每个磁盘块可存放16个目录项。若共有3200个FCB，则需200个Block，查找一个文件平均启动磁盘100次。改进方法：由于文件查找时，首先根据文件名查找，找到匹配的文件名后，再读取文件的描述信息。为此，可将FCB分成2部分：文件名和文件描述。实现：用一个数据结构(称为索引结点/inode)记录文件的描述信息，每个文件有唯一的inode号。例：Unix文件目录结构,2020/5/28,计算机操作系统,Unix文件目录结构示例,Unix中，一个文件目录项共16B。其中14B保存文件名，2B存放i结点指针。则：1Block可存放64个目录项；查找一个文件平均启动磁盘的次数减少到1/4。,文件名外存inode号文件名1文件名2.,2020/5/28,计算机操作系统,磁盘索引结点inode主要包括7部分信息,1、文件主标识/组标识；2、文件类型：普通文件/目录文件/块设备文件/字符设备文件；3、文件存取权限；4、文件物理地址：数据文件的盘块号；5、文件长度；6、文件连接计数：文件在目录中具有的路径名数；图例7、文件存取时间：文件最近被存取、修改时间，索引结点修改时间。,2020/5/28,计算机操作系统,文件连接图例,.Name1inode:n.,目录/a/b,.Name2inode:n.,目录/c/d,.连接计数：2物理地址.,外存inode:n,文件存储块,Unix采用索引结构,2020/5/28,计算机操作系统,内存索引结点/活动索引结点表,每个文件在外存都有一个inode。当需要查询、修改外存inode中信息时，一般是将其临时调入内存，处理完毕后再回写到外存。由于系统对inode的访问频繁，按该方式进行很不经济。为此，可在内存设置索引结点，其内容较外存inode略有增减，增加部分主要有5部分：1、外存索引结点编号；2、状态：指示i结点是否被修改、上锁；3、访问计数：共享该i结点的进程数；4、文件所在设备的逻辑设备号；5、链接指针：空闲/散列队列指针,2020/5/28,计算机操作系统,7.4常见目录结构及查询技术,7.4.1单级目录结构(SingleLevelDirectory)7.4.2两级目录结构(TwoLevelDirectory)7.4.3树型目录结构/多级目录(Tree-structuredDirectory)7.4.4目录查询技术,2020/5/28,计算机操作系统,7.4.1单级目录结构图例,1、查找速度慢：N个目录，平均查找N/2个目录项；2、不允许重名；,文件名状态位物理地址.AlphaReportText.,2个缺点：,实现：整个系统只建立一张目录表，为每个文件分配一个目录项。,2020/5/28,计算机操作系统,7.4.2两级目录结构,实现：目录分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、不同用户文件可以重名,2020/5/28,计算机操作系统,两级目录结构图例,User1User2User3.Usern,AlphaProgram1,AlphaTest,.,MFD,UFD,2020/5/28,计算机操作系统,7.4.3树型目录结构/多级目录,一、实现在两级目录中，允许用户创建自己的子目录并组织其文件，即可形成多级目录结构。图例二、路径名从根目录到文件之间的通路。三、当前目录相对路径名：从当前目录到文件之间的路径。绝对路径名：从根目录到文件之间的路径。四、目录的增加和删除增加：无重名。删除：不删除非空目录/可删除非空目录。,2020/5/28,计算机操作系统,树型目录结构图例,ABC,ABD,FED,GA,AC,JNK,JMK,AHF,当前目录,2020/5/28,计算机操作系统,7.4.4目录查询技术,目前，采用的目录查询技术有两种：线性检索法和Hash方法。一、线性检索法按照用户给定文件名，顺序查找文件目录表，得到文件目录项。见P243，F8-11图例。二、Hash方法略。,2020/5/28,计算机操作系统,7.5文件共享,多个用户（进程）共享同一份文件，即系统中只保存共享文件的一个副本。7.5.1早期文件共享方法一、绕弯路法二、连访法三、用基本文件目录实现共享7.5.2基于索引结点的共享方式7.5.3利用符号链实现文件共享,2020/5/28,计算机操作系统,一、绕弯路法,实现：系统设置当前目录指针，用户可对当前目录下的文件直接访问。当需访问其它目录下的文件时，通过指定路径来完成。系统设定*表示当前目录的父目录。例如：*.E.J表示访问其父目录下E子目录中的J文件。图示,实现：建立目录之间的链接，使一个目录中的目录项直接指向另一个目录中的目录项。同时在文件说明中增设“连访”属性标识物理地址是文件或目录项的指针；增设“用户计数”标识共享文件的用户数。例如：图示,二、连访法,2020/5/28,计算机操作系统,用基本文件目录实现共享,实现：系统将原文件目录分成两部分：1、基本文件目录BFD(BaseFileDirectory)每个文件/目录有一个目录项，包含：文件标识数，其它目录信息。2、符号文件目录SFD(SymbolFileDirectory)每个用户有一个，其中目录项指示其文件的文件名和文件标识数。图示提高文件访问速度的方法：系统在内存设置一张活动文件表AFT，为每个用户设置一张活动名字表ANT。执行OPEN操作时将SFD内容入ANT；BFD内容入AFT。,2020/5/28,计算机操作系统,用基本文件目录实现共享图示,0123456789.,BFD,空闲文件目录,Wang3Zhang4,Sqrt5Beta6.,Mist7Alpha6Report8Oaf9.,MFD,FFD,WangSFD,ZhangSFD,2020/5/28,计算机操作系统,7.5.2基于索引结点的共享方式,与设置BDF、SFD实现共享类似。实现：设置索引结点，存储文件的物理地址、链接计数（共享计数）及其它文件属性；文件目录只包括文件名和该文件对应索引结点的指针。优点：任何对索引结点内容的修改对其它共享用户都是透明的。,2020/5/28,计算机操作系统,7.5.3利用符号链实现文件共享,实现：设B为了共享C的文件F，在B中创建一个Link类型的新文件，新文件目录中只包含被链接文件F的路径名，称这种链接方法为符号链接(symbolicLinking)说明：只有文件主人的目录中有文件索引结点的指针，其它用户目录中只有路径名。,2020/5/28,计算机操作系统,7.6文件保护,7.6.1影响文件系统安全性的3个主要因素：1、人为因素；2、系统因素：系统部分软件、介质故障；3、自然因素：存放在磁盘中的数据，随着时间的推移发生溢出或逐渐消失；7.6.2文件系统保护机构应有的3个功能：1、防止未核准用户存取文件；2、防止一个用户冒充另一个用户存取文件；3、防止核准用户误用文件；,文件保护措施,2020/5/28,计算机操作系统,7.6.3文件保护措施,文件保护：防止合法用户由于误操作而破坏文件；文件保密：防止未核准用户使用文件；可采用下列3种措施保证文件系统的安全：1、通过存取控制机制，防止人为因素造成的不安全性；2、通过容错技术，防止系统部分的故障造成的不安全性；3、通过“后备系统”，防止自然因素造成的不安全性；,存取控制机制,2020/5/28,计算机操作系统,7.6.4存取控制机制,实现文件存取控制方法较多，且各有特点，主要介绍基本概念和常见存取控制机制。一、保护域(ProtectionDomain)二、访问矩阵(AccessMatrix)三、访问矩阵的修改四、访问矩阵实现访问控制表(AccessControlList)访问权限表(AccessCapabilitiesList)五、分级安全管理（自习）,2020/5/28,计算机操作系统,一、保护域(ProtectionDomain),进程可访问的对象称为保护域。对不同的对象，系统允许进程执行的操作不同。一个进程对某对象可执行操作的权限成为访问权。可用有序对(对象名，权集)表示，例如：（F1，R|W）表示进程对文件F1的操作权限为读、写。一组对象访问权的集合用域表示，可将每个用户或每个进程视为一个域。例F8-16进程与域的联系方式有2种：1、静态联系：进程可用资源集是固定的。2、动态联系：进程可用资源集是变化的。,2020/5/28,计算机操作系统,例F9-16,(F1,R)(F2,R|W),(F3,R)(F4,RWE)(F5,RW),(F6,RWE)(Printer1,W),域1,域2,域3,2020/5/28,计算机操作系统,7.6.2访问矩阵(AccessMatrix),描述域及所属对象的矩阵称为访问矩阵。访问矩阵中对象访问权由资源拥有者或管理者确定。通过设置域间切换开关实现进程与域的动态联系。,文件1文件2文件3文件4打印机1绘图仪D1D2D3D1RRWSD2RRWEWSD3WW,2020/5/28,计算机操作系统,7.6.3访问矩阵的修改,为满足系统动态变化的需要，访问矩阵中的权限应允许有限制地进行修改，为此，系统中增设拷贝权、所有权和控制权。一、拷贝权(CopyRight)若进程对域中某一对象访问权有拷贝权（*），则它可将对该对象的访问权拷贝到其它域中，使其它域中进程对同一对象也有相同的访问权。拷贝访问权的2种应用：1、转移拷贝权：拷贝后取消原域的权限；例2、限制拷贝：拷贝后的访问权无拷贝权；例,2020/5/28,计算机操作系统,拷贝权示例,文件1文件2文件3D1EW*D2ER*ED3E,文件1文件2文件3D1ED2ER*ED3EW*,文件1文件2文件3D1EW*D2ER*ED3EW,转换拷贝权,限制拷贝,任意键，限制拷贝.,2020/5/28,计算机操作系统,访问控制表(AccessControlList),当系统中的域和对象数量较大时，访问矩阵对内存的要求会很高。一般地，由于并非每一个用户进程对系统中每一个对象都进行访问，所以访问控制矩阵是稀疏矩阵，为此，将访问矩阵按列划分，每列建立一张访问控制表ACL，删除其中空项。ACL由（域，权集）组成，如果其对象是文件，则可将对应的ACL存放在该文件的目录项中。用户/进程对文件进行访问时，系统先检查ACL，确定访问是否合法：是，执行访问操作；否，拒绝访问，提示相关信息。,2020/5/28,计算机操作系统,访问权限表(AccessCapabilitiesList),将访问矩阵按行（域）进行划分，每一行构成一张访问权限表。例如：D2域的访问权限表为：,对象类型访问权限对象文件R指向文件3的指针文件RWE指向文件4的指针打印机1W指向打印机1的指针,2020/5/28,计算机操作系统,7.6.5分级安全管理,2020/5/28,计算机操作系统,8.1磁盘I/O8.2外存分配方法8.3空闲存储器的管理8.4磁盘容错技术8.5文件系统性能的改善8.6数据一致性控制,第8章磁盘存储管理,2020/5/28,计算机操作系统,8.1磁盘I/O,一、磁盘的2种类型（图例）1、固定头磁盘2、移动头磁盘二、移动头磁盘访问时间的3个组成部分1、寻道时间Ts2、旋转延迟时间Tr3、数据传输时间Tt,磁盘调度算法,2020/5/28,计算机操作系统,磁盘类型图例,2020/5/28,计算机操作系统,磁盘调度算法,1、先来先服务FCFS(FirstComeFirstServed)2、最短寻道时间优先SSTF(ShortestSeekTimeFirst)3、4种扫描算法*扫描算法SCAN（电梯调度法）*循环扫描CSCAN（CircularSCAN）*N步扫描（NStepSCAN）*FSCAN,2020/5/28,计算机操作系统,先来先服务FCFS,思想：选择等待队列中最先到达的访问请求，作为下一次的访问对象。例：P261，F9-2,100磁道,低磁道,高磁道,2020/5/28,计算机操作系统,最短寻道时间优先SSTF,思想：选择等待队列中离当前磁道最近的访问请求，作为下一次的访问对象。例：P261，F9-3,100磁道,低磁道,高磁道,2020/5/28,计算机操作系统,扫描算法SCAN（电梯调度法）,思想：选择等待队列中离当前磁头移动方向最近的访问请求，作为下一次的访问对象。例：P262，F9-3设，磁头向磁道增加方向移动,100磁道,低磁道,高磁道,2020/5/28,计算机操作系统,循环扫描CSCAN,思想：单向扫描，选择等待队列中离当前磁头移动方向最近的访问请求，作为下一次的访问对象，直到该方向最后一个请求，反向。例：P262，F9-4设，磁头向磁道增加方向移动,100磁道,低磁道,高磁道,2020/5/28,计算机操作系统,N步扫描,思想：将磁盘请求队列分为若干长度为N的子队列，并按FCFS算法依次处理这些队列，在处理每一个队列时，采用SCAN算法。(分析N=1和N为无穷情况)例：设N=3，到达次序：55,58,39,18,90,160,150,38,184,100磁道,低磁道,高磁道,2020/5/28,计算机操作系统,FSCAN算法,思想：将磁盘请求队列分为2个子队列，其中一个为当前所有请求构成的队列，另一个为扫描期间新到达的请求构成的队列，并按N步扫描处理。,2020/5/28,计算机操作系统,10.2外存分配方法,一般有3种：连续分配、链接分配和索引分配。一、连续分配思想：文件在外存分配连续的磁盘块。优点：1、支持顺序访问、直接访问；2、磁头定位时间短，顺序访问速度快。缺点：1、要求连续盘块，易产生碎片；2、需预知文件长度OVER,链接分配,2020/5/28,计算机操作系统,外存分配方法（续1）,二、链接分配思想：通过磁盘块中的链接指针，将文件所属盘块链成链表，构成链接文件。分为2种：1、隐式链接（P265，F9-7）实现：文件目录中只给出文件第一、最后一个盘块的指针，其余由链接指针给出。2、显式链接（P266，F9-8）实现：系统设置一张链接表（FAT），存放每一个链接文件各物理块的指针。文件目录中保存第一块的盘块号。缺点：不支持直接访问，FAT需磁盘空间。,索引分配,2020/5/28,计算机操作系统,外存分配方法（续2）,三、索引分配（分3种）1、单级索引分配（P267，F9-10）建立一张索引表保存文件所分配的块号。2、多级索引分配（F9-11）思考题3、混合索引分配结合直接地址和索引分配方式的分配方式。例：在UNIXS5系统中，有13个地址项，若每个盘块大小为4KB，一个盘块可存放1K个盘块号，则按照F9-12混合分配方式文件最大长度可达4TB。,2020/5/28,计算机操作系统,多级索引分配思考题,某文件有1000个记录，文件采用索引分配，设每一个盘块存放一个记录，每一盘块可以存放10个索引表目。问：1、保存该文件需要建立几级索引？2、共需要多少磁盘块？,2020/5/28,计算机操作系统,10.3空闲存储器的管理,主要功能：1、设置相应数据结构，记录空闲存储空间的分配情况；2、实现存储空间的分配与回收。空闲存储器的4种管理方法：1、空闲表法（空白文件目录）2、空闲块链3、位示图法4、成组链接法,2020/5/28,计算机操作系统,1、空闲表法（空白文件目录）,管理：系统为每一个空白文件（一个连续未分配的区域）建立一个目录，每个空闲区有一个表目。主要结构为：第一个空白块地址空白块数分配：系统依次扫描空白文件目录，找到一个合适的空白文件分配。回收：动态修改空白文件表（合并）。2个特点：1、适用于建立顺序文件；2、当有大量小的空白文件时，效率降低。,2020/5/28,计算机操作系统,2、空闲块链,管理：将所有空闲块链接在一起，组成队列。分配：从链首依次摘取1块或n块。回收：回收块入链尾。特点：操作简单；当链较长时，效率较低。改进：采用空闲盘区链：将所有空闲盘区链接在一起，每个盘区可包含若干空闲盘块。分配/回收：类似动态分区分配。OVER,2020/5/28,计算机操作系统,3、位示图法,管理：系统专设几个字，每个字的每一位对应一个磁盘块。F9-14位：为1表示该块已分配；为0表示该块未分配。每位对应盘块号b=(i-1)*n+j其中：i、j分别为行列值，n为每行位数2个特点：1、由于辅存物理块数固定，位示图尺寸固定；2、位示图较小，可常驻内存，分配/回收速度快。,2020/5/28,计算机操作系统,4、成组链接法（Unix采用）,管理：设置空闲盘块号栈，存放当前可用的一组空闲盘块的盘块号（最多存放100个号），以及堆栈中尚有的空闲块数。说明：1、栈属于临界资源，应互斥使用；2、S.free(0)是栈底，栈满时，栈顶为S.free(99)。例：设共有10000个盘块，第201-7999号盘块用于存放文件，则成组链接法结构见F9-15空闲盘块的分配与回收（P273）,2020/5/28,计算机操作系统,UNIX成组链接法图例,空闲盘块号栈,.100300299298.202201.,100400399.301,100500499.401,9907999.7901,299,399,7899,7999,201,301,7801,7901,.,.,.,.,.,.,.,300,400,7900,S.free,0,1,2,98,99,2020/5/28,计算机操作系统,10.4磁盘容错技术,通过增加冗余的磁盘驱动器、控制器来提高磁盘系统的可靠性。磁盘冗错技术/系统冗错技术SFT(SystemFaultTolerance)分3个级别：SFT-I：低级，防止磁盘表面缺陷引起的数据丢失。SFT-2：中级，防止驱动器、控制器故障引起的不正常。SFT-3：高级，利用冗余的存储信息作错误校正。,2020/5/28,计算机操作系统,10.4.1第一级冗错技术,主要措施：双目录、双FAT、写后读校验。一、双目录和双FAT实现：在不同盘或同一盘的不同区域，建立2份目录和FAT。系统初启时验证一致性。二、热修复重定向和写后读校验防止将数据写入有缺陷的盘块中。1、热修复重定向：磁盘设置热修复重定向区，存放发现盘块有缺陷时的待写数据，并登记。2、写后读校验：将写入磁盘的数据立即读入内存另一缓冲区，并与原数据比较是否一致。,2020/5/28,计算机操作系统,10.4.2第二级冗错技术,1、磁盘镜像(DiskMirroring)实现：用同一磁盘控制器来控制2个完全相同的驱动器，每次对主磁盘写入数据后，采用写后读校验方式，写入备份盘。F9-16缺点：磁盘利用率低；无法处理控制器故障。2、磁盘双工（DiskDuplexing）实现：将2台磁盘驱动器分别连到2个磁盘控制器、通道上，并镜像成对。F9-17优点：A、2个独立通道，可并行写操作；B、读数据时，可采用分离搜索技术，从响应快的通道取数据。,2020/5/28,计算机操作系统,磁盘镜像/双工示意图,磁盘镜像示意图,磁盘双工示意图,主机,磁盘控制器,通道,磁盘驱动器,主机,磁盘控制器,通道,磁盘控制器,通道,磁盘驱动器,2020/5/28,计算机操作系统,10.4.3廉价磁盘冗余阵列RAIDRedundantArrayofInexpensive