精华内容
下载资源
问答
  • 针对LIRS 算法结构复杂、适应性差的不足,提出一种改进的自适应时钟算法。在LIRS 算法基础上借鉴Clock 算法思想,简化算法组织结构,加强对不同数据访问模式的适应性和捕获高频数据的能力。实验结果证明,与LIRS ...
  • 时钟算法

    千次阅读 2017-07-31 08:51:38
    时钟算法计算机内存中,缓存是一种稀缺资源,虽然运行速度非常快,但是一个合理的算法能更好的提升性能.例如一个循环,在csapp一书中提到,是否合理的使用缓存的区域性.能影响两倍的性能.今天重点在页面置换的时钟算法不...

    时钟算法

    计算机内存中,缓存是一种稀缺资源,虽然运行速度非常快,但是一个合理的算法能更好的提升性能.例如一个循环,在csapp一书中提到,是否合理的使用缓存的区域性.能影响两倍的性能.今天重点在页面置换的时钟算法不在这里过多描述.有兴趣的可以自行阅读,这个缓存区域性问题,在csapp中是很重视的.

    算法数据结构描述

    它就像一个时钟(顾名思义),但是却是一个只有时指针的时钟.刻度也是,没有分秒.但是这个时钟的移动却是为了寻找需要被替换的页面.
    时钟算法
    这里还有一个r 和w分别指,读写这个页面,它的写入我是没有做的,因为毕竟是描述这个算法.

    工作方式

    使用链表或者数组,但是我这里使用了链表.双向的.组成一个循环链表.每次寻找满足条件,r为为零就代表没有读过,也就是未使用,抛弃这个页面.如果为1就将这个页面置0,并指针向下移动.重复上述操作.直到找到满足条件.

    结构体

    typedef struct NODE {  //页面
        char read;
        char write;
        struct NODE *left;
        struct NODE *right;
        int date;
    }node;
    typedef struct CLOCK {     //时钟结构体sd
        int count; //时钟大小
        node * ptr;  //指针
        node *root;
    }clock;

    全部实现

    #include<stdio.h>
    #include<stdlib.h>
    #include<String.h>
    typedef struct NODE {  //页面
        char read;
        char write;
        struct NODE *left;
        struct NODE *right;
        int date;
    }node;
    typedef struct CLOCK {     //时钟结构体sd
        int count; //时钟大小
        node * ptr;  //指针
        node *root;
    }clock;
    
    void * Calloc(unsigned count , unsigned size);
    node * readNode(node * n);
    node *createnode(int size);
    clock * init(int size);
    node * position(node *root);
    void moveNode(node * newNode, clock * cl);
    void print(clock  *cl);
    node * newNode(int date);
    
    //包装器
    void *Calloc(unsigned count, unsigned size) 
    {
        void *ptr = NULL;
        if ((ptr = calloc(count, size)) == NULL) {
            fprintf(stderr, "Calloc error!\n");
            exit(-1);
        }
        else {
            return ptr;
        }
    }
    //通過驗證
    node *createnode(int size)
    {
        node *root = NULL;
        node *ptr = NULL;
        int  i = 0;
        root = (node*)Calloc(1, sizeof(node));
        root->date = 0;
        ptr = root;
        for (i = 1; i < size; i++) {
            ptr->right = (node*)Calloc(1, sizeof(node));
            ptr->right->left = ptr;
            ptr->date = i;
            ptr = ptr->right;
        }
        ptr->right = root;
        root->left = ptr;
        return root->left;
    }
    
    //初始化时钟
    clock * init(int size)   //通過
    {
        clock * root = (clock*)Calloc(1, sizeof(clock));
        root->count = size;
        root->root = createnode(size);
        root->ptr = root->root;
        return root;
    }
    //定位到符合条件的地方
    node * position(node *root)
    {
        node *tmp = root;
        while (1) {
            if (tmp->read == 0) {
                return tmp;
            }
            else {
                tmp->read = 0;
            }
            tmp = tmp->right;
        }
    
    }
    
    //页面置换 
    void moveNode(node * new_node, clock * cl)
    {
        node *ptr = position(cl->ptr);
        new_node->left = ptr->left;
        new_node->right = ptr->right;
        ptr->right->left = new_node;
        ptr->left->right = new_node;
        cl->ptr = new_node->right;
        if (ptr == cl->root) {
            cl->root = new_node;
        }
        free(ptr);
    }
    //遍历时钟
    void print(clock  *cl) 
    {   
        node *ptr = cl->root;
        node *ptrEnd = cl->root;
        printf("%d \n", ptr->date);
        ptr = ptr->right;
        while (ptr != ptrEnd) {
            printf("%d \n", ptr->date);
            ptr = ptr->right;
        }
    }
    //读数据
    node * readNode(node * n)
    {
        n->read = 1;
        return n;
    }
    //创建一个时钟节点
    node * newNode(int date) 
    {
        node * tmp = (node*)Calloc(1, sizeof(node));
        tmp->date = date;
        return tmp;
    }
    int main(void)
    {
        clock * cl = init(10);
        node * tmp1 = newNode(20);
        node * tmp2 = newNode(21);
        node * tmp3 = newNode(22);
        node * tmp4 = newNode(23);
        node * tmp5 = newNode(24);
        node * tmp6 = newNode(25);
        node * tmp7 = newNode(26);
        node * tmp8 = newNode(27);
        print(cl);
        moveNode(tmp1,cl);
        printf("------------------------\n");
        print(cl);
        moveNode(tmp2, cl);
        printf("------------------------\n");
        print(cl);
        moveNode(tmp3, cl);
        printf("------------------------\n");
        print(cl);
        moveNode(tmp4, cl);
        printf("------------------------\n");
        print(cl);
        moveNode(tmp5, cl);
        printf("------------------------\n");
        print(cl);
        moveNode(tmp6, cl);
        printf("------------------------\n");
        print(cl);
        moveNode(tmp7, cl);
        moveNode(tmp8, cl);
        printf("------------------------\n");
        print(cl);
        system("pause");
        return 0;
    }

    这里因为篇幅已经很长了就不上运行结果.如果发现问题请帮忙指出.编写环境windows10 vs2017 如果是linux环境需要替换头文件,可以man查看.

    展开全文
  • 改进时钟算法

    2020-05-02 18:16:23
    改进时钟算法 // C语言实现操作系统改进时钟式淘汰算法 #include <stdio.h> #include <stdlib.h> #include <string.h> #define length 10//定义数组长度 typedef struct Node {//生成数据节点 ...

    改进时钟算法

    // C语言实现操作系统改进时钟式淘汰算法
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define length 10//定义数组长度
    
    typedef struct Node {//生成数据节点
        int index;
        int list;
        int A;//访问标志
        int M;//修改标志
    } dataNode;
    
    dataNode *initList(dataNode node[]) {//生成随机访问序列
        for (int i = 0; i < length; ++i) {
            int randNumber = rand() % 9 + 1;
            int randNumber2 = rand() % 2;
            int randNumber3 = rand() % 2;
            node[i].index = i;
            node[i].list = randNumber;
            node[i].A = randNumber2;
            node[i].M = randNumber3;
        }
        return node;
    }
    
    void NRU(dataNode node[], int bwoList[]) {//最近最久未使用淘汰算法核心
    
        int count = 0;//设置全部为0时推出条件
        int index = 1;
        while (count <= length) {
            int countLoss = 0;//统计缺页次数
            int cou = 0;//存储淘汰有序列
            printf("第%d次淘汰序列为:", index++);
            for (int i = 0; i < length; ++i) {
                if (node[i].A == 0) {
                    if (node[i].M == 0) {
                        countLoss++;
                        count++;
                        printf("%d ", node[i].list);
                        bwoList[i - cou] = node[i].list;
                    } else {
                        node[i].M = 0;
                    }
                } else {
                    node[i].A = 0;
                }
            }
            printf("\n");
            printf("----淘汰率为:%.2lf%%\n", (1.0 * countLoss / length) * 100);
        }
    
    }
    
    
    int main() {
        printf("\t欢迎来到简单时钟式淘汰算法\n");
        int bwoList[length];//淘汰序列
        memset(bwoList, -1, sizeof(bwoList));
        dataNode node[length];//生成时钟访问结构体
        initList(node);
        printf("----随机生成的相关数据为:\n");
        for (int j = 0; j < length; ++j) {
            if (j < length - 1)
                printf("%d %d %d %d", node[j].index, node[j].list, node[j].A,node[j].M);
            else
                printf("%d %d %d %d", node[j].index, node[j].list, node[j].A,node[j].M);
            printf("\n");
    
        }
        NRU(node, bwoList);
    
    }
    

    在这里插入图片描述

    展开全文
  • 本实验使用一下算法 使用rand()函数随机产生页面号,用数组装入页面号,模拟页面调入内存中发生页面置换的过程。 整个过程,都是使用数组来实现每个算法,模拟队列,模拟堆栈的功能,实现每一个置换算法。 页面...
  • NULL 博文链接:https://comsci.iteye.com/blog/2255684
  • 实现时钟算法

    2014-01-08 11:03:16
    用C#实现时钟,用时钟界面,包括分针,失真和秒针,使用容器存放各种按钮控件,实现封装
  • 向量时钟算法正是设计出来解决因果关系问题的。 我们来回顾一下因果问题,在实际日常的网页行为当中,部分行为存在因果关系。比方说知乎里面回答问题,显然得先有一个同学提出问题,然后才能有各路大V谢邀解答问题...

    今天的文章来聊聊向量时钟,在前文介绍分布式系统一致性的时候,曾经介绍过,在弱一致性模型当中会有一个因果性的问题。向量时钟算法正是设计出来解决因果关系问题的。


    我们来回顾一下因果问题,在实际日常的网页行为当中,部分行为存在因果关系。比方说知乎里面回答问题,显然得先有一个同学提出问题,然后才能有各路大V谢邀解答问题。但是由于是分布式系统,有可能问题和回答并不是存放在同一台机器,导致有可能它们更新的顺序不一致,所以就有可能会出现用户在访问知乎的时候,发现自己关注的大V回答了某个问题,但是点进去问题却是空的。这种幽灵情况不是灵异事件,只是单纯的分布式系统设计没过关,没有考虑因果问题。


    有的同学可以会说,这个不难啊,我们加入时间戳啊。时间戳的确可以解决一部分问题,但是并不能解决所有问题。有了时间戳之后,我们可以获得事件发生的时间,但是仍然不知道不同的数据之间的因果关系。由于分布式系统存在延迟,也不能简单地通过时间戳来做过滤或者筛选。不过,虽然单纯的时间戳不行,但已经非常接近了。


    我们日常生活当中用事件发生的时间来反应事物发生的顺序,我们说的先后顺序,其实是以客观上的时间作为参考系参考得到的结果。问题来了,我们能不能找到或者构造出其他的参考系来反应事物发生的顺序呢?


    当然是可以的,不然也没有这篇文章了,这就是大名鼎鼎的逻辑时钟算法。多说一句,逻辑时钟算法和许多其他分布式算法一样,同样源于大神Lamport的发明。


    逻辑时钟


    我们还用之前的例子来思考一下,一个人在知乎提交了问题,另一个人回答了问题,这是两个事件。我们第一反应自然是通过两个事件发生的时间来反应因果顺序,但我们仔细分析一下这个场景。后面那个人既然能回答问题,说明他一定是看到了问题。也就是说回答问题和看到问题之间发生了交互,所以很自然地可以想到,我们是不是可以用两个系统或者是两个事件之间有没有发生过信息交互来反应因果顺序呢?


    于是基于这个思想,Lamport大神提出了逻辑时钟的概念。逻辑时钟概念的核心就是刚才我们说的,两个事件之间建立因果关系的前提是,两个事件之间发生过信息传递


    我们梳理一下可能发生的事件的种类,可以分成三种。第一种是发生在某个节点内部,也就是说没有和其他任何节点发生联系。第二种是发送事件,是事件的发送方。第三种是接收事件,和第二种对应,是事件的接收方。明确了这三点之后,我们就可以用时间戳来表示这三种情况了。首先,我们假设每个节点内部都会维护一个时间戳,记录当下节点的状态。


    针对上面说是三种时序关系呢,我们设定三种策略。


    首先是内部事件,对于节点内部发生事件呢,很简单,我们只需要将它的时间戳增大1,表示发生过了某件事情。


    其次是发送事件,节点内部的时间戳自增1,并且在发送消息当中加上这个时间戳。


    最后是接收事件,由于会额外接收到一个时间戳,所以我们需要利用这个时间戳来更新节点内部的时间戳。更新的方法也很简单,假设节点内部的时间戳是 t t t,跟着消息传递而来的时间戳是 t ′ t' t, 那么: t n e w = m a x ( t + 1 , t ′ ) t_{new} = max(t + 1, t') tnew=max(t+1,t)


    我们分析一下上面这个关系,假设当下有事件A和B,如果事件A是事件B发生的前提。那么显然事件A的时间戳小于事件B。如果反过来,事件A的时间戳小于B,能说明事件A是事件B的前提吗?并不能,所以时间戳较小是因果关系的必要条件,但不是充分条件


    由于会存在多个节点或者进程时间戳相等的情况,所以我们把进程id也作为比较的银子。我们用C表示一个事件的时间戳,P表示事件的进程pid。如果事件A排在事件B前面,只有两种可能:


    1. C ( A ) < C ( B ) C(A) < C(B) C(A)<C(B)
    2. C ( A ) = C ( B ) , P ( A ) < P ( B ) C(A) = C(B), P(A) < P(B) C(A)=C(B),P(A)<P(B)

    我们来看一个例子:

    上图当中有A、B和C三个进程,其中P(A) < P(B) < P©。图中每一个箭头都代表传递的消息


    我们根据重新定义的时序关系,可以得到这些点的先后顺序是:


    C1⇒B1⇒B2⇒A1⇒B3⇒A2⇒C2⇒B4⇒C3⇒A3⇒B5⇒C4⇒C5⇒A4


    如果仔细观察这条链的话会发现它并不能真实反映事件发生的顺序,会存在不公平的情况。但至少因果关系可以保证。


    以上这个算法被称为是逻辑时钟算法,它相当于重新定义了一个逻辑上的时间来代替真实物理世界的时间。由于它是Lamport大神提出的,所以也被称为是Lamport逻辑时钟算法


    向量时钟


    在上面的文章当中我们也分析了,逻辑时钟算法有一个问题是虽然保证了因果顺序,但也牺牲了公平。比如上图当中B3和A2发生在同一时间,但是B3排在A2的前面。也就是说我们通过比较 C ( A ) C(A) C(A) C ( B ) C(B) C(B)无法得出真实的发生顺序。


    为了解决这个问题,大神们在Lamport的逻辑时钟上做了改进,提出了向量时钟算法


    向量时钟和逻辑时钟的原理几乎一样,只不过对于每个节点或者进程而言,它维护的不再是一个单个的时间戳,而是一个时间戳构成的向量。向量的维度就等于进程的数量,也就是说每个进程不止记录自己的时间戳,而且还会记录其他进程的时间戳,这些时间戳组合在一起,就构成了一个时间向量


    在事件的处理上,向量时钟算法和逻辑时钟基本一致。


    1. 在进程i发生事件(接收、发送或者是内部事件)的时候, C i [ i ] + = 1 C_i[i] += 1 Ci[i]+=1,这时候C是一个时间戳向量,i是进程i的下标。
    2. 当进程i发送消息的时候,会将消息和自己的时钟向量一同发出。
    3. 当进程i收到进程j发送来的消息时,会根据一起发送来的时钟向量更新自己的时钟向量: C i [ k ] = m a x ( C i [ k ] , C j [ k ] ) , k = 1 , 2 , ⋯   , n C_i[k] = max(C_i[k], C_j[k]), k = 1, 2, \cdots, n Ci[k]=max(Ci[k],Cj[k]),k=1,2,,n

    同样,由于单个时间戳换成了向量时钟,所以我们判断因果顺序的方式也需要变化。在向量时钟算法当中,我们定义如果事件A在事件B之前,那么需要满足两个条件:


    1. 对于所有的下标K,都有 C A [ k ] ≤ C B [ k ] C_A[k] \leq C_B[k] CA[k]CB[k]
    2. 存在下标 k 0 k_0 k0,使得 C A [ k 0 ] < C B [ k 0 ] C_A[k_0] < C_B[k_0] CA[k0]<CB[k0]

    也就是说至少需要一个维度存在严格小于,其他维度全部小于等于,才可以看做是因果关系。原因也很简单,因为如果存在消息传递,那么至少有一个维度会带来增加。如果两个事件的向量时钟相等,说明两者是没有发生过信息传递的,自然也就不符合我们定义的因果关系。


    我们回顾一下之前的例子,将节点改写成向量时钟之后,得到的结果如下图:



    将逻辑时钟优化成向量时钟之后,就可以严格判断因果关系了。如果两个节点的时钟向量没有大小关系,那么可以说明这两个事件之间没有联系。


    实际应用


    和我们之前介绍的一样,向量时钟算法主要用在分布式系统的因果关系的检测上。而因果关系之所以需要检测,往往是因为我们面临多个副本同时更新,我们需要检测这些副本的冲突


    我们来一起看一个例子,这个例子是亚马逊的Dynamo系统, 它是一个KV的存储系统,类似于redis,可以简单理解成缓存。为了高可用,Dynamo保证即使在出现网络分区或者机器宕机的时候,仍然可读可写。但是这会导致一个问题,当网络分区恢复之后,多个副本的数据可能会出现不一致的情况,这个时候我们就需要通过向量时钟算法来检测冲突了。



    假设一开始的时候客户端W创建了一个记录X,这个记录是由机器 S x S_x Sx来负责的。那么则形成了数据 D 1 D_1 D1和它对应的向量时钟 [ S x , 1 ] [S_x, 1] [Sx,1]


    之后,客户端继续更新记录X,同样由机器 S x S_x Sx执行,形成了新数据 D 2 D_2 D2,它的向量时钟变成 [ S x , 2 ] [S_x, 2] [Sx,2],它和 [ S x , 1 ] [S_x, 1] [Sx,1]存在因果关系。所以我们可以知道 D 2 D_2 D2是最新的数据。


    再之后,客户端继续更新X,这次由 S y S_y Sy执行,同样,可以知道操作结束之后它的向量时钟为 [ S x , 2 ] , [ S y , 1 ] [S_x, 2], [S_y, 1] [Sx,2],[Sy,1]


    与此同时,另一个客户端读入了 D 2 D_2 D2之后,在机器 S z S_z Sz上更新产生了 D 4 D_4 D4,此时的向量时钟是 [ S x , 2 ] , [ S z , 1 ] [S_x, 2], [S_z, 1] [Sx,2],[Sz,1]


    我们来分析一下,如果这时候有客户端同时读到 D 2 D_2 D2 D 3 D_3 D3,那么通过向量时钟可以判断出来, D 3 D_3 D3是最新的数据。如果同时读到 D 3 D_3 D3 D 4 D_4 D4,由于这两者的向量时钟并没有因果关系,所以无法判断谁是最新的数据,这就产生了冲突


    但是必须要说明的是,向量时钟算法只能检测冲突,并不能解决冲突,冲突需要客户端自己解决。如果客户端判断,决定应该以 S x S_x Sx的节点为准,那么最后的数据就会变成 D 5 D_5 D5,此时的向量时钟为 [ S x , 3 ] , [ S y , 1 ] , [ S z , 1 ] [S_x, 3], [S_y, 1], [S_z, 1] [Sx,3],[Sy,1],[Sz,1]


    除了知乎之外,其实还有很多场景下的一致性问题都需要考虑因果关系。因此向量时钟算法在分布式领域可以说是鼎鼎大名,使用非常广泛。在刚听到这个名字的时候,往往会觉得它非常晦涩难懂,但实际深入了解之后,会发现其实并不困难,反而非常有趣,这也算是学习的乐趣之一吧。


    今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

    展开全文
  • C语言实现改进clock时钟算法

    千次阅读 2019-12-08 13:14:57
    实验作业,欢迎大神指教 clock_pro.c /* * clock_pro.c * * Created on: 2019年12月6日 * Author: zyli */ #include<stdio.h> #include<stdlib.h> #include<stdbool.h>...int blo...

    实验作业,欢迎大神指教

    下图是测试数据及结果
    测试数据及结果
    clock_pro.c

    /*
     * clock_pro.c
     *
     *  Created on: 2019年12月6日
     *      Author: zyli
     */
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    #define Maxblocks 3
    int blocks[Maxblocks] = {};
    int access[Maxblocks] = {};
    int modify[Maxblocks] = {};
    int pages_in_blocks = 0;
    int is_modified = 0;
    int aimed_i=-1;
    bool is_aimed(int pn)
    {
    	aimed_i=-1;
    	for(int i=0;i<pages_in_blocks;i++)
    	{
    		if(blocks[i]==pn)
    		{
    			aimed_i=i;
    			return true;
    		}
    	}
    	return false;
    }
    void loop()
    {
    	int taotaip=0;
    	for(int j=0;j<2;j++)
    	{
    		for(int i=0;i<pages_in_blocks;i++)
    		{
    			if(!access[i]&&!modify[i])
    			{
    				taotaip=blocks[i];
    				for(;i<pages_in_blocks;i++)
    				{blocks[i]=blocks[i+1];access[i]=access[i+1];modify[i]=modify[i+1];}
    				if(!j) printf("第一圈有(0,0)的,是页面  %d,淘汰!把新页面放入队尾\n",taotaip);
    				else printf("第三圈有(0,0)的,是页面  %d,淘汰!把新页面放入队尾\n",taotaip);
    				return;
    			}
    		}
    		if(!j) printf("第一圈没有(0,0)的,接着找(0,1)的\n");
    		else printf("第三圈没有(0,0)的,即上一圈(第二圈)全为(0,1)\n");
    		for(int i=0;i<pages_in_blocks;i++)
    		{
    			if(!(!access[i]&&modify[i]))
    			{
    				access[i]=0;
    			}
    			else
    			{
    				taotaip=blocks[i];
    				for(;i<pages_in_blocks;i++)
    				{blocks[i]=blocks[i+1];access[i]=access[i+1];modify[i]=modify[i+1];}
    				if(!j) printf("第二圈有(0,1)的,是页面  %d,淘汰!第一个(0,1)之前的页面访问位全部置为0,并把新页面放入队尾\n",taotaip);
    				else printf("第四圈必有(0,1)的,将第一个(0,1)的,即页面%d淘汰!把新页面放入队尾\n",taotaip);
    				return;
    
    			}
    		}
    		printf("第二圈没有(0,1)的,但把所有访问位置为0了,接着第三圈找(0,0)的\n");
    	}
    }
    void clock_pro(int pn)
    {
    	if(pages_in_blocks<Maxblocks)
    		{
    			if(is_aimed(pn))
    			{
    				access[aimed_i]=1;
    				printf("输入页面是否被修改%d	(0/1)\n",pn);
    				scanf("%d",&is_modified);
    				if(is_modified) modify[aimed_i]=1;
    			}
    			else
    			{
    				blocks[pages_in_blocks]=pn;
    				access[pages_in_blocks]=1;
    				modify[pages_in_blocks]=0;
    				pages_in_blocks++;
    			}
    		}
    	else
    	{
    		if(is_aimed(pn))
    		{
    			access[aimed_i]=1;
    			printf("输入页面是否被修改%d	(0/1)\n",pn);
    			scanf("%d",&is_modified);
    			if(is_modified) modify[aimed_i]=1;
    		}
    		else
    		{
    			loop();
    			blocks[Maxblocks-1]=pn;
    			access[Maxblocks-1]=1;
    			modify[Maxblocks-1]=0;
    		}
    	}
    }
    void print_blocks()
    {
    	int cato=0;
    	printf("此时内存块里状态为:\n");
    	for(int i=0;i<pages_in_blocks;i++)
    	{
    		if(!access[i] && !modify[i]) cato=1;
    		if(!access[i] &&  modify[i]) cato=2;
    		if( access[i] && !modify[i]) cato=3;
    		if( access[i] &&  modify[i]) cato=4;
    		printf("%d	%d	%d  ,对应第%d类型页面\n",blocks[i],access[i],modify[i],cato);
    	}
    	printf("\n");
    
    }
    int main()
    {
    	for(int i=0;i<Maxblocks;i++){ blocks[i]=-1;access[i]=0;modify[i]=0;}
    	int n=0;
    		while(n>=0)
    		{
    			is_modified=0;
    			printf("输入此时进程对哪个页面访问,输入-1结束程序\n");
    			scanf("%d",&n);
    			if(n>=0)
    			{
    				clock_pro(n);
    				print_blocks();
    			}
    		}
    		system("pause");
    		return 0;
    	return 0;
    }
    
    
    
    
    展开全文
  • 时钟页面置换算法

    2021-03-10 02:59:45
    一、局部:时钟置换算法:1.最优置换算法:理论上的,预测最晚调用的页面。2.LRU算法,置换掉最久未使用的。一个链表。一个页面被调用的话,会被从链表中(它原本的位置)移动到链表首,而每次缺页,则会将链表尾部...
  • java 语言描述的时钟算法 比较简单 希望能对大家有些帮助
  • 工作集时钟页面置换算法

    千次阅读 2019-06-22 08:44:49
    工作集时钟页面置换算法是在工作集和时钟算法的基础上改进的,所以先看看什么是时钟算法: Clock置换算法 LRU算法的性能接近于OPT,但是实现起来比较困难,且开销大;FIFO算法实现简单,但性能差。所以操作系统的...
  • 可以体现Clock算法和LRU算法的的思想,用于操作系统的课程实训。 任务要求 从置换算法中任选1种(OPT、LRU、Clock); 建立页表 设计的输入数据要能体现算法的思想 模拟缺页中断过程; 求出各置换算法中的缺页...
  • 操作系统时钟(CLOCK)置换算法

    万次阅读 多人点赞 2020-01-14 20:08:44
    时钟(CLOCK)置换算法流程 注意:红色为访问位,蓝色为内存数据 箭头处开始 第一步: 第一个页面走向为3,此时内存中没有数据,且访问位为0,于是将3放入内存,并修改访问位为1,指针下移,得到如下图 ...
  • 文章目录前言知识总览最佳置换算法(OPT)先进先出置换算法(FIFO)最近最久未使用置换算法(LRU)时钟置换算法(CLOCK)改进型的时钟置换算法知识回顾与重要考点 前言 此篇文章是我在B站学习时所做的笔记,大部分图片...
  • 时钟(CLOCK)置换算法

    万次阅读 多人点赞 2018-12-28 21:44:19
    当调入进程所请求的页面时,如果内存中已经没有空闲块了,则必须按照某种算法将内存中的若干页面淘汰至外存。用于选择淘汰页面的算法称为页面置换算法,置换算法的好坏,将直接影响到请求分页系统的性能。 FIFO置换...
  • 简单时钟置换: 装入页面:当前页面置为一,指针下跳。 命中页面:命中页面置为一,指针不动。...改进型时钟替换算法: 1:找(0,0) 2:找(0,1),并将扫描过的访问位置零 3:找(0,0) 4:找(0,1) ...
  • 背景:在内存不足的情况下,操作系统会将内存中暂时不需要使用的信息换出到外存,页面置换算法就是用于选择到底将哪个页面换出到外存的算法。 注意:页面置换算法的好坏是可以通过缺页率来体现的,一个好的页面置换...
  • 时钟页面置换算法就是一种近似 LRU 的算法实现,可以看作是对 FIFO 算法的改进。 Clock 页面置换算法 为什么需要 clock 算法? LRU算法的性能接近于OPT,但是实现起来比较困难,且开销大;FIFO算法实现简单,但性能...
  • 时钟置换算法---CLOCK5.改造型时钟置换算法 0.思维导图 1.最佳置换算法—OPT 2.先进先出置换算法—FIFO 3.最近最久未使用置换算法—LRU 4.时钟置换算法—CLOCK 5.改造型时钟置换算法 只需一轮: 需要...
  • 对于任何通信系统,都需要提供一个精确的同步时钟,所以时钟性能与精度是影响整个系统性能的一个重要方面
  • 根据geeksforgeeks页面所说,时钟策略指的是维护一个顺时针的时钟指针,并为每个页附加一个访问位。 文中展示了下图,图的上方是页号访问序列,绿色箭头是时钟指针指向的位置,每个小图下方的文字"Pf=1", "2nd ...
  • 页面置换算法 根据中国大学MOOC计算机操作系统(电子科技大学)而写. 如果自己要设计页面置换,要根据什么原则来设计?我们首先想到的是存储器的局部性原理(时间局部性、空间局部性) Page removed should be the ...
  • 向量时钟策略并没有给出解决版本,留给用户自己去解决,只是告诉你目前数据存在冲突。 http://blog.csdn.net/hellochenlu/article/details/53264544 NTP协议 https://www.zhihu.com/question/19994133 ...
  • vector clock向量时钟算法简介

    千次阅读 2016-11-21 21:26:32
    先说一下需要用到向量时钟的场景。我们在写数据时候,经常希望数据不要存储在单点。如db1,db2都可以同时提供写服务,并且都存有全量数据。而client不管是写哪一个db都不用担心数据写乱问题。但是现实场景中往往会...
  • 在存在随机有界时延的情况下,现有的许多一致性时钟同步算法的同步过程是发散的.在平均一致性时钟同步算法(ATS)的基础上,通过对偏斜和偏移同步过程进行分析,找出导致同步过程发散的原因.通过改变相对偏移估计的方法,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 72,897
精华内容 29,158
关键字:

时钟算法