通知
  • 关于网站更多信息请加QQ群(1061691290)
  • jpress升级到4.x,显示有些问题,修复中
  • 网站还会持续更新

23考研复试-操作系统知识点总结

447人浏览 / 0人评论 / | 作者:whisper  | 分类: 操作系统  | 标签: 操作系统  | 

作者:whisper

链接:https://www.proprogrammar.com/article/1057

声明:请尊重原作者的劳动,如需转载请注明出处


第一章 操作系统概述

1.1操作系统的概念、特征、功能和提供的服务

1.1.1操作系统的目标

1)方便性(用户的观点)

2)有效性(系统管理人员的观点)

3)可扩充性

4)开放性

1.1.2操作系统的作用

1.OS作为用户与计算机硬件系统之间的接口

2.OS作为计算机系统资源的管理者

硬件和软件资源分为四类:

处理机、存储器、I/O设备和文件(数据和程序)

3.OS实现了对计算机资源的抽象

1.1.3操作系统的基本特性

多道批处理系统、分时系统和实时系统

批处理系统有着高的资源利用率和系统吞吐量;

分时系统能获得及时响应;

实时系统具有实时特征。

共同具有并发、共享、虚拟和异步四个基本特征。

1并发(Concurrence)

1.并行与并发

2共享(Sharing)

1.互斥共享方式

2.同时访问方式

3 虚拟(Virtual)

  1. 时分复用技术
  2. (1) 虚拟处理机技术。
    (2) 虚拟设备技术。
  3. 空分复用技术
    (1)虚拟磁盘
    (2)虚拟主存

4 异步(Asynchronism)

1.1.4 操作系统的主要功能

引入OS的主要目的是,为多道程序的运行提供良好的运行环境,以保证多道程序能有条不紊地、高效地运行,并能最大程度地提高系统中各种资源的利用率,方便用户的使用。

处理机管理功能

  1. 进程控制
  2. 进程同步
  3. 进程通信
  4. 调度
    (1) 作业调度。
    (2) 进程调度。

存储器管理功能

1.内存分配

2.内存保护

3.地址映射

4.内存扩充

设备管理功能

设备管理应具有缓冲管理、设备分配和设备处理以及虚拟设备等功能。

文件管理功能

1.文件存储空间的管理

2.目录管理

3.文件的读/写管理和保护

操作系统与用户之间的接口

1.用户接口

(1)联机用户接口。

联机用户,命令接口和解释程序

(2)脱机用户接口。

脱机用户,作业控制语言

(3)图形用户接口。

  1. 程序接口

1.2 操作系统的发展过程

1.2.1 未配置操作系统的计算机系统

  1. 人工操作方式

1.2.2 单道批处理系统

1.2.3 多道批处理系统

1.2.4 分时系统(Time Sharing System)

1.2.5 实时系统(Real Time System)

硬实时任务和软实时任务

1.2.6 微机操作系统的发展

  1. 单用户单任务操作系统
  2. 单用户多任务操作系统
  3. 多用户多任务操作系统

1.3 操作系统的运行环境

  1. 系统态和用户态
  2. 中断、异常

所谓中断(interrupt)是指处理机对系统中或系统外发生的异步事件的响应。异步事件是指无一定时序关系的随机发生的事件,如外部设备完成了数据传输任务,某一实时控制设备出现情况等。

异常(有时也称为陷阱trap)是指由系统发起的一次确定的服务过程(有些地方也称为软中断)

  1. 系统调用

1.4 操作系统体系结构

1.4.1 传统操作系统结构

  1. 无结构操作系统
  2. 模块化结构OS3. 分层式结构OS

1.4.2 客户/服务器模式(Client/Server Model)

1.4.3 面向对象的程序设计技术简介

1.4.4微内核OS结构-现代结构OS

第二章 进程管理

2.1 进程与线程

2.1.1 进程概念

1、前趋图和程序执行

2、程序顺序执行

1)程序的顺序执行

2). 程序顺序执行时的特征

①顺序性

②封闭性

③可再现性

3程序并发执行

1). 程序的并发执行

2). 程序并发执行时的特征

(1) 间断性

(2) 失去封闭性

(3) 不可再现性

4 进程的描述

1). 进程的定义

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

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

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

2). 进程的特征

(1) 动态性

(2) 并发性

(3) 独立性

(4) 异步性

2.1.2 进程的基本状态及转换

(1) 就绪(Ready)状态。

(2) 执行(Running)状态。

(3) 阻塞(Block)状态。

image.png

  1. 创建状态和终止状态

1) 创建状态

2) 终止状态

image.png

  1. 挂起操作的引入

(1) 终端用户的需要。

(2) 父进程请求。

(3) 负荷调节的需要。

(4) 操作系统的需要。

image.png

2.1.3 进程组织

  1. 操作系统中用于管理控制的数据结构
  2. 进程控制块PCB的作用
  3. 进程控制块中的信息

1) 进程标识符

2) 处理机状态

3) 进程调度信息

4) 进程控制信息

  1. 进程控制块的组织方式

(1) 线性方式

(2) 链接方式

(3) 索引方式

2.1.4 进程控制

进程控制一般是由OS的内核中的原语来实现的

进程的创建

  1. 进程的层次结构
  2. 进程图

image.png

  1. 引起创建进程的事件

(1) 用户登录。

(2) 作业调度。

(3) 提供服务。

(4) 应用请求。

  1. 进程的创建(Creation of Process)

(1) 申请空白PCB,为新进程申请获得唯一的数字标识符,并从PCB集合中索取一个空白PCB。

(2) 为新进程分配其运行所需的资源,包括各种物理和逻辑资源,如内存、文件、I/O设备和CPU时间等。

(3) 初始化进程控制块(PCB)。

(4) 如果进程就绪队列能够接纳新进程,便将新进程插入就绪队列。

进程的终止

(1) 正常结束

(2) 异常结束

(3) 外界干预

  1. 进程的终止过程

(1) 根据被终止进程的标识符,从PCB集合中检索出该进程的PCB,从中读出该进程的状态;

(2) 若被终止进程正处于执行状态,应立即终止该进程的执行,并置调度标志为真,用于指示该进程被终止后应重新进行调度;

(3) 若该进程还有子孙进程,还应将其所有子孙进程也都予以终止,以防它们成为不可控的进程

(4) 将被终止进程所拥有的全部资源或者归还给其父进程,或者归还给系统;

(5) 将被终止进程(PCB)从所在队列(或链表)中移出,等待其它程序来搜集信息。

进程的阻塞与唤醒

  1. 引起进程阻塞和唤醒的事件

(1) 向系统请求共享资源失败。

(2) 等待某种操作的完成。

(3) 新数据尚未到达。

(4) 等待新任务的到达。

  1. 进程阻塞过程
  2. 进程唤醒过程

进程的挂起与激活

  1. 进程的激活过程

2.1.5 进程通信

进程通信是指进程之间的信息交换。由于进程的互斥与同步,需要在进程间交换一定的信息,故不少学者将它们也归为进程通信,但只能把它们称为低级进程通信。

1)进程通信的类型

  1. 共享存储器系统(Shared-Memory System)
  2. 管道(pipe)通信系统
  3. 消息传递系统(Message passing system)

基于消息传递系统的通信方式属于高级通信方式,因其实现方式的不同,可进一步分成两类:

(1) 直接通信方式

(2) 间接通信方式

基于共享中间实体

信箱通信

2.1.6 线程(Threads)的概念与多线程模型

1 )线程的引入

在OS中引入进程的目的是为了使多个程序能并发执行,以提高资源利用率和系统吞吐量,

引入线程,则是为了减少程序在并发执行时所付出的时空开销,使OS具有更好的并发性。

  1. 进程的两个基本属性

①进程是一个可拥有资源的独立单位

②进程同时又是一个可独立调度和分派的基本单位

  1. 程序并发执行所需付出的时空开销

(1) 创建进程

(2) 撤消进程

(3) 进程切换

  1. 线程——作为调度和分派的基本单位

2)线程与进程的比较

  1. 调度的基本单位进程内,切换代价低
  2. 并发性
  3. 拥有资源

线程控制块TCB

  1. 独立性
  2. 系统开销
  3. 支持多处理机系统

3 )线程的状态和线程控制块

  1. 线程运行的三个状态

(1) 执行状态,线程已获得处理机而正在运行;

(2) 就绪状态,已具备了各种执行条件,只须再获得CPU便可立即执行;

(3) 阻塞状态,在执行中因某事件受阻而处于暂停状态,例如,当一个线程执行从键盘读入数据的系统调用时,该线程就被阻塞。

  1. 线程控制块TCB

①线程标识符

②寄存器状态,它包括程序计数器PC 和堆栈指针中的内容;堆栈,在堆栈中通常保存有局部变量和返回地址;

