并发：互斥与信号量
 
一、关键术语
 
       1原子操作：一个或多个指令的序列，对外是不可分的；即没有其他进程可以看到其中间状态或者中断此操作。
 
       2.临界区（critical section）：是一段代码，在这段代码中进程将访问资源；只能有一个进程在此段代码中运行。
 
       3.互斥（mutual exclusion）：当一个进程在临界区访问共享资源时，其他进程不能进入临界区访问任何资源。
 
 
 
二、互斥
 
       1.为什么要互斥：因为当多个进程同时运行在临界区对共享资源进行操作时，可能会导致得到非预期结果。
 
       2.互斥的实现
 
       2.1硬件方法
 
              2.1.1 中断禁用
 
                     在单处理器机器中，并发进程只能串行执行，所以只要禁止对临界区的中断即可保证互斥。
 
       缺点：导致效率降低；不能用于多处理器机器。
 
              2.1.2 专用机器指令
 
                     设计专门的指令，保证指令执行是原子的。
 
              1）.比较和交换指令
 
                     intcompare_and_swap(int &word, int testval, int newval)
 
                     {
 
                            intoldval=word;
 
                            if(old==testval)word=newval;
 
                            returnoldval;
 
                     }
 
                     compare_and_swap是机器指令，在执行期间不会被中断。
 
                     //***
 
                     while(compare_and_swap(a,0,1)==1);       //初始化a=0
 
                     //临界区
 
                     a=0;
 
                     //***
 
                     第一个进程执行时，a=0，指令返回0，所以进程进入临界区，然后a=1,其他进程无法进入临界区。
 
              缺点：使用了忙等待，无法进入临界区的进程一直在执行指令，消耗CPU时间。
 
       
 
              2.1.3 信号量(semaphore)
 
                     信号量是进程间传递信号的一个整数值。只能进行三种操作，初始化、递减和增加。
 
       1）一个信号量S可以被初始化为非负整数
 
       2）Wait(s)操作使S减1。如果S变成负数，则将执行Wait的进程阻塞，放进S的等待队列中。如果S为正，则继续执行（进入临界区）
 
       3）Signal(s)使S增加1。如果S小于等于0，则说明在S的等待队列中有进程被阻塞，所以将其中一个进程解除阻塞。
 
 
 
开始时，S被初始化为正数，S等于能同时进入临界区的解除进程数，当进入临界区的进程数超过初始值后，执行Wait()的进程进入等待队列，并阻塞（避免了忙等待），S值小于0，其绝对值|s|等于等待队列中进程数。
 
 
 
信号量的实现：
 
       因为信号量也是共享资源，对其操作也需要互斥，可以用cmp&swap实现。
 
如：
 
Wait(s)
 
{
 
       while(compare_and_swap(s.flag,0,1)==1);   
 
       s.count--;
 
       if(s.count<0)
 
       {     //阻塞该进程 s.flag=0
 
       }
 
       s.flag=0;//让其他进程通过while
 
}
 
Signal类似。
 
这里也需要忙等待，但是这里忙等待的对象是Wait和Signal，他们的操作相对于临界区来说很短，所以开销可以接受。
 
 
 
总结：
 
       比如临界区C是厕所，信号量S表示同时能进厕所的人数。
 
不使用信号量时：
 
 
第一个人进入C后，其他人只能在外面等待，并且不断询问里面的人好了没。
 
 
 
使用信号量：
 
       
 
增加了房间S和B，要上厕所时，先到S里面那C的钥匙（信号量的初始值即为钥匙总量），拿到的进入C，拿不到的进入B休息室（阻塞）。S每次也只能通过一个人，其他人也需要在S外面忙等待，但通过S的时间远小于C，所以等待时间不长。从C出来后，如果B中有人，就将钥匙给B中的人，即当s.count<=0是解除阻塞进程。
 
 
 
参考资料：操作系统：精髓与设计原理（原书第六版）

0、信号量机制
 
