Computer Professional Course保研

操作系统复习

教材使用汤小丹等编著的《计算机操作系统》(第四版)复习,页数有300来页,中间会跳过一些不太重要的章节

第1章回头再更新,操作系统介绍和历史什么的看起来太困了→_→

第2章 进程的描述与控制

为什么要引入进程?

为了提高资源利用率和系统吞吐量,采用多道程序设计技术,将多个程序同时装入内存,使之并发运行,传统意义上的程序不再能独立运行,因此引入进程作为资源分配和独立运行的基本单位

2.1 前趋图和程序执行

1.前趋图描述程序执行先后顺序,是一个DAG,类比数据结构有向无环图、拓扑排序和关键路径

2.一个程序由若干个程序段组成,每个程序段完成特定的功能

3.程序顺序执行的特征:①顺序性:按顺序②封闭性:在封闭环境执行,运行时独占资源不受外界因素影响③可再现性:只要执行环境和初始条件相同可复现

4.顺序执行的效率太低,于是并发执行,由数据结构知识可知,只有不存在前趋关系的程序可以并发执行

5.程序并发执行的特征:①间断性:程序并发执行共享系统资源,形成了相互制约的关系,呈现执行——暂停——执行的规律②失去封闭性:资源的状态由并发执行的程序改变,故失去封闭性③不可再现性:不可能再现并发执行的顺序

2.2 进程的描述

1.由于程序并发执行的间断性、失去封闭性和不可再现性,通常程序是不能参与并发执行的,为了能使程序并发执行并且对并发执行的程序加以描述和控制引入进程的概念

2.进程控制块(PCB)是操作系统为并发执行的程序配置的数据结构,能使参与并发执行的每个程序(含数据)都能独立运行,用来描述进程的基本情况和活动过程,进而控制和管理进程

3.程序段、相关的数据段和PCB构成进程实体(进程映像),一般进程实体简称为进程,创建进程实质是创建进程实体的PCB,撤消进程实质是撤消进程的PCB

4.进程:进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位

5.进程的特征:①动态性:由创建而产生,由调度而执行,由撤消而消亡②并发性③独立性④异步性:进程是按异步方式运行的,按各自独立的、不可预知的速度向前推进,因此程序如果并发执行不可再现,传统OS引入进程和进程同步机制就是为了保证进程并发执行的可再现性

6.进程的三种基本状态:①就绪状态:准备好运行状态,已分配除CPU之外的其他资源,只要分配CPU就可以运行,通常按一定策略将就绪进程排成一个队列,称为就绪队列②执行状态:获得CPU正在执行,同一时刻单处理机系统只有一个进程处于执行状态,多处理机系统有多个进程处于执行状态③阻塞状态:在执行中发生某事件停止执行,阻塞进程也排成一个队列,称为阻塞队列

7.三种基本状态的转换:①就绪态在调度被分配了CPU后便可变为执行态②执行态因时间片用完转为就绪态③执行态因发生某事件导致执行受阻时转为阻塞态

8.创建状态和终止状态:①创建状态:首先由进程申请一个空白PCB,并向PCB中填写用于控制和管理进程的信息;然后为该进程分配运行时所必须的资源;最后把该进程转入就绪状态插入就绪队列中②终止状态:首先等待操作系统进行善后处理;最后将其PCB清空,并将PCB空间返还系统

9.引入创建状态是为了保证进程的调度必须在创建工作完成后进行,以确保对进程控制块操作的完整性。进入终止态的进程以后不再执行,但在操作系统中依然保留一个记录,其中保存状态码和一些计时统计数据,供其他进程收集,一旦其他进程完成了对其信息的提取之后,操作系统将删除该进程,即将PCB清零,并将该空白PCB返还系统

10.为了系统和用户观察和分析进程的需要,引入挂起操作,如果该进程处于执行状态则暂停执行,若处于就绪状态则暂不接受调度,与之对应的是激活操作

11.

12.从创建状态到静止就绪状态:不分配给新建进程所需资源,进程状态转为静止就绪状态,不参与调度,此时进程创建工作尚未完成

