2022 年 1 月 – 3Fun's Blog

LRU算法四种实现方式介绍(转)

LRU全称是Least Recently Used，即最近最久未使用的意思。

LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

实现LRU

1. 用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。
2.利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。
3. 利用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。
对于第一种方法，需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。对于第二种方法，链表在定位数据的时候时间复杂度为O(n)。所以在一般使用第三种方式来是实现LRU算法。

当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。

扩展

1.LRU-K

LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。

数据第一次被访问时，加入到历史访问列表，如果书籍在访问历史列表中没有达到K次访问，则按照一定的规则（FIFO,LRU）淘汰；当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列中删除，将数据移到缓存队列中，并缓存数据，缓存队列重新按照时间排序；缓存数据队列中被再次访问后，重新排序，需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即“淘汰倒数K次访问离现在最久的数据”。LRU-K具有LRU的优点，同时还能避免LRU的缺点，实际应用中LRU-2是综合最优的选择。由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象，因此内存消耗会比LRU要多。

2.two queue

Two queues（以下使用2Q代替）算法类似于LRU-2，不同点在于2Q将LRU-2算法中的访问历史队列（注意这不是缓存数据的）改为一个FIFO缓存队列，即：2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。当数据第一次访问时，2Q算法将数据缓存在FIFO队列里面，当数据第二次被访问时，则将数据从FIFO队列移到LRU队列里面，两个队列各自按照自己的方法淘汰数据。

新访问的数据插入到FIFO队列中，如果数据在FIFO队列中一直没有被再次访问，则最终按照FIFO规则淘汰；如果数据在FIFO队列中再次被访问到，则将数据移到LRU队列头部，如果数据在LRU队列中再次被访问，则将数据移动LRU队列头部，LRU队列淘汰末尾的数据。

3.Multi Queue(MQ)

MQ算法根据访问频率将数据划分为多个队列，不同的队列具有不同的访问优先级，其核心思想是：优先缓存访问次数多的数据。详细的算法结构图如下，Q0，Q1….Qk代表不同的优先级队列，Q-history代表从缓存中淘汰数据，但记录了数据的索引和引用次数的队列：

新插入的数据放入Q0，每个队列按照LRU进行管理，当数据的访问次数达到一定次数，需要提升优先级时，将数据从当前队列中删除，加入到高一级队列的头部；为了防止高优先级数据永远不会被淘汰，当数据在指定的时间里没有被访问时，需要降低优先级，将数据从当前队列删除，加入到低一级的队列头部；需要淘汰数据时，从最低一级队列开始按照LRU淘汰，每个队列淘汰数据时，将数据从缓存中删除，将数据索引加入Q-history头部。如果数据在Q-history中被重新访问，则重新计算其优先级，移到目标队列头部。 Q-history按照LRU淘汰数据的索引。
MQ需要维护多个队列，且需要维护每个数据的访问时间，复杂度比LRU高。

LRU算法对比

对比点	对比
命中率	LRU-2 > MQ(2) > 2Q > LRU
复杂度	LRU-2 > MQ(2) > 2Q > LRU
代价	LRU-2 > MQ(2) > 2Q > LRU

原文地址：https://blog.csdn.net/elricboa/article/details/78847305

Windows10 下搭建汇编语言开发环境（转）

1. 工具准备

1）下载 DOSBOX

工具介绍：DOSBox 是一个 DOS 模拟程序，由于它采用的是 SDL 库，所以可以很方便的移植到其他的平台。目前，DOSBox 已经支持在 Windows、Linux、Mac OS X、BeOS 、palmOS、Android 、webOS、os/2等系统中运行。不少DOS下的游戏都可以直接在该平台上运行。

工具官网：http://www.dosbox.com/
项目主页：http://sourceforge.net/projects/dosbox/
下载链接：http://sourceforge.net/projects/dosbox/files/dosbox/0.74/DOSBox0.74-win32-installer.exe/download（32位）
说明：由于项目已经停更，目前官网上指出，DOSBOX可以运行于32位和64位的Windows Vista和Windows 7之上，根据本人亲测，亦可在 32位和 64位的 Windows 10 上运行 DOSBOX，因此有需要的童鞋可以试试。

2）下载 MASM32