信息量其实就是一个变量（一个整数，也可以是更复杂的记录变量），可以用一个信号量表示系统中某种资源的数量。比如：系统中只有一台打印机，就可以设置为1的信号量
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而实现进程互斥，进程同步
一对原语：wait(s) 和 signal(s) 简称P、V 操作（来自荷兰语proberen,verhogen）
**原语：**是一种特殊的程序，最接近底层硬件，其执行操作只能一气呵成，不能被中断。是由关中断 /
 开中断指令实现的。软件解决方案的主要问题就是进入区的操作不能一气呵成，因此把进入区、退出区的操作都用原语来实现，就能避免问题
 
1、整型信号量
 
 
2、记录型信号量
 
 
例子：
 
 
1、p0执行，wait操作s.value–,剩余资源1，切换p1 等待队列 null
 
2、p1执行，wait操作s.value–,剩余资源0，切换p2 等待队列 null
 
3、p2执行，wait操作s.value–,剩余资源-1表示有1进程等待，执行wait里block操作进入等待队列 等待队p2
 
4、p3执行，wait操作s.value–,剩余资源-2表示有2进程等待，执行wait里block操作进入等待队列 等待队p2->p3
 
5、p0执行，signal操作s.value++,剩余资源<0表示有进程等待，执行signal里wakeup操作唤醒等待队列队头p2进程 等待队列p3
 
6、p2执行，signal操作s.value++,剩余资源<0表示有进程等待，执行signal里wakeup操作唤醒等待队列队头p3进程 等待队列null
 
7、p1执行，signal操作s.value++,剩余资源1 等待队列null
 
8、p3执行，signal操作s.value++,剩余资源2 等待队列null
 
解析：
 
 
二、信号机制实现进程互斥
 
当没有进程在临界区时，任意一个进程要进入临界区执行P操作，把mutex–,然后进入临界区
 
而当有进程存在于临界区时，mutex的值为0，再有进程要进临界区，执行p操作将会被阻塞，直至在临界区中的进程推出这样便实现了临界区的互斥
 
 
三、信号机制实现进程同步
 
进程同步：让各并发进程按要求有序地推进
 
 
简单总结：
 
同步问题中，信号量设为0，如果某个行为要用到某种资源，那么就再那个行为前面p那种资源，如果某个行为会提供某种资源，就再那个行为后面v那种资源（前操作之后V,后操作之前P）
互斥问题：信号量设为1,P、V操作要仅仅夹着使用互斥资源的那个行为（临界区），中间不能有其他冗余代码
 
四、信号机制实现前驱关系
 

目录
 
1.总览
 
2.信号量机制实现进程互斥
 
3.信号量机制实现进程同步
 
 4.信号量机制实现前驱关系
 
5.小结
 

1.总览
 
 
2.信号量机制实现进程互斥
 
 
3.信号量机制实现进程同步
 
 
 4.信号量机制实现前驱关系
 
 
5.小结
 

实验5 利用信号量实现进程互斥 
 【实验目的】
 （1） 理解互斥概念、信号量机制及信号量结构；
 （2） 掌握信号量的使用方法；
 （3） 掌握PV操作的定义；
 （4） 掌握PV操作实现互斥的方法。
 【实验原理/实验基础知识】
 一、 互斥
 多进程不能同时访问共享的临界资源的现象称为互斥。
 二、 Linux信号量结构
 每一个信号量集由一个sem_array结构来描述，该结构定义在文件/usr/src/linux-2.4/include/linux/sem.h中（若实验使用操作系统为ubuntu，则在以下路径中查找/usr/src/linux-header2.6.32-21/include/linux/sem.h）。
 三、 有关信号量的系统调用函数
 
创建一个新的信号量集或获取一个已经存在的信号量集
 命令格式：int semget(key_t key, int nsems, int semflg)
 返回值：正确时返回信号量集的标识符号，错误时返回-1。
 参数说明：
 