③线程运行状态,用于描述线程正处于何种运行状态;

④优先级,描述线程执行的优先程度;

⑤线程专有存储器,用于保存线程自己的局部变量拷贝;

⑥信号屏蔽,即对某些信号加以屏蔽。

  1. 多线程OS中的进程属性

(1) 进程是一个可拥有资源的基本单位。

(2) 多个线程可并发执行。

(3) 进程已不是可执行的实体。

4)线程的实现方式

  1. 内核支持线程KST(Kernel Supported Threads)
  2. 用户级线程ULT(User Level Threads)
  3. 组合方式

有些OS把用户级线程和内核支持线程两种方式进行组合,提供了组合方式ULT/KST 线程。

image.png

5)线程的实现

1) 运行时系统(Runtime System)

2) 内核控制线程

6)线程的创建和终止

2.2进程同步

2.2.1进程同步的基本概念

  1. 两种形式的制约关系

1) 间接相互制约关系

又称为"互斥"

2) 直接相互制约关系

又称为"同步"

  1. 临界资源(Critical Resouce)

诸进程间应采取互斥方式,实现对这种资源的共享

生产者-消费者(producer-consumer)问题

  1. 临界区(critical section)

人们把在每个进程中访问临界资源的那段代码称为临界区(critical section)

  1. 同步机制应遵循的规则

(1) 空闲让进。

(2) 忙则等待。

(3) 有限等待。

(4) 让权等待。

2.2.2 实现临界区互斥的基本方法

(1)硬件同步机制

  1. 关中断
  2. 利用Test-and-Set指令实现互斥
  3. 利用Swap指令实现进程互斥

2.2.3 信号量机制

  1. 整型信号量
  2. 记录型信号量
  3. AND型信号量

信号量的应用

  1. 利用信号量实现进程互斥
  2. 利用信号量实现前趋关系

2.2.4管程

一个管程定义了一个数据结构和能为并发进程所执行的一组操作,这组操作能同步进程和改变管程中的数据(by Hansan)

①管程的名称;

②局部于管程的共享数据结构说明;

③对该数据结构进行操作的一组过程;

④对局部于管程的共享数据设置初始值的语句。

  1. 条件变量

在利用管程实现进程同步时,必须设置同步工具,如两个同步操作原语wait和signal

2.2.5经典进程的同步问题

“生产者—消费者”问题、“读者—写者问题”、“哲学家进餐问题”

2.3 处理器的调度

2.3.1 处理机调度的层次

  1. 高级调度(High Level Scheduling)
  2. 低级调度(Low Level Scheduling)
  3. 中级调度(Intermediate Scheduling)

高级调度(High Scheduling)

作业调度或长程调度(Long-Term Scheduling)

主要任务是按一定的原则对外存上处于后备状态的作业进行选择,给选中的作业分配内存、输入/输出设备等必要的资源,并建立相应的进程,放入就绪队列,以使该

作业的进程获得竞争处理机的权利

低级调度

进程调度或短程调度(Short-Term Scheduling)

主要任务是按照某种策略和方法选取一个处于就绪状态的进程,将处理机分配给它

常见的低级调度有非抢占式和抢占式两种

中级调度(Intermediate-Level Scheduling)

中程调度(Medium-Term Scheduling)

引入目的是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用

宝贵的内存资源,而将它们调至外存上去等待

2.3.2 处理机调度算法的目标

(1) 资源利用率

(2) 公平性

(3) 平衡性

(4) 策略强制执行

  1. 批处理系统的目标

(1) 平均周转时间短

(2) 系统吞吐量高

(3) 处理机利用率高

  1. 分时系统的目标

(1) 响应时间快。

(2) 均衡性。

  1. 实时系统的目标

(1) 截止时间的保证

(2) 可预测性

2.3.3 作业与作业调度

  1. 作业和作业步

(1) 作业(Job)。作业说明书,系统根据该说明书来对程序的运行进行控制。在批处理系统中,是以作业为基本单位从外存调入内存的

(2) 作业步(Job Step)。

编译-链接-运行

  1. 作业控制块(Job Control Block,JCB)

JCB包含:作业标识、用户名称、用户账号、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(预计运行时间、要求内存大小等)、资源使用情况等。

  1. 作业运行的三个阶段和三种状态

(1) 收容阶段。

(2) 运行阶段。

(3) 完成阶段。

作业调度的主要任务

调度算法

  1. 先来先服务(FCFS)调度算法
  2. 短作业优先(short job first,SJF)的调度算法
  3. 优先级调度算法(priority-scheduling algorithm,PSA)
  4. 高响应比优先调度算法(Highest Response Ratio Next,HRRN)

2.3.4 进 程 调 度

  1. 进程调度的任务

(1) 保存处理机的现场信息。

(2) 按某种算法选取进程。

(3) 把处理器分配给进程。

  1. 进程调度机制

(1) 排队器。

(2) 分派器。

(3) 上下文切换器。

  1. 进程调度方式

1) 非抢占方式(Nonpreemptive Mode)

2) 抢占方式(Preemptive Mode)

轮转调度算法

  1. 轮转法的基本原理
  2. 进程切换时机

优先级调度算法

  1. 优先级调度算法的类型

(1) 非抢占式优先级调度算法。

(2) 抢占式优先级调度算法。

  1. 优先级的类型

1) 静态优先级

2) 动态优先级

多级反馈队列调度算法

  1. 调度机制

(1) 设置多个就绪队列

image.png

(2) 每个队列都采用FCFS算法。

(3) 按队列优先级调度

  1. 调度算法的性能

在多级反馈队列调度算法中,如果规定第一个队列的时间片略大于多数人机交互所需

之处理时间时,便能较好地满足各种类型用户的需要。

(1) 终端型用户。

(2) 短批处理作业用户。

(3) 长批处理作业用户。

2.4 死锁

2.4.1 死锁概述

死锁例子

资源问题

在系统中有许多不同类型的资源,其中可以引起死锁的主要是,需要采用互斥访问方

法的、不可以被抢占的资源,即“临界资源”

  1. 可重用性资源和消耗性资源
  2. 可抢占性资源和不可抢占性资源

2.4.2 计算机系统中的死锁

  1. 竞争不可抢占性资源引起死锁
  2. 竞争可消耗资源引起死锁
  3. 进程推进顺序不当引起死锁

2.4.3 死锁的定义、必要条件和处理方法

  1. 死锁的定义

在一组进程发生死锁的情况下,这组死锁进程中的每一个进程,都在等待另一个死锁进程所占有的资源。

如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件,那么该组进程是死锁的

  1. 产生死锁的必要条件

(1) 互斥条件。

(2) 请求和保持条件。

(3) 不可抢占条件。

(4) 循环等待条件。

2.4.4 预防死锁

预防死锁的方法是通过破坏产生死锁的四个必要条件中的一个或几个,以避免发生死锁。

由于互斥条件是非共享设备所必须的,不仅不能改变,还应加以保证,因此主要是破坏产生死锁的后三个条件。

1) 破坏“请求和保持”条件

当一个进程在请求资源时,它不能持有不可抢占资源。

2) 破坏“不可抢占”条件

为了能破坏“不可抢占”条件,协议中规定,当一个已经保持了某些不可被抢占资源的进程,提出新的资源请求而不能得到满足时,它必须释放已经保持的所有资源,待以后需要时再重新申请。

3) 破坏“循环等待”条件

一个能保证“循环等待”条件不成立的方法是,对系统所有资源类型进行线性排序,并赋予不同的序号。

规定:所有进程申请资源必须按序号递增的顺序

当某进程占据了较高序号的资源,此后它继续申请的资源必定是空闲的

2.4.5 避免死锁

避免死锁同样是属于事先预防的策略,但并不是事先采取某种限制措施,破坏产生死锁必要条件

1) 系统安全状态

  1. 安全状态
  2. 由安全状态向不安全状态的转换

2) 利用银行家算法避免死锁

  1. 银行家算法中的数据结构

(1) 可利用资源向量Available

(2) 最大需求矩阵Max。

(3) 分配矩阵Allocation。

(4) 需求矩阵Need。

  1. 银行家算法
  2. 安全性算法

2.4.6 死锁的检测与解除

① 死锁检测算法。该方法用于检测系统状态,以确定系统中是否发生了死锁。

② 死锁解除算法。当认定系统中已发生了死锁,利用该算法可将系统从死锁状态中

解脱出来。

1) 死锁的检测

① 保存有关资源的请求和分配信息;

② 提供一种算法,它利用这些信息来检测系统是否已进入死锁状态。

  1. 资源分配图(Resource Allocation Graph)

2.死锁定理

2) 死锁的解除

  1. 终止进程的方法

1) 终止所有死锁进程

2) 逐个终止进程

第三章 内存管理

3.1 内存管理基础

