Yarrow Blog

内存基础知识 内存(Memory)是计算机的重要部件之一，也称内存储器和主存储器，它用于暂时存放CPU中的运算数据，与硬盘等外部存储器交换的数据。它是外存与CPU进行沟通的桥梁。只要计算机开始运行，操作系统就会把需要运算的数据从内存调到CPU中进行运算，当运算完成，CPU将结果传送出来。 在多道程序环境下，同一时间可能会有多个程序并发执行，即有多个程序的数据需要同时存放在内存中，此时，为了区分内存中不同数据存放的位置，就需要引入存储单元的概念 存储单元：一般应具有存储数据和读写数据的功能，以8位二进制作为一个存储单元，也就是一个字节。每个单元有一个地址，是一个整数编码，可以表示为二进制整数。程序中的变量和主存储器的存储单元相对应。变量的名字对应着存储单元的地址，变量内容对应着单元所存储的数据。存储地址一般用十六进制数表示，而每一个存储器地址中又存放着一组二进制（或十六进制）表示的数，通常称为该地址的内容。 如果计算机“按字节编址”则每个存储单元大小为1字节即1B，即8个二进制位 如果字长为16位的计算机“按字编址”，则每个存储单元大小为1字，每个字大小为16个二进制位 内存 ...

死锁的基本概念在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里资源，导致各个进程都阻塞，无法向前推进的现象，称为“死锁”。发生死锁后若无外力的干涉，这些进程都将无法向前推进 要注意的是，死锁，饥饿和死循环是三个比较容易混淆的概念 饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。例如：在短进程优先算法（SPF）中，若有源源不断的短进程到来，则长进程一直得不到处理机，从而发生长进程“饥饿” 死循环：某进程执行过程中一直跳不出某个循环的现象，有时是因为程序逻辑bug导致，有时也可能是程序故意设计 综上，可以总结三者的异同点： - 共同点 区别 死锁 都是进程无法顺利向前推进的现象 死锁一定是“循环等待对方手里的资源”导致的，因此如果有死锁现象，那至少有两个或以上的进程同时发生死锁。同时，由于是始终处于等待对方资源的状态，所以发生死锁的进程一定处于阻塞态 饥饿 - 可能只有一个进程发生饥饿（例如上文所提到的长进程饥饿）。发生饥饿的进程既可能是阻塞态（例如长期得不到I/O设备），也可能是就绪态（长期得不到处理机） 死循环 - 可能只有一个进程发生死循环 ...

管程信号量机制存在的问题编写程序困难，容易出错。因此人们考虑使用另外设计的机制，保证程序员在编写程序过程中不需要关注复杂的PV操作。 管程的定义和组成管程是一种特殊的软件模块，其组成部分为： 局部与管程的共享数据结构（类似于局部变量的概念，该数据结构只能被管程所访问） 对该数据结构进行操作的一组过程（类似于局部方法） 对局部于管程的共享数据设置初始值的语句（初始化方法） 管程的名字 管程的基本特征 局部与管程的数据只能被局部与管程的过程（方法）所访问 一个进程只有通过调用管程内的方法，才能进入管程并访问共享数据 每次仅允许一个进程在管程内执行某个内部过程（方法） 管程示例 这个过程中由编译器负责实现各个进程互斥的进入管程中的方法 注意 引入管程的目的无非是为了更方便的实现进程的互斥与同步 需要在管程中定义共享数据（例如生产者消费者问题中的缓冲区） 需要在管程中定义用于访问共享数据的“入口”，即函数 只有通过管程中定义的方法才能进入管程，才能访问共享数据 管程存在很多方法，但每次只能开放其中一个方法作为“入口”，并且只允许一个进程或线程进入（这种互斥的特性是由编译器实现的，程序员不 ...

吸烟者问题假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复(让三个抽烟者轮流地抽烟) 以上图为例，供应者向桌上摆放烟草和纸两种材料，缺少这两种材料的三号吸烟者就会取走材料吸烟，在吸烟结束后会提醒供应者放新的材料在桌上 根据题目我们直到，放在桌上的材料一共有三种组合方式 纸和胶水（order1）会被一号吸烟者取走 烟草和胶水（order2）会被二号吸烟者取走 烟草和纸（order3）会被三号吸烟者取走 本题可以看作是存在一个生产者和多个消费者的问题，同时生产者所生产的物品并不相同 关系分析找出题目中描述的各个进程，分析同步互斥关系 互斥关系：桌子可以抽象为容量为1的缓冲区，需要互斥访问 同步关系：桌上有组合一时第一个抽烟者取走物品 同步关系：桌上有组合 ...

区块链网络中矿池选择的演化博弈论文原文链接: 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才能成功取到数据，但两个进程并发执行，无法确定读写数据操作的先后顺序，而实际情况又要求必须先写后读的方式执行，此时就需要通过进程同步解决相关问题 进程同步亦称直接制约关系，它是指为完成某个任务而建立的两个或多个进程，这些进程由于需要在某些位置上协调工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作 进程互斥两种资源共享方式 通过之前的知识我们知道，进程的“并发”依赖于“共享”的支持，各个并发执行的进程不可避免的需要共享一些系统资源 我们把一个时间段内只允许一个进程使用的资源称为临界资源，许多物理（摄像头，打印机）都属于临界资源，此外还有许多变量，数据，内存缓冲区都属于临界资源 对临界资源的访问，必须互斥地进行。 互斥亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待，当前访问临界 ...