key：信号量集的key值。
 a) 使用IPC_PRIVATE，由系统产生key值并返回标识符，或者返回key值已存在的信号量集的标识符。
 b) 若key值不使用IPC_PRIVATE，而是由用户指定一个非0的整型数值，则对信号量集的打开或存取操作依赖于semflag参数的取值。
nsems：指定打开或者新创建的信号量集将包括的信号量的数目。如果该key值的信号量集已存在，而semflg只指定IPC_CREAT标志，那么参数nsems必须与原来的值一致，否则也会返回错误信息。该参数最大值在linux/sem.h中定义如下。
 #define SEMMSL 250 /* <= 8000 */
semflg：当key值不为IPC_PRIVATE时使用。
 a) 若只设置semflag的IPC_CREAT位，则创建一个信号量集，如果该信号量集已经存在，则返回其标识符号。
 b) 若设置semflag的IPC_CREAT|IPC_EXCL位，则创建一个新的信号量集，如果该key值的信号量集已经存在，则返回错误信息。
 c) 只设置IPC_EXCL位而不设置IPC_CREAT位没有任何意义。
 
对信号量的P、V操作
 命令格式：int semop（int semid， struct sembuf * sops， unsigned nsops）；
 返回值：正确时返回0，错误时返回-1。
 参数说明：
 （1） semid：信号量集的标识符号，由semget（）得到。
 （2） sops：指向一个sembuf结构数组，该数组的每个元素对应一次信号量操作。其sembuf数据结构如下。
 struct sembuf
 {
 unsigned short sem_num;
 short sem_op;
 short sem_flg;
 }
 其参数含义如下：
 sem_num：标明是信号量集的第几个元素，第一个信号量为0，第二个信号量为1，依次类推。
 sem_op：确定对信号量采取何种操作，可以为负数、正数、零。
 
sem_op为负数则相当于P操作，从信号量的值中减去sem_op的绝对值：
  差值大于0：表示该进程可以使用临界资源进入临界区；
  差值小于0：在没有指定IPC_NOWAIT的情况下，该进程睡眠，并插入sem_queues等待队列尾部，直到请求的条件得到满足；如果指定了IPC_NOWAIT，则出错返回。
sem_op为正数，此时相当于V操作，把它的值加到信号量中，意味着该进程释放资源。如果是互斥则出临界区，释放临界资源。
sem_op为0，则该进程进入睡眠，直到信号量的值也为0。
 系统会按顺序检查信号量等待队列(sem_pending)中的每一个成员，查看在当前信号量的状态下，其请求的操作是否可以成功，如果可以，则将它从等待队列中唤醒，并插入就绪队列等待调度运行。
 sem_flg：指明操作的执行模式，它有两个标志位。一个是IPC_NOWAIT，指明以非阻塞方式操作信号量。另一个是SEM_UNDO，指明内核为信号量操作保留恢复值。
 （3） nsops：是第二个参数所指向的sembuf结构数组中元素的个数，如果只有一个信号量，则为1。
 实验中使用该系统调用实现P、V操作,使用格式为:
 struct sembuf P,V;
 semop(semid,&P,1);
 semop(semid,&V,1);
 
信号量集的控制函数
 命令格式：int semctl(int semid, int semnum, int cmd, union semun arg);
 返回值：正确时根据cmd的不同返回需要的值或0，错误时返回-1。
 参数说明：
 （1） semid：信号量集的标识符，由semget（）得到。
 （2） semnum：指定semid信号量集的第几个信号量，在撤销信号量集时，此时参数可以默认。
 （3） cmd用于指定操作类别。其取值如下：
  GETVAL:返回semnum指定的信号量的semval域值。
  SETVAL：置信号量semval域值为arg.val。
  GETPID：返回semnum指定的信号量的sempid，即最近对该信号量进行操作的进程ID。
  GETNCNT：返回semncnt。
  GETZNCT：返回semzcnt。
  GETALL：返回所有信号量的值。
  SETALL：通过对arg.arrary更新所有信号量的值。
  IPC_STAT：获取信号量集的sem_array，存入arg.buf。
  IPC_SET：将arg.buf数据结构的sem_perm.uid、sem_perm.gid、sem_perm.mode成员赋给信号量的sem_array结构。
  IPC_RMID：删除指定信号量集。
  IPC_INFO：获取信号量集相关的信息，存放在arg.buf中。
 （4） arg为5种数据的共用体类型semun，该类型在include/linux/sem.h中定义如下：
 union semun
 {
 int val;
 struct semid_ds *buf;
 unsigned short *array;
 struct seminfo *_buf;
 void *_pad;
 };
 
