单个链接表是否有环,有两种方法可以实现!
公众号搜索“码路印记”,点关注不迷路!
背景
数据结构是我们程序员的基本功,无论是在日常工作还是在求职面试中都会经常用到;而且近年来程序员的工作竞争越来越大,数据结构和算法在大厂的面试中都成了必考题。我所了解的:华为技术人员招聘必须先通过机试才能获得面试机会,机试为两道数据结构编码题,每道题200分总分400,240分可通过。字节跳动面试考察算法是出名了的,不必多说。我所经历的美团面试也都考察了数据结构和算法。
由于我们的日常开发工作往往集中在业务逻辑代码的编写,并且运行在Spring等优秀的框架之上,JDK的数据结构虽然熟练使用,但是对于底层逻辑及数据结构的了解少之又少,所以这就导致了面试中的数据结构与算法题目变成了“送命题”。因此,我们开发人员在日常工作中需要多关注这些常用的数据结构、算法,功夫用在平时,多积累,这样在求职时才能够得心应手。
问题
最近有同事到某几个大厂面试,都问到了链表相关的数据结构问题,比如单链表是否有环及环的入口检测问题、单链表元素去重问题、单链表逆置问题等。我研究练习了“单链表是否有环及环的入口检测问题”,作为日常积累,分享给大家。通过下图,了解一下单链表有环和无环的两种情况。 作为链表的第一篇,先看下如何构建链表。简单起见,直接上代码(如下)。为了接下来演示方便,我提供了两种链表的构建方式。第一种方式的目标是根据输入的数组从前往后创建单链表;第二种方式的目标是创建带环的链表,带环的依据是输入的数组序列中有且只有一个重复元素。
/**
* 链表节点
*/
public class Node {
public Node(int data) {
this.data = data;
next = null;
}
public int data;
public Node next;
}
/**
* 构建链表(无环)
*/
private static Node buildLinklist(int[] texts) {
Node head = new Node(0);
Node node = head;
for (int text : texts) {
Node next = new Node(text);
node.next = next;
node = next;
}
return head;
}
/**
* 构建链表,可能有环
*/
private static Node buildCircleLinklist(int[] texts) {
Node head = new Node(0);
Node node = head;
// 存储已经创建过的节点
Map<Integer, Node> nodeMap = new HashMap<>();
for (int text : texts) {
Node next = null;
if (nodeMap.containsKey(text)) {
next = nodeMap.get(text);
} else {
next = new Node(text);
nodeMap.put(text, next);
}
node.next = next;
node = next;
}
return head;
}
解法一:辅助空间法
单链表是否有环及环的入口检测问题,从题目可以知道,这其实是两个问题。一是:检测单链表中是否存在环;二是:如果存在环,则找到环的入口节点。所以,我们必须先解决第一个问题。
从头节点遍历链表,我们会发现:若链表中存在环,我们将无法找到链表的尾节点,一旦遍历过程进入环,遍历过程将在环内转圈,永远停不下来;若链表中不存在环,在有限的步骤内,我们的遍历过程就会停止。所以,从链表遍历的角度来看,我们可发现链表有环和无环的区别:
- 无环:在有限步骤内,我们可以找到链表的尾节点,即:存在一个节点指向空地址。
- 有环:永远无法找到尾节点,并且会在环内循环。
试想一下:如果我们的遍历过程是有记忆的,记住所有走过的节点(从内存上来看每个节点都是唯一的),那么我们会得出以下结论:
- 无环:遍历过程中从头到尾每个节点都是不同的,上图结果为:1-2-3-4-5-6-7-8-9-10-11;
- 有环:遍历过程中,一旦进入环的循环过程,环内的节点将会重复出现,上图结果为:1-2-3-4-5-6-7-8-9-10-11-4-5-6-7-8-9-10-11-4-5-6……。
所以,我就得出了今天的第一种解法,即:借助辅助空间,存储遍历过程中所有经过的节点唯一信息,每遍历一个节点检查其是否重复出现过,若遍历过程结束也没有发现重复节点,即可说明链表无环;若遍历过程中出现节点重复时,即可说明链表有环,并且第一个重复的元素为环的入口。
补充说明一点:节点唯一信息是通过Node对象的hashCode识别的,对于Node这个类,我并没有重写hashCode()方法,它代表的是对象的内存地址。
具体实现的代码如下所示:
/**
* 检查链表中是否有环:采用node唯一信息,配合HashMap
*
* @param head 头节点
* @return 若为空,则不存在环;不为空,则输出为入口节点
*/
private static Node detectCircleByExtraSpace(Node head) {
// 用这个map存储所有遍历过的节点
Map<Integer, Node> nodeHashCodeMap = new HashMap<>();
Node node = head.next;
// 节点不空则继续遍历,循环停止的条件有两个:一是遍历到链表尾节点,二是发现重复元素。
while (node != null) {
// 获取节点hashCode
Integer hashCode = node.hashCode();
// 判断是否曾经遍历过
if (nodeHashCodeMap.containsKey(hashCode)) {
// 如果曾经遍历过,说明有环,并且这是入口
return node;
}
// 遍历过即加入map
nodeHashCodeMap.put(node.hashCode(), node);
// 下一个
node = node.next;
}
// 走到这里,就说明没有环了。
return null;
}
接下来可以写段代码进行测试,下面的例子使用序列“1, 2, 3, 4, 5, 6, 3”创建有环和无环两种链表,结构如下图所示;然后使用detectCircleByExtraSpace进行检测。对于无环的应该输出“无环”,对于有环的应该输出“有环,入口为:3”。
public static void main(String[] args) {
int[] texts = {1, 2, 3, 4, 5, 6, 3};
Node head = buildCircleLinklist(texts);
Node node = detectCircleByExtraSpace(head);
printResult(node);
head = buildLinklist(texts);
node = detectCircleByExtraSpace(head);
printResult(node);
}
private static void printResult(Node node) {
if (node == null) {
System.out.println("无环");
} else {
System.out.println("有环,入口为:" + node.data);
}
}
上面的例子,输出结果如下,符合预期。
有环,入口为:3
无环
解法二:快慢指针法
熟悉这道题目的朋友,在看到题目时应该就想到了可以使用快慢指针来解决这个问题。一开始我只能理解检测是否存在环这部分,对于入口检测始终搞不明白,经过一阵公司推导,才弄清楚。这个解法的关键在于如何理解问题,以及理解问题后的一些数学公式推导。我试着说明一下快慢指针的解法原理。
首先看链表环的检测。假如把带环的链表比作一条单向的跑道,只能沿着箭头方向跑,那么跑步的人最终将会在环形跑道内转圈。假设,甲乙两人在沿跑道向相同的方向跑步,其中甲的速度是乙的速度的2倍;那么,甲会先进入环形跑道一直绕圈,乙再进入环形跑道。甲乙都进入环形跑道后,就变成了行程问题中的“追及问题”,由于甲的速度大于乙,那么在一段时间后甲肯定会追上乙的。当然,如果链表中没有环,甲的速度大于乙,那么甲会先跑到终点,过程中不会与乙相遇。
所以,我们可以使用上面“追及问题”的方式来解决链表环的检测问题。设置两个指针fast、slow,从链表头部开始向后遍历,fast的速度是slow的两倍。如果fast能够“追上”slow,则说明链表中存在环;若fast遍历完成走到尾节点,则说明链表中不存在环。
然后分析如何找到环的入口。先说结论:如果链表中存在环,快慢指针相遇后,把fast指针移到链表头部;然后fast和slow以相同的速度(每次移动一个节点)移动,当它们相遇时,相遇的点即为环的入口。再说如何推导,结合下图进行说明: 先做几个假设:
- 假设从头节点到环入口的距离为a,从环入口到fast、slow相遇点的距离为b,从相遇点到环入口的距离为c;
- 再假设链表的长度为L,环的长度为R;
- 假设slow走的距离为S,那么fast走过的距离为2S(fast除了走过a+b外,可能还会绕环走n圈)。
那么,就会有以下公式的推导:
最终得到:。结合上面说的结论(即:fast、slow相遇后,fast从头节点开始移动,slow从相遇点继续移动,fast的速度与slow一致),仔细看下这个公式代表了什么?
- a代表了从头节点到环入口的距离,相当于fast走过的距离;
- c+(n-1)*R代表从slow从相遇点走到环入口后又沿着环走了n-1圈;
- 以上两者相等即说明:fast、slow会在环的入口相遇;
所以:如果链表中存在环,快慢指针相遇后,把fast指针移到链表头部;然后fast和slow以相同的速度(每次移动一个节点)移动,当它们相遇时,相遇的点即为环的入口。
以上就是快慢指针解法的原理过程,这么看下来其实也是比较容易理解的。但是,如果没有遇到过、听说过,我是真的很难想到这个解法,尤其是第二步查找环入口。好了,理论部分分析完了,我们看下代码该如何实现:
/**
* 检测链表是否有环,若有环则找到入口
* 使用快慢指针的方式
*
* @param head 链表头节点
* @return 若为空,则不存在环;不为空,则输出为入口节点
*/
private static Node detectCircleByFastSlow(Node head) {
// 快慢指针从头节点开始
Node fast = head;
Node slow = head;
// 用于记录相遇点
Node encounter = null;
// fast一次走两步,所以要保证next和next.next都不为空,为空就说明无环
while (fast.next != null && fast.next.next != null) {
// fast走两步,slow走一步
fast = fast.next.next;
slow = slow.next;
// fast和slow一样,说明相遇了,或者fast追上slow了。
if (fast == slow) {
// 记录相遇点,fast或slow都一样
encounter = fast;
// 相遇了,就退出环检测过程
break;
}
}
// 如果encounter为空,说明没有环,就不用继续找环入口了。
if (encounter == null) {
return encounter;
}
// fast回到head位置
fast = head;
// 只要两者不相遇,就一直走下去
while (fast != slow) {
// fast每次走一步,slow每次走一步,速度一样
fast = fast.next;
slow = slow.next;
}
// 相遇点,即为环入口
return fast;
}
修改上面的测试代码,会发现与解法一的结果一致。
public static void main(String[] args) {
int[] texts = {1, 2, 3, 4, 5, 6, 3};
Node head = buildCircleLinklist(texts);
Node node = detectCircleByFastSlow(head);
printResult(node);
head = buildLinklist(texts);
node = detectCircleByFastSlow(head);
printResult(node);
}
总结
本文采用“辅助空间法”和“快慢指针法”两种方式解决了判断单链表是否有环及环入口查找的经典问题,两种方法各有利弊,简单总结如下:
- 辅助空间法:时间复杂度为O(n),空间复杂度为O(n)。好处是容易想到,容易理解;坏处是会消耗额外的辅助空间;
- 快慢指针法:时间复杂度为O(n),空间复杂度为O(1)。性能较好,但是不容易理解。
数据结构与算法的重要性文章开头已经说了,我还想再补充一些:虽然看起来很难,但是这些常见的问题、解法都是固定的,只要我们多积累、多练习、多思考,并且灵活运用到工作中去,就会发现它其实没有想象中那么难。
如果本文对你有帮助,麻烦转发给更多的朋友看到!
下一篇: 博弈论]斐波那契博弈
推荐阅读
-
单个链接表是否有环,有两种方法可以实现!
-
纯干货分享 | 研发效能提升——敏捷需求篇-而敏捷需求是提升效能的方式中不可或缺的模块之一。 云智慧的敏捷教练——Iris Xu近期在公司做了一场分享,主题为「敏捷需求挖掘和组织方法,交付更高业务价值的产品」。Iris具有丰富的团队敏捷转型实施经验,完成了企业多个团队从传统模式到敏捷转型的落地和实施,积淀了很多的经验。 这次分享主要包含以下2个部分: 第一部分是用户影响地图 第二部分是事件驱动的业务分析Event driven business analysis(以下简称EDBA) 用户影响地图,是一种从业务目标到产品需求映射的需求挖掘和组织的方法。 在软件开发过程中可能会遇到一些问题,比如大家使用不同的业务语言、技术语言,造成角色间的沟通阻碍,还会导致一些问题,比如需求误解、需求传递错误等;这会直接导致产品的功能需求和要实现的业务目标不是映射关系。 但在交付期间,研发人员必须要将这些需求实现交付,他们实则并不清楚这些功能需求产生的原因是什么、要解决客户的哪些痛点。研发人员往往只是拿到了解决方案,需要把它实现,但没有和业务侧一起去思考解决方案是否正确,能否真正的帮助客户解决问题。而用户影响地图通常是能够连接业务目标和产品功能的一种手段。 我们在每次迭代里加入的假设,也就是功能需求。首先把它先实现,再逐步去验证我们每一个小目标是否已经实现,再看下一个目标要是什么。那影响地图就是在这个过程中帮我们不断地去梳理目标和功能之间的关系。 我们在软件开发中可能存在的一些问题 针对这些问题,我们如何避免?先简单介绍做敏捷转型的常规思路: 先做团队级的敏捷,首先把产品、开发、测试人员,还有一些更后端的人员比如交互运维的同学放在一起,组成一个特训团队做交付。这个团队要包含交付过程中所涉及的所有角色。 接着业务敏捷要打通整个业务环节和研发侧的一个交付。上图中可以看到在敏捷中需求是分层管理的,第一层是业务需求,在这个层级是以用户目标和业务目标作为输入进行规划,同时需要去考虑客户的诉求。业务人员通过获取到的业务需求,进一步的和团队一起将其分解为产品需求。所以业务需求其实是我们真正去发布和运营的单元,它可以被独立发布到我们的生产环境上。我们的产品需求其实就是产品的具体功能,它是我们集成和测试的对象,也就是我们最终去部署到系统上的一个基本单元。产品需求再到了我们的开发团队,映射到迭代计划会上要把它分解为相应的技术任务,包括我们平时所说的比如一些前端的开发、后端的开发、测试都是相应的技术任务。所以业务敏捷要达到的目标是需要去持续顺畅高质量的交付业务价值。 将这几个点串起来,形成金字塔结构。最上层我们会把业务目标放在整个金字塔的塔尖。这个业务目标是通过用户的目标以及北极星指标确立的。确认业务目标后再去梳理相应的业务流程,最后生产。另外产品需求包含了操作流程和业务规则,具需求交付时间、工程时间以及我们的一些质量标准的要求。 谈到用户影响的地图,在敏捷江湖上其实有一个传说,大家都有一个说法叫做敏捷需求的“任督二脉”。用户影响地图其实就是任脉,在黑客马拉松上用过的用户故事地图其实叫督脉。所以说用户影响地图是在用户故事地图之前,先帮我们去梳理出我们要做哪些东西。当我们真正识别出我们要实现的业务活动之后,用户故事地图才去梳理我们整个的业务工作流,以及每个工作流节点下所要包含的具体功能和用户故事。所以说用户影响地图需要解决的问题,我们包括以下这些: 首先是范围蔓延,我们在整张地图上,功能和对应的业务目标是要去有一个映射的。这就避免了一些在我们比如有很多干系人参与的会议上,那大家都有不同想法些立场,会提出很多需求(正确以及错误的需求)。这个时候我们会依据目标去看这些需求是否真的是会影响我们的目标。 这里提到的错误需求,比如是利益相关的人提出的、客户认为产品应该有的、某个产品经理需求分析师认为可以有的....但是这些功能在用户影响地图中匹配不到对应目标的话,就需要降低优先级或弃掉。另外,通常我们去制定解决方案的时候,会考虑较完美的实现,导致解决方案括很多的功能。这个时候关键目标至关重要,会帮助我们梳理筛选、确定优先级。 看一下用户影响到地图概貌 总共分为一个三层的结构: 第一层why,你的业务目标哪个是最重要的,为什么?涉及到的角色有哪些? 第二层how ,怎样产生影响?影响用户角色什么样的行为? (不需要去列出所有的影响,基于业务目标) 第三层what,最关键的是在梳理需求时不需一次把所有细节想全,这通常团队中经常遇到的问题。 我们用这个例子来看一下 这是一个客服中心的影响地图,业务目标是 3个月内不增加客服人数的前提下能支持1.5倍的用户数。此业务目标设定是符合 smart 原则的,specific非常的具体,miserable 是可以衡量的,action reoriented是面向活动的, real list 也是很实际的。 量化的目标会指引我们接下来的行动,梳理一个业务目标,尽量去量化,比如 :我们通过打造一条什么样的流水线,能够提高整个部署的效率,时间是原来的 1/2 。这样才是一个能量化的有意义的目标。 回到这幅图, how 层级识别出来的内容,客服角色:想要对它施加的影响,把客户引导到论坛上,帮助客户更容易的跟踪问题,更快速的去定位问题。初级用户:方论坛上找到问题。高级用户:在论坛上回答问题。通过我们这些用户角色,进行活动,完成在不增加客户客服人数的前提下支持更多的用户数量。 最后一个层级,才是我们日常接触比较多的真正的功能的特性和需求,比如引导到客户到论坛上,其实这个产品就需要有一个常见问题的论坛的链接。这个层次需要我们团队进一步地在交付,在每个迭代之前做进一步的梳理,细化成相应的用户故事。 这个是云智慧团队中,自己做的影响地图的范例,可以看下整个的层级结构。序号表示优先级。 那我们用户影响地图可以总结为:
-
统计学习 04:假设检验(以 t 检验为例)和 P 值 - 要点 I. 假设检验的一般思路 假设检验 清楚你的问题是什么?期望得出什么结论? 例如,两种药物的疗效是否存在差异,自变量与因变量之间是否存在回归关系 .... 请始终牢记,假设检验回答的是是否存在某种关系的问题:它并不衡量这种关系有多大。 提出两种假设:零假设 (H0) 和备择假设 (H1) 零假设与备择假设相反,一般来说,研究的目的是证明原假设是错误的,即得出备择假设的结论。 例如,如果实验预期希望两种药物的疗效存在差异,那么 H0:μ1 - μ2 = 0;H1:μ1 - μ2 ≠ 0 H0:μ1-μ2 = 0 的一般形式称为双侧检验,而 >、<等零假设称为单侧检验。一般来说双侧检验更为常见,下面也主要介绍这种方法。 单尾或双尾测试 根据原始数据计算零假设概率分布的统计量(t 值、Z 值、F 值等)。 根据问题的性质选择合适的概率检验方法,从而计算出相应的统计量值;因此,不同情况的统计量值有不同的计算方法。 根据计算出的统计量值,利用统计软件,可以知道相应的 p 值是多少 也可以先确定一个合适的显著性水平(0.0.001....),并计算其临界值,再与我们计算出的统计量值进行比较,从而做出判断。 根据第四步的比较结果,如果 p 值小于预期的显著性水平(α,通常设定为 0.05),则认为该统计量远离原假设分布,属于小概率事件,则拒绝原假设,从而接受备择假设。 决定 要点 2:以 t 检验为例,演示上述假设检验思路。 t 检验基于 t 分布,常见的 t 检验有三种,如下图所示,但我认为第三种配对设计可能更常用(零假设:差异是否为零),下面介绍的例子就是一种配对设计 三次 t 检验 举例测量两组大鼠肝脏中维生素 A 的含量,比较两组大鼠维生素 A 含量是否有差异。数据如下 数据 (1) 预计两组大鼠的维生素 A 水平存在差异 (2) H0:μd=0,H1:μd≠0,α=0.05,双侧检验 (3) t 统计量的计算 配方 计算 上述程序计算的是*度为 7 的 t 分布情况下的 t 值。只需理解公式即可,不同的方法有不同的公式,这些交给统计软件即可。
-
windows下进程间通信的(13种方法)-摘 要 本文讨论了进程间通信与应用程序间通信的含义及相应的实现技术,并对这些技术的原理、特性等进行了深入的分析和比较。 ---- 关键词 信号 管道 消息队列 共享存储段 信号灯 远程过程调用 Socket套接字 MQSeries 1 引言 ---- 进程间通信的主要目的是实现同一计算机系统内部的相互协作的进程之间的数据共享与信息交换,由于这些进程处于同一软件和硬件环境下,利用操作系统提供的的编程接口,用户可以方便地在程序中实现这种通信;应用程序间通信的主要目的是实现不同计算机系统中的相互协作的应用程序之间的数据共享与信息交换,由于应用程序分别运行在不同计算机系统中,它们之间要通过网络之间的协议才能实现数据共享与信息交换。进程间通信和应用程序间通信及相应的实现技术有许多相同之处,也各有自己的特色。即使是同一类型的通信也有多种的实现方法,以适应不同情况的需要。 ---- 为了充分认识和掌握这两种通信及相应的实现技术,本文将就以下几个方面对这两种通信进行深入的讨论:问题的由来、解决问题的策略和方法、每种方法的工作原理和实现、每种实现方法的特点和适用的范围等。 2 进程间的通信及其实现技术 ---- 用户提交给计算机的任务最终都是通过一个个的进程来完成的。在一组并发进程中的任何两个进程之间,如果都不存在公共变量,则称该组进程为不相交的。在不相交的进程组中,每个进程都独立于其它进程,它的运行环境与顺序程序一样,而且它的运行环境也不为别的进程所改变。运行的结果是确定的,不会发生与时间相关的错误。 ---- 但是,在实际中,并发进程的各个进程之间并不是完全互相独立的,它们之间往往存在着相互制约的关系。进程之间的相互制约关系表现为两种方式: ---- (1) 间接相互制约:共享CPU ---- (2) 直接相互制约:竞争和协作 ---- 竞争——进程对共享资源的竞争。为保证进程互斥地访问共享资源,各进程必须互斥地进入各自的临界段。 ---- 协作——进程之间交换数据。为完成一个共同任务而同时运行的一组进程称为同组进程,它们之间必须交换数据,以达到协作完成任务的目的,交换数据可以通知对方可以做某事或者委托对方做某事。 ---- 共享CPU问题由操作系统的进程调度来实现,进程间的竞争和协作由进程间的通信来完成。进程间的通信一般由操作系统提供编程接口,由程序员在程序中实现。UNIX在这个方面可以说最具特色,它提供了一整套进程间的数据共享与信息交换的处理方法——进程通信机制(IPC)。因此,我们就以UNIX为例来分析进程间通信的各种实现技术。 ---- 在UNIX中,文件(File)、信号(Signal)、无名管道(Unnamed Pipes)、有名管道(FIFOs)是传统IPC功能;新的IPC功能包括消息队列(Message queues)、共享存储段(Shared memory segment)和信号灯(Semapores)。 ---- (1) 信号 ---- 信号机制是UNIX为进程中断处理而设置的。它只是一组预定义的值,因此不能用于信息交换,仅用于进程中断控制。例如在发生浮点错、非法内存访问、执行无效指令、某些按键(如ctrl-c、del等)等都会产生一个信号,操作系统就会调用有关的系统调用或用户定义的处理过程来处理。 ---- 信号处理的系统调用是signal,调用形式是: ---- signal(signalno,action) ---- 其中,signalno是规定信号编号的值,action指明当特定的信号发生时所执行的动作。 ---- (2) 无名管道和有名管道 ---- 无名管道实际上是内存中的一个临时存储区,它由系统安全控制,并且独立于创建它的进程的内存区。管道对数据采用先进先出方式管理,并严格按顺序操作,例如不能对管道进行搜索,管道中的信息只能读一次。 ---- 无名管道只能用于两个相互协作的进程之间的通信,并且访问无名管道的进程必须有共同的祖先。 ---- 系统提供了许多标准管道库函数,如: pipe——打开一个可以读写的管道; close——关闭相应的管道; read——从管道中读取字符; write——向管道中写入字符; ---- 有名管道的操作和无名管道类似,不同的地方在于使用有名管道的进程不需要具有共同的祖先,其它进程,只要知道该管道的名字,就可以访问它。管道非常适合进程之间快速交换信息。 ---- (3) 消息队列(MQ) ---- 消息队列是内存中独立于生成它的进程的一段存储区,一旦创建消息队列,任何进程,只要具有正确的的访问权限,都可以访问消息队列,消息队列非常适合于在进程间交换短信息。 ---- 消息队列的每条消息由类型编号来分类,这样接收进程可以选择读取特定的消息类型——这一点与管道不同。消息队列在创建后将一直存在,直到使用msgctl系统调用或iqcrm -q命令删除它为止。 ---- 系统提供了许多有关创建、使用和管理消息队列的系统调用,如: ---- int msgget(key,flag)——创建一个具有flag权限的MQ及其相应的结构,并返回一个唯一的正整数msqid(MQ的标识符); ---- int msgsnd(msqid,msgp,msgsz,msgtyp,flag)——向队列中发送信息; ---- int msgrcv(msqid,cmd,buf)——从队列中接收信息; ---- int msgctl(msqid,cmd,buf)——对MQ的控制操作; ---- (4) 共享存储段(SM) ---- 共享存储段是主存的一部分,它由一个或多个独立的进程共享。各进程的数据段与共享存储段相关联,对每个进程来说,共享存储段有不同的虚拟地址。系统提供的有关SM的系统调用有: ---- int shmget(key,size,flag)——创建大小为size的SM段,其相应的数据结构名为key,并返回共享内存区的标识符shmid; ---- char shmat(shmid,address,flag)——将当前进程数据段的地址赋给shmget所返回的名为shmid的SM段; ---- int shmdr(address)——从进程地址空间删除SM段; ---- int shmctl (shmid,cmd,buf)——对SM的控制操作; ---- SM的大小只受主存限制,SM段的访问及进程间的信息交换可以通过同步读写来完成。同步通常由信号灯来实现。SM非常适合进程之间大量数据的共享。 ---- (5) 信号灯 ---- 在UNIX中,信号灯是一组进程共享的数据结构,当几个进程竞争同一资源时(文件、共享内存或消息队列等),它们的操作便由信号灯来同步,以防止互相干扰。 ---- 信号灯保证了某一时刻只有一个进程访问某一临界资源,所有请求该资源的其它进程都将被挂起,一旦该资源得到释放,系统才允许其它进程访问该资源。信号灯通常配对使用,以便实现资源的加锁和解锁。 ---- 进程间通信的实现技术的特点是:操作系统提供实现机制和编程接口,由用户在程序中实现,保证进程间可以进行快速的信息交换和大量数据的共享。但是,上述方式主要适合在同一台计算机系统内部的进程之间的通信。 3 应用程序间的通信及其实现技术 ---- 同进程之间的相互制约一样,不同的应用程序之间也存在竞争和协作的关系。UNIX操作系统也提供一些可用于应用程序之间实现数据共享与信息交换的编程接口,程序员可以通过自己编程来实现。如远程过程调用和基于TCP/IP协议的套接字(Socket)编程。但是,相对普通程序员来说,它们涉及的技术比较深,编程也比较复杂,实现起来困难较大。 ---- 于是,一种新的技术应运而生——通过将有关通信的细节完全掩盖在某个独立软件内部,即底层的通讯工作和相应的维护管理工作由该软件内部来实现,用户只需要将通信任务提交给该软件去完成,而不必理会它的具体工作过程——这就是所谓的中间件技术。 ---- 我们在这里分别讨论这三种常用的应用程序间通信的实现技术——远程过程调用、会话编程技术和MQSeries消息队列技术。其中远程过程调用和会话编程属于比较低级的方式,程序员参与的程度较深,而MQSeries消息队列则属于比较高级的方式,即中间件方式,程序员参与的程度较浅。 ---- 4.1 远程过程调用(RPC)