13.PCB的作用是使一个在多道程序环境下不能独立运行的程序(含数据)成为一个能独立运行的基本单位,一个能与其他进程并发执行的进程。

14.PCB的具体作用:①作为独立运行基本单位的标志:配置PCB后具有取得OS服务的权利,系统通过PCB感知进程的存在,PCB成为进程存在的唯一标志②能实现间断性运行方式:进程因阻塞暂停运行时可以保留运行时的CPU现场信息在PCB中,等到再次被调度运行时可以恢复其CPU现场信息③提供进程管理所需要的信息④提供进程调度所需要的信息:例如优先级、等待时间等⑤实现与其它进程的同步与通信:例如信号量机制等

15.PCB中的信息:①进程标识符:唯一标识一个进程,通常分为外部标识符和内部标识符,为了方便用户对进程的访问,外部标识符由字母和数字组成,还设置父进程和子进程的标识,还可设置用户标识,为了方便系统对进程的使用,OS为进程设置了内部标识符,赋予每一个进程唯一数字标识符②处理机状态:又称处理机上下文,主要由处理机各种寄存器中内容组成,包括通用寄存器(用户程序访问的,用于暂存信息)、指令计数器(存放要访问的下一条指令的地址)、程序状态字PSW(含有状态信息,如条件码等)、用户栈指针(每个用户进程都有一个系统栈,用于存放过程和系统调用参数及调用地址)③进程调度信息:包括进程的当前状态、进程优先级、进程调度所需其它信息、事件(如阻塞原因)④进程控制信息:包括程序和数据的地址、进程同步和通信机制、资源清单和链接指针

16.PCB的组织方式:

①线性方式:把所有PCB放进一张线性表中,该方式实现简单、开销小,但每次查找都要扫描整张表,适合进程数目不多的系统

②链接方式:具有相同状态进程的PCB分别通过PCB的链接字链接成一个队列,可以形成就绪队列、阻塞队列等

③索引方式:根据进程状态不同,建立几张索引表,然后先从索引表上查找相应PCB的地址,然后指向相应PCB

2.3 进程控制

1.与硬件紧密相关的模块(如中断处理程序等)、各种常用设备的驱动程序以及运行频率较高的模块都安排在紧靠硬件的软件层次中,将它们常驻内存中,通常被称为OS内核

2.为了防止os本身及关键数据(如PCB等)遭受到应用程序有意或无意的破坏,通常也将处理机的执行状态分成系统态和用户态两种,系统态/管态/内核态,能执行一切指令,访问所有寄存器和存储区,传统os都在系统态运行,用户态/目态,具有较低特权的执行状态,仅能执行规定的指令,访问指定的寄存器和存储区

3.大多数os内核都包含两大方面功能:

①支撑功能:三种最基本的支撑功能包括中断处理、时钟管理和原语操作

(1)中断处理:中断处理是内核中最基本的功能,是整个操作系统赖以活动的基础

(2)时钟管理:如时间片轮转调度中,每当时间片用完,由时钟管理发出中断信号

(3)原语操作:由若干条指令组成,用于完成一定功能的一个过程,是原子操作,不可分割的基本单位,原语在执行过程中不允许被中断,在系统态下执行,常驻内存

②资源管理功能:(1)进程管理(2)存储器管理:如地址转换机构、内存分配与回收的功能模块(3)设备管理:各类设备的驱动程序、用于缓和CPU与I/O速度不匹配的缓冲管理等

4.在os中,允许一个进程创建另一个进程,创建者为父进程,被创建者为子进程,但是Windows中不存在任何进程层次结构的概念,所有进程都具有相同的地位,一个进程在创建另一个进程时获得一个句柄,作用相当于一个令牌,可以用来控制被创建的进程,因此进程之间的关系不再是层次关系,而是获得句柄与否、控制与被控制的简单关系

5.形象地描述进程的家族关系引入进程图,进程图就是一棵有向树,进程以及它的子进程构成一棵进程树

6.引起进程创建的事件有四类:用户登录、作业调度、提供服务和应用请求