工具介绍：MASM32是国外的MASM爱好者Steve Hutchesson自行整理和编写的一个软件包，目前最高版本为11r版。MASM32并非指Microsoft的MASM宏汇编器，而是包含了不同版本工具组建的汇编开发工具包。它的汇编编译器是MASM6.0以上版本中的Ml.exe，资源编译器是Microsoft Visual Studio中的Rc.exe，32位链接器是Microsoft Visual Studio中的Link.exe，同时包含有其他的一些如 Lib.exe 和 DumpPe.exe 等工具。
工具官网：http://www.masm32.com/
下载链接：http://www.masm32.com/download.htm

汇编文件2019年7月 https://pan.baidu.com/s/1w27JQtrklbaM4ZpzGVZr7A

masm文件夹内至少要包含这4个文件：masm.exe, link.exe, debug.exe, exe2bin.exe。其中：
masm.exe：汇编程序，用于汇编源程序(.asm)，得到目标程序(.obj)；
link.exe：连接程序，用于连接目标程序，得到可执行程序(.exe)；
debug.exe：调试程序，用于调试可执行程序。
还可以下载其他的程序。

注意：masm工具压缩包，里面包含必要的汇编、链接、调试工具

2.安装工具

1）安装 DOSBOX

  安装下载到的DOSBox0.74-win32-installer.exe，直接一路Next完成安装。

2）配置 DOSBOX

创建两个目录，

一个用来保存汇编工具，如：D:\huibian\masm 。将汇编工具放到新建的工作目录下。（实际会用到的有以下程序：debug.exe edit.com link.exe masm.exe ）
一个用来保存汇编源文件（如：D:\huibian\debug ）。

打开 DOSBOX 的安装根目录（默认安装路径：C:\Program Files\DOSBox-0.74；若是64位的系统，则默认安装路径：C:\Program Files (x86)\DOSBox-0.74），双击文件 DOSBox 0.74 Options.bat，运行该批处理文件后系统会用文本文档Notepad打开配置文件dosbox-0.74.conf。（如果双击没反应，直接命令行执行）

将光标定位到 dosbox-0.74.conf 文件的 [autoexec] 节点（一般在该文件末尾），在文件中添加以下内容：

MOUNT C D:\huibian               # 将 目录 D:\huibian 挂载为 DOSBOX 下的 C:
 set PATH=$PATH$;C:\masm          # 将 映射后 C:\masm 写入环境变量 PATH 中
 环境变量添加 c:\masm，这样就可以调用 d:\huibian\masm\下的编译工具;
 注意：不能设置成 set path=%path%;d:\masm\，因为此时 d盘 已挂载到 c盘 上
 C:                               # 进入 dosbox 系统 的 C 盘

mount 的作用是将 pc 目录映射到 dos 系统的目录。这里是将我电脑中 D:\huibian 映射到了 dos 系统 c 盘，这样你对 dos 的c盘的操作就相当于是对 D:\huibian 的操作。

其实可以不修改 conf 文件，只要在每次运行时输入这两个命令就行了。

保存文件后关闭。

为什么要修改 dosbox 的 conf 文件？ dosbox 的 conf 文件的 [autoexec]标签下面的代码会在 dosbox 启动时运行，这样就不用在 dosbox 中每次输入代码了。

3）安装 MASM32

将压缩包里面的 MASM 文件夹里面的东西放到一个文件夹，路径尽量为英文，其他路径也可以，但是路径不要有中文和空格。
我的电脑中路径：（ D:\huibian\masm ）

现在，打开 dosbox，输入 dir 。看看有没有 DEBUG，MASM 等文件。如果有的话就说明成功了，可以开始写汇编了。

安装结束后，可直接利用 masm32v11r 中的 gedit.exe 程序编写、编译和链接 asm 汇编程序。

3. 编辑和调试程序

3.1. 编辑源程序。

有两种方法编辑汇编源程序：

新建文本文件，修改文件名和文件扩展名为 test.asm，将 test.asm 放到 D:\huibian\debug 文件夹。
也可以运行 DOSBOX，在命令符 C:\DEBUG> 下输入命令：edit test.asm，启动 EDIT.EXE 进入代码编辑状态，并输入如下样例程序：
也可以使用 edit 命令直接编辑。使用 edit 命令进去后光标会消失，此时调用任务管理器 alt+ctrl+del 即可释放光标。