该数据表示int数值时，用于GETVAL、SETVAL或GETPID等设置或获取整型数据的操作。
该数据指向semid_ds（即sem_array）结构数据时，用于IPC_STAT或IPC_SET等针对信号量集进行的操作。
该数据指向unsigned short数组时，用于GETALL或SETALL。
该数据指向seminfo结构时，用于IPC_INFO操作，所指向的seminfo结构在include/linux/sem.h中定义，其定义如下：
 struct seminfo
 {
 int semmap;
 int semmni;
 int semmns;
 int semmnu;
 int semmsl;
 int semopm;
 int semume;
 int semusz;
 int semvmx;
 int semaem;
 };
 上述系统调用使用系列头文件：
 #include<sys/types.h>
 #inclue<linux/sem.h>
 四、 信号量及其P、V操作的实现方式
 
定义信号量标识符号
 int semid;
定义信号量数据结构
 
定义P、V操作所用的数据结构
 struct sembuf P,V;
定义给信号量赋初值的参数数据结构
 union semun arg;
 
申请只有一个信号量的信号量集
 semid=semget(IPC_PRIVATE,1,IPC_0666);
 IPC_PRIVATE：可由系统产生key值；
 1：表示信号量集中只有一个信号量；
 IPC_0666：表示操作权限。0666表示任意用户可读可写，只设置semflag的IPC_CREAT位，则创建一个信号量集。
分别对每个信号量semid赋初值
 arg.val=初值;
 semctl(semid,0,SETVAL,arg);
 其中0表示第0个信号量，arg的值由arg.val决定，所以必须事先为arg.val赋值。
定义信号量P操作
 P.sem_num=0;
 P.sem_op=-1;
 P.sem_flg=SEM_UNDO;
定义信号量V操作
 V.sem_num=0;
 V.sem_op=1;
 V.sem_flg=SEM_UNDO;
对信号量semid执行P操作
 semop(mutexid,&P,1);
对信号量semid执行V操作
 semop(mutexid,&V,1);
撤销信号量
 semctl(semid,IPC_REID,0);
 信号量非普通变量，对它的赋值操作只能通过semctl(semid,0,SETVAL,arg)进行，其值的修改只能通过P、V操作，而不能使用普通的赋值语句。因此其初值和信号量的P、V操作需要事先定义好后才能在进程中执行。
 【实验环境】VMware Workstation、RedHat
 【实验步骤】
 一、父子进程以非互斥方式共享访问临界资源
 
创建父子进程
父子进程共享一个临界资源,每个进程循环进入该临界区3次。
父进程每次进入临界区后显示“parent in”，出临界区显示“parent out”。
 printf(“parent in\n”);
 sleep(1);
 printf(“parent out\n”);
子进程每次进入临界区后显示“child in”，出临界区显示“child out”。
 printf(“child in\n”);
 sleep(1);
 printf(“child out\n”);