7.

第3章 处理机调度与死锁

3.1 处理机调度的层次和调度算法的目标

1.处理机调度的层次:①高级调度(长程调度/作业调度):调度对象是作业,主要功能是决定将外存上处于后备队列中的哪几个作业调入内存,为它们创建进程、分配必要的资源并放入就绪队列,主要用于多道批处理系统中,在分时和实时系统中不设置高级调度②低级调度(进程调度/短程调度):调度对象是进程(或内核级进程),主要功能是决定就绪队列中的哪个进程获得处理机,是最基本的一种调度,在多道批处理、实时和分时三种OS中都必须配置③中级调度(内存调度):主要目的是提高内存利用率和系统吞吐量,把那些暂时不能运行的进程调至外存等待,此时进程状态称为就绪驻外存状态(或挂起状态),当它们具备运行条件且内存有空闲时,由中级调度决定把进程再重新载入内存,修改其状态为就绪状态,挂在就绪队列上等待,实际上就是存储器管理中的对换功能

2.进程调度运行频率最高,中级调度和作业调度依据其名称次之

3.处理机调度算法的共同目标:①资源利用率:CPU利用率=CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)②公平性:应使诸进程都获得合理的CPU时间,不会发生进程饥饿现象③平衡性:调度算法应尽可能保持系统资源使用的平衡性,使系统中的CPU和各外部设备经常处于忙碌状态④策略强制执行

4.批处理系统的目标:①平均周转时间短:周转时间包括作业在外存后备队列上等待(作业)调度的时间、进程在就绪队列上等待进程调度的时间、进程在CPU上执行的时间和进程等待I/O操作完成的时间四部分,带权周转时间=作业周转时间T/系统提供服务的时间T_s②系统吞吐量高③处理机利用率高。可以看出这些目标之间是存在矛盾的

5.分时系统的目标:①响应时间快②均衡性:系统响应时间的快慢与用户所请求服务的复杂性相适应

6.实时系统的目标:①截止时间的保证:某任务必须开始执行的最迟时间或必须完成的最迟时间②可预测性

3.2 作业与作业调度

1.作业是一个比程序更广泛的概念,不仅包含了程序和数据,还应配有作业说明书,在批处理系统中是以作业为基本单位从外存调入内存的

2.每个作业都必须经过若干个相对独立,又相互关联的顺序加工步骤才能得到结果,其中每一个加工步骤称为一个作业步,一个典型的作业可分成“编译”作业步、“链接装配”作业步和“运行”作业步

3.为管理和调度作业,在多道批处理系统中为每个作业设置了一个作业控制块JCB,是作业在系统中存在的标志,其中保存了系统对作业进行管理和调度的全部信息

4.每当作业进入系统时便为该作业建立一个作业控制块JCB,再根据作业类型将它放到相应的作业后备队列中等待调度

5.作业运行的三个阶段和状态:①收容阶段:作业通过某种输入方式或SPOOLing系统输入到硬盘,为该作业建立JCB,并把它放入作业后备队列中,此时为后备状态②运行阶段:作业被作业调度选中后,便为它分配必要的资源和建立进程,并将它放入就绪队列,此时为运行状态③完成阶段:作业完成或发生异常提前结束时,系统回收资源,作业为完成状态

6.作业调度的主要任务是根据JCB中的信息,检查系统中的资源能否满足作业对资源的需求,以及按照一定的调度算法,从外存的后备队列中选取某些作业调入内存,并为它们创建进程、分配必要的资源

7.每次作业调度都需做接纳多少作业和接纳哪些作业的决定,第一个决定取决于多道程序度,即允许多少个作业同时再内存中运行,多道程序度的确定是根据计算机的系统规模、运行速度、作业大小以及能否获得较好的系统性能等情况作出适当抉择的,第二个决定取决于作业调度算法

8.先来先服务(FCFS)调度算法:系统按照作业到达的先后次序来进行调度,在单处理机系统中已很少作为主调度算法,经常与其他调度算法结合使用形成更为有效的调度算法