3.1.1 内存管理概念

  1. 存储器的多层结构

存储层次至少应具有三级:

最高层为CPU寄存器,

中间为主存,

最底层是辅存。

在较高档的计算机中,还可以根据具体的功能细分为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。

  1. 可执行存储器

寄存器和主存储器称为可执行存储器。

对辅存的访问则需要通过I/O设备实现

在访问中将涉及到中断、设备驱动程序以及物理设备的运行,

所需耗费的时间远远高于访问可执行存储器的时间,一般相差3个数量级甚至更多。

主存储器简称内存或主存,是计算机系统中的主要部件,用于保存进程运行时的程序和数据,也称可执行存储器。

寄存器具有与处理机相同的速度,故对寄存器的访问速度最快,完全能与CPU协调工作,但价格却十分昂贵,因此容量不可能做得很大。

高速缓存和磁盘缓存

高速缓存是现代计算机结构中的一个重要部件,它是介于寄存器和存储器之间的存储器,主要用于备份主存中较常用的数据,以减少处理机对主存储器的访问次数,大幅度地提高程序执行速度。

高速缓存容量远大于寄存器,而比内存约小两到三个数量级左右,从几十KB到几MB,访问速度快于主存储器。

由于目前磁盘的I/O速度远低于对主存的访问速度,为了缓和两者之间在速度上的不匹配,而设置了磁盘缓存,主要用于暂时存放频繁使用的一部分磁盘数据和信息,以减少访问磁盘的次数。

但磁盘缓存与高速缓存不同,它本身并不是一种实际存在的存储器,而是利用主存中的部分存储空间暂时存放从磁盘中读出(或写入)的信息

主存也可以看作是辅存的高速缓存,

辅存中的数据必须复制到主存方能使用,反之,数据也必须先存在主存中,才能输出到辅存。

1)程序的装入和链接

用户程序要在系统中运行,必须先将它装入内存,然后再将其转变为一个可以执行的程序,通常都要经过以下步骤:

(1) 编译,由编译程序(Compiler)对用户源程序进行编译,形成若干个目标模块(Object Module);

(2) 链接,由链接程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起,形成一个完整的装入模块(Load Module);

(3) 装入,由装入程序(Loader)将装入模块装入内存。

image.png

程序的装入

一个无需进行链接的单个目标模块的装入过程该目标模块也就是装入模块。在将一个装入模块装入内存时,可以有如下三种装入方式:

  1. 绝对装入方式(Absolute Loading Mode)
  2. 可重定位装入方式(Relocation Loading Mode)
  3. 动态运行时的装入方式(Dynamic Run-time Loading)

程序的链接

  1. 静态链接(Static Linking)方式
  2. 装入时动态链接(Load-time Dynamic Linking)
  3. 运行时动态链接(Run-time Dynamic Linking)

3.1.2 交换与覆盖-对换(Swapping)

对换技术也称为交换技术,最早用于麻省理工学院的单用户分时系统CTSS中。

由于当时计算机的内存都非常小,为了使该系统能分时运行多个用户程序而引入了对换技术。

系统把所有的用户作业存放在磁盘上,每次只能调入一个作业进入内存,当该作业的一个时间片用完时,将它调至外存的后备队列上等待,再从后备队列上将另一个作业调入内存。

这就是最早出现的分时系统中所用的对换技术。现在已经很少使用。

  1. 对换的引入
  2. 对换的类型

(1) 整体对换。进程对换

(2) 页面(分段)对换。部分对换

对换空间的管理

进程的换出与换入

3.1.3 连续分配存储管理方式

1 单一连续分配

2 固定分区分配

  1. 划分分区的方法

(1) 分区大小相等(指所有的内存分区大小相等)

(2) 分区大小不等。

  1. 内存分配

3 动态分区分配

  1. 动态分区分配中的数据结构

① 空闲分区表

② 空闲分区链

  1. 动态分区分配算法

3 回收内存

当进程运行完毕释放内存时,系统根据回收区的首址,从空闲区链(表)中找到相应的插入点,此时可能出现以下四种情况之一:

(1) 回收区与插入点的前一个空闲分区F1相邻接图(a)。此时应将回收区与插入点的前一分区合并,不必为回收分区分配新表项,而只需修改其前一分区F1的大小。

(2) 回收分区与插入点的后一空闲分区F2相邻接,见图(b)。此时也可将两分区合并,形成新的空闲分区,但用回收区的首址作为新空闲区的首址,大小为两者之和。

(3) 回收区同时与插入点的前、后两个分区邻接,见图(c)。此时将三个分区合并,使用F1的表项和F1的首址,取消F2的表项,大小为三者之和。

(4) 回收区既不与F1邻接,又不与F2邻接。这时应为回收区单独建立一个新表项,填写回收区的首址和大小,并根据其首址插入到空闲链中的适当位置。

image.png

4 基于顺序搜索的动态分区分配算法

  1. 首次适应(first fit,FF)算法
  2. 循环首次适应(next fit,NF)算法
  3. 最佳适应(best fit,BF)算法
  4. 最坏适应(worst fit,WF)算法

5 动态可重定位分区分配

3.1.4 非连续分配管理方式

连续分配方式要求为一个进程分配连续的内存空间,会形成许多“碎片”(外部碎片),尽管采用“紧凑”技术可以解决这个问题,但要为移动大量信息花去不少的处理机时间,代价较高

如果允许一个进程直接分散地装入到许多不相邻接的分区中,称为离散分配方式

(1) 分页存储管理方式。

(2) 分段存储管理方式。

(3) 段页式存储管理方式。

1) 分页管理方式

页面和物理块

(1) 页面。

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

从0 开始编制页号,页内地址是相对于0 编址。

物理块:内存按页的大小划分为大小相等的区域,称为物理块(物理页面,页框

(frame),帧),同样加以编号,如0 #块、1#块等等

在为进程分配内存时,以块为单位将进程中的若干个页分别装入到多个可以不相邻接

的物理块中

由于进程的最后一页经常装不满一块而形成了不可利用的碎片,称之为“页内碎片”

(2) 页面大小。

页面的大小应选择的适中,且页面大小应是2 的幂,通常为512 B~8 KB

如果选择的页面较大

虽然可以减少页表的长度,提高页面换进换出的速度,但却又会使页内碎片增大。

页面若太小

虽然可使内存碎片减小,从而减少了内存碎片的总空间,有利于提高内存利用率,但

也会使每个进程占用较多的页面,从而导致进程的页表过长,占用大量内存;

此外,还会降低页面换进换出的效率

  1. 地址结构

分页地址中的地址结构如下:

image.png

  1. 页表

在分页系统中,允许将进程的各个页离散地存储在内存的任一物理块中,

为保证进程仍然能够正确地运行,即能在内存中找到每个页面所对应的物理块,

系统又为每个进程建立了一张页面映像表,简称页表。

列出了用户程序的逻辑地址与其在主存中的物理地址间的对应关系

一个页表中包含若干个表目,表目的自然序号对应于用户程序中的页号,表目中的块号是该页对应的物理块号。

页表的每一个表目除了包含指向页框的指针外,还包括一个存取控制字段。

image.png

页表的作用

地址变换机构

基本的地址变换机构

进程在运行期间,需要对程序和数据的地址进行变换,即将用户地址空间中的逻辑地址变换为内存空间中的物理地址,由于它执行的频率非常高,每条指令的地址都需要进行变换,因此需要采用硬件来实现。

页表功能是由一组专门的寄存器来实现的。一个页表项用一个寄存器。

页表大多驻留在内存中,在系统中设置页表寄存器PTR(Page – Table Register),在其中存放页表在内存中的始址和页表的长度

进程未执行时,页表的始址和页表长度存放在本进程的PCB中,当调度程序调度到某进程时,才将这两个数据装入页表寄存器

image.png

分页系统的地址变换机构

具有快表的地址变换机构

由于页表是存放在内存中的,这使CPU在每存取一个数据时,都要两次访问内存。

第一次是访问内存中的页表,从中找到指定页的物理块号,再将块号与页内偏移量W拼接,以形成物理地址。

第二次访问内存时,才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。

为提高地址变换速度,在地址变换机构中增设一个具有并行查询能力的高速缓冲寄存器,又称为“联想寄存器”

(Associative Memory)或“快表”,IBM系统又成为TLB,(Translation Look aside Buffer)用以存放当前访问的那些页表项

image.png

具有快表的地址变换机构

访问内存的有效时间

从进程发出指定逻辑地址的访问请求,经过地址变换,到在内存中找到对应的实际物理地址单元并取出数据,所需要花费的总时间,称为内存的有效访问时间(Effective Access Time,EAT)。

