【王道】操作系统 知识点总结(合集)【超详细!】
定义操作系统(Operating System,OS)是指控制和管理整个计算机系统的硬件和软件资源,并合理地组织调度计算机的工作和资源的分配;以提供给用户和其他软件方便的接口和环境;它是计算机系统中最基本的系统软件。特征并发并发指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的,但微观上是交替发生的。OS的并发性是通过分时实现的。单核CPU同一时刻只能执行一个程序,各个程序只能并发
操作系统
1 计算机系统概述
1.1 操作系统的基本概念
-
定义
操作系统(Operating System,OS)是指控制和管理整个计算机系统的硬件和软件资源,并合理地组织调度计算机的工作和资源的分配;以提供给用户和其他软件方便的接口和环境;它是计算机系统中最基本的系统软件。
-
特征
-
并发
并发指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的,但微观上是交替发生的。
OS的并发性是通过分时实现的。
-
单核CPU同一时刻只能执行一个程序,各个程序只能并发地执行
-
多核CPU同一时刻可以同时执行多个程序,多个程序可以并行地执行
并发性:两个或多个事件在同一时间间隔内发生。
并行性:两个或多个事件在同一时刻发生,需要硬件支持,如多流水线或多处理机硬件环境。
多道程序环境下,一段时间,宏观上,多道程序同时执行某一时刻,单处理机环境下实际仅有一道程序执行,微观上程序分时交替执行
-
-
共享
共享即资源共享,是指系统中的资源可供内存中多个并发执行的进程共同使用。
-
互斥共享方式:系统中的某些资源,虽然可以提供给多个进程使用,但一个时间段内只允许一个进程访问该资源。
应用:使用QQ和微信视频。同一时间段内摄像头只能分配给其中一个进程。
-
同时共享方式:系统中的某些资源,允许一个时间段内由多个进程“同时”对它们进行访问。
应用:使用QQ发送文件A,同时使用微信发送文件B。宏观上看,两边都在同时读取并发送文件说明两个进程都在访问硬盘资源,从中读取数据。微观上看,两个进程是交替着访问硬盘的。
所谓的“同时”往往是宏观上的,而在微观上,这些进程可能是交替地对该资源进行访问的(即分时共享)
并发和共享是操作系统两个最基本的特征,两者之间互为存在的条件:
- ①资源共享是以程序的并发为条件的,若系统不允许程序并发执行,则自然不存在资源共享问题;
- ②若系统不能对资源共享实施有效的管理,则必将影响到程序的并发执行,甚至根本无法并发执行。
-
-
虚拟
虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体(前者)是实际存在的,而逻辑上对应物(后者)是用户感受到的。
-
虚拟处理器:通过时分复用技术,让多道程序并发执行的方法,来分时使用一个处理器的。
虽然只有一个处理器,但它能同时为多个用户服务,使每个终端用户都感觉有一个中央处理器(CPU)在专门为它服务。
-
虚拟存储器:通过空分复用技术,将一台机器的物理存储器变为虚拟存储器,以便从逻辑上扩充存储器的容量。当然,这时用户所感觉到的内存容量是虚的。
-
虚拟I/O设备:采用虚拟设备技术将一台物理I/O设备虚拟为多台逻辑上的I/O设备,并允许每个用户占用一台逻辑上的I/O设备,使原来仅允许在一段时间内由一个用户访问的设备(即临界资源)变为在一段时间内允许多个用户同时访问的共享设备。
-
-
异步
在多道程序环境下,允许多个程序并发执行,但由于资源有限,进程的执行不是一贯到底的,而是走走停停,以不可预知的速度向前推进,这就是进程的异步性。
-
-
功能
为了给多道程序提供良好的运行环境,操作系统应具有以下几方面的功能:处理机管理、存储器管理、设备管理和文件管理。为了方便用户使用操作系统,还必须向用户提供接口。同时,操作系统可用来扩充机器,以提供更方便的服务、更高的资源利用率。
-
操作系统是系统资源的管理者
-
处理机管理
即对进程的管理,包括进程控制、进程同步、进程通信、死锁处理、处理机调度等。
-
存储器管理
方便程序运行、用户使用及提高内存的利用率,包括内存分配与回收、地址映射、内存保护与共享和内存扩充等功能。
-
文件管理
计算机中的信息都是以文件的形式存在的,操作系统中负责文件管理的部分称为文件系统。
文件管理包括文件存储空间的管理、目录管理及文件读写管理和保护等。
-
设备管理
设备管理的主要任务是完成用户的I/O请求,方便用户使用各种设备,并提高设备的利用率,主要包括缓冲管理、设备分配、设备处理和虚拟设备等功能。
-
-
向上层提供方便易用的服务
-
命令接口
用户利用这些操作命令来组织和控制作业的执行。
-
联机命令接口:即交互式命令接口,适用于分时或实时系统。
“雇主”说一句话,“工人”做一件事,并做出反馈,这就强调了交互性。
-
脱机命令接口:即批处理命令接口,适用于批处理系统
“雇主”把要“工人”做的事写在清单上,“工人”按照清单命令逐条完成这些事,这就是批处理。
-
-
程序接口
程序接口由一组系统调用(也称广义指令)组成。是为编程人员提供的接口。普通用户不能直接使用程序接口,只能通过程序代码间接使用。
用户通过在程序中使用系统调用命令请求OS为其提供服务。系统调用命令又称广义指令。
-
GUl:图形化用户接口(Graphical User Interface)
用户可以使用形象的图形界面进行操作,而不再需要记忆复杂的命令、参数。
-
-
是最接近硬件的一层软件
裸机:没有任何软件支持的计算机称为裸机,它仅构成计算机系统的物质基础。
在裸机上安装的操作系统,可以提供资源管理功能和方便用户的服务功能,将裸机改造成功能更强、使用更方便的机器。
通常把覆盖了软件的机器成为扩充机器,又称之为虚拟机。
-
例:
1.2 操作系统发展历程
-
手工操作阶段(此阶段无操作系统)
用户在计算机上算题的所有工作都要人工干预,如程序的装入、运行、结果的输出等。
- 缺点:
- 用户独占全机
- CPU等待手工操作,CPU利用不充分
- 人机矛盾:CPU和I/O速度不匹配的矛盾。
- 缺点:
-
批处理阶段(操作系统开始出现)
-
单道批处理系统:引入脱机输入输出技术
-
特征:
- 自动性。在顺利的情况下,磁带上的一批作业能自动地逐个运行,而无须人工干预。
- 顺序性。磁带上的各道作业顺序地进入内存,各道作业的完成顺序与它们进入内存的顺序在正常情况下应完全相同,亦即先调入内存的作业先完成。
- 单道性。内存中仅有一道程序运行,即监督程序每次从磁带上只调入一道程序进入内存运行,当该程序完成或发生异常情况时,才换入其后继程序进入内存运行。
-
优点:缓解人机速度矛盾。
-
缺点:资源利用率仍低,高速CPU等待低速I/O。
-
-
多道批处理系统:多道程序设计技术操作系统开始出现
多道程序设计:允许多个程序同时进入内存并允许它们在CPU中交替地运行,这些程序共享系统中的各种硬/软件资源。当一道程序因I/O请求而暂停运行时,CPU便立即转去运行另一道程序。
-
特点:
- 多道。计算机内存中同时存放多道相互独立的程序。
- 宏观上并行。同时进入系统的多道程序都处于运行过程中,即它们先后开始各自的运行,但都未运行完毕。
- 微观上串行。内存中的多道程序轮流占有CPU,交替执行。
- 间断性:由于多道程序之间需要共享和竞争系统资源,因此每个程序的执行过程不是连续的,而是有间断的。
- 共享性:多道程序之间需要共享系统的各种资源,如CPU、内存、外设等。
- 制约性:多道程序之间存在相互制约的关系,如同步、互斥、优先级等。
-
技术实现:
- 如何分配处理器。
- 多道程序的内存分配问题。
- I/O设备如何分配。
- 如何组织和存放大量的程序和数据,以方便用户使用并保证其安全性与一致性。
-
优点:
- 资源利用率高,多道程序并发执行,共享计算机资源
- 系统吞叶量大,CPU和其他资源保持"忙碌"
-
缺点:用户响应时间长、无人机交互能力
-
-
-
分时操作系统
分时技术:计算机以时间片为单位轮流为各个用户/作业服务,各个用户可通过终端与计算机进行交互。
多个用户通过终端同时共享一台主机,用户可以同时与主机进行交互操作而互不干扰。
-
特点
- 同时性。同时性也称多路性,指允许多个终端用户同时使用一台计算机,即一台计算机与若干台终端相连接,终端上的这些用户可以同时或基本同时使用计算机。
- 交互性。用户能够方便地与系统进行人机对话,即用户通过终端采用人机对话的方式直接控制程序运行,与同程序进行交互。
- 独立性。系统中多个用户可以彼此独立地进行操作,互不干扰,单个用户感觉不到别人也在使用这台计算机,好像只有自己单独使用这台计算机一样。
- 及时性。用户请求能在很短时间内获得响应。分时系统采用时间片轮转方式使一台计算机同时为多个终端服务,使用户能够对系统的及时响应感到满意。
-
优点
-
用户请求可以被即时响应,解决了人机交互问题。
-
允许多个用户同时使用一台计算机,并且用户对计算机的操作相互独立,感受不到别人的存在。
-
-
缺点:无法优先处理紧急任务
-
-
实时操作系统
能在某个时间限制内完成某些紧急任务而不需要时间片排队。
-
分类:
-
软实时系统:能够接受偶尔违反时间规定且不会引起永久性的损害。
如飞机订票系统、银行管理系统。
-
硬实时系统:某个动作必须绝对地在规定的时刻(或规定的时间范围)发生。
如飞行器的飞行自动控制系统。
-
-
特点
- 及时性
- 可靠性
-
优点:能够优先处理紧急任务
-
-
网络操作系统和分布式计算机系统
-
网络操作系统:把计算机网络中的各台计算机有机地结合起来,提供一种统一、经济而有效的使用各台计算机的方法,实现各台计算机之间数据的互相传送。
- 特点
- 网络中各种资源的共享
- 各台计算机之间的通信
- 特点
-
分布式计算机系统:由多台计算机组成并满足下列条件的系统,主要特点是分布性和并行性。
- 系统中任意两台计算机通过通信方式交换信息
- 系统中的每台计算机都具有同等的地位,即没有主机也没有从机
- 每台计算机上的资源为所有用户共享
- 系统中的任意台计算机都可以构成一个子系统,并且还能重构
- 任何工作都可以分布在几台计算机上,由它们并行工作、协同完成
-
分布式操作系统与网络操作系统的本质不同:分布式操作系统中的若干计算机相互协同完成同一任务。
-
-
个人计算机操作系统
个人计算机操作系统是目前使用最广泛的操作系统,它广泛应用于文字处理、电子表格、游戏中。
常见的有Windows、Linux和MacOS等。
操作系统发展历程如下图所示。
此外,还有嵌入式操作系统、服务器操作系统、智能手机操作系统等。
例
1.3 操作系统运行环境
1.3.1 处理器运行模型
-
在计算机系统中,通常CPU执行两种不同性质的程序:
- 操作系统内核程序:是用户自编程序的管理者,“管理程序”(即内核程序)要执行一些特权指令。
- 用户自编程序:即系统外层的应用程序,或简称“应用程序”,“被管理程序”(即用户自编程序)出于安全考虑不能执行这特权指令。
-
特权指令和非特权指令
- 特权指令:是指不允许用户直接使用的指令,如/O指令、置中断指令,存取用于内存保护的寄存器、送程序状态字到程序状态字寄存器等的指令。
- 非特权指令:是指允许用户直接使用的指令,它不能直接访问系统中的软硬件资源,仅限于访问用户的地址空间,这也是为了防止用户程序对系统造成破坏。
-
CPU的运行模式
- 用户态(目态):CPU处于用户态,此时CPU只能执行非特权指令。
- 核心态(又称管态、内核态):CPU处于核心态,此时CPU可以执行特权指令,切换到用户态的指令也是特权指令。
应用程序运行在用户态,操作系统内核程序运行在核心态。
内核态一>用户态:一条修改PSW的特权指令
用户态一>内核态:应用程序向操作系统请求服务时通过使用访管指令,从而产生一个中断事件将操作系统转换为核心态。
-
分层管理
-
一些与硬件关联较紧密的模块,如时钟管理、中断处理、设备驱动等处于最低层。
-
其次是运行频率较高的程序,如进程管理、存储器管理和设备管理等。
这两部分内容构成了操作系统的内核。这部分内容的指令操作工作在核心态。
-
-
操作系统内核功能
内核(Kernel)是计算机上配置的底层软件,它管理着系统的各种资源,可以看作是连接应用程序和硬件的一座桥梁。由很多内核程序组成操作系统内核。
-
时钟管理
-
计时:是时钟的第一功能,操作系统需要通过时钟管理,向用户提供标准的系统时间。
-
进程切换:通过时钟中断的管理实现。
例如,在分时操作系统中采用时间片轮转调度,在实时系统中按截止时间控制运行,在批处理系统中通过时钟管理来衡量一个作业的运行程度等。
-
-
中断机制
中断作用:
- 让操作系统内核强行夺回CPU的控制权
- 使CPU从用户态变为内核态
引入原因:提高多道程序运行环境中CPU的利用率。
现代操作系统是靠中断驱动的软件
-
原语
由若干条指令组成的,用于完成一定功能的一个过程。
特点:
- 1)处于操作系统的最底层,是最接近硬件的部分。
- 2)这些程序的运行具有原子性,其操作只能一气呵成(出于系统安全性和便于管理考虑)。
- 3)这些程序的运行时间都较短,而且调用频繁。
定义原语的直接方法是关闭中断,让其所有动作不可分割地完成后再打开中断。
系统中的设备驱动、CPU切换、进程通信等功能中的部分操作都可定义为原语,使它们成为内核的组成部分。
-
系统控制的数据结构及处理
系统中用来登记状态信息的数据结构很多,如作业控制块、进程控制块(PCB)、设备控制块、各类链表、消息队列、缓冲区、空闲区登记表、内存分配表等。
为了实现有效的管理,系统需要一些基本的操作,常见的操作有以下3种:
- 1)进程管理。进程状态管理、进程调度和分派、创建与撤销进程控制块等。
- 2)存储器管理。存储器的空间分配和回收、内存信息保护程序、代码对换程序等。
- 3)设备管理。缓冲区管理、设备分配和回收等。
核心态指令实际上包括系统调用类指令和一些针对时钟、中断和原语的操作指令。
-
1.3.2 中断和异常的概念
-
中断作用
让操作系统内核强行夺回CPU的控制权;使CPU从用户态变为内核态。
-
中断和异常的分类
-
异常:又称内中断,指来自CPU执行指令内部的事件,如程序的非法操作码、地址越界、运算溢出、虚存系统的缺页及专门的陷入指令等引起的事件。
- 故障(Fault)通常是由指令执行引起的异常,如非法操作码、缺页故障、除数为0、运算溢出等。
- 自陷(Trap)是一种事先安排的“异常”事件,用于在用户态下调用操作系统内核程序,如条件陷阱指令。
- 终止(Abort)是指出现了使得CPU无法继续执行的硬件故障,如控制器出错、存储器校验错等。
-
中断:又称外中断,指来自CPU执行指令外部的事件,通常用于信息输入/输出,如I/O中断,时钟中断。
-
可屏蔽中断:指通过INTR线发出的中断请求,通过改变屏蔽字可以实现多重中断,从而使得中断处理更加灵活。
-
不可屏蔽中断:指通过NMI线发出的中断请求,通常是紧急的硬件故障,如电源掉电等。此外,异常也是不能被屏蔽的。
-
故障异常和自陷异常属于软件中断(程序性异常),终止异常和外部中断属于硬件中断。
异常不能被屏蔽,一旦出现,就应立即处理。
-
-
中断和异常的处理过程
-
当CPU在执行用户程序的第i条指令时检测到一个异常事件,或在执行第i条指令后发现一个中断请求信号,
-
则CPU打断当前的用户程序,然后转到相应的中断或异常处理程序去执行。
-
若中断或异常处理程序能够解决相应的问题,则在中断或异常处理程序的最后,CPU通过执行中断或异常返回指令,回到被打断的用户程序的第i条指令或第i+1条指令继续执行
返回第i+1条指令:由自陷(Trap)引起的内中断;如系统调用。由外部设备引起的外中断,如键盘
返回第i条指令:由故障(Fault)引起的内中断;如缺页等。
-
若中断或异常处理程序发现是不可恢复的致命错误,则终止用户程序。
通常情况下,对中断和异常的具体处理过程由操作系统(和驱动程序)完成。
-
1.3.3 系统调用
-
定义
操作系统作为用户和计算机硬件之间的接口,需要向上提供一些简单易用的服务,系统调用可视为特殊的公共子程序。又称广义指令。程序接口由一组系统调用组成。目的为解决资源分配问题
-
分类
- 设备管理:完成设备的请求或释放,以及设备启动等功能。
- 文件管理:完成文件的读、写、创建及删除等功能。
- 进程控制:完成进程的创建、撤销、阻塞及唤醒等功能。
- 进程通信:完成进程之间的消息传递或信号传递等功能。
- 内存管理:完成内存的分配、回收以及获取作业占用内存区大小及始址等功能。
-
系统调用过程
系统调用的处理需要由操作系统内核程序负责完成,要运行在核心态。
用户程序可以执行陷入指令(又称访管指令或trap指令)来发起系统调用,请求操作系统提供服务。
访管指令不是特权指令,访管指令是在用户态使用的,所以它不可能是特权指令。
-
系统调用执行过程:
传递系统调用参数→执行陷入(trap)指令→执行相应的服务程序→返回用户态
- 当需要管理程序服务时,系统则通过硬件中断机制进入核心态,运行管理程序;
- 也可能是程序运行出现异常情况,被动地需要管理程序的服务,这时就通过异常处理来进入核心态。
- 管理程序运行结束时,用户程序需要继续运行,此时通过相应的保存的程序现场退出中断处理程序或异常处理程序,返回断点处继续执行
-
用户态转向核心态的例子:
- 用户程序要求操作系统的服务,即系统调用。
- 发生一次中断。
- 用户程序中产生了一个错误状态。
- 用户程序中企图执行一条特权指令。
- 从核心态转向用户态由一条指令实现,这条指令也是特权命令,一般是中断返回指令。
-
只能在核心态下执行的指令(特权指令):
- 开关中断指令,用于允许或禁止中断,控制中断屏蔽位
- 设置时钟日期指令,用于修改系统时钟
- 改变存储映像图指令,用于修改主存保护机制
- 启动I/O指令,用于控制I/O设备的工作状态和动作
- 加载PSW指令,用于修改程序状态字(PSW),包括中断标志位、运算结果标志位等
- 置特殊寄存器指令,用于存取中断寄存器、时钟寄存器等特殊寄存器
- 停机指令,用于停止一个中央处理器的工作
注意:由用户态进入核心态,不仅状态需要切换,而且所用的堆栈也可能需要由用户堆栈切换为系统堆栈,但这个系统堆栈也是属于该进程的。
-
-
与库函数的区别
- 有的库函数是对系统调用的进一步封装:如“创建一个新文件”的函数
- 有的库函数没有使用系统调用:如的“取绝对值”的函数
例:
1.4 操作系统结构
-
分层法
分层法是将操作系统分为若干层,最底层(层0)为硬件,最高层(层N)为用户接口,每层只能调用紧邻它的低层的功能和服务(单向依赖)。
- 优点:
- ①便于系统的调试和验证,简化了系统的设计和实现。只需调试每层功能,无需考虑其他层。
- ②易扩充和易维护。在系统中修改添加某层,不改变接口就不影响其他层。
- 缺点:
- ①合理定义各层比较困难。因为依赖关系固定后,往往就显得不够灵活。
- ②效率较差。执行一个功能要穿梭多层,每层通信增大开销。
- 优点:
-
模块化
模块化是将操作系统按功能划分为若干具有一定独立性的模块。每个模块具有某方面的管理功能,并规定好各模块间的接口,使各模块之间能够通过接口进行通信。各模块还可划分成子模块,子模块之间也规定好接口。
-
模块划分应考虑其划分大小,及独立性,衡量独立性有两个标准:
- 内聚性,模块内部各部分间联系的紧密程度。内聚性越高,模块独立性越好。
- 耦合度,模块间相互联系和相互影响的程度。耦合度越低,模块独立性越好。
-
优点:
-
①提高了操作系统设计的正确性、可理解性和可维护性;
-
②增强了操作系统的可适应性;
-
③加速了操作系统的开发过程。
-
-
缺点:
- ①模块间的接口规定很难满足对接口的实际需求。
- ②各模块设计者齐头并进,每个决定无法建立在上一个已验证的正确决定的基础上,因此无法找到一个可靠的决定顺序。
-
-
宏内核
又称大内核或单内核,是指将系统的主要功能模块都作为一个紧密联系的整体运行在核心态,从而为用户程序提供高性能的系统服务。
- 优点:高性能
- 缺点:内核代码庞大,结构混乱,难以维护
- 应用:Windows、Linux、Android、IOS、macOS等架构;但其都广泛吸取微内核的优点进行改进。
-
微内核
微内核构架,是指将内核中最基本的功能保留在内核,而将那些不需要在核心态执行的功能移到用户态执行,从而降低内核的设计复杂性。
那些移出内核的操作系统代码根据分层的原则被划分成若干服务程序,它们的执行相互独立,交互则都借助于微内核进行通信。
微内核架构=微内核+多个服务器
-
微内核内容
- ①与硬件处理紧密相关的部分
- ②一些较基本的功能
- ③客户和服务器之间的通信。
-
服务器(进程)
-
用于提供对进程(线程)进行管理的进程(线程)服务器、
-
提供虚拟存储器管理功能的虚拟存储器服务器等,
它们都是作为进程来实现的,运行在用户态,客户与服务器之间是借助微内核提供的消息传递机制来实现交互的。下图为单机环境下的客户/服务器模式。
-
-
微内核基本功能
-
①进程(线程)管理。
如进程(线程)之间通信、切换、调度以及多处理机之间的同步。
-
②低级存储器管理。
如用于实现将逻辑地址变换为物理地址等的页表机制和地址变换机制,这一部分是依赖于硬件的,因此放入微内核。
-
③中断和陷入处理。
捕获所发生的中断和陷入事件,并进行中断响应处理,在识别中断或陷入的事件后,再发送给相关的服务器来处理
-
-
微内核特点
- ①扩展性和灵活性。增添新的功能无需改变内核代码,只需在相应服务器中修改添加新功能。
- ②可靠性和安全性。某个模块崩溃时,只会使该进程崩溃,不会使整个系统崩溃。
- ③可移植性。与CPU和I/O硬件有关的代码均放在内核中,移植代码无需考虑硬件差异。
- ④分布式计算。采用消息传递机制,使微内核系统能很好地支持分布式系统和网络系统。
-
微内核缺点:需要频繁地在核心态和用户态之间切换,性能低
-
应用:鸿蒙OS、实时、工业、航空及军事应用。
-
-
外核(exokernel)
内核负责进程调度、进程通信等功能;外核在内核态运行,负责为用户进程分配未经抽象的硬件资源,且由外核负责保证资源使用安全。
-
任务:为虚拟机分配资源,并检查使用这些资源的企图,以确保没有机器会使用他人的资源。每个用户层的虚拟机可以运行自己的操作系统,但限制只能使用已经申请并且获得分配的那部分资源。
-
优点
- 外核可直接给用户进程分配“不虚拟、不抽象的硬件资源,使用户进程可以更灵活的使用硬件资源
- 减少了虚拟硬件资源的“映射层",提升效率
-
缺点
- 降低了系统的一致性
- 使系统变得更复杂
-
1.5 操作系统引导
-
概念
-
BIOS 程序(Basic Input/Output System)
BIOS 是固化在主板上的基本输入输出系统,是计算机启动第一个运行的软件,存放在ROM中。它会进行硬件初始化和自检,然后查找引导程序并执行。
-
引导程序(Boot)
引导程序是存储在主存ROM中的一段小程序,它的作用是将操作系统的内核文件从硬盘中读取到内存中,并跳转到内核入口点开始执行。
-
主引导记录(MBR)
MBR是硬盘的主引导记录,位于硬盘的第一个扇区。它包含了磁盘引导程序和分区表。该引导程序会找到活动分区并读取其分区引导记录,完成硬盘的引导。
-
分区引导记录(PBR)
PBR是分区引导记录,位于每个分区的第一个扇区。PBR中包含了一个引导程序,可以寻找并激活分区根目录下的启动管理器,完成分区的引导过程。
-
-
引导过程
引导过程:
- ①CPU从一个特定主存地址开始,取指令,执行ROM中的引导程序(先进行硬件自检,再开机)
- BIOS初始化并执行引导程序进行自检,确保硬件工作正常。
- BIOS查找可引导设备(通常是安装有操作系统的硬盘),读取主引导记录(MBR)。
- ②将磁盘的第一块一一主引导记录读入内存,执行磁盘引导程序,扫描分区表
- MBR执行,识别活动分区,查找并执行该分区的分区引导记录(PBR)。
- ③从活动分区(又称主分区,即安装了操作系统的分区)读入分区引导记录,执行其中的程序
- PBR找到分区中操作系统的启动管理器程序并加载执行。
- ④从根目录下找到完整的操作系统初始化程序(即启动管理器)并执行,完成“开机”的一系列动作
- 启动管理器进一步加载操作系统内核和关键组件到内存。
- 操作系统内核接管硬件控制权,初始化系统,启动操作系统。
注:操作系统最终被加载到 RAM 中。
- ①CPU从一个特定主存地址开始,取指令,执行ROM中的引导程序(先进行硬件自检,再开机)
1.6 虚拟机
-
定义
使用虚拟化技术,将一台物理机器虚拟化为多台虚拟机器(Virtual Machine,VM),每个虚拟机器都可以独立运行一个操作系统。
-
分类
-
第一类虚拟机程序
第一类虚拟机管理程序就像一个操作系统,因为它是唯一一个运行在最高特权级的程序。
它在裸机上运行并且具备多道程序功能。虚拟机管理程序向上层提供若干台虚拟机,这些虚拟机是裸机硬件的精确复制品。由于每台虚拟机都与裸机相同,所以在不同的虚拟机上可以运行任何不同的操作系统。
虚拟内核态:虚拟机作为用户态的一个进程运行,不允许执行敏感指令。然而,虚拟机上的操作系统认为自己运行在内核态(实际上不是),称为虚拟内核态。
-
第二类虚拟机程序
它是一个依赖于Windows、Linux等操作系统分配和调度资源的程序,很像一个普通的进程。
如VMware Workstation。
对于第二类虚拟机管理程序,运行在底层硬件上的操作系统称为宿主操作系统;运行在虚拟机管理程序上的操作系统称为客户操作系统。
首次启动时,第二类虚拟机管理程序像一台刚启动的计算机那样运转,期望找到的驱动器可以是虚拟设备。然后将操作系统安装到虚拟磁盘上(其实只是宿主操作系统中的一个文件)。客户操作系统安装完成后,就能启动并运行。
-
-
对比
第一类VMM 第二类VMM 对物理资源的控制权 直接运行在硬件之上,能直接控制和分配物理资源 运行在Host OS之上,依赖于Host OS为其分配物理资源 资源分配方式 在安装Guest OS时,VMM要在原本的硬盘上自行分配存储空间,类似于"外核“的分配方式,分配未经抽象的物理硬件 GuestOs拥有自己的虚拟磁盘,该盘实际上是HostOs文件系统中的一个大文件。GuestOs分配到的内存是虚拟内存 性能 性能更好 性能更差,需要Host Os作为"中介” 可支持的虚拟机数量 更多,不需要和Host OS竞争资源,相同的硬件资源可以支持更多的虚拟机 更少,Host Os本身需要使用物理资源,Host OS上运行的其他进程也需要物理资源 虚拟机的可迁移性 更差 更好,只需导出虚拟机镜像文件即可迁移到另一台Host Os上,商业化应用更广泛 运行模式 第一类VMM运行在最高特权级(Ring 0),可以执行最高特权的指令。 第二类VMM部分运行在用户态、部分运行在内核态。GuestOs发出的系统调用会被VMM截获,并转化为VMM对Hostos的系统调用
2 进程与线程
2.1 进程与线程
2.1.1 进程的概念和特征
-
进程的概念
进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。
进程实现操作系统的并发性和共享性。
程序:是静态的,就是个存放在磁盘里的可执行文件,如:QQ.exe。
进程:是动态的,是程序的一次执行过程,或者是一个正在运行的程序,如:可同时启动多次QQ程序。
进程实体:即进程映像,是静态的,可理解为进程的一次时刻的状态。
作业:用户向计算机提交的一项任务,是静态的,它通常是一个批处理程序或一个后台程序。
-
进程实体的组成
-
程序控制块PCB
PCB是进程存在的唯一标志,当进程被创建时,操作系统为其创建PCB,当进程结束时,会回收其PCB。
- 进程描述信息
- 进程标识符PID:当进程被创建时,操作系统会为该进程分配一个唯一的、不重复的“身份证号”–PID(Process ID,进程ID)
- 用户标识符UID
- 进程控制和管理信息
- CPU、磁盘、网络流量使用情况统计…
- 进程当前状态:就绪态/阻塞态/运行态.…
- 资源分配清单
- 正在使用哪些文件
- 正在使用哪些内存区域
- 正在使用哪些I/O设备
- 处理机相关信息(CPU现场信息):如PSW、PC等等各种寄存器的值(用于实现进程切换)
- 进程描述信息
① PCB,即进程控制块,操作系统需要对各个并发运行的进程进行管理, 但凡管理时所需要的信息,都会被放在 PCB 中。
② PCB 是进程存在的唯一标志。
③ PCB 存于内存的内核区,注意内存的内核区和 OS 的内核态的区别,内核程序运行在内核态。- 程序段:程序的代码(指令序列)
- 数据段:运行过程中产生的各种数据(如:程序中定义的变量)
①PCB 是给操作系统用的,程序段和数据段是给进程自己用的。
②引入进程实体的概念后,可把进程定义为是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。
-
-
进程的特征
- 动态性:进程是程序的一次执行过程,是动态地产生、变化和消亡的;动态性是进程最基本的特征。
- 并发性:内存中有多个进程实体,各进程可并发执行
- 独立性:进程是能独立运行、独立获得资源、独立接受调度的基本单位
- 异步性:各进程按各自独立的、不可预知的速度向前推进,异步性会导致并发程序执行结果的不确定性。
- 结构性:每个进程都会配置一个PCB。结构上看,进程由程序段、数据段、PCB组成
2.1.2 进程的状态与转换
-
基本状态
-
运行态。占有CPU,并在CPU上运行;√CPU√其他所需资源
-
就绪态。已具有运行条件,但无空闲CPU,暂时不能运行;×CPU√其他所需资源
系统中处于就绪状态的进程可能有多个,通常将它们排成一个队列,称为就绪队列。
-
阻塞态,又称等待态。因等待某一事件暂时不能运行;×CPU×其他所需资源
系统通常将处于阻塞态的进程也排成一个队列,甚至根据阻塞原因的不同,设置多个阻塞队列。
-
创建态。进程正在被创建,尚未转到就绪态。OS为进程分配系统资源、初始化PCB
- 首先申请一个空白PCB,并向PCB中填写用于控制和管理进程的信息
- 然后为该进程分配运行时所必须的资源
- 最后把该进程转入就绪态并插入就绪队列
但是,如果进程所需的资源尚不能得到满足,如内存不足,则创建工作尚未完成,进程此时所处的状态称为创建态。
-
终止态。进程正从系统中消失,进程正常结束或其他原因退出运行。OS回收进程拥有的资源,撤销PCB
-
-
进程状态的转换
- 就绪态一>运行态:进程被调度
- 运行态一>就绪态:时间片到 or CPU被其他进程抢占
- 运行态一>阻塞态:等待系统资源分配or等待某事件发生(主动行为)
- 阻塞态一>就绪态:资源分配到位,等待的事件发生(被动行为)
- 创建态一>就绪态:系统完成创建进程相关的工作
- 运行态一>终止态:进程运行结束 or 运行过程中遇到不可修复的错误
2.1.3 进程的组织方式
-
链接方式
链接方式是将同一状态的进程的PCB组成一个双向链表,称为进程队列。
-
结构:每个队列的队首和队尾都有一个指针,指向第一个和最后一个PCB。每个PCB中也有两个指针,分别指向前一个和后一个PCB。这样,就可以方便地在队列中插入或删除PCB。
-
优点:简单、灵活
-
缺点:查找效率低,需要遍历链表
-
-
索引方式
索引方式是将所有的PCB存放在一张索引表中,每个表项包含一个PCB的地址和状态信息。
- 结构:索引表可以是顺序表或散列表,可以按照进程号或其他关键字进行排序或散列。
- 优点:查找效率高,可以快速定位到某个PCB
- 缺点:需要额外的空间存储索引表,且索引表的大小受限于内存容量
2.1.4 进程控制
进程控制就是要实现进程状态的转换,通过原语实现。
-
进程的创建
-
创建原语:操作系统创建一个进程时使用的原语,其操作如下;创建态→就绪态
- 申请空白PCB
- 为新进程分配所需资源
- 初始化PCB
- 将PCB插入就绪队列
-
引起进程创建的事件
- 用户登录:分时系统中,用户登录成功,系统会建立为其建立一个新的进程
- 作业调度:多道批处理系统中,有新的作业放入内存时,会为其建立一个新的进程
- 提供服务:用户向操作系统提出某些请求时,会新建一个进程处理该请求
- 应用请求:由用户进程主动请求创建一个子进程
-
父子进程
允许一个进程创建另一个进程,此时创建者称为父进程,被创建的进程称为子进程。
- 进程可以继承父进程所拥有的资源。
- 当子进程被撤销时,应将其从父进程那里获得的资源归还给父进程。
- 在撤销父进程时,通常也会同时撤销其所有的子进程。
-
-
进程的终止
- 撤销原语:其操作如下;就绪态/阻塞态/运行态→终止态→无
- 从PCB集合中找到终止进程的PCB
- 若进程正在运行,立即剥夺CPU,将CPU分配给其他进程
- 终止其所有子进程
- 将该进程拥有的所有资源归还给父进程或操作系统
- 删除PCB
- 引起进程终止的事件
- 正常结束:进程自已请求终止(exit系统调用)
- 异常结束:整数除以0、非法使用特权指令,然后被操作系统强行杀掉
- 外界干预:Ctrl+Alt+delete,用户选择杀掉进程
- 撤销原语:其操作如下;就绪态/阻塞态/运行态→终止态→无
-
进程的阻塞
- 阻塞原语:其操作如下;运行态→阻塞态
- 找到要阻塞的进程对应的PCB
- 保护进程运行现场,将PCB状态信息设置为“阻塞态,暂时停止进程运行
- 将PCB插入相应事件的等待队列
- 引起进程阻塞的事件
- 需要等待系统分配某种资源
- 需要等待相互合作的其他进程完成工作
- 阻塞原语:其操作如下;运行态→阻塞态
-
进程的唤醒
- 唤醒原语:其操作如下;阻塞态→就绪态
- 在事件等待队列中找到PCB
- 将PCB从等待队列移除,设置进程为就绪态
- 将PCB插入就绪队列,等待被调度
- 引起进程唤醒的事件
- 等待的事件发生:因何事阻塞,就应由何事唤醒
阻塞原语唤醒原语必须成对使用
- 唤醒原语:其操作如下;阻塞态→就绪态
-
进程的切换
- 切换原语:其操作如下;运行态→就绪态,就绪态→运行态
- 将运行环境信息存入PCB
- PCB移入相应队列选择
- 另一个进程执行,并更新其PCB
- 根据PCB恢复新进程所需的运行环境
- 引起进程切换的事件
- 当前进程时间片到
- 有更高优先级的进程到达
- 当前进程主动阻塞
- 当前进程终止
- 切换原语:其操作如下;运行态→就绪态,就绪态→运行态
2.1.5 进程的通信
低级通信方式:PV操作。高级通信方式:共享存储、消息传递、管道通信。
-
共享存储
设置一个共享空间,通过对其进行读/写操作实现信息交换
在对共享空间进行写/读操作时,需要使用同步互斥工具(如PV操作)。
共享存储分为两种:
-
低级方式:基于数据结构的共享
比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多,是一种低级通信方式
-
高级方式:基于存储区的共享
操作系统在内存中划出一块共享存储区,数据的形式、存放位置都由通信进程控制,而不是操作系统。这种共享方式速度很快,是一种高级通信方式。
进程之间共享空间需要通过特殊的系统调用实现;进程内线程共享进程空间。
-
-
消息传递
在消息传递系统中,进程间的数据交换以格式化的消息(Message)为单位。
在微内核操作系统中,微内核与服务器之间的通信就采用了消息传递机制。
消息格式:
- 消息头:发送进程ID、接受进程ID、消息长度等格式化的信息
- 消息体
通信方式:
-
直接通信方式:发送进程直接把消息发送给接收进程,并将它挂在接收进程的消息缓冲队列上,接收进程从消息缓冲队列中取得消息。
-
间接通信方式:送进程通过信箱间接地通信,将消息发送到某个中间实体,接收进程从中间实体取得消息。该通信方式广泛应用于计算机网络中。
注:可以多个进程往同一个信箱 send 消息,也可以多个进程从同一个信箱中 receive 消息。
用发送原语和接收原语实现基于信箱的进程间通信
-
管道通信
管道是一个特殊的共享文件,又名pipe文件。其实就是在内存中开辟一个大小固定的内存缓冲区。
管道通信允许两个进程按生产者-消费者方式进行通信。各进程要互斥访问管道。
- 写满时,不能再写,读空时,不能再读
- 没写满时,不能读,没读空时,不能写
一个管道只能实现半双工通信;实现双向同时通信要建立两个管道
-
管道本质上是一种特殊的文件。相比于普通的文件通信,其区别如下:
- 限制管道的大小。管道文件是一个固定大小的缓冲区,使得它的大小不像普通文件那样不加检验地增长。
- 读进程也可能工作得比写进程快。读空时再读管道会被阻塞,而不是调用返回文件结束。
-
管道中的数据一旦被读出,就彻底消失。因此,当多个进程读同一个管道时,可能会错乱。对此,通常有两种解决方案:
- ①一个管道允许多个写进程,一个读进程(2014年408真题高教社官方答案);
- ②允许有多个写进程,多个读进程,但系统会让各个读进程轮流从管道中读数据(Liux的方案)。
管道只能由创建进程所访问,当父进程创建一个管道后,由于管道是一种特殊文件,子进程会继承父进程的打开文件,因此子进程也继承父进程的管道,并使用它来与父进程进进行通信。
2.1.6 线程和多线程模型
-
线程的基本概念
线程可理解为轻量级进程,它是一个基本的CPU执行单元,也是程序执行流的最小单位。
线程由线程ID、程序计数器、寄存器集合和堆栈组成。
引入进程的目的是更好地使多道程序并发执行,提高资源利用率和系统吞吐量;
而引入线程的目的则是减小程序在并发执行时所付出的时空开销,提高操作系统的并发性能。
引入线程后,进程只作为除CPU外的系统资源的分配单位,线程则作为处理机的分配单元
-
线程与进程的比较
传统进程机制 引入线程后 资源分配、调度 进程是资源分配、调度基本单位 进程是资源分配基本单位
线程是资源调度基本单位并发性 进程间并发 线程间也能并发 拥有资源 拥有资源的基本单位 不拥有系统资源 独立性 进程间独立地址空间和资源 同进程下的线程共享地址空间和资源 系统开销 需要切换进程运行环境,开销大 同一进程内线程,不需切换进程环境,开销小 支持多处理机系统 进程只能运行在一个处理机上 进程中多个线程可以分配到多个处理机执行 -
线程的属性
多线程操作系统中的进程已不再是一个基本的执行实体,但它仍具有与执行相关的状态。所谓进程处于“执行”状态,实际上是指该进程中的某线程正在执行。
- 线程是处理机调度的单位
- 多CPU计算机中,各个线程可占用不同的CPU
- 每个线程都有一个线程ID、线程控制块(TCB)
- 线程也有就绪、阻塞、运行三种基本状态
- 线程几乎不拥有系统资源
- 同一进程的不同线程间共享进程的资源
- 由于共享内存地址空间,同一进程中的线程间通信甚至无需系统干预
- 同一进程中的线程切换,不会引起进程切换
- 不同进程中的线程切换,会引起进程切换
- 切换同进程内的线程,系统开销很小
- 切换进程,系统开销较大
注:线程是处理机调度的单位,这里的线程指的是 操作系统看得见的内核级线程,内核级线程是处理机分配的单位 。
同进程的线程之间可以共享进程的代码段、全局变量、打开的文件,不共享线程各自的栈指针等TCB内容
-
线程的实现方式
线程的实现可以分为两类:用户级线程 和 内核级线程。内核级线程又称内核支持的线程。
-
用户级线程
在用户级线程中,有关线程管理(创建、撤销和切换等)的所有工作都由应用程序在用户空间中完成,内核意识不到线程的存在,因此说用户级线程对操作系统透明。
- 用户级线程由应用程序通过线程库实现,所有的线程管理工作都由应用程序负责(包括线程切换)
- 用户级线程中,线程切换可以在用户态下即可完成,无需操作系统干预。
- 在用户看来,是有多个线程。但是在操作系统内核看来,并意识不到线程的存在。“用户级线程”就是“从用户视角看能看到的线程
若系统中只有用户级线程,则处理机的调度对象是进程
优点:
- 用户级线程的切换在用户空间即可完成,不需要切换到核心态,
- 线程管理的系统开销小,效率高
缺点:
- 当一个用户级线程被阻塞后,整个进程都会被阻塞,并发度不高。
- 多个线程不可在多核处理机上并行运行
-
内核级线程
内核级线程是在内核的支持下运行的,线程管理的所有工作也是在内核空间内实现的。
- 内核级线程的管理工作由操作系统内核完成。
- 线程调度、切换等工作都由内核负责,因此**内核级线程的切换**必然需要在核心态下才能完成。
- 操作系统会为每个内核级线程建立相应的==TCB(Thread Control Block,线程控制块)==通过TCB对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”
优点:
- 当一个线程被阻塞后,别的线程还可以继续执行,并发能力强。
- 多线程可在多核处理机上并行执行。
缺点:
- 一个用户进程会占用多个内核级线程,线程切换由操作系统内核完成,需要切换到核心态,因此线程管理的成本高,开销大。
用户级线程 内核级线程 线程的管理工作由谁来完成 由 应用程序 通过线程库实现所有的线程管理工作 ,包括线程切换 线程管理工作由 操作系统内核完成 线程切换是否需要 CPU 变态 用户级线程切换 可以在用户态下即可完成 ,无需操作系统干预 线程调度、切换等工作都由内核负责,因此 内核级线程的切换 必然需要在 核心态 下才能完成。 OS 是否能意识到用户级线程的存在 OS 内核意识不到用户级线程的存在
用户级线程就是从用户视角看能看到的线程OS 会为每个内核级线程建立相应的 TCB(线程控制块)
通过TCB对线程进行管理
内核级线程就是从操作系统内核视角看能看到的线程优点 用户级线程的切换在用户空间即可完成,
不需要切换到核心态,线程管理的系统开销小,效率高当一个线程被阻塞后,其他线程还可以继续执行,并发能力强
多线程可在多核处理机上并行执行缺点 当一个用户级线程被阻塞后,整个进程都会被阻塞,并发度不高
因为进程是处理机调度的基本单位,同一进程的多个线程不可在多核处理机上并行运行一个用户进程会占用多个内核级线程,线程切换由操作系统内核完成
需要切换到核心态,因此线程管理的开销大,效率低,成本高 -
组合方式
有些系统使用组合方式的多线程实现。在组合实现方式中,内核支持多个内核级线程的建立、调度和管理,同时允许用户程序建立、调度和管理用户级线程。
- 一些内核级线程对应多个用户级线程,这是用户级线程通过时分多路复用内核级线程实现的。
- 同一进程中的多个线程可以同时在多处理机上并行执行,
- 且在阻塞一个线程时不需要将整个进程阻塞,
-
线程库
线程库是为程序员提供创建和管理线程的API。实现方式有以下两种。
- ①在用户空间中提供一个没有内核支持的库。这种库的所有代码和数据结构都位于用户空间中。这意味着,调用库内的一个函数只导致用户空间中的一个本地函数的调用。
- ②实现由操作系统直接支持的内核级的一个库。对于这种情况,库内的代码和数据结构位于内核空间。调用库中的一个API函数通常会导致对内核的系统调用。
-
-
多线程模型
-
一对一模型
一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
- 优点:当一个线程被阻塞后,别的线程还可以继续执行,并发能力强。多线程可在多核处理机上并行执行。(内核级线程优点)
- 缺点:一个用户进程会占用多个内核级线程,线程切换由操作系统内核完成,需要切换到核心态,因此线程管理的成本高,开销大。(内核级线程缺点)
-
多对一模型
多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。
- 优点:用户级线程的切换在用户空间即可完成,不需要切换到核心态,线程管理的系统开销小,效率高(用户级线程优点)
- 缺点:当一个用户级线程被阻塞后,整个进程都会被阻塞,并发度不高。多个线程不可在多核处理机上并行运行(用户级线程缺点)
-
多对多模型
n用户及线程映射到m个内核级线程(n>=m)。每个用户进程对应m个内核级线程。
克服了多对一模型并发度不高的缺点(一个阻塞全体阻塞),又克服了一对一模型中一个用户进程占用太多内核级线程,开销太大的缺点。还拥有上述两种模型各自的优点。
-
-
线程的状态与转换
-
线程的组织与控制
-
线程控制块
与进程类似,系统也为每个线程配置一个线程控制块TCB,用于记录控制和管理线程的信息。线程控制块通常包括
- ①线程标识符
- ②一组寄存器,包括程序计数器、状态寄存器和通用寄存器
- ③线程运行状态,用于描述线程正处于何种状态
- ④优先级
- ⑤线程专有存储区,线程切换时用于保存现场等
- ⑥堆栈指针,用于过程调用时保存局部变量及返回地址等。
同一进程中的所有线程都完全共享进程的地址空间和全局变量。
各个线程都可以访问进程地址空间的每个单元,所以一个线程可以读、写或甚至清除另一个线程的堆栈。
-
线程的创建
用户程序启动时,通常仅有一个称为“初始化线程”的线程正在执行,其主要功能是用于创建新线程。
在创建新线程时,需要利用一个线程创建函数,并提供相应的参数,如指向线程主程序的入口指针、堆栈的大小、线程优先级等。线程创建函数执行完后,将返回一个线程标识符。
-
线程的终止
当一个线程完成自己的任务后,或线程在运行中出现异常而要被强制终止时,由终止线程调用相应的函数执行终止操作。
但是有些线程(主要是系统线程)一旦被建立,便一直运行而不会被终止。通常,线程被终止后并不立即释放它所占有的资源,只有当进程中的其他线程执行了分离函数后,被终止线程才与资源分离,此时的资源才能被其他线程利用。
被终止但尚未释放资源的线程仍可被其他线程调用,以使被终止线程重新恢复运行。
-
2.2 处理机调度
2.2.1 调度的概念
-
调度的基本概念
处理机调度是对处理机进行分配,即从就绪队列中按照一定的算法(公平、高效的原则)去选择一个进程并将处理机分配给它运行,以实现进程并发地执行。
-
调度对层次
一个作业从提交开始直到完成,要经历以下三级调度,如下图所示。
-
高级调度(作业调度)
内存空间有限时,无法将用户提交的作业全部放入内存,需要按一定的原则从外存的作业 后备队列 中挑选一个作业调入内存,并创建进程。
每个作业只调入一次,调出一次。作业调入时会建立PCB,调出时才撤销PCB。
作业:一个具体的任务
多道批处理系统中大多配有作业调度,而其他系统中通常不需要配置作业调度。
- 发生频率最低 外存→内存(面向作业)
-
中级调度(内存调度)
内存不够时,可将某些进程的数据调出外存。等内存空闲或者进程需要运行时,按照某种策略从 挂起队列 中选择合适的进程重新调入内存。
暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列。
- 外存→内存(面向进程)
-
低级调度(进程调度)
在内存中的按照某种策略从 就绪队列 中选取一个进程,将处理机分配给它。
- 发生频率高 内存→CPU
-
-
三级调度的联系
-
七状态模型
挂起和阻塞的区别: 两种状态都不获得 CPU 服务,但挂起状态将进程调到外存,而阻塞态还在内存中。
-
三层调度对比
要做什么 在哪调度 发生频率 对进程状态影响 高级调度
(作业调度)从后备队列中选择合适的作业
将其调入内存,并为其创建进程外存→内存
(面向作业)最低 无→创建态→就绪态 中级调度
(内存调度)从挂起队列中选择合适的进程
将其数据调回内存外存→内存
(面向进程)中等 挂起态→就绪态
阻塞挂起→阻塞态低级调度
(进程调度)从就绪队列中选择一个进程
为其分配处理机内存→CPU 最高 就绪态→运行态 -
三层调度联系
- 1)作业调度为进程活动做准备,进程调度使进程正常活动起来。
- 2)中级调度将暂时不能运行的进程挂起,中级调度处于作业调度和进程调度之间。
- 3)作业调度次数少,中级调度次数略多,进程调度频率最高。
- 4)进程调度是最基本的,不可或缺。
-
2.2.2 调度的目标
不同的调度算法具有不同的特性,在选择调度算法时,必须考虑算法的特性。评价标准如下。
-
CPU利用率:指CPU“忙碌”的时间占总时间的比例。
利用率 = 忙碌的时间 总时间 利用率=\frac{忙碌的时间}{总时间} 利用率=总时间忙碌的时间 -
系统吞吐率:单位时间内完成作业的数量。
系统吞吐率 = 总共完成了多少道作业 总共花了多少时间 系统吞吐率=\frac{总共完成了多少道作业}{总共花了多少时间} 系统吞吐率=总共花了多少时间总共完成了多少道作业 -
周转时间:指从作业被提交给系统开始,到作业完成为止的这段时间间隔。
周转时间 = 作业完成时间 − 作业提交时间 周转时间=作业完成时间-作业提交时间 周转时间=作业完成时间−作业提交时间
平均周转时间:指多个作业周转时间的平均值。
平均周转时间 = 各个作业周转时间之和 作业数 平均周转时间=\frac{各个作业周转时间之和}{作业数} 平均周转时间=作业数各个作业周转时间之和
带权周转时间:作业周转时间与作业实际运行时间的比值。带权周转时间必然≥1
带权周转时间 = 作业周转时间 作业实际运行时间 = 作业完成时间 − 作业提交时间 作业实际运行时间 带权周转时间=\frac{作业周转时间}{作业实际运行时间}=\frac{作业完成时间-作业提交时间}{作业实际运行时间} 带权周转时间=作业实际运行时间作业周转时间=作业实际运行时间作业完成时间−作业提交时间
平均带权周转时间:多个作业带权周转时间的平均值。
平均带权周转时间 = 各个作业带权周转时间之和 作业数 平均带权周转时间=\frac{各个作业带权周转时间之和}{作业数} 平均带权周转时间=作业数各个作业带权周转时间之和 -
等待时间
等待时间,指进程/作业处于等待处理机状态时间之和,等待时间越长,用户满意度越低。
等待时间 = 周转时间 − 运行时间 等待时间=周转时间-运行时间 等待时间=周转时间−运行时间-
对于进程来说,等待时间就是指进程建立后等待被服务的时间之和。
-
对于作业来说,不仅要考虑建立进程后的等待时间,还要加上作业在外存后备队列中等待的时间。
平均等待时间:各个进程/作业等待时间的平均值。
平均等待时间 = 各个进程 / 作业等待时间之和 进程 / 作业数 平均等待时间=\frac{各个进程/作业等待时间之和}{进程/作业数} 平均等待时间=进程/作业数各个进程/作业等待时间之和 -
-
响应时间:从用户提交请求到首次产生响应所用的时间。
2.2.3 调度的实现
-
调度程序(调度器)
用于调度和分派CPU 的组件称为调度程序,它通带由三部分组成,如图所示。
- 排队器:将系统中的所有就绪进程按照一定的策略排成一个或多个队列,以便于调度程序选择。每当有一个进程转变为就绪态时,排队器便将它插入到相应的就绪队列中。
- 分派器:依据调度程序所选的进程,将其从就绪队列中取出,将CPU分配给新进程。
- 上下文切换器:在对处理机进行切换时,会发生两对上下文的切换操作:
- 第一对,将当前进程的上下文保存到其PCB中,再装入分派程序的上下文,以便分派程序运行;
- 第二对,移出分派程序的上下文,将新选进程的CPU现场信息装入处理机的各个相应寄存器。
-
调度的时机
-
需要调度
- 主动放弃:进程正常终止;运行过程中发生异常而终止;主动阻塞(比如等待IO)
- 被动放弃:时间片用完;有更紧急的事情处理(I/O中断);有更高优先级的进程进入就结队列
-
不能调度
-
处理中断的过程中
-
进程在操作系统内核程序临界区中
-
原子操作过程中
-
临界资源:一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
临界区:访问临界资源的那段代码。
内核程序临界区一般是用来访问某种内核数据结构的,比如进程的就绪队列(由各就绪进程的PCB组成)
-
-
进程调度方式
-
非剥夺调度方式
又称非抢占方式。即,只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达,当前进程依然会继续使用处理机,直到该进程终止或主动要求进入阻塞态。
实现简单,系统开销小但是无法及时处理紧急任务,适合于早期的批处理系统
-
剥夺调度方式
又称抢占方式。当一个进程正在处理机上执行时,如果有一个更重要或更紧迫的进程需要使用处理机,则==立即暂停在执行的进程==,将处理机分配给更重要紧迫的那个进程。
可以优先处理更紧急的进程,也可实现让各进程按时间片轮流执行的功能(通过时钟中断)。适合于分时操作系统、实时操作系统
-
-
进程切换
-
上下文切换:切换CPU到另一个进程需要保存当前进程状态并恢复另一个进程的状态。
- 对原来运行进程各种数据的保存
- 对新的进程各种数据的恢复(如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息,这些信息一保存在进程控制块)
上下文:某一时刻CPU寄存器和程序计数器的内容。
切换流程:
- 挂起一个进程,保存CPU上下文,包括程序计数器和其他寄存器。
- 更新PCB信息。
- 把进程的PCB移入相应的队列,如就绪、在某事件阻塞等队列。
- 选择另一个进程执行,并更新其PCB。
- 跳转到新进程PCB中的程序计数器所指向的位置执行。
- 恢复处理机上下文。
-
上下文切换的消耗
上下文切换需要消耗大量CPU时间,有些处理器有多个寄存器组,则切换只需改变指针。
进程切换是有代价的,因此如果过于频繁的进行进程调度、切换,必然会使整个系统的效率降低,使系统大部分时间都花在了进程切换上,而真正用于执行进程的时间减少。
-
上下文切换与模式切换
-
模式切换是用户态和内核态之间的切换,CPU逻辑上可能还在执行同一进程。用户进程最开始都运行在用户态,若进程因中断或异常进入核心态运行,执行完后又回到用户态刚被中断的进程运行。
-
上下文切换切换了进程,只能发生在内核态,它是多任务操作系统中的一个必需的特性。
-
-
-
闲逛进程
调度程序永远的备胎,没有其他就绪进程时,运行闲逛进程(idle)
特性:
- 优先级最低;
- 可以是0地址指令,占一个完整的指令周期(指令周期末尾例行检查中断)
- 能耗低
闲逛进程不需要CPU之外的资源,它不会被阻塞。
-
两种线程的调度
- 用户级线程调度。由于内核并不知道线程的存在,所以内核还是和以前一样,选择一个进程,并给予时间控制。由进程中的调度程序决定哪个线程运行。
- 内核级线程调度。内核选择一个特定线程运行,通常不用考虑该线程属于哪个进程。对被选择的线程赋予一个时间片,如果超过了时间片,就会强制挂起该线程。
用户级线程的线程切换在同一进程中进行,仅需少量的机器指令;
内核级线程的线程切换需要完整的上下文切换、修改内存映像、使高速缓存失效,这就导致了若干数量级的延迟。
2.2.4 典型的调度算法
-
先来先服务(FCFS)
-
算法思想:主要从“公平”的角度考虑(类似于我们生活中排队买东西的例子)
-
算法规则:按照作业/进程到达的先后顺序进行服务
-
用于作业/进程调度:
- 用于作业调度时,考虑是哪作业先达后备队列;
- 用于进程调度时,考虑的是哪个进程先到达就绪队列
-
优缺点:
- 优点:公平、算法实现简单
- 缺点:排在长作业(进程)后面的短作业需要等待很长时间,带权周转时间很大,对短作业来说用户体验不好。即,FCFS算法对长作业有利,对作(Eg:排队。)
-
非抢占式的算法;不会导致饥饿
-
-
短作业优先(SJF)
-
算法思想:追求最少的平均等待时间,最少的平均周转时间、最少的平均平均带权周转时间
-
算法规则:最短的作业/进程优先得到服务(所谓“最短”,是指要求服务时间最短)
-
用于作业/进程调度
- 即可用于作业调度,也可用于进程调度。
- 用于进程调度时为"短进程优先"(SPF,Shortest Process First)
-
优缺点
- 优点:“最短的”平均等待时间、平均周转时间;
- 在所有进程都几乎同时到达时,采用SJF调度算法的平均等待时间、平均周转时间最少;
- “抢占式的短作业/进程优先调度算法(最短剩余时间优先,SRNT算法)的平均等待时间、平均周转时间最少”
- 缺点:不公平。对短作业有利,对长作业不利。可能产生饥饿现象。另外,作业进程的运行时间是由用户提供的,并不一定真实,不一定能做到真正的短作业优先。
- 优点:“最短的”平均等待时间、平均周转时间;
-
抢占式的算法;会导致饥饿
SJF和SPF是非抢占式的算法。但是也有抢占式的版本:最剩间优先算法(SRTN,Shortest Remaining Time Next)
每当有进程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行的进程剩余时间更短,则由新进程抢占处理机,当前运行进程重新回到就绪队列。另外,当一个进程完成时也需要调度
-
-
高响应比优先(HRRN)
-
算法思想:要综合考虑作业/进程的等待时间和要求服务的时间
-
算法规则:在每次调度时先计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务
响应比 = 等待时间 + 要求服务时间 要求服务时间 响应比=\frac{等待时间+要求服务时间}{要求服务时间} 响应比=要求服务时间等待时间+要求服务时间
高响应比优先算法:非抢占式的调度算法,只有当前运行的进程主动放CPU(常/常成,主动阻塞),需行调度,调度时计算所有就绪进程的响应比,选响应比最高的进程上处理机。 -
用于作业/进程调度:即可用于作业调度,也可用于进程调度
-
优缺点
- 综合考虑了等待时间和运行时间(要求服务时间)等待时间相同时,要求服务时间短的优先(SJF的优点);
- 要求服务时间相同时,等待时间长的优先(FCFS的优点)
- 对于长作业来说,随着等待时间越来越久,其响应比也会越来越大,从而避免了长作业饥饿的问题
-
非抢占式的算法;不会导致饥饿
非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时,才需要调度,计算响应比
-
-
时间片轮转调度算法(RR)
-
算法思想:公平地、轮流地为各个进程服务,让每个进程在一定时间间隔内都可以得到响应
-
算法规则:按照各进程到达就绪队列的顺序,轮流让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完,则剥夺处理机,将进程重新放到就绪队列队尾重新排队。
-
用于作业/进程调度:用于进程调度(只有作业放入内存建立了相应的进程后,才能被分配处理机时间片)
-
优缺点
- 优点:公平;响应快,适用于分时操作系统;
- 缺点:由于高频率的进程切换,因此有一定开销;不区分任务的紧急程度。
-
抢占式的算法;不会导致饥饿
若进程未能在时间片内运行完,将被强行剥夺处理机使用权,因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到
-
-
优先级调度算法
-
算法思想:随着计算机的发展,特别是实时操作系统的出现,越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
-
算法规则:每个作业/进程有各自的优先级,调度时选择优先级最高的作业/进程
-
用于作业/进程调度:既可用于作业调度,也可用于进程调度。甚至,还会用于在之后会学习的I/O调度中
-
优缺点
- 优点:用优先级区分紧急程度、重要程度,适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度
- 缺点:若源源不断地有高优先级进程到来,则可能导致饥饿
-
抢占式/非抢占式的算法;会导致饥饿
抢占式、非抢占式都有。做题时的区别在于:非抢占式只需在进程主动放弃处理机时进行调度即可,而抢占式还需在就绪队列变化时,检查是否会发生抢占。
-
优先级排序
系统进程优先级高于用户进程
前台进程优先级高于后台进程
操作系统更偏好I/O型进程(或称I/O繁忙型进程)
注:与I/O型进程相对的是计算型进程(或称CPU繁忙型程)
-
优先级分类:根据优先级是否可以动态改变,可将优先级分为静态优先级和动态优先级两种。
- 静态优先级:创建进程时确定,之后一直不变
- 动态优先级:创建进程时有一个初始值,之后会根据情况动态地调整优先级。
就绪队列未必只有一个,可以按照不同优先级来组织。另外,也可以把优先级高的进程排在更靠近队头的位置
-
-
多级队列调度算法
- 系统中按进程类型设置多个队列,进程创建成功后插入某个队列
-
队列之间可采取固定优先级,或时间片划分
-
固定优先级:高优先级空时低优先级进程才能被调度
-
时间片划分:如三个队列分配时间50%、40%、10%
-
-
各队列可采用不同的调度策略,如
系统进程队列采用优先级调度、交互式队列采用RR、批处理队列采用FCFS
-
多级反馈队列调度算法
-
算法思想:对其他调度算法的折中权衡
-
算法规则:
- 1.设置多级就绪队列,各级队列==优先级从高到低,时间片从小到大==
- 2.新进程到达时先进入第1级队列,按FCFS原则排队等待被分配时间片,若用完时间片进程还未结束,则进程进入下一级队列队尾。如果此时已经是在最下级的队列,则重新放回该队列队尾
- 3.只有第k级队列为空时,才会为k+1级队头的进程分配时间片
-
用于作业/进程调度:用于进程调度
-
优缺点
- 对各类型进程相对公平(FCFS的优点);
- 每个新到达的进程都可以很快就得到响应(RR优点);
- 短进程只用较少的时间就可完成(SPF优点);
- 不必实现估程运时间(避用户作假);
- 可灵活地调整对各类进程的偏好程度,比如CPU密集型进程、IO密集型进程
拓展:可以将因I/O而阻塞的进程重新放回原队列,这样I/O型进程就可以保持较高优先级
-
抢占式的算法;会导致饥饿
在k级队列的进程运行过程中,若更上级的队列(1~k-1级)中进入了一个新进程,则由于新进程处于优先级更高的队列中,因此新进程会抢占处理机,原来运行的进程放回k级队列队尾。
-
例:
-
(2019年408第27题)系统采用二级反馈队列调度算法进行进程调度。就绪队列Q1采用时间片轮转调度算法,时间片为10ms;就绪队列Q2采用短进程优先调度算法,系统优先调度Q1队列中的进程,当Q1为空时系统才会调度Q2中的进程;新创建的进程首先进入Q1;Q1中的进程执行一个时间片后,若未结束,则转入Q2。若当前Q1、Q2为空,系统依次创建进程P1、P2后即开始进程调度,P1、P2需要的 CPU 时间分别为 30ms 和 20ms,则进程P1、P2在系统中的平均等待时间为( 15ms )。
-
P1等待时间 = P1周转时间 - P1运行时间 = 50-30 = 20ms
-
P2等待时间 = P2周转时间 - P2运行时间 = 30-20 = 10ms
-
P1、P2在系统中的平均等待时间 = (P1等待时间+P2等待时间)/2 = 15ms
-
-
先来先服务 | 短作业优先 | 高响应比优先 | 时间片轮转 | 多级反馈队列 | |
---|---|---|---|---|---|
能否是可抢占 | 否 | 能 | 能 | 能 | 队列内算法不一定 |
能否是非抢占 | 能 | 能 | 能 | 否 | 队列内算法不一定 |
优点 | 公平,实现简单 | 平均等待时间最少,效率最高 | 兼顾长短作业 | 兼顾长短作业 | 兼顾长短作业, 有较好的的响应时间, 可行性强 |
缺点 | 不利于短作业 | 长作业会饥饿, 估计时间不易确定 | 计算响应比的开销大 | 平均等待时间较长, 上下文切换浪费时间 | 无 |
适用于 | 无 | 作业调度, 批处理系统 | 无 | 分时系统 | 相当通用 |
默认决策模式 | 非抢占 | 非抢占 | 非抢占 | 抢占 | 抢占 |
2.3 同步与互斥
2.3.1 同步与互斥的基本概念
-
临界资源:一次仅允许一个进程使用的资源
-
类型:物理设备,如打印机等;可被进程共享的许多变量、数据等
-
临界区:访问临界资源的那段代码。
为了保证临界资源的正确使用,可把临界资源的访问过程分成4个部分:
- 1)进入区。为了进入临界区使用临界资源,在进入区要检查可否进入临界区,若能进入临界区,则应设置正在访问临界区的标志,以阻止其他进程同时进入临界区。
- 2)临界区。进程中访问临界资源的那段代码,又称临界段。
- 3)退出区。将正在访问临界区的标志清除。
- 4)剩余区。代码中的其余部分。
do{ entry section; //进入区 critical section; //临界区 exit section; //退出区 remainder section; //剩余区 }while(true)
-
-
同步
-
同步亦称直接制约关系,它是指为完成某种任务而建立的两个或多个进程,这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
-
读进程和写进程并发地运行,由于并发必然导致异步性,因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中,又必须按照“写数据→读数据”的顺序来执行的。
如何解决这种异步问题,就是“进程同步”所讨论的内容。
-
-
互斥
互斥也称间接制约关系。当一个进程进入临界区使用临界资源,另一进程必须等待当占用临界资源的进程退出临界区后,另一进程才能访问此临界资源。
遵循原则:
- 空闲让进。临界区空闲时,可以允许一个请求进入临界区的进程立即进入临界区;
- 忙则等待。当已有进程进入临界区时,其他图进入临界区进必须等待
- 有限等待。对请求访问的进程,应保证能在有限时间内进入临界区(保证不会饥饿)
- 让权等待。当进程不能进入临界区时,应立即释放处理机,防止进程忙等待。
2.3.2 实现临界区互斥的基本方法
软件实现方法
-
单标志法(违背“空闲让进”原则)
两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。
该算法设置一个公用整型变量turn,用于指示被允许进入临界区的进程编号。
若某个进程不再进入临界区,则另一个 进程也将无法进入临界区(违背"空闲让进”)。
-
双标志法先检查(违背“忙则等待”原则)
在每一个进程访问临界区资源之前,先查看一下临界区资源是否正被访问,若正被访问,该进程需等待:否则,进程才进入自己自己的临界区。
设置一个布尔型数组flag[ ],数组中各个元素用来标记各进程想进入临界区的意愿,比如“flag[0]=ture”意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区,如果没有,则把自身对应的标志flag设为true,之后开始访问临界区。
-
优点:不用交替进入,可连续使用
-
缺点:按序列①⑤②⑥执行时,会同时进入临界区(违背“忙则等待”),Pi进程和Pj进程可能同时进入临界区;检查和修改操作不能一次进行。
-
-
双标志法后检查
双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”,但是这两个操作又无法一气呵成,因此导致了两个进程同时进入临界区的问题。因此,人们又想到先“上锁”后“检查”的方法,来避免上述问题。
- 缺点:当两个进程几乎同时都想进入临界区时,它们分别将自己的标志值设置为TRUE,并且同时检测对方的状态,发现对方也要进入临界区,于是双方互相谦让,结果谁也进不了临界区,从而导致“饥饿”现象。违背了“空闲让进”和“有限等待”产生饥饿
-
Peterson算法
结合双标志法、单标志法的思想。如果双方都争着想进入临界区,那可以让进程尝试“孔融让梨”(谦让)。做一个有礼貌的进程。
-
为了防止两个进程为进入临界区而无限期等待,又设置了变量turn,每个进程在先设置自己的标志后再设置turn标志。这时,再同时检测另一个进程状态标志和允许进入标志,以便保证两个进程同时要求进入临界区时,只允许一个进程进入临界区。
-
进程在进入区要做的步骤: ① 主动争取 ② 主动谦让 ③ 检查对方是否也想使用,且最后一次是不是自己说了客气话
-
存在问题:Peterson 算法用软件方法解决了进程互斥问题, 遵循 “空闲让进”、“忙则等待”、“有限等待” 三个原则,但是依然 未遵循 “让权等待” 的原则。
-
-
软件方法总结
单标志法 双标志先检查 双标志后检查 Peterson 算法 算法 在进入区只做“检查",不"上锁“
在退出区把临界区的使用权转交给另一个进程
(相当于在退出区既给另一进程"解锁",又给自己"上锁")在进入区先"检查"后"上锁",退出区"解锁“ 在进入区先"加锁"后"检查",退出区"解锁" 在进入区"主动争取一主动谦让一检查对方是否想进、已方是否谦让“ 问题 不遵循“空闲让进” 不遵循"忙则等待” 不遵循“空闲让进、有限等待”,可能导致“饥饿” 不遵循“让权等待”,会发生“忙等”
硬件实现方法
-
中断屏蔽方法
当一个进程正在使用处理机执行它的临界区代码时,要防止其他进程再进入其临界区访问的最简单的方法是:禁止一切中断发生,或称之为屏蔽中断、关中断。
关中断; 临界区; 开中断;
- 优点:简单、高效
- 缺点:不适用于多处理机;只适用于操作系统内核进程,不适用于用户进程(因为开/关中断指令只能运行在内核态,这组指令如果能让用户随意使用会很危险)
-
硬件指令法
-
TestAndSet指令
简称TS指令,也有地方称为TestAndSetLock指令,或TSL指令TSL指令是用硬件实现的。TS是原子操作,执行的过程不允许被中断,只能一气呵成。以下是用C语言描述的逻辑。
相比软件实现方法,TSL 指令把 上锁和检查操作 用硬件的方式变成了一气呵成的 原子操作 。
- 优点: 实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞。适用于多处理机环境。
- 缺点: 不满足 “让权等待” 原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致 忙等。
-
Swap指令
有的地方也叫Exchange指令,或简称XCHG指令。Swp指令是用硬件实现的,是原子操作,执行的过程不允许被中断,只能一气呵成。
逻辑上来看 Swap 和 TSL 并无太大区别,都是先记录下此时临界区是否已经被上锁(记录在 old 变量上),再将上锁标记 lock 设置为 true,最后检查 old,如果 old 为 false 则说明之前没有别的进程对临界区上锁,则可跳出循环,进入临界区。Swap 指令优点缺点和TSL指令相同。
- 硬件方法的优点
- 适用于任意数目的进程,不管是单处理机还是多处理机;简单、容易验证其正确性。
- 可以支持进程内有多个临界区,只需为每个临界区设立一个布尔变量。
- 硬件方法的缺点
- 进程等待进入临界区时要耗费处理时间,不能实现让权等待。
- 从等待进程中随机选择一个进入临界区,有进程可能一直选不上,从而导致“饥饿”现象。
-
2.3.3 互斥锁
解决临界区最简单的工具就是互斥锁(mutex lock)。一个进程在进入临界区时获得锁;在退出临界区时释放锁。函数acquire()获得锁,而函数release()释放锁。acquire()和release()是原子操作,由硬件机制完成。
每个互斥锁有一个布尔变量available,表示锁是否可用。如果锁是可用的,调用acquire()会成功,且锁不再可用。当一个进程试图获取不可用的锁时,会被阻塞,直到锁被释放。
acquire(){
while(!available); //忙等待
avilable = false; //获得锁
}
release(){
available = true; //释放锁
}
- 优点:等待期间不用切换进程上下文,多处理器系统中,若上锁的时间短,则等待代价很低
- 缺点:需忙等,进程时间片用完才下处理机,违反“让权等待”;不太适用于单处理机系统,忙等的过程中不可能解锁
2.3.4 信号量
信号量机制是一种功能较强的机制,可用来解决互斥与同步问题,它只能被两个标准的原语wait(S)和signal(S)访问,也可记为“P操作"和"V操作”。
信号量其实就是一个变量(可以是一个整数,也可以是更复杂的记录型变量),可以用一个信号量来表示系统中某种资源的数量,比如:系统中只有一台打印机,就可以设置一个初值为1的信号量。
原语是一种特殊的程序段,其执行只能一气呵成,不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”,因此如果能把进入区、退出区的操作都用“原语”实现,使这些操作能“一气呵成”就能避免问题。
-
整型信号量
用一个整数型的变量作为信号量,用来表示系统中某种资源的数量。wait(S)、signal(S)可描述为:
与普通整数变量的区别:对信号量的操作只有三种,即初始化、P操作、V操作
wait(S) 原语,“检查”和“上锁”一气呵成,避免了并发、异步导致的问题。以申请使用打印机举例:
存在的问题: 不满足 “让权等待” 原则,会发生 忙等。
-
记录型信号量
整型信号量存在“忙等”问题,因此人们又提出了“记录型信号量”,即用记录型数据结构表示的信号量。
除了需要用于代表资源数目的整型变量value外,再增加一个进程链表L,用于链接所有等待该资源的进程。
- wait:如果剩余资源数不够使用block原语使进程从运行态进入阻塞态,并把挂到信号量S的等待队列(即阻塞队列)中。
- signal:释放资源后,若还有别的进程在等待这种资源,则使用wakeup原语唤醒等待队列中的一个进程,该进程从阻塞态变为就绪态。
- S.value的初值表示系统中某种资源的数目。
- P操作:
- 对信号量S的一次P操作意味着进程请求一个单位的该资源,因此需要执行S.value-,表示资源数减1
- 当S.value<0时表示该类资源已分配完毕,因此进程应调用bock原语进行自我阻塞(当前运行的进程从运行态→阻塞态),主动放弃处理机,并插入该类资源的等待队列S.L中。
- 可见,该机制遵循了“让权等待”原则,不会出现“忙等”现象。
- V操作:
- 对信号量S的一次V操作意味进程释放一个单位的该资源,因此需要执行S.value.+,表示资源数加1,
- 若加1后仍是S.value<=0,表示依然有进程在等待该类资源,因此应调用wakeup原语唤醒等待队列中的第一个进程(被唤醒进程从阻塞态→就绪态)
例:某计算机系统中有1台打印机,则可在初始化信号量 S 时将 S.value 的值设为 1,队列 S.L 设置为空。
① CPU 为 P0 服务,S.value --,值为 0,P0开始使用打印机。
② CPU 为 P1 服务,S.value --,值为 -1,无资源执行 block 原语( wait原语 )。阻塞队列( P1 ),S.value = -1 说明有1个进程在等待资源。
③ CPU 为 P2 服务,S.value --,值为 -2,无资源执行 block 原语。阻塞队列( P1→P2 ),S.value = -2 说明有2个进程在等待资源。
④ CPU 为 P0 服务,S.value ++,S.value = -1 ≤ 0,说明有进程在等待该资源。因此应调用 wakeup 原语(signal原语)唤醒等待队列中的第一个进程P1,将释放资源给 P1,P1从阻塞态变为就绪态,等待被 CPU 服务(CPU顺序执行)。阻塞队列( P2 )
⑤ CPU 为 P1 服务,P1 使用完打印机,S.value ++,S.value = 0,调用 wakeup 原语唤醒 P2。阻塞队列()。
⑥ CPU 为 P2 服务, P2是用完打印机,S.value ++,S.value = 1。 -
信号量机制实现进程互斥
-
伪代码如下所示:
设 S 为实现进程 P1、P2 互斥的信号量,由于只允许一个进程进入临界区,所以 S 的初值应设为 1。然后把临界区置于 P(S) 和 V(S) 之间,进入区之前申请资源(P操作),退出区之前释放资源( V操作 ),即可实现两个进程对临界资源的互斥访问。
-
操作:
- 1.分析并发进程的关键活动,划定临界区(如:对临界资源打印机的访问就应放在临界区)
- 2.设置互斥信号量mutex,初值为1
- 3.在进入区P(mutex)一一申请资源
- 4.在退出区V(mutex)一一释放资源
-
注意
- 对不同的临界资源需要设置不同的互斥信号量。
- P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放,等待进程永不被唤醒。
-
-
信号量机制实现进程同步
进程同步要让各并发进程按要求有序地推进。
-
程序
保证了代码4一定是在代码2之后执行。
-
步骤:先V后P,后V前P
- 1.分析什么地方需要实现“同步关系”,即必须保证“一前一后”执行的两个操作(或两句代码)
- 2.设置同步信号量S,初始为0
- 3.在==“前操作”之后==执行V(S)
- 4.在==“后操作”之前==执行P(S)
-
注意
- 若先执行到V(S)操作,则S+后S=1。之后当执行到P(S)操作时,由于S=1,表示有可用资源,会执行S-,S的值变回0,P2进程不会执行block原语,而是继续往下执行代码4。
- 若先执行到P(S)操作,由于S=0,S-后S=-1,表示此时没有可用资源,因此P操作中会执行bock原语,主动请求阻塞;当执行完代码2,继而执行V(S)操作,S+,使S变回0,由于此时有进程在该信号量对应的阻塞队列中,因此会在V操作中执行wakeup原语,唤醒P2进程。这样P2就可以继续执行代码4
-
-
信号量机制实现前驱关系
分析问题,画出前驱图,把每一对前驱关系都看成一个同步问题
-
问题:下图是一个前驱图,其中 S1, S2, S3, … ,S6 是进程 P1, P2, P3,…, P6 中的程序段,这些程序段要求按如下前驱图所示的顺序来执行:
-
代码:
-
操作:
- 1.要为每一对前驱关系各设置一个同步信号量
- 2.在“前操作”之后对相应的同步信号量执行V操作
- 3.在“后操作”之前对相应的同步信号量执行P操作
-
-
同步、互斥信号量总结
注:互斥信号量初值一般为1,同步信号量的初始值要看对应资源的初始值是多少。
2.3.5 管程
-
引入管程原因
管程的引入让程序员写程序时不需要再关注复杂的PV操作,从而避免了传统信号量机制存在的很多问题。
-
定义:由一组数据及定义在这组数据之上的对这组数据的操作组成的软件模块,这组操作能初始化并改变管程中的数据和同步进程。
-
管程的组成
- 局部于管程的共享数据结构说明
- 对该数据结构进行操作的一组过程(函数)
- 对局部于管程的共享数据设置初始值的语句
- 管程的名字
monitor Demo{//定义一个名称为"Demo"的管程 //定义共享数据结构,对应系统中的某种共享资源 共享数据结构 S; //对共享数据结构初始化的语句 init_code(){ S=5; //初始资源数等于5 } //过程1:申请一个资源 take_away(){ 对共享数据结构x的一系列处理; s--; //可用资源-1 ... } //过程2:归还一个资源 give_back(){ 对共享数据结构x的一系列处理; s++; //可用资源+1 ... } }
-
管程的基本特征
- 局部于管程的数据只能被局部于管程的过程所访问
- 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
- 每次仅允许一个进程在管程内执行某个内部过程
注:过程其实就是函数,如下面这个 People 类,People 是管程的名字,username 和 str 是局部于管程的共享数据结构,login 方法是该数据结构进行操作的过程。
public class People{ private String username = "admin"; // 用户名 private String str= "123456"; // 密码 public void login(){ if("admin".equals(username) && "123456".equals(str)){ System.out.println("登录成功!"); } } }
-
条件变量
条件变量condition,是表示管程阻塞原因的变量。
通常,一个进程被阻塞的原因可以有多个,因此在管程中设置了多个条件变量。每个条件变量保存了一个等待队列,用于记录因该条件变量而阻塞的所有进程,对条件变量只能进行两种操作,即wait和signal。
- x.wait:当x对应的条件不满足时,正在调用管程的进程调用x.wait将自己插入x条件的等待队列,并释放管程。此时其他进程可以使用该管程。
- x.signal:x对应的条件发生了变化,则调用x.signal,唤醒一个因x条件而阻塞的进程。
monitor Demo{ 共享数据结构 S; condition x; //定义一个条件变量x init_code(){...} take_away(){ if(S<0) x.wait(); //资源不够,在条件变量x上阻塞等待 资源足够,分配资源,做一系列处理; } give_back(){ 归还资源,做一系列相应处理; if(有进程在等待)x.signal(); //唤醒一个阻塞进程 } }
- 条件变量和信号量的比较:
- 相似点:条件变量的wait/signal操作类似于信号量的P/V操作,可以实现进程的阻塞/唤醒。
- 不同点:条件变量是“没有值”的,仅实现了“排队等待”功能;而信号量是“有值”的,信号量的值反映了剩余资源数,而在管程中,剩余资源数用共享数据结构记录。
2.3.6 经典同步问题
-
生产者-消费者问题
-
问题描述
系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用。(注:这里的“产品”理解为某种数据)
生产者、消费者共享一个初始为空、大小为n的缓冲区。
-
只有缓冲区没满时,生产者才能把产品放入缓冲区,否则必须等待。
-
只有缓冲区不空时,消费者才能从中取出产品,否则必须等待。
缓冲区是临界资源,各进程必须互斥地访问。
-
-
问题分析
-
1.关系分析。找出题目中描述的各个进程,分析它们之间的同步、互斥关系。
同步关系:缓冲区没满,生产者生产;缓冲区没空,消费者消费。
互斥关系:各进程互斥访问缓冲区。
-
2.整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
-
3.设置信号量。并根据题目条件确定信号量初值。(互斥信号量初值一般为1,同步信号量的初始值要看对应资源的初始值是多少)
semaphore mutex = 1; //互斥信号量,实现对缓冲区的互斥访问 semaphore empty = n; //同步信号量,表示空闲缓冲区的数量 semaphore full = 0; //同步信号量,表示产品的数量,也即非空缓冲区的数量
-
-
进程描述
-
能否改变相邻P、V操作的顺序?
不能,会发生死锁
若此时缓冲区内已经放满产品,则 empty=0,full=n。则生产者进程执行 ① 使mutex变为0,再执行②,由于已没有空闲缓冲区,因此生产者被阻塞。由于生产者阻塞,因此切换回消费者进程。消费者进程执行 ③,由于 mutex 为 0,即生产者还没释放对临界资源的 “锁”,因此消费者也被阻塞。生产者和消费者循环等待被对方唤醒,出现 死锁。
因此 实现互斥的 P 操作一定要在实现同步的 P 操作之后。
V 操作不会导致进程阻塞,因此 两个 V 操作顺序可以交换。
-
能否只设置一个同步信号量
不能。原因在于:两个信号量 empty 和 full,其中 empty 用于制约生产者生产,full 用于制约消费者消费。如果只设置一个信号量,如 full,那么生产者会无限的生产,起不到制约作用。
-
-
多生产者多消费者问题
-
问题描述
桌子上有一只盘子,每次只能向其中放入一个水果。爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,儿子专等着吃盘子中的橘子,女儿专等着吃盘子中的苹果。只有盘子空时,爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时,儿子或女儿可以从盘子中取出水果。
-
问题分析
-
1.关系分析
同步关系:① 父亲将苹果放入盘子,女儿才能取苹果;
② 母亲将句子放入盘子,儿子才能取橘子;
③ 只有盘子为空,父亲或者母亲才能放水果。
互斥关系:对缓冲区(盘子)的访问要互斥的进行。 -
2.整理思路
注:盘子为空这个事件可由儿子或者女儿触发,发生后父亲或母亲才可放水果。
分析同步要以 事件 的角度分析,不要以 进程 的角度分析。 -
3.信号量的设置
semaphore mutex = 1; //实现互斥访问盘子(缓冲区) semaphore apple = 0; //盘子中有几个苹果 semaphore orange = 0; //盘子中有几个橘子 semaphore plate = 1; //盘子中还可以放多少个水果
-
-
进程描述
-
能否不用互斥信号量
如果缓冲区大小为1,在任何时刻,apple、orange、plate 三个信号量中最多只有一个是1。因此在任何时刻,最多只有一个进程的P操作不会被阻塞,并顺利地进入临界区。
如果缓冲区大小大于1,数据可能存在相互覆盖的情况。如:父亲在向盘子放橘子的同时,母亲也可以往盘子里放橘子,有可能导致两个进程写入缓冲区的数据相互覆盖的情况。
因此,当缓冲区大小等于1,有可能不设置互斥变量。当缓冲区大小大于1,必须设置互斥变量。是否不用设置互斥信号量主要观察,同一时刻信号量是否最多一个1,建议设置互斥信号量。但需要注意的是,实现互斥的P操作一定要在实现同步的P操作之后,否则可能引起“死锁”。
-
分析
在分析同步问题(一前一后问题)的时候不能从单个进程行为的角度来分析,要把“一前一后”发生的事看做是两种“事件”的前后关系。
如果从 单个进程的角度 来考虑的话,会有以下结论:
- ① 如果盘子里装有苹果,那么一定要女儿取走苹果后父亲或母亲才能再放入水果;
- ② 如果盘子里装有橘子,那么一定要儿子取走橘子后父亲或母亲才能再放入水果。
这就意味着要 设置四个同步信号量 分别实现这 四个一前一后的关系,较为复杂。
若从 事件的角度 来考虑,我们可以把上述四对进程行为的前后关系抽象为 一对事件 的前后关系,即:盘子变空事件 → 放入水果事件。
-
-
读者-写者问题
-
问题描述
有读者和写者两组并发进程,共享一个文件,当两个或两个以上的读进程同时访问共享数据时不会产生副作用,但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求:
- ①允许多个读者可以同时对文件执行读操作
- ②只允许一个写者往文件中写信息
- ③任一写者在完成写操作之前不允许其他读者或写者工作
- ④写者执行写操作前,应让已有的读者和写者全部退出
-
问题分析
- 两类进程:写进程、读进程
- 互斥关系:写进程一写进程、写进程一读进程。读进程与读进程不存在互斥问题
-
进程描述
-
方案1
方案设置 rw 和 mutex 两个信号量。rw 信号量 用于实现 读进程与写进程、写进程与写进程 对共享文件的互斥访问。mutex 信号量 用于保证对 count 变量的互斥访问。
若没有设置 mutex 信号量,两个读进程并发执行到 if 条件且都满足,都会执行 P(rw),会造成其中一个读进程阻塞的情况。设置 mutex 信号量,使得 count 信号量的检查和赋值操作一气呵成,保证了对 count 信号量访问的互斥性。
方案 1 存在的问题: 只要有读进程还在读,写进程就要一直阻塞等待,可能 “饿死”。因此,这种算法中,读进程是优先的。
-
方案2
方案 2 是对方案 1 问题的修正,添加了 w 信号量,保证了 读写公平 。如:假设对共享文件的访问顺序是:读者1→读者2→ 写者1 → 读者3 ,读者 2 执行完后,写者 1 将会进行写文件,读者 3 进程将会被阻塞。待写者1写完文件后,读者 3 进行读写者 1 访问后的文件。
算法 核心思想 在于设置了一个 计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程,从而做出不同的处理。另外,还需考虑 count 变量的互斥性。
-
-
结论
在这种算法中,连续进入的多个读者可以同时读文件;写者和其他进程不能同时访问文件;写者不会饥饿,但也并不是真正的“写优先”,而是相对公平的先来先服务原则。
有的书上把这种算法称为“读写公平法”
-
-
哲学家进餐问题
-
问题描述
一张圆桌上坐着5名哲学家,每两个哲学家之间的桌上摆一根筷子,桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐,哲学家在思考时,并不影响他人。只有当哲学家饥饿时,才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上,则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐,当进餐完毕后,放下筷子继续思考。
-
问题分析
-
1.关系分析
系统中有5个哲学家进程,5位哲学家与左右邻居对其中间筷子的访问是互斥关系。
-
2.整理思路
哲学家进餐问题中 只有互斥关系,但与之前遇到的问题不同点在于,每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象,是哲学家问题的关键。
-
3.信号量的设置
定义互斥信号量数组 chopstick[5]={1,1,1,1,1} 用于实现对 5 个筷子的互斥访问。并对哲学家按0~4编号,哲学家 i 左边的筷子编号为 i,右边的筷子编号为 (i+1)%5。此外,还需要设置 互斥信号量mutex,用以保证哲学家进程左右两支筷子都可用。
-
-
进程描述
算法保证,一个哲学家再拿到筷子拿到一半时被阻塞,也不会有别的哲学家尝试拿筷子,即至少有一个哲学家进程不阻塞。
其他方案:
① 对哲学家进程施加一些限制条件,如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。
② 要求奇数号哲学家先拿左边的筷子,然后再拿右边的筷子,而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭,那么只会有其中一个可以拿起第一只筷子,另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。
-
-
吸烟者问题
-
问题描述
假设一个系统有 三个抽烟者进程 和 一个供应者进程。每个抽烟者不停地卷烟并抽掉它,但是要卷起并抽掉一支烟,抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中,第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料,供应者每次将两种材料放桌子上,拥有剩下那种材料的抽烟者卷一根烟并抽掉它,并给供应者进程一个信号告诉完成了,供应者就会放另外两种材料在桌上,这个过程一直重复(让三个抽烟者轮流地抽烟)。
-
问题分析
-
1.关系分析
同步关系:① 桌上有组合一,第一个抽烟者取走东西
② 桌上有组合二,第二个抽烟者取走东西
③ 桌上有组合三,第三个抽烟者取走东西
④ 抽烟者抽完发出完成信号,供应者将下一个组合放到桌上
互斥关系:对缓冲区的访问要互斥的进行。 -
2.整理思路
注:由于缓冲区大小为1,任意时刻同步信号量和互斥信号量最多只有一个1,因此互斥信号量可以不设置。
-
3.信号量的设置
semaphore offer1 = 0; //桌上组合一的数量 semaphore offer2 = 0; //桌上组合二的数量 semaphore offer3 = 0; //桌上组合三的数量 semaphore finish = 0; //抽烟是否完成 int i = 0; //用于实现“三个抽烟者轮流抽烟”
-
-
进程描述
-
能否从进程角度思考?
不可以。
同多生产者多消费者问题,假设从进程角度思考,那么第一个抽烟者抽完后,供应者再将第一个组合放到桌上;第二个抽烟者抽完后,供应者再将第二个组合放到桌上;第三个抽烟者抽完后,供应者再将第三个组合放到桌上。这样相比于从事件考虑的一个一前一后的关系,多出了多个关系,并且较为复杂。因此要从事件的角度思考 PV 关系。
-
2.4 死锁
2.4.1 死锁的概念
-
死锁的定义
在并发环境下,各进程因竞争资源而造成的一种互相等待对方手里的资源,导致各进程都阻塞,都无法向前推进的现象,就是“死锁”。发生死锁后若无外力干涉这些进程都将无法向前推进。
-
死锁、饥饿、死循环的区别
-
共同点:都是进程无法顺利向前推进的现象(故意设计的死循环除外)
-
区别:
-
死锁:各进程互相等待对方手里的资源,导致各进程都阻塞,无法向前推进的现象。两个以上程序
-
饥饿:由于长期得不到想要的资源,某进程无法向前推进的现象。单个程序
比如:在短进程优先(SPF)算法中,若有源源不断的短进程到来,则长进程将一直得不到处理机,从而发生长进程“饥饿”
-
死循环:某进程执行过程中一直跳不出某个循环的现象。
有时是因为程序逻辑bug导致的,有时是程序员故意设计的。
-
-
-
死锁产生原因
-
对系统资源的竞争
各进程对不可剥夺的资源(如打印机)的竞争可能引起死锁,对可剥夺的资源(CPU)的竞争是不会引起死锁的。
-
进程推进顺序非法
请求和释放资源的顺序不当,也同样会导致死锁。例如,并发执行的进程P1、P2分别申请并占有了资源R1、R2,之后进程P1又紧接着申请资源R2,而进程P2又申请资源R1,两者会因为申请的资源被对方占有而阻塞,从而发生死锁。
-
信号量的使用不当也会造成死锁
如生产者-消费者问题中,如果实现互斥的P操柞在实现同步的P操作之前,就有可能导致死锁。(可以把互斥信号量、同步信号量也看做是一种抽象的系统资源)
-
-
死锁产出的必要条件
产生死锁 必须同时满足以下四个条件,只要其中任一条件不成立,死锁就不会发生。
- ① 互斥条件:只有对必须 互斥使用的资源的争抢 才会导致死锁(如哲学家的筷子、打印机设备)。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的(因为进程不用阻塞等待这种资源)。
- ② 不剥夺条件:进程所获得的资源在未使用完之前,不能由其他进程强行夺走,只能主动释放。
- ③ 请求和保持条件:进程已经 保持了至少一个资源,但又提出了新的资源请求,而该资源又被其他进程占有,此时请求进程被阻塞,但又对自己已有的资源保持不放。
- ④ 循环等待条件:存在一种进程资源的 循环等待链,链中的每一个进程已获得的资源同时被下一个进程所请求。
注:发生死锁时一定有循环等待,但是发生循环等待时未必死锁,即 循环等待是死锁的必要不充分条件。
如果同类资源数大于1,则即使有循环等待,也未必发生死锁(如上图 Pn 可以同时请求 P1 或者 Pk 的资源,得到 Pk 资源后,不会发生死锁)。 但如果系统中每类资源都只有一个,那循环等待就是死锁的充分必要条件了。
-
死锁处理策略
- 死锁预防。设置某些限制条件,破坏产生死锁的4个必要条件中的一个或几个。
- 避免死锁。在资源的动态分配过程中,用某种方法防止系统进入不安全状态。
- 死锁的检测及解除。无须采取任何限制性措施,允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生,然后采取某种措施解除死锁。
死锁的几种处理策略的比较见下表。
资源分配策略 各种可能模式 主要优点 主要缺点 死锁预防 保守,宁可资源闲置 一次请求所有资源,资源剥夺,资源按序分配 适用于突发式处理的进程,不必进行剥夺 效率低,进程初始化时间延长;剥夺次数过多;不便灵活申请新资源 死锁避免 是“预防”和“检测”的折中(在运行时判断是否可能死锁) 寻找可能的安全允许顺序 不必进行剥夺 必须知道将来的资源需求;进程不能被长时间阻塞 死锁检测 宽松,只要允许就分配资源 定期检查死锁是否已经发生 不延长进程初始化时间,允许对死锁进行现场处理 通过剥夺解除死锁,造成损失
2.4.2 死锁预防
死锁的产生必须满足四个必要条件,只要其中一个或者几个条件不满足,死锁不会发生。
-
破坏互斥条件
把只能互斥使用的资源改造为允许共享使用,则系统不会进入死锁状态。如: SPOOLing技术。使用 SPOOLing 技术可以把 独占设备在逻辑上改造成共享设备。比如,用SPOOLing技术将打印机改造为共享设备…
-
破坏不剥夺条件
-
提供两种方案:
-
① 申请资源得不到时,主动释放所占有资源。
-
② 申请资源被其他进程占用时,由 OS 协助剥夺。
-
-
策略的缺点:
- 实现起来比较复杂;
- 释放已获得的资源可能造成前一阶段工作的失效,因此这种方法一般只适用于易保存和恢复状态的资源,如CPU;
- 反复地申请和释放资源会增加系统开销,降低系统吞吐量;
- 方案 ① 可能导致进程饥饿。
-
-
破坏请求和保持条件
采用 静态分配方法,即进程 在运行前一次申请完它所需要的全部资源,在它的资源未满足前,不让它投入运行。一旦投入运行后,这些资源就一直归它所有,该进程就不会再请求别的任何资源了。
策略的缺点: 进程在整个运行期间都一直保持着所有资源,就会造成严重的资源浪费,资源利用率极低。另外,该策略也有 可能导致某些进程饥饿。
-
破坏循环等待条件
采用 顺序资源分配法。首先给系统中的资源编号,要求进程只能按编号递增顺序请求资源。
原理分析: 一个进程只有已占有小编号的资源时,才有资格申请更大编号的资源。按此规则,已持有大编号资源的进程不可能逆向地回来申请小编号的资源,从而就不会产生循环等待的现象(类比拓扑排序)。
策略的缺点: 不方便增加新的设备,因为可能需要重新分配所有的编号;进程实际使用资源的顺序可能和编号递增顺序不一致,会导致资源浪费;必须按规定次序申请资源,用户编程麻烦。
2.4.3 死锁避免
死锁的避免是在资源动态分配过程中,防止系统进入不安全状态,以避免发生死锁。
-
系统安全状态
-
安全序列:是指如果系统按照这种序列分配资源,则每个进程都能顺利完成。
-
安全状态:系统如果存在安全序列,则处于安全状态,安全状态一定不发生死锁。安全序列可能有多个。
-
不安全状态:如果分配了资源之后,系统中找不出任何一个安全序列,系统就进入了不安全状态。可能发生死锁(处于不安全状态未必就是发生了死锁,但发生死锁时一定是在不安全状态)
安全序列的计算方法:
已知现有三个进程的资源分配表如下(可用代表系统还剩有 3 个资源),现假设可用资源每次分配都是全部分配,并且分配给进程的资源总数应满足进程最多还需求的资源数目(如:可用资源有 3 个,由于 P2 进程还需要 2 个资源,因此只能满足 P2),分配完后回收该进程所拥有的全部资源。
计算步骤如下:
因此得到安全序列是 {P2, P1, P3}。
如果计算到 P3 时,可用资源无法满足 P3 的最大需求,即还需要的资源数目多于可用资源数目,那么就不存在安全序列。
注:死锁状态一定是不安全状态,不安全状态不一定是死锁状态,即:死锁状态 ⇒ 不安全状态。
如:A 进程需 10 个资源,而可用资源有 5 个。若 A 还未提出申请,则不会进入死锁状态。
系统进入不安全状态后,便可能进入死锁状态;反之,只要系统处于安全状态,系统变可避免进入死锁。
-
-
银行家算法
核心思想: 在分配资源前,预先判断这次分配是否会导致系统进入不安全状态,以此来决定是否答应资源分配请求,从而使得系统避免死锁。
-
数据结构描述:
- ①可利用资源向量 A v a i l a b l e Available Available(一维数据)
- ②最大需求矩阵 M a x Max Max
- ③分配矩阵 A l l o c a t i o n Allocation Allocation
- ④需求矩阵 N e e d Need Need
其中, N e e d = M a x − A l l o c a t i o n Need=Max-Allocation Need=Max−Allocation
注: A v a i l a b l e ( A , B , C ) = ( 3 , 3 , 2 ) Available(A,B,C)=(3,3,2) Available(A,B,C)=(3,3,2)代表可用的 A 类资源数目有 3 个,B 类资源数目有3个,C 类资源数目有 2 个。
-
银行家算法描述
设 R e q u e s t i Request_i Requesti是进程Pi的请求向量, R e q u e s t i [ j ] = K Request_i[j]=K Requesti[j]=K表示进程 P i Pi Pi需要 j j j类资源 K K K个。
-
①若 R e q u e s t i [ j ] ≤ N e e d [ i , j ] Request_i[j]≤Need[i,j] Requesti[j]≤Need[i,j],检查此次申请是否超过最多还需求数。
-
②若 R e q u e s t i [ j ] ≤ A v a i l a b l e [ j ] Request_i[j]≤Available[j] Requesti[j]≤Available[j],检查系统的可用资源是否还能满足此次需求。
-
③系统试探着把资源分配给 P i Pi Pi,并修改下面数据结构的数值:
A v a i l a b l e = A v a i l a b l e − R e q u e s t i Available=Available-Request_i Available=Available−Requesti,修改i进程剩余可用资源数
A l l o c a t i o n [ i , j ] = A l l o c a t i o n [ i , j ] + R e q u e s t i [ j ] Allocation[i,j]=Allocation[i,j]+Request_i[j] Allocation[i,j]=Allocation[i,j]+Requesti[j],i进程已分配资源数加上本次请求资源数
N e e d [ i , j ] = N e e d [ i , j ] − R e q u e s t i [ j ] Need[i,j]=Need[i,j]-Request_i[j] Need[i,j]=Need[i,j]−Requesti[j],i进程还需的资源数减去本次请求的资源数
-
④执行安全性算法,检查系统是否处于安全状态,即检查当前系统是否存在安全序列。
若系统安全,才正式将资源分配给 P i Pi Pi;否则此次试探分配作废,恢复原来分配状态。
注:安全性算法是银行家算法的核心。
-
-
安全性算法描述
设置工作向量 W o r k Work Work,表示系统中剩余可用资源数目。算法执行开始时, W o r k = A v a i l a b l e Work=Available Work=Available
- ①初始时安全序列为空。
- ②检查当前的剩余资源是否能满足某个进程的最大需求。如果可以就将它加入安全序列;若找不到执行步骤④
- ③把该进程持有资源全部回收,返回步骤②
- ④若此时安全序列中已有所有进程,则系统处于安全状态,否则处于不安全状态。
-
例题
假设当前系统中资源分配和剩余情况如下表所示,现 P 1 P1 P1发出请求向量 R e q u e s t 1 ( 1 , 0 , 2 ) Request_1(1,0,2) Request1(1,0,2),判断此次请求是否分配成功。
-
① 系统按银行家算法进行检查:
R e q u e s t 1 ( 1 , 0 , 2 ) ≤ N e e d 1 ( 1 , 2 , 2 ) Request_1(1,0,2)≤Need_1(1,2,2) Request1(1,0,2)≤Need1(1,2,2), R e q u e s t 1 ( 1 , 0 , 2 ) ≤ A v a i l a b l e ( 3 , 2 , 2 ) Request_1(1,0,2)≤Available(3,2,2) Request1(1,0,2)≤Available(3,2,2)
此次申请未超过 P 1 P1 P1进程最多还需求数,并且当前可用资源数可满足此次申请,则可试探的为 P 1 P1 P1分配资源,并修改:
A v a i l a b l e = A v a i l a b l e − R e q u e s t 1 = ( 2 , 3 , 0 ) Available=Available-Request_1=(2,3,0) Available=Available−Request1=(2,3,0)
A l l o c a t i o n 1 = A l l o c a t i o n 1 + R e q u e s t 1 = ( 3 , 0 , 2 ) Allocation_1=Allocation_1+Request_1=(3,0,2) Allocation1=Allocation1+Request1=(3,0,2)
N e e d 1 = N e e d 1 − R e q u e s t 1 = ( 0 , 2 , 0 ) Need_1=Need_1-Request_1=(0,2,0) Need1=Need1−Request1=(0,2,0) -
② 系统执行安全性算法检查安全状态:
令 W o r k = A v a i l a b l e = ( 2 , 3 , 0 ) Work=Available=(2,3,0) Work=Available=(2,3,0),执行安全性算法,如下表所示:
由安全性检查而知,可以找到一个安全序列 { P1, P3, P4, P0, P2 },因此系统是安全的,可以将P1所申请的资源分配给他。
王道书解法:
-
-
2.4.4 死锁检测和解除
如果系统既不采取预防死锁的措施,也不采取避免死锁的措施,系统就很可能发生死锁。在这种情况下,系统应当提供死锁检测和解除的手段。
-
资源分配图
系统死锁可利用 资源分配图 来描述。圆代表一个进程,框代表一类资源,框中一个圆代表一类资源中的一个资源。
- 两种结点:
- 进程结点:对应一个进程
- 资源结点:对应一类资源,一类资源可能有多个
- 两种边:
- 请求边:表示进程想申请几个资源(每条边代表一个)
- 分配边:表示已经为进程分配了几个资源(每条边代表一个)
- 两种结点:
-
死锁定理
简化资源分配图可检测系统状态是否为死锁状态。简化方法如下:
① 在资源分配图中,找出 既不阻塞又不是孤点的进程 Pi。
- 不阻塞:表示进程申请的资源可以被满足,如 P1 进程。由于 R2 资源除分配给 P2 进程一个资源外,还剩有一个资源,因此 P1 进程申请的 R2 资源可以被满足。相反,P2 进程申请 R1 资源则不会被满足,由于 R1 资源全部被分配完。
- 不是孤点:表示与该进程节点至少一个边相连。
② 消去进程所有的请求边和分配边,使之成为孤点。
重复以上步骤,若能消去图中所有的边,则称该图是可完全简化的。
注:并不是系统中所有的进程都是死锁状态,用死锁检测算法 化简资源分配图后,还连着边的那些进程就是死锁进程。
死锁定理:如果某时刻系统的资源分配图是不可完全简化的,那么此时系统死锁
-
死锁解除
一旦检测出死锁的发生,就应该立即解除死锁。解除死锁的主要方法有:
-
资源剥夺法
挂起(暂时放到外存上)某些死锁进程,并抢占它的资源,将这些资源分配给其他的死锁进程。但是 应防止被挂起的进程长时间得不到资源而饥饿。
-
撤销进程法(或称终止进程法)
强制撤销部分甚至全部死锁进程,并剥夺这些进程的资源。这种方式的优点是实现简单,但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间,已经接近结束了,一旦被终止可谓功亏一篑,以后还得从头再来。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
-
进程回退法
让一个或多个死锁进程回退到足以避免死锁的地步。进程回退时,自愿释放资源而非剥夺。这就要求系统要记录进程的历史信息,设置还原点。
注:撤销进程法中参考的优先级,应考虑:进程优先级、已执行多长时间、还要多久能完成、进程已经使用了多少资源、进程是交互式的还是批处理式的等因素。
-
3 内存管理
3.1 内存管理概念
3.1.1 内存管理的基本原理和要求
-
内存管理的概念
虽然计算机技术飞速发展,内存容量也在不断扩大,但仍然不可能将所有用户进程和系统所需的全部程序与数据放入内存,因此操作系统对内存空间进行合理的划分和有效的动态分配。操作系统对内存的划分和动态分配,就是内存管理的概念。
内存空间的主要功能有:
-
① 内存空间的分配与回收:OS 要怎么记录哪些内存区域已经被分配出去了,哪些又还空闲;当进程运行结束之后,如何将进程占用的内存空间回收。
-
② 内存空间的扩充:OS 利用虚拟内存技术或自动覆盖技术使得系统运行很大的程序,从逻辑上扩充内存。
-
③ 地址转换:为了使编程更方便,程序员写程序时应该只需要关注指令、数据的逻辑地址。而 逻辑地址到物理地址的转换(这个过程称为地址重定位)应该由操作系统负责,其中地址重定位有三种方式。
-
④** 内存保护**:保证各进程在各自存储空间内运行,互不干扰。
-
-
程序执行过程
创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序,通常需要以下几个步骤:
- 编译:由编译程序将用户源代码编译成若干目标模块,编译就是把高级语言翻译为机器语言。
- 链接:由链接程序将编译后形成的一组目标模块及它们所需的库函数链接在一起,形成一个完整的装入模块。
- 装入:由装入程序将装入模块装入内存运行。
编译后,每个目标模块都是从 0 号单元开始编址,这称为该目标模块的 逻辑地址 (或相对地址)。当链接程序将各个模块连接成一个完整的可执行目标程序时,链接程序顺序依次按各个模块的相对地址构成统一的从 0 号单元开始编制的 逻辑地址空间。用户程序和程序员只需知道逻辑地址,而内存管理的具体机制则是完全透明的,只有系统编程人员才会涉及内存管理的具体机制。不同进程可以有相同的逻辑地址,因为这些相同的逻辑地址可以映射到内存的不同位置。
物理地址空间 是指内存中物理单元的集合,它是地址转换的最终地址。进程在运行时执行指令和访问数据,最后都要通过物理地址从主存中存取。当装入程序将可执行代码装入内存时,必须通过地址转换将逻辑地址转换成物理地址(动态重定位是地址转换推迟到程序真正要执行时才进行),这个过程称为 地址重定位。 -
程序的链接
-
静态链接
在程序运行之前,先将各目标模块及它们所需的库函数连接成一个完整的可执行文件(装入模块),之后不再拆开。
-
装入时动态链接
将各 目标模块装入内存时,边装入边链接的链接方式。
-
运行时动态链接
在程序执行中需要该目标模块时,才对它进行链接。其优点是便于修改和更新,便于实现对目标模块的共享。
-
-
程序的装入
-
绝对装入
在编译与链接后,得到的装入模块指定 直接使用了绝对地址。
-
可重定位装入
装入时对地址进行重定位,即将逻辑地址变换为物理地址,地址变换是在装入时一次完成的。
静态重定位的特点: 在一个作业装入内存时,必须分配其要求的全部内存空间,如果没有足够的内存,就不能装入该作业。作业一旦进入内存后,在运行期间就不能再移动,也不能再申请内存空间。
-
动态运行时装入
装入程序把装入模块装入内存后,并不会立即把逻辑地址转换为物理地址(装入时依然保持使用逻辑地址),而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。
动态重定位特点: 可以将程序分配到不连续的存储区中;在程序运行前只需装入它的部分代码即可投入运行,然后在程序运行期间,根据需要动态申请分配内存;便于程序段的共享,可以向用户提供一个比存储空间大得多的地址空间;采用动态重定位时允许程序在内存中发生移动。
注:链接的作用是形成了完整的装入模块与逻辑地址,但逻辑地址到物理地址的转换过程是重定位,而不是装入。
-
-
内存映像
不同于存放在硬盘上的可执行程序文件,当一个程序调入内存运行时,就构成了进程的内存映像。一个进程的内存映像一般有几个要素:
- 代码段:即程序的二进制代码,代码段是只读的,可以被多个进程共享。
- 数据段:即程序运行时加工处理的对象,包括全局变量和静态变量。
- 进程控制块(PCB):存放在系统区。操作系统通过PCB来控制和管理进程。
- 堆:用来存放动态分配的变量。通过调用malloc 函数动态地向高地址分配空间。
- 栈:用来实现函数调用。从用户空间的最大地址往低地址方向增长。
代码段和数据段在程序调入内存时就指定了大小,而堆和栈不一样。
当调用像malloc和free这样的C标准库函数时,堆可以在运行时动态地扩展和收缩。
用户栈在程序运行期间也可以动态地扩展和收缩,每次调用一个函数,栈就会增长;从一个函数返回时,栈就会收缩。
上图是一个进程在内存中的映像。
- 其中,共享库用来存放进程用到的共享函数库代码,如printf函数等。
- 在只读代码段中,.iit是程序初始化时调用的_init函数;.text是用户程序的机器代码;.rodata是只读数据。
- 在读/写数据段中,.data是已初始化的全局变量和静态变量;.bss是未初始化及所有初始化为0的全局变量和静态变量。
-
内存保护
确保每个进程都有一个单独的内存空间。内存分配前,需要保护操作系统不受用户进程的影响,同时保护用户进程不受其他用户进程的影响。内存保护可采取两种方法:
-
在CPU中设置一对上、下限寄存器,存放用户作业在主存中的下限和上限地址,每当CPU要访问一个地址时,分别和两个寄存器的值相比,判断有无越界。
-
采用==重定位寄存器(又称基地址寄存器)和界地址寄存器(又称限长寄存器)==来实现这种保护。
重定位寄存器含最小的物理地址值,界地址寄存器含逻辑地址的最大值。内存管理机构动态地将逻辑地址与界地址寄存器进行比较,若未发生地址越界,则加上重定位寄存器的值后映射成物理地址,再送交内存单元,如下图所示。
重定位寄存器是用来“加”的,逻辑地址加上重定位寄存器中的值就能得到物理地址;
界地址寄存器是用来“比”的,通过比较界地址寄存器中的值与逻辑地址的值来判断是否越界。
加载重定位寄存器和界地址寄存器时必须使用特权指令,只有操作系统内核才可以加载这
两个存储器。这种方案允许操作系统内核修改这两个寄存器的值,而不允许用户程序修改。
-
-
内存共享
并不是所有的进程内存空间都适合共享,只有那些只读的区域才可以共享。
可重入代码又称纯代码,是一种允许多个进程同时访问但不允许被任何进程修改的代码。
在实际运行时,每个进程有自己的私有数据段,可以更改自己私有的数据区数据,不可改变共享的代码。
例:考虑一个可以同时容纳40个用户的多用户系统,他们同时执行一个文本编辑程序,若该程序有160KB代码区和40KB数据区,则共需8000KB的内存空间来支持40个用户。如果160KB代码是可分享的纯代码,则不论是在分页系统中还是在分段系统中,整个系统只需保留一份副本即可,此时所需的内存空间仅为40KB×40+160KB=1760KB。
对于分页系统,假设页面大小为4KB,则代码区占用40个页面、数据区占用10个页面。为实现代码共享,应在每个进程的页表中都建立40个页表项,它们都指向共享代码区的物理页号。此外,每个进程还要为自己的数据区建立10个页表项,指向私有数据区的物理页号。
对于分段系统,由于是以段为分配单位的,不管该段有多大,都只需为该段设置一个段表项(指向共享代码段始址,以及段长160KB)。由此可见,段的共享非常简单易行。
-
内存分配与回收
在操作系统由单道向多道发展时,存储管理方式便由单一连续分配发展为固定分区分配。为了能更好地适应不同大小的程序要求,又从固定分区分配发展到动态分区分配。
为了更好地提高内存的利用率,进而从连续分配方式发展到离散分配方式一一页式存储管理。
引入分段存储管理的目的,主要是为了满足用户在编程和使用方面的要求,其中某些要求是其他几种存储管理方式难以满足的。
3.1.2 覆盖与交换
覆盖与交换技术是在多道程序环境下用来扩充内存的两种方法。
-
覆盖
- 基本思想:由于程序运行时并非任何时候都要访问程序及数据的各个部分(尤其是大程序),因此可把用户空间分成一个固定区和若干覆盖区。
- 将经常活跃的部分放在固定区,其余部分按调用关系分段。
- 首先将那些即将要访问的段放入覆盖区,其他段放在外存中,在需要调用前,系统再将其调入覆盖区,替换覆盖区中原有的段。
- 特点:
- 打破了必须将一个进程的全部信息装入主存后才能运行的限制,但当同时运行程序的代码量大于主存时仍不能运行;
- 内存中能够更新的地方只有覆盖区的段,不在覆盖区中的段会常驻内存;
- 覆盖技术对用户和程序员不透明。
- 基本思想:由于程序运行时并非任何时候都要访问程序及数据的各个部分(尤其是大程序),因此可把用户空间分成一个固定区和若干覆盖区。
-
交换
- 基本思想:把处于等待状态(或在CPU调度原则下被剥夺运行权利)的程序从内存移到辅存,把内存空间腾出来,这一过程又称换出;把准备好竞争CPU运行的程序从辅存移到内存,这一过程又称换入。
- 交换过程:例如,有一个CPU采用时间片轮转调度算法的多道程序环境。时间片到,内存管理器将刚刚执行过的进程换出,将另一进程换入刚刚释放的内存空间。同时,CPU调度器可以将时间片分配给其他已在内存中的进程。每个进程用完时间片都与另一进程交换。在理想情况下,内存管理器的交换过程速度足够快,总有进程在内存中可以执行。
- 问题:
- 交换需要备份存储,通常是磁盘。它必须足够大,并提供对这些内存映像的直接访问。
- 为了有效使用CPU,需要使每个进程的执行时间比交换时间长。
- 若换出进程,则必须确保该进程完全处于空闲状态。
- 交换空间通常作为磁盘的一整块,且独立于文件系统,因此使用起来可能很快。
- 交换通常在有许多进程运行且内存空间吃紧时开始启动,而在系统负荷降低时就暂停。
- 普通的交换使用不多,但交换策略的某些变体在许多系统(如UNX)中仍发挥作用。
-
区别
交换技术主要在不同进程(或作业)之间进行,而覆盖则用于同一个程序或进程中。对于主存无法存放用户程序的矛盾,现代操作系统是通过虚拟内存技术来解决的,覆盖技术则已成为历史;而交换技术在现代操作系统中仍具有较强的生命力。
3.1.3 连续分配管理方式
连续分配方式是指为一个用户程序分配一个连续的内存空间,包括单一连续分配、固定分区分配和动态分区分配。
-
单一连续分配
在单一连续分配方式中,内存被分为 系统区和用户区。系统区通常位于内存的低地址部分,用于存放操作系统相关数据;用户区用于存放用户进程相关数据。内存中只能有一道用户程序,用户程序独占整个用户区空间。
优点: 实现简单;无外部碎片;可以采用覆盖技术扩充内存;无需采取内存保护,因为内存中永远只有一道程序。
**缺点:**只能用于单用户、单任务的操作系统中;有内部碎片;存储器利用率极低。
内部碎片:分配给某进程的内存区域中,如果有些部分没有用上。
外部碎片:是指内存中的某些空闲分区由于太小而难以利用。
-
固定分区分配
固定分区分配是最简单的一种多道程序存储管理方式,它将整个用户空间划分为若干个固定大小的分区,在每个分区中只装入一道作业。当有空闲分区时,便可从外存的后备作业队列中选择适当大小的作业装入该分区,如此循环。划分分区有两种方法:
- 分区大小相等。程序太小会造成浪费,程序太大又无法装入,缺乏灵活性。
- 分区大小不等。划分为多个较小的分区、适量的中等分区和少量大分区,增加了灵活性。
为了便于分配,建立一张分区使用表,通常按分区大小排队,各表项包括每个分区的起始地址、大小及状态(是否已分配),如下图所示。
分配内存时,便检索该表,以找到一个能满足要求且尚未分配的分区分配给装入程序,并将对应表项的状态置为“已分配”;若找不到这样的分区,则拒绝分配。
回收内存时,只需将对应表项的状态置为“未分配”即可。
优点: 实现简单,无外部碎片。
缺点: 当用户程序太大时,可能所有的分区都不能满足需求,此时不得不采用覆盖技术来解决,但这又会降低性能;会产生内部碎片,内存利用率低。
-
动态分区分配
动态分区分配 又称为 可变分区分配。这种分配方式不会预先划分内存分区,而是在进程装入内存时,根据进程的大小动态地建立分区,并使分区的大小正好适合进程的需要。因此,系统分区的大小和数目是可变的。
例:如图所示,系统有64MB内存空间,其中低8MB固定分配给操作系统,其余为用户可用内存。
开始时装入前三个进程,它们分别分配到所需的空间后,内存仅剩4MB,进程4无法装入。
在某个时刻,内存中没有一个就绪进程,CPU出现空闲,操作系统就换出进程2,换入进程4。由于进程4比进程2小,这样在主存中就产生了一个6MB的内存块。
之后CPU又出现空闲,需要换入进程2,而主存无法容纳进程2,操作系统就换出进程1,换入进程2。
紧凑技术:动态分区在开始时是很好的,但随着时间的推移,内存中会产生越来越多的外部碎片。需要通过紧凑技术来解决,即操作系统不时地对进程进行移动和整理。但这需要动态重定位寄存器的支持,且相对费时。
在进程装入或换入主存时,若内存中有多个足够大的空闲块,则操作系统必须确定分配哪个内存块给进程使用,这就是动态分区的分配策略。考虑以下几种算法:
- 首次适应(FirstFit)算法
- 算法思想:每次都从低地址开始查找,找到第一个能满足大小的空闲分区。
- 如何实现:空闲分区以地址递增的次序链接。分配内存时,从链首开始顺序查找,找到大小能满足要求的第一个空闲分区分配给作业。
- 算法简单,最好最快,回收分区后一般不需要对空闲分区队列重新排序
- 最佳适应(BestFit)算法
- 算法思想:优先使用更小的分区,以保留更多大分区。
- **如何实现:**空闲分区按容量递增的次序形成空闲分区链,找到第一个能满足要求且最小的空闲分区分配给作业,避免“大材小用”。
- 缺点:产生大量小的、难以利用的外部碎片
- 最坏适应(WorstFit)算法(最大适应算法)
- 算法思想:优先使用更大的分区,以防止产生太小的不可用的碎片。
- **如何实现:**空闲分区以容量递减的次序链接,找到第一个能满足要求的,即最大的分区,从中分割一部分存储空间给作业。
- 缺点:如果之后有“大进程”到达,无足够大连续内存空间分配。
- 邻近适应(NextFit)算法(循环首次适应算法)
- 算法思想:由首次适应演变而来,每次从上次查找结束位置开始查找。
- **如何实现:**空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
- **缺点:**导致无论低地址、高地址部分的空闲分区都有相同的概率被使用,也就导致了高地址部分的大分区更可能被使用,划分为小分区,最后导致无大分区可用。
算法 算法思想 分区排列顺序 优点 缺点 首次适应 从头到尾找适合的分区 空闲分区以地址递增次序排列 性能最好
算法开销小最佳适应 优先使用更小的分区 空闲分区以容量递增次序排列 保留更大分区 产生大量碎小的外部碎片;算法开销大 最坏适应 优先使用更大的分区 空闲分区以容量递减次序排列 减少难以利用的碎片 大分区容易被用完;算法开销大 邻近适应 每次从上次查找结束位置开始查找 空闲分区以地址递增次序排列(可排列成循环链表) 空闲分区有相同概率被使用,算法开销小 使高地址大分区也被用完 注:动态分区分配没有内部碎片,但是有外部碎片。
- 首次适应(FirstFit)算法
-
分区的分配与回收
回收内存分区时,有可能遇到四种情况:
- ① 回收区的后面有一个相邻的空闲分区。
- ② 回收区的前面有一个相邻的空闲分区。
- ③ 回收区的前、后各有一个相邻的空闲分区。
- ④ 回收区的前、后都没有相邻的空闲分区。
无论那种情况,都要遵循相邻的空闲分区要合并的原则。
3.1.4 基本分页存储管理
固定分区会产生内部碎片,动态分区会产生外部碎片,这两种技术对内存的利用率都比较低。为了避免碎片的产出,引出了分页的思想。
分页的思想:把主存空间划分为大小相等且固定的块,块相对较小,作为主存的基本单位。每个进程也以块为单位进行划分,进程在执行时,以块为单位逐个申请主存中的块空间。
分页管理与固定分区类似,不会产生外部碎片;进程运行按块申请主存空间,只会在最后一块有内部碎片,每个进程平均只有半个块的内部碎片(页内碎片)。
-
基本概念
-
页面和页面大小
- 进程中的块称为页或页面(Page),
- 内存中的块称为页框或页帧(Page Frame)
- 外存也以同样的单位进行划分,直接称为块或盘块(Block)。
进程在执行时需要为每个页面分配主存中的可用页框,这就产生了页和页框的一一对应。
-
将内存空间分为一个个大小相等的分区,每个分区就是一个页框 。每个页框有一个编号,即 页框号,页框号 从 0 开始。
-
将进程的逻辑地址空间也分为与页框大小相等的一个个部分,每个部分称为一个 页或页面。每个页面也有一个编号,即 页号,页号也是 从 0 开始。
页框=页帧=内存块=物理块=物理页面
为方便地址转换,页面大小应是2的整数幂。同时页面大小应该适中,
- 页面太小会使进程的页面数过多,这样页表就会过长,占用大量内存,而且也会增加硬件地址转换的开销,降低页面换入/换出的效率;
- 页面过大又会使页内碎片增多,降低内存的利用率。
-
地址结构
地址结构决定了虚拟内存的寻址空间有多大。
分页存储管理的 逻辑地址结构 如下所示:
地址结构包含两个部分:前一部分为页号,后一部分为页内偏移量 W。
在上图所示的例子中,地址长度为 32 位,其中 0 ~ 11位 为页内偏移量(或称页内地址),即每页大小为 4KB;12~31 位为页号,进程地址空间最多允许 220 页。
-
页表
为了能知道进程的每个页面在内存中存放的位置,操作系统要为每个进程建立一张 页表。页表通常存在 PCB (进程控制块,在操作系统的内核地址空间)中。页表记录进程 页面 和实际存放的 内存块 之间的 映射关系。
- ①一个进程对应一张页表。
- ②进程的每个页面对应一个页表项。
- ③每个页表项由页号和块号组成。
- ④每个页表项的长度是相同的。
例:假设某系统物理内存大小为 4 GB,页面大小为 4 KB,则每个页表项至少应该为多少字节?
- 内存块大小=页面大小=4KB=212B
- 4GB的内存总共会被分为232/212=220个内存块
- 内存块号的范围应该是0~220-1
- 内存块号至少要用20 bit来表示
- 至少要用3B来表示块号(3*8=24 bit>20bit)
页表项在内存中是连续存放,因此页号是可以隐藏的,不占内存空间,页表项占 3 个字节。
注:如果未特别强调,默认计算机按字节编址。
-
地址转换
分页存储特点: 虽然进程的各个页面是离散存放的,但是页面内部是连续存放的。
页号 = 逻辑地址 / 页面长度
页内偏移量 = 逻辑地址 % 页面长度如果要访问逻辑地址 A 的物理块,则
- ① 确定逻辑地址 A 对应的页号 P
- ② 找到 P 号页面在内存中的起始地址(需要查页表)
- ③ 确定逻辑地址 A 的页内偏移量 W
-
-
基本地址变换机构
基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。变换机构如下图所示。
通常会在系统中设置一个 页表寄存器(PTR),存放 页表在内存中的起始地址 F 和页表长度 M。
进程未执行时,页表的始址 和 页表长度 放在进程控制块(PCB)中,当进程被调度时,操作系统内核会把它们放到页表寄存器中。-
设页面大小为 L ,逻辑地址 A 到物理地址 E 的变换过程如下:
-
①**计算页号P和页内偏移量W**
如果用十进制数手算,则 P = A / L , W = A P=A/L,W=A%L P=A/L,W=A;但是在计算机实际运行时,逻辑地址结构是固定不变的,因此计算机硬件可以更快地得到二进制表示的页号、页内偏移量
-
②**判断页号是否越界**
比较页号P和页表长度M,若P≥M,则产生越界中断,否则继续执行。
注意:页号是从0开始的,而页表长度至少是1,因此P=M时也会越界
-
③**查页表,找页号对应的页表项,确定内存块号**
页表中页号 P 对应的页表项地址 = 页表起始地址 F + 页号 P ∗ 页表项长度 页表中页号P对应的页表项地址=页表起始地址F+页号P*页表项长度 页表中页号P对应的页表项地址=页表起始地址F+页号P∗页表项长度
取出该页表项内容b,即为内存块号。注意区分页表项长度、页表长度、页面大小的区别。
页表长度指的是这个页表中总共有几个页表项,即总共有几个页;
页表项长度指的是每个页表项占多大的存储空间;
页面大小指的是一个页面占多大的存储空间
-
④**用内存块号和偏移量得到物理地址**
计算 E = b ∗ L + W E=b*L+W E=b∗L+W,用得到的物理地址E去访存。
如果内存块号、页面偏移量是用二进制表示的,那么把二者拼接起来就是最终的物理地址了
-
⑤**访问目标内存单元**
-
在分页存储管理(页式管理)的系统中,页是信息的物理单位,分页完全是系统行为,因此 页的大小由系统决定,逻辑地址在计算机的视角很好确定。所以,页式管理中地址是一维的。即,只要给出一个逻辑地址,系统就可以自动地算出页号、页内偏移量 两个部分,并不需要显式地告诉系统这个逻辑地址中,页内偏移量占多少位。
-
-
具有快表的地址变换机构
快表,又称联想寄存器(TLB),是一种 访问速度比内存快很多的高速缓存器,用来存放最近访问的页表项的副本,可以加速地址变换的速度。与此对应,内存中的页表常称为慢表。
注:TLB 不是内存;快表与 Cache(高速缓冲器) 的区别在于,块表中只有页表项的副本,而普通 Cache 中可能有其他各种数据的副本,可以把快表理解为一种特殊的 Cache。
-
设某进程执行过程中要访问 (0,4) 这个逻辑地址,访问过程如下:
- ① CPU 给出逻辑地址,由硬件进行地址转换,将页号与快表中的所有页号进行比较。
- ② 如果找到匹配的页号,说明要访问的页表项在快表中有副本,则直接从中取出该页对应的内存块号,再将内存块号与页内偏移量拼接形成物理地址,最后再访存。因此,若快表命中,存取数据仅一次访存。
- ③ 如果没有找到匹配的页号,则需要访问内存中的页表。找到对应页表项,得到页面存放的内存块号,再将内存块号与页内偏移量拼接形成物理地址,最后再访存。因此,若快表未命中,存取数据需两次访存。
注:在找到页表项后,应同时将其存入快表,以便后面可能的再次访问。但若快表已满,则必须按照一定算法对旧的页表项进行替换(局部性原理)。
-
-
两级页表
两级页表的分配管理方式属于基本分页存储管理范畴,其用于解决页表项占据连续页框的问题。
-
单级页表存在的问题
问题一:页表必须连续存放,因此当页表很大时,需要占用很多个连续的页框。
解决:可建立两级页表,一级页表为页目录表,二级页表离散存储。
问题二:没有必要让整个页表常驻内存,因为进程在一段时间内可能只需要访问某几个特定的页面。
解决:可以在需要访问页面时才把页面调入内存(虚拟存储技术)。可以在页表项中增加一个标志位,用于表示该页面是否已经调入内存
-
两级页表的原理、地址结构
二级页表实际上是在原有页表结构上再加上一层页表,如下图所示。
建立多级页表的目的在于建立索引,以便不用浪费主存空间去存储无用的页表项,也不用盲目地顺序式查找页表项。
例:某系统按字节寻址,支持 30 位的逻辑地址,采用分页存储管理,页面大小为 4KB,页表项长度为 4B,试问逻辑地址的结构。
页面大小为4KB=212B,则页内偏移量要用12位表示。
30-12=18,则顷号用18位表示,即进程最多有218个页面,一共需要218个页表项来记录这些页面与物理块的映射关系,且页号范围是:0~218-1。
页表项长度是4B,一个内存块(页框)最多存储4K/4=212/4=210个页表项。
218个页表项则需要218/210=28个内存块才能存储。
即需要专门给进程分配28=256个连续的物理块(页框)来存放它的页表。
为避免连续占用内存块问题,可以设置28=256个二级页表,并用一级页表来记录这些二级页表,因此一级页号占8位。
-
地址变换
例: 将逻辑地址 (00000000,0000000001,111111111111) 转换为物理地址(用十进制表示)。
首先,按照地址结构将逻辑地址拆分成三部分
- ① 从 PCB 中读出页目录表始址,再根据一级页号查页目录表,找到下一级页表在内存中的存放位置。
- ② 根据二级页号查二级页表,找到最终想访问的内存块号。
- ③ 结合页内偏移量得到物理地址。
最终要访问的内存块号为 4,该内存块的起始地址为 4*4096 = 16384 页内偏移量为 4095。
最终的物理地址为:16384 + 4095= 20479。
两次页表,若采用“快表”,需要3次访存。
- 第一次:访问页目录表。
- 第二次:访问内存中的二级页表。
- 第三次:访问目标内存单元。
-
多级页表
若分为两级页表后,页表依然很长,则可以采用更多级页表。并且,若采用多级页表机制,则各级页表的大小不能超过一个页面。
例:某系统按字节编址,采用 40 位逻辑地址,页面大小为 4KB,页表项大小为 4B,假设采用纯页式存储,则要采用 ( ) 级页表,页内偏移量为 ( ) 位?
页面大小=4KB=212B,按字节编址,因此页内偏移量为12位。
页号=40-12=28位
页面大小=212B,页表项大小=4B,则每个页面可存放212/4=210个页表项。
因此,各级页表最多包含210个页表项,需要10位二进制位才能映射到210个页表项。
因此每一级的页表对应页号应为10位。总共28位的页号至少要分为3级。
此外,若未用“快表”,N 级页表机制,需要 N+1 次访问内存。
-
3.1.5 基本分段式存储管理
分页管理方式是从计算机的角度考虑设计的,目的是提高内存的利用率,提升计算机的性能。分页通过硬件机制实现,对用户完全透明。
分段管理方式的提出则考虑了用户和程序员,以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。
-
分段
段式管理方式按照用户进程中的自然段划分逻辑空间。
例如,用户进程由主程序段、两个子程序段、栈段和数据段组成,于是可以把这个用户进程划分为5段,每段从0开始编址,并分配一段连续的地址空间。
段内要求连续,段间不要求连续,因此整个作业的地址空间是二维的。
其逻辑地址由段号S与段内偏移量W两部分组成,如下图所示分段系统中的逻辑地址结构。
其中,段号为16位,段内偏移量为16位,因此一个作业最多有216=65536段,最大段长为64KB。
在页式系统中,逻辑地址的页号和页内偏移量对用户是透明的,但在段式系统中,段号和段内偏移量必须由用户显式提供,在高级程序设计语言中,这个工作由编译程序完成。
-
段表
程序分多个段,各段离散地装入内存,为了保证程序能正常运行,就必须能从物理内存中找到各个逻辑段的存放位置。为此,需为每个进程建立一张段映射表,简称段表。
段表用于实现从逻辑段到物理内存区的映射。
特点:
- ① 每个段对应一个段表项,其中 记录了该段在内存中的起始位置(又称“基址”)和段的长度。
- ② 各个段表项的长度是相同的。
- ③ 由于段表项长度相同,在内存中是连续存放,因此段号可以是隐含的,不占存储空间。
- ④ 段内要求连续,段间不要求连续,因此整个作业的地址空间是二维的。
-
地址变换机构
分段系统的地址变换过程如图所示。为了实现进程从逻辑地址到物理地址的变换功能,在系统中设置了段表寄存器,用于存放段表始址F和段表长度M。从逻辑地址A到物理地址E之间的地址变换过程如下:
-
① 根据逻辑地址得到段号,段内地址
从逻辑地址A中取出前几位为段号S,后几位为段内偏移量W。
-
② 判断段号是否越界
比较段号S和段表长度M,若 段号 S ≥ 段表长度 M 段号S≥段表长度M 段号S≥段表长度M ,则产生越界中断,否则继续执行。
-
③ 查询段表,找到对应段表项
段表中段号S对应的 段表项地址 = 段表始址 F + 段号 S × 段表项长度 段表项地址=段表始址F+段号S×段表项长度 段表项地址=段表始址F+段号S×段表项长度 。
-
④ 检查段内地址是否超过段长
取出该段表项的前几位得到段长C。若 段内偏移量 W ≥ 段长 C 段内偏移量W≥段长C 段内偏移量W≥段长C,则产生越界中断,否则继续执行。
-
⑤ 计算得到物理地址
取出段表项中该段的始址b,计算 物理地址 E = 段基址 b + 偏移量 W 物理地址E=段基址b+偏移量W 物理地址E=段基址b+偏移量W ,得到物理地址E。
-
⑥ 访问目标内存单元
用得到的物理地址E去访问内存。
-
-
段的共享与保护
-
共享
在分段系统中,段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。
不能修改的代码称为纯代码或可重入代码(它不属于临界资源),这样的代码和不能修改的数据可以共享,而可修改的代码和数据不能共享。
-
保护
分段管理的保护方法主要有两种:一种是存取控制保护,另一种是地址越界保护。
- 存取控制保护:指在段表的每个表项中,设置“存取控制”字段,规定对该段的访问方式。
- 地址越界保护:指在进行存储访问时,要检查逻辑地址是否超出了进程的地址空间。
-
-
分段、分页管理的对比
存储信息 地址空间 信息保护 访存次数 分页管理 页是信息的物理单位
对用户透明
系统行为一维
记忆符(<A>)不易 分页(单级页表)需两次访问
页表+目标内存单元分段管理 段是信息的逻辑单位
对用户可见
用户需求二维
段名+段内地址([D]|<A>)容易
纯代码分段需两次访问
段表+目标内存单元
3.1.6 段页式管理
-
段页式管理结构
分页存储管理能有效地提高内存利用率,而分段存储管理能反映程序的逻辑结构并有利于段的共享和保护。将这两种存储管理方法结合起来,便形成了段页式存储管理方式。
段页式存储管理方式,将作业的地址空间首先被分成若干逻辑段,每段都有自己的段号,然后将每个段分成若干大小固定的页,内存空间分为大小一个个大小相等的分区。如下图所示。
在段页式系统中,作业的逻辑地址分为三部分:段号、页号和页内偏移量。如下图所示。
段号的位数决定了每个进程最多可以分几个段,页号位数决定了每个段最大有多少页,页内偏移量决定了页面大小、内存块大小是多少。
在一个进程中,段表只有一个,而页表可能有多个。
例:如下图所示的段页式格式,
- 段号16位,因此进程中最多有216=64K个段。
- 页号4位,因此每个段最多有24=16页。
- 页内偏移量有12位,因此每个内存块大小为212=2KB
分段对用户是可见的,程序员编程时需要显式地给出段号、段内地址。而将各段分页对用户是不可见的。系统会根据段内地址自动划分页号和页内偏移量。因此,段页式管理的地址结构是二维的。
-
地址转换
在进行地址变换时,首先通过段表查到页表始址,然后通过页表找到页号,最后形成物理地址。
如下图所示,进行一次访问实际需要三次访问主存,这里同样可以使用快表来加快查找速度,其关键字由段号、页号组成,值是对应的页帧号和保护码。
- ① 根据逻辑地址得到段号、页号、页内偏移量
- ② 判断段号是否越界若S≥M,则产生越界中断,否则继续执行
- ③ 查询段表找到对应的段表项,段表项的存放地址为 F + S × 段表顶长度 F+S×段表顶长度 F+S×段表顶长度
- ④ 检查页号是香越界,若页号≥页表长度,则发生越界中断,否则继续执行
- ⑤ 根据页表存放块号、页号查询页表找到对应页表项
- ⑥ 根据内存块号页内偏移量得到最终的物理地址
- ⑦ 访问目标内存单元
3.2 虚拟内存管理
3.2.1 虚拟内存的基本概念
-
传统存储管理方式的特征
-
传统存储管理方式
-
连续分配
- 单一连续分配
- 固定分区分配
- 动态分区分配
-
非连续分配
- 基本分页存储管理
- 基本分段存储管理
- 基本段页式存储管理
-
特征:
- 一次性:作业必须一次性全部装入内存后,才能开始运行。这会导致两种情况:
- ①当作业很大而不能全部被装入内存时,将使该作业无法运行;
- ②当大量作业要求运行时,由于内存不足以容纳所有作业,只能使少数作业先运行,导致多道程序度的下降。
- 驻留性:作业被装入内存后,就一直驻留在内存中,其任何部分都不会被换出,直至作业运行结束。运行中的进程会因等待IO而被阻塞,可能处于长期等待状态。
由以上分析可知,许多在程序运行中不用或暂时不用的程序(数据)占据了大量的内存空间,而一些需要运行的作业又无法装入运行,显然浪费了宝贵的内存资源。
-
-
局部性原理
快表、页高速缓存及虚拟内存技术都属于高速缓存技术,这个技术所依赖的原理就是局部性原理。
-
时间局部性。
程序中的某条指令一且执行,不久后该指令可能再次执行;某数据被访问过,不久后该数据可能再次被访问。产生的原因是程序中存在着大量的循环操作。
-
空间局部性。
一旦程序访问了某个存储单元,在不久后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围之内,因为指令通常是顺序存放、顺序执行的,数据也一般是以向量、数组、表等形式聚存储的。
-
-
虚拟存储器的定义和特征
程序不需全部装入即可运行,运行时根据需要动态调入数据,若内存不够,还需换出一些数据。系统好像为用户提供了一个比实际内存容量大得多的存储器,称为虚拟存储器。
- 多次性:无需在作业运行时一次性全部装入内存,而是允许被分成多次调入内存。
- 对换性:无需在作业运行时一直常驻内存,而是允许在作业运行过程中,将作业换入、换出。
- 虚拟性:从逻辑上扩充了内存的容量,使用户看到的内存容量,远大于实际的容量。
-
虚拟内存技术的实现
虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。
访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存(请求调页功能)
内存空间不够时,将内存中暂时用不到的信息换出到外存(页面置换功能)
- 虚拟内存的实现方式
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
- 所需要的硬件支持
- 一定容量的内存和外存。
- 页表机制(或段表机制),作为主要的数据结构。
- 中断机构,当用户程序要访问的部分尚未调入内存时,则产生中断。
- 地址变换机构,逻辑地址到物理地址的变换。
- 虚拟内存的实现方式
3.2.2 请求分页管理方式
请求分页系统建立在基本分页系统基础之上,为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。
-
页表机制
请求分页系统在一个作业运行之前不要求全部一次性调入内存,因此在作业的运行过程中,必然会出现要访问的页面不在内存中的情况。因此在请求页表项中增加了 4个字段,如下图所示。
- 状态位P:用于指示该页是否已调入内存,供程序访问时参考。
- 访问字段A:用于记录本页在一段时间内被访问的次数,或记录本页最近已有多长时间未被访问,供置换算法换出页面时参考。
- 修改位M:标识该页在调入内存后是否被修改过,以确定页面置换时是否写回外存。
- 外存地址:用于指出该页在外存上的地址,通常是物理块号,供调入该页时参考。
-
缺页中断机构
在请求分页系统中,每当所要访问的页面不在内存中时,便产生一个缺页中断,请求操作系统将所缺的页调入内存。
-
缺页中断执行过程
- 先将缺页的进程阻塞(调页完成唤醒),
- 若内存中有空闲块,则分配一个块,将要调入的页装入该块,并修改页表中的相应页表项,
- 若此时内存中没有空闲块,则要淘汰某页(若被淘汰页在内存期间被修改过,则要将其写回外存)。
-
缺页中断和一般中断的区别:
- 在指令执行期间而非一条指令执行完后产生和处理中断信号,属于内部异常。
- 一条指令在执行期间,可能产生多次缺页中断。
-
-
地址变换机构
请求分页系统中的地址变换机构,是在分页系统地址变换机构的基础上,为实现虚拟内存,又增加了某些功能而形成的,如产生和处理缺页中断,及从内存中换出一页的功能等等。
- 新增步骤1:请求调页(查到页表项时进行判断)
- 新增步骤2:页面置换(需要调入页面,但没有空闲内存块时进行)
- 新增步骤3:需要修改请求页表中新增的表项
请求分页管理的地址变换过程,如下图所示,红框部分为新增步骤:
①只有“写指令”才需要修改“修改位”。并且,一般来说只需修改快表中的数据,只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。
②和普通的中断处理一样,缺页中断处理依然需要保留CPU现场。
③需要用某种“页面置换算法”来决定一个换出页面(下节内容)
④换入/换出页面都需要启动慢速的I/O操作,可见,如果换入换出太频繁,会有很大的开销。
⑤页面调入内存后,需要修改慢表,同时也需要将表项复制到快表中。
3.2.3 页框分配
-
驻留集大小
给一个进程分配的物理页框的集合就是这个进程的驻留集。
- 分配给一个进程的页框越少,驻留在主存中的进程就越多,从而可提高CPU的利用率。
- 若一个进程在主存中的页面过少,则尽管有局部性原理,缺页率仍相对较高。
- 若分配的页框过多,则由于局部性原理,对该进程的缺页率没有太明显的影响。
-
内存分配策略
在请求分页系统中,可采取两种内存分配策略,即固定和可变分配策略。在进行置换时,也可采取两种策略,即全局置换和局部置换。
- 固定分配:操作系统为每个进程分配一组固定数目的物理块,在进程运行期间不再改变。即,驻留集大小不变
- 可变分配:先为每个进程分配一定数目的物理块,在进程运行期间,可根据情况做适当的增加或减少。即驻留集大小可变
- 局部置换:发生缺页时只能选进程自己的物理块进行置换。
- 全局置换:可以将操作系统保留的空闲物理块分配给缺页进程,也可以将别的进程持有的物理块置换到外存,再分配给缺页进程。
固定分配VS可变分配:区别在于进程运行期间驻留集大小是否可变
局部置换VS全局置换:区别在于发生缺页时是否只能从进程自己的页面中选择一个换出
-
固定分配局部置换
它为每个进程分配一定数目的物理块,在整个运行期间都不改变。
若进程在运行中发生缺页,则只能从该进程在内存中的页面中选出一页换出,然后再调入需要的页面。
-
可变分配全局置换
为系统中的每个进程分配一定数目的物理块,操作系统自身也保持一个空闲物理块队列。
当某进程发生缺页时,系统从空闲物理块队列中取出物理块分配给该进程,井将欲调入的页装入其中。
-
可变分配局部置换
它为每个进程分配一定数目的物理块,当某进程发生缺页时,只允许从该进程在内存的页面中选出一页换出动态变换,频繁缺页,分配物理块,缺页率低,减少物理块
-
物理块调入算法
采用固定分配策略时,将系统中的空闲物理块分配给各个进程,可采用下述几种算法。
- 平均分配算法,将系统中所有可供分配的物理块平均分配给各个进程。
- 按比例分配算法,根据进程的大小按比例分配物理块。
- 优先权分配算法,为重要和紧迫的进程分配较多的物理块。通常采取的方法是把所有可分配的物理块分成两部分:一部分按比例分配给各个进程;一部分则根据优先权分配。
-
调入页面的时机
为确定系统将进程运行时所缺的页面调入内存的时机,可采取以下两种调页策略:
- **预调页策略:**将预计在不久后便会被访问的页面预先调入内存;主要用于进程的首次调入,由程序员指出应先调入哪些页。
- **请求调页策略:**进程在运行中需要访问的页面不再内存而提出请求,由系统将所需页面调入内存。每次仅调入一页,增加了磁盘I/O开销。
-
从何处调入页面
请求分页系统中的外存分为两部分:用于存放文件的文件区和用于存放对换页面的对换区。
对换区采用连续分配方式,而文件区采用离散分配方式,因此对换区的磁盘IO速度比文件区的更快。这样,当发生缺页请求时,系统从何处将缺页调入内存就分为三种情况:
-
系统拥有足够的对换区空间
可以全部从对换区调入所需页面,以提高调页速度。为此,在进程运行前,需将与该进程有关的文件从文件区复制到对换区。
-
系统缺少足够的对换区空间
凡是不会被修改的文件都直接从文件区调入;而当换出这些页面时,由于它们未被修改而不必再将它们换出。但对于那些可能被修改的部分,在将它们换出时须调到对换区,以后需要时再从对换区调入(因为读比写的速度快)。
-
UNIX方式
运行之前进程有关的数据全部放在文件区,故未使用过的页面,都可从文件区调入。若被使用过的页面需要换出,则写回对换区,下次需要时从对换区调入。进程请求的共享页面若被其他进程调入内存,则无须再从对换区调入。
-
-
如何调入页面
-
当进程所访问的页面不在内存中时(存在位为0),便向CPU发出缺页中断,中断响应后便转入缺页中断处理程序。
-
该程序通过查找页表得到该页的物理块,此时如果内存未满,则启动磁盘I/O,将所缺页调入内存,并修改页表。
-
如果内存已满,则先按某种置换算法从内存中选出一页准备换出;
- 如果该页未被修改过(修改位为0),则无须将该页写回磁盘;
- 如果该页已被修改(修改位为1),则必须将该页写回磁盘,
然后将所缺页调入内存,并修改页表中的相应表项,置其存在位为1。
-
调入完成后,进程就可利用修改后的页表形成所要访问数据的内存地址。
-
3.2.4 页面置换算法
进程运行时,若其访问的页面不在内存中而需将其调入,但内存已无空闲空间时,就需要从内存中调出一页程序或数据,送入磁盘的对换区,选择调出页面的算法就称为页面置换算法。
-
最佳置换算法(OPT)
选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。
但由于人们目前无法预知进程在内存下的页面中哪个是未来最长时间内不再被访问的,因而该算法无法实现。
-
先进先出置换算法(FIFO)
优先淘汰最早进入内存的页面,即在内存中驻留时间最久的页面。
该算法实现简单,只需把调入内存的页面根据先后次序链接成队列,设置一个指针总指向最早的页面。
-
Belady异常一一当为进程分配的物理块数增大时,缺页次数不减反增的异常现象。
只有FIFO算法回产生Belady异常,算法性能差。
该算法与进程实际运行时的规律不适应,因为在进程中,有的页面经常被访问。
-
-
最近最久未使用置换算法(LRU)
选择最近最长时间未访问过的页面予以淘汰,它认为过去一段时间内未访问过的页面,在最近的将来可能也不会被访问。
该算法为每个页面设置一个访问字段,来记录页面自上次被访问以来所经历的时间,淘汰页面时选择现有页面中值最大的予以淘汰。
该算法的实现需要专门的硬件支持,虽然算法性能好,但是实现困难,开销大。
-
时钟置换算法(CLOCK)/最近未用算法(NRU)
简单的CLOCK算法实现方法:
- 为每个页面设置一个访问位,再将内存中的页面都通过链接指针链接成一个循环队列。
- 当某页被访问时,其访问位置为1。
- 当需要淘汰一个页面时,只需检查页的访问位。如果是0,就选择该页换出;如果是1,则将它置为0,暂不换出,继续检查下一个页面,
- 若第一轮扫描中所有页面都是1,则将这些页面的访问位依次置为0后,再进行第二轮扫描(第二轮扫描中一定会有访问位为0的页面,因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)
-
改进型的时钟置换算法
-
简单时钟问题:简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上,如果被淘汰的页面没有被修改过,就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时,才需要写回外存。
因此,除了考虑一个页面最近有没有被访问过之外,操作系统还应考虑页面有没有被修改过。在其他条件都相同时,应优先淘汰没有修改过的页面,避免I/O操作。这就是改进型的时钟置换算法的思想。
修改位=0,表示页面没有被修改过:修改位=1,表示页面被修改过。
-
算法规则:将所有可能被置换的页面排成一个循环队列,用(访问位A,修改位M)表示各页面状态。
替换帧优先级:
- 1类A=0,M=0:最近未被访问且未被修改,是最佳淘汰页。
- 2类A=0,M=1:最近未被访问,但已被修改,不是很好的淘汰页。
- 3类A=1,M=0:最近已被访问,但未被修改,可能再被访问。
- 4类A=1,M=1:最近已被访问且已被修改,可能再被访问。
-
第一轮:第一优先级——最近设访问,且没修改的页面
从当前位置开始扫描到第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位
-
第二轮:第二优先级——最近没访问,但修改过的页面
若第一轮扫描失败,则重新扫描,查找第一个(0,1)的帧用于替换。本轮将所有扫描过的帧访问位设为0
-
第三轮:第三优先级——最近访问过,但没修改的页面
若第二轮扫描失败,则重新扫描,查找第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位
-
第四轮:第四优先级——最近访问过,且修改过的页面
若第三轮扫描失败,则重新扫描,查找第一个(0,1)的帧用于替换。
由于第二轮己将所有帧的访问位设为0,因此经过第三轮、第四轮扫描定会有一个帧被选中,因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描。
-
性能:算法开销较小,性能也不错
-
3.2.5 抖动和工作集
-
抖动
-
定义:抖动,又称颠簸,指在页面置换过程中,刚刚换出的页面马上又要换入主存,刚刚换入的页面马上又要换出主存。
-
抖动发生的原因:系统中同时运行的进程太多,由此分配给每个进程的物理块太少,不能满足进程正常运行的基本要求,致使每个进程在运行时频繁地出现缺页,必须请求系统将所缺页面调入内存。
-
抖动的危害:
- 使得在系统中排队等待页面调入/调出的进程数目增加。
- 对磁盘的有效访问时间也随之急剧增加,造成每个进程的大部分时间都用于页面的换入/换出,而几乎不能再去做任何有效的工作,
- 进而导致发生处理机的利用率急剧下降并趋于零的情况。
-
-
工作集
由于抖动的发生与系统为进程分配物理块的多少有关,于是又提出了关于进程工作集的概念。
工作集是指在某段时间间隔内,进程要访问的页面集合。
基于局部性原理,可以用最近访问过的页面来确定工作集。一般来说,工作集 W W W可由时间 t t t和工作集窗口大小 Δ Δ Δ来确定。例如,某进程对页面的访问次序如下:
假设系统为该进程设定的工作集窗口大小 Δ Δ Δ为5,则在 t 1 t_1 t1时刻,进程的工作集为{2,3,5},在 t 2 t_2 t2时刻,进程的工作集为{1,2,3,4}。
工作集大小一般会比窗口小很多,工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合,因此,若分配给进程的物理块小于工作集大小,则该进程就很有可能频繁缺页。
一般来说分配给进程的物理块数(即驻留集大小)要大于工作集大小。
3.2.6 内存映射文件
内存映射文件(Memory-MappedFiles)与虚拟内存有些相似,将磁盘文件的全部或部分内容与进程虚拟地址空间的某个区域建立映射关系,便可以直接访问被映射的文件,而不必执行文件 I/O 操作,也无须对文件内容进行缓存处理。这种特性非常适合用来管理大尺寸文件。
-
特性
- 进程可使用系统调用,请求操作系统将文件映射到进程的虚拟地址空间
- 以访问内存的方式读写文件
- 进程关闭文件时,操作系统负责将文件数据写回磁盘,并解除内存映射
- 多个进程可以映射同一个文件,方便共享
-
优点
- 程序员编程更简单,已建立映射的文件,只需按访问内存的方式读写即可
- 文件数据的读入/写出完全由操作系统负责,I\O效率可以由操作系统负责优化
3.2.7 虚拟存储器性能影响因素
-
页面大小
根据局部性原理,页面较大则缺页率较低,页面较小则缺页率较高。
- 页面较小时,一方面减少了内存碎片,有利于提高内存利用率;另一方面,也会使每个进程要求较多的页面,导致页表过长,占用大量内存。
- 页面较大时,虽然可以减少页表长度,但会使页内碎片增大。
-
分配给进程的物理块
分配给进程的物理块数越多,缺页率就越低,但是当物理块超过某个数目时,再为进程增加一个物理块对缺页率的改善是不明显的。
-
页面置换算法
好的页面置换算法可使进程在运行过程中具有较低的缺页率。
选择LRU、CLOCK等置换算法,将未来有可能访问的页面尽量保留在内存中,从而提高页面的访问速度。
-
写回磁盘的频率
换出已修改过的页面时,应当写回磁盘,如果每当一个页面被换出时就将它写回磁盘,那么每换出一个页面就需要启动一次磁盘,效率极低。
建立一个已修改换出页面的链表,对每个要被换出的页面(已修改),可以暂不将它们写回磁盘,而将它们挂在该链表上,仅当被换出页面数达到给定值时,才将其写回磁盘。
-
局部化程度
编写程序的局部化程度越高,执行时的缺页率就越低。如果存储采用的是按行存储,访问时就要尽量采用相同的访问方式,避免按列访问造成缺页率过高的现象。
3.2.8 地址翻译
设某系统满足以下条件:
- 有一个TLB与一个data Cache
- 存储器以字节为编址单位
- 虚拟地址14位
- 物理地址12位
- 页面大小为64B
- TLB为四路组相联,共有16个条目
- data Cache是物理寻址、直接映射的,行大小为4B,共有16组
写出访问地址为0x03d4, 0x00f1和0x0229的过程。
-
写出其地址结构
-
根据页面大小求页内偏移量与页号长度
本系统以字节编址,页面大小为64B,则页内偏移量为 l o g 2 ( 64 B / 1 B ) = 6 位 log_2(64B/1B)=6位 log2(64B/1B)=6位,所以虚拟页号为 14 − 6 = 8 位 14-6=8位 14−6=8位,物理页号为 12 − 6 = 6 位 12-6=6位 12−6=6位。
-
根据TLB结构求虚拟页号地址结构
因为TLB为四路组相联,共有16个条目,则TLB有16/4=4组,因此虚拟页号低 l o g 2 4 = 2 位 log_24=2位 log24=2位就为组索引,高6位为TLB标记。
-
根据Cache机构求物理页号地址结构
因为Cache行大小为4B,因此物理地址中低 l o g 2 4 = 2 位 log_24=2位 log24=2位为块索引,Cache共有16组,可知接下来 l o g 2 16 = 4 位 log_216=4位 log216=4位为组索引,剩下高6位作为标记。
-
-
根据TLB、页表寻找物理页号
先把十六进制的虚拟地址0x03d4, 0x00f1和0x0229转化为二进制形式,如下表所示。
得到每个地址的组索引和TLB标记,接下来就要找出每个地址的页面在不在主存中,若在主存中,则还要找出物理地址。
- 查TLB得到物理块号
- 对于0x03d4,组索引为3,TLB标记为0x03。
- 查TLB表,第3组中有标记为03的项,且有效位为1,找到物理块0D。
- 拼接页内地址(010100),得到物理地址为0x354。
- 查TLB未得到物理块号,查页表得到物理块号
- 对于0x00f1,组索引为3,TLB标记为0x00。
- 查TLB表,第3组未找到有标记为00的项。
- 访存查页表,根据虚拟页号0x03,找到物理块号02,且有有效位为1。
- 拼接页内地址(110001),得到物理地址为0x0b1。
- 查TLB未得到物理块号,查页表也未得到物理块号
- 对于0x0229,组索引为0,TLB标记为0x02。
- 查TLB表,第0组未找到有标记为02的项。
- 访存查页表,根据虚拟页号0x08,页表08项有效位为0,页面不在主存中,产生缺页中断。
- 查TLB得到物理块号
-
根据Cache寻找内存地址
找出在主存中的页面的物理地址后,就要通过物理地址访问数据,接下来要找该物理地址的 内容在不在Cache中,物理地址结构如下表所示。
- Cache块命中
- 对于0x354,Cache索引为5,Cache标记为0x0d。
- 查询Cache索引为5的行,标记为0d,有效位为1,则该块在Cache中。
- 偏移为0,即块0,可得虚拟地址0x03d4的内容为36H。
- Cache块未命中
- 对于0x0b1,Cache索引为C,Cache标记为0x02。
- 查询Cache索引为C的行,标记为02,有效位为0,则该块不在Cache中。
- 需去访问主存查找,物理页号为2、偏移为0x31的内容。
- Cache块命中
-
虚拟地址寻址总流程
4 文件管理
4.1 文件系统基础
4.1.1 文件的基本概念
-
定义
文件是以计算机硬盘为载体的存储在计算机上的信息集合,在用户进行的输入、输出中,以文件位基本单位。
文件管理系统是实现的文件的访问、修改和保存,对文件维护管理的系统。
-
文件的组成
- 存储空间:用于存储数据
- 标签:便于对数据的分类和索引
- 访问权限:不同用户对数据有不同的访问权限
-
文件的结构
- 数据项:是文件系统中最低级的数据组织形式,可分为以下两种类型:
- 基本数据项:用于描述一个对象的某种属性的一个值,是数据中的最小逻辑单位。
- 组合数据项:由多个基本数据项组成。
- 记录:是一组相关的数据项的集合,用于描述一个对象在某方面的属性。
- 文件:是指由创建者所定义的、具有文件名的一组相关元素的集合,分为有结构文件和无结构文件两种。
- 在有结构的文件中,文件由若干个相似的记录组成,如一个班的学生记录;
- 无结构文件则被视为一个字符流,比如一个二进制文件或字符文件。
- 数据项:是文件系统中最低级的数据组织形式,可分为以下两种类型:
4.1.2 文件控制块和索引结点
-
文件的属性
- 文件名:由创建文件的用户决定文件名,主要是为了方便用户找到文件,同一目录下不允许有重名文件
- 标识符:一个系统内的各文件标识符唯一,对用户来说毫无可读性,因此标识符只是操作系统用于区分各个文件的一种内部名称。
- 类型:指明文件的类型
- 位置:文件存放的路径(让用户使用)、在外存中的地址(操作系统使用,对用户不可见)
- 大小:指明文件大小
- 保护信息:对文件进行保护的访问控制信息
- 创建时间、最后一次修改时间和最后一次存取时间:文件创建、上次修改和上次访问的相关信息,用于保护和跟踪文件的使用。
-
文件控制块FCB
文件控制块(FCB)是用来存放控制文件需要的各种信息的数据结构,以实现“按名存取"。
操作系统通过文件控制块(FCB)来维护文件元数据。FCB的有序集合称为文件目录,一个FCB就是一个文件目录项。下图为一个典型的FCB。
FCB包含以下信息:
- 基本信息:如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
- 存取控制信息:包括文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。
- 使用信息:如文件建立时间、上次修改时间等。
一个文件目录也被视为一个文件,称为目录文件。
-
索引结点
在检索目录时,只用到了文件名,因此有的系统采用文件名与文件描述分开的方法,使文件描述信息单独形成一个称为索引结点的数据结构,简称 i 结点(inode)。
在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成。
假设一个FCB为64B,盘块大小是1KB,则每个盘块中可以存放16个FCB(FCB必须连续存放),若一个文件目录共有640个FCB,则查找文件平均需要启动磁盘20次。
而在UNIX系统中,一个目录项仅占16B,其中14B是文件名,2B是 i 结点指针。在1KB的盘块中可存放64个目录项。这样,可使查找文件的平均启动磁盘次数减少到原来的1/4,大大节省了系统开销。
-
磁盘索引结点
它是指存放在磁盘上的索引结点。每个文件有一个唯一的磁盘索引结点,主要包括以下内容:
-
文件主标识符,拥有该文件的个人或小组的标识符。
-
文件类型,包括普通文件、目录文件或特别文件。
-
文件存取权限,各类用户对该文件的存取权限。
-
文件物理地址,每个索引结点中含有13个地址项,即iaddr(0)~iaddr(12),它们以直接或间接方式给出数据文件所在盘块的编号。
-
文件长度,指以字节为单位的文件长度。
-
文件链接计教,在本文件系统中所有指向该文件的文件名的指针计数。
-
文件存取时间,本文件最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间。
-
-
内存索引结点
它是指存放在内存中的索引结点。当文件被打开时,要将磁盘索引结点复制到内存的索引结点中,便于以后使用。在内存索引结点中增加了以下内容:
- 索引结点编号,用于标识内存索引结点。
- 状态,指示 i 结点是否上锁或被修改。
- 访问计数,每当有一进程要访问此 i 结点时,计数加1;访问结束减1。
- 逻辑设备号,文件所属文件系统的逻辑设备号。
- 链接指针,设置分别指向空闲链表和散列队列的指针。
-
4.1.3 文件的操作
-
文件的基本操作
文件属于抽象数据类型。为了正确地定义文件,需要考虑可以对文件执行的操作。操作系统提供系统调用,它对文件进行创建、写、读、重定位、删除和截断等操作。
-
创建文件(create系统调用)
- 为新文件分配必要的外存空间;
- 在目录 中为之创建一个目录项,目录项记录了新文件名、在外存中的地址及其他可能的信息。
-
删除文件(delete系统调用)
- 先从目录中检索指定文件名的目录项
- 然后释放该文件所占的存储空间,以便可被其他文件重复使用,并删除目录条目。
-
读文件(read系统调用)
- 对于给定文件名,搜索目录以查找文件位置。
- 系统维护一个读位置的指针。
- 每当发生读操作时,更新读指针。
-
写文件(write系统调用)
- 对于给定文件名,搜索目录以查找文件位置。
- 系统必须为该文件维护一个写位置的指针。
- 每当发生写操作时,便更新写指针。
一个进程通常只对一个文件读或写,因此当前操作位置可作为每个进程当前文件位置的指针。
由于读和写操作都使用同一指针,因此节省了空间,也降低了系统复杂度。
-
重新定位文件
也称文件定位。搜索目录以找到适当的条目,并将当前文件位置指针重新定位到给定值。
重新定位文件不涉及读、写文件。
-
截断文件
允许文件所有属性不变,并删除文件内容,将其长度置为0并释放其空间。
这6个基本操作可以组合起来执行其他文件操作。例如,一个文件的复制,可以创建新文件、从旧文件读出并写入新文件。
-
-
文件的打开与关闭
-
打开文件(open系统调用)
- 过程:调用open根据文件名搜索目录,将指明文件的属性(包括该文件在外存上的物理位置),从外存复制到内存打开文件表的一个表目中,并将该表目的编号(也称索引)返回给用户。
打开文件时并不会把文件数据直接读入内存。“索引号”也称“文件描述符”。
打开文件之后,对文件的操作不再需要每次都查询目录,可以根据内存中的打开文件表进行操作。
如上图所示,在多个不同进程同时打开文件的操作系统中,通常采用两级表:整个系统表和每个进程表。
- 整个系统的打开文件表包含FCB的副本及其他信息。
- 每个进程的打开文件表根据它打开的所有文件,包含指向系统表中适当条目的指针。
一旦有进程打开了一个文件,系统表就包含该文件的条目。当另一个进程执行调用open时,只不过是在其文件打开表中增加一个条目,并指向系统表的相应条目。
-
关闭文件(close系统调用)
- 1.将进程的打开文件表相应表项删除
- 2.回收分配给该文件的内存空间等资源
- 3.系统打开文件表的打开计数器count减1,若count=0,则删除对应表项。
系统打开文件表为每个文件关联一个打开计数器(OpenCount),以记录多少进程打开了该文件。
文件名不必是打开文件表的一部分,因为一且完成对FCB在磁盘上的定位,系统就不再使用文件名。对于访问打开文件表的索引,UNIX称之为文件描述符,而Windows称之为文件句柄。
因此,只要文件未被关闭,所有文件操作就通过打开文件表来进行。- 打开文件信息
- 文件指针。系统跟踪上次的读写位置作为当前文件位置的指针,这种指针对打开文件的某个进程来说是唯一的,因此必须与磁盘文件属性分开保存。
- 文件打开计数。计数器跟踪当前文件打开和关闭的数量。因为多个进程可能打开同一个文件,所以系统在删除打开文件条目之前,必须等待最后一个进程关闭文件。
- 文件磁盘位置。大多数文件操作要求系统修改文件数据。查找磁盘上的文件所需的信息保存在内存中,以便系统不必为每个操作都从磁盘上读取该信息。
- 访问权限。每个进程打开文件都需要有一个访问模式(创建、只读、读写、添加等)。该信息保存在进程的打开文件表中,以便操作系统能够允许或拒绝后续的I/O请求。
-
4.1.4 文件保护
文件保护通过口令保护、加密保护和访问控制等方式实现。其中,口令和加密是为了防止用户文件被他人存取或窃取,而访问控制则用于控制用户对文件的访问方式。
-
口令保护
为文件设置一个“口令”,用户想要访问文件时需要提供口令,由系统验证口令是否正确。
实现开销小,但“口令”一般存放在FCB或索引结点中(也就是存放在系统中)因此不太安全
-
加密保护
用一个“密码“对文件加密,用户想要访问文件时,需要提供相同的“密码“才能正确的解密
安全性高,但加密解密需要耗费一定的时间(Eg:异或加密)
-
访问控制
-
访问类型
对文件的保护可从限制对文件的访问类型中出发。可加以控制的访问类型主要有以下几种。
- 读。从文件中读。
- 写。向文件中写。
- 执行。将文件装入内存并执行。
- 添加。将新信息添加到文件结尾部分。
- 删除。删除文件,释放空间。
- 列表清单。列出文件名和文件属性。
此外还可以对文件的重命名、复制、编辑等加以控制。这些高层的功能可以通过系统程序调用低层系统调用来实现。保护可以只在低层提供。
-
访问控制
解决访问控制最常用的方法是根据用户身份进行控制。而实现基于身份访问的最为普通的方法是,为每个文件和目录增加一个访问控制列表(Access-Control List,ACL),以规定每个用户名及其所允许的访问类型。
- 优点:可以使用复杂的访问方法,
- 缺点:长度无法预计并且可能导致复杂的空间管理,
使用精简的访问列表可以解决这个问题,精简的访问列表采用拥有者、组和其他三种用户类型。
- 拥有者。创建文件的用户。
- 组。一组需要共享文件且具有类似访问的用户。
- 其他。系统内的所有其他用户。
文件主在创建文件时,说明创建者用户名及所在的组名,系统在创建文件时也将文件主的名字、所属组名列在该文件的FCB中。用户访问该文件时,
- 若用户是文件主,按照文件主所拥有的权限访问文件;
- 若用户和文件主在同一个用户组,则按照同组权限访问,
- 否则只能按其他用户权限访问。
-
4.1.5 文件的逻辑结构
文件的逻辑结构是从用户观点出发看到的文件的组织形式。文件的物理结构(存储结构)是从实现观点出发看到的文件在外存上的存储组织形式。
文件的逻辑结构与存储介质特性无关,它实际上是指在文件的内部,数据逻辑上是如何组织起来的。
-
无结构文件(流式文件)
无结构文件将数据按顺序组织成记录并积累、保存,它是有序相关信息项的集合,以字节(Byte)为单位。
-
只能通过穷举搜索的方式访问记录。
-
其管理简单,用户操作方便。
-
对基本信息单位操作不多的文件适于采用字符流的无结构文件。例如源程序文件、目标代码文件等。
-
-
有结构文件(记录式文件)
-
顺序文件
文件中的记录一个接一个地顺序排列(逻辑上),记录可以是定长的或可变长的。
各个记录在物理上可以顺序存储或链式存储。
-
链式存储:无论是定长何变长记录,都无法实现随机存取,每次只能从第一个记录开始依次往后查找
-
顺序存储:
可实现随机存取,记录长度为L,则第ⅰ个记录存放的相对位置是i*L
若采用串结构,记录之间的顺序与关键字无关,无法快速找到某关键字对应的记录
若采用顺序结构,可以快速找到某关键字对应的记录(如折半查找)
定长记录的顺序文件,若物理上采用顺序存储,则可实现随机存取:若能再保证记录的顺序结构,则可实现快速检索(即根据关键字快速找到对应记录)
优点:读写一大批文件时,效率最高。适用于顺序存储设备(磁带)
缺点:不方便增加、删除记录
-
-
索引文件
-
索引表:高效查询变长记录文件。索引表本身是定长记录的顺序文件,因此可以快速找到第ⅰ个记录对应的索引项。
-
方式:可将关键字作为索引号内容,若按关键字顺序排列,则还可以支持按照关键字折半查找
每当要增加/删除一个记录时,需要对索引表进行修改。由于索引文件有很快的检索速度,因此主要用于对信息处理的及时性要求比较高的场合。
-
-
索引顺序文件
索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中,同样会为文件建立一张索引表,但不同的是:并不是每个记录对应一个索引表项,而是一组记录对应一个索引表项。
- 将记录分组,每组对应一个素引表项
- 检素记录时先顺序查索引表,找到分组,再顺序查找分组
- 当记录过多时,可建立多级素引表
如上图所示,主文件名包含姓名和其他数据项。
- 姓名为关键字,索引表中为每组的第一条记录(不是每条记录)的关键字值,用指针指向主文件中该记录的起始位置。
- 索引表只包含关键字和指针两个数据项,所有姓名关键字递增排列。
- 主文件中记录分组排列,同一个组中的关键字可以无序,但组与组之间的关键字必须有序。
- 查找一条记录时,首先通过索引表找到其所在的组,然后在该组中使用顺序查找,就能很快地找到记录。
-
直接文件或散列文件(Hash File)
给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件或索引文件,没有顺序的特性。
散列文件有很高的存取速度,但是会引起冲突,即不同关键字的散列函数值相同。
-
4.1.6 文件的物理结构
文件的物理结构就是研究文件的实现,即文件数据在物理存储设备上是如何分布和组织的。
文件分配对应于文件的物理结构,是指如何为文件分配磁盘块。常用的磁盘空间分配方法有三种:连续分配、链接分配和索引分配。
-
连续分配
连续分配方法要求每个文件在磁盘上占有一组连续的块。磁盘地址定义了磁盘上的一个线性排序,这种排序使作业访问磁盘时需要的寻道数和寻道时间最小。
- 物理块号=起始块号+逻辑块号
- 优点:支持顺序访问和直接访问(即随机访问);连续分配的文件在顺序访问时速度最快。
- 缺点:不方便文件拓展、存储空间利用率低、会产生磁盘碎片(外部碎片)。
- ①文件长度不宜动态增加,因为一个文件末尾后的盘块可能已分配给其他文件,一旦需要增加,就需要大量移动盘块。
- ②为保持文件的有序性,删除和插入记录时,需要对相邻的记录做物理上的移动,还会动态改变文件的长度。
- ③反复增删文件后会产生外部碎片(与内存管理分配方式中的碎片相似)。
- ④很难确定一个文件需要的空间大小,因而只适用于长度固定的文件。
- 访存次数:访问第n条记录需访问磁盘1次
-
链接分配
链接分配采取离散分配的方式,可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
访问第n条记录需访问磁盘n次
-
隐式链接
除文件的最后一个盘块之外,每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
- 优点:很方便文件拓展,不会有碎片问题,外存利用率高。
- 缺点:只支持顺序访问,不支持随机访问,查找效率低,指向下一个盘块的指针也需要耗费少量的存储空间。
- 结论:采用隐式链接的链接分配方式,很方便文件拓展。另外,所有的空闲磁盘块都可以被利用,不会有碎片问题,外存利用率高
-
显式链接
把用于链接文件各物理块的指针显式地存放在文件分配表(FAT)中。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存,并常驻内存。
- 优点:很方便文件拓展,不会有碎片问题,外存利用率高,并且支持随机访问。相比于隐式链接来说,地址转换时不需要访问磁盘,因此文件的访问效率更高。
- 缺点:文件分配表的需要占用一定的存储空间。
- 结论:采用链式分配(显式链接)方式的文件,支持顺序访问,也支持随机访问(想访问ⅰ号逻辑块时,并不需要依次访问之前的0~i-1号逻辑块),由于块号转换的过程不需要访问磁盘,因此相比于隐式链接来说,访问速度快很多。
-
文件分配表:FAT不仅记录了文件分配信息(显示链接),还“兼职”做了空闲块管理
-
-
索引分配
索引分配允许文件离散地分配在各个磁盘块中,系统会为每个文件建立一张索引表,索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
索引表的 逻辑块号 可以是隐含的,进一步节约空间;
-
链接方案
如果索引表太大,一个索引块装不下,那么可以将多个索引块链接起来存放。
缺点:需要顺序访问,当文件很大时,查我效率低下
-
多层索引
建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。
采用K层索引结构,且顶级索引表未调入内存,则访问一个数据块只需要K+1次读磁盘操作
缺点:即使是小文件,访问数据块也需受K+1次读磁盘
-
混合索引
多种索引分配方式的结合。例如,一个文件的顶级索引表中,既包含直接地址索引(直接指向数据块),又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。
所允许的文件最大长度:设有N0个直接地址项;N1个一次间接地址项;N2个二次间接地址项;每个盘块大小M字节;盘块号占m个字节,公式如下:
文件最大长度 = ( N 0 + N 1 ⋅ M m + N 2 ⋅ ( M m ) 2 ) ⋅ M 文件最大长度=(N_0 + N_1·\frac{M}{m}+N_2·(\frac{M}{m})^2)·M 文件最大长度=(N0+N1⋅mM+N2⋅(mM)2)⋅M
优点:对于小文件,只需较少的读磁盘次数就可以访问目标数据块。(一般计算机中小文件更多) -
总结
-
4.2 目录
4.2.1 目录的基本概念
文件目录指FCB的有序集合,一个FCB就是一个文件的目录项。与文件管理系统和文件集合相关联的是文件目录,它包含有关文件的属性、位置和所有权等。
- 目录管理的基本要求:
- 从用户的角度看,目录在用户(应用程序)所需要的文件名和文件之间提供一种映射,所以目录管理要实现“按名存取";
- 目录存取的效率直接影响到系统的性能,所以要提高对目录的检索速度;
- 在多用户系统中,应允许多个用户共享一个文件,因此目录还需要提供用于控制访问文件的信息。
- 此外,应允许不同用户对不同文件采用相同的名字,以便于用户按自己的习惯给文件命名,目录管理通过树形结构来解决和实现。
4.2.2 目录结构
-
单级目录结构
在整个文件系统中只建立一张目录表,每个文件占一个目录项,不允许文件重名,如下图所示。
当访问一个文件时,先按文件名在该目录中查找到相应的FCB,经合法性检查后执行相应的操作。
当建立一个新文件时,必须先检索所有目录项,以确保没有“重名”的情况,然后在该目录中增设一项,把新文件的属性信息填入到该项中。
-
两级目录结构
将文件目录分成主文件目录(MFD)和用户文件目录(UFD)两级,不同用户的文件可以重名,但不能对文件分类。
主文件目录项记录用户名及相应用户文件目录所在的存储位置。
用户文件目录项记录该用户文件的FCB信息。
-
树形目录结构
不同目录下的文件可以重名,可以对文件进行分类,不方便共享。
根据“文件路径”找到目标文件。用户(或用户进程)要访问某个文件时要用文件路径名标识文件,文件路径名是个字符串。各级日录之间用“/”隔开。从根目录出发的路径称为绝对路径。
例如:自拍.jpg的绝对路径是“/照片/2015-08/自拍jpg”
系统根据绝对路径一层一层地找到下一级目录。刚开始从外存读入根目录的目录表;找到“照片”目录的存放位置后,从外存读入对应的目录表;再找到“2015-08”目录的存放位置,再从外存读入对应目录表;最后才找到文件“自拍Jpg”的存放位置。整个过程需要3次读磁盘I/O操作。
引入“当前目录”和“相对路径”后,磁盘I/O的次数减少了。这就提升了访问文件的效率。
从根目录出发是绝对路径;从当前目录出发是相对路径。
-
无环图目录结构
在树形目录的基础上,增加一些指向同一结点的有向边,使整个目录成为一个有向无环图,实现文件的共享。
为共享结点设置一个共享计数器,计数器为0时才真正删除该结点。
对于共享文件,只存在一个真正的文件,任何改变都会为其他用户所见。
4.2.3 目录的操作
- 搜索。当用户使用一个文件时,需要搜索目录,以找到该文件的对应目录项。
- 创建文件。当创建一个新文件时,需要在目录中增加一个目录项。
- 删除文件。当删除一个文件时,需要在目录中删除相应的目录项。
- 创建目录。在树形目录结构中,用户可创建自己的用户文件目录,并可再创建子目录。
- 删除目录。有两种方式:①不删除非空目录,删除时要先删除目录中的所有文件,并递归地删除子目录。②可删除非空目录,目录中的文件和子目录同时被删除。
- 移动目录。将文件或子目录在不同的父目录之间移动,文件的路径名也会随之改变。
- 显示目录。用户可以请求显示目录的内容,如显示该用户目录中的所有文件及属性。
- 修改目录。某些文件属性保存在目录中,因而这些属性的变化需要改变相应的目录项。
4.2.4 目录实现
目录实现有线性列表和哈希表两种方式,线性列表实现对应线性查找,哈希表的实现对应散列查找。
-
线性列表
最简单的目录实现方法是,采用文件名和数据块指针的线性列表。
- 当创建新文件时,必须首先搜索目录以确定没有同名的文件存在,然后在目录中增加一个新的目录项。
- 当删除文件时,则根据给定的文件名搜索目录,然后释放分配给它的空间。
- 当要重用目录项时有许多种方法:
- 可以将目录项标记为不再使用,或将它加到空闲目录项的列表上,
- 还可以将目录的最后一个目录项复制到空闲位置,并减少目录的长度。
采用链表结构可以减少删除文件的时间。
线性列表的优点在于实现简单,不过由于线性表的特殊性,查我比较费时。
-
哈希表
哈希表根据文件名得到一个值,并返回一个指向线性列表中元素的指针。
- 优点:查找非常迅速,插入和删除也较简单,
- 问题:需要一些措施来避免冲突(两个文件名称哈希到同一位置)。
为了减少I/O操作,把当前使用的文件目录复制到内存,以后要使用该文件时只需在内存中操作,因此降低了磁盘操作次数,提高了系统速度。
4.2.5 文件共享
文件共享使多个用户共享同一个文件,系统中只需保留该文件的一个副本。
-
基于索引结点的共享方式(硬链接)
各个用户的目录项指向同一个索引结点,索引结点中需要链接计数count,用于表示链接到本索引结点上的用户目录项数。
某用户删除文件只是删除该用户的目录项,count–
只有count==0才能真正删除文件数据和索引结点。
-
利用符号链实现文件共享(软链接)
为使用户B能共享用户A的一个文件F,可以由系统创建一个LINK类型的新文件,也取名为F,并将该文件写入用户B的目录中,以实现用户B的目录与文件F的链接。
在一个Link型的文件中记录共享文件的存放路径(Windows快捷方式),操作系统根据路径一层层查找目录,最终找到共享文件。
当User3访问“ccc”时,操作系统判断文件“ccc”属于Link类型文件,于是会根据其中记录的路径层层查找目录,最终找到User1的目录表中的“aaa”表项,于是就找到了文件1的索引结点。
即使软链接指向的共享文件已被删除,Link型文件依然存在,只是通过Link型文件中的路径去查找共享文件会失败(找不到对应目录项)。
由于用软链接的方式访问共享文件时要查询多级目录,会有多次磁盘I/O,因此用软链接访问的速度要比硬链接更慢。
硬链接和软链接都是文件系统中的静态共享方法,在文件系统中还存在着另外的共享需求,即两个进程同时对同一个文件进行操作,这样的共享称为动态共享。
4.3 文件系统
4.3.1 文件系统结构
文件系统(File system)提供高效和便捷的磁盘访问,以便允许存储、定位、提取数据。
用一个例子来辅助记忆文件系统的层次结构:
假设某用户请求删除文件"D:/工作目录/学生信息.xIsx"的最后100条记录。
- 用户需要通过操作系统提供的接口发出上述请求一一用户接口
- 由于用户提供的是文件的存放路径,因此需要操作系统一层一层地查找目录,找到对应的目录项一一文件目录系统
- 不同的用户对文件有不同的操作权限,因此为了保证安全,需要检查用户是否有访问权限一一存取控制模块(存取控制验证层)
- 验证了用户的访问权限之后,需要把用户提供的“记录号”转变为对应的逻辑地址一一逻辑文件系统与文件信息缓冲区
- 知道了标记录对应的逻辑地址后,还需要转换成实际的物理地址一一物理文件系统
- 要删除这条记录,必定要对磁盘设备发出请求一一设备管理程序模块
- 删除这些记录后,会有一些盘块空闲,因此要将这些空闲盘块回收一一辅助分配模块
4.3.2 文件系统布局
-
文件系统在磁盘中的结构
文件系统存放在磁盘上,多数磁盘划分为一个或多个分区,每个分区中有一个独立的文件系统。文件系统可能包括如下信息:启动存储在那里的操作系统的方式、总的块数、空闲块的数量和位置、目录结构以及各个具体文件等。如下图所示。
-
主引导记录(MasterBootRecord,MBR),位于磁盘的0号扇区,用来引导计算机,MBR后面是分区表,该表给出每个分区的起始和结束地址。表中的一个分区被标记为活动分区,当计算机启动时,BIOS读入并执行MBR。MBR做的第一件事是确定活动分区,读入它的第一块,即引导块。
-
引导块(bootblock),MBR执行引导块中的程序后,该程序负责启动该分区中的操作系统。为统一起见,每个分区都从一个引导块开始,即使它不含有一个可启动的操作系统,也不排除以后会在该分区安装一个操作系统。Windows系统称之为分区引导扇区。
除了从引导块开始,磁盘分区的布局是随着文件系统的不同而变化的。文件系统经常包含有如上图所列的一些项目。
-
超级块(superblock),包含文件系统的所有关键信息,在计算机启动时,或者在该文件系统首次使用时,超级块会被读入内存。超级块中的典型信息包括分区的块的数量、块的大小、空闲块的数量和指针、空闲的FCB数量和FCB指针等。
-
文件系统中空闲块的信息,可以使用位示图或指针链接的形式给出。
-
i 结点。索引结点,连续存放,每个文件对应一个结点,可以把 i 结点区看成一个大数组;
-
根目录,它存放文件系统目录树的根部。
-
其他部分,存放了其他所有的目录和文件。
-
-
文件系统在内存中的结构
内存中的信息用于管理文件系统并通过缓存来提高性能。这些数据在安装文件系统时被加载,在文件系统操作期间被更新,在卸载时被丢弃。这些结构的类型可能包括:
- 内存中的安装表(mount table),包含每个己安装文件系统分区的有关信息。
- 内存中的目录结构的缓存,包含最近访问目录的信息。对安装分区的目录,它可以包括一个指向分区表的指针。
- 整个系统的打开文件表,包含每个打开文件的FCB副本及其他信息。
- 每个进程的打开文件表,包含一个指向整个系统的打开文件表中的适当条目的指针,以及其他信息。
进程创建:
为了创建新的文件,应用程序调用逻辑文件系统。逻辑文件系统知道目录结构的格式,它将为文件分配一个新的FCB。然后,系统将相应的目录读入内存,使用新的文件名和FCB进行更新,并将它写回磁盘。
一旦文件被创建,它就能用于I/O,不过,首先要打开文件。系统调用open()将文件名传递给逻辑文件系统。
- 调用open()首先搜索整个系统的打开文件表,以确定这个文件是否已被其他进程使用。
- 如果已被使用,则在单个进程的打开文件表中创建一个条目,让其指向现有整个系统的打开文件表的相应条目。该算法在文件已打开时,能节省大量开销。
- 如果这个文件尚未打开,则根据给定文件名来搜索目录结构。部分目录结构通常缓存在内存中,以加快目录操作。
- 找到文件后,它的FCB会复制到整个系统的打开文件表中;该表不但存储FCB,而且跟踪打开该文件的进程的数量。
- 然后,在单个进程的打开文件表中创建一个条目,并且通过指针将整个系统打开文件表的条目与其他域(如文件当前位置的指针和文件访问模式等)相连。
- 调用open()返回的是一个指向单个进程的打开文件表中的适当条自的指针。以后,所有文件操作都通过该指针执行。
- 一旦文件被打开,内核就不再使用文件名来访问文件,而使用文件描述符(Windows称之为文件句柄)
进程关闭:
当进程关闭一个文件时,就会删除单个进程打开文件表中的相应条目,整个系统的打开文件表的文件打开数量也会递减。当所有打开某个文件的用户都关闭该文件后,任何更新的元数据将复制到磁盘的目录结构中,并且整个系统的打开文件表的对应条目也会被删除。
4.3.3 外存空闲空间管理
一个存储设备可以按整体用于文件系统,也可以细分。例如,一个磁盘可以划分为4个分区,每个分区都可以有单独的文件系统。包含文件系统的分区通常称为卷(volumme)。卷可以是磁盘的一部分,也可以是整个磁盘,还可以是多个磁盘组成RAID集,如图所示。
在一个卷中,存放文件数据的空间(文件区)和FCB的空间(目录区)是分离的。
文件存储设备分成许多大小相同的物理块,并以块为单位交换信息,因此,文件存储设备的管理实质上是对空闲块的组织和管理,它包括空闲块的组织、分配与回收等问题。
-
空闲表法
空闲表法属于连续分配方式,它与内存的动态分配方式类似,为每个文件分配一块连续的存储空间。
-
盘块的分配
与内存管理中的动态分区分配很类似,为一个文件分配连续的存储空间。
同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
-
盘块的回收
与内存管理中的动态分区分配很类似,当回收某个存储区时需要有四种情况:
-
①回收区的前后都没有相邻空闲区
-
②回收区的前后都是空闲区
-
③回收区前面是空闲区
-
④回收区后面是空闲区
总之,回收时需要注意表项的合并问题
-
-
-
空闲链表法
将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同,分为两种形式:
-
空闲盘块链:将磁盘上的所有空闲空间以盘块为单位拉成一条链。
操作系统保存着链头、链尾指针。
- 如何分配:若某文件申请K个盘块,则从链头开始依次摘下K个盘块分配,并修改空闲链的链头指针。
- 如何回收:回收的盘块依次挂到链尾,并修改空闲链的链尾指针。
适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作
-
空闲盘区链:将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。
操作系统保存着链头、链尾指针。
-
如何分配:
若某文件申请K个盘块,则可以采用首次适应、最佳适应等算法,从链头开始检索,按照算法规则找到一个大小符合要求的空闲盘区,分配给文件。
若没有合适的连续空闲块,也可以将不同盘区的盘块同时分配给一个文件,注意分配后可能要修改相应的链指针、盘区大小等数据。
-
如何回收:若回收区和某个空闲盘区相邻,则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻,将回收区作为单独的一个空闲盘区挂到链尾。
离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。
-
-
-
位示图法
位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况,磁盘上所有的盘块都有一个二进制位与之对应。当其值为“0”时,表示对应的盘块空闲;为“1”时,表示已分配。
这样,一个m×n位组成的位示图就可用来表示m×n个盘块的使用情况,如图所示。行为位号,列为字号
注意:盘块号、字号、位号到底是从0开始,还是从1开始。两者计算盘块号方式不同。
-
盘块的分配
-
顺序扫描位示图,从中找出一个或一组其值为“0”的二进制位。
-
将找到的一个或一组二进制位,转换成与之对应的盘块号。若找到的其值为“0”的二进制位位于位示图的第i行、第j列,则其相应的盘块号应按下式计算(n为每行位数):
{ b = n ( i − 1 ) + j , 字、位、盘块号从1开始 b = n i + j 字、位、盘块号从0开始 \begin{cases}b=n(i-1)+j, & \text{字、位、盘块号从1开始}\\ b=ni+j& \text{字、位、盘块号从0开始}\end{cases} {b=n(i−1)+j,b=ni+j字、位、盘块号从1开始字、位、盘块号从0开始 -
修改位示图,令 m a p [ i , j ] = 1 map[i,j]=1 map[i,j]=1
-
-
盘块的回收
-
将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为
{ i = ( b − 1 ) / n + 1 ; j = ( b − 1 ) % n + 1 , 字、位、盘块号从1开始 i = b / n ; j = b % n , 字、位、盘块号从0开始 \begin{cases}i=(b-1)/n+1;j=(b-1)\% n+1, & \text{字、位、盘块号从1开始}\\ i=b/n;j=b\% n, & \text{字、位、盘块号从0开始}\end{cases} {i=(b−1)/n+1;j=(b−1)%n+1,i=b/n;j=b%n,字、位、盘块号从1开始字、位、盘块号从0开始 -
修改位示图,令 m a p [ i , j ] = 0 map[i,j]=0 map[i,j]=0。
-
空闲表法和空闲链表法都不适用于大型文件系统,因为这会使空闲表或空闲链表太大。
-
-
成组链接法
在UNIX系统中采用的是成组链接法,这种方法结合了空闲表和空闲链表两种方法,它具有上述两种方法的优点,克服了两种方法均有的表太长的缺点。
文件卷的目录区中专门用一个磁盘块作为“超级块”,当系统启动时需要将超级块读入内存。并且要保
证内存与外存中的“超级块”数据一致。用来存放一组空闲盘块号(空闲盘块的块号)的盘块称为成组链块。
-
成组链接思想:把顺序的n个空闲盘块号保存在第一个成组链块中,其最后一个空闲盘块(作为成组链块)则用于保存另一组空闲盘块号,如此继续,直至所有空闲盘块均予以链接。
-
盘块的分配
分配1个空闲块:
- ①检查第一个分组的块数是否足够。1<100,是足够的。
- ②分配第一个分组中的1个空闲块,并修改相应数据
分配100个空闲块:
- ①检查第一个分组的块数是否足够。100=100,是足够的。
- ②分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息,因此300号块的数据需要复制到超级块中
-
盘块的回收
需要将超级块中的数据复制到新回收的块中,并修改超级块的内容,让新回收的块成为第一个分组。
-
4.3.4 虚拟文件系统
虚拟文件系统(VFS)为用户程序提供了文件系统操作的统一接口,屏蔽了不同文件系统的差异和操作细节。
-
普通文件系统
下图普通的文件系统,不同的外部存储设备,它的文件系统可能是不相同的,对于同一个操作的函数方法定义也许也各不相同;
-
虚拟文件系统
下图为虚拟文件系统,用户程序可以通过VFS提供的统一调用函数(如open()等)来操作不同文件系统的文件,而无须考虑具体的文件系统和实际的存储介质。
虚拟文件系统采用了面向对象的思想,它抽象出一个通用的文件系统模型,定义了通用文件系统都支持的接口。新的文件系统只要支持并实现这些接口,即可安装和使用。
为了实现VFS,Linux主要抽象了四种对象类型。每个VFS对象都存放在一个适当的数据结构中,其中包括对象的属性和指向对象方法(函数)表的指针。
- 超级块对象:表示一个已安装(或称挂载)的特定文件系统。
- 索引结点对象:表示一个特定的文件。
- 目录项对象:表示一个特定的目录项。
- 文件对象:表示一个与进程相关的已打开文件。
进程与VFS对象之间的交互如下图所示。
三个不同的进程已打开了同一个文件,其中两个进程使用同一个硬链接。
在这种情况下,每个进程都使用自己的文件对象,但只需要两个目录项对象,每个硬链接对应一个目录项对象。这两个目录项对象指向同一个索引结点对象, 这个索引结点对象标识的是超级块对象及随后的普通磁盘文件。
对于不同文件系统的数据结构,VFS 在每打开一个文件,就在主存建立一个vnode,用统一的数据结构表示文件;
打开文件后,创建vnode,并将文件信息复制到vnode中,vnode的功能指针指向具体文件系统的函数功能
vnode只存在于主存中,而inode既会被调入主存,也会在外存中存储
特点:
- ①向上层用户进程提供统一标准的系统调用接口,屏蔽底层具体文件系统的实现差异
- ②VFS要求下层的文件系统必须实现某些规定的函数功能,如:open/read/write。一个新的文件系统想要在某操作系统上被使用,就必须满足该操作系统VFS的要求
- ③每打开一个文件,VFS就在主存中新建一个vnode,用统一的数据结构表示文件,无论该文件存储在哪个文件系统
4.3.5 分区和安装
-
分区
-
物理格式化(低级格式化):划分扇区、检测坏扇区、用备用扇区替换坏扇区;当要访问某一块坏扇区时,会使用备用扇区,默默完成替换工作;
-
逻辑格式化(高级格式化):磁盘分区;每个区的大小、地址范围等信息,会使用 分区表 来记录;
在每个区里可以建立各自独立的文件系统 ,例如在C盘里建立UNIZX文件系统;
分区的第一部分是引导块,里面存储着引导信息,它有自身的格式,因为在引导时系统并未 加载文件系统代码,因此不能解释文件系统的格式。下图为一个典型的Linux分区。
-
-
安装
文件系统在进程使用前必须先安装,也称挂载,任务是将一个文件系统挂载到操作系统中。
功能:
- ①在VFS中注册新挂载的文件系统。内存中的挂载表(mount table)包含每个文件系统的相关信息,包括文件系统类型、容量大小等。
- ②新挂载的文件系统,要向VFS提供一个函数地址列表
- ③将新文件系统加到挂载点(mountpoint),也就是将新文件系统挂载在某个父目录下
UNIX本身是一个固定的目录树,只要安装就有,但是如果不给它分配存储空间,就不能对它进行操作,所以首先要给根目录分配空间,这样才能操作这个目录树。
5 输入/输出(I/O)管理
5.1 I/O管理概述
5.1.1 I/O设备
I/O设备是将数据输入到计算机中,或者可以接收计算机输出数据的外部设备,属于计算机中的硬件部件;
-
设备的分类
-
按使用特性分类:
- 人机交互类外部设备:鼠标、键盘、打印机等,用于人机交互。数据传输速度慢。
- 存储设备:移动硬盘、光盘等,用于数据存储。数据传输速度快。
- 网络通信设备:调制解调器等,用于网络通信。数据传输速度介于上述二者之间。
-
按信息交换的单位分类:
- 块设备。信息交换以数据块为单位。它属于有结构设备,如磁盘等。磁盘设备的基本特征是传输速率较高、可寻址,即对它可随机地读/写任意一块。
- 字符设备。信息交换以字符为单位。它属于无结构类型,如交互式终端机、打印机等。
-
按传输速率分类:
- 低速设备。传输速率仅为每秒几字节到数百字节的一类设备,如键盘、鼠标等。
- 中速设备。传输速率为每秒数千字节至数万字节的一类设备,如激光打印机等。
- 高速设备。传输速率在数百千字节至千兆字节的一类设备,如磁盘机、光盘机等。
-
-
I/O接口
I/O接口(设备控制器)位于CPU与设备之间,它既要与CPU通信,又要与设备通信,还要具有按CPU发来的命令去控制设备工作的功能,主要由三部分组成,如下图所示。
-
组成部分:
-
设备控制器与CPU的接口:实现控制器与CPU之间的通信
该接口有三类信号线:数据线、地址线和控制线。
数据线与两类寄存器相连:数据寄存器(存放从设备送来的输入数据或从CPU送来的输出数据)和控制/状态寄存器(存放从CPU送来的控制信息或设备的状态信息)。
-
设备控制器与设备的接口:实现控制器与设备之间的通信
一个设备控制器可以连接一个或多个设备,因此控制器中有一个或多个设备接口。
每个接口中都存在数据、控制和状态三种类型的信号。
-
I/O逻辑:负责识别CPU发出的命令,并向设备发出命令
用于实现对设备的控制。它通过一组控制线与CPU交互,对从CPU收到的I/O命令进行译码。
CPU启动设备时,将启动命令发送给控制器,同时通过地址线把地址发送给控制器,由控制器的I/O逻辑对地址进行译码,并相应地对所选设备进行控制。
-
-
主要功能:
- 接受和识别CPU发出的指令(控制寄存器)
- 向CPU报告设备的状态(状态寄存器)
- 数据交换(数据寄存器暂存数据)
- 地址识别(由I/O逻辑实现)
- 数据缓冲
- 差错控制
-
-
I/O端口
I/O端口是指设备控制器中可被CPU直接访问的寄存器,主要有以下三类寄存器。
-
寄存器类型:
- 数据寄存器:实现CPU和外设之间的数据缓冲。
- 状态寄存器:获取执行结果和设备的状态信息,以让CPU知道是否准备好。
- 控制寄存器:由CPU写入,以便启动命令或更改设备模式。
-
实现I/O端口通信,有两种编址方法:
- 独立编址。为每个端口分配一个I/O端口号,所有I/O端口形成I/O端口空间,普通用户程序不能对其进行访问,只有操作系统使用特殊的I/O指令才能访问端口。
- 统一编址。又称内存映射I/O,每个端口被分配唯一的内存地址,且不会有内存被分配这地址,通常分配给端口的地址靠近地址空间的顶端。
-
5.1.2 I/O控制方式
设备管理的主要任务之一是控制设备和内存或CPU之间的数据传送。外围设备与内存之间的输入/输出控制方式有以下4种。
-
程序直接控制方式
如下图所示,计算机从外部设备读取的每个字,CPU需要对外设状态进行循环检查,直到确定该字已经在I/O控制器的数据寄存器中。
-
工作流程:
-
CPU干预的频率:很频繁,I/O操作开始之前、完成之后需要CPU介入,并且在等待I/O完成的过程中CPU需要不断地轮询检查。
-
数据传送的单位:每次读/写一个字
-
数据的流向:
- 读操作(数据输入):I/O设备→CPU→内存
- 写操作(数据输出):内存→CPU→I/O设备
- 每个字的读/写都需要CPU的帮助
-
优点:实现简单。在读/写指令之后,加上实现循环检查的一系列指令即可
-
缺点:CPU和I/O设备只能串行工作,CPU需要一直轮询检查,长期处于“忙等”状态,CPU利用率低。
-
-
中断驱动方式
中断驱动方式的思想是,允许I/O设备主动打断CPU的运行并请求服务,从而"解放” CPU,使得其向I/O控制器发送读命令后可以继续做其他有用的工作。
-
工作流程:
-
引入中断机制。由于I/O设备速度很慢,因此在CPU发出读/写命令后,可将等待I/O的进程阻塞,先切换到别的进程执行。
-
当I/O完成后,控制器会向CPU发出一个中断信号,CPU检测到中断信号后,会保存当前进程的运行环境信息,转去执行中断处理程序处理该中断。
-
处理中断的过程中,CPU从I/O控制器读一个字的数据传送到CPU寄存器,再写入主存。接着,CPU恢复等待I/O的进程(或其他进程)的运行环境,然后继续执行。
-
①CPU会在每个指令周期的末尾检查中断:
②中断处理过程中需要保存、恢复进程的运行环境,这个过程是需要一定时间开销的。可见,如果中断发生的须率太高,也会降低系统性能。- CPU干预的频率:每次I/O操作开始之前、完成之后需要CPU介入。等待I/O完成的过程中CPU可以切换到别的进程执行。
- 数据传送单位:每次读/写一个字
- 数据流向:
- 读操作(数据输入):I/O设备→CPU→内存
- 写操作(数据输出):内存→CPU→I/O设备
- 优点:与“程序直接控制方式”相比,在“中断驱动方式”中,I/O控制器会通过中断信号主动报告I/O已完成,CPU不再需要不停地轮询。CPU和I/O设备可并行工作,CPU利用率得到明显提升。
- 缺点:每个字在I/O设备与内存之间的传输,都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间。
-
-
DMA方式
DMA(直接存储器存取)方式的基本思想是在I/O设备和内存之间开辟直接的数据交换通路,彻底“解放”CPU。下图为DMA工作流程。
-
与“中断驱动方式”相比,DMA方式有这样几个改进:
- ①数据的传送单位是“块”。不再是一个字、一个字的传送:
- ②数据的流向是从设备直接放入内存,或者从内存直接到设备。不再需要CPU作为“快递小哥”。
- ③仅在传送一个或多个数据块的开始和结束时,才需要CPU干预,数据传送通过DMA控制器完成。
-
DMA控制器组成:
下图为DMA控制器的组成。
DMA控制器中设置如下4类寄存器:
- 数据寄存器(DR)。暂存从设备到内存或从内存到设备的数据。
- 内存地址寄存器(MAR)。在输入时,它存放把数据从设备传送到内存的起始目标地址;在输出时,它存放由内存到设备的内存源地址。
- 数据计数器(DC)。存放本次要传送的字(节)数,剩余要读/写的字节数。
- 命令/状态寄存器(CR)。接收从CPU发来的I/O命令、有关控制信息,或设备的状态。
-
CPU干预的频率:仅在传送一个或多个数据块的开始和结束时,才需要CPU干预。
-
数据传送单位:每次读/写一个或多个块(注意:每次读写的只能是连续的多个块,且这些块读入内存后在内存中也必须是连续的)
-
数据流向:
- 读操作(数据输入):I/O设备→内存
- 写操作(数据输出):内存→I/O设备
-
优点:数据传输以“块”为单位,CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存,数据传输效率进一步增加。CPU和I/O设备的并行性得到提升。
-
缺点:CPU每发出一条I/O指令,只能读/写一个或多个连续的数据块。如果要读/写多个离散存储的数据块,或者要将数据分别写到不同的内存区域时,CPU要发出多条I/O指令,进行多次中断处理才能完成。
-
-
通道控制方式
通道:I/O通道是指专门负责输入输出的处理机。是一种硬件,可以理解为是“弱鸡版的CPU”。通道可以识别并执行一系列通道指令。
与CPU相比,通道可以执行的指令很单一,并且通道程序是放在主机内存中的,也就是说通道与CPU共享内存
-
完成一次读写流程:
-
CPU干预的频率:极低,通道会根据CPU的指示执行相应的通道程序,只有完成一组数据块的读/写后才需要发出中断信号,请求CPU干预。
-
数据传送的单位:每次读/写一组数据块
-
数据的流向(在通道的控制下进行)
- 读操作(数据输入):I/O设备→内存
- 写操作(数据输出):内存→I/O设备
-
缺点:实现复杂,需要专门的通道硬件支持
-
优点:CPU、通道、I/O设备可并行工作,资源利用率很高。
-
5.1.3 I/O软件层次结构
为了更好地设计 I/O 软件,采用 层次式结构 的 I/O 软件;
一个比较合理的层次划分如上图所示。整个I/O软件可以视为具有4个层次的系统结构,各层次功能如下:
-
用户层软件
实现了与用户交互的接口,用户可直接使用该层提供的、与I/O操作相关的库函数对设备进行操作。
用户层软件将用户请求翻译成格式化的I/O请求,并通过“系统调用”请求操作系统内核的服务
-
设备独立性软件
设备独立性软件,又称设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现。
-
功能:
- ① 向上层提供统一的调用接口(如read/write系统调用)
- ② 设备的保护
- ③ 差错处理
- ④ 设备的分配与可收
- ⑤ 数据缓冲区管理
- ⑥ 建立逻辑设备名到物理设备名的映射关系;根据设备类型选择调用相应的驱动程序
-
逻辑设备
为实现设备独立性而引入了逻辑设备和物理设备这两个概念。在应用程序中,使用逻辑设备名来请求使用某类设备;而在系统实际执行时,必须将逻辑设备名映射成物理设备名使用。
使用逻辑设备名好处:
- ①增加设备分配的灵活性
- ②易于实现I/O重定向,指用于I/O操作的设备可以更换(即重定向),而不必改变应用程序。
设备独立性软件需要通过“逻辑设备表(LUT,Logical Unit Table)”来确定逻辑设备对应的物理设备,并找到该设备对应的设备驱动程序。
I/O设备被当做一种特殊的文件;不同类型的I/O设备需要有不同的驱动程序处理
操作系统系统可以采用两种方式管理逻辑设备表(LUT):
- 第一种方式,整个系统只设置一张LUT,这就意味着所有用户不能使用相同的逻辑设备名,因此这种方式只适用于单用户操作系统。
- 第二种方式,为每个用户设置一张LUT,各个用户使用的逻辑设备名可以重复,适用于多用户操作系统。系统会在用户登录时为其建立一个用户管理进程,而LUT就存放在用户管理进程的PCB中。
-
-
设备驱动程序
与硬件直接相关,负责具体实现系统对设备发出的操作指令,驱动I/O设备工作的驱动程序。 将上层发出的一系列命令(如read/write)转化成特定设备“能听得懂”的一系列操作。
不同设备的内部硬件特性也不同,这些特性只有厂家才知道,因此厂家须提供与设备相对应的驱动程序,CPU执行驱动程序的指令序列,来完成设置设备寄存器,检查设备状态等工作。
为I/O内核子系统隐藏设备控制器之间的差异。
-
中断处理程序
当I/O任务完成时,I/O控制器会发送一个中断信号,系统会根据中断信号类型找到相应的中断处理程序并执行。
-
中断处理程序的处理流程如下:
-
中断处理层的任务:
- 进行进程上下文的切换,
- 对处理中断信号源进行测试,
- 读取设备状态和修改进程状态等。
由于中断处理与硬件紧密相关,对用户而言,应尽量加以屏蔽,因此应放在操作系统的底层,系统的其余部分尽可能少地与之发生联系。
-
-
总结
说明用户对设备的一次命令过程如下所示:
- ①当用户要读取某设备的内容时,通过操作系统提供的read命令接口,这就经过了用户层。
- ②操作系统提供给用户使用的接口,一般是统一的通用接口,也就是几乎每个设备都可以响应的统一命令,如read命令,用户发出的read命令,首先经过设备独立层进行解析,然后交往下层。
- ③接下来,不同类型的设备对read命令的行为会有所不同,如磁盘接收read命令后的行为与打印机接收read命令后的行为是不同的。因此,需要针对不同的设备,把read命令解析成不同的指令,这就经过了设备驱动层。
- ④命令解析完毕后,需要中断正在运行的进程,转而执行read命令,这就需要中断处理程序。
- ⑤最后,命令真正抵达硬件设备,硬件设备的控制器按照上层传达的命令操控硬件设备,完成相应的功能。
直接涉及到硬件其体细节、且与中断无关的操作肯定是在设备驱动程序层完成的;
没有涉及硬件的、对各种设备都需要进行的管理工作都是在设备独立性软件层完成的。
5.1.4 应用程序I/O接口
在I/O系统与高层之间的接口中,根据设备类型的不同,又进一步分为若干接口。
-
字符设备接口
字符设备是指数据的存取和传输是以字符为单位的设备,如键盘、打印机等。基本特征是传输速率较低、不可寻址,并且在输入输出时通常采用中断驱动方式。
-
字符设备的操作
- get和put操作。由于字符设备不可寻址,只能采取顺序存取方式,通常为字符设备建立一个字符缓冲区,用户程序通过get操作从缓冲区获取字符,通过put操作将字符输出到缓冲区。
- in-control指令。字符设备类型繁多,差异甚大,因此在接口中提供一种通用的in-control指令来处理它们(包含了许多参数,每个参数表示一个与具体设备相关的特定功能)。
字符设备都属于独占设备,为此接口中还需要提供打开和关闭操作,以实现互斥共享。
-
-
块设备接口
块设备是指数据的存取和传输是以数据块为单位的设备,典型的块设备是磁盘。基本特征是传输速率较高、可寻址。磁盘设备的I/O常采用DMA方式。
- 隐藏了磁盘的二维结构:在二维结构中,每个扇区的地址需要用磁道号和扇区号来表示。块设备接口将磁盘的所有扇区从0到n-1依次编号,这样,就将二维结构变为一种线性序列。
- 将抽象命令映射为低层操作:块设备接口支持上层发来的对文件或设备的打开、读、写和关闭等抽象命令,该接口将上述命令映射为设备能识别的较低层的具体操作。
- 内存映射接口:内存映射接口通过内存的字节数组来访问磁盘,而不提供读/写磁盘操作。映射文件到内存的系统调用返回包含文件副本的一个虚拟内存地址。只在需要访问内存映像时,才由虚拟存储器实际调页。内存映射文件的访问如同内存读写一样简单,极大地方便了程序员。
-
网络设备接口
许多操作系统提供的网络I/O接口为网络套接字接口,套接字接口的系统调用使应用程序创建的本地套接字连接到远程应用程序创建的套接字,通过此连接发送和接收数据。
-
阻塞/非阻塞I/O
-
**阻塞I/O:**当用户进程调用I/O操作时,进程就被阻塞,需要等待I/O操作完成,进程才被唤醒继续执行。
eg:字符设备接口一一从键盘读一个字符get
-
非阻塞I/O:用户进程调用I/O操作时,不阻塞该进程,该I/O调用返回一个错误返回值,通常,进程需要通过轮询的方式来查询I/O操作是否完成。
eg:块设备接口一一往磁盘写数据write
-
5.2 设备独立性软件
5.2.1 与设备无关的软件
与设备无关的软件是I/O系统的最高层软件,它的下层是设备驱动程序。
- 设备保护:
- 操作系统需要实现文件保护功能,不同的用户对各个文件有不同的访问权限(如:只读、读和写等)
- 在UNIX系统中,设备被看做是一种特殊的文件,每个设备也会有对应的FCB。当用户请求访问某个设备时,系统根据FCB中记录的信息来判断该用户是否有相应的访问权限,以此实现“设备保护”的功能。
5.2.2 高速缓存与缓冲区
-
磁盘高速缓存(Disk Cache)
操作系统中使用磁盘高速缓存技术来提高磁盘的I/O速度,对访问高速缓存要比访问原始磁盘数据更为高效。
磁盘高速缓存技术不同于通常意义下的介于CPU与内存之间的小容量高速存储器,而是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。因此,磁盘高速缓存逻辑上属于磁盘,物理上则是驻留在内存中的盘块。
- 高速缓存在内存中分为两种形式:
- 一种是在内存中开辟一个单独的空间作为磁盘高速缓存,大小固定
- 另一种是把未利用的内存空间作为一个缓冲池,供请求分页系统和磁盘I/O时共享。
- 高速缓存在内存中分为两种形式:
-
缓冲区(Buffer)
-
概念:缓冲区是一个存储区域,可以由专门的硬件寄存器组成,也可利用内存作为缓冲区。
- 硬件做缓冲区:使用硬件作为缓冲区的成本较高,容量也较小,一般仅用在对速度要求非常高的场合(如存储器管理中所用的联想寄存器,由于对页表的访问频率极高,因此使用速度很快的联想寄存器来存放页表项的副本)
- 内存做缓冲区:一般情况下,更多的是利用内存作为缓冲区,“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区
-
作用
- 缓和CPU与I/O设备之间速度不匹配的矛盾
- 减少对CPU的中断频率,放宽对CPU中断相应时间的限制
- 解决数据粒度不匹配的问题
- 提高CPU与I/O设备之间的并行性
-
单缓冲
若采用单缓冲的策略,操作系统会在主存中为其分配一个缓冲区(若题目中没有特别说明,一个缓冲区的大小就是一个块)。
注意:当缓冲区数据非空时,不能往缓冲区冲入数据,只能从缓冲区把数据传出;当缓冲区为空时,可以往缓冲区冲入数据,但必须把缓冲区充满以后,才能从缓冲区把数据传出。
设块设备输入缓冲区时间为T,缓冲区传送至工作区时间为M,CPU处理工作区时间为C:
- 若T>C,从初始状态到下一个开始状态,整个过程用时为M+T
- 若T<C,从初始状态到下一个开始状态,整个过程用时为M+C
结论:故单缓冲区处理每块数据的用时为 m a x ( C , T ) + M max(C,T)+M max(C,T)+M。
若两个相互通信的机器只设置单缓冲区,在任一时刻只能实现数据的单向传输。
-
双缓冲
若采用双缓冲的策略,操作系统会在主存中为其分配两个缓冲区。
双缓冲题目中,假设初始状态为;工作区空,其中一个缓冲区满,另一个缓冲区空
- 若T>C+M,则处理一块数据的平均用时为T
- 若T<C+M,意味着输入数据块速度要比处理机处理数据块速度更快,处理一个数据块的平均耗时为C+M
结论:采用双缓冲策略,处理一个数据块的平均耗时为 M a x ( T , C + M ) Max(T,C+M) Max(T,C+M)
若两个相互通信的机器只设置单缓冲区,在任一时刻只能实现数据的单向传输。
若两个相互通信的机器设置双缓冲区,则同一时刻可以实现双向的数据传输。
-
循环缓冲
将多个大小相等的缓冲区链接成一个循环队列。
注:上图中,橙色表示已充满数据的缓冲区,绿色表示空缓冲区。
-
缓冲池
缓冲池由系统中共用的缓冲区组成。
这些缓冲区按使用状况可以分为:
- 空缓冲队列
- 装满输入数据的缓冲队列(输入队列)
- 装满输出数据的缓冲队列(输出队列)
根据一个缓冲区在实际运算中扮演的功能不同,又设置了四种工作缓冲区:
- 用于收容输入数据的工作缓冲区(hin)
- 用于提取输入数据的工作缓冲区(sin)
- 用于收容输出教据的工作绥冲区(hout)
- 用于提取输出数据的工作缓冲区(sout)
工作过程:
-
① 输入进程请求输入数据
从空缓冲队列中取出一块作为收容输入数据的工作缓冲区(hin)。冲满数据后将缓冲区挂到输入队列队尾
-
② 计算进程想要取得一块输入数据
从输入队列中取得一块冲满输入数据的缓冲区作为“提取输入数据的工作缓冲区(sin)”。缓冲区读空后挂到空缓冲区队列
-
③ 计算进程想要将准备好的数据冲入缓冲区
从空缓冲队列中取出一块作为“收容输出数据的工作缓冲区(hout)”,数据冲满后将缓冲区挂到输出队列队尾
-
④ 输出进程请求输出数据
从输出队列中取得一块冲满输出数据的缓冲区作为“提取输出数据的工作缓冲区(sout)”。缓冲区读空后挂到空缓冲区队列
-
5.2.3 设备的分配与回收
-
设备分配概述
设备分配是指根据用户的I/O请求分配所需的设备。分配的总原则是充分发挥设备的使用效率,尽可能地让设备忙碌,又要避免由于不合理的分配方法造成进程死锁。
从设备特性来看,分为以下三种设备:
- 独占式使用设备。进程分配到独占设备后,便由其独占,直至该进程释放该设备。
- 分时式共享使用设备。对于共享设备,可同时分配给多个进程,通过分时共享使用。
- 以SPOOLing方式使用外部设备。SPOOLing技术实现了虚拟设备功能,可以将设备同时分配给多个进程。这种技术实质上就是实现了对设备的I/O操作的批处理。
-
设备分配的数据结构
设备分配依据的主要数据结构有设备控制表(DCT)、控制器控制表(COCT)、通道控制表 (CHCT)和系统设备表(SDT),各数据结构功能如下。
-
设备控制表(DCT):系统为每个设备配置一张DCT,用于记录设备情况
-
控制器控制表(COCT):每个设备控制器都会对应一张COCT。操作系统根据COCT的信息对控制器进行操作和管理。
-
通道控制表(CHCT):每个通道都会对应一张CHCT。操作系统根据CHCT的信息对通道进行操作和管理。
-
系统设备表(SDT):记录了系统中全部设备的情况,每个设备对应一个表目。
-
-
设备分配的策略
-
设备分配原则。设备分配应根据设备特性、用户要求和系统配置情况。既要充分发挥设备的使用效率,又要避免造成进程死锁,还要将用户程序和具体设备隔离开。
-
设备分配方式。设备分配方式有静态分配和动态分配两种。
-
①静态分配:进程运行前为其分配全部所需资源,运行结束后归还资源。主要用于对独占设备的分配,它在用户作业开始执行前,由系统一次性分配该作业所要求的全部设备、控制器。
静态分配方式不会出现死锁,但设备的使用效率低。
-
②动态分配:进程运行过程中动态申请设备资源。在进程执行过程中根据执行需要进行。
这种方式有利于提高设备利用率,但若分配算法使用不当,则有可能造成进程死锁。
-
-
设备分配算法。常用的动态设备分配算法有先请求先分配、优先级高者优先等。
-
-
设备分配的安全性
设备分配的安全性是指设备分配中应防止发生进程死锁。
-
安全分配方式。
- 为进程分配一个设备后就将进程阻塞,本次I/O完成后才将进程唤醒。一个时段内每个进程只能使用一个设备。
- 优点:破坏了“请求和保持”条件,不会死锁
- 缺点:对于一个进程来说,CPU和I/O设备只能串行工作
-
不安全分配方式。
进程发出I/O请求后,系统为其分配I/O设备,进程可继续执行,之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞。一个进程可以同时使用多个设备。
- 优点:进程的计算任务和I/O任务可以并行处理,使进程迅速推进
- 缺点:有可能发生死锁(死锁避免、死锁的检测和解除)
-
-
设备分配的步骤
-
步骤
- ① 根据进程请求的物理设备名查找SDT(注:物理设备名是进程请求分配设备时提供的参数)
- ② 根据SDT找到DCT,若设备忙碌则将进程PCB挂到设备等待队列中,不忙碌则将设备分配给进程。
- ③ 根据DCT找到COCT,若控制器忙碌则将进程PCB挂到控制器等待队列中,不忙碌则将控制器分配给进程。
- ④ 根据COCT找到CHCT,若通道忙碌则将进程PCB挂到通道等待队列中,不忙碌则将通道分配给进程。
注:只有设备、控制器、通道三者都分配成功时,这次设备分配才算成功,之后便可启动I/O设备进行数据传送
-
缺点
- ①用户编程时必须使用“物理设备名”,底层细节对用户不透明,不方便编程
- ②若换了一个物理设备,则程序无法运行
- ③若进程请求的物理设备正在忙碌,则即使系统中还有同类型的设备,进程也必须阻塞等待
-
-
设备分配步骤的改进
改进方法:建立逻辑设备名与物理设备名的映射机制,用户编程时只需提供逻辑设备名。
-
逻辑设备表(LUT)
逻辑设备表(LUT)建立了逻辑设备名与物理设备名之间的映射关系。
某用户进程第一次使用设备时使用逻辑设备名向操作系统发出请求,操作系统根据用户进程指定的设备类型(逻辑设备名)查找系统设备表,找到一个空闲设备分配给进程,并在LUT中增加相应表项。
如果之后用户进程再次通过相同的逻辑设备名请求使用设备,则操作系统通过LUT表即可知道用户进程实际要使用的是哪个物理设备了,并且也能知道该设备的驱动程序入口地址。
- 整个系统只有一张LUT:各用户所用的逻辑设备名不允许重复,适用于单用户操作系统
- 每个用户一张LUT:不同用户的逻辑设备名可重复,适用于多用户操作系统
-
步骤
- ① 根据进程请求的逻辑设备名查找SDT(注:用户编程时提供的逻辑设备名其实就是“设备类型”)
- ② 查找SDT,找到用户进程指定类型的、并且空闲的设备,将其分配给该进程。操作系统在逻辑设备表(LUT)中新增一个表项。
- ③ 根据DCT找到COCT,若控制器忙碌则将进程PCB挂到控制器等待队列中,不忙碌则将控制器分配给进程。
- ④ 根据COCT找到CHCT,若通道忙碌则将进程PCB挂到通道等待队列中,不忙碌则将通道分配给进程
-
5.2.4 SPOOLing技术(假脱机技术)
-
概念
-
脱机技术:脱离主机的控制进行的输入/输出操作。
批处理阶段引入了脱机输入/输出技术(用磁带完成),在外围控制机的控制下,慢速输入设备的数据先被输入到更快速的磁带上。之后主机可以从快速的磁带上读入数据,从而缓解了速度矛盾。
-
SPOOLing技术:“假脱机技术”,又称“SPOOLing技术”,用软件的方式模拟脱机技术。
要实现SPOOLing技术,必须要有多道程序技术的支持。系统会建立“输入进程”和“输出进程”
-
-
原理
- 输入井和输出井
- 在磁盘上开辟出两个存储区域一一“输入井”和“输出井”
- ”输入井”模拟脱机输入时的磁带,用于收容I/O设备输入的数据
- “输出井”模拟脱机输出时的磁带,用于收容用户进程输出的数据
- 输入进程和输出进程
- “输入进程”模拟脱机输入时的外围控制机
- “输出进程”模拟脱机输出时的外围控制机
- 输入缓冲区和输出缓冲区
- 在输入进程的控制下,“输入缓冲区”用于暂存从输入设备输入的数据,之后再转存到输入井中
- 在输出进程的控制下,“输出缓冲区”用于暂存从输出井送来的数据,之后再传送到输出设备上
- 注意,输入缓冲区和输出缓冲区是在内存中的缓冲区
- 输入井和输出井
-
预读和滞后写
-
预读(提前读):
如果采用的顺序访问方式对文件进行访问,便可预知下一次要读的盘块。此时可采用预读策略,即在读当前块的同时,也将下一个盘块提前读入内存缓冲区,这样在访问下一个盘块时就不需要再启动磁盘,从而提升磁盘I/O速度。
-
滞后写(延迟写)
滞后写是指缓冲区A中的数据本应立即写回磁盘,但考虑到其中的数据在不久之后有可能再次被访问,因此并不会立即把A中的数据写回磁盘,而是将缓冲区A挂到空闲缓冲区队列。如果有别的进程申请使用该缓冲区时,才把A中的数据写回磁盘。这样做的好处是,只要缓冲区A仍在队列中,任何访问该数据的进程,都可以直接读出其中的数据而不必访问磁盘。因而这种方式也可以减少磁盘I/O次数,改善性能。
-
-
共享打印机的原理分析
SPOOLing技术可以把一台物理设备虚拟成逻辑上的多台设备,可将独占式设备改造成共享设备。
- 当多个用户进程提出输出打印的请求时,系统会答应它们的请求,但是并不是真正把打印机分配给他们,而是由假脱机管理进程为每个进程做两件事:
- 1)在磁盘输出井中为进程申请一个空闲缓冲区(也就是说,这个缓冲区是在磁盘上的),并将要打印的数据送入其中
- 2)为用户进程申请一张空白的打印请求表,并将用户的打印请求填入表中(其实就是用来说明用户的打印数据存放位置等信息的),再将该表挂到假脱机文件队列上。
当打印机空闲时,输出进程会从文件队列的队头取出一张打印请求表,并根据表中的要求将要打印的数据从输出井传送到输出缓冲区,再输出到打印机进行打印。用这种方式可依次处理完全部的打印任务。
虽然系统中只有一个台打印机,但每个进程提出打印请求时,系统都会为在输出井中为其分配一个存储区(相当于分配了一个逻辑设备),使每个用户进程都觉得自己在独占一台打印机,从而实现对打印机的共享。
- 当多个用户进程提出输出打印的请求时,系统会答应它们的请求,但是并不是真正把打印机分配给他们,而是由假脱机管理进程为每个进程做两件事:
5.2.5 设备驱动程序接口
要求每个设备驱动程序与操作系统之间都有着相同或相近的接口。这样会使得添加一个新设备驱动程序变得很容易,同时也便于开发人员编制设备驱动程序。
对于每种设备类型,例如磁盘,操作系统都要定义一组驱动程序必须支持的函数。
与设备无关的软件还要负责将符号化的设备名映射到适当的驱动程序上。
在UNIX和Windows中,设备是作为命名对象出现在文件系统中的,因此针对文件的常规保护规则也适用于I/O设备。系统管理员可以为每个设备设置适当的访问权限。
5.3 磁盘和固态硬盘
5.3.1 磁盘
-
磁盘结构
-
磁盘:磁盘的表面由一些磁性物质组成,可以用这些磁性物质来记录二进制数据
-
磁道:磁盘的盘面被划分成一个个磁道。这样的一个“圈”就是一个磁道
-
扇区:一个磁道又被划分成一个个扇区,每个扇区就是一个“磁盘块”各个扇区存放的数据量相同
最内侧磁道上的扇区面积最小,因此数据密度最大
-
盘面:磁盘有多个盘片"摞"起来,每个盘片有两个盘面。
-
柱面:所有盘面中相对位置相同的磁道组成柱面。
-
-
如何在磁盘中读/写数据
需要把“磁头”移动到想要读/写的扇区所在的磁道。磁盘会转起来,让目标扇区从磁头下面划过,才能完成对扇区的读/写操作。
-
磁盘的物理地址:磁盘地址用“柱面号•盘面号•扇区号”表示,可根据该地址读取一个“块”
-
①根据“柱面号”移动磁臂,让磁头指向指定柱面;
-
②激活指定盘面对应的磁头;
-
③磁盘旋转的过程中,指定的扇区会从磁头下面划过,这样就完成了对指定扇区的读/写。
-
-
磁盘读写时间
- 寻找时间Ts:在读/写数据前,将磁头移动到指定磁道所花的时间。
- ①启动磁头臂是需要时间的。假设耗时为s;
- ②移动磁头也是需要时间的。假设磁头匀速移动,每跨越一个磁道耗时为m,总共需要跨越n条磁道。则:寻道时间 T s = s + m ∗ n Ts=s+ m*n Ts=s+m∗n
- 延迟时间TR:通过旋转磁盘,使磁头定位到目标扇区所需要的时间。
- 设磁盘转速为r(单位:转/秒,或转/分),则平均所需的延迟时间 T R = ( 1 / 2 ) ∗ ( 1 / r ) = 1 / 2 r TR=(1/2)*(1/r)= 1/2r TR=(1/2)∗(1/r)=1/2r
- 硬盘的典型转速为5400 转/分,或7200转/分
- 传输时间Tt:从磁盘读出或向磁盘写入数据所经历的时间
- 假设磁盘转速为r,此次读/写的字节数为b,每个磁道上的字节数为N。
- 则:传输时间 T t = ( 1 / r ) ∗ ( b / N ) = b / ( r N ) Tt=(1/r)*(b/N)= b/(rN) Tt=(1/r)∗(b/N)=b/(rN)
- 平均存取时间
- 总的平均存取时间 T = T s + 1 / 2 r + b / ( r N ) T=Ts + 1/2r + b/(rN) T=Ts+1/2r+b/(rN)
- 延迟时间和传输时间都与磁盘转速相关,且为线性相关而转速是硬件的固有属性,因此操作系统也无法优化延迟时间和传输时间
- 寻找时间Ts:在读/写数据前,将磁头移动到指定磁道所花的时间。
-
磁盘的分类
- 磁头是否移动
- 磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道
- 磁头不可移动的称为固定头磁盘。这种磁盘中每个磁道有一个磁头
- 根据盘片是否可更换
- 固定盘磁盘
- 可换盘磁盘
- 磁头是否移动
5.3.2 磁盘管理
-
磁盘初始化
一个新的磁盘只是一个磁性记录材料的空白盘。在磁盘可以存储数据之前,必须将它分成扇区,以便磁盘控制器能够进行读写操作,这个过程称为低级格式化(或称物理格式化)。
低级格式化为每个扇区使用特殊的数据结构,填充磁盘。每个扇区的数据结构通常由头部、数据区域(通常为512B大小)和尾部组成。头部和尾部包含了一些磁盘控制器的使用信息。
-
分区
在可以使用磁盘存储文件之前,操作系统还要将自己的数据结构记录到磁盘上,分为两步:
- 第一步是,将磁盘分为由一个或多个柱面组成的分区(即我们熟悉的C盘、D盘等形式的分区),每个分区的起始扇区和大小都记录在磁盘主引导记录的分区表中
- 第二步是,对物理分区进行逻辑格式化(创建文件系统),操作系统将初始的文件系统数据结构存储到磁盘上,这些数据结构包括空闲空间和已分配的空间以及一个初始为空的目录。
因扇区的单位太小,为了提高效率,操作系统将多个相邻的扇区组合在一起,形成一簇(在Linux中称为块)。为了更高效地管理磁盘,一簇只能存放一个文件的内容,文件所占用的空间只能是簇的整数倍;如果文件大小小于一簇(甚至是0字节),也要占用一簇的空间。
-
引导块
计算机启动时需要运行一个初始化程序(自举程序),它初始化CPU、寄存器、设备控制器和内存等,接着启动操作系统。为此,自举程序找到磁盘上的操作系统内核,将它加载到内存, 并转到起始地址,从而开始操作系统的运行。
自举程序通常存放在ROM中,为了避免改变自举代码而需要改变ROM硬件的问题,通常只在ROM中保留很小的自举装入程序,而将完整功能的引导程序保存在磁盘的启动块上,启动块位于磁盘的固定位置。具有启动分区的磁盘称为启动磁盘或系统磁盘。
-
Windows允许将磁盘分为多个分区,有一个分区为引导分区,它包含操作系统和设备驱动程序。
-
Windows系统将引导代码存储在磁盘的第0号扇区,它称为主引导记录(MBR)。
-
引导首先运行ROM中的代码,这个代码指示系统从MBR中读取引导代码。
除了包含引导代码,MBR还包含:一个磁盘分区表和一个标志(以指示从哪个分区引导系统)
-
当系统找到引导分区时,读取分区的第一个扇区,称为引导扇区,并继续余下的引导过程,包括加载各种系统服务。
-
-
坏块
由于磁盘有移动部件且容错能力弱,因此容易导致一个或多个扇区损坏。
- 对于简单磁盘,如采用IDE控制器的磁盘,坏块可手动处理,如MS-DOS的Format命令执行逻辑格式化时会扫描磁盘以检查坏块。坏块在FAT表上会标明,因此程序不会使用它们。
- 对于复杂的磁盘,控制器维护磁盘内的坏块列表。这个列表在出厂低级格式化时就已初始化,并在磁盘的使用过程中不断更新。低级格式化将一些块保留作为备用,操作系统看不到这些块。
控制器可以采用备用块来逻辑地替代坏块,这种方案称为扇区备用。
对坏块的处理实质上就是用某种机制使系统不去使用坏块。
-
减少磁盘延迟时间的方法
- 磁盘地址结构的设计:
- 为什么磁盘的物理地址是(柱面号,盘面号,扇区号)而不是(盘面号,柱面号,扇区号)?
- 答:读取地址连续的磁盘块时,采用这样的的地址结构可以减少磁头移动消耗的时间
- 方法
- 交替编号
- 具体做法:让编号相邻的扇区在物理上不相邻
- 原理:磁头读入一个扇区数据后需要一小段时间处理,如果逻辑上相邻的扇区在物理上也相邻,则读入几个连续的逻辑扇区,可能需要很长的“延迟时间”
- 错位命名
- 具体做法:让相邻盘面的扇区编号"错位"
- 原理:与"交替编号"的原理相同。“错位命名法"可降低延迟时间
- 交替编号
- 磁盘地址结构的设计:
5.3.3 磁盘调度算法
-
先来先服务(FCFS)
根据进程请求访问磁盘的先后顺序进行调度。
-
优点:公平;如果请求访问的磁道比较集中的话,算法性能还算过的去
-
缺点:如果有大量进程竞争使用磁盘,请求访问的磁道很分散,则FCFS在性能上很差,寻道时间长。
-
-
最短寻找时间优先(SSTF)
SSTF算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短,但是并不能保证总的寻道时间最短。(其实就是贪心算法的思想,只是选择眼前最优,但是总体未必最优)
-
优点:性能较好,平均寻道时间短
-
缺点:可能产生“饥饿”现象,磁头有可能在一个小区域内来回来去地移动。
Eg:本例中,如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求,处理38号磁道的访问请求时又来了一个18号磁道的访问请求。如果有源源不断的18号、38号磁道的访问请求到来的话,150、160、184号磁道的访问请求就永远得不到满足,从而产生“饥饿”现象。
-
-
扫描算法(SCAN)
又称电梯算法,只有磁头移动到最外侧磁道的时候才能往内移动,移动到最内侧磁道的时候才能往外移动。
-
优点:性能较好,平均寻道时间较短,不会产生饥饿现象
-
缺点:
- ①只有到达最边上的磁道时才能改变磁头移动方向,事实上,处理了184号磁道的访问请求之后就不需要再往右移动磁头了。
- ②SCAN算法对于各个位置磁道的响应频率不平均(如:假设此时磁头正在往右移动,且刚处理过90号磁道,那么下次处理90号磁道的请求就需要等磁头移动很长一段距离;而响应了184号磁道的请求之后,很快又可以再次响应184号磁道的请求了)
-
-
LOOK调度算法
如果在磁头移动方向上已经没有别的请求,就可以立即改变磁头移动方向。(边移动边观察,因此叫 LOOK)
- 优点:比起SCAN算法来,不需要每次都移动到最外侧或最内侧才改变磁头方向,使寻道时间进一步缩短
-
循环扫描算法(C-SCAN)
只有磁头朝某个特定方向移动时才处理磁道访问请求,而返回时直接快速移动至起始端而不处理任何请求。
- 优点:比起SCAN来,对于各个位置磁道的响应频率很平均。
- 缺点:只有到达最边上的磁道时才能改变磁头移动方向,事实上,处理了184号磁道的访问请求之后就不需要再往右移动磁头了;并且,磁头返回时其实只需要返回到18号磁道即可,不需要返回到最边缘的磁道。另外,比起SCAN算法来,平均寻道时间更长。
-
C-LOOK 调度算法
如果磁头移动的方向上已经没有磁道访问请求了,就可以立即让磁头返回,并且磁头只需要返回到有磁道访问请求的位置即可。
- 优点:比起C-SCAN算法,不需要每次都移动到最外侧或最内侧才改变磁头方向,使寻道时间进一步缩短
5.3.4 固态硬盘
-
固态硬盘的特性
-
原理:固态硬盘(SSD)是基于闪存技术Flash Memory,属于电可擦除ROM,即EEPROM
-
组成:
- 闪存翻译层:负责翻译逻辑块号,找到对应页(Page)
- 存储介质:多个闪存芯片(Flash Chip);每个芯片包含多个块(block);每个块包含多个页(page)。
-
读写性能特性:
- 数据是以页为单位读写的。相当于磁盘的“扇区”
- 以块(bock)为单位“擦除“,擦干净的块,其中的每页都可以写一次,读无限次。
- 支持随机访问,系统给定一个逻辑地址,闪存翻译层可通过电路迅速定位到对应的物理地址
- 读快、写慢。要写的页如果有数据,则不能写入,需要将块内其他页全部复制到一个新的(擦除过的)块中,再写入新的页
-
与机械硬盘对比
- SSD读写速度快,随机访问性能高,用电路控制访问位置;机诚硬盘通过移动磁臂旋转磁盘控制访问位置,有寻道时间和旋转延迟
- SSD安静无噪音、耐摔抗震、能耗低、造价更贵
- SSD的一个"块"被擦除次数过多(重复写同一个块)可能会坏掉,而机械硬盘的扇区不会因为写的次数太多而坏掉
-
-
磨碎均衡
思想:将“擦除”平均分布在各个块上,以提升使用寿命
- 动态磨损均衡:写入数据时,优先选择累计擦除次数少的新闪存块。
- 静态磨损均衡:SSD监测并自动进行数据分配、迁移,让老旧的闪存块承担以读为主的储存任务,让较新的闪存块承担更多的写任务
例:某固态硬盘采用磨损均衡技术,大小为240B=1TB,闪存块的擦写寿命只有210=1K次。某男子平均每天会对该固态硬盘写237B=128GB数据。在最理想的情况下,这个固态硬盘可以用多久?
SSD采用磨损均衡技术,最理想情况下,SSD中每个块被擦除的次数都是完全均衡的。
1 T / 128 G = 8 1T/128G=8 1T/128G=8
因此,平均8天,每个闪存块需要擦除一次。每个闪存块可以被擦除1K次,因此经过8K天,约23年,固态使用到寿命。
更多推荐
所有评论(0)