Ywrby个人博客网站

区块链网络中矿池选择的演化博弈论文原文链接: Evolutionary Game for Mining Pool Selection in Blockchain Networks Abstract在基于工作量证明（POW）的区块链网络中，区块矿工参与解决加密难题的竞赛，以赢得发布（即挖掘）新区块的奖励。由于加密难题的显著难度，个体矿工倾向于加入矿池以确保稳定的利润。我们研究了区块链网络中矿池选择的动态，其中矿池可以选择任意块挖掘策略（补充）。我们将解谜的哈希率和区块传播延迟确定为决定挖矿竞争结果的两个主要因素。然后我们将个体矿工的策略演化建模为演化博弈。我们提供了两个池情况下池选择动力学中演化稳定性的理论分析。数值模拟支持我们的理论发现，并证明了一般情况下矿工策略演变的稳定性 Section1-Introduction公共区块链网络构建为覆盖点对点 (P2P) 网络，用于去中心化防篡改数据记录。中本聪共识协议 用于在利益角度上激励全节点（区块矿工）遵守区块链状态维护的“最长链规则”。遵循该协议，区块矿工将一组任意经过验证的交易打包成一个数据结构，称为候选“区块”，并将其广播到整个网络。 ...

生产者与消费者问题系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品就放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用（这里的产品可能是某种数据） 生产者和消费者共享一个初始为空，大小为n的缓冲区 只有缓冲区没满时，生产者才能将产品放入缓冲区，否则必须等待 只有缓冲区不空时，消费者才能从缓冲区取出产品，否则必须等待 缓冲区是临界资源，各进程必须互斥访问 PV操作题目常见方法信号量机制可以实现互斥，同步以及对一类资源的申请和释放 互斥：一般会设置初值为1的互斥信号量 同步：设置初值为0的同步信号量（实现一前一后） 资源的释放和申请：设置一个信号量，初始值即为资源数量（本质还是进程同步） PV操作题目分析步骤 关系分析，找出题目中描述的各个进程，分析它们之间的同步互斥关系 本题中，涉及以下几种进程同步，互斥关系 互斥关系：对于临界区的访问，必须互斥进行 同步关系：缓冲区满，生产者必须开始等待，直到消费者取走产品 同步关系：缓冲区空，消费者必须开始等待，直到生产者放入产品 整理思路，根据各进程的操作流程确定P，V操作的大致顺序 生产者每次要消耗一个空闲缓冲 ...