9.短作业优先(SJF)调度算法:以作业的长短来计算优先级,可以分别用于作业调度和进程调度,缺点是必须预知作业运行的时间、对长作业非常不利、人机无法实现交互和不能保证紧迫性作业得到及时处理

10.优先级(PSA)调度算法:基于作业的紧迫程度由外部赋予作业相应的优先级来调度

11.高响应比优先(HRRN)调度算法:每个作业引入动态优先级,优先级R_p=(等待时间+要求服务时间)/要求服务时间,结合FCFS和SJF的优势,利用该算法每次要进行调度之前都需要先做响应比的计算,增加了系统开销

3.3 进程调度

1.进程调度的任务:①保存处理机的现场信息②按某种算法选取进程③把处理器分配给进程

2.进程调度机制:①排队器:排队器将系统中的所有就绪进程按照一定的策略排成一个或多个队列②分派器:依据进程调度程序所选定的进程,将其从就绪队列中取出,然后进程从分派器到新选出进程间的上下文切换,将处理机分配给新选出的进程③上下文切换器:切换时发生两对上下文切换操作:(1)OS保存当前进程上下文,即把当前进程的处理机寄存器内容保存到该进程的进程控制块内相应单元,再装入分派程序上下文,以便分派程序进行(2)移出分派程序上下文,把新选进程的CPU现场信息装入处理机的各个相应寄存器中,方便新选进程运行

3.进程调度方式:①非抢占方式:非抢占方式可能引起进程调度的因素可以为正在执行的进程运行完毕或因发生某种事件无法继续运行、正在执行的进程因提出I/O请求暂停执行、进程通信或同步时执行了如Block等原语操作,非抢占方式的优点是实现简单,系统开销小,适用于大多数批处理系统,但不能用于分时系统和大多数实时系统②抢占方式:现代OS大多采用抢占方式,在分时系统中只有采用抢占方式才能实现人机交互,抢占遵循的原则主要有优先权原则、短进程优先原则和时间片原则

4.轮转(RR)调度算法:让就绪队列中的每个进程仅运行一个时间片,进程切换的时机有(1)若时间片尚未用完进程便已完成,立即激活调度程序,将它从就绪队列中删除再调度就绪队列中的队首进程运行,启动一个新的时间片(2)在一个时间片用完时,如果进程尚未运行完毕,调度程序将它送往就绪队列末尾

5.优先级调度算法分为抢占式和非抢占式两种,抢占式的每当系统中出现一个新的就绪进程时将其优先级与正在运行的优先级进行比较,若优先级更大则进程切换,常用于实时性要求较高的系统中

6.静态优先级是在创建进程时确定的,确定进程的优先级通常依据进程类型、进程对资源的要求和用户要求决定,静态优先级法简单易行,系统开销小,但不够精确,可能会出现优先级低的进程长期没有被调度的情况

7.动态优先级在创建之初先赋予一个优先级,随进程的推进或等待时间的增加而改变,以便获得更好的调度性能

8.多队列调度算法将系统中的就绪队列从一个拆分为若干个,将不同类型或性质的进程固定分配在不同的就绪队列,可以对每个处理机的调度可以实施不同的调度策略

9.多级反馈队列(MFQ)调度算法设置多个就绪队列,队列的优先级逐个降低,不同就绪队列中的进程执行时间片的大小也各不相同,优先级高的队列中时间片越小,每个队列采用FCFS算法,在该队列的进程时间片结束尚未完成时插入下一队列的末尾,在第n个队列中采用RR方式运行,按队列优先级调度,仅当第1~(i-1)所有队列均空时,才会调度第i个队列中的进程运行

10.保证调度算法向用户作出明确的性能保证,可以做到调度的公平性,如果系统内有n个相同类型的进程同时运行,保证每个进程获得相同的处理机时间1/n

11.公平分享调度算法:该调度算法中调度的公平性主要是针对用户而言,使所有用户能获得相同的处理机时间或所要求的时间比例

3.4 实时调度

3.5 死锁概述