访问一次内存的时间为t,在基本分页存储管理方式中,有效访问时间分为第一次访问内存时间(即查找页表对应的页表项所耗费的时间t)与第二次访问内存时间(即将页表项中的物理块号与页内地址拼接成实际物理地址所耗费的时间t)之和:

EAT = t + t = 2t

在引入快表的分页存储管理方式中,通过快表查询,可以直接得到逻辑页所对应的物理块号,由此拼接形成实际物理地址,减少了一次内存访问,缩短了进程访问内存的有效时间。

由于快表的容量限制,不可能将一个进程的整个页表全部装入快表,所以在快表中查找到所需表项存在着命中率的问题。

命中率,是指使用快表并在其中成功查找到所需页面的表项的比率。

在引入快表的分页存储管理方式中,有效访问时间的计算公式即为:

image.png

image.png

两级和多级页表

两级页表(Two-Level Page Table)

现代计算机支持非常大的逻辑地址空间(2^32 ~2^64)。页表变得非常大,占用相当大的内存空间

对于一个具有32位逻辑地址空间的分页系统,若规定页面大小为4 KB即2^12 B,则在每个进程页表中的页表项可达1M(2^20)个之多。若每个表项占用4个字节(32bit),故每个进程仅仅其页表就要占用4 MB的内存空间,而且还要求是连续的.

针对难于找到大的连续的内存空间来存放页表的问题,可利用将页表进行分页的方法,使每个页面的大小与内存物理块的大小相同,

并为它们进行编号,即依次为0# 页、1# 页,…,n# 页,然后离散地将各个页面分别存放在不同的物理块中。

两级页表(Two-Level Page Table)

要为离散分配的页表再建立一张页表,称为外层页表(Outer Page Table),在每个页表项中记录了页表页面的物理块号。

image.png

两级页表结构

为了方便实现地址变换,在地址变换机构中,同样需要增设一个外层页表寄存器,用

于存放外层页表的始址,并利用逻辑地址中的外层页号作为外层页表的索引,从中找到指

定页表分页的始址,

利用P2 作为指定页表分页的索引,找到指定的页表项,其中即含有该页在内存的物

理块号,

该块号P 和页内地址d 即可构成访问的内存物理地址。

image.png

具有两级页表的地址变换机构

image.png

多级页表

对于32 位的机器,采用两级页表结构是合适的,但对于64 位的机器,采用两级页表

是否仍然合适,须做以下简单分析。

如果页面大小仍采用4 KB 即212 B,那么还剩下52 位,假定仍按物理块的大小(212

位)来划分页表,则将余下的42 位用于外层页号。

在外层页表中可能有4096 G个页表项,要占用16 384 GB的连续内存空间。

2)分段存储管理方式

存储管理方式随着OS的发展也在不断地发展。当OS由单道向多道发展时,存储管理方式便由单一连续分配发展为固定分区分配。

分段存储管理方式的引入

方便编程

通常,用户把自己的作业按照逻辑关系划分为若干个段,每个段都从0开始编址,并有自己的名字和长度。

程序员们需要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的,这不仅可以方便程序员编程,也可使程序非常直观,更具可读性。例如,下述的两条指令便使用段名和段内地址:

LOAD 1,[A] |〈D〉;

STORE 1,[B] |〈C〉;

信息共享

在实现对程序和数据的共享时,是以信息的逻辑单位为基础的。

为了共享某个过程、函数或文件。分页系统中的“页”只是存放信息的物理单位(块),并无完整的逻辑意义,这样,一个可被共享的过程往往可能需要占用数十个页面,这为实现共享增加了困难。

信息保护

信息保护同样是以信息的逻辑单位为基础的,而且经常是以一个过程、函数或文件为基本单位进行保护的。

动态增长

在实际应用中,往往存在着一些段,尤其是数据段,在它们的使用过程中,由于数据量的不断增加,而使数据段动态增长,相应地它所需要的存储空间也会动态增加。

对于数据段究竟会增长到多大,事先又很难确切地知道。对此,很难采取预先多分配的方法进行解决。

动态链接

为了提高内存的利用率,系统只将真正要运行的目标程序装入内存,也就是说,动态链接在作业运行之前,并不把所有的目标程序段都链接起来。

当程序要运行时,首先将主程序和它立即需要用到的目标程序装入内存,即启动运行。

在程序运行过程中,当需要调用某个目标程序时,才将该段(目标程序)调入内存并

进行链接。

分段系统的基本原理

分段

在分段存储管理方式中,作业的地址空间被划分为若干个段,每个段定义了一组逻辑

信息。

主程序段MAIN、子程序段X、数据段D 及栈段S 等

分段地址中的地址具有如下结构

image.png

段表

在前面所介绍的动态分区分配方式中,系统为整个进程分配一个连续的内存空间。

在分段式存储管理系统中,则是为每个分段分配一个连续的分区。

进程中的各个段,可以离散地装入内存中不同的分区中。

为保证程序能正常运行,就必须能从物理内存中找出每个逻辑段所对应的位置。

每个段在段表中占一个表项,其中记录了该段在内存中的起始地址(又称为“基址”)

和段的长度

image.png

利用段表实现地址映射

地址变换机构

为了实现进程从逻辑地址到物理地址的变换功能,在系统中设置了段表寄存器,用于存放段表始址和段表长度TL。

在进行地址变换时,系统将逻辑地址中的段号与段表长度TL进行比较。

若S>TL,表示段号太大,是访问越界,于是产生越界中断信号。

若未越界,则根据段表的始址和该段的段号,计算出该段对应段表项的位置,从中读出该段在内存的起始地址。

地址变换机构

再检查段内地址d是否超过该段的段长SL。

若超过,即d>SL,同样发出越界中断信号。

若未越界,则将该段的基址d与段内地址相加,即可得到要访问的内存物理地址

image.png

分页和分段的主要区别

(1) 页是信息的物理单位。分页是为实现离散分配方式,以消减内存的外零头,提高内存的利用率。或者说,分页仅仅是由于系统管理的需要而不是用户的需要。

段则是信息的逻辑单位,它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。

(2) 页的大小固定且由系统决定。由系统把逻辑地址划分为页号和页内地址两部分,是由机器硬件实现的,因而在系统中只能有一种大小的页面;

而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时,根据信息的性质来划分。

(3) 分页的用户程序地址空间是一维的。即单一的线性地址空间,程序员只需利用一个记忆符,即可表示一个地址;

分段的作业地址空间则是二维的,程序员在标识一个地址时,既需给出段名,又需给出段内地址。

3) 段页式存储管理方式

基本原理

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

图(a)示出了一个作业地址空间的结构。该作业有三个段:主程序段、子程序段和数据段;

页面大小为4 KB。在段页式系统中,其地址结构由段号、段内页号及页内地址三部分所组成,

image.png

在段页式系统中,为了实现从逻辑地址到物理地址的变换,系统中需要同时配置段表和页表。

段表的内容与分段系统略有不同,它不再是内存始址和段长,而是页表始址和页表长度。

image.png

地址变换过程

段页式系统中,为了便于实现地址变换,须配置一个段表寄存器,其中存放段表始址和段长TL。

进行地址变换时,首先利用段号S,将它与段长TL进行比较。

若S < TL,表示未越界,于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置,从中得到该段的页表始址,

得到该段的页表始址,利用逻辑地址中的段内页号P来获得对应页的页表项位置,从中读出该页所在的物理块号b,

再利用块号b和页内地址来构成物理地址

image.png

3.2 虚拟内存管理

3.2.1 虚拟存储器概述

基本存储器管理方式有一个共同的特点,即要求将一个作业全部装入内存后方能运行。

(1) 有的作业很大,其所要求的内存空间超过了内存总容量,作业不能全部被装入内存,致使该作业无法运行;

(2) 有大量作业要求运行,但由于内存容量不足以容纳所有这些作业,只能将少数作业装入内存让它们先运行,而将其它大量的作业留在外存上等待。

1)常规存储管理方式的特征和局部性原理

常规存储器管理方式的特征

把所介绍的各种存储器管理方式统称为传统存储器管理方式,具有两个共同的特征

(1) 一次性

(2) 驻留性

局部性原理

1968年,P.Denning指出:程序在执行时将呈现出局部性规律,即在一较短的时间内,程序的执行仅局限于某个部分,相应地,它所访问的存储空间也局限于某个区域。

局限性又表现在下述两个方面:

(1) 时间局限性

大量循环操作

(2) 空间局限性

程序的顺序执行,顺序存储

虚拟存储器的基本工作情况

基于局部性原理可知,应用程序在运行之前没有必要将之全部装入内存,

而仅须将那些当前要运行的少数页面或段先装入内存便可运行,其余部分暂留在盘上。

2)虚拟存储器的定义和特征

虚拟存储器的定义

所谓虚拟存储器,是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统。

逻辑容量由内存容量和外存容量之和所决定,

运行速度接近于内存速度,而每位的成本却又接近于外存