信号量机制实现进程互斥主要步骤 分析并发进程的关键活动，划定临界区（例如：对打印机等临界资源的访问就应放在临界区内） 设置互斥信号量，常命名为mutex，初值为1（因为一般情况下对临界区的访问同一时间只能存在一个进程） 在临界区之前执行P(mutex) 在临界区之后执行V(mutex) 示例12345678910111213141516semaphore mutex=1;P1(){ ... P(mutex) 临界区代码段... V(mutex) ...}P2(){ ... P(mutex) 临界区代码段... V(mutex) ...} 注意 对不同的临界资源需要设置不同的互斥信号量（mutex1，mutex2） P,V操作必须成对出现，缺少P就不能保证临界资源的互斥访问，缺少V就会导致资源永远不被释放，等待进程永远不能唤醒 信号量机制实现进程同步进程同步的目的在于让各个本来异步并发的进程按要求有序推进 1234567891011P1(){ 代码1; 代码2; ...

信号量机制在我们之前学习的有关进程互斥的硬件软件方法中，都存在着一些不可避免的问题 例如在双标志检查法中，由于检查和上锁操作不能原子性的完成，导致两个进程可能同时进入临界区 又比如之前所讲的软硬件方法都无法实现“让权等待” 基于以上所说的问题，我们最终提出了有效解决进程互斥与进程同步的方法–信号量机制 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而方便的实现进程互斥与进程同步 信号量实质就是一个变量（可以是一个整数，也可以是复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量（例如：系统有两台打印机，就可以设置一个信号量初始值为2） 原语是一种特殊程序段，其执行只能一气呵成，不可中断。原语是利用开/关中断指令实现的。软件解决方案的主要问题基本都出在进入区中的各种操作不能原子性的执行，因此如果能把进入区，退出区的操作都利用原语实现，就可以避免问题的产生 我们所使用的一对原语是：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名为wait和signal，括号里的S表示信号量S，其实就是函数调用时所传入的一个参数 wait和 ...

归并要了解归并排序算法首先要了解归并这一过程，归并过程处理两个可比较数组（两个数组已经各自有序），在归并过程中，不断对两个数组的当前首元素进行比较，将较小的元素放置到新数组的下一位置。 归并实现：(原地归并的抽象方法)123456789101112131415161718192021222324252627282930package cn.ywrby.test;public class MergeTest { private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } //原地归并的抽象实现 /* * 参数a表示已经部分有序的原数组（前一部分，后一部分分别有序） * 参数lo表示前一部分数组的首元素（前一部分最小值） * 参数mid表示前一部分数组最后一个元素（后一部分数组首元素的前一位，前一部分最大值） * 参数hi表示后一部分数组最后一位(后一部分最大值) * */ ...

进程同步 回顾:进程具有异步性的特征，即各个并发执行的进程以各自独立的，不可预知的速度向前推进 但进程的异步性在有些情况下可能会影响程序的正常运行，以上图的管道通信为例，进程1负责写入数据，进程2负责读取数据，只有进程1将管道数据填满后进程2才能成功取到数据，但两个进程并发执行，无法确定读写数据操作的先后顺序，而实际情况又要求必须先写后读的方式执行，此时就需要通过进程同步解决相关问题 进程同步亦称直接制约关系，它是指为完成某个任务而建立的两个或多个进程，这些进程由于需要在某些位置上协调工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作 进程互斥两种资源共享方式 通过之前的知识我们知道，进程的“并发”依赖于“共享”的支持，各个并发执行的进程不可避免的需要共享一些系统资源 我们把一个时间段内只允许一个进程使用的资源称为临界资源，许多物理（摄像头，打印机）都属于临界资源，此外还有许多变量，数据，内存缓冲区都属于临界资源 对临界资源的访问，必须互斥地进行。 互斥亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待，当前访问临界 ...

常见调度算法FCFS-先来先服务 (First Come First Server)算法思想主要从“公平”角度考虑，类似我们生活中的排队购物现象，先到先服务 算法规则按照作业/进程到达的先后顺序进行服务 用于作业/进程调度 用于作业调度时：考虑的是哪个作业先到达后备队列 用于进程调度时：考虑的是哪个进程先到达就绪队列 是否可抢占？非抢占式算法 示例 优缺点 优点：公平，算法实现简单 缺点：排在长作业/长进程后面的短作业需要等待很长时间，其带权周转时间很大，对短作业用户体验不好。 综上即FCFS算法对长作业有利，对短作业不利（例如上面例题种P3作业的带权周转时间达到了很大的8） 是否会导致饥饿饥饿指某进/作业长时间得不到服务 FCFS算法不会导致饥饿，只要各个任务依序排队，总会轮到响应作业 SJF-短作业优先 (Shortest Job First)算法思想追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间 算法规则最短的作业/进程有限得到服务（这里的最短指的是要求服务时间最短） 用于作业/进程调度即可用于作业调度，也可用于进程调度，用于进程调度事被称为“短进程优先算 ...

调度算法的评价指标CPU利用率指CPU忙碌时间占总时间的比例 $$利用率=\frac{忙碌的时间}{总时间}$$ Eg:某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5秒，再用打印机打印输出5秒，之后再执行5秒，才能结束。在此过程中CPU利用率、打印机利用率分别是多少? $$CPU利用率=\frac{5+5}{5+5+5}=66.67%$$ $$打印机利用率=\frac{5}{5+5+5}=33.33%$$ 系统吞吐量单位时间内完成作业的数量，对于计算机而言，肯定更希望用尽可能少的时间处理完尽可能多的作业，即系统吞吐量越大越好 $$系统吞吐量=\frac{总共完成的作业数目}{总共花费的时间总数}(单位：道/秒)$$ 周转时间指从作业被提交给系统开始，到作业完成为止的这段时间间隔。由四部分组成： 高级调度时间：作业在外存后被队列上等待的时间(在一个作业处理过程中，只会发生一次) 低级调度时间(就绪态)：进程在就绪队列上等待进程调度的时间。即进程处于就绪态的情况 运行态：进程在CPU上执行的时间 阻塞态：进程等待I/O设备操作完成的时间 (后三种时间在一个作业的整个处理过程 ...

进程调度进程调度(低级调度)，就是按照某种算法从就绪队列中选择一个进程为其分配处理机 需要进行进程调度与切换的情况（进程调度的时机）1. 当前运行的进程主动放弃处理机 进程正常终止 运行过程中发生异常而终止 进程主动请求阻塞（如等待I/O设备） 2. 当前运行的进程被动放弃处理机 分给进程的时间片用完 有更紧急的事情需要处理（如I/O中断） 有更高优先级的进程进入就绪队列 不能进行进程调度与切换的情况 在处理中断的过程中：中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换 进程在操作系统内核程序临界区中（具体解释见下文） 在原子操作过程中(原语)。原子操作不可中断，要一气呵成，所以运行过程中不可进行进程调度或切换 进程在操作系统内核程序临界区中不能进行进程调度和切换。临界资源：一个时间段内只允许一个进程使用的资源，各个进程需要互斥的访问临界资源 临界区：访问临界资源的代码 内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程PCB组成） 假如某进程当前正处在内核程序临界区，并且正在/之前访问就绪队列，则该进程会对就绪队列进行上锁操作 ...

调度概念当有多项任务需要处理时，由于资源有限，所有任务无法同时处理，此时就需要确定某种规则来决定各项任务的执行顺序，这就是调度 在多道程序系统中，进程的数量往往多于处理机个数，这样不可能同时并行处理各个进程 处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给该进程使用，以实现进程的并发执行 调度的三个层次高级调度（作业调度） 由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定作业调入内存的顺序，即高级调度 高级调度（作业调度）。按一定的原则从外存上处于后备队列（存储所有还没有进过内存的任务）的作业中挑选一个或多个作业，给他们分配内存等必要资源，并建立相应进程（建立PCB），以使他们获得竞争处理机的权利 高级调度是辅存(外存)与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。（即对于每项任务，高级调度只执行一次） 中级调度（内存调度） 引入了虚拟存储技术之后，可将暂时不能运行的进程 ...