深入理解C++队列的创建与使用方法
什么是队列结构
队列结构是从数据运算来分类的,也就是说队列结构具有特殊的运算规则。而从数据的逻辑结构来看,队列结构其实就是一种线性结构。如果从数据的存储结构来进一步划分,队列结构可以分成两类。
顺序队列结构:即使用一组地址连续的内存单元依次保存队列中的数据。在程序中,可以定义一个指定大小的结构数组来作为队列。
链式队列结构:即使用链表形式保存队列中各元素的值。
在队列结构中允许对两端进行操作,但是两端的操作不同。在表的一端只能进行删除操作,称为队头;在表的另一端只能进行插入操作,称为队尾。如果队列中没有数据元素,则称之为空队列。从数据的运算角度分析,队列是按照“先进先出”的原则处理结点的。
可以将队列结构理解成是:超市排队结账的人群,排在队首的人先结账,然后不断会有人排在队尾等待结账,这就是一个先来先服务的队列的现实中的例子。
一般队列结构的基本操作只有两个:
入队列:将一个元素添加到队尾(相当于到队列最后排队等待)
出队列:将对头的元素取出,同时删除该元素,使后一个元素成为队头。
初次之外,还有初始化队列、获取队列长度的简单运算。下面,我们就是用C++建立顺序队列结构,并完成顺序队列结构的基本运算。
准备数据
准备数据就是定义在队列操作中需要用到的变量及数据结构等。
struct DATA{
string name;
int age;
};
struct SQType
{
DATA data[QUEUELEN]; //队列数组
int head; //队头
int tail; //队尾
};
这里,定义了队列结构的最大长度QUEUELEN ,队列结构数据元素的类型DATA以及队列结构的数据结构SQType。在数据结构SQType中,data为数据元素,head为队首的序号,tail为队尾的序号。当head=0时表示队列为空,当tail=QUEUELEN时表示队列满。
初始化队列数据
顺序队列的初始化操作步骤如下:
(1)按符号常量QUEUELEN指定的大小申请一段内存空间,用来保存队列中的数据。
(2)设置head=0和tail=0,表示一个空栈。
示例代码如下:
SQType *SQTypeInit()
{
SQType * q;
if(q=new SQType) //申请队列的内存空间
{
q->head=0; //设置队首
q->tail=0; //设置队尾
return q;
}
else
{
return NULL; //返回空
}
}
首先使用new申请内存,申请成功以后设置队头和队尾,然后返回申请内存的首地址,如果申请失败则返回NULL。
判断空队列
判断空队列是判断一个队列结构是否为空。如果是空队列,则表示该队列结构中国没有数据。此时可以进入如队列操作,不可以进行出队列操作。
示例代码如下:
int SQTypeIsEmpty(SQType *q)
{
return(q->head==q->tail);
}
输入参数q为一个指向操作的队列的指针。程序中,根据队列head是否等于tail判断队列是否为空。
判断满队列
判断满队列就是判断一个队列结构是否为满。如果是满队列,则表示该队列中没有多余的空间来保存额外数据。测试不可以进行入队列操作,可以进行出队列操作。
示例代码如下:
int SQTypeIsFull(SQType *q)
{
return(q->tail==QUEUELEN)
}
输入参数q为一个指向操作的队列的指针。程序中,根据队列tail是否等于队列的最大值QUEUELEN判断队列是否是满的。
清空队列
清空队列就是清楚一个队列中的所有的数据。示例代码如下:
void SQTypeClear(SQType *q)
{
q->head=0;
q->tail=0;
}
将队列顶指针head和尾指针tail设置为0,表示执行清空操作。
释放空间
释放空间是释放队列结构所占用的内存单元。由前面可知,在初始化队列结构时,使用了new关键字分配内存单元。虽然可以使用清空队列操作,但是清空队列操作并没有释放内存空间,这就需要使用delete关键字释放所占的内存单元。
示例代码如下:
void SQTypeFree(SQType *q)
{
if(q!=NULL) delete q;
}
程序中,调用了得delete释放new申请的内存空间。
入队列
入队列是队列结构的基本操作,主要操作是将数据元素保存到队列结构。入队列操作的具体步骤如下:
(1)首先判断队尾,如果tail等于QUEUELEN,则表示溢出,进行出错处理。否则执行以下操作。
(2)设置tail=tail+1(队列顶指针加1,指向入队列地址)
(3)就将入队列元素保存到tail指向的位置
示例代码如下:
int InSQType(SQType *q,DATA data)
{
if(q->tail==QUEUELEN)
{
cout<<"队列已满!操作失败!"<<endl;
return 0;
}else
{
q-data[q->tail++]=data; //将元素入队列
return 1;
}
}
输入参数q为指向操作的队列的指针,输入参数data为需要入队列的数据元素。程序中首先判断队列是否溢出,如果溢出则不进行入队列操作,否则修改队列顶指针的值,再将元素入队列。
因为tail的值从0开始,当前的值就是要插入的数组对应的元素的位置,所以写成q->tail++。
出队列
出队列是队列结构的基本操作,主要操作与入队列相反,其实从队列顶弹出一个数据元素。出队列操作的具体步骤如下:
(1)首先判断队首head,如果head等于tail,则表示为空队列,进行出错处理。否则,执行下面的步骤
(2)从队列首部取出队头元素(实际返回队头元素的指针)
(3)修改队首head的序号,使其指向后一个元素。
示例代码如下:
DATA *OutSQType(SQType *q)
{
if(q->tail==q->head)
{
cout<<"队列已空!操作失败!"<<endl;
exit(0);
}else
{
return &(q->data[q->head++]);
}
}
输入参数q为指向操作的队列的指针。该函数返回值是一个DATA类型的数据,返回值是指向该数据元素的指针。
读结点数据
读结点数据也就是读取队列结构中结点的数据,这里的读操作其实就是读队列头的数据。需要助于的是,读结点数据的操作和出队列操作不同。读结点数据的操作仅是显示队列顶结点数据的内容,而出队列操作则将队列顶数据弹出,该数据不再存在。
示例代码如下:
DATA * PeekSQType(SQType *q)
{
if(SQTypeIsEmpty(q))
{
cout<<"空队列"<<endl;
return NULL;
}else
{
return &(q->data[q->head]);
}
}
该函数返回值同样是一个DATA类型的指针数据,返回值是指向数据元素的指针。
计算队列长度
计算队列长度就是统计该队列中数据结点的个数。计算队列长度的方法比较简单,直接队尾序号减去队首序号即可。
示例代码如下:
int SQTypeLen(SQType *q)
{
return(q->tail-q->head);
}
队列结构操作实例代码:
完整的代码会比较长,不过函数部分和上面介绍的基本一致,主要是看main函数中这些函数的用法:
#include<iostream>
#include<string>
using namespace std;
#define QUEUELEN 10
struct DATA{
string name;
int age;
};
struct SQType
{
DATA data[QUEUELEN]; //队列数组
int head; //队头
int tail; //队尾
};
/*******************队列的初始化*************************/
SQType *SQTypeInit()
{
SQType * q;
if(q=new SQType) //申请队列的内存空间
{
q->head=0; //设置队首
q->tail=0; //设置队尾
return q;
}
else
{
return NULL; //返回空
}
}
/*******************判断空队列*************************/
int SQTypeIsEmpty(SQType *q)
{
return(q->head==q->tail);
}
/*******************判断满队列*************************/
int SQTypeIsFull(SQType *q)
{
return(q->tail==QUEUELEN);
}
/*******************清空队列*************************/
void SQTypeClear(SQType *q)
{
q->head=0;
q->tail=0;
}
/*******************释放空间*************************/
void SQTypeFree(SQType *q)
{
if(q!=NULL) delete q;
}
/*******************入队列操作*************************/
int InSQType(SQType *q,DATA data)
{
if(q->tail==QUEUELEN)
{
cout<<"队列已满!操作失败!"<<endl;
return 0;
}else
{
q->data[q->tail++]=data; //将元素入队列
return 1;
}
}
/*******************出队列操作*************************/
DATA *OutSQType(SQType *q)
{
if(q->tail==q->head)
{
return NULL;
}else
{
return &(q->data[q->head++]);
}
}
/*******************读结点数据*************************/
DATA * PeekSQType(SQType *q)
{
if(SQTypeIsEmpty(q))
{
cout<<"空队列"<<endl;
return NULL;
}else
{
return &(q->data[q->head]);
}
}
/*******************计算队列长度*************************/
int SQTypeLen(SQType *q)
{
return(q->tail-q->head);
}
/*********************主函数******************************/
int main()
{
SQType *stack;
DATA data,*p;
stack=SQTypeInit(); //执行初始化操作
cout<<"执行入队列操作:"<<endl;
cout<<"输入姓名,年龄进行入队操作:"<<endl;
while(1)
{
cin>>data.name>>data.age;
if(data.age==0)
{
break; //若输入为0,则退出
}
else
{
InSQType(stack,data);
}
}
cout<<"进行出栈操作:"<<endl;
p=OutSQType(stack);
cout<<p->name<<","<<p->age<<endl;
cout<<"读取首结点数据:"<<endl;
p=PeekSQType(stack);
cout<<p->name<<","<<p->age<<endl;
cout<<"执行出栈操作:"<<endl;
while(1)
{
if(SQTypeIsEmpty(stack))
{
cout<<"所有数据出栈完毕,栈为空!"<<endl;
break;
}else
{
p=OutSQType(stack);
cout<<p->name<<","<<p->age<<endl;
}
}
SQTypeFree(stack);
return 0;
}
程序运行界面:
上一篇: C/C++ 实现循环队列的方法
下一篇: 全面解析C语言中处理进程信号的实用函数
推荐阅读
-
epoll简介及触发模式(accept、read、send)-epoll的简单介绍 epoll在LT和ET模式下的读写方式 一、epoll的接口非常简单,一共就三个函数:1. int epoll_create(int size);创建一个epoll的句柄,size用来告诉内核这个监听的数目一共有多大。这个参数不同于select中的第一个参数,给出最大监听的fd+1的值。需要注意的是,当创建好epoll句柄后,它就是会占用一个fd值,在linux下如果查看/proc/进程id/fd/,是能够看到这个fd的,所以在使用完epoll后,必须调用close关闭,否则可能导致fd被耗尽。2. int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);epoll的事件注册函数,它不同与select是在监听事件时告诉内核要监听什么类型的事件,而是在这里先注册要监听的事件类型。第一个参数是epoll_create的返回值,第二个参数表示动作,用三个宏来表示:EPOLL_CTL_ADD:注册新的fd到epfd中;EPOLL_CTL_MOD:修改已经注册的fd的监听事件;EPOLL_CTL_DEL:从epfd中删除一个fd;第三个参数是需要监听的fd,第四个参数是告诉内核需要监听什么事,struct epoll_event结构如下:struct epoll_event { __uint32_t events; /* Epoll events */ epoll_data_t data; /* User data variable */};events可以是以下几个宏的集合:EPOLLIN :表示对应的文件描述符可以读(包括对端SOCKET正常关闭); EPOLLIN事件:EPOLLIN事件则只有当对端有数据写入时才会触发,所以触发一次后需要不断读取所有数据直到读完EAGAIN为止。否则剩下的数据只有在下次对端有写入时才能一起取出来了。现在明白为什么说epoll必须要求异步socket了吧?如果同步socket,而且要求读完所有数据,那么最终就会在堵死在阻塞里。 EPOLLOUT:表示对应的文件描述符可以写; EPOLLOUT事件:EPOLLOUT事件只有在连接时触发一次,表示可写,其他时候想要触发,那要先准备好下面条件:1.某次write,写满了发送缓冲区,返回错误码为EAGAIN。2.对端读取了一些数据,又重新可写了,此时会触发EPOLLOUT。简单地说:EPOLLOUT事件只有在不可写到可写的转变时刻,才会触发一次,所以叫边缘触发,这叫法没错的!其实,如果真的想强制触发一次,也是有办法的,直接调用epoll_ctl重新设置一下event就可以了,event跟原来的设置一模一样都行(但必须包含EPOLLOUT),关键是重新设置,就会马上触发一次EPOLLOUT事件。1. 缓冲区由满变空.2.同时注册EPOLLIN | EPOLLOUT事件,也会触发一次EPOLLOUT事件这个两个也会触发EPOLLOUT事件 EPOLLPRI:表示对应的文件描述符有紧急的数据可读(这里应该表示有带外数据到来);EPOLLERR:表示对应的文件描述符发生错误;EPOLLHUP:表示对应的文件描述符被挂断;EPOLLET: 将EPOLL设为边缘触发(Edge Triggered)模式,这是相对于水平触发(Level Triggered)来说的。EPOLLONESHOT:只监听一次事件,当监听完这次事件之后,如果还需要继续监听这个socket的话,需要再次把这个socket加入到EPOLL队列里3. int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);等待事件的产生,类似于select调用。参数events用来从内核得到事件的集合,maxevents告之内核这个events有多大,这个maxevents的值不能大于创建epoll_create时的size,参数timeout是超时时间(毫秒,0会立即返回,-1将不确定,也有说法说是永久阻塞)。该函数返回需要处理的事件数目,如返回0表示已超时。-------------------------------------------------------------------------------------------- 从man手册中,得到ET和LT的具体描述如下EPOLL事件有两种模型:Edge Triggered (ET)Level Triggered (LT)假如有这样一个例子:1. 我们已经把一个用来从管道中读取数据的文件句柄(RFD)添加到epoll描述符2. 这个时候从管道的另一端被写入了2KB的数据3. 调用epoll_wait(2),并且它会返回RFD,说明它已经准备好读取操作4. 然后我们读取了1KB的数据5. 调用epoll_wait(2)......Edge Triggered 工作模式:如果我们在第1步将RFD添加到epoll描述符的时候使用了EPOLLET标志,那么在第5步调用epoll_wait(2)之后将有可能会挂起,因为剩余的数据还存在于文件的输入缓冲区内,而且数据发出端还在等待一个针对已经发出数据的反馈信息。只有在监视的文件句柄上发生了某个事件的时候 ET 工作模式才会汇报事件。因此在第5步的时候,调用者可能会放弃等待仍在存在于文件输入缓冲区内的剩余数据。在上面的例子中,会有一个事件产生在RFD句柄上,因为在第2步执行了一个写操作,然后,事件将会在第3步被销毁。因为第4步的读取操作没有读空文件输入缓冲区内的数据,因此我们在第5步调用 epoll_wait(2)完成后,是否挂起是不确定的。epoll工作在ET模式的时候,必须使用非阻塞套接口,以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。最好以下面的方式调用ET模式的epoll接口,在后面会介绍避免可能的缺陷。 i 基于非阻塞文件句柄 ii 只有当read(2)或者write(2)返回EAGAIN时才需要挂起,等待。但这并不是说每次read时都需要循环读,直到读到产生一个EAGAIN才认为此次事件处理完成,当read返回的读到的数据长度小于请求的数据长度时,就可以确定此时缓冲中已没有数据了,也就可以认为此事读事件已处理完成。Level Triggered 工作模式相反的,以LT方式调用epoll接口的时候,它就相当于一个速度比较快的poll(2),并且无论后面的数据是否被使用,因此他们具有同样的职能。因为即使使用ET模式的epoll,在收到多个chunk的数据的时候仍然会产生多个事件。调用者可以设定EPOLLONESHOT标志,在 epoll_wait(2)收到事件后epoll会与事件关联的文件句柄从epoll描述符中禁止掉。因此当EPOLLONESHOT设定后,使用带有 EPOLL_CTL_MOD标志的epoll_ctl(2)处理文件句柄就成为调用者必须作的事情。然后详细解释ET, LT:LT(level triggered)是缺省的工作方式,并且同时支持block和no-block socket.在这种做法中,内核告诉你一个文件描述符是否就绪了,然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作,内核还是会继续通知你的,所以,这种模式编程出错误可能性要小一点。传统的select/poll都是这种模型的代表.ET(edge-triggered)是高速工作方式,只支持no-block socket。在这种模式下,当描述符从未就绪变为就绪时,内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪,并且不会再为那个文件描述符发送更多的就绪通知,直到你做了某些操作导致那个文件描述符不再为就绪状态了(比如,你在发送,接收或者接收请求,或者发送接收的数据少于一定量时导致了一个EWOULDBLOCK 错误)。但是请注意,如果一直不对这个fd作IO操作(从而导致它再次变成未就绪),内核不会发送更多的通知(only once),不过在TCP协议中,ET模式的加速效用仍需要更多的benchmark确认(这句话不理解)。在许多测试中我们会看到如果没有大量的idle -connection或者dead-connection,epoll的效率并不会比select/poll高很多,但是当我们遇到大量的idle- connection(例如WAN环境中存在大量的慢速连接),就会发现epoll的效率大大高于select/poll。(未测试)另外,当使用epoll的ET模型来工作时,当产生了一个EPOLLIN事件后,读数据的时候需要考虑的是当recv返回的大小如果等于请求的大小,那么很有可能是缓冲区还有数据未读完,也意味着该次事件还没有处理完,所以还需要再次读取: 这里只是说明思路(参考《UNIX网络编程》) while(rs) {buflen = recv(activeevents[i].data.fd, buf, sizeof(buf), 0);if(buflen < 0){// 由于是非阻塞的模式,所以当errno为EAGAIN时,表示当前缓冲区已无数据可读// 在这里就当作是该次事件已处理处.if(errno == EAGAIN)break; else return; }else if(buflen == 0) { // 这里表示对端的socket已正常关闭. } if(buflen == sizeof(buf) rs = 1; // 需要再次读取 else rs = 0; } 还有,假如发送端流量大于接收端的流量(意思是epoll所在的程序读比转发的socket要快),由于是非阻塞的socket,那么send函数虽然返回,但实际缓冲区的数据并未真正发给接收端,这样不断的读和发,当缓冲区满后会产生EAGAIN错误(参考man send),同时,不理会这次请求发送的数据.所以,需要封装socket_send的函数用来处理这种情况,该函数会尽量将数据写完再返回,返回-1表示出错。在socket_send内部,当写缓冲已满(send返回-1,且errno为EAGAIN),那么会等待后再重试.这种方式并不很完美,在理论上可能会长时间的阻塞在socket_send内部,但暂没有更好的办法. ssize_t socket_send(int sockfd, const char* buffer, size_t buflen) { ssize_t tmp; size_t total = buflen; const char *p = buffer; while(1) { tmp = send(sockfd, p, total, 0); if(tmp < 0) { // 当send收到信号时,可以继续写,但这里返回-1. if(errno == EINTR) return -1; // 当socket是非阻塞时,如返回此错误,表示写缓冲队列已满, // 在这里做延时后再重试. if(errno == EAGAIN) { usleep(1000); continue; } return -1; } if((size_t)tmp == total) return buflen; total -= tmp; p += tmp; } return tmp; } 二、epoll在LT和ET模式下的读写方式 在一个非阻塞的socket上调用read/write函数, 返回EAGAIN或者EWOULDBLOCK(注: EAGAIN就是EWOULDBLOCK) 从字面上看, 意思是: * EAGAIN: 再试一次 * EWOULDBLOCK: 如果这是一个阻塞socket, 操作将被block * perror输出: Resource temporarily unavailable 总结: 这个错误表示资源暂时不够, 可能read时, 读缓冲区没有数据, 或者, write时,写缓冲区满了 。 遇到这种情况, 如果是阻塞socket, read/write就要阻塞掉。 而如果是非阻塞socket, read/write立即返回-1, 同 时errno设置为EAGAIN. 所以, 对于阻塞socket, read/write返回-1代表网络出错了. 但对于非阻塞socket, read/write返回-1不一定网络真的出错了. 可能是Resource temporarily unavailable. 这时你应该再试, 直到Resource available. 综上, 对于non-blocking的socket, 正确的读写操作为: 读: 忽略掉errno = EAGAIN的错误, 下次继续读 写: 忽略掉errno = EAGAIN的错误, 下次继续写 对于select和epoll的LT模式, 这种读写方式是没有问题的. 但对于epoll的ET模式, 这种方式还有漏洞. epoll的两种模式 LT 和 ET
-
Java 类加载器的作用 - 简介:类加载器是 Java™ 中一个非常重要的概念。类加载器负责将 Java 类的字节码加载到 Java 虚拟机中。本文首先详细介绍了 Java 类加载器的基本概念,包括代理模型、加载类的具体过程和线程上下文类加载器等。然后介绍了如何开发自己的类加载器,最后介绍了类加载器在 Web 容器和 OSGi™ 中的应用。 类加载器是 Java 语言的一项创新,也是 Java 语言广受欢迎的重要原因之一。它允许将 Java 类动态加载到 Java 虚拟机中并执行。类加载器从 JDK 1.0 开始出现,最初是为了满足 Java Applets 的需求而开发的,Java Applets 需要从远程位置下载 Java 类文件并在浏览器中执行。现在,类加载器已广泛应用于网络容器和 OSGi。一般来说,Java 应用程序的开发人员不需要直接与类加载器交互;Java 虚拟机的默认行为足以应对大多数情况。但是,如果遇到需要与类加载器交互的情况,而您又不太了解类加载器的机制,就很容易花费大量时间调试异常,如 ClassNotFoundException 和 NoClassDefFoundError。本文将详细介绍 Java 的类加载器,帮助读者深入理解 Java 语言中的这一重要概念。下面先介绍一些基本概念。 类加载器的基本概念 顾名思义,类加载器用于将 Java 类加载到 Java 虚拟机中。一般来说,Java 虚拟机以如下方式使用 Java 类:Java 源程序(.java 文件)经 Java 编译器编译后转换为 Java 字节代码(.class 文件)。类加载器负责读取 Java 字节代码并将其转换为 java.lang 实例。每个实例都用来表示一个 Java 类。通过该实例的 newInstance 方法创建该类的对象。实际情况可能更加复杂,例如,Java 字节代码可能是由工具动态生成或通过网络下载的。 基本上,所有类加载器都是 java.lang.ClassLoader 类的实例。下面将详细介绍这个 Java 类。 java.lang.ClassLoader 类简介 java.lang.ClassLoader 类的基本职责是根据给定类的名称为其查找或生成相应的字节码,然后根据这些字节码定义一个 Java 类,即 java.lang.Class 类的实例。除此之外,ClassLoader 还负责加载 Java 应用程序所需的资源,如图像文件和配置文件。不过,本文只讨论它加载类的功能。为了履行加载类的职责,ClassLoader 提供了许多方法,其中比较重要的方法如表 1 所示。下文将详细介绍这些方法。 表 1.与加载类相关的 ClassLoader 方法
-
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)
-
深入理解并实战演示 C++ 优先级队列 priority_queue 的工作原理与实现
-
C++中的栈(Stack)与队列(Queue):理解这两种基本数据结构
-
C++编程:实战教程 - 实现栈与队列(Deque) 容器适配器,探讨Stack和Queue的实现及Queueue(Deque)的问题。深入理解:如何模拟实现Priority Queue (优先级队列) - 实例与解题,以及仿射函数入门(第一部分)
-
C++编程:深入理解编译与链接的基本原理
-
深入理解:C++中数据共享与保护的静类成员详解 - 📖关于类的静态成员在实践中的协作与安全考量
-
深入理解机器学习(3):KNN算法详解与C++实战实现 - K近邻算法的三个关键元素
-
第二章:深入理解Linux编程 - 进程工作原理:剖析进程定义与特性、状态转换、关键数据结构、从创建到结束的过程、睡眠与唤醒机制、暂停与重启操作,以及处理器调度的核心概念