㈠ 算法中基本运算的频度是什么意思
语句执行频度表示一次运行中语句总共执行的次数时间复杂度用基本语句执行频度表示
㈡ 磁盘缓存置换算法作用是什么
虽然缓存的最终目的为了提高性能，但缓存写的技术与缓存读的技术有很大的不同。但如果它带来的数据丢失危险很大，那么，就是一个不可接受的方案。因此，安全地将数据保存在非易失存储中是很重要的，因为这样数据就可以长期地保存。虽然读缓存技术用于读操作时可以提高系统性能，但当用于新产生数据的写操作时，却产生了一些有趣的问题。
目前，用于缓存实现的大部分存储器都是易失型存储器，因此，当断电的时候，所有缓存的数据都将丢失。为了避免这个问题，一种专为缓存而特别设计的存储器已经面世，这种特制的存储器内嵌后备电池，经常用于磁盘子系统，以保证在某一指定时间内供电和数据存储。其他类型的非易失内存也已经生产出来，如闪存，但由于它们价格相对较高、性能较低及使用寿命有限等，通常不被用作缓存内存。
下面考虑使用L R U的示例，并假定某个应用正在更新数据。由于在缓存中可能存储了过时数据。这里过时数据是指被存储的数据，但不表示最新的版本。当应用修改数据时，过时的数据也必须要修改，无论它存放在哪里—在磁盘上，或者在磁盘和缓存内存里。图显示了两种情况：第一种情况是数据仅存放在磁盘上；第二种情况是数据既存放在磁盘上，也存放在缓存内存中。
在缓存未命中情况下，缓存控制器决定是否缓存这些数据。对于这个例子，缓存控制器决定放弃缓存关于这个写操作的数据，而把该数据直接写入非易失存储。换言之，数据仅写入磁盘，继续执行下一个操作。
在缓存命中情况下，缓存控制器可以修改缓存，甚至丢弃缓存，或使缓存内容无效，以致于后来的数据能够覆盖它。假如修改了缓存，必须最终在某个时刻将它写入非易失磁盘存储，但什么时候写呢？可能数据在近期将不被修改，但也可能它成为一个热点，将经历接二连三地、快速的操作。数据写入非易失存储器速度相对较慢，因为必须等待磁盘设备写完成后，才能进行新的写操作，致使系统的性能降低。另一方面，假如数据首先被写进缓存，延迟一段时间后才被写到非易失存储，那么，电源的临时故障就有可能导致数据的丢失。
㈢ 代码访问频率太高，消耗cpu，如何优化
你好
1，右击任务栏，然后点击任务管理器，点进程，关闭耗资源高的程序。
2，可能是电脑中毒，电脑杀毒，建议在安全模式下进行杀毒。
3，少开一些比较耗CPU资源的程序。
4，可能CPU逻辑处理器数少，程序所需的资源不足，便会达到100%，所以建议更换拥有更多核心的CPU。
㈣ 请问AMD的处理器 主频怎么计算 一级、二级缓存技术是怎么回事
这个没用固定的计算公式，只有死记频率了，比如3000+对应1.8G。
缓存是CPU的一部分，它存在于CPU中
CPU存取数据的速度非常的快，一秒钟能够存取、处理十亿条指令和数据（术语：CPU主频1G），而内存就慢很多，快的内存能够达到几十兆就不错了，可见两者的速度差异是多么的大
缓存是为了解决CPU速度和内存速度的速度差异问题
内存中被CPU访问最频繁的数据和指令被复制入CPU中的缓存，这样CPU就可以不经常到象“蜗牛”一样慢的内存中去取数据了，CPU只要到缓存中去取就行了，而缓存的速度要比内存快很多
这里要特别指出的是：
1.因为缓存只是内存中少部分数据的复制品，所以CPU到缓存中寻找数据时，也会出现找不到的情况（因为这些数据没有从内存复制到缓存中去），这时CPU还是会到内存中去找数据，这样系统的速度就慢下来了，不过CPU会把这些数据复制到缓存中去，以便下一次不要再到内存中去取。
2.因为随着时间的变化，被访问得最频繁的数据不是一成不变的，也就是说，刚才还不频繁的数据，此时已经需要被频繁的访问，刚才还是最频繁的数据，现在又不频繁了，所以说缓存中的数据要经常按照一定的算法来更换，这样才能保证缓存中的数据是被访问最频繁的
3.关于一级缓存和二级缓存
为了分清这两个概念，我们先了解一下RAM
ram和ROM相对的，RAM是掉电以后，其中才信息就消失那一种，ROM在掉电以后信息也不会消失那一种
RAM又分两种，
一种是静态RAM，SRAM；一种是动态RAM，DRAM。前者的存储速度要比后者快得多，我们现在使用的内存一般都是动态RAM。
有的菜鸟就说了，为了增加系统的速度，把缓存扩大不就行了吗，扩大的越大，缓存的数据越多，系统不就越快了吗
缓存通常都是静态RAM，速度是非常的快，
但是静态RAM集成度低（存储相同的数据，静态RAM的体积是动态RAM的6倍），
价格高（同容量的静态RAM是动态RAM的四倍），
由此可见，扩大静态RAM作为缓存是一个非常愚蠢的行为，
但是为了提高系统的性能和速度，我们必须要扩大缓存，
这样就有了一个折中的方法，不扩大原来的静态RAM缓存，而是增加一些高速动态RAM做为缓存，
这些高速动态RAM速度要比常规动态RAM快，但比原来的静态RAM缓存慢，
我们把原来的静态ram缓存叫一级缓存，而把后来增加的动态RAM叫二级缓存。
一级缓存和二级缓存中的内容都是内存中访问频率高的数据的复制品（映射），它们的存在都是为了减少高速CPU对慢速内存的访问。
通常CPU找数据或指令的顺序是：先到一级缓存中找，找不到再到二级缓存中找，如果还找不到就只有到内存中找了
㈤ linux内核物理内存管理有哪些常用算法 lru slab
采用伙伴算法分配内存时，每次至少分配一个页面。但当请求分配的内存大小为几十个字节或几百个字节时应该如何处理？如何在一个页面中分配小的内存区，小内存区的分配所产生的内碎片又如何解决？
Linux2.0采用的解决办法是建立了13个空闲区链表，它们的大小从32字节到132056字节。从Linux2.2开始，MM的开发者采用了一种叫做slab的分配模式，该模式早在1994年就被开发出来，用于Sun Microsystem Solaris 2.4操作系统中。Slab的提出主要是基于以下考虑：
· 内核对内存区的分配取决于所存放数据的类型。例如，当给用户态进程分配页面时，内核调用get_free_page()函数，并用0填充这个页面。 而给内核的数据结构分配页面时，事情没有这么简单，例如，要对数据结构所在的内存进行初始化、在不用时要收回它们所占用的内存。因此，Slab中引入了对象这个概念，所谓对象就是存放一组数据结构的内存区，其方法就是构造或析构函数，构造函数用于初始化数据结构所在的内存区，而析构函数收回相应的内存区。但为了便于理解，你也可以把对象直接看作内核的数据结构。为了避免重复初始化对象，Slab分配模式并不丢弃已分配的对象，而是释放但把它们依然保留在内存中。当以后又要请求分配同一对象时，就可以从内存获取而不用进行初始化，这是在Solaris 中引入Slab的基本思想。
实际上，Linux中对Slab分配模式有所改进，它对内存区的处理并不需要进行初始化或回收。出于效率的考虑，Linux并不调用对象的构造或析构函数，而是把指向这两个函数的指针都置为空。Linux中引入Slab的主要目的是为了减少对伙伴算法的调用次数。
· 实际上，内核经常反复使用某一内存区。例如，只要内核创建一个新的进程，就要为该进程相关的数据结构（task_struct、打开文件对象等）分配内存区。当进程结束时，收回这些内存区。因为进程的创建和撤销非常频繁，因此，Linux的早期版本把大量的时间花费在反复分配或回收这些内存区上。从Linux2.2开始，把那些频繁使用的页面保存在高速缓存中并重新使用。
· 可以根据对内存区的使用频率来对它分类。对于预期频繁使用的内存区，可以创建一组特定大小的专用缓冲区进行处理，以避免内碎片的产生。对于较少使用的内存区，可以创建一组通用缓冲区（如Linux2.0中所使用的2的幂次方）来处理，即使这种处理模式产生碎片，也对整个系统的性能影响不大。
· 硬件高速缓存的使用，又为尽量减少对伙伴算法的调用提供了另一个理由，因为对伙伴算法的每次调用都会“弄脏”硬件高速缓存，因此，这就增加了对内存的平均访问次数。
Slab分配模式把对象分组放进缓冲区（尽管英文中使用了Cache这个词，但实际上指的是内存中的区域，而不是指硬件高速缓存）。因为缓冲区的组织和管理与硬件高速缓存的命中率密切相关，因此，Slab缓冲区并非由各个对象直接构成，而是由一连串的“大块（Slab）”构成，而每个大块中则包含了若干个同种类型的对象，这些对象或已被分配，或空闲，如图6.12所示。一般而言，对象分两种，一种是大对象，一种是小对象。所谓小对象，是指在一个页面中可以容纳下好几个对象的那种。例如，一个inode结构大约占300多个字节，因此，一个页面中可以容纳8个以上的inode结构，因此，inode结构就为小对象。Linux内核中把小于512字节的对象叫做小对象。
㈥ 最佳页面淘汰算法是怎样计算的
<1> 先进先出调度算法
先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。
<2>最近最少调度算法
先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。
<3>最近最不常用调度算法
由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由硬件或操作系统自动定时清零。
（2）缺页调度次数和缺页中断率、缺页置换率计算
缺页中断次数是缺页时发出缺页中断的次数。
缺页中断率=缺页中断次数/总的页面引用次数*100%
缺页调度次数是调入新页时需要进行页面调度的次数
缺页置换率=缺页调度次数/总的页面引用次数*100%
㈦ 页面淘汰算法
LRU（2个块）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 3 3 2 2 5 5 2 2 2 2 7 7 3 3 1 1 3 3
2 2 4 4 1 1 6 6 1 1 3 3 6 6 2 2 2 2 6
缺页中断18次
LRU（4个块）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 1 1 6 6 6 6 6 6 6
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 5 5 5 5 5 3 3 3 3 3 3 3 3 3
4 4 4 4 6 6 6 6 6 7 7 7 7 1 1 1 1
缺页中断次数10次
FIFO（2个块）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 3 3 6 6 2 2 2 3 3
2 2 4 4 1 1 6 6 1 1 2 7 7 3 3 1 1 1 6
缺页中断次数18次
FIFO（4个块）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 5 5 5 5 5 3 3 3 3 3 1 1 1 1
2 2 2 2 2 2 6 6 6 6 6 7 7 7 7 7 7 3 7
3 3 3 3 3 3 2 2 2 2 2 6 6 6 6 6 6 6
4 4 4 4 4 4 1 1 1 1 1 1 2 2 2 2 2
缺页中断次数：14次
㈧ CACHE替换算法有哪几种，分别简要说明
其代表算法有：①Hybrid算法：算法对Cache中的每一个对象赋予一个效用函数，将效用最小的对象替换出Cache；②LowestRelativeValue算法：将效用值最低的对象替换出Cache；③（LCNR）算法：该算法使用一个关于文档访问频次、传输时间和大小的推理函数来确定替换文档；④Bolot等人提出了一种基于文档传输时间代价、大小、和上次访问时间的权重推理函数来确定文档替换；⑤SizeAdjustLRU（SLRU）算法：对缓存的对象按代价与大小的比率进行排序，并选取比率最小的对象进行替换
扩展知识:
Cache是一种根据程序局部性原则，通过小容量速度快的存储器缓存部分数据，以减少处理器对慢速大容量存储器的访问次数，从而提升处理器取指效率的机制。Cache替换算法是指当Cache缺失发生后，Cache按某种机制选中高速缓存中的某个地址进行数据更新。Cache替换算法对Cache的命中率有较大的影响。目前主流的Cache替换算法有伪随机、先进先出(FIFO——First In First Out)和最近最少使用(LRU——Least Recently Used)等。相较于伪随机和先进先出算法，LRU算法更符合程序局部性原则(当前执行的程序代码，在不久后会再次访问该代码段)，Cache的命中率更高，但其硬件资源消耗非常大。
传统的LRU算法对Cache的每一路进行统计，在需要替换时，将最近最少被使用的那一路替换。由于传统LRU算法的数据使用频率统计为向上计数，故其计数器计数位宽较大，且需要额外的机制来处理计数溢出的情况。
㈨ 如何通过用数据挖掘技术来分析Web网站日志
1、数据预处理阶段根据挖掘的目的，对原始Web日志文件中的数据进行提取、分解、合并、最后转换为用户会话文件。该阶段是Web访问信息挖掘最关键的阶段，数据预处理包括:关于用户访问信息的预处理、关于内容和结构的预处理。
2、会话识别阶段该阶段本是属于数据预处理阶段中的一部分，这里将其划分成单独的一个阶段，是因为把用户会话文件划分成的一组组用户会话序列将直接用于挖掘算法，它的精准度直接决定了挖掘结果的好坏，是挖掘过程中最重要的阶段。
3、模式发现阶段模式发现是运用各种方法和技术从Web日志数据中挖掘和发现用户使用Web的各种潜在的规律和模式。模式发现使用的算法和方法不仅仅来自数据挖掘领域，还包括机器学习、统计学和模式识别等其他专业领域。
模式发现的主要技术有：统计分析（statistical analysis）、关联规则（association rules）、聚类（clustering）、归类（classification）、序列模式（sequential patterns）、依赖关系（dependency）。
（1）统计分析（statistical analysis）：常用的统计技术有：贝叶斯定理、预测回归、对数回归、对数-线性回归等。可用来分析网页的访问频率，网页的访问时间、访问路径。可用于系统性能分析、发现安全漏洞、为网站修改、市场决策提供支持。
（2）关联规则（association rules）：关联规则是最基本的挖掘技术，同时也是WUM最常用的方法。在WUM中常常用在被访问的网页中，这有利于优化网站组织、网站设计者、网站内容管理者和市场分析，通过市场分析可以知道哪些商品被频繁购买，哪些顾客是潜在顾客。
（3）聚类（clustering）：聚类技术是在海量数据中寻找彼此相似对象组，这些数据基于距离函数求出对象组之间的相似度。在WUM中可以把具有相似模式的用户分成组，可以用于电子商务中市场分片和为用户提供个性化服务。
（4）归类（classification）：归类技术主要用途是将用户资料归入某一特定类中，它与机器学习关系很紧密。可以用的技术有：决策树（decision tree）、K-最近邻居、Naïve Bayesian classifiers、支持向量机（support vector machines）。
（5）序列模式（sequential patterns）：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即子序列在序列集中的出现频率不低于用户指定的最小支持度阈值。
（6）依赖关系（dependency）：一个依赖关系存在于两个元素之间，如果一个元素A的值可以推出另一个元素B的值，则B依赖于A。
4、模式分析阶段模式分析是Web使用挖掘最后一步，主要目的是过滤模式发现阶段产生的规则和模式，去除那些无用的模式，并把发现的模式通过一定的方法直观的表现出来。由于Web使用挖掘在大多数情况下属于无偏向学习，有可能挖掘出所有的模式和规则，所以不能排除其中有些模式是常识性的，普通的或最终用户不感兴趣的，故必须采用模式分析的方法使得挖掘出来的规则和知识具有可读性和最终可理解性。常见的模式分析方法有图形和可视化技术、数据库查询机制、数理统计和可用性分析等。
㈩ 页面置换算法的常见的置换算法
最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。
这种算法只是在按线性顺序访问地址空间 时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。
FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。
FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。
LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。
LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：
1.计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做， 不仅要查页表，而且当页表改变时（因CPU调度）要 维护这个页表中的时间，还要考虑到时钟值溢出的问题。
2.栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。
因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。
一种LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在之前最近一段时间里它未被访问过。
4）Clock置换算法（LRU算法的近似实现）
5）最少使用（LFU）置换算法
在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在之前时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度，例如100 ns，在1 ms时间内可能对某页面连续访 问成千上万次，因此，通常不能直接利用计数器来记录某页被访问的次数，而是采用移位寄存器方式。每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间(例如100 ns)右移一次。这样，在最近一段时间使用最少的页面将是∑Ri最小的页。
LFU置换算法的页面访问图与LRU置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现LRU算法，又可实现LFU算法。应该指出，LFU算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10 000次是等效的。
6）工作集算法
7）工作集时钟算法
8）老化算法（非常类似LRU的有效算法）
9）NRU(最近未使用）算法
10）第二次机会算法
第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，检查它的访问位。如果是 0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。
第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个 存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。
