PV原语小结

原稿链接:http://blog.csdn.net/ppooqq/archive/2006/07/28/994849.aspx

 

     PV原语通过操作信号量来拍卖过程间的一路与排斥的题目。其主导就是一
段不可分割不可中断的主次。

信号量的定义1965年由著名的荷兰王国电脑数学家Dijkstra提议,其基本思路是用一种新的变量类型(semaphore)来记录当前可用资源的数额。有两种实现格局:1)semaphore的取值必须高于或等于0。0表示近年来已没有空闲资源,而正数表示目前有空资源的数量;2)semaphore的取值可正可负,负数的断然值表示正在等候进入临界区的过程个
数。

信号量是由操作系统来保障的,用户进程只可以通过起初化和多少个标
准原语(P、V原语)来访问。开端化可指定一个非负整数,即空闲资源总数。

P原语:P是爱沙尼亚语Proberen(测试)的首字母。为阻隔原语,负责把近期经过由运行情形转换
为阻塞状态,直到此外一个历程唤醒它。操作为:申请一个空暇资源(把信号量减1),若成功,则脱离;若失败,则该过程被封堵;

V原语:V是意大利语Verhogen(增添)的首字母。为指示原语,负责把一个被卡住的过程唤醒,
它有一个参数表,存放着等候被唤起的经过信息。操作为:释放一个被占用的资源(把信号量加1),如若发现有被封堵的历程,则接纳一个提醒之。

 

现实PV原语对信号量的操作可以分成两种情状:

1)              把信号量视为一个加锁标志位,实现对一个共享变量的排斥访问。

贯彻过程:

P(mutex);           // mutex的开头值为1

访问该共享数据;

V(mutex);

非临界区

2)              把信号量视为是某系列型的共享资源的结余个数,实现对一类共享资
源的访问。

兑现过程:

P(resource);          //
resource的起首值为该资源的个数N

拔取该资源;

V(resource);

非临界区

3)              把信号量作为进程间的一道工具

落实过程:

临界区C1;   P(S);

V(S);           临界区C2;

 

下边用多少个例证来具体表明:

例1:某商城门口为买主准备了100辆手推车,每位顾客在进入买东西时取一辆推车,在买完东西结完
帐将来再把推车还再次来到。试用P、V操作正确贯彻顾客进程的共同互斥关系。

分析:把手推车视为某种资源,每个顾客为一个要互斥访问该资源的经过。因而那些事例为PV原语的第两种采纳类型。

解:semaphore S_CartNum;   // 空闲的手推车多少,
初值为100

void consumer(void)           //
顾客进程
{
        P(S_CartNum);

        买东西;

        结帐;

        V(S_CartNum);
}

例2:案子上有一个水果盘,每三遍可以往里面放入一个水果。四伯专向
盘子中放苹果,外孙子专等吃盘子中的苹果。把老爹、外孙子当作二个经过,试用P、V操作使这四个过程能正确地涌出执行。

分析:爹爹和外孙子多少个过程并行制约,二叔进程执行完即往盘中放入苹果后,外甥进程才能举办即吃苹果。因而该问
题为经过间的联名问题。

解:semaphore S_PlateNum; // 盘子容量,初值为1

semaphore S_AppleNum;   // 苹
果数量,初值为0

void father( )               
// 父 亲进程
{

    while(1)

    {
        P(S_PlateNum);

        往盘子中放入一个苹果;

        V(S_AppleNum);

    }
}

void son( )   // 外甥进程
{

    while(1)

    {
        P(S_AppleNum);

        从盘中取出苹果;

        V(S_PlateNum);

        吃苹果;

    }
}

另附用PV原语解决进程同步与排斥问题的例证:

经文IPC问题如:生产者-消费者,读者-写者,翻译家就餐,睡着的整容
师等可参占卜关教材。

一、三个过程PA、PB通过五个FIFO(先进先出)缓冲区队列连接(如图)

PA

PB

Q1