1.可重用性资源是一种可供用户重复使用多次的资源,每一个可重用性资源中的单元只能分配给一个进程使用,不允许多个进程共享,进程在使用可重用性资源时必须按照请求资源、使用资源和释放资源的顺序,每一类可重用性资源中的单元数目是相对固定的,进程在运行期间既不能创建也不能删除它

2.可消耗性资源又称为临时资源,是在进程运行期间由进程动态地创建和消耗的,可消耗性资源的单元数目在进程运行期间是可以不断变化的,进程在运行过程中可以请求若干个可消耗性资源用于进程自己消耗不再返回资源类中,通常是由生产者进程创建,由消费者进程消耗

3.可抢占性资源:进程在获得这类资源后可以被其他进程或系统抢占,CPU和主存均属于可抢占性资源,这类资源是不会引起死锁的

4.不可抢占性资源:一旦系统将这类资源分配给进程后,不能强行收回,只能进程用完后释放,磁带机、打印机都属于不可抢占性资源

5.多个进程在对不可抢占性资源和可消耗资源进行争夺时或进程推进顺序不当时可能引起死锁

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

7.产生死锁的必要条件:①互斥条件:一段时间内,某资源只能被一个进程占用②请求和保持条件:进程在保持至少一个资源又提出新的资源请求,而该资源已被其他进程占有③不可抢占条件:获得的资源不可抢占④循环等待条件:发生死锁时必然存在一个进程——资源的循环链

8.处理死锁的方法:①预防死锁:设置某些限制条件破坏产生死锁的四个必要条件②避免死锁:资源的动态分配时用某种方法防止系统进入不安全状态,从而可以避免死锁③检测死锁:允许发生死锁,通过检测机构检测死锁的发生并采取解决措施④解除死锁:当发生死锁时采取相应措施,常用方法是撤消一些进程,回收它们的资源,将它们分配给已处于阻塞状态的进程使其能继续运行

3.6 预防死锁

1.预防死锁的方法是破坏产生死锁的四个必要条件中的一个或几个,由于互斥条件是非共享设备所必须的,因此主要是破坏产生死锁的后三个条件

2.破坏请求和保持条件,系统必须保证做到当一个进程在请求资源时它不能持有不可抢占资源,可通过两个不同的协议实现:①所有进程在开始运行之前,必须一次性地申请其在整个运行过程中所需的全部资源,优点是简单、易行且安全,缺点是资源被严重浪费,使进程经常发生饥饿现象②允许一个进程只获得运行初期所需资源便开始运行,运行过程中逐步释放已分配给自己的且已用毕的资源,然后再请求新的所需资源

3.破坏不可抢占条件,规定当一个已经保持了某些不可被抢占资源的进程,提出新的资源请求而不能得到满足时,它必须释放已经保持的所有资源,待以后需要时再重新申请,实现起来比较复杂,延长进程的周转时间,增加系统开销,降低系统吞吐量

4.破坏循环等待条件,对系统所有资源类型进行线性排序并赋予不同的序号,规定每个进程必须按序号递增的顺序请求资源,这种策略资源利用率和系统吞吐量都有明显改善,但也存在限制新设备的增加等问题

3.7 避免死锁

1.避免死锁是在资源动态分配过程中防止系统进入不安全状态以避免发生死锁

2.允许进程动态地申请资源,但系统在分配资源之前会先计算此次资源分配的安全性

3.银行家算法,原理较简单这里不详细说了,前提是每一个新进程在进入系统时必须申明在运行过程中可能需要每种资源类型的最大单元数目,其数目吗不应超过系统所拥有的资源总量

4.可利用资源向量Available 最大需求矩阵Max 分配矩阵Allocation 需求矩阵Need Need=Max-Allocation

5.安全性算法用来检查此次资源分配后系统是否处于安全状态,设置工作向量Work和Finish,分别表示系统提供给进程继续运行所需的各类资源数目和系统是否又足够的资源分配给进程使之完成

3.8 死锁的检测与解除

