信号量及信号量上的操作是E.W.Dijkstra 在1965年提出的一种解决同步、互斥问题的较通用的方法,并在很多操作系统中得以实现, Linux改进并实现了这种机制。
信号量(semaphore )实际是一个整数,它的值由多个进程进行测试(test)和设置(set)。就每个进程所关心的测试和设置操作而言,这两个操作是不可中断的,或称“原子”操作,即一旦开始直到两个操作全部完成。测试和设置操作的结果是:信号量的当前值和设置值相加,其和或者是正或者为负。根据测试和设置操作的结果,一个进程可能必须睡眠,直到有另一个进程改变信号量的值。
信号量可用来实现所谓的“临界区”的互斥使用,临界区指同一时刻只能有一个进程执行其中代码的代码段。为了进一步理解信号量的使用,下面我们举例说明。
假设你有很多相互协作的进程,它们正在读或写一个数据文件中的记录。你可能希望严格协调对这个文件的存取,于是你使用初始值为1的信号量,在这个信号量上实施两个操作,首先测试并且给信号量的值减1,然后测试并给信号量的值加1。当第一个进程存取文件时,它把信号量的值减1,并获得成功,信号量的值现在变为0,这个进程可以继续执行并存取数据文件。但是,如果另外一个进程也希望存取这个文件,那么它也把信号量的值减1,结果是不能存取这个文件,因为信号量的值变为-1。这个进程将被挂起,直到第一个进程完成对数据文件的存取。当第一个进程完成对数据文件的存取,它将增加信号量的值,使它重新变为1,现在,等待的进程被唤醒,它对信号量的减1操作将获得成功。
上述的进程互斥问题,是针对进程之间要共享一个临界资源而言的,信号量的初值为1。实际上,信号量作为资源计数器,它的初值可以是任何正整数,其初值不一定为0或1。另外,如果一个进程要先获得两个或多个的共享资源后才能执行的话,那么,相应地也需要多个信号量,而多个进程要分别获得多个临界资源后方能运行,这就是信号量集合机制,Linux 讨论的就是信号量集合问题。
1. 信号量的数据结构
Linux中信号量是通过内核提供的一系列数据结构实现的,这些数据结构存在于内核空间,对它们的分析是充分理解信号量及利用信号量实现进程间通信的基础,下面先给出信号量的数据结构(存在于include/linux/sem.h中),其它一些数据结构将在相关的系统调用中介绍。
(1)系统中每个信号量的数据结构(sem)
struct sem {
int semval; /* 信号量的当前值 */
int sempid; /*在信号量上最后一次操作的进程识别号 *
};
(2)系统中表示信号量集合(set)的数据结构(semid_ds)
struct semid_ds {
struct ipc_perm sem_perm; /* IPC权限 */
long sem_otime; /* 最后一次对信号量操作(semop)的时间 */
long sem_ctime; /* 对这个结构最后一次修改的时间 */
struct sem *sem_base; /* 在信号量数组中指向第一个信号量的指针 */
struct sem_queue *sem_pending; /* 待处理的挂起操作*/
struct sem_queue **sem_pending_last; /* 最后一个挂起操作 */
struct sem_undo *undo; /* 在这个数组上的undo 请求 */
ushort sem_nsems; /* 在信号量数组上的信号量号 */
};
(3) 系统中每一信号量集合的队列结构(sem_queue)
struct sem_queue {
struct sem_queue * next; /* 队列中下一个节点 */
struct sem_queue ** prev; /* 队列中前一个节点, *(q->prev) == q */
struct wait_queue * sleeper; /* 正在睡眠的进程 */
struct sem_undo * undo; /* undo 结构*/
int pid; /* 请求进程的进程识别号 */
int status; /* 操作的完成状态 */
struct semid_ds * sma; /*有操作的信号量集合数组 */
struct sembuf * sops; /* 挂起操作的数组 */
int nsops; /* 操作的个数 */
};
(4)几个主要数据结构之间的关系
从7.3图可以看出,semid_ds结构的sem_base指向一个信号量数组,允许操作这些信号量集合的进程可以利用系统调用执行操作 。注意,信号量信号量集合的区别,从上面可以看出,信号量用“sem” 结构描述,而信号量集合用“semid_ds”结构描述,实际上,在后面的讨论中,我们以信号量集合为讨论的主要对象。下面我们给出这几个结构之间的关系,如图7.3所示。
图7.3 System V IPC信号量数据结构之间的关系
Linux对信号量的这种实现机制,是为了与消息和共享内存的实现机制保持一致,但信号量是这三者中最难理解的,因此我们将结合系统调用做进一步的介绍,通过对系统调用的深入分析,我们可以较清楚地了解内核对信号量的实现机制。
2. 系统调用:semget()
为了创建一个新的信号量集合,或者存取一个已存在的集合,要使用segget()系统调用,其描述如下:
原型: int semget ( key_t key, int nsems, int semflg );
返回值: 如果成功,则返回信号量集合的IPC识别号
如果为-1,则出现错误:
semget()中的第一个参数是键值, 这个键值要与已有的键值进行比较,已有的键值指在内核中已存在的其它信号量集合的键值。对信号量集合的打开或存取操作依赖于semflg参数的取值:
IPC_CREAT :如果内核中没有新创建的信号量集合,则创建它。
IPC_EXCL :当与IPC_CREAT一起使用时,但信号量集合已经存在,则创建失败。
如果IPC_CREAT单独使用,semget()为一个新创建的集合返回标识号,或者返回具有相同键值的已存在集合的标识号。如果IPC_EXCL与IPC_CREAT一起使用,要么创建一个新的集合,要么对已存在的集合返回-1。IPC_EXCL单独是没有用的,当与IPC_CREAT结合起来使用时,可以保证新创建集合的打开和存取。
作为System V IPC的其它形式,一种可选项是把一个八进制与掩码或,形成信号量集合的存取权限。
第三个参数nsems指的是在新创建的集合中信号量的个数。其最大值在“linux/sem.h”中定义:
#define SEMMSL 250 /* <= 8 000 max num of semaphores per id */
注意:如果你是显式地打开一个现有的集合,则nsems参数可以忽略。
下面举例说明。
int open_semaphore_set( key_t keyval, int numsems )
{
int sid;
if ( ! numsems )
return(-1);
if((sid = semget( keyval, numsems, IPC_CREAT | 0660 )) == -1)
{
return(-1);
}
return(sid);
}
注意,这个例子显式地用了0660权限。这个函数要么返回一个集合的标识号,要么返回-1而出错。键值必须传递给它,信号量的个数也传递给它,这是因为如果创建成功则要分配空间。
3. 系统调用: semop()
原型: int semop ( int semid, struct sembuf *sops, unsigned nsops);
返回: 如果所有的操作都执行,则成功返回0。
如果为-1,则出错。
semop()中的第一个参数(semid)是集合的识别号(可以由semget()系统调用得到)。第二个参数(sops)是一个指针,它指向在集合上执行操作的数组。而第三个参数(nsop)是在那个数组上操作的个数。
sops参数指向类型为sembuf的一个数组,这个结构在/inclide/linux/sem.h 中声明,是内核中的一个数据结构,描述如下:
struct sembuf {
ushort sem_num; /* 在数组中信号量的索引值 */
short sem_op; /* 信号量操作值(正数、负数或0) */
short sem_flg; /* 操作标志,为IPC_NOWAIT或SEM_UNDO*/
};
如果sem_op为负数,那么就从信号量的值中减去sem_op的绝对值,这意味着进程要获取资源,这些资源是由信号量控制或监控来存取的。如果没有指定IPC_NOWAIT,那么调用进程睡眠到请求的资源数得到满足(其它的进程可能释放一些资源)。
如果sem_op是正数,把它的值加到信号量,这意味着把资源归还给应用程序的集合。
最后,如果sem_op为0,那么调用进程将睡眠到信号量的值也为0,这相当于一个信号量到达了100%的利用。
综上所述,Linux 按如下的规则判断是否所有的操作都可以成功:操作值和信号量的当前值相加大于 0,或操作值和当前值均为 0,则操作成功。如果系统调用中指定的所有操作中有一个操作不能成功时,则 Linux 会挂起这一进程。但是,如果操作标志指定这种情况下不能挂起进程的话,系统调用返回并指明信号量上的操作没有成功,而进程可以继续执行。如果进程被挂起,Linux 必须保存信号量的操作状态并将当前进程放入等待队列。为此,Linux 内核在堆栈中建立一个 sem_queue 结构并填充该结构。新的 sem_queue 结构添加到集合的等待队列中(利用 sem_pending 和sem_pending_last 指针)。当前进程放入 sem_queue 结构的等待队列中(sleeper)后调用调度程序选择其他的进程运行。
为了进一步解释semop()调用,让我们来看一个例子。假设我们有一台打印机,一次只能打印一个作业。我们创建一个只有一个信号量的集合(仅一个打印机),并且给信号量的初值为1(因为一次只能有一个作业)。
每当我们希望把一个作业发送给打印机时,首先要确定这个资源是可用的,可以通过从信号量中获得一个单位而达到此目的。让我们装载一个sembuf数组来执行这个操作:
struct sembuf sem_lock = { 0, -1, IPC_NOWAIT };
从这个初始化结构可以看出,0表示集合中信号量数组的索引,即在集合中只有一个信号量,-1表示信号量操作(sem_op),操作标志为IPC_NOWAIT,表示或者调用进程不用等待可立即执行,或者失败(另一个进程正在打印)。下面是用初始化的sembuf结构进行semop()系统调用的例子:
if((semop(sid, &sem_lock, 1) == -1)
fprintf(stderr,”semopn”);
第三个参数(nsops)是说我们仅仅执行了一个操作(在我们的操作数组中只有一个sembuf结构),sid参数是我们集合的IPC识别号。
当我们使用完打印机,我们必须把资源返回给集合,以便其它的进程使用。
struct sembuf sem_unlock = { 0, 1, IPC_NOWAIT };
上面这个初始化结构表示,把1加到集合数组的第0个元素,换句话说,一个单位资源返回给集合。
4. 系统调用 : semctl()
原型: int semctl ( int semid, int semnum, int cmd, union semun arg );
返回值: 成功返回正数,出错返回-1。
注意:semctl()是在集合上执行控制操作。
semctl()的第一个参数(semid)是集合的标识号,第二个参数(semnn)是将要操作的信号量个数,从本质上说,它是集合的一个索引,对于集合上的第一个信号量,则该值为0。
- cmd参数表示在集合上执行的命令,这些命令及解释如表7.2所示:
- arg参数的类型为semun,这个特殊的联合体在 include/linux/sem.h中声明,对它的描述如下:
/* arg for semctl system calls. */
union semun {
int val; /* value for SETVAL */
struct semid_ds *buf; /* buffer for IPC_STAT & IPC_SET */
ushort *array; /* array for GETALL & SETALL */
struct seminfo *__buf; /* buffer for IPC_INFO */
void *__pad;
};
表7.2 cmd命令及解释
命令 | 解 释 |
IPC_STAT | 从信号量集合上检索semid_ds结构,并存到semun联合体参数的成员buf的地址中 |
IPC_SET | 设置一个信号量集合的semid_ds结构中ipc_perm域的值,并从semun的buf中取出值 |
IPC_RMID | 从内核中删除信号量集合 |
GETALL | 从信号量集合中获得所有信号量的值,并把其整数值存到semun联合体成员的一个指针数组中 |
GETNCNT | 返回当前等待资源的进程个数 |
GETPID | 返回最后一个执行系统调用semop()进程的PID |
GETVAL | 返回信号量集合内单个信号量的值 |
GETZCNT | 返回当前等待100%资源利用的进程个数 |
SETALL | 与GETALL正好相反 |
SETVAL | 用联合体中val成员的值设置信号量集合中单个信号量的值 |
这个联合体中,有三个成员已经在表7-1中提到,剩下的两个成员_buf 和_pad用在内核中信号量的实现代码,开发者很少用到。事实上,这两个成员是Linux操作系统所特有的,在UINX中没有。
这个系统调用比较复杂,我们举例说明。
下面这个程序段返回集合上索引为semnum对应信号量的值。当用GETVAL命令时,最后的参数(semnum)被忽略。
int get_sem_val( int sid, int semnum )
{
return( semctl(sid, semnum, GETVAL, 0));
}
关于信号量的三个系统调用,我们进行了详细的介绍。从中可以看出,这几个系统调用的实现和使用都和系统内核密切相关,因此,如果在了解内核的基础上,再理解系统调用,相对要简单地多,也深入地多。
5. 死锁
和信号量操作相关的概念还有“死锁”。当某个进程修改了信号量而进入临界区之后,却因为崩溃或被“杀死(kill)”而没有退出临界区,这时,其他被挂起在信号量上的进程永远得不到运行机会,这就是所谓的死锁。Linux 通过维护一个信号量数组的调整列表(semadj)来避免这一问题。其基本思想是,当应用这些“调整”时,让信号量的状态退回到操作实施前的状态。
关于调整的描述是在sem_undo数据结构中,在include/linux/sem.h描述如下:
/*每一个任务都有一系列的恢复(undo)请求,当进程退出时,自动执行undo请求*/
struct sem_undo {
struct sem_undo * proc_next; /*在这个进程上的下一个sem_undo节点 */
struct sem_undo * id_next; /* 在这个信号量集和上的下一个sem_undo节点*/
int semid; /* 信号量集的标识号*/
short * semadj; /* 信号量数组的调整,每个进程一个*/
};
sem_undo结构也出现在task_struct数据结构中。
每一个单独的信号量操作也许要请求得到一次“调整”,Linux将为每一个信号量数组的每一个进程维护至少一个sem_undo结构。如果请求的进程没有这个结构,当必要时则创建它,新创建的sem_undo数据结构既在这个进程的task_struct数据结构中排队,也在信号量数组的semid_ds结构中排队。当对信号量数组上的一个信号量施加操作时,这个操作值的负数与这个信号量的“调整”相加,因此,如果操作值为2,则把-2加到这个信号量的“调整”域。
当进程被删除时,Linux完成了对sem_undo数据结构的设置及对信号量数组的调整。如果一个信号量集合被删除,sem_undo结构依然留在这个进程的task_struct结构中,但信号量集合的识别号变为无效。