Yarrow Blog

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

常见调度算法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设备操作完成的时间 (后三种时间在一个作业的整个处理过程 ...