2009-04-15 08:49:00 Y465993416 阅读数 4981

1  在某展示厅设置一个自动计数系统,以计数器count表示在场的人数,count是动态变化的,若有一个人进入展示厅进程pin对计数器count1,当有一个人退出展示厅时,进程pout实现计数器减1。由于进、出所以展示厅的人是随机的,用P-V操作实现。(并发进程之间的互斥问题)

解:定义信号量:S——表示是否有进程进入临界区,初值为1.(表示没有进程进入临界区)

begin

   count: Integer;

   S: semaphore;

   count:=0;

   S:=1;

cobegin

process Pin

      R1: Integer;

begin

P (S);

R1:=count;

R1:=R1+1;

count:=R1;

V(S);

end;

   Process Pout

      R2: Integer;

begin

P (S);

R2:=count;

R2:=R2-1;

count:=R2;

V (S);

end;

count;

end;

 

 

2  与生产者和消费过者相似的问题,把“A进程将记录送入缓冲器看生产者生产了一件物品且把物品存入缓冲器,把“B进程从缓冲器中取出记录并加工看作是消费者从缓冲器取出物品去消费,缓冲器中只能放一个记录(一件物品),用P-V操作实现。(并发进程之间的同步问题)

解:定义两个信号量为:spsg

sp:表示生产者是否右以把物品存入缓冲器。由于缓冲器只能存放一个物品,因此sp的初值为1,即sp:=1

sg:表示缓冲是否存有物品,它的初值应该为0,即sg=0,表示缓冲器中还没有物品存在。

生产者和消费者两个进程并发执行时,可按以下的方式实现同步:

      sp:=1;sg:=0;

      cobegin

      process producer (生产者进程)

              begin

                 L1:produce a product;

                   P(sp);

                   Buffer:=product;

                   V(sg);

                   goto L1

              end

process consumer(消费者进程)

          begin

            L2: P(sg);

                  Take a product;

                   V(sp);

                   consume;

                   goto L1

              end;

coend;

 

 

3  如果一个生产者和一个消费共享缓冲器容量为可以存放n件物品时,生产者总可继续存入物品;同时当缓冲器的物品不为“0”时,消费者总可从缓冲器中取走物品,用P-V操作实现。(并发进程之间的同步问题)

解:sp:表示生产者是否可以把物品存入,初值为n;(因为,缓冲器的容量为n件物品);

sg:表示缓冲器中是否存有物品,初值为0.

B: away[0:n-1]of integer;

k, t: integer;

k:=0; t:=0; sp:=n; sg:=0;

cobegin

process producer

     begin

     L1:produce a product;

     B[k]:=product;

     k:=(k+1)mod n;

     V(sg);

     goto L1

coend;

process consumer

     begin

     L2:P(sg);

     Tack a product from B[t];

     t:=(t+1)mod n;

     V(sp);

     consume;

     goto:= L2

     end

coend

 

 

4  桌上有一只盘子,每一次放入一个水果,爸爸向盘中放苹果,妈妈向盘中放桔子,一个女儿专吃盘中的苹果,一个儿了专等吃盘中的桔子。试用P-V操作定出他们能同步的流程图。(并发进程之间同步与互斥的混合问题)

解:定义信号量:dish:表明盘子中是否为空,初值为1

Apple:表明盘子中是否有苹果,初值为0

Orange:表明盘子中是否有桔子,初值为0

main ()

{cobegin

   father ();

   mother ();

      son ();

daughter ();

     coend

}

father ()

{ P(dish);

放苹果

V(apple);

}

mother()

{ P(dish);

   …

放桔子

   …

V(orange);

}

son ()

{ P(orange);

   …

取桔子

   …

V(dish);

}

daughter()

{ P(apple);

   …

取苹果

   …

V(dish);

}

 

 

5  设公共汽车上,司机和售票员的活动分别为:司机的活动是启动车辆、正常开驶、到站停车;售票员的活动是关门、售票、开门。试指出在汽车出站、行驶、到站过程中,述两种活动有什么同步关系?P-V操作实现它们之间的同步关系。(并发进程之间的同步问题)

解:司机启动车辆与售票员关车门为同步关系;

      司机到站停车与售票员开车门为同步关系。

定义两个信号量: S1——表示门是否关了,初始值为0

S2——表示汽车是否到站,初始值为0

main()

{cobegin

     Process司();

     Process售();

   coend

}

Process司()

{ P(S1);

    启动;

    行驶;

    到站停车;

    V(S2);

   }

Process售()

{ 关车门;

    VS1;

    售票;

    PS2);

    开车门;

   }

 

 

6  多个进程共享一个文件,其中写文件的称为写者,读文件的称为读者,写者与写者、写者与读者之间要互斥地访问文件,读者之间可同时读,试用P-V操作实现它们之间的关系。(进程之间的互斥问题)

解:定义变量:count:表现当前读者个数,初值为0

              mutex:用来对共享变量count进行互斥访问,初值为1

              write:用来使写者与写者,写者与读者之间互斥访问文件,初值为1.