如果你觉得窗口太小，字体太小，你可以按 alt+enter 切换到全屏模式
同时在配置文件的第26行有一行字符 “fullresolution=original”，这是用来调节DOS窗口全屏下的分辨率的，默认original的值是640×480（中间是小写x），我个人的电脑将 original 改为 800×600 就比较舒服

;完整段的 Hello World 程序
 DATAS  SEGMENT
      STRING  DB  'Hello World!',13,10,'$'
 DATAS  ENDS
 CODES  SEGMENT
      ASSUME    CS:CODES,DS:DATAS
 START:
      MOV  AX,DATAS
      MOV  DS,AX
      LEA  DX,STRING
      MOV  AH,9
      INT  21H
  MOV  AH,4CH  INT  21H
 CODES  ENDS
     END   START

3.2. 汇编

打开 dosbox，输入命令：masm，然后输入汇编源文件名，其他都默认即可。

命令执行完后，会生成目标文件文件名 .OBJ（生成过程中可以修改目标文件名，直接回车可保持默认目标文件名）。

 注意：此时可能生成三个文件：*.obj、*.lst和*.crf文件（ Windows10 x64系统只会生成*.obj文件 ）。其中，列表文件*.lst和交叉引用文件非必选，前者是汇编语言汇编的机器语言与汇编语言对照表，可用于调试；后者给出了用户定义的所有符号和对每个符号定义、引用的行号。

3.3. 连接

先输入link，再输入文件名，之后一直回车。

LINK 文件名.OBJ，链接生成可执行文件文件名.EXE。

注意：由于在上述代码中未定义堆栈段，故在链接时会提示：LINK : warning L4021: no stack segment，因不会影响执行文件的生成，故暂时忽略。

 另外，此时可能生成两个文件：*.exe和*.map文件（Windows10 x64系统可能只会生成*.exe文件）。其中，地址映射文件*.map给出内存地址分配的有关信息。

3.4. 运行

直接运行生成的 exe 程序

3.5. 调试

汇编语言之 Debug 教程篇：https://blog.csdn.net/qq_36215315/article/details/79893476

输入命令：debug 文件名.EXE，在 DEBUG 的命令提示符 ‘-‘ 出现后开始调试，

注意：是针对可执行程序。debug 文件名.exe。进入调试模式，在短横线后输入命令。

网上可查到命令集。以下是部分调试命令及截图：

R：查看程序运行前的寄存器组初始值；
U：查看程序反汇编代码。从反汇编代码中可看出，变量会被汇编为直接寻址方式，使用变量在数据段内的有效地址表示。
T：单步调试；
D：观察内存变化（D后不带地址或范围，默认显示上一个D命令之后的80字节内容）；
G 地址：程序从当前位置直接运行到指定地址处停下。
E 地址：修改内存中的内容，如：E DS:0100，输入空格可逐个字节修改，回车停止修改。

例如，g：运行程序。q：退出调试模式。

4. 其他工具

emu8086。直接编译、运行、调试，不需要dosbox。
masm for windows，友好的文本编辑器，但是运行和调试仍会调出dosbox。

链接：https://pan.baidu.com/s/16DxS5Yjizc-mve_5oUShBg 密码：3z3e

原文地址

VirtualBox 安装ubuntu全屏显示

首先在virtualbox的工具栏中，点击“设备”选项；选择“安装增强功能”，如果是英文版的VirtualBox，英文也很容易看懂。当点击后，virtualbox会挂载工具在ubuntu的一个文件下。

启动ubuntu，点击终端工具，进入命令行模式。用 cd /media 命令到这个目录下。
3目录会有一个以你账号名字的文件夹，继续用cd命令进入下一层目录。就能看到virtualbox为各种不同的系统平台准备的工具。
4在管理员模式下，运行对应的平台命令。本系统是ubuntu，所以运行的命令是sudo ./VBoxLinuxAdditions.run 。等待命令行脚本执行完毕。

当系统提示按回车完成的时候，就表示安装完成。如果是英文系统，请留意最后一句话。
6安装完成后，需要重启系统生效。这时候，可以直接在命令行中输入reboot, 重启系统。也可以在virtualbox外部提供的工具中，暴力的重启系统。
7当重启完成后，进入系统。这时候拉动virtualbox的窗口大小。系统也会跟随着变大变小。