1.为了检测死锁的发生,系统中必须保存有关资源的请求和分配信息并且提供一种算法来利用这些信息来检测是否发生死锁

2.系统死锁可用资源分配图来描述,是一个进程和资源的有向图,进程申请资源则进程向资源连一条有向边,资源分配给进程则资源向进程连一条有向边

3.可以利用资源分配图加以简化的方法来检测系统处于S状态时是否为死锁状态,简化方法为一直找既不阻塞也不独立的进程结点消去与之相连的请求边和分配边,如果能消去图中所有的边则该图是可简化的,否则是不可完全简化的

4.文献证明所有的简化顺序都将得到相同的不可简化图,因此当且仅当S状态的资源分配图是不可完全简化时S状态为死锁状态

5.常用的解除死锁的两个方法:①抢占资源:从一个或多个进程中抢占足够数量的资源,分配给死锁进程解除死锁状态②终止(或撤消)进程:终止(或撤消)系统中的一个或多个死锁进程,直至打破循环环路

6.终止进程的方法:①终止所有死锁进程:代价可能很大②逐个终止进程:按照某种顺序,逐个终止进程,直至有足够的资源打破循环等待

7.付出代价最小的死锁解除算法类似动态规划思想,将所有状态都尝试一遍从中取代价最小的方法,但是计算这些状态可能付出的代价非常巨大,实际应用不太现实

8.一个比较有效的死锁解除算法类似贪心思想,从每个子状态中选取代价的最小的一直终止,直到解除死锁状态

第4章 存储器管理

4.1 存储器的层次结构

1.计算机存储层次至少应有三级,最高层为CPU寄存器,中间为主存,最底层为辅存,还可以根据具体的功能细分为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘和可移动存储介质6层,层次越高,存储介质的访问速度越快,存储容量越小

2.寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴,掉电后它们中存储的信息不再存在,低层的固定磁盘和可移动存储介质属于设备管理的管辖范畴,存储的信息将被长期保存

3.寄存器和主存储器被称为可执行存储器,进程可在很少的时钟周期对可执行存储器进行访问,对辅存的访问需要通过I/O设备实现

4.主存储器简称内存或主存,用于保存进程运行的程序和数据,由于主存储器访问速度远低于CPU执行指令的速度,为缓和这一矛盾引入寄存器和高速缓存

5.高速缓存是介于寄存器和存储器之间的存储器,主要用于备份主存中常用的数据,容量远大于寄存器,访问速度快于主存

6.为缓和磁盘的I/O速度远低于主存的访问速度这一矛盾设置磁盘缓存,磁盘缓存本身并不是一种实际存在的存储器,而是利用主存中的部分存储空间暂时存放从磁盘中读出(或写入)的信息

4.2 程序的装入和链接

1.用户程序要在系统中运行要先装入内存,通常要经过编译、链接和装入三个步骤,编译程序对用户源程序进行编译形成若干个目标模块,由链接程序将目标模块和库函数链接形成装入模块,由装入程序将装入模块装入内存

2.绝对装入方式:仅运行单道程序时,完全有可能知道程序将驻留在内存什么位置,程序中的逻辑地址与实际内存地址完全相同

3.可重定位装入方式:多道程序下程序不可能预知目标模块应放在内存何处,使用可重定位装入程序将装入模块装入内存后,模块中的所有逻辑地址与实际装入内存的物理地址不同,通常把装入时对目标程序中指令和数据地址的修改过程称为重定位,地址变换通常是在进程装入时一次完成的,称为静态重定位

4.动态运行时的装入方式:静态重定位不允许程序运行时在内存中移动位置,动态运行的装入程序把装入模块装入内存后并不立即把装入模块中的逻辑地址转换为物理地址,而是把地址转换推迟到程序真正要执行时才进行,为使地址转换不影响指令的执行速度,这种方式需要一个重定位寄存器的支持

5.静态链接方式:将各目标模块及所需库函数链接成一个完整的装配模块,不再拆开,需对各目标模块的相对地址进行修改以及变换外部调用符号