虚拟存储器的特征

具有三个重要特征:

(1) 多次性。

(2) 对换性。

(3) 虚拟性

虚拟性是以多次性和对换性为基础的

3)虚拟存储器的实现方法

分页请求系统

1) 硬件支持

主要的硬件支持有:

(1) 请求分页的页表机制。

(2) 缺页中断机构。

(3) 地址变换机构。

2) 实现请求分页的软件

3.2.2 请求分页管理方式

1) 请求分页中的硬件支持

为了实现请求分页,系统必须提供一定的硬件支持。

计算机系统除了要求一定容量的内存和外存外,还需要有请求页表机制、缺页中断机

构以及地址变换机构

请求页表机制

在请求分页系统中需要的主要数据结构是请求页表,其基本作用仍然是将用户地址空

间中的逻辑地址映射为内存空间中的物理地址。

为了满足页面换进换出的需要,在请求页表中又增加了四个字段。

image.png

缺页中断机构

(1) 在指令执行期间产生和处理中断信号。

(2) 一条指令在执行期间可能产生多次缺页中断

image.png

地址变换机构

请求分页系统中的地址变换机构是在分页系统地址变换机构的基础上,为实现虚拟存储器,再增加了某些功能所形成的,如产生和处理缺页中断,以及从内存中换出一页的功能等等。

image.png

3.2.3 页面置换算法

在进程运行过程中,若其所要访问的页面不在内存,而需把它们调入内存,但内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据送到磁盘的对换区中

但应调出哪个页面,根据一定的算法来确定。

把选择换出页面的算法称为页面置换算法(Page-Replacement Algorithms)。

置换算法的好坏将直接影响到系统的性能。

1) 最佳置换算法和先进先出置换算法

最佳(Optimal)置换算法

最佳置换算法是由Belady于1966年提出的一种理论上的算法。

所选择的被淘汰页面将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。

最佳置换算法通常可保证获得最低的缺页率。

由于人们目前还无法预知,一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法是无法实现的,但可以利用该算法去评价其它算法

image.png

先进先出(FIFO)页面置换算法

FIFO算法是最早出现的置换算法。

该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。

该算法实现简单,只需把一个进程已调入内存的页面按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。

image.png

2) 最近最久未使用和最少使用置换算法

LRU(Least Recently Used)置换算法

FIFO置换算法的性能之所以较差,是因为它所依据的条件是各个页面调入内存的时间,而页面调入的先后并不能反映页面的使用情况。

最近最久未使用(LRU)的页面置换算法是根据页面调入内存后的使用情况做出决策的。

由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU 置换算法是选择最近最久未使用的页面予以淘汰。

该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t,当须淘汰一个页面时,选择现有页面中其t 值最大的,即最近最久未使用的页面予以淘汰。

image.png

Clock置换算法

简单的Clock置换算法

当利用简单Clock算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列。

置换算法在选择一页淘汰时,只需检查页的访问位。如果是0,就选择该页换出;若为1,则重新将它置0,暂不换出,而给该页第二次驻留内存的机会,再按照FIFO 算法检查下一个页面。

image.png

由于该算法是循环地检查各页面的使用情况,故称为Clock 算法。

但因该算法只有一位访问位,只能用它表示该页是否已经使用过,而置换时是将未使用过的页面换出去,故又把该算法称为最近未用算法NRU(Not Recently Used)。

改进型Clock置换算法

在将一个页面换出时,如果该页已被修改过,便须将该页重新写回到磁盘上;但如果该页未被修改过,则不必将它拷回磁盘。

对于修改过的页面,在换出时所付出的开销比未修改过的页面大,或者说,置换代价大。在改进型Clock算法中,除须考虑页面的使用情况外,还须再增加一个因素——置换代价。

访问位A和修改位M可以组合成下面四种类型的页面:

1 类(A=0,M=0):表示该页最近既未被访问,又未被修改,是最佳淘汰页。

2 类(A=0,M=1):表示该页最近未被访问,但已被修改,并不是很好的淘汰页。

3 类(A=1,M=0):表示该页最近已被访问,但未被修改,该页有可能再被访问。

4 类(A=1,M=1):表示该页最近已被访问且被修改,该页可能再被访问。

(1) 从指针所指示的当前位置开始,扫描循环队列,寻找A=0 且M=0的第一类页面,将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。

(2) 如果第一步失败,即查找一周后未遇到第一类页面,则开始第二轮扫描,寻找A=0且M=1的第二类页面,将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间,将所有扫描过的页面的访问位都置0。

(3) 如果第二步也失败,亦即未找到第二类页面,则将指针返回到开始的位置,并将所有的访问位复0。然后重复第一步,如果仍失败,必要时再重复第二步,此时就一定能找到被淘汰的页。

该算法与简单Clock算法比较,可减少磁盘的I/O 操作次数。实现该算法本身的开销将有所增加。

3.2.4 页面分配策略

最小物理块数的确定

最小物理块数,是指能保证进程正常运行所需的最小物理块数。

当系统为进程分配的物理块数少于此值时,进程将无法运行。

进程应获得的最少物理块数与计算机的硬件结构有关,取决于指令的格式、功能和寻址方式

内存分配策略

两种内存分配策略,即固定和可变分配策略。

两种置换策略,即全局置换和局部置换。

可组合出以下三种适用的策略。

1) 固定分配局部置换(Fixed Allocation,Local Replacement)

2) 可变分配全局置换(Variable Allocation,Global Replacement)

3) 可变分配局部置换(Variable Allocation,Local Replacement)

物理块分配算法

采用固定分配策略时,如何将系统中可供分配的所有物理块分配给各个进程,可采用下述算法:

(1) 平均分配算法,即将系统中所有可供分配的物理块平均分配给各个进程。

(2) 按比例分配算法,即根据进程的大小按比例分配物理块。

(3) 考虑优先权的分配算法。

在实际应用中,为了照顾到重要的、紧迫的作业能尽快地完成,应为它分配较多的内存空间。

通常采取的方法是把内存中可供分配的所有物理块分成两部分:

一部分按比例地分配给各进程;

另一部分则根据各进程的优先权进行分配,为高优先进程适当地增加其相应份额。

重要的实时控制系统,采用完全按优先权分配

3.2.5 “抖动”与工作集

由于请求分页式虚拟存储器系统的性能优越,在正常运行情况下,它能有效地减少内存碎片,提高处理机的利用率和吞吐量,故是目前最常用的一种系统。

但如果在系统中运行的进程太多,进程在运行中会频繁地发生缺页情况,这又会对系统的性能产生很大的影响,故还须对请求分页系统的性能做简单的分析。

1) 多道程序度与“抖动”

发生“抖动”的根本原因是,同时在系统中运行的进程太多,由此分配给每一个进程的物理块太少,不能满足进程正常运行的基本要求,致使每个进程在运行时,频繁地出现缺页,必须请求系统将所缺之页调入内存

使得在系统中排队等待页面调进/调出的进程数目增加。对磁盘的有效访问时间也随之急剧增加

造成每个进程的大部分时间都用于页面的换进/换出,而几乎不能再去做任何有效的工作,从而导致发生处理机的利用率急剧下降并趋于0的情况

此时的进程是处于“抖动”状态。

2 ) 工作集

工作集的基本概念

所谓工作集,是指在某段时间间隔Δ里,进程实际所要访问页面的集合。

Denning指出,虽然程序只需要少量的几页在内存便可运行,但为了较少地产生缺页,应将程序的全部工作集装入内存中。

无法事先预知程序在不同时刻将访问哪些页面,故仍只有像置换算法那样,用程序的过去某段时间内的行为作为程序在将来某段时间内行为的近似。

3) “抖动”的预防方法

采取局部置换策略

在页面分配和置换策略中,如果采取的是可变分配方式,则为了预防发生“抖动”,可采取局部置换策略。

把工作集算法融入到处理机调度中

当调度程序发现处理机利用率低下时,它将试图从外存调入一个新作业进入内存,来改善处理机的利用率。

利用“L=S”准则调节缺页率

Denning于1980年提出了“L=S”的准则来调节多道程序度,

L是缺页之间的平均时间,

S是平均缺页服务时间,即用于置换一个页面所需的时间。

如果是L远比S大,说明很少发生缺页,磁盘的能力尚未得到充分的利用;

如果是L比S小,则说明频繁发生缺页,缺页的速度已超过磁盘的处理能力。

只有当L与S接近时,磁盘和处理机都可达到它们的最大利用率。

理论和实践都已证明,利用“L=S”准则,对于调节缺页率是十分有效的

选择暂停的进程

当多道程序度偏高时,已影响到处理机的利用率,为了防止发生“抖动”,系统必须减少多道程序的数目。

第四章 文件管理

4.1 文件基础