semaphone mutex:=1;

    semaphone write:=1;

    int count:=0;

    main()

    {cobegin

       Reader();

       Writer();

     coend

    }

   Reader()

   {while(true)

    {P(mutex);

      if(count==0)

      p(write)

      count++;

      V(mutex);

       读文件;

      P(mutex);

      count--;

      if(count==0) V(write)

       V(mutex);

     }

    }

   writer()

   {while(true)

    {P(write);

     写文件;

     V(write);

   }}

 

 

7  有一个阅览室,共有100个座位,读者进入时必须先在一张登记表上登记,该表为每一座位列一表目,包括座号和读者姓名等,读者离开时要消掉登记的信息,试问:

(1)       为描述读者的动作,应编写几个程序,设置几个进程?

(2)       试用PV操作描述读者进程之间的同步关系。

答:读者的动作有两个,一是填表进入阅览室,这时要考虑阅览室里是否有座位;一是读者阅读完毕,离开阅览室,这时的操作要考虑阅览室里是否有读者。读者在阅览室读书时,由于没有引起资源的变动,不算动作变化。

算法的信号量有三个:seats——表示阅览室是否有座位(初值为100,代表阅览室的空座位数);readers——表示阅览室里的读者数,初值为0;用于互斥的mutex,初值为1

读者进入阅览室的动作描述getin

while(TRUE){

P (seats);                                     /*没有座位则离开*/

Pmutex                                  /*进入临界区*/

填写登记表;

进入阅览室读书;

Vmutex                                  /*离开临界区*/

Vreaders 

}

 

读者离开阅览室的动作描述getout

while(TRUE){

Preaders                                   /*阅览室是否有人读书*/

Pmutex                                   /*进入临界区*/

消掉登记;

离开阅览室;                               

Vmutex                                  /*离开临界区*/

Vseats                                   /*释放一个座位资源*/

}

 

 

8  UNIX文件系统中的目录结构如下图所示:

                         ¡

 

       ¡     ¡     ¡  ¡        ¡        ¡      ¡       ¡ usr

      bin    dev    etc    lib    lost+found    mnt    tmp             

                                                         ¡ mengqc    ¡ liu

                                                                       

                                                  sub1¡               

                                                                          

                                                        m1.c  m2.c

                                                    

                                                  file_a

(1)     设当前工作目录是/usr,那么,访问文件file_a的绝对路径名和相对路径名各是什么?

(2)     现在想把工作目录改到liu,应使用什么命令(写出完整命令行)?

(3)     如果用  ls  –l  /usr/mengqc命令列出指定目录的内容,其中有如下所示的一项:

      - r w – r - - - - -    2     mengqc   ……       m2.c

那么,该文件m2.c对文件主、同组用户、其他用户分别规定了什么权限?

: (1) 访问文件file_a的绝对路径名是: /usr/mengqc/sub1/file_a

  访问文件file_a的相对路径名是: mengqc/sub1/file_a

(2) cd  /usr/liu    或者   cd  liu

(3) 文件主权限是: 可读、可写,但不可执行

              同组用户权限是:只可读

                  其他用户权限是:无(即:不能读、写或执行)

 

 

9  设公共汽车上有一位司机和一位售票员,它们的活动如下:

 

司机:                             售票员:

启动车辆                                售票

                    正常行车                               开车门

                    到站停车                               关车门

 

请分析司机与售票员之间的同步关系,如何用PV操作实现。

答:为了安全起见,显然要求:关车门后才能启动车辆;到站停车后才能开车门。所以司机和售票员在到站、开门、关门、启动车辆这几个活动之间存在着同步关系。用两个信号量S1S2分别表示可以开车和可以开门,S1的初值为1S2的初值为0PV操作实现司机进程和售票员进程同步的算法描述如下:

司机:                             售票员:

 PS1                                售票

启动车辆                                PS2

                    正常行车                                开车门

                    到站停车                                关车门

                     VS2                                VS1

 

另外,程序中PV操作出现的顺序与信号量的初值设置有关,以本题为例,算法如下描述时,S1S2的初值均应为0

司机:                             售票员:

正常行车                                售票

到站停车                                PS2

                    VS2                                开车门

                    PS1                                 关车门

                    启动车辆                                VS1

 

 

 

10  现有一个作业,在段式存储管理的系统中已为其主存分配,建立的段表内容如下:

段号

主存起始地址

段长度

0

120

40

1

760

30

2

480

20

3

370

20

       计算逻辑地址(215),(060),(318)的绝对地址是多少?

(注:括号中第一个元素为段号,第二个元素为段内地址。)   

 

答:段式存储管理的地址转换过程为:(1)根据逻辑地址中的段号查段表的相应栏目;(2)根据段内地址<段长度,检查地址是否越界;(3)若不越界,则绝对地址=该段的主存起始地址+段内地址。

逻辑地址(215)查段表得段长度为20,段内地址15<20,地址不越界,段号2查表得段首地址为480,于是绝对地址为480+15=495

逻辑地址(060)查段表得段长度为40,段内地址60>40,地址越界,系统发出“地址越界”中断。

逻辑地址(318)查段表得段长度为20,段内地址18<20,地址不越界,段号3查表得段首地址为370,于是绝对地址=370+18=388

 

 

 

 

11  某段表内容如下:

段号

段首地址

段长度

0

120K

40K

1

760K