6.装入时动态链接:边装入边链接,若发生一个外部模块调用事件,将引起装入程序去找出相应外部目标模块并将它装入内存,还要按照静态链接方式修改相对地址,优点有便于修改和更新和便于实现对目标模块的共享

7.运行时动态链接:对某些模块的链接推迟到程序执行时才执行,发现一个被调用模块尚未装入内存时立即由OS去找到该模块并将之装入内存,链接到调用者模块上,不仅能加快程序的装入过程,而且可节省大量内存空间

4.3 连续分配存储管理方式

1.连续分配是为一个用户程序分配一个连续的内存空间,即程序中代码或数据的逻辑地址相邻,体现在内存空间分配时物理地址的相邻

2.单一连续分配:单道程序环境下,内存分为用户区和系统区两部分,系统区仅提供给OS使用,通常放在内存的低址部分,用户区内存仅装有一道用户程序,即整个内存的用户空间仅由该程序独占

3.固定分区分配:为能在内存中装入多道程序,将整个用户空间划分为若干个固定大小的区域,每个分区中装入一道作业,可以划分大小相等或不等的分区,分区大小相等的缺点是缺乏灵活性,造成内存空间浪费,分区大小不等增加存储器分配的灵活性,内存分配时分区按大小进行排队建立分区使用表,各表项包括每个分区的起始地址、大小及状态,由于分区大小固定必然会造成存储空间的浪费

4.动态分区分配:又称可变分区分配,根据进程实际需要动态地分配内存空间,涉及分区分配所用数据结构、分区分配算法和分区的分配与回收操作三方面问题

(1)分区分配所用数据结构:①空闲分区表,用于记录每个分区的情况,每个空闲分区占一个表目,表目中包括分区号、分区大小和分区始址等数据项②空闲分区链:实际上是一个双向链表,里面记录的内容与空闲分区表没有区别

(2)分区分配算法:下一条介绍

(3)分区分配操作:主要是分配内存和回收内存,分配操作是从空闲分区表(链)中找到所需大小的分区,分区大小与请求的分区大小的差大于规定大小,则切割该分区将剩余部分插入空闲分区表(链)中,否则不切割,回收操作是判断回收分区与上下分区是否空闲,若有相邻的空闲分区则合并空闲分区

5.基于顺序搜索的动态分区分配算法:

①首次适应(FF)算法:顺序查找空闲分区链,若某个空闲分区大于请求大小则分配,倾向于优先利用内存中低址部分的空闲分区,保留了高址部分大空闲区,缺点是低址部分不断被划分,会留下很多碎片,每次查找都从低址部分开始,增加查找时的开销

②循环首次适应(NF)算法:与首次适应不同的是不再是每次从链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,能使空闲分区分布得更均匀,减少了查找时的开销,但会缺乏大的空闲分区

③最佳适应(BF)算法:每次分配内存总是把满足要求又最小的空闲分区分配给作业,为加速寻找需将所有空闲分区按升序排序,会留下很多碎片

④最坏适应(WF)算法:与最佳适应相反,每次挑选最大的,优点是剩下的空闲区不至于太小,产生碎片的可能性最小,将所有空闲分区按降序排列,查找时只需要看第一个分区能否满足作业要求即可,查找效率高

6.基于索引搜索的动态分区分配算法:

①快速适应(quick fit)算法:又称分类搜索法,根据容量大小进行分类,对相同容量的所有空闲分区单独设立一个空闲分区链表,同时在内存中设立一个管理索引表,每一个索引表项对应一种空闲分区类型并记录该类型空闲分区链表表头指针,不会对任何分区产生分割,能保留大的分区,满足对大空间的需求,不会产生碎片,优点是查找效率高,缺点是为有效合并分区,分区归还主存时算法复杂系统开销大,或多或少空间存在一定浪费,典型的以空间换时间的做法