Q2

   PA从Q2取消息,处理后往Q1发信息,PB从Q1取信息,处理后往Q2发音信,每个缓冲镇长度等于传送音信长度. Q1队列长度为n,Q2队列长度为m. 假使先导时Q1中装满了音讯,试用P、V操作解决上述进程间通讯问题。

解:// Q1序列当中的悠闲缓
冲区个数,初值为0
semaphore S_BuffNum_Q1;  

// Q2连串当中的空余缓冲区个数,初值为m
semaphore S_BuffNum_Q2;    

// Q1队列当中的音讯数量,初值为n
semaphore S_MessageNum_Q1;

// Q2行列当中的音讯数量,初值为0
semaphore S_MessageNum_Q2;

void PA( )
{

        while(1)

        {
                P(S_MessageNum_Q2);

                从Q2当中取出一条消息;

                V(S_BuffNum_Q2);

                处理信息;

                生成新的音讯;

                P(S_BuffNum_Q1);

                把该音讯发送到Q1当中;

               
V(S_MessageNum_Q1);

        }
}

void PB( )
{

        while(1)

        {
               
P(S_MessageNum_Q1);

                从Q1当中取出一条信息;

                V(S_BuffNum_Q1);

                处理信息;

                生成新的音讯;

                P(S_BuffNum_Q2);

                把该音信发送到Q2当中;

               
V(S_MessageNum_Q2);

        }
}

 

二、《操作系统》课程的期末考试即将举办,假诺把学生和监考老师都看成进程,学生有N人,教授1人。考场门口每回只好进出一个人,进考场的尺度是先来先进。当N个学生都跻身了考场后,助教才能发卷子。学生完成后即可离开考
场,而老师要等收上来全体试卷并封装卷子后才能离开考场。

(1)问共需安装多少个经过?

(2)请用P、V操作解决上述问题中的同步和排斥关系。

解:semaphore S_Door;          // 能否进出门,初值1

semaphore S_StudentReady;    //
学生是否到齐,初值为0

semaphore S_ExamBegin;   // 起头试验,初值为0

semaphore S_ExamOver;    // 考试完毕,初值为0

int nStudentNum = 0;          //
学生数量

semaphore S_Mutex1        
//互斥信号量,初值为1

int nPaperNum = 0;       // 已交的卷子数目

semaphore S_Mutex2        
//互斥信号量,初值为1

void student( )
{

        P(S_Door);

        进门;
        V(S_Door);

        P(S_Mutex1);

        nStudentNum ++;         //
增加学生的个数

        if(nStudentNum ==
N) V(S_StudentReady);

        V(S_Mutex1);

        P(S_ExamBegin);         //
等导师发布考试开头

        考试中…

        交卷;

P(S_Mutex2);

        nPaperNum ++;      //
扩展试卷的份数

        if(nPaperNum ==
N) V(S_ExamOver);

        V(S_Mutex2);

        P(S_Door);

        出门;

        V(S_Door);

}

void teacher( )
{

        P(S_Door);

        进门;
        V(S_Door);

        P(S_StudentReady);//等待最后一个学员来唤醒

        发卷子;

        for(i = 1; i <= N; i++)   
V(S_ExamBegin);

        P(S_ExamOver);         //
等待考试截止

        封装试卷;

        P(S_Door);

        出门;
        V(S_Door);

}

 

三、某商行有二种食品A和B,最大数额均为m个。 该商厦将A、B二种食品搭配出售,每趟各取一个。为制止食品变质,服从先到食
品先出售的准绳。有两个食品商店分别不断地供应A、B二种食品(每一次一个)。为力保健康销售,当某种食物的数据比另一种的数量超过k(k<m)个时,暂停对数码大的食物采购,补充数量少的食品。

(1) 问共需安装几个经过?

(2) 用P、V操作解决上述问题中的同步互斥关系。

解:semaphore S_BuffNum_A; //A的缓冲区个数, 初值m

