第1章操作系统引论
计算机操作系统【第一章】
1. 设计现代OS的主要目标是什么
答:方便性,有效性,可扩充性和开放性.
2. 用户角度:OS的作用可表现为哪几个方面
a. 资源管理角度:OS作为用户与计算机硬件系统之间的接口;
b. OS作为计算机系统资源的管理者;
c. OS实现了对计算机资源的抽象。
3. 试说明推动多道批处理系统形成和发展的主要动力是什么以及比较优缺点
答:不断提高计算机资源利用率和系统吞吐量的需要;
比较:a. 单道批处理系统是最早出现的一种OS,它具有自动性,顺序性和单道性的特点;
---多道批处理系统则具有调度性,无序性和多道性的特点;
b. 单道批处理系统是在解决人机矛盾及CPU和I/O设备之间速度不匹配的矛盾中形成的,旨在提高系统
资源利用率和系统吞吐量,但是仍然不能很好的利用系统资源;
---多道批处理系统是对单道批处理系统的改进,其主要优点是资源利用率高,系统吞吐量大;缺点是
平均周转时间长,无交互能力.
5:多道批处理系统的优缺点以及需要解决的问题
答:优点:资源利用率高、系统吞吐量大、提高了I/O设备和内存的利用率。
缺点:平均周转时间长、无交互能力。
问题:处理机、内存、I/O设备、文件、作业管理问题。
6. 试说明推动分时系统形成和发展的主要动力是什么以及特征
答:用户的需要.即对用户来说,更好的满足了人-机交互,共享主机以及便于用户上机的需求.
特征:多路性、独立性、及时性和交互性。
7:实时系统
答:(1)实时控制、实时信息处理;
(2)实时任务:周期性、非周期性、硬、软实时任务。
(3)与分时比较:多路性、独立性、及时性、交互性和更可靠。
(4)关键问题:及时接收,及时处理
8: OS具有哪几大特征它的最基本特征是什么
答:(1)并发(Concurrence),共享(Sharing),虚拟(Virtual),异步性(Asynchronism).
(2) 其中最基本特征是并发和共享.
9:进程和线程
答:进程:是资源分配的基本单位,由机器指令、数据和堆栈组成;
线程:是独立运行和独立调度的基本单位。
10:处理机、内存、设备和文件管理具有哪些功能
答:处理机:(1)进程控制: 创建、撤销进程和控制进程状态;
(2)进程同步: 对诸进程的运行进行调节;
(3)进程通信: 实现在相互合作进程之间的信息交换;
(4) 调度: 作业调度和进程调度;
内存:(1)内存分配(静态和动态);(2)内存保护(3)地址映射(4)内存扩充等
设备:缓冲管理,设备分配和设备处理,以及虚拟设备等。
文件:对文件存储空间的管理,目录管理,文件的读,写管理以及文件的共享和保护. 主要任务是对用户文件和系统文件进行管理,以方便用户使用,并保证文件的安全性。
11:模块接口法的优缺点
答:优点:提高操作系统设计的正确性、可理解性和可维护性;增强操作系统的适应性;加速操作系统的开发过程。
缺点:
12:客户/服务器模式的优缺点
答:数据的分布处理和存储;便于集中管理;灵活性和可扩充性;易于改编应用软件。
不足:不可靠性和瓶颈问题。
13:微内核操作系统的描述及优点
答:描述:足够小的内核、基于客户/服务器模式、应用“机制与策略”分离原理、采用面向对象技术。
优点:提高了系统的可扩展性、增强了系统的可靠性、可移植性、提供了对分布式系统的支持和融入了面向对象技术。
14:操作系统的用户接口有:命令接口、程序接口、图形接口
第2章进程管理
1:程序顺序和并发执行的特征
答:顺序:顺序型、封闭性和可再现性。
并发:间断性、失去封闭性、不可再线性。
2:对进程的描述特征
答:(1)结构特性(程序段、数据段和PCB);(2)动态性;(3)并发性;(4)独立性;(5)异步性。进程是进程实体的运行过程,是系统的进行资源分配和调度的一个独立单位。
3:引入挂起(suspend)状态的原因
答:(1)终端用户的请求(2)父进程请求(3)负荷调节的需要(4)操作系统的需要。
4:进程控制块包含的信息及组织方式
答:(1)进程标识符(内部和外部标识符);
(2)处理机状态(通用寄存器、指令寄存器、程序状态字PSW和用户栈指针);
(3)进程调度信息(进程状态、进程优先级、进程调度所需其他信息和事件如阻塞原因);
(4)进程控制信息(程序和数据的地址、进程同步和通信机制、资源清单和链接指针)。
组织方式:链接方式和索引方式。
5:引起创建进程的事件以及创建过程
答:事件:(1)用户登录;(2)作业调度;(3)提供服务;(4)应用请求(自己创建进程)。
过程:(1)申请空白PCB;(2)为新进程分配资源;(3)初始化进程控制块;(4)将新进程插入就绪队列。
6:引起进程终止事件
答:(1)正常结束;
(2)异常结束(越界错误、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错和I/O故障);
(3)外界干预(操作员或操作系统干预、父进程请求和父进程终止)。
7:引起进程的阻塞block()或唤醒wakeup()
答:(1)请求系统服务(2)启动某种操作(3)新数据尚未到达(4)无新工作可做。
8:同步机制应该遵循哪些规则
答:空闲让进、忙则等待、有限等待和让全等待。
9:管程组成与特性
答:组成:名称、局部于内部的共享数据结构和一组操作过程以及设置初始值语句。
特性:模块化、抽象数据类型和信息掩蔽。
管程定义共有数据结构如消息队列,同步操作和初始化操作,解决共享资源的互斥使用问题,被动工作方式,不能与调用者并发是一个资源管理模块。
……进程通信……
10:进程通信的类型
答:共享存储器系统、消息传递系统和管道通信系统(互斥、同步、确定对方存在)。
11:消息传递系统实现的问题
答:(1)通信链路:1)点对点链接和多点链接,2)通信方式:单向和多向通信链路
(2)消息的格式(短和长消息格式);
(3)进程同步方式(发送与接受进程的三种阻塞组合)。
……线 程……
12线程的属性
答:轻型实体、独立调度和分派的基本单位、可并发执行和共享进程资源。
线程是比进程更小的单位,独立运行的单位,是为了减少程序并发执行时所付出的时空开销,是OS有更好的的 你 吗并发性。
13内核支持线程、用户级线程和组合方式。
第3章处理机调度与死锁
……处理机的调度的层次……
调度分为批量型调度和终端型调度;批量型调度过程是:高级调度(作业调度)->中级调度->低级调度(进程调度)。
1:高级调度。
作业的组成:程序、数据和作业说明书。
作业的三个作业步:“编译”、“连结装配”和“运行”作业步。
调度多少个作业:多道程序度
调度哪些作业:调度算法
2:低级调度。
功能:保存处理机的现场信息、按某种算法选取进程和把处理机分配给进程。
实现调度机制:排队器、分派器和上下文切换机制。
抢占调度原则:优先权原则、短作业(程序)优先原则和时间片原则。
……调度队列模型和调度准则……
1:选择调度算法的准则
答:面向用户的准则
1)周转时间短(批处理系统),2)响应时间快(分时系统),3)截至时间的保证(实时),4)优先权准则(三种系统)。
面向系统准则:系统吞吐量(批处理)、处理机利用率和各类资源的平衡利用。
……调度算法……
调度算法:根据系统的资源分配策略所规定的资源分配算法。
算法:(1)先来先服务(FCFS);
(2)短作业(进程)优先;
(3)高优先权优先调度
1)静态优先权和动态优先权;
2)高响应比优先调度算法:优先权=(等待时间+要求服务时间)/要求服务时间
(4)基于时间片的轮转调度算法
1)时间轮转发;
2)多级反馈队列调度算法。(适用终端型、短批处理和长批处理作业用户)
……实时调度……
1:实现实时调度应具备一下条件。
答:(1)提供必要信息(就绪时间、开始截止时间和完成截止时间、处理时间、资源要求和优先级)
(2)系统处理能力强;
(3)采用抢占式调度机制;
(4)具有快速切换机制。
2:常用的集中实时调度算法。
答:(1)最早截止时间优先即EDF算法;(2)最低松弛度优先即LLF算法。
……思索的原因和必要条件……
1:产生死锁的条件和处理。
答:条件:互斥条件、请求和保持条件、不剥夺条件和环路等待条件。
处理:(1)预防死锁(摒弃“请求和保持”、摒弃“不剥夺”、摒弃“环路等待”条件);
(2)避免死锁;
(3)检测死锁和解除思索(撤销和挂起进程)。
第4章存储器
1:程序链接分类:静态链接、装入时动态链接和运动时动态链接。
……连续分配方式……
1:连续分配方式绯分为:
(1)单一连续分配(系统区和用户区);
(2)固定分区分配(划分分区大小相等和不等);
(3)动态分区分配;
1)分区分配中的数据结构(空闲分区表和空闲分区链);
2)分区分配算法(首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法-最大块、伙伴系统和快速适应算法-索引表以及哈希算法(哈希函数));
3)分区的分配与回收。
(4)动态可重定位分区分配。
2:引入分段存储管理方式是为了满足用户的下列需求
答:方便编程、信息共享、信息保护、动态增长和动态链接。
3:虚拟存储器的特征:多次性、对唤醒和虚拟性。
4:请求分页存储管理方式的物理块分配策略和算法。
答:固定分配局部置换、可变分配全局置换和可变分配局部置换。
算法:平均分配算法、按比例分配算法和考虑优先权的分配算法。
4:页面置换算法。
答:(1)最佳置换算法(未来最长时间不被访问);
(2)先进先出FIFO页面置换算法;
(3)最近最久未使用置换算法(页表中最长时间未被使用t=t+1);
(4)Clock置换算法(循环,访问位为0置换出,为1则改为0)。
1. 可采用哪几种方式将程序装入内存它们分别适用于何种场合
a. 首先由编译程序将用户源代码编译成若干目标模块,再由链接程序将编译后形成的目标模块和所需的
---库函数链接在一起,组成一个装入模块,再由装入程序将装入模块装入内存;
b. 装入模块的方式有: 绝对装入方式,可重定位方式和动态运行时装入方式;
c. 绝对装入方式适用于单道程序环境下;
d. 可重定位方式适用于多道程序环境下;
e. 动态运行时装入方式也适用于多道程序环境下.
2. 何谓静态链接及装入时动态链接和运行时的动态链接
a. 静态链接是指事先进行链接形成一个完整的装入模块,以后不再拆开的链接方---式;
b. 装入时动态链接是指目标模块在装入内存时,边装入边链接的链接方式;
c. 运行时的动态链接是将某些目标模块的链接推迟到执行时才进行.
3. 在进行程序链接时,应完成哪些工作
a. 对相对地址进行修改;
b. 变换外部调用符号.
4. 在动态分区分配方式中,可利用哪些分区分配算法
a. 首次适应算法;
b. 循环首次适应算法;
c. 最佳适应算法.
5. 在动态分区分配方式中,应如何将各空闲分区链接成空闲分区链
应在每个分区的起始地址部分,设置一些用于控制分区分配的信息,以及用于链接各分区的前向指针;
在分区尾部则设置一后向指针,通过前,后向指针将所有的分区链接成一个双向链.
6. 为什么要引入动态重定位如何实现
a. 为了在程序执行过程中,每当访问指令或数据时,将要访问的程序或数据的逻辑地址转换成物理地
---址,引入了动态重定位.
b. 可在系统中增加一个重定位寄存器,用它来装入(存放)程序在内存中的起始地址,程序在执行时,真
---正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的,从而实现动态重定位.
7. 试用类Pascal语言来描述首次适应算法进行内存分配的过程.
(略)
8. 在采用首次适应算法回收内存时,可能出现哪几种情况应怎样处理这些情况
a. 回收区与插入点的前一个分区相邻接,此时可将回收区与插入点的前一分区合并,不再为回收分区
---分配新表项,而只修改前邻接分区的大小;
b. 回收分区与插入点的后一分区相邻接,此时合并两区,然后用回收区的首址作为新空闲区的首址,大
---小为两者之和;
c. 回收区同时与插入点的前后两个分区邻接,此时将三个分区合并,使用前邻接分区的首址,大小为
---三区之和,取消后邻接分区的表项;
d. 回收区没有邻接空闲分区,则应为回收区单独建立一个新表项,填写回收区的首址和大小,并根据
---其首址,插入到空闲链中的适当位置.
9. 在系统中引入对换后带有哪些好处
能将内存中暂时不运行的进程或暂时不用的程序和数据,换到外存上,以腾出足够的内存空间,把已
具备运行条件的进程或进程所需的程序和数据换入内存,从而大大地提高了内存的利用率.
10 为实现对换,系统应具备哪几方面功能
a. 对对换空间的管理;
b. 进程的换出;
c. 进程的换入.
11 在以进程为单位进行对换时,每次是否都将整个进程换出为什么
a. 以进程为单位进行对换时,每次都将整个进程换出;
b. 目的为了解决内存紧张的问题,提高内存的利用率.
12 为实现分页存储管理,需要哪些硬件支持你认为以Intel 8086,MC68000,
Intel 80286为芯片的微机,是否适合于实现分页管理
(有待讨论)
13 请较详细地说明,引入分页存储管理(估计印错了,是分段存储管理)是为了满足用户哪几方面的需要
a. 方便了编程;
b. 实现了分段共享;
c. 实现了分段保护;
d. 实现了动态链接;
e. 实现了动态增长.
14 在具有快表的段页式存储管理方式中,如何实现地址变换
首先,必须配置一段表寄存器,在其中存放段表始址和段长TL. 进行地址变换时,先利用段号S,与段长TL
进行比较,若S
始址和段号来求出该段对应的段表项在段表中的位置,从中求出该段的页表始址,并利用逻辑地址中的段
内页号P来获得对应页的页表项位置,从中读出该页所在的物理块号b,再用块号b和页内地址构成物理地址.
15 为什么说分段系统较之分页系统更易于实现信息共享和保护
a. 对于分页系统,每个页面是分散存储的,为了实现信息共享和保护,则页面之间需要一一对应起来,为此
---需要建立大量的页表项;
b. 而对于分段系统,每个段都从0开始编址,并采用一段连续的地址空间,这样在实现共享和保护时,只需
---为所要共享和保护的程序设置一个段表项,将其中的基址与内存地址一一对应起来即可.
16 分页和分段有何区别
a. 分页和分段都采用离散分配的方式,且都要通过地址映射机构来实现地址变换,这是它们的共同点;
b. 对于它们的不同点有三,第一,从功能上看,页是信息的物理单位,分页是为实现离散分配方式,以消减
---内存的外零头,提高内存的利用率,即满足系统管理的需要,而不是用户的需要;而段是信息的逻辑单位,
---它含有一组其意义相对完整的信息,目的是为了能更好地满足用户的需要;
c. 页的大小固定且由系统确定,而段的长度却不固定,决定于用户所编写的程序;
d. 分页的作业地址空间是一维的,而分段的作业地址空间是二维的
第5章设备管理
1:I/O设备类型
答:(1)按设备使用特性分类:存储设备和输入/输出设备。
(2)按传输速率分类:低速、中速和高速设备。
(3)按信息交换的单位分类:块设备和字符设备。
(4)按设备的共享属性分类:独占设备、共享设备和虚拟设备。
2:设备控制器的基本功能及组成。
答:功能:(1)接收和识别命令;(2)数据交换;(3)标识和报告设备的状态;(4)地址识别;(5)数据缓冲;(6)差错控制。
组成:(1)设备控制器与处理机的接口;(2)设备控制器与设备的接口;(3)I/O逻辑。
3:I/O通道的类型。
答:(1)字节多路通道(2)数组选择通道(3)数组多路通道。
4:总线:8位ISA和32位EISA总线;局部总线:VESA(Pentium微机)和64位PCI总线。
5:I/O控制方式:(1)程序控制方式;(2)中断驱动I/O控制方式;(3)直接存储器访问DMA I/O控制方式;(4)I/O通道控制方式。
6:引入缓冲的原因
答:(1)缓和CPU与I/O设备间速度的不匹配;(2)较少对CPU的中断频率,放宽对CPU中断响应时间的限制;(3)提高CPU与I/O之间的并行性。
7:I/O软件应该达到的目标
答:(1)与具体设备无关(2)统一命名(3)对错误的处理(4)缓冲技术(5)设备的分配与释放(6)I/O控制方式。
8:I/O软件的层次式结构
答:(1)用户软件(2)设备独立性软件(3)设备驱动程序(4)中断处理程序。再下就是硬件
9:I/O中断处理过程
答:(1)唤醒被阻塞的驱动(程序)进程;(2)保护被中断进程的CPU环境;(3)转入相应的设备处理程序;(4)中断处理;(5)恢复被中断进程的现场。
10:设备驱动程序的特点
答:(1)驱动程序主要是指在请求I/O的进程和设备控制器之间的一个通信和转换过程;(2)驱动程序与设备控制器和I/O设备的硬件特性紧密相关;(3)驱动程序与I/O设备所采用的I/O控制方式紧密相关;(4)由于驱动程序和硬件紧密相关,因而其中的一部分必须用汇编语言书写;(5)驱动程序应允许可重写。
11:设备驱动器的处理过程
答:(1)将抽象要求转化为具体要求;(2)检查I/O请求的合法性;(3)读出和检查设备的状态;(4)转送必要的参数;(5)工作方式的设置;(6)启动I/O设备。
……设备分配……
1:设备控制表COCT、通道控制表CHCT和系统设备表SDT。
2:设备的固有属性:独自性、共享性和可虚拟设备。
3:设备分配的算法:先来先服务和优先级高者优先。
4:设备分配步骤:分配设备、分配控制器、分配通道。
5:磁盘调度算法。
答:(1)先来先服务FCFS;
(2)最短寻道时间优先SSTF;
(3)扫描算法SCAN;(里外里…)考虑到欲访问的磁道与当前磁道间的距离,更优先考虑的是磁头当前的移动方向。
(4)循环扫描算法CSCAN(里外再里外…)获得了较好的寻道性能又能防止“饥饿”现象;
(5)NStepSCA和NFSCAN调度算法;防止“磁臂粘着”现象。
NStepSCA:分成长度为N的子队列,队列间按FCFS,队列按SCAN。
NFSCAN:上面N=2;
第6章文件管理
1:数据组分为:数据项、记录和文件。
2:文件类型:
按用途:系统、用户和库文件。
按文件中数据形式:源、目标和可执行。
按存取控制:只执行、只读和读写文件。
按组织形式和处理方式:普通、目录和特殊文件。
3:文件结构的逻辑类型。
答:(1)有结构文件
a定长记录b变长记录
(顺序文件-定长记录、索引文件和索引顺序文件)
(2)无结构文件-流式文件。
4:文件连续分配方式优缺点。
答:优点:顺序访问容易、速度块;缺点:要求有连续的存储空间、必须事先知道文件的长度。
5:链接方式:隐式和显式链接。
1. 分别就数据项、记录和文件的概念进行解释。
数据项可分为基本数据项和组合数据项。基本数据项是用于描述一个对象某种属性的字符集,是数据组织中可以命名的最小逻辑数据单位,又称为原子数据、数据元素或字段,其 具有数据名、数据类型及数据值三个特性。组合数据项则由若干数据项构成。记录是一组相关数据项的集合,用于描述一个对象某方面的属性。文件是具有文件名的一组相关信息的集合。
2. 按文件的物理结构,可将文件分为哪几类
按文件的物理结构,可将文件分为三类:(1)顺序文件,指把逻辑文件中的记录顺序地存储到连续的物理盘块中;(2)链接文件,指文件中的各个记录可以存放在不相邻的各个 物理块中,但通过物理块中的链接指针,将它们链接成一个链表;(3)索引文件,指文件中的各个记录可以存放在不相邻的各个物理块中,但通过为每个文件建立一张索引表来实 现记录和物理块之间的映射关系。
3. 文件系统的模型可分为三层,试说明其每一层所包含的基本内容。
答: 文件系统模型如图所示:
(1)最低层为对象及其属性说明,主要包括文件、目录、磁盘存储空间等三类对象。(2)最高层是文件系统提供给用户的接口,分为命令接口、程序接口和图形化用户接口等三 种类型。(3)中间层是对对象进行操纵和管理的软件集合,是文件系统的核心部分,拥有文件存储空间管理、文件目录管理、地址映射、文件读写管理及文件共享与保护等诸多功 能。具体又可分为四个子层:①I/O控制层(又称为设备驱动程序层),主要由磁盘驱动程序和磁带驱动程序组成,负责启动I/O设备和对设备发来的中断信号进行处理;②基本文 件系统层(又称为物理I/O层),主要用于处理内存与磁盘或磁带机系统之间数据块的交换,通过向I/O控制层发送通用指令及读写的物理盘块号与缓冲区号等I/O参数来完成;③基 本I/O管理程序层(即文件组织模块层),负责完成与磁盘I/O有关的大量事务,包括文件所在设备的选定、文件逻辑块号到物理块号的转换、空闲盘块的管理及I/O缓冲的指定等; ④逻辑文件系统层,负责所读写的文件逻辑块号的确定、目录项的创建与修改、文件与记录的保护等。
文件系统接口
对对象操纵和管理的软件集合 逻辑文件系统
基本I/O管理程序(文件组织模块)
基本文件系统(物理I/O层)
I/O控制层(设备驱动程序)
对象及其属性说明
4. 对于一个较完善的文件系统,应具备哪些功能
对于一个较完善的文件系统,应具备一系列的功能,包括对文件存储空间的管理、目录管理、文件的读写管理以及文件的共享与保护等。其中,有些功能对用户是透明的,就呈现 在用户面前的功能来说,可通过用户对文件所能施加的操作来表现。对文件的操作可分为两大类:一类是对文件自身的操作,包括文件的创建、删除、读、写、截断及文件读/写位 置的设置;一类是对记录的操作,包括记录的遍历(即检索所有记录)、单个记录的检索以及记录的插入、修改和删除。
5. 什么是文件的逻辑结构什么是文件的物理结构
文件的逻辑结构是指从用户的观点出发所观察到的文件组织形式,也就是用户可以直接处理的数据及其结构,它独立于物理特性;而文件的物理结构则是指文件在外存上的存储组 织形式,与存储介质的存储性能有关。
6. 你认为内存管理和外存管理有哪些相同点和不同点
内存管理和外存管理均追求存储空间利用率的提高,都具有存储空间的分配与回收、地址映射、共享与保护等功能。但二者的目的和任务不同,因而技术侧重点也有所不同。具体 而言,内存管理着眼于为多道程序的运行提供良好的环境,以进程作为分配对象,并要求能从逻辑上扩充内存;而外存管理则着眼于为每个文件分配必要的外存空间,并能有助于 提高文件系统的工作速度特别是文件的访问速度。
7. 如何提高对变长记录顺序文件的检索速度
为了提高对变长记录顺序文件的检索速度,可为其建立一张索引表,以主文件中每条记录的长度及指向对应记录的指针(即该记录在逻辑地址空间的首址)作为相应每个表项的内 容。由于索引表本身是一个定长记录的顺序文件,若将其按记录键排序,则可以实现对主文件的方便快速的直接存取。需要指出的是,如果文件较大,应通过建立分组多级索引以 进一步提高检索效率。
8. 试说明关于索引文件和索引顺序文件的检索方法。
答:①对索引文件进行检索时,首先根据用户(程序)提供的关键字,并利用折半查找法检索索引表,从中找到相应的表项;再利用该表项中给出的指向记录的指针值,去访问对 应的记录。②对索引顺序文件进行检索时,首先利用用户(程序)提供的关键字以及某种查找方法,去检索索引表,找到该记录所在记录组中的第一条记录的表项,从中得到该记 录组第一个记录在主文件中的位置;然后再利用顺序查找法去查找主文件,从而找到所要求的记录。
索引文件的检索:首先是根据用户(程序)提供的关键字,并利用折半查找法,去检索索引表,从中找到相应的项,再利用该表项中给出的指向记录的指针值,去访问所需的记录 。 索引顺序文件检索:首先利用用户(程序)提供的关键字以及某种查找方法,去检索索引表,找到该记录所在记录组中第一个记录的表项,从中得到该记录组第一个记 录在主文件中的位置;然后,再利用顺序查找法去查找主文件,从中找到所要求的记录。
9. 试从检索速度和存储费用两方面对索引文件和索引顺序文件进行比较。
假设主文件拥有N条记录。对于索引文件,主文件的每条记录均需配置一个索引项,故存储开销为N;而为检索到具有指定关键字的记录,平均需要查找N/2条记录。对于索引顺序文件,应为每个记录分组配置一个索引项,故存储开销为N1/2;而为检索到具有指定关键字的记录,平均需要查找N 1/ 2条记录。对于两级索引顺序文件,存储开销为N2/3+N1/3;而为检索到具有指定关键字的记录,平均需要查找3条记录。
10.目录管理主要有哪些要求
答:对文件目录的管理有以下要求:
a) 实现“按名存取”
b) 提高对目录的检索速度
c) 文件共享
d) 允许文件重名
11.采用单级目录能否满足目录管理的主要要求
采用单级目录只能实现目录管理的基本功能(即文件的按名存取),而对于其它三项要求则不能满足。
12.目前广泛采用的目录结构形式是什么它有什么优点
目前广泛采用的目录结构形式是树型目录结构,其具有检索效率高、允许重名、便于实现文件共享等一系列优点。
13.Hash检索法有何优点有何局限性
又称杂凑结构或散列结构。这种结构只适用于定长记录文件和按记录随机查找的访问方式。
Hash结构的思想是通过计算来确定一个记录在存储设备上的存储位置,依次先后存入的两个记录在物理设备上不一定相邻。按Hash结构组织文件的两个关键问题是:
定义一个杂凑函数;
解决冲突;
14.在Hash检索法中,如何解决“冲突”问题
15.解释关于树型目录结构采用线性检索法的检索过程。
假设用户给定的文件路径名为/Level1/Level2/…/Leveln/datafile,则关于树型目录结构采用线性检索法检索该文件的基本过程为:①读入第一个文件分量名Level1,用它与根目 录文件(或当前目录文件)中各个目录项的文件名顺序地进行比较,从中找出匹配者,并得到匹配项的索引结点号,再从对应索引结点中获知Level1目录文件所在的盘块号,将相 应盘块读入内存。②对于2~n,循环执行以下步骤,以检索各级目录文件:读入第i个文件分量名Leveli,用它与最新调入内存的当前目录文件中各个目录项的文件名顺序地进行比 较,从中找出匹配者,并得到匹配项的索引结点号,再从对应索引结点中获知Leveli目录文件所在的盘块号,将相应盘块读入内存。③读入最后一个文件分量名即datafile,用它 与第n级目录文件中各个目录项的文件名进行比较,从而得到该文件对应的索引结点号,进而找到该文件物理地址,目录查找操作成功结束。如果在上述查找过程中,发现任何一个 文件分量名未能找到,则停止查找并返回“文件未找到”的出错信息。
16.基于索引结点的共享方式有哪些优缺点
就基于索引结点的共享方式而言,其优点在于“建立新的共享链接,并不改变文件拥有者的关系,仅把索引结点共享计数器加1,所以系统可方便获悉由多少个目录项指向该文件” 。同时,该方式也存在所谓“悬空指针”的问题和缺点。具体而言,文件拥有者不能删除自己的文件,否则将留下指向该结点的悬空指针,造成该结点再分配时,系统出错;为此 ,拥有者只能清除自己的目录项,且要为其它共享者无端付费,直至其它共有者清除该文件
17.基于符号链的文件共享方式有哪些优缺点
就基于符号链的文件共享方式来说,只有文件主才拥有指向其索引结点的指针,而共享该文件的其它用户只有该文件的路径名且没有指向索引结点的指针,所以也就不会发生在文 件主删除共享文件后留下所谓“悬空指针”的问题。当文件拥有者把一个共享文件删除后,其它用户试图通过符号链来访问一个被删除的共享文件时将因系统找不到该文件而使访 问失败,于是将符号链删除,此时不会有任何其它负面效应。当然,这种方式也存在自己的问题。在其它用户访问共享文件时,系统是根据给定的文件路径名,逐个分量地去查找 目录,直至找到该文件的索引结点。因此,在访问共享文件时要多次读盘,使每次访问文件的系统开销加大,且增加了启动磁盘的频率。此外,要为每个共享用户建立一条符号链 ,而该链实际上是一个文件,尽管该文件非常简单,却仍需为之配置一个索引结点,故而也要消耗一定的磁盘空间。需要指出的是,本共享方式还有一个特殊的优点,即它能够用 于链接(通过计算机网络)世界上任何地方的机器中的文件,此时只需提供该文件所在机器的网络地址以及在该机器中的文件路径。
18.什么是保护域进程与保护域之间存在着什么动态联系
保护域规定了进程所能访问的一组(硬件或软件)对象以及相应的操作类型(即访问权)。进程与保护域之间的动态联系是指进程的可用资源集在其整个生命周期中是变化的;也 就是说,进程运行在不同的阶段时,需要从一个保护域切换到另外一个保护域。
19.如何利用拷贝权来扩散某种访问权
如果域i具有关于对象j的某访问权access(i,j)的拷贝权,则运行在域i的进程可将其关于对象j的访问权access(i,j)扩展到访问矩阵同一列中的其它域中,即为运行在其它域的进程也赋予关于同一对象的同样访问权限(access(k,j))。
20.如何利用拥有权来增、删某种访问权
如果域i具有关于对象j的所有权,则运行在域i的进程可以增加或删除在j列的任何项中的任何访问权。换言之,该进程可以增加或删除在任何其它域中运行的进程关于对象j的任何访问权。
21.增加控制权的主要目的是什么试举例说明控制权的应用。
拷贝权和所有权均用于改变运行在不同域中的进程对同一对象的访问权,而控制权则用于改变某个域中运行进程关于不同对象的访问权。进一步说,若某域访问权access(i,j)中含 有控制权C,则运行在Di域中的进程能改变运行在Qj域中的任何进程关于任何对象的任何访问权。
22.什么是访问控制表什么是访问权限表
针对访问矩阵按列(对象)进行划分,为每一列建立一张访问控制表,同时将访问矩阵属于对应列的所有空项删除,故而访问控制表由有序对集{<域,权集>}所组成,可用于描述 不同用户(进程)关于同一对象的不同访问权限集。针对访问矩阵按行(域)进行划分,为每一行建立一张访问权限表,其由有序对集{<对象,权集>}所组成。当域为用户(进程) ,对象为文件时,访问权限表便可用来描述一个用户(进程)对每一个文件所能执行的一组操作。访问控制表也可用于定义各域关于某对象的缺省的访问权集,并作为资源能否使用的首要依据。
23.系统如何利用访问控制表和访问权限表来实现对文件的保护(P252)
答:我们可利用访问矩阵来描述系统的存取控制,访问矩阵的行代表域,列代表对象,矩阵中的每一项是由一组访问权组成。
访问控制表:是指对访问矩阵列(对象)进行划分,为每一列建立一张访问控制表ACL。在该表中已经把矩阵总属于该列的所有空项删除,此时的访问控制表是由一有 序对(域,权集)所组成。系统中配置了这种表后,当某用户(进程)要访问某资源时,通常,系统首先到缺省访问控制表中去查找该用户(进程)是否具有对指定资源进行访问 的权力,如果找不到再到对应对象的访问控制表中去查找。
访问权限表:是指访问矩阵按行(即域)进行划分,由每一行构成一张访问权限表。这是一个由一个域对每一个对象可以执行的一组操作所构成的表。表中的每一项即 为该域对某一对象的访问权限。如UNIX系统中:
类型 权力 对象
文件 RW- 指向文件的指针
首先访问权限表必须是安全的,系统对其使用了特殊的保护。
目前,大多数的系统都同时采用访问控制表和访问权限表,在系统中为每个对象配置一张访问控制表。当一个进程第一次试图访问一个对象时,必须先检查访问控制表 ,检查进程是否具有对该对象的访问权,如果无权访问该对象,由系统来拒绝该进程的访问,并构成一例外(异常)事件;否则(有权访问)便允许该进程访问该对象而为之建立 一访问权限,并将它连接到该进程,以后进程便可直接利用这一返回的权限去访问该对象,这样便可快速地验证访问地合法性。当进程不再需要对该对象进行访问时,便可将访问 权限取消。
24.在对文件的四级安全管理中,每一级安全管理的主要用途是什么(P253)
答:文件的四级安全管理措施:
(1) 系统级管理:主要任务时部允许未经核准的用户进入系统,从而也就防止了他人非法地使用系统中地各类资源。主要地方法有注册、登录、时限等等。
(2) 用户级安全管理:是为了给用户分配“文件访问权”而设计的。包括对所有用户进行分类、为指定用户分配文件访问权等。
(3) 目录级安全管理:是为了保护系统中的各种目录而设计的,它与用户权限无关。为保证目录的安全,规定只有系统核心才具有写目录的权利。通常,系统是分别 为用户和目录独立地指定权限的。当一用户试图访问一目录时,核心将通过对用户访问权和目录中的访问权的比较后,用户才能获得有效的访问权。
(4) 文件级安全管理:是通过系统管理员或文件主对文件属性的设置,来控制用户对文件的访问。用户对文件的访问,将由用户访问权、目录访问权限和文件属性三 者的权限所确定。