30K

2

480K

20K

3

370K

20K

        一逻辑地址为(2154)的实际物理地址为多少?

答:逻辑地址(2154)表示段号为2,即段首地址为480K154为单元号,则实际物理地址为480K+154

 

 

12  考虑下述页面走向:

        12342156212376321236

当内存块数量分别为3时,试问FIFOLRUOPT这三种置换算法的缺页次数各是多少?

答:缺页定义为所有内存块最初都是空的,所以第一次用到的页面都产生一次缺页。

当内存块数量为3时:

   FIFO    12342156212376321236

        1  1  1  4     4  4  6  6  6     3  3  3     2  2     2  6

           2  2  2     1  1  1  2  2     2  7  7     7  1     1  1

              3  3     3  5  5  5  1     1  1  6     6  6     3  3

发生缺页中断的次数为16

FIFO算法中,先进入内存的页面被先换出。当页6要调入时,内存的状态为415,考查页6之前调入的页面,分别为5124,可见4为最先进入内存的,本次应换出,然后把页6调入内存。

   LRU    12342156212376321236

           1  1  1  4     4  5  5  5  1     1  7  7     2  2        2

              2  2  2     2  2  6  6  6     3  3  3     3  3        3

                 3  3     1  1  1  2  2     2  2  6     6  1        6

发生缺页中断的次数为15

LRU算法中,最近最少使用的页面被先换出。当页6要调入时,内存的状态为521,考查页6之前调入的页面,分别为512,可见2为最近一段时间内使用最少的,本次应换出,然后把页6调入内存。

   OPT    12342156212376321236

           1  1  1  1        1  1           3  3        3  3        6

              2  2  2        2  2           2  7        2  2        2

                 3  4        5  6           6  6        6  1        1

发生缺页中断的次数为11

OPT算法中,在最远的将来才被访问的页面被先换出。当页6要调入时,内存的状态为125,考查页6后面要调入的页面,分别为212,可见5为最近一段时间内使用最少的,本次应换出,然后把页6调入内存。

 

 

13  下表给出作业l23的提交时间和运行时间。采用先来先服务调度算法和短作业优先调度算法,试问作业调度次序和平均周转时间各为多少?(时间单位:小时,以十进制进行计算。)

作业号

提交时间

运行时间

1

2

3

0.0

0.4

1.0

8.0

4.0

1.0

提示: 采用先来先服务调度算法,是按照作业提交的先后次序挑选作业,先进入的作业优先被挑选。采用短作业优先调度算法,作业调度时根据作业的运行时间,优先选择计算时间短且资源能得满足的作业

另外,要记住以下公式:

作业i的周转时间Ti作业完成时间-作业提交时间

系统中n个作业的平均周转时间 ,其中Ti为作业i的周转时间。

采用先来先服务调度策略,则调度次序为l23

作业号  提交时间       运行时间       开始时间       完成时间         周转时间

1           0.0                   8.0                0.0                8.0                  8.0

2           0.4                   4.0                8.0             12.0                11.6

3           1.0                   1.0                      12.0                 13.0               12.0

