admin 管理员组

文章数量: 887021

文章目录

  • 一、 银行家算法
    • 1.1 用途
    • 1.2 数据结构
    • 1.3 算法描述
    • 1.4 例题说明
  • 二、 连续分配管理方式
    • 2.1 分类
      • 单一连续分配
      • 固定分区分配
      • 动态分区分配
    • 2.2 ☆动态分区分配算法
      • 首次适应算法FF
      • 下次适应算法NF
      • 最佳适应算法BF
      • 最差适应算法WF
      • 例题说明
  • 三、 页面置换算法
    • 3.1 最佳置换算法OPT
    • 3.2 先进先出算法FIFO
    • 3.3 最近最少使用算法LRU
    • 3.4 例题说明

一、 银行家算法

1.1 用途

银行家算法用于避免死锁，是最著名的死锁避免算法

竞争资源和进程推进顺序不恰当会导致死锁

所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，都将无法再向前推进

  • 产生死锁的必要条件：
    ①互斥：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用
    ②请求和保持：当进程因请求资源而阻塞时，对已获得的资源保持不放
    ③不剥夺：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放
    ④环路等待：在发生死锁时，必然存在一个进程–资源的环形链

1.2 数据结构

  • (1) 可利用资源向量 Available
    这是一个含有 m 个元素的数组，其中每一个元素（Available[i]）代表第i类可利用的资源数目，其初始值是系统中所配置的该类资源的数目，其数值随该类资源的分配和回收而动态改变
    【Available[j] 表示系统中有的j类资源数量】
  • (2) 最大需求矩阵Max
    这是一个n x m的矩阵，定义了系统中每个进程对m类资源的总需求
    【Max[i][j] 表示第i个进程对j类资源的总需求数】
  • (3) 分配矩阵 Allocation
    这也是一个n x m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数
    【 Allocation[i][j]表示进程i当前己获得的第j类的资源数目
  • (4) 需求矩阵Need
    这也是一个n×m的矩阵，用以表示每一个进程还需要的各类资源数
    【Need[i][j]表示进程i还需要第j类的资源数量】

上述n x m矩阵间存在下述关系:
　　　　　　　　　Need[i][j] = Max[i][j] - allocation[i][j]

1.3 算法描述

资源分配算法

安全性算法（即上图资源分配算法中的安全检查部分）

1.4 例题说明


① T0时刻是否安全？

②T0时刻以后，若进程P2发出资源请求Request2(1,0,1)，系统能否将资源分配给它？

③在进程P2申请资源后，若P1发出资源请求Request1(1,0,1)，系统能否将资源分配给它？
④在进程P1申请资源后，若P3发出资源请求Request3(0,0,1)，系统能否将资源分配给它？

二、 连续分配管理方式

连续分配方式，即为一个用户程序分配一个连续的内存空间

2.1 分类

单一连续分配

最简单的一种存储管理方式，只能用于单用户、单任务的操作系统中

将内存分为系统区（内存低端，分配给OS用）和用户区（内存高端，分配给用户用）

采用静态分配方式，即作业一旦进入内存，就要等待它运行结束后才能释放内存

单一连续分配会产生内部碎片

–

固定分区分配

最早使用的一种可运行多道程序的存储管理方法

将内存空间划分为若干个固定大小的分区，除OS占一区外，其余的一个分区装入一道程序，分区的大小可以不相等，但事先必须确定，在运行时不能改变，即分区大小及边界在运行时不能改变

固定分区分配中，程序通常采用静态重定位方式装入内存，当某个用户程序要装入内存时，由内存分配程序检索分区说明表，从表中找出一个满足要求且尚未非配的分区分配给该程序

不能实现多进程共享一个主存区，利用率较低，会产生内部碎片

–

动态分区分配

又称为可变式分区分配，是一种动态划分存储器的分区方法

不事先将内存划分成一块块的分区，而是在作业进入内存时，根据作业的大小动态地建立分区，并使分区的大小正好适应作业的需要，因此系统中分区的大小是可变的，分区的数目也是可变的

  • 分区分配中的数据结构：
    ① 空闲分区表
    ② 空闲分区链

动态分区分配算法见2.2

2.2 ☆动态分区分配算法

首次适应算法FF

FF：First Fit

空闲分区（链）按地址递增的次序排列
在进行内存分配时，从空闲分区表/链首开始顺序查找，直到找到第一个满足要求的空闲分区为止。然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表/链中

优先利用低地址空间，但是低地址空间被多次划分后会产生外部碎片

–

下次适应算法NF

NF：Next Fit

又称为循环首次适应算法，即在首次适应算法的基础上把队列改为循环队列（依然是空闲分区（链）按地址递增的次序排列），每次从上次找到的空闲分区的下一个分区进行查找

分布均匀，但是缺乏大的空闲分区

–

最佳适应算法BF

BF：Best Fit

空闲分区表/链按容量大小递增的次序排列，在进行内存分配时，从空闲分区表/链的首开始顺序查找，直到找到第一个满足其大小要求的空闲分区

外部碎片很小，总能分配给作业最恰当的分区并保留大的分区，但是产生很多难以利用的碎片空间

–

最差适应算法WF

WF：Worst Fit

空闲分区表/链按容量大小递减的次序排列，在进行内存分配时，从空闲分区表/链的首开始顺序查找，直到找到第一个比其大的空闲分区，剩下的空闲仍留在空闲分区表/链中

分配完剩下的空间比较大，适合下次用，但是大空间会被用完

–

例题说明

三、 页面置换算法

3.1 最佳置换算法OPT

在预知一个进程的页面号引用串的情况下，每次都淘汰以后不再使用或者以后最迟再被使用的页面

最佳置换算法最优，具有最低缺页率，但是由于实际操作中往往无法事先知道以后会引用到的所有页面信息，因此无法实现，只能作为一个标准衡量其它置换算法的优劣

–

3.2 先进先出算法FIFO

最简单的页面置换算法，每次总是淘汰最先进入内存的页面

–

3.3 最近最少使用算法LRU

选择最近最长时间没有被使用的页面予以淘汰

该算法可以用寄存器组合栈来实现，性能较好，常用的页面置换算法中，此算法最接近最佳置换算法

–

3.4 例题说明

本文标签： 死锁 算法 分配 银行家 题型

版权声明：本文标题：操作系统经典题型：死锁避免之银行家算法、连续分配管理方式之动态分区分配、页面置换算法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1727375562h1110719.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。