Optimistic semaphores with non‐deterministic choice operation for heterogeneous manycore systems

The Nix operating system permits different roles to be assigned to the cores. One of the roles is to be able to run user‐space code with no interrupts from the operating system, which is particularly useful for high‐performance computing. System calls are especially expensive to a core playing this role. This paper presents a new implementation of optimistic semaphores that avoid performing expensive system calls in an uncontended scenario. The implementation is straightforward and somewhat unorthodox: a semaphore is based on a data structure and a lock that are shared between user space and kernel space. This study aims at evaluating if such an approach is viable. In addition, the implementation includes a non‐deterministic choice operation over a collection of semaphores, altsems. This novel operation facilitates the creation of higher‐level communication mechanisms, such as sockets and channels. To support this claim, we implemented a new kind of buffered communication channels named tubes, tailored for communicating processes running on different (heterogeneous) cores. The paper describes the implementation of the semaphores and the tubes, a comparative analysis of optimistic and non‐optimistic semaphores on Nix, and a comparative analysis of tubes and other kinds of communication channels that are available on the Nix operating system. Copyright © 2014 John Wiley & Sons, Ltd.     

Extended semaphore operations

Extended semaphores systems such as in UNIX System V are a powerful extension of Dijkstra's semaphores. They allow efficient solutions to a number of classic synchronization problems. UNIX semaphore operations appear to be insufficiently well defined, in particular when a semaphore is repeated in an operator. This results in several solutions relying on assumed properties. A new semaphore operator, isem, based on extended semaphore operators is introduced. The operator isem is clearly defined, can be implemented efficiently, and yields simple solutions to many classic synchronization problems. Copyright © 2000 John Wiley & Sons, Ltd.     

Unshuffling a square is NP-hard

A shuffle of two strings is formed by interleaving the characters into a new string, keeping the characters of each string in order. A string is a square if it is a shuffle of two identical strings. There is a known polynomial time dynamic programming algorithm to determine if a given string z is the shuffle of two given strings x, y; however, it has been an open question whether there is a polynomial time algorithm to determine if a given string z is a square. We resolve this by proving that this problem is NP-complete via a many-one reduction from 3-Partition.     

Process scheduling and UNIX semaphores

Semaphores have been used extensively in programming concurrent tasks. Various extensions have been proposed for problems in which traditional semaphores turned out to be difficult to use. The extended semaphore primitives investigated here are based on the version of semaphores implemented in UNIX System V. Implementation issues are discussed and practical illustrations of their use are provided. In particular, algorithms for a variety of common process scheduling schemes are shown. These solutions are evaluated and the strengths and weaknesses of UNIX semaphores are discussed.     

用信号量实现进程同步的一题四解方法

用信号量机制实现并发进程之间的同步是操作系统中研究的重要课题。对于该问题,进行了方法学的讨论,提出了四种解题方法,其中混合型方法实现了用最少的信号量实现进程同步的问题,对该知识点的理解和掌握很有帮助。     

Java多线程设计模式研究

针对Java多线程并发程序设计，归类和总结了不同功能的Java多线程设计模式，结合实例分析比较了这些设计模式，这有助于解决实际编程中的并发问题，开发出高质量的Java多线程程序。     

浅析多线程Java程序中死锁问题的解决

本文就操作系统中死锁的概念进行了阐述。提出了多线程Java程序中死锁问题的解决，就关键的死锁的防止问题进行了分析。并通过实例说明问题的解决方法。     

Towards a derivational style of distributed system design — An example

Rederivation of the train signalling protocol developed in the 19th century is used to illustrate the application of several formal techniques to assist in the derivation of an implementation of a simple distributed system from its specification. It was this train signalling protocol that gave rise to the now-familiar concept ofsemaphore. However, a study of the train system shows that there is much more to its protocol than simply the instantiation of the semaphore concept.The derivation makes use of several formal techniques including weakest precondition calculation, finite differencing, generalization, and weakening of invariants. Informal reasoning is used to treat concerns of availability of information, and availability of control. Opportunities for inserting additional robustness into the derived implementation are identified during the process.The objective is to demonstrate the degree to which an implementation can bederived, rather than merely verified after some unknown invention process.     

网络状态感知的MapReduce作业洗牌数据传输调度研究

MapReduce作业在洗牌阶段花费大量时间,因此有效的洗牌数据传输调度可以提高MapReduce的性能。数据中心网络中,常有一些周期性的数据流传输。在考虑已知这些周期性数据流传输的情况下,为MapReduce的洗牌数据传输调度问题建立了优化模型,并设计了一个有效的数据传输调度算法。在网络空闲时间段大小相同的情况下,证明了所提算法是近似比为3/2的近似算法。仿真实验结果表明,该算法能够有效地利用网络资源,减少洗牌数据流的调度长度。     

一种基于四叉树的空域图像选择加密算法

提出一种基于四叉树结构的选择加密算法。对空域图像位平面采用四叉树编码,根据四叉树编码的结构特点对数据进行置乱和选择加密,对加密算法进行加密数据量分析和安全性评估。实验结果表明,该算法安全性较高,其空域图像的加密数据量为一般加密算法的50%左右。     

一种新型流密码系统

根据人们常用的洗牌算法对LFSR进行非线性变换,利用该变换可以改变元素原有的排列顺序,扰乱序列原有的某种规律性和结构性,提高序列的非线性,从而构造出一种新流密码系统。实验结果表明,由该系统产生的密钥序列具有均匀性,相关性小的特点。该密码系统能构被应用于网络安全等领域。     

一种基于Linux的数据共享模型的研究与实现

越来越多的工业控制项目都要求计算机的多个进程同时读取或修改该计算机不断收到的实时数据,这就带来了系统I/O的速度和系统资源的安全问题。基于此,提出了一种在Linux平台下基于双缓冲和强制访问控制机制的实时数据共享模型,并介绍了该模型主要用到的技术,最后给出了具体的实现方法。     

广播机制解决Shuffle过程数据倾斜的方法

在Spark计算平台中，数据倾斜往往导致某些节点承受更大的网络流量和计算压力，给集群的CPU、内存、磁盘和流量带来了巨大的负担，影响整个集群的计算性能.本文通过对Spark Shuffle设计和算法实现的研究，深入分析在大规模分布式环境下发生数据倾斜的本质原因.提出了广播机制避免Shuffle过程数据倾斜的方法，分析了广播变量分发逻辑过程，给出广播变量性能优势分析和该方法的算法实现.通过Broadcast Join实验验证了该方法在性能上有稳定的提升.     

Finding shuffle words that represent optimal scheduling of shared memory access

In the present paper, we introduce and study the problem of computing, for any given finite set of words, a shuffle word with a minimum so-called scope coincidence degree. The scope coincidence degree is the maximum number of different symbols that parenthesize any position in the shuffle word. This problem is motivated by an application of a new automaton model and can be regarded as the problem of scheduling shared memory accesses of some parallel processes in a way that minimizes the number of memory cells required. We investigate the complexity of this problem and show that it can be solved in polynomial time.     

信号量在μC/OS-Ⅱ中的应用

实时多任务操作系统在嵌入式系统中的应用越来越受到开发者的重视,信号量做为任务之间的通信手段之一,在实时多任务操作系统中广泛使用;文章首先介绍了实时操作系统中的信号量及其类型,然后介绍了μC/OS-Ⅱ中信号量的管理,并重点分类讨论了信号量的作用、工作原理以及具体的实现方法,最后给出了μC/OS-Ⅱ中信号量在无人机系统中的应用。