semaphore S_Num_A;         // A的个数,初值为0

semaphore S_BuffNum_B; //B的缓冲区个数, 初值m

semaphore S_Num_B;         // B的个数,初值为0

void Shop( )
{

        while(1)

        {
               
P(S_Num_A);

                P(S_Num_B);

                分别取出A、B食品各一个;

                V(S_BuffNum_A);

                V(S_BuffNum_A);

                搭配地销售这一对食物;

        }
}

// “A食品加1,而B食品不变”这种景色允许出现的次数(许可证的多少),其值等于//k-(A-B),初值为k

semaphore S_A_B;

// “B食品加1,而A食品不变”这种状态允许出现的次数(许可证的数码),其值等于//k-(B-A),初值为k

semaphore S_B_A;

void Producer_A ( )
{

        while(1)

        {
                生产一个A食品;

               
P(S_BuffNum_A);

                P(S_A_B);

                向公司提供一个A食品;

                V(S_Num_A);

                V(S_B_A);

        }
}

void Producer_B ( )
{

        while(1)

        {
                生产一个B食品;

               
P(S_BuffNum_B);

                P(S_B_A);

                向商店提供一个B食品;

                V(S_Num_B);

                V(S_A_B);

        }
}

四:在一栋学生公寓里,唯有一间浴室,而且这间浴室万分小,每三回只好容纳一个人。公寓里既住着男生也住着女子,他们只能分享这间浴室。由此,楼长制定了以下的澡堂使用规则:(1)每几遍只好有一个人在使用;(2)女孩子的先行级要压倒男生,即只要还要有男生和女人在等待使用
浴室,则女孩子优先;(3)对于同一性其它人来说,接纳先来先拔取的基准。

假设:

(1)当一个男生想要使用浴室时,他会去实践一个函数boy_wants_to_use_bathroom,当他相差浴室时,也会去实施其余一个函数boy_leaves_bathroom;

(2)当一个女子想要使用浴室时,会去执行函数girl_wants_to_use_bathroom,当他相差时, 也会进行函数girl_leaves_bathroom;

题目:请用信号量和P、V操作来实现这六个函数(初步状态:浴室是空的)。

解:信号量的概念:

semaphore S_mutex;     // 互斥信号量,初值均为1

semaphore S_boys; // 男生等待队列,初值为0

semaphore S_girls;   // 女孩子等待队列,初值为0

通常变量的定义:

int boys_waiting = 0;     //
正在等候的男生数;

int girls_waiting = 0; // 正在等候的女子数;

int using = 0;      // 当前是不是有人在利用浴室;

void boy_wants_to_use_bathroom ( )
{

        P(S_mutex);

        if((using == 0) &&
(girls_waiting == 0))

         {

                using = 1;

                V(S_mutex);

         }

        else

         {

                boys_waiting ++;

                V(S_mutex);

                P(S_boys);

         }

}

void boy_leaves_bathroom ( )
{

        P(S_mutex);

        if(girls_waiting > 0) //
优先唤醒女人

         {

                girls_waiting –;

                V(S_girls);

         }

       
else if(boys_waiting > 0)

         {

伟德国际1946手机版下载,                boys_waiting –;

                V(S_ boys);

         }

        else    using = 0;         //
无人在等候

        V(S_mutex);

}

void girl_wants_to_use_bathroom ( )
{

        P(S_mutex);

        if(using == 0)

         {

                using = 1;

                V(S_mutex);

         }

        else

         {

                girls_waiting ++;

                V(S_mutex);

                P(S_girls);

         }

}

void girl_leaves_bathroom ( )
{

        P(S_mutex);

        if(girls_waiting > 0) //
优先唤醒女子

         {

                girls_waiting –;

                V(S_girls);

         }

       
else if(boys_waiting > 0)

         {

                boys_waiting –;

                V(S_ boys);

         }

        else    using = 0;         //
无人在等待

        V(S_mutex);

}

相关文章