文件系统的管理功能是将其管理的程序和数据通过组织为一系列文件的方式实现的。
文件则是指具有文件名的若干相关元素的集合。
元素通常是记录,记录又是一组有意义的数据项的集合。
基于文件系统的概念,可以把数据组成分为数据项、记录和文件三级。

4.1.1 文件的概念

  1. 数据项

(1) 基本数据项。

(2) 组合数据项

  1. 记录

  2. 文件

有结构文件和无结构文件两种

文件属性:文件类型,文件长度,文件的物理位置,文件建立时间(修改时间)等。

文件名和类型

文件名和扩展名

(1) 文件名。
(2) 扩展名。

文件系统的层次结构

文件系统模型分为三个层次:最底层是对象及其属性,中间层是对对象进行操纵和管理的软件集合,最高层是文件系统提供给用户的接口。

image.png

对象及其属性

文件管理系统管理的对象如下:

(1) 文件。
(2) 目录。在目录中除包含文件名外,还包括对文件属性的说明。
(3) 磁盘(磁带)存储空间。

对对象操纵和管理的软件集合

该层是文件管理系统的核心部分

① 对文件存储空间的管理;
② 对文件目录的管理;
③ 用于将文件的逻辑地址转换为物理地址的机制;
④ 对文件读和写的管理;
⑤ 对文件的共享与保护等功能。

采取了层次组织结构,即在每一层中都包含了一定的功能,处于某个层次的软件,只能调用同层或更低层次中的功能模块。

(1)I/O控制层。最低层,主要由磁盘驱动程序和磁带驱动程序组成,故该层又称为设备驱动程序层

(2)基本文件系统。物理I/O层。该层用于处理内存与磁盘或磁带机系统之间数据块的交换

(3)基本I/O管理程序。文件组织模块。这一层次完成与磁盘I/O有关的大量事务。

(4)逻辑文件系统。基本文件系统所处理的数据块的交换,逻辑文件系统所处理的则是文件和记录相关操作。

文件系统的接口

为方便用户的使用,文件系统以接口的形式提供了一组对文件和记录操作的方法和手段。

通常是下面两种类型的接口:

(1) 命令接口,是指作为用户与文件系统直接交互的接口,用户可通过键盘终端键入命令取得文件系统的服务。
(2) 程序接口,是指作为用户程序与文件系统的接口,用户程序可通过系统调用取得文件系统的服务,例如,用于创建文件的系统调用Creat,用于打开一个文件的系统调用Open等。

文件操作

最基本的文件操作

最基本的文件操作包含下述内容:

(1) 创建文件。
(2) 删除文件。
(3)读文件:
(4)写文件:

文件的“打开”和“关闭”操作

当用户要求对一个文件实施多次读/写或其它操作时,每次都要从检索目录开始。
为了避免多次重复地检索目录,在大多数OS中都引入了“打开”(open)这一文件系统调用,当用户第一次请求对某文件进行操作时,须先利用open系统调用将该文件打开。
“关闭”(CLOSE)系统调用来关闭此文件,OS将会把该文件从打开文件表中的表目上删除掉

4.1.2 文件的逻辑结构

(1) 文件的逻辑结构(File Logical Structure)

用户角度,文件是逻辑记录的组成,是用户可以直接处理的数据机器结构,独立于物理特性,称为文件组织。

(2) 文件的物理结构,又称为文件的存储结构。

系统角度,外存的组织形式,与所采用的外存分配方式有关

按文件是否有结构分类

1) 有结构文件

(1) 定长记录。
(2) 变长记录。

大量的信息管理系统和数据库系统中,广泛采用了有结构的文件形式(即文件是由定长或变长记录构成的)

2) 无结构文件

在系统中运行的大量的源程序、可执行文件、库函数等,所采用的就是无结构的文件形式,即流式文件。文件的长度是以字节为单位的。
对流式文件的访问,则是利用读、写指针来指出下一个要访问的字符。
可以把流式文件看做是记录式文件的一个特例一个记录仅有一个字节。

按文件的组织方式分类

(1) 顺序文件。由一系列记录按某种顺序排列所形成的文件,其中的记录通常是定长记录。
(2) 索引文件。当记录为变长记录时,通常为之建立一张索引表,并为每个记录设置一张表项,以加快对记录的检索速度。
(3) 索引顺序文件。上述2种文件的一个结合,为文件建立一张索引表,为每一组记录中的第一个记录设置一个表项。

一级索引顺序文件

两级索引顺序文件

直接文件

哈希(Hash)文件

4.1.3 目录结构

(1) 实现“按名存取”。
(2) 提高对目录的检索速度。
(3) 文件共享。
(4) 允许文件重名

文件控制块和索引结点

文件控制块FCB(File Control Block)

基本信息
存取控制信息
使用信息

1) 基本信息类

基本信息类包括:

(1) 文件名。
(2) 文件物理位置。
(3) 文件逻辑结构。
(4) 文件的物理结构。

2) 存取控制信息类

存取控制信息类包括文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。

3) 使用信息类

使用信息类包括文件的建立日期和时间、文件上一次修改的日期和时间,以及当前使用信息。
包括当前已打开该文件的进程数,是否被其它进程锁住,文件在内存中是否已被修改但尚未拷贝到盘上等。

索引结点

1) 索引结点的引入

把文件名与文件描述信息分开的办法,亦即,使文件描述信息单独形成一个称为索引结点的数据结构

在文件目录中的每个目录项仅由文件名和指向该文件所对应的结点的指针所构成

2) 磁盘索引结点

这是存放在磁盘上的索引结点。每个文件有唯一的一个磁盘索引结点,它主要包括以下内容:

(1) 文件主标识符,即拥有该文件的个人或小组的标识符;
(2) 文件类型,包括正规文件、目录文件或特别文件;
(3) 文件存取权限,指各类用户对该文件的存取权限;
(4) 文件物理地址,每一个索引结点中含有13个地址项,
即iaddr(0)~iaddr(12),它们以直接或间接方式给出数据文件所在盘块的编号;
(5) 文件长度,指以字节为单位的文件长度;
(6) 文件连接计数,表明在本文件系统中所有指向该(文件的)文件名的指针计数;
(7) 文件存取时间,指出本文件最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间。

3) 内存索引结点

这是存放在内存中的索引结点。
当文件被打开时,要将磁盘索引结点拷贝到内存的索引结点中,便于以后使用。增加以下内容

(1) 索引结点编号,用于标识内存索引结点;
(2) 状态,指示i结点是否上锁或被修改;
(3) 访问计数,每当有一进程要访问此i结点时,将该访问计数加1,访问完再减1;
(4) 文件所属文件系统的逻辑设备号;
(5) 链接指针,设置有分别指向空闲链表和散列队列的指针。

简单的文件目录

单级文件目录

两级文件目录

树形结构目录(Tree-Structured Directory)

树形目录

主目录在这里被称为根目录,在每个文件目录中,只能有一个根目录,每个文件和每个目录都只能有一个父目录。
把数据文件称为树叶,其它的目录均作为树的结点,或称为子目录。

image.png

多级目录结构

路径名和当前目录

1) 路径名(path name)

2) 当前目录(Current Directory)

可为每个进程设置一个“当前目录”,又称为“工作目录”。文件访问都相对于“当前目录”
各文件所使用的路径名,只需从当前目录开始,逐级经过中间的目录文件,最后到达要访问的数据文件(相对路径)。

目录操作

(1) 创建目录。
(2) 删除目录。
① 不删除非空目录。
② 可删除非空目录。
(3) 改变目录。
(4) 移动目录。
(5) 链接(Link)操作。
(6) 查找。

目录查询技术

线性检索法

线性检索法又称为顺序检索法。
在单级目录中,利用用户提供的文件名,用顺序查找法直接从文件目录中找到指名文件的目录项。
在树形目录中,用户提供的文件名是由多个文件分量名组成的路径名,此时需对多级目录进行查找。
假定用户给定的文件路径名是 /usr/ast/mbox,则查找 /usr/ast/mbox文件的过程。

image.png

4.1.4 文件共享

文件共享手段,即指系统应允许多个用户(进程)共享同一份文件。
在系统中只需保留该共享文件的一份副本。
如果系统不能提供文件共享功能,就意味着凡是需要该文件的用户,都须各自备有此文件的副本,显然这会造成对存储空间的极大浪费。

基于有向无循环图实现文件共享

利用索引结点

为了解决这个问题,可以引用索引结点

image.png

image.png

利用符号链接实现文件共享

利用符号链接(Symbolic Linking)的基本思想

允许一个文件或子目录有多个父目录,但其中仅有一个作为主(属主)父目录,其它的几个父目录都是通过符号链接方式与之相链接的(简称链接父目录)

image.png

4.1.5 文件保护

影响文件安全性的主要因素有