②伙伴系统(buddy system):算法规定分区都为大小为2的k次幂,通常2^m是整个可分配内存的大小,系统运行过程中由于不断划分会形成若干个不连续的空闲分区,将这些空闲分区按分区的大小进行分类,对于具有相同大小的所有分区,单独设立一个空闲分区双向链表,这样不同大小的空闲分区形成了k个空闲分区链表,每次分配时划分,每次回收时若有相同大小的空闲分区则合并,回收空闲分区时时间性能比快速适应算法差,比顺序搜索算法好,空间性能对空闲分区进行了合并,减少了小的空间分区,提高了可空闲分区的可使用率,优于快速适应算法,比顺序搜索算法略差

③哈希算法:建立哈希函数,构造一张以空闲分区大小为关键字的哈希表,每次查找更快

7.紧凑:移动内存中的作业,把内存空间的许多碎片进行合并形成一个大的内存空间

8.动态重定位分区分配:与动态分区分配的区别在于增加了紧凑操作,增设重定位寄存器,用来存放程序在内存中的起始地址,这样不需对程序做任何修改,只要用该程序在内存的新起始地址置换原来的起始地址

4.4 对换

1.多道程序环境下,内存中的某些进程由于某事件尚未发生被阻塞运行,却占用了大量的内存空间,另一方面又有许多作业,因内存空间不足驻留在外存不能进入内存运行,为解决这一问题增设了对换设施,对换是改善内存利用率的有效措施,可以直接提高处理机利用率和吞吐量

2.实现对换功能的方法通常是在系统中设置一个对换进程,由它将内存中暂时不能运行的进程调出到磁盘的对换区,同样也将磁盘上已具备运行条件的进程调入内存

3.对换分为整体对换和页面(分段)对换两种,整体对换目的是用来解决内存紧张问题,进一步提高内存的利用率和系统吞吐量,中级调度中对换是以整个进程为单位的,也称为进程对换,页面(分段)对换是以进程的一个页面或分段为单位进行的,目的是为了支持虚拟存储系统

4.为了实现进程对换,系统必须实现对对换的管理、进程的换出和进程的换入

5.磁盘空间分为文件区和对换区两部分,对文件区管理的主要目标是提高文件存储空间的利用率,然后才是提高对文件的访问速度,对文件区空间的管理采取离散分配方式,对对换空间管理的主要目标是提高进程换入和换出的速度,然后才是提高文件存储空间的利用率,对对换空间的管理采取连续分配方式

6.进程的换出:检查所有驻留内存的进程,首先选择处于阻塞或睡眠状态的进程,当有多个这样的进程时应当选择优先级最低的进程作为换出进程,还需考虑进程在内存的驻留时间,在换出的过程中只能换出非共享的程序和数据段,进行换出时先申请对换空间,若申请成功启动磁盘将该进程的程序和数据传送到磁盘的对换区上,若此时内存还有可换出的进程,则继续执行换出过程,直到内存中再无阻塞进程为止

7.进程的换入:查看PCB集合中所有进程状态,从中找出就绪状态但已换出的进程,然后申请内存,若申请成功可直接将进程从外存调入内存

8.由于对换需要较多的时间,一般在处理机正常运行时不启动对换程序,如果发现有许多进程在运行时经常发生缺页且显现出内存紧张的情况才启动对换程序,将一部分进程调至外存

4.5 分页存储管理方式

1.如果允许将一个进程直接分散地装入到许多不相邻的分区中便可充分利用内存空间,无须紧凑,这就是离散分配方式,离散分配方式主要有分页存储管理、分段存储管理和段页式存储管理

2.分页存储管理将进程的逻辑地址空间分成若干个页,并为各页加以编号,由于进程的最后一页经常装不满一块,形成了不可利用的碎片,称之为“页内碎片”

3.页面大小应适中,过小可以起到减少内存碎片的作用,利于内存利用率的提高,但会造成每个进程占用较多的页面,从而导致进程页表过长占用大量内存,过大可以减小页表长度,提高页面换入换出的速度,但又不会使页内碎片增大

4.分页地址的地址结构包含两部分:前一部分为页号P,后一部分为偏移量W,即页内地址,页内地址的位数表示了页的大小,页号的位数表示了有多少个页

5.

发表评论

邮箱地址不会被公开。 必填项已用*标注