平均周转时间T=(811.612/310.53

采用短作业优先调度策略,则调度次序为l32

作业号 提交时间           运行时间           开始时间           完成时间           周转时间

1           0.0                  8.0                      0.0                      8.0                      8.0

3           1.0                       1.0               8.0                9.0                8.0

2                 0.4               4.0                     9.0                      13.0                 12.6

平均周转时间T=(8812.6/39.53

 

 

14   在一个单道的程序设计系统中,有3个作业J1J2J3,它们到达输入井的时间分别为850900930,它们需要执行的时间分别为1.5小时、0.4小时、1小时。系统在1000按响应比高者优先算法对它们进行调度,请回答:(1)作业被选中执行的次序是什么?

2)三个作业被选中时的响应比分别是多少?

提示: 响应比=作业周转时间/作业运行时间=1+作业等待时间/作业运行时间

系统在1000,计算作业的响应比:

J1为例,它的作业计算时间是1.5小时,即90分钟;J1850到达输入井,在1000时刻,J1的等待时间为70分钟,因此作业J1的响应比为:170分钟/90分钟=1.77  

同理,J2160分钟/24分钟=3.5    J3130分钟/60分钟=1.5

因此按照响应比高者优先算法,优先调度J2

1024J2完成。这时计算J1J3的响应比:

J11+(7024)分钟/90分钟=2.04    J31+(3024)分钟/60分钟=1.9  

按照响应比高者优先算法,优先调度J1

1154J1完成,系统调度J3J3的响应比为1+(302490)分钟/60分钟=3.4 因此,作业被选中执行的次序是J2J1J3

三个作业被选中时的响应比分别是:J12.04J23.5J33.4

 

 

2016-12-28 19:17:22 yangkuiwu 阅读数 4020

题目:在一个盒子里,混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开,设分拣系统有二个进程P1 和P2 ,其中P1 拣白子;P2 拣黑子。规定每个进程每次只拣一子;当一个进程在拣时,不允许另一个进程去拣;当一个进程拣了一子时,必须让另一个进程去拣。试写出两进程P1 和P2 能并发正确执行的程序。

 

分析:

PV操作的题,也就是与信号量处理相关的问题,对于学生而言,一般是比较棘手的。不知道该如何入手。一般而言,主要是上课听课不认真,另外就是没有做过练习题造成的。

信号量,说白了,就是生活中的一个标志。比如火车上的卫生间,为了防止大家误入,卫生间门上有个标志,进去了的人将标志设为“有人”,出来以后再设置为“无人”,大家约定,看到“有人”就不能进入,否则就可以进入。如果大家都遵守这个约定,那么就不会多个人一同进去了。“有人”“没人”就可以在计算机中用0和1来表示。卫生间进人,需要将“没人”变成“有人”,实际上就是将1变成0。人从卫生间出来,需要将“有人”变成“没人”,就是将0变成1。  好了,将1变成0,我们用P来表示(减一),将0变成1我们用V来表示(加一),P V操作就有了。

解决PV的习题,就是要想办法设置好这个标志,然后对标志进行加减操作。

 

解答:

思路一:

捡棋子,这个问题的关键就在于,我捡完了你捡,你捡完了我捡,不能连续捡。如果让两个进程在盒子里捡,那么很明显,我们要设置两个标志F1,F2。F1=1表示P1可以捡,F2=1表示P2可捡,另外P1,P2要约定好,某个进程准备捡的时候要先将自己的标志置0,捡完了,要把对方的标志置1。这样就可以防止两次连续进入了。

 

因此设置信号量:F1=0,F2=1(哪个为0,哪个为1无所谓)。

P1

P(F1)

   捡白子

V(F2

 

P2

P(F2)

   捡黑子

V(F1

 

 

 思路二:

设置信号量s=1,代表盒子,盒子同一时刻只能有一个进程访问

设置信号量k=1,代表刚刚P1操作过。如果k=0,代表P2刚刚操作过。

P1

P(s)

If(k=1

{ 什么都不做}

else

   {捡白子,k=1}

V(s

 

P2

P(s)

If(k=0

{ 什么都不做}

else

   {捡白子,k=0}

V(s

 

 

思路二也是对的,程序也可以正确运行。但是相比思路一,思路二程序的效率肯定不高。

因此PV操作的答案是不唯一的。都可能对,且保证不出错,但是效率的高不高可不一定。

老羊快跑,欢迎关注。

2019-04-14 01:16:38 xhy1999 阅读数 99

前言:这次操作系统课上老师介绍了信号量同步机制,并且给我们留了实践作业,在此记录一下比较具有代表性的实践作业。

题目:将共享内存中的例子中加入信号量机制,从而使得每个写入共享内存的信息读且只被读一次。

分析:在例题中老师已经给我们实现了共享内存,因此这道题本质上就是让我们自己实现信号量机制,然后在读取和写入共享内存时使用P、V操作即可。

在这里我就不对信号量进行过多的描述,直接开始分析我的核心代码。

(1).sem头文件

在此文件中主要用来实现信号量的初始化,删除和PV操作。

头文件和要实现的方法:

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <unistd.h>

void init_sem(int, int);
void del_sem(int);
void sem_p(int);
void sem_v(int);

信号量的union semum结构:

union semun {    		    //信号量
    int val;		    //值
    //struct semid_ds *buf;
    //unsigned short *array;
};

初始化信号量函数:

void init_sem(int id, int val) {
    union semun sem;
    sem.val = val;
    if (semctl(id, 0, SETVAL, sem) < 0) {
	fprintf(stderr, "init failed:%s\n", strerror(errno));
	exit(-1);
    }
}

其中用到了semctl()函数,该函数可以直接控制信号量信息。也就是直接删除信号量或者初始化信号量。

原型:int semctl(int semid,int semnum,int cmd, /*union semun arg*/);

参数:

  int semid        //信号量(集)的标识符,可通过semget获取。

  int semnum   //要给该信号量集中的第semnum个信号量设置初值。

  int cmd     //通常用SETVAL/GETVAL设置和获取信号量集中的一个单独的信号量。

       参数cmd中可以使用的命令如下:
                         ·IPC_STAT读取一个信号量集的数据结构semid_ds,并将其存储在semun中的buf参数中。
                         ·IPC_SET设置信号量集的数据结构semid_ds中的元素ipc_perm,其值取自semun中的buf参数。
                         ·IPC_RMID将信号量集从内存中删除。
                         ·GETALL用于读取信号量集中的所有信号量的值。
                         ·GETNCNT返回正在等待资源的进程数目。
                         ·GETPID返回最后一个执行semop操作的进程的PID。
                         ·GETVAL返回信号量集中的一个单个的信号量的值。
                         ·GETZCNT返回正在等待完全空闲的资源的进程数目。
                         ·SETALL设置信号量集中的所有的信号量的值。
                         ·SETVAL设置信号量集中的一个单独的信号量的值。

        第四个参数arg代表一个semun的实例。semun是在linux/sem.h中定义的:

union semun {
    int val;                     //信号量初始值(通常有他就够了)
    struct semid_ds *buf;        //在IPC_STAT/IPC_SET中使用,代表了内核中使用的信号量的数据结构
    unsigned short int *array;   //使用GETALL/SETALL命令时使用的指针
    struct seminfo *__buf;       //IPC_INFO的缓冲区
}; 

返回值:
                  成功执行时,则为一个正数;
                  如果失败,则返回-1,errno被设为以下的某个值:
                        EACCES(权限不够)
                        EFAULT(arg指向的地址无效)
                        EIDRM(信号量集已经删除)
                        EINVAL(信号量集不存在,或者semid无效)
                        EPERM(EUID没有cmd的权利)
                        ERANGE(信号量值超出范围)

删除信号量的函数:

void del_sem(int id) {
    union semun sem;
    if (semctl(id, 0, IPC_RMID, sem) < 0) {	    //(第三个参数即为删除操作)
	fprintf(stderr, "delete failed:%s\n", strerror(errno));
        exit(-1);
    }
}

P操作函数:

void sem_p(int id) {
    struct sembuf sb;
    //sb = {0, -1, 0};		        //两种赋值方式
    sb.sem_num = 0;                         //信号在信号集中的索引
    sb.sem_op = -1;                         //操作类型
    sb.sem_flg = 0;                         //操作标志
    if (semop(id, &sb, 1) < 0) {		//系统调用(此函数具有原子性)
	printf("failed to execute P (id:%d)\n", id);
	fprintf(stderr, "failed to execute P:%s\n", strerror(errno));
	exit(-1);
    }
}

其中用semop()函数来改变信号量的值。

原型:int semop(int semid,struct sembuf *sops,size_t nsops)

参数:

  int semid        //信号量(集)的标识符,可通过semget获取。

       第二个参数sops是指向存储信号操作结构的数组指针,该结构定义在 linux/sem.h中:

struct sembuf {
    unsigned short sem_num;     //信号量编号
    short sem_op;               //信号量操作
    short sem_flg;              //操作标志
};
/*
注意:
    这里的sem_op如果其值为正数,该值会加到现有的信号内含值中。通常用于释放所控资源的使用权;如果sem_op的值为负数,而其绝对值又大于信号的现值,操作将会阻塞,直到信号值大于或等于sem_op的绝对值。
    而sem_flg信号操作标志,可能的选择有两种:
        IPC_NOWAIT:对信号的操作不能满足时,semop()不会阻塞,并立即返回,同时设定错误信息。
        SEM_UNDO : 程序结束时(不论正常或不正常),保证信号值会被重设为semop()调用前的值。这样做的目的在于避免程序在异常情况下结束时未将锁定的资源解锁,造成该资源永远锁定。
*/

       int nsops        //信号操作结构的数量,恒大于或等于1。

返回值:
                  成功执行时,两个系统调用都返回0;
                  如果失败,则返回-1,errno被设为以下的某个值:
                        E2BIG:一次对信号的操作数超出系统的限制
                        EACCES:调用进程没有权能执行请求的操作,并且不具有CAP_IPC_OWNER权能
                        EAGAIN:信号操作暂时不能满足,需要重试
                        EFAULT:sops或timeout指针指向的空间不可访问
                        EFBIG:sem_num指定的值无效
                        EIDRM:信号集已被移除
                        EINTR:系统调用阻塞时,被信号中断
                        EINVAL:参数无效
                        ENOMEM:内存不足
                        ERANGE:信号所允许的值越界

V操作函数(同上,仅需把sem_op设置为1即可):

void sem_v(int id) {
    struct sembuf sb;
    //sb = {0, 1, 0};
    sb.sem_num = 0;
    sb.sem_op = 1;
    sb.sem_flg = 0;
    if (semop(id, &sb, 1) < 0) {
	printf("failed to execute V (id:%d)\n", id);
	fprintf(stderr, "failed to execute V:%s\n", strerror(errno));
	exit(-1);
    }
}

(2).reader部分

首先,通过semget函数获得semid,然后初始化信号量:

if ((semid = semget(key, 1, IPC_CREAT | 0666)) < 0) {
    perror("failed to semget");
    exit(-1);
}
init_sem(semid, 0);

原型:int semget(key_t key, int nsems, int semflg)

参数:

  key_t key        //所创建或打开信号量集的键值。

  int nsems        //创建的信号量集中的信号量的个数,需要注意的是,该参数只在创建信号量集时有效。

  int semflg        //调用函数

返回值:
                  成功执行时,返回信号量集的IPC标识符。
                  如果失败,则返回-1,errno被设为以下的某个值:
                        EACCES:没有访问该信号量集的权限
                        EEXIST:信号量集已经存在,无法创建
                        EINVAL:有下面两种可能:
                                         1.参数nsems的值小于0或者大于该信号量集的限制
                                         2.该key关联的信号量集已存在,并且nsems大于该信号量集的信号量数
                        ENOENT:信号量集不存在,同时没有使用IPC_CREAT
                        ENOMEM :没有足够的内存创建新的信号量集
                        ENOSPC:超出系统限制

然后,我们就可以实现程序的主体部分:

while (1) {
    sem_p(semid);                    //在读之前必须要求信号量大于0(即写过数据)
    strncpy(buf1, shmaddr1, SIZE);   //读出数据
    printf(" read :  %s\n", buf1);
}

当然,这样写是有很大问题的,我后面会做说明。

(3).writer部分(初始化部分同reader部分,此处省略)

主体部分:

for (i = 0; i <= 10; i++) {		//循环发送数据
    buf2[17] = (char)('0' + i);
    strncpy(shmaddr2, buf2, SIZE);	//写入数据
    printf("write  %d :  %s\n", i, buf2);
    sem_v(semid);			//写完后增加信号量(V操作),使得reader可以读到其中信息
}

同样,这样写是有很大问题的。

(4).运行结果

我的reader只读到了writer发送的最后一个消息,很显然,运行结果有很大的问题,那么问题出在哪里呢?又该怎么解决呢?

(5).解决方法一

思考:首先,我目前的信号量是没有问题的,如果我加信号量有问题的话reader和writer的读写次数会不一样,所以我是否能想出一个办法,使我的reader在writer每次写完数据后能读到数据。

于是,我想到了让writer在每次读完后sleep(1),给reader留足够的时间去读数据,实现起来也很简单,只需在writer的最后部分加上sleep(1)即可。

for (i = 0; i <= 10; i++) {
    buf2[17] = (char)('0' + i);
    strncpy(shmaddr2, buf2, SIZE);
    printf("write  %d :  %s\n", i, buf2);
    sem_v(semid);
    sleep(1);
}

然后让我们运行一下:

这样看貌似没啥问题了哈,但是总感觉有些问题,于是去问了下老师:

呵......(我明明完成题目要求了呀)

但是这样看来sleep()就不能用了(其实我感觉这也有点投机取巧),没办法,在想想看喽。

(6).解决方法二

既然不能sleep(),那我只要让reader和writer不同时运行不就好了吗,所以我只要再加一个信号量(其实从上面运行结果的截图就可以看出来我用了两个信号量),使我的进程互斥即可。

第二个信号量初始化只需要换一个key的值即可(下面以writer为例)

for (i = 0; i <= 10; i++) {
    sem_p(semid2);
    //...原来的代码
    sem_v(semid2);
}

运行结果:

呵...

但是,作为一个热爱学习的人,这怎么能放弃呢?

于是,在我不断的调试过程中我发现,如果把writer写成死循环的话:

咦,这样好像没啥问题,但是原来的运行结果是怎么回事呢......

哎,反正这个方法也不能用(但其实只要稍微改一下代码就是正解)。

(7).解决方法三(正解)

其实早在讲进程的同步问题中,我们就遇到过此类问题,即读者-写者问题,它要求允许多个进程同时读一个共享对象,但不允许writer与其他writer或reader同时访问共享对象。

因此我们只要确保writer写完后,reader才能读;reader读完后,writer才能写即可。

下面附上代码:

writer部分

for (i = 0; i <= 10; i++) {
	sem_p(semid2);	//申请信号量(P操作,初始值为1),使得信息写完(进行P操作)以后才能读
	buf2[17] = (char)('0' + i);
	strncpy(shmaddr2, buf2, SIZE);
	printf("write  %d :  %s\n", i, buf2);
	sem_v(semid);	//写完后增加信号量(V操作),使得reader可以读到其中信息
}

reader部分

while (1) {
    sem_p(semid);     //等信息写完(进行P操作)以后才能读
    strncpy(buf1, shmaddr1, SIZE);
    printf(" read :  %s\n", buf1);
    sem_v(semid2);    //等信息读完(进行V操作)以后才能写
}

这里需要特别注意:semid2的初始值必须为1(必须先要给writer写的权限,不然整个程序没有意义)

最后的运行结果:

这样的话问题就解决了!不容易呀

2010-05-22 15:20:00 do2jiang 阅读数 9076

     2.理发师问题:一个理发店有一个入口和一个出口。理发店内有一个可站5 位顾客的站席区、4 个单人沙发、3 个理发师及其专用理发工具、一个收银台。新来的顾客坐在沙发上等待;没有空沙发时,可在站席区等待;站席区满时,只能在入口外等待。理发师可从事理发、收银和休息三种活动。理发店的活动满足下列条件:
  1)休息的理发师是坐地自己专用的理发椅上,不会占用顾客的沙发;
  2)处理休息状态的理发师可为在沙发上等待时间最长的顾客理发;
  3)理发时间长短由理发师决定;
  4)在站席区等待时间最长的顾客可坐到空闲的理发上;
  5)任何时刻最多只能有一个理发师在收银。
  试用信号量机制或管程机制实现理发师进程和顾客进程。
  原理:
  (1)customer 进程:
  首先检查站席区是否已满(stand_capacity),若满选择离开,否则进入站席区,即进入理发店。在站席区等待沙发的空位(信号量sofa),如果沙发已满,则进入阻塞等待队列,直到出现空位,在站席区中等待时间最长的顾客离开站席区(stand_capacity)。坐到沙发上,等待理发椅(barber_chair),如果理发椅已满,则进入阻塞等待队列,直到出现空位,在沙发上等待时间最长的顾客离开沙发(释放信号量sofa)。坐到理发椅上,释放准备好的信号(customer_ready),获得该理发师的编号(0~1 的数字)。等待理发师理发结束(finished[barber_number])。在离开理发椅之前付款(payment),等待收据(receipt),离开理发椅(leave_barberchair)。最后离开理发店。
  这里需要注意几点:
  a) 首先是几个需要进行互斥处理的地方,主要包括:进入站席区、进入沙发、进入理发椅和付款几个地方。
  b) 通过barber_chair 保证一个理发椅上最多只有一名顾客。但这也不够,因为单凭baber_chair 无法保证一名顾客离开理发椅之前,另一位顾客不会坐到该理发椅上,因此增加信号量leave_barberchair,让顾客离开理发椅后,释放该信号,而理发师接收到该信号后才释放barber_chair 等待下一位顾客。
  c) 在理发的过程中,需要保证是自己理发完毕,才能够进行下面的付款、离开理发椅的活动。这个机制是通过customer 进程获得给他理发的理发师编号来实现的,这样,当该编号的理发师释放对应的finished[i]信号的时候,该顾客才理发完毕。
  d) 理发师是通过mutex 信号量保证他们每个人同时只进行一项操作(理发或者收款)。
  e) 为了保证该顾客理发完毕后马上可以付款离开,就应该保证给该顾客理发的理发师在理
  发完毕后马上到收银台进入收款操作而不是给下一位顾客服务。在伪码中由以下机制实现:即顾客在释放离开理发椅的信号前,发出付款的信号。这样该理发师得不到顾客的离开理发椅的信号,不能进入下一个循环为下一名顾客服务,而只能进入收款台的收款操作。直到顾客接到收据后,才释放离开理发椅的信号,离开理发椅,让理发师释放该理发椅的信号,让下一位等待的顾客坐到理发椅上。
  (2)barber 进程
  首先将该理发师的编号压入队列,供顾客提取。等待顾客坐到理发椅坐好(信号量customer_ready),开始理发,理发结束后释放结束信号(finished[i])。等待顾客离开理发椅(leave_barberchair)(期间去收银台进行收款活动),释放理发椅空闲信号(barber_chair),等待下一位顾客坐上来。
  (3)cash(收银台)进程
  等待顾客付款(payment),执行收款操作,收款操作结束,给付收据(receipt)。
  信号量总表:
  信号量 wait signal
  stand_capacity 顾客等待进入理发店 顾客离开站席区
  sofa 顾客等待坐到沙发 顾客离开沙发
  barber_chair 顾客等待空理发椅 理发师释放空理发椅
  customer_ready 理发师等待,直到一个顾客坐到理发椅顾客坐到理发椅上,给理发师发出信号mutex 等待理发师空闲,执行理发或收款操作理发师执行理发或收款结束,进入空闲状态mutex1 执行入队或出队等待 入队或出队结束,释放信号finished[i] 顾客等待对应编号理发师理发结束;理发师理发结束,释放信号leave_barberchair 理发师等待顾客离开理发椅 顾客付款完毕得到收据,离开理发椅释放信号payment 收银员等待顾客付款 顾客付款,发出信号receipt 顾客等待收银员收、开具收据收银员收款结束、开具收据,释放信号


  伪码:
  semaphore stand_capacity=5;
  semaphore sofa=4;
  semaphore barber_chair=3;
  semaphore customer_ready=0;
  semaphore mutex=3;
  semaphore mutex1=1;
  semaphore finished[3]={0,0,0};
  semaphore leave_barberchair=0;
  semaphore payment=0;
  semaphore receipt=0;
  void customer()
  {
  int barber_number;
  wait(stand_capacity); //等待进入理发店
  enter_room(); //进入理发店
  wait(sofa); //等待沙发
  leave_stand_section(); //离开站席区
  signal(stand_capacity);
  sit_on_sofa(); //坐在沙发上
  wait(barber_chair); //等待理发椅
  get_up_sofa(); //离开沙发
  signal(sofa);
  wait(mutex1);
  sit_on_barberchair(); //坐到理发椅上
  signal(customer_ready);
  barber_number=dequeue(); //得到理发师编号
  signal(mutex1);
  wait(finished[barber_number]); //等待理发结束
  pay(); //付款
  signal(payment); //付款
  wait(receipt); //等待收据
  get_up_barberchair(); //离开理发椅
  signal(leave_barberchair); //发出离开理发椅信号
  exit_shop(); //了离开理发店
  }
  void barber(int i)
  {
  while(true)
  {
  wait(mutex1);
  enqueue(i); //将该理发师的编号加入队列
  signal(mutex1);
  wait(customer_ready); //等待顾客准备好
  wait(mutex);
  cut_hair(); //理发
  signal(mutex);
  signal(finished[i]); //理发结束
  wait(leave_barberchair); //等待顾客离开理发椅信号
  signal(barber_chair); //释放barber_chair 信号
  }
  }
  void cash() //收银
  {
  while(true)
  {
  wait(payment); //等待顾客付款
  wait(mutex); //原子操作
  get_pay(); //接受付款
  give_receipt(); //给顾客收据
  signal(mutex);
  signal(receipt); //收银完毕,释放信号
  }
  }


  分析:
  在分析该问题过程中,出现若干问题,是参阅相关资料后才认识到这些问题的隐蔽性和严重性的,主要包括:
  (1)在顾客进程,如果是在释放leave_barberchair 信号之后进行付款动作的话,很容易造成没有收银员为其收款的情形, 原因是: 为该顾客理发的理发师收到leave_barberchair 信号后,释放barber_chair 信号,另外一名顾客坐到理发椅上,该理发师有可能为这另外一名顾客理发,而没有为刚理完发的顾客收款。为解决这个问题,就是采取在释放leave_barberchair 信号之前,完成付款操作。这样该理发师无法进入下一轮循环为另外顾客服务,只能到收银台收款。
  (2)本算法是通过给理发师编号的方式,当顾客坐到某理发椅上也同时获得理发师的编号,如此,当该理发师理发结束,释放信号,顾客只有接收到为其理发的理发师的理发结束信号才会进行付款等操作。这样实现,是为避免这样的错误,即:如果仅用一个finished 信号量的话,很容易出现别的理发师理发完毕释放了finished 信号,把正在理发的这位顾客赶去付款,而已经理完发的顾客却被阻塞在理发椅上的情形。当然也可以为顾客进行编号,让理发师获取他理发的顾客的编号,但这样就会限制顾客的数量,因为finished[]数组不能是无限的。而为理发师编号,则只需要三个元素即可。