(1) 人为因素。
(2) 系统因素。
(3) 自然因素。

为了确保文件系统的安全性,可针对上述原因而采取三方面的措施:

(1) 通过存取控制机制,防止由人为因素所造成的文件不安全性。
(2) 采取系统容错技术,防止系统部分的故障所造成的文件的不安全性。
(3) 建立后备系统,防止由自然因素所造成的不安全性。

保护域(Protection Domain)

访问权

把一个进程能对某对象执行操作的权力,称为访问权(Access right)

保护域

为了对系统中的资源进行保护而引入了保护域的概念,保护域简称为“域”。“域”是进程对一组对象访问权的集合,进程只能在指定域内执行操作。
“域”也就规定了进程所能访问的对象和能执行的操作。

访问矩阵

基本的访问矩阵

image.png

访问矩阵的实现

访问控制表(Access Control List)

这是指对访问矩阵按列(对象)划分,为每一列建立一张访问控制表ACL。

访问权限(Capabilities)表

4.2 文件系统的实现

文件的物理结构直接与外存的组织方式有关。对于不同的外存组织方式,将形成不同的文件物理结构

常用的外存组织方式有

(1) 连续组织方式。
(2) 链接组织方式。
(3) 索引组织方式。

连续组织方式

image.png

链接组织方式

隐式链接

显式链接

image.png

FAT技术引入卷的概念

FAT12

早期的FAT12文件系统

FAT12是以盘块为基本分配单位的。
由于FAT是文件系统中最重要的数据结构,为了安全起见,在每个分区中都配有两张相同的文件分配表FAT1和FAT2。
在FAT的每个表项中存放下一个盘块号,它实际上是用于盘块之间的链接的指针,
通过它可以将一个文件的所有的盘块链接起来
将文件的第一个盘块号放在自己的FCB中

image.png

以簇为单位的FAT12文件系统

如果把每个盘块(扇区)的容量增大n倍,则磁盘的最大容量便可增加n倍

但要增加盘块的容量是不方便和不灵活的。为此,引入了簇(cluster)的概念。
簇是一组相邻的扇区,盘块分配以簇为单位,一般为2n个盘块,即1个扇区(512B),2个扇区(1KB),4个扇区(2KB)

FAT16

FAT12对磁盘容量限制的原因在于,FAT12表中的表项有限制,亦即最多只允许4096个。
随着磁盘容量的增加,必定会引起簇的大小和簇内碎片也随之增加。

FAT32

由于FAT16表的长度只有65 535项,随着磁盘容量的增加,簇的大小也必然会随之增加,为了减少簇内零,也就应当增加FAT表的长度,
为此需要再增加FAT表的宽度,这样也就由FAT16演变为FAT32

索引组织方式

单级索引组织方式

image.png

多级索引组织方式

image.png

两级索引分配

增量式索引组织方式

1) 增量式索引组织方式的基本思想
为了能较全面地照顾到小、中、大及特大型作业,可以采取多种组织方式来构成文件的物理结构

如果盘块的大小为1 KB或4 KB,对于小文件(如1 KB~10 KB或4 KB~40 KB)而言,最多只会占用10个盘块,为了能提高对数量众多的小型作业的访问速度,最好能将它们的每一个盘块地址都直接放入文件控制块FCB(或索引结点)中,这样就可以直接从FCB中获得该文件的盘块地址。

此寻址方式成为直接寻址
对于中等文件,可以采用单级索引组织方式,从FCB中获取该文件的索引表,称为一次间址
对于大型文件,可以采用二级和三级索引组织方式,称为二级间址,三级间址

包含其上方式,称为混合组织方式

文件存储空间的管理

空闲表法

1) 空闲表

空闲表法属于连续分配方式,它与内存的动态分配方式雷同,它为每个文件分配一块连续的存储空间。
即系统也为外存上的所有空闲区建立一张空闲表,每个空闲区对应于一个空闲表项,其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。
再将所有空闲区按其起始盘块号递增的次序排列,形成空闲盘块表。

image.png

空闲链表法

空闲盘块链

这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外,还应有能指明本盘区大小(盘块数)的信息。

位示图

利用二进制的一位来表示磁盘中一个盘块的使用情况。
当其值为“0”时,表示对应的盘块空闲;为“1”时,表示已分配。
有的系统把“0”作为盘块已分配的标志,把“1”作为空闲标志。(在本质上是相同的,都是用一位的两种状态来标志空闲和已分配两种情况。)
磁盘上的所有盘块都有一个二进制位与之对应
由所有盘块所对应的位构成一个集合,称为位示图。

image.png

成组链接法

空闲盘块的组织

空闲盘块号栈,用来存放当前可用的一组空闲盘块的盘块号(最多含100个号),以及栈中尚有的空闲盘块(号)数N

image.png

4.3 磁盘的组织和管理

4.3.1 磁盘的结构

磁盘设备是一种相当复杂的机电设备,在此仅对磁盘的某些性能,如数据的组织、磁盘的类型和访问时间等方面做扼要的阐述

数据的组织和格式

磁盘设备可包括一个或多个物理盘片,每个磁盘片分一个或两个存储面(Surface),
每个盘面上有若干个磁道(Track),磁道之间留有必要的间隙(Gap)。
为使处理简单起见,在每条磁道上可存储相同数目的二进制位。

image.png

磁盘的类型

硬盘和软盘、单片盘和多片盘、固定头磁盘和活动头(移动头)磁盘等。

下面仅对固定头磁盘和移动头磁盘做些介绍

(1) 固定头磁盘。
(2) 移动头磁盘

磁盘访问时间

1) 寻道时间Ts

2) 旋转延迟时间Tr

3) 传输时间Tt

4.3.2 磁盘调度算法

先来先服务(FCFS)

image.png

最短寻道时间优先(SSTF)

image.png

扫描(SCAN)算法

image.png

循环扫描(CSCAN)算法

image.png

NStepSCAN和FSCAN调度算法

NStepSCAN算法

FSCAN算法

4.3.3 磁盘的管理

(1) 改进文件的目录结构以及检索目录的方法来减少对目录的查找时间;
(2) 选取好的文件存储结构,以提高对文件的访问速度;
(3) 提高磁盘的I/O速度,能将文件中的数据快速地从磁盘传送到内存中,或者相反

磁盘高速缓存(Disk Cache)

提高磁盘I/O速度的其它方法

提前读

延迟写

优化物理块的分布

廉价磁盘冗余阵列(RAID)

并行交叉存取

这是把在大、中型机中,用于提高访问内存速度的并行交叉存取技术应用到磁盘存储系统中,以提高对磁盘的I/O 速度。在该系统中,有多台磁盘驱动器,系统将每一盘块中的数据分为若干个子盘块数据,再把每一个子盘块的数据分别存储到各个不同磁盘中的相同位置上。以后当要将一个盘块的数据传送到内存时,采取并行传输方式,将各个盘块中的子盘块数据同时向内存中传输,从而使传输时间大大减少。

image.png

RAID的分级

RAID在刚被推出时,是分成6级的,后来又增加了RAID 6 级和RAID 7级

(1) RAID 0级。
(2) RAID 1级。
(3) RAID 3级。
(4) RAID 5级。

(5) RAID 6级和RAID 7级。

第五章 输入输出(I/O)系统

5.1 I/O管理概述

1) I/O系统的功能、模型和接口

I/O系统管理的主要对象是I/O设备和相应的设备控制器。主要的任务是,完成用户提出的I/O请求,提高I/O速率,以及提高设备的利用率,并能为更高层的进程方便地使用这些设备提供手段。

I/O系统的基本功能

隐藏物理设备的细节

与设备的无关性

提高处理机和I/O设备的利用率

对I/O设备进行控制

确保对设备的正确共享

独占设备 共享设备

错误处理

I/O系统的层次结构和模型

I/O软件的层次结构

通常把I/O 软件组织成四个层次

image.png

I/O系统中各种模块之间的层次视图

1)I/O系统的上、下接口

(1) I/O系统接口。
(2) 软件/硬件(RW/HW)接口。

2) I/O系统的分层

(1) 中断处理程序。
(2) 设备驱动程序。
(3) 设备独立性软件。

I/O系统接口

块设备接口 流设备接口 网络通信接口

I/O设备

I/O设备的类型

1) 按使用特性分类

存储设备

I/O设备(输入,输出,交互式显示器)

2) 按传输速率分类

低速设备/中速设备/高速设备

设备与控制器之间的接口

设备并不是直接与CPU进行通信,而是与设备控制器通信,在I/O设备中应含有与设备控制器间的接口,在该接口中有三种类型的信号,各对应一条信号线

(1) 数据信号线。
(2) 控制信号线。
(3) 状态信号线。

image.png

设备与控制器间的接口

设备控制器

设备控制器的基本功能