观察执行结果。
 #include<stdio.h>标准输入输出函数库
 #include<stdlib.h>是C语言库头文件之一，包含了以下函数：
 1 字符串转换为数字的函数，包括atoi, atof, strtol等。
 2 随机数函数，包括srand, rand等。
 3 内存分配释放函数，如malloc,calloc,realloc,free等。
 4 程序运行控制函数，如exit, abort等。
 5 系统访问相关函数，如printenv, setenv，system等。
 6 常用算法函数，如qsort, bsearch, abs,div等。
 #include<unistd.h>不是c语言的东西，是linux/unix的系统调用，包含了许多U N I X系统服务的函数原型,例如 read，write和getpid函数。unistd.h在unix中类shu似于window中的windows.h!
 #include<sys/types.h>此头文件还包含适当时应使用的多个基本派生类型。尤其是以下类型更为重要：clock_t 表示系统时间（以时钟周期为单位）。　　dev_t 用于设备号。　　off_t 用于文件大小和偏移量。　　ptrdiff_t 是一种带符号整型，用于对两个指针执行减法运算后所得的结果。　　size_t 反映内存中对象的大小（以字节为单位）。　　ssize_t 供返回字节计数或错误提示的函数使用。　　time_t 以秒为单位计时。　　所有这些类型在 ILP32 编译环境中保持为 32 位值，并会在 LP64 编译环境中增长为 64 位值。
 #include<sys/sem.h>是glibc提供的调用接口，#include <linux/sem.h>是系统提供的调用接口，本身不是同一个实现。
 
#include<stdio.h>
 #include<unistd.h>
 #include<stdlib.h>
 #include<sys/types.h>
 #include<linux/sem.h>
 int mutexid;
 int main()
 {
 int chld,i,j;
 while((chld=fork())-1);
 if(chld>0)
 {
 i=1;
 while(i<=3)
 {
 sleep(1);
 printf(“parent in.\n”);
 sleep(1);
 printf(“parent out.\n”);
 i++;
 }
 wait(0);
 exit(0);
 }
 else
 {
 j=1;
 while(j<=3)
 {
 sleep(1);
 printf(“child in.\n”);
 sleep(1);
 printf(“child out.\n”);
 j++;
 }
 exit(0);
 }
 }
 
 
 二、PV操作实现进程互斥。以实验步骤一为基础，增加PV操作，实现父子进程互斥访问临界区。
 （1） 定义与PV操作相关的数据结构；
 （2） 定义信号量，给信号量赋值；
 （3） 定义PV操作；
 （4） PV操作实现进程互斥。 
 （5） 观察执行结果，并与实验步骤一的结果比较。
 #include<unistd.h>
 #include<stdio.h>
 #include<stdlib.h>
 #include<sys/types.h>
 #include<linux/sem.h>
 int mutexid;
 int main()
 {
 int chld,i,j;
 struct sembuf P,V;
 union semun arg;
 untexid = semget(IPC_PRIVATE,1,0666|IPC_CREAT);
 arg.val=1;
 if(semctl(mutexid,0,SETVAL,arg)-1)
 perror(“semctl setval error.”);
 P.sem_num=0;
 P.sem_op=-1;
 P.sem_flg=SEM_UNDO;
 V.sem_num=0;
 V.sem_op=1;
 V.sem_flg=SEM_UNDO;
 while((chld=fork())==-1)
 if(chld>0)
 {
 i=1;
 while(i<=3)
 {
 sleep(1);
 semop(mutexid,&P,1);//进入临界区，执行P操作
 printf(“parent in.\n”);
 sleep(1);
 printf(“parent out.\n”);//出临界区，执行V操作
 semop(mutexid,&V,1);
 i++;
 }
 wait(0);
 semctl(mutexid,IPC_RMID,0);
 exit(0);
 }
 else
 {
 j=1;
 while(j<=3)
 {
 sleep(1);
 semop(mutexid,&P,1);
 printf(“child in.\n”);
 sleep(1);
 printf(“child out.\n”);
 semop(mutexid,&V,1);
 j++;
 }
 exit(0);
 }
 }
 
 
 
 
 【实验报告】
 填写《信息技术学院学生上机实验报告》。
 【思考题】
 （1） 实验步骤一的结果说明什么？
 （2） P、V操作在各进程代码中的位置应该如何处理？