2018-11-08 14:16:57 congjichukaishi 阅读数 255

如果你不了解信号和PV操作,可以看我上篇博客,这篇主要是实现同步互斥。

场景:当一个进程和另一个进程在同时使用一个临界资源时,会变得错乱,所以我们需要通过信号量的PV操作,来加同步互斥。

前言:1操作系统是通过数组来管理信号量的数量的。

           2,P操作,是对信号量进行减减,V操作是对信号进行加加,(当信号量小于0时,会等待,这就是同步)。

          3.当信号量的数为1时,我们可以实现互斥(先给一个进程进行P操作,结束后进行V操作),这样就达到了互斥。

          4.消费者模型,让篇博客里有,很全面

具体:fork出两个进程,让它们同时在显示器输出,当他们是成对出现的时候,就很好的实现了同步与互斥。

头文件:

#pragma once 
#include <iostream>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <unistd.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/wait.h>
using namespace std;

#define PATHNAME "."
#define PROJ_ID 0x6666
union semun
{
  int val; //value for SERVAL
  struct semid_ds *but; //Buffer for IPC_STAT,IPC_SET
  unsigned short *array;  //Array for GETALL,SERALL
  struct seminfo *_buf; //Buffer for IPC_INFO
};
int createSemSet(int nums);
int initSem(int semid,int nums,int initVal);
int getSemSet(int nums);
int P(int semid,int who);
int V(int semid ,int who);
int destroySemSet(int semid);