(1) 接收和识别命令。
(2) 数据交换。
(3) 标识和报告设备的状态。
(4) 地址识别。
(5) 数据缓冲区。
(6) 差错控制。

设备控制器的组成

由于设备控制器位于CPU与设备之间,它既要与CPU通信,又要与设备通信,还应具有按照CPU所发来的命令去控制设备工作的功能,因此,现有的大多数控制器都是由以下三部分组成:

(1) 设备控制器与处理机的接口。
(2) 设备控制器与设备的接口。

(3) I/O逻辑

image.png

5.1.1 I/O控制方式

对设备的控制,早期是使用轮询的可编程I/O方式,后来发展为使用中断的可编程I/O方式。

使用轮询的可编程I/O方式

使用中断的可编程I/O方式

直接存储器访问方式

1) 直接存储器访问方式的引入

该方式的特点是:
(1) 数据传输的基本单位是数据块,即在CPU与I/O设备之间,每次传送至少一个数据块。
(2) 所传送的数据是从设备直接送入内存的,或者相反。
(3) 仅在传送一个或多个数据块的开始和结束时,才需CPU 干预,整块数据的传送是在控制器的控制下完成的。

可见,DMA方式较之中断驱动方式又进一步提高了CPU与I/O设备的并行操作程度

image.png

2) DMA控制器的组成

DMA控制器由三部分组成:
主机与DMA控制器的接口;
DMA控制器与块设备的接口;
I/O控制逻辑。CR状态

image.png

3) DMA工作过程

当CPU要从磁盘读入一数据块时,便向磁盘控制器发送一条读命令。
该命令被送入命令寄存器CR中。
同时,需要将本次要读入数据在内存的起始目标地址送入内存地址寄存器MAR中。
启动DMA控制器

5.1.2 I/O软件层次结构

通常把I/O 软件组织成四个层次

image.png

内容太多,不大懂,略过

5.2 I/O核心子系统

5.2.1 I/O调度概念

I/O调度就是确定一个好的顺序来执行这些I/O请求。应用程序所发布的系统调用的顺序不一定总是最佳选择,所以需要I/o 调度来改善系统整体性能,使进程之间公平地共享设备访问,减少I/O完成所需要的平均等待时间。

操作系统开发人员通过为每个设备维护一个请求队列来实现调度。当一个应用程序执行阻塞I/O系统调用时,该请求就加到相应设备的队列上。
I/O调度会重新安排队列顺序以改善系统总体效率和应用程序的平均响应时间。

5.2.2 高速缓冲与缓冲区

在现代操作系统中,几乎所有的I/O设备在与处理机交换数据时都用了缓冲区。
缓冲区是一个存储区域,它可以由专门的硬件寄存器组成,但由于硬件的成本较高,容量也较小,一般仅用在对速度要求非常高的场合,
存储器管理中所用的联想存储器;
设备控制器中用的数据缓冲区等。

1) 缓冲的引入

引入缓冲区的原因可归结为以下几点:
(1) 缓和CPU与I/O设备间速度不匹配的矛盾。
(2) 减少对CPU的中断频率,放宽对CPU中断响应时间的限制。
(3) 解决数据粒度不匹配的问题。
(4) 提高CPU和I/O设备之间的并行性。

2 ) 单缓冲区和双缓冲区

单缓冲区(Single Buffer)

在单缓冲情况下,每当用户进程发出一I/O请求时,操作系统便在主存中为之分配一缓冲区。

image.png

双缓冲区(Double Buffer)

由于缓冲区是共享资源,生产者与消费者在使用缓冲区时必须互斥

如果消费者尚未取走缓冲区中的数据,即使生产者又生产出新的数据,也无法将它送入缓冲区,生产者等待。
如果为生产者与消费者设置了两个缓冲区,便能解决这一问题。

image.png

如果在实现两台机器之间的通信时仅为它们配置了单缓冲,那么,它们之间在任一时刻都只能实现单方向的数据传输。例如,只允许把数据从A传送到B,或者从B传送到A,而绝不允许双方同时向对方发送数据。
为了实现双向数据传输,必须在两台机器中都设置两个缓冲区,一个用作发送缓冲区,另一个用作接收缓冲区。

image.png

3) 环形缓冲区

环形缓冲区的组成

(1) 多个缓冲区

包括多个缓冲区,其每个缓冲区的大小相同。
作为输入的多缓冲区可分为三种类型:

用于装输入数据的空缓冲区R、

已装满数据的缓冲区G
计算进程正在使用的现行工作缓冲区C。

image.png

环形缓冲区的使用

计算进程和输入进程可利用下述两个过程来使用形环缓冲区

(1) Getbuf过程。满缓冲转为计算
(2) Releasebuf过程。计算转为空

进程之间的同步问题

输入循环缓冲,使输入进程和计算进程并行执行。
相应地,指针Nexti和指针Nextg将不断地沿着顺时针方向移动,这样就可能出现下述两种情况:
(1) Nexti指针追赶上Nextg指针。
装满
(2) Nextg指针追赶上Nexti指针。
抽空

4) 缓冲池(Buffer Pool)

缓冲池的组成

缓冲池管理着多个缓冲区,每个缓冲区由用于标识和管理的缓冲首部以及用于存放数据的缓冲体两部分组成。
缓冲首部一般包括缓冲区号、设备号、设备上的数据块号、同步信号量以及队列链接指针等。
一般将缓冲池中具有相同类型的缓冲区链接成一个队列,于是可形成以下三个队列

(1) 空白缓冲队列emq。
(2) 输入队列inq。
(3) 输出队列outq。

5.2.3 设备分配

系统为实现对独占设备的分配,必须在系统中配置相应的数据结构

设备分配中的数据结构

在用于设备分配的数据结构中,记录了对设备或控制器进行控制所需的信息。在进行设备分配时需要如下的数据结构

1) 设备控制表DCT

系统为每一个设备都配置了一张设备控制表,用于记录设备的情况

image.png

2) 控制器控制表、通道控制表和系统设备表

(1) 控制器控制表(COCT)。系统为每一个控制器都设置了用于记录控制器情况的控制器控制表。
(2) 通道控制表(CHCT)。每个通道都有一张通道控制表。
(3) 系统设备表(SDT)。这是系统范围的数据结构,记录了系统中全部设备的情况,每个设备占一个表目,其中包括有设备类型、设备标识符、设备控制表及设备驱动程序的入口等项。

image.png

1) 基本的设备分配程序

当某进程提出I/O请求后,系统的设备分配程序可按下述步骤进行设备分配

(1) 分配设备。SDT->DCT
(2) 分配控制器。COCT
(3) 分配通道。CHCT

逻辑设备名到物理设备名映射的实现

逻辑设备表LUT(Logical Unit Table)

在逻辑设备表的每个表目中包含了三项:
逻辑设备名、
物理设备名、
设备驱动程序的入口地址。

image.png

逻辑设备表的设置问题

在系统中可采取两种方式设置逻辑设备表:
第一种方式,是在整个系统中只设置一张LUT。
第二种方式,是为每个用户设置一张LUT。

5.2.4 假脱机(Spooling)系统

假脱机技术

在20世纪50年代,为了缓和CPU的高速性与I/O设备低速性间的矛盾,而引入了脱机输入、脱机输出技术。
该技术是利用专门的外围控制机,先将低速I/O设备上的数据传送到高速磁盘上,或者相反。
这样当处理机需要输入数据时,便可以直接从磁盘中读取数据,极大地提高了输入速度。
反之,在处理机需要输出数据时,也可以很快的速度把数据先输出到磁盘上,处理机便可去做自己的事情。
外围操作与CPU对数据的处理同时进行,在联机情况下实现的同时外围操作称为SPOOLing(Simultaneaus Periphernal Operating On Line),或称为假脱机操作

SPOOLing的组成

SPOOLing技术是对脱机输入/输出系统的模拟,SPOOLing 系统建立在通道技术和多道程序技术的基础上,以高速随机外存(通常为磁盘)为后援存储器。

SPOOLing系统主要由以下四部分构成:

(1) 输入井和输出井。磁盘
(2) 输入缓冲区和输出缓冲区。内存
(3) 输入进程和输出进程。
(4) 井管理程序。

SPOOLing系统的特点

(1) 提高了I/O的速度。
(2) 将独占设备改造为共享设备。
(3) 实现了虚拟设备功能。

假脱机打印机系统

打印机是经常用到的输出设备,属于独占设备。
利用假脱机技术可将它改造为一台可供多个用户共享的打印设备,从而提高设备的利用率,也方便了用户
共享打印机技术已被广泛地用于多用户系统和局域网络中。

假脱机打印系统主要有以下三部分:

(1) 磁盘缓冲区。
(2) 打印缓冲区。
(3) 假脱机管理进程和假脱机打印进程。


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!