分配_分配单元大小 - CSDN
精华内容
参与话题
  • 转:-连续分配、链式分配、索引分配 外存,指的是除了cpu缓存和内存以外的存储器,硬盘、光盘、U盘都可以被称为外存。所有的数据,也都存在这里面,故他的分配方式变得极其重要,这直接影响到了计算机的运行速度。 ...

    转:-连续分配、链式分配、索引分配

    外存,指的是除了cpu缓存和内存以外的存储器,硬盘、光盘、U盘都可以被称为外存。所有的数据,也都存在这里面,故他的分配方式变得极其重要,这直接影响到了计算机的运行速度。

    外存分配方式主要有这几种:连续分配,链式分配,索引分配。

     

    一.  连续分配

    原理:创建文件时,分配一组连续的块;FAT(文档分配表)中每个文件只要一项,说明起始块和文件长度。对于顺序文件有利。

    优点:1.简便。适用于一次性写入操作。2.支持顺序存取和随机存取,顺序存取速度快。3.所需的磁盘寻道次数和寻道时间最少。(因为空间的连续性,当访问下一个磁盘块时,一般无需移动磁头,当需要移动磁头时,只需要移动一个磁道。)

    缺点:1.文件不能动态增长。(可能文件末尾处的空块已经分配给了别的文件。)2.不利于文件的插入和删除。3.外部碎片问题。(反复增删文件后,很难找到空间大小足够的连续块,需要进行紧缩。)4.在创建文件时需生命文件大小。

    如图:

     

    二.  链式分配

    原理:一个文件的信息存放在若干个不连续的物理块中,各块之间通过指针连接,前一个物理块指向下一个物理块。fat中每个文件同样只需要一项,包括文件名、起始块号和最后块号。任何一个自由块都可以加入到链中。

    优点:1.提高磁盘的空间利用率,不存在外部碎片问题。2.有利于文件的插入和删除。3.有利于文件的动态扩充。

    缺点:1.存取速度慢,一般只适用于信息的顺序存取,不适于随机存取。2.查找某一块必须从头到尾沿着指针进行。3.可靠性问题,如指针出错。4.更多的寻道次数和寻道时间。5.链接指针占一定的空间,将多个块组成簇,按簇进行分配而不是按块进行分配。(增加了磁盘碎片)

    如图:

    使用FAT文件分配表法,链接分配的变种,如MS-DOS 和 OS/2.

     

    三.  索引分配

    原理:每个文件在FAT中有一个一级索引,索引包含分配给文件的每个分区的入口。文件的索引保存在单独的一个块中,FAT中该文件的入口指向这一块。

    优点:1.保持了链接结构的优点,又解决了其缺点:按快分配可以消除外部碎片。按大小可改变的分区分配可以提高局部性。索引分配支持顺序访问文件和直接访问文件,是普遍采用的一种方式。2.满足了文件动态增长,插入删除的要求。(只要有空闲块)3.能充分利用外存空间。

    缺点:1.较多的寻道次数和寻道空间。2.索引表本身带来了系统开销,如:内外存空间、存取时间。

    如图:

     

    四.  连续分配和索引分配相结合

    原理:对于小文件(3、4块),采用连续分配;当文件大时,自动切换到索引分配。

    文件的直接访问:使用连续分配方式。

    文件的顺序访问:采用链接分配。

    对于这些系统,所使用的访问类型,必须在文件创建时加以说明。

     

    五.  多重索引

    原理:首先,多重索引也是索引分配的一种,只不过它是将一个大文件的所有索引表(二级索引)的地址放在另一个索引表(一级索引)中。ps:跟数据库第四范式非常像。

    大文件:设一个盘块大小为1kb,长度100kb的文件就需要100个盘块,索引表至少需要100项;若文件大小为1000kb,则索引表项就要有1000项。设盘块号用4个字节表示,则该索引表至少占用4000bye(约4k)。

    当文件很大时,存在的问题:1.需要很多磁盘块。2.索引表很大。3.不能将整个索引表放在内存。

    解决途径:采用多重索引表结构。

    如图:

    多重索引表结构图示:

     

    暂时就简单介绍到这里,后续会为大家添加也一些样例,如有不对地方请指正,谢谢!

    展开全文
  • 三种文件分配方式的区别

    千次阅读 2015-12-30 18:14:31
    文件分配方式分为三种:连续分配、链接分配、索引分配。其中链接分配又分为隐式链接分配和显式链接分配;索引分配又分为单级索引分配、两级(多级)索引分配,混合索引分配。 这里要说的是显式链接分配和索引...
    文件分配方式分为三种:连续分配、链接分配、索引分配。其中链接分配又分为隐式链接分配和显式链接分配;索引分配又分为单级索引分配、两级(多级)索引分配,混合索引分配。


    这里要说的是显式链接分配和索引分配(指单级)的区别。
    链接分配的特点是已知一个物理块位置寻找下一个物理块位置必须通过指针进行,而且必须顺序寻找。比如我们当前位于3号物理块要去4号物理块,必须根据3号物理块中4号物理块的指针(地址)寻找,而且我们下一个访问必须是4号,而不能是5号(即使4号我们不需要)。这是链接分配的基本思想,优缺点对比连续分配很明显,自己找就可以了,这里不赘述。但是这种朴素的链接分配思想有一个致命的问题,就是一旦出现断链,后续物理块无法访问,并且我们需要的物理块不在链的前方时,顺序寻找花费大量读磁盘时间(读磁盘时间远远大于读内存时间)。所以需要对这种朴素的链接分配思想进行改造。


    于是出现了显式链接分配(朴素的链接分配也是隐式链接分配),即把所有的物理块中的指针收集在一起统一放在内存的一张链接表FAT中(请注意是内存),这样就大大减轻了朴素链接分配思想上述致命缺点,由于地址存放在一起,所以不太容易出现丢失个别地址现象,而且内存访问速度快。但是这本质上仍然是链接分配,即进程给出文件物理块起始地址等信息,然后根据内存FAT中地址的链接情况进行查找,得到所需物理块。在查找过程中仍然是一个一个的顺序查找。


    下面叙述索引分配的特点。显式链接分配虽然解决了隐式链接分配的致命缺点,但仍有一些问题,主要是非直接访问时间长(相对于CPU来说内存访问还是慢),所以出现了索引分配。索引分配和显式链接分配唯一类似之处在于它有索引表(相对于FAT),但是索引表中数据并不是链接存放,而是顺序存放,也就是说在索引表中可以进行直接访问。而在物理块中,则是任意存放,条件是必须存索引于索引表。索引表一般存放于磁盘(与FAT不同)但在使用时可以先调入内存,进程需要查找文件时,提供的不是文件物理块地址,而是索引表中的索引地址,这个与显式链接分配也不同。


    总的来说,显式链接分配是将地址链接集中在内存中的FAT表中,FAT表中是链接寻找;索引分配是将地址位置存放在索引表中,索引表中是直接寻找,简单的说索引分配是连续分配和链接分配的综合。
    展开全文
  • LTE资源分配图解

    千次阅读 2018-10-05 09:56:53
      ...PCFICH占用第一个符号的4个REG,频带上均匀分布 ...PHICH至少占用3个REG,可以是分布在第1~3个符号,频带上均匀分布 ...PDCCH占用第1~3个符号的扣除PCFICH、PHICH、RS之外的资源,频带上均匀分布(DwPTS只能...

     

     

    PCFICH占用第一个符号的4个REG,频带上均匀分布

    PHICH至少占用3个REG,可以是分布在第1~3个符号,频带上均匀分布

    PDCCH占用第1~3个符号的扣除PCFICH、PHICH、RS之外的资源,频带上均匀分布(DwPTS只能占用第1~2个符号)

    PBCH占用中心频带72个子载波,在每无线帧的0子帧的第2个时隙的第1~4个符号

    PUCCH位于上行子帧的频域两边带上,并根据容量依次向频带中心占用RB

    SRS:
    可以在普通上行子帧上传输,也可以在UpPTS上传输,位于上行子帧的最后一个SC-FDMA符号,eNB配置UE在某个时频资源上

    DMRS: 作为PUSCH的伴随信令,位于每个时隙的第4个符号

    用于PUCCH-ACK,在频带边带上的每个时隙中间三个符号(第3、4、5个符号)

    用于PUCCH-CQI,在频带边带上的每个时隙第2、6个符号

    PRACH频域上72个子载波的大小,可以频分成多个PRACH的资源块,一般挨着PUCCH依次向外放置,不一定要在中心频率上在普通子帧是format0~3,在UpPTS上是format4;每10ms无线帧接入0.5~6次,每个子帧采用频分方式可支持多个随机接入

     

     

     

     

    展开全文
  • 详解操作系统分配内存

    万次阅读 2017-07-08 16:37:29
    计算机体系结构和内存层次 操作系统中内存的最小访问单位是 字节 ,也就是8bit。 通常我们所说的计算机系统是32位的总线,所谓的32位总线就是说一次读写可以从内存当中读或者写32位(也就是4字节)。...

    计算机体系结构和内存层次

    操作系统中内存的最小访问单位是 字节 ,也就是8bit。

    通常我们所说的计算机系统是32位的总线,所谓的32位总线就是说一次读写可以从内存当中读或者写32位(也就是4字节)。

    因为一次读写是32位,所以需要地址对齐,访问的时候不能从任意地方开始。

    在CPU中可以看到高速缓存,由于指令执行和访问数据都需要从内存里读数据,如果此时有大量数据要读写而且会重复利用的话,那么在CPU中加高速缓存会使读写进行得更快。

    有了这样一个大致了解,可以来看内存层次结构。

    首先CPU在读写指令和数据的时候,如果缓存里已经有相应的内容,那么CPU直接从缓存中拿到数据,这时候速度是最快的。(写程序的时候完全感受不到L1缓存和L2缓存的存在,因为这部分是硬件控制的,不能显示使用它们。)

    如果缓存不命中,那么就必须去内存中读。如果内存还是没找到,那就去外存中读。(访问速度又有很大差别)

    虽然计算机硬件一直在飞速发展,内存容量也在不断增长,但是仍然不可能将所有用户进程和系统所需要的全部程序和数据放入主存中,所以操作系统就要对内存进行合理地划分和有效地动态分配。操作系统需要做到四个方面:抽象、保护、共享和虚拟化。

    如图,四个进程在操作系统的划分和管理下,彼此之间在逻辑上既需要相互独立,又可以相互通信。

    操作系统中采用的内存管理方式有:

    • 重定位(relocation)
    • 分段(segmentation)
    • 分页(paging)
    • 虚拟存储(virtual memory)

    目前多数系统(如 Linux)采用按需页式虚拟存储。

    地址空间和地址生成

    物理地址空间——硬件支持的地址空间,起始地址从0直到MAXsys。这个编号在存储单元角度来讲是唯一的,但是这种唯一对于我们写程序来说是不大容易的,因为我们在写程序的时候对于到底要使用哪个地址可能是不知道的。

    逻辑地址空间——在CPU运行的进程看到的地址,起始地址从0知道MAXprog。对应的是可执行文件的那段空间。

    对于我们用高级语言编写的程序,经过如下过程生成它的逻辑地址:

    此时的逻辑地址生成时机的不同会有不同的限制。

    • 编译时:已经假设起始地址已知,如果起始地址改变,必须重新编译。例如以前的手机,程序是写死的,不能自己安装应用,只能用手机里编译好的。
    • 加载时:如编译时起始位置未知,编译器需生成可重定位的代码。例如现在的智能手机,可以下载很多APP。
    • 执行时:执行时代码可移动,但需地址转换(映射)硬件支持。这种情况出现在使用虚拟存储的系统,

    逻辑地址生成后,接着就是生成物理地址,过程如下:

    因为内存有着诸多限制,所以也有着对应的检查机制。检查过程如图:

    连续地址分配

    生成地址后接着分配地址,连续内存分配是给进程分配一块不小于指定大小的连续的物理内存区域。地址分配从两个角度考虑:如何去找你要用的空间分区;如何处理不能利用的小的空闲分区。

    这里不能利用的小的空闲分区我们统称为 内存碎片 ,内存碎片分为三类:

    • 内存碎片:有的还可以用,有的无论如何都用不起来了。
    • 外部碎片:分配单元之间的未被使用内存
    • 内部碎片:分配单元内部的未被使用内存(你只占500字节,但是不得不分配512字节)

    这里我们就不得不有所取舍地选择不同的分配策略,常用的有三种:最先匹配(First-fit)、最佳匹配(Best-fit)、最差匹配(Worst-fit)。

    最先匹配(First Fit Allocation)策略

    原理 & 实现:

    • 空闲分区列表按地址顺序排序
    • 分配过程时,搜索一个合适的分区
    • 释放分区时,检查是否可与临近的空闲分区合并

    优点:

    • 简单(这也算优点的话)
    • 在高地址空间有大块的空闲分区

    缺点:

    • 外部碎片
    • 分配大块时较慢

    最佳匹配(Best Fit Allocation)策略

    原理 & 实现:

    • 空闲分区列表按照大小排序
    • 分配时,查找一个合适的分区
    • 释放时,查找并且合并临近的空闲分区(如果找到)

    优点:

    • 大部分分配的尺寸较小时,效果很好(可避免大的空闲分区被拆分)
    • 可减小外部碎片的大小

    缺点:

    • 外部碎片
    • 释放分区缓慢
    • 容易产生很多无用的小碎片

    最差匹配(Worst Fit Allocation)策略

    原理 & 实现:

    • 空闲分区列表按由大到小排序
    • 分配时,选最大的分区
    • 释放时,检查是否可与临近的空闲分区合并,进行可能的合并,并调整空闲分区列表顺序

    优点:

    • 中等大小的分配较多时,效果最好
    • 避免出现太多的小碎片

    缺点:

    • 释放分区较慢
    • 外部碎片
    • 容易破坏大的空闲分区,因此后续难以分配大的分区

    碎片整理

    通过调整进程占用的分区位置来减少或避免分区碎片

    1. 紧凑(compaction) 通过移动分配给进程的内存分区,以合并外部碎片。紧凑的条件是:所有的应用程序可动态重定位。

    2. 分区对换(Swapping in/out) 通过抢占并回收处于等待状态进程的分区,以增大可用内存空间。

    伙伴系统(Buddy System)

    伙伴系统即,整个可分配的分区大小2^U,需要的分区大小为2^(U-1) < s ≤ 2^U 时,把整个块分配给该进程。

    伙伴系统的实现参见: Buddy memory allocation



      内存是计算机中最重要的资源之一,通常情况下,物理内存无法容纳下所有的进程。虽然物理内存的增长现在达到了N个GB,但比物理内存增长还快的是程序,所以无论物理内存如何增长,都赶不上程序增长的速度,所以操作系统如何有效的管理内存便显得尤为重要。本文讲述操作系统对于内存的管理的过去和现在,以及一些页替换的算法的介绍。

     

    对于进程的简单介绍

        在开始之前,首先从操作系统的角度简单介绍一下进程。进程是占有资源的最小单位,这个资源当然包括内存。在现代操作系统中,每个进程所能访问的内存是互相独立的(一些交换区除外)。而进程中的线程所以共享进程所分配的内存空间。

        在操作系统的角度来看,进程=程序+数据+PCB(进程控制块)。这个概念略微有点抽象,我通过一个类比来说吧:比如,你正在厨房做饭,你一边看着菜谱一边按照菜谱将原料做成菜,就在这时,你儿子进来告诉你他擦破了腿,此时你停下手中的工作,将菜谱反扣过来,然后找来急救书按照书中的内容给你儿子贴上创口贴,贴完后你继续回去打开菜谱,然后继续做饭。在这个过程中,你就好比CPU,菜谱就好比程序,而做菜的原料就好比数据。你按照程序指令加工数据,而急救工作好比一个更高优先级的进程,中断了你当前做饭的工作,然后你将菜谱反扣过来(保护现场),转而去处理高优先级的进程,处理完毕后你继续从刚才的页读菜谱(恢复现场),然后继续执行做菜这个进程。

        在简单介绍完进程的概念后,我们来转入内存。

     

    没有内存抽象的年代

        在早些的操作系统中,并没有引入内存抽象的概念。程序直接访问和操作的都是物理内存。比如当执行如下指令时:

    mov reg1,1000

        这条指令会毫无想象力的将物理地址1000中的内容赋值给寄存器。不难想象,这种内存操作方式使得操作系统中存在多进程变得完全不可能,比如MS-DOS,你必须执行完一条指令后才能接着执行下一条。如果是多进程的话,由于直接操作物理内存地址,当一个进程给内存地址1000赋值后,另一个进程也同样给内存地址赋值,那么第二个进程对内存的赋值会覆盖第一个进程所赋的值,这回造成两条进程同时崩溃。

        没有内存抽象对于内存的管理通常非常简单,除去操作系统所用的内存之外,全部给用户程序使用。或是在内存中多留一片区域给驱动程序使用,如图1所示。

        1

        图1.没有内存抽象时,对内存的使用

      

        第一种情况操作系统存于RAM中,放在内存的低地址,第二种情况操作系统存在于ROM中,存在内存的高地址,一般老式的手机操作系统是这么设计的。

        如果这种情况下,想要操作系统可以执行多进程的话,唯一的解决方案就是和硬盘搞交换,当一个进程执行到一定程度时,整个存入硬盘,转而执行其它进程,到需要执行这个进程时,再从硬盘中取回内存,只要同一时间内存中只有一个进程就行,这也就是所谓的交换(Swapping)技术。但这种技术由于还是直接操作物理内存,依然有可能引起进程的崩溃。

        所以,通常来说,这种内存操作往往只存在于一些洗衣机,微波炉的芯片中,因为不可能有第二个进程去征用内存。

     

    内存抽象

        在现代的操作系统中,同一时间运行多个进程是再正常不过的了。为了解决直接操作内存带来的各种问题,引入的地址空间(Address Space),这允许每个进程拥有自己的地址。这还需要硬件上存在两个寄存器,基址寄存器(base register)和界址寄存器(limit register),第一个寄存器保存进程的开始地址,第二个寄存器保存上界,防止内存溢出。在内存抽象的情况下,当执行

    mov reg1,20

        这时,实际操作的物理地址并不是20,而是根据基址和偏移量算出实际的物理地址进程操作,此时操作的实际地址可能是:

    mov reg1,16245

     

        在这种情况下,任何操作虚拟地址的操作都会被转换为操作物理地址。而每一个进程所拥有的内存地址是完全不同的,因此也使得多进程成为可能。

        但此时还有一个问题,通常来说,内存大小不可能容纳下所有并发执行的进程。因此,交换(Swapping)技术应运而生。这个交换和前面所讲的交换大同小异,只是现在讲的交换在多进程条件下。交换的基本思想是,将闲置的进程交换出内存,暂存在硬盘中,待执行时再交换回内存,比如下面一个例子,当程序一开始时,只有进程A,逐渐有了进程B和C,此时来了进程D,但内存中没有足够的空间给进程D,因此将进程B交换出内存,分给进程D。如图2所示。

        2

        图2.交换技术

     

        通过图2,我们还发现一个问题,进程D和C之间的空间由于太小无法另任何进程使用,这也就是所谓的外部碎片。一种方法是通过紧凑技术(Memory Compaction)解决,通过移动进程在内存中的地址,使得这些外部碎片空间被填满。还有一些讨巧的方法,比如内存整理软件,原理是申请一块超大的内存,将所有进程置换出内存,然后再释放这块内存,从而使得从新加载进程,使得外部碎片被消除。这也是为什么运行完内存整理会狂读硬盘的原因。另外,使用紧凑技术会非常消耗CPU资源,一个2G的CPU没10ns可以处理4byte,因此多一个2G的内存进行一次紧凑可能需要好几秒的CPU时间。

        上面的理论都是基于进程所占的内存空间是固定的这个假设,但实际情况下,进程往往会动态增长,因此创建进程时分配的内存就是个问题了,如果分配多了,会产生内部碎片,浪费了内存,而分配少了会造成内存溢出。一个解决方法是在进程创建的时候,比进程实际需要的多分配一点内存空间用于进程的增长。一种是直接多分配一点内存空间用于进程在内存中的增长,另一种是将增长区分为数据段和栈(用于存放返回地址和局部变量),如图3所示。

        3

        图3.创建进程时预留空间用于增长

     

        当预留的空间不够满足增长时,操作系统首先会看相邻的内存是否空闲,如果空闲则自动分配,如果不空闲,就将整个进程移到足够容纳增长的空间内存中,如果不存在这样的内存空间,则会将闲置的进程置换出去。

         当允许进程动态增长时,操作系统必须对内存进行更有效的管理,操作系统使用如下两种方法之一来得知内存的使用情况,分别为1)位图(bitmap) 2)链表

         使用位图,将内存划为多个大小相等的块,比如一个32K的内存1K一块可以划为32块,则需要32位(4字节)来表示其使用情况,使用位图将已经使用的块标为1,位使用的标为0.而使用链表,则将内存按使用或未使用分为多个段进行链接,这个概念如图4所示。

        4

         图4.位图和链表表示内存的使用情况

     

         使用链表中的P表示进程,从0-2是进程,H表示空闲,从3-4表示是空闲。

         使用位图表示内存简单明了,但一个问题是当分配内存时必须在内存中搜索大量的连续0的空间,这是十分消耗资源的操作。相比之下,使用链表进行此操作将会更胜一筹。还有一些操作系统会使用双向链表,因为当进程销毁时,邻接的往往是空内存或是另外的进程。使用双向链表使得链表之间的融合变得更加容易。

        还有,当利用链表管理内存的情况下,创建进程时分配什么样的空闲空间也是个问题。通常情况下有如下几种算法来对进程创建时的空间进行分配。

    •      临近适应算法(Next fit)---从当前位置开始,搜索第一个能满足进程要求的内存空间
    •      最佳适应算法(Best fit)---搜索整个链表,找到能满足进程要求最小内存的内存空间
    •      最大适应算法(Wrost fit)---找到当前内存中最大的空闲空间
    •      首次适应算法(First fit) ---从链表的第一个开始,找到第一个能满足进程要求的内存空间

     

    虚拟内存(Virtual Memory)

        虚拟内存是现代操作系统普遍使用的一种技术。前面所讲的抽象满足了多进程的要求,但很多情况下,现有内存无法满足仅仅一个大进程的内存要求(比如很多游戏,都是10G+的级别)。在早期的操作系统曾使用覆盖(overlays)来解决这个问题,将一个程序分为多个块,基本思想是先将块0加入内存,块0执行完后,将块1加入内存。依次往复,这个解决方案最大的问题是需要程序员去程序进行分块,这是一个费时费力让人痛苦不堪的过程。后来这个解决方案的修正版就是虚拟内存。

        虚拟内存的基本思想是,每个进程有用独立的逻辑地址空间,内存被分为大小相等的多个块,称为(Page).每个页都是一段连续的地址。对于进程来看,逻辑上貌似有很多内存空间,其中一部分对应物理内存上的一块(称为页框,通常页和页框大小相等),还有一些没加载在内存中的对应在硬盘上,如图5所示。

        5

        图5.虚拟内存和物理内存以及磁盘的映射关系

     

        由图5可以看出,虚拟内存实际上可以比物理内存大。当访问虚拟内存时,会访问MMU(内存管理单元)去匹配对应的物理地址(比如图5的0,1,2),而如果虚拟内存的页并不存在于物理内存中(如图5的3,4),会产生缺页中断,从磁盘中取得缺的页放入内存,如果内存已满,还会根据某种算法将磁盘中的页换出。

        而虚拟内存和物理内存的匹配是通过页表实现,页表存在MMU中,页表中每个项通常为32位,既4byte,除了存储虚拟地址和页框地址之外,还会存储一些标志位,比如是否缺页,是否修改过,写保护等。可以把MMU想象成一个接收虚拟地址项返回物理地址的方法。

        因为页表中每个条目是4字节,现在的32位操作系统虚拟地址空间会是2的32次方,即使每页分为4K,也需要2的20次方*4字节=4M的空间,为每个进程建立一个4M的页表并不明智。因此在页表的概念上进行推广,产生二级页表,二级页表每个对应4M的虚拟地址,而一级页表去索引这些二级页表,因此32位的系统需要1024个二级页表,虽然页表条目没有减少,但内存中可以仅仅存放需要使用的二级页表和一级页表,大大减少了内存的使用。

     

    页面替换算法

        因为在计算机系统中,读取少量数据硬盘通常需要几毫秒,而内存中仅仅需要几纳秒。一条CPU指令也通常是几纳秒,如果在执行CPU指令时,产生几次缺页中断,那性能可想而知,因此尽量减少从硬盘的读取无疑是大大的提升了性能。而前面知道,物理内存是极其有限的,当虚拟内存所求的页不在物理内存中时,将需要将物理内存中的页替换出去,选择哪些页替换出去就显得尤为重要,如果算法不好将未来需要使用的页替换出去,则以后使用时还需要替换进来,这无疑是降低效率的,让我们来看几种页面替换算法。

       

    最佳置换算法(Optimal Page Replacement Algorithm)

         最佳置换算法是将未来最久不使用的页替换出去,这听起来很简单,但是无法实现。但是这种算法可以作为衡量其它算法的基准。

     

    最近不常使用算法(Not Recently Used Replacement Algorithm)

         这种算法给每个页一个标志位,R表示最近被访问过,M表示被修改过。定期对R进行清零。这个算法的思路是首先淘汰那些未被访问过R=0的页,其次是被访问过R=1,未被修改过M=0的页,最后是R=1,M=1的页。

     

    先进先出页面置换算法(First-In,First-Out Page Replacement Algorithm)

        这种算法的思想是淘汰在内存中最久的页,这种算法的性能接近于随机淘汰。并不好。

     

    改进型FIFO算法(Second Chance Page Replacement Algorithm)

        这种算法是在FIFO的基础上,为了避免置换出经常使用的页,增加一个标志位R,如果最近使用过将R置1,当页将会淘汰时,如果R为1,则不淘汰页,将R置0.而那些R=0的页将被淘汰时,直接淘汰。这种算法避免了经常被使用的页被淘汰。

     

    时钟替换算法(Clock Page Replacement Algorithm)

        虽然改进型FIFO算法避免置换出常用的页,但由于需要经常移动页,效率并不高。因此在改进型FIFO算法的基础上,将队列首位相连形成一个环路,当缺页中断产生时,从当前位置开始找R=0的页,而所经过的R=1的页被置0,并不需要移动页。如图6所示。

        6

        图6.时钟置换算法

     

    最久未使用算法(LRU Page Replacement Algorithm)

        LRU算法的思路是淘汰最近最长未使用的页。这种算法性能比较好,但实现起来比较困难。

     

    下面表是上面几种算法的简单比较:

    算法 描述
    最佳置换算法 无法实现,最为测试基准使用
    最近不常使用算法 和LRU性能差不多
    先进先出算法 有可能会置换出经常使用的页
    改进型先进先出算法 和先进先出相比有很大提升
    最久未使用算法 性能非常好,但实现起来比较困难
    时钟置换算法 非常实用的算法

     

        上面几种算法或多或少有一些局部性原理的思想。局部性原理分为时间和空间上的局部性

        1.时间上,最近被访问的页在不久的将来还会被访问。

        2.空间上,内存中被访问的页周围的页也很可能被访问。



    展开全文
  • 资源分配

    万次阅读 2017-05-27 11:48:43
    为了准确的描述死锁问题,我们引出了资源分配
  • 任务分配问题(匈牙利算法)

    千次阅读 2017-04-27 00:24:30
    问题描述:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。 问题数学描述:   二、实例分
  • 栈上分配、TLAB

    千次阅读 2018-05-24 14:46:25
    如果开启栈上分配,JVM会先进行栈上分配,如果没有开启栈上分配或则不符合条件的则会进行TLAB分配,如果TLAB分配不成功,再尝试在eden区分配,如果对象满足了直接进入老年代的条件,那就直接分配在老年代,如下图。...
  • 连续分配之顺序搜索法 (1)单一连续分配:只能用于单用户、单任务的操作系统中。采用这: 种存储管理方式时,可把内存分为系统区和用户区两部分,系统区仅提供给OS使用,通常是放在内存的低址部分;用户区是指除...
  • 下载一个 分区助手 操作很简单,别忘了最后点提交按钮
  • 路由器为进行动态ip分配 解决1: 进入路由器后台设置动态ip获取 或者手机设置静态ip 原因2: 路由器已开启动态ip,可能动态ip池满了 解决2 在路由器上踢掉某些不用的DHCP 客户端,释放 ip 资源, 连接中的手机会自动连接 ...
  • 内存的静态分配和动态分配的区别

    万次阅读 2011-08-27 12:04:13
    内存的静态分配和动态分配的区别主要是两个:  一是时间不同。静态分配发生在程序编译和连接的时候。动态分配则发生在程序调入和执行的时候。  二是空间不同。堆都是动态分配的,没有静态分配的堆。栈有2种分配...
  • Matlab预分配内存优化for循环

    万次阅读 2016-06-04 23:30:22
    在Matlab中for循环在进行前没有预分配内存。重复扩展数组的尺寸,会花费更多的时间分配内存,导致程序性能降低。并且这些内存不一定是连续的,这更会减慢程序的操作。因此,我们可以采用预分配数组空间来解决这一...
  • Matlab预分配内存

    万次阅读 多人点赞 2016-10-15 10:31:31
    分配内存简介:对于for,while循环,在循环的过程中每次不断的增加数据结构的大小,影响了性能和内存的使用。重复的调整数据的大小需要Matlab花费额外的时间寻找更大的连续内存块,并且将现在的数组移动到连续的...
  • 内存分配方式有几种?

    万次阅读 2013-10-12 09:11:55
    内存分配方式有几种? 静态存储区 栈 堆 的内存分配 1,从静态存储区域分配内存。程序编译的时候内存已经分配好了,并且在程序的整个运行期间都存在,例如全局变量。 2,在栈上创建。在执行函数时,函数内局部...
  • 安装ubuntu时如何合理为各区间分配磁盘空间? 具体怎么安装ubuntu就不用介绍了,网上有很多相关内容,一般用U盘装的话比较简单,也很方便,我自己平常装系统的话,一般是做一个U盘启动盘,然后用U盘安装(如何做U盘...
  • 在黑色的未分配空间上建立新的卷 使用分区助手或者DiskGenius将新建立的卷从主分区转换成逻辑分区 在磁盘管理中删除这个卷,然后就会变成绿色的空用空间 ...
  • 1.用分区助手等软件将未分配的分区合并到相邻分区 2.在合并后的分区压缩卷,数值填入“可用”的大小 3.此时你会发现该块内存已经是可用空间。  
  • 动态分区分配算法

    万次阅读 多人点赞 2016-12-08 17:11:46
    动态分区分配算法 一.顺序搜索的动态分区分配算法 1.首次适应算法(First Fit)  算法思想:将空闲分区链以地址递增的顺序连接;在进行内存分配时,从链首开始顺序查找,直到找到一块分区的大小可以满足需求时,...
  • 参考: http://bbs.csdn.net/topics/391071992
1 2 3 4 5 ... 20
收藏数 2,284,266
精华内容 913,706
关键字:

分配