函数实现文件:

#include"comm.h"
using namespace std;
static int commSemSet(int nums,int flags)
{
  key_t key = ftok(PATHNAME,PROJ_ID);
  if(key < 0)
  {
    perror("ftok");
    exit(-1);
  }
  int semid  = semget(key,nums,flags);
  if(semid < 0)
  {
    perror("semget");
    exit(-1);
  }
  return semid;
}
int createSemSet(int nums)
{
  int semmid = commSemSet(nums,IPC_CREAT|IPC_EXCL|06666);
  return semmid;
}
int initSem(int semid,int nums,int initVal)
{
 union semun _un;
 _un.val = initVal;
 if(semctl(semid,nums,SETVAL,_un)< 0)
 {
    perror("semctl");
    return -3;
 } 
     return 0;
}
int getSemSet(int nums)
{
  return commSemSet(nums,IPC_CREAT);
}
static int commPV(int semid,int who,int op)
{
  struct sembuf _sf;
  _sf.sem_num = who;
  _sf.sem_op = op;
  _sf.sem_flg = 0;
  if(semop(semid,&_sf,1) < 0)
  {
    perror("semop");
    return -1;
  }
  return 0;
}
int P(int semid,int who)
{
   return commPV(semid,who,-1);
}
int V(int semid ,int who)
{
 return commPV(semid,who,1);
}
int destroySemSet(int semid)
{

  if(semctl(semid,0,IPC_RMID) < 0)
  {
    perror("semctl");
    exit(-1);
  }
  return 0;
}

测试文件:

#include"comm.h"
int main()
{
  int semid = createSemSet(1);
  initSem(semid,0,1);
  pid_t id = fork();
  if(id == 0)
  {
    //int  _semid = getSemSet(0);
    while(1)
    {
      P(semid,0);
      cout << "我是子进程,我正在用显示器";
      fflush(stdout);
      cout <<endl;
      sleep(2);
      cout << "我已经用完了";
      fflush(stdout);
      cout << endl;
      V(semid,0);
 
    }
  } else 
    {
      while(1)
      {
      P(semid,0);
      cout << "我是父进程,我正在用显示器";
      fflush(stdout);
      cout << endl;
      sleep(3);
      cout << "我已经用完了";
      fflush(stdout);
      cout << endl;
       V(semid,0);
    }
      wait(NULL);
  }
        destroySemSet(semid);
         return 0;

}

另外这是我的Makefile:

	test:comm.cpp comm.h test_sem.cpp
	g++ -o $@ $^
.PHONY:clean
clean:
	rm -f test

 

PV操作例题(转)

阅读数 609

没有更多推荐了,返回首页